/* * Copyright 2013 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef GrTMultiMap_DEFINED #define GrTMultiMap_DEFINED #include "GrTypes.h" #include "SkTDynamicHash.h" /** A set that contains pointers to instances of T. Instances can be looked up with key Key. * Multiple (possibly same) values can have the same key. */ template <typename T, typename Key, const Key& (GetKey)(const T&), uint32_t (Hash)(const Key&), bool (Equal)(const T&, const Key&)> class GrTMultiMap { struct ValueList { explicit ValueList(T* value) : fValue(value), fNext(NULL) {} static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); } static uint32_t ListHash(const Key& key) { return Hash(key); } static bool ListEqual(const ValueList& a, const Key& b) { return Equal(*a.fValue, b); } T* fValue; ValueList* fNext; }; public: GrTMultiMap() : fCount(0) {} ~GrTMultiMap() { SkASSERT(fCount == 0); SkASSERT(fHash.count() == 0); } void insert(const Key& key, T* value) { ValueList* list = fHash.find(key); if (NULL != list) { // The new ValueList entry is inserted as the second element in the // linked list, and it will contain the value of the first element. ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue)); newEntry->fNext = list->fNext; // The existing first ValueList entry is updated to contain the // inserted value. list->fNext = newEntry; list->fValue = value; } else { fHash.add(SkNEW_ARGS(ValueList, (value))); } ++fCount; } void remove(const Key& key, const T* value) { ValueList* list = fHash.find(key); // Since we expect the caller to be fully aware of what is stored, just // assert that the caller removes an existing value. SkASSERT(NULL != list); ValueList* prev = NULL; while (list->fValue != value) { prev = list; list = list->fNext; } if (NULL != list->fNext) { ValueList* next = list->fNext; list->fValue = next->fValue; list->fNext = next->fNext; SkDELETE(next); } else if (NULL != prev) { prev->fNext = NULL; SkDELETE(list); } else { fHash.remove(key); SkDELETE(list); } --fCount; } T* find(const Key& key) const { ValueList* list = fHash.find(key); if (NULL != list) { return list->fValue; } return NULL; } template<class FindPredicate> T* find(const Key& key, const FindPredicate f) { ValueList* list = fHash.find(key); while (NULL != list) { if (f(list->fValue)){ return list->fValue; } list = list->fNext; } return NULL; } int count() const { return fCount; } private: SkTDynamicHash<ValueList, Key, ValueList::ListGetKey, ValueList::ListHash, ValueList::ListEqual> fHash; int fCount; }; #endif