home *** CD-ROM | disk | FTP | other *** search
/ Acorn User 11 / AUCD11B.iso / LANGUAGES / WraithSet / AwkStuff / GawkSrc / c / array < prev    next >
Encoding:
Text File  |  1999-05-03  |  13.2 KB  |  531 lines
  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. }
  531.