OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2013 Google Inc. | 3 * Copyright 2013 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #ifndef SkTMultiMap_DEFINED | 9 #ifndef SkTMultiMap_DEFINED |
10 #define SkTMultiMap_DEFINED | 10 #define SkTMultiMap_DEFINED |
11 | 11 |
12 #include "GrTypes.h" | 12 #include "GrTypes.h" |
13 #include "SkTDynamicHash.h" | 13 #include "SkTDynamicHash.h" |
14 | 14 |
15 /** A set that contains pointers to instances of T. Instances can be looked up w
ith key Key. | 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. | 16 * Multiple (possibly same) values can have the same key. |
17 */ | 17 */ |
18 template <typename T, | 18 template <typename T, |
19 typename Key, | 19 typename Key, |
20 typename HashTraits=T> | 20 typename HashTraits=T> |
21 class SkTMultiMap { | 21 class SkTMultiMap { |
22 struct ValueList { | 22 struct ValueList { |
23 explicit ValueList(T* value) : fValue(value), fNext(NULL) {} | 23 explicit ValueList(T* value) : fValue(value), fNext(nullptr) {} |
24 | 24 |
25 static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey
(*e.fValue); } | 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); } | 26 static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); } |
27 T* fValue; | 27 T* fValue; |
28 ValueList* fNext; | 28 ValueList* fNext; |
29 }; | 29 }; |
30 public: | 30 public: |
31 SkTMultiMap() : fCount(0) {} | 31 SkTMultiMap() : fCount(0) {} |
32 | 32 |
33 ~SkTMultiMap() { | 33 ~SkTMultiMap() { |
(...skipping 17 matching lines...) Expand all Loading... |
51 } | 51 } |
52 | 52 |
53 ++fCount; | 53 ++fCount; |
54 } | 54 } |
55 | 55 |
56 void remove(const Key& key, const T* value) { | 56 void remove(const Key& key, const T* value) { |
57 ValueList* list = fHash.find(key); | 57 ValueList* list = fHash.find(key); |
58 // Since we expect the caller to be fully aware of what is stored, just | 58 // Since we expect the caller to be fully aware of what is stored, just |
59 // assert that the caller removes an existing value. | 59 // assert that the caller removes an existing value. |
60 SkASSERT(list); | 60 SkASSERT(list); |
61 ValueList* prev = NULL; | 61 ValueList* prev = nullptr; |
62 while (list->fValue != value) { | 62 while (list->fValue != value) { |
63 prev = list; | 63 prev = list; |
64 list = list->fNext; | 64 list = list->fNext; |
65 } | 65 } |
66 | 66 |
67 if (list->fNext) { | 67 if (list->fNext) { |
68 ValueList* next = list->fNext; | 68 ValueList* next = list->fNext; |
69 list->fValue = next->fValue; | 69 list->fValue = next->fValue; |
70 list->fNext = next->fNext; | 70 list->fNext = next->fNext; |
71 delete next; | 71 delete next; |
72 } else if (prev) { | 72 } else if (prev) { |
73 prev->fNext = NULL; | 73 prev->fNext = nullptr; |
74 delete list; | 74 delete list; |
75 } else { | 75 } else { |
76 fHash.remove(key); | 76 fHash.remove(key); |
77 delete list; | 77 delete list; |
78 } | 78 } |
79 | 79 |
80 --fCount; | 80 --fCount; |
81 } | 81 } |
82 | 82 |
83 T* find(const Key& key) const { | 83 T* find(const Key& key) const { |
84 ValueList* list = fHash.find(key); | 84 ValueList* list = fHash.find(key); |
85 if (list) { | 85 if (list) { |
86 return list->fValue; | 86 return list->fValue; |
87 } | 87 } |
88 return NULL; | 88 return nullptr; |
89 } | 89 } |
90 | 90 |
91 template<class FindPredicate> | 91 template<class FindPredicate> |
92 T* find(const Key& key, const FindPredicate f) { | 92 T* find(const Key& key, const FindPredicate f) { |
93 ValueList* list = fHash.find(key); | 93 ValueList* list = fHash.find(key); |
94 while (list) { | 94 while (list) { |
95 if (f(list->fValue)){ | 95 if (f(list->fValue)){ |
96 return list->fValue; | 96 return list->fValue; |
97 } | 97 } |
98 list = list->fNext; | 98 list = list->fNext; |
99 } | 99 } |
100 return NULL; | 100 return nullptr; |
101 } | 101 } |
102 | 102 |
103 int count() const { return fCount; } | 103 int count() const { return fCount; } |
104 | 104 |
105 #ifdef SK_DEBUG | 105 #ifdef SK_DEBUG |
106 // This is not particularly fast and only used for validation, so debug only
. | 106 // This is not particularly fast and only used for validation, so debug only
. |
107 int countForKey(const Key& key) const { | 107 int countForKey(const Key& key) const { |
108 int count = 0; | 108 int count = 0; |
109 ValueList* list = fHash.find(key); | 109 ValueList* list = fHash.find(key); |
110 while (list) { | 110 while (list) { |
111 list = list->fNext; | 111 list = list->fNext; |
112 ++count; | 112 ++count; |
113 } | 113 } |
114 return count; | 114 return count; |
115 } | 115 } |
116 #endif | 116 #endif |
117 | 117 |
118 private: | 118 private: |
119 SkTDynamicHash<ValueList, Key> fHash; | 119 SkTDynamicHash<ValueList, Key> fHash; |
120 int fCount; | 120 int fCount; |
121 }; | 121 }; |
122 | 122 |
123 #endif | 123 #endif |
OLD | NEW |