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