summaryrefslogtreecommitdiffstats
path: root/xpcom/docs/hashtables_detailed.rst
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--xpcom/docs/hashtables_detailed.rst121
1 files changed, 121 insertions, 0 deletions
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
+<https://searchfox.org/mozilla-central/source/nsprpub/lib/ds/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
+<https://searchfox.org/mozilla-central/source/xpcom/ds/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
+<https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_ and is the same for all
+three classes:
+
+- ``nsTHashMap<KeyClass, DataType>`` - ``DataType`` is a simple
+ type such as ``uint32_t`` or ``bool``.
+- ``nsInterfaceHashtable<KeyClass, Interface>`` - ``Interface`` is an
+ XPCOM interface such as ``nsISupports`` or ``nsIDocShell``
+- ``nsClassHashtable<KeyClass, T>`` - ``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 <https://searchfox.org/mozilla-central/source/xpcom/ds/nsBaseHashtable.h>`_
+and
+`nsHashKeys.h <https://searchfox.org/mozilla-central/source/xpcom/ds/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<nsSomeHashKey>``.
+The appropriate entries are GetEntry and PutEntry.