| 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 initalizes 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 | pointer 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 pointer ht_add(HashTable ht, pointer 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, pointer 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 pointer ht_find(HashTable ht, pointer 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 |