The Tor Browser: js/src/jsapi-tests/testHashTable.cpp@b8a032363ba2

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     1 /* This Source Code Form is subject to the terms of the Mozilla Public

     2  * License, v. 2.0. If a copy of the MPL was not distributed with this

     3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     5 #include "js/HashTable.h"

     6 #include "jsapi-tests/tests.h"

     8 //#define FUZZ

    10 typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;

    11 typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;

    13 /*

    14  * The rekeying test as conducted by adding only keys masked with 0x0000FFFF

    15  * that are unique. We rekey by shifting left 16 bits.

    16  */

    17 #ifdef FUZZ

    18 const size_t TestSize = 0x0000FFFF / 2;

    19 const size_t TestIterations = SIZE_MAX;

    20 #else

    21 const size_t TestSize = 10000;

    22 const size_t TestIterations = 10;

    23 #endif

    25 JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);

    27 struct LowToHigh

    28 {

    29     static uint32_t rekey(uint32_t initial) {

    30         if (initial > uint32_t(0x0000FFFF))

    31             return initial;

    32         return initial << 16;

    33     }

    35     static bool shouldBeRemoved(uint32_t initial) {

    36         return false;

    37     }

    38 };

    40 struct LowToHighWithRemoval

    41 {

    42     static uint32_t rekey(uint32_t initial) {

    43         if (initial > uint32_t(0x0000FFFF))

    44             return initial;

    45         return initial << 16;

    46     }

    48     static bool shouldBeRemoved(uint32_t initial) {

    49         if (initial >= 0x00010000)

    50             return (initial >> 16) % 2 == 0;

    51         return initial % 2 == 0;

    52     }

    53 };

    55 static bool

    56 MapsAreEqual(IntMap &am, IntMap &bm)

    57 {

    58     bool equal = true;

    59     if (am.count() != bm.count()) {

    60         equal = false;

    61         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());

    62     }

    63     for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {

    64         if (!bm.has(r.front().key())) {

    65             equal = false;

    66             fprintf(stderr, "B does not have %x which is in A\n", r.front().key());

    67         }

    68     }

    69     for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {

    70         if (!am.has(r.front().key())) {

    71             equal = false;

    72             fprintf(stderr, "A does not have %x which is in B\n", r.front().key());

    73         }

    74     }

    75     return equal;

    76 }

    78 static bool

    79 SetsAreEqual(IntSet &am, IntSet &bm)

    80 {

    81     bool equal = true;

    82     if (am.count() != bm.count()) {

    83         equal = false;

    84         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());

    85     }

    86     for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {

    87         if (!bm.has(r.front())) {

    88             equal = false;

    89             fprintf(stderr, "B does not have %x which is in A\n", r.front());

    90         }

    91     }

    92     for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {

    93         if (!am.has(r.front())) {

    94             equal = false;

    95             fprintf(stderr, "A does not have %x which is in B\n", r.front());

    96         }

    97     }

    98     return equal;

    99 }

   101 static bool

   102 AddLowKeys(IntMap *am, IntMap *bm, int seed)

   103 {

   104     size_t i = 0;

   105     srand(seed);

   106     while (i < TestSize) {

   107         uint32_t n = rand() & 0x0000FFFF;

   108         if (!am->has(n)) {

   109             if (bm->has(n))

   110                 return false;

   111             am->putNew(n, n);

   112             bm->putNew(n, n);

   113             i++;

   114         }

   115     }

   116     return true;

   117 }

   119 static bool

   120 AddLowKeys(IntSet *as, IntSet *bs, int seed)

   121 {

   122     size_t i = 0;

   123     srand(seed);

   124     while (i < TestSize) {

   125         uint32_t n = rand() & 0x0000FFFF;

   126         if (!as->has(n)) {

   127             if (bs->has(n))

   128                 return false;

   129             as->putNew(n);

   130             bs->putNew(n);

   131             i++;

   132         }

   133     }

   134     return true;

   135 }

   137 template <class NewKeyFunction>

   138 static bool

   139 SlowRekey(IntMap *m) {

   140     IntMap tmp;

   141     tmp.init();

   143     for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {

   144         if (NewKeyFunction::shouldBeRemoved(r.front().key()))

   145             continue;

   146         uint32_t hi = NewKeyFunction::rekey(r.front().key());

   147         if (tmp.has(hi))

   148             return false;

   149         tmp.putNew(hi, r.front().value());

   150     }

   152     m->clear();

   153     for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {

   154         m->putNew(r.front().key(), r.front().value());

   155     }

   157     return true;

   158 }

   160 template <class NewKeyFunction>

   161 static bool

   162 SlowRekey(IntSet *s) {

   163     IntSet tmp;

   164     tmp.init();

   166     for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {

   167         if (NewKeyFunction::shouldBeRemoved(r.front()))

   168             continue;

   169         uint32_t hi = NewKeyFunction::rekey(r.front());

   170         if (tmp.has(hi))

   171             return false;

   172         tmp.putNew(hi);

   173     }

   175     s->clear();

   176     for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {

   177         s->putNew(r.front());

   178     }

   180     return true;

   181 }

   183 BEGIN_TEST(testHashRekeyManual)

   184 {

   185     IntMap am, bm;

   186     am.init();

   187     bm.init();

   188     for (size_t i = 0; i < TestIterations; ++i) {

   189 #ifdef FUZZ

   190         fprintf(stderr, "map1: %lu\n", i);

   191 #endif

   192         CHECK(AddLowKeys(&am, &bm, i));

   193         CHECK(MapsAreEqual(am, bm));

   195         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {

   196             uint32_t tmp = LowToHigh::rekey(e.front().key());

   197             if (tmp != e.front().key())

   198                 e.rekeyFront(tmp);

   199         }

   200         CHECK(SlowRekey<LowToHigh>(&bm));

   202         CHECK(MapsAreEqual(am, bm));

   203         am.clear();

   204         bm.clear();

   205     }

   207     IntSet as, bs;

   208     as.init();

   209     bs.init();

   210     for (size_t i = 0; i < TestIterations; ++i) {

   211 #ifdef FUZZ

   212         fprintf(stderr, "set1: %lu\n", i);

   213 #endif

   214         CHECK(AddLowKeys(&as, &bs, i));

   215         CHECK(SetsAreEqual(as, bs));

   217         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {

   218             uint32_t tmp = LowToHigh::rekey(e.front());

   219             if (tmp != e.front())

   220                 e.rekeyFront(tmp);

   221         }

   222         CHECK(SlowRekey<LowToHigh>(&bs));

   224         CHECK(SetsAreEqual(as, bs));

   225         as.clear();

   226         bs.clear();

   227     }

   229     return true;

   230 }

   231 END_TEST(testHashRekeyManual)

   233 BEGIN_TEST(testHashRekeyManualRemoval)

   234 {

   235     IntMap am, bm;

   236     am.init();

   237     bm.init();

   238     for (size_t i = 0; i < TestIterations; ++i) {

   239 #ifdef FUZZ

   240         fprintf(stderr, "map2: %lu\n", i);

   241 #endif

   242         CHECK(AddLowKeys(&am, &bm, i));

   243         CHECK(MapsAreEqual(am, bm));

   245         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {

   246             if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) {

   247                 e.removeFront();

   248             } else {

   249                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key());

   250                 if (tmp != e.front().key())

   251                     e.rekeyFront(tmp);

   252             }

   253         }

   254         CHECK(SlowRekey<LowToHighWithRemoval>(&bm));

   256         CHECK(MapsAreEqual(am, bm));

   257         am.clear();

   258         bm.clear();

   259     }

   261     IntSet as, bs;

   262     as.init();

   263     bs.init();

   264     for (size_t i = 0; i < TestIterations; ++i) {

   265 #ifdef FUZZ

   266         fprintf(stderr, "set1: %lu\n", i);

   267 #endif

   268         CHECK(AddLowKeys(&as, &bs, i));

   269         CHECK(SetsAreEqual(as, bs));

   271         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {

   272             if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {

   273                 e.removeFront();

   274             } else {

   275                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front());

   276                 if (tmp != e.front())

   277                     e.rekeyFront(tmp);

   278             }

   279         }

   280         CHECK(SlowRekey<LowToHighWithRemoval>(&bs));

   282         CHECK(SetsAreEqual(as, bs));

   283         as.clear();

   284         bs.clear();

   285     }

   287     return true;

   288 }

   289 END_TEST(testHashRekeyManualRemoval)

The Tor Browser / file revision

js/src/jsapi-tests/testHashTable.cpp@b8a032363ba2

js/src/jsapi-tests/testHashTable.cpp