The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/gpu/GrTMultiMap.h
gfx/skia/trunk/src/gpu/GrTMultiMap.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:243efb6c763d |
|---|---|
| 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 with 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.fValue); } | |
| 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 |
