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 >
Wrap
C/C++ Source or Header
|
1990-10-01
|
6KB
|
272 lines
/*
* awk8.c -- routines for associative arrays.
*/
/*
* $Log: awk8.c,v $
* Revision 1.9 89/03/31 13:20:20 david
* GNU license; comment
*
* Revision 1.8 89/03/29 14:11:37 david
* delinting
*
* Revision 1.7 89/03/24 15:59:22 david
* AHASH becomes NODE
*
* Revision 1.6 89/03/21 10:44:17 david
* minor cleanup
*
*/
/*
* Copyright (C) 1986, 1988, 1989 the Free Software Foundation, Inc.
*
* This file is part of GAWK, the GNU implementation of the
* AWK Progamming Language.
*
* GAWK is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 1, or (at your option)
* any later version.
*
* GAWK is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with GAWK; see the file COPYING. If not, write to
* the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#include "awk.h"
#ifdef DONTDEF
int primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
#endif
#define ASSOC_HASHSIZE 127
#define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
#define HASHSTEP(old, c) ((old << 1) + c)
#define MAKE_POS(v) (v & ~0x80000000) /* make number positive */
NODE *
concat_exp(tree)
NODE *tree;
{
NODE *r;
char *s;
unsigned len;
int subseplen;
char *subsep;
if (tree->type != Node_expression_list)
return force_string(tree_eval(tree));
r = force_string(tree_eval(tree->lnode));
if (tree->rnode == NULL)
return r;
subseplen = SUBSEP_node->lnode->stlen;
subsep = SUBSEP_node->lnode->stptr;
len = r->stlen + subseplen;
emalloc(s, char *, len + 1, "concat_exp");
(void) strcpy(s, r->stptr);
free_temp(r);
tree = tree->rnode;
while (tree) {
(void) strcat(s, subsep);
r = force_string(tree_eval(tree->lnode));
len += r->stlen + subseplen;
erealloc(s, char *, len + 1, "concat_exp");
(void) strcat(s, r->stptr);
free_temp(r);
tree = tree->rnode;
}
len -= subseplen;
r = tmp_string(s, (int) len);
free(s);
return r;
}
/* Flush all the values in symbol[] before doing a split() */
void
assoc_clear(symbol)
NODE *symbol;
{
int i;
NODE *bucket, *next;
if (symbol->var_array == 0)
return;
for (i = 0; i < ASSOC_HASHSIZE; i++) {
for (bucket = symbol->var_array[i]; bucket; bucket = next) {
next = bucket->ahnext;
deref = bucket->ahname;
do_deref();
deref = bucket->ahvalue;
do_deref();
freenode(bucket);
}
symbol->var_array[i] = 0;
}
}
/*
* calculate the hash function of the string subs, also returning in *typtr
* the type (string or number)
*/
static int
hash_calc(subs)
NODE *subs;
{
register int hash1 = 0, i;
subs = force_string(subs);
for (i = 0; i < subs->stlen; i++)
hash1 = HASHSTEP(hash1, subs->stptr[i]);
hash1 = MAKE_POS(STIR_BITS((int) hash1)) % ASSOC_HASHSIZE;
return (hash1);
}
/*
* locate symbol[subs], given hash of subs and type
*/
static NODE * /* NULL if not found */
assoc_find(symbol, subs, hash1)
NODE *symbol, *subs;
int hash1;
{
register NODE *bucket;
for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
if (cmp_nodes(bucket->ahname, subs))
continue;
return bucket;
}
return NULL;
}
/*
* test whether the array element symbol[subs] exists or not
*/
int
in_array(symbol, subs)
NODE *symbol, *subs;
{
register int hash1;
if (symbol->type == Node_param_list)
symbol = stack_ptr[symbol->param_cnt];
if (symbol->var_array == 0)
return 0;
subs = concat_exp(subs);
hash1 = hash_calc(subs);
if (assoc_find(symbol, subs, hash1) == NULL) {
free_temp(subs);
return 0;
} else {
free_temp(subs);
return 1;
}
}
/*
* SYMBOL is the address of the node (or other pointer) being dereferenced.
* SUBS is a number or string used as the subscript.
*
* Find SYMBOL[SUBS] in the assoc array. Install it with value "" if it
* isn't there. Returns a pointer ala get_lhs to where its value is stored
*/
NODE **
assoc_lookup(symbol, subs)
NODE *symbol, *subs;
{
register int hash1 = 0, i;
register NODE *bucket;
hash1 = hash_calc(subs);
if (symbol->var_array == 0) { /* this table really should grow
* dynamically */
emalloc(symbol->var_array, NODE **, (sizeof(NODE *) *
ASSOC_HASHSIZE), "assoc_lookup");
for (i = 0; i < ASSOC_HASHSIZE; i++)
symbol->var_array[i] = 0;
symbol->type = Node_var_array;
} else {
bucket = assoc_find(symbol, subs, hash1);
if (bucket != NULL) {
free_temp(subs);
return &(bucket->ahvalue);
}
}
bucket = newnode(Node_ahash);
bucket->ahname = dupnode(subs);
bucket->ahvalue = Nnull_string;
bucket->ahnext = symbol->var_array[hash1];
symbol->var_array[hash1] = bucket;
return &(bucket->ahvalue);
}
void
do_delete(symbol, tree)
NODE *symbol, *tree;
{
register int hash1 = 0;
register NODE *bucket, *last;
NODE *subs;
if (symbol->var_array == 0)
return;
subs = concat_exp(tree);
hash1 = hash_calc(subs);
last = NULL;
for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
if (cmp_nodes(bucket->ahname, subs) == 0)
break;
free_temp(subs);
if (bucket == NULL)
return;
if (last)
last->ahnext = bucket->ahnext;
else
symbol->var_array[hash1] = NULL;
deref = bucket->ahname;
do_deref();
deref = bucket->ahvalue;
do_deref();
freenode(bucket);
}
struct search *
assoc_scan(symbol)
NODE *symbol;
{
struct search *lookat;
if (!symbol->var_array)
return 0;
emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
lookat->numleft = ASSOC_HASHSIZE;
lookat->arr_ptr = symbol->var_array;
lookat->bucket = symbol->var_array[0];
return assoc_next(lookat);
}
struct search *
assoc_next(lookat)
struct search *lookat;
{
for (; lookat->numleft; lookat->numleft--) {
while (lookat->bucket != 0) {
lookat->retval = lookat->bucket->ahname;
lookat->bucket = lookat->bucket->ahnext;
return lookat;
}
lookat->bucket = *++(lookat->arr_ptr);
}
free((char *) lookat);
return 0;
}