| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 RefPtrHashMap_h | |
| 22 #define RefPtrHashMap_h | |
| 23 | |
| 24 namespace WTF { | |
| 25 | |
| 26 // This specialization is a copy of HashMap for use with RefPtr keys, with o
verloaded functions | |
| 27 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count chur
n. | |
| 28 | |
| 29 // FIXME: Find a way to do this with traits that doesn't require a copy of
the HashMap template. | |
| 30 | |
| 31 template<typename T, typename MappedArg, typename HashArg, typename KeyTrait
sArg, typename MappedTraitsArg> | |
| 32 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>
{ | |
| 33 WTF_MAKE_FAST_ALLOCATED; | |
| 34 private: | |
| 35 typedef KeyTraitsArg KeyTraits; | |
| 36 typedef MappedTraitsArg MappedTraits; | |
| 37 typedef KeyValuePairHashTraits<KeyTraits, MappedTraits> ValueTraits; | |
| 38 | |
| 39 public: | |
| 40 typedef typename KeyTraits::TraitType KeyType; | |
| 41 typedef T* RawKeyType; | |
| 42 typedef typename MappedTraits::TraitType MappedType; | |
| 43 typedef typename ValueTraits::TraitType ValueType; | |
| 44 | |
| 45 private: | |
| 46 typedef typename MappedTraits::PassInType MappedPassInType; | |
| 47 typedef typename MappedTraits::PassOutType MappedPassOutType; | |
| 48 typedef typename MappedTraits::PeekType MappedPeekType; | |
| 49 | |
| 50 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; | |
| 51 | |
| 52 typedef HashArg HashFunctions; | |
| 53 | |
| 54 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType
>, | |
| 55 HashFunctions, ValueTraits, KeyTraits> HashTableType; | |
| 56 | |
| 57 typedef HashMapTranslator<ValueTraits, HashFunctions> | |
| 58 Translator; | |
| 59 | |
| 60 public: | |
| 61 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; | |
| 62 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_it
erator; | |
| 63 typedef typename HashTableType::AddResult AddResult; | |
| 64 | |
| 65 void swap(HashMap&); | |
| 66 | |
| 67 int size() const; | |
| 68 int capacity() const; | |
| 69 bool isEmpty() const; | |
| 70 | |
| 71 // iterators iterate over pairs of keys and values | |
| 72 iterator begin(); | |
| 73 iterator end(); | |
| 74 const_iterator begin() const; | |
| 75 const_iterator end() const; | |
| 76 | |
| 77 iterator find(const KeyType&); | |
| 78 iterator find(RawKeyType); | |
| 79 const_iterator find(const KeyType&) const; | |
| 80 const_iterator find(RawKeyType) const; | |
| 81 bool contains(const KeyType&) const; | |
| 82 bool contains(RawKeyType) const; | |
| 83 MappedPeekType get(const KeyType&) const; | |
| 84 MappedPeekType get(RawKeyType) const; | |
| 85 MappedPeekType inlineGet(RawKeyType) const; | |
| 86 | |
| 87 // replaces value but not key if key is already present | |
| 88 // return value is a pair of the iterator to the key location, | |
| 89 // and a boolean that's true if a new value was actually added | |
| 90 AddResult set(const KeyType&, MappedPassInType); | |
| 91 AddResult set(RawKeyType, MappedPassInType); | |
| 92 | |
| 93 // does nothing if key is already present | |
| 94 // return value is a pair of the iterator to the key location, | |
| 95 // and a boolean that's true if a new value was actually added | |
| 96 AddResult add(const KeyType&, MappedPassInType); | |
| 97 AddResult add(RawKeyType, MappedPassInType); | |
| 98 | |
| 99 void remove(const KeyType&); | |
| 100 void remove(RawKeyType); | |
| 101 void remove(iterator); | |
| 102 void clear(); | |
| 103 | |
| 104 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove | |
| 105 MappedPassOutType take(RawKeyType); // efficient combination of get with
remove | |
| 106 | |
| 107 private: | |
| 108 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); | |
| 109 AddResult inlineAdd(RawKeyType, MappedPassInReferenceType); | |
| 110 | |
| 111 HashTableType m_impl; | |
| 112 }; | |
| 113 | |
| 114 template<typename T, typename U, typename V, typename W, typename X> | |
| 115 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other) | |
| 116 { | |
| 117 m_impl.swap(other.m_impl); | |
| 118 } | |
| 119 | |
| 120 template<typename T, typename U, typename V, typename W, typename X> | |
| 121 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const | |
| 122 { | |
| 123 return m_impl.size(); | |
| 124 } | |
| 125 | |
| 126 template<typename T, typename U, typename V, typename W, typename X> | |
| 127 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const | |
| 128 { | |
| 129 return m_impl.capacity(); | |
| 130 } | |
| 131 | |
| 132 template<typename T, typename U, typename V, typename W, typename X> | |
| 133 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const | |
| 134 { | |
| 135 return m_impl.isEmpty(); | |
| 136 } | |
| 137 | |
| 138 template<typename T, typename U, typename V, typename W, typename X> | |
| 139 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::begin() | |
| 140 { | |
| 141 return m_impl.begin(); | |
| 142 } | |
| 143 | |
| 144 template<typename T, typename U, typename V, typename W, typename X> | |
| 145 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::end() | |
| 146 { | |
| 147 return m_impl.end(); | |
| 148 } | |
| 149 | |
| 150 template<typename T, typename U, typename V, typename W, typename X> | |
| 151 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPt
r<T>, U, V, W, X>::begin() const | |
| 152 { | |
| 153 return m_impl.begin(); | |
| 154 } | |
| 155 | |
| 156 template<typename T, typename U, typename V, typename W, typename X> | |
| 157 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPt
r<T>, U, V, W, X>::end() const | |
| 158 { | |
| 159 return m_impl.end(); | |
| 160 } | |
| 161 | |
| 162 template<typename T, typename U, typename V, typename W, typename X> | |
| 163 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::find(const KeyType& key) | |
| 164 { | |
| 165 return m_impl.find(key); | |
| 166 } | |
| 167 | |
| 168 template<typename T, typename U, typename V, typename W, typename X> | |
| 169 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::find(RawKeyType key) | |
| 170 { | |
| 171 return m_impl.template find<Translator>(key); | |
| 172 } | |
| 173 | |
| 174 template<typename T, typename U, typename V, typename W, typename X> | |
| 175 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPt
r<T>, U, V, W, X>::find(const KeyType& key) const | |
| 176 { | |
| 177 return m_impl.find(key); | |
| 178 } | |
| 179 | |
| 180 template<typename T, typename U, typename V, typename W, typename X> | |
| 181 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPt
r<T>, U, V, W, X>::find(RawKeyType key) const | |
| 182 { | |
| 183 return m_impl.template find<Translator>(key); | |
| 184 } | |
| 185 | |
| 186 template<typename T, typename U, typename V, typename W, typename X> | |
| 187 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) con
st | |
| 188 { | |
| 189 return m_impl.contains(key); | |
| 190 } | |
| 191 | |
| 192 template<typename T, typename U, typename V, typename W, typename X> | |
| 193 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const | |
| 194 { | |
| 195 return m_impl.template contains<Translator>(key); | |
| 196 } | |
| 197 | |
| 198 template<typename T, typename U, typename V, typename W, typename X> | |
| 199 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 200 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInRe
ferenceType mapped) | |
| 201 { | |
| 202 return m_impl.template add<Translator>(key, mapped); | |
| 203 } | |
| 204 | |
| 205 template<typename T, typename U, typename V, typename W, typename X> | |
| 206 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 207 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInRefere
nceType mapped) | |
| 208 { | |
| 209 return m_impl.template add<Translator>(key, mapped); | |
| 210 } | |
| 211 | |
| 212 template<typename T, typename U, typename V, typename W, typename X> | |
| 213 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 214 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, MappedPassInType map
ped) | |
| 215 { | |
| 216 AddResult result = inlineAdd(key, mapped); | |
| 217 if (!result.isNewEntry) { | |
| 218 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | |
| 219 MappedTraits::store(mapped, result.iterator->value); | |
| 220 } | |
| 221 return result; | |
| 222 } | |
| 223 | |
| 224 template<typename T, typename U, typename V, typename W, typename X> | |
| 225 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 226 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, MappedPassInType mapped)
| |
| 227 { | |
| 228 AddResult result = inlineAdd(key, mapped); | |
| 229 if (!result.isNewEntry) { | |
| 230 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | |
| 231 MappedTraits::store(mapped, result.iterator->value); | |
| 232 } | |
| 233 return result; | |
| 234 } | |
| 235 | |
| 236 template<typename T, typename U, typename V, typename W, typename X> | |
| 237 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 238 HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, MappedPassInType map
ped) | |
| 239 { | |
| 240 return inlineAdd(key, mapped); | |
| 241 } | |
| 242 | |
| 243 template<typename T, typename U, typename V, typename W, typename X> | |
| 244 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | |
| 245 HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, MappedPassInType mapped) | |
| 246 { | |
| 247 return inlineAdd(key, mapped); | |
| 248 } | |
| 249 | |
| 250 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
| 251 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType | |
| 252 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const | |
| 253 { | |
| 254 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); | |
| 255 if (!entry) | |
| 256 return MappedTraits::peek(MappedTraits::emptyValue()); | |
| 257 return MappedTraits::peek(entry->value); | |
| 258 } | |
| 259 | |
| 260 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
| 261 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType | |
| 262 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key)
const | |
| 263 { | |
| 264 ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<Tr
anslator>(key); | |
| 265 if (!entry) | |
| 266 return MappedTraits::peek(MappedTraits::emptyValue()); | |
| 267 return MappedTraits::peek(entry->value); | |
| 268 } | |
| 269 | |
| 270 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
| 271 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType | |
| 272 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const | |
| 273 { | |
| 274 return inlineGet(key); | |
| 275 } | |
| 276 | |
| 277 template<typename T, typename U, typename V, typename W, typename X> | |
| 278 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it) | |
| 279 { | |
| 280 if (it.m_impl == m_impl.end()) | |
| 281 return; | |
| 282 m_impl.internalCheckTableConsistency(); | |
| 283 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); | |
| 284 } | |
| 285 | |
| 286 template<typename T, typename U, typename V, typename W, typename X> | |
| 287 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key) | |
| 288 { | |
| 289 remove(find(key)); | |
| 290 } | |
| 291 | |
| 292 template<typename T, typename U, typename V, typename W, typename X> | |
| 293 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key) | |
| 294 { | |
| 295 remove(find(key)); | |
| 296 } | |
| 297 | |
| 298 template<typename T, typename U, typename V, typename W, typename X> | |
| 299 inline void HashMap<RefPtr<T>, U, V, W, X>::clear() | |
| 300 { | |
| 301 m_impl.clear(); | |
| 302 } | |
| 303 | |
| 304 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
| 305 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType | |
| 306 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key) | |
| 307 { | |
| 308 iterator it = find(key); | |
| 309 if (it == end()) | |
| 310 return MappedTraits::passOut(MappedTraits::emptyValue()); | |
| 311 MappedPassOutType result = MappedTraits::passOut(it->value); | |
| 312 remove(it); | |
| 313 return result; | |
| 314 } | |
| 315 | |
| 316 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
| 317 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType | |
| 318 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key) | |
| 319 { | |
| 320 iterator it = find(key); | |
| 321 if (it == end()) | |
| 322 return MappedTraits::passOut(MappedTraits::emptyValue()); | |
| 323 MappedPassOutType result = MappedTraits::passOut(it->value); | |
| 324 remove(it); | |
| 325 return result; | |
| 326 } | |
| 327 | |
| 328 } // namespace WTF | |
| 329 | |
| 330 #endif // RefPtrHashMap_h | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 14238015:
Move Source/WTF/wtf to Source/wtf (Closed)
Base URL: svn://svn.chromium.org/blink/trunk