Line data    Source code

       1             : /*
       2             :  * STX B+ Tree Test Suite v0.9
       3             :  * Copyright (C) 2008-2013 Timo Bingmann
       4             :  *
       5             :  * This program is free software: you can redistribute it and/or modify it
       6             :  * under the terms of the GNU General Public License as published by the Free
       7             :  * Software Foundation, either version 3 of the License, or (at your option)
       8             :  * any later version.
       9             :  *
      10             :  * This program is distributed in the hope that it will be useful, but WITHOUT
      11             :  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      12             :  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
      13             :  * more details.
      14             :  *
      15             :  * You should have received a copy of the GNU General Public License along with
      16             :  * this program. If not, see <http://www.gnu.org/licenses/>.
      17             :  */
      18             : 
      19             : #include "tpunit.h"
      20             : 
      21             : #include <stdlib.h>
      22             : 
      23             : #include <stx/btree_multiset.h>
      24             : 
      25             : struct StructureTest : public tpunit::TestFixture
      26             : {
      27           1 :     StructureTest() : tpunit::TestFixture(
      28             :         TEST(StructureTest::test_insert_erase)
      29           1 :         )
      30           1 :     {}
      31             : 
      32             :     struct testdata
      33             :     {
      34             :         unsigned int a, b;
      35             : 
      36             :         // required by the btree
      37       73924 :         testdata()
      38       73924 :             : a(0), b(0)
      39             :         {
      40       73924 :         }
      41             : 
      42             :         // also used as implicit conversion constructor
      43         640 :         inline testdata(unsigned int _a)
      44         640 :             : a(_a), b(0)
      45             :         {
      46         640 :         }
      47             :     };
      48             : 
      49             :     struct testcomp
      50             :     {
      51             :         unsigned int somevalue;
      52             : 
      53           1 :         inline testcomp(unsigned int sv)
      54           1 :             : somevalue(sv)
      55             :         {
      56           1 :         }
      57             : 
      58      397156 :         bool operator()(const struct testdata &a, const struct testdata &b) const
      59             :         {
      60      397156 :             return a.a > b.a;
      61             :         }
      62             :     };
      63             : 
      64             :     template <typename KeyType>
      65             :     struct traits_nodebug : stx::btree_default_set_traits<KeyType>
      66             :     {
      67             :         static const bool       selfverify = true;
      68             :         static const bool       debug = false;
      69             : 
      70             :         static const int        leafslots = 8;
      71             :         static const int        innerslots = 8;
      72             :     };
      73             : 
      74           1 :     void test_insert_erase()
      75             :     {
      76             :         typedef stx::btree_multiset<struct testdata, struct testcomp,
      77             :             struct traits_nodebug<struct testdata> > btree_type;
      78             : 
      79           1 :         btree_type bt( testcomp(42) );
      80             : 
      81           1 :         srand(34234235);
      82         321 :         for(unsigned int i = 0; i < 320; i++)
      83             :         {
      84         320 :             ASSERT(bt.size() == i);
      85         320 :             bt.insert(rand() % 100);
      86         320 :             ASSERT(bt.size() == i + 1);
      87             :         }
      88             : 
      89           1 :         srand(34234235);
      90         321 :         for(unsigned int i = 0; i < 320; i++)
      91             :         {
      92         320 :             ASSERT(bt.size() == 320 - i);
      93         320 :             ASSERT( bt.erase_one(rand() % 100) );
      94         320 :             ASSERT(bt.size() == 320 - i - 1);
      95           1 :         }
      96             :     }
      97             : 
      98           1 : } __StructureTest;
      99             : 
     100             : inline std::ostream& operator<< (std::ostream &o, const struct StructureTest::testdata &t)
     101             : {
     102             :     return o << t.a;
     103           3 : }