repositories / deb_xorg-server.git / blame
| Commit | Line | Data |
|---|---|---|
| a09e091a JB |
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 |