For 5.12: saner behaviour for `length`
[p5sagit/p5-mst-13.2.git] / x2p / hash.c
1 /*    hash.c
2  *
3  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1999, 2000, 2001, 2002,
4  *    2005 by Larry Wall and others
5  *
6  *    You may distribute under the terms of either the GNU General Public
7  *    License or the Artistic License, as specified in the README file.
8  */
9
10 #include <stdio.h>
11 #include "EXTERN.h"
12 #include "a2p.h"
13 #include "util.h"
14
15 #ifdef NETWARE
16 char *savestr(char *str);
17 #endif
18
19 STR *
20 hfetch(register HASH *tb, char *key)
21 {
22     register char *s;
23     register int i;
24     register int hash;
25     register HENT *entry;
26
27     if (!tb)
28         return NULL;
29     for (s=key,         i=0,    hash = 0;
30       /* while */ *s;
31          s++,           i++,    hash *= 5) {
32         hash += *s * coeff[i];
33     }
34     entry = tb->tbl_array[hash & tb->tbl_max];
35     for (; entry; entry = entry->hent_next) {
36         if (entry->hent_hash != hash)           /* strings can't be equal */
37             continue;
38         if (strNE(entry->hent_key,key)) /* is this it? */
39             continue;
40         return entry->hent_val;
41     }
42     return NULL;
43 }
44
45 bool
46 hstore(register HASH *tb, char *key, STR *val)
47 {
48     register char *s;
49     register int i;
50     register int hash;
51     register HENT *entry;
52     register HENT **oentry;
53
54     if (!tb)
55         return FALSE;
56     for (s=key,         i=0,    hash = 0;
57       /* while */ *s;
58          s++,           i++,    hash *= 5) {
59         hash += *s * coeff[i];
60     }
61
62     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
63     i = 1;
64
65     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
66         if (entry->hent_hash != hash)           /* strings can't be equal */
67             continue;
68         if (strNE(entry->hent_key,key)) /* is this it? */
69             continue;
70         /*NOSTRICT*/
71         safefree(entry->hent_val);
72         entry->hent_val = val;
73         return TRUE;
74     }
75     /*NOSTRICT*/
76     entry = (HENT*) safemalloc(sizeof(HENT));
77
78     entry->hent_key = savestr(key);
79     entry->hent_val = val;
80     entry->hent_hash = hash;
81     entry->hent_next = *oentry;
82     *oentry = entry;
83
84     if (i) {                            /* initial entry? */
85         tb->tbl_fill++;
86         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
87             hsplit(tb);
88     }
89
90     return FALSE;
91 }
92
93 void
94 hsplit(HASH *tb)
95 {
96     const int oldsize = tb->tbl_max + 1;
97     register int newsize = oldsize * 2;
98     register int i;
99     register HENT **a;
100     register HENT **b;
101     register HENT *entry;
102     register HENT **oentry;
103
104     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
105     memset(&a[oldsize], 0, oldsize * sizeof(HENT*)); /* zero second half */
106     tb->tbl_max = --newsize;
107     tb->tbl_array = a;
108
109     for (i=0; i<oldsize; i++,a++) {
110         if (!*a)                                /* non-existent */
111             continue;
112         b = a+oldsize;
113         for (oentry = a, entry = *a; entry; entry = *oentry) {
114             if ((entry->hent_hash & newsize) != i) {
115                 *oentry = entry->hent_next;
116                 entry->hent_next = *b;
117                 if (!*b)
118                     tb->tbl_fill++;
119                 *b = entry;
120                 continue;
121             }
122             else
123                 oentry = &entry->hent_next;
124         }
125         if (!*a)                                /* everything moved */
126             tb->tbl_fill--;
127     }
128 }
129
130 HASH *
131 hnew(void)
132 {
133     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
134
135     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
136     tb->tbl_fill = 0;
137     tb->tbl_max = 7;
138     hiterinit(tb);      /* so each() will start off right */
139     memset(tb->tbl_array, 0, 8 * sizeof(HENT*));
140     return tb;
141 }
142
143 int
144 hiterinit(register HASH *tb)
145 {
146     tb->tbl_riter = -1;
147     tb->tbl_eiter = (HENT*)NULL;
148     return tb->tbl_fill;
149 }