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

/* $Header: hash.c,v 3.0 89/10/18 15:18:32 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  89/10/18  15:18:32  lwall
 * 3.0 baseline
 * 
 */

#include "EXTERN.h"
#include "perl.h"
#include <errno.h>

extern int errno;

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