commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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 | |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 8 | #ifndef SkTMultiMap_DEFINED |
| 9 | #define SkTMultiMap_DEFINED |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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, |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 19 | typename HashTraits=T> |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 20 | class SkTMultiMap { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 21 | struct ValueList { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 22 | explicit ValueList(T* value) : fValue(value), fNext(nullptr) {} |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 23 | |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 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); } |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 26 | T* fValue; |
| 27 | ValueList* fNext; |
| 28 | }; |
| 29 | public: |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 30 | SkTMultiMap() : fCount(0) {} |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 31 | |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 32 | ~SkTMultiMap() { |
Robert Phillips | 57aa367 | 2017-07-21 11:38:13 -0400 | [diff] [blame] | 33 | typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash); |
| 34 | for ( ; !iter.done(); ++iter) { |
| 35 | ValueList* next; |
| 36 | for (ValueList* cur = &(*iter); cur; cur = next) { |
Robert Phillips | f8e2502 | 2017-11-08 15:24:31 -0500 | [diff] [blame] | 37 | HashTraits::OnFree(cur->fValue); |
Robert Phillips | 57aa367 | 2017-07-21 11:38:13 -0400 | [diff] [blame] | 38 | next = cur->fNext; |
| 39 | delete cur; |
| 40 | } |
| 41 | } |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 42 | } |
| 43 | |
| 44 | void insert(const Key& key, T* value) { |
| 45 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 46 | if (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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. |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 49 | ValueList* newEntry = new ValueList(list->fValue); |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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 { |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 56 | fHash.add(new ValueList(value)); |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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. |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 66 | SkASSERT(list); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 67 | ValueList* prev = nullptr; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 68 | while (list->fValue != value) { |
| 69 | prev = list; |
| 70 | list = list->fNext; |
| 71 | } |
| 72 | |
Robert Phillips | f8e2502 | 2017-11-08 15:24:31 -0500 | [diff] [blame] | 73 | this->internalRemove(prev, list, key); |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 74 | } |
| 75 | |
| 76 | T* find(const Key& key) const { |
| 77 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 78 | if (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 79 | return list->fValue; |
| 80 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 81 | return nullptr; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 82 | } |
| 83 | |
| 84 | template<class FindPredicate> |
| 85 | T* find(const Key& key, const FindPredicate f) { |
| 86 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 87 | while (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 88 | if (f(list->fValue)){ |
| 89 | return list->fValue; |
| 90 | } |
| 91 | list = list->fNext; |
| 92 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 93 | return nullptr; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Robert Phillips | f8e2502 | 2017-11-08 15:24:31 -0500 | [diff] [blame] | 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 | |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 113 | int count() const { return fCount; } |
| 114 | |
bsalomon | 8b79d23 | 2014-11-10 10:19:06 -0800 | [diff] [blame] | 115 | #ifdef SK_DEBUG |
robertphillips | c4ed684 | 2016-05-24 14:17:12 -0700 | [diff] [blame] | 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 | |
bsalomon | 8b79d23 | 2014-11-10 10:19:06 -0800 | [diff] [blame] | 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 | |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 173 | private: |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 174 | SkTDynamicHash<ValueList, Key> fHash; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 175 | int fCount; |
Robert Phillips | f8e2502 | 2017-11-08 15:24:31 -0500 | [diff] [blame] | 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 | |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 194 | }; |
| 195 | |
| 196 | #endif |