blob: c8872143b38e6210aa76e728e25ac616b0feaa58 [file] [log] [blame]
/*
* 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 GrTMultiMap_DEFINED
#define GrTMultiMap_DEFINED
#include "GrTypes.h"
#include "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,
const Key& (GetKey)(const T&),
uint32_t (Hash)(const Key&),
bool (Equal)(const T&, const Key&)>
class GrTMultiMap {
struct ValueList {
explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); }
static uint32_t ListHash(const Key& key) { return Hash(key); }
static bool ListEqual(const ValueList& a, const Key& b) {
return Equal(*a.fValue, b);
}
T* fValue;
ValueList* fNext;
};
public:
GrTMultiMap() : fCount(0) {}
~GrTMultiMap() {
SkASSERT(fCount == 0);
SkASSERT(fHash.count() == 0);
}
void insert(const Key& key, T* value) {
ValueList* list = fHash.find(key);
if (NULL != 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 = SkNEW_ARGS(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(SkNEW_ARGS(ValueList, (value)));
}
++fCount;
}
void remove(const Key& key, const T* value) {
ValueList* list = fHash.find(key);
// Since we expect the caller to be fully aware of what is stored, just
// assert that the caller removes an existing value.
SkASSERT(NULL != list);
ValueList* prev = NULL;
while (list->fValue != value) {
prev = list;
list = list->fNext;
}
if (NULL != list->fNext) {
ValueList* next = list->fNext;
list->fValue = next->fValue;
list->fNext = next->fNext;
SkDELETE(next);
} else if (NULL != prev) {
prev->fNext = NULL;
SkDELETE(list);
} else {
fHash.remove(key);
SkDELETE(list);
}
--fCount;
}
T* find(const Key& key) const {
ValueList* list = fHash.find(key);
if (NULL != list) {
return list->fValue;
}
return NULL;
}
template<class FindPredicate>
T* find(const Key& key, const FindPredicate f) {
ValueList* list = fHash.find(key);
while (NULL != list) {
if (f(list->fValue)){
return list->fValue;
}
list = list->fNext;
}
return NULL;
}
int count() const { return fCount; }
private:
SkTDynamicHash<ValueList,
Key,
ValueList::ListGetKey,
ValueList::ListHash,
ValueList::ListEqual> fHash;
int fCount;
};
#endif