chiark - git - mdw - become/blob - src/sym.c

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