1 static char rcsid[] = "@(#)$Id: ndbz.c,v 1.2 1995/09/29 17:41:22 wfp5p Exp $";
2
3 /*******************************************************************************
4 * The Elm Mail System - $Revision: 1.2 $ $State: Exp $
5 *
6 * Copyright (c) 1988-1995 USENET Community Trust
7 * Copyright (c) 1986,1987 Dave Taylor
8 *******************************************************************************
9 * Bug reports, patches, comments, suggestions should be sent to:
10 *
11 * Bill Pemberton, Elm Coordinator
12 * flash@virginia.edu
13 *
14 *******************************************************************************
15 * $Log: ndbz.c,v $
16 * Revision 1.2 1995/09/29 17:41:22 wfp5p
17 * Alpha 8 (Chip's big changes)
18 *
19 * Revision 1.1.1.1 1995/04/19 20:38:32 wfp5p
20 * Initial import of elm 2.4 PL0 as base for elm 2.5.
21 *
22 ******************************************************************************/
23
24 /**
25 multi-database dbm replacement
26
27 **/
28
29 /*
30
31 ndbz.c V1.0
32 Syd Weinstein <syd@dsi.com>
33 Based on dbz.c from the C News distribution
34 Modified to support multiple DBZ files.
35
36 Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
37 You can use this code in any manner, as long as you leave my name on it
38 and don't hold me responsible for any problems with it.
39
40 Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun 5 00:27:08 CDT 1988
41
42 Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
43
44 Major reworking by Henry Spencer as part of the C News project.
45
46 These routines replace dbm as used by the usenet news software
47 (it's not a full dbm replacement by any means). It's fast and
48 simple. It contains no AT&T code.
49
50 In general, dbz's files are 1/20 the size of dbm's. Lookup performance
51 is somewhat better, while file creation is spectacularly faster, especially
52 if the incore facility is used.
53
54 */
55
56 #include "elm_defs.h"
57 #include <errno.h>
58
59 /*
60 * #ifdef index. "LIA" = "leave it alone unless you know what you're doing".
61 *
62 * FUNNYSEEKS SEEK_SET is not 0, get it from <unistd.h>
63 * INDEX_SIZE backward compatibility with old dbz; avoid using this
64 * NMEMORY number of days of memory for use in sizing new table (LIA)
65 * INCORE backward compatibility with old dbz; use dbzincore() instead
66 * DEFSIZE default table size (not as critical as in old dbz)
67 * NOTAGS fseek offsets are strange, do not do tagging (see below)
68 * NPAGBUF size of .pag buffer, in longs (LIA)
69 * SHISTBUF size of ASCII-file buffer, in bytes (LIA)
70 * MAXRUN length of run which shifts to next table (see below) (LIA)
71 * OVERFLOW long-int arithmetic overflow must be avoided, will trap
72 * NOBUFFER do not buffer hash-table i/o, B News locking is defective
73 */
74
75 #ifdef FUNNYSEEKS
76 #include <unistd.h>
77 #else
78 #define SEEK_SET 0
79 #endif
80 #ifdef OVERFLOW
81 #include <limits.h>
82 #endif
83
84 static int dbzversion = 3; /* for validating .dir file format */
85
86 /*
87 * The dbz database exploits the fact that when news stores a <key,value>
88 * tuple, the `value' part is a seek offset into a text file, pointing to
89 * a copy of the `key' part. This avoids the need to store a copy of
90 * the key in the dbz files. However, the text file *must* exist and be
91 * consistent with the dbz files, or things will fail.
92 *
93 * The basic format of the database is a simple hash table containing the
94 * values. A value is stored by indexing into the table using a hash value
95 * computed from the key; collisions are resolved by linear probing (just
96 * search forward for an empty slot, wrapping around to the beginning of
97 * the table if necessary). Linear probing is a performance disaster when
98 * the table starts to get full, so a complication is introduced. The
99 * database is actually one *or more* tables, stored sequentially in the
100 * .pag file, and the length of linear-probe sequences is limited. The
101 * search (for an existing item or an empty slot) always starts in the
102 * first table, and whenever MAXRUN probes have been done in table N,
103 * probing continues in table N+1. This behaves reasonably well even in
104 * cases of massive overflow. There are some other small complications
105 * added, see comments below.
106 *
107 * The table size is fixed for any particular database, but is determined
108 * dynamically when a database is rebuilt. The strategy is to try to pick
109 * the size so the first table will be no more than 2/3 full, that being
110 * slightly before the point where performance starts to degrade. (It is
111 * desirable to be a bit conservative because the overflow strategy tends
112 * to produce files with holes in them, which is a nuisance.)
113 */
114
115 /*
116 * The following is for backward compatibility.
117 */
118 #ifdef INDEX_SIZE
119 #define DEFSIZE INDEX_SIZE
120 #endif
121 #include "ndbz.h"
122
123 /*
124 * We assume that unused areas of a binary file are zeros, and that the
125 * bit pattern of `(of_t)0' is all zeros. The alternative is rather
126 * painful file initialization. Note that okayvalue(), if OVERFLOW is
127 * defined, knows what value of an offset would cause overflow.
128 */
129 #define VACANT ((of_t)0)
130 #define BIAS(o) ((o)+1) /* make any valid of_t non-VACANT */
131 #define UNBIAS(o) ((o)-1) /* reverse BIAS() effect */
132
133 /*
134 * In a Unix implementation, or indeed any in which an of_t is a byte
135 * count, there are a bunch of high bits free in an of_t. There is a
136 * use for them. Checking a possible hit by looking it up in the base
137 * file is relatively expensive, and the cost can be dramatically reduced
138 * by using some of those high bits to tag the value with a few more bits
139 * of the key's hash. This detects most false hits without the overhead of
140 * seek+read+strcmp. We use the top bit to indicate whether the value is
141 * tagged or not, and don't tag a value which is using the tag bits itself.
142 * We're in trouble if the of_t representation wants to use the top bit.
143 * The actual bitmasks and offset come from the configuration stuff,
144 * which permits fiddling with them as necessary, and also suppressing
145 * them completely (by defining the masks to 0). We build pre-shifted
146 * versions of the masks for efficiency.
147 */
148 #define HASTAG(o) ((o)&db->dbz_taghere)
149 #define TAG(o) ((o)&db->dbz_tagbits)
150 #define NOTAG(o) ((o)&~db->dbz_tagboth)
151 #define CANTAG(o) (((o)&db->dbz_tagboth) == 0)
152 #define MKTAG(v) (((v)<<db->dbz_conf.tagshift)&db->dbz_tagbits)
153
154 /*
155 * A new, from-scratch database, not built as a rebuild of an old one,
156 * needs to know table size and tagging. Normally
157 * the user supplies this info, but there have to be defaults.
158 */
159 #ifndef DEFSIZE
160 #define DEFSIZE 120011 /* 300007 might be better */
161 #endif
162 #ifndef NOTAGS
163 #define TAGENB 0x80 /* tag enable is top bit, tag is next 7 */
164 #define TAGMASK 0x7f
165 #define TAGSHIFT 24
166 #else
167 #define TAGENB 0 /* no tags */
168 #define TAGMASK 0
169 #define TAGSHIFT 0
170 #endif
171
172 static int getconf();
173 static int32 getno();
174 static int putconf();
175 static void mybytemap();
176 static of_t bytemap();
177
178 /*
179 * For a program that makes many, many references to the database, it
180 * is a large performance win to keep the table in core, if it will fit.
181 * Note that this does hurt robustness in the event of crashes, and
182 * dbz_close() *must* be called to flush the in-core database to disk.
183 * The code is prepared to deal with the possibility that there isn't
184 * enough memory. There *is* an assumption that a size_t is big enough
185 * to hold the size (in bytes) of one table, so dbz_open() tries to figure
186 * out whether this is possible first.
187 *
188 * The preferred way to ask for an in-core table is to do dbzincore(1)
189 * before dbz_open(). The default is not to do it, although -DINCORE
190 * overrides this for backward compatibility with old dbz.
191 *
192 * We keep only the first table in core. This greatly simplifies the
193 * code, and bounds memory demand. Furthermore, doing this is a large
194 * performance win even in the event of massive overflow.
195 */
196 #ifdef INCORE
197 static int default_incore = 1;
198 #else
199 static int default_incore = 0;
200 #endif
201
202 # ifndef MAXRUN
203 # define MAXRUN 100
204 # endif
205 static void start();
206 #define FRESH ((struct searcher *)NULL)
207 static of_t search();
208 #define NOTFOUND ((of_t)-1)
209 static int okayvalue();
210 static int set();
211
212 /*
213 * Arguably the searcher struct for a given routine ought to be local to
214 * it, but a dbz_fetch() is very often immediately followed by a dbz_store(), and
215 * in some circumstances it is a useful performance win to remember where
216 * the dbz_fetch() completed. So we use a global struct and remember whether
217 * it is current.
218 */
219
220 /* byte-ordering stuff */
221 #define MAPIN(o) ((db->dbz_bytesame) ? (o) : bytemap((o), db->dbz_conf.bytemap, db->dbz_mybmap))
222 #define MAPOUT(o) ((db->dbz_bytesame) ? (o) : bytemap((o), db->dbz_mybmap, db->dbz_conf.bytemap))
223
224 /* externals used */
225 #if !defined(atol) /* avoid problems with systems that declare atol as a macro */
226 extern long atol();
227 #endif
228
229 /* misc. forwards */
230 static long hash();
231 static void crcinit();
232 static int isprime();
233 static FILE *latebase();
234
235 /* file-naming stuff */
236 static char dir[] = ".dir";
237 static char pag[] = ".pag";
238 static char *enstring();
239
240 /* central data structures */
241 static of_t *getcore();
242 static int putcore();
243
244 /*
245 - dbz_fresh - set up a new database, no historical info
246 */
247 DBZ * /* NULL for failure, !NULL for success */
dbz_fresh(name,size,fs,tagmask)248 dbz_fresh(name, size, fs, tagmask)
249 char *name; /* base name; .dir and .pag must exist */
250 long size; /* table size (0 means default) */
251 int fs; /* field-separator character in base file */
252 of_t tagmask; /* 0 default, 1 no tags */
253 {
254 register char *fn;
255 struct dbzconfig c;
256 register of_t m;
257 register FILE *f;
258
259 if (size != 0 && size < 2) {
260 dprint(5, (debugfile, "dbz_fresh: preposterous size (%ld)\n", size));
261 return (DBZ *)NULL;
262 }
263
264 /* get default configuration */
265 if (getconf((FILE *)NULL, (FILE *)NULL, &c) < 0)
266 return (DBZ *)NULL; /* "can't happen" */
267
268 /* and mess with it as specified */
269 if (size != 0)
270 c.tsize = size;
271 c.fieldsep = fs;
272 switch (tagmask) {
273 case 0: /* default */
274 break;
275 case 1: /* no tags */
276 c.tagshift = 0;
277 c.tagmask = 0;
278 c.tagenb = 0;
279 break;
280 default:
281 m = tagmask;
282 c.tagshift = 0;
283 while (!(m&01)) {
284 m >>= 1;
285 c.tagshift++;
286 }
287 c.tagmask = m;
288 c.tagenb = (m << 1) & ~m;
289 break;
290 }
291
292 /* write it out */
293 fn = enstring(name, dir);
294 if (fn == NULL)
295 return (DBZ *)NULL;
296 f = fopen(fn, "w");
297 free((malloc_t)fn);
298 if (f == NULL) {
299 dprint(5, (debugfile, "dbz_fresh: unable to write config\n"));
300 return (DBZ *)NULL;
301 }
302 if (putconf(f, &c) < 0) {
303 (void) fclose(f);
304 return (DBZ *)NULL;
305 }
306 if (fclose(f) == EOF) {
307 dprint(5, (debugfile, "dbz_fresh: fclose failure\n"));
308 return (DBZ *)NULL;
309 }
310
311 /* create/truncate .pag */
312 fn = enstring(name, pag);
313 if (fn == NULL)
314 return (DBZ *)NULL;
315 f = fopen(fn, "w");
316 free((malloc_t)fn);
317 if (f == NULL) {
318 dprint(5, (debugfile, "dbz_fresh: unable to create/truncate .pag file\n"));
319 return (DBZ *)NULL;
320 } else
321 (void) fclose(f);
322
323 /* and punt to dbz_open for the hard work */
324 return(dbz_open(name, O_RDWR, 0));
325 }
326
327 /*
328 - dbz_size - what's a good table size to hold this many entries?
329 */
330 long
dbzsize(contents)331 dbzsize(contents)
332 long contents; /* 0 means what's the default */
333 {
334 register long n;
335
336 if (contents <= 0) { /* foulup or default inquiry */
337 dprint(5, (debugfile, "dbzsize: preposterous input (%ld)\n", contents));
338 return(DEFSIZE);
339 }
340 n = (contents/2)*3; /* try to keep table at most 2/3 full */
341 if (!(n&01)) /* make it odd */
342 n++;
343 dprint(5, (debugfile, "dbzsize: tentative size %ld\n", n));
344 while (!isprime(n)) /* and look for a prime */
345 n += 2;
346 dprint(5, (debugfile, "dbzsize: final size %ld\n", n));
347
348 return(n);
349 }
350
351 /*
352 - isprime - is a number prime?
353 *
354 * This is not a terribly efficient approach.
355 */
356 static int /* predicate */
isprime(x)357 isprime(x)
358 register long x;
359 {
360 static int quick[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0 };
361 register int *ip;
362 register long div;
363 register long stop;
364
365 /* hit the first few primes quickly to eliminate easy ones */
366 /* this incidentally prevents ridiculously small tables */
367 for (ip = quick; (div = *ip) != 0; ip++)
368 if (x%div == 0) {
369 dprint(5, (debugfile, "isprime: quick result on %ld\n", (long)x));
370 return(0);
371 }
372
373 /* approximate square root of x */
374 for (stop = x; x/stop < stop; stop >>= 1)
375 continue;
376 stop <<= 1;
377
378 /* try odd numbers up to stop */
379 for (div = *--ip; div < stop; div += 2)
380 if (x%div == 0)
381 return(0);
382
383 return(1);
384 }
385
386 /*
387 - dbz_again - set up a new database to be a rebuild of an old one
388 */
389 DBZ * /* NULL for failure, !NULL for success */
dbz_again(name,oldname)390 dbz_again(name, oldname)
391 char *name; /* base name; .dir and .pag must exist */
392 char *oldname; /* base name; all must exist */
393 {
394 register char *fn;
395 struct dbzconfig c;
396 register int i;
397 register long top;
398 register FILE *f;
399 register int newtable;
400 register of_t newsize;
401
402 /* pick up the old configuration */
403 fn = enstring(oldname, dir);
404 if (fn == NULL)
405 return (DBZ *)NULL;
406 f = fopen(fn, "r");
407 free((malloc_t)fn);
408 if (f == NULL) {
409 dprint(5, (debugfile, "dbz_again: cannot open old .dir file\n"));
410 return (DBZ *)NULL;
411 }
412 i = getconf(f, (FILE *)NULL, &c);
413 (void) fclose(f);
414 if (i < 0) {
415 dprint(5, (debugfile, "dbz_again: getconf failed\n"));
416 return (DBZ *)NULL;
417 }
418
419 /* tinker with it */
420 top = 0;
421 newtable = 0;
422 for (i = 0; i < NUSEDS; i++) {
423 if (top < c.used[i])
424 top = c.used[i];
425 if (c.used[i] == 0)
426 newtable = 1; /* hasn't got full usage history yet */
427 }
428 if (top == 0) {
429 dprint(5, (debugfile, "dbz_again: old table has no contents!\n"));
430 newtable = 1;
431 }
432 for (i = NUSEDS-1; i > 0; i--)
433 c.used[i] = c.used[i-1];
434 c.used[0] = 0;
435 newsize = dbzsize(top);
436 if (!newtable || newsize > c.tsize) /* don't shrink new table */
437 c.tsize = newsize;
438
439 /* write it out */
440 fn = enstring(name, dir);
441 if (fn == NULL)
442 return (DBZ *)NULL;
443 f = fopen(fn, "w");
444 free((malloc_t)fn);
445 if (f == NULL) {
446 dprint(5, (debugfile, "dbz_again: unable to write new .dir\n"));
447 return (DBZ *)NULL;
448 }
449 i = putconf(f, &c);
450 (void) fclose(f);
451 if (i < 0) {
452 dprint(5, (debugfile, "dbz_again: putconf failed\n"));
453 return (DBZ *)NULL;
454 }
455
456 /* create/truncate .pag */
457 fn = enstring(name, pag);
458 if (fn == NULL)
459 return (DBZ *)NULL;
460 f = fopen(fn, "w");
461 free((malloc_t)fn);
462 if (f == NULL) {
463 dprint(5, (debugfile, "dbz_again: unable to create/truncate .pag file\n"));
464 return (DBZ *)NULL;
465 } else
466 (void) fclose(f);
467
468 /* and let dbz_open do the work */
469 return(dbz_open(name, O_RDWR, 0));
470 }
471
472 /*
473 - dbz_open - open a database, creating it (using defaults) if necessary
474 *
475 * We try to leave errno set plausibly, to the extent that underlying
476 * functions permit this, since many people consult it if dbz_open() fails.
477 */
478 DBZ * /* NULL for failure, !NULL for success */
dbz_open(name,mode,flags)479 dbz_open(name, mode, flags)
480 char *name;
481 int mode, flags;
482 {
483 register int i;
484 register size_t s;
485 register DBZ *db;
486 register char *dirfname;
487 register char *pagfname;
488
489 if ((db = (DBZ *) calloc(sizeof(DBZ), 1)) == NULL) {
490 dprint(5, (debugfile, "dbz_open: no room for DBZ structure\n"));
491 return (DBZ *)NULL;
492 }
493 /* open the .dir file */
494 dirfname = enstring(name, dir);
495 if (dirfname == NULL) {
496 free((malloc_t)db);
497 return (DBZ *)NULL;
498 }
499
500 if (mode == O_RDONLY) {
501 db->dbz_dirf = fopen(dirfname, "r");
502 db->dbz_dirronly = 1;
503 } else
504 db->dbz_dirf = fopen(dirfname, "r+");
505 free((malloc_t)dirfname);
506
507 if (db->dbz_dirf == NULL) {
508 dprint(5, (debugfile, "dbz_open: can't open .dir file\n"));
509 free((malloc_t)db);
510 return (DBZ *)NULL;
511 }
512
513 /* open the .pag file */
514 pagfname = enstring(name, pag);
515 if (pagfname == NULL) {
516 (void) fclose(db->dbz_dirf);
517 free((malloc_t)db);
518 return (DBZ *)NULL;
519 }
520 if (mode == O_RDONLY) {
521 db->dbz_pagf = fopen(pagfname, "rb");
522 db->dbz_pagronly = 1;
523 } else
524 db->dbz_pagf = fopen(pagfname, "r+b");
525
526 if (db->dbz_pagf == NULL) {
527 dprint(5, (debugfile, "dbz_open: .pag open failed\n"));
528 (void) fclose(db->dbz_dirf);
529 free((malloc_t)pagfname);
530 free((malloc_t)db);
531 return (DBZ *)NULL;
532 }
533 #ifdef NOBUFFER
534 /*
535 * B News does not do adequate locking on its database accesses.
536 * Why it doesn't get into trouble using dbm is a mystery. In any
537 * case, doing unbuffered i/o does not cure the problem, but does
538 * enormously reduce its incidence.
539 */
540 (void) setbuf(db->dbz_pagf, (char *)NULL);
541 #else
542 #ifdef _IOFBF
543 (void) setvbuf(db->dbz_pagf, (char *)db->dbz_pagbuf, _IOFBF, sizeof(db->dbz_pagbuf));
544 #endif
545 #endif
546 db->dbz_pagpos = -1;
547 /* don't free pagfname, need it below */
548
549 /* open the base file */
550 db->dbz_basef = fopen(name, "r");
551 if (db->dbz_basef == NULL) {
552 dprint(5, (debugfile, "dbz_open: basefile open failed\n"));
553 db->dbz_basefname = enstring(name, "");
554 if (db->dbz_basefname == NULL) {
555 (void) fclose(db->dbz_pagf);
556 (void) fclose(db->dbz_dirf);
557 free((malloc_t)pagfname);
558 free((malloc_t)db);
559 return (DBZ *)NULL;
560 }
561 } else
562 db->dbz_basefname = NULL;
563 #ifdef _IOFBF
564 if (db->dbz_basef != NULL)
565 (void) setvbuf(db->dbz_basef, db->dbz_basebuf, _IOFBF, sizeof(db->dbz_basebuf));
566 #endif
567
568 /* pick up configuration */
569 if (getconf(db->dbz_dirf, db->dbz_pagf, &db->dbz_conf) < 0) {
570 dprint(5, (debugfile, "dbz_open: getconf failure\n"));
571 (void) fclose(db->dbz_basef);
572 (void) fclose(db->dbz_pagf);
573 (void) fclose(db->dbz_basef);
574 (void) fclose(db->dbz_dirf);
575 free((malloc_t)pagfname);
576 free((malloc_t)db);
577 errno = EDOM; /* kind of a kludge, but very portable */
578 return (DBZ *)NULL;
579 }
580 db->dbz_tagbits = db->dbz_conf.tagmask << db->dbz_conf.tagshift;
581 db->dbz_taghere = db->dbz_conf.tagenb << db->dbz_conf.tagshift;
582 db->dbz_tagboth = db->dbz_tagbits | db->dbz_taghere;
583 mybytemap(db->dbz_mybmap);
584 db->dbz_bytesame = 1;
585 for (i = 0; i < SOF; i++)
586 if (db->dbz_mybmap[i] != db->dbz_conf.bytemap[i])
587 db->dbz_bytesame = 0;
588
589 /* get first table into core, if it looks desirable and feasible */
590 s = (size_t)db->dbz_conf.tsize * SOF;
591 db->dbz_incore = default_incore;
592 if (db->dbz_incore && (of_t)(s/SOF) == db->dbz_conf.tsize) {
593 db->dbz_bufpagf = fopen(pagfname, (db->dbz_pagronly) ? "rb" : "r+b");
594 if (db->dbz_bufpagf != NULL)
595 db->dbz_corepag = getcore(db);
596 } else {
597 db->dbz_bufpagf = NULL;
598 db->dbz_corepag = NULL;
599 }
600 free((malloc_t)pagfname);
601
602 /* misc. setup */
603 crcinit();
604 db->dbz_written = 0;
605 db->dbz_prevp = FRESH;
606 dprint(5, (debugfile, "dbz_open: succeeded\n"));
607 return(db);
608 }
609
610 /*
611 - enstring - concatenate two strings into a malloced area
612 */
613 static char * /* NULL if malloc fails */
enstring(s1,s2)614 enstring(s1, s2)
615 char *s1;
616 char *s2;
617 {
618 register char *p;
619
620 p = malloc((size_t)strlen(s1) + (size_t)strlen(s2) + 1);
621 if (p != NULL) {
622 (void) strcpy(p, s1);
623 (void) strcat(p, s2);
624 } else {
625 dprint(5, (debugfile, "enstring(%s, %s) out of memory\n", s1, s2));
626 }
627 return(p);
628 }
629
630 /*
631 - dbz_close - close a database
632 */
633 int
dbz_close(db)634 dbz_close(db)
635 register DBZ *db;
636 {
637 register int ret = 0;
638
639 if (db->dbz_pagf == NULL) {
640 dprint(5, (debugfile, "dbz_close: not opened!\n"));
641 return(-1);
642 }
643
644 if (fclose(db->dbz_pagf) == EOF) {
645 dprint(5, (debugfile, "dbz_close: fclose(pagf) failed\n"));
646 ret = -1;
647 }
648 if (dbz_sync(db) < 0)
649 ret = -1;
650 if (db->dbz_bufpagf != NULL && fclose(db->dbz_bufpagf) == EOF) {
651 dprint(5, (debugfile, "dbz_close: fclose(bufpagf) failed\n"));
652 ret = -1;
653 }
654 if (db->dbz_corepag != NULL)
655 free((malloc_t)db->dbz_corepag);
656 db->dbz_corepag = NULL;
657 if (fclose(db->dbz_basef) == EOF) {
658 dprint(5, (debugfile, "dbz_close: fclose(basef) failed\n"));
659 ret = -1;
660 }
661 if (db->dbz_basefname != NULL)
662 free((malloc_t)db->dbz_basefname);
663 db->dbz_basef = NULL;
664 db->dbz_pagf = NULL;
665 if (fclose(db->dbz_dirf) == EOF) {
666 dprint(5, (debugfile, "dbz_close: fclose(dirf) failed\n"));
667 ret = -1;
668 }
669
670 free((malloc_t) db);
671
672 dprint(5, (debugfile, "dbz_close: %s\n", (ret == 0) ? "succeeded" : "failed"));
673 return(ret);
674 }
675
676 /*
677 - dbz_sync - push all in-core data out to disk
678 */
679 int
dbz_sync(db)680 dbz_sync(db)
681 register DBZ *db;
682 {
683 register int ret = 0;
684
685 if (db->dbz_pagf == NULL) {
686 dprint(5, (debugfile, "dbzsync: not opened!\n"));
687 return(-1);
688 }
689 if (!db->dbz_written)
690 return(0);
691
692 if (db->dbz_corepag != NULL) {
693 if (putcore(db) < 0) {
694 dprint(5, (debugfile, "dbzsync: putcore failed\n"));
695 ret = -1;
696 }
697 }
698 if (!db->dbz_conf.olddbz)
699 if (putconf(db->dbz_dirf, &db->dbz_conf) < 0)
700 ret = -1;
701
702 dprint(5, (debugfile, "dbzsync: %s\n", (ret == 0) ? "succeeded" : "failed"));
703 return(ret);
704 }
705
706 /*
707 - dbzcancel - cancel writing of in-core data
708 * Mostly for use from child processes.
709 * Note that we don't need to futz around with stdio buffers, because we
710 * always fflush them immediately anyway and so they never have stale data.
711 */
712 int
dbz_cancel(db)713 dbz_cancel(db)
714 register DBZ *db;
715 {
716 if (db->dbz_pagf == NULL) {
717 dprint(5, (debugfile, "dbz_cancel: not opened!\n"));
718 return(-1);
719 }
720
721 db->dbz_written = 0;
722 return(0);
723 }
724
725 /*
726 - dbz_fetch - get an entry from the database
727 *
728 * Disgusting fine point, in the name of backward compatibility: if the
729 * last character of "key" is a NUL, that character is (effectively) not
730 * part of the comparison against the stored keys.
731 */
732 datum /* dptr NULL, dsize 0 means failure */
dbz_fetch(db,key)733 dbz_fetch(db, key)
734 register DBZ *db;
735 datum key;
736 {
737 char buffer[DBZMAXKEY + 1];
738 static of_t key_ptr; /* return value points here */
739 datum output;
740 register size_t keysize;
741 register size_t cmplen;
742 register char *sepp;
743
744 dprint(5, (debugfile, "dbz_fetch: (%s)\n", key.dptr));
745 output.dptr = NULL;
746 output.dsize = 0;
747 db->dbz_prevp = FRESH;
748
749 /* Key is supposed to be less than DBZMAXKEY */
750 keysize = key.dsize;
751 if (keysize >= DBZMAXKEY) {
752 keysize = DBZMAXKEY;
753 dprint(5, (debugfile, "keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
754 }
755
756 if (db->dbz_pagf == NULL) {
757 dprint(5, (debugfile, "dbz_fetch: database not open!\n"));
758 return(output);
759 } else if (db->dbz_basef == NULL) { /* basef didn't exist yet */
760 db->dbz_basef = latebase(db);
761 if (db->dbz_basef == NULL)
762 return(output);
763 }
764
765 cmplen = keysize;
766 sepp = &db->dbz_conf.fieldsep;
767 if (key.dptr[keysize-1] == '\0') {
768 cmplen--;
769 sepp = &buffer[keysize-1];
770 }
771 start(db, &key, FRESH);
772 while ((key_ptr = search(db)) != NOTFOUND) {
773 dprint(5, (debugfile, "got 0x%lx\n", key_ptr));
774
775 /* fetch the key */
776 if (fseek(db->dbz_basef, key_ptr, SEEK_SET) != 0) {
777 dprint(5, (debugfile, "dbz_fetch: seek failed\n"));
778 return(output);
779 }
780 if (fread(buffer, 1, keysize, db->dbz_basef) != keysize) {
781 dprint(5, (debugfile, "dbz_fetch: read failed\n"));
782 return(output);
783 }
784
785 /* try it */
786 buffer[keysize] = '\0'; /* terminated for DEBUG */
787 dprint(5, (debugfile, "dbz_fetch: buffer (%s) looking for (%s) size = %d\n",
788 buffer, key.dptr, keysize));
789 if (bcmp(key.dptr, buffer, cmplen) == 0 &&
790 (*sepp == db->dbz_conf.fieldsep || *sepp == '\0')) {
791 /* we found it */
792 output.dptr = (char *)&key_ptr;
793 output.dsize = SOF;
794 dprint(5, (debugfile, "dbz_fetch: successful\n"));
795 return(output);
796 }
797 }
798
799 /* we didn't find it */
800 dprint(5, (debugfile, "dbz_fetch: failed\n"));
801 db->dbz_prevp = &db->dbz_srch; /* remember where we stopped */
802 return(output);
803 }
804
805 /*
806 - latebase - try to open a base file that wasn't there at the start
807 */
808 static FILE *
latebase(db)809 latebase(db)
810 register DBZ *db;
811 {
812 register FILE *it;
813
814 if (db->dbz_basefname == NULL) {
815 dprint(5, (debugfile, "latebase: name foulup\n"));
816 return (FILE *)NULL;
817 }
818 it = fopen(db->dbz_basefname, "r");
819 if (it == NULL) {
820 dprint(5, (debugfile, "latebase: still can't open base\n"));
821 } else {
822 dprint(5, (debugfile, "latebase: late open succeeded\n"));
823 free((malloc_t)db->dbz_basefname);
824 db->dbz_basefname = NULL;
825 #ifdef _IOFBF
826 (void) setvbuf(it, db->dbz_basebuf, _IOFBF, sizeof(db->dbz_basebuf));
827 #endif
828 }
829 return(it);
830 }
831
832 /*
833 - dbz_store - add an entry to the database
834 */
835 int /* 0 success, -1 failure */
dbz_store(db,key,data)836 dbz_store(db, key, data)
837 register DBZ *db;
838 datum key;
839 datum data;
840 {
841 of_t value;
842
843 if (db->dbz_pagf == NULL) {
844 dprint(5, (debugfile, "dbz_store: database not open!\n"));
845 return(-1);
846 } else if (db->dbz_basef == NULL) { /* basef didn't exist yet */
847 db->dbz_basef = latebase(db);
848 if (db->dbz_basef == NULL)
849 return(-1);
850 }
851 if (db->dbz_pagronly) {
852 dprint(5, (debugfile, "dbz_store: database open read-only\n"));
853 return(-1);
854 }
855 if (data.dsize != SOF) {
856 dprint(5, (debugfile, "dbz_store: value size wrong (%d)\n", data.dsize));
857 return(-1);
858 }
859 if (key.dsize >= DBZMAXKEY) {
860 dprint(5, (debugfile, "dbz_store: key size too big (%d)\n", key.dsize));
861 return(-1);
862 }
863
864 /* copy the value in to ensure alignment */
865 (void) bcopy(data.dptr, (char *)&value, SOF);
866 dprint(5, (debugfile, "dbz_store: (%s, %ld)\n", key.dptr, (long)value));
867 if (!okayvalue(db, value)) {
868 dprint(5, (debugfile, "dbz_store: reserved bit or overflow in 0x%lx\n", value));
869 return(-1);
870 }
871
872 /* find the place, exploiting previous search if possible */
873 start(db, &key, db->dbz_prevp);
874 while (search(db) != NOTFOUND)
875 continue;
876
877 db->dbz_prevp = FRESH;
878 db->dbz_conf.used[0]++;
879 dprint(5, (debugfile, "dbz_store: used count %ld\n", db->dbz_conf.used[0]));
880 db->dbz_written = 1;
881 return(set(db, value));
882 }
883
884 /*
885 - dbz_incore - control attempts to keep .pag file in core
886 */
887 int /* old setting */
dbz_incore(value)888 dbz_incore(value)
889 int value;
890 {
891 register int old = default_incore;
892
893 default_incore = value;
894 return(old);
895 }
896
897 /*
898 - getconf - get configuration from .dir file
899 */
900 static int /* 0 success, -1 failure */
getconf(df,pf,cp)901 getconf(df, pf, cp)
902 register FILE *df; /* NULL means just give me the default */
903 register FILE *pf; /* NULL means don't care about .pag */
904 register struct dbzconfig *cp;
905 {
906 register int c;
907 register int i;
908 int err = 0;
909
910 c = (df != NULL) ? getc(df) : EOF;
911 if (c == EOF) { /* empty file, no configuration known */
912 cp->olddbz = 0;
913 if (df != NULL && pf != NULL && getc(pf) != EOF)
914 cp->olddbz = 1;
915 cp->tsize = DEFSIZE;
916 cp->fieldsep = '\t';
917 for (i = 0; i < NUSEDS; i++)
918 cp->used[i] = 0;
919 cp->valuesize = SOF;
920 mybytemap(cp->bytemap);
921 cp->tagenb = TAGENB;
922 cp->tagmask = TAGMASK;
923 cp->tagshift = TAGSHIFT;
924 dprint(5, (debugfile, "getconf: defaults (%ld, (0x%lx/0x%lx<<%d))\n",
925 cp->tsize, cp->tagenb, cp->tagmask, cp->tagshift));
926 return(0);
927 }
928 (void) ungetc(c, df);
929
930 /* first line, the vital stuff */
931 if (getc(df) != 'd' || getc(df) != 'b' || getc(df) != 'z')
932 err = -1;
933 if (getno(df, &err) != dbzversion)
934 err = -1;
935 cp->tsize = getno(df, &err);
936 cp->fieldsep = getno(df, &err);
937 while ((c = getc(df)) == ' ')
938 continue;
939 cp->tagenb = getno(df, &err);
940 cp->tagmask = getno(df, &err);
941 cp->tagshift = getno(df, &err);
942 cp->valuesize = getno(df, &err);
943 if (cp->valuesize != SOF) {
944 dprint(5, (debugfile, "getconf: wrong of_t size (%d)\n", cp->valuesize));
945 err = -1;
946 cp->valuesize = SOF; /* to protect the loops below */
947 }
948 for (i = 0; i < cp->valuesize; i++)
949 cp->bytemap[i] = getno(df, &err);
950 if (getc(df) != '\n')
951 err = -1;
952 dprint(5, (debugfile, "size %ld, sep %d, tags 0x%lx/0x%lx<<%d, ", cp->tsize,
953 cp->fieldsep, cp->tagenb, cp->tagmask, cp->tagshift));
954 dprint(5, (debugfile, "bytemap (%d)", cp->valuesize));
955 for (i = 0; i < cp->valuesize; i++) {
956 dprint(5, (debugfile, " %d", cp->bytemap[i]));
957 }
958 dprint(5, (debugfile, "\n"));
959
960 /* second line, the usages */
961 for (i = 0; i < NUSEDS; i++)
962 cp->used[i] = getno(df, &err);
963 if (getc(df) != '\n')
964 err = -1;
965 dprint(5, (debugfile, "used %ld %ld %ld...\n", cp->used[0], cp->used[1], cp->used[2]));
966
967 if (err < 0) {
968 dprint(5, (debugfile, "getconf error\n"));
969 return(-1);
970 }
971 return(0);
972 }
973
974 /*
975 - getno - get an int32
976 */
977 static int32
getno(f,ep)978 getno(f, ep)
979 FILE *f;
980 int *ep;
981 {
982 register char *p;
983 # define MAXN 50
984 char getbuf[MAXN];
985 register int c;
986
987 while ((c = getc(f)) == ' ')
988 continue;
989 if (c == EOF || c == '\n') {
990 dprint(5, (debugfile, "getno: missing number\n"));
991 *ep = -1;
992 return(0);
993 }
994 p = getbuf;
995 *p++ = c;
996 while ((c = getc(f)) != EOF && c != '\n' && c != ' ')
997 if (p < &getbuf[MAXN-1])
998 *p++ = c;
999 if (c == EOF) {
1000 dprint(5, (debugfile, "getno: EOF\n"));
1001 *ep = -1;
1002 } else
1003 (void) ungetc(c, f);
1004 *p = '\0';
1005
1006 if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
1007 dprint(5, (debugfile, "getno: `%s' non-numeric\n", getbuf));
1008 *ep = -1;
1009 }
1010
1011 return((int32)atol(getbuf));
1012 }
1013
1014 /*
1015 - putconf - write configuration to .dir file
1016 */
1017 static int /* 0 success, -1 failure */
putconf(f,cp)1018 putconf(f, cp)
1019 register FILE *f;
1020 register struct dbzconfig *cp;
1021 {
1022 register int i;
1023 register int ret = 0;
1024
1025 if (fseek(f, (of_t)0, SEEK_SET) != 0) {
1026 dprint(5, (debugfile, "fseek failure in putconf\n"));
1027 ret = -1;
1028 }
1029 fprintf(f, "dbz %d %ld %d %ld %ld %d %d", dbzversion, cp->tsize,
1030 cp->fieldsep, cp->tagenb,
1031 cp->tagmask, cp->tagshift, cp->valuesize);
1032 for (i = 0; i < cp->valuesize; i++)
1033 fprintf(f, " %d", cp->bytemap[i]);
1034 fprintf(f, "\n");
1035 for (i = 0; i < NUSEDS; i++)
1036 fprintf(f, "%ld%c", cp->used[i], (i < NUSEDS-1) ? ' ' : '\n');
1037
1038 (void) fflush(f);
1039 if (ferror(f))
1040 ret = -1;
1041
1042 dprint(5, (debugfile, "putconf status %d\n", ret));
1043 return(ret);
1044 }
1045
1046 /*
1047 - getcore - try to set up an in-core copy of .pag file
1048 */
1049 static of_t * /* pointer to copy, or NULL */
getcore(db)1050 getcore(db)
1051 register DBZ *db;
1052 {
1053 register of_t *p;
1054 register size_t i;
1055 register size_t nread;
1056 register char *it;
1057
1058 it = malloc((size_t)db->dbz_conf.tsize * SOF);
1059 if (it == NULL) {
1060 dprint(5, (debugfile, "getcore: malloc failed\n"));
1061 return (of_t *)NULL;
1062 }
1063
1064 nread = fread(it, SOF, (size_t)db->dbz_conf.tsize, db->dbz_bufpagf);
1065 if (ferror(db->dbz_bufpagf)) {
1066 dprint(5, (debugfile, "getcore: read failed\n"));
1067 free((malloc_t)it);
1068 return (of_t *)NULL;
1069 }
1070
1071 p = (of_t *)it + nread;
1072 i = (size_t)db->dbz_conf.tsize - nread;
1073 while (i-- > 0)
1074 *p++ = VACANT;
1075 return((of_t *)it);
1076 }
1077
1078 /*
1079 - putcore - try to rewrite an in-core table
1080 */
1081 static int /* 0 okay, -1 fail */
putcore(db)1082 putcore(db)
1083 register DBZ *db;
1084 {
1085 if (fseek(db->dbz_bufpagf, (of_t)0, SEEK_SET) != 0) {
1086 dprint(5, (debugfile, "fseek failure in putcore\n"));
1087 return(-1);
1088 }
1089 (void) fwrite((char *)db->dbz_corepag, SOF, (size_t)db->dbz_conf.tsize, db->dbz_bufpagf);
1090 (void) fflush(db->dbz_bufpagf);
1091 return((ferror(db->dbz_bufpagf)) ? -1 : 0);
1092 }
1093
1094 /*
1095 - start - set up to start or restart a search
1096 */
1097 static void
start(db,kp,osp)1098 start(db, kp, osp)
1099 register DBZ *db;
1100 register datum *kp;
1101 register struct searcher *osp; /* may be FRESH, i.e. NULL */
1102 {
1103 register struct searcher *sp = &db->dbz_srch;
1104 register long h;
1105
1106 h = hash(kp->dptr, kp->dsize);
1107 if (osp != FRESH && osp->hash == h) {
1108 if (sp != osp)
1109 *sp = *osp;
1110 dprint(5, (debugfile, "search restarted\n"));
1111 } else {
1112 sp->hash = h;
1113 sp->tag = MKTAG(h / db->dbz_conf.tsize);
1114 dprint(5, (debugfile, "tag 0x%lx\n", sp->tag));
1115 sp->place = h % db->dbz_conf.tsize;
1116 sp->tabno = 0;
1117 sp->run = (db->dbz_conf.olddbz) ? db->dbz_conf.tsize : MAXRUN;
1118 sp->aborted = 0;
1119 }
1120 sp->seen = 0;
1121 }
1122
1123 /*
1124 - search - conduct part of a search
1125 */
1126 static of_t /* NOTFOUND if we hit VACANT or error */
search(db)1127 search(db)
1128 register DBZ *db;
1129 {
1130 register struct searcher *sp = &db->dbz_srch;
1131 register of_t dest;
1132 register of_t value;
1133 of_t val; /* buffer for value (can't fread register) */
1134 register of_t place;
1135
1136 if (sp->aborted)
1137 return(NOTFOUND);
1138
1139 for (;;) {
1140 /* determine location to be examined */
1141 place = sp->place;
1142 if (sp->seen) {
1143 /* go to next location */
1144 if (--sp->run <= 0) {
1145 sp->tabno++;
1146 sp->run = MAXRUN;
1147 }
1148 place = (place+1)%db->dbz_conf.tsize + sp->tabno*db->dbz_conf.tsize;
1149 sp->place = place;
1150 } else
1151 sp->seen = 1; /* now looking at current location */
1152 dprint(5, (debugfile, "search @ %ld\n", place));
1153
1154 /* get the tagged value */
1155 if (db->dbz_corepag != NULL && place < db->dbz_conf.tsize) {
1156 dprint(5, (debugfile, "search: in core\n"));
1157 value = MAPIN(db->dbz_corepag[place]);
1158 } else {
1159 /* seek, if necessary */
1160 dest = place * SOF;
1161 if (db->dbz_pagpos != dest) {
1162 if (fseek(db->dbz_pagf, dest, SEEK_SET) != 0) {
1163 dprint(5, (debugfile, "search: seek failed\n"));
1164 db->dbz_pagpos = -1;
1165 sp->aborted = 1;
1166 return(NOTFOUND);
1167 }
1168 db->dbz_pagpos = dest;
1169 }
1170
1171 /* read it */
1172 if (fread((char *)&val, sizeof(val), 1, db->dbz_pagf) == 1)
1173 value = MAPIN(val);
1174 else if (ferror(db->dbz_pagf)) {
1175 dprint(5, (debugfile, "search: read failed\n"));
1176 db->dbz_pagpos = -1;
1177 sp->aborted = 1;
1178 return(NOTFOUND);
1179 } else
1180 value = VACANT;
1181
1182 /* and finish up */
1183 db->dbz_pagpos += sizeof(val);
1184 }
1185
1186 /* vacant slot is always cause to return */
1187 if (value == VACANT) {
1188 dprint(5, (debugfile, "search: empty slot\n"));
1189 return(NOTFOUND);
1190 };
1191
1192 /* check the tag */
1193 value = UNBIAS(value);
1194 dprint(5, (debugfile, "got 0x%lx\n", value));
1195 if (!HASTAG(value)) {
1196 dprint(5, (debugfile, "tagless\n"));
1197 return(value);
1198 } else if ((TAG(value) == sp->tag) || db->dbz_taghere) {
1199 dprint(5, (debugfile, "match\n"));
1200 return(NOTAG(value));
1201 } else {
1202 dprint(5, (debugfile, "mismatch 0x%lx\n", TAG(value)));
1203 }
1204 }
1205 /* NOTREACHED */
1206 }
1207
1208 /*
1209 - okayvalue - check that a value can be stored
1210 */
1211 static int /* predicate */
okayvalue(db,value)1212 okayvalue(db, value)
1213 register DBZ *db;
1214 of_t value;
1215 {
1216 if (HASTAG(value))
1217 return(0);
1218 #ifdef OVERFLOW
1219 if (value == LONG_MAX) /* BIAS() and UNBIAS() will overflow */
1220 return(0);
1221 #endif
1222 return(1);
1223 }
1224
1225 /*
1226 - set - store a value into a location previously found by search
1227 */
1228 static int /* 0 success, -1 failure */
set(db,value)1229 set(db, value)
1230 register DBZ *db;
1231 of_t value;
1232 {
1233 register struct searcher *sp = &db->dbz_srch;
1234 register of_t place = sp->place;
1235 register of_t v = value;
1236
1237 if (sp->aborted)
1238 return(-1);
1239
1240 if (CANTAG(v) && !db->dbz_conf.olddbz) {
1241 v |= sp->tag | db->dbz_taghere;
1242 if (v != UNBIAS(VACANT)) /* BIAS(v) won't look VACANT */
1243 #ifdef OVERFLOW
1244 if (v != LONG_MAX) /* and it won't overflow */
1245 #endif
1246 value = v;
1247 }
1248 dprint(5, (debugfile, "tagged value is 0x%lx\n", value));
1249 value = BIAS(value);
1250 value = MAPOUT(value);
1251
1252 /* If we have the index file in memory, use it */
1253 if (db->dbz_corepag != NULL && place < db->dbz_conf.tsize) {
1254 db->dbz_corepag[place] = value;
1255 dprint(5, (debugfile, "set: incore\n"));
1256 return(0);
1257 }
1258
1259 /* seek to spot */
1260 db->dbz_pagpos = -1; /* invalidate position memory */
1261 if (fseek(db->dbz_pagf, place * SOF, SEEK_SET) != 0) {
1262 dprint(5, (debugfile, "set: seek failed\n"));
1263 sp->aborted = 1;
1264 return(-1);
1265 }
1266
1267 /* write in data */
1268 if (fwrite((char *)&value, SOF, 1, db->dbz_pagf) != 1) {
1269 dprint(5, (debugfile, "set: write failed\n"));
1270 sp->aborted = 1;
1271 return(-1);
1272 }
1273 /* fflush improves robustness, and buffer re-use is rare anyway */
1274 if (fflush(db->dbz_pagf) == EOF) {
1275 dprint(5, (debugfile, "set: fflush failed\n"));
1276 sp->aborted = 1;
1277 return(-1);
1278 }
1279
1280 dprint(5, (debugfile, "set: succeeded\n"));
1281 return(0);
1282 }
1283
1284 /*
1285 - mybytemap - determine this machine's byte map
1286 *
1287 * A byte map is an array of ints, sizeof(of_t) of them. The 0th int
1288 * is the byte number of the high-order byte in my of_t, and so forth.
1289 */
1290 static void
mybytemap(map)1291 mybytemap(map)
1292 int map[]; /* -> int[SOF] */
1293 {
1294 union {
1295 of_t o;
1296 char c[SOF];
1297 } u;
1298 register int *mp = &map[SOF];
1299 register int ntodo;
1300 register int i;
1301
1302 u.o = 1;
1303 for (ntodo = (int)SOF; ntodo > 0; ntodo--) {
1304 for (i = 0; i < SOF; i++)
1305 if (u.c[i] != 0)
1306 break;
1307 if (i == SOF) {
1308 /* trouble -- set it to *something* consistent */
1309 dprint(5, (debugfile, "mybytemap: nonexistent byte %d!!!\n", ntodo));
1310 for (i = 0; i < SOF; i++)
1311 map[i] = i;
1312 return;
1313 }
1314 dprint(5, (debugfile, "mybytemap: byte %d\n", i));
1315 *--mp = i;
1316 while (u.c[i] != 0)
1317 u.o <<= 1;
1318 }
1319 }
1320
1321 /*
1322 - bytemap - transform an of_t from byte ordering map1 to map2
1323 */
1324 static of_t /* transformed result */
bytemap(ino,map1,map2)1325 bytemap(ino, map1, map2)
1326 of_t ino;
1327 int *map1;
1328 int *map2;
1329 {
1330 union oc {
1331 of_t o;
1332 char c[SOF];
1333 };
1334 union oc in;
1335 union oc out;
1336 register int i;
1337
1338 in.o = ino;
1339 for (i = 0; i < SOF; i++)
1340 out.c[map2[i]] = in.c[map1[i]];
1341 return(out.o);
1342 }
1343
1344 /*
1345 * This is a simplified version of the pathalias hashing function.
1346 * Thanks to Steve Belovin and Peter Honeyman
1347 *
1348 * hash a string into a long int. 31 bit crc (from andrew appel).
1349 * the crc table is computed at run time by crcinit() -- we could
1350 * precompute, but it takes 1 clock tick on a 750.
1351 *
1352 * This fast table calculation works only if POLY is a prime polynomial
1353 * in the field of integers modulo 2. Since the coefficients of a
1354 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
1355 * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
1356 * 31 down to 25 are zero. Happily, we have candidates, from
1357 * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
1358 * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
1359 * x^31 + x^3 + x^0
1360 *
1361 * We reverse the bits to get:
1362 * 111101010000000000000000000000001 but drop the last 1
1363 * f 5 0 0 0 0 0 0
1364 * 010010000000000000000000000000001 ditto, for 31-bit crc
1365 * 4 8 0 0 0 0 0 0
1366 */
1367
1368 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
1369
1370 static long CrcTable[128];
1371
1372 /*
1373 - crcinit - initialize tables for hash function
1374 */
1375 static void
crcinit()1376 crcinit()
1377 {
1378 register int i, j;
1379 register long sum;
1380
1381 for (i = 0; i < 128; ++i) {
1382 sum = 0L;
1383 for (j = 7 - 1; j >= 0; --j)
1384 if (i & (1 << j))
1385 sum ^= POLY >> j;
1386 CrcTable[i] = sum;
1387 }
1388 dprint(5, (debugfile, "crcinit: done\n"));
1389 }
1390
1391 /*
1392 - hash - Honeyman's nice hashing function
1393 */
1394 static long
hash(name,size)1395 hash(name, size)
1396 register char *name;
1397 register int size;
1398 {
1399 register long sum = 0L;
1400
1401 while (size--) {
1402 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
1403 }
1404 dprint(5, (debugfile, "hash: returns (%ld)\n", sum));
1405 return(sum);
1406 }
1407
1408 /*
1409 - dbzdebug - control dbz debugging at run time
1410 */
1411 int /* old value */
dbzdebug(value)1412 dbzdebug(value)
1413 int value;
1414 {
1415 #ifdef DBZDEBUG
1416 register int old = debug;
1417
1418 debug = value;
1419 return(old);
1420 #else
1421 return(-1);
1422 #endif
1423 }
1424