src/third_party/skia/src/core/SkTMultiMap.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 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  */
  18 template <typename T,
  19           typename Key,
  20           typename HashTraits=T>
  21 class SkTMultiMap {
  22     struct ValueList {
  23         explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
  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     };
  30 public:
  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 (NULL != 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 = SkNEW_ARGS(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(SkNEW_ARGS(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(NULL != list);
  61         ValueList* prev = NULL;
  62         while (list->fValue != value) {
  63             prev = list;
  64             list = list->fNext;
  65         }
  66
  67         if (NULL != list->fNext) {
  68             ValueList* next = list->fNext;
  69             list->fValue = next->fValue;
  70             list->fNext = next->fNext;
  71             SkDELETE(next);
  72         } else if (NULL != prev) {
  73             prev->fNext = NULL;
  74             SkDELETE(list);
  75         } else {
  76             fHash.remove(key);
  77             SkDELETE(list);
  78         }
  79
  80         --fCount;
  81     }
  82
  83     T* find(const Key& key) const {
  84         ValueList* list = fHash.find(key);
  85         if (NULL != list) {
  86             return list->fValue;
  87         }
  88         return NULL;
  89     }
  90
  91     template<class FindPredicate>
  92     T* find(const Key& key, const FindPredicate f) {
  93         ValueList* list = fHash.find(key);
  94         while (NULL != list) {
  95             if (f(list->fValue)){
  96                 return list->fValue;
  97             }
  98             list = list->fNext;
  99         }
 100         return NULL;
 101     }
 102
 103     int count() const { return fCount; }
 104
 105 private:
 106     SkTDynamicHash<ValueList, Key> fHash;
 107     int fCount;
 108 };
 109
 110 #endif