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 "include/gpu/GrTypes.h"
12#include "src/core/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 */
17template <typename T,
18 typename Key,
19 typename HashTraits=T>
20class 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 };
29public:
30 SkTMultiMap() : fCount(0) {}
31
32 ~SkTMultiMap() {
33 fHash.foreach([&](ValueList* vl) {
34 ValueList* next;
35 for (ValueList* it = vl; it; it = next) {
36 HashTraits::OnFree(it->fValue);
37 next = it->fNext;
38 delete it;
39 }
40 });
41 }
42
43 void insert(const Key& key, T* value) {
44 ValueList* list = fHash.find(key);
45 if (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 = new 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(new ValueList(value));
56 }
57
58 ++fCount;
59 }
60
61 void remove(const Key& key, const T* value) {
62 ValueList* list = fHash.find(key);
63 // Temporarily making this safe for remove entries not in the map because of
64 // crbug.com/877915.
65#if 0
66 // Since we expect the caller to be fully aware of what is stored, just
67 // assert that the caller removes an existing value.
68 SkASSERT(list);
69 ValueList* prev = nullptr;
70 while (list->fValue != value) {
71 prev = list;
72 list = list->fNext;
73 }
74 this->internalRemove(prev, list, key);
75#else
76 ValueList* prev = nullptr;
77 while (list && list->fValue != value) {
78 prev = list;
79 list = list->fNext;
80 }
81 // Crash in Debug since it'd be great to detect a repro of 877915.
82 SkASSERT(list);
83 if (list) {
84 this->internalRemove(prev, list, key);
85 }
86#endif
87 }
88
89 T* find(const Key& key) const {
90 ValueList* list = fHash.find(key);
91 if (list) {
92 return list->fValue;
93 }
94 return nullptr;
95 }
96
97 template<class FindPredicate>
98 T* find(const Key& key, const FindPredicate f) {
99 ValueList* list = fHash.find(key);
100 while (list) {
101 if (f(list->fValue)){
102 return list->fValue;
103 }
104 list = list->fNext;
105 }
106 return nullptr;
107 }
108
109 template<class FindPredicate>
110 T* findAndRemove(const Key& key, const FindPredicate f) {
111 ValueList* list = fHash.find(key);
112
113 ValueList* prev = nullptr;
114 while (list) {
115 if (f(list->fValue)){
116 T* value = list->fValue;
117 this->internalRemove(prev, list, key);
118 return value;
119 }
120 prev = list;
121 list = list->fNext;
122 }
123 return nullptr;
124 }
125
126 int count() const { return fCount; }
127
128#ifdef SK_DEBUG
129 template <typename Fn> // f(T) or f(const T&)
130 void foreach(Fn&& fn) const {
131 fHash.foreach([&](const ValueList& vl) {
132 for (const ValueList* it = &vl; it; it = it->fNext) {
133 fn(*it->fValue);
134 }
135 });
136 }
137
138 bool has(const T* value, const Key& key) const {
139 for (ValueList* list = fHash.find(key); list; list = list->fNext) {
140 if (list->fValue == value) {
141 return true;
142 }
143 }
144 return false;
145 }
146
147 // This is not particularly fast and only used for validation, so debug only.
148 int countForKey(const Key& key) const {
149 int count = 0;
150 ValueList* list = fHash.find(key);
151 while (list) {
152 list = list->fNext;
153 ++count;
154 }
155 return count;
156 }
157#endif
158
159private:
160 SkTDynamicHash<ValueList, Key> fHash;
161 int fCount;
162
163 void internalRemove(ValueList* prev, ValueList* elem, const Key& key) {
164 if (elem->fNext) {
165 ValueList* next = elem->fNext;
166 elem->fValue = next->fValue;
167 elem->fNext = next->fNext;
168 delete next;
169 } else if (prev) {
170 prev->fNext = nullptr;
171 delete elem;
172 } else {
173 fHash.remove(key);
174 delete elem;
175 }
176
177 --fCount;
178 }
179
180};
181
182#endif
183