Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include <new>
8 : #include <stdio.h>
9 : #include <stdlib.h>
10 : #include <string.h>
11 : #include "PLDHashTable.h"
12 : #include "mozilla/HashFunctions.h"
13 : #include "mozilla/MathAlgorithms.h"
14 : #include "mozilla/OperatorNewExtensions.h"
15 : #include "nsAlgorithm.h"
16 : #include "mozilla/Likely.h"
17 : #include "mozilla/MemoryReporting.h"
18 : #include "mozilla/ChaosMode.h"
19 :
20 : using namespace mozilla;
21 :
22 : #ifdef DEBUG
23 :
24 : class AutoReadOp
25 : {
26 : Checker& mChk;
27 : public:
28 239615 : explicit AutoReadOp(Checker& aChk) : mChk(aChk) { mChk.StartReadOp(); }
29 239610 : ~AutoReadOp() { mChk.EndReadOp(); }
30 : };
31 :
32 : class AutoWriteOp
33 : {
34 : Checker& mChk;
35 : public:
36 211259 : explicit AutoWriteOp(Checker& aChk) : mChk(aChk) { mChk.StartWriteOp(); }
37 211258 : ~AutoWriteOp() { mChk.EndWriteOp(); }
38 : };
39 :
40 : class AutoIteratorRemovalOp
41 : {
42 : Checker& mChk;
43 : public:
44 : explicit AutoIteratorRemovalOp(Checker& aChk)
45 : : mChk(aChk)
46 : {
47 : mChk.StartIteratorRemovalOp();
48 : }
49 : ~AutoIteratorRemovalOp() { mChk.EndIteratorRemovalOp(); }
50 : };
51 :
52 : class AutoDestructorOp
53 : {
54 : Checker& mChk;
55 : public:
56 5582 : explicit AutoDestructorOp(Checker& aChk)
57 5582 : : mChk(aChk)
58 : {
59 5582 : mChk.StartDestructorOp();
60 5583 : }
61 5583 : ~AutoDestructorOp() { mChk.EndDestructorOp(); }
62 : };
63 :
64 : #endif
65 :
66 : /* static */ PLDHashNumber
67 31000 : PLDHashTable::HashStringKey(const void* aKey)
68 : {
69 31000 : return HashString(static_cast<const char*>(aKey));
70 : }
71 :
72 : /* static */ PLDHashNumber
73 86339 : PLDHashTable::HashVoidPtrKeyStub(const void* aKey)
74 : {
75 86339 : return uintptr_t(aKey) >> 2;
76 : }
77 :
78 : /* static */ bool
79 24302 : PLDHashTable::MatchEntryStub(const PLDHashEntryHdr* aEntry, const void* aKey)
80 : {
81 24302 : const PLDHashEntryStub* stub = (const PLDHashEntryStub*)aEntry;
82 :
83 24302 : return stub->key == aKey;
84 : }
85 :
86 : /* static */ bool
87 148 : PLDHashTable::MatchStringKey(const PLDHashEntryHdr* aEntry, const void* aKey)
88 : {
89 148 : const PLDHashEntryStub* stub = (const PLDHashEntryStub*)aEntry;
90 :
91 : // XXX tolerate null keys on account of sloppy Mozilla callers.
92 444 : return stub->key == aKey ||
93 444 : (stub->key && aKey &&
94 296 : strcmp((const char*)stub->key, (const char*)aKey) == 0);
95 : }
96 :
97 : /* static */ void
98 60998 : PLDHashTable::MoveEntryStub(PLDHashTable* aTable,
99 : const PLDHashEntryHdr* aFrom,
100 : PLDHashEntryHdr* aTo)
101 : {
102 60998 : memcpy(aTo, aFrom, aTable->mEntrySize);
103 60998 : }
104 :
105 : /* static */ void
106 2627 : PLDHashTable::ClearEntryStub(PLDHashTable* aTable, PLDHashEntryHdr* aEntry)
107 : {
108 2627 : memset(aEntry, 0, aTable->mEntrySize);
109 2627 : }
110 :
111 : static const PLDHashTableOps gStubOps = {
112 : PLDHashTable::HashVoidPtrKeyStub,
113 : PLDHashTable::MatchEntryStub,
114 : PLDHashTable::MoveEntryStub,
115 : PLDHashTable::ClearEntryStub,
116 : nullptr
117 : };
118 :
119 : /* static */ const PLDHashTableOps*
120 673 : PLDHashTable::StubOps()
121 : {
122 673 : return &gStubOps;
123 : }
124 :
125 : static bool
126 18394 : SizeOfEntryStore(uint32_t aCapacity, uint32_t aEntrySize, uint32_t* aNbytes)
127 : {
128 18394 : uint64_t nbytes64 = uint64_t(aCapacity) * uint64_t(aEntrySize);
129 18394 : *aNbytes = aCapacity * aEntrySize;
130 18394 : return uint64_t(*aNbytes) == nbytes64; // returns false on overflow
131 : }
132 :
133 : // Compute max and min load numbers (entry counts). We have a secondary max
134 : // that allows us to overload a table reasonably if it cannot be grown further
135 : // (i.e. if ChangeTable() fails). The table slows down drastically if the
136 : // secondary max is too close to 1, but 0.96875 gives only a slight slowdown
137 : // while allowing 1.3x more elements.
138 : static inline uint32_t
139 200036 : MaxLoad(uint32_t aCapacity)
140 : {
141 200036 : return aCapacity - (aCapacity >> 2); // == aCapacity * 0.75
142 : }
143 : static inline uint32_t
144 0 : MaxLoadOnGrowthFailure(uint32_t aCapacity)
145 : {
146 0 : return aCapacity - (aCapacity >> 5); // == aCapacity * 0.96875
147 : }
148 : static inline uint32_t
149 9961 : MinLoad(uint32_t aCapacity)
150 : {
151 9961 : return aCapacity >> 2; // == aCapacity * 0.25
152 : }
153 :
154 : // Compute the minimum capacity (and the Log2 of that capacity) for a table
155 : // containing |aLength| elements while respecting the following contraints:
156 : // - table must be at most 75% full;
157 : // - capacity must be a power of two;
158 : // - capacity cannot be too small.
159 : static inline void
160 13606 : BestCapacity(uint32_t aLength, uint32_t* aCapacityOut,
161 : uint32_t* aLog2CapacityOut)
162 : {
163 : // Compute the smallest capacity allowing |aLength| elements to be inserted
164 : // without rehashing.
165 13606 : uint32_t capacity = (aLength * 4 + (3 - 1)) / 3; // == ceil(aLength * 4 / 3)
166 13606 : if (capacity < PLDHashTable::kMinCapacity) {
167 12774 : capacity = PLDHashTable::kMinCapacity;
168 : }
169 :
170 : // Round up capacity to next power-of-two.
171 13606 : uint32_t log2 = CeilingLog2(capacity);
172 13606 : capacity = 1u << log2;
173 13606 : MOZ_ASSERT(capacity <= PLDHashTable::kMaxCapacity);
174 :
175 13606 : *aCapacityOut = capacity;
176 13606 : *aLog2CapacityOut = log2;
177 13606 : }
178 :
179 : /* static */ MOZ_ALWAYS_INLINE uint32_t
180 13559 : PLDHashTable::HashShift(uint32_t aEntrySize, uint32_t aLength)
181 : {
182 13559 : if (aLength > kMaxInitialLength) {
183 0 : MOZ_CRASH("Initial length is too large");
184 : }
185 :
186 : uint32_t capacity, log2;
187 13559 : BestCapacity(aLength, &capacity, &log2);
188 :
189 : uint32_t nbytes;
190 13559 : if (!SizeOfEntryStore(capacity, aEntrySize, &nbytes)) {
191 0 : MOZ_CRASH("Initial entry store size is too large");
192 : }
193 :
194 : // Compute the hashShift value.
195 13559 : return kHashBits - log2;
196 : }
197 :
198 13559 : PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
199 13559 : uint32_t aLength)
200 : : mOps(aOps)
201 13559 : , mHashShift(HashShift(aEntrySize, aLength))
202 : , mEntrySize(aEntrySize)
203 : , mEntryCount(0)
204 : , mRemovedCount(0)
205 : , mEntryStore()
206 : #ifdef DEBUG
207 27118 : , mChecker()
208 : #endif
209 : {
210 13559 : }
211 :
212 : PLDHashTable&
213 3 : PLDHashTable::operator=(PLDHashTable&& aOther)
214 : {
215 3 : if (this == &aOther) {
216 0 : return *this;
217 : }
218 :
219 : // Destruct |this|.
220 3 : this->~PLDHashTable();
221 :
222 : // |mOps| and |mEntrySize| are const so we can't assign them. Instead, we
223 : // require that they are equal. The justification for this is that they're
224 : // conceptually part of the type -- indeed, if PLDHashTable was a templated
225 : // type like nsTHashtable, they *would* be part of the type -- so it only
226 : // makes sense to assign in cases where they match.
227 3 : MOZ_RELEASE_ASSERT(mOps == aOther.mOps);
228 3 : MOZ_RELEASE_ASSERT(mEntrySize == aOther.mEntrySize);
229 :
230 : // Move non-const pieces over.
231 3 : mHashShift = Move(aOther.mHashShift);
232 3 : mEntryCount = Move(aOther.mEntryCount);
233 3 : mRemovedCount = Move(aOther.mRemovedCount);
234 3 : mEntryStore = Move(aOther.mEntryStore);
235 : #ifdef DEBUG
236 3 : mChecker = Move(aOther.mChecker);
237 : #endif
238 :
239 : // Clear up |aOther| so its destruction will be a no-op.
240 : {
241 : #ifdef DEBUG
242 6 : AutoDestructorOp op(mChecker);
243 : #endif
244 3 : aOther.mEntryStore.Set(nullptr);
245 : }
246 :
247 3 : return *this;
248 : }
249 :
250 : PLDHashNumber
251 495325 : PLDHashTable::Hash1(PLDHashNumber aHash0)
252 : {
253 495325 : return aHash0 >> mHashShift;
254 : }
255 :
256 : void
257 146186 : PLDHashTable::Hash2(PLDHashNumber aHash0,
258 : size_t& aHash2Out, size_t& aSizeMaskOut)
259 : {
260 146186 : size_t sizeLog2 = kHashBits - mHashShift;
261 146186 : size_t sizeMask = (PLDHashNumber(1) << sizeLog2) - 1;
262 146186 : aSizeMaskOut = sizeMask;
263 :
264 : // The incoming aHash0 always has the low bit unset (since we leave it
265 : // free for the collision flag), and should have reasonably random
266 : // data in the other 31 bits. We used the high bits of aHash0 for
267 : // Hash1, so we use the low bits here. If the table size is large,
268 : // the bits we use may overlap, but that's still more random than
269 : // filling with 0s.
270 : //
271 : // Double hashing needs the second hash code to be relatively prime to table
272 : // size, so we simply make hash2 odd.
273 : //
274 : // This also conveniently covers up the fact that we have the low bit
275 : // unset since aHash0 has the low bit unset.
276 146186 : aHash2Out = (aHash0 & sizeMask) | 1;
277 146186 : }
278 :
279 : // Reserve mKeyHash 0 for free entries and 1 for removed-entry sentinels. Note
280 : // that a removed-entry sentinel need be stored only if the removed entry had
281 : // a colliding entry added after it. Therefore we can use 1 as the collision
282 : // flag in addition to the removed-entry sentinel value. Multiplicative hash
283 : // uses the high order bits of mKeyHash, so this least-significant reservation
284 : // should not hurt the hash function's effectiveness much.
285 :
286 : // Match an entry's mKeyHash against an unstored one computed from a key.
287 : /* static */ bool
288 505357 : PLDHashTable::MatchEntryKeyhash(PLDHashEntryHdr* aEntry, PLDHashNumber aKeyHash)
289 : {
290 505357 : return (aEntry->mKeyHash & ~kCollisionFlag) == aKeyHash;
291 : }
292 :
293 : // Compute the address of the indexed entry in table.
294 : PLDHashEntryHdr*
295 785600 : PLDHashTable::AddressEntry(size_t aIndex)
296 : {
297 : return reinterpret_cast<PLDHashEntryHdr*>(
298 785600 : mEntryStore.Get() + aIndex * mEntrySize);
299 : }
300 :
301 11159 : PLDHashTable::~PLDHashTable()
302 : {
303 : #ifdef DEBUG
304 6893 : AutoDestructorOp op(mChecker);
305 : #endif
306 :
307 5580 : if (!mEntryStore.Get()) {
308 4266 : return;
309 : }
310 :
311 : // Clear any remaining live entries.
312 1314 : char* entryAddr = mEntryStore.Get();
313 1314 : char* entryLimit = entryAddr + Capacity() * mEntrySize;
314 36642 : while (entryAddr < entryLimit) {
315 17664 : PLDHashEntryHdr* entry = (PLDHashEntryHdr*)entryAddr;
316 17664 : if (EntryIsLive(entry)) {
317 4819 : mOps->clearEntry(this, entry);
318 : }
319 17664 : entryAddr += mEntrySize;
320 : }
321 :
322 : // Entry storage is freed last, by ~EntryStore().
323 5580 : }
324 :
325 : void
326 771 : PLDHashTable::ClearAndPrepareForLength(uint32_t aLength)
327 : {
328 : // Get these values before the destructor clobbers them.
329 771 : const PLDHashTableOps* ops = mOps;
330 771 : uint32_t entrySize = mEntrySize;
331 :
332 771 : this->~PLDHashTable();
333 771 : new (KnownNotNull, this) PLDHashTable(ops, entrySize, aLength);
334 771 : }
335 :
336 : void
337 770 : PLDHashTable::Clear()
338 : {
339 770 : ClearAndPrepareForLength(kDefaultInitialLength);
340 770 : }
341 :
342 : // If |Reason| is |ForAdd|, the return value is always non-null and it may be
343 : // a previously-removed entry. If |Reason| is |ForSearchOrRemove|, the return
344 : // value is null on a miss, and will never be a previously-removed entry on a
345 : // hit. This distinction is a bit grotty but this function is hot enough that
346 : // these differences are worthwhile.
347 : template <PLDHashTable::SearchReason Reason>
348 : PLDHashEntryHdr* NS_FASTCALL
349 423052 : PLDHashTable::SearchTable(const void* aKey, PLDHashNumber aKeyHash)
350 : {
351 423052 : MOZ_ASSERT(mEntryStore.Get());
352 423044 : NS_ASSERTION(!(aKeyHash & kCollisionFlag),
353 : "!(aKeyHash & kCollisionFlag)");
354 :
355 : // Compute the primary hash address.
356 423044 : PLDHashNumber hash1 = Hash1(aKeyHash);
357 423044 : PLDHashEntryHdr* entry = AddressEntry(hash1);
358 :
359 : // Miss: return space for a new entry.
360 423042 : if (EntryIsFree(entry)) {
361 111018 : return (Reason == ForAdd) ? entry : nullptr;
362 : }
363 :
364 : // Hit: return entry.
365 312013 : PLDHashMatchEntry matchEntry = mOps->matchEntry;
366 491282 : if (MatchEntryKeyhash(entry, aKeyHash) &&
367 179270 : matchEntry(entry, aKey)) {
368 179264 : return entry;
369 : }
370 :
371 : // Collision: double hash.
372 : PLDHashNumber hash2;
373 : size_t sizeMask;
374 132754 : Hash2(aKeyHash, hash2, sizeMask);
375 :
376 : // Save the first removed entry pointer so Add() can recycle it. (Only used
377 : // if Reason==ForAdd.)
378 132751 : PLDHashEntryHdr* firstRemoved = nullptr;
379 :
380 : for (;;) {
381 272747 : if (Reason == ForAdd && !firstRemoved) {
382 131534 : if (MOZ_UNLIKELY(EntryIsRemoved(entry))) {
383 1694 : firstRemoved = entry;
384 : } else {
385 129840 : entry->mKeyHash |= kCollisionFlag;
386 : }
387 : }
388 :
389 272253 : hash1 -= hash2;
390 272253 : hash1 &= sizeMask;
391 :
392 272253 : entry = AddressEntry(hash1);
393 272254 : if (EntryIsFree(entry)) {
394 : return (Reason == ForAdd) ? (firstRemoved ? firstRemoved : entry)
395 78887 : : nullptr;
396 : }
397 :
398 247242 : if (MatchEntryKeyhash(entry, aKeyHash) &&
399 53872 : matchEntry(entry, aKey)) {
400 53872 : return entry;
401 : }
402 : }
403 :
404 : // NOTREACHED
405 : return nullptr;
406 : }
407 :
408 : // This is a copy of SearchTable(), used by ChangeTable(), hardcoded to
409 : // 1. assume |Reason| is |ForAdd|,
410 : // 2. assume that |aKey| will never match an existing entry, and
411 : // 3. assume that no entries have been removed from the current table
412 : // structure.
413 : // Avoiding the need for |aKey| means we can avoid needing a way to map entries
414 : // to keys, which means callers can use complex key types more easily.
415 : MOZ_ALWAYS_INLINE PLDHashEntryHdr*
416 72296 : PLDHashTable::FindFreeEntry(PLDHashNumber aKeyHash)
417 : {
418 72296 : MOZ_ASSERT(mEntryStore.Get());
419 72296 : NS_ASSERTION(!(aKeyHash & kCollisionFlag),
420 : "!(aKeyHash & kCollisionFlag)");
421 :
422 : // Compute the primary hash address.
423 72296 : PLDHashNumber hash1 = Hash1(aKeyHash);
424 72296 : PLDHashEntryHdr* entry = AddressEntry(hash1);
425 :
426 : // Miss: return space for a new entry.
427 72296 : if (EntryIsFree(entry)) {
428 58863 : return entry;
429 : }
430 :
431 : // Collision: double hash.
432 : PLDHashNumber hash2;
433 : size_t sizeMask;
434 13433 : Hash2(aKeyHash, hash2, sizeMask);
435 :
436 4613 : for (;;) {
437 18046 : NS_ASSERTION(!EntryIsRemoved(entry),
438 : "!EntryIsRemoved(entry)");
439 18046 : entry->mKeyHash |= kCollisionFlag;
440 :
441 18046 : hash1 -= hash2;
442 18046 : hash1 &= sizeMask;
443 :
444 18046 : entry = AddressEntry(hash1);
445 18046 : if (EntryIsFree(entry)) {
446 13433 : return entry;
447 : }
448 : }
449 :
450 : // NOTREACHED
451 : }
452 :
453 : bool
454 1393 : PLDHashTable::ChangeTable(int32_t aDeltaLog2)
455 : {
456 1393 : MOZ_ASSERT(mEntryStore.Get());
457 :
458 : // Look, but don't touch, until we succeed in getting new entry store.
459 1393 : int32_t oldLog2 = kHashBits - mHashShift;
460 1393 : int32_t newLog2 = oldLog2 + aDeltaLog2;
461 1393 : uint32_t newCapacity = 1u << newLog2;
462 1393 : if (newCapacity > kMaxCapacity) {
463 0 : return false;
464 : }
465 :
466 : uint32_t nbytes;
467 1393 : if (!SizeOfEntryStore(newCapacity, mEntrySize, &nbytes)) {
468 0 : return false; // overflowed
469 : }
470 :
471 1393 : char* newEntryStore = (char*)malloc(nbytes);
472 1393 : if (!newEntryStore) {
473 0 : return false;
474 : }
475 :
476 : // We can't fail from here on, so update table parameters.
477 1393 : mHashShift = kHashBits - newLog2;
478 1393 : mRemovedCount = 0;
479 :
480 : // Assign the new entry store to table.
481 1393 : memset(newEntryStore, 0, nbytes);
482 : char* oldEntryStore;
483 : char* oldEntryAddr;
484 1393 : oldEntryAddr = oldEntryStore = mEntryStore.Get();
485 1393 : mEntryStore.Set(newEntryStore);
486 1393 : PLDHashMoveEntry moveEntry = mOps->moveEntry;
487 :
488 : // Copy only live entries, leaving removed ones behind.
489 1393 : uint32_t oldCapacity = 1u << oldLog2;
490 98937 : for (uint32_t i = 0; i < oldCapacity; ++i) {
491 97544 : PLDHashEntryHdr* oldEntry = (PLDHashEntryHdr*)oldEntryAddr;
492 97544 : if (EntryIsLive(oldEntry)) {
493 72296 : oldEntry->mKeyHash &= ~kCollisionFlag;
494 72296 : PLDHashEntryHdr* newEntry = FindFreeEntry(oldEntry->mKeyHash);
495 72296 : NS_ASSERTION(EntryIsFree(newEntry), "EntryIsFree(newEntry)");
496 72296 : moveEntry(this, oldEntry, newEntry);
497 72296 : newEntry->mKeyHash = oldEntry->mKeyHash;
498 : }
499 97544 : oldEntryAddr += mEntrySize;
500 : }
501 :
502 1393 : free(oldEntryStore);
503 1393 : return true;
504 : }
505 :
506 : MOZ_ALWAYS_INLINE PLDHashNumber
507 423045 : PLDHashTable::ComputeKeyHash(const void* aKey)
508 : {
509 423045 : MOZ_ASSERT(mEntryStore.Get());
510 :
511 423042 : PLDHashNumber keyHash = mOps->hashKey(aKey);
512 423042 : keyHash *= kGoldenRatio;
513 :
514 : // Avoid 0 and 1 hash codes, they indicate free and removed entries.
515 423042 : if (keyHash < 2) {
516 9469 : keyHash -= 2;
517 : }
518 423042 : keyHash &= ~kCollisionFlag;
519 :
520 423042 : return keyHash;
521 : }
522 :
523 : PLDHashEntryHdr*
524 239441 : PLDHashTable::Search(const void* aKey)
525 : {
526 : #ifdef DEBUG
527 478877 : AutoReadOp op(mChecker);
528 : #endif
529 :
530 239453 : PLDHashEntryHdr* entry = mEntryStore.Get()
531 239453 : ? SearchTable<ForSearchOrRemove>(aKey,
532 : ComputeKeyHash(aKey))
533 239436 : : nullptr;
534 478890 : return entry;
535 : }
536 :
537 : PLDHashEntryHdr*
538 200036 : PLDHashTable::Add(const void* aKey, const mozilla::fallible_t&)
539 : {
540 : #ifdef DEBUG
541 400071 : AutoWriteOp op(mChecker);
542 : #endif
543 :
544 : // Allocate the entry storage if it hasn't already been allocated.
545 200036 : if (!mEntryStore.Get()) {
546 : uint32_t nbytes;
547 : // We already checked this in the constructor, so it must still be true.
548 3442 : MOZ_RELEASE_ASSERT(SizeOfEntryStore(CapacityFromHashShift(), mEntrySize,
549 : &nbytes));
550 3442 : mEntryStore.Set((char*)malloc(nbytes));
551 3442 : if (!mEntryStore.Get()) {
552 0 : return nullptr;
553 : }
554 3442 : memset(mEntryStore.Get(), 0, nbytes);
555 : }
556 :
557 : // If alpha is >= .75, grow or compress the table. If aKey is already in the
558 : // table, we may grow once more than necessary, but only if we are on the
559 : // edge of being overloaded.
560 200036 : uint32_t capacity = Capacity();
561 200036 : if (mEntryCount + mRemovedCount >= MaxLoad(capacity)) {
562 : // Compress if a quarter or more of all entries are removed.
563 : int deltaLog2;
564 1346 : if (mRemovedCount >= capacity >> 2) {
565 0 : deltaLog2 = 0;
566 : } else {
567 1346 : deltaLog2 = 1;
568 : }
569 :
570 : // Grow or compress the table. If ChangeTable() fails, allow overloading up
571 : // to the secondary max. Once we hit the secondary max, return null.
572 1346 : if (!ChangeTable(deltaLog2) &&
573 0 : mEntryCount + mRemovedCount >= MaxLoadOnGrowthFailure(capacity)) {
574 0 : return nullptr;
575 : }
576 : }
577 :
578 : // Look for entry after possibly growing, so we don't have to add it,
579 : // then skip it while growing the table and re-add it after.
580 200036 : PLDHashNumber keyHash = ComputeKeyHash(aKey);
581 200036 : PLDHashEntryHdr* entry = SearchTable<ForAdd>(aKey, keyHash);
582 200036 : if (!EntryIsLive(entry)) {
583 : // Initialize the entry, indicating that it's no longer free.
584 113636 : if (EntryIsRemoved(entry)) {
585 1677 : mRemovedCount--;
586 1677 : keyHash |= kCollisionFlag;
587 : }
588 113636 : if (mOps->initEntry) {
589 86578 : mOps->initEntry(entry, aKey);
590 : }
591 113635 : entry->mKeyHash = keyHash;
592 113635 : mEntryCount++;
593 : }
594 :
595 200035 : return entry;
596 : }
597 :
598 : PLDHashEntryHdr*
599 82329 : PLDHashTable::Add(const void* aKey)
600 : {
601 82329 : PLDHashEntryHdr* entry = Add(aKey, fallible);
602 82329 : if (!entry) {
603 0 : if (!mEntryStore.Get()) {
604 : // We OOM'd while allocating the initial entry storage.
605 : uint32_t nbytes;
606 0 : (void) SizeOfEntryStore(CapacityFromHashShift(), mEntrySize, &nbytes);
607 0 : NS_ABORT_OOM(nbytes);
608 : } else {
609 : // We failed to resize the existing entry storage, either due to OOM or
610 : // because we exceeded the maximum table capacity or size; report it as
611 : // an OOM. The multiplication by 2 gets us the size we tried to allocate,
612 : // which is double the current size.
613 0 : NS_ABORT_OOM(2 * EntrySize() * EntryCount());
614 : }
615 : }
616 82329 : return entry;
617 : }
618 :
619 : void
620 9311 : PLDHashTable::Remove(const void* aKey)
621 : {
622 : #ifdef DEBUG
623 18622 : AutoWriteOp op(mChecker);
624 : #endif
625 :
626 9311 : PLDHashEntryHdr* entry = mEntryStore.Get()
627 9311 : ? SearchTable<ForSearchOrRemove>(aKey,
628 : ComputeKeyHash(aKey))
629 9311 : : nullptr;
630 9311 : if (entry) {
631 9118 : RawRemove(entry);
632 9118 : ShrinkIfAppropriate();
633 : }
634 9311 : }
635 :
636 : void
637 1912 : PLDHashTable::RemoveEntry(PLDHashEntryHdr* aEntry)
638 : {
639 : #ifdef DEBUG
640 3824 : AutoWriteOp op(mChecker);
641 : #endif
642 :
643 1912 : RawRemove(aEntry);
644 1912 : ShrinkIfAppropriate();
645 1912 : }
646 :
647 : void
648 11181 : PLDHashTable::RawRemove(PLDHashEntryHdr* aEntry)
649 : {
650 : // Unfortunately, we can only do weak checking here. That's because
651 : // RawRemove() can be called legitimately while an Enumerate() call is
652 : // active, which doesn't fit well into how Checker's mState variable works.
653 11181 : MOZ_ASSERT(mChecker.IsWritable());
654 :
655 11181 : MOZ_ASSERT(mEntryStore.Get());
656 :
657 11181 : MOZ_ASSERT(EntryIsLive(aEntry), "EntryIsLive(aEntry)");
658 :
659 : // Load keyHash first in case clearEntry() goofs it.
660 11181 : PLDHashNumber keyHash = aEntry->mKeyHash;
661 11181 : mOps->clearEntry(this, aEntry);
662 11181 : if (keyHash & kCollisionFlag) {
663 2709 : MarkEntryRemoved(aEntry);
664 2709 : mRemovedCount++;
665 : } else {
666 8472 : MarkEntryFree(aEntry);
667 : }
668 11181 : mEntryCount--;
669 11181 : }
670 :
671 : // Shrink or compress if a quarter or more of all entries are removed, or if the
672 : // table is underloaded according to the minimum alpha, and is not minimal-size
673 : // already.
674 : void
675 11096 : PLDHashTable::ShrinkIfAppropriate()
676 : {
677 11096 : uint32_t capacity = Capacity();
678 22226 : if (mRemovedCount >= capacity >> 2 ||
679 21044 : (capacity > kMinCapacity && mEntryCount <= MinLoad(capacity))) {
680 : uint32_t log2;
681 47 : BestCapacity(mEntryCount, &capacity, &log2);
682 :
683 47 : int32_t deltaLog2 = log2 - (kHashBits - mHashShift);
684 47 : MOZ_ASSERT(deltaLog2 <= 0);
685 :
686 47 : (void) ChangeTable(deltaLog2);
687 : }
688 11096 : }
689 :
690 : size_t
691 174 : PLDHashTable::ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
692 : {
693 : #ifdef DEBUG
694 348 : AutoReadOp op(mChecker);
695 : #endif
696 :
697 348 : return aMallocSizeOf(mEntryStore.Get());
698 : }
699 :
700 : size_t
701 0 : PLDHashTable::ShallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
702 : {
703 0 : return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
704 : }
705 :
706 0 : PLDHashTable::Iterator::Iterator(Iterator&& aOther)
707 0 : : mTable(aOther.mTable)
708 0 : , mStart(aOther.mStart)
709 0 : , mLimit(aOther.mLimit)
710 0 : , mCurrent(aOther.mCurrent)
711 0 : , mNexts(aOther.mNexts)
712 0 : , mNextsLimit(aOther.mNextsLimit)
713 0 : , mHaveRemoved(aOther.mHaveRemoved)
714 : {
715 : // No need to change |mChecker| here.
716 0 : aOther.mTable = nullptr;
717 0 : aOther.mStart = nullptr;
718 0 : aOther.mLimit = nullptr;
719 0 : aOther.mCurrent = nullptr;
720 0 : aOther.mNexts = 0;
721 0 : aOther.mNextsLimit = 0;
722 0 : aOther.mHaveRemoved = false;
723 0 : }
724 :
725 4639 : PLDHashTable::Iterator::Iterator(PLDHashTable* aTable)
726 : : mTable(aTable)
727 4639 : , mStart(mTable->mEntryStore.Get())
728 4639 : , mLimit(mTable->mEntryStore.Get() + mTable->Capacity() * mTable->mEntrySize)
729 4639 : , mCurrent(mTable->mEntryStore.Get())
730 : , mNexts(0)
731 4639 : , mNextsLimit(mTable->EntryCount())
732 23195 : , mHaveRemoved(false)
733 : {
734 : #ifdef DEBUG
735 4639 : mTable->mChecker.StartReadOp();
736 : #endif
737 :
738 4639 : if (ChaosMode::isActive(ChaosFeature::HashTableIteration) &&
739 0 : mTable->Capacity() > 0) {
740 : // Start iterating at a random entry. It would be even more chaotic to
741 : // iterate in fully random order, but that's harder.
742 0 : mCurrent += ChaosMode::randomUint32LessThan(mTable->Capacity()) *
743 0 : mTable->mEntrySize;
744 : }
745 :
746 : // Advance to the first live entry, if there is one.
747 4639 : if (!Done()) {
748 17122 : while (IsOnNonLiveEntry()) {
749 7143 : MoveToNextEntry();
750 : }
751 : }
752 4639 : }
753 :
754 9278 : PLDHashTable::Iterator::~Iterator()
755 : {
756 4639 : if (mTable) {
757 4639 : if (mHaveRemoved) {
758 66 : mTable->ShrinkIfAppropriate();
759 : }
760 : #ifdef DEBUG
761 4639 : mTable->mChecker.EndReadOp();
762 : #endif
763 : }
764 4639 : }
765 :
766 : MOZ_ALWAYS_INLINE bool
767 197595 : PLDHashTable::Iterator::IsOnNonLiveEntry() const
768 : {
769 197595 : MOZ_ASSERT(!Done());
770 197595 : return !EntryIsLive(reinterpret_cast<PLDHashEntryHdr*>(mCurrent));
771 : }
772 :
773 : MOZ_ALWAYS_INLINE void
774 194759 : PLDHashTable::Iterator::MoveToNextEntry()
775 : {
776 194759 : mCurrent += mTable->mEntrySize;
777 194759 : if (mCurrent == mLimit) {
778 0 : mCurrent = mStart; // Wrap-around. Possible due to Chaos Mode.
779 : }
780 194759 : }
781 :
782 : void
783 123576 : PLDHashTable::Iterator::Next()
784 : {
785 123576 : MOZ_ASSERT(!Done());
786 :
787 123576 : mNexts++;
788 :
789 : // Advance to the next live entry, if there is one.
790 123576 : if (!Done()) {
791 187616 : do {
792 187616 : MoveToNextEntry();
793 : } while (IsOnNonLiveEntry());
794 : }
795 123576 : }
796 :
797 : void
798 148 : PLDHashTable::Iterator::Remove()
799 : {
800 : // This cast is needed for the same reason as the one in the destructor.
801 148 : mTable->RawRemove(Get());
802 148 : mHaveRemoved = true;
803 148 : }
804 :
805 : #ifdef DEBUG
806 : void
807 32 : PLDHashTable::MarkImmutable()
808 : {
809 32 : mChecker.SetNonWritable();
810 32 : }
811 : #endif
|
