[p5sagit/p5-mst-13.2.git] / hash.c

/* $Header: hash.c,v 3.0.1.4 90/08/09 03:50:22 lwall Locked $
 *
 *    Copyright (c) 1989, Larry Wall
 *
 *    You may distribute under the terms of the GNU General Public License
 *    as specified in the README file that comes with the perl 3.0 kit.
 *
 * $Log:	hash.c,v $
 * Revision 3.0.1.4  90/08/09  03:50:22  lwall
 * patch19: dbmopen(name, 'filename', undef) now refrains from creating
 * 
 * Revision 3.0.1.3  90/03/27  15:59:09  lwall
 * patch16: @dbmvalues{'foo','bar'} could use the same cache entry for both values
 * 
 * Revision 3.0.1.2  89/12/21  20:03:39  lwall
 * patch7: errno may now be a macro with an lvalue
 * 
 * Revision 3.0.1.1  89/11/11  04:34:18  lwall
 * patch2: CX/UX needed to set the key each time in associative iterators
 * 
 * Revision 3.0  89/10/18  15:18:32  lwall
 * 3.0 baseline
 * 
 */

#include "EXTERN.h"
#include "perl.h"

static char coeff[] = {
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};

STR *
hfetch(tb,key,klen,lval)
register HASH *tb;
char *key;
int klen;
int lval;
{
    register char *s;
    register int i;
    register int hash;
    register HENT *entry;
    register int maxi;
    STR *str;
#ifdef SOME_DBM
    datum dkey,dcontent;
#endif

    if (!tb)
	return Nullstr;

    /* The hash function we use on symbols has to be equal to the first
     * character when taken modulo 128, so that str_reset() can be implemented
     * efficiently.  We throw in the second character and the last character
     * (times 128) so that long chains of identifiers starting with the
     * same letter don't have to be strEQ'ed within hfetch(), since it
     * compares hash values before trying strEQ().
     */
    if (!tb->tbl_coeffsize)
	hash = *key + 128 * key[1] + 128 * key[klen-1];	/* assuming klen > 0 */
    else {	/* use normal coefficients */
	if (klen < tb->tbl_coeffsize)
	    maxi = klen;
	else
	    maxi = tb->tbl_coeffsize;
	for (s=key,		i=0,	hash = 0;
			    i < maxi;
	     s++,		i++,	hash *= 5) {
	    hash += *s * coeff[i];
	}
    }

    entry = tb->tbl_array[hash & tb->tbl_max];
    for (; entry; entry = entry->hent_next) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	return entry->hent_val;
    }
#ifdef SOME_DBM
    if (tb->tbl_dbm) {
	dkey.dptr = key;
	dkey.dsize = klen;
	dcontent = dbm_fetch(tb->tbl_dbm,dkey);
	if (dcontent.dptr) {			/* found one */
	    str = Str_new(60,dcontent.dsize);
	    str_nset(str,dcontent.dptr,dcontent.dsize);
	    hstore(tb,key,klen,str,hash);		/* cache it */
	    return str;
	}
    }
#endif
    if (lval) {		/* gonna assign to this, so it better be there */
	str = Str_new(61,0);
	hstore(tb,key,klen,str,hash);
	return str;
    }
    return Nullstr;
}

bool
hstore(tb,key,klen,val,hash)
register HASH *tb;
char *key;
int klen;
STR *val;
register int hash;
{
    register char *s;
    register int i;
    register HENT *entry;
    register HENT **oentry;
    register int maxi;

    if (!tb)
	return FALSE;

    if (hash)
	;
    else if (!tb->tbl_coeffsize)
	hash = *key + 128 * key[1] + 128 * key[klen-1];
    else {	/* use normal coefficients */
	if (klen < tb->tbl_coeffsize)
	    maxi = klen;
	else
	    maxi = tb->tbl_coeffsize;
	for (s=key,		i=0,	hash = 0;
			    i < maxi;
	     s++,		i++,	hash *= 5) {
	    hash += *s * coeff[i];
	}
    }

    oentry = &(tb->tbl_array[hash & tb->tbl_max]);
    i = 1;

    for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	Safefree(entry->hent_val);
	entry->hent_val = val;
	return TRUE;
    }
    New(501,entry, 1, HENT);

    entry->hent_klen = klen;
    entry->hent_key = nsavestr(key,klen);
    entry->hent_val = val;
    entry->hent_hash = hash;
    entry->hent_next = *oentry;
    *oentry = entry;

    /* hdbmstore not necessary here because it's called from stabset() */

    if (i) {				/* initial entry? */
	tb->tbl_fill++;
#ifdef SOME_DBM
	if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
	    return FALSE;
#endif
	if (tb->tbl_fill > tb->tbl_dosplit)
	    hsplit(tb);
    }
#ifdef SOME_DBM
    else if (tb->tbl_dbm) {		/* is this just a cache for dbm file? */
	void hentdelayfree();

	entry = tb->tbl_array[hash & tb->tbl_max];
	oentry = &entry->hent_next;
	entry = *oentry;
	while (entry) {	/* trim chain down to 1 entry */
	    *oentry = entry->hent_next;
	    hentdelayfree(entry);	/* no doubt they'll want this next. */
	    entry = *oentry;
	}
    }
#endif

    return FALSE;
}

STR *
hdelete(tb,key,klen)
register HASH *tb;
char *key;
int klen;
{
    register char *s;
    register int i;
    register int hash;
    register HENT *entry;
    register HENT **oentry;
    STR *str;
    int maxi;
#ifdef SOME_DBM
    datum dkey;
#endif

    if (!tb)
	return Nullstr;
    if (!tb->tbl_coeffsize)
	hash = *key + 128 * key[1] + 128 * key[klen-1];
    else {	/* use normal coefficients */
	if (klen < tb->tbl_coeffsize)
	    maxi = klen;
	else
	    maxi = tb->tbl_coeffsize;
	for (s=key,		i=0,	hash = 0;
			    i < maxi;
	     s++,		i++,	hash *= 5) {
	    hash += *s * coeff[i];
	}
    }

    oentry = &(tb->tbl_array[hash & tb->tbl_max]);
    entry = *oentry;
    i = 1;
    for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
	if (entry->hent_hash != hash)		/* strings can't be equal */
	    continue;
	if (entry->hent_klen != klen)
	    continue;
	if (bcmp(entry->hent_key,key,klen))	/* is this it? */
	    continue;
	*oentry = entry->hent_next;
	str = str_static(entry->hent_val);
	hentfree(entry);
	if (i)
	    tb->tbl_fill--;
#ifdef SOME_DBM
      do_dbm_delete:
	if (tb->tbl_dbm) {
	    dkey.dptr = key;
	    dkey.dsize = klen;
	    dbm_delete(tb->tbl_dbm,dkey);
	}
#endif
	return str;
    }
#ifdef SOME_DBM
    str = Nullstr;
    goto do_dbm_delete;
#else
    return Nullstr;
#endif
}

hsplit(tb)
HASH *tb;
{
    int oldsize = tb->tbl_max + 1;
    register int newsize = oldsize * 2;
    register int i;
    register HENT **a;
    register HENT **b;
    register HENT *entry;
    register HENT **oentry;

    a = tb->tbl_array;
    Renew(a, newsize, HENT*);
    Zero(&a[oldsize], oldsize, HENT*);		/* zero 2nd half*/
    tb->tbl_max = --newsize;
    tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
    tb->tbl_array = a;

    for (i=0; i<oldsize; i++,a++) {
	if (!*a)				/* non-existent */
	    continue;
	b = a+oldsize;
	for (oentry = a, entry = *a; entry; entry = *oentry) {
	    if ((entry->hent_hash & newsize) != i) {
		*oentry = entry->hent_next;
		entry->hent_next = *b;
		if (!*b)
		    tb->tbl_fill++;
		*b = entry;
		continue;
	    }
	    else
		oentry = &entry->hent_next;
	}
	if (!*a)				/* everything moved */
	    tb->tbl_fill--;
    }
}

HASH *
hnew(lookat)
unsigned int lookat;
{
    register HASH *tb;

    Newz(502,tb, 1, HASH);
    if (lookat) {
	tb->tbl_coeffsize = lookat;
	tb->tbl_max = 7;		/* it's a normal associative array */
	tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
    }
    else {
	tb->tbl_max = 127;		/* it's a symbol table */
	tb->tbl_dosplit = 128;		/* so never split */
    }
    Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
    tb->tbl_fill = 0;
#ifdef SOME_DBM
    tb->tbl_dbm = 0;
#endif
    (void)hiterinit(tb);	/* so each() will start off right */
    return tb;
}

void
hentfree(hent)
register HENT *hent;
{
    if (!hent)
	return;
    str_free(hent->hent_val);
    Safefree(hent->hent_key);
    Safefree(hent);
}

void
hentdelayfree(hent)
register HENT *hent;
{
    if (!hent)
	return;
    str_2static(hent->hent_val);	/* free between statements */
    Safefree(hent->hent_key);
    Safefree(hent);
}

void
hclear(tb)
register HASH *tb;
{
    register HENT *hent;
    register HENT *ohent = Null(HENT*);

    if (!tb)
	return;
    (void)hiterinit(tb);
    while (hent = hiternext(tb)) {	/* concise but not very efficient */
	hentfree(ohent);
	ohent = hent;
    }
    hentfree(ohent);
    tb->tbl_fill = 0;
#ifndef lint
    (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
#endif
}

void
hfree(tb)
register HASH *tb;
{
    register HENT *hent;
    register HENT *ohent = Null(HENT*);

    if (!tb)
	return;
    (void)hiterinit(tb);
    while (hent = hiternext(tb)) {
	hentfree(ohent);
	ohent = hent;
    }
    hentfree(ohent);
    Safefree(tb->tbl_array);
    Safefree(tb);
}

int
hiterinit(tb)
register HASH *tb;
{
    tb->tbl_riter = -1;
    tb->tbl_eiter = Null(HENT*);
    return tb->tbl_fill;
}

HENT *
hiternext(tb)
register HASH *tb;
{
    register HENT *entry;
#ifdef SOME_DBM
    datum key;
#endif

    entry = tb->tbl_eiter;
#ifdef SOME_DBM
    if (tb->tbl_dbm) {
	if (entry) {
#ifdef NDBM
#ifdef _CX_UX
	    key.dptr = entry->hent_key;
	    key.dsize = entry->hent_klen;
	    key = dbm_nextkey(tb->tbl_dbm, key);
#else
	    key = dbm_nextkey(tb->tbl_dbm);
#endif /* _CX_UX */
#else
	    key.dptr = entry->hent_key;
	    key.dsize = entry->hent_klen;
	    key = nextkey(key);
#endif
	}
	else {
	    Newz(504,entry, 1, HENT);
	    tb->tbl_eiter = entry;
	    key = dbm_firstkey(tb->tbl_dbm);
	}
	entry->hent_key = key.dptr;
	entry->hent_klen = key.dsize;
	if (!key.dptr) {
	    if (entry->hent_val)
		str_free(entry->hent_val);
	    Safefree(entry);
	    tb->tbl_eiter = Null(HENT*);
	    return Null(HENT*);
	}
	return entry;
    }
#endif
    do {
	if (entry)
	    entry = entry->hent_next;
	if (!entry) {
	    tb->tbl_riter++;
	    if (tb->tbl_riter > tb->tbl_max) {
		tb->tbl_riter = -1;
		break;
	    }
	    entry = tb->tbl_array[tb->tbl_riter];
	}
    } while (!entry);

    tb->tbl_eiter = entry;
    return entry;
}

char *
hiterkey(entry,retlen)
register HENT *entry;
int *retlen;
{
    *retlen = entry->hent_klen;
    return entry->hent_key;
}

STR *
hiterval(tb,entry)
register HASH *tb;
register HENT *entry;
{
#ifdef SOME_DBM
    datum key, content;

    if (tb->tbl_dbm) {
	key.dptr = entry->hent_key;
	key.dsize = entry->hent_klen;
	content = dbm_fetch(tb->tbl_dbm,key);
	if (!entry->hent_val)
	    entry->hent_val = Str_new(62,0);
	str_nset(entry->hent_val,content.dptr,content.dsize);
    }
#endif
    return entry->hent_val;
}

#ifdef SOME_DBM
#if	defined(FCNTL) && ! defined(O_CREAT)
#include <fcntl.h>
#endif

#ifndef O_RDONLY
#define O_RDONLY 0
#endif
#ifndef O_RDWR
#define O_RDWR 2
#endif
#ifndef O_CREAT
#define O_CREAT 01000
#endif

#ifndef NDBM
static int dbmrefcnt = 0;
#endif

bool
hdbmopen(tb,fname,mode)
register HASH *tb;
char *fname;
int mode;
{
    if (!tb)
	return FALSE;
#ifndef NDBM
    if (tb->tbl_dbm)	/* never really closed it */
	return TRUE;
#endif
    if (tb->tbl_dbm) {
	hdbmclose(tb);
	tb->tbl_dbm = 0;
    }
    hclear(tb);
#ifdef NDBM
    if (mode >= 0)
	tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
    if (!tb->tbl_dbm)
	tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
#else
    if (dbmrefcnt++)
	fatal("Old dbm can only open one database");
    sprintf(buf,"%s.dir",fname);
    if (stat(buf, &statbuf) < 0) {
	if (mode < 0 || close(creat(buf,mode)) < 0)
	    return FALSE;
	sprintf(buf,"%s.pag",fname);
	if (close(creat(buf,mode)) < 0)
	    return FALSE;
    }
    tb->tbl_dbm = dbminit(fname) >= 0;
#endif
    return tb->tbl_dbm != 0;
}

void
hdbmclose(tb)
register HASH *tb;
{
    if (tb && tb->tbl_dbm) {
#ifdef NDBM
	dbm_close(tb->tbl_dbm);
	tb->tbl_dbm = 0;
#else
	/* dbmrefcnt--;  */	/* doesn't work, rats */
#endif
    }
    else if (dowarn)
	warn("Close on unopened dbm file");
}

bool
hdbmstore(tb,key,klen,str)
register HASH *tb;
char *key;
int klen;
register STR *str;
{
    datum dkey, dcontent;
    int error;

    if (!tb || !tb->tbl_dbm)
	return FALSE;
    dkey.dptr = key;
    dkey.dsize = klen;
    dcontent.dptr = str_get(str);
    dcontent.dsize = str->str_cur;
    error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
    if (error) {
	if (errno == EPERM)
	    fatal("No write permission to dbm file");
	warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
#ifdef NDBM
        dbm_clearerr(tb->tbl_dbm);
#endif
    }
    return !error;
}
#endif /* SOME_DBM */
Commit	Line	Data
154e51a4	1	/* $Header: hash.c,v 3.0.1.4 90/08/09 03:50:22 lwall Locked $
a687059c	2	*
	3	* Copyright (c) 1989, Larry Wall
	4	*
	5	* You may distribute under the terms of the GNU General Public License
	6	* as specified in the README file that comes with the perl 3.0 kit.
8d063cd8	7	*
8d063cd8	8	* $Log: hash.c,v $
154e51a4	9	* Revision 3.0.1.4 90/08/09 03:50:22 lwall
	10	* patch19: dbmopen(name, 'filename', undef) now refrains from creating
	11	*
b1248f16	12	* Revision 3.0.1.3 90/03/27 15:59:09 lwall
	13	* patch16: @dbmvalues{'foo','bar'} could use the same cache entry for both values
	14	*
663a0e37	15	* Revision 3.0.1.2 89/12/21 20:03:39 lwall
	16	* patch7: errno may now be a macro with an lvalue
	17	*
bf38876a	18	* Revision 3.0.1.1 89/11/11 04:34:18 lwall
	19	* patch2: CX/UX needed to set the key each time in associative iterators
	20	*
a687059c	21	* Revision 3.0 89/10/18 15:18:32 lwall
a687059c	22	* 3.0 baseline
8d063cd8	23	*
	24	*/
	25
8d063cd8	26	#include "EXTERN.h"
8d063cd8	27	#include "perl.h"
8d063cd8	28
154e51a4	29	static char coeff[] = {
	30	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	31	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	32	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	33	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	34	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	35	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	36	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
	37	61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
	38
8d063cd8	39	STR *
a687059c	40	hfetch(tb,key,klen,lval)
8d063cd8	41	register HASH *tb;
8d063cd8	42	char *key;
a687059c	43	int klen;
a687059c	44	int lval;
8d063cd8	45	{
	46	register char *s;
	47	register int i;
	48	register int hash;
	49	register HENT *entry;
a687059c	50	register int maxi;
	51	STR *str;
	52	#ifdef SOME_DBM
	53	datum dkey,dcontent;
	54	#endif
8d063cd8	55
	56	if (!tb)
	57	return Nullstr;
a687059c	58
	59	/* The hash function we use on symbols has to be equal to the first
	60	* character when taken modulo 128, so that str_reset() can be implemented
	61	* efficiently. We throw in the second character and the last character
	62	* (times 128) so that long chains of identifiers starting with the
	63	* same letter don't have to be strEQ'ed within hfetch(), since it
	64	* compares hash values before trying strEQ().
	65	*/
	66	if (!tb->tbl_coeffsize)
	67	hash = key + 128 key[1] + 128 * key[klen-1]; /* assuming klen > 0 */
	68	else { /* use normal coefficients */
	69	if (klen < tb->tbl_coeffsize)
	70	maxi = klen;
	71	else
	72	maxi = tb->tbl_coeffsize;
	73	for (s=key, i=0, hash = 0;
	74	i < maxi;
	75	s++, i++, hash *= 5) {
	76	hash += s coeff[i];
	77	}
8d063cd8	78	}
a687059c	79
8d063cd8	80	entry = tb->tbl_array[hash & tb->tbl_max];
	81	for (; entry; entry = entry->hent_next) {
	82	if (entry->hent_hash != hash) /* strings can't be equal */
	83	continue;
a687059c	84	if (entry->hent_klen != klen)
	85	continue;
	86	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
8d063cd8	87	continue;
	88	return entry->hent_val;
	89	}
a687059c	90	#ifdef SOME_DBM
	91	if (tb->tbl_dbm) {
	92	dkey.dptr = key;
	93	dkey.dsize = klen;
	94	dcontent = dbm_fetch(tb->tbl_dbm,dkey);
	95	if (dcontent.dptr) { /* found one */
	96	str = Str_new(60,dcontent.dsize);
	97	str_nset(str,dcontent.dptr,dcontent.dsize);
	98	hstore(tb,key,klen,str,hash); /* cache it */
	99	return str;
	100	}
	101	}
	102	#endif
	103	if (lval) { /* gonna assign to this, so it better be there */
	104	str = Str_new(61,0);
	105	hstore(tb,key,klen,str,hash);
	106	return str;
	107	}
8d063cd8	108	return Nullstr;
	109	}
	110
	111	bool
a687059c	112	hstore(tb,key,klen,val,hash)
8d063cd8	113	register HASH *tb;
8d063cd8	114	char *key;
a687059c	115	int klen;
8d063cd8	116	STR *val;
a687059c	117	register int hash;
8d063cd8	118	{
	119	register char *s;
	120	register int i;
8d063cd8	121	register HENT *entry;
8d063cd8	122	register HENT **oentry;
a687059c	123	register int maxi;
8d063cd8	124
	125	if (!tb)
	126	return FALSE;
a687059c	127
	128	if (hash)
	129	;
	130	else if (!tb->tbl_coeffsize)
	131	hash = key + 128 key[1] + 128 * key[klen-1];
	132	else { /* use normal coefficients */
	133	if (klen < tb->tbl_coeffsize)
	134	maxi = klen;
	135	else
	136	maxi = tb->tbl_coeffsize;
	137	for (s=key, i=0, hash = 0;
	138	i < maxi;
	139	s++, i++, hash *= 5) {
	140	hash += s coeff[i];
	141	}
8d063cd8	142	}
	143
	144	oentry = &(tb->tbl_array[hash & tb->tbl_max]);
	145	i = 1;
	146
	147	for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
	148	if (entry->hent_hash != hash) /* strings can't be equal */
	149	continue;
a687059c	150	if (entry->hent_klen != klen)
	151	continue;
	152	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
8d063cd8	153	continue;
a687059c	154	Safefree(entry->hent_val);
8d063cd8	155	entry->hent_val = val;
	156	return TRUE;
	157	}
a687059c	158	New(501,entry, 1, HENT);
8d063cd8	159
a687059c	160	entry->hent_klen = klen;
a687059c	161	entry->hent_key = nsavestr(key,klen);
8d063cd8	162	entry->hent_val = val;
	163	entry->hent_hash = hash;
	164	entry->hent_next = *oentry;
	165	*oentry = entry;
	166
a687059c	167	/* hdbmstore not necessary here because it's called from stabset() */
a687059c	168
8d063cd8	169	if (i) { /* initial entry? */
8d063cd8	170	tb->tbl_fill++;
a687059c	171	#ifdef SOME_DBM
	172	if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
	173	return FALSE;
	174	#endif
	175	if (tb->tbl_fill > tb->tbl_dosplit)
8d063cd8	176	hsplit(tb);
8d063cd8	177	}
a687059c	178	#ifdef SOME_DBM
a687059c	179	else if (tb->tbl_dbm) { /* is this just a cache for dbm file? */
b1248f16	180	void hentdelayfree();
b1248f16	181
a687059c	182	entry = tb->tbl_array[hash & tb->tbl_max];
	183	oentry = &entry->hent_next;
	184	entry = *oentry;
	185	while (entry) { /* trim chain down to 1 entry */
	186	*oentry = entry->hent_next;
b1248f16	187	hentdelayfree(entry); /* no doubt they'll want this next. */
a687059c	188	entry = *oentry;
	189	}
	190	}
	191	#endif
8d063cd8	192
	193	return FALSE;
	194	}
	195
378cc40b	196	STR *
a687059c	197	hdelete(tb,key,klen)
8d063cd8	198	register HASH *tb;
8d063cd8	199	char *key;
a687059c	200	int klen;
8d063cd8	201	{
	202	register char *s;
	203	register int i;
	204	register int hash;
	205	register HENT *entry;
	206	register HENT **oentry;
378cc40b	207	STR *str;
a687059c	208	int maxi;
	209	#ifdef SOME_DBM
	210	datum dkey;
	211	#endif
8d063cd8	212
8d063cd8	213	if (!tb)
378cc40b	214	return Nullstr;
a687059c	215	if (!tb->tbl_coeffsize)
	216	hash = key + 128 key[1] + 128 * key[klen-1];
	217	else { /* use normal coefficients */
	218	if (klen < tb->tbl_coeffsize)
	219	maxi = klen;
	220	else
	221	maxi = tb->tbl_coeffsize;
	222	for (s=key, i=0, hash = 0;
	223	i < maxi;
	224	s++, i++, hash *= 5) {
	225	hash += s coeff[i];
	226	}
8d063cd8	227	}
	228
	229	oentry = &(tb->tbl_array[hash & tb->tbl_max]);
	230	entry = *oentry;
	231	i = 1;
378cc40b	232	for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
8d063cd8	233	if (entry->hent_hash != hash) /* strings can't be equal */
8d063cd8	234	continue;
a687059c	235	if (entry->hent_klen != klen)
	236	continue;
	237	if (bcmp(entry->hent_key,key,klen)) /* is this it? */
8d063cd8	238	continue;
8d063cd8	239	*oentry = entry->hent_next;
378cc40b	240	str = str_static(entry->hent_val);
378cc40b	241	hentfree(entry);
8d063cd8	242	if (i)
8d063cd8	243	tb->tbl_fill--;
a687059c	244	#ifdef SOME_DBM
	245	do_dbm_delete:
	246	if (tb->tbl_dbm) {
	247	dkey.dptr = key;
	248	dkey.dsize = klen;
	249	dbm_delete(tb->tbl_dbm,dkey);
	250	}
	251	#endif
378cc40b	252	return str;
8d063cd8	253	}
a687059c	254	#ifdef SOME_DBM
	255	str = Nullstr;
	256	goto do_dbm_delete;
	257	#else
378cc40b	258	return Nullstr;
a687059c	259	#endif
8d063cd8	260	}
8d063cd8	261
	262	hsplit(tb)
	263	HASH *tb;
	264	{
	265	int oldsize = tb->tbl_max + 1;
	266	register int newsize = oldsize * 2;
	267	register int i;
	268	register HENT **a;
	269	register HENT **b;
	270	register HENT *entry;
	271	register HENT **oentry;
	272
a687059c	273	a = tb->tbl_array;
	274	Renew(a, newsize, HENT*);
	275	Zero(&a[oldsize], oldsize, HENT); / zero 2nd half*/
8d063cd8	276	tb->tbl_max = --newsize;
a687059c	277	tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
8d063cd8	278	tb->tbl_array = a;
	279
	280	for (i=0; i<oldsize; i++,a++) {
	281	if (!a) / non-existent */
	282	continue;
	283	b = a+oldsize;
	284	for (oentry = a, entry = a; entry; entry = oentry) {
	285	if ((entry->hent_hash & newsize) != i) {
	286	*oentry = entry->hent_next;
	287	entry->hent_next = *b;
	288	if (!*b)
	289	tb->tbl_fill++;
	290	*b = entry;
	291	continue;
	292	}
	293	else
	294	oentry = &entry->hent_next;
	295	}
	296	if (!a) / everything moved */
	297	tb->tbl_fill--;
	298	}
	299	}
	300
	301	HASH *
a687059c	302	hnew(lookat)
a687059c	303	unsigned int lookat;
8d063cd8	304	{
a687059c	305	register HASH *tb;
8d063cd8	306
a687059c	307	Newz(502,tb, 1, HASH);
	308	if (lookat) {
	309	tb->tbl_coeffsize = lookat;
	310	tb->tbl_max = 7; /* it's a normal associative array */
	311	tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
	312	}
	313	else {
	314	tb->tbl_max = 127; /* it's a symbol table */
	315	tb->tbl_dosplit = 128; /* so never split */
	316	}
	317	Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
8d063cd8	318	tb->tbl_fill = 0;
a687059c	319	#ifdef SOME_DBM
	320	tb->tbl_dbm = 0;
	321	#endif
	322	(void)hiterinit(tb); /* so each() will start off right */
8d063cd8	323	return tb;
	324	}
	325
378cc40b	326	void
	327	hentfree(hent)
	328	register HENT *hent;
	329	{
	330	if (!hent)
	331	return;
	332	str_free(hent->hent_val);
a687059c	333	Safefree(hent->hent_key);
a687059c	334	Safefree(hent);
378cc40b	335	}
	336
	337	void
b1248f16	338	hentdelayfree(hent)
	339	register HENT *hent;
	340	{
	341	if (!hent)
	342	return;
	343	str_2static(hent->hent_val); /* free between statements */
	344	Safefree(hent->hent_key);
	345	Safefree(hent);
	346	}
	347
	348	void
378cc40b	349	hclear(tb)
	350	register HASH *tb;
	351	{
	352	register HENT *hent;
	353	register HENT ohent = Null(HENT);
	354
	355	if (!tb)
	356	return;
a687059c	357	(void)hiterinit(tb);
378cc40b	358	while (hent = hiternext(tb)) { /* concise but not very efficient */
	359	hentfree(ohent);
	360	ohent = hent;
	361	}
	362	hentfree(ohent);
	363	tb->tbl_fill = 0;
a687059c	364	#ifndef lint
	365	(void)bzero((char)tb->tbl_array, (tb->tbl_max + 1) sizeof(HENT*));
	366	#endif
378cc40b	367	}
378cc40b	368
378cc40b	369	void
378cc40b	370	hfree(tb)
a687059c	371	register HASH *tb;
378cc40b	372	{
a687059c	373	register HENT *hent;
	374	register HENT ohent = Null(HENT);
	375
378cc40b	376	if (!tb)
a687059c	377	return;
a687059c	378	(void)hiterinit(tb);
378cc40b	379	while (hent = hiternext(tb)) {
	380	hentfree(ohent);
	381	ohent = hent;
	382	}
	383	hentfree(ohent);
a687059c	384	Safefree(tb->tbl_array);
a687059c	385	Safefree(tb);
378cc40b	386	}
8d063cd8	387
a687059c	388	int
8d063cd8	389	hiterinit(tb)
	390	register HASH *tb;
	391	{
	392	tb->tbl_riter = -1;
	393	tb->tbl_eiter = Null(HENT*);
	394	return tb->tbl_fill;
	395	}
	396
	397	HENT *
	398	hiternext(tb)
	399	register HASH *tb;
	400	{
	401	register HENT *entry;
a687059c	402	#ifdef SOME_DBM
	403	datum key;
	404	#endif
8d063cd8	405
8d063cd8	406	entry = tb->tbl_eiter;
a687059c	407	#ifdef SOME_DBM
	408	if (tb->tbl_dbm) {
	409	if (entry) {
	410	#ifdef NDBM
	411	#ifdef _CX_UX
bf38876a	412	key.dptr = entry->hent_key;
bf38876a	413	key.dsize = entry->hent_klen;
a687059c	414	key = dbm_nextkey(tb->tbl_dbm, key);
	415	#else
	416	key = dbm_nextkey(tb->tbl_dbm);
	417	#endif /* _CX_UX */
	418	#else
	419	key.dptr = entry->hent_key;
	420	key.dsize = entry->hent_klen;
	421	key = nextkey(key);
	422	#endif
	423	}
	424	else {
	425	Newz(504,entry, 1, HENT);
	426	tb->tbl_eiter = entry;
	427	key = dbm_firstkey(tb->tbl_dbm);
	428	}
	429	entry->hent_key = key.dptr;
	430	entry->hent_klen = key.dsize;
	431	if (!key.dptr) {
	432	if (entry->hent_val)
	433	str_free(entry->hent_val);
	434	Safefree(entry);
	435	tb->tbl_eiter = Null(HENT*);
	436	return Null(HENT*);
	437	}
	438	return entry;
	439	}
	440	#endif
8d063cd8	441	do {
	442	if (entry)
	443	entry = entry->hent_next;
	444	if (!entry) {
	445	tb->tbl_riter++;
	446	if (tb->tbl_riter > tb->tbl_max) {
	447	tb->tbl_riter = -1;
	448	break;
	449	}
	450	entry = tb->tbl_array[tb->tbl_riter];
	451	}
	452	} while (!entry);
	453
	454	tb->tbl_eiter = entry;
	455	return entry;
	456	}
	457
	458	char *
a687059c	459	hiterkey(entry,retlen)
8d063cd8	460	register HENT *entry;
a687059c	461	int *retlen;
8d063cd8	462	{
a687059c	463	*retlen = entry->hent_klen;
8d063cd8	464	return entry->hent_key;
	465	}
	466
	467	STR *
a687059c	468	hiterval(tb,entry)
a687059c	469	register HASH *tb;
8d063cd8	470	register HENT *entry;
8d063cd8	471	{
a687059c	472	#ifdef SOME_DBM
	473	datum key, content;
	474
	475	if (tb->tbl_dbm) {
	476	key.dptr = entry->hent_key;
	477	key.dsize = entry->hent_klen;
	478	content = dbm_fetch(tb->tbl_dbm,key);
	479	if (!entry->hent_val)
	480	entry->hent_val = Str_new(62,0);
	481	str_nset(entry->hent_val,content.dptr,content.dsize);
	482	}
	483	#endif
8d063cd8	484	return entry->hent_val;
8d063cd8	485	}
a687059c	486
	487	#ifdef SOME_DBM
	488	#if defined(FCNTL) && ! defined(O_CREAT)
	489	#include <fcntl.h>
	490	#endif
	491
	492	#ifndef O_RDONLY
	493	#define O_RDONLY 0
	494	#endif
	495	#ifndef O_RDWR
	496	#define O_RDWR 2
	497	#endif
	498	#ifndef O_CREAT
	499	#define O_CREAT 01000
	500	#endif
	501
	502	#ifndef NDBM
	503	static int dbmrefcnt = 0;
	504	#endif
	505
	506	bool
	507	hdbmopen(tb,fname,mode)
	508	register HASH *tb;
	509	char *fname;
	510	int mode;
	511	{
	512	if (!tb)
	513	return FALSE;
	514	#ifndef NDBM
	515	if (tb->tbl_dbm) /* never really closed it */
	516	return TRUE;
	517	#endif
154e51a4	518	if (tb->tbl_dbm) {
a687059c	519	hdbmclose(tb);
154e51a4	520	tb->tbl_dbm = 0;
154e51a4	521	}
a687059c	522	hclear(tb);
a687059c	523	#ifdef NDBM
154e51a4	524	if (mode >= 0)
	525	tb->tbl_dbm = dbm_open(fname, O_RDWR\|O_CREAT, mode);
	526	if (!tb->tbl_dbm)
	527	tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
a687059c	528	#else
	529	if (dbmrefcnt++)
	530	fatal("Old dbm can only open one database");
	531	sprintf(buf,"%s.dir",fname);
	532	if (stat(buf, &statbuf) < 0) {
154e51a4	533	if (mode < 0 \|\| close(creat(buf,mode)) < 0)
a687059c	534	return FALSE;
	535	sprintf(buf,"%s.pag",fname);
	536	if (close(creat(buf,mode)) < 0)
	537	return FALSE;
	538	}
	539	tb->tbl_dbm = dbminit(fname) >= 0;
	540	#endif
	541	return tb->tbl_dbm != 0;
	542	}
	543
	544	void
	545	hdbmclose(tb)
	546	register HASH *tb;
	547	{
	548	if (tb && tb->tbl_dbm) {
	549	#ifdef NDBM
	550	dbm_close(tb->tbl_dbm);
	551	tb->tbl_dbm = 0;
	552	#else
	553	/* dbmrefcnt--; / / doesn't work, rats */
	554	#endif
	555	}
	556	else if (dowarn)
	557	warn("Close on unopened dbm file");
	558	}
	559
	560	bool
	561	hdbmstore(tb,key,klen,str)
	562	register HASH *tb;
	563	char *key;
	564	int klen;
	565	register STR *str;
	566	{
	567	datum dkey, dcontent;
	568	int error;
	569
	570	if (!tb \|\| !tb->tbl_dbm)
	571	return FALSE;
	572	dkey.dptr = key;
	573	dkey.dsize = klen;
	574	dcontent.dptr = str_get(str);
	575	dcontent.dsize = str->str_cur;
	576	error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
	577	if (error) {
	578	if (errno == EPERM)
	579	fatal("No write permission to dbm file");
	580	warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
	581	#ifdef NDBM
	582	dbm_clearerr(tb->tbl_dbm);
	583	#endif
	584	}
	585	return !error;
	586	}
	587	#endif /* SOME_DBM */