1 2 /* 3 * Copyright 2013 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 #ifndef SkTMultiMap_DEFINED 10 #define SkTMultiMap_DEFINED 11 12 #include "GrTypes.h" 13 #include "SkTDynamicHash.h" 14 15 /** A set that contains pointers to instances of T. Instances can be looked up with key Key. 16 * Multiple (possibly same) values can have the same key. 17 */ 18 template <typename T, 19 typename Key, 20 typename HashTraits=T> 21 class SkTMultiMap { 22 struct ValueList { ValueListValueList23 explicit ValueList(T* value) : fValue(value), fNext(nullptr) {} 24 GetKeyValueList25 static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); } HashValueList26 static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); } 27 T* fValue; 28 ValueList* fNext; 29 }; 30 public: SkTMultiMap()31 SkTMultiMap() : fCount(0) {} 32 ~SkTMultiMap()33 ~SkTMultiMap() { 34 SkASSERT(fCount == 0); 35 SkASSERT(fHash.count() == 0); 36 } 37 insert(const Key & key,T * value)38 void insert(const Key& key, T* value) { 39 ValueList* list = fHash.find(key); 40 if (list) { 41 // The new ValueList entry is inserted as the second element in the 42 // linked list, and it will contain the value of the first element. 43 ValueList* newEntry = new ValueList(list->fValue); 44 newEntry->fNext = list->fNext; 45 // The existing first ValueList entry is updated to contain the 46 // inserted value. 47 list->fNext = newEntry; 48 list->fValue = value; 49 } else { 50 fHash.add(new ValueList(value)); 51 } 52 53 ++fCount; 54 } 55 remove(const Key & key,const T * value)56 void remove(const Key& key, const T* value) { 57 ValueList* list = fHash.find(key); 58 // Since we expect the caller to be fully aware of what is stored, just 59 // assert that the caller removes an existing value. 60 SkASSERT(list); 61 ValueList* prev = nullptr; 62 while (list->fValue != value) { 63 prev = list; 64 list = list->fNext; 65 } 66 67 if (list->fNext) { 68 ValueList* next = list->fNext; 69 list->fValue = next->fValue; 70 list->fNext = next->fNext; 71 delete next; 72 } else if (prev) { 73 prev->fNext = nullptr; 74 delete list; 75 } else { 76 fHash.remove(key); 77 delete list; 78 } 79 80 --fCount; 81 } 82 find(const Key & key)83 T* find(const Key& key) const { 84 ValueList* list = fHash.find(key); 85 if (list) { 86 return list->fValue; 87 } 88 return nullptr; 89 } 90 91 template<class FindPredicate> find(const Key & key,const FindPredicate f)92 T* find(const Key& key, const FindPredicate f) { 93 ValueList* list = fHash.find(key); 94 while (list) { 95 if (f(list->fValue)){ 96 return list->fValue; 97 } 98 list = list->fNext; 99 } 100 return nullptr; 101 } 102 count()103 int count() const { return fCount; } 104 105 #ifdef SK_DEBUG 106 // This is not particularly fast and only used for validation, so debug only. countForKey(const Key & key)107 int countForKey(const Key& key) const { 108 int count = 0; 109 ValueList* list = fHash.find(key); 110 while (list) { 111 list = list->fNext; 112 ++count; 113 } 114 return count; 115 } 116 #endif 117 118 private: 119 SkTDynamicHash<ValueList, Key> fHash; 120 int fCount; 121 }; 122 123 #endif 124