1 files changed, 128 insertions, 0 deletions
diff --git a/js/src/ds/FixedSizeHash.h b/js/src/ds/FixedSizeHash.h
new file mode 100644
index 000000000..9b4752a4f
--- /dev/null
+++ b/js/src/ds/FixedSizeHash.h
@@ -0,0 +1,128 @@
+/* -*- 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_ */