3 * Hash table implemenation.
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)
13 typedef struct HASHSTRUCT * HASHTYPE;
15 /* function pointer types to deal with the datatypes the hash works with */
17 #define hashFunctionType JOIN(HASHTYPE,HashFunctionType)
18 #define hashEqualityType JOIN(HASHTYPE,HashEqualityType)
19 #define hashFreeKey JOIN(HASHTYPE,FreeKey)
21 typedef unsigned int (*hashFunctionType) (HTKEYTYPE string);
22 typedef int (*hashEqualityType) (HTKEYTYPE key1, HTKEYTYPE key2);
23 typedef HTKEYTYPE (*hashFreeKey) (HTKEYTYPE);
26 #define hashFreeData JOIN(HASHTYPE,FreeData)
27 typedef HTDATATYPE (*hashFreeData) (HTDATATYPE);
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
42 HASHTYPE HASHPREFIX(Create)(int numBuckets,
43 hashFunctionType fn, hashEqualityType eq,
46 , hashFreeData freeData
52 * @param ht pointer to hash table
56 HASHTYPE HASHPREFIX(Free)( HASHTYPE ht);
59 * Remove all entries from the hash table.
60 * @param ht pointer to hash table
63 void HASHPREFIX(Empty)(HASHTYPE ht);
66 * Calculate hash for key.
67 * @param @ht pointer to hash table
71 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key);
74 * Add item to hash table.
75 * @param ht pointer to hash table
77 * @param data data value
80 void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
87 * Retrieve item from hash table.
88 * @param ht pointer to hash table
89 * @param key key value
90 * @retval data address to store data value from bucket
91 * @retval dataCount address to store data value size from bucket
92 * @retval tableKey address to store key value from bucket (may be NULL)
93 * @return 1 on success, 0 if the item is not found.
96 int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
101 HTKEYTYPE* tableKey);
104 * Check for key in hash table.
105 * @param ht pointer to hash table
106 * @param key key value
107 * @return 1 if the key is present, 0 otherwise
110 int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key);
113 * How many buckets are currently allocated (result is implementation
115 * @param ht pointer to hash table
116 * @result number of buckets allocated
119 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht);
122 * How many buckets are used (result is implementation dependent)
123 * @param ht pointer to hash table
124 * @result number of buckets used
127 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht);
130 * How many (unique) keys have been added to the hash table
131 * @param ht pointer to hash table
132 * @result number of unique keys
135 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht);
139 * How many data entries have been added to the hash table
140 * @param ht pointer to hash table
141 * @result number of data entries
144 unsigned int HASHPREFIX(NumData)(HASHTYPE ht);
148 * Print statistics about the hash to stderr
149 * This is for debugging only
150 * @param ht pointer to hash table
153 void HASHPREFIX(PrintStats)(HASHTYPE ht);