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         typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash);
     34         for ( ; !iter.done(); ++iter) {
     35             ValueList* next;
     36             for (ValueList* cur = &(*iter); cur; cur = next) {
     37                 HashTraits::OnFree(cur->fValue);
     38                 next = cur->fNext;
     39                 delete cur;
     40             }
     41         }
     42     }
     43 
     44     void insert(const Key& key, T* value) {
     45         ValueList* list = fHash.find(key);
     46         if (list) {
     47             // The new ValueList entry is inserted as the second element in the
     48             // linked list, and it will contain the value of the first element.
     49             ValueList* newEntry = new ValueList(list->fValue);
     50             newEntry->fNext = list->fNext;
     51             // The existing first ValueList entry is updated to contain the
     52             // inserted value.
     53             list->fNext = newEntry;
     54             list->fValue = value;
     55         } else {
     56             fHash.add(new ValueList(value));
     57         }
     58 
     59         ++fCount;
     60     }
     61 
     62     void remove(const Key& key, const T* value) {
     63         ValueList* list = fHash.find(key);
     64         // Since we expect the caller to be fully aware of what is stored, just
     65         // assert that the caller removes an existing value.
     66         SkASSERT(list);
     67         ValueList* prev = nullptr;
     68         while (list->fValue != value) {
     69             prev = list;
     70             list = list->fNext;
     71         }
     72 
     73         this->internalRemove(prev, list, key);
     74     }
     75 
     76     T* find(const Key& key) const {
     77         ValueList* list = fHash.find(key);
     78         if (list) {
     79             return list->fValue;
     80         }
     81         return nullptr;
     82     }
     83 
     84     template<class FindPredicate>
     85     T* find(const Key& key, const FindPredicate f) {
     86         ValueList* list = fHash.find(key);
     87         while (list) {
     88             if (f(list->fValue)){
     89                 return list->fValue;
     90             }
     91             list = list->fNext;
     92         }
     93         return nullptr;
     94     }
     95 
     96     template<class FindPredicate>
     97     T* findAndRemove(const Key& key, const FindPredicate f) {
     98         ValueList* list = fHash.find(key);
     99 
    100         ValueList* prev = nullptr;
    101         while (list) {
    102             if (f(list->fValue)){
    103                 T* value = list->fValue;
    104                 this->internalRemove(prev, list, key);
    105                 return value;
    106             }
    107             prev = list;
    108             list = list->fNext;
    109         }
    110         return nullptr;
    111     }
    112 
    113     int count() const { return fCount; }
    114 
    115 #ifdef SK_DEBUG
    116     class ConstIter {
    117     public:
    118         explicit ConstIter(const SkTMultiMap* mmap)
    119             : fIter(&(mmap->fHash))
    120             , fList(nullptr) {
    121             if (!fIter.done()) {
    122                 fList = &(*fIter);
    123             }
    124         }
    125 
    126         bool done() const {
    127             return fIter.done();
    128         }
    129 
    130         const T* operator*() {
    131             SkASSERT(fList);
    132             return fList->fValue;
    133         }
    134 
    135         void operator++() {
    136             if (fList) {
    137                 fList = fList->fNext;
    138             }
    139             if (!fList) {
    140                 ++fIter;
    141                 if (!fIter.done()) {
    142                     fList = &(*fIter);
    143                 }
    144             }
    145         }
    146 
    147     private:
    148         typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
    149         const ValueList* fList;
    150     };
    151 
    152     bool has(const T* value, const Key& key) const {
    153         for (ValueList* list = fHash.find(key); list; list = list->fNext) {
    154             if (list->fValue == value) {
    155                 return true;
    156             }
    157         }
    158         return false;
    159     }
    160 
    161     // This is not particularly fast and only used for validation, so debug only.
    162     int countForKey(const Key& key) const {
    163         int count = 0;
    164         ValueList* list = fHash.find(key);
    165         while (list) {
    166             list = list->fNext;
    167             ++count;
    168         }
    169         return count;
    170     }
    171 #endif
    172 
    173 private:
    174     SkTDynamicHash<ValueList, Key> fHash;
    175     int fCount;
    176 
    177     void internalRemove(ValueList* prev, ValueList* elem, const Key& key) {
    178         if (elem->fNext) {
    179             ValueList* next = elem->fNext;
    180             elem->fValue = next->fValue;
    181             elem->fNext = next->fNext;
    182             delete next;
    183         } else if (prev) {
    184             prev->fNext = nullptr;
    185             delete elem;
    186         } else {
    187             fHash.remove(key);
    188             delete elem;
    189         }
    190 
    191         --fCount;
    192     }
    193 
    194 };
    195 
    196 #endif
    197