xpcom/docs/hashtables_detailed.rst

   1 XPCOM Hashtable Technical Details
   2 =================================
   3
   4 .. note::
   5
   6    This is a deep-dive into the underlying mechanisms that power the XPCOM
   7    hashtables. Some of this information is quite old and may be out of date. If
   8    you're looking for how to use XPCOM hashtables, you should consider reading
   9    the :ref:`XPCOM Hashtable Guide` instead.
  10
  11 Mozilla's Hashtable Implementations
  12 -----------------------------------
  13
  14 Mozilla has several hashtable implementations, which have been tested
  15 and tuned, and hide the inner complexities of hashtable implementations:
  16
  17 -  ``PLHashTable`` - low-level C API; entry class pointers are constant;
  18    more efficient for large entry structures; often wastes memory making
  19    many small heap allocations.
  20 -  ``nsTHashtable`` - low-level C++ wrapper around ``PLDHash``;
  21    generates callback functions and handles most casting automagically.
  22    Client writes their own entry class which can include complex key and
  23    data types.
  24 -  ``nsTHashMap/nsInterfaceHashtable/nsClassHashtable`` -
  25    simplifies the common usage pattern mapping a simple keytype to a
  26    simple datatype; client does not need to declare or manage an entry class;
  27    ``nsTHashMap`` datatype is a scalar such as ``uint64_t``;
  28    ``nsInterfaceHashtable`` datatype is an XPCOM interface;
  29    ``nsClassHashtable`` datatype is a class pointer owned by the
  30    hashtable.
  31
  32 .. _PLHashTable:
  33
  34 PLHashTable
  35 ~~~~~~~~~~~
  36
  37 ``PLHashTable`` is a part of NSPR. The header file can be found at `plhash.h
  38 <https://searchfox.org/mozilla-central/source/nsprpub/lib/ds/plhash.h>`_.
  39
  40 There are two situations where ``PLHashTable`` may be preferable:
  41
  42 -  You need entry-pointers to remain constant.
  43 -  The entries stored in the table are very large (larger than 12
  44    words).
  45
  46 .. _nsTHashtable:
  47
  48 nsTHashtable
  49 ~~~~~~~~~~~~
  50
  51 To use ``nsTHashtable``, you must declare an entry-class. This
  52 entry class contains the key and the data that you are hashing. It also
  53 declares functions that manipulate the key. In most cases, the functions
  54 of this entry class can be entirely inline. For examples of entry classes,
  55 see the declarations at `nsHashKeys.h
  56 <https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_.
  57
  58 The template parameter is the entry class. After construction, use the
  59 functions ``PutEntry/GetEntry/RemoveEntry`` to alter the hashtable. The
  60 ``Iterator`` class will do iteration, but beware that the iteration will
  61 occur in a seemingly-random order (no sorting).
  62
  63 -  ``nsTHashtable``\ s can be allocated on the stack, as class members,
  64    or on the heap.
  65 -  Entry pointers can and do change when items are added to or removed
  66    from the hashtable. Do not keep long-lasting pointers to entries.
  67 -  because of this, ``nsTHashtable`` is not inherently thread-safe. If
  68    you use a hashtable in a multi-thread environment, you must provide
  69    locking as appropriate.
  70
  71 Before using ``nsTHashtable``, see if ``nsBaseHashtable`` and relatives
  72 will work for you. They are much easier to use, because you do not have
  73 to declare an entry class. If you are hashing a simple key type to a
  74 simple data type, they are generally a better choice.
  75
  76 .. _nsBaseHashtable_and_friends:nsTHashMap.2C_nsInterfaceHashtable.2C_and_nsClassHashtable:
  77
  78 nsBaseHashtable and friends: nsTHashMap, nsInterfaceHashtable, and nsClassHashtable
  79 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  80
  81 These C++ templates provide a high-level interface for using hashtables
  82 that hides most of the complexities of the underlying implementation. They
  83 provide the following features:
  84
  85 -  hashtable operations can be completed without using an entry class,
  86    making code easier to read
  87 -  optional thread-safety: the hashtable can manage a read-write lock
  88    around the table
  89 -  predefined key classes provide automatic cleanup of
  90    strings/interfaces
  91 -  ``nsInterfaceHashtable`` and ``nsClassHashtable`` automatically
  92    release/delete objects to avoid leaks.
  93
  94 ``nsBaseHashtable`` is not used directly; choose one of the three
  95 derivative classes based on the data type you want to store. The
  96 ``KeyClass`` is taken from `nsHashKeys.h
  97 <https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_ and is the same for all
  98 three classes:
  99
 100 -  ``nsTHashMap<KeyClass, DataType>`` - ``DataType`` is a simple
 101    type such as ``uint32_t`` or ``bool``.
 102 -  ``nsInterfaceHashtable<KeyClass, Interface>`` - ``Interface`` is an
 103    XPCOM interface such as ``nsISupports`` or ``nsIDocShell``
 104 -  ``nsClassHashtable<KeyClass, T>`` - ``T`` is any C++ class. The
 105    hashtable stores a pointer to the object, and deletes that object
 106    when the entry is removed.
 107
 108 The important files to read are
 109 `nsBaseHashtable.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsBaseHashtable.h>`_
 110 and
 111 `nsHashKeys.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_.
 112 These classes can be used on the stack, as a class member, or on the heap.
 113
 114 .. _Using_nsTHashtable_as_a_hash-set:
 115
 116 Using nsTHashtable as a hash-set
 117 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 118
 119 A hash set only tracks the existence of keys: it does not associate data
 120 with the keys. This can be done using ``nsTHashtable<nsSomeHashKey>``.
 121 The appropriate entries are GetEntry and PutEntry.