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