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 SkTMultiMap_DEFINED
10 #define SkTMultiMap_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           typename HashTraits=T>
21 class SkTMultiMap {
22     struct ValueList {
ValueListValueList23         explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
24 
GetKeyValueList25         static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
HashValueList26         static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
27         T* fValue;
28         ValueList* fNext;
29     };
30 public:
SkTMultiMap()31     SkTMultiMap() : fCount(0) {}
32 
~SkTMultiMap()33     ~SkTMultiMap() {
34         SkASSERT(fCount == 0);
35         SkASSERT(fHash.count() == 0);
36     }
37 
insert(const Key & key,T * value)38     void insert(const Key& key, T* value) {
39         ValueList* list = fHash.find(key);
40         if (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 
remove(const Key & key,const T * value)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(list);
61         ValueList* prev = NULL;
62         while (list->fValue != value) {
63             prev = list;
64             list = list->fNext;
65         }
66 
67         if (list->fNext) {
68             ValueList* next = list->fNext;
69             list->fValue = next->fValue;
70             list->fNext = next->fNext;
71             SkDELETE(next);
72         } else if (prev) {
73             prev->fNext = NULL;
74             SkDELETE(list);
75         } else {
76             fHash.remove(key);
77             SkDELETE(list);
78         }
79 
80         --fCount;
81     }
82 
find(const Key & key)83     T* find(const Key& key) const {
84         ValueList* list = fHash.find(key);
85         if (list) {
86             return list->fValue;
87         }
88         return NULL;
89     }
90 
91     template<class FindPredicate>
find(const Key & key,const FindPredicate f)92     T* find(const Key& key, const FindPredicate f) {
93         ValueList* list = fHash.find(key);
94         while (list) {
95             if (f(list->fValue)){
96                 return list->fValue;
97             }
98             list = list->fNext;
99         }
100         return NULL;
101     }
102 
count()103     int count() const { return fCount; }
104 
105 #ifdef SK_DEBUG
106     // This is not particularly fast and only used for validation, so debug only.
countForKey(const Key & key)107     int countForKey(const Key& key) const {
108         int count = 0;
109         ValueList* list = fHash.find(key);
110         while (list) {
111             list = list->fNext;
112             ++count;
113         }
114         return count;
115     }
116 #endif
117 
118 private:
119     SkTDynamicHash<ValueList, Key> fHash;
120     int fCount;
121 };
122 
123 #endif
124