1 /* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkTMultiMap_DEFINED 9 #define SkTMultiMap_DEFINED 10 11 #include "GrTypes.h" 12 #include "SkTDynamicHash.h" 13 14 /** A set that contains pointers to instances of T. Instances can be looked up with key Key. 15 * Multiple (possibly same) values can have the same key. 16 */ 17 template <typename T, 18 typename Key, 19 typename HashTraits=T> 20 class SkTMultiMap { 21 struct ValueList { 22 explicit ValueList(T* value) : fValue(value), fNext(nullptr) {} 23 24 static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); } 25 static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); } 26 T* fValue; 27 ValueList* fNext; 28 }; 29 public: 30 SkTMultiMap() : fCount(0) {} 31 32 ~SkTMultiMap() { 33 typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash); 34 for ( ; !iter.done(); ++iter) { 35 ValueList* next; 36 for (ValueList* cur = &(*iter); cur; cur = next) { 37 HashTraits::OnFree(cur->fValue); 38 next = cur->fNext; 39 delete cur; 40 } 41 } 42 } 43 44 void insert(const Key& key, T* value) { 45 ValueList* list = fHash.find(key); 46 if (list) { 47 // The new ValueList entry is inserted as the second element in the 48 // linked list, and it will contain the value of the first element. 49 ValueList* newEntry = new ValueList(list->fValue); 50 newEntry->fNext = list->fNext; 51 // The existing first ValueList entry is updated to contain the 52 // inserted value. 53 list->fNext = newEntry; 54 list->fValue = value; 55 } else { 56 fHash.add(new ValueList(value)); 57 } 58 59 ++fCount; 60 } 61 62 void remove(const Key& key, const T* value) { 63 ValueList* list = fHash.find(key); 64 // Since we expect the caller to be fully aware of what is stored, just 65 // assert that the caller removes an existing value. 66 SkASSERT(list); 67 ValueList* prev = nullptr; 68 while (list->fValue != value) { 69 prev = list; 70 list = list->fNext; 71 } 72 73 this->internalRemove(prev, list, key); 74 } 75 76 T* find(const Key& key) const { 77 ValueList* list = fHash.find(key); 78 if (list) { 79 return list->fValue; 80 } 81 return nullptr; 82 } 83 84 template<class FindPredicate> 85 T* find(const Key& key, const FindPredicate f) { 86 ValueList* list = fHash.find(key); 87 while (list) { 88 if (f(list->fValue)){ 89 return list->fValue; 90 } 91 list = list->fNext; 92 } 93 return nullptr; 94 } 95 96 template<class FindPredicate> 97 T* findAndRemove(const Key& key, const FindPredicate f) { 98 ValueList* list = fHash.find(key); 99 100 ValueList* prev = nullptr; 101 while (list) { 102 if (f(list->fValue)){ 103 T* value = list->fValue; 104 this->internalRemove(prev, list, key); 105 return value; 106 } 107 prev = list; 108 list = list->fNext; 109 } 110 return nullptr; 111 } 112 113 int count() const { return fCount; } 114 115 #ifdef SK_DEBUG 116 class ConstIter { 117 public: 118 explicit ConstIter(const SkTMultiMap* mmap) 119 : fIter(&(mmap->fHash)) 120 , fList(nullptr) { 121 if (!fIter.done()) { 122 fList = &(*fIter); 123 } 124 } 125 126 bool done() const { 127 return fIter.done(); 128 } 129 130 const T* operator*() { 131 SkASSERT(fList); 132 return fList->fValue; 133 } 134 135 void operator++() { 136 if (fList) { 137 fList = fList->fNext; 138 } 139 if (!fList) { 140 ++fIter; 141 if (!fIter.done()) { 142 fList = &(*fIter); 143 } 144 } 145 } 146 147 private: 148 typename SkTDynamicHash<ValueList, Key>::ConstIter fIter; 149 const ValueList* fList; 150 }; 151 152 bool has(const T* value, const Key& key) const { 153 for (ValueList* list = fHash.find(key); list; list = list->fNext) { 154 if (list->fValue == value) { 155 return true; 156 } 157 } 158 return false; 159 } 160 161 // This is not particularly fast and only used for validation, so debug only. 162 int countForKey(const Key& key) const { 163 int count = 0; 164 ValueList* list = fHash.find(key); 165 while (list) { 166 list = list->fNext; 167 ++count; 168 } 169 return count; 170 } 171 #endif 172 173 private: 174 SkTDynamicHash<ValueList, Key> fHash; 175 int fCount; 176 177 void internalRemove(ValueList* prev, ValueList* elem, const Key& key) { 178 if (elem->fNext) { 179 ValueList* next = elem->fNext; 180 elem->fValue = next->fValue; 181 elem->fNext = next->fNext; 182 delete next; 183 } else if (prev) { 184 prev->fNext = nullptr; 185 delete elem; 186 } else { 187 fHash.remove(key); 188 delete elem; 189 } 190 191 --fCount; 192 } 193 194 }; 195 196 #endif 197