Recent changes to C++ XPCOM hashtable class templates

[Simon Giesecke]

Hi,

TL;DR The XPCOM hashtable types of first choice are now nsTHashMap and
nsTHashSet, e.g. nsTHashMap<uint32_t, RefPtr<Foo>> or
nsTHashSet<nsCString>. The interface of nsTHashtable/nsBaseHashtable
and its subtypes is maintained, after some changes had been made to
these class templates themselves.

In particular, nika and janv have contributed largely to these
efforts. Thanks also to the reviewers from various modules for making
this possible smoothly.

Some details on the new types:

The key parameter specified for nsTHashMap/nsTHashSet can either be a
well-known key type such as nsCString, RefPtr<T> or T* and a suitable
PLD key class is automatically determined, or it can be a custom key
class derived from PLDEntryHdr, as known from the previous hashtable
class templates. The value parameter specified for nsTHashMap can
generally be any type, but care must still be taken for types that are
not trivially relocatable (e.g. because they have internal pointer
references).

nsBaseHashtable’s UserDataType can mostly be ignored now. For
nsTHashMap, it is always the same as DataType.

An overview of the changes follows. For more details, please refer to
the inline documentation.

Changes to the type constraints
- nsBaseHashtable now allows value types (“DataType”) that are not
default-constructible and/or UserDataTypes that are neither copy- nor
move-constructible. Specifically, this allows us to use `NotNull<>` as
the value type.

Changes in the type hierarchy
- nsTHashMap is new (based on nsBaseHashtable)
- nsTHashSet is new (based on nsTHashtable)
- nsRefPtrHashtable and nsInterfaceHashtable are deprecated (and their
previously separate implementations have recently been replaced by
nsRefCountedHashtable, but this is only an implementation detail)
- nsDataHashtable is gone already
- nsClassHashtable is deprecated
- using nsBaseHashtable directly is deprecated for most use cases (it
is the internal implementation of nsTHashMap though, so it won’t be
removed, but might be moved to a detail namespace)

There are even less reasons now to use nsTHashtable directly. Usually,
you should be able to use either nsTHashMap or nsTHashSet. Some of the
remaining uses of nsTHashtable might be migrated by splitting their
key and value types, and use nsTHashMap. For set-like uses, there are
already patches up that migrate most uses to nsTHashSet, some of those
have already landed.

Changes in member functions

- LookupForAdd is gone, and WithEntryHandle is its replacement

- LookupOrInsert, LookupOrInsertWith and TryLookupOrInsertWith have been added

- Put has been renamed to InsertOrUpdate, and it no longer wraps UserDataType

- GetAndRemove has been renamed to Extract

- GetOrInsertNew is now also available for the RefPtr<T>-valued nsTHashMaps

- ConstIter now returns a real const iterator (it used to remain the
same as Iter before), but you should usually not need to bother, as
range-based for using the STL-style iterators internally is usually
preferable

- Keys and Values now return a range of only keys respectively values,
where applicable, rather than the hashtable entries; KeyArray and
ValueArray return a copy of the keys resp. Values

- Some member functions are now [[nodiscard]]

- Clone was added (but avoid using it, cloning a hashtable may be expensive)

- nsTHashtable and its descendants are now STL-style ranges

- RemoveIf was added

Some possible/desirable future work, that's welcome to be picked by
anyone interested:

- Change already migrated nsTHashMap uses to make use of the key class
deduction.

- The expectation of most uses of
nsRefPtrHashtable/nsInterfaceHashtable and particularly
nsClassHashtable has been that the stored value is always non-null.
However, this isn’t enforced and in fact in some cases this constraint
is violated. As a consequence, there are numerous runtime checks and
assertions around that verify that the values are not-null, which lead
to unnecessary complexity and are error-prone. While the changes have
made it possible to use a `nsBaseHashtable<KeyClass,
NotNull<RefPtr<T>>, MovingNotNull<RefPtr<T>>>` this remains
suboptimal. We should provide a better default and integrate this
better with nsTHashMap and with the operations offered by the
hashtables. Maybe this allows to eventually remove the UserDataType
type argument from nsBaseHashtable (Bug 1608528).

- Provide a more efficient way to clone hashtables (Bug 1694368)

- Ensure that keys are not unnecessarily copied in
nsTHashtable/nsBaseHashtable operations (Bug 1697377)

- Migrate existing uses of the deprecated
nsRefPtrHashtable/nsInterfaceHashtable/nsClassHashtable classes to
nsTHashMap and remove the deprecated classes.

I am here for questions :)

Best wishes
Simon