2 * array.c - routines for associative arrays.
6 * Copyright (C) 1986, 1988, 1989, 1991-2000 the Free Software Foundation, Inc.
8 * This file is part of GAWK, the GNU implementation of the
9 * AWK Programming Language.
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.
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.
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
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
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.
38 #define AVG_CHAIN_MAX 10 /* don't want to linear search more than this */
42 static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
43 static void grow_table P((NODE *symbol));
45 /* concat_exp --- concatenate expression list into a single string */
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)
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);
71 for (tree = tree->rnode; tree != NULL; tree = tree->rnode) {
75 memcpy(s, subsep, subseplen+1);
78 r = force_string(tree_eval(tree->lnode));
79 len += r->stlen + subseplen;
81 erealloc(str, char *, len, "concat_exp");
83 memcpy(s, r->stptr, r->stlen+1);
87 r = make_str_node(str, s - str, ALREADY_MALLOCED);
92 /* assoc_clear --- flush all the values in symbol[] before doing a split() */
101 if (symbol->var_array == NULL)
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);
110 symbol->var_array[i] = NULL;
112 free(symbol->var_array);
113 symbol->var_array = NULL;
114 symbol->array_size = symbol->table_size = 0;
115 symbol->flags &= ~ARRAYMAXED;
118 /* hash --- calculate the hash function of the string in subs */
122 register const char *s;
126 register unsigned long h = 0;
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.
136 * OZ's original sdbm hash, copied from Margo Seltzers db package.
141 * #define HASHC h = *s++ + 65599 * h
142 * Because 65599 = pow(2, 6) + pow(2, 16) - 1 we multiply by shifts
144 #define HASHC htmp = (h << 6); \
145 h = *s++ + htmp + (htmp << 10) - h
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
158 switch (len & (8 - 1)) {
170 register size_t loop = len >> 3;
183 /* "Duff's Device" for those who can handle it */
185 register size_t loop = (len + 8 - 1) >> 3;
187 switch (len & (8 - 1)) {
189 do { /* All fall throughs */
208 /* assoc_find --- locate symbol[subs] */
210 static NODE * /* NULL if not found */
211 assoc_find(symbol, subs, hash1)
216 register NODE *bucket;
219 for (bucket = symbol->var_array[hash1]; bucket != NULL;
220 bucket = bucket->ahnext) {
222 * This used to use cmp_nodes() here. That's wrong.
223 * Array indexes are strings; compare as such, always!
226 s1 = force_string(s1);
229 if (s1->stlen == s2->stlen) {
230 if (s1->stlen == 0 /* "" is a valid index */
231 || STREQN(s1->stptr, s2->stptr, s1->stlen))
238 /* in_array --- test whether the array element symbol[subs] exists or not */
241 in_array(symbol, subs)
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");
254 * evaluate subscript first, it could have side effects
256 subs = concat_exp(subs); /* concat_exp returns a string node */
257 if (symbol->var_array == NULL) {
261 hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
262 ret = (assoc_find(symbol, subs, hash1) != NULL);
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.
272 * SYMBOL is the address of the node (or other pointer) being dereferenced.
273 * SUBS is a number or string used as the subscript.
277 assoc_lookup(symbol, subs)
281 register NODE *bucket;
283 assert(symbol->type == Node_var_array || symbol->type == Node_var);
285 (void) force_string(subs);
287 if ((symbol->flags & SCALAR) != 0)
288 fatal("attempt to use scalar as array");
290 if (symbol->var_array == NULL) {
291 if (symbol->type != Node_var_array) {
292 unref(symbol->var_value);
293 symbol->type = Node_var_array;
295 symbol->array_size = symbol->table_size = 0; /* sanity */
296 symbol->flags &= ~ARRAYMAXED;
298 hash1 = hash(subs->stptr, subs->stlen,
299 (unsigned long) symbol->array_size);
301 hash1 = hash(subs->stptr, subs->stlen,
302 (unsigned long) symbol->array_size);
303 bucket = assoc_find(symbol, subs, hash1);
304 if (bucket != NULL) {
306 return &(bucket->ahvalue);
310 /* It's not there, install it. */
311 if (do_lint && subs->stlen == 0)
312 warning("subscript of array `%s' is null string",
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) {
320 /* have to recompute hash value for new size */
321 hash1 = hash(subs->stptr, subs->stlen,
322 (unsigned long) symbol->array_size);
326 bucket->type = Node_ahash;
327 bucket->ahname = dupnode(subs);
330 bucket->ahvalue = Nnull_string;
331 bucket->ahnext = symbol->var_array[hash1];
332 symbol->var_array[hash1] = bucket;
333 return &(bucket->ahvalue);
336 /* do_delete --- perform `delete array[s]' */
339 do_delete(symbol, tree)
343 register NODE *bucket, *last;
346 if (symbol->type == Node_param_list) {
347 symbol = stack_ptr[symbol->param_cnt];
348 if (symbol->type == Node_var)
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)
357 fatal("delete: illegal use of variable `%s' as array",
360 if (tree == NULL) { /* delete array */
365 subs = concat_exp(tree); /* concat_exp returns string node */
366 hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
369 for (bucket = symbol->var_array[hash1]; bucket != NULL;
370 last = bucket, bucket = bucket->ahnext) {
372 * This used to use cmp_nodes() here. That's wrong.
373 * Array indexes are strings; compare as such, always!
378 s1 = force_string(s1);
381 if (s1->stlen == s2->stlen) {
382 if (s1->stlen == 0 /* "" is a valid index */
383 || STREQN(s1->stptr, s2->stptr, s1->stlen))
388 if (bucket == NULL) {
390 warning("delete: index `%s' not in array `%s'",
391 subs->stptr, symbol->vname);
397 last->ahnext = bucket->ahnext;
399 symbol->var_array[hash1] = bucket->ahnext;
400 unref(bucket->ahname);
401 unref(bucket->ahvalue);
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;
414 /* do_delete_loop --- simulate ``for (iggy in foo) delete foo[iggy]'' */
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'.
423 do_delete_loop(symbol, tree)
428 Func_ptr after_assign = NULL;
430 if (symbol->type == Node_param_list) {
431 symbol = stack_ptr[symbol->param_cnt];
432 if (symbol->type == Node_var)
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)
441 fatal("delete: illegal use of variable `%s' as array",
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);
449 *lhs = dupnode(symbol->var_array[i]->ahname);
454 /* blast the array in one shot */
458 /* assoc_scan --- start a ``for (iggy in foo)'' loop */
461 assoc_scan(symbol, lookat)
463 struct search *lookat;
465 lookat->sym = symbol;
467 lookat->bucket = NULL;
468 lookat->retval = NULL;
469 if (symbol->var_array != NULL)
473 /* assoc_next --- actually find the next element in array */
477 struct search *lookat;
479 register NODE *symbol = lookat->sym;
482 fatal("null symbol in assoc_next");
483 if (symbol->var_array == NULL || lookat->idx > symbol->array_size) {
484 lookat->retval = NULL;
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
498 if (lookat->bucket != NULL) {
499 lookat->retval = lookat->bucket->ahname;
500 lookat->bucket = lookat->bucket->ahnext;
503 for (; lookat->idx < symbol->array_size; lookat->idx++) {
506 if ((bucket = symbol->var_array[lookat->idx]) != NULL) {
507 lookat->retval = bucket->ahname;
508 lookat->bucket = bucket->ahnext;
513 lookat->retval = NULL;
514 lookat->bucket = NULL;
518 /* grow_table --- grow a hash table */
524 NODE **old, **new, *chain, *next;
527 unsigned long oldsize, newsize;
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.
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,
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]) {
555 if (newsize == oldsize) { /* table already at max (!) */
556 symbol->flags |= ARRAYMAXED;
560 /* allocate new table */
561 emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
562 memset(new, '\0', newsize * sizeof(NODE *));
564 /* brand new hash table, set things up and return */
565 if (symbol->var_array == NULL) {
566 symbol->table_size = 0;
570 /* old hash table there, move stuff to new, free old */
571 old = symbol->var_array;
572 for (i = 0; i < oldsize; i++) {
576 for (chain = old[i]; chain != NULL; chain = next) {
577 next = chain->ahnext;
578 hash1 = hash(chain->ahname->stptr,
579 chain->ahname->stlen, newsize);
581 /* remove from old list, add to new */
582 chain->ahnext = new[hash1];
591 * note that symbol->table_size does not change if an old array,
592 * and is explicitly set to 0 if a new one.
594 symbol->var_array = new;
595 symbol->array_size = newsize;
598 /* pr_node --- print simple node info */
604 if ((n->flags & (NUM|NUMBER)) != 0)
605 printf("%g", n->numbr);
607 printf("%.*s", (int) n->stlen, n->stptr);
610 /* assoc_dump --- dump the contents of an array */
619 if (symbol->var_array == NULL) {
620 printf("%s: empty (null)\n", symbol->vname);
621 return tmp_number((AWKNUM) 0);
624 if (symbol->table_size == 0) {
625 printf("%s: empty (zero)\n", symbol->vname);
626 return tmp_number((AWKNUM) 0);
629 printf("%s: table_size = %d, array_size = %d\n", symbol->vname,
630 symbol->table_size, symbol->array_size);
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: [",
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);
648 return tmp_number((AWKNUM) 0);
651 /* do_adump --- dump an array: interface to assoc_dump */
661 if (a->type == Node_param_list) {
662 printf("%s: is paramater\n", a->vname);
663 a = stack_ptr[a->param_cnt];
666 if (a->type == Node_array_ref) {
667 printf("%s: array_ref to %s\n", a->vname,
668 a->orig_array->vname);