1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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.
|
