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

/* $Header: hash.c,v 4.0 91/03/20 01:22:26 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 4.0  91/03/20  01:22:26  lwall
 * 4.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;
#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)
	;
    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_mortal(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;
#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
}

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