• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

WTF

  • kjs
  • wtf
RefPtrHashMap.h
Go to the documentation of this file.
1// -*- mode: c++; c-basic-offset: 4 -*-
2/*
3 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22namespace WTF {
23
24 // This specialization is a direct copy of HashMap, with overloaded functions
25 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
26
27 // FIXME: Find a better way that doesn't require an entire copy of the HashMap template.
28
29 template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions>
30 struct RefPtrHashMapRawKeyTranslator {
31 typedef typename ValueType::first_type KeyType;
32 typedef typename ValueType::second_type MappedType;
33 typedef typename ValueTraits::FirstTraits KeyTraits;
34 typedef typename ValueTraits::SecondTraits MappedTraits;
35
36 static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); }
37 static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); }
38 static void translate(ValueType& location, RawKeyType key, const MappedType& mapped)
39 {
40 location.first = key;
41 location.second = mapped;
42 }
43 };
44
45 template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
46 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
47 private:
48 typedef KeyTraitsArg KeyTraits;
49 typedef MappedTraitsArg MappedTraits;
50 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
51
52 public:
53 typedef typename KeyTraits::TraitType KeyType;
54 typedef T* RawKeyType;
55 typedef typename MappedTraits::TraitType MappedType;
56 typedef typename ValueTraits::TraitType ValueType;
57
58 private:
59 typedef HashArg HashFunctions;
60
61 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,
62 HashFunctions, ValueTraits, KeyTraits> HashTableType;
63
64 typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions>
65 RawKeyTranslator;
66
67 public:
68 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
69 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
70
71 void swap(HashMap&);
72
73 int size() const;
74 int capacity() const;
75 bool isEmpty() const;
76
77 // iterators iterate over pairs of keys and values
78 iterator begin();
79 iterator end();
80 const_iterator begin() const;
81 const_iterator end() const;
82
83 iterator find(const KeyType&);
84 iterator find(RawKeyType);
85 const_iterator find(const KeyType&) const;
86 const_iterator find(RawKeyType) const;
87 bool contains(const KeyType&) const;
88 bool contains(RawKeyType) const;
89 MappedType get(const KeyType&) const;
90 MappedType get(RawKeyType) const;
91 MappedType inlineGet(RawKeyType) const;
92
93 // replaces value but not key 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 pair<iterator, bool> set(const KeyType&, const MappedType&);
97 pair<iterator, bool> set(RawKeyType, const MappedType&);
98
99 // does nothing if key is already present
100 // return value is a pair of the iterator to the key location,
101 // and a boolean that's true if a new value was actually added
102 pair<iterator, bool> add(const KeyType&, const MappedType&);
103 pair<iterator, bool> add(RawKeyType, const MappedType&);
104
105 void remove(const KeyType&);
106 void remove(RawKeyType);
107 void remove(iterator);
108 void clear();
109
110 MappedType take(const KeyType&); // efficient combination of get with remove
111 MappedType take(RawKeyType); // efficient combination of get with remove
112
113 private:
114 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
115 pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
116
117 HashTableType m_impl;
118 };
119
120 template<typename T, typename U, typename V, typename W, typename X>
121 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
122 {
123 m_impl.swap(other.m_impl);
124 }
125
126 template<typename T, typename U, typename V, typename W, typename X>
127 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
128 {
129 return m_impl.size();
130 }
131
132 template<typename T, typename U, typename V, typename W, typename X>
133 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
134 {
135 return m_impl.capacity();
136 }
137
138 template<typename T, typename U, typename V, typename W, typename X>
139 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
140 {
141 return m_impl.isEmpty();
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>::begin()
146 {
147 return m_impl.begin();
148 }
149
150 template<typename T, typename U, typename V, typename W, typename X>
151 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
152 {
153 return m_impl.end();
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<RefPtr<T>, U, V, W, X>::begin() const
158 {
159 return m_impl.begin();
160 }
161
162 template<typename T, typename U, typename V, typename W, typename X>
163 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
164 {
165 return m_impl.end();
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(const KeyType& key)
170 {
171 return m_impl.find(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>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
176 {
177 return m_impl.template find<RawKeyType, RawKeyTranslator>(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<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
182 {
183 return m_impl.find(key);
184 }
185
186 template<typename T, typename U, typename V, typename W, typename X>
187 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
188 {
189 return m_impl.template find<RawKeyType, RawKeyTranslator>(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(const KeyType& key) const
194 {
195 return m_impl.contains(key);
196 }
197
198 template<typename T, typename U, typename V, typename W, typename X>
199 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
200 {
201 return m_impl.template contains<RawKeyType, RawKeyTranslator>(key);
202 }
203
204 template<typename T, typename U, typename V, typename W, typename X>
205 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
206 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
207 {
208 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
209 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
210 }
211
212 template<typename T, typename U, typename V, typename W, typename X>
213 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
214 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped)
215 {
216 return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped);
217 }
218
219 template<typename T, typename U, typename V, typename W, typename X>
220 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
221 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
222 {
223 pair<iterator, bool> result = inlineAdd(key, mapped);
224 if (!result.second) {
225 // add call above didn't change anything, so set the mapped value
226 result.first->second = mapped;
227 }
228 return result;
229 }
230
231 template<typename T, typename U, typename V, typename W, typename X>
232 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
233 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped)
234 {
235 pair<iterator, bool> result = inlineAdd(key, mapped);
236 if (!result.second) {
237 // add call above didn't change anything, so set the mapped value
238 result.first->second = mapped;
239 }
240 return result;
241 }
242
243 template<typename T, typename U, typename V, typename W, typename X>
244 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
245 HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
246 {
247 return inlineAdd(key, mapped);
248 }
249
250 template<typename T, typename U, typename V, typename W, typename X>
251 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
252 HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
253 {
254 return inlineAdd(key, mapped);
255 }
256
257 template<typename T, typename U, typename V, typename W, typename MappedTraits>
258 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
259 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
260 {
261 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
262 if (!entry)
263 return MappedTraits::emptyValue();
264 return entry->second;
265 }
266
267 template<typename T, typename U, typename V, typename W, typename MappedTraits>
268 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
269 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const
270 {
271 ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key);
272 if (!entry)
273 return MappedTraits::emptyValue();
274 return entry->second;
275 }
276
277 template<typename T, typename U, typename V, typename W, typename MappedTraits>
278 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
279 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
280 {
281 return inlineGet(key);
282 }
283
284 template<typename T, typename U, typename V, typename W, typename X>
285 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
286 {
287 if (it.m_impl == m_impl.end())
288 return;
289 m_impl.checkTableConsistency();
290 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
291 }
292
293 template<typename T, typename U, typename V, typename W, typename X>
294 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
295 {
296 remove(find(key));
297 }
298
299 template<typename T, typename U, typename V, typename W, typename X>
300 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
301 {
302 remove(find(key));
303 }
304
305 template<typename T, typename U, typename V, typename W, typename X>
306 inline void HashMap<RefPtr<T>, U, V, W, X>::clear()
307 {
308 m_impl.clear();
309 }
310
311 template<typename T, typename U, typename V, typename W, typename MappedTraits>
312 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
313 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
314 {
315 // This can probably be made more efficient to avoid ref/deref churn.
316 iterator it = find(key);
317 if (it == end())
318 return MappedTraits::emptyValue();
319 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
320 remove(it);
321 return result;
322 }
323
324 template<typename T, typename U, typename V, typename W, typename MappedTraits>
325 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
326 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
327 {
328 // This can probably be made more efficient to avoid ref/deref churn.
329 iterator it = find(key);
330 if (it == end())
331 return MappedTraits::emptyValue();
332 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
333 remove(it);
334 return result;
335 }
336
337} // namespace WTF
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::contains
bool contains(const KeyType &) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::KeyType
KeyTraits::TraitType KeyType
Definition: RefPtrHashMap.h:53
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::find
iterator find(RawKeyType)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::remove
void remove(RawKeyType)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::RawKeyType
T * RawKeyType
Definition: RefPtrHashMap.h:54
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::end
const_iterator end() const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::find
const_iterator find(RawKeyType) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::get
MappedType get(const KeyType &) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::swap
void swap(HashMap &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::add
pair< iterator, bool > add(RawKeyType, const MappedType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::ValueType
ValueTraits::TraitType ValueType
Definition: RefPtrHashMap.h:56
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::remove
void remove(iterator)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::size
int size() const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::add
pair< iterator, bool > add(const KeyType &, const MappedType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::remove
void remove(const KeyType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::MappedType
MappedTraits::TraitType MappedType
Definition: RefPtrHashMap.h:55
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::clear
void clear()
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::capacity
int capacity() const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::take
MappedType take(const KeyType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::end
iterator end()
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::inlineGet
MappedType inlineGet(RawKeyType) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::begin
iterator begin()
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::set
pair< iterator, bool > set(const KeyType &, const MappedType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::set
pair< iterator, bool > set(RawKeyType, const MappedType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::isEmpty
bool isEmpty() const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::get
MappedType get(RawKeyType) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::take
MappedType take(RawKeyType)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::begin
const_iterator begin() const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::find
iterator find(const KeyType &)
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::contains
bool contains(RawKeyType) const
WTF::HashMap< RefPtr< T >, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg >::find
const_iterator find(const KeyType &) const
WTF::HashMap
Definition: HashMap.h:33
WTF::HashMap::swap
void swap(HashMap &)
Definition: HashMap.h:112
WTF::HashTable
Definition: HashTable.h:272
WTF::RefPtr
Definition: RefPtr.h:37
WTF
Definition: ASCIICType.h:45
WTF::HashTableConstIteratorAdapter
Definition: HashTable.h:1081
WTF::HashTableIteratorAdapter
Definition: HashTable.h:1094
WTF::PairHashTraits
Definition: HashTraits.h:126
WTF::PairHashTraits::TraitType
pair< typename FirstTraits::TraitType, typename SecondTraits::TraitType > TraitType
Definition: HashTraits.h:129
WTF::RefPtrHashMapRawKeyTranslator
Definition: RefPtrHashMap.h:30
WTF::RefPtrHashMapRawKeyTranslator::MappedType
ValueType::second_type MappedType
Definition: RefPtrHashMap.h:32
WTF::RefPtrHashMapRawKeyTranslator::MappedTraits
ValueTraits::SecondTraits MappedTraits
Definition: RefPtrHashMap.h:34
WTF::RefPtrHashMapRawKeyTranslator::equal
static bool equal(const KeyType &a, RawKeyType b)
Definition: RefPtrHashMap.h:37
WTF::RefPtrHashMapRawKeyTranslator::translate
static void translate(ValueType &location, RawKeyType key, const MappedType &mapped)
Definition: RefPtrHashMap.h:38
WTF::RefPtrHashMapRawKeyTranslator::hash
static unsigned hash(RawKeyType key)
Definition: RefPtrHashMap.h:36
WTF::RefPtrHashMapRawKeyTranslator::KeyTraits
ValueTraits::FirstTraits KeyTraits
Definition: RefPtrHashMap.h:33
WTF::RefPtrHashMapRawKeyTranslator::KeyType
ValueType::first_type KeyType
Definition: RefPtrHashMap.h:31
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Mon Feb 20 2023 00:00:00 by doxygen 1.9.6 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal