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 { ValueListValueList22 explicit ValueList(T* value) : fValue(value), fNext(nullptr) {} 23 GetKeyValueList24 static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); } HashValueList25 static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); } 26 T* fValue; 27 ValueList* fNext; 28 }; 29 public: SkTMultiMap()30 SkTMultiMap() : fCount(0) {} 31 ~SkTMultiMap()32 ~SkTMultiMap() { 33 SkASSERT(fCount == 0); 34 SkASSERT(fHash.count() == 0); 35 } 36 insert(const Key & key,T * value)37 void insert(const Key& key, T* value) { 38 ValueList* list = fHash.find(key); 39 if (list) { 40 // The new ValueList entry is inserted as the second element in the 41 // linked list, and it will contain the value of the first element. 42 ValueList* newEntry = new ValueList(list->fValue); 43 newEntry->fNext = list->fNext; 44 // The existing first ValueList entry is updated to contain the 45 // inserted value. 46 list->fNext = newEntry; 47 list->fValue = value; 48 } else { 49 fHash.add(new ValueList(value)); 50 } 51 52 ++fCount; 53 } 54 remove(const Key & key,const T * value)55 void remove(const Key& key, const T* value) { 56 ValueList* list = fHash.find(key); 57 // Since we expect the caller to be fully aware of what is stored, just 58 // assert that the caller removes an existing value. 59 SkASSERT(list); 60 ValueList* prev = nullptr; 61 while (list->fValue != value) { 62 prev = list; 63 list = list->fNext; 64 } 65 66 if (list->fNext) { 67 ValueList* next = list->fNext; 68 list->fValue = next->fValue; 69 list->fNext = next->fNext; 70 delete next; 71 } else if (prev) { 72 prev->fNext = nullptr; 73 delete list; 74 } else { 75 fHash.remove(key); 76 delete list; 77 } 78 79 --fCount; 80 } 81 find(const Key & key)82 T* find(const Key& key) const { 83 ValueList* list = fHash.find(key); 84 if (list) { 85 return list->fValue; 86 } 87 return nullptr; 88 } 89 90 template<class FindPredicate> find(const Key & key,const FindPredicate f)91 T* find(const Key& key, const FindPredicate f) { 92 ValueList* list = fHash.find(key); 93 while (list) { 94 if (f(list->fValue)){ 95 return list->fValue; 96 } 97 list = list->fNext; 98 } 99 return nullptr; 100 } 101 count()102 int count() const { return fCount; } 103 104 #ifdef SK_DEBUG 105 class ConstIter { 106 public: ConstIter(const SkTMultiMap * mmap)107 explicit ConstIter(const SkTMultiMap* mmap) 108 : fIter(&(mmap->fHash)) 109 , fList(nullptr) { 110 if (!fIter.done()) { 111 fList = &(*fIter); 112 } 113 } 114 done()115 bool done() const { 116 return fIter.done(); 117 } 118 119 const T* operator*() { 120 SkASSERT(fList); 121 return fList->fValue; 122 } 123 124 void operator++() { 125 if (fList) { 126 fList = fList->fNext; 127 } 128 if (!fList) { 129 ++fIter; 130 if (!fIter.done()) { 131 fList = &(*fIter); 132 } 133 } 134 } 135 136 private: 137 typename SkTDynamicHash<ValueList, Key>::ConstIter fIter; 138 const ValueList* fList; 139 }; 140 has(const T * value,const Key & key)141 bool has(const T* value, const Key& key) const { 142 for (ValueList* list = fHash.find(key); list; list = list->fNext) { 143 if (list->fValue == value) { 144 return true; 145 } 146 } 147 return false; 148 } 149 150 // This is not particularly fast and only used for validation, so debug only. countForKey(const Key & key)151 int countForKey(const Key& key) const { 152 int count = 0; 153 ValueList* list = fHash.find(key); 154 while (list) { 155 list = list->fNext; 156 ++count; 157 } 158 return count; 159 } 160 #endif 161 162 private: 163 SkTDynamicHash<ValueList, Key> fHash; 164 int fCount; 165 }; 166 167 #endif 168