| 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 18 matching lines...) Expand all Loading... |
| 29 | 29 |
| 30 // An unordered hash set that keeps track of how many times you added an item to | 30 // An unordered hash set that keeps track of how many times you added an item to |
| 31 // the set. The iterators have fields ->key and ->value that return the set | 31 // the set. The iterators have fields ->key and ->value that return the set |
| 32 // members and their counts, respectively. | 32 // members and their counts, respectively. |
| 33 template < | 33 template < |
| 34 typename Value, | 34 typename Value, |
| 35 typename HashFunctions = typename DefaultHash<Value>::Hash, | 35 typename HashFunctions = typename DefaultHash<Value>::Hash, |
| 36 typename Traits = HashTraits<Value>, | 36 typename Traits = HashTraits<Value>, |
| 37 typename Allocator = PartitionAllocator> | 37 typename Allocator = PartitionAllocator> |
| 38 class HashCountedSet { | 38 class HashCountedSet { |
| 39 WTF_USE_ALLOCATOR(HashCountedSet, Allocator); | 39 WTF_USE_ALLOCATOR(HashCountedSet, Allocator); |
| 40 private: | |
| 41 typedef HashMap<Value, unsigned, HashFunctions, Traits, HashTraits<unsigned>
, Allocator> ImplType; | |
| 42 public: | |
| 43 typedef Value ValueType; | |
| 44 typedef typename ImplType::iterator iterator; | |
| 45 typedef typename ImplType::const_iterator const_iterator; | |
| 46 typedef typename ImplType::AddResult AddResult; | |
| 47 | 40 |
| 48 HashCountedSet() {} | 41 private: |
| 42 typedef HashMap<Value, unsigned, HashFunctions, Traits, HashTraits<unsigned>,
Allocator> ImplType; |
| 49 | 43 |
| 50 void swap(HashCountedSet& other) { m_impl.swap(other.m_impl); } | 44 public: |
| 45 typedef Value ValueType; |
| 46 typedef typename ImplType::iterator iterator; |
| 47 typedef typename ImplType::const_iterator const_iterator; |
| 48 typedef typename ImplType::AddResult AddResult; |
| 51 | 49 |
| 52 unsigned size() const { return m_impl.size(); } | 50 HashCountedSet() {} |
| 53 unsigned capacity() const { return m_impl.capacity(); } | |
| 54 bool isEmpty() const { return m_impl.isEmpty(); } | |
| 55 | 51 |
| 56 // Iterators iterate over pairs of values (called key) and counts (called | 52 void swap(HashCountedSet& other) { m_impl.swap(other.m_impl); } |
| 57 // value). | |
| 58 iterator begin() { return m_impl.begin(); } | |
| 59 iterator end() { return m_impl.end(); } | |
| 60 const_iterator begin() const { return m_impl.begin(); } | |
| 61 const_iterator end() const { return m_impl.end(); } | |
| 62 | 53 |
| 63 iterator find(const ValueType& value) { return m_impl.find(value); } | 54 unsigned size() const { return m_impl.size(); } |
| 64 const_iterator find(const ValueType& value) const { return m_impl.find(value
); } | 55 unsigned capacity() const { return m_impl.capacity(); } |
| 65 bool contains(const ValueType& value ) const { return m_impl.contains(value)
; } | 56 bool isEmpty() const { return m_impl.isEmpty(); } |
| 66 unsigned count(const ValueType& value ) const { return m_impl.get(value); } | |
| 67 | 57 |
| 68 // Increases the count if an equal value is already present the return value | 58 // Iterators iterate over pairs of values (called key) and counts (called |
| 69 // is a pair of an iterator to the new value's location, and a bool that is | 59 // value). |
| 70 // true if an new entry was added. | 60 iterator begin() { return m_impl.begin(); } |
| 71 AddResult add(const ValueType&); | 61 iterator end() { return m_impl.end(); } |
| 62 const_iterator begin() const { return m_impl.begin(); } |
| 63 const_iterator end() const { return m_impl.end(); } |
| 72 | 64 |
| 73 // Reduces the count of the value, and removes it if count goes down to | 65 iterator find(const ValueType& value) { return m_impl.find(value); } |
| 74 // zero, returns true if the value is removed. | 66 const_iterator find(const ValueType& value) const { return m_impl.find(value);
} |
| 75 bool remove(const ValueType& value) { return remove(find(value)); } | 67 bool contains(const ValueType& value) const { return m_impl.contains(value); } |
| 76 bool remove(iterator); | 68 unsigned count(const ValueType& value) const { return m_impl.get(value); } |
| 77 | 69 |
| 78 // Removes the value, regardless of its count. | 70 // Increases the count if an equal value is already present the return value |
| 79 void removeAll(const ValueType& value) { removeAll(find(value)); } | 71 // is a pair of an iterator to the new value's location, and a bool that is |
| 80 void removeAll(iterator); | 72 // true if an new entry was added. |
| 73 AddResult add(const ValueType&); |
| 81 | 74 |
| 82 // Clears the whole set. | 75 // Reduces the count of the value, and removes it if count goes down to |
| 83 void clear() { m_impl.clear(); } | 76 // zero, returns true if the value is removed. |
| 77 bool remove(const ValueType& value) { return remove(find(value)); } |
| 78 bool remove(iterator); |
| 84 | 79 |
| 85 template <typename VisitorDispatcher> | 80 // Removes the value, regardless of its count. |
| 86 void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); } | 81 void removeAll(const ValueType& value) { removeAll(find(value)); } |
| 82 void removeAll(iterator); |
| 87 | 83 |
| 88 private: | 84 // Clears the whole set. |
| 89 ImplType m_impl; | 85 void clear() { m_impl.clear(); } |
| 86 |
| 87 template <typename VisitorDispatcher> |
| 88 void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); } |
| 89 |
| 90 private: |
| 91 ImplType m_impl; |
| 90 }; | 92 }; |
| 91 | 93 |
| 92 template <typename T, typename U, typename V, typename W> | 94 template <typename T, typename U, typename V, typename W> |
| 93 inline typename HashCountedSet<T, U, V, W>::AddResult HashCountedSet<T, U, V, W>
::add(const ValueType& value) | 95 inline typename HashCountedSet<T, U, V, W>::AddResult HashCountedSet<T, U, V, W>
::add(const ValueType& value) { |
| 94 { | 96 AddResult result = m_impl.add(value, 0); |
| 95 AddResult result = m_impl.add(value, 0); | 97 ++result.storedValue->value; |
| 96 ++result.storedValue->value; | 98 return result; |
| 97 return result; | |
| 98 } | 99 } |
| 99 | 100 |
| 100 template <typename T, typename U, typename V, typename W> | 101 template <typename T, typename U, typename V, typename W> |
| 101 inline bool HashCountedSet<T, U, V, W>::remove(iterator it) | 102 inline bool HashCountedSet<T, U, V, W>::remove(iterator it) { |
| 102 { | 103 if (it == end()) |
| 103 if (it == end()) | 104 return false; |
| 104 return false; | |
| 105 | 105 |
| 106 unsigned oldVal = it->value; | 106 unsigned oldVal = it->value; |
| 107 ASSERT(oldVal); | 107 ASSERT(oldVal); |
| 108 unsigned newVal = oldVal - 1; | 108 unsigned newVal = oldVal - 1; |
| 109 if (newVal) { | 109 if (newVal) { |
| 110 it->value = newVal; | 110 it->value = newVal; |
| 111 return false; | 111 return false; |
| 112 } | 112 } |
| 113 | 113 |
| 114 m_impl.remove(it); | 114 m_impl.remove(it); |
| 115 return true; | 115 return true; |
| 116 } | 116 } |
| 117 | 117 |
| 118 template <typename T, typename U, typename V, typename W> | 118 template <typename T, typename U, typename V, typename W> |
| 119 inline void HashCountedSet<T, U, V, W>::removeAll(iterator it) | 119 inline void HashCountedSet<T, U, V, W>::removeAll(iterator it) { |
| 120 { | 120 if (it == end()) |
| 121 if (it == end()) | 121 return; |
| 122 return; | |
| 123 | 122 |
| 124 m_impl.remove(it); | 123 m_impl.remove(it); |
| 125 } | 124 } |
| 126 | 125 |
| 127 template <typename T, typename U, typename V, typename W, typename VectorType> | 126 template <typename T, typename U, typename V, typename W, typename VectorType> |
| 128 inline void copyToVector(const HashCountedSet<T, U, V, W>& collection, VectorTyp
e& vector) | 127 inline void copyToVector(const HashCountedSet<T, U, V, W>& collection, VectorTyp
e& vector) { |
| 129 { | 128 typedef typename HashCountedSet<T, U, V, W>::const_iterator iterator; |
| 130 typedef typename HashCountedSet<T, U, V, W>::const_iterator iterator; | |
| 131 | 129 |
| 132 vector.resize(collection.size()); | 130 vector.resize(collection.size()); |
| 133 | 131 |
| 134 iterator it = collection.begin(); | 132 iterator it = collection.begin(); |
| 135 iterator end = collection.end(); | 133 iterator end = collection.end(); |
| 136 for (unsigned i = 0; it != end; ++it, ++i) | 134 for (unsigned i = 0; it != end; ++it, ++i) |
| 137 vector[i] = *it; | 135 vector[i] = *it; |
| 138 } | 136 } |
| 139 | 137 |
| 140 template <typename Value, typename HashFunctions, typename Traits, typename Allo
cator, size_t inlineCapacity, typename VectorAllocator> | 138 template <typename Value, typename HashFunctions, typename Traits, typename Allo
cator, size_t inlineCapacity, typename VectorAllocator> |
| 141 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits, Allo
cator>& collection, Vector<Value, inlineCapacity, VectorAllocator>& vector) | 139 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits, Allo
cator>& collection, Vector<Value, inlineCapacity, VectorAllocator>& vector) { |
| 142 { | 140 typedef typename HashCountedSet<Value, HashFunctions, Traits, Allocator>::cons
t_iterator iterator; |
| 143 typedef typename HashCountedSet<Value, HashFunctions, Traits, Allocator>::co
nst_iterator iterator; | |
| 144 | 141 |
| 145 vector.resize(collection.size()); | 142 vector.resize(collection.size()); |
| 146 | 143 |
| 147 iterator it = collection.begin(); | 144 iterator it = collection.begin(); |
| 148 iterator end = collection.end(); | 145 iterator end = collection.end(); |
| 149 for (unsigned i = 0; it != end; ++it, ++i) | 146 for (unsigned i = 0; it != end; ++it, ++i) |
| 150 vector[i] = (*it).key; | 147 vector[i] = (*it).key; |
| 151 } | 148 } |
| 152 | 149 |
| 153 #if !ENABLE(OILPAN) | 150 #if !ENABLE(OILPAN) |
| 154 template <typename T, typename U, typename V> | 151 template <typename T, typename U, typename V> |
| 155 struct NeedsTracing<HashCountedSet<T, U, V>> { | 152 struct NeedsTracing<HashCountedSet<T, U, V>> { |
| 156 static const bool value = false; | 153 static const bool value = false; |
| 157 }; | 154 }; |
| 158 #endif | 155 #endif |
| 159 | 156 |
| 160 } // namespace WTF | 157 } // namespace WTF |
| 161 | 158 |
| 162 using WTF::HashCountedSet; | 159 using WTF::HashCountedSet; |
| 163 | 160 |
| 164 #endif // WTF_HashCountedSet_h | 161 #endif // WTF_HashCountedSet_h |
| OLD | NEW |