1#ifndef HASHTABLE_H
2#define HASHTABLE_H 1
3
4#include <dix-config.h>
5#include <X11/Xfuncproto.h>
6#include <X11/Xdefs.h>
7#include "list.h"
8
9/** @brief A hashing function.
10
11  @param[in/out] cdata  Opaque data that can be passed to HtInit that will
12                        eventually end up here
13  @param[in] ptr        The data to be hashed. The size of the data, if
14                        needed, can be configured via a record that can be
15                        passed via cdata.
16  @param[in] numBits    The number of bits this hash needs to have in the
17                        resulting hash
18
19  @return  A numBits-bit hash of the data
20*/
21typedef unsigned (*HashFunc)(void * cdata, const void * ptr, int numBits);
22
23/** @brief A comparison function for hashed keys.
24
25  @param[in/out] cdata  Opaque data that ca be passed to Htinit that will
26                        eventually end up here
27  @param[in] l          The left side data to be compared
28  @param[in] r          The right side data to be compared
29
30  @return -1 if l < r, 0 if l == r, 1 if l > r
31*/
32typedef int (*HashCompareFunc)(void * cdata, const void * l, const void * r);
33
34struct HashTableRec;
35
36typedef struct HashTableRec *HashTable;
37
38/** @brief  A configuration for HtGenericHash */
39typedef struct {
40    int             keySize;
41} HtGenericHashSetupRec, *HtGenericHashSetupPtr;
42
43/** @brief  ht_create initializes a hash table for a certain hash table
44            configuration
45
46    @param[out] ht       The hash table structure to initialize
47    @param[in] keySize   The key size in bytes
48    @param[in] dataSize  The data size in bytes
49    @param[in] hash      The hash function to use for hashing keys
50    @param[in] compare   The comparison function for hashing keys
51    @param[in] cdata     Opaque data that will be passed to hash and
52                         comparison functions
53*/
54extern _X_EXPORT HashTable ht_create(int             keySize,
55                                     int             dataSize,
56                                     HashFunc        hash,
57                                     HashCompareFunc compare,
58                                     void            *cdata);
59/** @brief  HtDestruct deinitializes the structure. It does not free the
60            memory allocated to HashTableRec
61*/
62extern _X_EXPORT void ht_destroy(HashTable ht);
63
64/** @brief  Adds a new key to the hash table. The key will be copied
65            and a pointer to the value will be returned. The data will
66            be initialized with zeroes.
67
68  @param[in/out] ht  The hash table
69  @param[key] key    The key. The contents of the key will be copied.
70
71  @return On error NULL is returned, otherwise a pointer to the data
72          associated with the newly inserted key.
73
74  @note  If dataSize is 0, a pointer to the end of the key may be returned
75         to avoid returning NULL. Obviously the data pointed cannot be
76         modified, as implied by dataSize being 0.
77*/
78extern _X_EXPORT void *ht_add(HashTable ht, const void *key);
79
80/** @brief  Removes a key from the hash table along with its
81            associated data, which will be free'd.
82*/
83extern _X_EXPORT void ht_remove(HashTable ht, const void *key);
84
85/** @brief  Finds the associated data of a key from the hash table.
86
87   @return  If the key cannot be found, the function returns NULL.
88            Otherwise it returns a pointer to the data associated
89            with the key.
90
91   @note  If dataSize == 0, this function may return NULL
92          even if the key has been inserted! If dataSize == NULL,
93          use HtMember instead to determine if a key has been
94          inserted.
95*/
96extern _X_EXPORT void *ht_find(HashTable ht, const void *key);
97
98/** @brief  A generic hash function */
99extern _X_EXPORT unsigned ht_generic_hash(void *cdata,
100                                          const void *ptr,
101                                          int numBits);
102
103/** @brief  A generic comparison function. It compares data byte-wise. */
104extern _X_EXPORT int ht_generic_compare(void *cdata,
105                                        const void *l,
106                                        const void *r);
107
108/** @brief  A debugging function that dumps the distribution of the
109            hash table: for each bucket, list the number of elements
110            contained within. */
111extern _X_EXPORT void ht_dump_distribution(HashTable ht);
112
113/** @brief  A debugging function that dumps the contents of the hash
114            table: for each bucket, list the elements contained
115            within. */
116extern _X_EXPORT void ht_dump_contents(HashTable ht,
117                                       void (*print_key)(void *opaque, void *key),
118                                       void (*print_value)(void *opaque, void *value),
119                                       void* opaque);
120
121/** @brief  A hashing function to be used for hashing resource IDs when
122            used with HashTables. It makes no use of cdata, so that can
123            be NULL. It uses HashXID underneath, and should HashXID be
124            unable to hash the value, it switches into using the generic
125            hash function. */
126extern _X_EXPORT unsigned ht_resourceid_hash(void *cdata,
127                                             const void * data,
128                                             int numBits);
129
130/** @brief  A comparison function to be used for comparing resource
131            IDs when used with HashTables. It makes no use of cdata,
132            so that can be NULL. */
133extern _X_EXPORT int ht_resourceid_compare(void *cdata,
134                                           const void *a,
135                                           const void *b);
136
137#endif // HASHTABLE_H
138