mfbt/tests/TestSplayTree.cpp

   1 /* -*- Mode: C++; tab-width: 9; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/ArrayUtils.h"
   8 #include "mozilla/Assertions.h"
   9 #include "mozilla/SplayTree.h"
  10 #include "mozilla/Unused.h"
  11
  12 using mozilla::SplayTree;
  13 using mozilla::SplayTreeNode;
  14
  15 // The following array contains the values 0..999 in random order, as computed
  16 // with the following Python program:
  17 //
  18 //   from random import shuffle
  19 //   x = range(1000)
  20 //   shuffle(x)
  21 //   print(x);
  22 //
  23 static int gValues[] = {
  24     778, 999, 248, 795, 607, 177, 725, 33,  215, 565, 436, 821, 941, 802, 322,
  25     54,  151, 416, 531, 65,  818, 99,  340, 401, 274, 767, 278, 617, 425, 629,
  26     833, 878, 440, 984, 724, 519, 100, 369, 490, 131, 422, 169, 932, 476, 823,
  27     521, 390, 781, 747, 218, 376, 461, 717, 532, 471, 298, 720, 608, 334, 788,
  28     161, 500, 280, 963, 430, 484, 779, 572, 96,  333, 650, 158, 199, 137, 991,
  29     399, 882, 689, 358, 548, 196, 718, 211, 388, 133, 188, 321, 892, 25,  694,
  30     735, 886, 872, 785, 195, 275, 696, 975, 393, 619, 894, 18,  281, 191, 792,
  31     846, 861, 351, 542, 806, 570, 702, 931, 585, 444, 284, 217, 132, 251, 253,
  32     302, 808, 224, 37,  63,  863, 409, 49,  780, 790, 31,  638, 890, 186, 114,
  33     152, 949, 491, 207, 392, 170, 460, 794, 482, 877, 407, 263, 909, 249, 710,
  34     614, 51,  431, 915, 62,  332, 74,  495, 901, 23,  365, 752, 89,  660, 745,
  35     741, 547, 669, 449, 465, 605, 107, 774, 205, 852, 266, 247, 690, 835, 765,
  36     410, 140, 122, 400, 510, 664, 105, 935, 230, 134, 106, 959, 375, 884, 361,
  37     527, 715, 840, 272, 232, 102, 415, 903, 117, 313, 153, 463, 464, 876, 406,
  38     967, 713, 381, 836, 555, 190, 859, 172, 483, 61,  633, 294, 993, 72,  337,
  39     11,  896, 523, 101, 916, 244, 566, 706, 533, 439, 201, 222, 695, 739, 553,
  40     571, 289, 918, 209, 189, 357, 814, 670, 866, 910, 579, 246, 636, 750, 891,
  41     494, 758, 341, 626, 426, 772, 254, 682, 588, 104, 347, 184, 977, 126, 498,
  42     165, 955, 241, 516, 235, 497, 121, 123, 791, 844, 259, 995, 283, 602, 417,
  43     221, 308, 855, 429, 86,  345, 928, 44,  679, 796, 363, 402, 445, 492, 450,
  44     964, 749, 925, 847, 637, 982, 648, 635, 481, 564, 867, 940, 291, 159, 290,
  45     929, 59,  712, 986, 611, 954, 820, 103, 622, 316, 142, 204, 225, 678, 314,
  46     84,  578, 315, 141, 990, 880, 504, 969, 412, 746, 47,  517, 124, 848, 466,
  47     438, 674, 979, 782, 651, 181, 26,  435, 832, 386, 951, 229, 642, 655, 91,
  48     162, 921, 647, 113, 686, 56,  805, 763, 245, 581, 287, 998, 525, 641, 135,
  49     634, 237, 728, 112, 828, 228, 899, 1,   723, 16,  613, 144, 659, 97,  185,
  50     312, 292, 733, 624, 276, 387, 926, 339, 768, 960, 610, 807, 656, 851, 219,
  51     582, 709, 927, 514, 680, 870, 597, 536, 77,  164, 512, 149, 900, 85,  335,
  52     997, 8,   705, 777, 653, 815, 311, 701, 507, 202, 530, 827, 541, 958, 82,
  53     874, 55,  487, 383, 885, 684, 180, 829, 760, 109, 194, 540, 816, 906, 657,
  54     469, 446, 857, 907, 38,  600, 618, 797, 950, 822, 277, 842, 116, 513, 255,
  55     424, 643, 163, 372, 129, 67,  118, 754, 529, 917, 687, 473, 174, 538, 939,
  56     663, 775, 474, 242, 883, 20,  837, 293, 584, 943, 32,  176, 904, 14,  448,
  57     893, 888, 744, 171, 714, 454, 691, 261, 934, 606, 789, 825, 671, 397, 338,
  58     317, 612, 737, 130, 41,  923, 574, 136, 980, 850, 12,  729, 197, 403, 57,
  59     783, 360, 146, 75,  432, 447, 192, 799, 740, 267, 214, 250, 367, 853, 968,
  60     120, 736, 391, 881, 784, 665, 68,  398, 350, 839, 268, 697, 567, 428, 738,
  61     48,  182, 70,  220, 865, 418, 374, 148, 945, 353, 539, 589, 307, 427, 506,
  62     265, 558, 128, 46,  336, 299, 349, 309, 377, 304, 420, 30,  34,  875, 948,
  63     212, 394, 442, 719, 273, 269, 157, 502, 675, 751, 838, 897, 862, 831, 676,
  64     590, 811, 966, 854, 477, 15,  598, 573, 108, 98,  81,  408, 421, 296, 73,
  65     644, 456, 362, 666, 550, 331, 368, 193, 470, 203, 769, 342, 36,  604, 60,
  66     970, 748, 813, 522, 515, 90,  672, 243, 793, 947, 595, 632, 912, 475, 258,
  67     80,  873, 623, 524, 546, 262, 727, 216, 505, 330, 373, 58,  297, 609, 908,
  68     150, 206, 703, 755, 260, 511, 213, 198, 766, 898, 992, 488, 405, 974, 770,
  69     936, 743, 554, 0,   499, 976, 94,  160, 919, 434, 324, 156, 757, 830, 677,
  70     183, 630, 871, 640, 938, 518, 344, 366, 742, 552, 306, 535, 200, 652, 496,
  71     233, 419, 787, 318, 981, 371, 166, 143, 384, 88,  508, 698, 812, 559, 658,
  72     549, 208, 599, 621, 961, 668, 563, 93,  154, 587, 560, 389, 3,   210, 326,
  73     4,   924, 300, 2,   804, 914, 801, 753, 654, 27,  236, 19,  708, 451, 985,
  74     596, 478, 922, 240, 127, 994, 983, 385, 472, 40,  528, 288, 111, 543, 568,
  75     155, 625, 759, 937, 956, 545, 953, 962, 382, 479, 809, 557, 501, 354, 414,
  76     343, 378, 843, 379, 178, 556, 800, 803, 592, 627, 942, 576, 920, 704, 707,
  77     726, 223, 119, 404, 24,  879, 722, 868, 5,   238, 817, 520, 631, 946, 462,
  78     457, 295, 480, 957, 441, 145, 286, 303, 688, 17,  628, 493, 364, 226, 110,
  79     615, 69,  320, 534, 593, 721, 411, 285, 869, 952, 849, 139, 356, 346, 28,
  80     887, 810, 92,  798, 544, 458, 996, 692, 396, 667, 328, 173, 22,  773, 50,
  81     645, 987, 42,  685, 734, 700, 683, 601, 580, 639, 913, 323, 858, 179, 761,
  82     6,   841, 905, 234, 730, 29,  21,  575, 586, 902, 443, 826, 646, 257, 125,
  83     649, 53,  453, 252, 13,  87,  971, 227, 485, 168, 380, 711, 79,  732, 325,
  84     52,  468, 76,  551, 39,  395, 327, 973, 459, 45,  583, 989, 147, 455, 776,
  85     944, 569, 889, 256, 35,  175, 834, 756, 933, 860, 526, 845, 864, 764, 771,
  86     282, 9,   693, 352, 731, 7,   577, 264, 319, 138, 467, 819, 930, 231, 115,
  87     988, 978, 762, 486, 301, 616, 10,  78,  603, 452, 965, 279, 972, 413, 895,
  88     591, 662, 594, 348, 423, 489, 43,  699, 433, 509, 355, 270, 66,  83,  95,
  89     561, 661, 562, 329, 620, 370, 64,  187, 503, 716, 856, 310, 786, 167, 71,
  90     239, 359, 537, 437, 305, 673, 824, 911, 681, 271};
  91
  92 struct SplayInt : SplayTreeNode<SplayInt> {
  93   explicit SplayInt(int aValue) : mValue(aValue) {}
  94
  95   static int compare(const SplayInt& aOne, const SplayInt& aTwo) {
  96     if (aOne.mValue < aTwo.mValue) {
  97       return -1;
  98     }
  99     if (aOne.mValue > aTwo.mValue) {
 100       return 1;
 101     }
 102     return 0;
 103   }
 104
 105   int mValue;
 106 };
 107
 108 struct SplayNoCopy : SplayTreeNode<SplayNoCopy> {
 109   SplayNoCopy(const SplayNoCopy&) = delete;
 110   SplayNoCopy(SplayNoCopy&&) = delete;
 111
 112   static int compare(const SplayNoCopy&, const SplayNoCopy&) { return 0; }
 113 };
 114
 115 static SplayTree<SplayNoCopy, SplayNoCopy> testNoCopy;
 116
 117 int main() {
 118   mozilla::Unused << testNoCopy;
 119
 120   SplayTree<SplayInt, SplayInt> tree;
 121
 122   MOZ_RELEASE_ASSERT(tree.empty());
 123
 124   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0)));
 125
 126   static const int N = mozilla::ArrayLength(gValues);
 127
 128   // Insert the values, and check each one is findable just after insertion.
 129   for (int i = 0; i < N; i++) {
 130     tree.insert(new SplayInt(gValues[i]));
 131     SplayInt* inserted = tree.find(SplayInt(gValues[i]));
 132     MOZ_RELEASE_ASSERT(inserted);
 133     MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
 134     tree.checkCoherency();
 135   }
 136
 137   // Check they're all findable after all insertions.
 138   for (int i = 0; i < N; i++) {
 139     MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
 140     MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
 141     tree.checkCoherency();
 142   }
 143
 144   // Check that non-inserted values cannot be found.
 145   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
 146   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
 147   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));
 148
 149   // Remove the values, and check each one is not findable just after removal.
 150   for (int i = 0; i < N; i++) {
 151     SplayInt* removed = tree.remove(SplayInt(gValues[i]));
 152     MOZ_RELEASE_ASSERT(removed->mValue == gValues[i]);
 153     MOZ_RELEASE_ASSERT(!tree.find(*removed));
 154     delete removed;
 155     tree.checkCoherency();
 156   }
 157
 158   MOZ_RELEASE_ASSERT(tree.empty());
 159
 160   // Insert the values, and check each one is findable just after insertion.
 161   for (int i = 0; i < N; i++) {
 162     SplayInt* inserted = tree.findOrInsert(SplayInt(gValues[i]));
 163     MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])) == inserted);
 164     MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
 165     tree.checkCoherency();
 166   }
 167
 168   // Check they're all findable after all insertions.
 169   for (int i = 0; i < N; i++) {
 170     MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
 171     MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
 172     tree.checkCoherency();
 173   }
 174
 175   // Check that non-inserted values cannot be found.
 176   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
 177   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
 178   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));
 179
 180   // Remove the values, and check each one is not findable just after removal.
 181   for (int i = 0; i < N; i++) {
 182     SplayInt* removed = tree.remove(SplayInt(gValues[i]));
 183     MOZ_RELEASE_ASSERT(removed->mValue == gValues[i]);
 184     MOZ_RELEASE_ASSERT(!tree.find(*removed));
 185     delete removed;
 186     tree.checkCoherency();
 187   }
 188
 189   MOZ_RELEASE_ASSERT(tree.empty());
 190
 191   // Reinsert the values, in reverse order to last time.
 192   for (int i = 0; i < N; i++) {
 193     tree.insert(new SplayInt(gValues[N - i - 1]));
 194     tree.checkCoherency();
 195   }
 196
 197   // Remove the minimum value repeatedly.
 198   for (int i = 0; i < N; i++) {
 199     SplayInt* removed = tree.removeMin();
 200     MOZ_RELEASE_ASSERT(removed->mValue == i);
 201     delete removed;
 202     tree.checkCoherency();
 203   }
 204
 205   MOZ_RELEASE_ASSERT(tree.empty());
 206
 207   return 0;
 208 }