The Tor Browser / file comparison
comparison: js/src/ds/FixedSizeHash.h
js/src/ds/FixedSizeHash.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d9fe0e201d9f |
|---|---|
| 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/. */ | |
| 6 | |
| 7 #ifndef jsfixedsizehash_h_ | |
| 8 #define jsfixedsizehash_h_ | |
| 9 | |
| 10 #include "ds/LifoAlloc.h" | |
| 11 | |
| 12 namespace js { | |
| 13 | |
| 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; | |
| 43 | |
| 44 static const size_t NumHashes = HashPolicy::NumHashes; | |
| 45 | |
| 46 public: | |
| 47 typedef typename HashPolicy::Lookup Lookup; | |
| 48 | |
| 49 FixedSizeHashSet() | |
| 50 : entries(), lastOperations(), numOperations(0) | |
| 51 { | |
| 52 JS_STATIC_ASSERT(Capacity > 0); | |
| 53 JS_ASSERT(HashPolicy::isCleared(entries[0])); | |
| 54 } | |
| 55 | |
| 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 } | |
| 66 | |
| 67 void insert(const Lookup &lookup, const T &entry) | |
| 68 { | |
| 69 size_t buckets[NumHashes]; | |
| 70 getBuckets(lookup, buckets); | |
| 71 | |
| 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 } | |
| 83 | |
| 84 entries[min] = entry; | |
| 85 lastOperations[min] = numOperations++; | |
| 86 } | |
| 87 | |
| 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 } | |
| 95 | |
| 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); | |
| 102 | |
| 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 } | |
| 110 | |
| 111 return false; | |
| 112 } | |
| 113 | |
| 114 template <typename S> | |
| 115 void getBuckets(const S &s, size_t buckets[NumHashes]) | |
| 116 { | |
| 117 HashNumber hashes[NumHashes]; | |
| 118 HashPolicy::hash(s, hashes); | |
| 119 | |
| 120 for (size_t i = 0; i < NumHashes; i++) | |
| 121 buckets[i] = hashes[i] % Capacity; | |
| 122 } | |
| 123 }; | |
| 124 | |
| 125 } /* namespace js */ | |
| 126 | |
| 127 #endif /* jsfixedsizehash_h_ */ |
