1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/FixedSizeHash.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,127 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jsfixedsizehash_h_
1.11 +#define jsfixedsizehash_h_
1.12 +
1.13 +#include "ds/LifoAlloc.h"
1.14 +
1.15 +namespace js {
1.16 +
1.17 +/*
1.18 + * Class representing a hash set with fixed capacity, with newer entries
1.19 + * evicting older entries. Each entry has several hashes and can be stored in
1.20 + * different buckets, with the choice of which to evict on insertion being
1.21 + * managed via LRU. For tables with a relatively small size, using different
1.22 + * hashes increases utilization and makes it less likely that entries will keep
1.23 + * evicting each other due to wanting to use the same bucket.
1.24 + *
1.25 + * T indicates the type of hash elements, HashPolicy must have the following
1.26 + * contents:
1.27 + *
1.28 + * Lookup - As for HashMap / HashSet.
1.29 + *
1.30 + * bool match(T, Lookup) - As for HashMap / HashSet.
1.31 + *
1.32 + * NumHashes - Number of different hashes generated for each entry.
1.33 + *
1.34 + * void hash(Lookup, HashNumber[NumHashes]) - Compute all hashes for an entry.
1.35 + *
1.36 + * void clear(T *) - Clear an entry, such that isCleared() holds afterwards.
1.37 + *
1.38 + * bool isCleared(T) - Test whether an entry has been cleared.
1.39 + */
1.40 +template <class T, class HashPolicy, size_t Capacity>
1.41 +class FixedSizeHashSet
1.42 +{
1.43 + T entries[Capacity];
1.44 + uint32_t lastOperations[Capacity];
1.45 + uint32_t numOperations;
1.46 +
1.47 + static const size_t NumHashes = HashPolicy::NumHashes;
1.48 +
1.49 + public:
1.50 + typedef typename HashPolicy::Lookup Lookup;
1.51 +
1.52 + FixedSizeHashSet()
1.53 + : entries(), lastOperations(), numOperations(0)
1.54 + {
1.55 + JS_STATIC_ASSERT(Capacity > 0);
1.56 + JS_ASSERT(HashPolicy::isCleared(entries[0]));
1.57 + }
1.58 +
1.59 + bool lookup(const Lookup &lookup, T *pentry)
1.60 + {
1.61 + size_t bucket;
1.62 + if (lookupReference(lookup, &bucket)) {
1.63 + *pentry = entries[bucket];
1.64 + lastOperations[bucket] = numOperations++;
1.65 + return true;
1.66 + }
1.67 + return false;
1.68 + }
1.69 +
1.70 + void insert(const Lookup &lookup, const T &entry)
1.71 + {
1.72 + size_t buckets[NumHashes];
1.73 + getBuckets(lookup, buckets);
1.74 +
1.75 + size_t min = buckets[0];
1.76 + for (size_t i = 0; i < NumHashes; i++) {
1.77 + const T &entry = entries[buckets[i]];
1.78 + if (HashPolicy::isCleared(entry)) {
1.79 + entries[buckets[i]] = entry;
1.80 + lastOperations[buckets[i]] = numOperations++;
1.81 + return;
1.82 + }
1.83 + if (i && lastOperations[min] > lastOperations[buckets[i]])
1.84 + min = buckets[i];
1.85 + }
1.86 +
1.87 + entries[min] = entry;
1.88 + lastOperations[min] = numOperations++;
1.89 + }
1.90 +
1.91 + template <typename S>
1.92 + void remove(const S &s)
1.93 + {
1.94 + size_t bucket;
1.95 + if (lookupReference(s, &bucket))
1.96 + HashPolicy::clear(&entries[bucket]);
1.97 + }
1.98 +
1.99 + private:
1.100 + template <typename S>
1.101 + bool lookupReference(const S &s, size_t *pbucket)
1.102 + {
1.103 + size_t buckets[NumHashes];
1.104 + getBuckets(s, buckets);
1.105 +
1.106 + for (size_t i = 0; i < NumHashes; i++) {
1.107 + const T &entry = entries[buckets[i]];
1.108 + if (!HashPolicy::isCleared(entry) && HashPolicy::match(entry, s)) {
1.109 + *pbucket = buckets[i];
1.110 + return true;
1.111 + }
1.112 + }
1.113 +
1.114 + return false;
1.115 + }
1.116 +
1.117 + template <typename S>
1.118 + void getBuckets(const S &s, size_t buckets[NumHashes])
1.119 + {
1.120 + HashNumber hashes[NumHashes];
1.121 + HashPolicy::hash(s, hashes);
1.122 +
1.123 + for (size_t i = 0; i < NumHashes; i++)
1.124 + buckets[i] = hashes[i] % Capacity;
1.125 + }
1.126 +};
1.127 +
1.128 +} /* namespace js */
1.129 +
1.130 +#endif /* jsfixedsizehash_h_ */
