| /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- |
| * vim: set ts=8 sts=4 et sw=4 tw=99: |
| * 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/. */ |
| |
| #ifndef jsfixedsizehash_h_ |
| #define jsfixedsizehash_h_ |
| |
| #include "ds/LifoAlloc.h" |
| |
| namespace js { |
| |
| /* |
| * Class representing a hash set with fixed capacity, with newer entries |
| * evicting older entries. Each entry has several hashes and can be stored in |
| * different buckets, with the choice of which to evict on insertion being |
| * managed via LRU. For tables with a relatively small size, using different |
| * hashes increases utilization and makes it less likely that entries will keep |
| * evicting each other due to wanting to use the same bucket. |
| * |
| * T indicates the type of hash elements, HashPolicy must have the following |
| * contents: |
| * |
| * Lookup - As for HashMap / HashSet. |
| * |
| * bool match(T, Lookup) - As for HashMap / HashSet. |
| * |
| * NumHashes - Number of different hashes generated for each entry. |
| * |
| * void hash(Lookup, HashNumber[NumHashes]) - Compute all hashes for an entry. |
| * |
| * void clear(T*) - Clear an entry, such that isCleared() holds afterwards. |
| * |
| * bool isCleared(T) - Test whether an entry has been cleared. |
| */ |
| template <class T, class HashPolicy, size_t Capacity> |
| class FixedSizeHashSet |
| { |
| T entries[Capacity]; |
| uint32_t lastOperations[Capacity]; |
| uint32_t numOperations; |
| |
| static const size_t NumHashes = HashPolicy::NumHashes; |
| |
| static_assert(Capacity > 0, "an empty fixed-size hash set is meaningless"); |
| |
| public: |
| typedef typename HashPolicy::Lookup Lookup; |
| |
| FixedSizeHashSet() |
| : entries(), lastOperations(), numOperations(0) |
| { |
| MOZ_ASSERT(HashPolicy::isCleared(entries[0])); |
| } |
| |
| bool lookup(const Lookup& lookup, T* pentry) |
| { |
| size_t bucket; |
| if (lookupReference(lookup, &bucket)) { |
| *pentry = entries[bucket]; |
| lastOperations[bucket] = numOperations++; |
| return true; |
| } |
| return false; |
| } |
| |
| void insert(const Lookup& lookup, const T& entry) |
| { |
| size_t buckets[NumHashes]; |
| getBuckets(lookup, buckets); |
| |
| size_t min = buckets[0]; |
| for (size_t i = 0; i < NumHashes; i++) { |
| const T& entry = entries[buckets[i]]; |
| if (HashPolicy::isCleared(entry)) { |
| entries[buckets[i]] = entry; |
| lastOperations[buckets[i]] = numOperations++; |
| return; |
| } |
| if (i && lastOperations[min] > lastOperations[buckets[i]]) |
| min = buckets[i]; |
| } |
| |
| entries[min] = entry; |
| lastOperations[min] = numOperations++; |
| } |
| |
| template <typename S> |
| void remove(const S& s) |
| { |
| size_t bucket; |
| if (lookupReference(s, &bucket)) |
| HashPolicy::clear(&entries[bucket]); |
| } |
| |
| private: |
| template <typename S> |
| bool lookupReference(const S& s, size_t* pbucket) |
| { |
| size_t buckets[NumHashes]; |
| getBuckets(s, buckets); |
| |
| for (size_t i = 0; i < NumHashes; i++) { |
| const T& entry = entries[buckets[i]]; |
| if (!HashPolicy::isCleared(entry) && HashPolicy::match(entry, s)) { |
| *pbucket = buckets[i]; |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| template <typename S> |
| void getBuckets(const S& s, size_t buckets[NumHashes]) |
| { |
| HashNumber hashes[NumHashes]; |
| HashPolicy::hash(s, hashes); |
| |
| for (size_t i = 0; i < NumHashes; i++) |
| buckets[i] = hashes[i] % Capacity; |
| } |
| }; |
| |
| } /* namespace js */ |
| |
| #endif /* jsfixedsizehash_h_ */ |