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 */
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        SkASSERT(fCount == 0);
34        SkASSERT(fHash.count() == 0);
35    }
36
37    void insert(const Key& key, T* value) {
38        ValueList* list = fHash.find(key);
39        if (list) {
40            // The new ValueList entry is inserted as the second element in the
41            // linked list, and it will contain the value of the first element.
42            ValueList* newEntry = new ValueList(list->fValue);
43            newEntry->fNext = list->fNext;
44            // The existing first ValueList entry is updated to contain the
45            // inserted value.
46            list->fNext = newEntry;
47            list->fValue = value;
48        } else {
49            fHash.add(new ValueList(value));
50        }
51
52        ++fCount;
53    }
54
55    void remove(const Key& key, const T* value) {
56        ValueList* list = fHash.find(key);
57        // Since we expect the caller to be fully aware of what is stored, just
58        // assert that the caller removes an existing value.
59        SkASSERT(list);
60        ValueList* prev = nullptr;
61        while (list->fValue != value) {
62            prev = list;
63            list = list->fNext;
64        }
65
66        if (list->fNext) {
67            ValueList* next = list->fNext;
68            list->fValue = next->fValue;
69            list->fNext = next->fNext;
70            delete next;
71        } else if (prev) {
72            prev->fNext = nullptr;
73            delete list;
74        } else {
75            fHash.remove(key);
76            delete list;
77        }
78
79        --fCount;
80    }
81
82    T* find(const Key& key) const {
83        ValueList* list = fHash.find(key);
84        if (list) {
85            return list->fValue;
86        }
87        return nullptr;
88    }
89
90    template<class FindPredicate>
91    T* find(const Key& key, const FindPredicate f) {
92        ValueList* list = fHash.find(key);
93        while (list) {
94            if (f(list->fValue)){
95                return list->fValue;
96            }
97            list = list->fNext;
98        }
99        return nullptr;
100    }
101
102    int count() const { return fCount; }
103
104#ifdef SK_DEBUG
105    class ConstIter {
106    public:
107        explicit ConstIter(const SkTMultiMap* mmap)
108            : fIter(&(mmap->fHash))
109            , fList(nullptr) {
110            if (!fIter.done()) {
111                fList = &(*fIter);
112            }
113        }
114
115        bool done() const {
116            return fIter.done();
117        }
118
119        const T* operator*() {
120            SkASSERT(fList);
121            return fList->fValue;
122        }
123
124        void operator++() {
125            if (fList) {
126                fList = fList->fNext;
127            }
128            if (!fList) {
129                ++fIter;
130                if (!fIter.done()) {
131                    fList = &(*fIter);
132                }
133            }
134        }
135
136    private:
137        typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
138        const ValueList* fList;
139    };
140
141    bool has(const T* value, const Key& key) const {
142        for (ValueList* list = fHash.find(key); list; list = list->fNext) {
143            if (list->fValue == value) {
144                return true;
145            }
146        }
147        return false;
148    }
149
150    // This is not particularly fast and only used for validation, so debug only.
151    int countForKey(const Key& key) const {
152        int count = 0;
153        ValueList* list = fHash.find(key);
154        while (list) {
155            list = list->fNext;
156            ++count;
157        }
158        return count;
159    }
160#endif
161
162private:
163    SkTDynamicHash<ValueList, Key> fHash;
164    int fCount;
165};
166
167#endif
168