The Tor Browser: js/src/jsapi-tests/testHashTable.cpp@6474c204b198 (annotated)

js/src/jsapi-tests/testHashTable.cpp@6474c204b198 (annotated)

js/src/jsapi-tests/testHashTable.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 #include "js/HashTable.h"
 #include "jsapi-tests/tests.h"
 //#define FUZZ
 typedef js::HashMap<uint32_t, uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntMap;
 typedef js::HashSet<uint32_t, js::DefaultHasher<uint32_t>, js::SystemAllocPolicy> IntSet;
 /*
  * The rekeying test as conducted by adding only keys masked with 0x0000FFFF
  * that are unique. We rekey by shifting left 16 bits.
  */
 #ifdef FUZZ
 const size_t TestSize = 0x0000FFFF / 2;
 const size_t TestIterations = SIZE_MAX;
 #else
 const size_t TestSize = 10000;
 const size_t TestIterations = 10;
 #endif
 JS_STATIC_ASSERT(TestSize <= 0x0000FFFF / 2);
 struct LowToHigh
 {
     static uint32_t rekey(uint32_t initial) {
         if (initial > uint32_t(0x0000FFFF))
             return initial;
         return initial << 16;
     }
     static bool shouldBeRemoved(uint32_t initial) {
         return false;
     }
 };
 struct LowToHighWithRemoval
 {
     static uint32_t rekey(uint32_t initial) {
         if (initial > uint32_t(0x0000FFFF))
             return initial;
         return initial << 16;
     }
     static bool shouldBeRemoved(uint32_t initial) {
         if (initial >= 0x00010000)
             return (initial >> 16) % 2 == 0;
         return initial % 2 == 0;
     }
 };
 static bool
 MapsAreEqual(IntMap &am, IntMap &bm)
 {
     bool equal = true;
     if (am.count() != bm.count()) {
         equal = false;
         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
     }
     for (IntMap::Range r = am.all(); !r.empty(); r.popFront()) {
         if (!bm.has(r.front().key())) {
             equal = false;
             fprintf(stderr, "B does not have %x which is in A\n", r.front().key());
         }
     }
     for (IntMap::Range r = bm.all(); !r.empty(); r.popFront()) {
         if (!am.has(r.front().key())) {
             equal = false;
             fprintf(stderr, "A does not have %x which is in B\n", r.front().key());
         }
     }
     return equal;
 }
 static bool
 SetsAreEqual(IntSet &am, IntSet &bm)
 {
     bool equal = true;
     if (am.count() != bm.count()) {
         equal = false;
         fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), bm.count());
     }
     for (IntSet::Range r = am.all(); !r.empty(); r.popFront()) {
         if (!bm.has(r.front())) {
             equal = false;
             fprintf(stderr, "B does not have %x which is in A\n", r.front());
         }
     }
     for (IntSet::Range r = bm.all(); !r.empty(); r.popFront()) {
         if (!am.has(r.front())) {
             equal = false;
             fprintf(stderr, "A does not have %x which is in B\n", r.front());
         }
     }
     return equal;
 }
 static bool
 AddLowKeys(IntMap *am, IntMap *bm, int seed)
 {
     size_t i = 0;
     srand(seed);
     while (i < TestSize) {
         uint32_t n = rand() & 0x0000FFFF;
         if (!am->has(n)) {
             if (bm->has(n))
                 return false;
             am->putNew(n, n);
             bm->putNew(n, n);
             i++;
         }
     }
     return true;
 }
 static bool
 AddLowKeys(IntSet *as, IntSet *bs, int seed)
 {
     size_t i = 0;
     srand(seed);
     while (i < TestSize) {
         uint32_t n = rand() & 0x0000FFFF;
         if (!as->has(n)) {
             if (bs->has(n))
                 return false;
             as->putNew(n);
             bs->putNew(n);
             i++;
         }
     }
     return true;
 }
 template <class NewKeyFunction>
 static bool
 SlowRekey(IntMap *m) {
     IntMap tmp;
     tmp.init();
     for (IntMap::Range r = m->all(); !r.empty(); r.popFront()) {
         if (NewKeyFunction::shouldBeRemoved(r.front().key()))
             continue;
         uint32_t hi = NewKeyFunction::rekey(r.front().key());
         if (tmp.has(hi))
             return false;
         tmp.putNew(hi, r.front().value());
     }
     m->clear();
     for (IntMap::Range r = tmp.all(); !r.empty(); r.popFront()) {
         m->putNew(r.front().key(), r.front().value());
     }
     return true;
 }
 template <class NewKeyFunction>
 static bool
 SlowRekey(IntSet *s) {
     IntSet tmp;
     tmp.init();
     for (IntSet::Range r = s->all(); !r.empty(); r.popFront()) {
         if (NewKeyFunction::shouldBeRemoved(r.front()))
             continue;
         uint32_t hi = NewKeyFunction::rekey(r.front());
         if (tmp.has(hi))
             return false;
         tmp.putNew(hi);
     }
     s->clear();
     for (IntSet::Range r = tmp.all(); !r.empty(); r.popFront()) {
         s->putNew(r.front());
     }
     return true;
 }
 BEGIN_TEST(testHashRekeyManual)
 {
     IntMap am, bm;
     am.init();
     bm.init();
     for (size_t i = 0; i < TestIterations; ++i) {
 #ifdef FUZZ
         fprintf(stderr, "map1: %lu\n", i);
 #endif
         CHECK(AddLowKeys(&am, &bm, i));
         CHECK(MapsAreEqual(am, bm));
         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
             uint32_t tmp = LowToHigh::rekey(e.front().key());
             if (tmp != e.front().key())
                 e.rekeyFront(tmp);
         }
         CHECK(SlowRekey<LowToHigh>(&bm));
         CHECK(MapsAreEqual(am, bm));
         am.clear();
         bm.clear();
     }
     IntSet as, bs;
     as.init();
     bs.init();
     for (size_t i = 0; i < TestIterations; ++i) {
 #ifdef FUZZ
         fprintf(stderr, "set1: %lu\n", i);
 #endif
         CHECK(AddLowKeys(&as, &bs, i));
         CHECK(SetsAreEqual(as, bs));
         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
             uint32_t tmp = LowToHigh::rekey(e.front());
             if (tmp != e.front())
                 e.rekeyFront(tmp);
         }
         CHECK(SlowRekey<LowToHigh>(&bs));
         CHECK(SetsAreEqual(as, bs));
         as.clear();
         bs.clear();
     }
     return true;
 }
 END_TEST(testHashRekeyManual)
 BEGIN_TEST(testHashRekeyManualRemoval)
 {
     IntMap am, bm;
     am.init();
     bm.init();
     for (size_t i = 0; i < TestIterations; ++i) {
 #ifdef FUZZ
         fprintf(stderr, "map2: %lu\n", i);
 #endif
         CHECK(AddLowKeys(&am, &bm, i));
         CHECK(MapsAreEqual(am, bm));
         for (IntMap::Enum e(am); !e.empty(); e.popFront()) {
             if (LowToHighWithRemoval::shouldBeRemoved(e.front().key())) {
                 e.removeFront();
             } else {
                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front().key());
                 if (tmp != e.front().key())
                     e.rekeyFront(tmp);
             }
         }
         CHECK(SlowRekey<LowToHighWithRemoval>(&bm));
         CHECK(MapsAreEqual(am, bm));
         am.clear();
         bm.clear();
     }
     IntSet as, bs;
     as.init();
     bs.init();
     for (size_t i = 0; i < TestIterations; ++i) {
 #ifdef FUZZ
         fprintf(stderr, "set1: %lu\n", i);
 #endif
         CHECK(AddLowKeys(&as, &bs, i));
         CHECK(SetsAreEqual(as, bs));
         for (IntSet::Enum e(as); !e.empty(); e.popFront()) {
             if (LowToHighWithRemoval::shouldBeRemoved(e.front())) {
                 e.removeFront();
             } else {
                 uint32_t tmp = LowToHighWithRemoval::rekey(e.front());
                 if (tmp != e.front())
                     e.rekeyFront(tmp);
             }
         }
         CHECK(SlowRekey<LowToHighWithRemoval>(&bs));
         CHECK(SetsAreEqual(as, bs));
         as.clear();
         bs.clear();
     }
     return true;
 }
 END_TEST(testHashRekeyManualRemoval)

The Tor Browser / annotate

js/src/jsapi-tests/testHashTable.cpp@6474c204b198 (annotated)

js/src/jsapi-tests/testHashTable.cpp