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