123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298 |
- /*
- * Copyright 2013 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SkTDynamicHash_DEFINED
- #define SkTDynamicHash_DEFINED
- #include "include/core/SkMath.h"
- #include "include/core/SkTypes.h"
- #include "include/private/SkTemplates.h"
- // Traits requires:
- // static const Key& GetKey(const T&) { ... }
- // static uint32_t Hash(const Key&) { ... }
- // We'll look on T for these by default, or you can pass a custom Traits type.
- template <typename T,
- typename Key,
- typename Traits = T,
- int kGrowPercent = 75> // Larger -> more memory efficient, but slower.
- class SkTDynamicHash {
- public:
- SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
- SkASSERT(this->validate());
- }
- ~SkTDynamicHash() {
- sk_free(fArray);
- }
- class Iter {
- public:
- explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
- SkASSERT(hash);
- ++(*this);
- }
- bool done() const {
- SkASSERT(fCurrentIndex <= fHash->fCapacity);
- return fCurrentIndex == fHash->fCapacity;
- }
- T& operator*() const {
- SkASSERT(!this->done());
- return *this->current();
- }
- void operator++() {
- do {
- fCurrentIndex++;
- } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
- }
- private:
- T* current() const { return fHash->fArray[fCurrentIndex]; }
- SkTDynamicHash* fHash;
- int fCurrentIndex;
- };
- class ConstIter {
- public:
- explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
- SkASSERT(hash);
- ++(*this);
- }
- bool done() const {
- SkASSERT(fCurrentIndex <= fHash->fCapacity);
- return fCurrentIndex == fHash->fCapacity;
- }
- const T& operator*() const {
- SkASSERT(!this->done());
- return *this->current();
- }
- void operator++() {
- do {
- fCurrentIndex++;
- } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
- }
- private:
- const T* current() const { return fHash->fArray[fCurrentIndex]; }
- const SkTDynamicHash* fHash;
- int fCurrentIndex;
- };
- int count() const { return fCount; }
- // Return the entry with this key if we have it, otherwise nullptr.
- T* find(const Key& key) const {
- int index = this->firstIndex(key);
- for (int round = 0; round < fCapacity; round++) {
- SkASSERT(index >= 0 && index < fCapacity);
- T* candidate = fArray[index];
- if (Empty() == candidate) {
- return nullptr;
- }
- if (Deleted() != candidate && GetKey(*candidate) == key) {
- return candidate;
- }
- index = this->nextIndex(index, round);
- }
- SkASSERT(fCapacity == 0);
- return nullptr;
- }
- // Add an entry with this key. We require that no entry with newEntry's key is already present.
- void add(T* newEntry) {
- SkASSERT(nullptr == this->find(GetKey(*newEntry)));
- this->maybeGrow();
- this->innerAdd(newEntry);
- SkASSERT(this->validate());
- }
- // Remove the entry with this key. We require that an entry with this key is present.
- void remove(const Key& key) {
- SkASSERT(this->find(key));
- this->innerRemove(key);
- SkASSERT(this->validate());
- }
- void rewind() {
- if (fArray) {
- sk_bzero(fArray, sizeof(T*)* fCapacity);
- }
- fCount = 0;
- fDeleted = 0;
- }
- void reset() {
- fCount = 0;
- fDeleted = 0;
- fCapacity = 0;
- sk_free(fArray);
- fArray = nullptr;
- }
- protected:
- // These methods are used by tests only.
- int capacity() const { return fCapacity; }
- // How many collisions do we go through before finding where this entry should be inserted?
- int countCollisions(const Key& key) const {
- int index = this->firstIndex(key);
- for (int round = 0; round < fCapacity; round++) {
- SkASSERT(index >= 0 && index < fCapacity);
- const T* candidate = fArray[index];
- if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
- return round;
- }
- index = this->nextIndex(index, round);
- }
- SkASSERT(fCapacity == 0);
- return 0;
- }
- private:
- // We have two special values to indicate an empty or deleted entry.
- static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr
- static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer.
- bool validate() const {
- #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false
- static const int kLarge = 50; // Arbitrary, tweak to suit your patience.
- // O(1) checks, always done.
- // Is capacity sane?
- SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
- // O(N) checks, skipped when very large.
- if (fCount < kLarge * kLarge) {
- // Are fCount and fDeleted correct, and are all elements findable?
- int count = 0, deleted = 0;
- for (int i = 0; i < fCapacity; i++) {
- if (Deleted() == fArray[i]) {
- deleted++;
- } else if (Empty() != fArray[i]) {
- count++;
- SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
- }
- }
- SKTDYNAMICHASH_CHECK(count == fCount);
- SKTDYNAMICHASH_CHECK(deleted == fDeleted);
- }
- // O(N^2) checks, skipped when large.
- if (fCount < kLarge) {
- // Are all entries unique?
- for (int i = 0; i < fCapacity; i++) {
- if (Empty() == fArray[i] || Deleted() == fArray[i]) {
- continue;
- }
- for (int j = i+1; j < fCapacity; j++) {
- if (Empty() == fArray[j] || Deleted() == fArray[j]) {
- continue;
- }
- SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
- SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
- }
- }
- }
- #undef SKTDYNAMICHASH_CHECK
- return true;
- }
- void innerAdd(T* newEntry) {
- const Key& key = GetKey(*newEntry);
- int index = this->firstIndex(key);
- for (int round = 0; round < fCapacity; round++) {
- SkASSERT(index >= 0 && index < fCapacity);
- const T* candidate = fArray[index];
- if (Empty() == candidate || Deleted() == candidate) {
- if (Deleted() == candidate) {
- fDeleted--;
- }
- fCount++;
- fArray[index] = newEntry;
- return;
- }
- index = this->nextIndex(index, round);
- }
- SkASSERT(fCapacity == 0);
- }
- void innerRemove(const Key& key) {
- const int firstIndex = this->firstIndex(key);
- int index = firstIndex;
- for (int round = 0; round < fCapacity; round++) {
- SkASSERT(index >= 0 && index < fCapacity);
- const T* candidate = fArray[index];
- if (Deleted() != candidate && GetKey(*candidate) == key) {
- fDeleted++;
- fCount--;
- fArray[index] = Deleted();
- return;
- }
- index = this->nextIndex(index, round);
- }
- SkASSERT(fCapacity == 0);
- }
- void maybeGrow() {
- if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
- auto newCapacity = fCapacity > 0 ? fCapacity : 4;
- // Only grow the storage when most non-empty entries are
- // in active use. Otherwise, just purge the tombstones.
- if (fCount > fDeleted) {
- newCapacity *= 2;
- }
- SkASSERT(newCapacity > fCount + 1);
- this->resize(newCapacity);
- }
- }
- void resize(int newCapacity) {
- SkDEBUGCODE(int oldCount = fCount;)
- int oldCapacity = fCapacity;
- SkAutoTMalloc<T*> oldArray(fArray);
- fCount = fDeleted = 0;
- fCapacity = newCapacity;
- fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
- for (int i = 0; i < oldCapacity; i++) {
- T* entry = oldArray[i];
- if (Empty() != entry && Deleted() != entry) {
- this->innerAdd(entry);
- }
- }
- SkASSERT(oldCount == fCount);
- }
- // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
- uint32_t hashMask() const { return fCapacity - 1; }
- int firstIndex(const Key& key) const {
- return Hash(key) & this->hashMask();
- }
- // Given index at round N, what is the index to check at N+1? round should start at 0.
- int nextIndex(int index, int round) const {
- // This will search a power-of-two array fully without repeating an index.
- return (index + round + 1) & this->hashMask();
- }
- static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
- static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
- int fCount; // Number of non Empty(), non Deleted() entries in fArray.
- int fDeleted; // Number of Deleted() entries in fArray.
- int fCapacity; // Number of entries in fArray. Always a power of 2.
- T** fArray;
- };
- #endif
|