The Tor Browser: comparison gfx/skia/trunk/src/gpu/GrTHashTable.h

--1:000000000000
+:302761ac988e
+/*
+* Copyright 2010 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#ifndef GrTHashTable_DEFINED
+#define GrTHashTable_DEFINED
+#include "GrTypes.h"
+#include "SkTDArray.h"
+/**
+*  Key needs
+*      static bool Equals(const Entry&, const Key&);
+*      static bool LessThan(const Entry&, const Key&);
+*      static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
+*      static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
+*      uint32_t getHash() const;
+*
+*  Allows duplicate key entries but on find you may get
+*  any of the duplicate entries returned.
+*/
+template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
+public:
+GrTHashTable() { this->clearHash(); }
+~GrTHashTable() {}
+int count() const { return fSorted.count(); }
+struct Any {
+// Return the first resource that matches the key.
+bool operator()(const T*) const { return true; }
+};
+T* find(const Key& key) const { return this->find(key, Any()); }
+template <typename Filter> T* find(const Key&, Filter filter) const;
+// return true if key was unique when inserted.
+bool insert(const Key&, T*);
+void remove(const Key&, const T*);
+void deleteAll();
+#ifdef SK_DEBUG
+void validate() const;
+bool contains(T*) const;
+#endif
+// testing
+const SkTDArray<T*>& getArray() const { return fSorted; }
+SkTDArray<T*>& getArray() { return fSorted; }
+private:
+void clearHash() { sk_bzero(fHash, sizeof(fHash)); }
+enum {
+kHashCount = 1 << kHashBits,
+kHashMask  = kHashCount - 1
+};
+static unsigned hash2Index(uint32_t hash) {
+hash ^= hash >> 16;
+if (kHashBits <= 8) {
+hash ^= hash >> 8;
+}
+return hash & kHashMask;
+}
+mutable T* fHash[kHashCount];
+SkTDArray<T*> fSorted;
+// search fSorted, and return the found index, or ~index of where it
+// should be inserted
+int searchArray(const Key&) const;
+};
+///////////////////////////////////////////////////////////////////////////////
+template <typename T, typename Key, size_t kHashBits>
+int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
+int count = fSorted.count();
+if (0 == count) {
+// we should insert it at 0
+return ~0;
+}
+const T* const* array = fSorted.begin();
+int high = count - 1;
+int low = 0;
+while (high > low) {
+int index = (low + high) >> 1;
+if (Key::LessThan(*array[index], key)) {
+low = index + 1;
+} else {
+high = index;
+}
+}
+// check if we found it
+if (Key::Equals(*array[high], key)) {
+// above search should have found the first occurrence if there
+// are multiple.
+SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
+return high;
+}
+// now return the ~ of where we should insert it
+if (Key::LessThan(*array[high], key)) {
+high += 1;
+}
+return ~high;
+}
+template <typename T, typename Key, size_t kHashBits>
+template <typename Filter>
+T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const {
+int hashIndex = hash2Index(key.getHash());
+T* elem = fHash[hashIndex];
+if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
+return elem;
+}
+// bsearch for the key in our sorted array
+int index = this->searchArray(key);
+if (index < 0) {
+return NULL;
+}
+const T* const* array = fSorted.begin();
+// above search should have found the first occurrence if there
+// are multiple.
+SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
+for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
+if (filter(fSorted[index])) {
+// update the hash
+fHash[hashIndex] = fSorted[index];
+return fSorted[index];
+}
+}
+return NULL;
+}
+template <typename T, typename Key, size_t kHashBits>
+bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
+int index = this->searchArray(key);
+bool first = index < 0;
+if (first) {
+// turn it into the actual index
+index = ~index;
+}
+// add it to our array
+*fSorted.insert(index) = elem;
+// update our hash table (overwrites any dupe's position in the hash)
+fHash[hash2Index(key.getHash())] = elem;
+return first;
+}
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
+int index = hash2Index(key.getHash());
+if (fHash[index] == elem) {
+fHash[index] = NULL;
+}
+// remove from our sorted array
+index = this->searchArray(key);
+SkASSERT(index >= 0);
+// if there are multiple matches searchArray will give us the first match
+// march forward until we find elem.
+while (elem != fSorted[index]) {
+++index;
+SkASSERT(index < fSorted.count());
+}
+SkASSERT(elem == fSorted[index]);
+fSorted.remove(index);
+}
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::deleteAll() {
+fSorted.deleteAll();
+this->clearHash();
+}
+#ifdef SK_DEBUG
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::validate() const {
+int count = fSorted.count();
+for (int i = 1; i < count; i++) {
+SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
+Key::Equals(*fSorted[i - 1], *fSorted[i]));
+}
+}
+template <typename T, typename Key, size_t kHashBits>
+bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
+int index = fSorted.find(elem);
+return index >= 0;
+}
+#endif
+#endif

The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/gpu/GrTHashTable.h

gfx/skia/trunk/src/gpu/GrTHashTable.h