GrTHashCache -> GrTHashTable

src/gpu/GrTHashCache.h

-
-/*
- * 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 GrTHashCache_DEFINED
-#define GrTHashCache_DEFINED
-
-#include "GrTypes.h"
-#include "SkTDArray.h"
-
-// GrTDefaultFindFunctor implements the default find behavior for
-// GrTHashTable (i.e., return the first resource that matches the
-// provided key)
-template <typename T> class GrTDefaultFindFunctor {
-public:
-    // always accept the first element examined
-    bool operator()(const T*) const { return true; }
-};
-
-/**
- *  Key needs
- *      static bool EQ(const Entry&, const HashKey&);
- *      static bool LT(const Entry&, const HashKey&);
- *      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() { sk_bzero(fHash, sizeof(fHash)); }
-    ~GrTHashTable() {}
-
-    int count() const { return fSorted.count(); }
-    T*  find(const Key&) const;
-    template <typename FindFuncType> T*  find(const Key&, const FindFuncType&) const;
-    // return true if key was unique when inserted.
-    bool insert(const Key&, T*);
-    void remove(const Key&, const T*);
-    T* removeAt(int index, uint32_t hash);
-    void removeAll();
-    void deleteAll();
-    void unrefAll();
-
-    /**
-     *  Return the index for the element, using a linear search.
-     */
-    int slowFindIndex(T* elem) const { return fSorted.find(elem); }
-
-#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:
-    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::LT(*array[index], key)) {
-            low = index + 1;
-        } else {
-            high = index;
-        }
-    }
-
-    // check if we found it
-    if (Key::EQ(*array[high], key)) {
-        // above search should have found the first occurrence if there
-        // are multiple.
-        SkASSERT(0 == high || Key::LT(*array[high - 1], key));
-        return high;
-    }
-
-    // now return the ~ of where we should insert it
-    if (Key::LT(*array[high], key)) {
-        high += 1;
-    }
-    return ~high;
-}
-
-template <typename T, typename Key, size_t kHashBits>
-T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const {
-    GrTDefaultFindFunctor<T> find;
-
-    return this->find(key, find);
-}
-
-template <typename T, typename Key, size_t kHashBits>
-template <typename FindFuncType>
-T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const {
-
-    int hashIndex = hash2Index(key.getHash());
-    T* elem = fHash[hashIndex];
-
-    if (NULL != elem && Key::EQ(*elem, key) && findFunc(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::LT(*array[index - 1], key));
-
-    for ( ; index < count() && Key::EQ(*array[index], key); ++index) {
-        if (findFunc(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>
-T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) {
-    int hashIndex = hash2Index(hash);
-    if (fHash[hashIndex] == fSorted[elemIndex]) {
-        fHash[hashIndex] = NULL;
-    }
-    // remove from our sorted array
-    T* elem = fSorted[elemIndex];
-    fSorted.remove(elemIndex);
-    return elem;
-}
-
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::removeAll() {
-    fSorted.reset();
-    sk_bzero(fHash, sizeof(fHash));
-}
-
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::deleteAll() {
-    fSorted.deleteAll();
-    sk_bzero(fHash, sizeof(fHash));
-}
-
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::unrefAll() {
-    fSorted.unrefAll();
-    sk_bzero(fHash, sizeof(fHash));
-}
-
-#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::LT(*fSorted[i - 1], *fSorted[i]) ||
-                 Key::EQ(*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