chiark / gitweb /
b0aea23e4629689730106a2eb38e0773789b2787
[mLib] / hash.h
1 /* -*-c-*-
2  *
3  * General hashtable infrastructure
4  *
5  * (c) 1999 Straylight/Edgeware
6  */
7
8 /*----- Licensing notice --------------------------------------------------*
9  *
10  * This file is part of the mLib utilities library.
11  *
12  * mLib is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU Library General Public License as
14  * published by the Free Software Foundation; either version 2 of the
15  * License, or (at your option) any later version.
16  *
17  * mLib is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU Library General Public License for more details.
21  *
22  * You should have received a copy of the GNU Library General Public
23  * License along with mLib; if not, write to the Free
24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25  * MA 02111-1307, USA.
26  */
27
28 #ifndef MLIB_HASH_H
29 #define MLIB_HASH_H
30
31 #ifdef __cplusplus
32   extern "C" {
33 #endif
34
35 /*----- Notes -------------------------------------------------------------*
36  *
37  * This isn't a complete implementation of anything.  It's a collection of
38  * useful types and functions which will help when building hashtables of
39  * things.  The general-purpose hashtable is provided by the @sym@ functions.
40  */
41
42 /*----- Header files ------------------------------------------------------*/
43
44 #include <stddef.h>
45
46 #ifndef MLIB_ARENA_H
47 #  include "arena.h"
48 #endif
49
50 #ifndef MLIB_BITS_H
51 #  include "bits.h"
52 #endif
53
54 /*----- Data structures ---------------------------------------------------*/
55
56 /* --- Hashtable basics --- *
57  *
58  * This contains the bare minimum to actually get anything useful done.  In
59  * particular it doesn't maintain any weighting information: when to extend
60  * the table is left up to the particular implementation.
61  */
62
63 typedef struct hash_table {
64   uint32 mask;                          /* Bit mask of hash bits */
65   struct hash_base **v;                 /* Vector of hash bins */
66   arena *a;                             /* Allocation arena */
67 } hash_table;
68
69 /* --- A hashtable entry --- *
70  *
71  * This is the bare minimum of what needs to be remembered in each hashtable
72  * entry.  Comparison of elements is left to the implementation, so I don't
73  * need to know anything about how to represent hash keys here.
74  */
75
76 typedef struct hash_base {
77   struct hash_base *next;               /* Next entry in hash bin */
78   uint32 hash;                          /* Hash value for this entry */
79 } hash_base;
80
81 /* --- A hashtable iterator --- */
82
83 typedef struct hash_iter {
84   hash_table *t;                        /* Hashtable being iterated */
85   hash_base *p;                         /* Address of next item to return */
86   size_t i;                             /* Index of next hash bin to use */
87 } hash_iter;
88
89 /*----- Functions provided ------------------------------------------------*/
90
91 /* --- @hash_create@ --- *
92  *
93  * Arguments:   @hash_table *t@ = pointer to hashtable to initialize
94  *              @size_t n@ = number of bins to allocate (zero initially)
95  *
96  * Returns:     ---
97  *
98  * Use:         Initializes a hashtable with a given number of bins.  The
99  *              bins are initially empty.  The number of bins must be a power
100  *              of two.  This is not checked.
101  */
102
103 extern void hash_create(hash_table */*t*/, size_t /*n*/);
104
105 /* --- @hash_destroy@ --- *
106  *
107  * Arguments:   @hash_table *t@ = pointer to hashtable to destroy
108  *
109  * Returns:     ---
110  *
111  * Use:         Frees a hashtable.  The items are not freed: they are the
112  *              responsibility of the implementation.
113  */
114
115 extern void hash_destroy(hash_table */*t*/);
116
117 /* --- @hash_bin@ --- *
118  *
119  * Arguments:   @hash_table *t@ = pointer to hashtable
120  *              @uint32 hash@ = hash value to look up
121  *
122  * Returns:     Pointer to the bin's list head.
123  *
124  * Use:         Given a hash value return the address of the appropriate list
125  *              head.  It is safe to remove the current entry from the table.
126  */
127
128 #define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask))
129
130 extern hash_base **hash_bin(hash_table */*t*/, uint32 /*hash*/);
131
132 /* --- @hash_extend@ --- *
133  *
134  * Arguments:   @hash_table *t@ = pointer to hashtable to extend
135  *
136  * Returns:     Nonzero if extension was successful.
137  *
138  * Use:         Extends a hashtable.  The number of bins is doubled and the
139  *              entries are redistributed.
140  */
141
142 extern int hash_extend(hash_table */*t*/);
143
144 /* --- @hash_remove@ --- *
145  *
146  * Arguments:   @hash_table *t@ = pointer to hashtable
147  *              @hash_base *p@ = pointer to item to remove
148  *
149  * Returns:     ---
150  *
151  * Use:         Removes an item from a hashtable.  The item itself is not
152  *              freed, although it is removed from the data structure and is
153  *              safe to free.
154  */
155
156 extern void hash_remove(hash_table */*t*/, hash_base */*p*/);
157
158 /* --- @hash_mkiter@ --- *
159  *
160  * Arguments:   @hash_iter *i@ = pointer to iterator to create
161  *              @hash_table *t@ = pointer to hashtable to iterate
162  *
163  * Returns:     ---
164  *
165  * Use:         Initializes a hashtable iterator.
166  */
167
168 #define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0)
169
170 extern void hash_mkiter(hash_iter */*i*/, hash_table */*t*/);
171
172 /* --- @hash_next@ --- *
173  *
174  * Arguments:   @hash_iter *i@ = pointer to iterator
175  *
176  * Returns:     Pointer to the next hashtable entry found, or null.
177  *
178  * Use:         Returns the next entry from the hashtable.
179  */
180
181 #define HASH_NEXT(i_, b_) do {                                          \
182   hash_iter *_i = (i_);                                                 \
183   hash_base *_p;                                                        \
184   hash_table *_t = _i->t;                                               \
185   uint32 _m = _t->mask;                                                 \
186                                                                         \
187   for (;;) {                                                            \
188     if (_i->p) {                                                        \
189       _p = _i->p;                                                       \
190       _i->p = _p->next;                                                 \
191       break;                                                            \
192     } else if (_i->i > _m) {                                            \
193       _p = 0;                                                           \
194       break;                                                            \
195     } else                                                              \
196       _i->p = _t->v[_i->i++];                                           \
197   }                                                                     \
198   (b_) = _p;                                                            \
199 } while (0)
200
201 extern hash_base *hash_next(hash_iter */*i*/);
202
203 /*----- That's all, folks -------------------------------------------------*/
204
205 #ifdef __cplusplus
206   }
207 #endif
208
209 #endif