src/third_party/skia/src/core/SkTDynamicHash.h

   1 /*
   2  * Copyright 2013 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #ifndef SkTDynamicHash_DEFINED
   9 #define SkTDynamicHash_DEFINED
  10
  11 #include "SkMath.h"
  12 #include "SkTemplates.h"
  13 #include "SkTypes.h"
  14
  15 // Traits requires:
  16 //   static const Key& GetKey(const T&) { ... }
  17 //   static uint32_t Hash(const Key&) { ... }
  18 // We'll look on T for these by default, or you can pass a custom Traits type.
  19 template <typename T,
  20           typename Key,
  21           typename Traits = T,
  22           int kGrowPercent = 75>  // Larger -> more memory efficient, but slower.
  23 class SkTDynamicHash {
  24 public:
  25     SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) {
  26         SkASSERT(this->validate());
  27     }
  28
  29     ~SkTDynamicHash() {
  30         sk_free(fArray);
  31     }
  32
  33     class Iter {
  34     public:
  35         explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
  36             SkASSERT(hash);
  37             ++(*this);
  38         }
  39         bool done() const {
  40             SkASSERT(fCurrentIndex <= fHash->fCapacity);
  41             return fCurrentIndex == fHash->fCapacity;
  42         }
  43         T& operator*() const {
  44             SkASSERT(!this->done());
  45             return *this->current();
  46         }
  47         void operator++() {
  48             do {
  49                 fCurrentIndex++;
  50             } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
  51         }
  52
  53     private:
  54         T* current() const { return fHash->fArray[fCurrentIndex]; }
  55
  56         SkTDynamicHash* fHash;
  57         int fCurrentIndex;
  58     };
  59
  60     class ConstIter {
  61     public:
  62         explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
  63             SkASSERT(hash);
  64             ++(*this);
  65         }
  66         bool done() const {
  67             SkASSERT(fCurrentIndex <= fHash->fCapacity);
  68             return fCurrentIndex == fHash->fCapacity;
  69         }
  70         const T& operator*() const {
  71             SkASSERT(!this->done());
  72             return *this->current();
  73         }
  74         void operator++() {
  75             do {
  76                 fCurrentIndex++;
  77             } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
  78         }
  79
  80     private:
  81         const T* current() const { return fHash->fArray[fCurrentIndex]; }
  82
  83         const SkTDynamicHash* fHash;
  84         int fCurrentIndex;
  85     };
  86
  87     int count() const { return fCount; }
  88
  89     // Return the entry with this key if we have it, otherwise NULL.
  90     T* find(const Key& key) const {
  91         int index = this->firstIndex(key);
  92         for (int round = 0; round < fCapacity; round++) {
  93             SkASSERT(index >= 0 && index < fCapacity);
  94             T* candidate = fArray[index];
  95             if (Empty() == candidate) {
  96                 return NULL;
  97             }
  98             if (Deleted() != candidate && GetKey(*candidate) == key) {
  99                 return candidate;
 100             }
 101             index = this->nextIndex(index, round);
 102         }
 103         SkASSERT(fCapacity == 0);
 104         return NULL;
 105     }
 106
 107     // Add an entry with this key.  We require that no entry with newEntry's key is already present.
 108     void add(T* newEntry) {
 109         SkASSERT(NULL == this->find(GetKey(*newEntry)));
 110         this->maybeGrow();
 111         this->innerAdd(newEntry);
 112         SkASSERT(this->validate());
 113     }
 114
 115     // Remove the entry with this key.  We require that an entry with this key is present.
 116     void remove(const Key& key) {
 117         SkASSERT(this->find(key));
 118         this->innerRemove(key);
 119         SkASSERT(this->validate());
 120     }
 121
 122     void rewind() {
 123         if (fArray) {
 124             sk_bzero(fArray, sizeof(T*)* fCapacity);
 125         }
 126         fCount = 0;
 127         fDeleted = 0;
 128     }
 129
 130     void reset() {
 131         fCount = 0;
 132         fDeleted = 0;
 133         fCapacity = 0;
 134         sk_free(fArray);
 135         fArray = NULL;
 136     }
 137
 138 protected:
 139     // These methods are used by tests only.
 140
 141     int capacity() const { return fCapacity; }
 142
 143     // How many collisions do we go through before finding where this entry should be inserted?
 144     int countCollisions(const Key& key) const {
 145         int index = this->firstIndex(key);
 146         for (int round = 0; round < fCapacity; round++) {
 147             SkASSERT(index >= 0 && index < fCapacity);
 148             const T* candidate = fArray[index];
 149             if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
 150                 return round;
 151             }
 152             index = this->nextIndex(index, round);
 153         }
 154         SkASSERT(fCapacity == 0);
 155         return 0;
 156     }
 157
 158 private:
 159     // We have two special values to indicate an empty or deleted entry.
 160     static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
 161     static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
 162
 163     bool validate() const {
 164         #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
 165         static const int kLarge = 50;  // Arbitrary, tweak to suit your patience.
 166
 167         // O(1) checks, always done.
 168         // Is capacity sane?
 169         SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
 170
 171         // O(N) checks, skipped when very large.
 172         if (fCount < kLarge * kLarge) {
 173             // Are fCount and fDeleted correct, and are all elements findable?
 174             int count = 0, deleted = 0;
 175             for (int i = 0; i < fCapacity; i++) {
 176                 if (Deleted() == fArray[i]) {
 177                     deleted++;
 178                 } else if (Empty() != fArray[i]) {
 179                     count++;
 180                     SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
 181                 }
 182             }
 183             SKTDYNAMICHASH_CHECK(count == fCount);
 184             SKTDYNAMICHASH_CHECK(deleted == fDeleted);
 185         }
 186
 187         // O(N^2) checks, skipped when large.
 188         if (fCount < kLarge) {
 189             // Are all entries unique?
 190             for (int i = 0; i < fCapacity; i++) {
 191                 if (Empty() == fArray[i] || Deleted() == fArray[i]) {
 192                     continue;
 193                 }
 194                 for (int j = i+1; j < fCapacity; j++) {
 195                     if (Empty() == fArray[j] || Deleted() == fArray[j]) {
 196                         continue;
 197                     }
 198                     SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
 199                     SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
 200                 }
 201             }
 202         }
 203         #undef SKTDYNAMICHASH_CHECK
 204         return true;
 205     }
 206
 207     void innerAdd(T* newEntry) {
 208         const Key& key = GetKey(*newEntry);
 209         int index = this->firstIndex(key);
 210         for (int round = 0; round < fCapacity; round++) {
 211             SkASSERT(index >= 0 && index < fCapacity);
 212             const T* candidate = fArray[index];
 213             if (Empty() == candidate || Deleted() == candidate) {
 214                 if (Deleted() == candidate) {
 215                     fDeleted--;
 216                 }
 217                 fCount++;
 218                 fArray[index] = newEntry;
 219                 return;
 220             }
 221             index = this->nextIndex(index, round);
 222         }
 223         SkASSERT(fCapacity == 0);
 224     }
 225
 226     void innerRemove(const Key& key) {
 227         const int firstIndex = this->firstIndex(key);
 228         int index = firstIndex;
 229         for (int round = 0; round < fCapacity; round++) {
 230             SkASSERT(index >= 0 && index < fCapacity);
 231             const T* candidate = fArray[index];
 232             if (Deleted() != candidate && GetKey(*candidate) == key) {
 233                 fDeleted++;
 234                 fCount--;
 235                 fArray[index] = Deleted();
 236                 return;
 237             }
 238             index = this->nextIndex(index, round);
 239         }
 240         SkASSERT(fCapacity == 0);
 241     }
 242
 243     void maybeGrow() {
 244         if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
 245             this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
 246         }
 247     }
 248
 249     void resize(int newCapacity) {
 250         SkDEBUGCODE(int oldCount = fCount;)
 251         int oldCapacity = fCapacity;
 252         SkAutoTMalloc<T*> oldArray(fArray);
 253
 254         fCount = fDeleted = 0;
 255         fCapacity = newCapacity;
 256         fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
 257
 258         for (int i = 0; i < oldCapacity; i++) {
 259             T* entry = oldArray[i];
 260             if (Empty() != entry && Deleted() != entry) {
 261                 this->innerAdd(entry);
 262             }
 263         }
 264         SkASSERT(oldCount == fCount);
 265     }
 266
 267     // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
 268     uint32_t hashMask() const { return fCapacity - 1; }
 269
 270     int firstIndex(const Key& key) const {
 271         return Hash(key) & this->hashMask();
 272     }
 273
 274     // Given index at round N, what is the index to check at N+1?  round should start at 0.
 275     int nextIndex(int index, int round) const {
 276         // This will search a power-of-two array fully without repeating an index.
 277         return (index + round + 1) & this->hashMask();
 278     }
 279
 280     static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
 281     static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
 282
 283     int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
 284     int fDeleted;   // Number of Deleted() entries in fArray.
 285     int fCapacity;  // Number of entries in fArray.  Always a power of 2.
 286     T** fArray;
 287 };
 288
 289 #endif