home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / mac / unix / gawk.sit / source / array.c < prev    next >
Text File  |  1990-08-05  |  6KB  |  266 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989 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. #ifdef DONTDEF
  29. int primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
  30. #endif
  31.  
  32. #define ASSOC_HASHSIZE 127
  33. #define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
  34. #define HASHSTEP(old, c) ((old << 1) + c)
  35. #define MAKE_POS(v) (v & ~0x80000000)    /* make number positive */
  36.  
  37. NODE *
  38. concat_exp(tree)
  39. NODE *tree;
  40. {
  41.     NODE *r;
  42.     char *str;
  43.     char *s;
  44.     unsigned len;
  45.     int offset;
  46.     int subseplen;
  47.     char *subsep;
  48.  
  49.     if (tree->type != Node_expression_list)
  50.         return force_string(tree_eval(tree));
  51.     r = force_string(tree_eval(tree->lnode));
  52.     if (tree->rnode == NULL)
  53.         return r;
  54.     subseplen = SUBSEP_node->lnode->stlen;
  55.     subsep = SUBSEP_node->lnode->stptr;
  56.     len = r->stlen + subseplen + 1;
  57.     emalloc(str, char *, len, "concat_exp");
  58.     memcpy(str, r->stptr, r->stlen+1);
  59.     s = str + r->stlen;
  60.     free_temp(r);
  61.     tree = tree->rnode;
  62.     while (tree) {
  63.         if (subseplen == 1)
  64.             *s++ = *subsep;
  65.         else {
  66.             memcpy(s, subsep, subseplen+1);
  67.             s += subseplen;
  68.         }
  69.         r = force_string(tree_eval(tree->lnode));
  70.         len += r->stlen + subseplen;
  71.         offset = s - str;
  72.         erealloc(str, char *, len, "concat_exp");
  73.         s = str + offset;
  74.         memcpy(s, r->stptr, r->stlen+1);
  75.         s += r->stlen;
  76.         free_temp(r);
  77.         tree = tree->rnode;
  78.     }
  79.     r = tmp_string(str, s - str);
  80.     free(str);
  81.     return r;
  82. }
  83.  
  84. /* Flush all the values in symbol[] before doing a split() */
  85. void
  86. assoc_clear(symbol)
  87. NODE *symbol;
  88. {
  89.     int i;
  90.     NODE *bucket, *next;
  91.  
  92.     if (symbol->var_array == 0)
  93.         return;
  94.     for (i = 0; i < ASSOC_HASHSIZE; i++) {
  95.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  96.             next = bucket->ahnext;
  97.             deref = bucket->ahname;
  98.             do_deref();
  99.             deref = bucket->ahvalue;
  100.             do_deref();
  101.             freenode(bucket);
  102.         }
  103.         symbol->var_array[i] = 0;
  104.     }
  105. }
  106.  
  107. /*
  108.  * calculate the hash function of the string subs, also returning in *typtr
  109.  * the type (string or number) 
  110.  */
  111. static int
  112. hash_calc(subs)
  113. NODE *subs;
  114. {
  115.     register int hash1 = 0, i;
  116.  
  117.     subs = force_string(subs);
  118.     for (i = 0; i < subs->stlen; i++)
  119.         hash1 = HASHSTEP(hash1, subs->stptr[i]);
  120.  
  121.     hash1 = MAKE_POS(STIR_BITS((int) hash1)) % ASSOC_HASHSIZE;
  122.     return (hash1);
  123. }
  124.  
  125. /*
  126.  * locate symbol[subs], given hash of subs and type 
  127.  */
  128. static NODE *                /* NULL if not found */
  129. assoc_find(symbol, subs, hash1)
  130. NODE *symbol, *subs;
  131. int hash1;
  132. {
  133.     register NODE *bucket;
  134.  
  135.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  136.         if (cmp_nodes(bucket->ahname, subs))
  137.             continue;
  138.         return bucket;
  139.     }
  140.     return NULL;
  141. }
  142.  
  143. /*
  144.  * test whether the array element symbol[subs] exists or not 
  145.  */
  146. int
  147. in_array(symbol, subs)
  148. NODE *symbol, *subs;
  149. {
  150.     register int hash1;
  151.  
  152.     if (symbol->type == Node_param_list)
  153.         symbol = stack_ptr[symbol->param_cnt];
  154.     if (symbol->var_array == 0)
  155.         return 0;
  156.     subs = concat_exp(subs);
  157.     hash1 = hash_calc(subs);
  158.     if (assoc_find(symbol, subs, hash1) == NULL) {
  159.         free_temp(subs);
  160.         return 0;
  161.     } else {
  162.         free_temp(subs);
  163.         return 1;
  164.     }
  165. }
  166.  
  167. /*
  168.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  169.  * SUBS is a number or string used as the subscript. 
  170.  *
  171.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  172.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  173.  */
  174. NODE **
  175. assoc_lookup(symbol, subs)
  176. NODE *symbol, *subs;
  177. {
  178.     register int hash1, i;
  179.     register NODE *bucket;
  180.  
  181.     hash1 = hash_calc(subs);
  182.  
  183.     if (symbol->var_array == 0) {    /* this table really should grow
  184.                      * dynamically */
  185.         emalloc(symbol->var_array, NODE **, (sizeof(NODE *) *
  186.             ASSOC_HASHSIZE), "assoc_lookup");
  187.         for (i = 0; i < ASSOC_HASHSIZE; i++)
  188.             symbol->var_array[i] = 0;
  189.         symbol->type = Node_var_array;
  190.     } else {
  191.         bucket = assoc_find(symbol, subs, hash1);
  192.         if (bucket != NULL) {
  193.             free_temp(subs);
  194.             return &(bucket->ahvalue);
  195.         }
  196.     }
  197.     bucket = newnode(Node_ahash);
  198.     bucket->ahname = dupnode(subs);
  199.     bucket->ahvalue = Nnull_string;
  200.     bucket->ahnext = symbol->var_array[hash1];
  201.     symbol->var_array[hash1] = bucket;
  202.     return &(bucket->ahvalue);
  203. }
  204.  
  205. void
  206. do_delete(symbol, tree)
  207. NODE *symbol, *tree;
  208. {
  209.     register int hash1;
  210.     register NODE *bucket, *last;
  211.     NODE *subs;
  212.  
  213.     if (symbol->var_array == 0)
  214.         return;
  215.     subs = concat_exp(tree);
  216.     hash1 = hash_calc(subs);
  217.  
  218.     last = NULL;
  219.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  220.         if (cmp_nodes(bucket->ahname, subs) == 0)
  221.             break;
  222.     free_temp(subs);
  223.     if (bucket == NULL)
  224.         return;
  225.     if (last)
  226.         last->ahnext = bucket->ahnext;
  227.     else
  228.         symbol->var_array[hash1] = bucket->ahnext;
  229.     deref = bucket->ahname;
  230.     do_deref();
  231.     deref = bucket->ahvalue;
  232.     do_deref();
  233.     freenode(bucket);
  234. }
  235.  
  236. struct search *
  237. assoc_scan(symbol)
  238. NODE *symbol;
  239. {
  240.     struct search *lookat;
  241.  
  242.     if (!symbol->var_array)
  243.         return 0;
  244.     emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
  245.     lookat->numleft = ASSOC_HASHSIZE;
  246.     lookat->arr_ptr = symbol->var_array;
  247.     lookat->bucket = symbol->var_array[0];
  248.     return assoc_next(lookat);
  249. }
  250.  
  251. struct search *
  252. assoc_next(lookat)
  253. struct search *lookat;
  254. {
  255.     for (; lookat->numleft; lookat->numleft--) {
  256.         while (lookat->bucket != 0) {
  257.             lookat->retval = lookat->bucket->ahname;
  258.             lookat->bucket = lookat->bucket->ahnext;
  259.             return lookat;
  260.         }
  261.         lookat->bucket = *++(lookat->arr_ptr);
  262.     }
  263.     free((char *) lookat);
  264.     return 0;
  265. }
  266.