Home | History | Annotate | Download | only in core 
      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 (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(list);
     61         ValueList* prev = NULL;
     62         while (list->fValue != value) {
     63             prev = list;
     64             list = list->fNext;
     65         }
     66 
     67         if (list->fNext) {
     68             ValueList* next = list->fNext;
     69             list->fValue = next->fValue;
     70             list->fNext = next->fNext;
     71             SkDELETE(next);
     72         } else if (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 (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 (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 #ifdef SK_DEBUG
    106     // This is not particularly fast and only used for validation, so debug only.
    107     int countForKey(const Key& key) const {
    108         int count = 0;
    109         ValueList* list = fHash.find(key);
    110         while (list) {
    111             list = list->fNext;
    112             ++count;
    113         }
    114         return count;
    115     }
    116 #endif
    117 
    118 private:
    119     SkTDynamicHash<ValueList, Key> fHash;
    120     int fCount;
    121 };
    122 
    123 #endif
    124