gfx/skia/trunk/src/gpu/GrTMultiMap.h@6474c204b198 (annotated)
gfx/skia/trunk/src/gpu/GrTMultiMap.h
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
| michael@0 | 1 | |
| michael@0 | 2 | /* |
| michael@0 | 3 | * Copyright 2013 Google Inc. |
| michael@0 | 4 | * |
| michael@0 | 5 | * Use of this source code is governed by a BSD-style license that can be |
| michael@0 | 6 | * found in the LICENSE file. |
| michael@0 | 7 | */ |
| michael@0 | 8 | |
| michael@0 | 9 | #ifndef GrTMultiMap_DEFINED |
| michael@0 | 10 | #define GrTMultiMap_DEFINED |
| michael@0 | 11 | |
| michael@0 | 12 | #include "GrTypes.h" |
| michael@0 | 13 | #include "SkTDynamicHash.h" |
| michael@0 | 14 | |
| michael@0 | 15 | /** A set that contains pointers to instances of T. Instances can be looked up with key Key. |
| michael@0 | 16 | * Multiple (possibly same) values can have the same key. |
| michael@0 | 17 | */ |
| michael@0 | 18 | template <typename T, |
| michael@0 | 19 | typename Key, |
| michael@0 | 20 | const Key& (GetKey)(const T&), |
| michael@0 | 21 | uint32_t (Hash)(const Key&), |
| michael@0 | 22 | bool (Equal)(const T&, const Key&)> |
| michael@0 | 23 | class GrTMultiMap { |
| michael@0 | 24 | struct ValueList { |
| michael@0 | 25 | explicit ValueList(T* value) : fValue(value), fNext(NULL) {} |
| michael@0 | 26 | |
| michael@0 | 27 | static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); } |
| michael@0 | 28 | static uint32_t ListHash(const Key& key) { return Hash(key); } |
| michael@0 | 29 | static bool ListEqual(const ValueList& a, const Key& b) { |
| michael@0 | 30 | return Equal(*a.fValue, b); |
| michael@0 | 31 | } |
| michael@0 | 32 | T* fValue; |
| michael@0 | 33 | ValueList* fNext; |
| michael@0 | 34 | }; |
| michael@0 | 35 | public: |
| michael@0 | 36 | GrTMultiMap() : fCount(0) {} |
| michael@0 | 37 | |
| michael@0 | 38 | ~GrTMultiMap() { |
| michael@0 | 39 | SkASSERT(fCount == 0); |
| michael@0 | 40 | SkASSERT(fHash.count() == 0); |
| michael@0 | 41 | } |
| michael@0 | 42 | |
| michael@0 | 43 | void insert(const Key& key, T* value) { |
| michael@0 | 44 | ValueList* list = fHash.find(key); |
| michael@0 | 45 | if (NULL != list) { |
| michael@0 | 46 | // The new ValueList entry is inserted as the second element in the |
| michael@0 | 47 | // linked list, and it will contain the value of the first element. |
| michael@0 | 48 | ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue)); |
| michael@0 | 49 | newEntry->fNext = list->fNext; |
| michael@0 | 50 | // The existing first ValueList entry is updated to contain the |
| michael@0 | 51 | // inserted value. |
| michael@0 | 52 | list->fNext = newEntry; |
| michael@0 | 53 | list->fValue = value; |
| michael@0 | 54 | } else { |
| michael@0 | 55 | fHash.add(SkNEW_ARGS(ValueList, (value))); |
| michael@0 | 56 | } |
| michael@0 | 57 | |
| michael@0 | 58 | ++fCount; |
| michael@0 | 59 | } |
| michael@0 | 60 | |
| michael@0 | 61 | void remove(const Key& key, const T* value) { |
| michael@0 | 62 | ValueList* list = fHash.find(key); |
| michael@0 | 63 | // Since we expect the caller to be fully aware of what is stored, just |
| michael@0 | 64 | // assert that the caller removes an existing value. |
| michael@0 | 65 | SkASSERT(NULL != list); |
| michael@0 | 66 | ValueList* prev = NULL; |
| michael@0 | 67 | while (list->fValue != value) { |
| michael@0 | 68 | prev = list; |
| michael@0 | 69 | list = list->fNext; |
| michael@0 | 70 | } |
| michael@0 | 71 | |
| michael@0 | 72 | if (NULL != list->fNext) { |
| michael@0 | 73 | ValueList* next = list->fNext; |
| michael@0 | 74 | list->fValue = next->fValue; |
| michael@0 | 75 | list->fNext = next->fNext; |
| michael@0 | 76 | SkDELETE(next); |
| michael@0 | 77 | } else if (NULL != prev) { |
| michael@0 | 78 | prev->fNext = NULL; |
| michael@0 | 79 | SkDELETE(list); |
| michael@0 | 80 | } else { |
| michael@0 | 81 | fHash.remove(key); |
| michael@0 | 82 | SkDELETE(list); |
| michael@0 | 83 | } |
| michael@0 | 84 | |
| michael@0 | 85 | --fCount; |
| michael@0 | 86 | } |
| michael@0 | 87 | |
| michael@0 | 88 | T* find(const Key& key) const { |
| michael@0 | 89 | ValueList* list = fHash.find(key); |
| michael@0 | 90 | if (NULL != list) { |
| michael@0 | 91 | return list->fValue; |
| michael@0 | 92 | } |
| michael@0 | 93 | return NULL; |
| michael@0 | 94 | } |
| michael@0 | 95 | |
| michael@0 | 96 | template<class FindPredicate> |
| michael@0 | 97 | T* find(const Key& key, const FindPredicate f) { |
| michael@0 | 98 | ValueList* list = fHash.find(key); |
| michael@0 | 99 | while (NULL != list) { |
| michael@0 | 100 | if (f(list->fValue)){ |
| michael@0 | 101 | return list->fValue; |
| michael@0 | 102 | } |
| michael@0 | 103 | list = list->fNext; |
| michael@0 | 104 | } |
| michael@0 | 105 | return NULL; |
| michael@0 | 106 | } |
| michael@0 | 107 | |
| michael@0 | 108 | int count() const { return fCount; } |
| michael@0 | 109 | |
| michael@0 | 110 | private: |
| michael@0 | 111 | SkTDynamicHash<ValueList, |
| michael@0 | 112 | Key, |
| michael@0 | 113 | ValueList::ListGetKey, |
| michael@0 | 114 | ValueList::ListHash, |
| michael@0 | 115 | ValueList::ListEqual> fHash; |
| michael@0 | 116 | int fCount; |
| michael@0 | 117 | }; |
| michael@0 | 118 | |
| michael@0 | 119 | #endif |
