forked from mozilla/gecko-dev
-
Notifications
You must be signed in to change notification settings - Fork 1
/
HashTable.h
2278 lines (1902 loc) · 71.8 KB
/
HashTable.h
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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/. */
//---------------------------------------------------------------------------
// Overview
//---------------------------------------------------------------------------
//
// This file defines HashMap<Key, Value> and HashSet<T>, hash tables that are
// fast and have a nice API.
//
// Both hash tables have two optional template parameters.
//
// - HashPolicy. This defines the operations for hashing and matching keys. The
// default HashPolicy is appropriate when both of the following two
// conditions are true.
//
// - The key type stored in the table (|Key| for |HashMap<Key, Value>|, |T|
// for |HashSet<T>|) is an integer, pointer, UniquePtr, float, or double.
//
// - The type used for lookups (|Lookup|) is the same as the key type. This
// is usually the case, but not always.
//
// There is also a |CStringHasher| policy for |char*| keys. If your keys
// don't match any of the above cases, you must provide your own hash policy;
// see the "Hash Policy" section below.
//
// - AllocPolicy. This defines how allocations are done by the table.
//
// - |MallocAllocPolicy| is the default and is usually appropriate; note that
// operations (such as insertions) that might cause allocations are
// fallible and must be checked for OOM. These checks are enforced by the
// use of [[nodiscard]].
//
// - |InfallibleAllocPolicy| is another possibility; it allows the
// abovementioned OOM checks to be done with MOZ_ALWAYS_TRUE().
//
// Note that entry storage allocation is lazy, and not done until the first
// lookupForAdd(), put(), or putNew() is performed.
//
// See AllocPolicy.h for more details.
//
// Documentation on how to use HashMap and HashSet, including examples, is
// present within those classes. Search for "class HashMap" and "class
// HashSet".
//
// Both HashMap and HashSet are implemented on top of a third class, HashTable.
// You only need to look at HashTable if you want to understand the
// implementation.
//
// How does mozilla::HashTable (this file) compare with PLDHashTable (and its
// subclasses, such as nsTHashtable)?
//
// - mozilla::HashTable is a lot faster, largely because it uses templates
// throughout *and* inlines everything. PLDHashTable inlines operations much
// less aggressively, and also uses "virtual ops" for operations like hashing
// and matching entries that require function calls.
//
// - Correspondingly, mozilla::HashTable use is likely to increase executable
// size much more than PLDHashTable.
//
// - mozilla::HashTable has a nicer API, with a proper HashSet vs. HashMap
// distinction.
//
// - mozilla::HashTable requires more explicit OOM checking. As mentioned
// above, the use of |InfallibleAllocPolicy| can simplify things.
//
// - mozilla::HashTable has a default capacity on creation of 32 and a minimum
// capacity of 4. PLDHashTable has a default capacity on creation of 8 and a
// minimum capacity of 8.
#ifndef mozilla_HashTable_h
#define mozilla_HashTable_h
#include <utility>
#include <type_traits>
#include "mozilla/AllocPolicy.h"
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/Casting.h"
#include "mozilla/HashFunctions.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Maybe.h"
#include "mozilla/MemoryChecking.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Opaque.h"
#include "mozilla/OperatorNewExtensions.h"
#include "mozilla/ReentrancyGuard.h"
#include "mozilla/UniquePtr.h"
#include "mozilla/WrappingOperations.h"
namespace mozilla {
template <class, class = void>
struct DefaultHasher;
template <class, class>
class HashMapEntry;
namespace detail {
template <typename T>
class HashTableEntry;
template <class T, class HashPolicy, class AllocPolicy>
class HashTable;
} // namespace detail
// The "generation" of a hash table is an opaque value indicating the state of
// modification of the hash table through its lifetime. If the generation of
// a hash table compares equal at times T1 and T2, then lookups in the hash
// table, pointers to (or into) hash table entries, etc. at time T1 are valid
// at time T2. If the generation compares unequal, these computations are all
// invalid and must be performed again to be used.
//
// Generations are meaningfully comparable only with respect to a single hash
// table. It's always nonsensical to compare the generation of distinct hash
// tables H1 and H2.
using Generation = Opaque<uint64_t>;
//---------------------------------------------------------------------------
// HashMap
//---------------------------------------------------------------------------
// HashMap is a fast hash-based map from keys to values.
//
// Template parameter requirements:
// - Key/Value: movable, destructible, assignable.
// - HashPolicy: see the "Hash Policy" section below.
// - AllocPolicy: see AllocPolicy.h.
//
// Note:
// - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
// called by HashMap must not call back into the same HashMap object.
//
template <class Key, class Value, class HashPolicy = DefaultHasher<Key>,
class AllocPolicy = MallocAllocPolicy>
class HashMap {
// -- Implementation details -----------------------------------------------
// HashMap is not copyable or assignable.
HashMap(const HashMap& hm) = delete;
HashMap& operator=(const HashMap& hm) = delete;
using TableEntry = HashMapEntry<Key, Value>;
struct MapHashPolicy : HashPolicy {
using Base = HashPolicy;
using KeyType = Key;
static const Key& getKey(TableEntry& aEntry) { return aEntry.key(); }
static void setKey(TableEntry& aEntry, Key& aKey) {
HashPolicy::rekey(aEntry.mutableKey(), aKey);
}
};
using Impl = detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy>;
Impl mImpl;
friend class Impl::Enum;
public:
using Lookup = typename HashPolicy::Lookup;
using Entry = TableEntry;
// -- Initialization -------------------------------------------------------
explicit HashMap(AllocPolicy aAllocPolicy = AllocPolicy(),
uint32_t aLen = Impl::sDefaultLen)
: mImpl(std::move(aAllocPolicy), aLen) {}
explicit HashMap(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
// HashMap is movable.
HashMap(HashMap&& aRhs) = default;
HashMap& operator=(HashMap&& aRhs) = default;
// -- Status and sizing ----------------------------------------------------
// The map's current generation.
Generation generation() const { return mImpl.generation(); }
// Is the map empty?
bool empty() const { return mImpl.empty(); }
// Number of keys/values in the map.
uint32_t count() const { return mImpl.count(); }
// Number of key/value slots in the map. Note: resize will happen well before
// count() == capacity().
uint32_t capacity() const { return mImpl.capacity(); }
// The size of the map's entry storage, in bytes. If the keys/values contain
// pointers to other heap blocks, you must iterate over the map and measure
// them separately; hence the "shallow" prefix.
size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
}
size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
return aMallocSizeOf(this) +
mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
}
// Attempt to minimize the capacity(). If the table is empty, this will free
// the empty storage and upon regrowth it will be given the minimum capacity.
void compact() { mImpl.compact(); }
// Attempt to reserve enough space to fit at least |aLen| elements. This is
// total capacity, including elements already present. Does nothing if the
// map already has sufficient capacity.
[[nodiscard]] bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
// -- Lookups --------------------------------------------------------------
// Does the map contain a key/value matching |aLookup|?
bool has(const Lookup& aLookup) const {
return mImpl.lookup(aLookup).found();
}
// Return a Ptr indicating whether a key/value matching |aLookup| is
// present in the map. E.g.:
//
// using HM = HashMap<int,char>;
// HM h;
// if (HM::Ptr p = h.lookup(3)) {
// assert(p->key() == 3);
// char val = p->value();
// }
//
using Ptr = typename Impl::Ptr;
MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& aLookup) const {
return mImpl.lookup(aLookup);
}
// Like lookup(), but does not assert if two threads call it at the same
// time. Only use this method when none of the threads will modify the map.
MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
return mImpl.readonlyThreadsafeLookup(aLookup);
}
// -- Insertions -----------------------------------------------------------
// Overwrite existing value with |aValue|, or add it if not present. Returns
// false on OOM.
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool put(KeyInput&& aKey, ValueInput&& aValue) {
return put(aKey, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool put(const Lookup& aLookup, KeyInput&& aKey,
ValueInput&& aValue) {
AddPtr p = lookupForAdd(aLookup);
if (p) {
p->value() = std::forward<ValueInput>(aValue);
return true;
}
return add(p, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
// Like put(), but slightly faster. Must only be used when the given key is
// not already present. (In debug builds, assertions check this.)
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool putNew(KeyInput&& aKey, ValueInput&& aValue) {
return mImpl.putNew(aKey, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool putNew(const Lookup& aLookup, KeyInput&& aKey,
ValueInput&& aValue) {
return mImpl.putNew(aLookup, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
// Like putNew(), but should be only used when the table is known to be big
// enough for the insertion, and hashing cannot fail. Typically this is used
// to populate an empty map with known-unique keys after reserving space with
// reserve(), e.g.
//
// using HM = HashMap<int,char>;
// HM h;
// if (!h.reserve(3)) {
// MOZ_CRASH("OOM");
// }
// h.putNewInfallible(1, 'a'); // unique key
// h.putNewInfallible(2, 'b'); // unique key
// h.putNewInfallible(3, 'c'); // unique key
//
template <typename KeyInput, typename ValueInput>
void putNewInfallible(KeyInput&& aKey, ValueInput&& aValue) {
mImpl.putNewInfallible(aKey, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
// Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
// insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
// |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
//
// using HM = HashMap<int,char>;
// HM h;
// HM::AddPtr p = h.lookupForAdd(3);
// if (!p) {
// if (!h.add(p, 3, 'a')) {
// return false;
// }
// }
// assert(p->key() == 3);
// char val = p->value();
//
// N.B. The caller must ensure that no mutating hash table operations occur
// between a pair of lookupForAdd() and add() calls. To avoid looking up the
// key a second time, the caller may use the more efficient relookupOrAdd()
// method. This method reuses part of the hashing computation to more
// efficiently insert the key if it has not been added. For example, a
// mutation-handling version of the previous example:
//
// HM::AddPtr p = h.lookupForAdd(3);
// if (!p) {
// call_that_may_mutate_h();
// if (!h.relookupOrAdd(p, 3, 'a')) {
// return false;
// }
// }
// assert(p->key() == 3);
// char val = p->value();
//
using AddPtr = typename Impl::AddPtr;
MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& aLookup) {
return mImpl.lookupForAdd(aLookup);
}
// Add a key/value. Returns false on OOM.
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool add(AddPtr& aPtr, KeyInput&& aKey, ValueInput&& aValue) {
return mImpl.add(aPtr, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
// See the comment above lookupForAdd() for details.
template <typename KeyInput, typename ValueInput>
[[nodiscard]] bool relookupOrAdd(AddPtr& aPtr, KeyInput&& aKey,
ValueInput&& aValue) {
return mImpl.relookupOrAdd(aPtr, aKey, std::forward<KeyInput>(aKey),
std::forward<ValueInput>(aValue));
}
// -- Removal --------------------------------------------------------------
// Lookup and remove the key/value matching |aLookup|, if present.
void remove(const Lookup& aLookup) {
if (Ptr p = lookup(aLookup)) {
remove(p);
}
}
// Remove a previously found key/value (assuming aPtr.found()). The map must
// not have been mutated in the interim.
void remove(Ptr aPtr) { mImpl.remove(aPtr); }
// Remove all keys/values without changing the capacity.
void clear() { mImpl.clear(); }
// Like clear() followed by compact().
void clearAndCompact() { mImpl.clearAndCompact(); }
// -- Rekeying -------------------------------------------------------------
// Infallibly rekey one entry, if necessary. Requires that template
// parameters Key and HashPolicy::Lookup are the same type.
void rekeyIfMoved(const Key& aOldKey, const Key& aNewKey) {
if (aOldKey != aNewKey) {
rekeyAs(aOldKey, aNewKey, aNewKey);
}
}
// Infallibly rekey one entry if present, and return whether that happened.
bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
const Key& aNewKey) {
if (Ptr p = lookup(aOldLookup)) {
mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewKey);
return true;
}
return false;
}
// -- Iteration ------------------------------------------------------------
// |iter()| returns an Iterator:
//
// HashMap<int, char> h;
// for (auto iter = h.iter(); !iter.done(); iter.next()) {
// char c = iter.get().value();
// }
//
using Iterator = typename Impl::Iterator;
Iterator iter() const { return mImpl.iter(); }
// |modIter()| returns a ModIterator:
//
// HashMap<int, char> h;
// for (auto iter = h.modIter(); !iter.done(); iter.next()) {
// if (iter.get().value() == 'l') {
// iter.remove();
// }
// }
//
// Table resize may occur in ModIterator's destructor.
using ModIterator = typename Impl::ModIterator;
ModIterator modIter() { return mImpl.modIter(); }
// These are similar to Iterator/ModIterator/iter(), but use different
// terminology.
using Range = typename Impl::Range;
using Enum = typename Impl::Enum;
Range all() const { return mImpl.all(); }
};
//---------------------------------------------------------------------------
// HashSet
//---------------------------------------------------------------------------
// HashSet is a fast hash-based set of values.
//
// Template parameter requirements:
// - T: movable, destructible, assignable.
// - HashPolicy: see the "Hash Policy" section below.
// - AllocPolicy: see AllocPolicy.h
//
// Note:
// - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
// HashSet must not call back into the same HashSet object.
//
template <class T, class HashPolicy = DefaultHasher<T>,
class AllocPolicy = MallocAllocPolicy>
class HashSet {
// -- Implementation details -----------------------------------------------
// HashSet is not copyable or assignable.
HashSet(const HashSet& hs) = delete;
HashSet& operator=(const HashSet& hs) = delete;
struct SetHashPolicy : HashPolicy {
using Base = HashPolicy;
using KeyType = T;
static const KeyType& getKey(const T& aT) { return aT; }
static void setKey(T& aT, KeyType& aKey) { HashPolicy::rekey(aT, aKey); }
};
using Impl = detail::HashTable<const T, SetHashPolicy, AllocPolicy>;
Impl mImpl;
friend class Impl::Enum;
public:
using Lookup = typename HashPolicy::Lookup;
using Entry = T;
// -- Initialization -------------------------------------------------------
explicit HashSet(AllocPolicy aAllocPolicy = AllocPolicy(),
uint32_t aLen = Impl::sDefaultLen)
: mImpl(std::move(aAllocPolicy), aLen) {}
explicit HashSet(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
// HashSet is movable.
HashSet(HashSet&& aRhs) = default;
HashSet& operator=(HashSet&& aRhs) = default;
// -- Status and sizing ----------------------------------------------------
// The set's current generation.
Generation generation() const { return mImpl.generation(); }
// Is the set empty?
bool empty() const { return mImpl.empty(); }
// Number of elements in the set.
uint32_t count() const { return mImpl.count(); }
// Number of element slots in the set. Note: resize will happen well before
// count() == capacity().
uint32_t capacity() const { return mImpl.capacity(); }
// The size of the set's entry storage, in bytes. If the elements contain
// pointers to other heap blocks, you must iterate over the set and measure
// them separately; hence the "shallow" prefix.
size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
}
size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
return aMallocSizeOf(this) +
mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
}
// Attempt to minimize the capacity(). If the table is empty, this will free
// the empty storage and upon regrowth it will be given the minimum capacity.
void compact() { mImpl.compact(); }
// Attempt to reserve enough space to fit at least |aLen| elements. This is
// total capacity, including elements already present. Does nothing if the
// map already has sufficient capacity.
[[nodiscard]] bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
// -- Lookups --------------------------------------------------------------
// Does the set contain an element matching |aLookup|?
bool has(const Lookup& aLookup) const {
return mImpl.lookup(aLookup).found();
}
// Return a Ptr indicating whether an element matching |aLookup| is present
// in the set. E.g.:
//
// using HS = HashSet<int>;
// HS h;
// if (HS::Ptr p = h.lookup(3)) {
// assert(*p == 3); // p acts like a pointer to int
// }
//
using Ptr = typename Impl::Ptr;
MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& aLookup) const {
return mImpl.lookup(aLookup);
}
// Like lookup(), but does not assert if two threads call it at the same
// time. Only use this method when none of the threads will modify the set.
MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
return mImpl.readonlyThreadsafeLookup(aLookup);
}
// -- Insertions -----------------------------------------------------------
// Add |aU| if it is not present already. Returns false on OOM.
template <typename U>
[[nodiscard]] bool put(U&& aU) {
AddPtr p = lookupForAdd(aU);
return p ? true : add(p, std::forward<U>(aU));
}
// Like put(), but slightly faster. Must only be used when the given element
// is not already present. (In debug builds, assertions check this.)
template <typename U>
[[nodiscard]] bool putNew(U&& aU) {
return mImpl.putNew(aU, std::forward<U>(aU));
}
// Like the other putNew(), but for when |Lookup| is different to |T|.
template <typename U>
[[nodiscard]] bool putNew(const Lookup& aLookup, U&& aU) {
return mImpl.putNew(aLookup, std::forward<U>(aU));
}
// Like putNew(), but should be only used when the table is known to be big
// enough for the insertion, and hashing cannot fail. Typically this is used
// to populate an empty set with known-unique elements after reserving space
// with reserve(), e.g.
//
// using HS = HashMap<int>;
// HS h;
// if (!h.reserve(3)) {
// MOZ_CRASH("OOM");
// }
// h.putNewInfallible(1); // unique element
// h.putNewInfallible(2); // unique element
// h.putNewInfallible(3); // unique element
//
template <typename U>
void putNewInfallible(const Lookup& aLookup, U&& aU) {
mImpl.putNewInfallible(aLookup, std::forward<U>(aU));
}
// Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
// insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
// |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
//
// using HS = HashSet<int>;
// HS h;
// HS::AddPtr p = h.lookupForAdd(3);
// if (!p) {
// if (!h.add(p, 3)) {
// return false;
// }
// }
// assert(*p == 3); // p acts like a pointer to int
//
// N.B. The caller must ensure that no mutating hash table operations occur
// between a pair of lookupForAdd() and add() calls. To avoid looking up the
// key a second time, the caller may use the more efficient relookupOrAdd()
// method. This method reuses part of the hashing computation to more
// efficiently insert the key if it has not been added. For example, a
// mutation-handling version of the previous example:
//
// HS::AddPtr p = h.lookupForAdd(3);
// if (!p) {
// call_that_may_mutate_h();
// if (!h.relookupOrAdd(p, 3, 3)) {
// return false;
// }
// }
// assert(*p == 3);
//
// Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
// entry |t|, where the caller ensures match(l,t).
using AddPtr = typename Impl::AddPtr;
MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& aLookup) {
return mImpl.lookupForAdd(aLookup);
}
// Add an element. Returns false on OOM.
template <typename U>
[[nodiscard]] bool add(AddPtr& aPtr, U&& aU) {
return mImpl.add(aPtr, std::forward<U>(aU));
}
// See the comment above lookupForAdd() for details.
template <typename U>
[[nodiscard]] bool relookupOrAdd(AddPtr& aPtr, const Lookup& aLookup,
U&& aU) {
return mImpl.relookupOrAdd(aPtr, aLookup, std::forward<U>(aU));
}
// -- Removal --------------------------------------------------------------
// Lookup and remove the element matching |aLookup|, if present.
void remove(const Lookup& aLookup) {
if (Ptr p = lookup(aLookup)) {
remove(p);
}
}
// Remove a previously found element (assuming aPtr.found()). The set must
// not have been mutated in the interim.
void remove(Ptr aPtr) { mImpl.remove(aPtr); }
// Remove all keys/values without changing the capacity.
void clear() { mImpl.clear(); }
// Like clear() followed by compact().
void clearAndCompact() { mImpl.clearAndCompact(); }
// -- Rekeying -------------------------------------------------------------
// Infallibly rekey one entry, if present. Requires that template parameters
// T and HashPolicy::Lookup are the same type.
void rekeyIfMoved(const Lookup& aOldValue, const T& aNewValue) {
if (aOldValue != aNewValue) {
rekeyAs(aOldValue, aNewValue, aNewValue);
}
}
// Infallibly rekey one entry if present, and return whether that happened.
bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
const T& aNewValue) {
if (Ptr p = lookup(aOldLookup)) {
mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewValue);
return true;
}
return false;
}
// Infallibly replace the current key at |aPtr| with an equivalent key.
// Specifically, both HashPolicy::hash and HashPolicy::match must return
// identical results for the new and old key when applied against all
// possible matching values.
void replaceKey(Ptr aPtr, const Lookup& aLookup, const T& aNewValue) {
MOZ_ASSERT(aPtr.found());
MOZ_ASSERT(*aPtr != aNewValue);
MOZ_ASSERT(HashPolicy::match(*aPtr, aLookup));
MOZ_ASSERT(HashPolicy::match(aNewValue, aLookup));
const_cast<T&>(*aPtr) = aNewValue;
MOZ_ASSERT(*lookup(aLookup) == aNewValue);
}
void replaceKey(Ptr aPtr, const T& aNewValue) {
replaceKey(aPtr, aNewValue, aNewValue);
}
// -- Iteration ------------------------------------------------------------
// |iter()| returns an Iterator:
//
// HashSet<int> h;
// for (auto iter = h.iter(); !iter.done(); iter.next()) {
// int i = iter.get();
// }
//
using Iterator = typename Impl::Iterator;
Iterator iter() const { return mImpl.iter(); }
// |modIter()| returns a ModIterator:
//
// HashSet<int> h;
// for (auto iter = h.modIter(); !iter.done(); iter.next()) {
// if (iter.get() == 42) {
// iter.remove();
// }
// }
//
// Table resize may occur in ModIterator's destructor.
using ModIterator = typename Impl::ModIterator;
ModIterator modIter() { return mImpl.modIter(); }
// These are similar to Iterator/ModIterator/iter(), but use different
// terminology.
using Range = typename Impl::Range;
using Enum = typename Impl::Enum;
Range all() const { return mImpl.all(); }
};
//---------------------------------------------------------------------------
// Hash Policy
//---------------------------------------------------------------------------
// A hash policy |HP| for a hash table with key-type |Key| must provide:
//
// - a type |HP::Lookup| to use to lookup table entries;
//
// - a static member function |HP::hash| that hashes lookup values:
//
// static mozilla::HashNumber hash(const Lookup&);
//
// - a static member function |HP::match| that tests equality of key and
// lookup values:
//
// static bool match(const Key& aKey, const Lookup& aLookup);
//
// |aKey| and |aLookup| can have different hash numbers, only when a
// collision happens with |prepareHash| operation, which is less frequent.
// Thus, |HP::match| shouldn't assume the hash equality in the comparison,
// even if the hash numbers are almost always same between them.
//
// Normally, Lookup = Key. In general, though, different values and types of
// values can be used to lookup and store. If a Lookup value |l| is not equal
// to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
// true. E.g.:
//
// mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
// if (!p) {
// assert(HP::match(k, l)); // must hold
// h.add(p, k);
// }
// A pointer hashing policy that uses HashGeneric() to create good hashes for
// pointers. Note that we don't shift out the lowest k bits because we don't
// want to assume anything about the alignment of the pointers.
template <typename Key>
struct PointerHasher {
using Lookup = Key;
static HashNumber hash(const Lookup& aLookup) { return HashGeneric(aLookup); }
static bool match(const Key& aKey, const Lookup& aLookup) {
return aKey == aLookup;
}
static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
};
// The default hash policy, which only works with integers.
template <class Key, typename>
struct DefaultHasher {
using Lookup = Key;
static HashNumber hash(const Lookup& aLookup) {
// Just convert the integer to a HashNumber and use that as is. (This
// discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
// subsequently called on the value to improve the distribution.
return aLookup;
}
static bool match(const Key& aKey, const Lookup& aLookup) {
// Use builtin or overloaded operator==.
return aKey == aLookup;
}
static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
};
// A DefaultHasher specialization for enums.
template <class T>
struct DefaultHasher<T, std::enable_if_t<std::is_enum_v<T>>> {
using Key = T;
using Lookup = Key;
static HashNumber hash(const Lookup& aLookup) { return HashGeneric(aLookup); }
static bool match(const Key& aKey, const Lookup& aLookup) {
// Use builtin or overloaded operator==.
return aKey == static_cast<Key>(aLookup);
}
static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
};
// A DefaultHasher specialization for pointers.
template <class T>
struct DefaultHasher<T*> : PointerHasher<T*> {};
// A DefaultHasher specialization for mozilla::UniquePtr.
template <class T, class D>
struct DefaultHasher<UniquePtr<T, D>> {
using Key = UniquePtr<T, D>;
using Lookup = Key;
using PtrHasher = PointerHasher<T*>;
static HashNumber hash(const Lookup& aLookup) {
return PtrHasher::hash(aLookup.get());
}
static bool match(const Key& aKey, const Lookup& aLookup) {
return PtrHasher::match(aKey.get(), aLookup.get());
}
static void rekey(UniquePtr<T, D>& aKey, UniquePtr<T, D>&& aNewKey) {
aKey = std::move(aNewKey);
}
};
// A DefaultHasher specialization for doubles.
template <>
struct DefaultHasher<double> {
using Key = double;
using Lookup = Key;
static HashNumber hash(const Lookup& aLookup) {
// Just xor the high bits with the low bits, and then treat the bits of the
// result as a uint32_t.
static_assert(sizeof(HashNumber) == 4,
"subsequent code assumes a four-byte hash");
uint64_t u = BitwiseCast<uint64_t>(aLookup);
return HashNumber(u ^ (u >> 32));
}
static bool match(const Key& aKey, const Lookup& aLookup) {
return BitwiseCast<uint64_t>(aKey) == BitwiseCast<uint64_t>(aLookup);
}
};
// A DefaultHasher specialization for floats.
template <>
struct DefaultHasher<float> {
using Key = float;
using Lookup = Key;
static HashNumber hash(const Lookup& aLookup) {
// Just use the value as if its bits form an integer. ScrambleHashCode() is
// subsequently called on the value to improve the distribution.
static_assert(sizeof(HashNumber) == 4,
"subsequent code assumes a four-byte hash");
return HashNumber(BitwiseCast<uint32_t>(aLookup));
}
static bool match(const Key& aKey, const Lookup& aLookup) {
return BitwiseCast<uint32_t>(aKey) == BitwiseCast<uint32_t>(aLookup);
}
};
// A hash policy for C strings.
struct CStringHasher {
using Key = const char*;
using Lookup = const char*;
static HashNumber hash(const Lookup& aLookup) { return HashString(aLookup); }
static bool match(const Key& aKey, const Lookup& aLookup) {
return strcmp(aKey, aLookup) == 0;
}
};
//---------------------------------------------------------------------------
// Fallible Hashing Interface
//---------------------------------------------------------------------------
// Most of the time generating a hash code is infallible, but sometimes it is
// necessary to generate hash codes on demand in a way that can fail. Specialize
// this class for your own hash policy to provide fallible hashing.
//
// This is used by MovableCellHasher to handle the fact that generating a unique
// ID for cell pointer may fail due to OOM.
//
// The default implementations of these methods delegate to the usual HashPolicy
// implementation and always succeed.
template <typename HashPolicy>
struct FallibleHashMethods {
// Return true if a hashcode is already available for its argument, and
// sets |aHashOut|. Once this succeeds for a specific argument it
// must continue to do so.
//
// Return false if a hashcode is not already available. This implies that any
// lookup must fail, as the hash code would have to have been successfully
// created on insertion.
template <typename Lookup>
static bool maybeGetHash(Lookup&& aLookup, HashNumber* aHashOut) {
*aHashOut = HashPolicy::hash(aLookup);
return true;
}
// Fallible method to ensure a hashcode exists for its argument and create one
// if not. Sets |aHashOut| to the hashcode and retuns true on success. Returns
// false on error, e.g. out of memory.
template <typename Lookup>
static bool ensureHash(Lookup&& aLookup, HashNumber* aHashOut) {
*aHashOut = HashPolicy::hash(aLookup);
return true;
}
};
template <typename HashPolicy, typename Lookup>
static bool MaybeGetHash(Lookup&& aLookup, HashNumber* aHashOut) {
return FallibleHashMethods<typename HashPolicy::Base>::maybeGetHash(
std::forward<Lookup>(aLookup), aHashOut);
}
template <typename HashPolicy, typename Lookup>
static bool EnsureHash(Lookup&& aLookup, HashNumber* aHashOut) {
return FallibleHashMethods<typename HashPolicy::Base>::ensureHash(
std::forward<Lookup>(aLookup), aHashOut);
}
//---------------------------------------------------------------------------
// Implementation Details (HashMapEntry, HashTableEntry, HashTable)
//---------------------------------------------------------------------------
// Both HashMap and HashSet are implemented by a single HashTable that is even
// more heavily parameterized than the other two. This leaves HashTable gnarly
// and extremely coupled to HashMap and HashSet; thus code should not use
// HashTable directly.
template <class Key, class Value>
class HashMapEntry {
Key key_;
Value value_;
template <class, class, class>
friend class detail::HashTable;
template <class>
friend class detail::HashTableEntry;
template <class, class, class, class>
friend class HashMap;
public:
template <typename KeyInput, typename ValueInput>
HashMapEntry(KeyInput&& aKey, ValueInput&& aValue)
: key_(std::forward<KeyInput>(aKey)),
value_(std::forward<ValueInput>(aValue)) {}
HashMapEntry(HashMapEntry&& aRhs) = default;
HashMapEntry& operator=(HashMapEntry&& aRhs) = default;
using KeyType = Key;
using ValueType = Value;
const Key& key() const { return key_; }
// Use this method with caution! If the key is changed such that its hash
// value also changes, the map will be left in an invalid state.
Key& mutableKey() { return key_; }
const Value& value() const { return value_; }
Value& value() { return value_; }
private:
HashMapEntry(const HashMapEntry&) = delete;
void operator=(const HashMapEntry&) = delete;
};
namespace detail {
template <class T, class HashPolicy, class AllocPolicy>
class HashTable;
template <typename T>
class EntrySlot;
template <typename T>
class HashTableEntry {
private:
using NonConstT = std::remove_const_t<T>;
// Instead of having a hash table entry store that looks like this:
//
// +--------+--------+--------+--------+
// | entry0 | entry1 | .... | entryN |
// +--------+--------+--------+--------+
//
// where the entries contained their cached hash code, we're going to lay out
// the entry store thusly:
//
// +-------+-------+-------+-------+--------+--------+--------+--------+
// | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |