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) |
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) |
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) |
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 | |