~mdw / become / blob
? search:


a698382befc64c3a055a46f03cfeee73eec764fb
[become] / src / sym.c
1 /* -*-c-*-
2 *
3 * $Id: sym.c,v 1.2 1997/08/04 10:24:25 mdw Exp $
4 *
5 * Symbol table management
6 *
7 * (c) 1996 Straylight
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of `become'
13 *
14 * `Become' is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
18 *
19 * `Become' 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
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with `become'; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 */
28
29 /*----- Revision history --------------------------------------------------*
30 *
31 * $Log: sym.c,v $
32 * Revision 1.2 1997/08/04 10:24:25 mdw
33 * Sources placed under CVS control.
34 *
35 * Revision 1.1 1997/07/21 13:47:44 mdw
36 * Initial revision
37 *
38 */
39
40 /*----- Header files ------------------------------------------------------*/
41
42 /* --- ANSI headers --- */
43
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47
48 /* --- Local headers --- */
49
50 #include "sym.h"
51 #include "utils.h"
52
53 /*----- Tuning parameters -------------------------------------------------*/
54
55 /* --- Initial hash table size --- *
56 *
57 * This is the initial @mask@ value. It must be of the form %$2^n - 1$%,
58 * so that it can be used to mask of the bottom bits of a hash value.
59 */
60
61 #define sym__iSize 255 /* Size of a new hash table */
62
63 /* --- Maximum load factor --- *
64 *
65 * This parameter controls how much the table has to be loaded before the
66 * table is extended. The number of elements %$n$%, the number of bins %$b$%
67 * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
68 * added to the table and this relation is found to be false, the table is
69 * doubled in size.
70 *
71 * The parameter @sym__limFactor@ is the value of %$l$% multiplied by 256;
72 * fixed point arithmetic is used to calculate the allowable load. Note
73 * that the exact calculation of this criterion isn't important; what's more
74 * significant is that the parameter allows tuning of the rehashing process.
75 *
76 * The current value is %$3 \over 4$%, which appears to be reasonable on the
77 * face of things.
78 */
79
80 #define sym__limFactor 0x0C0 /* Load factor for growing table */
81
82 /*----- CRC table ---------------------------------------------------------*/
83
84 /*****************************************************************/
85 /* */
86 /* CRC LOOKUP TABLE */
87 /* ================ */
88 /* */
89 /* The following CRC lookup table was generated automagically */
90 /* by `crcgen', which is based on the Rocksoft^tm Model CRC */
91 /* Algorithm Table Generation Program. The model parameters */
92 /* supplied to `crcgen' were: */
93 /* */
94 /* Width : 32 bits */
95 /* Poly : 0x04C11DB7 */
96 /* Init : 0xFFFFFFFF */
97 /* XorOut : 0xFFFFFFFF */
98 /* Reverse : Yes */
99 /* Check : 0xCBF43926 */
100 /* */
101 /* For more information on the Rocksoft^tm Model CRC Algorithm, */
102 /* see the document titled `A Painless Guide to CRC Error */
103 /* Detection Algorithms' by Ross Williams */
104 /* (ross@@guest.adelaide.edu.au.). This document is likely to be */
105 /* in the FTP archive `ftp.adelaide.edu.au/pub/rocksoft'. */
106 /* */
107 /*****************************************************************/
108
109 static unsigned long sym__crcTable[256] = {
110 0x00000000L, 0x77073096L, 0xEE0E612CL, 0x990951BAL,
111 0x076DC419L, 0x706AF48FL, 0xE963A535L, 0x9E6495A3L,
112 0x0EDB8832L, 0x79DCB8A4L, 0xE0D5E91EL, 0x97D2D988L,
113 0x09B64C2BL, 0x7EB17CBDL, 0xE7B82D07L, 0x90BF1D91L,
114 0x1DB71064L, 0x6AB020F2L, 0xF3B97148L, 0x84BE41DEL,
115 0x1ADAD47DL, 0x6DDDE4EBL, 0xF4D4B551L, 0x83D385C7L,
116 0x136C9856L, 0x646BA8C0L, 0xFD62F97AL, 0x8A65C9ECL,
117 0x14015C4FL, 0x63066CD9L, 0xFA0F3D63L, 0x8D080DF5L,
118 0x3B6E20C8L, 0x4C69105EL, 0xD56041E4L, 0xA2677172L,
119 0x3C03E4D1L, 0x4B04D447L, 0xD20D85FDL, 0xA50AB56BL,
120 0x35B5A8FAL, 0x42B2986CL, 0xDBBBC9D6L, 0xACBCF940L,
121 0x32D86CE3L, 0x45DF5C75L, 0xDCD60DCFL, 0xABD13D59L,
122 0x26D930ACL, 0x51DE003AL, 0xC8D75180L, 0xBFD06116L,
123 0x21B4F4B5L, 0x56B3C423L, 0xCFBA9599L, 0xB8BDA50FL,
124 0x2802B89EL, 0x5F058808L, 0xC60CD9B2L, 0xB10BE924L,
125 0x2F6F7C87L, 0x58684C11L, 0xC1611DABL, 0xB6662D3DL,
126 0x76DC4190L, 0x01DB7106L, 0x98D220BCL, 0xEFD5102AL,
127 0x71B18589L, 0x06B6B51FL, 0x9FBFE4A5L, 0xE8B8D433L,
128 0x7807C9A2L, 0x0F00F934L, 0x9609A88EL, 0xE10E9818L,
129 0x7F6A0DBBL, 0x086D3D2DL, 0x91646C97L, 0xE6635C01L,
130 0x6B6B51F4L, 0x1C6C6162L, 0x856530D8L, 0xF262004EL,
131 0x6C0695EDL, 0x1B01A57BL, 0x8208F4C1L, 0xF50FC457L,
132 0x65B0D9C6L, 0x12B7E950L, 0x8BBEB8EAL, 0xFCB9887CL,
133 0x62DD1DDFL, 0x15DA2D49L, 0x8CD37CF3L, 0xFBD44C65L,
134 0x4DB26158L, 0x3AB551CEL, 0xA3BC0074L, 0xD4BB30E2L,
135 0x4ADFA541L, 0x3DD895D7L, 0xA4D1C46DL, 0xD3D6F4FBL,
136 0x4369E96AL, 0x346ED9FCL, 0xAD678846L, 0xDA60B8D0L,
137 0x44042D73L, 0x33031DE5L, 0xAA0A4C5FL, 0xDD0D7CC9L,
138 0x5005713CL, 0x270241AAL, 0xBE0B1010L, 0xC90C2086L,
139 0x5768B525L, 0x206F85B3L, 0xB966D409L, 0xCE61E49FL,
140 0x5EDEF90EL, 0x29D9C998L, 0xB0D09822L, 0xC7D7A8B4L,
141 0x59B33D17L, 0x2EB40D81L, 0xB7BD5C3BL, 0xC0BA6CADL,
142 0xEDB88320L, 0x9ABFB3B6L, 0x03B6E20CL, 0x74B1D29AL,
143 0xEAD54739L, 0x9DD277AFL, 0x04DB2615L, 0x73DC1683L,
144 0xE3630B12L, 0x94643B84L, 0x0D6D6A3EL, 0x7A6A5AA8L,
145 0xE40ECF0BL, 0x9309FF9DL, 0x0A00AE27L, 0x7D079EB1L,
146 0xF00F9344L, 0x8708A3D2L, 0x1E01F268L, 0x6906C2FEL,
147 0xF762575DL, 0x806567CBL, 0x196C3671L, 0x6E6B06E7L,
148 0xFED41B76L, 0x89D32BE0L, 0x10DA7A5AL, 0x67DD4ACCL,
149 0xF9B9DF6FL, 0x8EBEEFF9L, 0x17B7BE43L, 0x60B08ED5L,
150 0xD6D6A3E8L, 0xA1D1937EL, 0x38D8C2C4L, 0x4FDFF252L,
151 0xD1BB67F1L, 0xA6BC5767L, 0x3FB506DDL, 0x48B2364BL,
152 0xD80D2BDAL, 0xAF0A1B4CL, 0x36034AF6L, 0x41047A60L,
153 0xDF60EFC3L, 0xA867DF55L, 0x316E8EEFL, 0x4669BE79L,
154 0xCB61B38CL, 0xBC66831AL, 0x256FD2A0L, 0x5268E236L,
155 0xCC0C7795L, 0xBB0B4703L, 0x220216B9L, 0x5505262FL,
156 0xC5BA3BBEL, 0xB2BD0B28L, 0x2BB45A92L, 0x5CB36A04L,
157 0xC2D7FFA7L, 0xB5D0CF31L, 0x2CD99E8BL, 0x5BDEAE1DL,
158 0x9B64C2B0L, 0xEC63F226L, 0x756AA39CL, 0x026D930AL,
159 0x9C0906A9L, 0xEB0E363FL, 0x72076785L, 0x05005713L,
160 0x95BF4A82L, 0xE2B87A14L, 0x7BB12BAEL, 0x0CB61B38L,
161 0x92D28E9BL, 0xE5D5BE0DL, 0x7CDCEFB7L, 0x0BDBDF21L,
162 0x86D3D2D4L, 0xF1D4E242L, 0x68DDB3F8L, 0x1FDA836EL,
163 0x81BE16CDL, 0xF6B9265BL, 0x6FB077E1L, 0x18B74777L,
164 0x88085AE6L, 0xFF0F6A70L, 0x66063BCAL, 0x11010B5CL,
165 0x8F659EFFL, 0xF862AE69L, 0x616BFFD3L, 0x166CCF45L,
166 0xA00AE278L, 0xD70DD2EEL, 0x4E048354L, 0x3903B3C2L,
167 0xA7672661L, 0xD06016F7L, 0x4969474DL, 0x3E6E77DBL,
168 0xAED16A4AL, 0xD9D65ADCL, 0x40DF0B66L, 0x37D83BF0L,
169 0xA9BCAE53L, 0xDEBB9EC5L, 0x47B2CF7FL, 0x30B5FFE9L,
170 0xBDBDF21CL, 0xCABAC28AL, 0x53B39330L, 0x24B4A3A6L,
171 0xBAD03605L, 0xCDD70693L, 0x54DE5729L, 0x23D967BFL,
172 0xB3667A2EL, 0xC4614AB8L, 0x5D681B02L, 0x2A6F2B94L,
173 0xB40BBE37L, 0xC30C8EA1L, 0x5A05DF1BL, 0x2D02EF8DL,
174 };
175
176 /*****************************************************************/
177 /* End of CRC Lookup Table */
178 /*****************************************************************/
179
180 /* --- Work out the CRC of a bytestring --- */
181
182 #define sym__crc(s_, l_, hv_) do { \
183 unsigned long h_ = 0xFFFFFFFFL; \
184 const char *p_ = s_; \
185 const char *e_ = (s_) + (l_); \
186 \
187 while (p_ < e_) \
188 h_ = (h_ >> 8) ^ (sym__crcTable[(*p_++ ^ h_) & 0xFF]); \
189 hv_ = ~h_ & 0xFFFFFFFFL; \
190 } while (0)
191
192 /*----- Main code ---------------------------------------------------------*/
193
194 #ifndef DEBUG_CRC
195
196 /* --- @sym_createTable@ --- *
197 *
198 * Arguments: @sym_table *t@ = symbol table to initialise
199 *
200 * Returns: ---
201 *
202 * Use: Initialises the given symbol table.
203 */
204
205 void sym_createTable(sym_table *t)
206 {
207 size_t i;
208
209 t->mask = sym__iSize;
210 t->c = (sym__iSize * sym__limFactor) >> 8;
211 t->a = xmalloc((t->mask + 1) * sizeof(sym_base *));
212
213 for (i = 0; i < sym__iSize + 1; i++)
214 t->a[i] = 0;
215 }
216
217 /* --- @sym_destroyTable@ --- *
218 *
219 * Arguments: @sym_table *t@ = pointer to symbol table in question
220 *
221 * Returns: ---
222 *
223 * Use: Destroys a symbol table, freeing all the memory it used to
224 * occupy.
225 */
226
227 void sym_destroyTable(sym_table *t)
228 {
229 size_t i;
230 sym_base *p, *q;
231
232 for (i = 0; i <= t->mask; i++) {
233 p = t->a[i];
234 while (p) {
235 q = p->next;
236 free(p);
237 p = q;
238 }
239 }
240 }
241
242 /* --- @sym_find@ --- *
243 *
244 * Arguments: @sym_table *t@ = pointer to symbol table in question
245 * @const char *n@ = pointer to symbol table to look up
246 * @long l@ = length of the name string or negative to measure
247 * @size_t sz@ = size of desired symbol object, or zero
248 * @unsigned *f@ = pointer to a flag, or null.
249 *
250 * Returns: The address of a @sym_base@ structure, or null if not found
251 * and @sz@ is zero.
252 *
253 * Use: Looks up a symbol in a given symbol table. The name is
254 * passed by the address of its first character. The length
255 * may be given, in which case the name may contain arbitrary
256 * binary data, or it may be given as a negative number, in
257 * which case the length of the name is calculated as
258 * @strlen(n)@.
259 *
260 * The return value is the address of a pointer to a @sym_base@
261 * block (which may have other things on the end, as above). If
262 * the symbol could be found, the return value points to the
263 * symbol block. If the symbol wasn't there, then if @sz@ is
264 * nonzero, a new symbol is created and its address is returned;
265 * otherwise a null pointer is returned.
266 *
267 * The value of @*f@ indicates whether a new symbol entry was
268 * created: a nonzero value indicates that an old value was
269 * found.
270 */
271
272 void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
273 {
274 unsigned long hash; /* Hash value for user's name */
275 size_t len = l < 0 ? strlen(n) + 1 : l; /* Find length of user's name */
276 sym_base *bin; /* Bin containing our item */
277 sym_base *p, *q; /* Pointer wandering through list */
278
279 /* --- Find the correct bin --- */
280
281 sym__crc(n, len, hash); /* Find hash value for this name */
282 bin = p = (sym_base *)(t->a + (hash & t->mask));
283
284 /* --- Search the bin list --- */
285
286 while (p->next) {
287 if (hash == p->next->hash && /* Check hash values first */
288 len == p->next->len && /* Then compare string lengths */
289 !memcmp(n, p->next->name, len)) /* And finally compare the strings */
290 {
291 /* --- Found a match --- *
292 *
293 * As a minor, and probably pointless, tweak, move the item to the
294 * front of its bin list.
295 */
296
297 q = p->next; /* Find the actual symbol block */
298 p->next = q->next; /* Extract block from bin list */
299 q->next = bin->next; /* Set up symbol's next pointer */
300 bin->next = q; /* And reinsert the block */
301
302 /* --- Return the block --- */
303
304 if (f) *f = 1; /* Didn't fail to find the item */
305 return (q); /* And return the block */
306 }
307
308 p = p->next; /* Move onto the next item */
309 }
310
311 /* --- Couldn't find the item there --- */
312
313 if (f) *f = 0; /* Failed to find the block */
314 if (!sz) return (0); /* Return zero if not creating */
315
316 /* --- Create a new symbol block and initialise it --- */
317
318 p = xmalloc(sz); /* Create a new symbol block */
319 p->next = bin->next; /* Set up the next pointer */
320 p->hash = hash; /* Set up the hash value too */
321 p->name = xmalloc(len); /* Allocate a block for the name */
322 p->len = len; /* And set up the string length */
323 memcpy(p->name, n, len); /* And copy the string over */
324
325 bin->next = p; /* Put the pointer into the bin */
326
327 /* --- Consider growing the array --- */
328
329 if (!--t->c) {
330 unsigned long m = t->mask + 1; /* Next set bit in has word */
331 sym_base *p, *q, *r; /* More useful pointers */
332 size_t i, lim; /* Loop counter and limit */
333
334 /* --- Update values in the anchor block --- */
335
336 t->c = ((t->mask + 1) * sym__limFactor) >> 8; /* Set load value */
337 t->mask = (t->mask + 1) * 2 - 1; /* Set the new mask value */
338 t->a = xrealloc(t->a, (t->mask + 1) * sizeof(sym_base *));
339
340 /* --- Now wander through the table rehashing things --- *
341 *
342 * This loop is very careful to avoid problems with aliasing. The items
343 * are dealt with from the end backwards to avoid overwriting bins before
344 * they've been processed.
345 */
346
347 lim = (t->mask + 1) >> 1;
348 for (i = 0; i < lim; i++) {
349 /* --- Some initialisation --- */
350
351 r = t->a[i]; /* Find the list we're dissecting */
352 p = (sym_base *)(t->a + i); /* Find bit-clear list */
353 q = (sym_base *)(t->a + i + lim); /* And the bit-set lsit */
354
355 /* --- Now go through the @r@ list --- */
356
357 while (r) {
358 if (r->hash & m) /* Is the next bit set? */
359 q = q->next = r; /* Yes, so fit up previous link */
360 else
361 p = p->next = r; /* No, so fit up previous link */
362 r = r->next; /* Move onto the next item */
363 }
364 p->next = q->next = 0; /* Null terminate the new lists */
365 }
366 }
367
368 /* --- Finished that, so return the new symbol block --- */
369
370 return (p);
371 }
372
373 /* --- @sym_remove@ --- *
374 *
375 * Arguments: @sym_table *i@ = pointer to a symbol table object
376 * @void *b@ = pointer to symbol table entry
377 *
378 * Returns: ---
379 *
380 * Use: Removes the object from the symbol table. The space occupied
381 * by the object and its name is freed; anything else attached
382 * to the entry should already be gone by this point.
383 */
384
385 void sym_remove(sym_table *t, void *b)
386 {
387 /* --- A quick comment --- *
388 *
389 * Since the @sym_base@ block contains the hash, finding the element in the
390 * bin list is really quick -- it's not worth bothering with things like
391 * doubly linked lists.
392 */
393
394 sym_base *p = b;
395 sym_base *bin = (sym_base *)(t->a + (p->hash & t->mask));
396
397 /* --- Find the item in the bin list --- */
398
399 while (bin->next) {
400 if (bin->next == p)
401 break;
402 bin = bin->next;
403 }
404 if (!bin->next)
405 return;
406
407 /* --- Now just remove the item from the list and free it --- *
408 *
409 * Oh, and bump the load counter.
410 */
411
412 bin->next = p->next;
413 free(p->name);
414 free(p);
415 t->c++;
416 }
417
418 /* --- @sym_createIter@ --- *
419 *
420 * Arguments: @sym_iter *i@ = pointer to an iterator object
421 * @sym_table *t@ = pointer to a symbol table object
422 *
423 * Returns: ---
424 *
425 * Use: Creates a new symbol table iterator which may be used to
426 * iterate through a symbol table.
427 */
428
429 void sym_createIter(sym_iter *i, sym_table *t)
430 {
431 i->t = t;
432 i->i = 0;
433 i->n = 0;
434 }
435
436 /* --- @sym_next@ --- *
437 *
438 * Arguments: @sym_iter *i@ = pointer to iterator object
439 *
440 * Returns: Pointer to the next symbol found, or null when finished.
441 *
442 * Use: Returns the next symbol from the table. Symbols are not
443 * returned in any particular order.
444 */
445
446 void *sym_next(sym_iter *i)
447 {
448 sym_base *p;
449
450 /* --- Find the next item --- */
451
452 while (!i->n) {
453 if (i->i > i->t->mask)
454 return (0);
455 i->n = i->t->a[i->i++];
456 }
457
458 /* --- Update the iterator block --- */
459
460 p = i->n;
461 i->n = p->next;
462
463 /* --- Done --- */
464
465 return (p);
466 }
467
468 #endif
469
470 /*----- CRC test code -----------------------------------------------------*/
471
472 #ifdef DEBUG_CRC
473
474 int main(void)
475 {
476 unsigned long h;
477 sym__crc("123456789", 9, h);
478 printf("crc check == %04x\n", h);
479 return (0);
480 }
481
482 #endif
483
484 /*----- Symbol table test code --------------------------------------------*/
485
486 #ifdef TEST_RIG
487
488 #include <errno.h>
489 #include <time.h>
490
491 #include "dbutils.h"
492
493 typedef struct sym_word {
494 sym_base base;
495 size_t i;
496 } sym_word;
497
498
499 /* --- What it does --- *
500 *
501 * Reads the file /usr/dict/words (change to some other file full of
502 * interesting and appropriate bits of text to taste) into a big buffer and
503 * picks apart into lines. Then picks lines at random and enters them into
504 * the symbol table.
505 */
506
507 int main(void)
508 {
509 char *buff, *p, *lim;
510 size_t sz, done;
511 FILE *fp;
512 int i;
513 char **line;
514 sym_word **flag;
515 sym_table tbl;
516 int entries;
517
518 /* --- Initialise for reading the file --- */
519
520 sz = BUFSIZ;
521 buff = xmalloc(sz + 1);
522 done = 0;
523
524 if ((fp = fopen("/usr/dict/words", "r")) == 0)
525 fprintf(stderr, "buggered ;-( (%s)\n", strerror(errno));
526
527 /* --- Read buffers of text --- *
528 *
529 * Read a buffer. If more to come, double the buffer size and try again.
530 * This is the method I recommended to comp.lang.c, so I may as well try
531 * it.
532 */
533
534 for (;;) {
535 i = fread(buff + done, 1, sz - done, fp);
536 done += i;
537 if (done != sz)
538 break;
539 sz <<= 1;
540 buff = xrealloc(buff, sz + 1);
541 }
542
543 /* --- Count the lines --- */
544
545 lim = buff + done;
546
547 sz = 1;
548 for (p = buff; p < lim; p++)
549 if (*p == '\n') sz++;
550
551 /* --- Build a table of line starts --- */
552
553 line = xmalloc(sz * sizeof(char *));
554 i = 0;
555 line[i++] = buff;
556 for (p = buff; p < lim; p++)
557 if (*p == '\n') *p = 0, line[i++] = p + 1;
558 *lim = 0;
559
560 /* --- Build a table of lines --- *
561 *
562 * This reverses the mapping which the symbol table performs, so that its
563 * accuracy can be tested.
564 */
565
566 flag = xmalloc(sz * sizeof(sym_word *));
567 for (i = 0; i < sz; i++)
568 flag[i] = 0;
569 entries = 0;
570
571 sym_createTable(&tbl);
572
573 for (;;) {
574 i = (unsigned)rand() % sz;
575
576 switch (rand() % 5)
577 {
578 case 0: {
579 sym_word *w;
580
581 /* printf("find `%s'\n", line[i]); */
582 if ((rand() & 1023) == 0) {
583 putchar('.'); fflush(stdout);
584 }
585
586 w = sym_find(&tbl, line[i], -1, 0, 0);
587 if (w != flag[i])
588 printf("*** error: find `%s' gave %p not %p\n",
589 line[i], (void *)w, (void *)flag[i]);
590 else if (w && w->i != i)
591 printf("*** error: find sym for `%s' gives index %i not %i\n",
592 line[i], w->i, i);
593 } break;
594
595 case 1: {
596 unsigned f;
597 sym_word *w;
598
599 /* printf("create `%s'\n", line[i]); */
600 if ((rand() & 1023) == 0) {
601 putchar('+'); fflush(stdout);
602 }
603
604 w = sym_find(&tbl, line[i], -1, sizeof(sym_word), &f);
605 if (f)
606 {
607 if (w != flag[i])
608 printf("*** error: create `%s' gave %p not %p\n",
609 line[i], (void *)w, (void *)flag[i]);
610 else if (w && w->i != i)
611 printf("*** error: create sym for `%s' gives index %i not %i\n",
612 line[i], w->i, i);
613 }
614 else
615 {
616 if (flag[i])
617 printf("*** error: create `%s' gave new block, should be %p\n",
618 line[i], (void *)flag[i]);
619 else {
620 flag[i] = w;
621 w->i = i;
622 entries++;
623 }
624 }
625 } break;
626
627 case 2: {
628 sym_iter it;
629 sym_word *w, **ntbl;
630 int v = (rand() % entries) == 0;
631 if (!v)
632 break;
633 printf("\niterated %i entries\n", entries);
634 break;
635
636 printf("iterate\n");
637
638 ntbl = xmalloc(sz * sizeof(sym_word *));
639 memcpy(ntbl, flag, sz * sizeof(sym_word *));
640 sym_createIter(&it, &tbl);
641
642 while ((w = sym_next(&it)) != 0) {
643 if (ntbl[w->i] == 0)
644 printf("*** error: iterate returned duff item %i\n", w->i);
645 else
646 ntbl[w->i] = 0;
647 }
648
649 for (i = 0; i < sz; i++)
650 if (ntbl[i]) printf("*** error: iterate didn't return item %i\n",
651 i);
652 free(ntbl);
653 } break;
654
655 case 3: {
656 sym_base *b;
657 int v = rand() & 255 ? 0 : 1;
658 break;
659
660 printf("dump\n");
661
662 for (i = 0; i <= tbl.mask; i++) {
663 if (!tbl.a[i]) continue;
664 if (v) printf(" %i: ", i);
665 b = tbl.a[i];
666 while (b) {
667 if ((b->hash & tbl.mask) != i)
668 printf("*** error: bad hash value found");
669 if (v) printf("`%s'(%08lx:%lu) ",
670 line[((sym_word *)b)->i],
671 b->hash,
672 b->hash & tbl.mask);
673 b = b->next;
674 }
675 if (v) putchar('\n');
676 }
677 } break;
678
679 case 4: {
680 if (flag[i]) {
681 /* printf("remove `%s'\n", flag[i]->base.name); */
682 if ((rand() & 1023) == 0) {
683 putchar('-'); fflush(stdout);
684 }
685 sym_remove(&tbl, flag[i]);
686 flag[i] = 0;
687 entries--;
688 }
689 } break;
690 }
691
692 }
693
694 return (0);
695 }
696
697 #endif
698
699 /*----- That's all, folks -------------------------------------------------*/
Management for shared accounts