Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       3             :  * This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef jsfixedsizehash_h_
       8             : #define jsfixedsizehash_h_
       9             : 
      10             : #include "ds/LifoAlloc.h"
      11             : 
      12             : namespace js {
      13             : 
      14             : /*
      15             :  * Class representing a hash set with fixed capacity, with newer entries
      16             :  * evicting older entries. Each entry has several hashes and can be stored in
      17             :  * different buckets, with the choice of which to evict on insertion being
      18             :  * managed via LRU. For tables with a relatively small size, using different
      19             :  * hashes increases utilization and makes it less likely that entries will keep
      20             :  * evicting each other due to wanting to use the same bucket.
      21             :  *
      22             :  * T indicates the type of hash elements, HashPolicy must have the following
      23             :  * contents:
      24             :  *
      25             :  * Lookup - As for HashMap / HashSet.
      26             :  *
      27             :  * bool match(T, Lookup) - As for HashMap / HashSet.
      28             :  *
      29             :  * NumHashes - Number of different hashes generated for each entry.
      30             :  *
      31             :  * void hash(Lookup, HashNumber[NumHashes]) - Compute all hashes for an entry.
      32             :  *
      33             :  * void clear(T*) - Clear an entry, such that isCleared() holds afterwards.
      34             :  *
      35             :  * bool isCleared(T) - Test whether an entry has been cleared.
      36             :  */
      37             : template <class T, class HashPolicy, size_t Capacity>
      38             : class FixedSizeHashSet
      39             : {
      40             :     T entries[Capacity];
      41             :     uint32_t lastOperations[Capacity];
      42             :     uint32_t numOperations;
      43             : 
      44             :     static const size_t NumHashes = HashPolicy::NumHashes;
      45             : 
      46             :     static_assert(Capacity > 0, "an empty fixed-size hash set is meaningless");
      47             : 
      48             :   public:
      49             :     typedef typename HashPolicy::Lookup Lookup;
      50             : 
      51           4 :     FixedSizeHashSet()
      52           4 :       : entries(), lastOperations(), numOperations(0)
      53             :     {
      54           4 :         MOZ_ASSERT(HashPolicy::isCleared(entries[0]));
      55           4 :     }
      56             : 
      57        1212 :     bool lookup(const Lookup& lookup, T* pentry)
      58             :     {
      59             :         size_t bucket;
      60        1212 :         if (lookupReference(lookup, &bucket)) {
      61           0 :             *pentry = entries[bucket];
      62           0 :             lastOperations[bucket] = numOperations++;
      63           0 :             return true;
      64             :         }
      65        1212 :         return false;
      66             :     }
      67             : 
      68        1211 :     void insert(const Lookup& lookup, const T& entry)
      69             :     {
      70             :         size_t buckets[NumHashes];
      71        1211 :         getBuckets(lookup, buckets);
      72             : 
      73        1211 :         size_t min = buckets[0];
      74        1211 :         for (size_t i = 0; i < NumHashes; i++) {
      75        1211 :             const T& entry = entries[buckets[i]];
      76        1211 :             if (HashPolicy::isCleared(entry)) {
      77        1211 :                 entries[buckets[i]] = entry;
      78        1211 :                 lastOperations[buckets[i]] = numOperations++;
      79        2422 :                 return;
      80             :             }
      81           0 :             if (i && lastOperations[min] > lastOperations[buckets[i]])
      82           0 :                 min = buckets[i];
      83             :         }
      84             : 
      85           0 :         entries[min] = entry;
      86           0 :         lastOperations[min] = numOperations++;
      87             :     }
      88             : 
      89             :     template <typename S>
      90           0 :     void remove(const S& s)
      91             :     {
      92             :         size_t bucket;
      93           0 :         if (lookupReference(s, &bucket))
      94           0 :             HashPolicy::clear(&entries[bucket]);
      95           0 :     }
      96             : 
      97             :   private:
      98             :     template <typename S>
      99        1211 :     bool lookupReference(const S& s, size_t* pbucket)
     100             :     {
     101             :         size_t buckets[NumHashes];
     102        1211 :         getBuckets(s, buckets);
     103             : 
     104        4844 :         for (size_t i = 0; i < NumHashes; i++) {
     105        3633 :             const T& entry = entries[buckets[i]];
     106        3633 :             if (!HashPolicy::isCleared(entry) && HashPolicy::match(entry, s)) {
     107           0 :                 *pbucket = buckets[i];
     108           0 :                 return true;
     109             :             }
     110             :         }
     111             : 
     112        1211 :         return false;
     113             :     }
     114             : 
     115             :     template <typename S>
     116        2422 :     void getBuckets(const S& s, size_t buckets[NumHashes])
     117             :     {
     118             :         HashNumber hashes[NumHashes];
     119        2422 :         HashPolicy::hash(s, hashes);
     120             : 
     121        9688 :         for (size_t i = 0; i < NumHashes; i++)
     122        7266 :             buckets[i] = hashes[i] % Capacity;
     123        2422 :     }
     124             : };
     125             : 
     126             : }  /* namespace js */
     127             : 
     128             : #endif /* jsfixedsizehash_h_ */