chiark / gitweb /
4543811676af87d303f88dbe0f3fd0e0a1fedf6c
[mLib] / sym.c
1 /* -*-c-*-
2  *
3  * Symbol table management
4  *
5  * (c) 1998 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 /*----- Header files ------------------------------------------------------*/
29
30 /* --- ANSI headers --- */
31
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35
36 /* --- Local headers --- */
37
38 #include "alloc.h"
39 #include "arena.h"
40 #include "bits.h"
41 #include "exc.h"
42 #include "hash.h"
43 #include "sub.h"
44 #include "sym.h"
45 #include "unihash.h"
46
47 /*----- Main code ---------------------------------------------------------*/
48
49 /* --- @sym_create@ --- *
50  *
51  * Arguments:   @sym_table *t@ = symbol table to initialize
52  *
53  * Returns:     ---
54  *
55  * Use:         Initializes the given symbol table.  Raises @EXC_NOMEM@ if
56  *              there isn't enough memory.
57  */
58
59 void sym_create(sym_table *t)
60 {
61   hash_create(&t->t, SYM_INITSZ);
62   t->s = &sub_global;
63   t->load = SYM_LIMIT(SYM_INITSZ);
64 }
65
66 /* --- @sym_destroy@ --- *
67  *
68  * Arguments:   @sym_table *t@ = pointer to symbol table in question
69  *
70  * Returns:     ---
71  *
72  * Use:         Destroys a symbol table, freeing all the memory it used to
73  *              occupy.
74  */
75
76 void sym_destroy(sym_table *t)
77 {
78   sym_iter i;
79
80   SYM_MKITER(&i, t);
81   for (;;) {
82     sym_base *p;
83     SYM_NEXT(&i, p);
84     if (!p)
85       break;
86     x_free(t->t.a, p);
87   }
88   hash_destroy(&t->t);
89 }
90
91 /* --- @sym_find@ --- *
92  *
93  * Arguments:   @sym_table *t@ = pointer to symbol table in question
94  *              @const char *n@ = pointer to symbol name to look up
95  *              @long l@ = length of the name string or negative to measure
96  *              @size_t sz@ = size of desired symbol object, or zero
97  *              @unsigned *f@ = pointer to a flag, or null.
98  *
99  * Returns:     The address of a @sym_base@ structure, or null if not found
100  *              and @sz@ is zero.
101  *
102  * Use:         Looks up a symbol in a given symbol table.  The name is
103  *              passed by the address of its first character.  The length
104  *              may be given, in which case the name may contain arbitrary
105  *              binary data, or it may be given as a negative number, in
106  *              which case the length of the name is calculated as
107  *              @strlen(n) + 1@.
108  *
109  *              The return value is the address of a pointer to a @sym_base@
110  *              block (which may have other things on the end, as above).  If
111  *              the symbol could be found, the return value points to the
112  *              symbol block.  If the symbol wasn't there, then if @sz@ is
113  *              nonzero, a new symbol is created and its address is returned;
114  *              otherwise a null pointer is returned.  The exception
115  *              @EXC_NOMEM@ is raised if the block can't be allocated.
116  *
117  *              The value of @*f@ indicates whether a new symbol entry was
118  *              created: a nonzero value indicates that an old value was
119  *              found.
120  */
121
122 void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
123 {
124   uint32 hash;
125   size_t len = 0;
126   hash_base **bin, **p;
127   sym_base *q;
128
129   /* --- Find the correct bin --- */
130
131   len = l < 0 ? strlen(n) : l;
132   hash = UNIHASH(&unihash_global, n, len);
133   bin = HASH_BIN(&t->t, hash);
134
135   /* --- Search the bin list --- */
136
137   for (p = bin; *p; p = &(*p)->next) {
138     q = (sym_base *)*p;
139     if (hash == q->b.hash && len == q->len && !memcmp(n, SYM_NAME(q), len)) {
140
141       /* --- Found a match --- *
142        *
143        * As a minor, and probably pointless, tweak, move the item to the
144        * front of its bin list.
145        */
146
147       (*p) = q->b.next;
148       q->b.next = *bin;
149       *bin = &q->b;
150
151       /* --- Return the block --- */
152
153       if (f) *f = 1;
154       return (q);
155     }
156   }
157
158   /* --- Couldn't find the item there --- */
159
160   if (f) *f = 0;
161   if (!sz) return (0);
162
163   /* --- Create a new symbol block and initialize it --- *
164    *
165    * The name is attached to the end of the symbol block.
166    */
167
168   q = x_alloc(t->t.a, sz + len + 1);
169   q->b.next = *bin;
170   q->b.hash = hash;
171   q->name = (char *)q + sz;
172   memcpy(q->name, n, len);
173   q->name[len] = 0;
174   q->len = len;
175   *bin = &q->b;
176
177   /* --- Consider growing the array --- */
178
179   if (t->load)
180     t->load--;
181   if (!t->load && hash_extend(&t->t))
182     t->load = SYM_LIMIT(t->t.mask + 1);
183
184   /* --- Finished that, so return the new symbol block --- */
185
186   return (q);
187 }
188
189 /* --- @sym_remove@ --- *
190  *
191  * Arguments:   @sym_table *t@ = pointer to a symbol table object
192  *              @void *p@ = pointer to symbol table entry
193  *
194  * Returns:     ---
195  *
196  * Use:         Removes the object from the symbol table.  The space occupied
197  *              by the object and its name is freed; anything else attached
198  *              to the entry should already be gone by this point.
199  */
200
201 void sym_remove(sym_table *t, void *p)
202 {
203   sym_base *q = p;
204   hash_remove(&t->t, &q->b);
205   xfree(q);
206   t->load++;
207 }
208
209 /* --- @sym_mkiter@ --- *
210  *
211  * Arguments:   @sym_iter *i@ = pointer to an iterator object
212  *              @sym_table *t@ = pointer to a symbol table object
213  *
214  * Returns:     ---
215  *
216  * Use:         Creates a new symbol table iterator which may be used to
217  *              iterate through a symbol table.
218  */
219
220 void sym_mkiter(sym_iter *i, sym_table *t) { SYM_MKITER(i, t); }
221
222 /* --- @sym_next@ --- *
223  *
224  * Arguments:   @sym_iter *i@ = pointer to iterator object
225  *
226  * Returns:     Pointer to the next symbol found, or null when finished.
227  *
228  * Use:         Returns the next symbol from the table.  Symbols are not
229  *              returned in any particular order.
230  */
231
232 void *sym_next(sym_iter *i)
233 {
234   void *p;
235   SYM_NEXT(i, p);
236   return (p);
237 }
238
239 /*----- That's all, folks -------------------------------------------------*/