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