This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
a30b01f57bfeb18b13f6304d46f26b4dd6672d05
[perl5.git] / hash.c
1 /* $Header: hash.c,v 3.0.1.5 90/08/13 22:18:27 lwall Locked $
2  *
3  *    Copyright (c) 1989, Larry Wall
4  *
5  *    You may distribute under the terms of the GNU General Public License
6  *    as specified in the README file that comes with the perl 3.0 kit.
7  *
8  * $Log:        hash.c,v $
9  * Revision 3.0.1.5  90/08/13  22:18:27  lwall
10  * patch28: defined(@array) and defined(%array) didn't work right
11  * 
12  * Revision 3.0.1.4  90/08/09  03:50:22  lwall
13  * patch19: dbmopen(name, 'filename', undef) now refrains from creating
14  * 
15  * Revision 3.0.1.3  90/03/27  15:59:09  lwall
16  * patch16: @dbmvalues{'foo','bar'} could use the same cache entry for both values
17  * 
18  * Revision 3.0.1.2  89/12/21  20:03:39  lwall
19  * patch7: errno may now be a macro with an lvalue
20  * 
21  * Revision 3.0.1.1  89/11/11  04:34:18  lwall
22  * patch2: CX/UX needed to set the key each time in associative iterators
23  * 
24  * Revision 3.0  89/10/18  15:18:32  lwall
25  * 3.0 baseline
26  * 
27  */
28
29 #include "EXTERN.h"
30 #include "perl.h"
31
32 static char coeff[] = {
33                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
34                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
35                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
36                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
37                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
38                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
39                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
40                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
41
42 STR *
43 hfetch(tb,key,klen,lval)
44 register HASH *tb;
45 char *key;
46 int klen;
47 int lval;
48 {
49     register char *s;
50     register int i;
51     register int hash;
52     register HENT *entry;
53     register int maxi;
54     STR *str;
55 #ifdef SOME_DBM
56     datum dkey,dcontent;
57 #endif
58
59     if (!tb)
60         return Nullstr;
61     if (!tb->tbl_array) {
62         if (lval)
63             Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
64         else
65             return Nullstr;
66     }
67
68     /* The hash function we use on symbols has to be equal to the first
69      * character when taken modulo 128, so that str_reset() can be implemented
70      * efficiently.  We throw in the second character and the last character
71      * (times 128) so that long chains of identifiers starting with the
72      * same letter don't have to be strEQ'ed within hfetch(), since it
73      * compares hash values before trying strEQ().
74      */
75     if (!tb->tbl_coeffsize)
76         hash = *key + 128 * key[1] + 128 * key[klen-1]; /* assuming klen > 0 */
77     else {      /* use normal coefficients */
78         if (klen < tb->tbl_coeffsize)
79             maxi = klen;
80         else
81             maxi = tb->tbl_coeffsize;
82         for (s=key,             i=0,    hash = 0;
83                             i < maxi;
84              s++,               i++,    hash *= 5) {
85             hash += *s * coeff[i];
86         }
87     }
88
89     entry = tb->tbl_array[hash & tb->tbl_max];
90     for (; entry; entry = entry->hent_next) {
91         if (entry->hent_hash != hash)           /* strings can't be equal */
92             continue;
93         if (entry->hent_klen != klen)
94             continue;
95         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
96             continue;
97         return entry->hent_val;
98     }
99 #ifdef SOME_DBM
100     if (tb->tbl_dbm) {
101         dkey.dptr = key;
102         dkey.dsize = klen;
103         dcontent = dbm_fetch(tb->tbl_dbm,dkey);
104         if (dcontent.dptr) {                    /* found one */
105             str = Str_new(60,dcontent.dsize);
106             str_nset(str,dcontent.dptr,dcontent.dsize);
107             hstore(tb,key,klen,str,hash);               /* cache it */
108             return str;
109         }
110     }
111 #endif
112     if (lval) {         /* gonna assign to this, so it better be there */
113         str = Str_new(61,0);
114         hstore(tb,key,klen,str,hash);
115         return str;
116     }
117     return Nullstr;
118 }
119
120 bool
121 hstore(tb,key,klen,val,hash)
122 register HASH *tb;
123 char *key;
124 int klen;
125 STR *val;
126 register int hash;
127 {
128     register char *s;
129     register int i;
130     register HENT *entry;
131     register HENT **oentry;
132     register int maxi;
133
134     if (!tb)
135         return FALSE;
136
137     if (hash)
138         ;
139     else if (!tb->tbl_coeffsize)
140         hash = *key + 128 * key[1] + 128 * key[klen-1];
141     else {      /* use normal coefficients */
142         if (klen < tb->tbl_coeffsize)
143             maxi = klen;
144         else
145             maxi = tb->tbl_coeffsize;
146         for (s=key,             i=0,    hash = 0;
147                             i < maxi;
148              s++,               i++,    hash *= 5) {
149             hash += *s * coeff[i];
150         }
151     }
152
153     if (!tb->tbl_array)
154         Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);
155
156     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
157     i = 1;
158
159     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
160         if (entry->hent_hash != hash)           /* strings can't be equal */
161             continue;
162         if (entry->hent_klen != klen)
163             continue;
164         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
165             continue;
166         Safefree(entry->hent_val);
167         entry->hent_val = val;
168         return TRUE;
169     }
170     New(501,entry, 1, HENT);
171
172     entry->hent_klen = klen;
173     entry->hent_key = nsavestr(key,klen);
174     entry->hent_val = val;
175     entry->hent_hash = hash;
176     entry->hent_next = *oentry;
177     *oentry = entry;
178
179     /* hdbmstore not necessary here because it's called from stabset() */
180
181     if (i) {                            /* initial entry? */
182         tb->tbl_fill++;
183 #ifdef SOME_DBM
184         if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
185             return FALSE;
186 #endif
187         if (tb->tbl_fill > tb->tbl_dosplit)
188             hsplit(tb);
189     }
190 #ifdef SOME_DBM
191     else if (tb->tbl_dbm) {             /* is this just a cache for dbm file? */
192         void hentdelayfree();
193
194         entry = tb->tbl_array[hash & tb->tbl_max];
195         oentry = &entry->hent_next;
196         entry = *oentry;
197         while (entry) { /* trim chain down to 1 entry */
198             *oentry = entry->hent_next;
199             hentdelayfree(entry);       /* no doubt they'll want this next. */
200             entry = *oentry;
201         }
202     }
203 #endif
204
205     return FALSE;
206 }
207
208 STR *
209 hdelete(tb,key,klen)
210 register HASH *tb;
211 char *key;
212 int klen;
213 {
214     register char *s;
215     register int i;
216     register int hash;
217     register HENT *entry;
218     register HENT **oentry;
219     STR *str;
220     int maxi;
221 #ifdef SOME_DBM
222     datum dkey;
223 #endif
224
225     if (!tb || !tb->tbl_array)
226         return Nullstr;
227     if (!tb->tbl_coeffsize)
228         hash = *key + 128 * key[1] + 128 * key[klen-1];
229     else {      /* use normal coefficients */
230         if (klen < tb->tbl_coeffsize)
231             maxi = klen;
232         else
233             maxi = tb->tbl_coeffsize;
234         for (s=key,             i=0,    hash = 0;
235                             i < maxi;
236              s++,               i++,    hash *= 5) {
237             hash += *s * coeff[i];
238         }
239     }
240
241     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
242     entry = *oentry;
243     i = 1;
244     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
245         if (entry->hent_hash != hash)           /* strings can't be equal */
246             continue;
247         if (entry->hent_klen != klen)
248             continue;
249         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
250             continue;
251         *oentry = entry->hent_next;
252         str = str_static(entry->hent_val);
253         hentfree(entry);
254         if (i)
255             tb->tbl_fill--;
256 #ifdef SOME_DBM
257       do_dbm_delete:
258         if (tb->tbl_dbm) {
259             dkey.dptr = key;
260             dkey.dsize = klen;
261             dbm_delete(tb->tbl_dbm,dkey);
262         }
263 #endif
264         return str;
265     }
266 #ifdef SOME_DBM
267     str = Nullstr;
268     goto do_dbm_delete;
269 #else
270     return Nullstr;
271 #endif
272 }
273
274 hsplit(tb)
275 HASH *tb;
276 {
277     int oldsize = tb->tbl_max + 1;
278     register int newsize = oldsize * 2;
279     register int i;
280     register HENT **a;
281     register HENT **b;
282     register HENT *entry;
283     register HENT **oentry;
284
285     a = tb->tbl_array;
286     Renew(a, newsize, HENT*);
287     Zero(&a[oldsize], oldsize, HENT*);          /* zero 2nd half*/
288     tb->tbl_max = --newsize;
289     tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
290     tb->tbl_array = a;
291
292     for (i=0; i<oldsize; i++,a++) {
293         if (!*a)                                /* non-existent */
294             continue;
295         b = a+oldsize;
296         for (oentry = a, entry = *a; entry; entry = *oentry) {
297             if ((entry->hent_hash & newsize) != i) {
298                 *oentry = entry->hent_next;
299                 entry->hent_next = *b;
300                 if (!*b)
301                     tb->tbl_fill++;
302                 *b = entry;
303                 continue;
304             }
305             else
306                 oentry = &entry->hent_next;
307         }
308         if (!*a)                                /* everything moved */
309             tb->tbl_fill--;
310     }
311 }
312
313 HASH *
314 hnew(lookat)
315 unsigned int lookat;
316 {
317     register HASH *tb;
318
319     Newz(502,tb, 1, HASH);
320     if (lookat) {
321         tb->tbl_coeffsize = lookat;
322         tb->tbl_max = 7;                /* it's a normal associative array */
323         tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
324     }
325     else {
326         tb->tbl_max = 127;              /* it's a symbol table */
327         tb->tbl_dosplit = 128;          /* so never split */
328     }
329     tb->tbl_fill = 0;
330 #ifdef SOME_DBM
331     tb->tbl_dbm = 0;
332 #endif
333     (void)hiterinit(tb);        /* so each() will start off right */
334     return tb;
335 }
336
337 void
338 hentfree(hent)
339 register HENT *hent;
340 {
341     if (!hent)
342         return;
343     str_free(hent->hent_val);
344     Safefree(hent->hent_key);
345     Safefree(hent);
346 }
347
348 void
349 hentdelayfree(hent)
350 register HENT *hent;
351 {
352     if (!hent)
353         return;
354     str_2static(hent->hent_val);        /* free between statements */
355     Safefree(hent->hent_key);
356     Safefree(hent);
357 }
358
359 void
360 hclear(tb)
361 register HASH *tb;
362 {
363     register HENT *hent;
364     register HENT *ohent = Null(HENT*);
365
366     if (!tb || !tb->tbl_array)
367         return;
368     (void)hiterinit(tb);
369     while (hent = hiternext(tb)) {      /* concise but not very efficient */
370         hentfree(ohent);
371         ohent = hent;
372     }
373     hentfree(ohent);
374     tb->tbl_fill = 0;
375 #ifndef lint
376     (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
377 #endif
378 }
379
380 void
381 hfree(tb)
382 register HASH *tb;
383 {
384     register HENT *hent;
385     register HENT *ohent = Null(HENT*);
386
387     if (!tb)
388         return;
389     (void)hiterinit(tb);
390     while (hent = hiternext(tb)) {
391         hentfree(ohent);
392         ohent = hent;
393     }
394     hentfree(ohent);
395     Safefree(tb->tbl_array);
396     Safefree(tb);
397 }
398
399 int
400 hiterinit(tb)
401 register HASH *tb;
402 {
403     tb->tbl_riter = -1;
404     tb->tbl_eiter = Null(HENT*);
405     return tb->tbl_fill;
406 }
407
408 HENT *
409 hiternext(tb)
410 register HASH *tb;
411 {
412     register HENT *entry;
413 #ifdef SOME_DBM
414     datum key;
415 #endif
416
417     entry = tb->tbl_eiter;
418 #ifdef SOME_DBM
419     if (tb->tbl_dbm) {
420         if (entry) {
421 #ifdef NDBM
422 #ifdef _CX_UX
423             key.dptr = entry->hent_key;
424             key.dsize = entry->hent_klen;
425             key = dbm_nextkey(tb->tbl_dbm, key);
426 #else
427             key = dbm_nextkey(tb->tbl_dbm);
428 #endif /* _CX_UX */
429 #else
430             key.dptr = entry->hent_key;
431             key.dsize = entry->hent_klen;
432             key = nextkey(key);
433 #endif
434         }
435         else {
436             Newz(504,entry, 1, HENT);
437             tb->tbl_eiter = entry;
438             key = dbm_firstkey(tb->tbl_dbm);
439         }
440         entry->hent_key = key.dptr;
441         entry->hent_klen = key.dsize;
442         if (!key.dptr) {
443             if (entry->hent_val)
444                 str_free(entry->hent_val);
445             Safefree(entry);
446             tb->tbl_eiter = Null(HENT*);
447             return Null(HENT*);
448         }
449         return entry;
450     }
451 #endif
452     if (!tb->tbl_array)
453         Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
454     do {
455         if (entry)
456             entry = entry->hent_next;
457         if (!entry) {
458             tb->tbl_riter++;
459             if (tb->tbl_riter > tb->tbl_max) {
460                 tb->tbl_riter = -1;
461                 break;
462             }
463             entry = tb->tbl_array[tb->tbl_riter];
464         }
465     } while (!entry);
466
467     tb->tbl_eiter = entry;
468     return entry;
469 }
470
471 char *
472 hiterkey(entry,retlen)
473 register HENT *entry;
474 int *retlen;
475 {
476     *retlen = entry->hent_klen;
477     return entry->hent_key;
478 }
479
480 STR *
481 hiterval(tb,entry)
482 register HASH *tb;
483 register HENT *entry;
484 {
485 #ifdef SOME_DBM
486     datum key, content;
487
488     if (tb->tbl_dbm) {
489         key.dptr = entry->hent_key;
490         key.dsize = entry->hent_klen;
491         content = dbm_fetch(tb->tbl_dbm,key);
492         if (!entry->hent_val)
493             entry->hent_val = Str_new(62,0);
494         str_nset(entry->hent_val,content.dptr,content.dsize);
495     }
496 #endif
497     return entry->hent_val;
498 }
499
500 #ifdef SOME_DBM
501 #if     defined(FCNTL) && ! defined(O_CREAT)
502 #include <fcntl.h>
503 #endif
504
505 #ifndef O_RDONLY
506 #define O_RDONLY 0
507 #endif
508 #ifndef O_RDWR
509 #define O_RDWR 2
510 #endif
511 #ifndef O_CREAT
512 #define O_CREAT 01000
513 #endif
514
515 #ifndef NDBM
516 static int dbmrefcnt = 0;
517 #endif
518
519 bool
520 hdbmopen(tb,fname,mode)
521 register HASH *tb;
522 char *fname;
523 int mode;
524 {
525     if (!tb)
526         return FALSE;
527 #ifndef NDBM
528     if (tb->tbl_dbm)    /* never really closed it */
529         return TRUE;
530 #endif
531     if (tb->tbl_dbm) {
532         hdbmclose(tb);
533         tb->tbl_dbm = 0;
534     }
535     hclear(tb);
536 #ifdef NDBM
537     if (mode >= 0)
538         tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
539     if (!tb->tbl_dbm)
540         tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
541 #else
542     if (dbmrefcnt++)
543         fatal("Old dbm can only open one database");
544     sprintf(buf,"%s.dir",fname);
545     if (stat(buf, &statbuf) < 0) {
546         if (mode < 0 || close(creat(buf,mode)) < 0)
547             return FALSE;
548         sprintf(buf,"%s.pag",fname);
549         if (close(creat(buf,mode)) < 0)
550             return FALSE;
551     }
552     tb->tbl_dbm = dbminit(fname) >= 0;
553 #endif
554     return tb->tbl_dbm != 0;
555 }
556
557 void
558 hdbmclose(tb)
559 register HASH *tb;
560 {
561     if (tb && tb->tbl_dbm) {
562 #ifdef NDBM
563         dbm_close(tb->tbl_dbm);
564         tb->tbl_dbm = 0;
565 #else
566         /* dbmrefcnt--;  */     /* doesn't work, rats */
567 #endif
568     }
569     else if (dowarn)
570         warn("Close on unopened dbm file");
571 }
572
573 bool
574 hdbmstore(tb,key,klen,str)
575 register HASH *tb;
576 char *key;
577 int klen;
578 register STR *str;
579 {
580     datum dkey, dcontent;
581     int error;
582
583     if (!tb || !tb->tbl_dbm)
584         return FALSE;
585     dkey.dptr = key;
586     dkey.dsize = klen;
587     dcontent.dptr = str_get(str);
588     dcontent.dsize = str->str_cur;
589     error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
590     if (error) {
591         if (errno == EPERM)
592             fatal("No write permission to dbm file");
593         warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
594 #ifdef NDBM
595         dbm_clearerr(tb->tbl_dbm);
596 #endif
597     }
598     return !error;
599 }
600 #endif /* SOME_DBM */