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