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/. */
7 #ifndef nsBaseHashtable_h__
8 #define nsBaseHashtable_h__
12 #include "mozilla/Maybe.h"
13 #include "mozilla/MemoryReporting.h"
15 #include "nsTHashtable.h"
17 template <class KeyClass
, class DataType
, class UserDataType
, class Converter
>
18 class nsBaseHashtable
; // forward declaration
21 * Data type conversion helper that is used to wrap and unwrap the specified
24 template <class DataType
, class UserDataType
>
25 class nsDefaultConverter
{
28 * Maps the storage DataType to the exposed UserDataType.
30 static UserDataType
Unwrap(DataType
& src
) { return UserDataType(src
); }
33 * Const ref variant used for example with nsCOMPtr wrappers.
35 static DataType
Wrap(const UserDataType
& src
) { return DataType(src
); }
38 * Generic conversion, this is useful for things like already_AddRefed.
41 static DataType
Wrap(U
&& src
) {
42 return std::forward
<U
>(src
);
46 static UserDataType
Unwrap(U
&& src
) {
47 return std::forward
<U
>(src
);
52 * the private nsTHashtable::EntryType class used by nsBaseHashtable
53 * @see nsTHashtable for the specification of this class
54 * @see nsBaseHashtable for template parameters
56 template <class KeyClass
, class DataType
>
57 class nsBaseHashtableET
: public KeyClass
{
59 const DataType
& GetData() const { return mData
; }
60 DataType
* GetModifiableData() { return &mData
; }
62 void SetData(U
&& aData
) {
63 mData
= std::forward
<U
>(aData
);
68 friend class nsTHashtable
<nsBaseHashtableET
<KeyClass
, DataType
>>;
69 template <typename KeyClassX
, typename DataTypeX
, typename UserDataTypeX
,
71 friend class nsBaseHashtable
;
73 typedef typename
KeyClass::KeyType KeyType
;
74 typedef typename
KeyClass::KeyTypePointer KeyTypePointer
;
76 explicit nsBaseHashtableET(KeyTypePointer aKey
);
77 nsBaseHashtableET(KeyTypePointer aKey
, const DataType
& aData
);
78 nsBaseHashtableET(KeyTypePointer aKey
, DataType
&& aData
);
79 nsBaseHashtableET(nsBaseHashtableET
<KeyClass
, DataType
>&& aToMove
);
80 ~nsBaseHashtableET() = default;
84 * templated hashtable for simple data types
85 * This class manages simple data types that do not need construction or
88 * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h
89 * for a complete specification.
90 * @param DataType the datatype stored in the hashtable,
91 * for example, uint32_t or nsCOMPtr.
92 * @param UserDataType the user sees, for example uint32_t or nsISupports*
93 * @param Converter that can be used to map from DataType to UserDataType. A
94 * default converter is provided that assumes implicit conversion is an
97 template <class KeyClass
, class DataType
, class UserDataType
,
98 class Converter
= nsDefaultConverter
<DataType
, UserDataType
>>
100 : protected nsTHashtable
<nsBaseHashtableET
<KeyClass
, DataType
>> {
101 using Base
= nsTHashtable
<nsBaseHashtableET
<KeyClass
, DataType
>>;
102 typedef mozilla::fallible_t fallible_t
;
105 typedef typename
KeyClass::KeyType KeyType
;
106 typedef nsBaseHashtableET
<KeyClass
, DataType
> EntryType
;
108 using nsTHashtable
<EntryType
>::Contains
;
109 using nsTHashtable
<EntryType
>::GetGeneration
;
110 using nsTHashtable
<EntryType
>::SizeOfExcludingThis
;
111 using nsTHashtable
<EntryType
>::SizeOfIncludingThis
;
113 nsBaseHashtable() = default;
114 explicit nsBaseHashtable(uint32_t aInitLength
)
115 : nsTHashtable
<EntryType
>(aInitLength
) {}
118 * Return the number of entries in the table.
119 * @return number of entries
121 uint32_t Count() const { return nsTHashtable
<EntryType
>::Count(); }
124 * Return whether the table is empty.
125 * @return whether empty
127 bool IsEmpty() const { return nsTHashtable
<EntryType
>::IsEmpty(); }
130 * Get the value, returning a flag indicating the presence of the entry in
133 * @param aKey the key to retrieve
134 * @param aData data associated with this key will be placed at this pointer.
135 * If you only need to check if the key exists, aData may be null.
136 * @return true if the key exists. If key does not exist, aData is not
139 bool Get(KeyType aKey
, UserDataType
* aData
) const {
140 EntryType
* ent
= this->GetEntry(aKey
);
146 *aData
= Converter::Unwrap(ent
->mData
);
153 * Get the value, returning a zero-initialized POD or a default-initialized
154 * object if the entry is not present in the table.
156 * This overload can only be used if UserDataType is default-constructible.
157 * Use the double-argument Get or MaybeGet with non-default-constructible
160 * @param aKey the key to retrieve
161 * @return The found value, or UserDataType{} if no entry was found with the
163 * @note If zero/default-initialized values are stored in the table, it is
164 * not possible to distinguish between such a value and a missing entry.
166 UserDataType
Get(KeyType aKey
) const {
167 EntryType
* ent
= this->GetEntry(aKey
);
169 return UserDataType
{};
172 return Converter::Unwrap(ent
->mData
);
176 * Get the value, returning Nothing if the entry is not present in the table.
178 * @param aKey the key to retrieve
179 * @return The found value wrapped in a Maybe, or Nothing if no entry was
180 * found with the given key.
182 mozilla::Maybe
<UserDataType
> MaybeGet(KeyType aKey
) const {
183 EntryType
* ent
= this->GetEntry(aKey
);
185 return mozilla::Nothing();
188 return mozilla::Some(Converter::Unwrap(ent
->mData
));
192 * Add aKey to the table if not already present, and return a reference to its
193 * value. If aKey is not already in the table then the a default-constructed
194 * or the provided value aData is used.
196 * If the arguments are non-trivial to provide, consider using GetOrInsertWith
199 template <typename
... Args
>
200 DataType
& GetOrInsert(const KeyType
& aKey
, Args
&&... aArgs
) {
201 return WithEntryHandle(aKey
, [&](auto entryHandle
) -> DataType
& {
202 return entryHandle
.OrInsert(std::forward
<Args
>(aArgs
)...);
207 * Add aKey to the table if not already present, and return a reference to its
208 * value. If aKey is not already in the table then the value is
209 * constructed using the given factory.
211 template <typename F
>
212 DataType
& GetOrInsertWith(const KeyType
& aKey
, F
&& aFunc
) {
213 return WithEntryHandle(aKey
, [&aFunc
](auto entryHandle
) -> DataType
& {
214 return entryHandle
.OrInsertWith(std::forward
<F
>(aFunc
));
219 * If it does not yet, inserts a new entry with the handle's key and the
220 * value passed to this function. Otherwise, it updates the entry by the
221 * value passed to this function.
223 * \tparam U DataType must be implicitly convertible (and assignable) from U
225 * \param aKey the key to put
226 * \param aData the new data
228 template <typename U
>
229 DataType
& Put(KeyType aKey
, U
&& aData
) {
230 return WithEntryHandle(aKey
, [&aData
](auto entryHandle
) -> DataType
& {
231 return entryHandle
.InsertOrUpdate(std::forward
<U
>(aData
));
235 template <typename U
>
236 [[nodiscard
]] bool Put(KeyType aKey
, U
&& aData
, const fallible_t
& aFallible
) {
237 return WithEntryHandle(aKey
, aFallible
, [&aData
](auto maybeEntryHandle
) {
238 if (!maybeEntryHandle
) {
241 maybeEntryHandle
->InsertOrUpdate(std::forward
<U
>(aData
));
247 * Remove the entry associated with aKey (if any), _moving_ its current value
248 * into *aData. Return true if found.
250 * This overload can only be used if DataType is default-constructible. Use
251 * the single-argument Remove or GetAndRemove with non-default-constructible
254 * @param aKey the key to remove from the hashtable
255 * @param aData where to move the value. If an entry is not found, *aData
256 * will be assigned a default-constructed value (i.e. reset to
257 * zero or nullptr for primitive types).
258 * @return true if an entry for aKey was found (and removed)
260 bool Remove(KeyType aKey
, DataType
* aData
) {
261 if (auto* ent
= this->GetEntry(aKey
)) {
263 *aData
= std::move(ent
->mData
);
265 this->RemoveEntry(ent
);
269 *aData
= std::move(DataType());
275 * Remove the entry associated with aKey (if any). Return true if found.
277 * @param aKey the key to remove from the hashtable
278 * @return true if an entry for aKey was found (and removed)
280 bool Remove(KeyType aKey
) {
281 if (auto* ent
= this->GetEntry(aKey
)) {
282 this->RemoveEntry(ent
);
290 * Retrieve the value for a key and remove the corresponding entry at
293 * @param aKey the key to retrieve and remove
294 * @return the found value, or Nothing if no entry was found with the
297 [[nodiscard
]] mozilla::Maybe
<DataType
> GetAndRemove(KeyType aKey
) {
298 mozilla::Maybe
<DataType
> value
;
299 if (EntryType
* ent
= this->GetEntry(aKey
)) {
300 value
.emplace(std::move(ent
->mData
));
301 this->RemoveEntry(ent
);
306 struct LookupResult
{
309 nsBaseHashtable
& mTable
;
311 uint32_t mTableGeneration
;
315 LookupResult(EntryType
* aEntry
, nsBaseHashtable
& aTable
)
320 mTableGeneration(aTable
.GetGeneration())
325 // Is there something stored in the table?
326 explicit operator bool() const {
327 MOZ_ASSERT(mTableGeneration
== mTable
.GetGeneration());
335 mTable
.RemoveEntry(mEntry
);
339 [[nodiscard
]] DataType
& Data() {
340 MOZ_ASSERT(!!*this, "must have an entry to access its value");
341 return mEntry
->mData
;
346 * Removes all entries matching a predicate.
348 * The predicate must be compatible with signature bool (const Iterator &).
350 template <typename Pred
>
351 void RemoveIf(Pred
&& aPred
) {
352 for (auto iter
= Iter(); !iter
.Done(); iter
.Next()) {
353 if (aPred(const_cast<std::add_const_t
<decltype(iter
)>&>(iter
))) {
360 * Looks up aKey in the hashtable and returns an object that allows you to
361 * read/modify the value of the entry, or remove the entry (if found).
363 * A typical usage of this API looks like this:
365 * if (auto entry = hashtable.Lookup(key)) {
366 * DoSomething(entry.Data());
367 * if (entry.Data() > 42) {
370 * } // else - an entry with the given key doesn't exist
372 * This is useful for cases where you want to read/write the value of an entry
373 * and (optionally) remove the entry without having to do multiple hashtable
374 * lookups. If you want to insert a new entry if one does not exist, then use
375 * WithEntryHandle instead, see below.
377 [[nodiscard
]] LookupResult
Lookup(KeyType aKey
) {
378 return LookupResult(this->GetEntry(aKey
), *this);
382 * Used by WithEntryHandle as the argument type to its functor. It is
383 * associated with the Key passed to WithEntryHandle and manages only the
384 * potential entry with that key. Note that in case no modifying operations
385 * are called on the handle, the state of the hashtable remains unchanged,
386 * i.e. WithEntryHandle does not modify the hashtable itself.
388 * Provides query functions (Key, HasEntry/operator bool, Data) and
389 * modifying operations for inserting new entries (Insert), updating existing
390 * entries (Update) and removing existing entries (Remove). They have
391 * debug-only assertion that fail when the state of the entry doesn't match
392 * the expectation. There are variants prefixed with "Or" (OrInsert, OrUpdate,
393 * OrRemove) that are a no-op in case the entry does already exist resp. does
394 * not exist. There are also variants OrInsertWith and OrUpdateWith that don't
395 * accept a value, but a functor, which is only called if the operation takes
396 * place, which should be used if the provision of the value is not trivial
397 * (e.g. allocates a heap object). Finally, there's InsertOrUpdate that
398 * handles both existing and non-existing entries.
400 * Note that all functions of EntryHandle only deal with DataType, not with
403 class EntryHandle
: protected nsTHashtable
<EntryType
>::EntryHandle
{
405 using Base
= typename nsTHashtable
<EntryType
>::EntryHandle
;
407 EntryHandle(EntryHandle
&& aOther
) = default;
408 ~EntryHandle() = default;
410 EntryHandle(const EntryHandle
&) = delete;
411 EntryHandle
& operator=(const EntryHandle
&) = delete;
412 EntryHandle
& operator=(const EntryHandle
&&) = delete;
416 using Base::HasEntry
;
418 using Base::operator bool;
423 * Inserts a new entry with the handle's key and the value passed to this
426 * \tparam Args DataType must be constructible from Args
430 template <typename
... Args
>
431 DataType
& Insert(Args
&&... aArgs
) {
432 Base::InsertInternal(std::forward
<Args
>(aArgs
)...);
437 * If it doesn't yet exist, inserts a new entry with the handle's key and
438 * the value passed to this function. The value is not consumed if no insert
441 * \tparam Args DataType must be constructible from Args
444 template <typename
... Args
>
445 DataType
& OrInsert(Args
&&... aArgs
) {
447 return Insert(std::forward
<Args
>(aArgs
)...);
453 * If it doesn't yet exist, inserts a new entry with the handle's key and
454 * the result of the functor passed to this function. The functor is not
455 * called if no insert takes place.
457 * \tparam F must return a value that is implicitly convertible to DataType
460 template <typename F
>
461 DataType
& OrInsertWith(F
&& aFunc
) {
463 return Insert(std::forward
<F
>(aFunc
)());
469 * Updates the entry with the handle's key by the value passed to this
472 * \tparam U DataType must be assignable from U
475 template <typename U
>
476 DataType
& Update(U
&& aData
) {
477 MOZ_RELEASE_ASSERT(HasEntry());
478 Data() = std::forward
<U
>(aData
);
483 * If an entry with the handle's key already exists, updates its value by
484 * the value passed to this function. The value is not consumed if no update
487 * \tparam U DataType must be assignable from U
489 template <typename U
>
490 void OrUpdate(U
&& aData
) {
492 Update(std::forward
<U
>(aData
));
497 * If an entry with the handle's key already exists, updates its value by
498 * the the result of the functor passed to this function. The functor is not
499 * called if no update takes place.
501 * \tparam F must return a value that DataType is assignable from
503 template <typename F
>
504 void OrUpdateWith(F
&& aFunc
) {
506 Update(std::forward
<F
>(aFunc
)());
511 * If it does not yet, inserts a new entry with the handle's key and the
512 * value passed to this function. Otherwise, it updates the entry by the
513 * value passed to this function.
515 * \tparam U DataType must be implicitly convertible (and assignable) from U
518 template <typename U
>
519 DataType
& InsertOrUpdate(U
&& aData
) {
521 Insert(std::forward
<U
>(aData
));
523 Update(std::forward
<U
>(aData
));
530 using Base::OrRemove
;
533 * Returns a reference to the value of the entry.
537 DataType
& Data() { return Entry()->mData
; }
540 friend class nsBaseHashtable
;
542 explicit EntryHandle(Base
&& aBase
) : Base(std::move(aBase
)) {}
546 * Performs a scoped operation on the entry for aKey, which may or may not
547 * exist when the function is called. It calls aFunc with an EntryHandle. The
548 * result of aFunc is returned as the result of this function. Its return type
549 * may be void. See the documentation of EntryHandle for the query and
550 * modifying operations it offers.
552 * A simple use of this function is, e.g.,
554 * hashtable.WithEntryHandle(key, [](auto&& entry) { entry.OrInsert(42); });
556 * \attention It is not safe to perform modifying operations on the hashtable
557 * other than through the EntryHandle within aFunc, and trying to do so will
558 * trigger debug assertions, and result in undefined behaviour otherwise.
561 auto WithEntryHandle(KeyType aKey
, F
&& aFunc
)
562 -> std::invoke_result_t
<F
, EntryHandle
&&> {
563 return Base::WithEntryHandle(
564 aKey
, [&aFunc
](auto entryHandle
) -> decltype(auto) {
565 return std::forward
<F
>(aFunc
)(EntryHandle
{std::move(entryHandle
)});
570 * Fallible variant of WithEntryHandle, with the following differences:
571 * - The functor aFunc must accept a Maybe<EntryHandle> (instead of an
573 * - In case allocation of the slot for the entry fails, Nothing is passed to
576 * For more details, see the explanation on the non-fallible overload above.
579 auto WithEntryHandle(KeyType aKey
, const fallible_t
& aFallible
, F
&& aFunc
)
580 -> std::invoke_result_t
<F
, mozilla::Maybe
<EntryHandle
>&&> {
581 return Base::WithEntryHandle(
582 aKey
, aFallible
, [&aFunc
](auto maybeEntryHandle
) {
583 return std::forward
<F
>(aFunc
)(
585 ? mozilla::Some(EntryHandle
{maybeEntryHandle
.extract()})
586 : mozilla::Nothing());
591 // This is an iterator that also allows entry removal. Example usage:
593 // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
594 // const KeyType key = iter.Key();
595 // const UserDataType data = iter.UserData();
597 // const DataType& data = iter.Data();
598 // // ... do stuff with |key| and/or |data| ...
599 // // ... possibly call iter.Remove() once ...
602 class Iterator
: public PLDHashTable::Iterator
{
604 typedef PLDHashTable::Iterator Base
;
606 explicit Iterator(nsBaseHashtable
* aTable
) : Base(&aTable
->mTable
) {}
607 Iterator(Iterator
&& aOther
) : Base(aOther
.mTable
) {}
608 ~Iterator() = default;
610 KeyType
Key() const { return static_cast<EntryType
*>(Get())->GetKey(); }
611 UserDataType
UserData() const {
612 return Converter::Unwrap(static_cast<EntryType
*>(Get())->mData
);
614 DataType
& Data() const { return static_cast<EntryType
*>(Get())->mData
; }
618 Iterator(const Iterator
&) = delete;
619 Iterator
& operator=(const Iterator
&) = delete;
620 Iterator
& operator=(const Iterator
&&) = delete;
623 Iterator
Iter() { return Iterator(this); }
625 Iterator
ConstIter() const {
626 return Iterator(const_cast<nsBaseHashtable
*>(this));
629 using typename nsTHashtable
<EntryType
>::iterator
;
630 using typename nsTHashtable
<EntryType
>::const_iterator
;
632 using nsTHashtable
<EntryType
>::begin
;
633 using nsTHashtable
<EntryType
>::end
;
634 using nsTHashtable
<EntryType
>::cbegin
;
635 using nsTHashtable
<EntryType
>::cend
;
638 * reset the hashtable, removing all entries
640 void Clear() { nsTHashtable
<EntryType
>::Clear(); }
643 * Measure the size of the table's entry storage. The size of things pointed
644 * to by entries must be measured separately; hence the "Shallow" prefix.
646 * @param aMallocSizeOf the function used to measure heap-allocated blocks
647 * @return the summed size of the table's storage
649 size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
650 return this->mTable
.ShallowSizeOfExcludingThis(aMallocSizeOf
);
654 * Like ShallowSizeOfExcludingThis, but includes sizeof(*this).
656 size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const {
657 return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf
);
661 * Swap the elements in this hashtable with the elements in aOther.
663 void SwapElements(nsBaseHashtable
& aOther
) {
664 nsTHashtable
<EntryType
>::SwapElements(aOther
);
667 using nsTHashtable
<EntryType
>::MarkImmutable
;
671 // nsBaseHashtableET definitions
674 template <class KeyClass
, class DataType
>
675 nsBaseHashtableET
<KeyClass
, DataType
>::nsBaseHashtableET(KeyTypePointer aKey
)
676 : KeyClass(aKey
), mData() {}
678 template <class KeyClass
, class DataType
>
679 nsBaseHashtableET
<KeyClass
, DataType
>::nsBaseHashtableET(KeyTypePointer aKey
,
680 const DataType
& aData
)
681 : KeyClass(aKey
), mData(aData
) {}
683 template <class KeyClass
, class DataType
>
684 nsBaseHashtableET
<KeyClass
, DataType
>::nsBaseHashtableET(KeyTypePointer aKey
,
686 : KeyClass(aKey
), mData(std::move(aData
)) {}
688 template <class KeyClass
, class DataType
>
689 nsBaseHashtableET
<KeyClass
, DataType
>::nsBaseHashtableET(
690 nsBaseHashtableET
<KeyClass
, DataType
>&& aToMove
)
691 : KeyClass(std::move(aToMove
)), mData(std::move(aToMove
.mData
)) {}
693 #endif // nsBaseHashtable_h__