1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrTHashTable.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,210 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2010 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +
1.14 +#ifndef GrTHashTable_DEFINED
1.15 +#define GrTHashTable_DEFINED
1.16 +
1.17 +#include "GrTypes.h"
1.18 +#include "SkTDArray.h"
1.19 +
1.20 +/**
1.21 + * Key needs
1.22 + * static bool Equals(const Entry&, const Key&);
1.23 + * static bool LessThan(const Entry&, const Key&);
1.24 + * static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
1.25 + * static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
1.26 + * uint32_t getHash() const;
1.27 + *
1.28 + * Allows duplicate key entries but on find you may get
1.29 + * any of the duplicate entries returned.
1.30 + */
1.31 +template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
1.32 +public:
1.33 + GrTHashTable() { this->clearHash(); }
1.34 + ~GrTHashTable() {}
1.35 +
1.36 + int count() const { return fSorted.count(); }
1.37 +
1.38 + struct Any {
1.39 + // Return the first resource that matches the key.
1.40 + bool operator()(const T*) const { return true; }
1.41 + };
1.42 +
1.43 + T* find(const Key& key) const { return this->find(key, Any()); }
1.44 + template <typename Filter> T* find(const Key&, Filter filter) const;
1.45 +
1.46 + // return true if key was unique when inserted.
1.47 + bool insert(const Key&, T*);
1.48 + void remove(const Key&, const T*);
1.49 +
1.50 + void deleteAll();
1.51 +
1.52 +#ifdef SK_DEBUG
1.53 + void validate() const;
1.54 + bool contains(T*) const;
1.55 +#endif
1.56 +
1.57 + // testing
1.58 + const SkTDArray<T*>& getArray() const { return fSorted; }
1.59 + SkTDArray<T*>& getArray() { return fSorted; }
1.60 +private:
1.61 + void clearHash() { sk_bzero(fHash, sizeof(fHash)); }
1.62 +
1.63 + enum {
1.64 + kHashCount = 1 << kHashBits,
1.65 + kHashMask = kHashCount - 1
1.66 + };
1.67 + static unsigned hash2Index(uint32_t hash) {
1.68 + hash ^= hash >> 16;
1.69 + if (kHashBits <= 8) {
1.70 + hash ^= hash >> 8;
1.71 + }
1.72 + return hash & kHashMask;
1.73 + }
1.74 +
1.75 + mutable T* fHash[kHashCount];
1.76 + SkTDArray<T*> fSorted;
1.77 +
1.78 + // search fSorted, and return the found index, or ~index of where it
1.79 + // should be inserted
1.80 + int searchArray(const Key&) const;
1.81 +};
1.82 +
1.83 +///////////////////////////////////////////////////////////////////////////////
1.84 +
1.85 +template <typename T, typename Key, size_t kHashBits>
1.86 +int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
1.87 + int count = fSorted.count();
1.88 + if (0 == count) {
1.89 + // we should insert it at 0
1.90 + return ~0;
1.91 + }
1.92 +
1.93 + const T* const* array = fSorted.begin();
1.94 + int high = count - 1;
1.95 + int low = 0;
1.96 + while (high > low) {
1.97 + int index = (low + high) >> 1;
1.98 + if (Key::LessThan(*array[index], key)) {
1.99 + low = index + 1;
1.100 + } else {
1.101 + high = index;
1.102 + }
1.103 + }
1.104 +
1.105 + // check if we found it
1.106 + if (Key::Equals(*array[high], key)) {
1.107 + // above search should have found the first occurrence if there
1.108 + // are multiple.
1.109 + SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
1.110 + return high;
1.111 + }
1.112 +
1.113 + // now return the ~ of where we should insert it
1.114 + if (Key::LessThan(*array[high], key)) {
1.115 + high += 1;
1.116 + }
1.117 + return ~high;
1.118 +}
1.119 +
1.120 +template <typename T, typename Key, size_t kHashBits>
1.121 +template <typename Filter>
1.122 +T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const {
1.123 +
1.124 + int hashIndex = hash2Index(key.getHash());
1.125 + T* elem = fHash[hashIndex];
1.126 +
1.127 + if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
1.128 + return elem;
1.129 + }
1.130 +
1.131 + // bsearch for the key in our sorted array
1.132 + int index = this->searchArray(key);
1.133 + if (index < 0) {
1.134 + return NULL;
1.135 + }
1.136 +
1.137 + const T* const* array = fSorted.begin();
1.138 +
1.139 + // above search should have found the first occurrence if there
1.140 + // are multiple.
1.141 + SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
1.142 +
1.143 + for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
1.144 + if (filter(fSorted[index])) {
1.145 + // update the hash
1.146 + fHash[hashIndex] = fSorted[index];
1.147 + return fSorted[index];
1.148 + }
1.149 + }
1.150 +
1.151 + return NULL;
1.152 +}
1.153 +
1.154 +template <typename T, typename Key, size_t kHashBits>
1.155 +bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
1.156 + int index = this->searchArray(key);
1.157 + bool first = index < 0;
1.158 + if (first) {
1.159 + // turn it into the actual index
1.160 + index = ~index;
1.161 + }
1.162 + // add it to our array
1.163 + *fSorted.insert(index) = elem;
1.164 + // update our hash table (overwrites any dupe's position in the hash)
1.165 + fHash[hash2Index(key.getHash())] = elem;
1.166 + return first;
1.167 +}
1.168 +
1.169 +template <typename T, typename Key, size_t kHashBits>
1.170 +void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
1.171 + int index = hash2Index(key.getHash());
1.172 + if (fHash[index] == elem) {
1.173 + fHash[index] = NULL;
1.174 + }
1.175 +
1.176 + // remove from our sorted array
1.177 + index = this->searchArray(key);
1.178 + SkASSERT(index >= 0);
1.179 + // if there are multiple matches searchArray will give us the first match
1.180 + // march forward until we find elem.
1.181 + while (elem != fSorted[index]) {
1.182 + ++index;
1.183 + SkASSERT(index < fSorted.count());
1.184 + }
1.185 + SkASSERT(elem == fSorted[index]);
1.186 + fSorted.remove(index);
1.187 +}
1.188 +
1.189 +template <typename T, typename Key, size_t kHashBits>
1.190 +void GrTHashTable<T, Key, kHashBits>::deleteAll() {
1.191 + fSorted.deleteAll();
1.192 + this->clearHash();
1.193 +}
1.194 +
1.195 +#ifdef SK_DEBUG
1.196 +template <typename T, typename Key, size_t kHashBits>
1.197 +void GrTHashTable<T, Key, kHashBits>::validate() const {
1.198 + int count = fSorted.count();
1.199 + for (int i = 1; i < count; i++) {
1.200 + SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
1.201 + Key::Equals(*fSorted[i - 1], *fSorted[i]));
1.202 + }
1.203 +}
1.204 +
1.205 +template <typename T, typename Key, size_t kHashBits>
1.206 +bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
1.207 + int index = fSorted.find(elem);
1.208 + return index >= 0;
1.209 +}
1.210 +
1.211 +#endif
1.212 +
1.213 +#endif
