1 /*******************WARNING*********************
2
3 This is a *MODIFIED* version of Geoff Coller's proof-of-concept NOV
4 implementation.
5
6 It has been modified to support threading directly from a file handle
7 to a NNTP server without a temporary file.
8
9 This is not a complete distribution. We have only distributed enough
10 to support NN's needs.
11
12 The original version came from world.std.com:/src/news/nov.dist.tar.Z
13 and was dated 11 Aug 1993.
14
15 In any case, bugs you find here are probably my fault, as I've trimmed
16 a fair bit of unused code.
17
18 -Peter Wemm <peter@DIALix.oz.au>
19 */
20
21 /*
22 * Copyright (c) Geoffrey Collyer 1992, 1993.
23 * All rights reserved.
24 * Written by Geoffrey Collyer.
25 * Thanks to UUNET Communications Services Inc for financial support.
26 *
27 * This software is not subject to any license of the American Telephone
28 * and Telegraph Company, the Regents of the University of California, or
29 * the Free Software Foundation.
30 *
31 * Permission is granted to anyone to use this software for any purpose on
32 * any computer system, and to alter it and redistribute it freely, subject
33 * to the following restrictions:
34 *
35 * 1. The authors are not responsible for the consequences of use of this
36 * software, no matter how awful, even if they arise from flaws in it.
37 *
38 * 2. The origin of this software must not be misrepresented, either by
39 * explicit claim or by omission. Since few users ever read sources,
40 * credits must appear in the documentation.
41 *
42 * 3. Altered versions must be plainly marked as such, and must not be
43 * misrepresented as being the original software. Since few users
44 * ever read sources, credits must appear in the documentation.
45 *
46 * 4. This notice may not be removed or altered.
47 */
48
49
50 /*
51 * general-purpose in-core hashing, dbm interface
52 */
53
54 #include <stdlib.h>
55 #include <string.h>
56 #include "config.h"
57 #include "hdbm.h"
58 #include "hdbmint.h"
59
60 /* tunable parameters */
61 #define RETAIN 300 /* retain & recycle this many HASHENTs */
62
63 /* fundamental constants */
64 #define YES 1
65 #define NO 0
66
67 static HASHENT *hereuse = NULL;
68 static int reusables = 0;
69
70 static HASHENT *healloc(void);
71
72 /*
73 * Gosling EMACS hash (h = 33*h + *s++) optimized, loop unrolled with
74 * "Duff's Device". Thanks to Chris Torek.
75 */
76 static unsigned
hdbmdef(register HDBMDATUM key)77 hdbmdef(register HDBMDATUM key)
78 {
79 register unsigned char *s = (unsigned char *) key.dat_ptr;
80 register int len = key.dat_len;
81 register unsigned h;
82 register int loop;
83
84 #define HASHC h = (h << 5) + h + *s++;
85
86 h = 0;
87 if (len > 0) {
88 loop = (len + 8 - 1) >> 3;
89
90 switch (len & (8 - 1)) {
91 case 0:
92 do { /* All fall throughs */
93 HASHC;
94 case 7:
95 HASHC;
96 case 6:
97 HASHC;
98 case 5:
99 HASHC;
100 case 4:
101 HASHC;
102 case 3:
103 HASHC;
104 case 2:
105 HASHC;
106 case 1:
107 HASHC;
108 } while (--loop);
109 }
110
111 }
112 return (h);
113 }
114
115 HASHTABLE *
hdbmcreate(register unsigned size,unsigned (* hashfunc)())116 hdbmcreate(register unsigned size, unsigned (*hashfunc) ())
117 /* size a crude guide to size */
118 {
119 register HASHTABLE *tbl;
120 register HASHENT **hepp;
121
122 /*
123 * allocate HASHTABLE and (HASHENT *) array together to reduce the number
124 * of malloc calls. this idiom ensures correct alignment of the array.
125 * dmr calls the one-element array trick `unwarranted chumminess with the
126 * compiler' though.
127 */
128 register struct alignalloc {
129 HASHTABLE ht;
130 HASHENT *hepa[1];/* longer than it looks */
131 } *aap;
132
133 aap = (struct alignalloc *)
134 malloc(sizeof *aap + (size - 1) * sizeof(HASHENT *));
135 if (aap == NULL)
136 return NULL;
137 tbl = &aap->ht;
138 tbl->ht_size = (size == 0 ? 1 : size); /* size of 0 is nonsense */
139 tbl->ht_magic = HASHMAG;
140 tbl->ht_hash = (hashfunc == NULL ? hdbmdef : hashfunc);
141 tbl->ht_addr = hepp = aap->hepa;
142 while (size-- > 0)
143 hepp[size] = NULL;
144 return tbl;
145 }
146
147 static void
hefree(register HASHENT * hp)148 hefree(register HASHENT * hp)
149 { /* free a hash entry */
150 if (reusables >= RETAIN) /* compost heap is full? */
151 free((char *) hp); /* yup, just pitch this one */
152 else { /* no, just stash for reuse */
153 ++reusables;
154 hp->he_next = hereuse;
155 hereuse = hp;
156 }
157 }
158
159 /*
160 * free all the memory associated with tbl, erase the pointers to it, and
161 * invalidate tbl to prevent further use via other pointers to it.
162 */
163 void
hdbmdestroy(register HASHTABLE * tbl)164 hdbmdestroy(register HASHTABLE * tbl)
165 {
166 register unsigned idx;
167 register HASHENT *hp, *next;
168 register HASHENT **hepp;
169 register int tblsize;
170
171 if (tbl == NULL || BADTBL(tbl))
172 return;
173 tblsize = tbl->ht_size;
174 hepp = tbl->ht_addr;
175 for (idx = 0; idx < tblsize; idx++) {
176 for (hp = hepp[idx]; hp != NULL; hp = next) {
177 next = hp->he_next;
178 hp->he_next = NULL;
179 hefree(hp);
180 }
181 hepp[idx] = NULL;
182 }
183 tbl->ht_magic = 0; /* de-certify this table */
184 tbl->ht_addr = NULL;
185 free((char *) tbl);
186 }
187
188 /*
189 * The returned value is the address of the pointer that refers to the
190 * found object. Said pointer may be NULL if the object was not found;
191 * if so, this pointer should be updated with the address of the object
192 * to be inserted, if insertion is desired.
193 */
194 static HASHENT **
hdbmfind(register HASHTABLE * tbl,HDBMDATUM key)195 hdbmfind(register HASHTABLE * tbl, HDBMDATUM key)
196 {
197 register HASHENT *hp, *prevhp = NULL;
198 register char *hpkeydat, *keydat = key.dat_ptr;
199 register int keylen = key.dat_len;
200 register HASHENT **hepp;
201 register unsigned size;
202
203 if (BADTBL(tbl))
204 return NULL;
205 size = tbl->ht_size;
206 if (size == 0) /* paranoia: avoid division by zero */
207 size = 1;
208 hepp = &tbl->ht_addr[(*tbl->ht_hash) (key) % size];
209 for (hp = *hepp; hp != NULL; prevhp = hp, hp = hp->he_next) {
210 hpkeydat = hp->he_key.dat_ptr;
211 if (hp->he_key.dat_len == keylen && hpkeydat[0] == keydat[0] &&
212 memcmp(hpkeydat, keydat, keylen) == 0)
213 break;
214 }
215 /* assert: *(returned value) == hp */
216 return (prevhp == NULL ? hepp : &prevhp->he_next);
217 }
218
219 static HASHENT *
healloc(void)220 healloc(void)
221 { /* allocate a hash entry */
222 register HASHENT *hp;
223
224 if (hereuse == NULL)
225 return (HASHENT *) malloc(sizeof(HASHENT));
226 /* pull the first reusable one off the pile */
227 hp = hereuse;
228 hereuse = hereuse->he_next;
229 hp->he_next = NULL; /* prevent accidents */
230 reusables--;
231 return hp;
232 }
233
234 int
hdbmstore(register HASHTABLE * tbl,HDBMDATUM key,HDBMDATUM data)235 hdbmstore(register HASHTABLE * tbl, HDBMDATUM key, HDBMDATUM data)
236 {
237 register HASHENT *hp;
238 register HASHENT **nextp;
239
240 if (BADTBL(tbl))
241 return NO;
242 nextp = hdbmfind(tbl, key);
243 if (nextp == NULL)
244 return NO;
245 hp = *nextp;
246 if (hp == NULL) { /* absent; allocate an entry */
247 hp = healloc();
248 if (hp == NULL)
249 return NO;
250 hp->he_next = NULL;
251 hp->he_key = key;
252 *nextp = hp; /* append to hash chain */
253 }
254 hp->he_data = data; /* supersede any old data for this key */
255 return YES;
256 }
257
258 /* return any existing entry for key; otherwise call allocator to make one */
259 HDBMDATUM
hdbmentry(register HASHTABLE * tbl,HDBMDATUM key,HDBMDATUM (* allocator)())260 hdbmentry(register HASHTABLE * tbl, HDBMDATUM key, HDBMDATUM(*allocator) ())
261 {
262 register HASHENT *hp;
263 register HASHENT **nextp;
264 static HDBMDATUM errdatum = {NULL, 0};
265
266 if (BADTBL(tbl))
267 return errdatum;
268 nextp = hdbmfind(tbl, key);
269 if (nextp == NULL)
270 return errdatum;
271 hp = *nextp;
272 if (hp == NULL) { /* absent; allocate an entry */
273 hp = healloc();
274 if (hp == NULL)
275 return errdatum;
276 hp->he_next = NULL;
277 hp->he_key = key;
278 hp->he_data = (*allocator) (key);
279 *nextp = hp; /* append to hash chain */
280 }
281 return hp->he_data;
282 }
283
284 int
hdbmdelete(register HASHTABLE * tbl,HDBMDATUM key)285 hdbmdelete(register HASHTABLE * tbl, HDBMDATUM key)
286 {
287 register HASHENT *hp;
288 register HASHENT **nextp;
289
290 nextp = hdbmfind(tbl, key);
291 if (nextp == NULL)
292 return NO;
293 hp = *nextp;
294 if (hp == NULL) /* absent */
295 return NO;
296 *nextp = hp->he_next; /* skip this entry */
297 hp->he_next = NULL;
298 hp->he_data.dat_ptr = hp->he_key.dat_ptr = NULL;
299 hefree(hp);
300 return YES;
301 }
302
303 HDBMDATUM /* data corresponding to key */
hdbmfetch(register HASHTABLE * tbl,HDBMDATUM key)304 hdbmfetch(register HASHTABLE * tbl, HDBMDATUM key)
305 {
306 register HASHENT *hp;
307 register HASHENT **nextp;
308 static HDBMDATUM errdatum = {NULL, 0};
309
310 if (BADTBL(tbl))
311 return errdatum;
312 nextp = hdbmfind(tbl, key);
313 if (nextp == NULL)
314 return errdatum;
315 hp = *nextp;
316 if (hp == NULL) /* absent */
317 return errdatum;
318 else
319 return hp->he_data;
320 }
321
322 /*
323 * visit each entry by calling nodefunc at each, with key, data and hook as
324 * arguments. hook is an attempt to allow side-effects and reentrancy at
325 * the same time.
326 */
327 void
hdbmwalk(HASHTABLE * tbl,register int (* nodefunc)(),register char * hook)328 hdbmwalk(HASHTABLE * tbl, register int (*nodefunc) (), register char *hook)
329 /* hook (void *) really */
330 {
331 register unsigned idx;
332 register HASHENT *hp;
333 register HASHENT **hepp;
334 register int tblsize;
335
336 if (BADTBL(tbl))
337 return;
338 hepp = tbl->ht_addr;
339 tblsize = tbl->ht_size;
340 for (idx = 0; idx < tblsize; idx++)
341 for (hp = hepp[idx]; hp != NULL; hp = hp->he_next)
342 (*nodefunc) (hp->he_key, hp->he_data, hook);
343 }
344