commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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 | |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 9 | #ifndef SkTMultiMap_DEFINED |
| 10 | #define SkTMultiMap_DEFINED |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 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, |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 20 | typename HashTraits=T> |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 21 | class SkTMultiMap { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 22 | struct ValueList { |
| 23 | explicit ValueList(T* value) : fValue(value), fNext(NULL) {} |
| 24 | |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 25 | static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); } |
| 26 | 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] | 27 | T* fValue; |
| 28 | ValueList* fNext; |
| 29 | }; |
| 30 | public: |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 31 | SkTMultiMap() : fCount(0) {} |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 32 | |
robertphillips | 7a037f4 | 2014-07-21 12:40:57 -0700 | [diff] [blame] | 33 | ~SkTMultiMap() { |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 34 | SkASSERT(fCount == 0); |
| 35 | SkASSERT(fHash.count() == 0); |
| 36 | } |
| 37 | |
| 38 | void insert(const Key& key, T* value) { |
| 39 | ValueList* list = fHash.find(key); |
| 40 | if (NULL != 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 = SkNEW_ARGS(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(SkNEW_ARGS(ValueList, (value))); |
| 51 | } |
| 52 | |
| 53 | ++fCount; |
| 54 | } |
| 55 | |
| 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(NULL != list); |
| 61 | ValueList* prev = NULL; |
| 62 | while (list->fValue != value) { |
| 63 | prev = list; |
| 64 | list = list->fNext; |
| 65 | } |
| 66 | |
| 67 | if (NULL != list->fNext) { |
| 68 | ValueList* next = list->fNext; |
| 69 | list->fValue = next->fValue; |
| 70 | list->fNext = next->fNext; |
| 71 | SkDELETE(next); |
| 72 | } else if (NULL != prev) { |
| 73 | prev->fNext = NULL; |
| 74 | SkDELETE(list); |
| 75 | } else { |
| 76 | fHash.remove(key); |
| 77 | SkDELETE(list); |
| 78 | } |
| 79 | |
| 80 | --fCount; |
| 81 | } |
| 82 | |
| 83 | T* find(const Key& key) const { |
| 84 | ValueList* list = fHash.find(key); |
| 85 | if (NULL != list) { |
| 86 | return list->fValue; |
| 87 | } |
| 88 | return NULL; |
| 89 | } |
| 90 | |
| 91 | template<class FindPredicate> |
| 92 | T* find(const Key& key, const FindPredicate f) { |
| 93 | ValueList* list = fHash.find(key); |
| 94 | while (NULL != list) { |
| 95 | if (f(list->fValue)){ |
| 96 | return list->fValue; |
| 97 | } |
| 98 | list = list->fNext; |
| 99 | } |
| 100 | return NULL; |
| 101 | } |
| 102 | |
| 103 | int count() const { return fCount; } |
| 104 | |
| 105 | private: |
commit-bot@chromium.org | 55bd940 | 2014-04-02 19:17:00 +0000 | [diff] [blame] | 106 | SkTDynamicHash<ValueList, Key> fHash; |
commit-bot@chromium.org | bd58feb | 2014-01-17 17:56:21 +0000 | [diff] [blame] | 107 | int fCount; |
| 108 | }; |
| 109 | |
| 110 | #endif |