The Tor Browser: js/src/ds/FixedSizeHash.h@6474c204b198

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

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

     2  * vim: set ts=8 sts=4 et sw=4 tw=99:

     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

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

     7 #ifndef jsfixedsizehash_h_

     8 #define jsfixedsizehash_h_

    10 #include "ds/LifoAlloc.h"

    12 namespace js {

    14 /*

    15  * Class representing a hash set with fixed capacity, with newer entries

    16  * evicting older entries. Each entry has several hashes and can be stored in

    17  * different buckets, with the choice of which to evict on insertion being

    18  * managed via LRU. For tables with a relatively small size, using different

    19  * hashes increases utilization and makes it less likely that entries will keep

    20  * evicting each other due to wanting to use the same bucket.

    21  *

    22  * T indicates the type of hash elements, HashPolicy must have the following

    23  * contents:

    24  *

    25  * Lookup - As for HashMap / HashSet.

    26  *

    27  * bool match(T, Lookup) - As for HashMap / HashSet.

    28  *

    29  * NumHashes - Number of different hashes generated for each entry.

    30  *

    31  * void hash(Lookup, HashNumber[NumHashes]) - Compute all hashes for an entry.

    32  *

    33  * void clear(T *) - Clear an entry, such that isCleared() holds afterwards.

    34  *

    35  * bool isCleared(T) - Test whether an entry has been cleared.

    36  */

    37 template <class T, class HashPolicy, size_t Capacity>

    38 class FixedSizeHashSet

    39 {

    40     T entries[Capacity];

    41     uint32_t lastOperations[Capacity];

    42     uint32_t numOperations;

    44     static const size_t NumHashes = HashPolicy::NumHashes;

    46   public:

    47     typedef typename HashPolicy::Lookup Lookup;

    49     FixedSizeHashSet()

    50       : entries(), lastOperations(), numOperations(0)

    51     {

    52         JS_STATIC_ASSERT(Capacity > 0);

    53         JS_ASSERT(HashPolicy::isCleared(entries[0]));

    54     }

    56     bool lookup(const Lookup &lookup, T *pentry)

    57     {

    58         size_t bucket;

    59         if (lookupReference(lookup, &bucket)) {

    60             *pentry = entries[bucket];

    61             lastOperations[bucket] = numOperations++;

    62             return true;

    63         }

    64         return false;

    65     }

    67     void insert(const Lookup &lookup, const T &entry)

    68     {

    69         size_t buckets[NumHashes];

    70         getBuckets(lookup, buckets);

    72         size_t min = buckets[0];

    73         for (size_t i = 0; i < NumHashes; i++) {

    74             const T &entry = entries[buckets[i]];

    75             if (HashPolicy::isCleared(entry)) {

    76                 entries[buckets[i]] = entry;

    77                 lastOperations[buckets[i]] = numOperations++;

    78                 return;

    79             }

    80             if (i && lastOperations[min] > lastOperations[buckets[i]])

    81                 min = buckets[i];

    82         }

    84         entries[min] = entry;

    85         lastOperations[min] = numOperations++;

    86     }

    88     template <typename S>

    89     void remove(const S &s)

    90     {

    91         size_t bucket;

    92         if (lookupReference(s, &bucket))

    93             HashPolicy::clear(&entries[bucket]);

    94     }

    96   private:

    97     template <typename S>

    98     bool lookupReference(const S &s, size_t *pbucket)

    99     {

   100         size_t buckets[NumHashes];

   101         getBuckets(s, buckets);

   103         for (size_t i = 0; i < NumHashes; i++) {

   104             const T &entry = entries[buckets[i]];

   105             if (!HashPolicy::isCleared(entry) && HashPolicy::match(entry, s)) {

   106                 *pbucket = buckets[i];

   107                 return true;

   108             }

   109         }

   111         return false;

   112     }

   114     template <typename S>

   115     void getBuckets(const S &s, size_t buckets[NumHashes])

   116     {

   117         HashNumber hashes[NumHashes];

   118         HashPolicy::hash(s, hashes);

   120         for (size_t i = 0; i < NumHashes; i++)

   121             buckets[i] = hashes[i] % Capacity;

   122     }

   123 };

   125 }  /* namespace js */

   127 #endif /* jsfixedsizehash_h_ */

The Tor Browser / file revision