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

   1 /* -*-c-*-
   2  *
   3  * $Id$
   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 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.
  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.2  2000/07/02 15:21:20  mdw
  54  * Fix licence text.
  55  *
  56  * Revision 1.1  2000/05/21 11:28:30  mdw
  57  * Initial check-in.
  58  *
  59  * --- Past lives (Become) --- *
  60  *
  61  * Revision 1.4  1998/01/12 16:46:28  mdw
  62  * Fix copyright date.
  63  *
  64  * Revision 1.3  1997/08/20  16:22:59  mdw
  65  * Patch memory leak.
  66  *
  67  * Revision 1.2  1997/08/04 10:24:25  mdw
  68  * Sources placed under CVS control.
  69  *
  70  * Revision 1.1  1997/07/21  13:47:44  mdw
  71  * Initial revision
  72  *
  73  */
  74
  75 /*----- Header files ------------------------------------------------------*/
  76
  77 #include <stdio.h>
  78 #include <stdlib.h>
  79 #include <string.h>
  80
  81 #include "bits.h"
  82 #include "sym.h"
  83
  84 /*----- Tuning parameters -------------------------------------------------*/
  85
  86 /* --- Initial hash table size --- *
  87  *
  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.
  90  */
  91
  92 #define SYM_INITSZ 256                  /* Size of a new hash table */
  93
  94 /* --- Maximum load factor --- *
  95  *
  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
 100  * doubled in size.
 101  */
 102
 103 #define SYM_LIMIT(n) ((n) * 2)          /* Load factor for growing table */
 104
 105 /*----- CRC table ---------------------------------------------------------*/
 106
 107 /*****************************************************************/
 108 /*                                                               */
 109 /* CRC LOOKUP TABLE                                              */
 110 /* ================                                              */
 111 /*                                                               */
 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:                                    */
 116 /*                                                               */
 117 /*    Width   : 32 bits                                          */
 118 /*    Poly    : 0x04C11DB7                                       */
 119 /*    Init    : 0xFFFFFFFF                                       */
 120 /*    XorOut  : 0xFFFFFFFF                                       */
 121 /*    Reverse : Yes                                              */
 122 /*    Check   : 0xCBF43926                                       */
 123 /*                                                               */
 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'.        */
 129 /*                                                               */
 130 /*****************************************************************/
 131
 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
 197 };
 198
 199 /*****************************************************************/
 200 /*                   End of CRC Lookup Table                     */
 201 /*****************************************************************/
 202
 203 /* --- Work out the CRC of a bytestring --- */
 204
 205 #define CRC(_s, _l, _hv) do {                                           \
 206   uint32 _h = 0xffffffff;                                               \
 207   const char *_p = _s;                                                  \
 208   const char *_e = (_s) + (_l);                                         \
 209                                                                         \
 210   while (_p < _e)                                                       \
 211     _h = (_h >> 8) ^ (crctab[(*_p++ ^ _h) & 0xFF]);                     \
 212   _hv = ~_h & 0xffffffff;                                               \
 213 } while (0)
 214
 215 /*----- Memory allocation -------------------------------------------------*/
 216
 217 static void die(const char *p)
 218 {
 219   fprintf(stderr, "%s\n", p);
 220   exit(EXIT_FAILURE);
 221 }
 222
 223 static void *xmalloc(size_t sz)
 224 {
 225   void *p = malloc(sz);
 226   if (!p)
 227     die("not enough memory");
 228   return (p);
 229 }
 230
 231 static void *xrealloc(void *p, size_t sz)
 232 {
 233   p = realloc(p, sz);
 234   if (!p)
 235     die("not enough memory");
 236   return (p);
 237 }
 238
 239
 240 /*----- Main code ---------------------------------------------------------*/
 241
 242 /* --- @sym_create@ --- *
 243  *
 244  * Arguments:   @sym_table *t@ = symbol table to initialize
 245  *
 246  * Returns:     ---
 247  *
 248  * Use:         Initialises the given symbol table.
 249  */
 250
 251 void sym_create(sym_table *t)
 252 {
 253   size_t i;
 254
 255   t->mask = SYM_INITSZ - 1;
 256   t->c = SYM_LIMIT(SYM_INITSZ);
 257   t->a = xmalloc((t->mask + 1) * sizeof(sym_base *));
 258
 259   for (i = 0; i < SYM_INITSZ + 1; i++)
 260     t->a[i] = 0;
 261 }
 262
 263 /* --- @sym_destroy@ --- *
 264  *
 265  * Arguments:   @sym_table *t@ = pointer to symbol table in question
 266  *
 267  * Returns:     ---
 268  *
 269  * Use:         Destroys a symbol table, freeing all the memory it used to
 270  *              occupy.
 271  */
 272
 273 void sym_destroy(sym_table *t)
 274 {
 275   size_t i;
 276   sym_base *p, *q;
 277
 278   for (i = 0; i <= t->mask; i++) {
 279     p = t->a[i];
 280     while (p) {
 281       q = p->next;
 282       free(p->name);
 283       free(p);
 284       p = q;
 285     }
 286   }
 287   free(t->a);
 288 }
 289
 290 /* --- @sym_find@ --- *
 291  *
 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.
 297  *
 298  * Returns:     The address of a @sym_base@ structure, or null if not found
 299  *              and @sz@ is zero.
 300  *
 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
 306  *              @strlen(n) + 1@.
 307  *
 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.
 314  *
 315  *              The value of @*f@ indicates whether a new symbol entry was
 316  *              created: a nonzero value indicates that an old value was
 317  *              found.
 318  */
 319
 320 void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
 321 {
 322   uint32 hash;
 323   size_t len = l < 0 ? strlen(n) + 1 : l;
 324   sym_base *bin;
 325   sym_base *p, *q;
 326
 327   /* --- Find the correct bin --- */
 328
 329   CRC(n, len, hash);
 330   bin = p = (sym_base *)(t->a + (hash & t->mask));
 331
 332   /* --- Search the bin list --- */
 333
 334   while (p->next) {
 335     if (hash == p->next->hash && len == p->next->len &&
 336         !memcmp(n, p->next->name, len)) {
 337
 338       /* --- Found a match --- *
 339        *
 340        * As a minor, and probably pointless, tweak, move the item to the
 341        * front of its bin list.
 342        */
 343
 344       q = p->next;
 345       p->next = q->next;
 346       q->next = bin->next;
 347       bin->next = q;
 348
 349       /* --- Return the block --- */
 350
 351       if (f) *f = 1;
 352       return (q);
 353     }
 354
 355     p = p->next;
 356   }
 357
 358   /* --- Couldn't find the item there --- */
 359
 360   if (f) *f = 0;
 361   if (!sz) return (0);
 362
 363   /* --- Create a new symbol block and initialize it --- */
 364
 365   p = xmalloc(sz);
 366   p->next = bin->next;
 367   p->hash = hash;
 368   p->name = xmalloc(len);
 369   p->len = len;
 370   memcpy(p->name, n, len);
 371
 372   bin->next = p;
 373
 374   /* --- Consider growing the array --- */
 375
 376   if (!--t->c) {
 377     uint32 m = t->mask + 1;
 378     sym_base *p, *q, *r;
 379     size_t i, lim;
 380
 381     /* --- Update values in the anchor block --- */
 382
 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 *));
 386
 387     /* --- Now wander through the table rehashing things --- *
 388      *
 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.
 392      */
 393
 394     lim = (t->mask + 1) >> 1;
 395     for (i = 0; i < lim; i++) {
 396
 397       /* --- Some initialization --- */
 398
 399       r = t->a[i];
 400       p = (sym_base *)(t->a + i);
 401       q = (sym_base *)(t->a + i + lim);
 402
 403       /* --- Now go through the @r@ list --- */
 404
 405       while (r) {
 406         if (r->hash & m)
 407           q = q->next = r;
 408         else
 409           p = p->next = r;
 410         r = r->next;
 411       }
 412       p->next = q->next = 0;
 413     }
 414   }
 415
 416   /* --- Finished that, so return the new symbol block --- */
 417
 418   return (p);
 419 }
 420
 421 /* --- @sym_remove@ --- *
 422  *
 423  * Arguments:   @sym_table *i@ = pointer to a symbol table object
 424  *              @void *b@ = pointer to symbol table entry
 425  *
 426  * Returns:     ---
 427  *
 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.
 431  */
 432
 433 void sym_remove(sym_table *t, void *b)
 434 {
 435   /* --- A quick comment --- *
 436    *
 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.
 440    */
 441
 442   sym_base *p = b;
 443   sym_base *bin = (sym_base *)(t->a + (p->hash & t->mask));
 444
 445   /* --- Find the item in the bin list --- */
 446
 447   while (bin->next) {
 448     if (bin->next == p)
 449       break;
 450     bin = bin->next;
 451   }
 452   if (!bin->next)
 453     return;
 454
 455   /* --- Now just remove the item from the list and free it --- *
 456    *
 457    * Oh, and bump the load counter.
 458    */
 459
 460   bin->next = p->next;
 461   free(p->name);
 462   free(p);
 463   t->c++;
 464 }
 465
 466 /* --- @sym_mkiter@ --- *
 467  *
 468  * Arguments:   @sym_iter *i@ = pointer to an iterator object
 469  *              @sym_table *t@ = pointer to a symbol table object
 470  *
 471  * Returns:     ---
 472  *
 473  * Use:         Creates a new symbol table iterator which may be used to
 474  *              iterate through a symbol table.
 475  */
 476
 477 void sym_mkiter(sym_iter *i, sym_table *t)
 478 {
 479   i->t = t;
 480   i->i = 0;
 481   i->n = 0;
 482 }
 483
 484 /* --- @sym_next@ --- *
 485  *
 486  * Arguments:   @sym_iter *i@ = pointer to iterator object
 487  *
 488  * Returns:     Pointer to the next symbol found, or null when finished.
 489  *
 490  * Use:         Returns the next symbol from the table.  Symbols are not
 491  *              returned in any particular order.
 492  */
 493
 494 void *sym_next(sym_iter *i)
 495 {
 496   sym_base *p;
 497
 498   /* --- Find the next item --- */
 499
 500   while (!i->n) {
 501     if (i->i > i->t->mask)
 502       return (0);
 503     i->n = i->t->a[i->i++];
 504   }
 505
 506   /* --- Update the iterator block --- */
 507
 508   p = i->n;
 509   i->n = p->next;
 510
 511   /* --- Done --- */
 512
 513   return (p);
 514 }
 515
 516 /*----- That's all, folks -------------------------------------------------*/