123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 |
- /*
- * Copyright 2013 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SkTMultiMap_DEFINED
- #define SkTMultiMap_DEFINED
- #include "include/gpu/GrTypes.h"
- #include "src/core/SkTDynamicHash.h"
- /** A set that contains pointers to instances of T. Instances can be looked up with key Key.
- * Multiple (possibly same) values can have the same key.
- */
- template <typename T,
- typename Key,
- typename HashTraits=T>
- class SkTMultiMap {
- struct ValueList {
- explicit ValueList(T* value) : fValue(value), fNext(nullptr) {}
- static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); }
- static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); }
- T* fValue;
- ValueList* fNext;
- };
- public:
- SkTMultiMap() : fCount(0) {}
- ~SkTMultiMap() {
- typename SkTDynamicHash<ValueList, Key>::Iter iter(&fHash);
- for ( ; !iter.done(); ++iter) {
- ValueList* next;
- for (ValueList* cur = &(*iter); cur; cur = next) {
- HashTraits::OnFree(cur->fValue);
- next = cur->fNext;
- delete cur;
- }
- }
- }
- void insert(const Key& key, T* value) {
- ValueList* list = fHash.find(key);
- if (list) {
- // The new ValueList entry is inserted as the second element in the
- // linked list, and it will contain the value of the first element.
- ValueList* newEntry = new ValueList(list->fValue);
- newEntry->fNext = list->fNext;
- // The existing first ValueList entry is updated to contain the
- // inserted value.
- list->fNext = newEntry;
- list->fValue = value;
- } else {
- fHash.add(new ValueList(value));
- }
- ++fCount;
- }
- void remove(const Key& key, const T* value) {
- ValueList* list = fHash.find(key);
- // Temporarily making this safe for remove entries not in the map because of
- // crbug.com/877915.
- #if 0
- // Since we expect the caller to be fully aware of what is stored, just
- // assert that the caller removes an existing value.
- SkASSERT(list);
- ValueList* prev = nullptr;
- while (list->fValue != value) {
- prev = list;
- list = list->fNext;
- }
- this->internalRemove(prev, list, key);
- #else
- ValueList* prev = nullptr;
- while (list && list->fValue != value) {
- prev = list;
- list = list->fNext;
- }
- // Crash in Debug since it'd be great to detect a repro of 877915.
- SkASSERT(list);
- if (list) {
- this->internalRemove(prev, list, key);
- }
- #endif
- }
- T* find(const Key& key) const {
- ValueList* list = fHash.find(key);
- if (list) {
- return list->fValue;
- }
- return nullptr;
- }
- template<class FindPredicate>
- T* find(const Key& key, const FindPredicate f) {
- ValueList* list = fHash.find(key);
- while (list) {
- if (f(list->fValue)){
- return list->fValue;
- }
- list = list->fNext;
- }
- return nullptr;
- }
- template<class FindPredicate>
- T* findAndRemove(const Key& key, const FindPredicate f) {
- ValueList* list = fHash.find(key);
- ValueList* prev = nullptr;
- while (list) {
- if (f(list->fValue)){
- T* value = list->fValue;
- this->internalRemove(prev, list, key);
- return value;
- }
- prev = list;
- list = list->fNext;
- }
- return nullptr;
- }
- int count() const { return fCount; }
- #ifdef SK_DEBUG
- class ConstIter {
- public:
- explicit ConstIter(const SkTMultiMap* mmap)
- : fIter(&(mmap->fHash))
- , fList(nullptr) {
- if (!fIter.done()) {
- fList = &(*fIter);
- }
- }
- bool done() const {
- return fIter.done();
- }
- const T* operator*() {
- SkASSERT(fList);
- return fList->fValue;
- }
- void operator++() {
- if (fList) {
- fList = fList->fNext;
- }
- if (!fList) {
- ++fIter;
- if (!fIter.done()) {
- fList = &(*fIter);
- }
- }
- }
- private:
- typename SkTDynamicHash<ValueList, Key>::ConstIter fIter;
- const ValueList* fList;
- };
- bool has(const T* value, const Key& key) const {
- for (ValueList* list = fHash.find(key); list; list = list->fNext) {
- if (list->fValue == value) {
- return true;
- }
- }
- return false;
- }
- // This is not particularly fast and only used for validation, so debug only.
- int countForKey(const Key& key) const {
- int count = 0;
- ValueList* list = fHash.find(key);
- while (list) {
- list = list->fNext;
- ++count;
- }
- return count;
- }
- #endif
- private:
- SkTDynamicHash<ValueList, Key> fHash;
- int fCount;
- void internalRemove(ValueList* prev, ValueList* elem, const Key& key) {
- if (elem->fNext) {
- ValueList* next = elem->fNext;
- elem->fValue = next->fValue;
- elem->fNext = next->fNext;
- delete next;
- } else if (prev) {
- prev->fNext = nullptr;
- delete elem;
- } else {
- fHash.remove(key);
- delete elem;
- }
- --fCount;
- }
- };
- #endif
|