1 /*****************************************************************************/
5 /* Generic hash table */
9 /* (C) 2003-2011, 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 /*****************************************************************************/
53 /* Hash table node. NOTE: This structure must be the first member of a struct
54 ** that is hashed by the module. Having it first allows to omit a pointer to
55 ** the entry itself, because the C standard guarantees that a pointer to a
56 ** struct can be converted to its first member.
58 typedef struct HashNode HashNode;
60 HashNode* Next; /* Next entry in hash list */
61 unsigned Hash; /* The full hash value */
64 #define STATIC_HASHNODE_INITIALIZER { 0, 0, 0 }
66 /* Hash table functions */
67 typedef struct HashFunctions HashFunctions;
68 struct HashFunctions {
70 unsigned (*GenHash) (const void* Key);
71 /* Generate the hash over a key. */
73 const void* (*GetKey) (const void* Entry);
74 /* Given a pointer to the user entry data, return a pointer to the key */
76 int (*Compare) (const void* Key1, const void* Key2);
77 /* Compare two keys. The function must return a value less than zero if
78 ** Key1 is smaller than Key2, zero if both are equal, and a value greater
79 ** than zero if Key1 is greater then Key2.
84 typedef struct HashTable HashTable;
86 unsigned Slots; /* Number of table slots */
87 unsigned Count; /* Number of table entries */
88 HashNode** Table; /* Table, dynamically allocated */
89 const HashFunctions* Func; /* Table functions */
92 #define STATIC_HASHTABLE_INITIALIZER(Slots, Func) { Slots, 0, 0, Func }
96 /*****************************************************************************/
98 /*****************************************************************************/
102 #if defined(HAVE_INLINE)
103 INLINE void InitHashNode (HashNode* N)
104 /* Initialize a hash node. */
109 #define InitHashNode(N) do { (N)->Next = 0; } while (0)
114 /*****************************************************************************/
115 /* struct HashTable */
116 /*****************************************************************************/
120 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func);
121 /* Initialize a hash table and return it */
123 void DoneHashTable (HashTable* T);
124 /* Destroy the contents of a hash table. Note: This will not free the entries
128 #if defined(HAVE_INLINE)
129 INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
130 /* Create a new hash table and return it. */
132 /* Allocate memory, initialize and return it */
133 return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func);
136 #define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func)
139 void FreeHashTable (HashTable* T);
140 /* Free a hash table. Note: This will not free the entries in the table! */
142 #if defined(HAVE_INLINE)
143 INLINE unsigned HT_GetCount (const HashTable* T)
144 /* Return the number of items in the table. */
149 #define HT_GetCount(T) ((T)->Count)
152 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash);
153 /* Find the node with the given key. Differs from HT_Find in that the hash
154 ** for the key is precalculated and passed to the function.
157 void* HT_Find (const HashTable* T, const void* Key);
158 /* Find the entry with the given key and return it */
160 void HT_Insert (HashTable* T, void* Entry);
161 /* Insert an entry into the given hash table */
163 void HT_Remove (HashTable* T, void* Entry);
164 /* Remove an entry from the given hash table */
166 void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data);
167 /* Walk over all nodes of a hash table, optionally deleting entries from the
168 ** table. For each node, the user supplied function F is called, passing a
169 ** pointer to the entry, and the data pointer passed to HT_Walk by the caller.
170 ** If F returns true, the node is deleted from the hash table otherwise it's
171 ** left in place. While deleting the node, the node is not accessed, so it is
172 ** safe for F to free the memory associcated with the entry.
177 /* End of hashtab.h */