1 /** 2 * \file lib/rpmhash.h 3 * Hash table implemenation. 4 */ 5 6 #include <string.h> 7 // Hackery to make sure that macros get expanded 8 #define __JOIN(a,b) a##b 9 #define JOIN(a,b) __JOIN(a,b) 10 #define HASHPREFIX(name) JOIN(HASHTYPE,name) 11 #define HASHSTRUCT JOIN(HASHTYPE,_s) 12 13 typedef struct HASHSTRUCT * HASHTYPE; 14 15 /* function pointer types to deal with the datatypes the hash works with */ 16 17 #define hashFunctionType JOIN(HASHTYPE,HashFunctionType) 18 #define hashEqualityType JOIN(HASHTYPE,HashEqualityType) 19 #define hashFreeKey JOIN(HASHTYPE,FreeKey) 20 21 typedef unsigned int (*hashFunctionType) (HTKEYTYPE string); 22 typedef int (*hashEqualityType) (HTKEYTYPE key1, HTKEYTYPE key2); 23 typedef HTKEYTYPE (*hashFreeKey) (HTKEYTYPE); 24 25 #ifdef HTDATATYPE 26 #define hashFreeData JOIN(HASHTYPE,FreeData) 27 typedef HTDATATYPE (*hashFreeData) (HTDATATYPE); 28 #endif 29 30 /** 31 * Create hash table. 32 * If keySize > 0, the key is duplicated within the table (which costs 33 * memory, but may be useful anyway. 34 * @param numBuckets number of hash buckets 35 * @param fn function to generate hash value for key 36 * @param eq function to compare hash keys for equality 37 * @param freeKey function to free the keys or NULL 38 * @param freeData function to free the data or NULL 39 * @return pointer to initialized hash table 40 */ 41 RPM_GNUC_INTERNAL 42 HASHTYPE HASHPREFIX(Create)(int numBuckets, 43 hashFunctionType fn, hashEqualityType eq, 44 hashFreeKey freeKey 45 #ifdef HTDATATYPE 46 , hashFreeData freeData 47 #endif 48 ); 49 50 /** 51 * Destroy hash table. 52 * @param ht pointer to hash table 53 * @return NULL always 54 */ 55 RPM_GNUC_INTERNAL 56 HASHTYPE HASHPREFIX(Free)( HASHTYPE ht); 57 58 /** 59 * Remove all entries from the hash table. 60 * @param ht pointer to hash table 61 */ 62 RPM_GNUC_INTERNAL 63 void HASHPREFIX(Empty)(HASHTYPE ht); 64 65 /** 66 * Calculate hash for key. 67 * @param @ht pointer to hash table 68 * @param @key key 69 */ 70 RPM_GNUC_INTERNAL 71 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key); 72 73 /** 74 * Add item to hash table. 75 * @param ht pointer to hash table 76 * @param key key 77 * @param data data value 78 */ 79 RPM_GNUC_INTERNAL 80 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key 81 #ifdef HTDATATYPE 82 , HTDATATYPE data 83 #endif 84 ); 85 86 /* Add item to hash table with precalculated key hash. */ 87 RPM_GNUC_INTERNAL 88 void HASHPREFIX(AddHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash 89 #ifdef HTDATATYPE 90 , HTDATATYPE data 91 #endif 92 ); 93 94 /** 95 * Retrieve item from hash table. 96 * @param ht pointer to hash table 97 * @param key key value 98 * @retval data address to store data value from bucket 99 * @retval dataCount address to store data value size from bucket 100 * @retval tableKey address to store key value from bucket (may be NULL) 101 * @return 1 on success, 0 if the item is not found. 102 */ 103 RPM_GNUC_INTERNAL 104 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, 105 #ifdef HTDATATYPE 106 HTDATATYPE** data, 107 int * dataCount, 108 #endif 109 HTKEYTYPE* tableKey); 110 111 /* Retrieve item from hash table with precalculated key hash. */ 112 RPM_GNUC_INTERNAL 113 int HASHPREFIX(GetHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash, 114 #ifdef HTDATATYPE 115 HTDATATYPE** data, 116 int * dataCount, 117 #endif 118 HTKEYTYPE* tableKey); 119 120 /** 121 * Check for key in hash table. 122 * @param ht pointer to hash table 123 * @param key key value 124 * @return 1 if the key is present, 0 otherwise 125 */ 126 RPM_GNUC_INTERNAL 127 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key); 128 129 /* Check for key in hash table with precalculated key hash. */ 130 RPM_GNUC_INTERNAL 131 int HASHPREFIX(HasHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash); 132 133 /** 134 * How many buckets are currently allocated (result is implementation 135 * dependent) 136 * @param ht pointer to hash table 137 * @result number of buckets allocated 138 */ 139 RPM_GNUC_INTERNAL 140 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht); 141 142 /** 143 * How many buckets are used (result is implementation dependent) 144 * @param ht pointer to hash table 145 * @result number of buckets used 146 */ 147 RPM_GNUC_INTERNAL 148 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht); 149 150 /** 151 * How many (unique) keys have been added to the hash table 152 * @param ht pointer to hash table 153 * @result number of unique keys 154 */ 155 RPM_GNUC_INTERNAL 156 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht); 157 158 #ifdef HTDATATYPE 159 /** 160 * How many data entries have been added to the hash table 161 * @param ht pointer to hash table 162 * @result number of data entries 163 */ 164 RPM_GNUC_INTERNAL 165 unsigned int HASHPREFIX(NumData)(HASHTYPE ht); 166 #endif 167 168 /** 169 * Print statistics about the hash to stderr 170 * This is for debugging only 171 * @param ht pointer to hash table 172 */ 173 RPM_GNUC_INTERNAL 174 void HASHPREFIX(PrintStats)(HASHTYPE ht); 175