1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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_ */
|
