This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
perl 5.0 alpha 5
[perl5.git] / hv.c
CommitLineData
79072805
LW
1/* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:21:48 $
2 *
3 * Copyright (c) 1991, Larry Wall
4 *
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.
7 *
8 * $Log: hash.c,v $
9 * Revision 4.1 92/08/07 18:21:48 lwall
10 *
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
15 *
16 * Revision 4.0.1.2 91/11/05 17:24:13 lwall
17 * patch11: saberized perl
18 *
19 * Revision 4.0.1.1 91/06/07 11:10:11 lwall
20 * patch4: new copyright notice
21 *
22 * Revision 4.0 91/03/20 01:22:26 lwall
23 * 4.0 baseline.
24 *
25 */
26
27#include "EXTERN.h"
28#include "perl.h"
29
30static void hsplit();
31
32static void hfreeentries();
33
34SV**
35hv_fetch(hv,key,klen,lval)
36HV *hv;
37char *key;
38U32 klen;
39I32 lval;
40{
41 register XPVHV* xhv;
42 register char *s;
43 register I32 i;
44 register I32 hash;
45 register HE *entry;
79072805 46 SV *sv;
79072805
LW
47
48 if (!hv)
49 return 0;
463ee0b2
LW
50
51 if (SvMAGICAL(hv)) {
52 if (mg_find((SV*)hv,'P')) {
53 sv = sv_2mortal(NEWSV(61,0));
54 mg_copy((SV*)hv, sv, key, klen);
55 if (!lval) {
56 mg_get(sv);
57 sv_unmagic(sv,'p');
58 }
59 Sv = sv;
60 return &Sv;
61 }
62 }
63
79072805
LW
64 xhv = (XPVHV*)SvANY(hv);
65 if (!xhv->xhv_array) {
66 if (lval)
463ee0b2 67 Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
79072805
LW
68 else
69 return 0;
70 }
71
463ee0b2
LW
72 i = klen;
73 hash = 0;
74 s = key;
75 while (i--)
76 hash = hash * 33 + *s++;
79072805 77
463ee0b2 78 entry = ((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
79072805
LW
79 for (; entry; entry = entry->hent_next) {
80 if (entry->hent_hash != hash) /* strings can't be equal */
81 continue;
82 if (entry->hent_klen != klen)
83 continue;
84 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
85 continue;
86 return &entry->hent_val;
87 }
79072805
LW
88 if (lval) { /* gonna assign to this, so it better be there */
89 sv = NEWSV(61,0);
90 return hv_store(hv,key,klen,sv,hash);
91 }
92 return 0;
93}
94
95SV**
96hv_store(hv,key,klen,val,hash)
97HV *hv;
98char *key;
99U32 klen;
100SV *val;
93a17b20 101register U32 hash;
79072805
LW
102{
103 register XPVHV* xhv;
104 register char *s;
105 register I32 i;
106 register HE *entry;
107 register HE **oentry;
79072805
LW
108
109 if (!hv)
110 return 0;
111
112 xhv = (XPVHV*)SvANY(hv);
463ee0b2
LW
113 if (SvMAGICAL(hv)) {
114 MAGIC* mg = SvMAGIC(hv);
115 mg_copy((SV*)hv, val, key, klen);
116 if (!xhv->xhv_array)
117 return 0;
118 }
119 if (!hash) {
120 i = klen;
121 s = key;
122 while (i--)
123 hash = hash * 33 + *s++;
79072805
LW
124 }
125
126 if (!xhv->xhv_array)
463ee0b2 127 Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
79072805 128
463ee0b2 129 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
79072805
LW
130 i = 1;
131
79072805
LW
132 for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
133 if (entry->hent_hash != hash) /* strings can't be equal */
134 continue;
135 if (entry->hent_klen != klen)
136 continue;
137 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
138 continue;
139 sv_free(entry->hent_val);
140 entry->hent_val = val;
141 return &entry->hent_val;
142 }
143 New(501,entry, 1, HE);
144
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;
150 *oentry = entry;
151
463ee0b2 152 xhv->xhv_keys++;
79072805 153 if (i) { /* initial entry? */
463ee0b2
LW
154 ++xhv->xhv_fill;
155 if (xhv->xhv_keys > xhv->xhv_max)
79072805
LW
156 hsplit(hv);
157 }
79072805
LW
158
159 return &entry->hent_val;
160}
161
162SV *
163hv_delete(hv,key,klen)
164HV *hv;
165char *key;
166U32 klen;
167{
168 register XPVHV* xhv;
169 register char *s;
170 register I32 i;
171 register I32 hash;
172 register HE *entry;
173 register HE **oentry;
174 SV *sv;
79072805
LW
175
176 if (!hv)
177 return Nullsv;
463ee0b2
LW
178 if (SvMAGICAL(hv)) {
179 sv = *hv_fetch(hv, key, klen, TRUE);
180 mg_clear(sv);
181 }
79072805
LW
182 xhv = (XPVHV*)SvANY(hv);
183 if (!xhv->xhv_array)
184 return Nullsv;
463ee0b2
LW
185 i = klen;
186 hash = 0;
187 s = key;
188 while (i--)
189 hash = hash * 33 + *s++;
79072805 190
463ee0b2 191 oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
79072805
LW
192 entry = *oentry;
193 i = 1;
194 for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
195 if (entry->hent_hash != hash) /* strings can't be equal */
196 continue;
197 if (entry->hent_klen != klen)
198 continue;
199 if (bcmp(entry->hent_key,key,klen)) /* is this it? */
200 continue;
201 *oentry = entry->hent_next;
202 if (i && !*oentry)
203 xhv->xhv_fill--;
204 sv = sv_mortalcopy(entry->hent_val);
205 he_free(entry);
463ee0b2 206 --xhv->xhv_keys;
79072805
LW
207 return sv;
208 }
79072805 209 return Nullsv;
79072805
LW
210}
211
212static void
213hsplit(hv)
214HV *hv;
215{
216 register XPVHV* xhv = (XPVHV*)SvANY(hv);
217 I32 oldsize = xhv->xhv_max + 1;
218 register I32 newsize = oldsize * 2;
219 register I32 i;
220 register HE **a;
221 register HE **b;
222 register HE *entry;
223 register HE **oentry;
224
463ee0b2 225 a = (HE**)xhv->xhv_array;
79072805
LW
226 nomemok = TRUE;
227 Renew(a, newsize, HE*);
228 nomemok = FALSE;
79072805
LW
229 Zero(&a[oldsize], oldsize, HE*); /* zero 2nd half*/
230 xhv->xhv_max = --newsize;
463ee0b2 231 xhv->xhv_array = (char*)a;
79072805
LW
232
233 for (i=0; i<oldsize; i++,a++) {
234 if (!*a) /* non-existent */
235 continue;
236 b = a+oldsize;
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;
241 if (!*b)
242 xhv->xhv_fill++;
243 *b = entry;
244 continue;
245 }
246 else
247 oentry = &entry->hent_next;
248 }
249 if (!*a) /* everything moved */
250 xhv->xhv_fill--;
251 }
252}
253
254HV *
463ee0b2 255newHV()
79072805
LW
256{
257 register HV *hv;
258 register XPVHV* xhv;
259
260 Newz(502,hv, 1, HV);
261 SvREFCNT(hv) = 1;
262 sv_upgrade(hv, SVt_PVHV);
263 xhv = (XPVHV*)SvANY(hv);
264 SvPOK_off(hv);
265 SvNOK_off(hv);
463ee0b2 266 xhv->xhv_max = 7; /* start with 8 buckets */
79072805
LW
267 xhv->xhv_fill = 0;
268 xhv->xhv_pmroot = 0;
79072805
LW
269 (void)hv_iterinit(hv); /* so each() will start off right */
270 return hv;
271}
272
273void
274he_free(hent)
275register HE *hent;
276{
277 if (!hent)
278 return;
279 sv_free(hent->hent_val);
280 Safefree(hent->hent_key);
281 Safefree(hent);
282}
283
284void
285he_delayfree(hent)
286register HE *hent;
287{
288 if (!hent)
289 return;
290 sv_2mortal(hent->hent_val); /* free between statements */
291 Safefree(hent->hent_key);
292 Safefree(hent);
293}
294
295void
463ee0b2 296hv_clear(hv)
79072805 297HV *hv;
79072805
LW
298{
299 register XPVHV* xhv;
300 if (!hv)
301 return;
302 xhv = (XPVHV*)SvANY(hv);
463ee0b2 303 hfreeentries(hv);
79072805 304 xhv->xhv_fill = 0;
79072805 305 if (xhv->xhv_array)
463ee0b2 306 (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
79072805
LW
307}
308
309static void
463ee0b2 310hfreeentries(hv)
79072805 311HV *hv;
79072805
LW
312{
313 register XPVHV* xhv;
314 register HE *hent;
315 register HE *ohent = Null(HE*);
79072805
LW
316
317 if (!hv)
318 return;
319 xhv = (XPVHV*)SvANY(hv);
320 if (!xhv->xhv_array)
321 return;
79072805
LW
322 (void)hv_iterinit(hv);
323 /*SUPPRESS 560*/
324 while (hent = hv_iternext(hv)) { /* concise but not very efficient */
325 he_free(ohent);
326 ohent = hent;
327 }
328 he_free(ohent);
79072805 329 if (SvMAGIC(hv))
463ee0b2 330 mg_clear((SV*)hv);
79072805
LW
331}
332
333void
463ee0b2 334hv_undef(hv)
79072805 335HV *hv;
79072805
LW
336{
337 register XPVHV* xhv;
338 if (!hv)
339 return;
340 xhv = (XPVHV*)SvANY(hv);
463ee0b2 341 hfreeentries(hv);
79072805
LW
342 Safefree(xhv->xhv_array);
343 xhv->xhv_array = 0;
463ee0b2 344 xhv->xhv_max = 7; /* it's a normal associative array */
79072805 345 xhv->xhv_fill = 0;
79072805
LW
346 (void)hv_iterinit(hv); /* so each() will start off right */
347}
348
349void
463ee0b2 350hv_free(hv)
79072805 351register HV *hv;
79072805
LW
352{
353 if (!hv)
354 return;
463ee0b2 355 hfreeentries(hv);
79072805
LW
356 Safefree(HvARRAY(hv));
357 Safefree(hv);
358}
359
360I32
361hv_iterinit(hv)
362HV *hv;
363{
364 register XPVHV* xhv = (XPVHV*)SvANY(hv);
365 xhv->xhv_riter = -1;
366 xhv->xhv_eiter = Null(HE*);
367 return xhv->xhv_fill;
368}
369
370HE *
371hv_iternext(hv)
372HV *hv;
373{
374 register XPVHV* xhv;
375 register HE *entry;
463ee0b2 376 MAGIC* mg;
79072805
LW
377
378 if (!hv)
463ee0b2 379 croak("Bad associative array");
79072805
LW
380 xhv = (XPVHV*)SvANY(hv);
381 entry = xhv->xhv_eiter;
463ee0b2
LW
382
383 if (SvMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
384 SV *key = sv_2mortal(NEWSV(0,0));
385 if (entry)
386 sv_setpvn(key, entry->hent_key, entry->hent_klen);
387 else {
388 Newz(504,entry, 1, HE);
389 xhv->xhv_eiter = entry;
390 }
391 magic_nextpack(hv,mg,key);
392 if (SvOK(key)) {
393 STRLEN len;
394 entry->hent_key = SvPV(key, len);
395 entry->hent_klen = len;
396 SvPOK_off(key);
397 SvPVX(key) = 0;
398 return entry;
399 }
400 if (entry->hent_val)
401 sv_free(entry->hent_val);
402 Safefree(entry);
403 xhv->xhv_eiter = Null(HE*);
404 return Null(HE*);
79072805 405 }
463ee0b2 406
79072805 407 if (!xhv->xhv_array)
463ee0b2 408 Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
79072805
LW
409 do {
410 if (entry)
411 entry = entry->hent_next;
412 if (!entry) {
413 xhv->xhv_riter++;
414 if (xhv->xhv_riter > xhv->xhv_max) {
415 xhv->xhv_riter = -1;
416 break;
417 }
463ee0b2 418 entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
79072805
LW
419 }
420 } while (!entry);
421
422 xhv->xhv_eiter = entry;
423 return entry;
424}
425
426char *
427hv_iterkey(entry,retlen)
428register HE *entry;
429I32 *retlen;
430{
431 *retlen = entry->hent_klen;
432 return entry->hent_key;
433}
434
435SV *
436hv_iterval(hv,entry)
437HV *hv;
438register HE *entry;
439{
463ee0b2
LW
440 if (SvMAGICAL(hv)) {
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);
444 mg_get(sv);
445 sv_unmagic(sv,'p');
446 return sv;
447 }
79072805 448 }
79072805
LW
449 return entry->hent_val;
450}
451
79072805
LW
452void
453hv_magic(hv, gv, how)
454HV* hv;
455GV* gv;
456I32 how;
457{
463ee0b2 458 sv_magic((SV*)hv, (SV*)gv, how, 0, 0);
79072805 459}