3 * $Id: sym.c,v 1.2 2000/07/02 15:21:20 mdw Exp $
5 * Symbol table management
8 * (c) 2000 Mark Wooding
11 /*----- Licensing notice --------------------------------------------------*
13 * Copyright (c) 2000 Mark Wooding
14 * All rights reserved.
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions are
20 * 1. Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
23 * 2, Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
27 * 3. The name of the authors may not be used to endorse or promote
28 * products derived from this software without specific prior written
31 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
32 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
33 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
34 * NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
35 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
36 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
37 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
40 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
41 * POSSIBILITY OF SUCH DAMAGE.
43 * Instead of accepting the above terms, you may redistribute and/or modify
44 * this software under the terms of either the GNU General Public License,
45 * or the GNU Library General Public License, published by the Free
46 * Software Foundation; either version 2 of the License, or (at your
47 * option) any later version.
50 /*----- Revision history --------------------------------------------------*
53 * Revision 1.2 2000/07/02 15:21:20 mdw
56 * Revision 1.1 2000/05/21 11:28:30 mdw
59 * --- Past lives (Become) --- *
61 * Revision 1.4 1998/01/12 16:46:28 mdw
64 * Revision 1.3 1997/08/20 16:22:59 mdw
67 * Revision 1.2 1997/08/04 10:24:25 mdw
68 * Sources placed under CVS control.
70 * Revision 1.1 1997/07/21 13:47:44 mdw
75 /*----- Header files ------------------------------------------------------*/
84 /*----- Tuning parameters -------------------------------------------------*/
86 /* --- Initial hash table size --- *
88 * This is the initial @mask@ value. It must be of the form %$2^n - 1$%,
89 * so that it can be used to mask of the bottom bits of a hash value.
92 #define SYM_INITSZ 256 /* Size of a new hash table */
94 /* --- Maximum load factor --- *
96 * This parameter controls how much the table has to be loaded before the
97 * table is extended. The number of elements %$n$%, the number of bins %$b$%
98 * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
99 * added to the table and this relation is found to be false, the table is
103 #define SYM_LIMIT(n) ((n) * 2) /* Load factor for growing table */
105 /*----- CRC table ---------------------------------------------------------*/
107 /*****************************************************************/
109 /* CRC LOOKUP TABLE */
110 /* ================ */
112 /* The following CRC lookup table was generated automagically */
113 /* by `crcgen', which is based on the Rocksoft^tm Model CRC */
114 /* Algorithm Table Generation Program. The model parameters */
115 /* supplied to `crcgen' were: */
117 /* Width : 32 bits */
118 /* Poly : 0x04C11DB7 */
119 /* Init : 0xFFFFFFFF */
120 /* XorOut : 0xFFFFFFFF */
122 /* Check : 0xCBF43926 */
124 /* For more information on the Rocksoft^tm Model CRC Algorithm, */
125 /* see the document titled `A Painless Guide to CRC Error */
126 /* Detection Algorithms' by Ross Williams */
127 /* (ross@@guest.adelaide.edu.au.). This document is likely to be */
128 /* in the FTP archive `ftp.adelaide.edu.au/pub/rocksoft'. */
130 /*****************************************************************/
132 static uint32 crctab
[256] = {
133 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
134 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
135 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
136 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
137 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
138 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
139 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
140 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
141 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
142 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
143 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
144 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
145 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
146 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
147 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
148 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
149 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
150 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
151 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
152 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
153 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
154 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
155 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
156 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
157 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
158 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
159 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
160 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
161 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
162 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
163 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
164 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
165 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
166 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
167 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
168 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
169 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
170 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
171 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
172 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
173 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
174 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
175 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
176 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
177 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
178 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
179 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
180 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
181 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
182 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
183 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
184 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
185 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
186 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
187 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
188 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
189 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
190 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
191 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
192 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
193 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
194 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
195 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
196 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
199 /*****************************************************************/
200 /* End of CRC Lookup Table */
201 /*****************************************************************/
203 /* --- Work out the CRC of a bytestring --- */
205 #define CRC(_s, _l, _hv) do { \
206 uint32 _h = 0xffffffff; \
207 const char *_p = _s; \
208 const char *_e = (_s) + (_l); \
211 _h = (_h >> 8) ^ (crctab[(*_p++ ^ _h) & 0xFF]); \
212 _hv = ~_h & 0xffffffff; \
215 /*----- Memory allocation -------------------------------------------------*/
217 static void die(const char *p
)
219 fprintf(stderr
, "%s\n", p
);
223 static void *xmalloc(size_t sz
)
225 void *p
= malloc(sz
);
227 die("not enough memory");
231 static void *xrealloc(void *p
, size_t sz
)
235 die("not enough memory");
240 /*----- Main code ---------------------------------------------------------*/
242 /* --- @sym_create@ --- *
244 * Arguments: @sym_table *t@ = symbol table to initialize
248 * Use: Initialises the given symbol table.
251 void sym_create(sym_table
*t
)
255 t
->mask
= SYM_INITSZ
- 1;
256 t
->c
= SYM_LIMIT(SYM_INITSZ
);
257 t
->a
= xmalloc((t
->mask
+ 1) * sizeof(sym_base
*));
259 for (i
= 0; i
< SYM_INITSZ
+ 1; i
++)
263 /* --- @sym_destroy@ --- *
265 * Arguments: @sym_table *t@ = pointer to symbol table in question
269 * Use: Destroys a symbol table, freeing all the memory it used to
273 void sym_destroy(sym_table
*t
)
278 for (i
= 0; i
<= t
->mask
; i
++) {
290 /* --- @sym_find@ --- *
292 * Arguments: @sym_table *t@ = pointer to symbol table in question
293 * @const char *n@ = pointer to symbol table to look up
294 * @long l@ = length of the name string or negative to measure
295 * @size_t sz@ = size of desired symbol object, or zero
296 * @unsigned *f@ = pointer to a flag, or null.
298 * Returns: The address of a @sym_base@ structure, or null if not found
301 * Use: Looks up a symbol in a given symbol table. The name is
302 * passed by the address of its first character. The length
303 * may be given, in which case the name may contain arbitrary
304 * binary data, or it may be given as a negative number, in
305 * which case the length of the name is calculated as
308 * The return value is the address of a pointer to a @sym_base@
309 * block (which may have other things on the end, as above). If
310 * the symbol could be found, the return value points to the
311 * symbol block. If the symbol wasn't there, then if @sz@ is
312 * nonzero, a new symbol is created and its address is returned;
313 * otherwise a null pointer is returned.
315 * The value of @*f@ indicates whether a new symbol entry was
316 * created: a nonzero value indicates that an old value was
320 void *sym_find(sym_table
*t
, const char *n
, long l
, size_t sz
, unsigned *f
)
323 size_t len
= l
< 0 ?
strlen(n
) + 1 : l
;
327 /* --- Find the correct bin --- */
330 bin
= p
= (sym_base
*)(t
->a
+ (hash
& t
->mask
));
332 /* --- Search the bin list --- */
335 if (hash
== p
->next
->hash
&& len
== p
->next
->len
&&
336 !memcmp(n
, p
->next
->name
, len
)) {
338 /* --- Found a match --- *
340 * As a minor, and probably pointless, tweak, move the item to the
341 * front of its bin list.
349 /* --- Return the block --- */
358 /* --- Couldn't find the item there --- */
363 /* --- Create a new symbol block and initialize it --- */
368 p
->name
= xmalloc(len
);
370 memcpy(p
->name
, n
, len
);
374 /* --- Consider growing the array --- */
377 uint32 m
= t
->mask
+ 1;
381 /* --- Update values in the anchor block --- */
383 t
->c
= SYM_LIMIT(t
->mask
+ 1);
384 t
->mask
= (t
->mask
+ 1) * 2 - 1;
385 t
->a
= xrealloc(t
->a
, (t
->mask
+ 1) * sizeof(sym_base
*));
387 /* --- Now wander through the table rehashing things --- *
389 * This loop is very careful to avoid problems with aliasing. The items
390 * are dealt with from the end backwards to avoid overwriting bins before
391 * they've been processed.
394 lim
= (t
->mask
+ 1) >> 1;
395 for (i
= 0; i
< lim
; i
++) {
397 /* --- Some initialization --- */
400 p
= (sym_base
*)(t
->a
+ i
);
401 q
= (sym_base
*)(t
->a
+ i
+ lim
);
403 /* --- Now go through the @r@ list --- */
412 p
->next
= q
->next
= 0;
416 /* --- Finished that, so return the new symbol block --- */
421 /* --- @sym_remove@ --- *
423 * Arguments: @sym_table *i@ = pointer to a symbol table object
424 * @void *b@ = pointer to symbol table entry
428 * Use: Removes the object from the symbol table. The space occupied
429 * by the object and its name is freed; anything else attached
430 * to the entry should already be gone by this point.
433 void sym_remove(sym_table
*t
, void *b
)
435 /* --- A quick comment --- *
437 * Since the @sym_base@ block contains the hash, finding the element in the
438 * bin list is really quick -- it's not worth bothering with things like
439 * doubly linked lists.
443 sym_base
*bin
= (sym_base
*)(t
->a
+ (p
->hash
& t
->mask
));
445 /* --- Find the item in the bin list --- */
455 /* --- Now just remove the item from the list and free it --- *
457 * Oh, and bump the load counter.
466 /* --- @sym_mkiter@ --- *
468 * Arguments: @sym_iter *i@ = pointer to an iterator object
469 * @sym_table *t@ = pointer to a symbol table object
473 * Use: Creates a new symbol table iterator which may be used to
474 * iterate through a symbol table.
477 void sym_mkiter(sym_iter
*i
, sym_table
*t
)
484 /* --- @sym_next@ --- *
486 * Arguments: @sym_iter *i@ = pointer to iterator object
488 * Returns: Pointer to the next symbol found, or null when finished.
490 * Use: Returns the next symbol from the table. Symbols are not
491 * returned in any particular order.
494 void *sym_next(sym_iter
*i
)
498 /* --- Find the next item --- */
501 if (i
->i
> i
->t
->mask
)
503 i
->n
= i
->t
->a
[i
->i
++];
506 /* --- Update the iterator block --- */
516 /*----- That's all, folks -------------------------------------------------*/