src/gpu/GrTHashTable.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 GrTHashTable_DEFINED
#define GrTHashTable_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