1 /*
2  * Copyright 2013 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef SkTMultiMap_DEFINED
9 #define SkTMultiMap_DEFINED
10 
11 #include "GrTypes.h"
12 #include "SkTDynamicHash.h"
13 
14 /** A set that contains pointers to instances of T. Instances can be looked up with key Key.
15  * Multiple (possibly same) values can have the same key.
16  */
17 template <typename T,
18           typename Key,
19           typename HashTraits=T>
20 class SkTMultiMap {
21     struct ValueList {
22         explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
23 
24         static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
25         static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
26         T* fValue;
27         ValueList* fNext;
28     };
29 public:
30     SkTMultiMap() : fCount(0) {}
31 
32     ~SkTMultiMap() {
33         typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash);
34         for ( ; !iter.done(); ++iter) {
35             ValueList* next;
36             for (ValueList* cur = &(*iter); cur; cur = next) {
37                 HashTraits::OnFree(cur->fValue);
38                 next = cur->fNext;
39                 delete cur;
40             }
41         }
42     }
43 
44     void insert(const Key& key, T* value) {
45         ValueList* list = fHash.find(key);
46         if (list) {
47             // The new ValueList entry is inserted as the second element in the
48             // linked list, and it will contain the value of the first element.
49             ValueList* newEntry = new ValueList(list->fValue);
50             newEntry->fNext = list->fNext;
51             // The existing first ValueList entry is updated to contain the
52             // inserted value.
53             list->fNext = newEntry;
54             list->fValue = value;
55         } else {
56             fHash.add(new ValueList(value));
57         }
58 
59         ++fCount;
60     }
61 
62     void remove(const Key& key, const T* value) {
63         ValueList* list = fHash.find(key);
64         // Since we expect the caller to be fully aware of what is stored, just
65         // assert that the caller removes an existing value.
66         SkASSERT(list);
67         ValueList* prev = nullptr;
68         while (list->fValue != value) {
69             prev = list;
70             list = list->fNext;
71         }
72 
73         this->internalRemove(prev, list, key);
74     }
75 
76     T* find(const Key& key) const {
77         ValueList* list = fHash.find(key);
78         if (list) {
79             return list->fValue;
80         }
81         return nullptr;
82     }
83 
84     template<class FindPredicate>
85     T* find(const Key& key, const FindPredicate f) {
86         ValueList* list = fHash.find(key);
87         while (list) {
88             if (f(list->fValue)){
89                 return list->fValue;
90             }
91             list = list->fNext;
92         }
93         return nullptr;
94     }
95 
96     template<class FindPredicate>
97     T* findAndRemove(const Key& key, const FindPredicate f) {
98         ValueList* list = fHash.find(key);
99 
100         ValueList* prev = nullptr;
101         while (list) {
102             if (f(list->fValue)){
103                 T* value = list->fValue;
104                 this->internalRemove(prev, list, key);
105                 return value;
106             }
107             prev = list;
108             list = list->fNext;
109         }
110         return nullptr;
111     }
112 
113     int count() const { return fCount; }
114 
115 #ifdef SK_DEBUG
116     class ConstIter {
117     public:
118         explicit ConstIter(const SkTMultiMap* mmap)
119             : fIter(&(mmap->fHash))
120             , fList(nullptr) {
121             if (!fIter.done()) {
122                 fList = &(*fIter);
123             }
124         }
125 
126         bool done() const {
127             return fIter.done();
128         }
129 
130         const T* operator*() {
131             SkASSERT(fList);
132             return fList->fValue;
133         }
134 
135         void operator++() {
136             if (fList) {
137                 fList = fList->fNext;
138             }
139             if (!fList) {
140                 ++fIter;
141                 if (!fIter.done()) {
142                     fList = &(*fIter);
143                 }
144             }
145         }
146 
147     private:
148         typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
149         const ValueList* fList;
150     };
151 
152     bool has(const T* value, const Key& key) const {
153         for (ValueList* list = fHash.find(key); list; list = list->fNext) {
154             if (list->fValue == value) {
155                 return true;
156             }
157         }
158         return false;
159     }
160 
161     // This is not particularly fast and only used for validation, so debug only.
162     int countForKey(const Key& key) const {
163         int count = 0;
164         ValueList* list = fHash.find(key);
165         while (list) {
166             list = list->fNext;
167             ++count;
168         }
169         return count;
170     }
171 #endif
172 
173 private:
174     SkTDynamicHash<ValueList, Key> fHash;
175     int fCount;
176 
177     void internalRemove(ValueList* prev, ValueList* elem, const Key& key) {
178         if (elem->fNext) {
179             ValueList* next = elem->fNext;
180             elem->fValue = next->fValue;
181             elem->fNext = next->fNext;
182             delete next;
183         } else if (prev) {
184             prev->fNext = nullptr;
185             delete elem;
186         } else {
187             fHash.remove(key);
188             delete elem;
189         }
190 
191         --fCount;
192     }
193 
194 };
195 
196 #endif
197