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

/* $Header: hash.c,v 3.0.1.7 90/10/20 02:10:00 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.7  90/10/20  02:10:00  lwall
 * patch37: hash.c called ndbm function on dbm system
 * 
 * Revision 3.0.1.6  90/10/15  17:32:52  lwall
 * patch29: non-existent array values no longer cause core dumps
 * patch29: %foo = () will now clear dbm files
 * patch29: dbm files couldn't be opened read only
 * patch29: the cache array for dbm files wasn't correctly created on fetches
 * 
 * Revision 3.0.1.5  90/08/13  22:18:27  lwall
 * patch28: defined(@array) and defined(%array) didn't work right
 * 
 * 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};

static void hfreeentries();

STR *
hfetch(tb,key,klen,lval)
register HASH *tb;
char *key;
unsigned 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 &str_undef;
    if (!tb->tbl_array) {
	if (lval)
	    Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
	else
	    return &str_undef;
    }

    /* 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 &str_undef;
}

bool
hstore(tb,key,klen,val,hash)
register HASH *tb;
char *key;
unsigned 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];
	}
    }

    if (!tb->tbl_array)
	Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);

    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;
unsigned 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 || !tb->tbl_array)
	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 */
    }
    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,dodbm)
register HASH *tb;
int dodbm;
{
    if (!tb)
	return;
    hfreeentries(tb,dodbm);
    tb->tbl_fill = 0;
#ifndef lint
    if (tb->tbl_array)
	(void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
#endif
}

static void
hfreeentries(tb,dodbm)
register HASH *tb;
int dodbm;
{
    register HENT *hent;
    register HENT *ohent = Null(HENT*);
#ifdef SOME_DBM
    datum dkey;
    datum nextdkey;
#ifdef NDBM
    DBM *old_dbm;
#else
    int old_dbm;
#endif
#endif

    if (!tb || !tb->tbl_array)
	return;
#ifdef SOME_DBM
    if ((old_dbm = tb->tbl_dbm) && dodbm) {
	while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
	    do {
#ifdef NDBM
#ifdef _CX_UX
		nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
#else
		nextdkey = dbm_nextkey(tb->tbl_dbm);
#endif
#else
		nextdkey = nextkey(dkey);
#endif
		dbm_delete(tb->tbl_dbm,dkey);
		dkey = nextdkey;
	    } while (dkey.dptr);	/* one way or another, this works */
	}
    }
    tb->tbl_dbm = 0;			/* now clear just cache */
#endif
    (void)hiterinit(tb);
    while (hent = hiternext(tb)) {	/* concise but not very efficient */
	hentfree(ohent);
	ohent = hent;
    }
    hentfree(ohent);
#ifdef SOME_DBM
    tb->tbl_dbm = old_dbm;
#endif
}

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