diff options
| author |  Florin Malita <fmalita@chromium.org> | 2017-03-10 11:51:07 -0500 |
|---|---|---|
| committer |  Skia Commit-Bot <skia-commit-bot@chromium.org> | 2017-03-10 17:28:04 +0000 |
| commit | 053730de732922ecee21be665af111ce671ce045 (patch) | |
| tree | a888069700f090ebe9d2b210d53e54e5efcfa2d2 | |
| parent | 566e53c7003920ff45c72498754060804b657c68 (diff) | |
Fix SkTHashTable dangling values
The element rearrange logic in SkTHashTable::remove() marks empty slots
as such, but does not reset their value.
When breaking out of the rearrange loop, we must also reset the last empty
slot value to avoid retaining unwanted copies.
Change-Id: I8ba2a25088c0aa5210277124e0917224cb295691
Reviewed-on: https://skia-review.googlesource.com/9533
Reviewed-by: Mike Klein <mtklein@chromium.org>
Reviewed-by: Ben Wagner <bungeman@google.com>
Commit-Queue: Florin Malita <fmalita@chromium.org>
| -rw-r--r-- | include/private/SkTHash.h | 9 | ||||
| -rw-r--r-- | tests/HashTest.cpp | 16 |
2 files changed, 21 insertions, 4 deletions
diff --git a/include/private/SkTHash.h b/include/private/SkTHash.h index 943129f8a9..2388905c38 100644 --- a/include/private/SkTHash.h +++ b/include/private/SkTHash.h @@ -95,7 +95,6 @@ public: for (;;) { Slot& emptySlot = fSlots[index]; int emptyIndex = index; - emptySlot.markEmpty(); int originalIndex; // Look for an element that can be moved into the empty slot. // If the empty slot is in between where an element landed, and its native slot, then @@ -106,7 +105,11 @@ public: do { index = this->next(index); Slot& s = fSlots[index]; - if (s.empty()) { return; } + if (s.empty()) { + // We're done shuffling elements around. Clear the last empty slot. + emptySlot = Slot(); + return; + } originalIndex = s.hash & (fCapacity - 1); } while ((index <= originalIndex && originalIndex < emptyIndex) || (originalIndex < emptyIndex && emptyIndex < index) @@ -205,8 +208,6 @@ private: bool empty() const { return this->hash == 0; } - void markEmpty() { this->hash = 0; } - T val; uint32_t hash; }; diff --git a/tests/HashTest.cpp b/tests/HashTest.cpp index 4a884e3b5b..667f8ea4c0 100644 --- a/tests/HashTest.cpp +++ b/tests/HashTest.cpp @@ -6,6 +6,7 @@ */ #include "SkChecksum.h" +#include "SkRefCnt.h" #include "SkString.h" #include "SkTHash.h" #include "Test.h" @@ -65,6 +66,21 @@ DEF_TEST(HashMap, r) { map.reset(); REPORTER_ASSERT(r, map.count() == 0); + + { + // Test that we don't leave dangling values in empty slots. + SkTHashMap<int, sk_sp<SkRefCnt>> refMap; + auto ref = sk_make_sp<SkRefCnt>(); + REPORTER_ASSERT(r, ref->unique()); + + refMap.set(0, ref); + REPORTER_ASSERT(r, refMap.count() == 1); + REPORTER_ASSERT(r, !ref->unique()); + + refMap.remove(0); + REPORTER_ASSERT(r, refMap.count() == 0); + REPORTER_ASSERT(r, ref->unique()); + } } DEF_TEST(HashSet, r) { |