Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef nsBaseHashtable_h__
8 : #define nsBaseHashtable_h__
9 :
10 : #include "mozilla/MemoryReporting.h"
11 : #include "mozilla/Move.h"
12 : #include "nsTHashtable.h"
13 : #include "nsDebug.h"
14 :
15 : template<class KeyClass, class DataType, class UserDataType>
16 : class nsBaseHashtable; // forward declaration
17 :
18 : /**
19 : * the private nsTHashtable::EntryType class used by nsBaseHashtable
20 : * @see nsTHashtable for the specification of this class
21 : * @see nsBaseHashtable for template parameters
22 : */
23 : template<class KeyClass, class DataType>
24 : class nsBaseHashtableET : public KeyClass
25 : {
26 : public:
27 : DataType mData;
28 : friend class nsTHashtable<nsBaseHashtableET<KeyClass, DataType>>;
29 :
30 : private:
31 : typedef typename KeyClass::KeyType KeyType;
32 : typedef typename KeyClass::KeyTypePointer KeyTypePointer;
33 :
34 : explicit nsBaseHashtableET(KeyTypePointer aKey);
35 : nsBaseHashtableET(nsBaseHashtableET<KeyClass, DataType>&& aToMove);
36 : ~nsBaseHashtableET();
37 : };
38 :
39 : /**
40 : * templated hashtable for simple data types
41 : * This class manages simple data types that do not need construction or
42 : * destruction.
43 : *
44 : * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h
45 : * for a complete specification.
46 : * @param DataType the datatype stored in the hashtable,
47 : * for example, uint32_t or nsCOMPtr. If UserDataType is not the same,
48 : * DataType must implicitly cast to UserDataType
49 : * @param UserDataType the user sees, for example uint32_t or nsISupports*
50 : */
51 : template<class KeyClass, class DataType, class UserDataType>
52 3924 : class nsBaseHashtable
53 : : protected nsTHashtable<nsBaseHashtableET<KeyClass, DataType>>
54 : {
55 : typedef mozilla::fallible_t fallible_t;
56 :
57 : public:
58 : typedef typename KeyClass::KeyType KeyType;
59 : typedef nsBaseHashtableET<KeyClass, DataType> EntryType;
60 :
61 : using nsTHashtable<EntryType>::Contains;
62 : using nsTHashtable<EntryType>::GetGeneration;
63 :
64 6506 : nsBaseHashtable() {}
65 513 : explicit nsBaseHashtable(uint32_t aInitLength)
66 513 : : nsTHashtable<EntryType>(aInitLength)
67 : {
68 513 : }
69 :
70 : /**
71 : * Return the number of entries in the table.
72 : * @return number of entries
73 : */
74 10663 : uint32_t Count() const { return nsTHashtable<EntryType>::Count(); }
75 :
76 : /**
77 : * retrieve the value for a key.
78 : * @param aKey the key to retreive
79 : * @param aData data associated with this key will be placed at this
80 : * pointer. If you only need to check if the key exists, aData
81 : * may be null.
82 : * @return true if the key exists. If key does not exist, aData is not
83 : * modified.
84 : */
85 15547 : bool Get(KeyType aKey, UserDataType* aData) const
86 : {
87 15547 : EntryType* ent = this->GetEntry(aKey);
88 15547 : if (!ent) {
89 5633 : return false;
90 : }
91 :
92 9914 : if (aData) {
93 9914 : *aData = ent->mData;
94 : }
95 :
96 9914 : return true;
97 : }
98 :
99 : /**
100 : * Get the value, returning a zero-initialized POD or a default-initialized
101 : * object if the entry is not present in the table.
102 : *
103 : * @param aKey the key to retrieve
104 : * @return The found value, or UserDataType{} if no entry was found with the
105 : * given key.
106 : * @note If zero/default-initialized values are stored in the table, it is
107 : * not possible to distinguish between such a value and a missing entry.
108 : */
109 24386 : UserDataType Get(KeyType aKey) const
110 : {
111 24386 : EntryType* ent = this->GetEntry(aKey);
112 24386 : if (!ent) {
113 7070 : return UserDataType{};
114 : }
115 :
116 17316 : return ent->mData;
117 : }
118 :
119 : /**
120 : * Add key to the table if not already present, and return a reference to its
121 : * value. If key is not already in the table then the value is default
122 : * constructed.
123 : */
124 0 : DataType& GetOrInsert(const KeyType& aKey)
125 : {
126 0 : EntryType* ent = this->PutEntry(aKey);
127 0 : return ent->mData;
128 : }
129 :
130 : /**
131 : * put a new value for the associated key
132 : * @param aKey the key to put
133 : * @param aData the new data
134 : * @return always true, unless memory allocation failed
135 : */
136 32695 : void Put(KeyType aKey, const UserDataType& aData)
137 : {
138 32695 : if (!Put(aKey, aData, mozilla::fallible)) {
139 0 : NS_ABORT_OOM(this->mTable.EntrySize() * this->mTable.EntryCount());
140 : }
141 32695 : }
142 :
143 32695 : MOZ_MUST_USE bool Put(KeyType aKey, const UserDataType& aData,
144 : const fallible_t&)
145 : {
146 32695 : EntryType* ent = this->PutEntry(aKey, mozilla::fallible);
147 32695 : if (!ent) {
148 0 : return false;
149 : }
150 :
151 32695 : ent->mData = aData;
152 :
153 32695 : return true;
154 : }
155 :
156 : /**
157 : * Remove the entry associated with aKey (if any), optionally _moving_ its
158 : * current value into *aData. Return true if found.
159 : * @param aKey the key to remove from the hashtable
160 : * @param aData where to move the value (if non-null). If an entry is not
161 : * found, *aData will be assigned a default-constructed value
162 : * (i.e. reset to zero or nullptr for primitive types).
163 : * @return true if an entry for aKey was found (and removed)
164 : */
165 3200 : bool Remove(KeyType aKey, DataType* aData = nullptr)
166 : {
167 3200 : if (auto* ent = this->GetEntry(aKey)) {
168 1466 : if (aData) {
169 172 : *aData = mozilla::Move(ent->mData);
170 : }
171 1466 : this->RemoveEntry(ent);
172 1466 : return true;
173 : }
174 1734 : if (aData) {
175 86 : *aData = mozilla::Move(DataType());
176 : }
177 1734 : return false;
178 : }
179 :
180 : struct LookupResult {
181 : private:
182 : EntryType* mEntry;
183 : nsBaseHashtable& mTable;
184 : #ifdef DEBUG
185 : uint32_t mTableGeneration;
186 : #endif
187 :
188 : public:
189 696 : LookupResult(EntryType* aEntry, nsBaseHashtable& aTable)
190 : : mEntry(aEntry)
191 : , mTable(aTable)
192 : #ifdef DEBUG
193 696 : , mTableGeneration(aTable.GetGeneration())
194 : #endif
195 696 : {}
196 :
197 : // Is there something stored in the table?
198 728 : explicit operator bool() const
199 : {
200 728 : MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
201 728 : return mEntry;
202 : }
203 :
204 2 : void Remove()
205 : {
206 2 : if (!*this) {
207 0 : return;
208 : }
209 2 : mTable.RemoveEntry(mEntry);
210 2 : mEntry = nullptr;
211 : }
212 :
213 30 : MOZ_MUST_USE DataType& Data()
214 : {
215 30 : MOZ_ASSERT(!!*this, "must have an entry to access its value");
216 30 : return mEntry->mData;
217 : }
218 : };
219 :
220 : /**
221 : * Looks up aKey in the hashtable and returns an object that allows you to
222 : * read/modify the value of the entry, or remove the entry (if found).
223 : *
224 : * A typical usage of this API looks like this:
225 : *
226 : * if (auto entry = hashtable.Lookup(key)) {
227 : * DoSomething(entry.Data());
228 : * if (entry.Data() > 42) {
229 : * entry.Remove();
230 : * }
231 : * } // else - an entry with the given key doesn't exist
232 : *
233 : * This is useful for cases where you want to read/write the value of an entry
234 : * and (optionally) remove the entry without having to do multiple hashtable
235 : * lookups. If you want to insert a new entry if one does not exist, then use
236 : * LookupForAdd instead, see below.
237 : */
238 696 : MOZ_MUST_USE LookupResult Lookup(KeyType aKey)
239 : {
240 696 : return LookupResult(this->GetEntry(aKey), *this);
241 : }
242 :
243 : struct EntryPtr {
244 : private:
245 : EntryType& mEntry;
246 : bool mExistingEntry;
247 : // For debugging purposes
248 : #ifdef DEBUG
249 : nsBaseHashtable& mTable;
250 : uint32_t mTableGeneration;
251 : bool mDidInitNewEntry;
252 : #endif
253 :
254 : public:
255 3693 : EntryPtr(nsBaseHashtable& aTable, EntryType* aEntry, bool aExistingEntry)
256 : : mEntry(*aEntry)
257 : , mExistingEntry(aExistingEntry)
258 : #ifdef DEBUG
259 : , mTable(aTable)
260 : , mTableGeneration(aTable.GetGeneration())
261 3693 : , mDidInitNewEntry(false)
262 : #endif
263 3693 : {}
264 3693 : ~EntryPtr()
265 : {
266 3693 : MOZ_ASSERT(mExistingEntry || mDidInitNewEntry,
267 : "Forgot to call OrInsert() on a new entry");
268 3693 : }
269 :
270 : // Is there something stored in the table already?
271 3189 : explicit operator bool() const
272 : {
273 3189 : MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
274 3189 : return mExistingEntry;
275 : }
276 :
277 : template <class F>
278 3620 : UserDataType OrInsert(F func)
279 : {
280 3620 : MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
281 3620 : if (!mExistingEntry) {
282 3598 : mEntry.mData = func();
283 : #ifdef DEBUG
284 3598 : mDidInitNewEntry = true;
285 : #endif
286 : }
287 3620 : return mEntry.mData;
288 : }
289 :
290 88 : MOZ_MUST_USE DataType& Data()
291 : {
292 88 : MOZ_ASSERT(mTableGeneration == mTable.GetGeneration());
293 88 : return mEntry.mData;
294 : }
295 : };
296 :
297 : /**
298 : * Looks up aKey in the hashtable and returns an object that allows you to
299 : * insert a new entry into the hashtable for that key if an existing entry
300 : * isn't found for it.
301 : *
302 : * A typical usage of this API looks like this:
303 : *
304 : * auto insertedValue = table.LookupForAdd(key).OrInsert([]() {
305 : * return newValue;
306 : * });
307 : *
308 : * auto p = table.LookupForAdd(key);
309 : * if (p) {
310 : * // The entry already existed in the table.
311 : * DoSomething(p.Data());
312 : * } else {
313 : * // An existing entry wasn't found, store a new entry in the hashtable.
314 : * p.OrInsert([]() { return newValue; });
315 : * }
316 : *
317 : * We ensure that the hashtable isn't modified before EntryPtr method calls.
318 : * This is useful for cases where you want to insert a new entry into the
319 : * hashtable if one doesn't exist before but would like to avoid two hashtable
320 : * lookups.
321 : */
322 3693 : MOZ_MUST_USE EntryPtr LookupForAdd(KeyType aKey)
323 : {
324 3693 : auto count = Count();
325 3693 : EntryType* ent = this->PutEntry(aKey);
326 3693 : return EntryPtr(*this, ent, count == Count());
327 : }
328 :
329 : // This is an iterator that also allows entry removal. Example usage:
330 : //
331 : // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
332 : // const KeyType key = iter.Key();
333 : // const UserDataType data = iter.UserData();
334 : // // or
335 : // const DataType& data = iter.Data();
336 : // // ... do stuff with |key| and/or |data| ...
337 : // // ... possibly call iter.Remove() once ...
338 : // }
339 : //
340 : class Iterator : public PLDHashTable::Iterator
341 : {
342 : public:
343 : typedef PLDHashTable::Iterator Base;
344 :
345 2155 : explicit Iterator(nsBaseHashtable* aTable) : Base(&aTable->mTable) {}
346 3 : Iterator(Iterator&& aOther) : Base(aOther.mTable) {}
347 2158 : ~Iterator() {}
348 :
349 3317 : KeyType Key() const { return static_cast<EntryType*>(Get())->GetKey(); }
350 1501 : UserDataType UserData() const
351 : {
352 1501 : return static_cast<EntryType*>(Get())->mData;
353 : }
354 2126 : DataType& Data() const { return static_cast<EntryType*>(Get())->mData; }
355 :
356 : private:
357 : Iterator() = delete;
358 : Iterator(const Iterator&) = delete;
359 : Iterator& operator=(const Iterator&) = delete;
360 : Iterator& operator=(const Iterator&&) = delete;
361 : };
362 :
363 1299 : Iterator Iter() { return Iterator(this); }
364 :
365 856 : Iterator ConstIter() const
366 : {
367 856 : return Iterator(const_cast<nsBaseHashtable*>(this));
368 : }
369 :
370 : /**
371 : * reset the hashtable, removing all entries
372 : */
373 523 : void Clear() { nsTHashtable<EntryType>::Clear(); }
374 :
375 : /**
376 : * Measure the size of the table's entry storage. The size of things pointed
377 : * to by entries must be measured separately; hence the "Shallow" prefix.
378 : *
379 : * @param aMallocSizeOf the function used to measure heap-allocated blocks
380 : * @return the summed size of the table's storage
381 : */
382 28 : size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
383 : {
384 28 : return this->mTable.ShallowSizeOfExcludingThis(aMallocSizeOf);
385 : }
386 :
387 : /**
388 : * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
389 : */
390 0 : size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
391 : {
392 0 : return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf);
393 : }
394 :
395 : /**
396 : * Swap the elements in this hashtable with the elements in aOther.
397 : */
398 0 : void SwapElements(nsBaseHashtable& aOther)
399 : {
400 0 : nsTHashtable<EntryType>::SwapElements(aOther);
401 0 : }
402 :
403 :
404 : #ifdef DEBUG
405 : using nsTHashtable<EntryType>::MarkImmutable;
406 : #endif
407 : };
408 :
409 : //
410 : // nsBaseHashtableET definitions
411 : //
412 :
413 : template<class KeyClass, class DataType>
414 40216 : nsBaseHashtableET<KeyClass, DataType>::nsBaseHashtableET(KeyTypePointer aKey)
415 : : KeyClass(aKey)
416 40216 : , mData()
417 : {
418 40216 : }
419 :
420 : template<class KeyClass, class DataType>
421 42 : nsBaseHashtableET<KeyClass, DataType>::nsBaseHashtableET(
422 : nsBaseHashtableET<KeyClass, DataType>&& aToMove)
423 42 : : KeyClass(mozilla::Move(aToMove))
424 42 : , mData(mozilla::Move(aToMove.mData))
425 : {
426 42 : }
427 :
428 : template<class KeyClass, class DataType>
429 3416 : nsBaseHashtableET<KeyClass, DataType>::~nsBaseHashtableET()
430 : {
431 3416 : }
432 :
433 : #endif // nsBaseHashtable_h__
|
