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 HashCountedSet()47 HashCountedSet() {} 48 swap(HashCountedSet & other)49 void swap(HashCountedSet& other) { m_impl.swap(other.m_impl); } 50 size()51 unsigned size() const { return m_impl.size(); } capacity()52 unsigned capacity() const { return m_impl.capacity(); } isEmpty()53 bool isEmpty() const { return m_impl.isEmpty(); } 54 55 // Iterators iterate over pairs of values (called key) and counts (called value). begin()56 iterator begin() { return m_impl.begin(); } end()57 iterator end() { return m_impl.end(); } begin()58 const_iterator begin() const { return m_impl.begin(); } end()59 const_iterator end() const { return m_impl.end(); } 60 find(const ValueType & value)61 iterator find(const ValueType& value) { return m_impl.find(value); } find(const ValueType & value)62 const_iterator find(const ValueType& value) const { return m_impl.find(value); } contains(const ValueType & value)63 bool contains(const ValueType& value ) const { return m_impl.contains(value); } count(const ValueType & 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. remove(const ValueType & value)73 bool remove(const ValueType& value) { return remove(find(value)); } 74 bool remove(iterator); 75 76 // Removes the value, regardless of its count. removeAll(const ValueType & value)77 void removeAll(const ValueType& value) { removeAll(find(value)); } 78 void removeAll(iterator); 79 80 // Clears the whole set. clear()81 void clear() { m_impl.clear(); } 82 trace(typename Allocator::Visitor * visitor)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> add(const ValueType & value)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> remove(iterator it)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> removeAll(iterator it)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> copyToVector(const HashCountedSet<T,U,V,W> & collection,VectorType & vector)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> copyToVector(const HashCountedSet<Value,HashFunctions,Traits,Allocator> & collection,Vector<Value,inlineCapacity,VectorAllocator> & vector)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 */ 156