The Tor Browser: gfx/skia/trunk/src/gpu/GrTMultiMap.h@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     2 /*

     3  * Copyright 2013 Google Inc.

     4  *

     5  * Use of this source code is governed by a BSD-style license that can be

     6  * found in the LICENSE file.

     7  */

     9 #ifndef GrTMultiMap_DEFINED

    10 #define GrTMultiMap_DEFINED

    12 #include "GrTypes.h"

    13 #include "SkTDynamicHash.h"

    15 /** A set that contains pointers to instances of T. Instances can be looked up with key Key.

    16  * Multiple (possibly same) values can have the same key.

    17  */

    18 template <typename T,

    19           typename Key,

    20           const Key& (GetKey)(const T&),

    21           uint32_t (Hash)(const Key&),

    22           bool (Equal)(const T&, const Key&)>

    23 class GrTMultiMap {

    24     struct ValueList {

    25         explicit ValueList(T* value) : fValue(value), fNext(NULL) {}

    27         static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); }

    28         static uint32_t ListHash(const Key& key) { return Hash(key); }

    29         static bool ListEqual(const ValueList& a, const Key& b) {

    30             return Equal(*a.fValue, b);

    31         }

    32         T* fValue;

    33         ValueList* fNext;

    34     };

    35 public:

    36     GrTMultiMap() : fCount(0) {}

    38     ~GrTMultiMap() {

    39         SkASSERT(fCount == 0);

    40         SkASSERT(fHash.count() == 0);

    41     }

    43     void insert(const Key& key, T* value) {

    44         ValueList* list = fHash.find(key);

    45         if (NULL != list) {

    46             // The new ValueList entry is inserted as the second element in the

    47             // linked list, and it will contain the value of the first element.

    48             ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue));

    49             newEntry->fNext = list->fNext;

    50             // The existing first ValueList entry is updated to contain the

    51             // inserted value.

    52             list->fNext = newEntry;

    53             list->fValue = value;

    54         } else {

    55             fHash.add(SkNEW_ARGS(ValueList, (value)));

    56         }

    58         ++fCount;

    59     }

    61     void remove(const Key& key, const T* value) {

    62         ValueList* list = fHash.find(key);

    63         // Since we expect the caller to be fully aware of what is stored, just

    64         // assert that the caller removes an existing value.

    65         SkASSERT(NULL != list);

    66         ValueList* prev = NULL;

    67         while (list->fValue != value) {

    68             prev = list;

    69             list = list->fNext;

    70         }

    72         if (NULL != list->fNext) {

    73             ValueList* next = list->fNext;

    74             list->fValue = next->fValue;

    75             list->fNext = next->fNext;

    76             SkDELETE(next);

    77         } else if (NULL != prev) {

    78             prev->fNext = NULL;

    79             SkDELETE(list);

    80         } else {

    81             fHash.remove(key);

    82             SkDELETE(list);

    83         }

    85         --fCount;

    86     }

    88     T* find(const Key& key) const {

    89         ValueList* list = fHash.find(key);

    90         if (NULL != list) {

    91             return list->fValue;

    92         }

    93         return NULL;

    94     }

    96     template<class FindPredicate>

    97     T* find(const Key& key, const FindPredicate f) {

    98         ValueList* list = fHash.find(key);

    99         while (NULL != list) {

   100             if (f(list->fValue)){

   101                 return list->fValue;

   102             }

   103             list = list->fNext;

   104         }

   105         return NULL;

   106     }

   108     int count() const { return fCount; }

   110 private:

   111     SkTDynamicHash<ValueList,

   112                    Key,

   113                    ValueList::ListGetKey,

   114                    ValueList::ListHash,

   115                    ValueList::ListEqual> fHash;

   116     int fCount;

   117 };

   119 #endif

The Tor Browser / file revision