aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkTMultiMap.h
blob: 1168ed6e915a0cd7d0c05144eaa1f1c24516c336 (plain)
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