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')) {
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 mg_copy((SV*)hv, val, key, klen);
122 hash = hash * 33 + *s++;
126 Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
128 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
131 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
132 if (entry->hent_hash != hash) /* strings can't be equal */
134 if (entry->hent_klen != klen)
136 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
138 SvREFCNT_dec(entry->hent_val);
139 entry->hent_val = val;
140 return &entry->hent_val;
142 New(501,entry, 1, HE);
144 entry->hent_klen = klen;
145 entry->hent_key = nsavestr(key,klen);
146 entry->hent_val = val;
147 entry->hent_hash = hash;
148 entry->hent_next = *oentry;
152 if (i) { /* initial entry? */
154 if (xhv->xhv_keys > xhv->xhv_max)
158 return &entry->hent_val;
162 hv_delete(hv,key,klen)
172 register HE **oentry;
177 if (SvRMAGICAL(hv)) {
178 sv = *hv_fetch(hv, key, klen, TRUE);
181 xhv = (XPVHV*)SvANY(hv);
188 hash = hash * 33 + *s++;
190 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
193 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
194 if (entry->hent_hash != hash) /* strings can't be equal */
196 if (entry->hent_klen != klen)
198 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
200 *oentry = entry->hent_next;
203 sv = sv_mortalcopy(entry->hent_val);
215 register XPVHV* xhv = (XPVHV*)SvANY(hv);
216 I32 oldsize = xhv->xhv_max + 1;
217 register I32 newsize = oldsize * 2;
222 register HE **oentry;
224 a = (HE**)xhv->xhv_array;
226 Renew(a, newsize, HE*);
228 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
229 xhv->xhv_max = --newsize;
230 xhv->xhv_array = (char*)a;
232 for (i=0; i<oldsize; i++,a++) {
233 if (!*a) /* non-existent */
236 for (oentry = a, entry = *a; entry; entry = *oentry) {
237 if ((entry->hent_hash & newsize) != i) {
238 *oentry = entry->hent_next;
239 entry->hent_next = *b;
246 oentry = &entry->hent_next;
248 if (!*a) /* everything moved */
261 sv_upgrade(hv, SVt_PVHV);
262 xhv = (XPVHV*)SvANY(hv);
265 xhv->xhv_max = 7; /* start with 8 buckets */
268 (void)hv_iterinit(hv); /* so each() will start off right */
278 SvREFCNT_dec(hent->hent_val);
279 Safefree(hent->hent_key);
289 sv_2mortal(hent->hent_val); /* free between statements */
290 Safefree(hent->hent_key);
301 xhv = (XPVHV*)SvANY(hv);
305 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
314 register HE *ohent = Null(HE*);
318 xhv = (XPVHV*)SvANY(hv);
321 (void)hv_iterinit(hv);
323 while (hent = hv_iternext(hv)) { /* concise but not very efficient */
339 xhv = (XPVHV*)SvANY(hv);
341 Safefree(xhv->xhv_array);
343 Safefree(HvNAME(hv));
347 xhv->xhv_max = 7; /* it's a normal associative array */
349 (void)hv_iterinit(hv); /* so each() will start off right */
356 register XPVHV* xhv = (XPVHV*)SvANY(hv);
358 xhv->xhv_eiter = Null(HE*);
359 return xhv->xhv_fill;
371 croak("Bad associative array");
372 xhv = (XPVHV*)SvANY(hv);
373 entry = xhv->xhv_eiter;
375 if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
376 SV *key = sv_newmortal();
378 sv_setpvn(key, entry->hent_key, entry->hent_klen);
380 Newz(504,entry, 1, HE);
381 xhv->xhv_eiter = entry;
383 magic_nextpack(hv,mg,key);
386 entry->hent_key = SvPV(key, len);
387 entry->hent_klen = len;
393 SvREFCNT_dec(entry->hent_val);
395 xhv->xhv_eiter = Null(HE*);
400 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
403 entry = entry->hent_next;
406 if (xhv->xhv_riter > xhv->xhv_max) {
410 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
414 xhv->xhv_eiter = entry;
419 hv_iterkey(entry,retlen)
423 *retlen = entry->hent_klen;
424 return entry->hent_key;
432 if (SvRMAGICAL(hv)) {
433 if (mg_find((SV*)hv,'P')) {
434 SV* sv = sv_newmortal();
435 mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
441 return entry->hent_val;
445 hv_magic(hv, gv, how)
450 sv_magic((SV*)hv, (SV*)gv, how, 0, 0);