home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 6 / FreshFish_September1994.bin / bbs / gnu / gawk-2.15.5-src.lha / GNU / src / amiga / gawk-2.15.5 / array.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-18  |  12.7 KB  |  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.         bucket->ahname = dupnode(subs);
  329.     else {
  330.         unsigned int saveflags = subs->flags;
  331.  
  332.         subs->flags &= ~MALLOC;
  333.         bucket->ahname = dupnode(subs);
  334.         subs->flags = saveflags;
  335.     }
  336.     free_temp(subs);
  337.  
  338.     /* array subscripts are strings */
  339.     bucket->ahname->flags &= ~NUMBER;
  340.     bucket->ahname->flags |= STRING;
  341.     bucket->ahvalue = Nnull_string;
  342.     bucket->ahnext = symbol->var_array[hash1];
  343.     symbol->var_array[hash1] = bucket;
  344.     return &(bucket->ahvalue);
  345. }
  346.  
  347. void
  348. do_delete(symbol, tree)
  349. NODE *symbol, *tree;
  350. {
  351.     register int hash1;
  352.     register NODE *bucket, *last;
  353.     NODE *subs;
  354.  
  355.     if (symbol->type == Node_param_list)
  356.         symbol = stack_ptr[symbol->param_cnt];
  357.     if (symbol->var_array == 0)
  358.         return;
  359.     subs = concat_exp(tree);    /* concat_exp returns string node */
  360.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  361.  
  362.     last = NULL;
  363.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  364.         if (cmp_nodes(bucket->ahname, subs) == 0)
  365.             break;
  366.     free_temp(subs);
  367.     if (bucket == NULL)
  368.         return;
  369.     if (last)
  370.         last->ahnext = bucket->ahnext;
  371.     else
  372.         symbol->var_array[hash1] = bucket->ahnext;
  373.     unref(bucket->ahname);
  374.     unref(bucket->ahvalue);
  375.     freenode(bucket);
  376.     symbol->table_size--;
  377.     if (symbol->table_size <= 0) {
  378.         memset(symbol->var_array, '\0',
  379.             sizeof(NODE *) * symbol->array_size);
  380.         symbol->table_size = symbol->array_size = 0;
  381.         symbol->flags &= ~ARRAYMAXED;
  382.         free((char *) symbol->var_array);
  383.         symbol->var_array = NULL;
  384.     }
  385. }
  386.  
  387. void
  388. assoc_scan(symbol, lookat)
  389. NODE *symbol;
  390. struct search *lookat;
  391. {
  392.     lookat->sym = symbol;
  393.     lookat->idx = 0;
  394.     lookat->bucket = NULL;
  395.     lookat->retval = NULL;
  396.     if (symbol->var_array != NULL)
  397.         assoc_next(lookat);
  398. }
  399.  
  400. void
  401. assoc_next(lookat)
  402. struct search *lookat;
  403. {
  404.     register NODE *symbol = lookat->sym;
  405.     
  406.     if (symbol == NULL)
  407.         fatal("null symbol in assoc_next");
  408.     if (symbol->var_array == NULL || lookat->idx > symbol->array_size) {
  409.         lookat->retval = NULL;
  410.         return;
  411.     }
  412.     /*
  413.      * This is theoretically unsafe.  The element bucket might have
  414.      * been freed if the body of the scan did a delete on the next
  415.      * element of the bucket.  The only way to do that is by array
  416.      * reference, which is unlikely.  Basically, if the user is doing
  417.      * anything other than an operation on the current element of an
  418.      * assoc array while walking through it sequentially, all bets are
  419.      * off.  (The safe way is to register all search structs on an
  420.      * array with the array, and update all of them on a delete or
  421.      * insert)
  422.      */
  423.     if (lookat->bucket != NULL) {
  424.         lookat->retval = lookat->bucket->ahname;
  425.         lookat->bucket = lookat->bucket->ahnext;
  426.         return;
  427.     }
  428.     for (; lookat->idx < symbol->array_size; lookat->idx++) {
  429.         NODE *bucket;
  430.  
  431.         if ((bucket = symbol->var_array[lookat->idx]) != NULL) {
  432.             lookat->retval = bucket->ahname;
  433.             lookat->bucket = bucket->ahnext;
  434.             lookat->idx++;
  435.             return;
  436.         }
  437.     }
  438.     lookat->retval = NULL;
  439.     lookat->bucket = NULL;
  440.     return;
  441. }
  442.  
  443. /* grow_table --- grow a hash table */
  444.  
  445. static void
  446. grow_table(symbol)
  447. NODE *symbol;
  448. {
  449.     NODE **old, **new, *chain, *next;
  450.     int i, j;
  451.     unsigned long hash1;
  452.     unsigned long oldsize, newsize;
  453.     /*
  454.      * This is an array of primes. We grow the table by an order of
  455.      * magnitude each time (not just doubling) so that growing is a
  456.      * rare operation. We expect, on average, that it won't happen
  457.      * more than twice.  The final size is also chosen to be small
  458.      * enough so that MS-DOG mallocs can handle it. When things are
  459.      * very large (> 8K), we just double more or less, instead of
  460.      * just jumping from 8K to 64K.
  461.      */
  462.     static long sizes[] = { 13, 127, 1021, 8191, 16381, 32749, 65497 };
  463.  
  464.     /* find next biggest hash size */
  465.     oldsize = symbol->array_size;
  466.     newsize = 0;
  467.     for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
  468.         if (oldsize < sizes[i]) {
  469.             newsize = sizes[i];
  470.             break;
  471.         }
  472.     }
  473.  
  474.     if (newsize == oldsize) {    /* table already at max (!) */
  475.         symbol->flags |= ARRAYMAXED;
  476.         return;
  477.     }
  478.  
  479.     /* allocate new table */
  480.     emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
  481.     memset(new, '\0', newsize * sizeof(NODE *));
  482.  
  483.     /* brand new hash table, set things up and return */
  484.     if (symbol->var_array == NULL) {
  485.         symbol->table_size = 0;
  486.         goto done;
  487.     }
  488.  
  489.     /* old hash table there, move stuff to new, free old */
  490.     old = symbol->var_array;
  491.     for (i = 0; i < oldsize; i++) {
  492.         if (old[i] == NULL)
  493.             continue;
  494.  
  495.         for (chain = old[i]; chain != NULL; chain = next) {
  496.             next = chain->ahnext;
  497.             hash1 = hash(chain->ahname->stptr,
  498.                     chain->ahname->stlen, newsize);
  499.  
  500.             /* remove from old list, add to new */
  501.             chain->ahnext = new[hash1];
  502.             new[hash1] = chain;
  503.  
  504.         }
  505.     }
  506.     free(old);
  507.  
  508. done:
  509.     /*
  510.      * note that symbol->table_size does not change if an old array,
  511.      * and is explicitly set to 0 if a new one.
  512.      */
  513.     symbol->var_array = new;
  514.     symbol->array_size = newsize;
  515. }
  516.