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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#ifndef HASHTABLE_H
#define HASHTABLE_H 1
#include <dix-config.h>
#include <X11/Xfuncproto.h>
#include <X11/Xdefs.h>
#include "list.h"
/** @brief A hashing function.
@param[in/out] cdata Opaque data that can be passed to HtInit that will
eventually end up here
@param[in] ptr The data to be hashed. The size of the data, if
needed, can be configured via a record that can be
passed via cdata.
@param[in] numBits The number of bits this hash needs to have in the
resulting hash
@return A numBits-bit hash of the data
*/
typedef unsigned (*HashFunc)(void * cdata, const void * ptr, int numBits);
/** @brief A comparison function for hashed keys.
@param[in/out] cdata Opaque data that ca be passed to Htinit that will
eventually end up here
@param[in] l The left side data to be compared
@param[in] r The right side data to be compared
@return -1 if l < r, 0 if l == r, 1 if l > r
*/
typedef int (*HashCompareFunc)(void * cdata, const void * l, const void * r);
struct HashTableRec;
typedef struct HashTableRec *HashTable;
/** @brief A configuration for HtGenericHash */
typedef struct {
int keySize;
} HtGenericHashSetupRec, *HtGenericHashSetupPtr;
/** @brief ht_create initalizes a hash table for a certain hash table
configuration
@param[out] ht The hash table structure to initialize
@param[in] keySize The key size in bytes
@param[in] dataSize The data size in bytes
@param[in] hash The hash function to use for hashing keys
@param[in] compare The comparison function for hashing keys
@param[in] cdata Opaque data that will be passed to hash and
comparison functions
*/
extern _X_EXPORT HashTable ht_create(int keySize,
int dataSize,
HashFunc hash,
HashCompareFunc compare,
pointer cdata);
/** @brief HtDestruct deinitializes the structure. It does not free the
memory allocated to HashTableRec
*/
extern _X_EXPORT void ht_destroy(HashTable ht);
/** @brief Adds a new key to the hash table. The key will be copied
and a pointer to the value will be returned. The data will
be initialized with zeroes.
@param[in/out] ht The hash table
@param[key] key The key. The contents of the key will be copied.
@return On error NULL is returned, otherwise a pointer to the data
associated with the newly inserted key.
@note If dataSize is 0, a pointer to the end of the key may be returned
to avoid returning NULL. Obviously the data pointed cannot be
modified, as implied by dataSize being 0.
*/
extern _X_EXPORT pointer ht_add(HashTable ht, pointer key);
/** @brief Removes a key from the hash table along with its
associated data, which will be free'd.
*/
extern _X_EXPORT void ht_remove(HashTable ht, pointer key);
/** @brief Finds the associated data of a key from the hash table.
@return If the key cannot be found, the function returns NULL.
Otherwise it returns a pointer to the data associated
with the key.
@note If dataSize == 0, this function may return NULL
even if the key has been inserted! If dataSize == NULL,
use HtMember instead to determine if a key has been
inserted.
*/
extern _X_EXPORT pointer ht_find(HashTable ht, pointer key);
/** @brief A generic hash function */
extern _X_EXPORT unsigned ht_generic_hash(void *cdata,
const void *ptr,
int numBits);
/** @brief A generic comparison function. It compares data byte-wise. */
extern _X_EXPORT int ht_generic_compare(void *cdata,
const void *l,
const void *r);
/** @brief A debugging function that dumps the distribution of the
hash table: for each bucket, list the number of elements
contained within. */
extern _X_EXPORT void ht_dump_distribution(HashTable ht);
/** @brief A debugging function that dumps the contents of the hash
table: for each bucket, list the elements contained
within. */
extern _X_EXPORT void ht_dump_contents(HashTable ht,
void (*print_key)(void *opaque, void *key),
void (*print_value)(void *opaque, void *value),
void* opaque);
/** @brief A hashing function to be used for hashing resource IDs when
used with HashTables. It makes no use of cdata, so that can
be NULL. It uses HashXID underneath, and should HashXID be
unable to hash the value, it switches into using the generic
hash function. */
extern _X_EXPORT unsigned ht_resourceid_hash(void *cdata,
const void * data,
int numBits);
/** @brief A comparison function to be used for comparing resource
IDs when used with HashTables. It makes no use of cdata,
so that can be NULL. */
extern _X_EXPORT int ht_resourceid_compare(void *cdata,
const void *a,
const void *b);
#endif // HASHTABLE_H
|
