hashtable.h (5663B)
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 */ 21 typedef 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 */ 32 typedef int (*HashCompareFunc)(void * cdata, const void * l, const void * r); 33 34 struct HashTableRec; 35 36 typedef struct HashTableRec *HashTable; 37 38 /** @brief A configuration for HtGenericHash */ 39 typedef 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 */ 54 extern _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 */ 62 extern _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 */ 78 extern _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 */ 83 extern _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 */ 96 extern _X_EXPORT void *ht_find(HashTable ht, const void *key); 97 98 /** @brief A generic hash function */ 99 extern _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. */ 104 extern _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. */ 111 extern _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. */ 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), 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. */ 126 extern _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. */ 133 extern _X_EXPORT int ht_resourceid_compare(void *cdata, 134 const void *a, 135 const void *b); 136 137 #endif // HASHTABLE_H