SkTMultiMap.h 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
  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. #ifndef SkTMultiMap_DEFINED
  8. #define SkTMultiMap_DEFINED
  9. #include "include/gpu/GrTypes.h"
  10. #include "src/core/SkTDynamicHash.h"
  11. /** A set that contains pointers to instances of T. Instances can be looked up with key Key.
  12. * Multiple (possibly same) values can have the same key.
  13. */
  14. template <typename T,
  15. typename Key,
  16. typename HashTraits=T>
  17. class SkTMultiMap {
  18. struct ValueList {
  19. explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
  20. static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
  21. static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
  22. T* fValue;
  23. ValueList* fNext;
  24. };
  25. public:
  26. SkTMultiMap() : fCount(0) {}
  27. ~SkTMultiMap() {
  28. typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash);
  29. for ( ; !iter.done(); ++iter) {
  30. ValueList* next;
  31. for (ValueList* cur = &(*iter); cur; cur = next) {
  32. HashTraits::OnFree(cur->fValue);
  33. next = cur->fNext;
  34. delete cur;
  35. }
  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 = new 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(new ValueList(value));
  51. }
  52. ++fCount;
  53. }
  54. void remove(const Key& key, const T* value) {
  55. ValueList* list = fHash.find(key);
  56. // Temporarily making this safe for remove entries not in the map because of
  57. // crbug.com/877915.
  58. #if 0
  59. // Since we expect the caller to be fully aware of what is stored, just
  60. // assert that the caller removes an existing value.
  61. SkASSERT(list);
  62. ValueList* prev = nullptr;
  63. while (list->fValue != value) {
  64. prev = list;
  65. list = list->fNext;
  66. }
  67. this->internalRemove(prev, list, key);
  68. #else
  69. ValueList* prev = nullptr;
  70. while (list && list->fValue != value) {
  71. prev = list;
  72. list = list->fNext;
  73. }
  74. // Crash in Debug since it'd be great to detect a repro of 877915.
  75. SkASSERT(list);
  76. if (list) {
  77. this->internalRemove(prev, list, key);
  78. }
  79. #endif
  80. }
  81. T* find(const Key& key) const {
  82. ValueList* list = fHash.find(key);
  83. if (list) {
  84. return list->fValue;
  85. }
  86. return nullptr;
  87. }
  88. template<class FindPredicate>
  89. T* find(const Key& key, const FindPredicate f) {
  90. ValueList* list = fHash.find(key);
  91. while (list) {
  92. if (f(list->fValue)){
  93. return list->fValue;
  94. }
  95. list = list->fNext;
  96. }
  97. return nullptr;
  98. }
  99. template<class FindPredicate>
  100. T* findAndRemove(const Key& key, const FindPredicate f) {
  101. ValueList* list = fHash.find(key);
  102. ValueList* prev = nullptr;
  103. while (list) {
  104. if (f(list->fValue)){
  105. T* value = list->fValue;
  106. this->internalRemove(prev, list, key);
  107. return value;
  108. }
  109. prev = list;
  110. list = list->fNext;
  111. }
  112. return nullptr;
  113. }
  114. int count() const { return fCount; }
  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. bool done() const {
  126. return fIter.done();
  127. }
  128. const T* operator*() {
  129. SkASSERT(fList);
  130. return fList->fValue;
  131. }
  132. void operator++() {
  133. if (fList) {
  134. fList = fList->fNext;
  135. }
  136. if (!fList) {
  137. ++fIter;
  138. if (!fIter.done()) {
  139. fList = &(*fIter);
  140. }
  141. }
  142. }
  143. private:
  144. typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
  145. const ValueList* fList;
  146. };
  147. bool has(const T* value, const Key& key) const {
  148. for (ValueList* list = fHash.find(key); list; list = list->fNext) {
  149. if (list->fValue == value) {
  150. return true;
  151. }
  152. }
  153. return false;
  154. }
  155. // This is not particularly fast and only used for validation, so debug only.
  156. int countForKey(const Key& key) const {
  157. int count = 0;
  158. ValueList* list = fHash.find(key);
  159. while (list) {
  160. list = list->fNext;
  161. ++count;
  162. }
  163. return count;
  164. }
  165. #endif
  166. private:
  167. SkTDynamicHash<ValueList, Key> fHash;
  168. int fCount;
  169. void internalRemove(ValueList* prev, ValueList* elem, const Key& key) {
  170. if (elem->fNext) {
  171. ValueList* next = elem->fNext;
  172. elem->fValue = next->fValue;
  173. elem->fNext = next->fNext;
  174. delete next;
  175. } else if (prev) {
  176. prev->fNext = nullptr;
  177. delete elem;
  178. } else {
  179. fHash.remove(key);
  180. delete elem;
  181. }
  182. --fCount;
  183. }
  184. };
  185. #endif