~mdw / become / blob
? search:


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