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*/
58typedef struct HashNode HashNode;
59struct 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 */
67typedef struct HashFunctions HashFunctions;
68struct 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 */
84typedef struct HashTable HashTable;
85struct 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)
103INLINE 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
120HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func);
121/* Initialize a hash table and return it */
122
123void 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)
129INLINE 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
139void FreeHashTable (HashTable* T);
140/* Free a hash table. Note: This will not free the entries in the table! */
141
142#if defined(HAVE_INLINE)
143INLINE 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
152HashNode* 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
157void* HT_Find (const HashTable* T, const void* Key);
158/* Find the entry with the given key and return it */
159
160void HT_Insert (HashTable* T, void* Entry);
161/* Insert an entry into the given hash table */
162
163void HT_Remove (HashTable* T, void* Entry);
164/* Remove an entry from the given hash table */
165
166void 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