Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2013 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #ifndef SkTMultiMap_DEFINED
      9 #define SkTMultiMap_DEFINED
     10 
     11 #include "GrTypes.h"
     12 #include "SkTDynamicHash.h"
     13 
     14 /** A set that contains pointers to instances of T. Instances can be looked up with key Key.
     15  * Multiple (possibly same) values can have the same key.
     16  */
     17 template <typename T,
     18           typename Key,
     19           typename HashTraits=T>
     20 class SkTMultiMap {
     21     struct ValueList {
     22         explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
     23 
     24         static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
     25         static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
     26         T* fValue;
     27         ValueList* fNext;
     28     };
     29 public:
     30     SkTMultiMap() : fCount(0) {}
     31 
     32     ~SkTMultiMap() {
     33         SkASSERT(fCount == 0);
     34         SkASSERT(fHash.count() == 0);
     35     }
     36 
     37     void insert(const Key& key, T* value) {
     38         ValueList* list = fHash.find(key);
     39         if (list) {
     40             // The new ValueList entry is inserted as the second element in the
     41             // linked list, and it will contain the value of the first element.
     42             ValueList* newEntry = new ValueList(list->fValue);
     43             newEntry->fNext = list->fNext;
     44             // The existing first ValueList entry is updated to contain the
     45             // inserted value.
     46             list->fNext = newEntry;
     47             list->fValue = value;
     48         } else {
     49             fHash.add(new ValueList(value));
     50         }
     51 
     52         ++fCount;
     53     }
     54 
     55     void remove(const Key& key, const T* value) {
     56         ValueList* list = fHash.find(key);
     57         // Since we expect the caller to be fully aware of what is stored, just
     58         // assert that the caller removes an existing value.
     59         SkASSERT(list);
     60         ValueList* prev = nullptr;
     61         while (list->fValue != value) {
     62             prev = list;
     63             list = list->fNext;
     64         }
     65 
     66         if (list->fNext) {
     67             ValueList* next = list->fNext;
     68             list->fValue = next->fValue;
     69             list->fNext = next->fNext;
     70             delete next;
     71         } else if (prev) {
     72             prev->fNext = nullptr;
     73             delete list;
     74         } else {
     75             fHash.remove(key);
     76             delete list;
     77         }
     78 
     79         --fCount;
     80     }
     81 
     82     T* find(const Key& key) const {
     83         ValueList* list = fHash.find(key);
     84         if (list) {
     85             return list->fValue;
     86         }
     87         return nullptr;
     88     }
     89 
     90     template<class FindPredicate>
     91     T* find(const Key& key, const FindPredicate f) {
     92         ValueList* list = fHash.find(key);
     93         while (list) {
     94             if (f(list->fValue)){
     95                 return list->fValue;
     96             }
     97             list = list->fNext;
     98         }
     99         return nullptr;
    100     }
    101 
    102     int count() const { return fCount; }
    103 
    104 #ifdef SK_DEBUG
    105     class ConstIter {
    106     public:
    107         explicit ConstIter(const SkTMultiMap* mmap)
    108             : fIter(&(mmap->fHash))
    109             , fList(nullptr) {
    110             if (!fIter.done()) {
    111                 fList = &(*fIter);
    112             }
    113         }
    114 
    115         bool done() const {
    116             return fIter.done();
    117         }
    118 
    119         const T* operator*() {
    120             SkASSERT(fList);
    121             return fList->fValue;
    122         }
    123 
    124         void operator++() {
    125             if (fList) {
    126                 fList = fList->fNext;
    127             }
    128             if (!fList) {
    129                 ++fIter;
    130                 if (!fIter.done()) {
    131                     fList = &(*fIter);
    132                 }
    133             }
    134         }
    135 
    136     private:
    137         typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
    138         const ValueList* fList;
    139     };
    140 
    141     bool has(const T* value, const Key& key) const {
    142         for (ValueList* list = fHash.find(key); list; list = list->fNext) {
    143             if (list->fValue == value) {
    144                 return true;
    145             }
    146         }
    147         return false;
    148     }
    149 
    150     // This is not particularly fast and only used for validation, so debug only.
    151     int countForKey(const Key& key) const {
    152         int count = 0;
    153         ValueList* list = fHash.find(key);
    154         while (list) {
    155             list = list->fNext;
    156             ++count;
    157         }
    158         return count;
    159     }
    160 #endif
    161 
    162 private:
    163     SkTDynamicHash<ValueList, Key> fHash;
    164     int fCount;
    165 };
    166 
    167 #endif
    168