home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / TOP / USR / SRC / gawk2.0.t.Z / gawk2.0.t / awk8.c < prev    next >
Text File  |  1988-12-31  |  6KB  |  257 lines
  1. /*
  2.  * routines for associative arrays.  SYMBOL is the address of the node (or
  3.  * other pointer) being dereferenced.  SUBS is a number or string used as the
  4.  * subscript. 
  5.  */
  6.  
  7. /*
  8.  * GAWK is distributed in the hope that it will be useful, but WITHOUT ANY
  9.  * WARRANTY.  No author or distributor accepts responsibility to anyone for
  10.  * the consequences of using it or for whether it serves any particular
  11.  * purpose or works at all, unless he says so in writing. Refer to the GAWK
  12.  * General Public License for full details. 
  13.  *
  14.  * Everyone is granted permission to copy, modify and redistribute GAWK, but
  15.  * only under the conditions described in the GAWK General Public License.  A
  16.  * copy of this license is supposed to have been given to you along with GAWK
  17.  * so you can know your rights and responsibilities.  It should be in a file
  18.  * named COPYING.  Among other things, the copyright notice and this notice
  19.  * must be preserved on all copies. 
  20.  *
  21.  * In other words, go ahead and share GAWK, but don't try to stop anyone else
  22.  * from sharing it farther.  Help stamp out software hoarding! 
  23.  */
  24.  
  25. #include "awk.h"
  26.  
  27. #ifdef DONTDEF
  28. int primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
  29. #endif
  30.  
  31. #define ASSOC_HASHSIZE 127
  32. #define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
  33. #define HASHSTEP(old, c) ((old << 1) + c)
  34. #define MAKE_POS(v) (v & ~0x80000000)    /* make number positive */
  35.  
  36. NODE *
  37. concat_exp(tree)
  38. NODE *tree;
  39. {
  40.     NODE *r;
  41.     NODE *n;
  42.     char *s;
  43.     unsigned char save;
  44.     unsigned len;
  45.     int subseplen;
  46.     char *subsep;
  47.     extern NODE *SUBSEP_node;
  48.     extern struct obstack other_stack;
  49.  
  50.     if (tree->type != Node_expression_list)
  51.         return force_string(tree_eval(tree));
  52.     r = force_string(tree_eval(tree->lnode));
  53.     if (tree->rnode == NULL) {
  54. #ifdef notdef
  55.         /* next four lines shouldn't be necessary, but they
  56.          * work around a mysterious bug
  57.          */
  58.         save = r->flags;
  59.         r->flags |= PERM;
  60.         n = dupnode(r);
  61.         r->flags = save;
  62. #endif
  63.         return r;
  64.     }
  65.     subseplen = SUBSEP_node->lnode->stlen;
  66.     subsep = SUBSEP_node->lnode->stptr;
  67.     len = r->stlen + subseplen;
  68.     emalloc(s, char *, len + 1, "concat_exp");
  69.     (void) strcpy(s, r->stptr);
  70.     tree = tree->rnode;
  71.     while (tree) {
  72.         (void) strcat(s, subsep);
  73.         r = force_string(tree_eval(tree->lnode));
  74.         len += r->stlen + subseplen;
  75.         erealloc(s, char *, len + 1, "concat_exp");
  76.         (void) strcat(s, r->stptr);
  77.         tree = tree->rnode;
  78.     }
  79.     len -= subseplen;
  80.     r = tmp_string(s, (int) len);
  81.     free(s);
  82.     return r;
  83. }
  84.  
  85. /* Flush all the values in symbol[] before doing a split() */
  86. assoc_clear(symbol)
  87. NODE *symbol;
  88. {
  89.     int i;
  90.     AHASH *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->next;
  97.             deref = bucket->name;
  98.             do_deref();
  99.             deref = bucket->value;
  100.             do_deref();
  101.             free((char *) 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 AHASH *                /* NULL if not found */
  129. assoc_find(symbol, subs, hash1)
  130. NODE *symbol, *subs;
  131. int hash1;
  132. {
  133.     register AHASH *bucket;
  134.  
  135.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->next) {
  136.         if (cmp_nodes(bucket->name, 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.         return 0;
  160.     else
  161.         return 1;
  162. }
  163.  
  164. /*
  165.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  166.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  167.  */
  168. NODE **
  169. assoc_lookup(symbol, subs)
  170. NODE *symbol, *subs;
  171. {
  172.     register int hash1 = 0, i;
  173.     register AHASH *bucket;
  174.  
  175.     hash1 = hash_calc(subs);
  176.  
  177.     if (symbol->var_array == 0) {    /* this table really should grow
  178.                      * dynamically */
  179.         emalloc(symbol->var_array, AHASH **, (sizeof(AHASH *) *
  180.             ASSOC_HASHSIZE), "assoc_lookup");
  181.         for (i = 0; i < ASSOC_HASHSIZE; i++)
  182.             symbol->var_array[i] = 0;
  183.         symbol->type = Node_var_array;
  184.     } else {
  185.         bucket = assoc_find(symbol, subs, hash1);
  186.         if (bucket != NULL)
  187.             return &(bucket->value);
  188.     }
  189.     emalloc(bucket, AHASH *, sizeof(AHASH), "assoc_lookup");
  190.     bucket->symbol = symbol;
  191.     bucket->name = dupnode(subs);
  192.     bucket->value = Nnull_string;
  193.     bucket->next = symbol->var_array[hash1];
  194.     symbol->var_array[hash1] = bucket;
  195.     return &(bucket->value);
  196. }
  197.  
  198. do_delete(symbol, tree)
  199. NODE *symbol, *tree;
  200. {
  201.     register int hash1 = 0;
  202.     register AHASH *bucket, *last;
  203.     NODE *subs;
  204.  
  205.     if (symbol->var_array == 0)
  206.         return;
  207.     subs = concat_exp(tree);
  208.     hash1 = hash_calc(subs);
  209.  
  210.     last = NULL;
  211.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->next)
  212.         if (cmp_nodes(bucket->name, subs) == 0)
  213.             break;
  214.     if (bucket == NULL)
  215.         return;
  216.     if (last)
  217.         last->next = bucket->next;
  218.     else
  219.         symbol->var_array[hash1] = NULL;
  220.     deref = bucket->name;
  221.     do_deref();
  222.     deref = bucket->value;
  223.     do_deref();
  224.     free((char *) bucket);
  225. }
  226.  
  227. struct search *
  228. assoc_scan(symbol)
  229. NODE *symbol;
  230. {
  231.     struct search *lookat;
  232.  
  233.     if (!symbol->var_array)
  234.         return 0;
  235.     lookat = (struct search *) obstack_alloc(&other_stack,
  236.             sizeof(struct search));
  237.     lookat->numleft = ASSOC_HASHSIZE;
  238.     lookat->arr_ptr = symbol->var_array;
  239.     lookat->bucket = symbol->var_array[0];
  240.     return assoc_next(lookat);
  241. }
  242.  
  243. struct search *
  244. assoc_next(lookat)
  245. struct search *lookat;
  246. {
  247.     for (; lookat->numleft; lookat->numleft--) {
  248.         while (lookat->bucket != 0) {
  249.             lookat->retval = lookat->bucket->name;
  250.             lookat->bucket = lookat->bucket->next;
  251.             return lookat;
  252.         }
  253.         lookat->bucket = *++(lookat->arr_ptr);
  254.     }
  255.     return 0;
  256. }
  257.