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

/* $RCSfile: hash.c,v $$Revision: 4.0.1.3 $$Date: 92/06/08 13:26:29 $
 *
 *    Copyright (c) 1991, Larry Wall
 *
 *    You may distribute under the terms of either the GNU General Public
 *    License or the Artistic License, as specified in the README file.
 *
 * $Log:	hash.c,v $
 * Revision 4.0.1.3  92/06/08  13:26:29  lwall
 * patch20: removed implicit int declarations on functions
 * patch20: delete could cause %array to give too low a count of buckets filled
 * patch20: hash tables now split only if the memory is available to do so
 * 
 * Revision 4.0.1.2  91/11/05  17:24:13  lwall
 * patch11: saberized perl
 * 
 * Revision 4.0.1.1  91/06/07  11:10:11  lwall
 * patch4: new copyright notice
 * 
 * Revision 4.0  91/03/20  01:22:26  lwall
 * 4.0 baseline.
 * 
 */

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

static void hsplit();

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;			/*SUPPRESS 8*/
	     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;
#ifdef HAS_GDBM
	dcontent = gdbm_fetch(tb->tbl_dbm,dkey);
#else
	dcontent = dbm_fetch(tb->tbl_dbm,dkey);
#endif
	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)
	/*SUPPRESS 530*/
	;
    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;			/*SUPPRESS 8*/
	     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;			/*SUPPRESS 8*/
	     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;
	if (i && !*oentry)
	    tb->tbl_fill--;
	str = str_mortal(entry->hent_val);
	hentfree(entry);
#ifdef SOME_DBM
      do_dbm_delete:
	if (tb->tbl_dbm) {
	    dkey.dptr = key;
	    dkey.dsize = klen;
#ifdef HAS_GDBM
	    gdbm_delete(tb->tbl_dbm,dkey);
#else
	    dbm_delete(tb->tbl_dbm,dkey);
#endif
	}
#endif
	return str;
    }
#ifdef SOME_DBM
    str = Nullstr;
    goto do_dbm_delete;
#else
    return Nullstr;
#endif
}

static void
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;
    nomemok = TRUE;
    Renew(a, newsize, HENT*);
    nomemok = FALSE;
    if (!a) {
	tb->tbl_dosplit = tb->tbl_max + 1;	/* never split again */
	return;
    }
    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_2mortal(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)memzero((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 HAS_GDBM
    GDBM_FILE old_dbm;
#else
#ifdef HAS_NDBM
    DBM *old_dbm;
#else
    int old_dbm;
#endif
#endif
#endif

    if (!tb || !tb->tbl_array)
	return;
#ifdef SOME_DBM
    if ((old_dbm = tb->tbl_dbm) && dodbm) {
#ifdef HAS_GDBM
	while (dkey = gdbm_firstkey(tb->tbl_dbm), dkey.dptr) {
#else
	while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
#endif
	    do {
#ifdef HAS_GDBM
		nextdkey = gdbm_nextkey(tb->tbl_dbm, dkey);
#else
#ifdef HAS_NDBM
#ifdef _CX_UX
		nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
#else
		nextdkey = dbm_nextkey(tb->tbl_dbm);
#endif
#else
		nextdkey = nextkey(dkey);
#endif
#endif
#ifdef HAS_GDBM
		gdbm_delete(tb->tbl_dbm,dkey);
#else
		dbm_delete(tb->tbl_dbm,dkey);
#endif
		dkey = nextdkey;
	    } while (dkey.dptr);	/* one way or another, this works */
	}
    }
    tb->tbl_dbm = 0;			/* now clear just cache */
#endif
    (void)hiterinit(tb);
    /*SUPPRESS 560*/
    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 HAS_GDBM
	    key.dptr = entry->hent_key;
	    key.dsize = entry->hent_klen;
	    key = gdbm_nextkey(tb->tbl_dbm, key);
#else
#ifdef HAS_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
#endif
	}
	else {
	    Newz(504,entry, 1, HENT);
	    tb->tbl_eiter = entry;
#ifdef HAS_GDBM
	    key = gdbm_firstkey(tb->tbl_dbm);
#else
	    key = dbm_firstkey(tb->tbl_dbm);
#endif
	}
	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;
#ifdef HAS_GDBM
	content = gdbm_fetch(tb->tbl_dbm,key);
#else
	content = dbm_fetch(tb->tbl_dbm,key);
#endif
	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

#ifndef O_CREAT
#  ifdef I_FCNTL
#    include <fcntl.h>
#  endif
#  ifdef I_SYS_FILE
#    include <sys/file.h>
#  endif
#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

#ifdef HAS_ODBM
static int dbmrefcnt = 0;
#endif

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