home *** CD-ROM | disk | FTP | other *** search
/ ftp.uni-stuttgart.de/pub/systems/acorn/ / Acorn.tar / Acorn / acornet / dev / gawk.spk / gawk-2154 / c / array < prev    next >
Text File  |  1994-01-16  |  12KB  |  483 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. }
  115.  
  116. /*
  117.  * calculate the hash function of the string in subs
  118.  */
  119. unsigned int
  120. hash(s, len, hsize)
  121. register const char *s;
  122. register size_t len;
  123. unsigned long hsize;
  124. {
  125.     register unsigned long h = 0;
  126.  
  127. #ifdef this_is_really_slow
  128.  
  129.     register unsigned long g;
  130.  
  131.     while (len--) {
  132.         h = (h << 4) + *s++;
  133.         g = (h & 0xf0000000);
  134.         if (g) {
  135.             h = h ^ (g >> 24);
  136.             h = h ^ g;
  137.         }
  138.     }
  139.  
  140. #else /* this_is_really_slow */
  141. /*
  142.  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
  143.  * units.  On the first time through the loop we get the "leftover bytes"
  144.  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
  145.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
  146.  * this routine is heavily used enough, it's worth the ugly coding.
  147.  *
  148.  * OZ's original sdbm hash, copied from Margo Seltzers db package.
  149.  *
  150.  */
  151.  
  152. /* Even more speed: */
  153. /* #define HASHC   h = *s++ + 65599 * h */
  154. /* Because 65599 = pow(2,6) + pow(2,16) - 1 we multiply by shifts */
  155. #define HASHC   htmp = (h << 6);  \
  156.         h = *s++ + htmp + (htmp << 10) - h
  157.  
  158.     unsigned long htmp;
  159.  
  160.     h = 0;
  161.  
  162. #if defined(VAXC)
  163. /*    
  164.  * [This was an implementation of "Duff's Device", but it has been
  165.  * redone, separating the switch for extra iterations from the loop.
  166.  * This is necessary because the DEC VAX-C compiler is STOOPID.]
  167.  */
  168.     switch (len & (8 - 1)) {
  169.     case 7:        HASHC;
  170.     case 6:        HASHC;
  171.     case 5:        HASHC;
  172.     case 4:        HASHC;
  173.     case 3:        HASHC;
  174.     case 2:        HASHC;
  175.     case 1:        HASHC;
  176.     default:    break;
  177.     }
  178.  
  179.     if (len > (8 - 1)) {
  180.         register size_t loop = len >> 3;
  181.         do {
  182.             HASHC;
  183.             HASHC;
  184.             HASHC;
  185.             HASHC;
  186.             HASHC;
  187.             HASHC;
  188.             HASHC;
  189.             HASHC;
  190.         } while (--loop);
  191.     }
  192. #else /* !VAXC */
  193.     /* "Duff's Device" for those who can handle it */
  194.     if (len > 0) {
  195.         register size_t loop = (len + 8 - 1) >> 3;
  196.  
  197.         switch (len & (8 - 1)) {
  198.         case 0:
  199.             do {    /* All fall throughs */
  200.                 HASHC;
  201.         case 7:        HASHC;
  202.         case 6:        HASHC;
  203.         case 5:        HASHC;
  204.         case 4:        HASHC;
  205.         case 3:        HASHC;
  206.         case 2:        HASHC;
  207.         case 1:        HASHC;
  208.             } while (--loop);
  209.         }
  210.     }
  211. #endif /* !VAXC */
  212. #endif /* this_is_really_slow - not */
  213.  
  214.     if (h >= hsize)
  215.         h %= hsize;
  216.     return h;
  217. }
  218.  
  219. /*
  220.  * locate symbol[subs]
  221.  */
  222. static NODE *                /* NULL if not found */
  223. assoc_find(symbol, subs, hash1)
  224. NODE *symbol;
  225. register NODE *subs;
  226. int hash1;
  227. {
  228.     register NODE *bucket, *prev = 0;
  229.  
  230.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  231.         if (cmp_nodes(bucket->ahname, subs) == 0) {
  232.             if (prev) {    /* move found to front of chain */
  233.                 prev->ahnext = bucket->ahnext;
  234.                 bucket->ahnext = symbol->var_array[hash1];
  235.                 symbol->var_array[hash1] = bucket;
  236.             }
  237.             return bucket;
  238.         } else
  239.             prev = bucket;    /* save previous list entry */
  240.     }
  241.     return NULL;
  242. }
  243.  
  244. /*
  245.  * test whether the array element symbol[subs] exists or not 
  246.  */
  247. int
  248. in_array(symbol, subs)
  249. NODE *symbol, *subs;
  250. {
  251.     register int hash1;
  252.  
  253.     if (symbol->type == Node_param_list)
  254.         symbol = stack_ptr[symbol->param_cnt];
  255.     if (symbol->var_array == 0)
  256.         return 0;
  257.     subs = concat_exp(subs);    /* concat_exp returns a string node */
  258.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  259.     if (assoc_find(symbol, subs, hash1) == NULL) {
  260.         free_temp(subs);
  261.         return 0;
  262.     } else {
  263.         free_temp(subs);
  264.         return 1;
  265.     }
  266. }
  267.  
  268. /*
  269.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  270.  * SUBS is a number or string used as the subscript. 
  271.  *
  272.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  273.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  274.  */
  275. NODE **
  276. assoc_lookup(symbol, subs)
  277. NODE *symbol, *subs;
  278. {
  279.     register int hash1;
  280.     register NODE *bucket;
  281.  
  282.     (void) force_string(subs);
  283.  
  284.     if (symbol->var_array == 0) {
  285.         symbol->type = Node_var_array;
  286.         symbol->array_size = symbol->table_size = 0;    /* sanity */
  287.         grow_table(symbol);
  288.         hash1 = hash(subs->stptr, subs->stlen,
  289.                 (unsigned long) symbol->array_size);
  290.     } else {
  291.         hash1 = hash(subs->stptr, subs->stlen,
  292.                 (unsigned long) symbol->array_size);
  293.         bucket = assoc_find(symbol, subs, hash1);
  294.         if (bucket != NULL) {
  295.             free_temp(subs);
  296.             return &(bucket->ahvalue);
  297.         }
  298.     }
  299.  
  300.     /* It's not there, install it. */
  301.     if (do_lint && subs->stlen == 0)
  302.         warning("subscript of array `%s' is null string",
  303.             symbol->vname);
  304.  
  305.     /* first see if we would need to grow the array, before installing */
  306.     symbol->table_size++;
  307.     if ((symbol->flags & ARRAYMAXED) == 0
  308.         && symbol->table_size/symbol->array_size > AVG_CHAIN_MAX) {
  309.         grow_table(symbol);
  310.         /* have to recompute hash value for new size */
  311.         hash1 = hash(subs->stptr, subs->stlen,
  312.                 (unsigned long) symbol->array_size);
  313.     }
  314.  
  315.     getnode(bucket);
  316.     bucket->type = Node_ahash;
  317.     if (subs->flags & TEMP)
  318.         bucket->ahname = dupnode(subs);
  319.     else {
  320.         unsigned int saveflags = subs->flags;
  321.  
  322.         subs->flags &= ~MALLOC;
  323.         bucket->ahname = dupnode(subs);
  324.         subs->flags = saveflags;
  325.     }
  326.     free_temp(subs);
  327.  
  328.     /* array subscripts are strings */
  329.     bucket->ahname->flags &= ~NUMBER;
  330.     bucket->ahname->flags |= STRING;
  331.     bucket->ahvalue = Nnull_string;
  332.     bucket->ahnext = symbol->var_array[hash1];
  333.     symbol->var_array[hash1] = bucket;
  334.     return &(bucket->ahvalue);
  335. }
  336.  
  337. void
  338. do_delete(symbol, tree)
  339. NODE *symbol, *tree;
  340. {
  341.     register int hash1;
  342.     register NODE *bucket, *last;
  343.     NODE *subs;
  344.  
  345.     if (symbol->type == Node_param_list)
  346.         symbol = stack_ptr[symbol->param_cnt];
  347.     if (symbol->var_array == 0)
  348.         return;
  349.     subs = concat_exp(tree);    /* concat_exp returns string node */
  350.     hash1 = hash(subs->stptr, subs->stlen, (unsigned long) symbol->array_size);
  351.  
  352.     last = NULL;
  353.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  354.         if (cmp_nodes(bucket->ahname, subs) == 0)
  355.             break;
  356.     free_temp(subs);
  357.     if (bucket == NULL)
  358.         return;
  359.     if (last)
  360.         last->ahnext = bucket->ahnext;
  361.     else
  362.         symbol->var_array[hash1] = bucket->ahnext;
  363.     unref(bucket->ahname);
  364.     unref(bucket->ahvalue);
  365.     freenode(bucket);
  366.     symbol->table_size--;
  367.     if (symbol->table_size <= 0) {
  368.         memset(symbol->var_array, '\0',
  369.             sizeof(NODE *) * symbol->array_size);
  370.         symbol->table_size = symbol->array_size = 0;
  371.         free(symbol->var_array);
  372.         symbol->var_array = NULL;
  373.     }
  374. }
  375.  
  376. void
  377. assoc_scan(symbol, lookat)
  378. NODE *symbol;
  379. struct search *lookat;
  380. {
  381.     if (symbol->var_array == NULL) {
  382.         lookat->retval = NULL;
  383.         return;
  384.     }
  385.     lookat->arr_ptr = symbol->var_array;
  386.     lookat->arr_end = lookat->arr_ptr + symbol->array_size;
  387.     lookat->bucket = symbol->var_array[0];
  388.     assoc_next(lookat);
  389. }
  390.  
  391. void
  392. assoc_next(lookat)
  393. struct search *lookat;
  394. {
  395.     while (lookat->arr_ptr < lookat->arr_end) {
  396.         if (lookat->bucket != 0) {
  397.             lookat->retval = lookat->bucket->ahname;
  398.             lookat->bucket = lookat->bucket->ahnext;
  399.             return;
  400.         }
  401.         lookat->arr_ptr++;
  402.         if (lookat->arr_ptr < lookat->arr_end)
  403.             lookat->bucket = *(lookat->arr_ptr);
  404.         else
  405.             lookat->retval = NULL;
  406.     }
  407.     return;
  408. }
  409.  
  410. /* grow_table --- grow a hash table */
  411.  
  412. static void
  413. grow_table(symbol)
  414. NODE *symbol;
  415. {
  416.     NODE **old, **new, *chain, *next;
  417.     int i, j;
  418.     unsigned long hash1;
  419.     unsigned long oldsize, newsize;
  420.     /*
  421.      * This is an array of primes. We grow the table by an order of
  422.      * magnitude each time (not just doubling) so that growing is a
  423.      * rare operation. We expect, on average, that it won't happen
  424.      * more than twice.  The final size is also chosen to be small
  425.      * enough so that MS-DOG mallocs can handle it. When things are
  426.      * very large (> 8K), we just double more or less, instead of
  427.      * just jumping from 8K to 64K.
  428.      */
  429.     static long sizes[] = { 13, 127, 1021, 8191, 16381, 32749, 65497 };
  430.  
  431.     /* find next biggest hash size */
  432.     oldsize = symbol->array_size;
  433.     newsize = 0;
  434.     for (i = 0, j = sizeof(sizes)/sizeof(sizes[0]); i < j; i++) {
  435.         if (oldsize < sizes[i]) {
  436.             newsize = sizes[i];
  437.             break;
  438.         }
  439.     }
  440.  
  441.     if (newsize == oldsize) {    /* table already at max (!) */
  442.         symbol->flags |= ARRAYMAXED;
  443.         return;
  444.     }
  445.  
  446.     /* allocate new table */
  447.     emalloc(new, NODE **, newsize * sizeof(NODE *), "grow_table");
  448.     memset(new, '\0', newsize * sizeof(NODE *));
  449.  
  450.     /* brand new hash table, set things up and return */
  451.     if (symbol->var_array == NULL) {
  452.         symbol->table_size = 0;
  453.         goto done;
  454.     }
  455.  
  456.     /* old hash table there, move stuff to new, free old */
  457.     old = symbol->var_array;
  458.     for (i = 0; i < oldsize; i++) {
  459.         if (old[i] == NULL)
  460.             continue;
  461.  
  462.         for (chain = old[i]; chain != NULL; chain = next) {
  463.             next = chain->ahnext;
  464.             hash1 = hash(chain->ahname->stptr,
  465.                     chain->ahname->stlen, newsize);
  466.  
  467.             /* remove from old list, add to new */
  468.             chain->ahnext = new[hash1];
  469.             new[hash1] = chain;
  470.  
  471.         }
  472.     }
  473.     free(old);
  474.  
  475. done:
  476.     /*
  477.      * note that symbol->table_size does not change if an old array,
  478.      * and is explicitly set to 0 if a new one.
  479.      */
  480.     symbol->var_array = new;
  481.     symbol->array_size = newsize;
  482. }
  483.