1 /*****************************************************************************/
2 /* */
3 /* hashtab.h */
4 /* */
5 /* Generic hash table */
6 /* */
7 /* */
8 /* */
9 /* (C) 2003-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
13 /* */
14 /* */
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. */
18 /* */
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: */
22 /* */
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 */
30 /* distribution. */
31 /* */
32 /*****************************************************************************/
33
34
35
36 #ifndef HASHTAB_H
37 #define HASHTAB_H
38
39
40
41 /* common */
42 #include "inline.h"
43 #include "xmalloc.h"
44
45
46
47 /*****************************************************************************/
48 /* Data */
49 /*****************************************************************************/
50
51
52
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.
57 */
58 typedef struct HashNode HashNode;
59 struct HashNode {
60 HashNode* Next; /* Next entry in hash list */
61 unsigned Hash; /* The full hash value */
62 };
63
64 #define STATIC_HASHNODE_INITIALIZER { 0, 0, 0 }
65
66 /* Hash table functions */
67 typedef struct HashFunctions HashFunctions;
68 struct HashFunctions {
69
70 unsigned (*GenHash) (const void* Key);
71 /* Generate the hash over a key. */
72
73 const void* (*GetKey) (const void* Entry);
74 /* Given a pointer to the user entry data, return a pointer to the key */
75
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.
80 */
81 };
82
83 /* Hash table */
84 typedef struct HashTable HashTable;
85 struct 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 */
90 };
91
92 #define STATIC_HASHTABLE_INITIALIZER(Slots, Func) { Slots, 0, 0, Func }
93
94
95
96 /*****************************************************************************/
97 /* struct HashNode */
98 /*****************************************************************************/
99
100
101
102 #if defined(HAVE_INLINE)
InitHashNode(HashNode * N)103 INLINE void InitHashNode (HashNode* N)
104 /* Initialize a hash node. */
105 {
106 N->Next = 0;
107 }
108 #else
109 #define InitHashNode(N) do { (N)->Next = 0; } while (0)
110 #endif
111
112
113
114 /*****************************************************************************/
115 /* struct HashTable */
116 /*****************************************************************************/
117
118
119
120 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func);
121 /* Initialize a hash table and return it */
122
123 void DoneHashTable (HashTable* T);
124 /* Destroy the contents of a hash table. Note: This will not free the entries
125 ** in the table!
126 */
127
128 #if defined(HAVE_INLINE)
NewHashTable(unsigned Slots,const HashFunctions * Func)129 INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
130 /* Create a new hash table and return it. */
131 {
132 /* Allocate memory, initialize and return it */
133 return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func);
134 }
135 #else
136 #define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func)
137 #endif
138
139 void FreeHashTable (HashTable* T);
140 /* Free a hash table. Note: This will not free the entries in the table! */
141
142 #if defined(HAVE_INLINE)
HT_GetCount(const HashTable * T)143 INLINE unsigned HT_GetCount (const HashTable* T)
144 /* Return the number of items in the table. */
145 {
146 return T->Count;
147 }
148 #else
149 #define HT_GetCount(T) ((T)->Count)
150 #endif
151
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.
155 */
156
157 void* HT_Find (const HashTable* T, const void* Key);
158 /* Find the entry with the given key and return it */
159
160 void HT_Insert (HashTable* T, void* Entry);
161 /* Insert an entry into the given hash table */
162
163 void HT_Remove (HashTable* T, void* Entry);
164 /* Remove an entry from the given hash table */
165
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.
173 */
174
175
176
177 /* End of hashtab.h */
178
179 #endif
180