third_party/WebKit/Source/wtf/HashCountedSet.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public License
  15  * along with this library; see the file COPYING.LIB.  If not, write to
  16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #ifndef WTF_HashCountedSet_h
  22 #define WTF_HashCountedSet_h
  23
  24 #include "wtf/Assertions.h"
  25 #include "wtf/HashMap.h"
  26 #include "wtf/Vector.h"
  27
  28 namespace WTF {
  29
  30     // An unordered hash set that keeps track of how many times you added an
  31     // item to the set. The iterators have fields ->key and ->value that return
  32     // the set members and their counts, respectively.
  33     template<
  34         typename Value,
  35         typename HashFunctions = typename DefaultHash<Value>::Hash,
  36         typename Traits = HashTraits<Value>,
  37         typename Allocator = DefaultAllocator > class HashCountedSet {
  38         WTF_USE_ALLOCATOR(HashCountedSet, Allocator);
  39     private:
  40         typedef HashMap<Value, unsigned, HashFunctions, Traits, HashTraits<unsigned>, Allocator> ImplType;
  41     public:
  42         typedef Value ValueType;
  43         typedef typename ImplType::iterator iterator;
  44         typedef typename ImplType::const_iterator const_iterator;
  45         typedef typename ImplType::AddResult AddResult;
  46
  47         HashCountedSet() {}
  48
  49         void swap(HashCountedSet& other) { m_impl.swap(other.m_impl); }
  50
  51         unsigned size() const { return m_impl.size(); }
  52         unsigned capacity() const { return m_impl.capacity(); }
  53         bool isEmpty() const { return m_impl.isEmpty(); }
  54
  55         // Iterators iterate over pairs of values (called key) and counts (called value).
  56         iterator begin() { return m_impl.begin(); }
  57         iterator end() { return m_impl.end(); }
  58         const_iterator begin() const { return m_impl.begin(); }
  59         const_iterator end() const { return m_impl.end(); }
  60
  61         iterator find(const ValueType& value) { return m_impl.find(value); }
  62         const_iterator find(const ValueType& value) const { return m_impl.find(value); }
  63         bool contains(const ValueType& value ) const { return m_impl.contains(value); }
  64         unsigned count(const ValueType& value ) const { return m_impl.get(value); }
  65
  66         // Increases the count if an equal value is already present
  67         // the return value is a pair of an iterator to the new value's
  68         // location, and a bool that is true if an new entry was added.
  69         AddResult add(const ValueType&);
  70
  71         // Reduces the count of the value, and removes it if count
  72         // goes down to zero, returns true if the value is removed.
  73         bool remove(const ValueType& value) { return remove(find(value)); }
  74         bool remove(iterator);
  75
  76         // Removes the value, regardless of its count.
  77         void removeAll(const ValueType& value) { removeAll(find(value)); }
  78         void removeAll(iterator);
  79
  80         // Clears the whole set.
  81         void clear() { m_impl.clear(); }
  82
  83         template<typename VisitorDispatcher>
  84         void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); }
  85
  86     private:
  87         ImplType m_impl;
  88     };
  89
  90     template<typename T, typename U, typename V, typename W>
  91     inline typename HashCountedSet<T, U, V, W>::AddResult HashCountedSet<T, U, V, W>::add(const ValueType& value)
  92     {
  93         AddResult result = m_impl.add(value, 0);
  94         ++result.storedValue->value;
  95         return result;
  96     }
  97
  98     template<typename T, typename U, typename V, typename W>
  99     inline bool HashCountedSet<T, U, V, W>::remove(iterator it)
 100     {
 101         if (it == end())
 102             return false;
 103
 104         unsigned oldVal = it->value;
 105         ASSERT(oldVal);
 106         unsigned newVal = oldVal - 1;
 107         if (newVal) {
 108             it->value = newVal;
 109             return false;
 110         }
 111
 112         m_impl.remove(it);
 113         return true;
 114     }
 115
 116     template<typename T, typename U, typename V, typename W>
 117     inline void HashCountedSet<T, U, V, W>::removeAll(iterator it)
 118     {
 119         if (it == end())
 120             return;
 121
 122         m_impl.remove(it);
 123     }
 124
 125     template<typename T, typename U, typename V, typename W, typename VectorType>
 126     inline void copyToVector(const HashCountedSet<T, U, V, W>& collection, VectorType& vector)
 127     {
 128         typedef typename HashCountedSet<T, U, V, W>::const_iterator iterator;
 129
 130         vector.resize(collection.size());
 131
 132         iterator it = collection.begin();
 133         iterator end = collection.end();
 134         for (unsigned i = 0; it != end; ++it, ++i)
 135             vector[i] = *it;
 136     }
 137
 138     template<typename Value, typename HashFunctions, typename Traits, typename Allocator, size_t inlineCapacity, typename VectorAllocator>
 139     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits, Allocator>& collection, Vector<Value, inlineCapacity, VectorAllocator>& vector)
 140     {
 141         typedef typename HashCountedSet<Value, HashFunctions, Traits, Allocator>::const_iterator iterator;
 142
 143         vector.resize(collection.size());
 144
 145         iterator it = collection.begin();
 146         iterator end = collection.end();
 147         for (unsigned i = 0; it != end; ++it, ++i)
 148             vector[i] = (*it).key;
 149     }
 150
 151 #if !ENABLE(OILPAN)
 152     template<typename T, typename U, typename V>
 153     struct NeedsTracing<HashCountedSet<T, U, V>> {
 154         static const bool value = false;
 155     };
 156 #endif
 157
 158 } // namespace WTF
 159
 160 using WTF::HashCountedSet;
 161
 162 #endif /* WTF_HashCountedSet_h */