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) { |
| 37 | next = cur->fNext; |
| 38 | delete cur; |
| 39 | } |
| 40 | } |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 41 | } |
| 42 | |
| 43 | void insert(const Key& key, T* value) { |
| 44 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 45 | if (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 46 | // The new ValueList entry is inserted as the second element in the |
| 47 | // linked list, and it will contain the value of the first element. |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 48 | ValueList* newEntry = new ValueList(list->fValue); |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 49 | newEntry->fNext = list->fNext; |
| 50 | // The existing first ValueList entry is updated to contain the |
| 51 | // inserted value. |
| 52 | list->fNext = newEntry; |
| 53 | list->fValue = value; |
| 54 | } else { |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 55 | fHash.add(new ValueList(value)); |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 56 | } |
| 57 | |
| 58 | ++fCount; |
| 59 | } |
| 60 | |
| 61 | void remove(const Key& key, const T* value) { |
| 62 | ValueList* list = fHash.find(key); |
| 63 | // Since we expect the caller to be fully aware of what is stored, just |
| 64 | // assert that the caller removes an existing value. |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 65 | SkASSERT(list); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 66 | ValueList* prev = nullptr; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 67 | while (list->fValue != value) { |
| 68 | prev = list; |
| 69 | list = list->fNext; |
| 70 | } |
| 71 | |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 72 | if (list->fNext) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 73 | ValueList* next = list->fNext; |
| 74 | list->fValue = next->fValue; |
| 75 | list->fNext = next->fNext; |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 76 | delete next; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 77 | } else if (prev) { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 78 | prev->fNext = nullptr; |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 79 | delete list; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 80 | } else { |
| 81 | fHash.remove(key); |
halcanary | 385fe4d | 2015-08-26 13:07:48 -0700 | [diff] [blame] | 82 | delete list; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 83 | } |
| 84 | |
| 85 | --fCount; |
| 86 | } |
| 87 | |
| 88 | T* find(const Key& key) const { |
| 89 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 90 | if (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 91 | return list->fValue; |
| 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 | |
| 96 | template<class FindPredicate> |
| 97 | T* find(const Key& key, const FindPredicate f) { |
| 98 | ValueList* list = fHash.find(key); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 99 | while (list) { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 100 | if (f(list->fValue)){ |
| 101 | return list->fValue; |
| 102 | } |
| 103 | list = list->fNext; |
| 104 | } |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 105 | return nullptr; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 106 | } |
| 107 | |
| 108 | int count() const { return fCount; } |
| 109 | |
bsalomon | 8b79d23 | 2014-11-10 10:19:06 -0800 | [diff] [blame] | 110 | #ifdef SK_DEBUG |
robertphillips | c4ed684 | 2016-05-24 14:17:12 -0700 | [diff] [blame] | 111 | class ConstIter { |
| 112 | public: |
| 113 | explicit ConstIter(const SkTMultiMap* mmap) |
| 114 | : fIter(&(mmap->fHash)) |
| 115 | , fList(nullptr) { |
| 116 | if (!fIter.done()) { |
| 117 | fList = &(*fIter); |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | bool done() const { |
| 122 | return fIter.done(); |
| 123 | } |
| 124 | |
| 125 | const T* operator*() { |
| 126 | SkASSERT(fList); |
| 127 | return fList->fValue; |
| 128 | } |
| 129 | |
| 130 | void operator++() { |
| 131 | if (fList) { |
| 132 | fList = fList->fNext; |
| 133 | } |
| 134 | if (!fList) { |
| 135 | ++fIter; |
| 136 | if (!fIter.done()) { |
| 137 | fList = &(*fIter); |
| 138 | } |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | private: |
| 143 | typename SkTDynamicHash<ValueList, Key>::ConstIter fIter; |
| 144 | const ValueList* fList; |
| 145 | }; |
| 146 | |
| 147 | bool has(const T* value, const Key& key) const { |
| 148 | for (ValueList* list = fHash.find(key); list; list = list->fNext) { |
| 149 | if (list->fValue == value) { |
| 150 | return true; |
| 151 | } |
| 152 | } |
| 153 | return false; |
| 154 | } |
| 155 | |
bsalomon | 8b79d23 | 2014-11-10 10:19:06 -0800 | [diff] [blame] | 156 | // This is not particularly fast and only used for validation, so debug only. |
| 157 | int countForKey(const Key& key) const { |
| 158 | int count = 0; |
| 159 | ValueList* list = fHash.find(key); |
| 160 | while (list) { |
| 161 | list = list->fNext; |
| 162 | ++count; |
| 163 | } |
| 164 | return count; |
| 165 | } |
| 166 | #endif |
| 167 | |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 168 | private: |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 169 | SkTDynamicHash<ValueList, Key> fHash; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 170 | int fCount; |
| 171 | }; |
| 172 | |
| 173 | #endif |