OLD | NEW |
(Empty) | |
| 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 |
| 9 #ifndef GrTMultiMap_DEFINED |
| 10 #define GrTMultiMap_DEFINED |
| 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 w
ith key Key. |
| 16 * Multiple (possibly same) values can have the same key. |
| 17 */ |
| 18 template <typename T, |
| 19 typename Key, |
| 20 const Key& (GetKey)(const T&), |
| 21 uint32_t (Hash)(const Key&), |
| 22 bool (Equal)(const T&, const Key&)> |
| 23 class GrTMultiMap { |
| 24 struct ValueList { |
| 25 explicit ValueList(T* value) : fValue(value), fNext(NULL) {} |
| 26 |
| 27 static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fVal
ue); } |
| 28 static uint32_t ListHash(const Key& key) { return Hash(key); } |
| 29 static bool ListEqual(const ValueList& a, const Key& b) { |
| 30 return Equal(*a.fValue, b); |
| 31 } |
| 32 T* fValue; |
| 33 ValueList* fNext; |
| 34 }; |
| 35 public: |
| 36 GrTMultiMap() : fCount(0) {} |
| 37 |
| 38 ~GrTMultiMap() { |
| 39 SkASSERT(fCount == 0); |
| 40 SkASSERT(fHash.count() == 0); |
| 41 } |
| 42 |
| 43 void insert(const Key& key, T* value) { |
| 44 ValueList* list = fHash.find(key); |
| 45 if (NULL != list) { |
| 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. |
| 48 ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue)); |
| 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 { |
| 55 fHash.add(SkNEW_ARGS(ValueList, (value))); |
| 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. |
| 65 SkASSERT(NULL != list); |
| 66 ValueList* prev = NULL; |
| 67 while (list->fValue != value) { |
| 68 prev = list; |
| 69 list = list->fNext; |
| 70 } |
| 71 |
| 72 if (NULL != list->fNext) { |
| 73 ValueList* next = list->fNext; |
| 74 list->fValue = next->fValue; |
| 75 list->fNext = next->fNext; |
| 76 SkDELETE(next); |
| 77 } else if (NULL != prev) { |
| 78 prev->fNext = NULL; |
| 79 SkDELETE(list); |
| 80 } else { |
| 81 fHash.remove(key); |
| 82 SkDELETE(list); |
| 83 } |
| 84 |
| 85 --fCount; |
| 86 } |
| 87 |
| 88 T* find(const Key& key) const { |
| 89 ValueList* list = fHash.find(key); |
| 90 if (NULL != list) { |
| 91 return list->fValue; |
| 92 } |
| 93 return NULL; |
| 94 } |
| 95 |
| 96 template<class FindPredicate> |
| 97 T* find(const Key& key, const FindPredicate f) { |
| 98 ValueList* list = fHash.find(key); |
| 99 while (NULL != list) { |
| 100 if (f(list->fValue)){ |
| 101 return list->fValue; |
| 102 } |
| 103 list = list->fNext; |
| 104 } |
| 105 return NULL; |
| 106 } |
| 107 |
| 108 int count() const { return fCount; } |
| 109 |
| 110 private: |
| 111 SkTDynamicHash<ValueList, |
| 112 Key, |
| 113 ValueList::ListGetKey, |
| 114 ValueList::ListHash, |
| 115 ValueList::ListEqual> fHash; |
| 116 int fCount; |
| 117 }; |
| 118 |
| 119 #endif |
OLD | NEW |