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)
52 if (mg_find((SV*)hv,'P')) {
53 sv = sv_2mortal(NEWSV(61,0));
54 mg_copy((SV*)hv, sv, key, klen);
64 xhv = (XPVHV*)SvANY(hv);
65 if (!xhv->xhv_array) {
67 Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
76 hash = hash * 33 + *s++;
78 entry = ((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
79 for (; entry; entry = entry->hent_next) {
80 if (entry->hent_hash != hash) /* strings can't be equal */
82 if (entry->hent_klen != klen)
84 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
86 return &entry->hent_val;
88 if (lval) { /* gonna assign to this, so it better be there */
90 return hv_store(hv,key,klen,sv,hash);
96 hv_store(hv,key,klen,val,hash)
107 register HE **oentry;
112 xhv = (XPVHV*)SvANY(hv);
114 MAGIC* mg = SvMAGIC(hv);
115 mg_copy((SV*)hv, val, key, klen);
123 hash = hash * 33 + *s++;
127 Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
129 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
132 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
133 if (entry->hent_hash != hash) /* strings can't be equal */
135 if (entry->hent_klen != klen)
137 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
139 sv_free(entry->hent_val);
140 entry->hent_val = val;
141 return &entry->hent_val;
143 New(501,entry, 1, HE);
145 entry->hent_klen = klen;
146 entry->hent_key = nsavestr(key,klen);
147 entry->hent_val = val;
148 entry->hent_hash = hash;
149 entry->hent_next = *oentry;
153 if (i) { /* initial entry? */
155 if (xhv->xhv_keys > xhv->xhv_max)
159 return &entry->hent_val;
163 hv_delete(hv,key,klen)
173 register HE **oentry;
179 sv = *hv_fetch(hv, key, klen, TRUE);
182 xhv = (XPVHV*)SvANY(hv);
189 hash = hash * 33 + *s++;
191 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
194 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
195 if (entry->hent_hash != hash) /* strings can't be equal */
197 if (entry->hent_klen != klen)
199 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
201 *oentry = entry->hent_next;
204 sv = sv_mortalcopy(entry->hent_val);
216 register XPVHV* xhv = (XPVHV*)SvANY(hv);
217 I32 oldsize = xhv->xhv_max + 1;
218 register I32 newsize = oldsize * 2;
223 register HE **oentry;
225 a = (HE**)xhv->xhv_array;
227 Renew(a, newsize, HE*);
229 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
230 xhv->xhv_max = --newsize;
231 xhv->xhv_array = (char*)a;
233 for (i=0; i<oldsize; i++,a++) {
234 if (!*a) /* non-existent */
237 for (oentry = a, entry = *a; entry; entry = *oentry) {
238 if ((entry->hent_hash & newsize) != i) {
239 *oentry = entry->hent_next;
240 entry->hent_next = *b;
247 oentry = &entry->hent_next;
249 if (!*a) /* everything moved */
262 sv_upgrade(hv, SVt_PVHV);
263 xhv = (XPVHV*)SvANY(hv);
266 xhv->xhv_max = 7; /* start with 8 buckets */
269 (void)hv_iterinit(hv); /* so each() will start off right */
279 sv_free(hent->hent_val);
280 Safefree(hent->hent_key);
290 sv_2mortal(hent->hent_val); /* free between statements */
291 Safefree(hent->hent_key);
302 xhv = (XPVHV*)SvANY(hv);
306 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
315 register HE *ohent = Null(HE*);
319 xhv = (XPVHV*)SvANY(hv);
322 (void)hv_iterinit(hv);
324 while (hent = hv_iternext(hv)) { /* concise but not very efficient */
340 xhv = (XPVHV*)SvANY(hv);
342 Safefree(xhv->xhv_array);
344 xhv->xhv_max = 7; /* it's a normal associative array */
346 (void)hv_iterinit(hv); /* so each() will start off right */
356 Safefree(HvARRAY(hv));
364 register XPVHV* xhv = (XPVHV*)SvANY(hv);
366 xhv->xhv_eiter = Null(HE*);
367 return xhv->xhv_fill;
379 croak("Bad associative array");
380 xhv = (XPVHV*)SvANY(hv);
381 entry = xhv->xhv_eiter;
383 if (SvMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
384 SV *key = sv_2mortal(NEWSV(0,0));
386 sv_setpvn(key, entry->hent_key, entry->hent_klen);
388 Newz(504,entry, 1, HE);
389 xhv->xhv_eiter = entry;
391 magic_nextpack(hv,mg,key);
394 entry->hent_key = SvPV(key, len);
395 entry->hent_klen = len;
401 sv_free(entry->hent_val);
403 xhv->xhv_eiter = Null(HE*);
408 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
411 entry = entry->hent_next;
414 if (xhv->xhv_riter > xhv->xhv_max) {
418 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
422 xhv->xhv_eiter = entry;
427 hv_iterkey(entry,retlen)
431 *retlen = entry->hent_klen;
432 return entry->hent_key;
441 if (mg_find((SV*)hv,'P')) {
442 SV* sv = sv_2mortal(NEWSV(61,0));
443 mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
449 return entry->hent_val;
453 hv_magic(hv, gv, how)
458 sv_magic((SV*)hv, (SV*)gv, how, 0, 0);