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