1 /* $Header: hash.c,v 4.0 91/03/20 01:22:26 lwall Locked $
3 * Copyright (c) 1989, Larry Wall
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.
9 * Revision 4.0 91/03/20 01:22:26 lwall
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};
27 static void hfreeentries();
30 hfetch(tb,key,klen,lval)
50 Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
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().
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)
68 maxi = tb->tbl_coeffsize;
69 for (s=key, i=0, hash = 0;
71 s++, i++, hash *= 5) {
72 hash += *s * coeff[i];
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 */
80 if (entry->hent_klen != klen)
82 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
84 return entry->hent_val;
91 dcontent = gdbm_fetch(tb->tbl_dbm,dkey);
93 dcontent = dbm_fetch(tb->tbl_dbm,dkey);
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 */
103 if (lval) { /* gonna assign to this, so it better be there */
105 hstore(tb,key,klen,str,hash);
112 hstore(tb,key,klen,val,hash)
121 register HENT *entry;
122 register HENT **oentry;
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)
136 maxi = tb->tbl_coeffsize;
137 for (s=key, i=0, hash = 0;
139 s++, i++, hash *= 5) {
140 hash += *s * coeff[i];
145 Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);
147 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
150 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
151 if (entry->hent_hash != hash) /* strings can't be equal */
153 if (entry->hent_klen != klen)
155 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
157 Safefree(entry->hent_val);
158 entry->hent_val = val;
161 New(501,entry, 1, HENT);
163 entry->hent_klen = klen;
164 entry->hent_key = nsavestr(key,klen);
165 entry->hent_val = val;
166 entry->hent_hash = hash;
167 entry->hent_next = *oentry;
170 /* hdbmstore not necessary here because it's called from stabset() */
172 if (i) { /* initial entry? */
175 if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
178 if (tb->tbl_fill > tb->tbl_dosplit)
182 else if (tb->tbl_dbm) { /* is this just a cache for dbm file? */
183 void hentdelayfree();
185 entry = tb->tbl_array[hash & tb->tbl_max];
186 oentry = &entry->hent_next;
188 while (entry) { /* trim chain down to 1 entry */
189 *oentry = entry->hent_next;
190 hentdelayfree(entry); /* no doubt they'll want this next. */
208 register HENT *entry;
209 register HENT **oentry;
216 if (!tb || !tb->tbl_array)
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)
224 maxi = tb->tbl_coeffsize;
225 for (s=key, i=0, hash = 0;
227 s++, i++, hash *= 5) {
228 hash += *s * coeff[i];
232 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
235 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
236 if (entry->hent_hash != hash) /* strings can't be equal */
238 if (entry->hent_klen != klen)
240 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
242 *oentry = entry->hent_next;
243 str = str_mortal(entry->hent_val);
253 gdbm_delete(tb->tbl_dbm,dkey);
255 dbm_delete(tb->tbl_dbm,dkey);
272 int oldsize = tb->tbl_max + 1;
273 register int newsize = oldsize * 2;
277 register HENT *entry;
278 register HENT **oentry;
281 Renew(a, newsize, HENT*);
282 Zero(&a[oldsize], oldsize, HENT*); /* zero 2nd half*/
283 tb->tbl_max = --newsize;
284 tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
287 for (i=0; i<oldsize; i++,a++) {
288 if (!*a) /* non-existent */
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;
301 oentry = &entry->hent_next;
303 if (!*a) /* everything moved */
314 Newz(502,tb, 1, HASH);
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;
321 tb->tbl_max = 127; /* it's a symbol table */
322 tb->tbl_dosplit = 128; /* so never split */
328 (void)hiterinit(tb); /* so each() will start off right */
338 str_free(hent->hent_val);
339 Safefree(hent->hent_key);
349 str_2mortal(hent->hent_val); /* free between statements */
350 Safefree(hent->hent_key);
361 hfreeentries(tb,dodbm);
365 (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
370 hfreeentries(tb,dodbm)
375 register HENT *ohent = Null(HENT*);
390 if (!tb || !tb->tbl_array)
393 if ((old_dbm = tb->tbl_dbm) && dodbm) {
395 while (dkey = gdbm_firstkey(tb->tbl_dbm), dkey.dptr) {
397 while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
401 nextdkey = gdbm_nextkey(tb->tbl_dbm, dkey);
405 nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
407 nextdkey = dbm_nextkey(tb->tbl_dbm);
410 nextdkey = nextkey(dkey);
414 gdbm_delete(tb->tbl_dbm,dkey);
416 dbm_delete(tb->tbl_dbm,dkey);
419 } while (dkey.dptr); /* one way or another, this works */
422 tb->tbl_dbm = 0; /* now clear just cache */
425 while (hent = hiternext(tb)) { /* concise but not very efficient */
431 tb->tbl_dbm = old_dbm;
442 hfreeentries(tb,dodbm);
443 Safefree(tb->tbl_array);
452 tb->tbl_eiter = Null(HENT*);
460 register HENT *entry;
465 entry = tb->tbl_eiter;
470 key.dptr = entry->hent_key;
471 key.dsize = entry->hent_klen;
472 key = gdbm_nextkey(tb->tbl_dbm, key);
476 key.dptr = entry->hent_key;
477 key.dsize = entry->hent_klen;
478 key = dbm_nextkey(tb->tbl_dbm, key);
480 key = dbm_nextkey(tb->tbl_dbm);
483 key.dptr = entry->hent_key;
484 key.dsize = entry->hent_klen;
490 Newz(504,entry, 1, HENT);
491 tb->tbl_eiter = entry;
493 key = gdbm_firstkey(tb->tbl_dbm);
495 key = dbm_firstkey(tb->tbl_dbm);
498 entry->hent_key = key.dptr;
499 entry->hent_klen = key.dsize;
502 str_free(entry->hent_val);
504 tb->tbl_eiter = Null(HENT*);
511 Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
514 entry = entry->hent_next;
517 if (tb->tbl_riter > tb->tbl_max) {
521 entry = tb->tbl_array[tb->tbl_riter];
525 tb->tbl_eiter = entry;
530 hiterkey(entry,retlen)
531 register HENT *entry;
534 *retlen = entry->hent_klen;
535 return entry->hent_key;
541 register HENT *entry;
547 key.dptr = entry->hent_key;
548 key.dsize = entry->hent_klen;
550 content = gdbm_fetch(tb->tbl_dbm,key);
552 content = dbm_fetch(tb->tbl_dbm,key);
554 if (!entry->hent_val)
555 entry->hent_val = Str_new(62,0);
556 str_nset(entry->hent_val,content.dptr,content.dsize);
559 return entry->hent_val;
569 # include <sys/file.h>
580 #define O_CREAT 01000
584 static int dbmrefcnt = 0;
588 hdbmopen(tb,fname,mode)
596 if (tb->tbl_dbm) /* never really closed it */
603 hclear(tb, FALSE); /* clear cache */
606 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRCREAT,mode, (void *) NULL);
608 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRITER, mode, (void *) NULL);
610 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_READER, mode, (void *) NULL);
614 tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
616 tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
618 tb->tbl_dbm = dbm_open(fname, O_RDONLY, mode);
621 fatal("Old dbm can only open one database");
622 sprintf(buf,"%s.dir",fname);
623 if (stat(buf, &statbuf) < 0) {
624 if (mode < 0 || close(creat(buf,mode)) < 0)
626 sprintf(buf,"%s.pag",fname);
627 if (close(creat(buf,mode)) < 0)
630 tb->tbl_dbm = dbminit(fname) >= 0;
633 if (!tb->tbl_array && tb->tbl_dbm != 0)
634 Newz(507,tb->tbl_array, tb->tbl_max + 1, HENT*);
635 return tb->tbl_dbm != 0;
642 if (tb && tb->tbl_dbm) {
644 gdbm_close(tb->tbl_dbm);
648 dbm_close(tb->tbl_dbm);
651 /* dbmrefcnt--; */ /* doesn't work, rats */
656 warn("Close on unopened dbm file");
660 hdbmstore(tb,key,klen,str)
666 datum dkey, dcontent;
669 if (!tb || !tb->tbl_dbm)
673 dcontent.dptr = str_get(str);
674 dcontent.dsize = str->str_cur;
676 error = gdbm_store(tb->tbl_dbm, dkey, dcontent, GDBM_REPLACE);
678 error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
682 fatal("No write permission to dbm file");
683 warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
685 dbm_clearerr(tb->tbl_dbm);
690 #endif /* SOME_DBM */