LCOV - code coverage report
Current view: top level - testsuite - SimpleTest.cc (source / functions) Hit Total Coverage
Test: STX B+ Tree Testsuite Lines: 98 98 100.0 %
Date: 2011-05-18 Functions: 14 15 93.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 33 42 78.6 %

           Branch data     Line data    Source code
       1                 :            : // $Id: SimpleTest.cc 128 2011-05-18 07:23:35Z tb $
       2                 :            : 
       3                 :            : /*
       4                 :            :  * STX B+ Tree Template Classes v0.8.6
       5                 :            :  * Copyright (C) 2008-2011 Timo Bingmann
       6                 :            :  *
       7                 :            :  * This library is free software; you can redistribute it and/or modify it
       8                 :            :  * under the terms of the GNU Lesser General Public License as published by the
       9                 :            :  * Free Software Foundation; either version 2.1 of the License, or (at your
      10                 :            :  * option) any later version.
      11                 :            :  *
      12                 :            :  * This library is distributed in the hope that it will be useful, but WITHOUT
      13                 :            :  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            :  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
      15                 :            :  * for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU Lesser General Public License
      18                 :            :  * along with this library; if not, write to the Free Software Foundation,
      19                 :            :  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <cppunit/extensions/HelperMacros.h>
      23                 :            : 
      24                 :            : #include <stdlib.h>
      25                 :            : 
      26                 :            : #include <stx/btree_multiset.h>
      27                 :            : #include <stx/btree_multimap.h>
      28                 :            : #include <stx/btree_map.h>
      29                 :            : 
      30                 :            : class SimpleTest : public CPPUNIT_NS::TestFixture
      31 [ +  - ][ #  # ]:         14 : {
      32 [ +  - ][ +  - ]:          2 :     CPPUNIT_TEST_SUITE( SimpleTest );
                 [ #  # ]
      33                 :          1 :     CPPUNIT_TEST(test_empty);
      34                 :          1 :     CPPUNIT_TEST(test_set_insert_erase_320);
      35                 :          1 :     CPPUNIT_TEST(test_set_insert_erase_320_descending);
      36                 :          1 :     CPPUNIT_TEST(test_map_insert_erase_320);
      37                 :          1 :     CPPUNIT_TEST(test_map_insert_erase_320_descending);
      38                 :          1 :     CPPUNIT_TEST(test2_map_insert_erase_strings);
      39                 :          1 :     CPPUNIT_TEST(test_set_100000_uint64);
      40                 :          2 :     CPPUNIT_TEST_SUITE_END();
      41                 :            : 
      42                 :            : protected:
      43                 :            : 
      44                 :            :     struct traits_nodebug
      45                 :            :     {
      46                 :            :         static const bool       selfverify = true;
      47                 :            :         static const bool       debug = false;
      48                 :            : 
      49                 :            :         static const int        leafslots = 8;
      50                 :            :         static const int        innerslots = 8;
      51                 :            :     };
      52                 :            : 
      53                 :          1 :     void test_empty()
      54                 :            :     {
      55                 :            :         typedef stx::btree_multiset<unsigned int,
      56                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
      57                 :            : 
      58                 :          1 :         btree_type bt, bt2;
      59                 :          1 :         bt.verify();
      60                 :            : 
      61                 :          1 :         CPPUNIT_ASSERT( bt.erase(42) == false );
      62                 :            : 
      63                 :          1 :         CPPUNIT_ASSERT( bt == bt2 );
      64                 :          1 :     }
      65                 :            : 
      66                 :          1 :     void test_set_insert_erase_320()
      67                 :            :     {
      68                 :            :         typedef stx::btree_multiset<unsigned int,
      69                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
      70                 :            : 
      71                 :          1 :         btree_type bt;
      72                 :          1 :         bt.verify();
      73                 :            : 
      74                 :          1 :         srand(34234235);
      75         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
      76                 :            :         {
      77                 :        320 :             CPPUNIT_ASSERT(bt.size() == i);
      78                 :        320 :             bt.insert(rand() % 100);
      79                 :        320 :             CPPUNIT_ASSERT(bt.size() == i + 1);
      80                 :            :         }
      81                 :            : 
      82                 :          1 :         srand(34234235);
      83         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
      84                 :            :         {
      85                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i);
      86                 :        320 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
      87                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
      88                 :            :         }
      89                 :            : 
      90                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
      91                 :          1 :     }
      92                 :            : 
      93                 :          1 :     void test_set_insert_erase_320_descending()
      94                 :            :     {
      95                 :            :         typedef stx::btree_multiset<unsigned int,
      96                 :            :             std::greater<unsigned int>, struct traits_nodebug> btree_type;
      97                 :            : 
      98                 :          1 :         btree_type bt;
      99                 :            : 
     100                 :          1 :         srand(34234235);
     101         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     102                 :            :         {
     103                 :        320 :             CPPUNIT_ASSERT(bt.size() == i);
     104                 :        320 :             bt.insert(rand() % 100);
     105                 :        320 :             CPPUNIT_ASSERT(bt.size() == i + 1);
     106                 :            :         }
     107                 :            : 
     108                 :          1 :         srand(34234235);
     109         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     110                 :            :         {
     111                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i);
     112                 :        320 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
     113                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
     114                 :            :         }
     115                 :            : 
     116                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
     117                 :          1 :     }
     118                 :            : 
     119                 :          1 :     void test_map_insert_erase_320()
     120                 :            :     {
     121                 :            :         typedef stx::btree_multimap<unsigned int, std::string,
     122                 :            :             std::less<unsigned int>, struct traits_nodebug> btree_type;
     123                 :            : 
     124                 :          1 :         btree_type bt;
     125                 :            : 
     126                 :          1 :         srand(34234235);
     127         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     128                 :            :         {
     129                 :        320 :             CPPUNIT_ASSERT(bt.size() == i);
     130                 :        320 :             bt.insert2(rand() % 100, "101");
     131                 :        320 :             CPPUNIT_ASSERT(bt.size() == i + 1);
     132                 :            :         }
     133                 :            : 
     134                 :          1 :         srand(34234235);
     135         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     136                 :            :         {
     137                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i);
     138                 :        320 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
     139                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
     140                 :            :         }
     141                 :            : 
     142                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
     143                 :          1 :         bt.verify();
     144                 :          1 :     }
     145                 :            : 
     146                 :          1 :     void test_map_insert_erase_320_descending()
     147                 :            :     {
     148                 :            :         typedef stx::btree_multimap<unsigned int, std::string,
     149                 :            :             std::greater<unsigned int>, struct traits_nodebug> btree_type;
     150                 :            : 
     151                 :          1 :         btree_type bt;
     152                 :            : 
     153                 :          1 :         srand(34234235);
     154         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     155                 :            :         {
     156                 :        320 :             CPPUNIT_ASSERT(bt.size() == i);
     157                 :        320 :             bt.insert2(rand() % 100, "101");
     158                 :        320 :             CPPUNIT_ASSERT(bt.size() == i + 1);
     159                 :            :         }
     160                 :            : 
     161                 :          1 :         srand(34234235);
     162         [ +  + ]:        321 :         for(unsigned int i = 0; i < 320; i++)
     163                 :            :         {
     164                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i);
     165                 :        320 :             CPPUNIT_ASSERT( bt.erase_one(rand() % 100) );
     166                 :        320 :             CPPUNIT_ASSERT(bt.size() == 320 - i - 1);
     167                 :            :         }
     168                 :            : 
     169                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
     170                 :          1 :         bt.verify();
     171                 :          1 :     }
     172                 :            : 
     173                 :          1 :     void test2_map_insert_erase_strings()
     174                 :            :     {
     175                 :            :         typedef stx::btree_multimap<std::string, unsigned int,
     176                 :            :             std::less<std::string>, struct traits_nodebug> btree_type;
     177                 :            : 
     178                 :          1 :         std::string letters = "abcdefghijklmnopqrstuvwxyz";
     179                 :            : 
     180                 :          1 :         btree_type bt;
     181                 :            : 
     182         [ +  + ]:         27 :         for(unsigned int a = 0; a < letters.size(); ++a)
     183                 :            :         {
     184         [ +  + ]:        702 :             for(unsigned int b = 0; b < letters.size(); ++b)
     185                 :            :             {
     186                 :            :                 bt.insert2(std::string(1, letters[a]) + letters[b],
     187                 :        676 :                            a * letters.size() + b);
     188                 :            :             }
     189                 :            :         }
     190                 :            : 
     191         [ +  + ]:         27 :         for(unsigned int b = 0; b < letters.size(); ++b)
     192                 :            :         {
     193         [ +  + ]:        702 :             for(unsigned int a = 0; a < letters.size(); ++a)
     194                 :            :             {
     195                 :        676 :                 std::string key = std::string(1, letters[a]) + letters[b];
     196                 :            : 
     197                 :        676 :                 CPPUNIT_ASSERT( bt.find(key)->second == a * letters.size() + b );
     198                 :        676 :                 CPPUNIT_ASSERT( bt.erase_one(key) );
     199                 :            :             }
     200                 :            :         }
     201                 :            : 
     202                 :          1 :         CPPUNIT_ASSERT( bt.empty() );
     203                 :          1 :         bt.verify();
     204                 :          1 :     }
     205                 :            : 
     206                 :            :     typedef unsigned char uint8_t;
     207                 :            :     typedef unsigned long long uint64_t;
     208                 :            : 
     209                 :          1 :     void test_set_100000_uint64()
     210                 :            :     {
     211                 :          1 :         stx::btree_map<uint64_t, uint8_t> bt;
     212                 :            : 
     213         [ +  + ]:      99991 :         for(uint64_t i = 10; i < 100000; ++i)
     214                 :            :         {
     215                 :      99990 :             uint64_t key = i % 1000;
     216                 :            : 
     217         [ +  + ]:      99990 :             if (bt.find(key) == bt.end())
     218                 :            :             {
     219                 :       1000 :                 bt.insert( std::make_pair(key, key % 100) );
     220                 :            :             }
     221                 :            :         }
     222                 :            : 
     223                 :          1 :         CPPUNIT_ASSERT( bt.size() == 1000 );
     224                 :          1 :     }
     225                 :            : };
     226                 :            : 
     227 [ +  - ][ +  - ]:          3 : CPPUNIT_TEST_SUITE_REGISTRATION( SimpleTest );

Generated by: LCOV version 1.9