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 */
18template <typename T,
19          typename Key,
20          typename HashTraits=T>
21class SkTMultiMap {
22    struct ValueList {
23        explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
24
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); }
27        T* fValue;
28        ValueList* fNext;
29    };
30public:
31    SkTMultiMap() : fCount(0) {}
32
33    ~SkTMultiMap() {
34        SkASSERT(fCount == 0);
35        SkASSERT(fHash.count() == 0);
36    }
37
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 = new 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(new ValueList(value));
51        }
52
53        ++fCount;
54    }
55
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 = nullptr;
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            delete next;
72        } else if (prev) {
73            prev->fNext = nullptr;
74            delete list;
75        } else {
76            fHash.remove(key);
77            delete list;
78        }
79
80        --fCount;
81    }
82
83    T* find(const Key& key) const {
84        ValueList* list = fHash.find(key);
85        if (list) {
86            return list->fValue;
87        }
88        return nullptr;
89    }
90
91    template<class FindPredicate>
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 nullptr;
101    }
102
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.
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
118private:
119    SkTDynamicHash<ValueList, Key> fHash;
120    int fCount;
121};
122
123#endif
124