src/third_party/skia/src/gpu/GrTMultiMap.h

   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 GrTMultiMap_DEFINED
  10 #define GrTMultiMap_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  */
  18 template <typename T,
  19           typename Key,
  20           const Key& (GetKey)(const T&),
  21           uint32_t (Hash)(const Key&),
  22           bool (Equal)(const T&, const Key&)>
  23 class GrTMultiMap {
  24     struct ValueList {
  25         explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
  26
  27         static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); }
  28         static uint32_t ListHash(const Key& key) { return Hash(key); }
  29         static bool ListEqual(const ValueList& a, const Key& b) {
  30             return Equal(*a.fValue, b);
  31         }
  32         T* fValue;
  33         ValueList* fNext;
  34     };
  35 public:
  36     GrTMultiMap() : fCount(0) {}
  37
  38     ~GrTMultiMap() {
  39         SkASSERT(fCount == 0);
  40         SkASSERT(fHash.count() == 0);
  41     }
  42
  43     void insert(const Key& key, T* value) {
  44         ValueList* list = fHash.find(key);
  45         if (NULL != list) {
  46             // The new ValueList entry is inserted as the second element in the
  47             // linked list, and it will contain the value of the first element.
  48             ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue));
  49             newEntry->fNext = list->fNext;
  50             // The existing first ValueList entry is updated to contain the
  51             // inserted value.
  52             list->fNext = newEntry;
  53             list->fValue = value;
  54         } else {
  55             fHash.add(SkNEW_ARGS(ValueList, (value)));
  56         }
  57
  58         ++fCount;
  59     }
  60
  61     void remove(const Key& key, const T* value) {
  62         ValueList* list = fHash.find(key);
  63         // Since we expect the caller to be fully aware of what is stored, just
  64         // assert that the caller removes an existing value.
  65         SkASSERT(NULL != list);
  66         ValueList* prev = NULL;
  67         while (list->fValue != value) {
  68             prev = list;
  69             list = list->fNext;
  70         }
  71
  72         if (NULL != list->fNext) {
  73             ValueList* next = list->fNext;
  74             list->fValue = next->fValue;
  75             list->fNext = next->fNext;
  76             SkDELETE(next);
  77         } else if (NULL != prev) {
  78             prev->fNext = NULL;
  79             SkDELETE(list);
  80         } else {
  81             fHash.remove(key);
  82             SkDELETE(list);
  83         }
  84
  85         --fCount;
  86     }
  87
  88     T* find(const Key& key) const {
  89         ValueList* list = fHash.find(key);
  90         if (NULL != list) {
  91             return list->fValue;
  92         }
  93         return NULL;
  94     }
  95
  96     template<class FindPredicate>
  97     T* find(const Key& key, const FindPredicate f) {
  98         ValueList* list = fHash.find(key);
  99         while (NULL != list) {
 100             if (f(list->fValue)){
 101                 return list->fValue;
 102             }
 103             list = list->fNext;
 104         }
 105         return NULL;
 106     }
 107
 108     int count() const { return fCount; }
 109
 110 private:
 111     SkTDynamicHash<ValueList,
 112                    Key,
 113                    ValueList::ListGetKey,
 114                    ValueList::ListHash,
 115                    ValueList::ListEqual> fHash;
 116     int fCount;
 117 };
 118
 119 #endif