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 */ 17template <typename T, 18 typename Key, 19 typename HashTraits=T> 20class 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 }; 29public: 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 162private: 163 SkTDynamicHash<ValueList, Key> fHash; 164 int fCount; 165}; 166 167#endif 168