home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 419b.lha / GNU_Awk_v2.10_Beta / awk8.c < prev    next >
C/C++ Source or Header  |  1990-10-01  |  6KB  |  272 lines
  1. /*
  2.  * awk8.c -- routines for associative arrays.
  3.  */
  4.  
  5. /*
  6.  * $Log:    awk8.c,v $
  7.  * Revision 1.9  89/03/31  13:20:20  david
  8.  * GNU license; comment
  9.  * 
  10.  * Revision 1.8  89/03/29  14:11:37  david
  11.  * delinting
  12.  * 
  13.  * Revision 1.7  89/03/24  15:59:22  david
  14.  * AHASH becomes NODE
  15.  * 
  16.  * Revision 1.6  89/03/21  10:44:17  david
  17.  * minor cleanup
  18.  * 
  19.  */
  20.  
  21. /* 
  22.  * Copyright (C) 1986, 1988, 1989 the Free Software Foundation, Inc.
  23.  * 
  24.  * This file is part of GAWK, the GNU implementation of the
  25.  * AWK Progamming Language.
  26.  * 
  27.  * GAWK is free software; you can redistribute it and/or modify
  28.  * it under the terms of the GNU General Public License as published by
  29.  * the Free Software Foundation; either version 1, or (at your option)
  30.  * any later version.
  31.  * 
  32.  * GAWK is distributed in the hope that it will be useful,
  33.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35.  * GNU General Public License for more details.
  36.  * 
  37.  * You should have received a copy of the GNU General Public License
  38.  * along with GAWK; see the file COPYING.  If not, write to
  39.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  40.  */
  41.  
  42. #include "awk.h"
  43.  
  44. #ifdef DONTDEF
  45. int primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
  46. #endif
  47.  
  48. #define ASSOC_HASHSIZE 127
  49. #define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
  50. #define HASHSTEP(old, c) ((old << 1) + c)
  51. #define MAKE_POS(v) (v & ~0x80000000)    /* make number positive */
  52.  
  53. NODE *
  54. concat_exp(tree)
  55. NODE *tree;
  56. {
  57.     NODE *r;
  58.     char *s;
  59.     unsigned len;
  60.     int subseplen;
  61.     char *subsep;
  62.  
  63.     if (tree->type != Node_expression_list)
  64.         return force_string(tree_eval(tree));
  65.     r = force_string(tree_eval(tree->lnode));
  66.     if (tree->rnode == NULL)
  67.         return r;
  68.     subseplen = SUBSEP_node->lnode->stlen;
  69.     subsep = SUBSEP_node->lnode->stptr;
  70.     len = r->stlen + subseplen;
  71.     emalloc(s, char *, len + 1, "concat_exp");
  72.     (void) strcpy(s, r->stptr);
  73.     free_temp(r);
  74.     tree = tree->rnode;
  75.     while (tree) {
  76.         (void) strcat(s, subsep);
  77.         r = force_string(tree_eval(tree->lnode));
  78.         len += r->stlen + subseplen;
  79.         erealloc(s, char *, len + 1, "concat_exp");
  80.         (void) strcat(s, r->stptr);
  81.         free_temp(r);
  82.         tree = tree->rnode;
  83.     }
  84.     len -= subseplen;
  85.     r = tmp_string(s, (int) len);
  86.     free(s);
  87.     return r;
  88. }
  89.  
  90. /* Flush all the values in symbol[] before doing a split() */
  91. void
  92. assoc_clear(symbol)
  93. NODE *symbol;
  94. {
  95.     int i;
  96.     NODE *bucket, *next;
  97.  
  98.     if (symbol->var_array == 0)
  99.         return;
  100.     for (i = 0; i < ASSOC_HASHSIZE; i++) {
  101.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  102.             next = bucket->ahnext;
  103.             deref = bucket->ahname;
  104.             do_deref();
  105.             deref = bucket->ahvalue;
  106.             do_deref();
  107.             freenode(bucket);
  108.         }
  109.         symbol->var_array[i] = 0;
  110.     }
  111. }
  112.  
  113. /*
  114.  * calculate the hash function of the string subs, also returning in *typtr
  115.  * the type (string or number) 
  116.  */
  117. static int
  118. hash_calc(subs)
  119. NODE *subs;
  120. {
  121.     register int hash1 = 0, i;
  122.  
  123.     subs = force_string(subs);
  124.     for (i = 0; i < subs->stlen; i++)
  125.         hash1 = HASHSTEP(hash1, subs->stptr[i]);
  126.  
  127.     hash1 = MAKE_POS(STIR_BITS((int) hash1)) % ASSOC_HASHSIZE;
  128.     return (hash1);
  129. }
  130.  
  131. /*
  132.  * locate symbol[subs], given hash of subs and type 
  133.  */
  134. static NODE *                /* NULL if not found */
  135. assoc_find(symbol, subs, hash1)
  136. NODE *symbol, *subs;
  137. int hash1;
  138. {
  139.     register NODE *bucket;
  140.  
  141.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  142.         if (cmp_nodes(bucket->ahname, subs))
  143.             continue;
  144.         return bucket;
  145.     }
  146.     return NULL;
  147. }
  148.  
  149. /*
  150.  * test whether the array element symbol[subs] exists or not 
  151.  */
  152. int
  153. in_array(symbol, subs)
  154. NODE *symbol, *subs;
  155. {
  156.     register int hash1;
  157.  
  158.     if (symbol->type == Node_param_list)
  159.         symbol = stack_ptr[symbol->param_cnt];
  160.     if (symbol->var_array == 0)
  161.         return 0;
  162.     subs = concat_exp(subs);
  163.     hash1 = hash_calc(subs);
  164.     if (assoc_find(symbol, subs, hash1) == NULL) {
  165.         free_temp(subs);
  166.         return 0;
  167.     } else {
  168.         free_temp(subs);
  169.         return 1;
  170.     }
  171. }
  172.  
  173. /*
  174.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  175.  * SUBS is a number or string used as the subscript. 
  176.  *
  177.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  178.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  179.  */
  180. NODE **
  181. assoc_lookup(symbol, subs)
  182. NODE *symbol, *subs;
  183. {
  184.     register int hash1 = 0, i;
  185.     register NODE *bucket;
  186.  
  187.     hash1 = hash_calc(subs);
  188.  
  189.     if (symbol->var_array == 0) {    /* this table really should grow
  190.                      * dynamically */
  191.         emalloc(symbol->var_array, NODE **, (sizeof(NODE *) *
  192.             ASSOC_HASHSIZE), "assoc_lookup");
  193.         for (i = 0; i < ASSOC_HASHSIZE; i++)
  194.             symbol->var_array[i] = 0;
  195.         symbol->type = Node_var_array;
  196.     } else {
  197.         bucket = assoc_find(symbol, subs, hash1);
  198.         if (bucket != NULL) {
  199.             free_temp(subs);
  200.             return &(bucket->ahvalue);
  201.         }
  202.     }
  203.     bucket = newnode(Node_ahash);
  204.     bucket->ahname = dupnode(subs);
  205.     bucket->ahvalue = Nnull_string;
  206.     bucket->ahnext = symbol->var_array[hash1];
  207.     symbol->var_array[hash1] = bucket;
  208.     return &(bucket->ahvalue);
  209. }
  210.  
  211. void
  212. do_delete(symbol, tree)
  213. NODE *symbol, *tree;
  214. {
  215.     register int hash1 = 0;
  216.     register NODE *bucket, *last;
  217.     NODE *subs;
  218.  
  219.     if (symbol->var_array == 0)
  220.         return;
  221.     subs = concat_exp(tree);
  222.     hash1 = hash_calc(subs);
  223.  
  224.     last = NULL;
  225.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  226.         if (cmp_nodes(bucket->ahname, subs) == 0)
  227.             break;
  228.     free_temp(subs);
  229.     if (bucket == NULL)
  230.         return;
  231.     if (last)
  232.         last->ahnext = bucket->ahnext;
  233.     else
  234.         symbol->var_array[hash1] = NULL;
  235.     deref = bucket->ahname;
  236.     do_deref();
  237.     deref = bucket->ahvalue;
  238.     do_deref();
  239.     freenode(bucket);
  240. }
  241.  
  242. struct search *
  243. assoc_scan(symbol)
  244. NODE *symbol;
  245. {
  246.     struct search *lookat;
  247.  
  248.     if (!symbol->var_array)
  249.         return 0;
  250.     emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
  251.     lookat->numleft = ASSOC_HASHSIZE;
  252.     lookat->arr_ptr = symbol->var_array;
  253.     lookat->bucket = symbol->var_array[0];
  254.     return assoc_next(lookat);
  255. }
  256.  
  257. struct search *
  258. assoc_next(lookat)
  259. struct search *lookat;
  260. {
  261.     for (; lookat->numleft; lookat->numleft--) {
  262.         while (lookat->bucket != 0) {
  263.             lookat->retval = lookat->bucket->ahname;
  264.             lookat->bucket = lookat->bucket->ahnext;
  265.             return lookat;
  266.         }
  267.         lookat->bucket = *++(lookat->arr_ptr);
  268.     }
  269.     free((char *) lookat);
  270.     return 0;
  271. }
  272.