Line data    Source code

       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           0 :         explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
      23             : 
      24           0 :         static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
      25           0 :         static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
      26             :         T* fValue;
      27             :         ValueList* fNext;
      28             :     };
      29             : public:
      30           0 :     SkTMultiMap() : fCount(0) {}
      31             : 
      32           0 :     ~SkTMultiMap() {
      33           0 :         SkASSERT(fCount == 0);
      34           0 :         SkASSERT(fHash.count() == 0);
      35           0 :     }
      36             : 
      37           0 :     void insert(const Key& key, T* value) {
      38           0 :         ValueList* list = fHash.find(key);
      39           0 :         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           0 :             ValueList* newEntry = new ValueList(list->fValue);
      43           0 :             newEntry->fNext = list->fNext;
      44             :             // The existing first ValueList entry is updated to contain the
      45             :             // inserted value.
      46           0 :             list->fNext = newEntry;
      47           0 :             list->fValue = value;
      48             :         } else {
      49           0 :             fHash.add(new ValueList(value));
      50             :         }
      51             : 
      52           0 :         ++fCount;
      53           0 :     }
      54             : 
      55           0 :     void remove(const Key& key, const T* value) {
      56           0 :         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           0 :         SkASSERT(list);
      60           0 :         ValueList* prev = nullptr;
      61           0 :         while (list->fValue != value) {
      62           0 :             prev = list;
      63           0 :             list = list->fNext;
      64             :         }
      65             : 
      66           0 :         if (list->fNext) {
      67           0 :             ValueList* next = list->fNext;
      68           0 :             list->fValue = next->fValue;
      69           0 :             list->fNext = next->fNext;
      70             :             delete next;
      71           0 :         } else if (prev) {
      72           0 :             prev->fNext = nullptr;
      73             :             delete list;
      74             :         } else {
      75           0 :             fHash.remove(key);
      76             :             delete list;
      77             :         }
      78             : 
      79           0 :         --fCount;
      80           0 :     }
      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           0 :     T* find(const Key& key, const FindPredicate f) {
      92           0 :         ValueList* list = fHash.find(key);
      93           0 :         while (list) {
      94           0 :             if (f(list->fValue)){
      95           0 :                 return list->fValue;
      96             :             }
      97           0 :             list = list->fNext;
      98             :         }
      99           0 :         return nullptr;
     100             :     }
     101             : 
     102           0 :     int count() const { return fCount; }
     103             : 
     104             : #ifdef SK_DEBUG
     105             :     class ConstIter {
     106             :     public:
     107           0 :         explicit ConstIter(const SkTMultiMap* mmap)
     108             :             : fIter(&(mmap->fHash))
     109           0 :             , fList(nullptr) {
     110           0 :             if (!fIter.done()) {
     111           0 :                 fList = &(*fIter);
     112             :             }
     113           0 :         }
     114             : 
     115           0 :         bool done() const {
     116           0 :             return fIter.done();
     117             :         }
     118             : 
     119           0 :         const T* operator*() {
     120           0 :             SkASSERT(fList);
     121           0 :             return fList->fValue;
     122             :         }
     123             : 
     124           0 :         void operator++() {
     125           0 :             if (fList) {
     126           0 :                 fList = fList->fNext;
     127             :             }
     128           0 :             if (!fList) {
     129           0 :                 ++fIter;
     130           0 :                 if (!fIter.done()) {
     131           0 :                     fList = &(*fIter);
     132             :                 }
     133             :             }
     134           0 :         }
     135             : 
     136             :     private:
     137             :         typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
     138             :         const ValueList* fList;
     139             :     };
     140             : 
     141           0 :     bool has(const T* value, const Key& key) const {
     142           0 :         for (ValueList* list = fHash.find(key); list; list = list->fNext) {
     143           0 :             if (list->fValue == value) {
     144           0 :                 return true;
     145             :             }
     146             :         }
     147           0 :         return false;
     148             :     }
     149             : 
     150             :     // This is not particularly fast and only used for validation, so debug only.
     151           0 :     int countForKey(const Key& key) const {
     152           0 :         int count = 0;
     153           0 :         ValueList* list = fHash.find(key);
     154           0 :         while (list) {
     155           0 :             list = list->fNext;
     156           0 :             ++count;
     157             :         }
     158           0 :         return count;
     159             :     }
     160             : #endif
     161             : 
     162             : private:
     163             :     SkTDynamicHash<ValueList, Key> fHash;
     164             :     int fCount;
     165             : };
     166             : 
     167             : #endif