1 /*****************************************************************************/
5 /* Generic hash table */
9 /* (C) 2003-2008 Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
47 /*****************************************************************************/
49 /*****************************************************************************/
54 typedef struct HashNode HashNode;
56 HashNode* Next; /* Next entry in hash list */
57 struct HashTable* Owner; /* Owner table */
58 unsigned Hash; /* The full hash value */
59 void* Entry; /* Pointer to user entry data */
62 #define STATIC_HASHNODE_INITIALIZER(Entry) { 0, 0, 0, Entry }
64 /* Hash table functions */
65 typedef struct HashFunctions HashFunctions;
66 struct HashFunctions {
68 unsigned (*GenHash) (const void* Key);
69 /* Generate the hash over a key. */
71 const void* (*GetKey) (void* Entry);
72 /* Given a pointer to the user entry data, return a pointer to the key */
74 HashNode* (*GetHashNode) (void* Entry);
75 /* Given a pointer to the user entry data, return a pointer to the hash node */
77 int (*Compare) (const void* Key1, const void* Key2);
78 /* Compare two keys. The function must return a value less than zero if
79 * Key1 is smaller than Key2, zero if both are equal, and a value greater
80 * than zero if Key1 is greater then Key2.
85 typedef struct HashTable HashTable;
87 unsigned Slots; /* Number of table slots */
88 unsigned Count; /* Number of table entries */
89 HashNode** Table; /* Table, dynamically allocated */
90 const HashFunctions* Func; /* Table functions */
93 #define STATIC_HASHTABLE_INITIALIZER(Slots, Func) { Slots, 0, 0, Func }
97 /*****************************************************************************/
99 /*****************************************************************************/
103 #if defined(HAVE_INLINE)
104 INLINE void InitHashNode (HashNode* N, void* Entry)
105 /* Initialize a hash node. */
112 #define InitHashNode(N, E) \
118 #if defined(HAVE_INLINE)
119 INLINE void* HN_GetEntry (HashNode* N)
120 /* Get the entry from a hash node */
125 #define HN_GetEntry(N) (N)->Entry
130 /*****************************************************************************/
131 /* struct HashTable */
132 /*****************************************************************************/
136 #if defined(HAVE_INLINE)
137 INLINE HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
138 /* Initialize a hash table and return it */
140 /* Initialize the fields */
146 /* Return the initialized table */
150 #define InitHashTable(T, Slots, Func) \
151 (T)->Slots = (Slots), \
154 (T)->Func = (Func), \
158 #if defined(HAVE_INLINE)
159 INLINE void DoneHashTable (HashTable* T)
160 /* Destroy the contents of a hash table. Note: This will not free the entries
164 /* Just free the array with the table pointers */
168 #define DoneHashTable(T) xfree ((T)->Table)
171 #if defined(HAVE_INLINE)
172 INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
173 /* Create a new hash table and return it. */
175 /* Allocate memory, initialize and return it */
176 return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func);
179 #define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func)
182 void FreeHashTable (HashTable* T);
183 /* Free a hash table. Note: This will not free the entries in the table! */
185 HashNode* HT_Find (const HashTable* T, const void* Key);
186 /* Find the node with the given key*/
188 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash);
189 /* Find the node with the given key. Differs from HT_Find in that the hash
190 * for the key is precalculated and passed to the function.
193 void* HT_FindEntry (const HashTable* T, const void* Key);
194 /* Find the node with the given key and return the corresponding entry */
196 void HT_Insert (HashTable* T, HashNode* N);
197 /* Insert a node into the given hash table */
199 void HT_InsertEntry (HashTable* T, void* Entry);
200 /* Insert an entry into the given hash table */
202 void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data);
203 /* Walk over all nodes of a hash table. For each node, the user supplied
204 * function F is called, passing a pointer to the entry, and the data pointer
205 * passed to HT_Walk by the caller.
210 /* End of hashtab.h */