1 /* $RCSfile: hash.c,v $$Revision: 4.0.1.1 $$Date: 91/06/07 11:10:11 $
3 * Copyright (c) 1991, Larry Wall
5 * You may distribute under the terms of either the GNU General Public
6 * License or the Artistic License, as specified in the README file.
9 * Revision 4.0.1.1 91/06/07 11:10:11 lwall
10 * patch4: new copyright notice
12 * Revision 4.0 91/03/20 01:22:26 lwall
20 static char coeff[] = {
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 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
27 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
28 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
30 static void hfreeentries();
33 hfetch(tb,key,klen,lval)
53 Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
58 /* The hash function we use on symbols has to be equal to the first
59 * character when taken modulo 128, so that str_reset() can be implemented
60 * efficiently. We throw in the second character and the last character
61 * (times 128) so that long chains of identifiers starting with the
62 * same letter don't have to be strEQ'ed within hfetch(), since it
63 * compares hash values before trying strEQ().
65 if (!tb->tbl_coeffsize)
66 hash = *key + 128 * key[1] + 128 * key[klen-1]; /* assuming klen > 0 */
67 else { /* use normal coefficients */
68 if (klen < tb->tbl_coeffsize)
71 maxi = tb->tbl_coeffsize;
72 for (s=key, i=0, hash = 0;
74 s++, i++, hash *= 5) {
75 hash += *s * coeff[i];
79 entry = tb->tbl_array[hash & tb->tbl_max];
80 for (; entry; entry = entry->hent_next) {
81 if (entry->hent_hash != hash) /* strings can't be equal */
83 if (entry->hent_klen != klen)
85 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
87 return entry->hent_val;
94 dcontent = gdbm_fetch(tb->tbl_dbm,dkey);
96 dcontent = dbm_fetch(tb->tbl_dbm,dkey);
98 if (dcontent.dptr) { /* found one */
99 str = Str_new(60,dcontent.dsize);
100 str_nset(str,dcontent.dptr,dcontent.dsize);
101 hstore(tb,key,klen,str,hash); /* cache it */
106 if (lval) { /* gonna assign to this, so it better be there */
108 hstore(tb,key,klen,str,hash);
115 hstore(tb,key,klen,val,hash)
124 register HENT *entry;
125 register HENT **oentry;
133 else if (!tb->tbl_coeffsize)
134 hash = *key + 128 * key[1] + 128 * key[klen-1];
135 else { /* use normal coefficients */
136 if (klen < tb->tbl_coeffsize)
139 maxi = tb->tbl_coeffsize;
140 for (s=key, i=0, hash = 0;
142 s++, i++, hash *= 5) {
143 hash += *s * coeff[i];
148 Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);
150 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
153 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
154 if (entry->hent_hash != hash) /* strings can't be equal */
156 if (entry->hent_klen != klen)
158 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
160 Safefree(entry->hent_val);
161 entry->hent_val = val;
164 New(501,entry, 1, HENT);
166 entry->hent_klen = klen;
167 entry->hent_key = nsavestr(key,klen);
168 entry->hent_val = val;
169 entry->hent_hash = hash;
170 entry->hent_next = *oentry;
173 /* hdbmstore not necessary here because it's called from stabset() */
175 if (i) { /* initial entry? */
178 if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
181 if (tb->tbl_fill > tb->tbl_dosplit)
185 else if (tb->tbl_dbm) { /* is this just a cache for dbm file? */
186 void hentdelayfree();
188 entry = tb->tbl_array[hash & tb->tbl_max];
189 oentry = &entry->hent_next;
191 while (entry) { /* trim chain down to 1 entry */
192 *oentry = entry->hent_next;
193 hentdelayfree(entry); /* no doubt they'll want this next. */
211 register HENT *entry;
212 register HENT **oentry;
219 if (!tb || !tb->tbl_array)
221 if (!tb->tbl_coeffsize)
222 hash = *key + 128 * key[1] + 128 * key[klen-1];
223 else { /* use normal coefficients */
224 if (klen < tb->tbl_coeffsize)
227 maxi = tb->tbl_coeffsize;
228 for (s=key, i=0, hash = 0;
230 s++, i++, hash *= 5) {
231 hash += *s * coeff[i];
235 oentry = &(tb->tbl_array[hash & tb->tbl_max]);
238 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
239 if (entry->hent_hash != hash) /* strings can't be equal */
241 if (entry->hent_klen != klen)
243 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
245 *oentry = entry->hent_next;
246 str = str_mortal(entry->hent_val);
256 gdbm_delete(tb->tbl_dbm,dkey);
258 dbm_delete(tb->tbl_dbm,dkey);
275 int oldsize = tb->tbl_max + 1;
276 register int newsize = oldsize * 2;
280 register HENT *entry;
281 register HENT **oentry;
284 Renew(a, newsize, HENT*);
285 Zero(&a[oldsize], oldsize, HENT*); /* zero 2nd half*/
286 tb->tbl_max = --newsize;
287 tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
290 for (i=0; i<oldsize; i++,a++) {
291 if (!*a) /* non-existent */
294 for (oentry = a, entry = *a; entry; entry = *oentry) {
295 if ((entry->hent_hash & newsize) != i) {
296 *oentry = entry->hent_next;
297 entry->hent_next = *b;
304 oentry = &entry->hent_next;
306 if (!*a) /* everything moved */
317 Newz(502,tb, 1, HASH);
319 tb->tbl_coeffsize = lookat;
320 tb->tbl_max = 7; /* it's a normal associative array */
321 tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
324 tb->tbl_max = 127; /* it's a symbol table */
325 tb->tbl_dosplit = 128; /* so never split */
331 (void)hiterinit(tb); /* so each() will start off right */
341 str_free(hent->hent_val);
342 Safefree(hent->hent_key);
352 str_2mortal(hent->hent_val); /* free between statements */
353 Safefree(hent->hent_key);
364 hfreeentries(tb,dodbm);
368 (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
373 hfreeentries(tb,dodbm)
378 register HENT *ohent = Null(HENT*);
393 if (!tb || !tb->tbl_array)
396 if ((old_dbm = tb->tbl_dbm) && dodbm) {
398 while (dkey = gdbm_firstkey(tb->tbl_dbm), dkey.dptr) {
400 while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
404 nextdkey = gdbm_nextkey(tb->tbl_dbm, dkey);
408 nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
410 nextdkey = dbm_nextkey(tb->tbl_dbm);
413 nextdkey = nextkey(dkey);
417 gdbm_delete(tb->tbl_dbm,dkey);
419 dbm_delete(tb->tbl_dbm,dkey);
422 } while (dkey.dptr); /* one way or another, this works */
425 tb->tbl_dbm = 0; /* now clear just cache */
428 while (hent = hiternext(tb)) { /* concise but not very efficient */
434 tb->tbl_dbm = old_dbm;
445 hfreeentries(tb,dodbm);
446 Safefree(tb->tbl_array);
455 tb->tbl_eiter = Null(HENT*);
463 register HENT *entry;
468 entry = tb->tbl_eiter;
473 key.dptr = entry->hent_key;
474 key.dsize = entry->hent_klen;
475 key = gdbm_nextkey(tb->tbl_dbm, key);
479 key.dptr = entry->hent_key;
480 key.dsize = entry->hent_klen;
481 key = dbm_nextkey(tb->tbl_dbm, key);
483 key = dbm_nextkey(tb->tbl_dbm);
486 key.dptr = entry->hent_key;
487 key.dsize = entry->hent_klen;
493 Newz(504,entry, 1, HENT);
494 tb->tbl_eiter = entry;
496 key = gdbm_firstkey(tb->tbl_dbm);
498 key = dbm_firstkey(tb->tbl_dbm);
501 entry->hent_key = key.dptr;
502 entry->hent_klen = key.dsize;
505 str_free(entry->hent_val);
507 tb->tbl_eiter = Null(HENT*);
514 Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
517 entry = entry->hent_next;
520 if (tb->tbl_riter > tb->tbl_max) {
524 entry = tb->tbl_array[tb->tbl_riter];
528 tb->tbl_eiter = entry;
533 hiterkey(entry,retlen)
534 register HENT *entry;
537 *retlen = entry->hent_klen;
538 return entry->hent_key;
544 register HENT *entry;
550 key.dptr = entry->hent_key;
551 key.dsize = entry->hent_klen;
553 content = gdbm_fetch(tb->tbl_dbm,key);
555 content = dbm_fetch(tb->tbl_dbm,key);
557 if (!entry->hent_val)
558 entry->hent_val = Str_new(62,0);
559 str_nset(entry->hent_val,content.dptr,content.dsize);
562 return entry->hent_val;
572 # include <sys/file.h>
583 #define O_CREAT 01000
587 static int dbmrefcnt = 0;
591 hdbmopen(tb,fname,mode)
599 if (tb->tbl_dbm) /* never really closed it */
606 hclear(tb, FALSE); /* clear cache */
609 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRCREAT,mode, (void *) NULL);
611 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRITER, mode, (void *) NULL);
613 tb->tbl_dbm = gdbm_open(fname, 0, GDBM_READER, mode, (void *) NULL);
617 tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
619 tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
621 tb->tbl_dbm = dbm_open(fname, O_RDONLY, mode);
624 fatal("Old dbm can only open one database");
625 sprintf(buf,"%s.dir",fname);
626 if (stat(buf, &statbuf) < 0) {
627 if (mode < 0 || close(creat(buf,mode)) < 0)
629 sprintf(buf,"%s.pag",fname);
630 if (close(creat(buf,mode)) < 0)
633 tb->tbl_dbm = dbminit(fname) >= 0;
636 if (!tb->tbl_array && tb->tbl_dbm != 0)
637 Newz(507,tb->tbl_array, tb->tbl_max + 1, HENT*);
638 return tb->tbl_dbm != 0;
645 if (tb && tb->tbl_dbm) {
647 gdbm_close(tb->tbl_dbm);
651 dbm_close(tb->tbl_dbm);
654 /* dbmrefcnt--; */ /* doesn't work, rats */
659 warn("Close on unopened dbm file");
663 hdbmstore(tb,key,klen,str)
669 datum dkey, dcontent;
672 if (!tb || !tb->tbl_dbm)
676 dcontent.dptr = str_get(str);
677 dcontent.dsize = str->str_cur;
679 error = gdbm_store(tb->tbl_dbm, dkey, dcontent, GDBM_REPLACE);
681 error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
685 fatal("No write permission to dbm file");
686 warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
688 dbm_clearerr(tb->tbl_dbm);
693 #endif /* SOME_DBM */