Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef js_HashTable_h
8 : #define js_HashTable_h
9 :
10 : #include "mozilla/Alignment.h"
11 : #include "mozilla/Assertions.h"
12 : #include "mozilla/Attributes.h"
13 : #include "mozilla/Casting.h"
14 : #include "mozilla/HashFunctions.h"
15 : #include "mozilla/MemoryReporting.h"
16 : #include "mozilla/Move.h"
17 : #include "mozilla/Opaque.h"
18 : #include "mozilla/PodOperations.h"
19 : #include "mozilla/ReentrancyGuard.h"
20 : #include "mozilla/TemplateLib.h"
21 : #include "mozilla/TypeTraits.h"
22 : #include "mozilla/UniquePtr.h"
23 :
24 : #include "js/Utility.h"
25 :
26 : namespace js {
27 :
28 : class TempAllocPolicy;
29 : template <class> struct DefaultHasher;
30 : template <class, class> class HashMapEntry;
31 : namespace detail {
32 : template <class T> class HashTableEntry;
33 : template <class T, class HashPolicy, class AllocPolicy> class HashTable;
34 : } // namespace detail
35 :
36 : /*****************************************************************************/
37 :
38 : // The "generation" of a hash table is an opaque value indicating the state of
39 : // modification of the hash table through its lifetime. If the generation of
40 : // a hash table compares equal at times T1 and T2, then lookups in the hash
41 : // table, pointers to (or into) hash table entries, etc. at time T1 are valid
42 : // at time T2. If the generation compares unequal, these computations are all
43 : // invalid and must be performed again to be used.
44 : //
45 : // Generations are meaningfully comparable only with respect to a single hash
46 : // table. It's always nonsensical to compare the generation of distinct hash
47 : // tables H1 and H2.
48 : using Generation = mozilla::Opaque<uint64_t>;
49 :
50 : // A JS-friendly, STL-like container providing a hash-based map from keys to
51 : // values. In particular, HashMap calls constructors and destructors of all
52 : // objects added so non-PODs may be used safely.
53 : //
54 : // Key/Value requirements:
55 : // - movable, destructible, assignable
56 : // HashPolicy requirements:
57 : // - see Hash Policy section below
58 : // AllocPolicy:
59 : // - see jsalloc.h
60 : //
61 : // Note:
62 : // - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
63 : // called by HashMap must not call back into the same HashMap object.
64 : // - Due to the lack of exception handling, the user must call |init()|.
65 : template <class Key,
66 : class Value,
67 : class HashPolicy = DefaultHasher<Key>,
68 : class AllocPolicy = TempAllocPolicy>
69 27071 : class HashMap
70 : {
71 : typedef HashMapEntry<Key, Value> TableEntry;
72 :
73 : struct MapHashPolicy : HashPolicy
74 : {
75 : using Base = HashPolicy;
76 : typedef Key KeyType;
77 2097144 : static const Key& getKey(TableEntry& e) { return e.key(); }
78 2496 : static void setKey(TableEntry& e, Key& k) { HashPolicy::rekey(e.mutableKey(), k); }
79 : };
80 :
81 : typedef detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy> Impl;
82 : Impl impl;
83 :
84 : public:
85 : typedef typename HashPolicy::Lookup Lookup;
86 : typedef TableEntry Entry;
87 :
88 : // HashMap construction is fallible (due to OOM); thus the user must call
89 : // init after constructing a HashMap and check the return value.
90 28287 : explicit HashMap(AllocPolicy a = AllocPolicy()) : impl(a) {}
91 5999 : MOZ_MUST_USE bool init(uint32_t len = 16) { return impl.init(len); }
92 17460 : bool initialized() const { return impl.initialized(); }
93 :
94 : // Return whether the given lookup value is present in the map. E.g.:
95 : //
96 : // typedef HashMap<int,char> HM;
97 : // HM h;
98 : // if (HM::Ptr p = h.lookup(3)) {
99 : // const HM::Entry& e = *p; // p acts like a pointer to Entry
100 : // assert(p->key == 3); // Entry contains the key
101 : // char val = p->value; // and value
102 : // }
103 : //
104 : // Also see the definition of Ptr in HashTable above (with T = Entry).
105 : typedef typename Impl::Ptr Ptr;
106 825320 : MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& l) const { return impl.lookup(l); }
107 :
108 : // Like lookup, but does not assert if two threads call lookup at the same
109 : // time. Only use this method when none of the threads will modify the map.
110 4650 : MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& l) const {
111 4650 : return impl.readonlyThreadsafeLookup(l);
112 : }
113 :
114 : // Assuming |p.found()|, remove |*p|.
115 4200 : void remove(Ptr p) { impl.remove(p); }
116 :
117 : // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
118 : // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
119 : // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new Entry. E.g.:
120 : //
121 : // typedef HashMap<int,char> HM;
122 : // HM h;
123 : // HM::AddPtr p = h.lookupForAdd(3);
124 : // if (!p) {
125 : // if (!h.add(p, 3, 'a'))
126 : // return false;
127 : // }
128 : // const HM::Entry& e = *p; // p acts like a pointer to Entry
129 : // assert(p->key == 3); // Entry contains the key
130 : // char val = p->value; // and value
131 : //
132 : // Also see the definition of AddPtr in HashTable above (with T = Entry).
133 : //
134 : // N.B. The caller must ensure that no mutating hash table operations
135 : // occur between a pair of |lookupForAdd| and |add| calls. To avoid
136 : // looking up the key a second time, the caller may use the more efficient
137 : // relookupOrAdd method. This method reuses part of the hashing computation
138 : // to more efficiently insert the key if it has not been added. For
139 : // example, a mutation-handling version of the previous example:
140 : //
141 : // HM::AddPtr p = h.lookupForAdd(3);
142 : // if (!p) {
143 : // call_that_may_mutate_h();
144 : // if (!h.relookupOrAdd(p, 3, 'a'))
145 : // return false;
146 : // }
147 : // const HM::Entry& e = *p;
148 : // assert(p->key == 3);
149 : // char val = p->value;
150 : typedef typename Impl::AddPtr AddPtr;
151 949551 : MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& l) const {
152 949551 : return impl.lookupForAdd(l);
153 : }
154 :
155 : template<typename KeyInput, typename ValueInput>
156 52457 : MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
157 : return impl.add(p,
158 : mozilla::Forward<KeyInput>(k),
159 52457 : mozilla::Forward<ValueInput>(v));
160 : }
161 :
162 : template<typename KeyInput>
163 : MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& k) {
164 : return impl.add(p, mozilla::Forward<KeyInput>(k), Value());
165 : }
166 :
167 : template<typename KeyInput, typename ValueInput>
168 1095 : MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
169 : return impl.relookupOrAdd(p, k,
170 : mozilla::Forward<KeyInput>(k),
171 1095 : mozilla::Forward<ValueInput>(v));
172 : }
173 :
174 : // |all()| returns a Range containing |count()| elements. E.g.:
175 : //
176 : // typedef HashMap<int,char> HM;
177 : // HM h;
178 : // for (HM::Range r = h.all(); !r.empty(); r.popFront())
179 : // char c = r.front().value();
180 : //
181 : // Also see the definition of Range in HashTable above (with T = Entry).
182 : typedef typename Impl::Range Range;
183 53696 : Range all() const { return impl.all(); }
184 :
185 : // Typedef for the enumeration class. An Enum may be used to examine and
186 : // remove table entries:
187 : //
188 : // typedef HashMap<int,char> HM;
189 : // HM s;
190 : // for (HM::Enum e(s); !e.empty(); e.popFront())
191 : // if (e.front().value() == 'l')
192 : // e.removeFront();
193 : //
194 : // Table resize may occur in Enum's destructor. Also see the definition of
195 : // Enum in HashTable above (with T = Entry).
196 : typedef typename Impl::Enum Enum;
197 :
198 : // Remove all entries. This does not shrink the table. For that consider
199 : // using the finish() method.
200 590 : void clear() { impl.clear(); }
201 :
202 : // Remove all entries. Unlike clear() this method tries to shrink the table.
203 : // Unlike finish() it does not require the map to be initialized again.
204 : void clearAndShrink() { impl.clearAndShrink(); }
205 :
206 : // Remove all the entries and release all internal buffers. The map must
207 : // be initialized again before any use.
208 117 : void finish() { impl.finish(); }
209 :
210 : // Does the table contain any entries?
211 13711 : bool empty() const { return impl.empty(); }
212 :
213 : // Number of live elements in the map.
214 30779 : uint32_t count() const { return impl.count(); }
215 :
216 : // Total number of allocation in the dynamic table. Note: resize will
217 : // happen well before count() == capacity().
218 : size_t capacity() const { return impl.capacity(); }
219 :
220 : // Don't just call |impl.sizeOfExcludingThis()| because there's no
221 : // guarantee that |impl| is the first field in HashMap.
222 0 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
223 0 : return impl.sizeOfExcludingThis(mallocSizeOf);
224 : }
225 0 : size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
226 0 : return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
227 : }
228 :
229 0 : Generation generation() const {
230 0 : return impl.generation();
231 : }
232 :
233 : /************************************************** Shorthand operations */
234 :
235 440976 : bool has(const Lookup& l) const {
236 440976 : return impl.lookup(l).found();
237 : }
238 :
239 : // Overwrite existing value with v. Return false on oom.
240 : template<typename KeyInput, typename ValueInput>
241 3159 : MOZ_MUST_USE bool put(KeyInput&& k, ValueInput&& v) {
242 3159 : AddPtr p = lookupForAdd(k);
243 3159 : if (p) {
244 5 : p->value() = mozilla::Forward<ValueInput>(v);
245 5 : return true;
246 : }
247 3154 : return add(p, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
248 : }
249 :
250 : // Like put, but assert that the given key is not already present.
251 : template<typename KeyInput, typename ValueInput>
252 15896 : MOZ_MUST_USE bool putNew(KeyInput&& k, ValueInput&& v) {
253 15896 : return impl.putNew(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
254 : }
255 :
256 : // Only call this to populate an empty map after reserving space with init().
257 : template<typename KeyInput, typename ValueInput>
258 2217 : void putNewInfallible(KeyInput&& k, ValueInput&& v) {
259 2217 : impl.putNewInfallible(k, mozilla::Forward<KeyInput>(k), mozilla::Forward<ValueInput>(v));
260 2217 : }
261 :
262 : // Add (k,defaultValue) if |k| is not found. Return a false-y Ptr on oom.
263 0 : Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
264 0 : AddPtr p = lookupForAdd(k);
265 0 : if (p)
266 0 : return p;
267 0 : bool ok = add(p, k, defaultValue);
268 0 : MOZ_ASSERT_IF(!ok, !p); // p is left false-y on oom.
269 : (void)ok;
270 0 : return p;
271 : }
272 :
273 : // Remove if present.
274 4476 : void remove(const Lookup& l) {
275 4476 : if (Ptr p = lookup(l))
276 4177 : remove(p);
277 4476 : }
278 :
279 : // Infallibly rekey one entry, if necessary.
280 : // Requires template parameters Key and HashPolicy::Lookup to be the same type.
281 24782 : void rekeyIfMoved(const Key& old_key, const Key& new_key) {
282 24782 : if (old_key != new_key)
283 24782 : rekeyAs(old_key, new_key, new_key);
284 24782 : }
285 :
286 : // Infallibly rekey one entry if present, and return whether that happened.
287 24782 : bool rekeyAs(const Lookup& old_lookup, const Lookup& new_lookup, const Key& new_key) {
288 24782 : if (Ptr p = lookup(old_lookup)) {
289 2496 : impl.rekeyAndMaybeRehash(p, new_lookup, new_key);
290 2496 : return true;
291 : }
292 22286 : return false;
293 : }
294 :
295 : // HashMap is movable
296 3117 : HashMap(HashMap&& rhs) : impl(mozilla::Move(rhs.impl)) {}
297 0 : void operator=(HashMap&& rhs) {
298 0 : MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
299 0 : impl = mozilla::Move(rhs.impl);
300 0 : }
301 :
302 : private:
303 : // HashMap is not copyable or assignable
304 : HashMap(const HashMap& hm) = delete;
305 : HashMap& operator=(const HashMap& hm) = delete;
306 :
307 : friend class Impl::Enum;
308 : };
309 :
310 : /*****************************************************************************/
311 :
312 : // A JS-friendly, STL-like container providing a hash-based set of values. In
313 : // particular, HashSet calls constructors and destructors of all objects added
314 : // so non-PODs may be used safely.
315 : //
316 : // T requirements:
317 : // - movable, destructible, assignable
318 : // HashPolicy requirements:
319 : // - see Hash Policy section below
320 : // AllocPolicy:
321 : // - see jsalloc.h
322 : //
323 : // Note:
324 : // - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
325 : // HashSet must not call back into the same HashSet object.
326 : // - Due to the lack of exception handling, the user must call |init()|.
327 : template <class T,
328 : class HashPolicy = DefaultHasher<T>,
329 : class AllocPolicy = TempAllocPolicy>
330 234 : class HashSet
331 : {
332 : struct SetOps : HashPolicy
333 : {
334 : using Base = HashPolicy;
335 : typedef T KeyType;
336 1160245 : static const KeyType& getKey(const T& t) { return t; }
337 471 : static void setKey(T& t, KeyType& k) { HashPolicy::rekey(t, k); }
338 : };
339 :
340 : typedef detail::HashTable<const T, SetOps, AllocPolicy> Impl;
341 : Impl impl;
342 :
343 : public:
344 : typedef typename HashPolicy::Lookup Lookup;
345 : typedef T Entry;
346 :
347 : // HashSet construction is fallible (due to OOM); thus the user must call
348 : // init after constructing a HashSet and check the return value.
349 3764 : explicit HashSet(AllocPolicy a = AllocPolicy()) : impl(a) {}
350 3728 : MOZ_MUST_USE bool init(uint32_t len = 16) { return impl.init(len); }
351 180080 : bool initialized() const { return impl.initialized(); }
352 :
353 : // Return whether the given lookup value is present in the map. E.g.:
354 : //
355 : // typedef HashSet<int> HS;
356 : // HS h;
357 : // if (HS::Ptr p = h.lookup(3)) {
358 : // assert(*p == 3); // p acts like a pointer to int
359 : // }
360 : //
361 : // Also see the definition of Ptr in HashTable above.
362 : typedef typename Impl::Ptr Ptr;
363 512146 : MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& l) const { return impl.lookup(l); }
364 :
365 : // Like lookup, but does not assert if two threads call lookup at the same
366 : // time. Only use this method when none of the threads will modify the map.
367 124762 : MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& l) const {
368 124762 : return impl.readonlyThreadsafeLookup(l);
369 : }
370 :
371 : // Assuming |p.found()|, remove |*p|.
372 874 : void remove(Ptr p) { impl.remove(p); }
373 :
374 : // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
375 : // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
376 : // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
377 : //
378 : // typedef HashSet<int> HS;
379 : // HS h;
380 : // HS::AddPtr p = h.lookupForAdd(3);
381 : // if (!p) {
382 : // if (!h.add(p, 3))
383 : // return false;
384 : // }
385 : // assert(*p == 3); // p acts like a pointer to int
386 : //
387 : // Also see the definition of AddPtr in HashTable above.
388 : //
389 : // N.B. The caller must ensure that no mutating hash table operations
390 : // occur between a pair of |lookupForAdd| and |add| calls. To avoid
391 : // looking up the key a second time, the caller may use the more efficient
392 : // relookupOrAdd method. This method reuses part of the hashing computation
393 : // to more efficiently insert the key if it has not been added. For
394 : // example, a mutation-handling version of the previous example:
395 : //
396 : // HS::AddPtr p = h.lookupForAdd(3);
397 : // if (!p) {
398 : // call_that_may_mutate_h();
399 : // if (!h.relookupOrAdd(p, 3, 3))
400 : // return false;
401 : // }
402 : // assert(*p == 3);
403 : //
404 : // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
405 : // entry |t|, where the caller ensures match(l,t).
406 : typedef typename Impl::AddPtr AddPtr;
407 838249 : MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& l) const {
408 838249 : return impl.lookupForAdd(l);
409 : }
410 :
411 : template <typename U>
412 194584 : MOZ_MUST_USE bool add(AddPtr& p, U&& u) {
413 194584 : return impl.add(p, mozilla::Forward<U>(u));
414 : }
415 :
416 : template <typename U>
417 15318 : MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, const Lookup& l, U&& u) {
418 15318 : return impl.relookupOrAdd(p, l, mozilla::Forward<U>(u));
419 : }
420 :
421 : // |all()| returns a Range containing |count()| elements:
422 : //
423 : // typedef HashSet<int> HS;
424 : // HS h;
425 : // for (HS::Range r = h.all(); !r.empty(); r.popFront())
426 : // int i = r.front();
427 : //
428 : // Also see the definition of Range in HashTable above.
429 : typedef typename Impl::Range Range;
430 99 : Range all() const { return impl.all(); }
431 :
432 : // Typedef for the enumeration class. An Enum may be used to examine and
433 : // remove table entries:
434 : //
435 : // typedef HashSet<int> HS;
436 : // HS s;
437 : // for (HS::Enum e(s); !e.empty(); e.popFront())
438 : // if (e.front() == 42)
439 : // e.removeFront();
440 : //
441 : // Table resize may occur in Enum's destructor. Also see the definition of
442 : // Enum in HashTable above.
443 : typedef typename Impl::Enum Enum;
444 :
445 : // Remove all entries. This does not shrink the table. For that consider
446 : // using the finish() method.
447 209 : void clear() { impl.clear(); }
448 :
449 : // Remove all entries. Unlike clear() this method tries to shrink the table.
450 : // Unlike finish() it does not require the set to be initialized again.
451 16 : void clearAndShrink() { impl.clearAndShrink(); }
452 :
453 : // Remove all the entries and release all internal buffers. The set must
454 : // be initialized again before any use.
455 4 : void finish() { impl.finish(); }
456 :
457 : // Does the table contain any entries?
458 192 : bool empty() const { return impl.empty(); }
459 :
460 : // Number of live elements in the map.
461 21296 : uint32_t count() const { return impl.count(); }
462 :
463 : // Total number of allocation in the dynamic table. Note: resize will
464 : // happen well before count() == capacity().
465 : size_t capacity() const { return impl.capacity(); }
466 :
467 : // Don't just call |impl.sizeOfExcludingThis()| because there's no
468 : // guarantee that |impl| is the first field in HashSet.
469 0 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
470 0 : return impl.sizeOfExcludingThis(mallocSizeOf);
471 : }
472 0 : size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
473 0 : return mallocSizeOf(this) + impl.sizeOfExcludingThis(mallocSizeOf);
474 : }
475 :
476 : Generation generation() const {
477 : return impl.generation();
478 : }
479 :
480 : /************************************************** Shorthand operations */
481 :
482 4869 : bool has(const Lookup& l) const {
483 4869 : return impl.lookup(l).found();
484 : }
485 :
486 : // Add |u| if it is not present already. Return false on oom.
487 : template <typename U>
488 11802 : MOZ_MUST_USE bool put(U&& u) {
489 11802 : AddPtr p = lookupForAdd(u);
490 11802 : return p ? true : add(p, mozilla::Forward<U>(u));
491 : }
492 :
493 : // Like put, but assert that the given key is not already present.
494 : template <typename U>
495 10 : MOZ_MUST_USE bool putNew(U&& u) {
496 10 : return impl.putNew(u, mozilla::Forward<U>(u));
497 : }
498 :
499 : template <typename U>
500 8341 : MOZ_MUST_USE bool putNew(const Lookup& l, U&& u) {
501 8341 : return impl.putNew(l, mozilla::Forward<U>(u));
502 : }
503 :
504 : // Only call this to populate an empty set after reserving space with init().
505 : template <typename U>
506 4190 : void putNewInfallible(const Lookup& l, U&& u) {
507 4190 : impl.putNewInfallible(l, mozilla::Forward<U>(u));
508 4190 : }
509 :
510 1152 : void remove(const Lookup& l) {
511 1152 : if (Ptr p = lookup(l))
512 827 : remove(p);
513 1152 : }
514 :
515 : // Infallibly rekey one entry, if present.
516 : // Requires template parameters T and HashPolicy::Lookup to be the same type.
517 : void rekeyIfMoved(const Lookup& old_value, const T& new_value) {
518 : if (old_value != new_value)
519 : rekeyAs(old_value, new_value, new_value);
520 : }
521 :
522 : // Infallibly rekey one entry if present, and return whether that happened.
523 471 : bool rekeyAs(const Lookup& old_lookup, const Lookup& new_lookup, const T& new_value) {
524 471 : if (Ptr p = lookup(old_lookup)) {
525 471 : impl.rekeyAndMaybeRehash(p, new_lookup, new_value);
526 471 : return true;
527 : }
528 0 : return false;
529 : }
530 :
531 : // Infallibly replace the current key at |p| with an equivalent key.
532 : // Specifically, both HashPolicy::hash and HashPolicy::match must return
533 : // identical results for the new and old key when applied against all
534 : // possible matching values.
535 146 : void replaceKey(Ptr p, const T& new_value) {
536 146 : MOZ_ASSERT(p.found());
537 146 : MOZ_ASSERT(*p != new_value);
538 146 : MOZ_ASSERT(HashPolicy::hash(*p) == HashPolicy::hash(new_value));
539 146 : MOZ_ASSERT(HashPolicy::match(*p, new_value));
540 146 : const_cast<T&>(*p) = new_value;
541 146 : }
542 :
543 : // HashSet is movable
544 78 : HashSet(HashSet&& rhs) : impl(mozilla::Move(rhs.impl)) {}
545 8 : void operator=(HashSet&& rhs) {
546 8 : MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
547 8 : impl = mozilla::Move(rhs.impl);
548 8 : }
549 :
550 : private:
551 : // HashSet is not copyable or assignable
552 : HashSet(const HashSet& hs) = delete;
553 : HashSet& operator=(const HashSet& hs) = delete;
554 :
555 : friend class Impl::Enum;
556 : };
557 :
558 : /*****************************************************************************/
559 :
560 : // Hash Policy
561 : //
562 : // A hash policy P for a hash table with key-type Key must provide:
563 : // - a type |P::Lookup| to use to lookup table entries;
564 : // - a static member function |P::hash| with signature
565 : //
566 : // static js::HashNumber hash(Lookup)
567 : //
568 : // to use to hash the lookup type; and
569 : // - a static member function |P::match| with signature
570 : //
571 : // static bool match(Key, Lookup)
572 : //
573 : // to use to test equality of key and lookup values.
574 : //
575 : // Normally, Lookup = Key. In general, though, different values and types of
576 : // values can be used to lookup and store. If a Lookup value |l| is != to the
577 : // added Key value |k|, the user must ensure that |P::match(k,l)|. E.g.:
578 : //
579 : // js::HashSet<Key, P>::AddPtr p = h.lookup(l);
580 : // if (!p) {
581 : // assert(P::match(k, l)); // must hold
582 : // h.add(p, k);
583 : // }
584 :
585 : // Pointer hashing policy that strips the lowest zeroBits when calculating the
586 : // hash to improve key distribution.
587 : template <typename Key, size_t zeroBits>
588 : struct PointerHasher
589 : {
590 : typedef Key Lookup;
591 1641695 : static HashNumber hash(const Lookup& l) {
592 1641695 : size_t word = reinterpret_cast<size_t>(l) >> zeroBits;
593 : static_assert(sizeof(HashNumber) == 4,
594 : "subsequent code assumes a four-byte hash");
595 : #if JS_BITS_PER_WORD == 32
596 : return HashNumber(word);
597 : #else
598 : static_assert(sizeof(word) == 8,
599 : "unexpected word size, new hashing strategy required to "
600 : "properly incorporate all bits");
601 1641695 : return HashNumber((word >> 32) ^ word);
602 : #endif
603 : }
604 2533579 : static bool match(const Key& k, const Lookup& l) {
605 2533579 : return k == l;
606 : }
607 866 : static void rekey(Key& k, const Key& newKey) {
608 866 : k = newKey;
609 866 : }
610 : };
611 :
612 : // Default hash policy: just use the 'lookup' value. This of course only
613 : // works if the lookup value is integral. HashTable applies ScrambleHashCode to
614 : // the result of the 'hash' which means that it is 'ok' if the lookup value is
615 : // not well distributed over the HashNumber domain.
616 : template <class Key>
617 19849 : struct DefaultHasher
618 : {
619 : typedef Key Lookup;
620 624994 : static HashNumber hash(const Lookup& l) {
621 : // Hash if can implicitly cast to hash number type.
622 624994 : return l;
623 : }
624 617775 : static bool match(const Key& k, const Lookup& l) {
625 : // Use builtin or overloaded operator==.
626 617775 : return k == l;
627 : }
628 2101 : static void rekey(Key& k, const Key& newKey) {
629 2101 : k = newKey;
630 2101 : }
631 : };
632 :
633 : // Specialize hashing policy for pointer types. It assumes that the type is
634 : // at least word-aligned. For types with smaller size use PointerHasher.
635 : template <class T>
636 : struct DefaultHasher<T*> : PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>
637 : {};
638 :
639 : // Specialize hashing policy for mozilla::UniquePtr to proxy the UniquePtr's
640 : // raw pointer to PointerHasher.
641 : template <class T, class D>
642 : struct DefaultHasher<mozilla::UniquePtr<T, D>>
643 : {
644 : using Lookup = mozilla::UniquePtr<T, D>;
645 : using PtrHasher = PointerHasher<T*, mozilla::tl::FloorLog2<sizeof(void*)>::value>;
646 :
647 : static HashNumber hash(const Lookup& l) {
648 : return PtrHasher::hash(l.get());
649 : }
650 : static bool match(const mozilla::UniquePtr<T, D>& k, const Lookup& l) {
651 : return PtrHasher::match(k.get(), l.get());
652 : }
653 : static void rekey(mozilla::UniquePtr<T, D>& k, mozilla::UniquePtr<T, D>&& newKey) {
654 : k = mozilla::Move(newKey);
655 : }
656 : };
657 :
658 : // For doubles, we can xor the two uint32s.
659 : template <>
660 : struct DefaultHasher<double>
661 : {
662 : typedef double Lookup;
663 0 : static HashNumber hash(double d) {
664 : static_assert(sizeof(HashNumber) == 4,
665 : "subsequent code assumes a four-byte hash");
666 0 : uint64_t u = mozilla::BitwiseCast<uint64_t>(d);
667 0 : return HashNumber(u ^ (u >> 32));
668 : }
669 0 : static bool match(double lhs, double rhs) {
670 0 : return mozilla::BitwiseCast<uint64_t>(lhs) == mozilla::BitwiseCast<uint64_t>(rhs);
671 : }
672 : };
673 :
674 : template <>
675 : struct DefaultHasher<float>
676 : {
677 : typedef float Lookup;
678 0 : static HashNumber hash(float f) {
679 : static_assert(sizeof(HashNumber) == 4,
680 : "subsequent code assumes a four-byte hash");
681 0 : return HashNumber(mozilla::BitwiseCast<uint32_t>(f));
682 : }
683 0 : static bool match(float lhs, float rhs) {
684 0 : return mozilla::BitwiseCast<uint32_t>(lhs) == mozilla::BitwiseCast<uint32_t>(rhs);
685 : }
686 : };
687 :
688 : // A hash policy that compares C strings.
689 : struct CStringHasher
690 : {
691 : typedef const char* Lookup;
692 0 : static js::HashNumber hash(Lookup l) {
693 0 : return mozilla::HashString(l);
694 : }
695 0 : static bool match(const char* key, Lookup lookup) {
696 0 : return strcmp(key, lookup) == 0;
697 : }
698 : };
699 :
700 : // Fallible hashing interface.
701 : //
702 : // Most of the time generating a hash code is infallible so this class provides
703 : // default methods that always succeed. Specialize this class for your own hash
704 : // policy to provide fallible hashing.
705 : //
706 : // This is used by MovableCellHasher to handle the fact that generating a unique
707 : // ID for cell pointer may fail due to OOM.
708 : template <typename HashPolicy>
709 : struct FallibleHashMethods
710 : {
711 : // Return true if a hashcode is already available for its argument. Once
712 : // this returns true for a specific argument it must continue to do so.
713 1941302 : template <typename Lookup> static bool hasHash(Lookup&& l) { return true; }
714 :
715 : // Fallible method to ensure a hashcode exists for its argument and create
716 : // one if not. Returns false on error, e.g. out of memory.
717 1683814 : template <typename Lookup> static bool ensureHash(Lookup&& l) { return true; }
718 : };
719 :
720 : template <typename HashPolicy, typename Lookup>
721 : static bool
722 1943313 : HasHash(Lookup&& l) {
723 1943313 : return FallibleHashMethods<typename HashPolicy::Base>::hasHash(mozilla::Forward<Lookup>(l));
724 : }
725 :
726 : template <typename HashPolicy, typename Lookup>
727 : static bool
728 1812051 : EnsureHash(Lookup&& l) {
729 1812051 : return FallibleHashMethods<typename HashPolicy::Base>::ensureHash(mozilla::Forward<Lookup>(l));
730 : }
731 :
732 : /*****************************************************************************/
733 :
734 : // Both HashMap and HashSet are implemented by a single HashTable that is even
735 : // more heavily parameterized than the other two. This leaves HashTable gnarly
736 : // and extremely coupled to HashMap and HashSet; thus code should not use
737 : // HashTable directly.
738 :
739 : template <class Key, class Value>
740 47151 : class HashMapEntry
741 : {
742 : Key key_;
743 : Value value_;
744 :
745 : template <class, class, class> friend class detail::HashTable;
746 : template <class> friend class detail::HashTableEntry;
747 : template <class, class, class, class> friend class HashMap;
748 :
749 : public:
750 : template<typename KeyInput, typename ValueInput>
751 71665 : HashMapEntry(KeyInput&& k, ValueInput&& v)
752 61823 : : key_(mozilla::Forward<KeyInput>(k)),
753 71665 : value_(mozilla::Forward<ValueInput>(v))
754 71665 : {}
755 :
756 52695 : HashMapEntry(HashMapEntry&& rhs)
757 52695 : : key_(mozilla::Move(rhs.key_)),
758 52695 : value_(mozilla::Move(rhs.value_))
759 52695 : {}
760 :
761 0 : void operator=(HashMapEntry&& rhs) {
762 0 : key_ = mozilla::Move(rhs.key_);
763 0 : value_ = mozilla::Move(rhs.value_);
764 0 : }
765 :
766 : typedef Key KeyType;
767 : typedef Value ValueType;
768 :
769 2127868 : const Key& key() const { return key_; }
770 9605 : Key& mutableKey() { return key_; }
771 835 : const Value& value() const { return value_; }
772 1809089 : Value& value() { return value_; }
773 :
774 : private:
775 : HashMapEntry(const HashMapEntry&) = delete;
776 : void operator=(const HashMapEntry&) = delete;
777 : };
778 :
779 : } // namespace js
780 :
781 : namespace mozilla {
782 :
783 : template <typename T>
784 : struct IsPod<js::detail::HashTableEntry<T> > : IsPod<T> {};
785 :
786 : template <typename K, typename V>
787 : struct IsPod<js::HashMapEntry<K, V> >
788 : : IntegralConstant<bool, IsPod<K>::value && IsPod<V>::value>
789 : {};
790 :
791 : } // namespace mozilla
792 :
793 : namespace js {
794 :
795 : namespace detail {
796 :
797 : template <class T, class HashPolicy, class AllocPolicy>
798 : class HashTable;
799 :
800 : template <class T>
801 : class HashTableEntry
802 : {
803 : template <class, class, class> friend class HashTable;
804 : typedef typename mozilla::RemoveConst<T>::Type NonConstT;
805 :
806 : HashNumber keyHash;
807 : mozilla::AlignedStorage2<NonConstT> mem;
808 :
809 : static const HashNumber sFreeKey = 0;
810 : static const HashNumber sRemovedKey = 1;
811 : static const HashNumber sCollisionBit = 1;
812 :
813 29202101 : static bool isLiveHash(HashNumber hash)
814 : {
815 29202101 : return hash > sRemovedKey;
816 : }
817 :
818 : HashTableEntry(const HashTableEntry&) = delete;
819 : void operator=(const HashTableEntry&) = delete;
820 : ~HashTableEntry() = delete;
821 :
822 : public:
823 : // NB: HashTableEntry is treated as a POD: no constructor or destructor calls.
824 :
825 104936 : void destroyIfLive() {
826 104936 : if (isLive())
827 24375 : mem.addr()->~T();
828 104936 : }
829 :
830 313192 : void destroy() {
831 313192 : MOZ_ASSERT(isLive());
832 313192 : mem.addr()->~T();
833 313192 : }
834 :
835 0 : void swap(HashTableEntry* other) {
836 0 : if (this == other)
837 0 : return;
838 0 : MOZ_ASSERT(isLive());
839 0 : if (other->isLive()) {
840 0 : mozilla::Swap(*mem.addr(), *other->mem.addr());
841 : } else {
842 0 : *other->mem.addr() = mozilla::Move(*mem.addr());
843 0 : destroy();
844 : }
845 0 : mozilla::Swap(keyHash, other->keyHash);
846 : }
847 :
848 6658999 : T& get() { MOZ_ASSERT(isLive()); return *mem.addr(); }
849 7 : NonConstT& getMutable() { MOZ_ASSERT(isLive()); return *mem.addr(); }
850 :
851 6258576 : bool isFree() const { return keyHash == sFreeKey; }
852 6482 : void clearLive() { MOZ_ASSERT(isLive()); keyHash = sFreeKey; mem.addr()->~T(); }
853 126352 : void clear() { if (isLive()) mem.addr()->~T(); keyHash = sFreeKey; }
854 2913593 : bool isRemoved() const { return keyHash == sRemovedKey; }
855 1624 : void removeLive() { MOZ_ASSERT(isLive()); keyHash = sRemovedKey; mem.addr()->~T(); }
856 21683317 : bool isLive() const { return isLiveHash(keyHash); }
857 1354002 : void setCollision() { MOZ_ASSERT(isLive()); keyHash |= sCollisionBit; }
858 0 : void unsetCollision() { keyHash &= ~sCollisionBit; }
859 8106 : bool hasCollision() const { return keyHash & sCollisionBit; }
860 5747248 : bool matchHash(HashNumber hn) { return (keyHash & ~sCollisionBit) == hn; }
861 313192 : HashNumber getKeyHash() const { return keyHash & ~sCollisionBit; }
862 :
863 : template <typename... Args>
864 610268 : void setLive(HashNumber hn, Args&&... args)
865 : {
866 610268 : MOZ_ASSERT(!isLive());
867 610268 : keyHash = hn;
868 610268 : new(mem.addr()) T(mozilla::Forward<Args>(args)...);
869 610268 : MOZ_ASSERT(isLive());
870 610268 : }
871 : };
872 :
873 : template <class T, class HashPolicy, class AllocPolicy>
874 : class HashTable : private AllocPolicy
875 : {
876 : friend class mozilla::ReentrancyGuard;
877 :
878 : typedef typename mozilla::RemoveConst<T>::Type NonConstT;
879 : typedef typename HashPolicy::KeyType Key;
880 : typedef typename HashPolicy::Lookup Lookup;
881 :
882 : public:
883 : typedef HashTableEntry<T> Entry;
884 :
885 : // A nullable pointer to a hash table element. A Ptr |p| can be tested
886 : // either explicitly |if (p.found()) p->...| or using boolean conversion
887 : // |if (p) p->...|. Ptr objects must not be used after any mutating hash
888 : // table operations unless |generation()| is tested.
889 : class Ptr
890 : {
891 : friend class HashTable;
892 :
893 : Entry* entry_;
894 : #ifdef JS_DEBUG
895 : const HashTable* table_;
896 : Generation generation;
897 : #endif
898 :
899 : protected:
900 3728918 : Ptr(Entry& entry, const HashTable& tableArg)
901 : : entry_(&entry)
902 : #ifdef JS_DEBUG
903 : , table_(&tableArg)
904 3728918 : , generation(tableArg.generation())
905 : #endif
906 3728924 : {}
907 :
908 : public:
909 409940 : Ptr()
910 : : entry_(nullptr)
911 : #ifdef JS_DEBUG
912 : , table_(nullptr)
913 409940 : , generation(0)
914 : #endif
915 409940 : {}
916 :
917 8246567 : bool isValid() const {
918 8246567 : return !!entry_;
919 : }
920 :
921 7703333 : bool found() const {
922 7703333 : if (!isValid())
923 30749 : return false;
924 : #ifdef JS_DEBUG
925 7672613 : MOZ_ASSERT(generation == table_->generation());
926 : #endif
927 7672603 : return entry_->isLive();
928 : }
929 :
930 3577115 : explicit operator bool() const {
931 3577115 : return found();
932 : }
933 :
934 : bool operator==(const Ptr& rhs) const {
935 : MOZ_ASSERT(found() && rhs.found());
936 : return entry_ == rhs.entry_;
937 : }
938 :
939 : bool operator!=(const Ptr& rhs) const {
940 : #ifdef JS_DEBUG
941 : MOZ_ASSERT(generation == table_->generation());
942 : #endif
943 : return !(*this == rhs);
944 : }
945 :
946 215086 : T& operator*() const {
947 : #ifdef JS_DEBUG
948 215086 : MOZ_ASSERT(found());
949 215086 : MOZ_ASSERT(generation == table_->generation());
950 : #endif
951 215084 : return entry_->get();
952 : }
953 :
954 2652949 : T* operator->() const {
955 : #ifdef JS_DEBUG
956 2652949 : MOZ_ASSERT(found());
957 2652926 : MOZ_ASSERT(generation == table_->generation());
958 : #endif
959 2652870 : return &entry_->get();
960 : }
961 : };
962 :
963 : // A Ptr that can be used to add a key after a failed lookup.
964 : class AddPtr : public Ptr
965 : {
966 : friend class HashTable;
967 : HashNumber keyHash;
968 : #ifdef JS_DEBUG
969 : uint64_t mutationCount;
970 : #endif
971 :
972 1787798 : AddPtr(Entry& entry, const HashTable& tableArg, HashNumber hn)
973 : : Ptr(entry, tableArg)
974 : , keyHash(hn)
975 : #ifdef JS_DEBUG
976 1787798 : , mutationCount(tableArg.mutationCount)
977 : #endif
978 1787799 : {}
979 :
980 : public:
981 242579 : AddPtr() : keyHash(0) {}
982 : };
983 :
984 : // A collection of hash table entries. The collection is enumerated by
985 : // calling |front()| followed by |popFront()| as long as |!empty()|. As
986 : // with Ptr/AddPtr, Range objects must not be used after any mutating hash
987 : // table operation unless the |generation()| is tested.
988 : class Range
989 : {
990 : protected:
991 : friend class HashTable;
992 :
993 53795 : Range(const HashTable& tableArg, Entry* c, Entry* e)
994 : : cur(c)
995 : , end(e)
996 : #ifdef JS_DEBUG
997 : , table_(&tableArg)
998 53795 : , mutationCount(tableArg.mutationCount)
999 : , generation(tableArg.generation())
1000 107590 : , validEntry(true)
1001 : #endif
1002 : {
1003 3997215 : while (cur < end && !cur->isLive())
1004 1971710 : ++cur;
1005 53795 : }
1006 :
1007 : Entry* cur;
1008 : Entry* end;
1009 : #ifdef JS_DEBUG
1010 : const HashTable* table_;
1011 : uint64_t mutationCount;
1012 : Generation generation;
1013 : bool validEntry;
1014 : #endif
1015 :
1016 : public:
1017 41145 : Range()
1018 : : cur(nullptr)
1019 : , end(nullptr)
1020 : #ifdef JS_DEBUG
1021 : , table_(nullptr)
1022 : , mutationCount(0)
1023 : , generation(0)
1024 41145 : , validEntry(false)
1025 : #endif
1026 41145 : {}
1027 :
1028 767042 : bool empty() const {
1029 : #ifdef JS_DEBUG
1030 767042 : MOZ_ASSERT(generation == table_->generation());
1031 767042 : MOZ_ASSERT(mutationCount == table_->mutationCount);
1032 : #endif
1033 767042 : return cur == end;
1034 : }
1035 :
1036 220710 : T& front() const {
1037 220710 : MOZ_ASSERT(!empty());
1038 : #ifdef JS_DEBUG
1039 220710 : MOZ_ASSERT(validEntry);
1040 220710 : MOZ_ASSERT(generation == table_->generation());
1041 220710 : MOZ_ASSERT(mutationCount == table_->mutationCount);
1042 : #endif
1043 220710 : return cur->get();
1044 : }
1045 :
1046 190779 : void popFront() {
1047 190779 : MOZ_ASSERT(!empty());
1048 : #ifdef JS_DEBUG
1049 190779 : MOZ_ASSERT(generation == table_->generation());
1050 190779 : MOZ_ASSERT(mutationCount == table_->mutationCount);
1051 : #endif
1052 2355753 : while (++cur < end && !cur->isLive())
1053 1082487 : continue;
1054 : #ifdef JS_DEBUG
1055 190779 : validEntry = true;
1056 : #endif
1057 190779 : }
1058 : };
1059 :
1060 : // A Range whose lifetime delimits a mutating enumeration of a hash table.
1061 : // Since rehashing when elements were removed during enumeration would be
1062 : // bad, it is postponed until the Enum is destructed. Since the Enum's
1063 : // destructor touches the hash table, the user must ensure that the hash
1064 : // table is still alive when the destructor runs.
1065 : class Enum : public Range
1066 : {
1067 : friend class HashTable;
1068 :
1069 : HashTable& table_;
1070 : bool rekeyed;
1071 : bool removed;
1072 :
1073 : // Enum is movable but not copyable.
1074 : Enum(const Enum&) = delete;
1075 : void operator=(const Enum&) = delete;
1076 :
1077 : public:
1078 : template<class Map>
1079 4049 : explicit Enum(Map& map)
1080 4049 : : Range(map.all()), table_(map.impl), rekeyed(false), removed(false) {}
1081 :
1082 : MOZ_IMPLICIT Enum(Enum&& other)
1083 : : Range(other), table_(other.table_), rekeyed(other.rekeyed), removed(other.removed)
1084 : {
1085 : other.rekeyed = false;
1086 : other.removed = false;
1087 : }
1088 :
1089 : // Removes the |front()| element from the table, leaving |front()|
1090 : // invalid until the next call to |popFront()|. For example:
1091 : //
1092 : // HashSet<int> s;
1093 : // for (HashSet<int>::Enum e(s); !e.empty(); e.popFront())
1094 : // if (e.front() == 42)
1095 : // e.removeFront();
1096 65 : void removeFront() {
1097 65 : table_.remove(*this->cur);
1098 65 : removed = true;
1099 : #ifdef JS_DEBUG
1100 65 : this->validEntry = false;
1101 65 : this->mutationCount = table_.mutationCount;
1102 : #endif
1103 65 : }
1104 :
1105 7 : NonConstT& mutableFront() {
1106 7 : MOZ_ASSERT(!this->empty());
1107 : #ifdef JS_DEBUG
1108 7 : MOZ_ASSERT(this->validEntry);
1109 7 : MOZ_ASSERT(this->generation == this->Range::table_->generation());
1110 7 : MOZ_ASSERT(this->mutationCount == this->Range::table_->mutationCount);
1111 : #endif
1112 7 : return this->cur->getMutable();
1113 : }
1114 :
1115 : // Removes the |front()| element and re-inserts it into the table with
1116 : // a new key at the new Lookup position. |front()| is invalid after
1117 : // this operation until the next call to |popFront()|.
1118 0 : void rekeyFront(const Lookup& l, const Key& k) {
1119 0 : MOZ_ASSERT(&k != &HashPolicy::getKey(this->cur->get()));
1120 0 : Ptr p(*this->cur, table_);
1121 0 : table_.rekeyWithoutRehash(p, l, k);
1122 0 : rekeyed = true;
1123 : #ifdef JS_DEBUG
1124 0 : this->validEntry = false;
1125 0 : this->mutationCount = table_.mutationCount;
1126 : #endif
1127 0 : }
1128 :
1129 0 : void rekeyFront(const Key& k) {
1130 0 : rekeyFront(k, k);
1131 0 : }
1132 :
1133 : // Potentially rehashes the table.
1134 4049 : ~Enum() {
1135 4049 : if (rekeyed) {
1136 0 : table_.gen++;
1137 0 : table_.checkOverRemoved();
1138 : }
1139 :
1140 4049 : if (removed)
1141 39 : table_.compactIfUnderloaded();
1142 4049 : }
1143 : };
1144 :
1145 : // HashTable is movable
1146 3195 : HashTable(HashTable&& rhs)
1147 74 : : AllocPolicy(rhs)
1148 : {
1149 3195 : mozilla::PodAssign(this, &rhs);
1150 3195 : rhs.table = nullptr;
1151 3195 : }
1152 8 : void operator=(HashTable&& rhs) {
1153 8 : MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
1154 8 : if (table)
1155 0 : destroyTable(*this, table, capacity());
1156 8 : mozilla::PodAssign(this, &rhs);
1157 8 : rhs.table = nullptr;
1158 8 : }
1159 :
1160 : private:
1161 : // HashTable is not copyable or assignable
1162 : HashTable(const HashTable&) = delete;
1163 : void operator=(const HashTable&) = delete;
1164 :
1165 : private:
1166 : static const size_t CAP_BITS = 30;
1167 :
1168 : public:
1169 : uint64_t gen:56; // entry storage generation number
1170 : uint64_t hashShift:8; // multiplicative hash shift
1171 : Entry* table; // entry storage
1172 : uint32_t entryCount; // number of entries in table
1173 : uint32_t removedCount; // removed entry sentinels in table
1174 :
1175 : #ifdef JS_DEBUG
1176 : uint64_t mutationCount;
1177 : mutable bool mEntered;
1178 : // Note that some updates to these stats are not thread-safe. See the
1179 : // comment on the three-argument overloading of HashTable::lookup().
1180 : mutable struct Stats
1181 : {
1182 : uint32_t searches; // total number of table searches
1183 : uint32_t steps; // hash chain links traversed
1184 : uint32_t hits; // searches that found key
1185 : uint32_t misses; // searches that didn't find key
1186 : uint32_t addOverRemoved; // adds that recycled a removed entry
1187 : uint32_t removes; // calls to remove
1188 : uint32_t removeFrees; // calls to remove that freed the entry
1189 : uint32_t grows; // table expansions
1190 : uint32_t shrinks; // table contractions
1191 : uint32_t compresses; // table compressions
1192 : uint32_t rehashes; // tombstone decontaminations
1193 : } stats;
1194 : # define METER(x) x
1195 : #else
1196 : # define METER(x)
1197 : #endif
1198 :
1199 : // The default initial capacity is 32 (enough to hold 16 elements), but it
1200 : // can be as low as 4.
1201 : static const unsigned sMinCapacityLog2 = 2;
1202 : static const unsigned sMinCapacity = 1 << sMinCapacityLog2;
1203 : static const unsigned sMaxInit = JS_BIT(CAP_BITS - 1);
1204 : static const unsigned sMaxCapacity = JS_BIT(CAP_BITS);
1205 : static const unsigned sHashBits = mozilla::tl::BitSize<HashNumber>::value;
1206 :
1207 : // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1208 : // math we implement it as a ratio of integers.
1209 : static const uint8_t sAlphaDenominator = 4;
1210 : static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
1211 : static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
1212 :
1213 : static const HashNumber sFreeKey = Entry::sFreeKey;
1214 : static const HashNumber sRemovedKey = Entry::sRemovedKey;
1215 : static const HashNumber sCollisionBit = Entry::sCollisionBit;
1216 :
1217 14211 : void setTableSizeLog2(unsigned sizeLog2)
1218 : {
1219 14211 : hashShift = sHashBits - sizeLog2;
1220 14211 : }
1221 :
1222 7524002 : static bool isLiveHash(HashNumber hash)
1223 : {
1224 7524002 : return Entry::isLiveHash(hash);
1225 : }
1226 :
1227 3779032 : static HashNumber prepareHash(const Lookup& l)
1228 : {
1229 3779032 : HashNumber keyHash = ScrambleHashCode(HashPolicy::hash(l));
1230 :
1231 : // Avoid reserved hash codes.
1232 3779064 : if (!isLiveHash(keyHash))
1233 39664 : keyHash -= (sRemovedKey + 1);
1234 3779059 : return keyHash & ~sCollisionBit;
1235 : }
1236 :
1237 : enum FailureBehavior { DontReportFailure = false, ReportFailure = true };
1238 :
1239 14211 : static Entry* createTable(AllocPolicy& alloc, uint32_t capacity,
1240 : FailureBehavior reportFailure = ReportFailure)
1241 : {
1242 : static_assert(sFreeKey == 0,
1243 : "newly-calloc'd tables have to be considered empty");
1244 14211 : if (reportFailure)
1245 13196 : return alloc.template pod_calloc<Entry>(capacity);
1246 :
1247 1015 : return alloc.template maybe_pod_calloc<Entry>(capacity);
1248 : }
1249 :
1250 : static Entry* maybeCreateTable(AllocPolicy& alloc, uint32_t capacity)
1251 : {
1252 : static_assert(sFreeKey == 0,
1253 : "newly-calloc'd tables have to be considered empty");
1254 : return alloc.template maybe_pod_calloc<Entry>(capacity);
1255 : }
1256 :
1257 2222 : static void destroyTable(AllocPolicy& alloc, Entry* oldTable, uint32_t capacity)
1258 : {
1259 2222 : Entry* end = oldTable + capacity;
1260 107158 : for (Entry* e = oldTable; e < end; ++e)
1261 104936 : e->destroyIfLive();
1262 2222 : alloc.free_(oldTable);
1263 2222 : }
1264 :
1265 : public:
1266 32051 : explicit HashTable(AllocPolicy ap)
1267 : : AllocPolicy(ap)
1268 : , gen(0)
1269 : , hashShift(sHashBits)
1270 : , table(nullptr)
1271 : , entryCount(0)
1272 : , removedCount(0)
1273 : #ifdef JS_DEBUG
1274 : , mutationCount(0)
1275 32051 : , mEntered(false)
1276 : #endif
1277 32051 : {}
1278 :
1279 9727 : MOZ_MUST_USE bool init(uint32_t length)
1280 : {
1281 9727 : MOZ_ASSERT(!initialized());
1282 :
1283 : // Reject all lengths whose initial computed capacity would exceed
1284 : // sMaxCapacity. Round that maximum length down to the nearest power
1285 : // of two for speedier code.
1286 9727 : if (MOZ_UNLIKELY(length > sMaxInit)) {
1287 0 : this->reportAllocOverflow();
1288 0 : return false;
1289 : }
1290 :
1291 : static_assert((sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,
1292 : "multiplication in numerator below could overflow");
1293 : static_assert(sMaxInit * sAlphaDenominator <= UINT32_MAX - sMaxAlphaNumerator,
1294 : "numerator calculation below could potentially overflow");
1295 :
1296 : // Compute the smallest capacity allowing |length| elements to be
1297 : // inserted without rehashing: ceil(length / max-alpha). (Ceiling
1298 : // integral division: <http://stackoverflow.com/a/2745086>.)
1299 : uint32_t newCapacity =
1300 9727 : (length * sAlphaDenominator + sMaxAlphaNumerator - 1) / sMaxAlphaNumerator;
1301 9727 : if (newCapacity < sMinCapacity)
1302 2529 : newCapacity = sMinCapacity;
1303 :
1304 : // FIXME: use JS_CEILING_LOG2 when PGO stops crashing (bug 543034).
1305 9727 : uint32_t roundUp = sMinCapacity, roundUpLog2 = sMinCapacityLog2;
1306 46093 : while (roundUp < newCapacity) {
1307 18183 : roundUp <<= 1;
1308 18183 : ++roundUpLog2;
1309 : }
1310 :
1311 9727 : newCapacity = roundUp;
1312 9727 : MOZ_ASSERT(newCapacity >= length);
1313 9727 : MOZ_ASSERT(newCapacity <= sMaxCapacity);
1314 :
1315 9727 : table = createTable(*this, newCapacity);
1316 9727 : if (!table)
1317 0 : return false;
1318 :
1319 9727 : setTableSizeLog2(roundUpLog2);
1320 9727 : METER(memset(&stats, 0, sizeof(stats)));
1321 9727 : return true;
1322 : }
1323 :
1324 207267 : bool initialized() const
1325 : {
1326 207267 : return !!table;
1327 : }
1328 :
1329 27305 : ~HashTable()
1330 : {
1331 27305 : if (table)
1332 2124 : destroyTable(*this, table, capacity());
1333 27305 : }
1334 :
1335 : private:
1336 4094592 : HashNumber hash1(HashNumber hash0) const
1337 : {
1338 4094592 : return hash0 >> hashShift;
1339 : }
1340 :
1341 : struct DoubleHash
1342 : {
1343 : HashNumber h2;
1344 : HashNumber sizeMask;
1345 : };
1346 :
1347 1190895 : DoubleHash hash2(HashNumber curKeyHash) const
1348 : {
1349 1190895 : unsigned sizeLog2 = sHashBits - hashShift;
1350 : DoubleHash dh = {
1351 1190895 : ((curKeyHash << sizeLog2) >> hashShift) | 1,
1352 1190895 : (HashNumber(1) << sizeLog2) - 1
1353 2381790 : };
1354 1190895 : return dh;
1355 : }
1356 :
1357 2616515 : static HashNumber applyDoubleHash(HashNumber h1, const DoubleHash& dh)
1358 : {
1359 2616515 : return (h1 - dh.h2) & dh.sizeMask;
1360 : }
1361 :
1362 290565 : bool overloaded()
1363 : {
1364 : static_assert(sMaxCapacity <= UINT32_MAX / sMaxAlphaNumerator,
1365 : "multiplication below could overflow");
1366 290565 : return entryCount + removedCount >=
1367 290565 : capacity() * sMaxAlphaNumerator / sAlphaDenominator;
1368 : }
1369 :
1370 : // Would the table be underloaded if it had the given capacity and entryCount?
1371 5290 : static bool wouldBeUnderloaded(uint32_t capacity, uint32_t entryCount)
1372 : {
1373 : static_assert(sMaxCapacity <= UINT32_MAX / sMinAlphaNumerator,
1374 : "multiplication below could overflow");
1375 8889 : return capacity > sMinCapacity &&
1376 8889 : entryCount <= capacity * sMinAlphaNumerator / sAlphaDenominator;
1377 : }
1378 :
1379 5074 : bool underloaded()
1380 : {
1381 5074 : return wouldBeUnderloaded(capacity(), entryCount);
1382 : }
1383 :
1384 3257393 : static MOZ_ALWAYS_INLINE bool match(Entry& e, const Lookup& l)
1385 : {
1386 3257393 : return HashPolicy::match(HashPolicy::getKey(e.get()), l);
1387 : }
1388 :
1389 : // Warning: in order for readonlyThreadsafeLookup() to be safe this
1390 : // function must not modify the table in any way when |collisionBit| is 0.
1391 : // (The use of the METER() macro to increment stats violates this
1392 : // restriction but we will live with that for now because it's enabled so
1393 : // rarely.)
1394 : MOZ_ALWAYS_INLINE Entry&
1395 3745435 : lookup(const Lookup& l, HashNumber keyHash, unsigned collisionBit) const
1396 : {
1397 3745435 : MOZ_ASSERT(isLiveHash(keyHash));
1398 3745288 : MOZ_ASSERT(!(keyHash & sCollisionBit));
1399 3745288 : MOZ_ASSERT(collisionBit == 0 || collisionBit == sCollisionBit);
1400 3745288 : MOZ_ASSERT(table);
1401 3745288 : METER(stats.searches++);
1402 :
1403 : // Compute the primary hash address.
1404 3745288 : HashNumber h1 = hash1(keyHash);
1405 3745369 : Entry* entry = &table[h1];
1406 :
1407 : // Miss: return space for a new entry.
1408 3745369 : if (entry->isFree()) {
1409 245522 : METER(stats.misses++);
1410 245522 : return *entry;
1411 : }
1412 :
1413 : // Hit: return entry.
1414 3499732 : if (entry->matchHash(keyHash) && match(*entry, l)) {
1415 2380459 : METER(stats.hits++);
1416 2380459 : return *entry;
1417 : }
1418 :
1419 : // Collision: double hash.
1420 1119364 : DoubleHash dh = hash2(keyHash);
1421 :
1422 : // Save the first removed entry pointer so we can recycle later.
1423 1119387 : Entry* firstRemoved = nullptr;
1424 :
1425 : while (true) {
1426 3907553 : if (MOZ_UNLIKELY(entry->isRemoved())) {
1427 1860 : if (!firstRemoved)
1428 1668 : firstRemoved = entry;
1429 : } else {
1430 2511565 : if (collisionBit == sCollisionBit)
1431 1250900 : entry->setCollision();
1432 : }
1433 :
1434 2513426 : METER(stats.steps++);
1435 2513426 : h1 = applyDoubleHash(h1, dh);
1436 :
1437 2513412 : entry = &table[h1];
1438 2513412 : if (entry->isFree()) {
1439 265726 : METER(stats.misses++);
1440 265726 : return firstRemoved ? *firstRemoved : *entry;
1441 : }
1442 :
1443 2247715 : if (entry->matchHash(keyHash) && match(*entry, l)) {
1444 853655 : METER(stats.hits++);
1445 853655 : return *entry;
1446 : }
1447 : }
1448 : }
1449 :
1450 : // This is a copy of lookup hardcoded to the assumptions:
1451 : // 1. the lookup is a lookupForAdd
1452 : // 2. the key, whose |keyHash| has been passed is not in the table,
1453 : // 3. no entries have been removed from the table.
1454 : // This specialized search avoids the need for recovering lookup values
1455 : // from entries, which allows more flexible Lookup/Key types.
1456 349293 : Entry& findFreeEntry(HashNumber keyHash)
1457 : {
1458 349293 : MOZ_ASSERT(!(keyHash & sCollisionBit));
1459 349293 : MOZ_ASSERT(table);
1460 349293 : METER(stats.searches++);
1461 :
1462 : // We assume 'keyHash' has already been distributed.
1463 :
1464 : // Compute the primary hash address.
1465 349293 : HashNumber h1 = hash1(keyHash);
1466 349293 : Entry* entry = &table[h1];
1467 :
1468 : // Miss: return space for a new entry.
1469 349293 : if (!entry->isLive()) {
1470 277790 : METER(stats.misses++);
1471 277790 : return *entry;
1472 : }
1473 :
1474 : // Collision: double hash.
1475 71503 : DoubleHash dh = hash2(keyHash);
1476 :
1477 31604 : while (true) {
1478 103107 : MOZ_ASSERT(!entry->isRemoved());
1479 103107 : entry->setCollision();
1480 :
1481 103107 : METER(stats.steps++);
1482 103107 : h1 = applyDoubleHash(h1, dh);
1483 :
1484 103107 : entry = &table[h1];
1485 103107 : if (!entry->isLive()) {
1486 71503 : METER(stats.misses++);
1487 71503 : return *entry;
1488 : }
1489 : }
1490 : }
1491 :
1492 : enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };
1493 :
1494 4483 : RebuildStatus changeTableSize(int deltaLog2, FailureBehavior reportFailure = ReportFailure)
1495 : {
1496 : // Look, but don't touch, until we succeed in getting new entry store.
1497 4483 : Entry* oldTable = table;
1498 4483 : uint32_t oldCap = capacity();
1499 4483 : uint32_t newLog2 = sHashBits - hashShift + deltaLog2;
1500 4483 : uint32_t newCapacity = JS_BIT(newLog2);
1501 4483 : if (MOZ_UNLIKELY(newCapacity > sMaxCapacity)) {
1502 0 : if (reportFailure)
1503 0 : this->reportAllocOverflow();
1504 0 : return RehashFailed;
1505 : }
1506 :
1507 4483 : Entry* newTable = createTable(*this, newCapacity, reportFailure);
1508 4483 : if (!newTable)
1509 0 : return RehashFailed;
1510 :
1511 : // We can't fail from here on, so update table parameters.
1512 4483 : setTableSizeLog2(newLog2);
1513 4483 : removedCount = 0;
1514 4483 : gen++;
1515 4483 : table = newTable;
1516 :
1517 : // Copy only live entries, leaving removed ones behind.
1518 4483 : Entry* end = oldTable + oldCap;
1519 533815 : for (Entry* src = oldTable; src < end; ++src) {
1520 529332 : if (src->isLive()) {
1521 313192 : HashNumber hn = src->getKeyHash();
1522 313192 : findFreeEntry(hn).setLive(
1523 313192 : hn, mozilla::Move(const_cast<typename Entry::NonConstT&>(src->get())));
1524 313192 : src->destroy();
1525 : }
1526 : }
1527 :
1528 : // All entries have been destroyed, no need to destroyTable.
1529 4483 : this->free_(oldTable);
1530 4483 : return Rehashed;
1531 : }
1532 :
1533 3592 : bool shouldCompressTable()
1534 : {
1535 : // Compress if a quarter or more of all entries are removed.
1536 3592 : return removedCount >= (capacity() >> 2);
1537 : }
1538 :
1539 287598 : RebuildStatus checkOverloaded(FailureBehavior reportFailure = ReportFailure)
1540 : {
1541 287598 : if (!overloaded())
1542 284006 : return NotOverloaded;
1543 :
1544 : int deltaLog2;
1545 3592 : if (shouldCompressTable()) {
1546 54 : METER(stats.compresses++);
1547 54 : deltaLog2 = 0;
1548 : } else {
1549 3538 : METER(stats.grows++);
1550 3538 : deltaLog2 = 1;
1551 : }
1552 :
1553 3592 : return changeTableSize(deltaLog2, reportFailure);
1554 : }
1555 :
1556 : // Infallibly rehash the table if we are overloaded with removals.
1557 2967 : void checkOverRemoved()
1558 : {
1559 2967 : if (overloaded()) {
1560 124 : if (checkOverloaded(DontReportFailure) == RehashFailed)
1561 0 : rehashTableInPlace();
1562 : }
1563 2967 : }
1564 :
1565 8106 : void remove(Entry& e)
1566 : {
1567 8106 : MOZ_ASSERT(table);
1568 8106 : METER(stats.removes++);
1569 :
1570 8106 : if (e.hasCollision()) {
1571 1624 : e.removeLive();
1572 1624 : removedCount++;
1573 : } else {
1574 6482 : METER(stats.removeFrees++);
1575 6482 : e.clearLive();
1576 : }
1577 8106 : entryCount--;
1578 : #ifdef JS_DEBUG
1579 8106 : mutationCount++;
1580 : #endif
1581 8106 : }
1582 :
1583 5074 : void checkUnderloaded()
1584 : {
1585 5074 : if (underloaded()) {
1586 867 : METER(stats.shrinks++);
1587 867 : (void) changeTableSize(-1, DontReportFailure);
1588 : }
1589 5074 : }
1590 :
1591 : // Resize the table down to the largest capacity which doesn't underload the
1592 : // table. Since we call checkUnderloaded() on every remove, you only need
1593 : // to call this after a bulk removal of items done without calling remove().
1594 55 : void compactIfUnderloaded()
1595 : {
1596 55 : int32_t resizeLog2 = 0;
1597 55 : uint32_t newCapacity = capacity();
1598 377 : while (wouldBeUnderloaded(newCapacity, entryCount)) {
1599 161 : newCapacity = newCapacity >> 1;
1600 161 : resizeLog2--;
1601 : }
1602 :
1603 55 : if (resizeLog2 != 0)
1604 24 : (void) changeTableSize(resizeLog2, DontReportFailure);
1605 55 : }
1606 :
1607 : // This is identical to changeTableSize(currentSize), but without requiring
1608 : // a second table. We do this by recycling the collision bits to tell us if
1609 : // the element is already inserted or still waiting to be inserted. Since
1610 : // already-inserted elements win any conflicts, we get the same table as we
1611 : // would have gotten through random insertion order.
1612 0 : void rehashTableInPlace()
1613 : {
1614 0 : METER(stats.rehashes++);
1615 0 : removedCount = 0;
1616 0 : gen++;
1617 0 : for (size_t i = 0; i < capacity(); ++i)
1618 0 : table[i].unsetCollision();
1619 :
1620 0 : for (size_t i = 0; i < capacity();) {
1621 0 : Entry* src = &table[i];
1622 :
1623 0 : if (!src->isLive() || src->hasCollision()) {
1624 0 : ++i;
1625 0 : continue;
1626 : }
1627 :
1628 0 : HashNumber keyHash = src->getKeyHash();
1629 0 : HashNumber h1 = hash1(keyHash);
1630 0 : DoubleHash dh = hash2(keyHash);
1631 0 : Entry* tgt = &table[h1];
1632 : while (true) {
1633 0 : if (!tgt->hasCollision()) {
1634 0 : src->swap(tgt);
1635 0 : tgt->setCollision();
1636 0 : break;
1637 : }
1638 :
1639 0 : h1 = applyDoubleHash(h1, dh);
1640 0 : tgt = &table[h1];
1641 : }
1642 : }
1643 :
1644 : // TODO: this algorithm leaves collision bits on *all* elements, even if
1645 : // they are on no collision path. We have the option of setting the
1646 : // collision bits correctly on a subsequent pass or skipping the rehash
1647 : // unless we are totally filled with tombstones: benchmark to find out
1648 : // which approach is best.
1649 0 : }
1650 :
1651 : // Note: |l| may be a reference to a piece of |u|, so this function
1652 : // must take care not to use |l| after moving |u|.
1653 : //
1654 : // Prefer to use putNewInfallible; this function does not check
1655 : // invariants.
1656 : template <typename... Args>
1657 33621 : void putNewInfallibleInternal(const Lookup& l, Args&&... args)
1658 : {
1659 33621 : MOZ_ASSERT(table);
1660 :
1661 33621 : HashNumber keyHash = prepareHash(l);
1662 33621 : Entry* entry = &findFreeEntry(keyHash);
1663 33621 : MOZ_ASSERT(entry);
1664 :
1665 33621 : if (entry->isRemoved()) {
1666 257 : METER(stats.addOverRemoved++);
1667 257 : removedCount--;
1668 257 : keyHash |= sCollisionBit;
1669 : }
1670 :
1671 33621 : entry->setLive(keyHash, mozilla::Forward<Args>(args)...);
1672 33621 : entryCount++;
1673 : #ifdef JS_DEBUG
1674 33621 : mutationCount++;
1675 : #endif
1676 33621 : }
1677 :
1678 : public:
1679 815 : void clear()
1680 : {
1681 : if (mozilla::IsPod<Entry>::value) {
1682 574 : memset(table, 0, sizeof(*table) * capacity());
1683 : } else {
1684 241 : uint32_t tableCapacity = capacity();
1685 241 : Entry* end = table + tableCapacity;
1686 126593 : for (Entry* e = table; e < end; ++e)
1687 126352 : e->clear();
1688 : }
1689 815 : removedCount = 0;
1690 815 : entryCount = 0;
1691 : #ifdef JS_DEBUG
1692 815 : mutationCount++;
1693 : #endif
1694 815 : }
1695 :
1696 16 : void clearAndShrink()
1697 : {
1698 16 : clear();
1699 16 : compactIfUnderloaded();
1700 16 : }
1701 :
1702 121 : void finish()
1703 : {
1704 : #ifdef JS_DEBUG
1705 121 : MOZ_ASSERT(!mEntered);
1706 : #endif
1707 121 : if (!table)
1708 23 : return;
1709 :
1710 98 : destroyTable(*this, table, capacity());
1711 98 : table = nullptr;
1712 98 : gen++;
1713 98 : entryCount = 0;
1714 98 : removedCount = 0;
1715 : #ifdef JS_DEBUG
1716 98 : mutationCount++;
1717 : #endif
1718 : }
1719 :
1720 53795 : Range all() const
1721 : {
1722 53795 : MOZ_ASSERT(table);
1723 53795 : return Range(*this, table, table + capacity());
1724 : }
1725 :
1726 13903 : bool empty() const
1727 : {
1728 13903 : MOZ_ASSERT(table);
1729 13903 : return !entryCount;
1730 : }
1731 :
1732 52075 : uint32_t count() const
1733 : {
1734 52075 : MOZ_ASSERT(table);
1735 52075 : return entryCount;
1736 : }
1737 :
1738 360615 : uint32_t capacity() const
1739 : {
1740 360615 : MOZ_ASSERT(table);
1741 360615 : return JS_BIT(sHashBits - hashShift);
1742 : }
1743 :
1744 16050841 : Generation generation() const
1745 : {
1746 16050841 : MOZ_ASSERT(table);
1747 16050841 : return Generation(gen);
1748 : }
1749 :
1750 0 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
1751 : {
1752 0 : return mallocSizeOf(table);
1753 : }
1754 :
1755 : size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const
1756 : {
1757 : return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
1758 : }
1759 :
1760 1813968 : MOZ_ALWAYS_INLINE Ptr lookup(const Lookup& l) const
1761 : {
1762 3627923 : mozilla::ReentrancyGuard g(*this);
1763 1813967 : if (!HasHash<HashPolicy>(l))
1764 2427 : return Ptr();
1765 1811539 : HashNumber keyHash = prepareHash(l);
1766 1811541 : return Ptr(lookup(l, keyHash, 0), *this);
1767 : }
1768 :
1769 129412 : MOZ_ALWAYS_INLINE Ptr readonlyThreadsafeLookup(const Lookup& l) const
1770 : {
1771 129412 : if (!HasHash<HashPolicy>(l))
1772 0 : return Ptr();
1773 129412 : HashNumber keyHash = prepareHash(l);
1774 129412 : return Ptr(lookup(l, keyHash, 0), *this);
1775 : }
1776 :
1777 1787804 : MOZ_ALWAYS_INLINE AddPtr lookupForAdd(const Lookup& l) const
1778 : {
1779 3575643 : mozilla::ReentrancyGuard g(*this);
1780 1787807 : if (!EnsureHash<HashPolicy>(l))
1781 0 : return AddPtr();
1782 1787809 : HashNumber keyHash = prepareHash(l);
1783 1787807 : Entry& entry = lookup(l, keyHash, sCollisionBit);
1784 1787801 : AddPtr p(entry, *this, keyHash);
1785 1787839 : return p;
1786 : }
1787 :
1788 : template <typename... Args>
1789 263454 : MOZ_MUST_USE bool add(AddPtr& p, Args&&... args)
1790 : {
1791 526909 : mozilla::ReentrancyGuard g(*this);
1792 263454 : MOZ_ASSERT(table);
1793 263454 : MOZ_ASSERT_IF(p.isValid(), p.table_ == this);
1794 263454 : MOZ_ASSERT(!p.found());
1795 263455 : MOZ_ASSERT(!(p.keyHash & sCollisionBit));
1796 :
1797 : // Check for error from ensureHash() here.
1798 263455 : if (!p.isValid())
1799 0 : return false;
1800 :
1801 263455 : MOZ_ASSERT(p.generation == generation());
1802 263455 : MOZ_ASSERT(p.mutationCount == mutationCount);
1803 :
1804 : // Changing an entry from removed to live does not affect whether we
1805 : // are overloaded and can be handled separately.
1806 263455 : if (p.entry_->isRemoved()) {
1807 232 : if (!this->checkSimulatedOOM())
1808 0 : return false;
1809 232 : METER(stats.addOverRemoved++);
1810 232 : removedCount--;
1811 232 : p.keyHash |= sCollisionBit;
1812 : } else {
1813 : // Preserve the validity of |p.entry_|.
1814 263223 : RebuildStatus status = checkOverloaded();
1815 263223 : if (status == RehashFailed)
1816 0 : return false;
1817 263223 : if (status == NotOverloaded && !this->checkSimulatedOOM())
1818 0 : return false;
1819 263223 : if (status == Rehashed)
1820 2480 : p.entry_ = &findFreeEntry(p.keyHash);
1821 : }
1822 :
1823 263455 : p.entry_->setLive(p.keyHash, mozilla::Forward<Args>(args)...);
1824 263455 : entryCount++;
1825 : #ifdef JS_DEBUG
1826 263455 : mutationCount++;
1827 263455 : p.generation = generation();
1828 263455 : p.mutationCount = mutationCount;
1829 : #endif
1830 263455 : return true;
1831 : }
1832 :
1833 : // Note: |l| may be a reference to a piece of |u|, so this function
1834 : // must take care not to use |l| after moving |u|.
1835 : template <typename... Args>
1836 30654 : void putNewInfallible(const Lookup& l, Args&&... args)
1837 : {
1838 30654 : MOZ_ASSERT(!lookup(l).found());
1839 61308 : mozilla::ReentrancyGuard g(*this);
1840 30654 : putNewInfallibleInternal(l, mozilla::Forward<Args>(args)...);
1841 30654 : }
1842 :
1843 : // Note: |l| may be alias arguments in |args|, so this function must take
1844 : // care not to use |l| after moving |args|.
1845 : template <typename... Args>
1846 24247 : MOZ_MUST_USE bool putNew(const Lookup& l, Args&&... args)
1847 : {
1848 24247 : if (!this->checkSimulatedOOM())
1849 0 : return false;
1850 :
1851 24247 : if (!EnsureHash<HashPolicy>(l))
1852 0 : return false;
1853 :
1854 24247 : if (checkOverloaded() == RehashFailed)
1855 0 : return false;
1856 :
1857 24247 : putNewInfallible(l, mozilla::Forward<Args>(args)...);
1858 24247 : return true;
1859 : }
1860 :
1861 : // Note: |l| may be a reference to a piece of |u|, so this function
1862 : // must take care not to use |l| after moving |u|.
1863 : template <typename... Args>
1864 16413 : MOZ_MUST_USE bool relookupOrAdd(AddPtr& p, const Lookup& l, Args&&... args)
1865 : {
1866 : // Check for error from ensureHash() here.
1867 16413 : if (!p.isValid())
1868 0 : return false;
1869 :
1870 : #ifdef JS_DEBUG
1871 16413 : p.generation = generation();
1872 16413 : p.mutationCount = mutationCount;
1873 : #endif
1874 : {
1875 32826 : mozilla::ReentrancyGuard g(*this);
1876 16413 : MOZ_ASSERT(prepareHash(l) == p.keyHash); // l has not been destroyed
1877 16413 : p.entry_ = &lookup(l, p.keyHash, sCollisionBit);
1878 : }
1879 16413 : return p.found() || add(p, mozilla::Forward<Args>(args)...);
1880 : }
1881 :
1882 5074 : void remove(Ptr p)
1883 : {
1884 5074 : MOZ_ASSERT(table);
1885 10148 : mozilla::ReentrancyGuard g(*this);
1886 5074 : MOZ_ASSERT(p.found());
1887 5074 : MOZ_ASSERT(p.generation == generation());
1888 5074 : remove(*p.entry_);
1889 5074 : checkUnderloaded();
1890 5074 : }
1891 :
1892 2967 : void rekeyWithoutRehash(Ptr p, const Lookup& l, const Key& k)
1893 : {
1894 2967 : MOZ_ASSERT(table);
1895 5934 : mozilla::ReentrancyGuard g(*this);
1896 2967 : MOZ_ASSERT(p.found());
1897 2967 : MOZ_ASSERT(p.generation == generation());
1898 5068 : typename HashTableEntry<T>::NonConstT t(mozilla::Move(*p));
1899 2967 : HashPolicy::setKey(t, const_cast<Key&>(k));
1900 2967 : remove(*p.entry_);
1901 2967 : putNewInfallibleInternal(l, mozilla::Move(t));
1902 2967 : }
1903 :
1904 2967 : void rekeyAndMaybeRehash(Ptr p, const Lookup& l, const Key& k)
1905 : {
1906 2967 : rekeyWithoutRehash(p, l, k);
1907 2967 : checkOverRemoved();
1908 2967 : }
1909 :
1910 : #undef METER
1911 : };
1912 :
1913 : } // namespace detail
1914 : } // namespace js
1915 :
1916 : #endif /* js_HashTable_h */
|
