home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / zip / gnu / gawk213s.lzh / GAWK213S / ARRAY.C < prev    next >
C/C++ Source or Header  |  1993-07-29  |  6KB  |  285 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989, 1991 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 1, or (at your option)
  14.  * 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, 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  */
  25.  
  26. #include "awk.h"
  27.  
  28. static NODE *assoc_find P((NODE *symbol, NODE *subs, int hash1));
  29.  
  30. NODE *
  31. concat_exp(tree)
  32. register NODE *tree;
  33. {
  34.     register NODE *r;
  35.     char *str;
  36.     char *s;
  37.     unsigned len;
  38.     int offset;
  39.     int subseplen;
  40.     char *subsep;
  41.  
  42.     if (tree->type != Node_expression_list)
  43.         return force_string(tree_eval(tree));
  44.     r = force_string(tree_eval(tree->lnode));
  45.     if (tree->rnode == NULL)
  46.         return r;
  47.     subseplen = SUBSEP_node->lnode->stlen;
  48.     subsep = SUBSEP_node->lnode->stptr;
  49.     len = r->stlen + subseplen + 2;
  50.     emalloc(str, char *, len, "concat_exp");
  51.     memcpy(str, r->stptr, r->stlen+1);
  52.     s = str + r->stlen;
  53.     free_temp(r);
  54.     tree = tree->rnode;
  55.     while (tree) {
  56.         if (subseplen == 1)
  57.             *s++ = *subsep;
  58.         else {
  59.             memcpy(s, subsep, subseplen+1);
  60.             s += subseplen;
  61.         }
  62.         r = force_string(tree_eval(tree->lnode));
  63.         len += r->stlen + subseplen;
  64.         offset = s - str;
  65.         erealloc(str, char *, len, "concat_exp");
  66.         s = str + offset;
  67.         memcpy(s, r->stptr, r->stlen+1);
  68.         s += r->stlen;
  69.         free_temp(r);
  70.         tree = tree->rnode;
  71.     }
  72.     r = make_str_node(str, s - str, ALREADY_MALLOCED);
  73.     r->flags |= TEMP;
  74.     return r;
  75. }
  76.  
  77. /* Flush all the values in symbol[] before doing a split() */
  78. void
  79. assoc_clear(symbol)
  80. NODE *symbol;
  81. {
  82.     int i;
  83.     NODE *bucket, *next;
  84.  
  85.     if (symbol->var_array == 0)
  86.         return;
  87.     for (i = 0; i < HASHSIZE; i++) {
  88.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  89.             next = bucket->ahnext;
  90.             unref(bucket->ahname);
  91.             unref(bucket->ahvalue);
  92.             freenode(bucket);
  93.         }
  94.         symbol->var_array[i] = 0;
  95.     }
  96. }
  97.  
  98. /*
  99.  * calculate the hash function of the string in subs
  100.  */
  101. unsigned int
  102. hash(s, len)
  103. register char *s;
  104. register int len;
  105. {
  106.     register unsigned int h = 0, g;
  107.  
  108.     while (len--) {
  109.         h = (h << 4) + *s++;
  110.         g = (h & 0xf0000000);
  111.         if (g) {
  112.             h = h ^ (g >> 24);
  113.             h = h ^ g;
  114.         }
  115.     }
  116.     if (h < HASHSIZE)
  117.         return h;
  118.     else
  119.         return h%HASHSIZE;
  120. }
  121.  
  122. /*
  123.  * locate symbol[subs]
  124.  */
  125. static NODE *                /* NULL if not found */
  126. assoc_find(symbol, subs, hash1)
  127. NODE *symbol;
  128. register NODE *subs;
  129. int hash1;
  130. {
  131.     register NODE *bucket;
  132.     int chained = 0;
  133.  
  134.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  135.         if (cmp_nodes(bucket->ahname, subs) == 0) {
  136.             if (chained) {    /* move found to front of chain */
  137.             register NODE *this, *prev;
  138.                 for (prev = this = symbol->var_array[hash1];
  139.                      this; prev = this, this = this->ahnext) {
  140.                     if (this == bucket) {
  141.                         prev->ahnext = this->ahnext;
  142.                         this->ahnext = symbol->var_array[hash1];
  143.                         symbol->var_array[hash1] = this;
  144.                     }
  145.                 }
  146.             }
  147.             return bucket;
  148.         }
  149.         if (bucket)
  150.             chained = 1;
  151.     }
  152.     return NULL;
  153. }
  154.  
  155. /*
  156.  * test whether the array element symbol[subs] exists or not 
  157.  */
  158. int
  159. in_array(symbol, subs)
  160. NODE *symbol, *subs;
  161. {
  162.     register int hash1;
  163.  
  164.     if (symbol->type == Node_param_list)
  165.         symbol = stack_ptr[symbol->param_cnt];
  166.     if (symbol->var_array == 0)
  167.         return 0;
  168.     subs = concat_exp(subs);    /* concat_exp returns a string node */
  169.     hash1 = hash(subs->stptr, subs->stlen);
  170.     if (assoc_find(symbol, subs, hash1) == NULL) {
  171.         free_temp(subs);
  172.         return 0;
  173.     } else {
  174.         free_temp(subs);
  175.         return 1;
  176.     }
  177. }
  178.  
  179. /*
  180.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  181.  * SUBS is a number or string used as the subscript. 
  182.  *
  183.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  184.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  185.  */
  186. NODE **
  187. assoc_lookup(symbol, subs)
  188. NODE *symbol, *subs;
  189. {
  190.     register int hash1;
  191.     register NODE *bucket;
  192.  
  193.     (void) force_string(subs);
  194.     hash1 = hash(subs->stptr, subs->stlen);
  195.  
  196.     if (symbol->var_array == 0) {    /* this table really should grow
  197.                      * dynamically */
  198.         unsigned size;
  199.  
  200.         size = sizeof(NODE *) * HASHSIZE;
  201.         emalloc(symbol->var_array, NODE **, size, "assoc_lookup");
  202.         memset((char *)symbol->var_array, 0, size);
  203.         symbol->type = Node_var_array;
  204.     } else {
  205.         bucket = assoc_find(symbol, subs, hash1);
  206.         if (bucket != NULL) {
  207.             free_temp(subs);
  208.             return &(bucket->ahvalue);
  209.         }
  210.     }
  211.     getnode(bucket);
  212.     bucket->type = Node_ahash;
  213.     bucket->ahname = dupnode(subs);
  214.     free_temp(subs);
  215.     bucket->ahvalue = Nnull_string;
  216.     bucket->ahnext = symbol->var_array[hash1];
  217.     symbol->var_array[hash1] = bucket;
  218.     return &(bucket->ahvalue);
  219. }
  220.  
  221. void
  222. do_delete(symbol, tree)
  223. NODE *symbol, *tree;
  224. {
  225.     register int hash1;
  226.     register NODE *bucket, *last;
  227.     NODE *subs;
  228.  
  229.     if (symbol->type == Node_param_list)
  230.         symbol = stack_ptr[symbol->param_cnt];
  231.     if (symbol->var_array == 0)
  232.         return;
  233.     subs = concat_exp(tree);    /* concat_exp returns string node */
  234.     hash1 = hash(subs->stptr, subs->stlen);
  235.  
  236.     last = NULL;
  237.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  238.         if (cmp_nodes(bucket->ahname, subs) == 0)
  239.             break;
  240.     free_temp(subs);
  241.     if (bucket == NULL)
  242.         return;
  243.     if (last)
  244.         last->ahnext = bucket->ahnext;
  245.     else
  246.         symbol->var_array[hash1] = bucket->ahnext;
  247.     unref(bucket->ahname);
  248.     unref(bucket->ahvalue);
  249.     freenode(bucket);
  250. }
  251.  
  252. void
  253. assoc_scan(symbol, lookat)
  254. NODE *symbol;
  255. struct search *lookat;
  256. {
  257.     if (!symbol->var_array) {
  258.         lookat->retval = NULL;
  259.         return;
  260.     }
  261.     lookat->arr_ptr = symbol->var_array;
  262.     lookat->arr_end = lookat->arr_ptr + HASHSIZE;    /* added */
  263.     lookat->bucket = symbol->var_array[0];
  264.     assoc_next(lookat);
  265. }
  266.  
  267. void
  268. assoc_next(lookat)
  269. struct search *lookat;
  270. {
  271.     while (lookat->arr_ptr < lookat->arr_end) {
  272.         if (lookat->bucket != 0) {
  273.             lookat->retval = lookat->bucket->ahname;
  274.             lookat->bucket = lookat->bucket->ahnext;
  275.             return;
  276.         }
  277.         lookat->arr_ptr++;
  278.         if (lookat->arr_ptr < lookat->arr_end)
  279.             lookat->bucket = *(lookat->arr_ptr);
  280.         else
  281.             lookat->retval = NULL;
  282.     }
  283.     return;
  284. }
  285.