diff options
Diffstat (limited to 'hash.c')
-rw-r--r-- | hash.c | 712 |
1 files changed, 0 insertions, 712 deletions
diff --git a/hash.c b/hash.c deleted file mode 100644 index 3cae533e8f..0000000000 --- a/hash.c +++ /dev/null @@ -1,712 +0,0 @@ -/* $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 */ |