1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrTMultiMap.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,119 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2013 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#ifndef GrTMultiMap_DEFINED
1.13 +#define GrTMultiMap_DEFINED
1.14 +
1.15 +#include "GrTypes.h"
1.16 +#include "SkTDynamicHash.h"
1.17 +
1.18 +/** A set that contains pointers to instances of T. Instances can be looked up with key Key.
1.19 + * Multiple (possibly same) values can have the same key.
1.20 + */
1.21 +template <typename T,
1.22 + typename Key,
1.23 + const Key& (GetKey)(const T&),
1.24 + uint32_t (Hash)(const Key&),
1.25 + bool (Equal)(const T&, const Key&)>
1.26 +class GrTMultiMap {
1.27 + struct ValueList {
1.28 + explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
1.29 +
1.30 + static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); }
1.31 + static uint32_t ListHash(const Key& key) { return Hash(key); }
1.32 + static bool ListEqual(const ValueList& a, const Key& b) {
1.33 + return Equal(*a.fValue, b);
1.34 + }
1.35 + T* fValue;
1.36 + ValueList* fNext;
1.37 + };
1.38 +public:
1.39 + GrTMultiMap() : fCount(0) {}
1.40 +
1.41 + ~GrTMultiMap() {
1.42 + SkASSERT(fCount == 0);
1.43 + SkASSERT(fHash.count() == 0);
1.44 + }
1.45 +
1.46 + void insert(const Key& key, T* value) {
1.47 + ValueList* list = fHash.find(key);
1.48 + if (NULL != list) {
1.49 + // The new ValueList entry is inserted as the second element in the
1.50 + // linked list, and it will contain the value of the first element.
1.51 + ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue));
1.52 + newEntry->fNext = list->fNext;
1.53 + // The existing first ValueList entry is updated to contain the
1.54 + // inserted value.
1.55 + list->fNext = newEntry;
1.56 + list->fValue = value;
1.57 + } else {
1.58 + fHash.add(SkNEW_ARGS(ValueList, (value)));
1.59 + }
1.60 +
1.61 + ++fCount;
1.62 + }
1.63 +
1.64 + void remove(const Key& key, const T* value) {
1.65 + ValueList* list = fHash.find(key);
1.66 + // Since we expect the caller to be fully aware of what is stored, just
1.67 + // assert that the caller removes an existing value.
1.68 + SkASSERT(NULL != list);
1.69 + ValueList* prev = NULL;
1.70 + while (list->fValue != value) {
1.71 + prev = list;
1.72 + list = list->fNext;
1.73 + }
1.74 +
1.75 + if (NULL != list->fNext) {
1.76 + ValueList* next = list->fNext;
1.77 + list->fValue = next->fValue;
1.78 + list->fNext = next->fNext;
1.79 + SkDELETE(next);
1.80 + } else if (NULL != prev) {
1.81 + prev->fNext = NULL;
1.82 + SkDELETE(list);
1.83 + } else {
1.84 + fHash.remove(key);
1.85 + SkDELETE(list);
1.86 + }
1.87 +
1.88 + --fCount;
1.89 + }
1.90 +
1.91 + T* find(const Key& key) const {
1.92 + ValueList* list = fHash.find(key);
1.93 + if (NULL != list) {
1.94 + return list->fValue;
1.95 + }
1.96 + return NULL;
1.97 + }
1.98 +
1.99 + template<class FindPredicate>
1.100 + T* find(const Key& key, const FindPredicate f) {
1.101 + ValueList* list = fHash.find(key);
1.102 + while (NULL != list) {
1.103 + if (f(list->fValue)){
1.104 + return list->fValue;
1.105 + }
1.106 + list = list->fNext;
1.107 + }
1.108 + return NULL;
1.109 + }
1.110 +
1.111 + int count() const { return fCount; }
1.112 +
1.113 +private:
1.114 + SkTDynamicHash<ValueList,
1.115 + Key,
1.116 + ValueList::ListGetKey,
1.117 + ValueList::ListHash,
1.118 + ValueList::ListEqual> fHash;
1.119 + int fCount;
1.120 +};
1.121 +
1.122 +#endif
