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