| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
| 5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
| 6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
| 7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
| 8 * | 8 * |
| 9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| (...skipping 19 matching lines...) Expand all Loading... |
| 30 template<typename Value, typename HashFunctions = typename DefaultHash<Value
>::Hash, | 30 template<typename Value, typename HashFunctions = typename DefaultHash<Value
>::Hash, |
| 31 typename Traits = HashTraits<Value> > class HashCountedSet { | 31 typename Traits = HashTraits<Value> > class HashCountedSet { |
| 32 WTF_MAKE_FAST_ALLOCATED; | 32 WTF_MAKE_FAST_ALLOCATED; |
| 33 private: | 33 private: |
| 34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType; | 34 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType; |
| 35 public: | 35 public: |
| 36 typedef Value ValueType; | 36 typedef Value ValueType; |
| 37 typedef typename ImplType::iterator iterator; | 37 typedef typename ImplType::iterator iterator; |
| 38 typedef typename ImplType::const_iterator const_iterator; | 38 typedef typename ImplType::const_iterator const_iterator; |
| 39 typedef typename ImplType::AddResult AddResult; | 39 typedef typename ImplType::AddResult AddResult; |
| 40 | 40 |
| 41 HashCountedSet() {} | 41 HashCountedSet() {} |
| 42 | 42 |
| 43 void swap(HashCountedSet&); | 43 void swap(HashCountedSet&); |
| 44 | 44 |
| 45 int size() const; | 45 int size() const; |
| 46 int capacity() const; | 46 int capacity() const; |
| 47 bool isEmpty() const; | 47 bool isEmpty() const; |
| 48 | 48 |
| 49 // Iterators iterate over pairs of values and counts. | 49 // Iterators iterate over pairs of values and counts. |
| 50 iterator begin(); | 50 iterator begin(); |
| 51 iterator end(); | 51 iterator end(); |
| 52 const_iterator begin() const; | 52 const_iterator begin() const; |
| 53 const_iterator end() const; | 53 const_iterator end() const; |
| 54 | 54 |
| 55 iterator find(const ValueType&); | 55 iterator find(const ValueType&); |
| 56 const_iterator find(const ValueType&) const; | 56 const_iterator find(const ValueType&) const; |
| 57 bool contains(const ValueType&) const; | 57 bool contains(const ValueType&) const; |
| 58 unsigned count(const ValueType&) const; | 58 unsigned count(const ValueType&) const; |
| 59 | 59 |
| 60 // Increases the count if an equal value is already present | 60 // Increases the count if an equal value is already present |
| 61 // the return value is a pair of an interator to the new value's | 61 // the return value is a pair of an interator to the new value's |
| 62 // location, and a bool that is true if an new entry was added. | 62 // location, and a bool that is true if an new entry was added. |
| 63 AddResult add(const ValueType&); | 63 AddResult add(const ValueType&); |
| 64 | 64 |
| 65 // Reduces the count of the value, and removes it if count | 65 // Reduces the count of the value, and removes it if count |
| 66 // goes down to zero, returns true if the value is removed. | 66 // goes down to zero, returns true if the value is removed. |
| 67 bool remove(const ValueType&); | 67 bool remove(const ValueType&); |
| 68 bool remove(iterator); | 68 bool remove(iterator); |
| 69 | 69 |
| 70 // Removes the value, regardless of its count. | 70 // Removes the value, regardless of its count. |
| 71 void removeAll(iterator); | 71 void removeAll(iterator); |
| 72 void removeAll(const ValueType&); | 72 void removeAll(const ValueType&); |
| 73 | 73 |
| 74 // Clears the whole set. | 74 // Clears the whole set. |
| 75 void clear(); | 75 void clear(); |
| 76 | 76 |
| 77 private: | 77 private: |
| 78 ImplType m_impl; | 78 ImplType m_impl; |
| 79 }; | 79 }; |
| 80 | 80 |
| 81 template<typename Value, typename HashFunctions, typename Traits> | 81 template<typename Value, typename HashFunctions, typename Traits> |
| 82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSe
t& other) | 82 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSe
t& other) |
| 83 { | 83 { |
| 84 m_impl.swap(other.m_impl); | 84 m_impl.swap(other.m_impl); |
| 85 } | 85 } |
| 86 | 86 |
| 87 template<typename Value, typename HashFunctions, typename Traits> | 87 template<typename Value, typename HashFunctions, typename Traits> |
| 88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const | 88 inline int HashCountedSet<Value, HashFunctions, Traits>::size() const |
| 89 { | 89 { |
| 90 return m_impl.size(); | 90 return m_impl.size(); |
| 91 } | 91 } |
| 92 | 92 |
| 93 template<typename Value, typename HashFunctions, typename Traits> | 93 template<typename Value, typename HashFunctions, typename Traits> |
| 94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const | 94 inline int HashCountedSet<Value, HashFunctions, Traits>::capacity() const |
| 95 { | 95 { |
| 96 return m_impl.capacity(); | 96 return m_impl.capacity(); |
| 97 } | 97 } |
| 98 | 98 |
| 99 template<typename Value, typename HashFunctions, typename Traits> | 99 template<typename Value, typename HashFunctions, typename Traits> |
| 100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const | 100 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const |
| 101 { | 101 { |
| 102 return size() == 0; | 102 return size() == 0; |
| 103 } | 103 } |
| 104 | 104 |
| 105 template<typename Value, typename HashFunctions, typename Traits> | 105 template<typename Value, typename HashFunctions, typename Traits> |
| 106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::begin() | 106 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::begin() |
| 107 { | 107 { |
| 108 return m_impl.begin(); | 108 return m_impl.begin(); |
| 109 } | 109 } |
| 110 | 110 |
| 111 template<typename Value, typename HashFunctions, typename Traits> | 111 template<typename Value, typename HashFunctions, typename Traits> |
| 112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::end() | 112 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::end() |
| 113 { | 113 { |
| 114 return m_impl.end(); | 114 return m_impl.end(); |
| 115 } | 115 } |
| 116 | 116 |
| 117 template<typename Value, typename HashFunctions, typename Traits> | 117 template<typename Value, typename HashFunctions, typename Traits> |
| 118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::begin() const | 118 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::begin() const |
| 119 { | 119 { |
| 120 return m_impl.begin(); | 120 return m_impl.begin(); |
| 121 } | 121 } |
| 122 | 122 |
| 123 template<typename Value, typename HashFunctions, typename Traits> | 123 template<typename Value, typename HashFunctions, typename Traits> |
| 124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::end() const | 124 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::end() const |
| 125 { | 125 { |
| 126 return m_impl.end(); | 126 return m_impl.end(); |
| 127 } | 127 } |
| 128 | 128 |
| 129 template<typename Value, typename HashFunctions, typename Traits> | 129 template<typename Value, typename HashFunctions, typename Traits> |
| 130 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) | 130 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashC
ountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) |
| 131 { | 131 { |
| 132 return m_impl.find(value); | 132 return m_impl.find(value); |
| 133 } | 133 } |
| 134 | 134 |
| 135 template<typename Value, typename HashFunctions, typename Traits> | 135 template<typename Value, typename HashFunctions, typename Traits> |
| 136 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) cons
t | 136 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator
HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) cons
t |
| 137 { | 137 { |
| 138 return m_impl.find(value); | 138 return m_impl.find(value); |
| 139 } | 139 } |
| 140 | 140 |
| 141 template<typename Value, typename HashFunctions, typename Traits> | 141 template<typename Value, typename HashFunctions, typename Traits> |
| 142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const Val
ueType& value) const | 142 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const Val
ueType& value) const |
| 143 { | 143 { |
| 144 return m_impl.contains(value); | 144 return m_impl.contains(value); |
| 145 } | 145 } |
| 146 | 146 |
| 147 template<typename Value, typename HashFunctions, typename Traits> | 147 template<typename Value, typename HashFunctions, typename Traits> |
| 148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const Va
lueType& value) const | 148 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const Va
lueType& value) const |
| 149 { | 149 { |
| 150 return m_impl.get(value); | 150 return m_impl.get(value); |
| 151 } | 151 } |
| 152 | 152 |
| 153 template<typename Value, typename HashFunctions, typename Traits> | 153 template<typename Value, typename HashFunctions, typename Traits> |
| 154 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult Hash
CountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) | 154 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult Hash
CountedSet<Value, HashFunctions, Traits>::add(const ValueType &value) |
| 155 { | 155 { |
| 156 AddResult result = m_impl.add(value, 0); | 156 AddResult result = m_impl.add(value, 0); |
| 157 ++result.iterator->value; | 157 ++result.iterator->value; |
| 158 return result; | 158 return result; |
| 159 } | 159 } |
| 160 | 160 |
| 161 template<typename Value, typename HashFunctions, typename Traits> | 161 template<typename Value, typename HashFunctions, typename Traits> |
| 162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const Value
Type& value) | 162 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const Value
Type& value) |
| 163 { | 163 { |
| 164 return remove(find(value)); | 164 return remove(find(value)); |
| 165 } | 165 } |
| 166 | 166 |
| 167 template<typename Value, typename HashFunctions, typename Traits> | 167 template<typename Value, typename HashFunctions, typename Traits> |
| 168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it
) | 168 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it
) |
| 169 { | 169 { |
| 170 if (it == end()) | 170 if (it == end()) |
| 171 return false; | 171 return false; |
| 172 | 172 |
| 173 unsigned oldVal = it->value; | 173 unsigned oldVal = it->value; |
| 174 ASSERT(oldVal); | 174 ASSERT(oldVal); |
| 175 unsigned newVal = oldVal - 1; | 175 unsigned newVal = oldVal - 1; |
| 176 if (newVal) { | 176 if (newVal) { |
| 177 it->value = newVal; | 177 it->value = newVal; |
| 178 return false; | 178 return false; |
| 179 } | 179 } |
| 180 | 180 |
| 181 m_impl.remove(it); | 181 m_impl.remove(it); |
| 182 return true; | 182 return true; |
| 183 } | 183 } |
| 184 | 184 |
| 185 template<typename Value, typename HashFunctions, typename Traits> | 185 template<typename Value, typename HashFunctions, typename Traits> |
| 186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const Va
lueType& value) | 186 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(const Va
lueType& value) |
| 187 { | 187 { |
| 188 removeAll(find(value)); | 188 removeAll(find(value)); |
| 189 } | 189 } |
| 190 | 190 |
| 191 template<typename Value, typename HashFunctions, typename Traits> | 191 template<typename Value, typename HashFunctions, typename Traits> |
| 192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator
it) | 192 inline void HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator
it) |
| 193 { | 193 { |
| 194 if (it == end()) | 194 if (it == end()) |
| 195 return; | 195 return; |
| 196 | 196 |
| 197 m_impl.remove(it); | 197 m_impl.remove(it); |
| 198 } | 198 } |
| 199 | 199 |
| 200 template<typename Value, typename HashFunctions, typename Traits> | 200 template<typename Value, typename HashFunctions, typename Traits> |
| 201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() | 201 inline void HashCountedSet<Value, HashFunctions, Traits>::clear() |
| 202 { | 202 { |
| 203 m_impl.clear(); | 203 m_impl.clear(); |
| 204 } | 204 } |
| 205 | 205 |
| 206 template<typename Value, typename HashFunctions, typename Traits, typename V
ectorType> | 206 template<typename Value, typename HashFunctions, typename Traits, typename V
ectorType> |
| 207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, VectorType& vector) | 207 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, VectorType& vector) |
| 208 { | 208 { |
| 209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; | 209 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; |
| 210 | 210 |
| 211 vector.resize(collection.size()); | 211 vector.resize(collection.size()); |
| 212 | 212 |
| 213 iterator it = collection.begin(); | 213 iterator it = collection.begin(); |
| 214 iterator end = collection.end(); | 214 iterator end = collection.end(); |
| 215 for (unsigned i = 0; it != end; ++it, ++i) | 215 for (unsigned i = 0; it != end; ++it, ++i) |
| 216 vector[i] = *it; | 216 vector[i] = *it; |
| 217 } | 217 } |
| 218 | 218 |
| 219 template<typename Value, typename HashFunctions, typename Traits> | 219 template<typename Value, typename HashFunctions, typename Traits> |
| 220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, Vector<Value>& vector) | 220 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>&
collection, Vector<Value>& vector) |
| 221 { | 221 { |
| 222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; | 222 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_ite
rator iterator; |
| 223 | 223 |
| 224 vector.resize(collection.size()); | 224 vector.resize(collection.size()); |
| 225 | 225 |
| 226 iterator it = collection.begin(); | 226 iterator it = collection.begin(); |
| 227 iterator end = collection.end(); | 227 iterator end = collection.end(); |
| 228 for (unsigned i = 0; it != end; ++it, ++i) | 228 for (unsigned i = 0; it != end; ++it, ++i) |
| 229 vector[i] = (*it).key; | 229 vector[i] = (*it).key; |
| 230 } | 230 } |
| 231 | 231 |
| 232 | 232 |
| 233 } // namespace khtml | 233 } // namespace khtml |
| 234 | 234 |
| 235 using WTF::HashCountedSet; | 235 using WTF::HashCountedSet; |
| 236 | 236 |
| 237 #endif /* WTF_HashCountedSet_h */ | 237 #endif /* WTF_HashCountedSet_h */ |
| OLD | NEW |