From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- xpcom/docs/hashtables_detailed.rst | 121 +++++++++++++++++++++++++++++++++++++ 1 file changed, 121 insertions(+) create mode 100644 xpcom/docs/hashtables_detailed.rst (limited to 'xpcom/docs/hashtables_detailed.rst') diff --git a/xpcom/docs/hashtables_detailed.rst b/xpcom/docs/hashtables_detailed.rst new file mode 100644 index 0000000000..200c47490d --- /dev/null +++ b/xpcom/docs/hashtables_detailed.rst @@ -0,0 +1,121 @@ +XPCOM Hashtable Technical Details +================================= + +.. note:: + + This is a deep-dive into the underlying mechanisms that power the XPCOM + hashtables. Some of this information is quite old and may be out of date. If + you're looking for how to use XPCOM hashtables, you should consider reading + the :ref:`XPCOM Hashtable Guide` instead. + +Mozilla's Hashtable Implementations +----------------------------------- + +Mozilla has several hashtable implementations, which have been tested +and tuned, and hide the inner complexities of hashtable implementations: + +- ``PLHashTable`` - low-level C API; entry class pointers are constant; + more efficient for large entry structures; often wastes memory making + many small heap allocations. +- ``nsTHashtable`` - low-level C++ wrapper around ``PLDHash``; + generates callback functions and handles most casting automagically. + Client writes their own entry class which can include complex key and + data types. +- ``nsTHashMap/nsInterfaceHashtable/nsClassHashtable`` - + simplifies the common usage pattern mapping a simple keytype to a + simple datatype; client does not need to declare or manage an entry class; + ``nsTHashMap`` datatype is a scalar such as ``uint64_t``; + ``nsInterfaceHashtable`` datatype is an XPCOM interface; + ``nsClassHashtable`` datatype is a class pointer owned by the + hashtable. + +.. _PLHashTable: + +PLHashTable +~~~~~~~~~~~ + +``PLHashTable`` is a part of NSPR. The header file can be found at `plhash.h +`_. + +There are two situations where ``PLHashTable`` may be preferable: + +- You need entry-pointers to remain constant. +- The entries stored in the table are very large (larger than 12 + words). + +.. _nsTHashtable: + +nsTHashtable +~~~~~~~~~~~~ + +To use ``nsTHashtable``, you must declare an entry-class. This +entry class contains the key and the data that you are hashing. It also +declares functions that manipulate the key. In most cases, the functions +of this entry class can be entirely inline. For examples of entry classes, +see the declarations at `nsHashKeys.h +`_. + +The template parameter is the entry class. After construction, use the +functions ``PutEntry/GetEntry/RemoveEntry`` to alter the hashtable. The +``Iterator`` class will do iteration, but beware that the iteration will +occur in a seemingly-random order (no sorting). + +- ``nsTHashtable``\ s can be allocated on the stack, as class members, + or on the heap. +- Entry pointers can and do change when items are added to or removed + from the hashtable. Do not keep long-lasting pointers to entries. +- because of this, ``nsTHashtable`` is not inherently thread-safe. If + you use a hashtable in a multi-thread environment, you must provide + locking as appropriate. + +Before using ``nsTHashtable``, see if ``nsBaseHashtable`` and relatives +will work for you. They are much easier to use, because you do not have +to declare an entry class. If you are hashing a simple key type to a +simple data type, they are generally a better choice. + +.. _nsBaseHashtable_and_friends:nsTHashMap.2C_nsInterfaceHashtable.2C_and_nsClassHashtable: + +nsBaseHashtable and friends: nsTHashMap, nsInterfaceHashtable, and nsClassHashtable +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +These C++ templates provide a high-level interface for using hashtables +that hides most of the complexities of the underlying implementation. They +provide the following features: + +- hashtable operations can be completed without using an entry class, + making code easier to read +- optional thread-safety: the hashtable can manage a read-write lock + around the table +- predefined key classes provide automatic cleanup of + strings/interfaces +- ``nsInterfaceHashtable`` and ``nsClassHashtable`` automatically + release/delete objects to avoid leaks. + +``nsBaseHashtable`` is not used directly; choose one of the three +derivative classes based on the data type you want to store. The +``KeyClass`` is taken from `nsHashKeys.h +`_ and is the same for all +three classes: + +- ``nsTHashMap`` - ``DataType`` is a simple + type such as ``uint32_t`` or ``bool``. +- ``nsInterfaceHashtable`` - ``Interface`` is an + XPCOM interface such as ``nsISupports`` or ``nsIDocShell`` +- ``nsClassHashtable`` - ``T`` is any C++ class. The + hashtable stores a pointer to the object, and deletes that object + when the entry is removed. + +The important files to read are +`nsBaseHashtable.h `_ +and +`nsHashKeys.h `_. +These classes can be used on the stack, as a class member, or on the heap. + +.. _Using_nsTHashtable_as_a_hash-set: + +Using nsTHashtable as a hash-set +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +A hash set only tracks the existence of keys: it does not associate data +with the keys. This can be done using ``nsTHashtable``. +The appropriate entries are GetEntry and PutEntry. -- cgit v1.2.3