4 #include <dix-config.h>
5 #include <X11/Xfuncproto.h>
9 /** @brief A hashing function.
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
16 @param[in] numBits The number of bits this hash needs to have in the
19 @return A numBits-bit hash of the data
21 typedef unsigned (*HashFunc
)(void * cdata
, const void * ptr
, int numBits
);
23 /** @brief A comparison function for hashed keys.
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
30 @return -1 if l < r, 0 if l == r, 1 if l > r
32 typedef int (*HashCompareFunc
)(void * cdata
, const void * l
, const void * r
);
36 typedef struct HashTableRec
*HashTable
;
38 /** @brief A configuration for HtGenericHash */
41 } HtGenericHashSetupRec
, *HtGenericHashSetupPtr
;
43 /** @brief ht_create initalizes a hash table for a certain hash table
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
54 extern _X_EXPORT HashTable
ht_create(int keySize
,
57 HashCompareFunc compare
,
59 /** @brief HtDestruct deinitializes the structure. It does not free the
60 memory allocated to HashTableRec
62 extern _X_EXPORT
void ht_destroy(HashTable ht
);
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.
68 @param[in/out] ht The hash table
69 @param[key] key The key. The contents of the key will be copied.
71 @return On error NULL is returned, otherwise a pointer to the data
72 associated with the newly inserted key.
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.
78 extern _X_EXPORT pointer
ht_add(HashTable ht
, pointer key
);
80 /** @brief Removes a key from the hash table along with its
81 associated data, which will be free'd.
83 extern _X_EXPORT
void ht_remove(HashTable ht
, pointer key
);
85 /** @brief Finds the associated data of a key from the hash table.
87 @return If the key cannot be found, the function returns NULL.
88 Otherwise it returns a pointer to the data associated
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
96 extern _X_EXPORT pointer
ht_find(HashTable ht
, pointer key
);
98 /** @brief A generic hash function */
99 extern _X_EXPORT
unsigned ht_generic_hash(void *cdata
,
103 /** @brief A generic comparison function. It compares data byte-wise. */
104 extern _X_EXPORT
int ht_generic_compare(void *cdata
,
108 /** @brief A debugging function that dumps the distribution of the
109 hash table: for each bucket, list the number of elements
111 extern _X_EXPORT
void ht_dump_distribution(HashTable ht
);
113 /** @brief A debugging function that dumps the contents of the hash
114 table: for each bucket, list the elements contained
116 extern _X_EXPORT
void ht_dump_contents(HashTable ht
,
117 void (*print_key
)(void *opaque
, void *key
),
118 void (*print_value
)(void *opaque
, void *value
),
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
126 extern _X_EXPORT
unsigned ht_resourceid_hash(void *cdata
,
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. */
133 extern _X_EXPORT
int ht_resourceid_compare(void *cdata
,
137 #endif // HASHTABLE_H