File indexing completed on 2024-05-12 15:43:40
0001 /* 0002 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 0003 * 0004 * This library is free software; you can redistribute it and/or 0005 * modify it under the terms of the GNU Library General Public 0006 * License as published by the Free Software Foundation; either 0007 * version 2 of the License, or (at your option) any later version. 0008 * 0009 * This library is distributed in the hope that it will be useful, 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 * Library General Public License for more details. 0013 * 0014 * You should have received a copy of the GNU Library General Public License 0015 * along with this library; see the file COPYING.LIB. If not, write to 0016 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 * Boston, MA 02110-1301, USA. 0018 * 0019 */ 0020 0021 #ifndef REFPTRHASHMAP_H 0022 #define REFPTRHASHMAP_H 0023 0024 namespace WTF 0025 { 0026 0027 // This specialization is a direct copy of HashMap, with overloaded functions 0028 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn. 0029 0030 // FIXME: Find a better way that doesn't require an entire copy of the HashMap template. 0031 0032 template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions> 0033 struct RefPtrHashMapRawKeyTranslator { 0034 typedef typename ValueType::first_type KeyType; 0035 typedef typename ValueType::second_type MappedType; 0036 typedef typename ValueTraits::FirstTraits KeyTraits; 0037 typedef typename ValueTraits::SecondTraits MappedTraits; 0038 0039 static unsigned hash(RawKeyType key) 0040 { 0041 return HashFunctions::hash(key); 0042 } 0043 static bool equal(const KeyType &a, RawKeyType b) 0044 { 0045 return HashFunctions::equal(a, b); 0046 } 0047 static void translate(ValueType &location, RawKeyType key, const MappedType &mapped) 0048 { 0049 location.first = key; 0050 location.second = mapped; 0051 } 0052 }; 0053 0054 template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 0055 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> 0056 { 0057 private: 0058 typedef KeyTraitsArg KeyTraits; 0059 typedef MappedTraitsArg MappedTraits; 0060 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 0061 0062 public: 0063 typedef typename KeyTraits::TraitType KeyType; 0064 typedef T *RawKeyType; 0065 typedef typename MappedTraits::TraitType MappedType; 0066 typedef typename ValueTraits::TraitType ValueType; 0067 0068 private: 0069 typedef HashArg HashFunctions; 0070 0071 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 0072 HashFunctions, ValueTraits, KeyTraits> HashTableType; 0073 0074 typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions> 0075 RawKeyTranslator; 0076 0077 public: 0078 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 0079 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 0080 0081 void swap(HashMap &); 0082 0083 int size() const; 0084 int capacity() const; 0085 bool isEmpty() const; 0086 0087 // iterators iterate over pairs of keys and values 0088 iterator begin(); 0089 iterator end(); 0090 const_iterator begin() const; 0091 const_iterator end() const; 0092 0093 iterator find(const KeyType &); 0094 iterator find(RawKeyType); 0095 const_iterator find(const KeyType &) const; 0096 const_iterator find(RawKeyType) const; 0097 bool contains(const KeyType &) const; 0098 bool contains(RawKeyType) const; 0099 MappedType get(const KeyType &) const; 0100 MappedType get(RawKeyType) const; 0101 MappedType inlineGet(RawKeyType) const; 0102 0103 // replaces value but not key if key is already present 0104 // return value is a pair of the iterator to the key location, 0105 // and a boolean that's true if a new value was actually added 0106 pair<iterator, bool> set(const KeyType &, const MappedType &); 0107 pair<iterator, bool> set(RawKeyType, const MappedType &); 0108 0109 // does nothing if key is already present 0110 // return value is a pair of the iterator to the key location, 0111 // and a boolean that's true if a new value was actually added 0112 pair<iterator, bool> add(const KeyType &, const MappedType &); 0113 pair<iterator, bool> add(RawKeyType, const MappedType &); 0114 0115 void remove(const KeyType &); 0116 void remove(RawKeyType); 0117 void remove(iterator); 0118 void clear(); 0119 0120 MappedType take(const KeyType &); // efficient combination of get with remove 0121 MappedType take(RawKeyType); // efficient combination of get with remove 0122 0123 private: 0124 pair<iterator, bool> inlineAdd(const KeyType &, const MappedType &); 0125 pair<iterator, bool> inlineAdd(RawKeyType, const MappedType &); 0126 0127 HashTableType m_impl; 0128 }; 0129 0130 template<typename T, typename U, typename V, typename W, typename X> 0131 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap &other) 0132 { 0133 m_impl.swap(other.m_impl); 0134 } 0135 0136 template<typename T, typename U, typename V, typename W, typename X> 0137 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const 0138 { 0139 return m_impl.size(); 0140 } 0141 0142 template<typename T, typename U, typename V, typename W, typename X> 0143 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const 0144 { 0145 return m_impl.capacity(); 0146 } 0147 0148 template<typename T, typename U, typename V, typename W, typename X> 0149 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const 0150 { 0151 return m_impl.isEmpty(); 0152 } 0153 0154 template<typename T, typename U, typename V, typename W, typename X> 0155 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin() 0156 { 0157 return m_impl.begin(); 0158 } 0159 0160 template<typename T, typename U, typename V, typename W, typename X> 0161 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end() 0162 { 0163 return m_impl.end(); 0164 } 0165 0166 template<typename T, typename U, typename V, typename W, typename X> 0167 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const 0168 { 0169 return m_impl.begin(); 0170 } 0171 0172 template<typename T, typename U, typename V, typename W, typename X> 0173 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const 0174 { 0175 return m_impl.end(); 0176 } 0177 0178 template<typename T, typename U, typename V, typename W, typename X> 0179 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType &key) 0180 { 0181 return m_impl.find(key); 0182 } 0183 0184 template<typename T, typename U, typename V, typename W, typename X> 0185 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) 0186 { 0187 return m_impl.template find<RawKeyType, RawKeyTranslator>(key); 0188 } 0189 0190 template<typename T, typename U, typename V, typename W, typename X> 0191 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType &key) const 0192 { 0193 return m_impl.find(key); 0194 } 0195 0196 template<typename T, typename U, typename V, typename W, typename X> 0197 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const 0198 { 0199 return m_impl.template find<RawKeyType, RawKeyTranslator>(key); 0200 } 0201 0202 template<typename T, typename U, typename V, typename W, typename X> 0203 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType &key) const 0204 { 0205 return m_impl.contains(key); 0206 } 0207 0208 template<typename T, typename U, typename V, typename W, typename X> 0209 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const 0210 { 0211 return m_impl.template contains<RawKeyType, RawKeyTranslator>(key); 0212 } 0213 0214 template<typename T, typename U, typename V, typename W, typename X> 0215 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0216 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType &key, const MappedType &mapped) 0217 { 0218 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 0219 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 0220 } 0221 0222 template<typename T, typename U, typename V, typename W, typename X> 0223 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0224 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType &mapped) 0225 { 0226 return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped); 0227 } 0228 0229 template<typename T, typename U, typename V, typename W, typename X> 0230 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0231 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType &key, const MappedType &mapped) 0232 { 0233 pair<iterator, bool> result = inlineAdd(key, mapped); 0234 if (!result.second) { 0235 // add call above didn't change anything, so set the mapped value 0236 result.first->second = mapped; 0237 } 0238 return result; 0239 } 0240 0241 template<typename T, typename U, typename V, typename W, typename X> 0242 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0243 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType &mapped) 0244 { 0245 pair<iterator, bool> result = inlineAdd(key, mapped); 0246 if (!result.second) { 0247 // add call above didn't change anything, so set the mapped value 0248 result.first->second = mapped; 0249 } 0250 return result; 0251 } 0252 0253 template<typename T, typename U, typename V, typename W, typename X> 0254 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0255 HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType &key, const MappedType &mapped) 0256 { 0257 return inlineAdd(key, mapped); 0258 } 0259 0260 template<typename T, typename U, typename V, typename W, typename X> 0261 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 0262 HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType &mapped) 0263 { 0264 return inlineAdd(key, mapped); 0265 } 0266 0267 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0268 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 0269 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType &key) const 0270 { 0271 ValueType *entry = const_cast<HashTableType &>(m_impl).lookup(key); 0272 if (!entry) { 0273 return MappedTraits::emptyValue(); 0274 } 0275 return entry->second; 0276 } 0277 0278 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0279 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 0280 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const 0281 { 0282 ValueType *entry = const_cast<HashTableType &>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key); 0283 if (!entry) { 0284 return MappedTraits::emptyValue(); 0285 } 0286 return entry->second; 0287 } 0288 0289 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0290 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 0291 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const 0292 { 0293 return inlineGet(key); 0294 } 0295 0296 template<typename T, typename U, typename V, typename W, typename X> 0297 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it) 0298 { 0299 if (it.m_impl == m_impl.end()) { 0300 return; 0301 } 0302 m_impl.checkTableConsistency(); 0303 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 0304 } 0305 0306 template<typename T, typename U, typename V, typename W, typename X> 0307 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType &key) 0308 { 0309 remove(find(key)); 0310 } 0311 0312 template<typename T, typename U, typename V, typename W, typename X> 0313 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key) 0314 { 0315 remove(find(key)); 0316 } 0317 0318 template<typename T, typename U, typename V, typename W, typename X> 0319 inline void HashMap<RefPtr<T>, U, V, W, X>::clear() 0320 { 0321 m_impl.clear(); 0322 } 0323 0324 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0325 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 0326 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType &key) 0327 { 0328 // This can probably be made more efficient to avoid ref/deref churn. 0329 iterator it = find(key); 0330 if (it == end()) { 0331 return MappedTraits::emptyValue(); 0332 } 0333 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 0334 remove(it); 0335 return result; 0336 } 0337 0338 template<typename T, typename U, typename V, typename W, typename MappedTraits> 0339 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 0340 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key) 0341 { 0342 // This can probably be made more efficient to avoid ref/deref churn. 0343 iterator it = find(key); 0344 if (it == end()) { 0345 return MappedTraits::emptyValue(); 0346 } 0347 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 0348 remove(it); 0349 return result; 0350 } 0351 0352 } // namespace WTF 0353 0354 #endif