a "replacement" for awk and sed
[perl.git] / x2p / hash.c
1 /* $Header: hash.c,v 1.0 87/12/18 13:07:18 root Exp $
2  *
3  * $Log:        hash.c,v $
4  * Revision 1.0  87/12/18  13:07:18  root
5  * Initial revision
6  * 
7  */
8
9 #include <stdio.h>
10 #include "EXTERN.h"
11 #include "handy.h"
12 #include "util.h"
13 #include "a2p.h"
14
15 STR *
16 hfetch(tb,key)
17 register HASH *tb;
18 char *key;
19 {
20     register char *s;
21     register int i;
22     register int hash;
23     register HENT *entry;
24
25     if (!tb)
26         return Nullstr;
27     for (s=key,         i=0,    hash = 0;
28       /* while */ *s;
29          s++,           i++,    hash *= 5) {
30         hash += *s * coeff[i];
31     }
32     entry = tb->tbl_array[hash & tb->tbl_max];
33     for (; entry; entry = entry->hent_next) {
34         if (entry->hent_hash != hash)           /* strings can't be equal */
35             continue;
36         if (strNE(entry->hent_key,key)) /* is this it? */
37             continue;
38         return entry->hent_val;
39     }
40     return Nullstr;
41 }
42
43 bool
44 hstore(tb,key,val)
45 register HASH *tb;
46 char *key;
47 STR *val;
48 {
49     register char *s;
50     register int i;
51     register int hash;
52     register HENT *entry;
53     register HENT **oentry;
54
55     if (!tb)
56         return FALSE;
57     for (s=key,         i=0,    hash = 0;
58       /* while */ *s;
59          s++,           i++,    hash *= 5) {
60         hash += *s * coeff[i];
61     }
62
63     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
64     i = 1;
65
66     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
67         if (entry->hent_hash != hash)           /* strings can't be equal */
68             continue;
69         if (strNE(entry->hent_key,key)) /* is this it? */
70             continue;
71         safefree((char*)entry->hent_val);
72         entry->hent_val = val;
73         return TRUE;
74     }
75     entry = (HENT*) safemalloc(sizeof(HENT));
76
77     entry->hent_key = savestr(key);
78     entry->hent_val = val;
79     entry->hent_hash = hash;
80     entry->hent_next = *oentry;
81     *oentry = entry;
82
83     if (i) {                            /* initial entry? */
84         tb->tbl_fill++;
85         if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
86             hsplit(tb);
87     }
88
89     return FALSE;
90 }
91
92 #ifdef NOTUSED
93 bool
94 hdelete(tb,key)
95 register HASH *tb;
96 char *key;
97 {
98     register char *s;
99     register int i;
100     register int hash;
101     register HENT *entry;
102     register HENT **oentry;
103
104     if (!tb)
105         return FALSE;
106     for (s=key,         i=0,    hash = 0;
107       /* while */ *s;
108          s++,           i++,    hash *= 5) {
109         hash += *s * coeff[i];
110     }
111
112     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
113     entry = *oentry;
114     i = 1;
115     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
116         if (entry->hent_hash != hash)           /* strings can't be equal */
117             continue;
118         if (strNE(entry->hent_key,key)) /* is this it? */
119             continue;
120         safefree((char*)entry->hent_val);
121         safefree(entry->hent_key);
122         *oentry = entry->hent_next;
123         safefree((char*)entry);
124         if (i)
125             tb->tbl_fill--;
126         return TRUE;
127     }
128     return FALSE;
129 }
130 #endif
131
132 hsplit(tb)
133 HASH *tb;
134 {
135     int oldsize = tb->tbl_max + 1;
136     register int newsize = oldsize * 2;
137     register int i;
138     register HENT **a;
139     register HENT **b;
140     register HENT *entry;
141     register HENT **oentry;
142
143     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
144     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
145     tb->tbl_max = --newsize;
146     tb->tbl_array = a;
147
148     for (i=0; i<oldsize; i++,a++) {
149         if (!*a)                                /* non-existent */
150             continue;
151         b = a+oldsize;
152         for (oentry = a, entry = *a; entry; entry = *oentry) {
153             if ((entry->hent_hash & newsize) != i) {
154                 *oentry = entry->hent_next;
155                 entry->hent_next = *b;
156                 if (!*b)
157                     tb->tbl_fill++;
158                 *b = entry;
159                 continue;
160             }
161             else
162                 oentry = &entry->hent_next;
163         }
164         if (!*a)                                /* everything moved */
165             tb->tbl_fill--;
166     }
167 }
168
169 HASH *
170 hnew()
171 {
172     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
173
174     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
175     tb->tbl_fill = 0;
176     tb->tbl_max = 7;
177     hiterinit(tb);      /* so each() will start off right */
178     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
179     return tb;
180 }
181
182 #ifdef NOTUSED
183 hshow(tb)
184 register HASH *tb;
185 {
186     fprintf(stderr,"%5d %4d (%2d%%)\n",
187         tb->tbl_max+1,
188         tb->tbl_fill,
189         tb->tbl_fill * 100 / (tb->tbl_max+1));
190 }
191 #endif
192
193 hiterinit(tb)
194 register HASH *tb;
195 {
196     tb->tbl_riter = -1;
197     tb->tbl_eiter = Null(HENT*);
198     return tb->tbl_fill;
199 }
200
201 HENT *
202 hiternext(tb)
203 register HASH *tb;
204 {
205     register HENT *entry;
206
207     entry = tb->tbl_eiter;
208     do {
209         if (entry)
210             entry = entry->hent_next;
211         if (!entry) {
212             tb->tbl_riter++;
213             if (tb->tbl_riter > tb->tbl_max) {
214                 tb->tbl_riter = -1;
215                 break;
216             }
217             entry = tb->tbl_array[tb->tbl_riter];
218         }
219     } while (!entry);
220
221     tb->tbl_eiter = entry;
222     return entry;
223 }
224
225 char *
226 hiterkey(entry)
227 register HENT *entry;
228 {
229     return entry->hent_key;
230 }
231
232 STR *
233 hiterval(entry)
234 register HENT *entry;
235 {
236     return entry->hent_val;
237 }