src/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         void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); }
  84
  85     private:
  86         ImplType m_impl;
  87     };
  88
  89     template<typename T, typename U, typename V, typename W>
  90     inline typename HashCountedSet<T, U, V, W>::AddResult HashCountedSet<T, U, V, W>::add(const ValueType& value)
  91     {
  92         AddResult result = m_impl.add(value, 0);
  93         ++result.storedValue->value;
  94         return result;
  95     }
  96
  97     template<typename T, typename U, typename V, typename W>
  98     inline bool HashCountedSet<T, U, V, W>::remove(iterator it)
  99     {
 100         if (it == end())
 101             return false;
 102
 103         unsigned oldVal = it->value;
 104         ASSERT(oldVal);
 105         unsigned newVal = oldVal - 1;
 106         if (newVal) {
 107             it->value = newVal;
 108             return false;
 109         }
 110
 111         m_impl.remove(it);
 112         return true;
 113     }
 114
 115     template<typename T, typename U, typename V, typename W>
 116     inline void HashCountedSet<T, U, V, W>::removeAll(iterator it)
 117     {
 118         if (it == end())
 119             return;
 120
 121         m_impl.remove(it);
 122     }
 123
 124     template<typename T, typename U, typename V, typename W, typename VectorType>
 125     inline void copyToVector(const HashCountedSet<T, U, V, W>& collection, VectorType& vector)
 126     {
 127         typedef typename HashCountedSet<T, U, V, W>::const_iterator iterator;
 128
 129         vector.resize(collection.size());
 130
 131         iterator it = collection.begin();
 132         iterator end = collection.end();
 133         for (unsigned i = 0; it != end; ++it, ++i)
 134             vector[i] = *it;
 135     }
 136
 137     template<typename Value, typename HashFunctions, typename Traits, typename Allocator, size_t inlineCapacity, typename VectorAllocator>
 138     inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits, Allocator>& collection, Vector<Value, inlineCapacity, VectorAllocator>& vector)
 139     {
 140         typedef typename HashCountedSet<Value, HashFunctions, Traits, Allocator>::const_iterator iterator;
 141
 142         vector.resize(collection.size());
 143
 144         iterator it = collection.begin();
 145         iterator end = collection.end();
 146         for (unsigned i = 0; it != end; ++it, ++i)
 147             vector[i] = (*it).key;
 148     }
 149
 150
 151 } // namespace WTF
 152
 153 using WTF::HashCountedSet;
 154
 155 #endif /* WTF_HashCountedSet_h */