home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / gnu / gawk-2.15.5-src.lha / gawk-2.15.5 / array.c < prev    next >
C/C++ Source or Header  |  1994-04-17  |  13KB  |  516 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989, 1991, 1992, 1993 the Free Software Foundation, Inc.
  7.  * 
  8.  * This file is part of GAWK, the GNU implementation of the
  9.  * AWK Progamming 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 GAWK; see the file COPYING.  If not, write to
  23.  * the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, 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. NODE *
  46. concat_exp(tree)
  47. register NODE *tree;
  48. {
  49.     register NODE *r;
  50.     char *str;
  51.     char *s;
  52.     size_t len;
  53.     int offset;
  54.     size_t subseplen;
  55.     char *subsep;
  56.  
  57.     if (tree->type != Node_expression_list)
  58.         return force_string(tree_eval(tree));
  59.     r = force_string(tree_eval(tree->lnode));
  60.     if (tree->rnode == NULL)
  61.         return r;
  62.     subseplen = SUBSEP_node->lnode->stlen;
  63.     subsep = SUBSEP_node->lnode->stptr;
  64.     len = r->stlen + subseplen + 2;
  65.     emalloc(str, char *, len, "concat_exp");
  66.     memcpy(str, r->stptr, r->stlen+1);
  67.     s = str + r->stlen;
  68.     free_temp(r);
  69.     tree = tree->rnode;
  70.     while (tree) {
  71.         if (subseplen == 1)
  72.             *s++ = *subsep;
  73.         else {
  74.             memcpy(s, subsep, subseplen+1);
  75.             s += subseplen;
  76.         }
  77.         r = force_string(tree_eval(tree->lnode));
  78.         len += r->stlen + subseplen;
  79.         offset = s - str;
  80.         erealloc(str, char *, len, "concat_exp");
  81.         s = str + offset;
  82.         memcpy(s, r->stptr, r->stlen+1);
  83.         s += r->stlen;
  84.         free_temp(r);
  85.         tree = tree->rnode;
  86.     }
  87.     r = make_str_node(str, s - str, ALREADY_MALLOCED);
  88.     r->flags |= TEMP;
  89.     return r;
  90. }
  91.  
  92. /* Flush all the values in symbol[] before doing a split() */
  93. void
  94. assoc_clear(symbol)
  95. NODE *symbol;
  96. {
  97.     int i;
  98.     NODE *bucket, *next;
  99.  
  100.     if (symbol->var_array == 0)
  101.         return;
  102.     for (i = 0; i < symbol->array_size; i++) {
  103.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  104.             next = bucket->ahnext;
  105.             unref(bucket->ahname);
  106.             unref(bucket->ahvalue);
  107.             freenode(bucket);
  108.         }
  109.         symbol->var_array[i] = 0;
  110.     }
  111.     free(symbol->var_array);
  112.     symbol->var_array = NULL;
  113.     symbol->array_size = symbol->table_size = 0;
  114.     symbol->flags &= ~ARRAYMAXED;
  115. }
  116.  
  117. /*
  118.  * 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. #ifdef this_is_really_slow
  129.  
  130.     register unsigned long g;
  131.  
  132.     while (len--) {
  133.         h = (h << 4) + *s++;
  134.         g = (h & 0xf0000000);
  135.         if (g) {
  136.             h = h ^ (g >> 24);
  137.             h = h ^ g;
  138.         }
  139.     }
  140.  
  141. #else /* this_is_really_slow */
  142. /*
  143.  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
  144.  * units.  On the first time through the loop we get the "leftover bytes"
  145.  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
  146.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
  147.  * this routine is heavily used enough, it's worth the ugly coding.
  148.  *
  149.  * OZ's original sdbm hash, copied from Margo Seltzers db package.
  150.  *
  151.  */
  152.  
  153. /* Even more speed: */
  154. /* #define HASHC   h = *s++ + 65599 * h */
  155. /* Because 65599 = pow(2,6) + pow(2,16) - 1 we multiply by shifts */
  156. #define HASHC   htmp = (h << 6);  \
  157.         h = *s++ + htmp + (htmp << 10) - h
  158.  
  159.     unsigned long htmp;
  160.  
  161.     h = 0;
  162.  
  163. #if defined(VAXC)
  164. /*    
  165.  * [This was an implementation of "Duff's Device", but it has been
  166.  * redone, separating the switch for extra iterations from the loop.
  167.  * This is necessary because the DEC VAX-C compiler is STOOPID.]
  168.  */
  169.     switch (len & (8 - 1)) {
  170.     case 7:        HASHC;
  171.     case 6:        HASHC;
  172.     case 5:        HASHC;
  173.     case 4:        HASHC;
  174.     case 3:        HASHC;
  175.     case 2:        HASHC;
  176.     case 1:        HASHC;
  177.     default:    break;
  178.     }
  179.  
  180.     if (len > (8 - 1)) {
  181.         register size_t loop = len >> 3;
  182.         do {
  183.             HASHC;
  184.             HASHC;
  185.             HASHC;
  186.             HASHC;
  187.             HASHC;
  188.             HASHC;
  189.             HASHC;
  190.             HASHC;
  191.         } while (--loop);
  192.     }
  193. #else /* !VAXC */
  194.     /* "Duff's Device" for those who can handle it */
  195.     if (len > 0) {
  196.         register size_t loop = (len + 8 - 1) >> 3;
  197.  
  198.         switch (len & (8 - 1)) {
  199.         case 0:
  200.             do {    /* All fall throughs */
  201.                 HASHC;
  202.         case 7:        HASHC;
  203.         case 6:        HASHC;
  204.         case 5:        HASHC;
  205.         case 4:        HASHC;
  206.         case 3:        HASHC;
  207.         case 2:        HASHC;
  208.         case 1:        HASHC;
  209.             } while (--loop);
  210.         }
  211.     }
  212. #endif /* !VAXC */
  213. #endif /* this_is_really_slow - not */
  214.  
  215.     if (h >= hsize)
  216.         h %= hsize;
  217.     return h;
  218. }
  219.  
  220. /*
  221.  * locate symbol[subs]
  222.  */
  223. static NODE *                /* NULL if not found */
  224. assoc_find(symbol, subs, hash1)
  225. NODE *symbol;
  226. register NODE *subs;
  227. int hash1;
  228. {
  229.     register NODE *bucket, *prev = 0;
  230.  
  231.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  232.         if (cmp_nodes(bucket->ahname, subs) == 0) {
  233. #if 0
  234.     /*
  235.      * Disable this code for now.  It screws things up if we have
  236.      * a ``for (iggy in foo)'' in progress.  Interestingly enough,
  237.      * this was not a problem in 2.15.3, only in 2.15.4.  I'm not
  238.      * sure why it works in 2.15.3.
  239.      */
  240.             if (prev) {    /* move found to front of chain */
  241.                 prev->ahnext = bucket->ahnext;
  242.                 bucket->ahnext = symbol->var_array[hash1];
  243.                 symbol->var_array[hash1] = bucket;
  244.             }
  245. #endif
  246.             return bucket;
  247.         } else
  248.             prev = bucket;    /* save previous list entry */
  249.     }
  250.     return NULL;
  251. }
  252.  
  253. /*
  254.  * test whether the array element symbol[subs] exists or not 
  255.  */
  256. int
  257. in_array(symbol, subs)
  258. NODE *symbol, *subs;
  259. {
  260.     register int hash1;
  261.  
  262.     if (symbol->type == Node_param_list)
  263.         symbol = stack_ptr[symbol->param_cnt];
  264.     if (symbol->var_array == 0)
  265.         return 0;
  266.     subs = concat_exp(subs);    /* concat_exp returns a string node */
  267.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  268.     if (assoc_find(symbol, subs, hash1) == NULL) {
  269.         free_temp(subs);
  270.         return 0;
  271.     } else {
  272.         free_temp(subs);
  273.         return 1;
  274.     }
  275. }
  276.  
  277. /*
  278.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  279.  * SUBS is a number or string used as the subscript. 
  280.  *
  281.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  282.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  283.  */
  284. NODE **
  285. assoc_lookup(symbol, subs)
  286. NODE *symbol, *subs;
  287. {
  288.     register int hash1;
  289.     register NODE *bucket;
  290.  
  291.     (void) force_string(subs);
  292.  
  293.     if (symbol->var_array == 0) {
  294.         symbol->type = Node_var_array;
  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.     if (subs->flags & TEMP)
  328.         b