chiark / gitweb /
Include @<ctype.h>@.
[mLib] / sym.c
CommitLineData
0875b58f 1/* -*-c-*-
2 *
ec6770dd 3 * $Id: sym.c,v 1.13 2001/01/25 21:14:49 mdw Exp $
0875b58f 4 *
5 * Symbol table management
6 *
7 * (c) 1998 Straylight/Edgeware
8 */
9
c846879c 10/*----- Licensing notice --------------------------------------------------*
0875b58f 11 *
12 * This file is part of the mLib utilities library.
13 *
14 * mLib is free software; you can redistribute it and/or modify
c846879c 15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
0875b58f 19 * mLib is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
c846879c 22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
0bd98442 25 * License along with mLib; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
0875b58f 28 */
29
30/*----- Revision history --------------------------------------------------*
31 *
32 * $Log: sym.c,v $
ec6770dd 33 * Revision 1.13 2001/01/25 21:14:49 mdw
34 * Always add a terminating null, and don't count it in the length.
35 *
2ae5376b 36 * Revision 1.12 2001/01/20 11:49:37 mdw
37 * Export tuning parameters from header file, for the benefit of other
38 * hashtable implementations. Change the storage of symbol names: store
39 * the name after the allocated symbol block in all cases. This replaces
40 * the previous complicated and slightly wasteful arrangement.
41 *
20eb516f 42 * Revision 1.11 2000/06/17 10:37:39 mdw
43 * Add support for arena management.
44 *
c6e0eaf0 45 * Revision 1.10 1999/12/10 23:42:04 mdw
46 * Change header file guard names.
47 *
cd300147 48 * Revision 1.9 1999/10/22 22:36:37 mdw
49 * New test structure for symbol tables.
50 *
03d53b73 51 * Revision 1.8 1999/08/02 14:45:48 mdw
52 * Break low-level hashtable code out from sym.
53 *
d4d7a053 54 * Revision 1.7 1999/06/01 09:49:08 mdw
55 * Allow things to be looked up by just their caller-supplied hashes. This
56 * actually needs to be thought through better.
57 *
34b97201 58 * Revision 1.6 1999/05/26 21:08:31 mdw
59 * Rename symbols in line with newer conventions.
60 *
a7a37c4a 61 * Revision 1.5 1999/05/13 22:48:37 mdw
62 * Twiddle the extension threshold. Change `-ise' to `-ize' throughout.
63 *
0bd98442 64 * Revision 1.4 1999/05/06 19:51:35 mdw
65 * Reformatted the LGPL notice a little bit.
66 *
c846879c 67 * Revision 1.3 1999/05/05 18:50:31 mdw
68 * Change licensing conditions to LGPL.
69 *
a5d14ede 70 * Revision 1.2 1998/11/26 19:27:33 mdw
71 * Move SYM_NAME into the header file. Fix bugs.
72 *
73 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
74 * Initial version of mLib
0875b58f 75 *
76 */
77
78/*----- Header files ------------------------------------------------------*/
79
80/* --- ANSI headers --- */
81
82#include <stdio.h>
83#include <stdlib.h>
84#include <string.h>
85
86/* --- Local headers --- */
87
88#include "alloc.h"
20eb516f 89#include "arena.h"
d4d7a053 90#include "bits.h"
0875b58f 91#include "crc32.h"
92#include "exc.h"
03d53b73 93#include "hash.h"
0875b58f 94#include "sub.h"
95#include "sym.h"
0875b58f 96
0875b58f 97/*----- Main code ---------------------------------------------------------*/
98
34b97201 99/* --- @sym_create@ --- *
0875b58f 100 *
a7a37c4a 101 * Arguments: @sym_table *t@ = symbol table to initialize
0875b58f 102 *
103 * Returns: ---
104 *
a7a37c4a 105 * Use: Initializes the given symbol table. Raises @EXC_NOMEM@ if
0875b58f 106 * there isn't enough memory.
107 */
108
34b97201 109void sym_create(sym_table *t)
0875b58f 110{
03d53b73 111 hash_create(&t->t, SYM_INITSZ);
20eb516f 112 t->s = &sub_global;
03d53b73 113 t->load = SYM_LIMIT(SYM_INITSZ);
0875b58f 114}
115
34b97201 116/* --- @sym_destroy@ --- *
0875b58f 117 *
118 * Arguments: @sym_table *t@ = pointer to symbol table in question
119 *
120 * Returns: ---
121 *
122 * Use: Destroys a symbol table, freeing all the memory it used to
123 * occupy.
124 */
125
34b97201 126void sym_destroy(sym_table *t)
0875b58f 127{
03d53b73 128 sym_iter i;
0875b58f 129
03d53b73 130 SYM_MKITER(&i, t);
131 for (;;) {
132 sym_base *p;
133 SYM_NEXT(&i, p);
134 if (!p)
135 break;
20eb516f 136 x_free(t->t.a, p);
0875b58f 137 }
03d53b73 138 hash_destroy(&t->t);
0875b58f 139}
140
141/* --- @sym_find@ --- *
142 *
143 * Arguments: @sym_table *t@ = pointer to symbol table in question
144 * @const char *n@ = pointer to symbol table to look up
145 * @long l@ = length of the name string or negative to measure
146 * @size_t sz@ = size of desired symbol object, or zero
147 * @unsigned *f@ = pointer to a flag, or null.
148 *
149 * Returns: The address of a @sym_base@ structure, or null if not found
150 * and @sz@ is zero.
151 *
152 * Use: Looks up a symbol in a given symbol table. The name is
153 * passed by the address of its first character. The length
154 * may be given, in which case the name may contain arbitrary
155 * binary data, or it may be given as a negative number, in
156 * which case the length of the name is calculated as
03d53b73 157 * @strlen(n) + 1@.
0875b58f 158 *
159 * The return value is the address of a pointer to a @sym_base@
160 * block (which may have other things on the end, as above). If
161 * the symbol could be found, the return value points to the
162 * symbol block. If the symbol wasn't there, then if @sz@ is
163 * nonzero, a new symbol is created and its address is returned;
164 * otherwise a null pointer is returned. The exception
165 * @EXC_NOMEM@ is raised if the block can't be allocated.
166 *
167 * The value of @*f@ indicates whether a new symbol entry was
168 * created: a nonzero value indicates that an old value was
169 * found.
170 */
171
172void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
173{
d4d7a053 174 uint32 hash;
175 size_t len = 0;
03d53b73 176 hash_base **bin, **p;
177 sym_base *q;
0875b58f 178
179 /* --- Find the correct bin --- */
180
ec6770dd 181 len = l < 0 ? strlen(n) : l;
03d53b73 182 CRC32(hash, 0, n, len);
183 bin = HASH_BIN(&t->t, hash);
0875b58f 184
185 /* --- Search the bin list --- */
186
03d53b73 187 for (p = bin; *p; p = &(*p)->next) {
188 q = (sym_base *)*p;
189 if (hash == q->b.hash && len == q->len && !memcmp(n, SYM_NAME(q), len)) {
190
0875b58f 191 /* --- Found a match --- *
192 *
193 * As a minor, and probably pointless, tweak, move the item to the
194 * front of its bin list.
195 */
196
03d53b73 197 (*p) = q->b.next;
198 q->b.next = *bin;
199 *bin = &q->b;
0875b58f 200
201 /* --- Return the block --- */
202
d4d7a053 203 if (f) *f = 1;
204 return (q);
0875b58f 205 }
0875b58f 206 }
207
208 /* --- Couldn't find the item there --- */
209
d4d7a053 210 if (f) *f = 0;
211 if (!sz) return (0);
0875b58f 212
2ae5376b 213 /* --- Create a new symbol block and initialize it --- *
214 *
215 * The name is attached to the end of the symbol block.
216 */
0875b58f 217
ec6770dd 218 q = x_alloc(t->t.a, sz + len + 1);
20eb516f 219 q->b.next = *bin;
220 q->b.hash = hash;
2ae5376b 221 q->name = (char *)q + sz;
222 memcpy(q->name, n, len);
ec6770dd 223 q->name[len] = 0;
20eb516f 224 q->len = len;
03d53b73 225 *bin = &q->b;
0875b58f 226
227 /* --- Consider growing the array --- */
228
03d53b73 229 if (t->load)
230 t->load--;
231 if (!t->load && hash_extend(&t->t))
2ae5376b 232 t->load = SYM_LIMIT(t->t.mask + 1);
0875b58f 233
234 /* --- Finished that, so return the new symbol block --- */
235
03d53b73 236 return (q);
0875b58f 237}
238
239/* --- @sym_remove@ --- *
240 *
c6e0eaf0 241 * Arguments: @sym_table *t@ = pointer to a symbol table object
03d53b73 242 * @void *p@ = pointer to symbol table entry
0875b58f 243 *
244 * Returns: ---
245 *
246 * Use: Removes the object from the symbol table. The space occupied
247 * by the object and its name is freed; anything else attached
248 * to the entry should already be gone by this point.
249 */
250
03d53b73 251void sym_remove(sym_table *t, void *p)
0875b58f 252{
03d53b73 253 sym_base *q = p;
254 hash_remove(&t->t, &q->b);
20eb516f 255 xfree(q);
03d53b73 256 t->load++;
0875b58f 257}
258
34b97201 259/* --- @sym_mkiter@ --- *
0875b58f 260 *
261 * Arguments: @sym_iter *i@ = pointer to an iterator object
262 * @sym_table *t@ = pointer to a symbol table object
263 *
264 * Returns: ---
265 *
266 * Use: Creates a new symbol table iterator which may be used to
267 * iterate through a symbol table.
268 */
269
03d53b73 270void sym_mkiter(sym_iter *i, sym_table *t) { SYM_MKITER(i, t); }
0875b58f 271
272/* --- @sym_next@ --- *
273 *
274 * Arguments: @sym_iter *i@ = pointer to iterator object
275 *
276 * Returns: Pointer to the next symbol found, or null when finished.
277 *
278 * Use: Returns the next symbol from the table. Symbols are not
279 * returned in any particular order.
280 */
281
282void *sym_next(sym_iter *i)
283{
03d53b73 284 void *p;
285 SYM_NEXT(i, p);
0875b58f 286 return (p);
287}
288
0875b58f 289/*----- That's all, folks -------------------------------------------------*/