]> git.sur5r.net Git - cc65/blob - src/common/hashtab.h
un-remove TABs in doc/using-make.sgml
[cc65] / src / common / hashtab.h
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