contrib/awk/array.c

   1 /*
   2  * array.c - routines for associative arrays.
   3  */
   4
   5 /*
   6  * Copyright (C) 1986, 1988, 1989, 1991-2000 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->var_value->stlen;
  65         subsep = SUBSEP_node->var_value->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         NODE *s1, *s2;
 218
 219         for (bucket = symbol->var_array[hash1]; bucket != NULL;
 220                         bucket = bucket->ahnext) {
 221                 /*
 222                  * This used to use cmp_nodes() here.  That's wrong.
 223                  * Array indexes are strings; compare as such, always!
 224                  */
 225                 s1 = bucket->ahname;
 226                 s1 = force_string(s1);
 227                 s2 = subs;
 228
 229                 if (s1->stlen == s2->stlen) {
 230                         if (s1->stlen == 0      /* "" is a valid index */
 231                             || STREQN(s1->stptr, s2->stptr, s1->stlen))
 232                                 return bucket;
 233                 }
 234         }
 235         return NULL;
 236 }
 237
 238 /* in_array --- test whether the array element symbol[subs] exists or not */
 239
 240 int
 241 in_array(symbol, subs)
 242 NODE *symbol, *subs;
 243 {
 244         register int hash1;
 245         int ret;
 246
 247         if (symbol->type == Node_param_list)
 248                 symbol = stack_ptr[symbol->param_cnt];
 249         if (symbol->type == Node_array_ref)
 250                 symbol = symbol->orig_array;
 251         if ((symbol->flags & SCALAR) != 0)
 252                 fatal("attempt to use scalar as array");
 253         /*
 254          * evaluate subscript first, it could have side effects
 255          */
 256         subs = concat_exp(subs);        /* concat_exp returns a string node */
 257         if (symbol->var_array == NULL) {
 258                 free_temp(subs);
 259                 return 0;
 260         }
 261         hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
 262         ret = (assoc_find(symbol, subs, hash1) != NULL);
 263         free_temp(subs);
 264         return ret;
 265 }
 266
 267 /*
 268  * assoc_lookup:
 269  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
 270  * isn't there. Returns a pointer ala get_lhs to where its value is stored.
 271  *
 272  * SYMBOL is the address of the node (or other pointer) being dereferenced.
 273  * SUBS is a number or string used as the subscript.
 274  */
 275
 276 NODE **
 277 assoc_lookup(symbol, subs)
 278 NODE *symbol, *subs;
 279 {
 280         register int hash1;
 281         register NODE *bucket;
 282
 283         assert(symbol->type == Node_var_array || symbol->type == Node_var);
 284
 285         (void) force_string(subs);
 286
 287         if ((symbol->flags & SCALAR) != 0)
 288                 fatal("attempt to use scalar as array");
 289
 290         if (symbol->var_array == NULL) {
 291                 if (symbol->type != Node_var_array) {
 292                         unref(symbol->var_value);
 293                         symbol->type = Node_var_array;
 294                 }
 295                 symbol->array_size = symbol->table_size = 0;    /* sanity */
 296                 symbol->flags &= ~ARRAYMAXED;
 297                 grow_table(symbol);
 298                 hash1 = hash(subs->stptr, subs->stlen,
 299                                 (unsigned long) symbol->array_size);
 300         } else {
 301                 hash1 = hash(subs->stptr, subs->stlen,
 302                                 (unsigned long) symbol->array_size);
 303                 bucket = assoc_find(symbol, subs, hash1);
 304                 if (bucket != NULL) {
 305                         free_temp(subs);
 306                         return &(bucket->ahvalue);
 307                 }
 308         }
 309
 310         /* It's not there, install it. */
 311         if (do_lint && subs->stlen == 0)
 312                 warning("subscript of array `%s' is null string",
 313                         symbol->vname);
 314
 315         /* first see if we would need to grow the array, before installing */
 316         symbol->table_size++;
 317         if ((symbol->flags & ARRAYMAXED) == 0
 318             && symbol->table_size/symbol->array_size > AVG_CHAIN_MAX) {
 319                 grow_table(symbol);
 320                 /* have to recompute hash value for new size */
 321                 hash1 = hash(subs->stptr, subs->stlen,
 322                                 (unsigned long) symbol->array_size);
 323         }
 324
 325         getnode(bucket);
 326         bucket->type = Node_ahash;
 327         bucket->ahname = dupnode(subs);
 328         free_temp(subs);
 329
 330         bucket->ahvalue = Nnull_string;
 331         bucket->ahnext = symbol->var_array[hash1];
 332         symbol->var_array[hash1] = bucket;
 333         return &(bucket->ahvalue);
 334 }
 335
 336 /* do_delete --- perform `delete array[s]' */
 337
 338 void
 339 do_delete(symbol, tree)
 340 NODE *symbol, *tree;
 341 {
 342         register int hash1;
 343         register NODE *bucket, *last;
 344         NODE *subs;
 345
 346         if (symbol->type == Node_param_list) {
 347                 symbol = stack_ptr[symbol->param_cnt];
 348                 if (symbol->type == Node_var)
 349                         return;
 350         }
 351         if (symbol->type == Node_array_ref)
 352                 symbol = symbol->orig_array;
 353         if (symbol->type == Node_var_array) {
 354                 if (symbol->var_array == NULL)
 355                         return;
 356         } else
 357                 fatal("delete: illegal use of variable `%s' as array",
 358                         symbol->vname);
 359
 360         if (tree == NULL) {     /* delete array */
 361                 assoc_clear(symbol);
 362                 return;
 363         }
 364
 365         subs = concat_exp(tree);        /* concat_exp returns string node */
 366         hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
 367
 368         last = NULL;
 369         for (bucket = symbol->var_array[hash1]; bucket != NULL;
 370                         last = bucket, bucket = bucket->ahnext) {
 371                 /*
 372                  * This used to use cmp_nodes() here.  That's wrong.
 373                  * Array indexes are strings; compare as such, always!
 374                  */
 375                 NODE *s1, *s2;
 376
 377                 s1 = bucket->ahname;
 378                 s1 = force_string(s1);
 379                 s2 = subs;
 380
 381                 if (s1->stlen == s2->stlen) {
 382                         if (s1->stlen == 0      /* "" is a valid index */
 383                             || STREQN(s1->stptr, s2->stptr, s1->stlen))
 384                                 break;
 385                 }
 386         }
 387
 388         if (bucket == NULL) {
 389                 if (do_lint)
 390                         warning("delete: index `%s' not in array `%s'",
 391                                 subs->stptr, symbol->vname);
 392                 free_temp(subs);
 393                 return;
 394         }
 395         free_temp(subs);
 396         if (last != NULL)
 397                 last->ahnext = bucket->ahnext;
 398         else
 399                 symbol->var_array[hash1] = bucket->ahnext;
 400         unref(bucket->ahname);
 401         unref(bucket->ahvalue);
 402         freenode(bucket);
 403         symbol->table_size--;
 404         if (symbol->table_size <= 0) {
 405                 memset(symbol->var_array, '\0',
 406                         sizeof(NODE *) * symbol->array_size);
 407                 symbol->table_size = symbol->array_size = 0;
 408                 symbol->flags &= ~ARRAYMAXED;
 409                 free((char *) symbol->var_array);
 410                 symbol->var_array = NULL;
 411         }
 412 }
 413
 414 /* do_delete_loop --- simulate ``for (iggy in foo) delete foo[iggy]'' */
 415
 416 /*
 417  * The primary hassle here is that `iggy' needs to have some arbitrary
 418  * array index put in it before we can clear the array, we can't
 419  * just replace the loop with `delete foo'.
 420  */
 421
 422 void
 423 do_delete_loop(symbol, tree)
 424 NODE *symbol, *tree;
 425 {
 426         size_t i;
 427         NODE *n, **lhs;
 428         Func_ptr after_assign = NULL;
 429
 430         if (symbol->type == Node_param_list) {
 431                 symbol = stack_ptr[symbol->param_cnt];
 432                 if (symbol->type == Node_var)
 433                         return;
 434         }
 435         if (symbol->type == Node_array_ref)
 436                 symbol = symbol->orig_array;
 437         if (symbol->type == Node_var_array) {
 438                 if (symbol->var_array == NULL)
 439                         return;
 440         } else
 441                 fatal("delete: illegal use of variable `%s' as array",
 442                         symbol->vname);
 443
 444         /* get first index value */
 445         for (i = 0; i < symbol->array_size; i++) {
 446                 if (symbol->var_array[i] != NULL) {
 447                         lhs = get_lhs(tree->lnode, & after_assign);
 448                         unref(*lhs);
 449                         *lhs = dupnode(symbol->var_array[i]->ahname);
 450                         break;
 451                 }
 452         }
 453
 454         /* blast the array in one shot */
 455         assoc_clear(symbol);
 456 }
 457
 458 /* assoc_scan --- start a ``for (iggy in foo)'' loop */
 459
 460 void
 461 assoc_scan(symbol, lookat)
 462 NODE *symbol;
 463 struct search *lookat;
 464 {
 465         lookat->sym = symbol;
 466         lookat->idx = 0;
 467         lookat->bucket = NULL;
 468         lookat->retval = NULL;
 469         if (symbol->var_array != NULL)
 470                 assoc_next(lookat);
 471 }
 472
 473 /* assoc_next --- actually find the next element in array */
 474
 475 void
 476 assoc_next(lookat)
 477 struct search *lookat;
 478 {
 479         register NODE *symbol = lookat->sym;
 480
 481         if (symbol == NULL)
 482                 fatal("null symbol in assoc_next");
 483         if (symbol->var_array == NULL || lookat->idx > symbol->array_size) {
 484                 lookat->retval = NULL;
 485                 return;
 486         }
 487         /*
 488          * This is theoretically unsafe.  The element bucket might have
 489          * been freed if the body of the scan did a delete on the next
 490          * element of the bucket.  The only way to do that is by array
 491          * reference, which is unlikely.  Basically, if the user is doing
 492          * anything other than an operation on the current element of an
 493          * assoc array while walking through it sequentially, all bets are
 494          * off.  (The safe way is to register all search structs on an
 495          * array with the array, and update all of them on a delete or
 496          * insert)
 497          */
 498         if (lookat->bucket != NULL) {
 499                 lookat->retval = lookat->bucket->ahname;
 500                 lookat->bucket = lookat->bucket->ahnext;
 501                 return;
 502         }
 503         for (; lookat->idx < symbol->array_size; lookat->idx++) {
 504                 NODE *bucket;
 505
 506                 if ((bucket = symbol->var_array[lookat->idx]) != NULL) {
 507                         lookat->retval = bucket->ahname;
 508                         lookat->bucket = bucket->ahnext;
 509                         lookat->idx++;
 510                         return;
 511                 }
 512         }
 513         lookat->retval = NULL;
 514         lookat->bucket = NULL;
 515         return;
 516 }
 517
 518 /* grow_table --- grow a hash table */
 519
 520 static void
 521 grow_table(symbol)
 522 NODE *symbol;
 523 {
 524         NODE **old, **new, *chain, *next;
 525         int i, j;
 526         unsigned long hash1;
 527         unsigned long oldsize, newsize;
 528         /*
 529          * This is an array of primes. We grow the table by an order of
 530          * magnitude each time (not just doubling) so that growing is a
 531          * rare operation. We expect, on average, that it won't happen
 532          * more than twice.  The final size is also chosen to be small
 533          * enough so that MS-DOG mallocs can handle it. When things are
 534          * very large (> 8K), we just double more or less, instead of
 535          * just jumping from 8K to 64K.
 536          */
 537         static long sizes[] = { 13, 127, 1021, 8191, 16381, 32749, 65497,
 538 #if ! defined(MSDOS) && ! defined(OS2) && ! defined(atarist)
 539                                 131101, 262147, 524309, 1048583, 2097169,
 540                                 4194319, 8388617, 16777259, 33554467,
 541                                 67108879, 134217757, 268435459, 536870923,
 542                                 1073741827
 543 #endif
 544         };
 545
 546         /* find next biggest hash size */
 547         newsize = oldsize = symbol->array_size;
 548         for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
 549                 if (oldsize < sizes[i]) {
 550                         newsize = sizes[i];
 551                         break;
 552                 }
 553         }
 554
 555         if (newsize == oldsize) {       /* table already at max (!) */
 556                 symbol->flags |= ARRAYMAXED;
 557                 return;
 558         }
 559
 560         /* allocate new table */
 561         emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
 562         memset(new, '\0', newsize * sizeof(NODE *));
 563
 564         /* brand new hash table, set things up and return */
 565         if (symbol->var_array == NULL) {
 566                 symbol->table_size = 0;
 567                 goto done;
 568         }
 569
 570         /* old hash table there, move stuff to new, free old */
 571         old = symbol->var_array;
 572         for (i = 0; i < oldsize; i++) {
 573                 if (old[i] == NULL)
 574                         continue;
 575
 576                 for (chain = old[i]; chain != NULL; chain = next) {
 577                         next = chain->ahnext;
 578                         hash1 = hash(chain->ahname->stptr,
 579                                         chain->ahname->stlen, newsize);
 580
 581                         /* remove from old list, add to new */
 582                         chain->ahnext = new[hash1];
 583                         new[hash1] = chain;
 584
 585                 }
 586         }
 587         free(old);
 588
 589 done:
 590         /*
 591          * note that symbol->table_size does not change if an old array,
 592          * and is explicitly set to 0 if a new one.
 593          */
 594         symbol->var_array = new;
 595         symbol->array_size = newsize;
 596 }
 597
 598 /* pr_node --- print simple node info */
 599
 600 static void
 601 pr_node(n)
 602 NODE *n;
 603 {
 604         if ((n->flags & (NUM|NUMBER)) != 0)
 605                 printf("%g", n->numbr);
 606         else
 607                 printf("%.*s", (int) n->stlen, n->stptr);
 608 }
 609
 610 /* assoc_dump --- dump the contents of an array */
 611
 612 NODE *
 613 assoc_dump(symbol)
 614 NODE *symbol;
 615 {
 616         int i;
 617         NODE *bucket;
 618
 619         if (symbol->var_array == NULL) {
 620                 printf("%s: empty (null)\n", symbol->vname);
 621                 return tmp_number((AWKNUM) 0);
 622         }
 623
 624         if (symbol->table_size == 0) {
 625                 printf("%s: empty (zero)\n", symbol->vname);
 626                 return tmp_number((AWKNUM) 0);
 627         }
 628
 629         printf("%s: table_size = %d, array_size = %d\n", symbol->vname,
 630                         symbol->table_size, symbol->array_size);
 631
 632         for (i = 0; i < symbol->array_size; i++) {
 633                 for (bucket = symbol->var_array[i]; bucket != NULL;
 634                                 bucket = bucket->ahnext) {
 635                         printf("%s: I: [(%p, %ld, %s) len %d <%.*s>] V: [",
 636                                 symbol->vname,
 637                                 bucket->ahname,
 638                                 bucket->ahname->stref,
 639                                 flags2str(bucket->ahname->flags),
 640                                 (int) bucket->ahname->stlen,
 641                                 (int) bucket->ahname->stlen,
 642                                 bucket->ahname->stptr);
 643                         pr_node(bucket->ahvalue);
 644                         printf("]\n");
 645                 }
 646         }
 647
 648         return tmp_number((AWKNUM) 0);
 649 }
 650
 651 /* do_adump --- dump an array: interface to assoc_dump */
 652
 653 NODE *
 654 do_adump(tree)
 655 NODE *tree;
 656 {
 657         NODE *r, *a;
 658
 659         a = tree->lnode;
 660
 661         if (a->type == Node_param_list) {
 662                 printf("%s: is paramater\n", a->vname);
 663                 a = stack_ptr[a->param_cnt];
 664         }
 665
 666         if (a->type == Node_array_ref) {
 667                 printf("%s: array_ref to %s\n", a->vname,
 668                                         a->orig_array->vname);
 669                 a = a->orig_array;
 670         }
 671
 672         r = assoc_dump(a);
 673
 674         return r;
 675 }