/* -*- 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 "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;

  public:
    typedef typename HashPolicy::Lookup Lookup;

    FixedSizeHashSet()
      : entries(), lastOperations(), numOperations(0)
    {
        JS_STATIC_ASSERT(Capacity > 0);
        JS_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_ */