chiark - git - mdw - storin/blob - sym.c

   1 /* -*-c-*-
   2  *
   3  * $Id: sym.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
   4  *
   5  * Symbol table management
   6  *
   7  * (c) 1998 Straylight
   8  * (c) 2000 Mark Wooding
   9  */
  10
  11 /*----- Licensing notice --------------------------------------------------*
  12  *
  13  * Copyright (c) 2000 Mark Wooding
  14  * All rights reserved.
  15  *
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions are
  18  * met:
  19  *
  20  * 1. Redistributions of source code must retain the above copyright
  21  *    notice, this list of conditions and the following disclaimer.
  22  *
  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.
  26  *
  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
  29  *    permission.
  30  *
  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 REGENTS 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.
  42  *
  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.
  48  */
  49
  50 /*----- Revision history --------------------------------------------------*
  51  *
  52  * $Log: sym.c,v $
  53  * Revision 1.1  2000/05/21 11:28:30  mdw
  54  * Initial check-in.
  55  *
  56  * --- Past lives (Become) --- *
  57  *
  58  * Revision 1.4  1998/01/12 16:46:28  mdw
  59  * Fix copyright date.
  60  *
  61  * Revision 1.3  1997/08/20  16:22:59  mdw
  62  * Patch memory leak.
  63  *
  64  * Revision 1.2  1997/08/04 10:24:25  mdw
  65  * Sources placed under CVS control.
  66  *
  67  * Revision 1.1  1997/07/21  13:47:44  mdw
  68  * Initial revision
  69  *
  70  */
  71
  72 /*----- Header files ------------------------------------------------------*/
  73
  74 #include <stdio.h>
  75 #include <stdlib.h>
  76 #include <string.h>
  77
  78 #include "bits.h"
  79 #include "sym.h"
  80
  81 /*----- Tuning parameters -------------------------------------------------*/
  82
  83 /* --- Initial hash table size --- *
  84  *
  85  * This is the initial @mask@ value.  It must be of the form %$2^n - 1$%,
  86  * so that it can be used to mask of the bottom bits of a hash value.
  87  */
  88
  89 #define SYM_INITSZ 256                  /* Size of a new hash table */
  90
  91 /* --- Maximum load factor --- *
  92  *
  93  * This parameter controls how much the table has to be loaded before the
  94  * table is extended.  The number of elements %$n$%, the number of bins %$b$%
  95  * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
  96  * added to the table and this relation is found to be false, the table is
  97  * doubled in size.
  98  */
  99
 100 #define SYM_LIMIT(n) ((n) * 2)          /* Load factor for growing table */
 101
 102 /*----- CRC table ---------------------------------------------------------*/
 103
 104 /*****************************************************************/
 105 /*                                                               */
 106 /* CRC LOOKUP TABLE                                              */
 107 /* ================                                              */
 108 /*                                                               */
 109 /* The following CRC lookup table was generated automagically    */
 110 /* by `crcgen', which is based on the Rocksoft^tm Model CRC      */
 111 /* Algorithm Table Generation Program.  The model parameters     */
 112 /* supplied to `crcgen' were:                                    */
 113 /*                                                               */
 114 /*    Width   : 32 bits                                          */
 115 /*    Poly    : 0x04C11DB7                                       */
 116 /*    Init    : 0xFFFFFFFF                                       */
 117 /*    XorOut  : 0xFFFFFFFF                                       */
 118 /*    Reverse : Yes                                              */
 119 /*    Check   : 0xCBF43926                                       */
 120 /*                                                               */
 121 /* For more information on the Rocksoft^tm Model CRC Algorithm,  */
 122 /* see the document titled `A Painless Guide to CRC Error        */
 123 /* Detection Algorithms' by Ross Williams                        */
 124 /* (ross@@guest.adelaide.edu.au.). This document is likely to be */
 125 /* in the FTP archive `ftp.adelaide.edu.au/pub/rocksoft'.        */
 126 /*                                                               */
 127 /*****************************************************************/
 128
 129 static uint32 crctab[256] = {
 130   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
 131   0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
 132   0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 133   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
 134   0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 135   0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 136   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
 137   0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
 138   0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 139   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 140   0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
 141   0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 142   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
 143   0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 144   0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 145   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
 146   0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
 147   0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 148   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
 149   0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 150   0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 151   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 152   0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 153   0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 154   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 155   0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 156   0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 157   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 158   0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 159   0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 160   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 161   0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 162   0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 163   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 164   0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 165   0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 166   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 167   0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 168   0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 169   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 170   0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 171   0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 172   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 173   0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 174   0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 175   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 176   0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 177   0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 178   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 179   0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 180   0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 181   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 182   0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 183   0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 184   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 185   0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 186   0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 187   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 188   0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 189   0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 190   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 191   0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 192   0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 193   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 194 };
 195
 196 /*****************************************************************/
 197 /*                   End of CRC Lookup Table                     */
 198 /*****************************************************************/
 199
 200 /* --- Work out the CRC of a bytestring --- */
 201
 202 #define CRC(_s, _l, _hv) do {                                           \
 203   uint32 _h = 0xffffffff;                                               \
 204   const char *_p = _s;                                                  \
 205   const char *_e = (_s) + (_l);                                         \
 206                                                                         \
 207   while (_p < _e)                                                       \
 208     _h = (_h >> 8) ^ (crctab[(*_p++ ^ _h) & 0xFF]);                     \
 209   _hv = ~_h & 0xffffffff;                                               \
 210 } while (0)
 211
 212 /*----- Memory allocation -------------------------------------------------*/
 213
 214 static void die(const char *p)
 215 {
 216   fprintf(stderr, "%s\n", p);
 217   exit(EXIT_FAILURE);
 218 }
 219
 220 static void *xmalloc(size_t sz)
 221 {
 222   void *p = malloc(sz);
 223   if (!p)
 224     die("not enough memory");
 225   return (p);
 226 }
 227
 228 static void *xrealloc(void *p, size_t sz)
 229 {
 230   p = realloc(p, sz);
 231   if (!p)
 232     die("not enough memory");
 233   return (p);
 234 }
 235
 236
 237 /*----- Main code ---------------------------------------------------------*/
 238
 239 /* --- @sym_create@ --- *
 240  *
 241  * Arguments:   @sym_table *t@ = symbol table to initialize
 242  *
 243  * Returns:     ---
 244  *
 245  * Use:         Initialises the given symbol table.
 246  */
 247
 248 void sym_create(sym_table *t)
 249 {
 250   size_t i;
 251
 252   t->mask = SYM_INITSZ - 1;
 253   t->c = SYM_LIMIT(SYM_INITSZ);
 254   t->a = xmalloc((t->mask + 1) * sizeof(sym_base *));
 255
 256   for (i = 0; i < SYM_INITSZ + 1; i++)
 257     t->a[i] = 0;
 258 }
 259
 260 /* --- @sym_destroy@ --- *
 261  *
 262  * Arguments:   @sym_table *t@ = pointer to symbol table in question
 263  *
 264  * Returns:     ---
 265  *
 266  * Use:         Destroys a symbol table, freeing all the memory it used to
 267  *              occupy.
 268  */
 269
 270 void sym_destroy(sym_table *t)
 271 {
 272   size_t i;
 273   sym_base *p, *q;
 274
 275   for (i = 0; i <= t->mask; i++) {
 276     p = t->a[i];
 277     while (p) {
 278       q = p->next;
 279       free(p->name);
 280       free(p);
 281       p = q;
 282     }
 283   }
 284   free(t->a);
 285 }
 286
 287 /* --- @sym_find@ --- *
 288  *
 289  * Arguments:   @sym_table *t@ = pointer to symbol table in question
 290  *              @const char *n@ = pointer to symbol table to look up
 291  *              @long l@ = length of the name string or negative to measure
 292  *              @size_t sz@ = size of desired symbol object, or zero
 293  *              @unsigned *f@ = pointer to a flag, or null.
 294  *
 295  * Returns:     The address of a @sym_base@ structure, or null if not found
 296  *              and @sz@ is zero.
 297  *
 298  * Use:         Looks up a symbol in a given symbol table.  The name is
 299  *              passed by the address of its first character.  The length
 300  *              may be given, in which case the name may contain arbitrary
 301  *              binary data, or it may be given as a negative number, in
 302  *              which case the length of the name is calculated as
 303  *              @strlen(n) + 1@.
 304  *
 305  *              The return value is the address of a pointer to a @sym_base@
 306  *              block (which may have other things on the end, as above).  If
 307  *              the symbol could be found, the return value points to the
 308  *              symbol block.  If the symbol wasn't there, then if @sz@ is
 309  *              nonzero, a new symbol is created and its address is returned;
 310  *              otherwise a null pointer is returned.
 311  *
 312  *              The value of @*f@ indicates whether a new symbol entry was
 313  *              created: a nonzero value indicates that an old value was
 314  *              found.
 315  */
 316
 317 void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
 318 {
 319   uint32 hash;
 320   size_t len = l < 0 ? strlen(n) + 1 : l;
 321   sym_base *bin;
 322   sym_base *p, *q;
 323
 324   /* --- Find the correct bin --- */
 325
 326   CRC(n, len, hash);
 327   bin = p = (sym_base *)(t->a + (hash & t->mask));
 328
 329   /* --- Search the bin list --- */
 330
 331   while (p->next) {
 332     if (hash == p->next->hash && len == p->next->len &&
 333         !memcmp(n, p->next->name, len)) {
 334
 335       /* --- Found a match --- *
 336        *
 337        * As a minor, and probably pointless, tweak, move the item to the
 338        * front of its bin list.
 339        */
 340
 341       q = p->next;
 342       p->next = q->next;
 343       q->next = bin->next;
 344       bin->next = q;
 345
 346       /* --- Return the block --- */
 347
 348       if (f) *f = 1;
 349       return (q);
 350     }
 351
 352     p = p->next;
 353   }
 354
 355   /* --- Couldn't find the item there --- */
 356
 357   if (f) *f = 0;
 358   if (!sz) return (0);
 359
 360   /* --- Create a new symbol block and initialize it --- */
 361
 362   p = xmalloc(sz);
 363   p->next = bin->next;
 364   p->hash = hash;
 365   p->name = xmalloc(len);
 366   p->len = len;
 367   memcpy(p->name, n, len);
 368
 369   bin->next = p;
 370
 371   /* --- Consider growing the array --- */
 372
 373   if (!--t->c) {
 374     uint32 m = t->mask + 1;
 375     sym_base *p, *q, *r;
 376     size_t i, lim;
 377
 378     /* --- Update values in the anchor block --- */
 379
 380     t->c = SYM_LIMIT(t->mask + 1);
 381     t->mask = (t->mask + 1) * 2 - 1;
 382     t->a = xrealloc(t->a, (t->mask + 1) * sizeof(sym_base *));
 383
 384     /* --- Now wander through the table rehashing things --- *
 385      *
 386      * This loop is very careful to avoid problems with aliasing.  The items
 387      * are dealt with from the end backwards to avoid overwriting bins before
 388      * they've been processed.
 389      */
 390
 391     lim = (t->mask + 1) >> 1;
 392     for (i = 0; i < lim; i++) {
 393
 394       /* --- Some initialization --- */
 395
 396       r = t->a[i];
 397       p = (sym_base *)(t->a + i);
 398       q = (sym_base *)(t->a + i + lim);
 399
 400       /* --- Now go through the @r@ list --- */
 401
 402       while (r) {
 403         if (r->hash & m)
 404           q = q->next = r;
 405         else
 406           p = p->next = r;
 407         r = r->next;
 408       }
 409       p->next = q->next = 0;
 410     }
 411   }
 412
 413   /* --- Finished that, so return the new symbol block --- */
 414
 415   return (p);
 416 }
 417
 418 /* --- @sym_remove@ --- *
 419  *
 420  * Arguments:   @sym_table *i@ = pointer to a symbol table object
 421  *              @void *b@ = pointer to symbol table entry
 422  *
 423  * Returns:     ---
 424  *
 425  * Use:         Removes the object from the symbol table.  The space occupied
 426  *              by the object and its name is freed; anything else attached
 427  *              to the entry should already be gone by this point.
 428  */
 429
 430 void sym_remove(sym_table *t, void *b)
 431 {
 432   /* --- A quick comment --- *
 433    *
 434    * Since the @sym_base@ block contains the hash, finding the element in the
 435    * bin list is really quick -- it's not worth bothering with things like
 436    * doubly linked lists.
 437    */
 438
 439   sym_base *p = b;
 440   sym_base *bin = (sym_base *)(t->a + (p->hash & t->mask));
 441
 442   /* --- Find the item in the bin list --- */
 443
 444   while (bin->next) {
 445     if (bin->next == p)
 446       break;
 447     bin = bin->next;
 448   }
 449   if (!bin->next)
 450     return;
 451
 452   /* --- Now just remove the item from the list and free it --- *
 453    *
 454    * Oh, and bump the load counter.
 455    */
 456
 457   bin->next = p->next;
 458   free(p->name);
 459   free(p);
 460   t->c++;
 461 }
 462
 463 /* --- @sym_mkiter@ --- *
 464  *
 465  * Arguments:   @sym_iter *i@ = pointer to an iterator object
 466  *              @sym_table *t@ = pointer to a symbol table object
 467  *
 468  * Returns:     ---
 469  *
 470  * Use:         Creates a new symbol table iterator which may be used to
 471  *              iterate through a symbol table.
 472  */
 473
 474 void sym_mkiter(sym_iter *i, sym_table *t)
 475 {
 476   i->t = t;
 477   i->i = 0;
 478   i->n = 0;
 479 }
 480
 481 /* --- @sym_next@ --- *
 482  *
 483  * Arguments:   @sym_iter *i@ = pointer to iterator object
 484  *
 485  * Returns:     Pointer to the next symbol found, or null when finished.
 486  *
 487  * Use:         Returns the next symbol from the table.  Symbols are not
 488  *              returned in any particular order.
 489  */
 490
 491 void *sym_next(sym_iter *i)
 492 {
 493   sym_base *p;
 494
 495   /* --- Find the next item --- */
 496
 497   while (!i->n) {
 498     if (i->i > i->t->mask)
 499       return (0);
 500     i->n = i->t->a[i->i++];
 501   }
 502
 503   /* --- Update the iterator block --- */
 504
 505   p = i->n;
 506   i->n = p->next;
 507
 508   /* --- Done --- */
 509
 510   return (p);
 511 }
 512
 513 /*----- That's all, folks -------------------------------------------------*/