contrib/awk/array.c

   1 /*
   2  * array.c - routines for associative arrays.
   3  */
   4
   5 /*
   6  * Copyright (C) 1986, 1988, 1989, 1991-1999 the Free Software Foundation, Inc.
   7  *
   8  * This file is part of GAWK, the GNU implementation of the
   9  * AWK Programming Language.
  10  *
  11  * GAWK is free software; you can redistribute it and/or modify
  12  * it under the terms of the GNU General Public License as published by
  13  * the Free Software Foundation; either version 2 of the License, or
  14  * (at your option) any later version.
  15  *
  16  * GAWK is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA
  24  */
  25
  26 /*
  27  * Tree walks (``for (iggy in foo)'') and array deletions use expensive
  28  * linear searching.  So what we do is start out with small arrays and
  29  * grow them as needed, so that our arrays are hopefully small enough,
  30  * most of the time, that they're pretty full and we're not looking at
  31  * wasted space.
  32  *
  33  * The decision is made to grow the array if the average chain length is
  34  * ``too big''. This is defined as the total number of entries in the table
  35  * divided by the size of the array being greater than some constant.
  36  */
  37
  38 #define AVG_CHAIN_MAX   10   /* don't want to linear search more than this */
  39
  40 #include "awk.h"
  41
  42 static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
  43 static void grow_table P((NODE *symbol));
  44
  45 /* concat_exp --- concatenate expression list into a single string */
  46
  47 NODE *
  48 concat_exp(tree)
  49 register NODE *tree;
  50 {
  51         register NODE *r;
  52         char *str;
  53         char *s;
  54         size_t len;
  55         int offset;
  56         size_t subseplen;
  57         char *subsep;
  58
  59         if (tree->type != Node_expression_list)
  60                 return force_string(tree_eval(tree));
  61         r = force_string(tree_eval(tree->lnode));
  62         if (tree->rnode == NULL)
  63                 return r;
  64         subseplen = SUBSEP_node->lnode->stlen;
  65         subsep = SUBSEP_node->lnode->stptr;
  66         len = r->stlen + subseplen + 2;
  67         emalloc(str, char *, len, "concat_exp");
  68         memcpy(str, r->stptr, r->stlen+1);
  69         s = str + r->stlen;
  70         free_temp(r);
  71         for (tree = tree->rnode; tree != NULL; tree = tree->rnode) {
  72                 if (subseplen == 1)
  73                         *s++ = *subsep;
  74                 else {
  75                         memcpy(s, subsep, subseplen+1);
  76                         s += subseplen;
  77                 }
  78                 r = force_string(tree_eval(tree->lnode));
  79                 len += r->stlen + subseplen;
  80                 offset = s - str;
  81                 erealloc(str, char *, len, "concat_exp");
  82                 s = str + offset;
  83                 memcpy(s, r->stptr, r->stlen+1);
  84                 s += r->stlen;
  85                 free_temp(r);
  86         }
  87         r = make_str_node(str, s - str, ALREADY_MALLOCED);
  88         r->flags |= TEMP;
  89         return r;
  90 }
  91
  92 /* assoc_clear --- flush all the values in symbol[] before doing a split() */
  93
  94 void
  95 assoc_clear(symbol)
  96 NODE *symbol;
  97 {
  98         int i;
  99         NODE *bucket, *next;
 100
 101         if (symbol->var_array == NULL)
 102                 return;
 103         for (i = 0; i < symbol->array_size; i++) {
 104                 for (bucket = symbol->var_array[i]; bucket != NULL; bucket = next) {
 105                         next = bucket->ahnext;
 106                         unref(bucket->ahname);
 107                         unref(bucket->ahvalue);
 108                         freenode(bucket);
 109                 }
 110                 symbol->var_array[i] = NULL;
 111         }
 112         free(symbol->var_array);
 113         symbol->var_array = NULL;
 114         symbol->array_size = symbol->table_size = 0;
 115         symbol->flags &= ~ARRAYMAXED;
 116 }
 117
 118 /* hash --- calculate the hash function of the string in subs */
 119
 120 unsigned int
 121 hash(s, len, hsize)
 122 register const char *s;
 123 register size_t len;
 124 unsigned long hsize;
 125 {
 126         register unsigned long h = 0;
 127
 128         /*
 129          * This is INCREDIBLY ugly, but fast.  We break the string up into
 130          * 8 byte units.  On the first time through the loop we get the
 131          * "leftover bytes" (strlen % 8).  On every other iteration, we
 132          * perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
 133          * saves us 7 cmp & branch instructions.  If this routine is
 134          * heavily used enough, it's worth the ugly coding.
 135          *
 136          * OZ's original sdbm hash, copied from Margo Seltzers db package.
 137          */
 138
 139         /*
 140          * Even more speed:
 141          * #define HASHC   h = *s++ + 65599 * h
 142          * Because 65599 = pow(2, 6) + pow(2, 16) - 1 we multiply by shifts
 143          */
 144 #define HASHC   htmp = (h << 6);  \
 145                 h = *s++ + htmp + (htmp << 10) - h
 146
 147         unsigned long htmp;
 148
 149         h = 0;
 150
 151 #if defined(VAXC)
 152         /*
 153          * This was an implementation of "Duff's Device", but it has been
 154          * redone, separating the switch for extra iterations from the
 155          * loop. This is necessary because the DEC VAX-C compiler is
 156          * STOOPID.
 157          */
 158         switch (len & (8 - 1)) {
 159         case 7:         HASHC;
 160         case 6:         HASHC;
 161         case 5:         HASHC;
 162         case 4:         HASHC;
 163         case 3:         HASHC;
 164         case 2:         HASHC;
 165         case 1:         HASHC;
 166         default:        break;
 167         }
 168
 169         if (len > (8 - 1)) {
 170                 register size_t loop = len >> 3;
 171                 do {
 172                         HASHC;
 173                         HASHC;
 174                         HASHC;
 175                         HASHC;
 176                         HASHC;
 177                         HASHC;
 178                         HASHC;
 179                         HASHC;
 180                 } while (--loop);
 181         }
 182 #else /* ! VAXC */
 183         /* "Duff's Device" for those who can handle it */
 184         if (len > 0) {
 185                 register size_t loop = (len + 8 - 1) >> 3;
 186
 187                 switch (len & (8 - 1)) {
 188                 case 0:
 189                         do {    /* All fall throughs */
 190                                 HASHC;
 191                 case 7:         HASHC;
 192                 case 6:         HASHC;
 193                 case 5:         HASHC;
 194                 case 4:         HASHC;
 195                 case 3:         HASHC;
 196                 case 2:         HASHC;
 197                 case 1:         HASHC;
 198                         } while (--loop);
 199                 }
 200         }
 201 #endif /* ! VAXC */
 202
 203         if (h >= hsize)
 204                 h %= hsize;
 205         return h;
 206 }
 207
 208 /* assoc_find --- locate symbol[subs] */
 209
 210 static NODE *                           /* NULL if not found */
 211 assoc_find(symbol, subs, hash1)
 212 NODE *symbol;
 213 register NODE *subs;
 214 int hash1;
 215 {
 216         register NODE *bucket;
 217
 218         for (bucket = symbol->var_array[hash1]; bucket != NULL;
 219                         bucket = bucket->ahnext) {
 220                 if (cmp_nodes(bucket->ahname, subs) == 0)
 221                         return bucket;
 222         }
 223         return NULL;
 224 }
 225
 226 /* in_array --- test whether the array element symbol[subs] exists or not */
 227
 228 int
 229 in_array(symbol, subs)
 230 NODE *symbol, *subs;
 231 {
 232         register int hash1;
 233         int ret;
 234
 235         if (symbol->type == Node_param_list)
 236                 symbol = stack_ptr[symbol->param_cnt];
 237         if ((symbol->flags & SCALAR) != 0)
 238                 fatal("attempt to use scalar as array");
 239         /*
 240          * evaluate subscript first, it could have side effects
 241          */
 242         subs = concat_exp(subs);        /* concat_exp returns a string node */
 243         if (symbol->var_array == NULL) {
 244                 free_temp(subs);
 245                 return 0;
 246         }
 247         hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
 248         ret = (assoc_find(symbol, subs, hash1) != NULL);
 249         free_temp(subs);
 250         return ret;
 251 }
 252
 253 /*
 254  * assoc_lookup:
 255  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
 256  * isn't there. Returns a pointer ala get_lhs to where its value is stored.
 257  *
 258  * SYMBOL is the address of the node (or other pointer) being dereferenced.
 259  * SUBS is a number or string used as the subscript.
 260  */
 261
 262 NODE **
 263 assoc_lookup(symbol, subs)
 264 NODE *symbol, *subs;
 265 {
 266         register int hash1;
 267         register NODE *bucket;
 268
 269         (void) force_string(subs);
 270
 271         if ((symbol->flags & SCALAR) != 0)
 272                 fatal("attempt to use scalar as array");
 273
 274         if (symbol->var_array == NULL) {
 275                 if (symbol->type != Node_var_array) {
 276                         unref(symbol->var_value);
 277                         symbol->type = Node_var_array;
 278                 }
 279                 symbol->array_size = symbol->table_size = 0;    /* sanity */
 280                 symbol->flags &= ~ARRAYMAXED;
 281                 grow_table(symbol);
 282                 hash1 = hash(subs->stptr, subs->stlen,
 283                                 (unsigned long) symbol->array_size);
 284         } else {
 285                 hash1 = hash(subs->stptr, subs->stlen,
 286                                 (unsigned long) symbol->array_size);
 287                 bucket = assoc_find(symbol, subs, hash1);
 288                 if (bucket != NULL) {
 289                         free_temp(subs);
 290                         return &(bucket->ahvalue);
 291                 }
 292         }
 293
 294         /* It's not there, install it. */
 295         if (do_lint && subs->stlen == 0)
 296                 warning("subscript of array `%s' is null string",
 297                         symbol->vname);
 298
 299         /* first see if we would need to grow the array, before installing */
 300         symbol->table_size++;
 301         if ((symbol->flags & ARRAYMAXED) == 0
 302             && symbol->table_size/symbol->array_size > AVG_CHAIN_MAX) {
 303                 grow_table(symbol);
 304                 /* have to recompute hash value for new size */
 305                 hash1 = hash(subs->stptr, subs->stlen,
 306                                 (unsigned long) symbol->array_size);
 307         }
 308
 309         getnode(bucket);
 310         bucket->type = Node_ahash;
 311         if (subs->flags & TEMP)
 312                 bucket->ahname = dupnode(subs);
 313         else {
 314                 unsigned int saveflags = subs->flags;
 315
 316                 subs->flags &= ~MALLOC;
 317                 bucket->ahname = dupnode(subs);
 318                 subs->flags = saveflags;
 319         }
 320         free_temp(subs);
 321
 322         /* array subscripts are strings */
 323         bucket->ahname->flags &= ~NUMBER;
 324         bucket->ahname->flags |= STRING;
 325         bucket->ahvalue = Nnull_string;
 326         bucket->ahnext = symbol->var_array[hash1];
 327         symbol->var_array[hash1] = bucket;
 328         return &(bucket->ahvalue);
 329 }
 330
 331 /* do_delete --- perform `delete array[s]' */
 332
 333 void
 334 do_delete(symbol, tree)
 335 NODE *symbol, *tree;
 336 {
 337         register int hash1;
 338         register NODE *bucket, *last;
 339         NODE *subs;
 340
 341         if (symbol->type == Node_param_list) {
 342                 symbol = stack_ptr[symbol->param_cnt];
 343                 if (symbol->type == Node_var)
 344                         return;
 345         }
 346         if (symbol->type == Node_var_array) {
 347                 if (symbol->var_array == NULL)
 348                         return;
 349         } else
 350                 fatal("delete: illegal use of variable `%s' as array",
 351                         symbol->vname);
 352
 353         if (tree == NULL) {     /* delete array */
 354                 assoc_clear(symbol);
 355                 return;
 356         }
 357
 358         subs = concat_exp(tree);        /* concat_exp returns string node */
 359         hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
 360
 361         last = NULL;
 362         for (bucket = symbol->var_array[hash1]; bucket != NULL;
 363                         last = bucket, bucket = bucket->ahnext)
 364                 if (cmp_nodes(bucket->ahname, subs) == 0)
 365                         break;
 366         if (bucket == NULL) {
 367                 if (do_lint)
 368                         warning("delete: index `%s' not in array `%s'",
 369                                 subs->stptr, symbol->vname);
 370                 free_temp(subs);
 371                 return;
 372         }
 373         free_temp(subs);
 374         if (last != NULL)
 375                 last->ahnext = bucket->ahnext;
 376         else
 377                 symbol->var_array[hash1] = bucket->ahnext;
 378         unref(bucket->ahname);
 379         unref(bucket->ahvalue);
 380         freenode(bucket);
 381         symbol->table_size--;
 382         if (symbol->table_size <= 0) {
 383                 memset(symbol->var_array, '\0',
 384                         sizeof(NODE *) * symbol->array_size);
 385                 symbol->table_size = symbol->array_size = 0;
 386                 symbol->flags &= ~ARRAYMAXED;
 387                 free((char *) symbol->var_array);
 388                 symbol->var_array = NULL;
 389         }
 390 }
 391
 392 /* assoc_scan --- start a ``for (iggy in foo)'' loop */
 393
 394 void
 395 assoc_scan(symbol, lookat)
 396 NODE *symbol;
 397 struct search *lookat;
 398 {
 399         lookat->sym = symbol;
 400         lookat->idx = 0;
 401         lookat->bucket = NULL;
 402         lookat->retval = NULL;
 403         if (symbol->var_array != NULL)
 404                 assoc_next(lookat);
 405 }
 406
 407 /* assoc_next --- actually find the next element in array */
 408
 409 void
 410 assoc_next(lookat)
 411 struct search *lookat;
 412 {
 413         register NODE *symbol = lookat->sym;
 414
 415         if (symbol == NULL)
 416                 fatal("null symbol in assoc_next");
 417         if (symbol->var_array == NULL || lookat->idx > symbol->array_size) {
 418                 lookat->retval = NULL;
 419                 return;
 420         }
 421         /*
 422          * This is theoretically unsafe.  The element bucket might have
 423          * been freed if the body of the scan did a delete on the next
 424          * element of the bucket.  The only way to do that is by array
 425          * reference, which is unlikely.  Basically, if the user is doing
 426          * anything other than an operation on the current element of an
 427          * assoc array while walking through it sequentially, all bets are
 428          * off.  (The safe way is to register all search structs on an
 429          * array with the array, and update all of them on a delete or
 430          * insert)
 431          */
 432         if (lookat->bucket != NULL) {
 433                 lookat->retval = lookat->bucket->ahname;
 434                 lookat->bucket = lookat->bucket->ahnext;
 435                 return;
 436         }
 437         for (; lookat->idx < symbol->array_size; lookat->idx++) {
 438                 NODE *bucket;
 439
 440                 if ((bucket = symbol->var_array[lookat->idx]) != NULL) {
 441                         lookat->retval = bucket->ahname;
 442                         lookat->bucket = bucket->ahnext;
 443                         lookat->idx++;
 444                         return;
 445                 }
 446         }
 447         lookat->retval = NULL;
 448         lookat->bucket = NULL;
 449         return;
 450 }
 451
 452 /* grow_table --- grow a hash table */
 453
 454 static void
 455 grow_table(symbol)
 456 NODE *symbol;
 457 {
 458         NODE **old, **new, *chain, *next;
 459         int i, j;
 460         unsigned long hash1;
 461         unsigned long oldsize, newsize;
 462         /*
 463          * This is an array of primes. We grow the table by an order of
 464          * magnitude each time (not just doubling) so that growing is a
 465          * rare operation. We expect, on average, that it won't happen
 466          * more than twice.  The final size is also chosen to be small
 467          * enough so that MS-DOG mallocs can handle it. When things are
 468          * very large (> 8K), we just double more or less, instead of
 469          * just jumping from 8K to 64K.
 470          */
 471         static long sizes[] = { 13, 127, 1021, 8191, 16381, 32749, 65497,
 472 #if ! defined(MSDOS) && ! defined(OS2) && ! defined(atarist)
 473                                 131101, 262147, 524309, 1048583, 2097169,
 474                                 4194319, 8388617, 16777259, 33554467,
 475                                 67108879, 134217757, 268435459, 536870923,
 476                                 1073741827
 477 #endif
 478         };
 479
 480         /* find next biggest hash size */
 481         newsize = oldsize = symbol->array_size;
 482         for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
 483                 if (oldsize < sizes[i]) {
 484                         newsize = sizes[i];
 485                         break;
 486                 }
 487         }
 488
 489         if (newsize == oldsize) {       /* table already at max (!) */
 490                 symbol->flags |= ARRAYMAXED;
 491                 return;
 492         }
 493
 494         /* allocate new table */
 495         emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
 496         memset(new, '\0', newsize * sizeof(NODE *));
 497
 498         /* brand new hash table, set things up and return */
 499         if (symbol->var_array == NULL) {
 500                 symbol->table_size = 0;
 501                 goto done;
 502         }
 503
 504         /* old hash table there, move stuff to new, free old */
 505         old = symbol->var_array;
 506         for (i = 0; i < oldsize; i++) {
 507                 if (old[i] == NULL)
 508                         continue;
 509
 510                 for (chain = old[i]; chain != NULL; chain = next) {
 511                         next = chain->ahnext;
 512                         hash1 = hash(chain->ahname->stptr,
 513                                         chain->ahname->stlen, newsize);
 514
 515                         /* remove from old list, add to new */
 516                         chain->ahnext = new[hash1];
 517                         new[hash1] = chain;
 518
 519                 }
 520         }
 521         free(old);
 522
 523 done:
 524         /*
 525          * note that symbol->table_size does not change if an old array,
 526          * and is explicitly set to 0 if a new one.
 527          */
 528         symbol->var_array = new;
 529         symbol->array_size = newsize;
 530 }