git.cworth.org Git - vogl/blob - src/voglcore/vogl_map.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_map.cpp
  28 #include "vogl_core.h"
  29 #include "vogl_map.h"
  30
  31 #define VOGL_MAP_COMPARATIVE_PERF_TESTING
  32
  33 #ifdef VOGL_MAP_COMPARATIVE_PERF_TESTING
  34 #include <map>
  35 #include "vogl_hash_map.h"
  36 //#include "vogl_treap.h"
  37 //#include "vogl_avltree.h"
  38 #endif
  39
  40 namespace vogl
  41 {
  42     bool map_test()
  43     {
  44         typedef vogl::map<int, vogl::vector<dynamic_string> > int_to_string_vec_map;
  45         int_to_string_vec_map blah;
  46         if (blah.contains(0))
  47             return false;
  48         for (uint i = 0; i < 100; i++)
  49         {
  50             vogl::vector<dynamic_string> v;
  51             v.push_back(dynamic_string(cVarArg, "hello %u", i));
  52             v.push_back(dynamic_string(cVarArg, "blah %u", i));
  53             blah.insert(i, v);
  54         }
  55
  56         if (blah.contains(cINT32_MAX))
  57             return false;
  58
  59         for (int_to_string_vec_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
  60         {
  61             if (!blah.contains(it->first))
  62                 return false;
  63
  64             printf("%u:\n", it->first);
  65             for (uint i = 0; i < it->second.size(); i++)
  66             {
  67                 printf("%s\n", it->second[i].get_ptr());
  68             }
  69         }
  70
  71         int_to_string_vec_map blah2(blah);
  72         if (blah2 != blah)
  73             return false;
  74         blah2 = blah;
  75         if (!blah2.debug_check())
  76             return false;
  77         if (blah2 != blah)
  78             return false;
  79
  80         if (!blah.debug_check())
  81             return false;
  82         blah.print_debug_info();
  83         blah.reset();
  84         if (!blah.debug_check())
  85             return false;
  86         blah.print_debug_info();
  87
  88         fast_random frm;
  89         frm.seed(5556);
  90
  91         typedef vogl::map<int> int_map;
  92
  93         int_map z;
  94
  95         for (uint i = 0; i < 10000; i++)
  96             z.insert_multi(frm.irand(0, 5000));
  97
  98         z.reset();
  99
 100         for (uint i = 0; i < 10000; i++)
 101             z.insert_multi(frm.irand(0, 5000));
 102
 103         int_map z1;
 104
 105         z1.unite_multi(z);
 106         if (z1 != z)
 107             return false;
 108
 109         int_map z2;
 110         z1.swap(z2);
 111         if (z1 == z)
 112             return false;
 113         if (z2 != z)
 114             return false;
 115
 116         if (!z2.debug_check())
 117             return false;
 118         while (z2.size())
 119         {
 120             int x = z2.begin()->first;
 121
 122             z2.erase_all(z2.begin()->first);
 123
 124             if (z2.size())
 125             {
 126                 if (z2.begin()->first == x)
 127                     return false;
 128             }
 129
 130             if (!z2.debug_check())
 131                 return false;
 132         }
 133         if (z2.size())
 134             return false;
 135
 136         for (uint i = 0; i < 1000; i++)
 137         {
 138             int l = frm.irand(0, 5000);
 139             int h = frm.irand(0, 5000);
 140             if (l > h)
 141                 std::swap(l, h);
 142
 143             printf("%i %i\n", l, h);
 144
 145             std::pair<int_map::iterator, int_map::iterator> p(z.equal_range(l));
 146             uint cnt = z.count(l);
 147             if (!cnt)
 148             {
 149                 if ((p.first != z.end()) || (p.second != z.end()))
 150                     return false;
 151             }
 152             else
 153             {
 154                 uint u = 0;
 155                 int_map::const_iterator it(p.first);
 156                 while (it != p.second)
 157                 {
 158                     u++;
 159                     ++it;
 160                 }
 161                 if (u != cnt)
 162                     return false;
 163             }
 164
 165             vogl::vector<int> uk;
 166             z.get_unique_keys(uk);
 167
 168             int_map tst;
 169             for (uint i = 0; i < uk.size(); i++)
 170             {
 171                 if (!tst.insert(uk[i]).second)
 172                     return false;
 173             }
 174             if (!tst.debug_check())
 175                 return false;
 176
 177             int_map::iterator nl_it(z.lower_bound(l));
 178             VOGL_NOTE_UNUSED(nl_it);
 179             int_map::iterator nh_it(z.upper_bound(h));
 180             VOGL_NOTE_UNUSED(nh_it);
 181
 182             int_map::const_iterator l_it(z.lower_bound(l));
 183             int_map::const_iterator h_it(z.upper_bound(h));
 184
 185             uint n = 0;
 186             for (int_map::const_iterator it = l_it; it != h_it; it++)
 187             {
 188                 if ((it->first < l) || (it->first > h))
 189                     return false;
 190                 n++;
 191             }
 192
 193             uint cn = 0;
 194             for (int_map::const_iterator it = z.begin(); it != z.end(); ++it)
 195                 if ((it->first >= l) && (it->first <= h))
 196                     cn++;
 197
 198             if (n != cn)
 199                 return false;
 200         }
 201
 202         int_map set_test;
 203
 204         for (uint i = 0; i < 1000; i++)
 205             set_test.insert_multi(frm.irand(0, 100));
 206
 207         for (int_map::const_iterator it = set_test.begin(); it != set_test.end(); it++)
 208             printf("%i ", it->first);
 209         printf("\n");
 210
 211         if (!set_test.debug_check())
 212             return false;
 213         int_map set_test2(set_test);
 214
 215         if (set_test2 != set_test)
 216             return false;
 217
 218         if (!set_test2.debug_check())
 219             return false;
 220
 221         for (int_map::const_iterator it = set_test2.begin(); it != set_test2.end(); it++)
 222             printf("%i ", it->first);
 223         printf("\n");
 224
 225         for (int_map::iterator it = set_test2.begin(); it != set_test2.end();)
 226         {
 227             if (frm.get_bit())
 228             {
 229                 int_map::iterator next_it = it;
 230                 ++next_it;
 231
 232                 set_test2.erase(it);
 233
 234                 it = next_it;
 235             }
 236             else
 237                 ++it;
 238         }
 239
 240         for (int_map::const_iterator it = set_test2.begin(); it != set_test2.end(); it++)
 241             printf("%i ", it->first);
 242         printf("\n");
 243
 244         if (!set_test2.debug_check())
 245             return false;
 246         set_test2.print_debug_info();
 247
 248         typedef vogl::map<int, int> int_to_int_map;
 249
 250         {
 251             int_to_int_map blah(10);
 252
 253             int_to_int_map::const_iterator it0;
 254             int_to_int_map::const_iterator it1(blah.begin());
 255             int_to_int_map::iterator it2(blah.begin());
 256
 257             it1 = it2;
 258             //it2 = it1;
 259
 260             bool ignored = it1 != it1;
 261             VOGL_NOTE_UNUSED(ignored);
 262             ignored = it2 != it2;
 263             ignored = it1 == it1;
 264             ignored = it2 == it2;
 265
 266             ignored = it1 != it2;
 267             ignored = it2 != it1;
 268
 269             int_to_int_map::const_iterator it3(it1);
 270             VOGL_NOTE_UNUSED(it3);
 271             int_to_int_map::const_iterator it4(it2);
 272             VOGL_NOTE_UNUSED(it4);
 273
 274             blah.insert_multi(0, 100);
 275             blah.insert_multi(0, 101);
 276             blah.insert_multi(1, 200);
 277
 278             if (blah.count(0) != 2)
 279                 return false;
 280
 281             vogl::vector<int> iv;
 282             blah.get_values(0, iv);
 283             if (iv.size() != 2)
 284                 return false;
 285             if ((iv[0] != 101) || (iv[1] != 100))
 286                 return false;
 287
 288             printf("-----\n");
 289             for (int_to_int_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
 290                 printf("%i %i\n", it->first, it->second);
 291             printf("-----\n");
 292
 293             printf("-----\n");
 294             for (int_to_int_map::iterator it = blah.begin(); it != blah.end(); ++it)
 295                 printf("%i %i\n", it->first, it->second);
 296             printf("-----\n");
 297
 298             bool status = blah.debug_check();
 299             if (!status)
 300                 return false;
 301
 302             //blah.erase(0);
 303             blah.erase(blah.begin());
 304             blah.erase(1);
 305
 306             printf("-----\n");
 307             for (int_to_int_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
 308                 printf("%i %i\n", it->first, it->second);
 309             printf("-----\n");
 310
 311             status = blah.debug_check();
 312             if (!status)
 313                 return false;
 314
 315             int_to_int_map blah2(blah);
 316
 317             status = blah2.debug_check();
 318             if (!status)
 319                 return false;
 320
 321             blah2.clear();
 322             status = blah2.debug_check();
 323             if (!status)
 324                 return false;
 325
 326             blah2 = blah;
 327             status = blah2.debug_check();
 328             if (!status)
 329                 return false;
 330
 331             blah2.print_debug_info();
 332         }
 333
 334         {
 335             typedef map<dynamic_string, dynamic_string> string_to_string_map;
 336             string_to_string_map s2s(5);
 337             s2s.insert_multi("Hello", "World");
 338             s2s.insert_multi("Hello", "2");
 339             s2s.insert_multi("Hello", "3");
 340             s2s.insert_multi("Hello", "4");
 341             s2s.insert_multi("Blah", "x");
 342
 343             for (string_to_string_map::const_iterator it = s2s.begin(); it != s2s.end(); it++)
 344             {
 345                 printf("%s %s\n", it->first.get_ptr(), it->second.get_ptr());
 346             }
 347
 348             printf("\n");
 349
 350             if (!s2s.erase("Hello"))
 351                 return false;
 352             if (!s2s.erase("Blah"))
 353                 return false;
 354             if (s2s.erase("ssss"))
 355                 return false;
 356
 357             for (string_to_string_map::const_iterator it = s2s.end(); it != s2s.begin();)
 358             {
 359                 it--;
 360                 printf("%s %s\n", it->first.get_ptr(), it->second.get_ptr());
 361             }
 362
 363             if (!s2s.debug_check())
 364                 return false;
 365
 366             s2s.print_debug_info();
 367
 368             s2s.clear();
 369
 370             if (!s2s.debug_check())
 371                 return false;
 372         }
 373
 374         {
 375             typedef map<dynamic_string, vogl::vector<uint> > string_to_vec_map;
 376             vogl::vector<uint> k;
 377             k.push_back(1);
 378             k.push_back(2);
 379             k.push_back(3);
 380             string_to_vec_map s2v(0);
 381             s2v.set_fixed_map_level(0);
 382             s2v.insert_multi("Hello", k);
 383
 384             k.push_back(111);
 385             k.push_back(333);
 386             s2v.insert_multi("X", k);
 387
 388             k.push_back(511);
 389             k.push_back(733);
 390             s2v.insert_multi("Y", k);
 391
 392             for (string_to_vec_map::const_iterator it = s2v.begin(); it != s2v.end(); it++)
 393             {
 394                 printf("%s %u\n", it->first.get_ptr(), it->second.size());
 395             }
 396
 397             if (!s2v.erase("X"))
 398                 return false;
 399
 400             for (string_to_vec_map::const_iterator it = s2v.end(); it != s2v.begin();)
 401             {
 402                 it--;
 403                 printf("%s %u\n", it->first.get_ptr(), it->second.size());
 404             }
 405
 406             if (!s2v.debug_check())
 407                 return false;
 408
 409             s2v.print_debug_info();
 410
 411             s2v.reset(5);
 412             s2v.insert_multi("Hello", k);
 413             for (string_to_vec_map::const_iterator it = s2v.begin(); it != s2v.end(); it++)
 414             {
 415                 printf("%s %u\n", it->first.get_ptr(), it->second.size());
 416             }
 417
 418             if (!s2v.debug_check())
 419                 return false;
 420         }
 421
 422         vogl::random rm;
 423         rm.seed(51553);
 424
 425         for (uint t = 0; t < 100; t++)
 426         {
 427             uint n = rm.irand(1, 5000000);
 428             uint k = rm.irand(1, n);
 429
 430             int_to_int_map m;
 431             if (rm.get_bit())
 432             {
 433                 uint max_level = (n < 512) ? rm.irand(0, 5) : rm.irand(5, 20);
 434                 m.set_fixed_map_level(max_level);
 435                 printf("Using fixed max level of %u\n", max_level);
 436             }
 437             else
 438                 printf("Auto max level\n");
 439
 440             printf("n=%u\n", n);
 441
 442             vogl::vector<int> keys(n);
 443             for (uint i = 0; i < n; i++)
 444             {
 445                 uint c = rm.irand_inclusive(0, k);
 446                 keys[i] = c;
 447                 m.insert_multi(c, i);
 448             }
 449             printf("max level: %u, max used level: %u, bytes allocated: %" PRIi64 ", avg per node: %f\n",
 450                    m.get_cur_max_level(), m.get_cur_list_level(), m.get_total_bytes_allocated(), m.get_total_bytes_allocated() / (double)n);
 451
 452             bool success = m.debug_check();
 453             if (!success)
 454                 return false;
 455
 456             m.print_debug_info();
 457
 458             for (int i = 0; i < static_cast<int>(n); i++)
 459             {
 460                 const int c = keys[i];
 461                 int_to_int_map::const_iterator it = m.find(c);
 462
 463                 VOGL_VERIFY(it != m.end());
 464                 VOGL_VERIFY(it->first == keys[i]);
 465                 if (it->second != i)
 466                 {
 467                     // duplicate, the iterator should always point at the beginning of the dup key run
 468                     int_to_int_map::const_iterator xit(it);
 469
 470                     if (xit != m.begin())
 471                     {
 472                         --xit;
 473
 474                         if (xit->first == c)
 475                         {
 476                             VOGL_VERIFY(0);
 477                         }
 478
 479                         VOGL_VERIFY(xit->first < c);
 480                     }
 481
 482                     xit = it;
 483
 484                     for (;;)
 485                     {
 486                         ++xit;
 487                         if (xit == m.end())
 488                         {
 489                             VOGL_VERIFY(0);
 490                             break;
 491                         }
 492                         if (xit->first != c)
 493                         {
 494                             VOGL_VERIFY(0);
 495                             break;
 496                         }
 497                         if (xit->second == i)
 498                             break;
 499                     }
 500                 }
 501             }
 502
 503             success = m.debug_check();
 504             if (!success)
 505                 return false;
 506
 507             for (uint j = 0; j < keys.size() / 2; j++)
 508             {
 509                 if (j == keys.size() / 4)
 510                 {
 511                     success = m.debug_check();
 512                     if (!success)
 513                         return false;
 514                 }
 515
 516                 int i = rm.irand(0, keys.size());
 517
 518                 int c = keys[i];
 519                 if (c < 0)
 520                     continue;
 521
 522                 int_to_int_map::iterator it = m.find(c);
 523
 524                 VOGL_VERIFY(it != m.end());
 525                 VOGL_VERIFY(it->first == c);
 526                 if (it->second != i)
 527                 {
 528                     // duplicate, the iterator should always point at the beginning of the dup key run
 529                     int_to_int_map::iterator xit(it);
 530
 531                     if (xit != m.begin())
 532                     {
 533                         --xit;
 534
 535                         if (xit->first == c)
 536                         {
 537                             VOGL_VERIFY(0);
 538                         }
 539
 540                         VOGL_VERIFY(xit->first < c);
 541                     }
 542
 543                     xit = it;
 544
 545                     for (;;)
 546                     {
 547                         ++xit;
 548                         if (xit == m.end())
 549                         {
 550                             VOGL_VERIFY(0);
 551                             break;
 552                         }
 553                         if (xit->first != c)
 554                         {
 555                             VOGL_VERIFY(0);
 556                             break;
 557                         }
 558                         if (xit->second == i)
 559                             break;
 560                     }
 561
 562                     it = xit;
 563                 }
 564
 565                 m.erase(it);
 566
 567                 keys[i] = -1;
 568             }
 569
 570             success = m.debug_check();
 571             if (!success)
 572                 return false;
 573
 574             while (!m.is_empty())
 575             {
 576                 if (rm.get_bit())
 577                     m.erase(m.begin());
 578                 else
 579                     m.erase(m.begin()->first);
 580             }
 581
 582             success = m.debug_check();
 583             if (!success)
 584                 return false;
 585
 586             m.print_debug_info();
 587
 588             printf("------------------\n");
 589         }
 590
 591         return true;
 592     }
 593
 594 #define VOGL_MAP_INSERT_ONLY_SPEED_TEST 0
 595
 596     void map_perf_test(uint Q)
 597     {
 598         printf("--------------------------------------------------\n");
 599         printf("map_perf_test int->int Q: %u\n", Q);
 600
 601         vogl::vector<uint> rand_indices(Q);
 602         for (uint i = 0; i < Q; i++)
 603             rand_indices[i] = i;
 604
 605         random rm;
 606         rand_indices.shuffle(rm);
 607
 608         for (uint i = 0; i < 2; i++)
 609         {
 610             printf("---------------------------- Run %u\n", i);
 611
 612 #ifdef VOGL_MAP_COMPARATIVE_PERF_TESTING
 613             typedef std::map<int, int> int_to_int_map;
 614
 615             {
 616                 printf("forwards std::map:\n");
 617                 timed_scope ts;
 618
 619                 int_to_int_map m;
 620                 for (uint t = 0; t < Q; t++)
 621                     m.insert(std::make_pair(t, t * 2));
 622
 623                 for (uint t = 0; t < Q; t++)
 624                 {
 625                     m.find(t);
 626                     m.erase(t);
 627                 }
 628             }
 629
 630             {
 631                 printf("backwards std::map:\n");
 632                 timed_scope ts;
 633
 634                 int_to_int_map m;
 635                 for (uint t = 0; t < Q; t++)
 636                     m.insert(std::make_pair(Q - 1 - t, t * 2));
 637
 638 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 639                 for (uint t = 0; t < Q; t++)
 640                 {
 641                     m.find(Q - 1 - t);
 642                     m.erase(Q - 1 - t);
 643                 }
 644 #endif
 645             }
 646
 647             {
 648                 printf("random std::map:\n");
 649                 timed_scope ts;
 650
 651                 int_to_int_map m;
 652                 for (uint t = 0; t < Q; t++)
 653                     m.insert(std::make_pair(rand_indices[t], t * 2));
 654
 655 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 656                 for (uint t = 0; t < Q; t++)
 657                 {
 658                     m.find(rand_indices[t]);
 659                     m.erase(rand_indices[t]);
 660                 }
 661 #endif
 662             }
 663
 664             printf("-----------------------\n");
 665             {
 666                 printf("vogl::hash_map:\n");
 667                 timed_scope ts;
 668
 669                 typedef vogl::hash_map<int, int> int_to_int_hash_map;
 670                 int_to_int_hash_map m;
 671
 672                 for (uint t = 0; t < Q; t++)
 673                     m.insert(t, t * 2);
 674
 675 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 676                 for (uint t = 0; t < Q; t++)
 677                 {
 678                     m.find(t);
 679                     m.erase(t);
 680                 }
 681 #endif
 682             }
 683
 684             {
 685                 printf("vogl::hash_map reserved:\n");
 686                 timed_scope ts;
 687
 688                 typedef vogl::hash_map<int, int> int_to_int_hash_map;
 689                 int_to_int_hash_map m;
 690
 691                 m.reserve(Q);
 692
 693                 for (uint t = 0; t < Q; t++)
 694                     m.insert(t, t * 2);
 695
 696 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 697                 for (uint t = 0; t < Q; t++)
 698                 {
 699                     m.find(t);
 700                     m.erase(t);
 701                 }
 702 #endif
 703             }
 704
 705 #if 0
 706             printf("-----------------------\n");
 707
 708             typedef Treap<int, int> int_to_int_treap;
 709
 710             {
 711                 printf("forwards Treap:\n");
 712                 timed_scope ts;
 713
 714                 int_to_int_treap m;
 715                 for (uint t = 0; t < Q; t++)
 716                     m.insert(t, t * 2);
 717
 718                 for (uint t = 0; t < Q; t++)
 719                 {
 720                     m.find(t);
 721                     m.erase(t);
 722                 }
 723             }
 724
 725             {
 726                 printf("backwards Treap:\n");
 727                 timed_scope ts;
 728
 729                 int_to_int_treap m;
 730                 for (uint t = 0; t < Q; t++)
 731                     m.insert(Q - 1 - t, t * 2);
 732
 733 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 734                 for (uint t = 0; t < Q; t++)
 735                 {
 736                     m.find(Q - 1 - t);
 737                     m.erase(Q - 1 - t);
 738                 }
 739 #endif
 740             }
 741
 742             {
 743                 printf("random Treap:\n");
 744                 timed_scope ts;
 745
 746                 int_to_int_treap m;
 747                 for (uint t = 0; t < Q; t++)
 748                     m.insert(rand_indices[t], t * 2);
 749
 750 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 751                 for (uint t = 0; t < Q; t++)
 752                 {
 753                     m.find(rand_indices[t]);
 754                     m.erase(rand_indices[t]);
 755                 }
 756 #endif
 757             }
 758 #endif
 759
 760 #if 0
 761             printf("-----------------------\n");
 762
 763             typedef AVLTree<int, int> int_to_int_avl_tree;
 764
 765             {
 766                 printf("forwards AVLTree:\n");
 767                 timed_scope ts;
 768
 769                 int_to_int_avl_tree m;
 770                 for (uint t = 0; t < Q; t++)
 771                     m.insert(t, t * 2);
 772
 773                 for (uint t = 0; t < Q; t++)
 774                 {
 775                     m.find(t);
 776                     m.erase(t);
 777                 }
 778             }
 779
 780             {
 781                 printf("backwards AVLTree:\n");
 782                 timed_scope ts;
 783
 784                 int_to_int_avl_tree m;
 785                 for (uint t = 0; t < Q; t++)
 786                     m.insert(Q - 1 - t, t * 2);
 787
 788 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 789                 for (uint t = 0; t < Q; t++)
 790                 {
 791                     m.find(Q - 1 - t);
 792                     m.erase(Q - 1 - t);
 793                 }
 794 #endif
 795             }
 796
 797             {
 798                 printf("random AVLTree:\n");
 799                 timed_scope ts;
 800
 801                 int_to_int_avl_tree m;
 802                 for (uint t = 0; t < Q; t++)
 803                     m.insert(rand_indices[t], t * 2);
 804
 805 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 806                 for (uint t = 0; t < Q; t++)
 807                 {
 808                     m.find(rand_indices[t]);
 809                     m.erase(rand_indices[t]);
 810                 }
 811 #endif
 812             }
 813 #endif
 814
 815 #endif
 816
 817             // Skip testing fixed max levels 0-4, they are just too slow
 818             const int skip_level = 5;
 819
 820             printf("-----------------------\n");
 821             for (int l = -1; l <= 11; l++)
 822             {
 823                 if ((l >= 0) && (l < skip_level))
 824                     continue;
 825
 826                 printf("forwards vogl::map max_level: %i\n", l);
 827
 828                 timed_scope ts;
 829
 830                 typedef vogl::map<int, int> int_to_int_map;
 831                 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
 832                 if (l >= 0)
 833                     m.set_fixed_map_level(l);
 834
 835                 for (uint t = 0; t < Q; t++)
 836                     m.insert(t, t * 2);
 837
 838 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 839                 for (uint t = 0; t < Q; t++)
 840                 {
 841                     m.find(t);
 842                     m.erase(t);
 843                 }
 844 #endif
 845             }
 846
 847             printf("-----------------------\n");
 848             for (int l = -1; l <= 11; l++)
 849             {
 850                 if ((l >= 0) && (l < skip_level))
 851                     continue;
 852
 853                 printf("backwards vogl::map max_level: %i\n", l);
 854
 855                 timed_scope ts;
 856
 857                 typedef vogl::map<int, int> int_to_int_map;
 858                 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
 859                 if (l >= 0)
 860                     m.set_fixed_map_level(l);
 861
 862                 for (uint t = 0; t < Q; t++)
 863                     m.insert(Q - 1 - t, t * 2);
 864
 865 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 866                 for (uint t = 0; t < Q; t++)
 867                 {
 868                     m.find(Q - 1 - t);
 869                     m.erase(Q - 1 - t);
 870                 }
 871 #endif
 872             }
 873
 874             printf("-----------------------\n");
 875             for (int l = -1; l <= 11; l++)
 876             {
 877                 if ((l >= 0) && (l < skip_level))
 878                     continue;
 879
 880                 printf("random vogl::map max_level: %i\n", l);
 881
 882                 timed_scope ts;
 883
 884                 typedef vogl::map<int, int> int_to_int_map;
 885                 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
 886                 if (l >= 0)
 887                     m.set_fixed_map_level(l);
 888
 889                 for (uint t = 0; t < Q; t++)
 890                     m.insert(rand_indices[t], t * 2);
 891
 892 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
 893                 for (uint t = 0; t < Q; t++)
 894                 {
 895                     m.find(rand_indices[t]);
 896                     m.erase(rand_indices[t]);
 897                 }
 898 #endif
 899             }
 900         }
 901     }
 902
 903 } // namespace vogl