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

/* $Header: hash.c,v 3.0.1.3 90/03/27 15:59:09 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.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"

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