Source code

Revision control

Other Tools

1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
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
//---------------------------------------------------------------------------
8
// Overview
9
//---------------------------------------------------------------------------
10
//
11
// This file defines HashMap<Key, Value> and HashSet<T>, hash tables that are
12
// fast and have a nice API.
13
//
14
// Both hash tables have two optional template parameters.
15
//
16
// - HashPolicy. This defines the operations for hashing and matching keys. The
17
// default HashPolicy is appropriate when both of the following two
18
// conditions are true.
19
//
20
// - The key type stored in the table (|Key| for |HashMap<Key, Value>|, |T|
21
// for |HashSet<T>|) is an integer, pointer, UniquePtr, float, or double.
22
//
23
// - The type used for lookups (|Lookup|) is the same as the key type. This
24
// is usually the case, but not always.
25
//
26
// There is also a |CStringHasher| policy for |char*| keys. If your keys
27
// don't match any of the above cases, you must provide your own hash policy;
28
// see the "Hash Policy" section below.
29
//
30
// - AllocPolicy. This defines how allocations are done by the table.
31
//
32
// - |MallocAllocPolicy| is the default and is usually appropriate; note that
33
// operations (such as insertions) that might cause allocations are
34
// fallible and must be checked for OOM. These checks are enforced by the
35
// use of MOZ_MUST_USE.
36
//
37
// - |InfallibleAllocPolicy| is another possibility; it allows the
38
// abovementioned OOM checks to be done with MOZ_ALWAYS_TRUE().
39
//
40
// Note that entry storage allocation is lazy, and not done until the first
41
// lookupForAdd(), put(), or putNew() is performed.
42
//
43
// See AllocPolicy.h for more details.
44
//
45
// Documentation on how to use HashMap and HashSet, including examples, is
46
// present within those classes. Search for "class HashMap" and "class
47
// HashSet".
48
//
49
// Both HashMap and HashSet are implemented on top of a third class, HashTable.
50
// You only need to look at HashTable if you want to understand the
51
// implementation.
52
//
53
// How does mozilla::HashTable (this file) compare with PLDHashTable (and its
54
// subclasses, such as nsTHashtable)?
55
//
56
// - mozilla::HashTable is a lot faster, largely because it uses templates
57
// throughout *and* inlines everything. PLDHashTable inlines operations much
58
// less aggressively, and also uses "virtual ops" for operations like hashing
59
// and matching entries that require function calls.
60
//
61
// - Correspondingly, mozilla::HashTable use is likely to increase executable
62
// size much more than PLDHashTable.
63
//
64
// - mozilla::HashTable has a nicer API, with a proper HashSet vs. HashMap
65
// distinction.
66
//
67
// - mozilla::HashTable requires more explicit OOM checking. As mentioned
68
// above, the use of |InfallibleAllocPolicy| can simplify things.
69
//
70
// - mozilla::HashTable has a default capacity on creation of 32 and a minimum
71
// capacity of 4. PLDHashTable has a default capacity on creation of 8 and a
72
// minimum capacity of 8.
73
74
#ifndef mozilla_HashTable_h
75
#define mozilla_HashTable_h
76
77
#include "mozilla/AllocPolicy.h"
78
#include "mozilla/Assertions.h"
79
#include "mozilla/Attributes.h"
80
#include "mozilla/Casting.h"
81
#include "mozilla/HashFunctions.h"
82
#include "mozilla/MathAlgorithms.h"
83
#include "mozilla/Maybe.h"
84
#include "mozilla/MemoryChecking.h"
85
#include "mozilla/MemoryReporting.h"
86
#include "mozilla/Move.h"
87
#include "mozilla/Opaque.h"
88
#include "mozilla/OperatorNewExtensions.h"
89
#include "mozilla/PodOperations.h"
90
#include "mozilla/ReentrancyGuard.h"
91
#include "mozilla/TypeTraits.h"
92
#include "mozilla/UniquePtr.h"
93
94
namespace mozilla {
95
96
template <class>
97
struct DefaultHasher;
98
99
template <class, class>
100
class HashMapEntry;
101
102
namespace detail {
103
104
template <typename T>
105
class HashTableEntry;
106
107
template <class T, class HashPolicy, class AllocPolicy>
108
class HashTable;
109
110
} // namespace detail
111
112
// The "generation" of a hash table is an opaque value indicating the state of
113
// modification of the hash table through its lifetime. If the generation of
114
// a hash table compares equal at times T1 and T2, then lookups in the hash
115
// table, pointers to (or into) hash table entries, etc. at time T1 are valid
116
// at time T2. If the generation compares unequal, these computations are all
117
// invalid and must be performed again to be used.
118
//
119
// Generations are meaningfully comparable only with respect to a single hash
120
// table. It's always nonsensical to compare the generation of distinct hash
121
// tables H1 and H2.
122
using Generation = Opaque<uint64_t>;
123
124
//---------------------------------------------------------------------------
125
// HashMap
126
//---------------------------------------------------------------------------
127
128
// HashMap is a fast hash-based map from keys to values.
129
//
130
// Template parameter requirements:
131
// - Key/Value: movable, destructible, assignable.
132
// - HashPolicy: see the "Hash Policy" section below.
133
// - AllocPolicy: see AllocPolicy.h.
134
//
135
// Note:
136
// - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
137
// called by HashMap must not call back into the same HashMap object.
138
//
139
template <class Key, class Value, class HashPolicy = DefaultHasher<Key>,
140
class AllocPolicy = MallocAllocPolicy>
141
class HashMap {
142
// -- Implementation details -----------------------------------------------
143
144
// HashMap is not copyable or assignable.
145
HashMap(const HashMap& hm) = delete;
146
HashMap& operator=(const HashMap& hm) = delete;
147
148
using TableEntry = HashMapEntry<Key, Value>;
149
150
struct MapHashPolicy : HashPolicy {
151
using Base = HashPolicy;
152
using KeyType = Key;
153
154
static const Key& getKey(TableEntry& aEntry) { return aEntry.key(); }
155
156
static void setKey(TableEntry& aEntry, Key& aKey) {
157
HashPolicy::rekey(aEntry.mutableKey(), aKey);
158
}
159
};
160
161
using Impl = detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy>;
162
Impl mImpl;
163
164
friend class Impl::Enum;
165
166
public:
167
using Lookup = typename HashPolicy::Lookup;
168
using Entry = TableEntry;
169
170
// -- Initialization -------------------------------------------------------
171
172
explicit HashMap(AllocPolicy aAllocPolicy = AllocPolicy(),
173
uint32_t aLen = Impl::sDefaultLen)
174
: mImpl(std::move(aAllocPolicy), aLen) {}
175
176
explicit HashMap(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
177
178
// HashMap is movable.
179
HashMap(HashMap&& aRhs) : mImpl(std::move(aRhs.mImpl)) {}
180
void operator=(HashMap&& aRhs) {
181
MOZ_ASSERT(this != &aRhs, "self-move assignment is prohibited");
182
mImpl = std::move(aRhs.mImpl);
183
}
184
185
// -- Status and sizing ----------------------------------------------------
186
187
// The map's current generation.
188
Generation generation() const { return mImpl.generation(); }
189
190
// Is the map empty?
191
bool empty() const { return mImpl.empty(); }
192
193
// Number of keys/values in the map.
194
uint32_t count() const { return mImpl.count(); }
195
196
// Number of key/value slots in the map. Note: resize will happen well before
197
// count() == capacity().
198
uint32_t capacity() const { return mImpl.capacity(); }
199
200
// The size of the map's entry storage, in bytes. If the keys/values contain
201
// pointers to other heap blocks, you must iterate over the map and measure
202
// them separately; hence the "shallow" prefix.
203
size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
204
return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
205
}
206
size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
207
return aMallocSizeOf(this) +
208
mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
209
}
210
211
// Attempt to minimize the capacity(). If the table is empty, this will free
212
// the empty storage and upon regrowth it will be given the minimum capacity.
213
void compact() { mImpl.compact(); }
214
215
// Attempt to reserve enough space to fit at least |aLen| elements. Does
216
// nothing if the map already has sufficient capacity.
217
MOZ_MUST_USE bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
218
219
// -- Lookups --------------------------------------------------------------
220
221
// Does the map contain a key/value matching |aLookup|?
222
bool has(const Lookup& aLookup) const {
223
return mImpl.lookup(aLookup).found();
224
}
225
226
// Return a Ptr indicating whether a key/value matching |aLookup| is
227
// present in the map. E.g.:
228
//
229
// using HM = HashMap<int,char>;
230
// HM h;
231
// if (HM::Ptr p = h.lookup(3)) {
232
// assert(p->key() == 3);
233
// char val = p->value();
234
// }
235
//
236
using Ptr = typename Impl::Ptr;
237
MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& aLookup) const {
238
return mImpl.lookup(aLookup);
239
}
240
241
// Like lookup(), but does not assert if two threads call it at the same
242
// time. Only use this method when none of the threads will modify the map.
243
MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
244
return mImpl.readonlyThreadsafeLookup(aLookup);
245
}
246
247
// -- Insertions -----------------------------------------------------------
248
249
// Overwrite existing value with |aValue|, or add it if not present. Returns
250
// false on OOM.
251
template <typename KeyInput, typename ValueInput>
252
MOZ_MUST_USE bool put(KeyInput&& aKey, ValueInput&& aValue) {
253
AddPtr p = lookupForAdd(aKey);
254
if (p) {
255
p->value() = std::forward<ValueInput>(aValue);
256
return true;
257
}
258
return add(p, std::forward<KeyInput>(aKey),
259
std::forward<ValueInput>(aValue));
260
}
261
262
// Like put(), but slightly faster. Must only be used when the given key is
263
// not already present. (In debug builds, assertions check this.)
264
template <typename KeyInput, typename ValueInput>
265
MOZ_MUST_USE bool putNew(KeyInput&& aKey, ValueInput&& aValue) {
266
return mImpl.putNew(aKey, std::forward<KeyInput>(aKey),
267
std::forward<ValueInput>(aValue));
268
}
269
270
// Like putNew(), but should be only used when the table is known to be big
271
// enough for the insertion, and hashing cannot fail. Typically this is used
272
// to populate an empty map with known-unique keys after reserving space with
273
// reserve(), e.g.
274
//
275
// using HM = HashMap<int,char>;
276
// HM h;
277
// if (!h.reserve(3)) {
278
// MOZ_CRASH("OOM");
279
// }
280
// h.putNewInfallible(1, 'a'); // unique key
281
// h.putNewInfallible(2, 'b'); // unique key
282
// h.putNewInfallible(3, 'c'); // unique key
283
//
284
template <typename KeyInput, typename ValueInput>
285
void putNewInfallible(KeyInput&& aKey, ValueInput&& aValue) {
286
mImpl.putNewInfallible(aKey, std::forward<KeyInput>(aKey),
287
std::forward<ValueInput>(aValue));
288
}
289
290
// Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
291
// insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
292
// |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
293
//
294
// using HM = HashMap<int,char>;
295
// HM h;
296
// HM::AddPtr p = h.lookupForAdd(3);
297
// if (!p) {
298
// if (!h.add(p, 3, 'a')) {
299
// return false;
300
// }
301
// }
302
// assert(p->key() == 3);
303
// char val = p->value();
304
//
305
// N.B. The caller must ensure that no mutating hash table operations occur
306
// between a pair of lookupForAdd() and add() calls. To avoid looking up the
307
// key a second time, the caller may use the more efficient relookupOrAdd()
308
// method. This method reuses part of the hashing computation to more
309
// efficiently insert the key if it has not been added. For example, a
310
// mutation-handling version of the previous example:
311
//
312
// HM::AddPtr p = h.lookupForAdd(3);
313
// if (!p) {
314
// call_that_may_mutate_h();
315
// if (!h.relookupOrAdd(p, 3, 'a')) {
316
// return false;
317
// }
318
// }
319
// assert(p->key() == 3);
320
// char val = p->value();
321
//
322
using AddPtr = typename Impl::AddPtr;
323
MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& aLookup) {
324
return mImpl.lookupForAdd(aLookup);
325
}
326
327
// Add a key/value. Returns false on OOM.
328
template <typename KeyInput, typename ValueInput>
329
MOZ_MUST_USE bool add(AddPtr& aPtr, KeyInput&& aKey, ValueInput&& aValue) {
330
return mImpl.add(aPtr, std::forward<KeyInput>(aKey),
331
std::forward<ValueInput>(aValue));
332
}
333
334
// See the comment above lookupForAdd() for details.
335
template <typename KeyInput, typename ValueInput>
336
MOZ_MUST_USE bool relookupOrAdd(AddPtr& aPtr, KeyInput&& aKey,
337
ValueInput&& aValue) {
338
return mImpl.relookupOrAdd(aPtr, aKey, std::forward<KeyInput>(aKey),
339
std::forward<ValueInput>(aValue));
340
}
341
342
// -- Removal --------------------------------------------------------------
343
344
// Lookup and remove the key/value matching |aLookup|, if present.
345
void remove(const Lookup& aLookup) {
346
if (Ptr p = lookup(aLookup)) {
347
remove(p);
348
}
349
}
350
351
// Remove a previously found key/value (assuming aPtr.found()). The map must
352
// not have been mutated in the interim.
353
void remove(Ptr aPtr) { mImpl.remove(aPtr); }
354
355
// Remove all keys/values without changing the capacity.
356
void clear() { mImpl.clear(); }
357
358
// Like clear() followed by compact().
359
void clearAndCompact() { mImpl.clearAndCompact(); }
360
361
// -- Rekeying -------------------------------------------------------------
362
363
// Infallibly rekey one entry, if necessary. Requires that template
364
// parameters Key and HashPolicy::Lookup are the same type.
365
void rekeyIfMoved(const Key& aOldKey, const Key& aNewKey) {
366
if (aOldKey != aNewKey) {
367
rekeyAs(aOldKey, aNewKey, aNewKey);
368
}
369
}
370
371
// Infallibly rekey one entry if present, and return whether that happened.
372
bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
373
const Key& aNewKey) {
374
if (Ptr p = lookup(aOldLookup)) {
375
mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewKey);
376
return true;
377
}
378
return false;
379
}
380
381
// -- Iteration ------------------------------------------------------------
382
383
// |iter()| returns an Iterator:
384
//
385
// HashMap<int, char> h;
386
// for (auto iter = h.iter(); !iter.done(); iter.next()) {
387
// char c = iter.get().value();
388
// }
389
//
390
using Iterator = typename Impl::Iterator;
391
Iterator iter() const { return mImpl.iter(); }
392
393
// |modIter()| returns a ModIterator:
394
//
395
// HashMap<int, char> h;
396
// for (auto iter = h.modIter(); !iter.done(); iter.next()) {
397
// if (iter.get().value() == 'l') {
398
// iter.remove();
399
// }
400
// }
401
//
402
// Table resize may occur in ModIterator's destructor.
403
using ModIterator = typename Impl::ModIterator;
404
ModIterator modIter() { return mImpl.modIter(); }
405
406
// These are similar to Iterator/ModIterator/iter(), but use different
407
// terminology.
408
using Range = typename Impl::Range;
409
using Enum = typename Impl::Enum;
410
Range all() const { return mImpl.all(); }
411
};
412
413
//---------------------------------------------------------------------------
414
// HashSet
415
//---------------------------------------------------------------------------
416
417
// HashSet is a fast hash-based set of values.
418
//
419
// Template parameter requirements:
420
// - T: movable, destructible, assignable.
421
// - HashPolicy: see the "Hash Policy" section below.
422
// - AllocPolicy: see AllocPolicy.h
423
//
424
// Note:
425
// - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
426
// HashSet must not call back into the same HashSet object.
427
//
428
template <class T, class HashPolicy = DefaultHasher<T>,
429
class AllocPolicy = MallocAllocPolicy>
430
class HashSet {
431
// -- Implementation details -----------------------------------------------
432
433
// HashSet is not copyable or assignable.
434
HashSet(const HashSet& hs) = delete;
435
HashSet& operator=(const HashSet& hs) = delete;
436
437
struct SetHashPolicy : HashPolicy {
438
using Base = HashPolicy;
439
using KeyType = T;
440
441
static const KeyType& getKey(const T& aT) { return aT; }
442
443
static void setKey(T& aT, KeyType& aKey) { HashPolicy::rekey(aT, aKey); }
444
};
445
446
using Impl = detail::HashTable<const T, SetHashPolicy, AllocPolicy>;
447
Impl mImpl;
448
449
friend class Impl::Enum;
450
451
public:
452
using Lookup = typename HashPolicy::Lookup;
453
using Entry = T;
454
455
// -- Initialization -------------------------------------------------------
456
457
explicit HashSet(AllocPolicy aAllocPolicy = AllocPolicy(),
458
uint32_t aLen = Impl::sDefaultLen)
459
: mImpl(std::move(aAllocPolicy), aLen) {}
460
461
explicit HashSet(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
462
463
// HashSet is movable.
464
HashSet(HashSet&& aRhs) : mImpl(std::move(aRhs.mImpl)) {}
465
void operator=(HashSet&& aRhs) {
466
MOZ_ASSERT(this != &aRhs, "self-move assignment is prohibited");
467
mImpl = std::move(aRhs.mImpl);
468
}
469
470
// -- Status and sizing ----------------------------------------------------
471
472
// The set's current generation.
473
Generation generation() const { return mImpl.generation(); }
474
475
// Is the set empty?
476
bool empty() const { return mImpl.empty(); }
477
478
// Number of elements in the set.
479
uint32_t count() const { return mImpl.count(); }
480
481
// Number of element slots in the set. Note: resize will happen well before
482
// count() == capacity().
483
uint32_t capacity() const { return mImpl.capacity(); }
484
485
// The size of the set's entry storage, in bytes. If the elements contain
486
// pointers to other heap blocks, you must iterate over the set and measure
487
// them separately; hence the "shallow" prefix.
488
size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
489
return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
490
}
491
size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
492
return aMallocSizeOf(this) +
493
mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
494
}
495
496
// Attempt to minimize the capacity(). If the table is empty, this will free
497
// the empty storage and upon regrowth it will be given the minimum capacity.
498
void compact() { mImpl.compact(); }
499
500
// Attempt to reserve enough space to fit at least |aLen| elements. Does
501
// nothing if the map already has sufficient capacity.
502
MOZ_MUST_USE bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
503
504
// -- Lookups --------------------------------------------------------------
505
506
// Does the set contain an element matching |aLookup|?
507
bool has(const Lookup& aLookup) const {
508
return mImpl.lookup(aLookup).found();
509
}
510
511
// Return a Ptr indicating whether an element matching |aLookup| is present
512
// in the set. E.g.:
513
//
514
// using HS = HashSet<int>;
515
// HS h;
516
// if (HS::Ptr p = h.lookup(3)) {
517
// assert(*p == 3); // p acts like a pointer to int
518
// }
519
//
520
using Ptr = typename Impl::Ptr;
521
MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& aLookup) const {
522
return mImpl.lookup(aLookup);
523
}
524
525
// Like lookup(), but does not assert if two threads call it at the same
526
// time. Only use this method when none of the threads will modify the set.
527
MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
528
return mImpl.readonlyThreadsafeLookup(aLookup);
529
}
530
531
// -- Insertions -----------------------------------------------------------
532
533
// Add |aU| if it is not present already. Returns false on OOM.
534
template <typename U>
535
MOZ_MUST_USE bool put(U&& aU) {
536
AddPtr p = lookupForAdd(aU);
537
return p ? true : add(p, std::forward<U>(aU));
538
}
539
540
// Like put(), but slightly faster. Must only be used when the given element
541
// is not already present. (In debug builds, assertions check this.)
542
template <typename U>
543
MOZ_MUST_USE bool putNew(U&& aU) {
544
return mImpl.putNew(aU, std::forward<U>(aU));
545
}
546
547
// Like the other putNew(), but for when |Lookup| is different to |T|.
548
template <typename U>
549
MOZ_MUST_USE bool putNew(const Lookup& aLookup, U&& aU) {
550
return mImpl.putNew(aLookup, std::forward<U>(aU));
551
}
552
553
// Like putNew(), but should be only used when the table is known to be big
554
// enough for the insertion, and hashing cannot fail. Typically this is used
555
// to populate an empty set with known-unique elements after reserving space
556
// with reserve(), e.g.
557
//
558
// using HS = HashMap<int>;
559
// HS h;
560
// if (!h.reserve(3)) {
561
// MOZ_CRASH("OOM");
562
// }
563
// h.putNewInfallible(1); // unique element
564
// h.putNewInfallible(2); // unique element
565
// h.putNewInfallible(3); // unique element
566
//
567
template <typename U>
568
void putNewInfallible(const Lookup& aLookup, U&& aU) {
569
mImpl.putNewInfallible(aLookup, std::forward<U>(aU));
570
}
571
572
// Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
573
// insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
574
// |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
575
//
576
// using HS = HashSet<int>;
577
// HS h;
578
// HS::AddPtr p = h.lookupForAdd(3);
579
// if (!p) {
580
// if (!h.add(p, 3)) {
581
// return false;
582
// }
583
// }
584
// assert(*p == 3); // p acts like a pointer to int
585
//
586
// N.B. The caller must ensure that no mutating hash table operations occur
587
// between a pair of lookupForAdd() and add() calls. To avoid looking up the
588
// key a second time, the caller may use the more efficient relookupOrAdd()
589
// method. This method reuses part of the hashing computation to more
590
// efficiently insert the key if it has not been added. For example, a
591
// mutation-handling version of the previous example:
592
//
593
// HS::AddPtr p = h.lookupForAdd(3);
594
// if (!p) {
595
// call_that_may_mutate_h();
596
// if (!h.relookupOrAdd(p, 3, 3)) {
597
// return false;
598
// }
599
// }
600
// assert(*p == 3);
601
//
602
// Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
603
// entry |t|, where the caller ensures match(l,t).
604
using AddPtr = typename Impl::AddPtr;
605
MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& aLookup) {
606
return mImpl.lookupForAdd(aLookup);
607
}
608
609
// Add an element. Returns false on OOM.
610
template <typename U>
611
MOZ_MUST_USE bool add(AddPtr& aPtr, U&& aU) {
612
return mImpl.add(aPtr, std::forward<U>(aU));
613
}
614
615
// See the comment above lookupForAdd() for details.
616
template <typename U>
617
MOZ_MUST_USE bool relookupOrAdd(AddPtr& aPtr, const Lookup& aLookup, U&& aU) {
618
return mImpl.relookupOrAdd(aPtr, aLookup, std::forward<U>(aU));
619
}
620
621
// -- Removal --------------------------------------------------------------
622
623
// Lookup and remove the element matching |aLookup|, if present.
624
void remove(const Lookup& aLookup) {
625
if (Ptr p = lookup(aLookup)) {
626
remove(p);
627
}
628
}
629
630
// Remove a previously found element (assuming aPtr.found()). The set must
631
// not have been mutated in the interim.
632
void remove(Ptr aPtr) { mImpl.remove(aPtr); }
633
634
// Remove all keys/values without changing the capacity.
635
void clear() { mImpl.clear(); }
636
637
// Like clear() followed by compact().
638
void clearAndCompact() { mImpl.clearAndCompact(); }
639
640
// -- Rekeying -------------------------------------------------------------
641
642
// Infallibly rekey one entry, if present. Requires that template parameters
643
// T and HashPolicy::Lookup are the same type.
644
void rekeyIfMoved(const Lookup& aOldValue, const T& aNewValue) {
645
if (aOldValue != aNewValue) {
646
rekeyAs(aOldValue, aNewValue, aNewValue);
647
}
648
}
649
650
// Infallibly rekey one entry if present, and return whether that happened.
651
bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
652
const T& aNewValue) {
653
if (Ptr p = lookup(aOldLookup)) {
654
mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewValue);
655
return true;
656
}
657
return false;
658
}
659
660
// Infallibly replace the current key at |aPtr| with an equivalent key.
661
// Specifically, both HashPolicy::hash and HashPolicy::match must return
662
// identical results for the new and old key when applied against all
663
// possible matching values.
664
void replaceKey(Ptr aPtr, const T& aNewValue) {
665
MOZ_ASSERT(aPtr.found());
666
MOZ_ASSERT(*aPtr != aNewValue);
667
MOZ_ASSERT(HashPolicy::hash(*aPtr) == HashPolicy::hash(aNewValue));
668
MOZ_ASSERT(HashPolicy::match(*aPtr, aNewValue));
669
const_cast<T&>(*aPtr) = aNewValue;
670
}
671
672
// -- Iteration ------------------------------------------------------------
673
674
// |iter()| returns an Iterator:
675
//
676
// HashSet<int> h;
677
// for (auto iter = h.iter(); !iter.done(); iter.next()) {
678
// int i = iter.get();
679
// }
680
//
681
using Iterator = typename Impl::Iterator;
682
Iterator iter() const { return mImpl.iter(); }
683
684
// |modIter()| returns a ModIterator:
685
//
686
// HashSet<int> h;
687
// for (auto iter = h.modIter(); !iter.done(); iter.next()) {
688
// if (iter.get() == 42) {
689
// iter.remove();
690
// }
691
// }
692
//
693
// Table resize may occur in ModIterator's destructor.
694
using ModIterator = typename Impl::ModIterator;
695
ModIterator modIter() { return mImpl.modIter(); }
696
697
// These are similar to Iterator/ModIterator/iter(), but use different
698
// terminology.
699
using Range = typename Impl::Range;
700
using Enum = typename Impl::Enum;
701
Range all() const { return mImpl.all(); }
702
};
703
704
//---------------------------------------------------------------------------
705
// Hash Policy
706
//---------------------------------------------------------------------------
707
708
// A hash policy |HP| for a hash table with key-type |Key| must provide:
709
//
710
// - a type |HP::Lookup| to use to lookup table entries;
711
//
712
// - a static member function |HP::hash| that hashes lookup values:
713
//
714
// static mozilla::HashNumber hash(const Lookup&);
715
//
716
// - a static member function |HP::match| that tests equality of key and
717
// lookup values:
718
//
719
// static bool match(const Key&, const Lookup&);
720
//
721
// Normally, Lookup = Key. In general, though, different values and types of
722
// values can be used to lookup and store. If a Lookup value |l| is not equal
723
// to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
724
// true. E.g.:
725
//
726
// mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
727
// if (!p) {
728
// assert(HP::match(k, l)); // must hold
729
// h.add(p, k);
730
// }
731
732
// A pointer hashing policy that uses HashGeneric() to create good hashes for
733
// pointers. Note that we don't shift out the lowest k bits because we don't
734
// want to assume anything about the alignment of the pointers.
735
template <typename Key>
736
struct PointerHasher {
737
using Lookup = Key;
738
739
static HashNumber hash(const Lookup& aLookup) {
740
size_t word = reinterpret_cast<size_t>(aLookup);
741
return HashGeneric(word);
742
}
743
744
static bool match(const Key& aKey, const Lookup& aLookup) {
745
return aKey == aLookup;
746
}
747
748
static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
749
};
750
751
// The default hash policy, which only works with integers.
752
template <class Key>
753
struct DefaultHasher {
754
using Lookup = Key;
755
756
static HashNumber hash(const Lookup& aLookup) {
757
// Just convert the integer to a HashNumber and use that as is. (This
758
// discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
759
// subsequently called on the value to improve the distribution.
760
return aLookup;
761
}
762
763
static bool match(const Key& aKey, const Lookup& aLookup) {
764
// Use builtin or overloaded operator==.
765
return aKey == aLookup;
766
}
767
768
static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
769
};
770
771
// A DefaultHasher specialization for pointers.
772
template <class T>
773
struct DefaultHasher<T*> : PointerHasher<T*> {};
774
775
// A DefaultHasher specialization for mozilla::UniquePtr.
776
template <class T, class D>
777
struct DefaultHasher<UniquePtr<T, D>> {
778
using Key = UniquePtr<T, D>;
779
using Lookup = Key;
780
using PtrHasher = PointerHasher<T*>;
781
782
static HashNumber hash(const Lookup& aLookup) {
783
return PtrHasher::hash(aLookup.get());
784
}
785
786
static bool match(const Key& aKey, const Lookup& aLookup) {
787
return PtrHasher::match(aKey.get(), aLookup.get());
788
}
789
790
static void rekey(UniquePtr<T, D>& aKey, UniquePtr<T, D>&& aNewKey) {
791
aKey = std::move(aNewKey);
792
}
793
};
794
795
// A DefaultHasher specialization for doubles.
796
template <>
797
struct DefaultHasher<double> {
798
using Key = double;
799
using Lookup = Key;
800
801
static HashNumber hash(const Lookup& aLookup) {
802
// Just xor the high bits with the low bits, and then treat the bits of the
803
// result as a uint32_t.
804
static_assert(sizeof(HashNumber) == 4,
805
"subsequent code assumes a four-byte hash");
806
uint64_t u = BitwiseCast<uint64_t>(aLookup);
807
return HashNumber(u ^ (u >> 32));
808
}
809
810
static bool match(const Key& aKey, const Lookup& aLookup) {
811
return BitwiseCast<uint64_t>(aKey) == BitwiseCast<uint64_t>(aLookup);
812
}
813
};
814
815
// A DefaultHasher specialization for floats.
816
template <>
817
struct DefaultHasher<float> {
818
using Key = float;
819
using Lookup = Key;
820
821
static HashNumber hash(const Lookup& aLookup) {
822
// Just use the value as if its bits form an integer. ScrambleHashCode() is
823
// subsequently called on the value to improve the distribution.
824
static_assert(sizeof(HashNumber) == 4,
825
"subsequent code assumes a four-byte hash");
826
return HashNumber(BitwiseCast<uint32_t>(aLookup));
827
}
828
829
static bool match(const Key& aKey, const Lookup& aLookup) {
830
return BitwiseCast<uint32_t>(aKey) == BitwiseCast<uint32_t>(aLookup);
831
}
832
};
833
834
// A hash policy for C strings.
835
struct CStringHasher {
836
using Key = const char*;
837
using Lookup = const char*;
838
839
static HashNumber hash(const Lookup& aLookup) { return HashString(aLookup); }
840
841
static bool match(const Key& aKey, const Lookup& aLookup) {
842
return strcmp(aKey, aLookup) == 0;
843
}
844
};
845
846
//---------------------------------------------------------------------------
847
// Fallible Hashing Interface
848
//---------------------------------------------------------------------------
849
850
// Most of the time generating a hash code is infallible so this class provides
851
// default methods that always succeed. Specialize this class for your own hash
852
// policy to provide fallible hashing.
853
//
854
// This is used by MovableCellHasher to handle the fact that generating a unique
855
// ID for cell pointer may fail due to OOM.
856
template <typename HashPolicy>
857
struct FallibleHashMethods {
858
// Return true if a hashcode is already available for its argument. Once
859
// this returns true for a specific argument it must continue to do so.
860
template <typename Lookup>
861
static bool hasHash(Lookup&& aLookup) {
862
return true;
863
}
864
865
// Fallible method to ensure a hashcode exists for its argument and create
866
// one if not. Returns false on error, e.g. out of memory.
867
template <typename Lookup>
868
static bool ensureHash(Lookup&& aLookup) {
869
return true;
870
}
871
};
872
873
template <typename HashPolicy, typename Lookup>
874
static bool HasHash(Lookup&& aLookup) {
875
return FallibleHashMethods<typename HashPolicy::Base>::hasHash(
876
std::forward<Lookup>(aLookup));
877
}
878
879
template <typename HashPolicy, typename Lookup>
880
static bool EnsureHash(Lookup&& aLookup) {
881
return FallibleHashMethods<typename HashPolicy::Base>::ensureHash(
882
std::forward<Lookup>(aLookup));
883
}
884
885
//---------------------------------------------------------------------------
886
// Implementation Details (HashMapEntry, HashTableEntry, HashTable)
887
//---------------------------------------------------------------------------
888
889
// Both HashMap and HashSet are implemented by a single HashTable that is even
890
// more heavily parameterized than the other two. This leaves HashTable gnarly
891
// and extremely coupled to HashMap and HashSet; thus code should not use
892
// HashTable directly.
893
894
template <class Key, class Value>
895
class HashMapEntry {
896
Key key_;
897
Value value_;
898
899
template <class, class, class>
900
friend class detail::HashTable;
901
template <class>
902
friend class detail::HashTableEntry;
903
template <class, class, class, class>
904
friend class HashMap;
905
906
public:
907
template <typename KeyInput, typename ValueInput>
908
HashMapEntry(KeyInput&& aKey, ValueInput&& aValue)
909
: key_(std::forward<KeyInput>(aKey)),
910
value_(std::forward<ValueInput>(aValue)) {}
911
912
HashMapEntry(HashMapEntry&& aRhs)
913
: key_(std::move(aRhs.key_)), value_(std::move(aRhs.value_)) {}
914
915
void operator=(HashMapEntry&& aRhs) {
916
key_ = std::move(aRhs.key_);
917
value_ = std::move(aRhs.value_);
918
}
919
920
using KeyType = Key;
921
using ValueType = Value;
922
923
const Key& key() const { return key_; }
924
925
// Use this method with caution! If the key is changed such that its hash
926
// value also changes, the map will be left in an invalid state.
927
Key& mutableKey() { return key_; }
928
929
const Value& value() const { return value_; }
930
Value& value() { return value_; }
931
932
private:
933
HashMapEntry(const HashMapEntry&) = delete;
934
void operator=(const HashMapEntry&) = delete;
935
};
936
937
template <typename K, typename V>
938
struct IsPod<HashMapEntry<K, V>>
939
: IntegralConstant<bool, IsPod<K>::value && IsPod<V>::value> {};
940
941
namespace detail {
942
943
template <class T, class HashPolicy, class AllocPolicy>
944
class HashTable;
945
946
template <typename T>
947
class EntrySlot;
948
949
template <typename T>
950
class HashTableEntry {
951
private:
952
using NonConstT = typename RemoveConst<T>::Type;
953
954
// Instead of having a hash table entry store that looks like this:
955
//
956
// +--------+--------+--------+--------+
957
// | entry0 | entry1 | .... | entryN |
958
// +--------+--------+--------+--------+
959
//
960
// where the entries contained their cached hash code, we're going to lay out
961
// the entry store thusly:
962
//
963
// +-------+-------+-------+-------+--------+--------+--------+--------+
964
// | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
965
// +-------+-------+-------+-------+--------+--------+--------+--------+
966
//
967
// with all the cached hashes prior to the actual entries themselves.
968
//
969
// We do this because implementing the first strategy requires us to make
970
// HashTableEntry look roughly like:
971
//
972
// template <typename T>
973
// class HashTableEntry {
974
// HashNumber mKeyHash;
975
// T mValue;
976
// };
977
//
978
// The problem with this setup is that, depending on the layout of `T`, there
979
// may be platform ABI-mandated padding between `mKeyHash` and the first
980
// member of `T`. This ABI-mandated padding is wasted space, and can be
981
// surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
982
// In such cases, we're throwing away a quarter of our entry store on padding,
983
// which is undesirable.
984
//
985
// The second layout above, namely:
986
//
987
// +-------+-------+-------+-------+--------+--------+--------+--------+
988
// | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
989
// +-------+-------+-------+-------+--------+--------+--------+--------+
990
//
991
// means there is no wasted space between the hashes themselves, and no wasted
992
// space between the entries themselves. However, we would also like there to
993
// be no gap between the last hash and the first entry. The memory allocator
994
// guarantees the alignment of the start of the hashes. The use of a
995
// power-of-two capacity of at least 4 guarantees that the alignment of the
996
// *end* of the hash array is no less than the alignment of the start.
997
// Finally, the static_asserts here guarantee that the entries themselves
998
// don't need to be any more aligned than the alignment of the entry store
999
// itself.
1000
#ifdef HAVE_64BIT_BUILD
1001
static_assert(alignof(NonConstT) <= alignof(void*),
1002
"cannot use over-aligned entries in mozilla::HashTable");
1003
#else
1004
// This assertion is safe for 32-bit builds because on both Windows and Linux
1005
// (including Android), the minimum alignment for allocations larger than 8
1006
// bytes is 8 bytes, and the actual data for entries in our entry store is
1007
// guaranteed to have that alignment as well, thanks to the power-of-two
1008
// number of cached hash values stored prior to the entry data.
1009
static_assert(alignof(NonConstT) <= 2 * alignof(void*),
1010
"cannot use over-aligned entries in mozilla::HashTable");
1011
#endif
1012
1013
static const HashNumber sFreeKey = 0;
1014
static const HashNumber sRemovedKey = 1;
1015
static const HashNumber sCollisionBit = 1;
1016
1017
alignas(NonConstT) unsigned char mValueData[sizeof(NonConstT)];
1018
1019
private:
1020
template <class, class, class>
1021
friend class HashTable;
1022
template <typename>
1023
friend class EntrySlot;
1024
1025
// Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1026
// -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1027
// through |void*|. Placing the latter cast in these separate functions
1028
// breaks the chain such that affected GCC versions no longer warn/error.
1029
void* rawValuePtr() { return mValueData; }
1030
1031
static bool isLiveHash(HashNumber hash) { return hash > sRemovedKey; }
1032
1033
HashTableEntry(const HashTableEntry&) = delete;
1034
void operator=(const HashTableEntry&) = delete;
1035
1036
NonConstT* valuePtr() { return reinterpret_cast<NonConstT*>(rawValuePtr()); }
1037
1038
void destroyStoredT() {
1039
NonConstT* ptr = valuePtr();
1040
ptr->~T();
1041
MOZ_MAKE_MEM_UNDEFINED(ptr, sizeof(*ptr));
1042
}
1043
1044
public:
1045
HashTableEntry() = default;
1046
1047
~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this)); }
1048
1049
void destroy() { destroyStoredT(); }
1050
1051
void swap(HashTableEntry* aOther, bool aIsLive) {
1052
if (this == aOther) {
1053
return;
1054
}
1055
if (aIsLive) {
1056
Swap(*valuePtr(), *aOther->valuePtr());
1057
} else {
1058
*aOther->valuePtr() = std::move(*valuePtr());
1059
destroy();
1060
}
1061
}
1062
1063
T& get() { return *valuePtr(); }
1064
1065
NonConstT& getMutable() { return *valuePtr(); }
1066
};
1067
1068
// A slot represents a cached hash value and its associated entry stored
1069
// in the hash table. These two things are not stored in contiguous memory.
1070
template <class T>
1071
class EntrySlot {
1072
using NonConstT = typename RemoveConst<T>::Type;
1073
1074
using Entry = HashTableEntry<T>;
1075
1076
Entry* mEntry;
1077
HashNumber* mKeyHash;
1078
1079
template <class, class, class>
1080
friend class HashTable;
1081
1082
EntrySlot(Entry* aEntry, HashNumber* aKeyHash)
1083
: mEntry(aEntry), mKeyHash(aKeyHash) {}
1084
1085
public:
1086
static bool isLiveHash(HashNumber hash) { return hash > Entry::sRemovedKey; }
1087
1088
EntrySlot(const EntrySlot&) = default;
1089
EntrySlot(EntrySlot&& aOther) = default;
1090
1091
EntrySlot& operator=(const EntrySlot&) = default;
1092
EntrySlot& operator=(EntrySlot&&) = default;
1093
1094
bool operator==(const EntrySlot& aRhs) const { return mEntry == aRhs.mEntry; }
1095
1096
bool operator<(const EntrySlot& aRhs) const { return mEntry < aRhs.mEntry; }
1097
1098
EntrySlot& operator++() {
1099
++mEntry;
1100
++mKeyHash;
1101
return *this;
1102
}
1103
1104
void destroy() { mEntry->destroy(); }
1105
1106
void swap(EntrySlot& aOther) {
1107
mEntry->swap(aOther.mEntry, aOther.isLive());
1108
Swap(*mKeyHash, *aOther.mKeyHash);
1109
}
1110
1111
T& get() const { return mEntry->get(); }
1112
1113
NonConstT& getMutable() { return mEntry->getMutable(); }
1114
1115
bool isFree() const { return *mKeyHash == Entry::sFreeKey; }
1116
1117
void clearLive() {
1118
MOZ_ASSERT(isLive());
1119
*mKeyHash = Entry::sFreeKey;
1120
mEntry->destroyStoredT();
1121
}
1122
1123
void clear() {
1124
if (isLive()) {
1125
mEntry->destroyStoredT();
1126
}
1127
MOZ_MAKE_MEM_UNDEFINED(mEntry, sizeof(*mEntry));
1128
*mKeyHash = Entry::sFreeKey;
1129
}
1130
1131
bool isRemoved() const { return *mKeyHash == Entry::sRemovedKey; }
1132
1133
void removeLive() {
1134
MOZ_ASSERT(isLive());
1135
*mKeyHash = Entry::sRemovedKey;
1136
mEntry->destroyStoredT();
1137
}
1138
1139
bool isLive() const { return isLiveHash(*mKeyHash); }
1140
1141
void setCollision() {
1142
MOZ_ASSERT(isLive());
1143
*mKeyHash |= Entry::sCollisionBit;
1144
}
1145
void unsetCollision() { *mKeyHash &= ~Entry::sCollisionBit; }
1146
bool hasCollision() const { return *mKeyHash & Entry::sCollisionBit; }
1147
bool matchHash(HashNumber hn) {
1148
return (*mKeyHash & ~Entry::sCollisionBit) == hn;
1149
}
1150
HashNumber getKeyHash() const { return *mKeyHash & ~Entry::sCollisionBit; }
1151
1152
template <typename... Args>
1153
void setLive(HashNumber aHashNumber, Args&&... aArgs) {
1154
MOZ_ASSERT(!isLive());
1155
*mKeyHash = aHashNumber;
1156
new (KnownNotNull, mEntry->valuePtr()) T(std::forward<Args>(aArgs)...);
1157
MOZ_ASSERT(isLive());
1158
}
1159
1160
Entry* toEntry() const { return mEntry; }
1161
};
1162
1163
template <class T, class HashPolicy, class AllocPolicy>
1164
class HashTable : private AllocPolicy {
1165
friend class mozilla::ReentrancyGuard;
1166
1167
using NonConstT = typename RemoveConst<T>::Type;
1168
using Key = typename HashPolicy::KeyType;
1169
using Lookup = typename HashPolicy::Lookup;
1170
1171
public:
1172
using Entry = HashTableEntry<T>;
1173
using Slot = EntrySlot<T>;
1174
1175
template <typename F>
1176
static void forEachSlot(char* aTable, uint32_t aCapacity, F&& f) {
1177
auto hashes = reinterpret_cast<HashNumber*>(aTable);
1178
auto entries = reinterpret_cast<Entry*>(&hashes[aCapacity]);
1179
Slot slot(entries, hashes);
1180
for (size_t i = 0; i < size_t(aCapacity); ++i) {
1181
f(slot);
1182
++slot;
1183
}
1184
}
1185
1186
// A nullable pointer to a hash table element. A Ptr |p| can be tested
1187
// either explicitly |if (p.found()) p->...| or using boolean conversion
1188
// |if (p) p->...|. Ptr objects must not be used after any mutating hash
1189
// table operations unless |generation()| is tested.
1190
class Ptr {
1191
friend class HashTable;
1192
1193
Slot mSlot;
1194
#ifdef DEBUG
1195
const HashTable* mTable;
1196
Generation mGeneration;
1197
#endif
1198
1199
protected:
1200
Ptr(Slot aSlot, const HashTable& aTable)
1201
: mSlot(aSlot)
1202
#ifdef DEBUG
1203
,
1204
mTable(&aTable),
1205
mGeneration(aTable.generation())
1206
#endif
1207
{
1208
}
1209
1210
// This constructor is used only by AddPtr() within lookupForAdd().
1211
explicit Ptr(const HashTable& aTable)
1212
: mSlot(nullptr, nullptr)
1213
#ifdef DEBUG
1214
,
1215
mTable(&aTable),
1216
mGeneration(aTable.generation())
1217
#endif
1218
{
1219
}
1220
1221
bool isValid() const { return !!mSlot.toEntry(); }
1222
1223
public:
1224
Ptr()
1225
: mSlot(nullptr, nullptr)
1226
#ifdef DEBUG
1227
,
1228
mTable(nullptr),
1229
mGeneration(0)
1230
#endif
1231
{
1232
}
1233
1234
bool found() const {
1235
if (!isValid()) {
1236
return false;
1237
}
1238
#ifdef DEBUG
1239
MOZ_ASSERT(mGeneration == mTable->generation());
1240
#endif
1241
return mSlot.isLive();
1242
}
1243
1244
explicit operator bool() const { return found(); }
1245
1246
bool operator==(const Ptr& aRhs) const {
1247
MOZ_ASSERT(found() && aRhs.found());
1248
return mSlot == aRhs.mSlot;
1249
}
1250
1251
bool operator!=(const Ptr& aRhs) const {
1252
#ifdef DEBUG
1253
MOZ_ASSERT(mGeneration == mTable->generation());
1254
#endif
1255
return !(*this == aRhs);
1256
}
1257
1258
T& operator*() const {
1259
#ifdef DEBUG
1260
MOZ_ASSERT(found());
1261
MOZ_ASSERT(mGeneration == mTable->generation());
1262
#endif
1263
return mSlot.get();
1264
}
1265
1266
T* operator->() const {
1267
#ifdef DEBUG
1268
MOZ_ASSERT(found());
1269
MOZ_ASSERT(mGeneration == mTable->generation());
1270
#endif
1271
return &mSlot.get();
1272
}
1273
};
1274
1275
// A Ptr that can be used to add a key after a failed lookup.
1276
class AddPtr : public Ptr {
1277
friend class HashTable;
1278
1279
HashNumber mKeyHash;
1280
#ifdef DEBUG
1281
uint64_t mMutationCount;
1282
#endif
1283
1284
AddPtr(Slot aSlot, const HashTable& aTable, HashNumber aHashNumber)
1285
: Ptr(aSlot, aTable),
1286
mKeyHash(aHashNumber)
1287
#ifdef DEBUG
1288
,
1289
mMutationCount(aTable.mMutationCount)
1290
#endif
1291
{
1292
}
1293
1294
// This constructor is used when lookupForAdd() is performed on a table
1295
// lacking entry storage; it leaves mSlot null but initializes everything
1296
// else.
1297
AddPtr(const HashTable& aTable, HashNumber aHashNumber)
1298
: Ptr(aTable),
1299
mKeyHash(aHashNumber)
1300
#ifdef DEBUG
1301
,
1302
mMutationCount(aTable.mMutationCount)
1303
#endif
1304
{
1305
MOZ_ASSERT(isLive());
1306
}
1307
1308
bool isLive() const { return isLiveHash(mKeyHash); }
1309
1310
public:
1311
AddPtr() : mKeyHash(0) {}
1312
};
1313
1314
// A hash table iterator that (mostly) doesn't allow table modifications.
1315
// As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1316
// hash table operation unless the |generation()| is tested.
1317
class Iterator {
1318
void moveToNextLiveEntry() {
1319
while (++mCur < mEnd && !mCur.isLive()) {
1320
continue;
1321
}
1322
}
1323
1324
protected:
1325
friend class HashTable;
1326
1327
explicit Iterator(const HashTable& aTable)
1328
: mCur(aTable.slotForIndex(0)),
1329
mEnd(aTable.slotForIndex(aTable.capacity()))
1330
#ifdef DEBUG
1331
,
1332
mTable(aTable),
1333
mMutationCount(aTable.mMutationCount),
1334
mGeneration(aTable.generation()),
1335
mValidEntry(true)
1336
#endif
1337
{
1338
if (!done() && !mCur.isLive()) {
1339
moveToNextLiveEntry();
1340
}
1341
}
1342
1343
Slot mCur;
1344
Slot mEnd;
1345
#ifdef DEBUG
1346
const HashTable& mTable;
1347
uint64_t mMutationCount;
1348
Generation mGeneration;
1349
bool mValidEntry;
1350
#endif
1351
1352
public:
1353
bool done() const {
1354
#ifdef DEBUG
1355
MOZ_ASSERT(mGeneration == mTable.generation());
1356
MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
1357
#endif
1358
return mCur == mEnd;
1359
}
1360
1361
T& get() const {
1362
MOZ_ASSERT(!done());
1363
#ifdef DEBUG
1364
MOZ_ASSERT(mValidEntry);
1365
MOZ_ASSERT(mGeneration == mTable.generation());
1366
MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
1367
#endif
1368
return mCur.get();
1369
}
1370
1371
void next() {
1372
MOZ_ASSERT(!done());
1373
#ifdef DEBUG
1374
MOZ_ASSERT(mGeneration == mTable.generation());
1375
MOZ_ASSERT(mMutationCount == mTable.mMutationCount);
1376
#endif
1377
moveToNextLiveEntry();
1378
#ifdef DEBUG
1379
mValidEntry = true;
1380
#endif
1381
}
1382
};
1383
1384
// A hash table iterator that permits modification, removal and rekeying.
1385
// Since rehashing when elements were removed during enumeration would be
1386
// bad, it is postponed until the ModIterator is destructed. Since the
1387
// ModIterator's destructor touches the hash table, the user must ensure
1388
// that the hash table is still alive when the destructor runs.
1389
class ModIterator : public Iterator {
1390
friend class HashTable;
1391
1392
HashTable& mTable;
1393
bool mRekeyed;
1394
bool mRemoved;
1395
1396
// ModIterator is movable but not copyable.
1397
ModIterator(const ModIterator&) = delete;
1398
void operator=(const ModIterator&) = delete;
1399
1400
protected:
1401
explicit ModIterator(HashTable& aTable)
1402
: Iterator(aTable), mTable(aTable), mRekeyed(false), mRemoved(false) {}
1403
1404
public:
1405
MOZ_IMPLICIT ModIterator(ModIterator&& aOther)
1406
: Iterator(aOther),
1407
mTable(aOther.mTable),
1408
mRekeyed(aOther.mRekeyed),
1409
mRemoved(aOther.mRemoved) {
1410
aOther.mRekeyed = false;
1411
aOther.mRemoved = false;
1412
}
1413
1414
// Removes the current element from the table, leaving |get()|
1415
// invalid until the next call to |next()|.
1416
void remove() {
1417
mTable.remove(this->mCur);
1418
mRemoved = true;
1419
#ifdef DEBUG
1420
this->mValidEntry = false;
1421
this->mMutationCount = mTable.mMutationCount;
1422
#endif
1423
}
1424
1425
NonConstT& getMutable() {
1426
MOZ_ASSERT(!this->done());
1427
#ifdef DEBUG
1428
MOZ_ASSERT(this->mValidEntry);
1429
MOZ_ASSERT(this->mGeneration == this->Iterator::mTable.generation());
1430
MOZ_ASSERT(this->mMutationCount == this->Iterator::mTable.mMutationCount);
1431
#endif
1432
return this->mCur.getMutable();
1433
}
1434
1435
// Removes the current element and re-inserts it into the table with
1436
// a new key at the new Lookup position. |get()| is invalid after
1437
// this operation until the next call to |next()|.
1438
void rekey(const Lookup& l, const Key& k) {
1439
MOZ_ASSERT(&k != &HashPolicy::getKey(this->mCur.get()));
1440
Ptr p(this->mCur, mTable);
1441
mTable.rekeyWithoutRehash(p, l, k);
1442
mRekeyed = true;
1443
#ifdef DEBUG
1444
this->mValidEntry = false;
1445
this->mMutationCount = mTable.mMutationCount;
1446
#endif
1447
}
1448
1449
void rekey(const Key& k) { rekey(k, k); }
1450
1451
// Potentially rehashes the table.
1452
~ModIterator() {
1453
if (mRekeyed) {
1454
mTable.mGen++;
1455
mTable.infallibleRehashIfOverloaded();
1456
}
1457
1458
if (mRemoved) {
1459
mTable.compact();
1460
}
1461
}
1462
};
1463
1464
// Range is similar to Iterator, but uses different terminology.
1465
class Range {
1466
friend class HashTable;
1467
1468
Iterator mIter;
1469
1470
protected:
1471
explicit Range(const HashTable& table) : mIter(table) {}
1472
1473
public:
1474
bool empty() const { return mIter.done(); }
1475
1476
T& front() const { return mIter.get(); }
1477
1478
void popFront() { return mIter.next(); }
1479
};
1480
1481
// Enum is similar to ModIterator, but uses different terminology.
1482
class Enum {
1483
ModIterator mIter;
1484
1485
// Enum is movable but not copyable.
1486
Enum(const Enum&) = delete;
1487
void operator=(const Enum&) = delete;
1488
1489
public:
1490
template <class Map>
1491
explicit Enum(Map& map) : mIter(map.mImpl) {}
1492
1493
MOZ_IMPLICIT Enum(Enum&& other) : mIter(std::move(other.mIter)) {}
1494
1495
bool empty() const { return mIter.done(); }
1496
1497
T& front() const { return mIter.get(); }
1498
1499
void popFront() { return mIter.next(); }
1500
1501
void removeFront() { mIter.remove(); }
1502
1503
NonConstT& mutableFront() { return mIter.getMutable(); }
1504
1505
void rekeyFront(const Lookup& aLookup, const Key& aKey) {
1506
mIter.rekey(aLookup, aKey);
1507
}
1508
1509
void rekeyFront(const Key& aKey) { mIter.rekey(aKey); }
1510
};
1511
1512
// HashTable is movable
1513
HashTable(HashTable&& aRhs) : AllocPolicy(std::move(aRhs)) { moveFrom(aRhs); }
1514
void operator=(HashTable&& aRhs) {
1515
MOZ_ASSERT(this != &aRhs, "self-move assignment is prohibited");
1516
if (mTable) {
1517
destroyTable(*this, mTable, capacity());
1518
}
1519
AllocPolicy::operator=(std::move(aRhs));
1520
moveFrom(aRhs);
1521
}
1522
1523
private:
1524
void moveFrom(HashTable& aRhs) {
1525
mGen = aRhs.mGen;
1526
mHashShift = aRhs.mHashShift;
1527
mTable = aRhs.mTable;
1528
mEntryCount = aRhs.mEntryCount;
1529
mRemovedCount = aRhs.mRemovedCount;
1530
#ifdef DEBUG
1531
mMutationCount = aRhs.mMutationCount;
1532
mEntered = aRhs.mEntered;
1533
#endif
1534
aRhs.mTable = nullptr;
1535
}
1536
1537
// HashTable is not copyable or assignable
1538
HashTable(const HashTable&) = delete;
1539
void operator=(const HashTable&) = delete;
1540
1541
static const uint32_t CAP_BITS = 30;
1542
1543
public:
1544
uint64_t mGen : 56; // entry storage generation number
1545
uint64_t mHashShift : 8; // multiplicative hash shift
1546
char* mTable; // entry storage
1547
uint32_t mEntryCount; // number of entries in mTable
1548
uint32_t mRemovedCount; // removed entry sentinels in mTable
1549
1550
#ifdef DEBUG
1551
uint64_t mMutationCount;
1552
mutable bool mEntered;
1553
#endif
1554
1555
// The default initial capacity is 32 (enough to hold 16 elements), but it
1556
// can be as low as 4.
1557
static const uint32_t sDefaultLen = 16;
1558
static const uint32_t sMinCapacity = 4;
1559
// See the comments in HashTableEntry about this value.
1560
static_assert(sMinCapacity >= 4, "too-small sMinCapacity breaks assumptions");
1561
static const uint32_t sMaxInit = 1u << (CAP_BITS - 1);
1562
static const uint32_t sMaxCapacity = 1u << CAP_BITS;
1563
1564
// Hash-table alpha is conceptually a fraction, but to avoid floating-point
1565
// math we implement it as a ratio of integers.
1566
static const uint8_t sAlphaDenominator = 4;
1567
static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
1568
static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
1569
1570
static const HashNumber sFreeKey = Entry::sFreeKey;
1571
static const HashNumber sRemovedKey = Entry::sRemovedKey;
1572
static const HashNumber sCollisionBit = Entry::sCollisionBit;
1573
1574
static uint32_t bestCapacity(uint32_t aLen) {
1575
static_assert(
1576
(sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,
1577
"multiplication in numerator below could overflow");
1578
static_assert(
1579
sMaxInit * sAlphaDenominator <= UINT32_MAX - sMaxAlphaNumerator,
1580
"numerator calculation below could potentially overflow");
1581
1582
// Callers should ensure this is true.
1583
MOZ_ASSERT(aLen <= sMaxInit);
1584
1585
// Compute the smallest capacity allowing |aLen| elements to be
1586
// inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1587
// integral division: <http://stackoverflow.com/a/2745086>.)
1588
uint32_t capacity = (aLen * sAlphaDenominator + sMaxAlphaNumerator - 1) /
1589
sMaxAlphaNumerator;
1590
capacity = (capacity < sMinCapacity) ? sMinCapacity : RoundUpPow2(capacity);
1591
1592
MOZ_ASSERT(capacity >= aLen);
1593
MOZ_ASSERT(capacity <= sMaxCapacity);
1594
1595
return capacity;
1596
}
1597
1598
static uint32_t hashShift(uint32_t aLen) {
1599
// Reject all lengths whose initial computed capacity would exceed
1600
// sMaxCapacity. Round that maximum aLen down to the nearest power of two
1601
// for speedier code.
1602
if (MOZ_UNLIKELY(aLen > sMaxInit)) {
1603
MOZ_CRASH("initial length is too large");
1604
}
1605
1606
return kHashNumberBits - mozilla::CeilingLog2(bestCapacity(aLen));
1607
}
1608
1609
static bool isLiveHash(HashNumber aHash) { return Entry::isLiveHash(aHash); }
1610
1611
static HashNumber prepareHash(const Lookup& aLookup) {
1612
HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(aLookup));
1613
1614
// Avoid reserved hash codes.
1615
if (!isLiveHash(keyHash)) {
1616
keyHash -= (sRemovedKey + 1);
1617
}
1618
return keyHash & ~sCollisionBit;
1619
}
1620
1621
enum FailureBehavior { DontReportFailure = false, ReportFailure = true };
1622
1623
// Fake a struct that we're going to alloc. See the comments in
1624
// HashTableEntry about how the table is laid out, and why it's safe.
1625
struct FakeSlot {
1626
unsigned char c[sizeof(HashNumber) + sizeof(typename Entry::NonConstT)];
1627
};
1628
1629
static char* createTable(AllocPolicy& aAllocPolicy, uint32_t aCapacity,
1630
FailureBehavior aReportFailure = ReportFailure) {
1631
FakeSlot* fake =
1632
aReportFailure
1633
? aAllocPolicy.template pod_malloc<FakeSlot>(aCapacity)
1634
: aAllocPolicy.template maybe_pod_malloc<FakeSlot>(aCapacity);
1635
char* table = reinterpret_cast<char*>(fake);
1636
if (table) {
1637
forEachSlot(table, aCapacity, [&](Slot& slot) {
1638
*slot.mKeyHash = sFreeKey;
1639
new (KnownNotNull, slot.toEntry()) Entry();
1640
});
1641
}
1642
return table;
1643
}
1644
1645
static void destroyTable(AllocPolicy& aAllocPolicy, char* aOldTable,
1646
uint32_t aCapacity) {
1647
forEachSlot(aOldTable, aCapacity, [&](const Slot& slot) {
1648
if (slot.isLive()) {
1649
slot.toEntry()->destroyStoredT();
1650
}
1651
});
1652
freeTable(aAllocPolicy, aOldTable, aCapacity);
1653
}
1654
1655
static void freeTable(AllocPolicy& aAllocPolicy, char* aOldTable,
1656
uint32_t aCapacity) {
1657
FakeSlot* fake = reinterpret_cast<FakeSlot*>(aOldTable);
1658
aAllocPolicy.free_(fake, aCapacity);
1659
}
1660
1661
public:
1662
HashTable(AllocPolicy aAllocPolicy, uint32_t aLen)
1663
: AllocPolicy(std::move(aAllocPolicy)),
1664
mGen(0),
1665
mHashShift(hashShift(aLen)),
1666
mTable(nullptr),
1667
mEntryCount(0),
1668
mRemovedCount(0)
1669
#ifdef DEBUG
1670
,
1671
mMutationCount(0),
1672
mEntered(false)
1673
#endif
1674
{
1675
}
1676
1677
explicit HashTable(AllocPolicy aAllocPolicy)
1678
: HashTable(aAllocPolicy, sDefaultLen) {}
1679
1680
~HashTable() {
1681
if (mTable) {
1682
destroyTable(*this, mTable, capacity());
1683
}
1684
}
1685
1686
private:
1687
HashNumber hash1(HashNumber aHash0) const { return aHash0 >> mHashShift; }
1688
1689
struct DoubleHash {
1690
HashNumber mHash2;
1691
HashNumber mSizeMask;
1692
};
1693
1694
DoubleHash hash2(HashNumber aCurKeyHash) const {
1695
uint32_t sizeLog2 = kHashNumberBits - mHashShift;
1696
DoubleHash dh = {((aCurKeyHash << sizeLog2) >> mHashShift) | 1,
1697
(HashNumber(1) << sizeLog2) - 1};
1698
return dh;
1699
}
1700
1701
static HashNumber applyDoubleHash(HashNumber aHash1,
1702
const DoubleHash& aDoubleHash) {
1703
return (aHash1 - aDoubleHash.mHash2) & aDoubleHash.mSizeMask;
1704
}
1705
1706
static MOZ_ALWAYS_INLINE bool match(T& aEntry, const Lookup& aLookup) {
1707
return HashPolicy::match(HashPolicy::getKey(aEntry), aLookup);
1708
}
1709
1710
enum LookupReason { ForNonAdd, ForAdd };
1711
1712
Slot slotForIndex(HashNumber aIndex) const {
1713
auto hashes = reinterpret_cast<HashNumber*>(mTable);
1714
auto entries = reinterpret_cast<Entry*>(&hashes[capacity()]);
1715
return Slot(&entries[aIndex], &hashes[aIndex]);
1716
}
1717
1718
// Warning: in order for readonlyThreadsafeLookup() to be safe this
1719
// function must not modify the table in any way when Reason==ForNonAdd.
1720
template <LookupReason Reason>
1721
MOZ_ALWAYS_INLINE Slot lookup(const Lookup& aLookup,
1722
HashNumber aKeyHash) const {
1723
MOZ_ASSERT(isLiveHash(aKeyHash));
1724
MOZ_ASSERT(!(aKeyHash & sCollisionBit));
1725
MOZ_ASSERT(mTable);
1726
1727
// Compute the primary hash address.
1728
HashNumber h1 = hash1(aKeyHash);
1729
Slot slot = slotForIndex(h1);
1730
1731
// Miss: return space for a new entry.
1732
if (slot.isFree()) {
1733
return slot;
1734
}
1735
1736
// Hit: return entry.
1737
if (slot.matchHash(aKeyHash) && match(slot.get(), aLookup)) {
1738
return slot;
1739
}
1740
1741
// Collision: double hash.
1742
DoubleHash dh = hash2(aKeyHash);
1743
1744
// Save the first removed entry pointer so we can recycle later.
1745
Maybe<Slot> firstRemoved;
1746
1747
while (true) {
1748
if (Reason == ForAdd && !firstRemoved) {
1749
if (MOZ_UNLIKELY(slot.isRemoved())) {
1750
firstRemoved.emplace(slot);
1751
} else {
1752
slot.setCollision();
1753
}
1754
}
1755
1756
h1 = applyDoubleHash(h1, dh);
1757
1758
slot = slotForIndex(h1);
1759
if (slot.isFree()) {
1760
return firstRemoved.refOr(slot);
1761
}
1762
1763
if (slot.matchHash(aKeyHash) && match(slot.get(), aLookup)) {
1764
return slot;
1765
}
1766
}
1767
}
1768
1769
// This is a copy of lookup() hardcoded to the assumptions:
1770
// 1. the lookup is for an add;
1771
// 2. the key, whose |keyHash| has been passed, is not in the table.
1772
Slot findNonLiveSlot(HashNumber aKeyHash) {
1773
MOZ_ASSERT(!(aKeyHash & sCollisionBit));
1774
MOZ_ASSERT(mTable);
1775
1776
// We assume 'aKeyHash' has already been distributed.
1777
1778
// Compute the primary hash address.
1779
HashNumber h1 = hash1(aKeyHash);
1780
Slot slot = slotForIndex(h1);
1781
1782
// Miss: return space for a new entry.
1783
if (!slot.isLive()) {
1784
return slot;
1785
}
1786
1787
// Collision: double hash.
1788
DoubleHash dh = hash2(aKeyHash);
1789
1790
while (true) {
1791
slot.setCollision();
1792
1793
h1 = applyDoubleHash(h1, dh);
1794
1795
slot = slotForIndex(h1);
1796
if (!slot.isLive()) {
1797
return slot;
1798
}
1799
}
1800
}
1801
1802
enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };
1803
1804
RebuildStatus changeTableSize(
1805
uint32_t newCapacity, FailureBehavior aReportFailure = ReportFailure) {
1806
MOZ_ASSERT(IsPowerOfTwo(newCapacity));
1807
MOZ_ASSERT(!!mTable == !!capacity());
1808
1809
// Look, but don't touch, until we succeed in getting new entry store.
1810
char* oldTable = mTable;
1811
uint32_t oldCapacity = capacity();
1812
uint32_t newLog2 = mozilla::CeilingLog2(newCapacity);
1813
1814
if (MOZ_UNLIKELY(newCapacity > sMaxCapacity)) {
1815
if (aReportFailure) {
1816
this->reportAllocOverflow();
1817
}
1818
return RehashFailed;
1819
}
1820
1821
char* newTable = createTable(*this, newCapacity, aReportFailure);
1822
if (!newTable) {
1823
return RehashFailed;
1824
}
1825
1826
// We can't fail from here on, so update table parameters.
1827
mHashShift = kHashNumberBits - newLog2;
1828
mRemovedCount = 0;
1829
mGen++;
1830
mTable = newTable;
1831
1832
// Copy only live entries, leaving removed ones behind.
1833
forEachSlot(oldTable, oldCapacity, [&](Slot& slot) {
1834
if (slot.isLive()) {
1835
HashNumber hn = slot.getKeyHash();
1836
findNonLiveSlot(hn).setLive(
1837
hn, std::move(const_cast<typename Entry::NonConstT&>(slot.get())));
1838
}
1839
1840
slot.clear();
1841
});
1842
1843
// All entries have been destroyed, no need to destroyTable.
1844
freeTable(*this, oldTable, oldCapacity);
1845
return Rehashed;
1846
}
1847
1848
RebuildStatus rehashIfOverloaded(
1849
FailureBehavior aReportFailure = ReportFailure) {
1850
static_assert(sMaxCapacity <= UINT32_MAX / sMaxAlphaNumerator,
1851
"multiplication below could overflow");
1852
1853
// Note: if capacity() is zero, this will always succeed, which is
1854
// what we want.
1855
bool overloaded = mEntryCount + mRemovedCount >=
1856
capacity() * sMaxAlphaNumerator / sAlphaDenominator;
1857
1858
if (!overloaded) {
1859
return NotOverloaded;
1860
}
1861
1862
// Succeed if a quarter or more of all entries are removed. Note that this
1863
// always succeeds if capacity() == 0 (i.e. entry storage has not been
1864
// allocated), which is what we want, because it means changeTableSize()
1865
// will allocate the requested capacity rather than doubling it.
1866
bool manyRemoved = mRemovedCount >= (capacity() >> 2);
1867
uint32_t newCapacity = manyRemoved ? rawCapacity() : rawCapacity() * 2;
1868
return changeTableSize(newCapacity, aReportFailure);
1869
}
1870
1871
void infallibleRehashIfOverloaded() {
1872
if (rehashIfOverloaded(DontReportFailure) == RehashFailed) {
1873
rehashTableInPlace();
1874
}
1875
}
1876
1877
void remove(Slot& aSlot) {
1878
MOZ_ASSERT(mTable);
1879
1880
if (aSlot.hasCollision()) {
1881
aSlot.removeLive();
1882
mRemovedCount++;
1883
} else {
1884
aSlot.clearLive();
1885
}
1886
mEntryCount--;
1887
#ifdef DEBUG
1888
mMutationCount++;
1889
#endif
1890
}
1891
1892
void shrinkIfUnderloaded() {
1893
static_assert(sMaxCapacity <= UINT32_MAX / sMinAlphaNumerator,
1894
"multiplication below could overflow");
1895
bool underloaded =
1896
capacity() > sMinCapacity &&
1897
mEntryCount <= capacity() * sMinAlphaNumerator / sAlphaDenominator;
1898
1899
if (underloaded) {
1900
(void)changeTableSize(capacity() / 2, DontReportFailure);
1901
}
1902
}
1903
1904
// This is identical to changeTableSize(currentSize), but without requiring
1905
// a second table. We do this by recycling the collision bits to tell us if
1906
// the element is already inserted or still waiting to be inserted. Since
1907
// already-inserted elements win any conflicts, we get the same table as we
1908
// would have gotten through random insertion order.
1909
void rehashTableInPlace() {
1910
mRemovedCount = 0;
1911
mGen++;
1912
forEachSlot(mTable, capacity(), [&](Slot& slot) { slot.unsetCollision(); });
1913
for (uint32_t i = 0; i < capacity();) {
1914
Slot src = slotForIndex(i);
1915
1916
if (!src.isLive() || src.hasCollision()) {
1917
++i;
1918
continue;
1919
}
1920
1921
HashNumber keyHash = src.getKeyHash();
1922
HashNumber h1 = hash1(keyHash);
1923
DoubleHash dh = hash2(keyHash);
1924
Slot tgt = slotForIndex(h1);
1925
while (true) {
1926
if (!tgt.hasCollisio