1bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 2bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org/* 3bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org * Copyright 2013 Google Inc. 4bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org * 5bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 6bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org * found in the LICENSE file. 7bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org */ 8bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 97a037f494f3be524843540634507789c39f83689robertphillips#ifndef SkTMultiMap_DEFINED 107a037f494f3be524843540634507789c39f83689robertphillips#define SkTMultiMap_DEFINED 11bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 12bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org#include "GrTypes.h" 13bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org#include "SkTDynamicHash.h" 14bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 15bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org/** A set that contains pointers to instances of T. Instances can be looked up with key Key. 16bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org * Multiple (possibly same) values can have the same key. 17bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org */ 18bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.orgtemplate <typename T, 19bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org typename Key, 2055bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org typename HashTraits=T> 217a037f494f3be524843540634507789c39f83689robertphillipsclass SkTMultiMap { 22bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org struct ValueList { 23bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org explicit ValueList(T* value) : fValue(value), fNext(NULL) {} 24bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 2555bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org static const Key& GetKey(const ValueList& e) { return HashTraits::GetKey(*e.fValue); } 2655bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org static uint32_t Hash(const Key& key) { return HashTraits::Hash(key); } 27bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org T* fValue; 28bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* fNext; 29bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org }; 30bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.orgpublic: 317a037f494f3be524843540634507789c39f83689robertphillips SkTMultiMap() : fCount(0) {} 32bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 337a037f494f3be524843540634507789c39f83689robertphillips ~SkTMultiMap() { 34bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org SkASSERT(fCount == 0); 35bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org SkASSERT(fHash.count() == 0); 36bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 37bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 38bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org void insert(const Key& key, T* value) { 39bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* list = fHash.find(key); 4049f085dddff10473b6ebf832a974288300224e60bsalomon if (list) { 41bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // The new ValueList entry is inserted as the second element in the 42bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // linked list, and it will contain the value of the first element. 43bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue)); 44bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org newEntry->fNext = list->fNext; 45bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // The existing first ValueList entry is updated to contain the 46bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // inserted value. 47bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list->fNext = newEntry; 48bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list->fValue = value; 49bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } else { 50bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org fHash.add(SkNEW_ARGS(ValueList, (value))); 51bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 52bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 53bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ++fCount; 54bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 55bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 56bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org void remove(const Key& key, const T* value) { 57bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* list = fHash.find(key); 58bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // Since we expect the caller to be fully aware of what is stored, just 59bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org // assert that the caller removes an existing value. 6049f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(list); 61bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* prev = NULL; 62bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org while (list->fValue != value) { 63bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org prev = list; 64bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list = list->fNext; 65bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 66bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 6749f085dddff10473b6ebf832a974288300224e60bsalomon if (list->fNext) { 68bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* next = list->fNext; 69bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list->fValue = next->fValue; 70bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list->fNext = next->fNext; 71bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org SkDELETE(next); 7249f085dddff10473b6ebf832a974288300224e60bsalomon } else if (prev) { 73bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org prev->fNext = NULL; 74bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org SkDELETE(list); 75bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } else { 76bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org fHash.remove(key); 77bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org SkDELETE(list); 78bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 79bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 80bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org --fCount; 81bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 82bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 83bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org T* find(const Key& key) const { 84bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* list = fHash.find(key); 8549f085dddff10473b6ebf832a974288300224e60bsalomon if (list) { 86bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org return list->fValue; 87bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 88bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org return NULL; 89bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 90bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 91bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org template<class FindPredicate> 92bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org T* find(const Key& key, const FindPredicate f) { 93bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org ValueList* list = fHash.find(key); 9449f085dddff10473b6ebf832a974288300224e60bsalomon while (list) { 95bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org if (f(list->fValue)){ 96bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org return list->fValue; 97bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 98bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org list = list->fNext; 99bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 100bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org return NULL; 101bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org } 102bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 103bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org int count() const { return fCount; } 104bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 105bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.orgprivate: 10655bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org SkTDynamicHash<ValueList, Key> fHash; 107bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org int fCount; 108bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org}; 109bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org 110bd58febffb103ea830bf027c5a95313548f7ea8ecommit-bot@chromium.org#endif 111