1 /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:21:48 $
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.1 92/08/07 18:21:48 lwall
11 * Revision 4.0.1.3 92/06/08 13:26:29 lwall
12 * patch20: removed implicit int declarations on functions
13 * patch20: delete could cause %array to give too low a count of buckets filled
14 * patch20: hash tables now split only if the memory is available to do so
16 * Revision 4.0.1.2 91/11/05 17:24:13 lwall
17 * patch11: saberized perl
19 * Revision 4.0.1.1 91/06/07 11:10:11 lwall
20 * patch4: new copyright notice
22 * Revision 4.0 91/03/20 01:22:26 lwall
32 static void hfreeentries();
35 hv_fetch(hv,key,klen,lval)
54 xhv = (XPVHV*)SvANY(hv);
55 if (!xhv->xhv_array) {
57 Newz(503,xhv->xhv_array, xhv->xhv_max + 1, HE*);
62 /* The hash function we use on symbols has to be equal to the first
63 * character when taken modulo 128, so that sv_reset() can be implemented
64 * efficiently. We throw in the second character and the last character
65 * (times 128) so that long chains of identifiers starting with the
66 * same letter don't have to be strEQ'ed within hv_fetch(), since it
67 * compares hash values before trying strEQ().
69 if (!xhv->xhv_coeffsize && klen)
70 hash = klen ? *key + 128 * key[1] + 128 * key[klen-1] : 0;
71 else { /* use normal coefficients */
72 if (klen < xhv->xhv_coeffsize)
75 maxi = xhv->xhv_coeffsize;
76 for (s=key, i=0, hash = 0;
77 i < maxi; /*SUPPRESS 8*/
78 s++, i++, hash *= 5) {
79 hash += *s * coeff[i];
83 entry = xhv->xhv_array[hash & xhv->xhv_max];
84 for (; entry; entry = entry->hent_next) {
85 if (entry->hent_hash != hash) /* strings can't be equal */
87 if (entry->hent_klen != klen)
89 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
91 return &entry->hent_val;
98 dcontent = gdbm_fetch(xhv->xhv_dbm,dkey);
100 dcontent = dbm_fetch(xhv->xhv_dbm,dkey);
102 if (dcontent.dptr) { /* found one */
103 sv = NEWSV(60,dcontent.dsize);
104 sv_setpvn(sv,dcontent.dptr,dcontent.dsize);
105 return hv_store(hv,key,klen,sv,hash); /* cache it */
109 if (lval) { /* gonna assign to this, so it better be there */
111 return hv_store(hv,key,klen,sv,hash);
117 hv_store(hv,key,klen,val,hash)
128 register HE **oentry;
134 xhv = (XPVHV*)SvANY(hv);
138 else if (!xhv->xhv_coeffsize && klen)
139 hash = klen ? *key + 128 * key[1] + 128 * key[klen-1] : 0;
140 else { /* use normal coefficients */
141 if (klen < xhv->xhv_coeffsize)
144 maxi = xhv->xhv_coeffsize;
145 for (s=key, i=0, hash = 0;
146 i < maxi; /*SUPPRESS 8*/
147 s++, i++, hash *= 5) {
148 hash += *s * coeff[i];
153 Newz(505,xhv->xhv_array, xhv->xhv_max + 1, HE*);
155 oentry = &(xhv->xhv_array[hash & xhv->xhv_max]);
159 MAGIC* mg = SvMAGIC(hv);
160 sv_magic(val, (SV*)hv, tolower(mg->mg_type), key, klen);
162 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
163 if (entry->hent_hash != hash) /* strings can't be equal */
165 if (entry->hent_klen != klen)
167 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
169 sv_free(entry->hent_val);
170 entry->hent_val = val;
171 return &entry->hent_val;
173 New(501,entry, 1, HE);
175 entry->hent_klen = klen;
176 entry->hent_key = nsavestr(key,klen);
177 entry->hent_val = val;
178 entry->hent_hash = hash;
179 entry->hent_next = *oentry;
182 /* hv_dbmstore not necessary here because it's called from sv_setmagic() */
184 if (i) { /* initial entry? */
187 if (xhv->xhv_dbm && xhv->xhv_max >= DBM_CACHE_MAX)
188 return &entry->hent_val;
190 if (xhv->xhv_fill > xhv->xhv_dosplit)
194 else if (xhv->xhv_dbm) { /* is this just a cache for dbm file? */
198 ent = xhv->xhv_array[hash & xhv->xhv_max];
199 oentry = &ent->hent_next;
201 while (ent) { /* trim chain down to 1 entry */
202 *oentry = ent->hent_next;
203 he_delayfree(ent); /* no doubt they'll want this next, sigh... */
209 return &entry->hent_val;
213 hv_delete(hv,key,klen)
223 register HE **oentry;
232 xhv = (XPVHV*)SvANY(hv);
235 if (!xhv->xhv_coeffsize && klen)
236 hash = klen ? *key + 128 * key[1] + 128 * key[klen-1] : 0;
237 else { /* use normal coefficients */
238 if (klen < xhv->xhv_coeffsize)
241 maxi = xhv->xhv_coeffsize;
242 for (s=key, i=0, hash = 0;
243 i < maxi; /*SUPPRESS 8*/
244 s++, i++, hash *= 5) {
245 hash += *s * coeff[i];
249 oentry = &(xhv->xhv_array[hash & xhv->xhv_max]);
252 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
253 if (entry->hent_hash != hash) /* strings can't be equal */
255 if (entry->hent_klen != klen)
257 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
259 *oentry = entry->hent_next;
262 sv = sv_mortalcopy(entry->hent_val);
270 gdbm_delete(xhv->xhv_dbm,dkey);
272 dbm_delete(xhv->xhv_dbm,dkey);
290 register XPVHV* xhv = (XPVHV*)SvANY(hv);
291 I32 oldsize = xhv->xhv_max + 1;
292 register I32 newsize = oldsize * 2;
297 register HE **oentry;
301 Renew(a, newsize, HE*);
304 xhv->xhv_dosplit = xhv->xhv_max + 1; /* never split again */
307 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
308 xhv->xhv_max = --newsize;
309 xhv->xhv_dosplit = xhv->xhv_max * FILLPCT / 100;
312 for (i=0; i<oldsize; i++,a++) {
313 if (!*a) /* non-existent */
316 for (oentry = a, entry = *a; entry; entry = *oentry) {
317 if ((entry->hent_hash & newsize) != i) {
318 *oentry = entry->hent_next;
319 entry->hent_next = *b;
326 oentry = &entry->hent_next;
328 if (!*a) /* everything moved */
342 sv_upgrade(hv, SVt_PVHV);
343 xhv = (XPVHV*)SvANY(hv);
347 xhv->xhv_coeffsize = lookat;
348 xhv->xhv_max = 7; /* it's a normal associative array */
349 xhv->xhv_dosplit = xhv->xhv_max * FILLPCT / 100;
352 xhv->xhv_max = 127; /* it's a symbol table */
353 xhv->xhv_dosplit = 128; /* so never split */
360 (void)hv_iterinit(hv); /* so each() will start off right */
370 sv_free(hent->hent_val);
371 Safefree(hent->hent_key);
381 sv_2mortal(hent->hent_val); /* free between statements */
382 Safefree(hent->hent_key);
394 xhv = (XPVHV*)SvANY(hv);
395 hfreeentries(hv,dodbm);
399 (void)memzero((char*)xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
404 hfreeentries(hv,dodbm)
410 register HE *ohent = Null(HE*);
427 xhv = (XPVHV*)SvANY(hv);
431 if ((old_dbm = xhv->xhv_dbm) && dodbm) {
433 while (dkey = gdbm_firstkey(xhv->xhv_dbm), dkey.dptr) {
435 while (dkey = dbm_firstkey(xhv->xhv_dbm), dkey.dptr) {
439 nextdkey = gdbm_nextkey(xhv->xhv_dbm, dkey);
443 nextdkey = dbm_nextkey(xhv->xhv_dbm, dkey);
445 nextdkey = dbm_nextkey(xhv->xhv_dbm);
448 nextdkey = nextkey(dkey);
452 gdbm_delete(xhv->xhv_dbm,dkey);
454 dbm_delete(xhv->xhv_dbm,dkey);
457 } while (dkey.dptr); /* one way or another, this works */
460 xhv->xhv_dbm = 0; /* now clear just cache */
462 (void)hv_iterinit(hv);
464 while (hent = hv_iternext(hv)) { /* concise but not very efficient */
470 xhv->xhv_dbm = old_dbm;
484 xhv = (XPVHV*)SvANY(hv);
485 hfreeentries(hv,dodbm);
486 Safefree(xhv->xhv_array);
488 if (xhv->xhv_coeffsize) {
489 xhv->xhv_max = 7; /* it's a normal associative array */
490 xhv->xhv_dosplit = xhv->xhv_max * FILLPCT / 100;
493 xhv->xhv_max = 127; /* it's a symbol table */
494 xhv->xhv_dosplit = 128; /* so never split */
500 (void)hv_iterinit(hv); /* so each() will start off right */
510 hfreeentries(hv,dodbm);
511 Safefree(HvARRAY(hv));
519 register XPVHV* xhv = (XPVHV*)SvANY(hv);
521 xhv->xhv_eiter = Null(HE*);
522 return xhv->xhv_fill;
536 fatal("Bad associative array");
537 xhv = (XPVHV*)SvANY(hv);
538 entry = xhv->xhv_eiter;
543 key.dptr = entry->hent_key;
544 key.dsize = entry->hent_klen;
545 key = gdbm_nextkey(xhv->xhv_dbm, key);
549 key.dptr = entry->hent_key;
550 key.dsize = entry->hent_klen;
551 key = dbm_nextkey(xhv->xhv_dbm, key);
553 key = dbm_nextkey(xhv->xhv_dbm);
556 key.dptr = entry->hent_key;
557 key.dsize = entry->hent_klen;
563 Newz(504,entry, 1, HE);
564 xhv->xhv_eiter = entry;
566 key = gdbm_firstkey(xhv->xhv_dbm);
568 key = dbm_firstkey(xhv->xhv_dbm);
571 entry->hent_key = key.dptr;
572 entry->hent_klen = key.dsize;
575 sv_free(entry->hent_val);
577 xhv->xhv_eiter = Null(HE*);
584 Newz(506,xhv->xhv_array, xhv->xhv_max + 1, HE*);
587 entry = entry->hent_next;
590 if (xhv->xhv_riter > xhv->xhv_max) {
594 entry = xhv->xhv_array[xhv->xhv_riter];
598 xhv->xhv_eiter = entry;
603 hv_iterkey(entry,retlen)
607 *retlen = entry->hent_klen;
608 return entry->hent_key;
621 fatal("Bad associative array");
622 xhv = (XPVHV*)SvANY(hv);
624 key.dptr = entry->hent_key;
625 key.dsize = entry->hent_klen;
627 content = gdbm_fetch(xhv->xhv_dbm,key);
629 content = dbm_fetch(xhv->xhv_dbm,key);
631 if (!entry->hent_val)
632 entry->hent_val = NEWSV(62,0);
633 sv_setpvn(entry->hent_val,content.dptr,content.dsize);
636 return entry->hent_val;
646 # include <sys/file.h>
657 #define OP_CREAT 01000
661 hv_dbmopen(hv,fname,mode)
669 xhv = (XPVHV*)SvANY(hv);
671 if (xhv->xhv_dbm) /* never really closed it */
678 hv_clear(hv, FALSE); /* clear cache */
681 xhv->xhv_dbm = gdbm_open(fname, 0, GDBM_WRCREAT,mode, (void *) NULL);
683 xhv->xhv_dbm = gdbm_open(fname, 0, GDBM_WRITER, mode, (void *) NULL);
685 xhv->xhv_dbm = gdbm_open(fname, 0, GDBM_READER, mode, (void *) NULL);
689 xhv->xhv_dbm = dbm_open(fname, OP_RDWR|OP_CREAT, mode);
691 xhv->xhv_dbm = dbm_open(fname, OP_RDWR, mode);
693 xhv->xhv_dbm = dbm_open(fname, OP_RDONLY, mode);
696 fatal("Old dbm can only open one database");
697 sprintf(buf,"%s.dir",fname);
698 if (stat(buf, &statbuf) < 0) {
699 if (mode < 0 || close(creat(buf,mode)) < 0)
701 sprintf(buf,"%s.pag",fname);
702 if (close(creat(buf,mode)) < 0)
705 xhv->xhv_dbm = dbminit(fname) >= 0;
708 if (!xhv->xhv_array && xhv->xhv_dbm != 0)
709 Newz(507,xhv->xhv_array, xhv->xhv_max + 1, HE*);
710 hv_magic(hv, 0, 'D');
711 return xhv->xhv_dbm != 0;
720 fatal("Bad associative array");
721 xhv = (XPVHV*)SvANY(hv);
724 gdbm_close(xhv->xhv_dbm);
728 dbm_close(xhv->xhv_dbm);
731 /* dbmrefcnt--; */ /* doesn't work, rats */
736 warn("Close on unopened dbm file");
740 hv_dbmstore(hv,key,klen,sv)
747 datum dkey, dcontent;
752 xhv = (XPVHV*)SvANY(hv);
757 dcontent.dptr = SvPVn(sv);
758 dcontent.dsize = SvCUR(sv);
760 error = gdbm_store(xhv->xhv_dbm, dkey, dcontent, GDBM_REPLACE);
762 error = dbm_store(xhv->xhv_dbm, dkey, dcontent, DBM_REPLACE);
766 fatal("No write permission to dbm file");
767 fatal("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
769 dbm_clearerr(xhv->xhv_dbm);
774 #endif /* SOME_DBM */
777 magictype = MgTYPE(magic);
786 for (i = 1; i < NSIG; i++)
787 signal(i, SIG_DFL); /* crunch, crunch, crunch */
792 sv_magic(tmpstr, (SV*)tmpgv, magic, tmps, SvCUR(sv));
793 sv_magicset(tmpstr, magic);
796 if (hv->hv_sv.sv_rare && !sv->sv_magic)
797 sv_magic(sv, (GV*)hv, hv->hv_sv.sv_rare, key, keylen);
801 hv_magic(hv, gv, how)
806 sv_magic(hv, gv, how, 0, 0);