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             : #include <vector>
      23             : 
      24             : #include <stx/btree_multiset.h>
      25             : #include <stx/btree_multimap.h>
      26             : #include <stx/btree_map.h>
      27             : 
      28             : struct BulkLoadTest : public tpunit::TestFixture
      29             : {
      30           1 :     BulkLoadTest() : tpunit::TestFixture(
      31             :         TEST(BulkLoadTest::test_set),
      32             :         TEST(BulkLoadTest::test_map)
      33           1 :         )
      34           1 :     {}
      35             : 
      36             :     template <typename KeyType>
      37             :     struct traits_nodebug : stx::btree_default_set_traits<KeyType>
      38             :     {
      39             :         static const bool       selfverify = true;
      40             :         static const bool       debug = false;
      41             : 
      42             :         static const int        leafslots = 8;
      43             :         static const int        innerslots = 8;
      44             :     };
      45             : 
      46        3197 :     void test_set_instance(size_t numkeys, unsigned int mod)
      47             :     {
      48             :         typedef stx::btree_multiset<unsigned int,
      49             :             std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
      50             : 
      51        3197 :         std::vector<unsigned int> keys (numkeys);
      52             : 
      53        3197 :         srand(34234235);
      54     5303227 :         for(unsigned int i = 0; i < numkeys; i++)
      55             :         {
      56     5300030 :             keys[i] = rand() % mod;
      57             :         }
      58             : 
      59        3197 :         std::sort(keys.begin(), keys.end());
      60             : 
      61        3197 :         btree_type bt;
      62        3197 :         bt.bulk_load(keys.begin(), keys.end());
      63             : 
      64        3197 :         unsigned int i = 0;
      65    10606454 :         for(btree_type::iterator it = bt.begin();
      66     5303227 :             it != bt.end(); ++it, ++i)
      67             :         {
      68     5300030 :             ASSERT( *it == keys[i]  );
      69        3197 :         }
      70             :     }
      71             : 
      72           1 :     void test_set()
      73             :     {
      74        3195 :         for (size_t n = 6; n < 3200; ++n)
      75        3194 :             test_set_instance(n, 1000);
      76             : 
      77           1 :         test_set_instance(31996, 10000);
      78           1 :         test_set_instance(32000, 10000);
      79           1 :         test_set_instance(117649, 100000);
      80           1 :     }
      81             : 
      82        3197 :     void test_map_instance(size_t numkeys, unsigned int mod)
      83             :     {
      84             :         typedef stx::btree_multimap<int, std::string,
      85             :             std::less<unsigned int>, traits_nodebug<unsigned int> > btree_type;
      86             : 
      87        3197 :         std::vector< std::pair<int,std::string> > pairs (numkeys);
      88             : 
      89        3197 :         srand(34234235);
      90     5303227 :         for(unsigned int i = 0; i < numkeys; i++)
      91             :         {
      92     5300030 :             pairs[i].first = rand() % mod;
      93     5300030 :             pairs[i].second = "key";
      94             :         }
      95             : 
      96        3197 :         std::sort(pairs.begin(), pairs.end());
      97             : 
      98        3197 :         btree_type bt;
      99        3197 :         bt.bulk_load(pairs.begin(), pairs.end());
     100             : 
     101        3197 :         unsigned int i = 0;
     102    15909681 :         for(btree_type::iterator it = bt.begin();
     103    10606454 :             it != bt.end(); ++it, ++i)
     104             :         {
     105     5300030 :             ASSERT( *it == pairs[i]  );
     106        3197 :         }
     107             :     }
     108             : 
     109           1 :     void test_map()
     110             :     {
     111        3195 :         for (size_t n = 6; n < 3200; ++n)
     112        3194 :             test_map_instance(n, 1000);
     113             : 
     114           1 :         test_map_instance(31996, 10000);
     115           1 :         test_map_instance(32000, 10000);
     116           1 :         test_map_instance(117649, 100000);
     117           1 :     }
     118             : 
     119           3 : } __BulkLoadTest;