1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkTDynamicHash.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,238 @@
1.4 +/*
1.5 + * Copyright 2013 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkTDynamicHash_DEFINED
1.12 +#define SkTDynamicHash_DEFINED
1.13 +
1.14 +#include "SkMath.h"
1.15 +#include "SkTemplates.h"
1.16 +#include "SkTypes.h"
1.17 +
1.18 +template <typename T,
1.19 + typename Key,
1.20 + const Key& (GetKey)(const T&),
1.21 + uint32_t (Hash)(const Key&),
1.22 + bool (Equal)(const T&, const Key&),
1.23 + int kGrowPercent = 75> // Larger -> more memory efficient, but slower.
1.24 +class SkTDynamicHash {
1.25 +public:
1.26 + SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) {
1.27 + SkASSERT(this->validate());
1.28 + }
1.29 +
1.30 + ~SkTDynamicHash() {
1.31 + sk_free(fArray);
1.32 + }
1.33 +
1.34 + class Iter {
1.35 + public:
1.36 + explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
1.37 + SkASSERT(hash);
1.38 + ++(*this);
1.39 + }
1.40 + bool done() const {
1.41 + SkASSERT(fCurrentIndex <= fHash->fCapacity);
1.42 + return fCurrentIndex == fHash->fCapacity;
1.43 + }
1.44 + T& operator*() const {
1.45 + SkASSERT(!this->done());
1.46 + return *this->current();
1.47 + }
1.48 + void operator++() {
1.49 + do {
1.50 + fCurrentIndex++;
1.51 + } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
1.52 + }
1.53 +
1.54 + private:
1.55 + T* current() const { return fHash->fArray[fCurrentIndex]; }
1.56 +
1.57 + SkTDynamicHash* fHash;
1.58 + int fCurrentIndex;
1.59 + };
1.60 +
1.61 + int count() const { return fCount; }
1.62 +
1.63 + // Return the entry with this key if we have it, otherwise NULL.
1.64 + T* find(const Key& key) const {
1.65 + int index = this->firstIndex(key);
1.66 + for (int round = 0; round < fCapacity; round++) {
1.67 + T* candidate = fArray[index];
1.68 + if (Empty() == candidate) {
1.69 + return NULL;
1.70 + }
1.71 + if (Deleted() != candidate && Equal(*candidate, key)) {
1.72 + return candidate;
1.73 + }
1.74 + index = this->nextIndex(index, round);
1.75 + }
1.76 + SkASSERT(fCapacity == 0);
1.77 + return NULL;
1.78 + }
1.79 +
1.80 + // Add an entry with this key. We require that no entry with newEntry's key is already present.
1.81 + void add(T* newEntry) {
1.82 + SkASSERT(NULL == this->find(GetKey(*newEntry)));
1.83 + this->maybeGrow();
1.84 + this->innerAdd(newEntry);
1.85 + SkASSERT(this->validate());
1.86 + }
1.87 +
1.88 + // Remove the entry with this key. We reqire that an entry with this key is present.
1.89 + void remove(const Key& key) {
1.90 + SkASSERT(NULL != this->find(key));
1.91 + this->innerRemove(key);
1.92 + SkASSERT(this->validate());
1.93 + }
1.94 +
1.95 +protected:
1.96 + // These methods are used by tests only.
1.97 +
1.98 + int capacity() const { return fCapacity; }
1.99 +
1.100 + // How many collisions do we go through before finding where this entry should be inserted?
1.101 + int countCollisions(const Key& key) const {
1.102 + int index = this->firstIndex(key);
1.103 + for (int round = 0; round < fCapacity; round++) {
1.104 + const T* candidate = fArray[index];
1.105 + if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
1.106 + return round;
1.107 + }
1.108 + index = this->nextIndex(index, round);
1.109 + }
1.110 + SkASSERT(fCapacity == 0);
1.111 + return 0;
1.112 + }
1.113 +
1.114 +private:
1.115 + // We have two special values to indicate an empty or deleted entry.
1.116 + static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL
1.117 + static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer.
1.118 +
1.119 + bool validate() const {
1.120 + #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
1.121 + static const int kLarge = 50; // Arbitrary, tweak to suit your patience.
1.122 +
1.123 + // O(1) checks, always done.
1.124 + // Is capacity sane?
1.125 + SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
1.126 +
1.127 + // O(N) checks, skipped when very large.
1.128 + if (fCount < kLarge * kLarge) {
1.129 + // Are fCount and fDeleted correct, and are all elements findable?
1.130 + int count = 0, deleted = 0;
1.131 + for (int i = 0; i < fCapacity; i++) {
1.132 + if (Deleted() == fArray[i]) {
1.133 + deleted++;
1.134 + } else if (Empty() != fArray[i]) {
1.135 + count++;
1.136 + SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])));
1.137 + }
1.138 + }
1.139 + SKTDYNAMICHASH_CHECK(count == fCount);
1.140 + SKTDYNAMICHASH_CHECK(deleted == fDeleted);
1.141 + }
1.142 +
1.143 + // O(N^2) checks, skipped when large.
1.144 + if (fCount < kLarge) {
1.145 + // Are all entries unique?
1.146 + for (int i = 0; i < fCapacity; i++) {
1.147 + if (Empty() == fArray[i] || Deleted() == fArray[i]) {
1.148 + continue;
1.149 + }
1.150 + for (int j = i+1; j < fCapacity; j++) {
1.151 + if (Empty() == fArray[j] || Deleted() == fArray[j]) {
1.152 + continue;
1.153 + }
1.154 + SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
1.155 + SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
1.156 + SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
1.157 + }
1.158 + }
1.159 + }
1.160 + #undef SKTDYNAMICHASH_CHECK
1.161 + return true;
1.162 + }
1.163 +
1.164 + void innerAdd(T* newEntry) {
1.165 + const Key& key = GetKey(*newEntry);
1.166 + int index = this->firstIndex(key);
1.167 + for (int round = 0; round < fCapacity; round++) {
1.168 + const T* candidate = fArray[index];
1.169 + if (Empty() == candidate || Deleted() == candidate) {
1.170 + if (Deleted() == candidate) {
1.171 + fDeleted--;
1.172 + }
1.173 + fCount++;
1.174 + fArray[index] = newEntry;
1.175 + return;
1.176 + }
1.177 + index = this->nextIndex(index, round);
1.178 + }
1.179 + SkASSERT(fCapacity == 0);
1.180 + }
1.181 +
1.182 + void innerRemove(const Key& key) {
1.183 + const int firstIndex = this->firstIndex(key);
1.184 + int index = firstIndex;
1.185 + for (int round = 0; round < fCapacity; round++) {
1.186 + const T* candidate = fArray[index];
1.187 + if (Deleted() != candidate && Equal(*candidate, key)) {
1.188 + fDeleted++;
1.189 + fCount--;
1.190 + fArray[index] = Deleted();
1.191 + return;
1.192 + }
1.193 + index = this->nextIndex(index, round);
1.194 + }
1.195 + SkASSERT(fCapacity == 0);
1.196 + }
1.197 +
1.198 + void maybeGrow() {
1.199 + if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
1.200 + this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
1.201 + }
1.202 + }
1.203 +
1.204 + void resize(int newCapacity) {
1.205 + SkDEBUGCODE(int oldCount = fCount;)
1.206 + int oldCapacity = fCapacity;
1.207 + SkAutoTMalloc<T*> oldArray(fArray);
1.208 +
1.209 + fCount = fDeleted = 0;
1.210 + fCapacity = newCapacity;
1.211 + fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
1.212 +
1.213 + for (int i = 0; i < oldCapacity; i++) {
1.214 + T* entry = oldArray[i];
1.215 + if (Empty() != entry && Deleted() != entry) {
1.216 + this->innerAdd(entry);
1.217 + }
1.218 + }
1.219 + SkASSERT(oldCount == fCount);
1.220 + }
1.221 +
1.222 + // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
1.223 + uint32_t hashMask() const { return fCapacity - 1; }
1.224 +
1.225 + int firstIndex(const Key& key) const {
1.226 + return Hash(key) & this->hashMask();
1.227 + }
1.228 +
1.229 + // Given index at round N, what is the index to check at N+1? round should start at 0.
1.230 + int nextIndex(int index, int round) const {
1.231 + // This will search a power-of-two array fully without repeating an index.
1.232 + return (index + round + 1) & this->hashMask();
1.233 + }
1.234 +
1.235 + int fCount; // Number of non Empty(), non Deleted() entries in fArray.
1.236 + int fDeleted; // Number of Deleted() entries in fArray.
1.237 + int fCapacity; // Number of entries in fArray. Always a power of 2.
1.238 + T** fArray;
1.239 +};
1.240 +
1.241 +#endif
