5 Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
6 You can use this code in any manner, as long as you leave my name on it
7 and don't hold me responsible for any problems with it.
9 Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun 5 00:27:08 CDT 1988
11 Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
13 Major reworking by Henry Spencer as part of the C News project.
15 These routines replace dbm as used by the usenet news software
16 (it's not a full dbm replacement by any means). It's fast and
17 simple. It contains no AT&T code.
19 In general, dbz's files are 1/20 the size of dbm's. Lookup performance
20 is somewhat better, while file creation is spectacularly faster, especially
21 if the incore facility is used.
26 #include <sys/types.h>
36 * #ifdef index. "LIA" = "leave it alone unless you know what you're doing".
38 * FUNNYSEEKS SEEK_SET is not 0, get it from <unistd.h>
39 * INDEX_SIZE backward compatibility with old dbz; avoid using this
40 * NMEMORY number of days of memory for use in sizing new table (LIA)
41 * INCORE backward compatibility with old dbz; use dbzincore() instead
42 * DBZDEBUG enable debugging
43 * DEFSIZE default table size (not as critical as in old dbz)
44 * OLDBNEWS default case mapping as in old B News; set NOBUFFER
45 * BNEWS default case mapping as in current B News; set NOBUFFER
46 * DEFCASE default case-map algorithm selector
47 * NOTAGS fseek offsets are strange, do not do tagging (see below)
48 * NPAGBUF size of .pag buffer, in longs (LIA)
49 * SHISTBUF size of ASCII-file buffer, in bytes (LIA)
50 * MAXRUN length of run which shifts to next table (see below) (LIA)
51 * OVERFLOW long-int arithmetic overflow must be avoided, will trap
52 * NOBUFFER do not buffer hash-table i/o, B News locking is defective
64 static int dbzversion = 3; /* for validating .dir file format */
67 * The dbz database exploits the fact that when news stores a <key,value>
68 * tuple, the `value' part is a seek offset into a text file, pointing to
69 * a copy of the `key' part. This avoids the need to store a copy of
70 * the key in the dbz files. However, the text file *must* exist and be
71 * consistent with the dbz files, or things will fail.
73 * The basic format of the database is a simple hash table containing the
74 * values. A value is stored by indexing into the table using a hash value
75 * computed from the key; collisions are resolved by linear probing (just
76 * search forward for an empty slot, wrapping around to the beginning of
77 * the table if necessary). Linear probing is a performance disaster when
78 * the table starts to get full, so a complication is introduced. The
79 * database is actually one *or more* tables, stored sequentially in the
80 * .pag file, and the length of linear-probe sequences is limited. The
81 * search (for an existing item or an empty slot) always starts in the
82 * first table, and whenever MAXRUN probes have been done in table N,
83 * probing continues in table N+1. This behaves reasonably well even in
84 * cases of massive overflow. There are some other small complications
85 * added, see comments below.
87 * The table size is fixed for any particular database, but is determined
88 * dynamically when a database is rebuilt. The strategy is to try to pick
89 * the size so the first table will be no more than 2/3 full, that being
90 * slightly before the point where performance starts to degrade. (It is
91 * desirable to be a bit conservative because the overflow strategy tends
92 * to produce files with holes in them, which is a nuisance.)
96 * The following is for backward compatibility.
99 #define DEFSIZE INDEX_SIZE
103 * ANSI C says the offset argument to fseek is a long, not an off_t, for some
104 * reason. Let's use off_t anyway.
106 #define SOF (sizeof(off_t))
109 * We assume that unused areas of a binary file are zeros, and that the
110 * bit pattern of `(off_t)0' is all zeros. The alternative is rather
111 * painful file initialization. Note that okayvalue(), if OVERFLOW is
112 * defined, knows what value of an offset would cause overflow.
114 #define VACANT ((off_t)0)
115 #define BIAS(o) ((o)+1) /* make any valid off_t non-VACANT */
116 #define UNBIAS(o) ((o)-1) /* reverse BIAS() effect */
119 * In a Unix implementation, or indeed any in which an off_t is a byte
120 * count, there are a bunch of high bits free in an off_t. There is a
121 * use for them. Checking a possible hit by looking it up in the base
122 * file is relatively expensive, and the cost can be dramatically reduced
123 * by using some of those high bits to tag the value with a few more bits
124 * of the key's hash. This detects most false hits without the overhead of
125 * seek+read+strcmp. We use the top bit to indicate whether the value is
126 * tagged or not, and don't tag a value which is using the tag bits itself.
127 * We're in trouble if the off_t representation wants to use the top bit.
128 * The actual bitmasks and offset come from the configuration stuff,
129 * which permits fiddling with them as necessary, and also suppressing
130 * them completely (by defining the masks to 0). We build pre-shifted
131 * versions of the masks for efficiency.
133 static off_t tagbits; /* pre-shifted tag mask */
134 static off_t taghere; /* pre-shifted tag-enable bit */
135 static off_t tagboth; /* tagbits|taghere */
136 #define HASTAG(o) ((o)&taghere)
137 #define TAG(o) ((o)&tagbits)
138 #define NOTAG(o) ((o)&~tagboth)
139 #define CANTAG(o) (((o)&tagboth) == 0)
140 #define MKTAG(v) (((v)<<conf.tagshift)&tagbits)
143 * A new, from-scratch database, not built as a rebuild of an old one,
144 * needs to know table size, casemap algorithm, and tagging. Normally
145 * the user supplies this info, but there have to be defaults.
148 #define DEFSIZE 120011 /* 300007 might be better */
151 #define DEFCASE '0' /* B2.10 -- no mapping */
152 #define NOBUFFER /* B News locking is defective */
155 #define DEFCASE '=' /* B2.11 -- all mapped */
156 #define NOBUFFER /* B News locking is defective */
158 #ifndef DEFCASE /* C News compatibility is the default */
159 #define DEFCASE 'C' /* C News -- RFC822 mapping */
162 #define TAGENB 0x80 /* tag enable is top bit, tag is next 7 */
166 #define TAGENB 0 /* no tags */
172 * We read configuration info from the .dir file into this structure,
173 * so we can avoid wired-in assumptions for an existing database.
175 * Among the info is a record of recent peak usages, so that a new table
176 * size can be chosen intelligently when rebuilding. 10 is a good
177 * number of usages to keep, since news displays marked fluctuations
178 * in volume on a 7-day cycle.
181 int olddbz; /* .dir file empty but .pag not? */
182 off_t tsize; /* table size */
184 # define NMEMORY 10 /* # days of use info to remember */
186 # define NUSEDS (1+NMEMORY)
187 off_t used[NUSEDS]; /* entries used today, yesterday, ... */
188 int valuesize; /* size of table values, == SOF */
189 int bytemap[SOF]; /* byte-order map */
190 char casemap; /* case-mapping algorithm (see cipoint()) */
191 char fieldsep; /* field separator in base file, if any */
192 off_t tagenb; /* unshifted tag-enable bit */
193 off_t tagmask; /* unshifted tag mask */
194 int tagshift; /* shift count for tagmask and tagenb */
196 static struct dbzconfig conf;
197 static int getconf();
199 static int putconf();
200 static void mybytemap();
201 static off_t bytemap();
204 * For a program that makes many, many references to the database, it
205 * is a large performance win to keep the table in core, if it will fit.
206 * Note that this does hurt robustness in the event of crashes, and
207 * dbmclose() *must* be called to flush the in-core database to disk.
208 * The code is prepared to deal with the possibility that there isn't
209 * enough memory. There *is* an assumption that a size_t is big enough
210 * to hold the size (in bytes) of one table, so dbminit() tries to figure
211 * out whether this is possible first.
213 * The preferred way to ask for an in-core table is to do dbzincore(1)
214 * before dbminit(). The default is not to do it, although -DINCORE
215 * overrides this for backward compatibility with old dbz.
217 * We keep only the first table in core. This greatly simplifies the
218 * code, and bounds memory demand. Furthermore, doing this is a large
219 * performance win even in the event of massive overflow.
222 static int incore = 1;
224 static int incore = 0;
228 * Stdio buffer for .pag reads. Buffering more than about 16 does not help
229 * significantly at the densities we try to maintain, and the much larger
230 * buffers that most stdios default to are much more expensive to fill.
231 * With small buffers, stdio is performance-competitive with raw read(),
232 * and it's much more portable.
239 static off_t pagbuf[NPAGBUF]; /* only needed if !NOBUFFER && _IOFBF */
244 * Stdio buffer for base-file reads. Message-IDs (all news ever needs to
245 * read) are essentially never longer than 64 bytes, and the typical stdio
246 * buffer is so much larger that it is much more expensive to fill.
252 static char basebuf[SHISTBUF]; /* only needed if _IOFBF exists */
256 * Data structure for recording info about searches.
259 off_t place; /* current location in file */
260 int tabno; /* which table we're in */
261 int run; /* how long we'll stay in this table */
265 long hash; /* the key's hash code (for optimization) */
266 off_t tag; /* tag we are looking for */
267 int seen; /* have we examined current location? */
268 int aborted; /* has i/o error aborted search? */
271 #define FRESH ((struct searcher *)NULL)
272 static off_t search();
273 #define NOTFOUND ((off_t)-1)
274 static int okayvalue();
278 * Arguably the searcher struct for a given routine ought to be local to
279 * it, but a fetch() is very often immediately followed by a store(), and
280 * in some circumstances it is a useful performance win to remember where
281 * the fetch() completed. So we use a global struct and remember whether
284 static struct searcher srch;
285 static struct searcher *prevp; /* &srch or FRESH */
287 /* byte-ordering stuff */
288 static int mybmap[SOF]; /* my byte order (see mybytemap()) */
289 static int bytesame; /* is database order same as mine? */
290 #define MAPIN(o) ((bytesame) ? (o) : bytemap((o), conf.bytemap, mybmap))
291 #define MAPOUT(o) ((bytesame) ? (o) : bytemap((o), mybmap, conf.bytemap))
294 * The double parentheses needed to make this work are ugly, but the
295 * alternative (under most compilers) is to pack around 2K of unused
296 * strings -- there's just no way to get rid of them.
298 static int debug; /* controlled by dbzdebug() */
300 #define DEBUG(args) if (debug) { (void) printf args ; }
302 #define DEBUG(args) ;
306 extern char *malloc();
307 extern char *calloc();
308 extern void free(); /* ANSI C; some old implementations say int */
314 static void crcinit();
315 static char *cipoint();
316 static char *mapcase();
317 static int isprime();
318 static FILE *latebase();
320 /* file-naming stuff */
321 static char dir[] = ".dir";
322 static char pag[] = ".pag";
323 static char *enstring();
325 /* central data structures */
326 static FILE *basef; /* descriptor for base file */
327 static char *basefname; /* name for not-yet-opened base file */
328 static FILE *dirf; /* descriptor for .dir file */
329 static int dirronly; /* dirf open read-only? */
330 static FILE *pagf = NULL; /* descriptor for .pag file */
331 static off_t pagpos; /* posn in pagf; only search may set != -1 */
332 static int pagronly; /* pagf open read-only? */
333 static off_t *corepag; /* incore version of .pag file, if any */
334 static FILE *bufpagf; /* well-buffered pagf, for incore rewrite */
335 static off_t *getcore();
336 static int putcore();
337 static int written; /* has a store() been done? */
340 - dbzfresh - set up a new database, no historical info
342 int /* 0 success, -1 failure */
343 dbzfresh(name, size, fs, cmap, tagmask)
344 char *name; /* base name; .dir and .pag must exist */
345 long size; /* table size (0 means default) */
346 int fs; /* field-separator character in base file */
347 int cmap; /* case-map algorithm (0 means default) */
348 off_t tagmask; /* 0 default, 1 no tags */
356 DEBUG(("dbzfresh: database already open\n"));
359 if (size != 0 && size < 2) {
360 DEBUG(("dbzfresh: preposterous size (%ld)\n", size));
364 /* get default configuration */
365 if (getconf((FILE *)NULL, (FILE *)NULL, &c) < 0)
366 return(-1); /* "can't happen" */
368 /* and mess with it as specified */
375 case 'B': /* 2.10 compat */
376 c.casemap = '0'; /* '\0' nicer, but '0' printable! */
379 case 'b': /* 2.11 compat */
389 DEBUG(("dbzfresh case map `%c' unknown\n", cmap));
394 case 0: /* default */
396 case 1: /* no tags */
409 c.tagenb = (m << 1) & ~m;
414 fn = enstring(name, dir);
420 DEBUG(("dbzfresh: unable to write config\n"));
423 if (putconf(f, &c) < 0) {
427 if (fclose(f) == EOF) {
428 DEBUG(("dbzfresh: fclose failure\n"));
432 /* create/truncate .pag */
433 fn = enstring(name, pag);
439 DEBUG(("dbzfresh: unable to create/truncate .pag file\n"));
444 /* and punt to dbminit for the hard work */
445 return(dbminit(name));
449 - dbzsize - what's a good table size to hold this many entries?
453 long contents; /* 0 means what's the default */
457 if (contents <= 0) { /* foulup or default inquiry */
458 DEBUG(("dbzsize: preposterous input (%ld)\n", contents));
461 n = (contents/2)*3; /* try to keep table at most 2/3 full */
462 if (!(n&01)) /* make it odd */
464 DEBUG(("dbzsize: tentative size %ld\n", n));
465 while (!isprime(n)) /* and look for a prime */
467 DEBUG(("dbzsize: final size %ld\n", n));
473 - isprime - is a number prime?
475 * This is not a terribly efficient approach.
477 static int /* predicate */
481 static int quick[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0 };
486 /* hit the first few primes quickly to eliminate easy ones */
487 /* this incidentally prevents ridiculously small tables */
488 for (ip = quick; (div = *ip) != 0; ip++)
490 DEBUG(("isprime: quick result on %ld\n", (long)x));
494 /* approximate square root of x */
495 for (stop = x; x/stop < stop; stop >>= 1)
499 /* try odd numbers up to stop */
500 for (div = *--ip; div < stop; div += 2)
508 - dbzagain - set up a new database to be a rebuild of an old one
510 int /* 0 success, -1 failure */
511 dbzagain(name, oldname)
512 char *name; /* base name; .dir and .pag must exist */
513 char *oldname; /* base name; all must exist */
520 register int newtable;
521 register off_t newsize;
524 DEBUG(("dbzagain: database already open\n"));
528 /* pick up the old configuration */
529 fn = enstring(oldname, dir);
535 DEBUG(("dbzagain: cannot open old .dir file\n"));
538 i = getconf(f, (FILE *)NULL, &c);
541 DEBUG(("dbzagain: getconf failed\n"));
548 for (i = 0; i < NUSEDS; i++) {
552 newtable = 1; /* hasn't got full usage history yet */
555 DEBUG(("dbzagain: old table has no contents!\n"));
558 for (i = NUSEDS-1; i > 0; i--)
559 c.used[i] = c.used[i-1];
561 newsize = dbzsize(top);
562 if (!newtable || newsize > c.tsize) /* don't shrink new table */
566 fn = enstring(name, dir);
572 DEBUG(("dbzagain: unable to write new .dir\n"));
578 DEBUG(("dbzagain: putconf failed\n"));
582 /* create/truncate .pag */
583 fn = enstring(name, pag);
589 DEBUG(("dbzagain: unable to create/truncate .pag file\n"));
594 /* and let dbminit do the work */
595 return(dbminit(name));
599 - dbminit - open a database, creating it (using defaults) if necessary
601 * We try to leave errno set plausibly, to the extent that underlying
602 * functions permit this, since many people consult it if dbminit() fails.
604 int /* 0 success, -1 failure */
610 register char *dirfname;
611 register char *pagfname;
614 DEBUG(("dbminit: dbminit already called once\n"));
619 /* open the .dir file */
620 dirfname = enstring(name, dir);
621 if (dirfname == NULL)
623 dirf = fopen(dirfname, "r+");
625 dirf = fopen(dirfname, "r");
631 DEBUG(("dbminit: can't open .dir file\n"));
635 /* open the .pag file */
636 pagfname = enstring(name, pag);
637 if (pagfname == NULL) {
641 pagf = fopen(pagfname, "r+b");
643 pagf = fopen(pagfname, "rb");
645 DEBUG(("dbminit: .pag open failed\n"));
657 * B News does not do adequate locking on its database accesses.
658 * Why it doesn't get into trouble using dbm is a mystery. In any
659 * case, doing unbuffered i/o does not cure the problem, but does
660 * enormously reduce its incidence.
662 (void) setbuf(pagf, (char *)NULL);
665 (void) setvbuf(pagf, (char *)pagbuf, _IOFBF, sizeof(pagbuf));
669 /* don't free pagfname, need it below */
671 /* open the base file */
672 basef = fopen(name, "r");
674 DEBUG(("dbminit: basefile open failed\n"));
675 basefname = enstring(name, "");
676 if (basefname == NULL) {
687 (void) setvbuf(basef, basebuf, _IOFBF, sizeof(basebuf));
690 /* pick up configuration */
691 if (getconf(dirf, pagf, &conf) < 0) {
692 DEBUG(("dbminit: getconf failure\n"));
693 (void) fclose(basef);
698 errno = EDOM; /* kind of a kludge, but very portable */
701 tagbits = conf.tagmask << conf.tagshift;
702 taghere = conf.tagenb << conf.tagshift;
703 tagboth = tagbits | taghere;
706 for (i = 0; i < SOF; i++)
707 if (mybmap[i] != conf.bytemap[i])
710 /* get first table into core, if it looks desirable and feasible */
711 s = (size_t)conf.tsize * SOF;
712 if (incore && (off_t)(s/SOF) == conf.tsize) {
713 bufpagf = fopen(pagfname, (pagronly) ? "rb" : "r+b");
715 corepag = getcore(bufpagf);
726 DEBUG(("dbminit: succeeded\n"));
731 - enstring - concatenate two strings into a malloced area
733 static char * /* NULL if malloc fails */
740 p = malloc((size_t)strlen(s1) + (size_t)strlen(s2) + 1);
742 (void) strcpy(p, s1);
743 (void) strcat(p, s2);
745 DEBUG(("enstring(%s, %s) out of memory\n", s1, s2));
751 - dbmclose - close a database
756 register int ret = 0;
759 DEBUG(("dbmclose: not opened!\n"));
763 if (fclose(pagf) == EOF) {
764 DEBUG(("dbmclose: fclose(pagf) failed\n"));
767 pagf = basef; /* ensure valid pointer; dbzsync checks it */
770 if (bufpagf != NULL && fclose(bufpagf) == EOF) {
771 DEBUG(("dbmclose: fclose(bufpagf) failed\n"));
775 free((char *)corepag);
777 if (fclose(basef) == EOF) {
778 DEBUG(("dbmclose: fclose(basef) failed\n"));
781 if (basefname != NULL)
785 if (fclose(dirf) == EOF) {
786 DEBUG(("dbmclose: fclose(dirf) failed\n"));
790 DEBUG(("dbmclose: %s\n", (ret == 0) ? "succeeded" : "failed"));
795 - dbzsync - push all in-core data out to disk
800 register int ret = 0;
803 DEBUG(("dbzsync: not opened!\n"));
809 if (corepag != NULL) {
810 if (putcore(corepag, bufpagf) < 0) {
811 DEBUG(("dbzsync: putcore failed\n"));
816 if (putconf(dirf, &conf) < 0)
819 DEBUG(("dbzsync: %s\n", (ret == 0) ? "succeeded" : "failed"));
824 - dbzcancel - cancel writing of in-core data
825 * Mostly for use from child processes.
826 * Note that we don't need to futz around with stdio buffers, because we
827 * always fflush them immediately anyway and so they never have stale data.
833 DEBUG(("dbzcancel: not opened!\n"));
842 - dbzfetch - fetch() with case mapping built in
848 char buffer[DBZMAXKEY + 1];
850 register size_t keysize;
852 DEBUG(("dbzfetch: (%s)\n", key.dptr));
854 /* Key is supposed to be less than DBZMAXKEY */
856 if (keysize >= DBZMAXKEY) {
858 DEBUG(("keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
861 mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
862 buffer[keysize] = '\0'; /* just a debug aid */
863 mappedkey.dsize = keysize;
865 return(fetch(mappedkey));
869 - fetch - get an entry from the database
871 * Disgusting fine point, in the name of backward compatibility: if the
872 * last character of "key" is a NUL, that character is (effectively) not
873 * part of the comparison against the stored keys.
875 datum /* dptr NULL, dsize 0 means failure */
879 char buffer[DBZMAXKEY + 1];
880 static off_t key_ptr; /* return value points here */
882 register size_t keysize;
883 register size_t cmplen;
886 DEBUG(("fetch: (%s)\n", key.dptr));
891 /* Key is supposed to be less than DBZMAXKEY */
893 if (keysize >= DBZMAXKEY) {
895 DEBUG(("keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
899 DEBUG(("fetch: database not open!\n"));
901 } else if (basef == NULL) { /* basef didn't exist yet */
908 sepp = &conf.fieldsep;
909 if (key.dptr[keysize-1] == '\0') {
911 sepp = &buffer[keysize-1];
913 start(&srch, &key, FRESH);
914 while ((key_ptr = search(&srch)) != NOTFOUND) {
915 DEBUG(("got 0x%lx\n", key_ptr));
918 if (fseek(basef, key_ptr, SEEK_SET) != 0) {
919 DEBUG(("fetch: seek failed\n"));
922 if (fread(buffer, 1, keysize, basef) != keysize) {
923 DEBUG(("fetch: read failed\n"));
928 buffer[keysize] = '\0'; /* terminated for DEBUG */
929 (void) mapcase(buffer, buffer, keysize);
930 DEBUG(("fetch: buffer (%s) looking for (%s) size = %d\n",
931 buffer, key.dptr, keysize));
932 if (memcmp(key.dptr, buffer, cmplen) == 0 &&
933 (*sepp == conf.fieldsep || *sepp == '\0')) {
935 output.dptr = (char *)&key_ptr;
937 DEBUG(("fetch: successful\n"));
942 /* we didn't find it */
943 DEBUG(("fetch: failed\n"));
944 prevp = &srch; /* remember where we stopped */
949 - latebase - try to open a base file that wasn't there at the start
956 if (basefname == NULL) {
957 DEBUG(("latebase: name foulup\n"));
960 it = fopen(basefname, "r");
962 DEBUG(("latebase: still can't open base\n"));
964 DEBUG(("latebase: late open succeeded\n"));
968 (void) setvbuf(it, basebuf, _IOFBF, sizeof(basebuf));
975 - dbzstore - store() with case mapping built in
982 char buffer[DBZMAXKEY + 1];
984 register size_t keysize;
986 DEBUG(("dbzstore: (%s)\n", key.dptr));
988 /* Key is supposed to be less than DBZMAXKEY */
990 if (keysize >= DBZMAXKEY) {
991 DEBUG(("dbzstore: key size too big (%d)\n", key.dsize));
995 mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
996 buffer[keysize] = '\0'; /* just a debug aid */
997 mappedkey.dsize = keysize;
999 return(store(mappedkey, data));
1003 - store - add an entry to the database
1005 int /* 0 success, -1 failure */
1013 DEBUG(("store: database not open!\n"));
1015 } else if (basef == NULL) { /* basef didn't exist yet */
1021 DEBUG(("store: database open read-only\n"));
1024 if (data.dsize != SOF) {
1025 DEBUG(("store: value size wrong (%d)\n", data.dsize));
1028 if (key.dsize >= DBZMAXKEY) {
1029 DEBUG(("store: key size too big (%d)\n", key.dsize));
1033 /* copy the value in to ensure alignment */
1034 (void) memcpy((char *)&value, data.dptr, SOF);
1035 DEBUG(("store: (%s, %ld)\n", key.dptr, (long)value));
1036 if (!okayvalue(value)) {
1037 DEBUG(("store: reserved bit or overflow in 0x%lx\n", value));
1041 /* find the place, exploiting previous search if possible */
1042 start(&srch, &key, prevp);
1043 while (search(&srch) != NOTFOUND)
1048 DEBUG(("store: used count %ld\n", conf.used[0]));
1050 return(set(&srch, value));
1054 - dbzincore - control attempts to keep .pag file in core
1056 int /* old setting */
1060 register int old = incore;
1067 - getconf - get configuration from .dir file
1069 static int /* 0 success, -1 failure */
1071 register FILE *df; /* NULL means just give me the default */
1072 register FILE *pf; /* NULL means don't care about .pag */
1073 register struct dbzconfig *cp;
1079 c = (df != NULL) ? getc(df) : EOF;
1080 if (c == EOF) { /* empty file, no configuration known */
1082 if (df != NULL && pf != NULL && getc(pf) != EOF)
1084 cp->tsize = DEFSIZE;
1085 cp->fieldsep = '\t';
1086 for (i = 0; i < NUSEDS; i++)
1088 cp->valuesize = SOF;
1089 mybytemap(cp->bytemap);
1090 cp->casemap = DEFCASE;
1091 cp->tagenb = TAGENB;
1092 cp->tagmask = TAGMASK;
1093 cp->tagshift = TAGSHIFT;
1094 DEBUG(("getconf: defaults (%ld, %c, (0x%lx/0x%lx<<%d))\n",
1095 cp->tsize, cp->casemap, cp->tagenb,
1096 cp->tagmask, cp->tagshift));
1099 (void) ungetc(c, df);
1101 /* first line, the vital stuff */
1102 if (getc(df) != 'd' || getc(df) != 'b' || getc(df) != 'z')
1104 if (getno(df, &err) != dbzversion)
1106 cp->tsize = getno(df, &err);
1107 cp->fieldsep = getno(df, &err);
1108 while ((c = getc(df)) == ' ')
1111 cp->tagenb = getno(df, &err);
1112 cp->tagmask = getno(df, &err);
1113 cp->tagshift = getno(df, &err);
1114 cp->valuesize = getno(df, &err);
1115 if (cp->valuesize != SOF) {
1116 DEBUG(("getconf: wrong off_t size (%d)\n", cp->valuesize));
1118 cp->valuesize = SOF; /* to protect the loops below */
1120 for (i = 0; i < cp->valuesize; i++)
1121 cp->bytemap[i] = getno(df, &err);
1122 if (getc(df) != '\n')
1124 DEBUG(("size %ld, sep %d, cmap %c, tags 0x%lx/0x%lx<<%d, ", cp->tsize,
1125 cp->fieldsep, cp->casemap, cp->tagenb, cp->tagmask,
1127 DEBUG(("bytemap (%d)", cp->valuesize));
1128 for (i = 0; i < cp->valuesize; i++) {
1129 DEBUG((" %d", cp->bytemap[i]));
1133 /* second line, the usages */
1134 for (i = 0; i < NUSEDS; i++)
1135 cp->used[i] = getno(df, &err);
1136 if (getc(df) != '\n')
1138 DEBUG(("used %ld %ld %ld...\n", cp->used[0], cp->used[1], cp->used[2]));
1141 DEBUG(("getconf error\n"));
1148 - getno - get a long
1160 while ((c = getc(f)) == ' ')
1162 if (c == EOF || c == '\n') {
1163 DEBUG(("getno: missing number\n"));
1169 while ((c = getc(f)) != EOF && c != '\n' && c != ' ')
1170 if (p < &getbuf[MAXN-1])
1173 DEBUG(("getno: EOF\n"));
1176 (void) ungetc(c, f);
1179 if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
1180 DEBUG(("getno: `%s' non-numeric\n", getbuf));
1183 return(atol(getbuf));
1187 - putconf - write configuration to .dir file
1189 static int /* 0 success, -1 failure */
1192 register struct dbzconfig *cp;
1195 register int ret = 0;
1197 if (fseek(f, 0, SEEK_SET) != 0) {
1198 DEBUG(("fseek failure in putconf\n"));
1201 fprintf(f, "dbz %d %ld %d %c %ld %ld %d %d", dbzversion,
1203 cp->fieldsep, cp->casemap, (long)cp->tagenb,
1204 (long)cp->tagmask, cp->tagshift,
1207 for (i = 0; i < cp->valuesize; i++)
1208 fprintf(f, " %d", cp->bytemap[i]);
1210 for (i = 0; i < NUSEDS; i++)
1212 (long)cp->used[i], (i < NUSEDS-1) ? ' ' : '\n');
1219 DEBUG(("putconf status %d\n", ret));
1224 - getcore - try to set up an in-core copy of .pag file
1226 static off_t * /* pointer to copy, or NULL */
1232 register size_t nread;
1235 it = malloc((size_t)conf.tsize * SOF);
1237 DEBUG(("getcore: malloc failed\n"));
1241 nread = fread(it, SOF, (size_t)conf.tsize, f);
1243 DEBUG(("getcore: read failed\n"));
1248 p = (off_t *)it + nread;
1249 i = (size_t)conf.tsize - nread;
1252 return((off_t *)it);
1256 - putcore - try to rewrite an in-core table
1258 static int /* 0 okay, -1 fail */
1263 if (fseek(f, 0, SEEK_SET) != 0) {
1264 DEBUG(("fseek failure in putcore\n"));
1267 (void) fwrite((char *)tab, SOF, (size_t)conf.tsize, f);
1269 return((ferror(f)) ? -1 : 0);
1273 - start - set up to start or restart a search
1277 register struct searcher *sp;
1279 register struct searcher *osp; /* may be FRESH, i.e. NULL */
1283 h = hash(kp->dptr, kp->dsize);
1284 if (osp != FRESH && osp->hash == h) {
1287 DEBUG(("search restarted\n"));
1290 sp->tag = MKTAG(h / conf.tsize);
1291 DEBUG(("tag 0x%lx\n", sp->tag));
1292 sp->place = h % conf.tsize;
1294 sp->run = (conf.olddbz) ? conf.tsize : MAXRUN;
1301 - search - conduct part of a search
1303 static off_t /* NOTFOUND if we hit VACANT or error */
1305 register struct searcher *sp;
1307 register off_t dest;
1308 register off_t value;
1309 off_t val; /* buffer for value (can't fread register) */
1310 register off_t place;
1316 /* determine location to be examined */
1319 /* go to next location */
1320 if (--sp->run <= 0) {
1324 place = (place+1)%conf.tsize + sp->tabno*conf.tsize;
1327 sp->seen = 1; /* now looking at current location */
1328 DEBUG(("search @ %ld\n", place));
1330 /* get the tagged value */
1331 if (corepag != NULL && place < conf.tsize) {
1332 DEBUG(("search: in core\n"));
1333 value = MAPIN(corepag[place]);
1335 /* seek, if necessary */
1337 if (pagpos != dest) {
1338 if (fseek(pagf, dest, SEEK_SET) != 0) {
1339 DEBUG(("search: seek failed\n"));
1348 if (fread((char *)&val, sizeof(val), 1, pagf) == 1)
1350 else if (ferror(pagf)) {
1351 DEBUG(("search: read failed\n"));
1359 pagpos += sizeof(val);
1362 /* vacant slot is always cause to return */
1363 if (value == VACANT) {
1364 DEBUG(("search: empty slot\n"));
1369 value = UNBIAS(value);
1370 DEBUG(("got 0x%lx\n", value));
1371 if (!HASTAG(value)) {
1372 DEBUG(("tagless\n"));
1374 } else if (TAG(value) == sp->tag) {
1376 return(NOTAG(value));
1378 DEBUG(("mismatch 0x%lx\n", TAG(value)));
1385 - okayvalue - check that a value can be stored
1387 static int /* predicate */
1394 if (value == LONG_MAX) /* BIAS() and UNBIAS() will overflow */
1401 - set - store a value into a location previously found by search
1403 static int /* 0 success, -1 failure */
1405 register struct searcher *sp;
1408 register off_t place = sp->place;
1409 register off_t v = value;
1414 if (CANTAG(v) && !conf.olddbz) {
1415 v |= sp->tag | taghere;
1416 if (v != UNBIAS(VACANT)) /* BIAS(v) won't look VACANT */
1418 if (v != LONG_MAX) /* and it won't overflow */
1422 DEBUG(("tagged value is 0x%lx\n", value));
1423 value = BIAS(value);
1424 value = MAPOUT(value);
1426 /* If we have the index file in memory, use it */
1427 if (corepag != NULL && place < conf.tsize) {
1428 corepag[place] = value;
1429 DEBUG(("set: incore\n"));
1434 pagpos = -1; /* invalidate position memory */
1435 if (fseek(pagf, place * SOF, SEEK_SET) != 0) {
1436 DEBUG(("set: seek failed\n"));
1442 if (fwrite((char *)&value, SOF, 1, pagf) != 1) {
1443 DEBUG(("set: write failed\n"));
1447 /* fflush improves robustness, and buffer re-use is rare anyway */
1448 if (fflush(pagf) == EOF) {
1449 DEBUG(("set: fflush failed\n"));
1454 DEBUG(("set: succeeded\n"));
1459 - mybytemap - determine this machine's byte map
1461 * A byte map is an array of ints, sizeof(off_t) of them. The 0th int
1462 * is the byte number of the high-order byte in my off_t, and so forth.
1466 int map[]; /* -> int[SOF] */
1472 register int *mp = &map[SOF];
1477 for (ntodo = (int)SOF; ntodo > 0; ntodo--) {
1478 for (i = 0; i < SOF; i++)
1482 /* trouble -- set it to *something* consistent */
1483 DEBUG(("mybytemap: nonexistent byte %d!!!\n", ntodo));
1484 for (i = 0; i < SOF; i++)
1488 DEBUG(("mybytemap: byte %d\n", i));
1496 - bytemap - transform an off_t from byte ordering map1 to map2
1498 static off_t /* transformed result */
1499 bytemap(ino, map1, map2)
1513 for (i = 0; i < SOF; i++)
1514 out.c[map2[i]] = in.c[map1[i]];
1519 * This is a simplified version of the pathalias hashing function.
1520 * Thanks to Steve Belovin and Peter Honeyman
1522 * hash a string into a long int. 31 bit crc (from andrew appel).
1523 * the crc table is computed at run time by crcinit() -- we could
1524 * precompute, but it takes 1 clock tick on a 750.
1526 * This fast table calculation works only if POLY is a prime polynomial
1527 * in the field of integers modulo 2. Since the coefficients of a
1528 * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
1529 * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
1530 * 31 down to 25 are zero. Happily, we have candidates, from
1531 * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
1532 * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
1535 * We reverse the bits to get:
1536 * 111101010000000000000000000000001 but drop the last 1
1538 * 010010000000000000000000000000001 ditto, for 31-bit crc
1542 #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
1544 static long CrcTable[128];
1547 - crcinit - initialize tables for hash function
1555 for (i = 0; i < 128; ++i) {
1557 for (j = 7 - 1; j >= 0; --j)
1562 DEBUG(("crcinit: done\n"));
1566 - hash - Honeyman's nice hashing function
1570 register char *name;
1573 register long sum = 0L;
1576 sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
1578 DEBUG(("hash: returns (%ld)\n", sum));
1583 * case-mapping stuff
1585 * Borrowed from C News, by permission of the authors. Somewhat modified.
1587 * We exploit the fact that we are dealing only with headers here, and
1588 * headers are limited to the ASCII characters by RFC822. It is barely
1589 * possible that we might be dealing with a translation into another
1590 * character set, but in particular it's very unlikely for a header
1591 * character to be outside -128..255.
1593 * Life would be a whole lot simpler if tolower() could safely and portably
1594 * be applied to any char.
1597 #define OFFSET 128 /* avoid trouble with negative chars */
1599 /* must call casencmp before invoking TOLOW... */
1600 #define TOLOW(c) (cmap[(c)+OFFSET])
1602 /* ...but the use of it in CISTREQN is safe without the preliminary call (!) */
1603 /* CISTREQN is an optimised case-insensitive strncmp(a,b,n)==0; n > 0 */
1604 #define CISTREQN(a, b, n) \
1605 (TOLOW((a)[0]) == TOLOW((b)[0]) && casencmp(a, b, n) == 0)
1607 #define MAPSIZE (256+OFFSET)
1608 static char cmap[MAPSIZE]; /* relies on init to '\0' */
1609 static int mprimed = 0; /* has cmap been set up? */
1612 - mapprime - set up case-mapping stuff
1621 static char lower[] = "abcdefghijklmnopqrstuvwxyz";
1622 static char upper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1624 for (lp = lower, up = upper; *lp != '\0'; lp++, up++) {
1627 cmap[*up+OFFSET] = c;
1629 for (i = 0; i < MAPSIZE; i++)
1630 if (cmap[i] == '\0')
1631 cmap[i] = (char)(i-OFFSET);
1636 - casencmp - case-independent strncmp
1638 static int /* < == > 0 */
1639 casencmp(s1, s2, len)
1654 while (--n >= 0 && *p1 != '\0' && TOLOW(*p1) == TOLOW(*p2)) {
1662 * The following case analysis is necessary so that characters
1663 * which look negative collate low against normal characters but
1664 * high against the end-of-string NUL.
1666 if (*p1 == '\0' && *p2 == '\0')
1668 else if (*p1 == '\0')
1670 else if (*p2 == '\0')
1673 return(TOLOW(*p1) - TOLOW(*p2));
1677 - mapcase - do case-mapped copy
1679 static char * /* returns src or dst */
1680 mapcase(dst, src, siz)
1681 char *dst; /* destination, used only if mapping needed */
1682 char *src; /* source; src == dst is legal */
1687 register char *c; /* case break */
1688 register char *e; /* end of source */
1691 c = cipoint(src, siz);
1710 - cipoint - where in this message-ID does it become case-insensitive?
1712 * The RFC822 code is not quite complete. Absolute, total, full RFC822
1713 * compliance requires a horrible parsing job, because of the arcane
1714 * quoting conventions -- abc"def"ghi is not equivalent to abc"DEF"ghi,
1715 * for example. There are three or four things that might occur in the
1716 * domain part of a message-id that are case-sensitive. They don't seem
1717 * to ever occur in real news, thank Cthulhu. (What? You were expecting
1718 * a merciful and forgiving deity to be invoked in connection with RFC822?
1719 * Forget it; none of them would come near it.)
1721 static char * /* pointer into s, or NULL for "nowhere" */
1727 static char post[] = "postmaster";
1728 static int plen = sizeof(post)-1;
1730 switch (conf.casemap) {
1731 case '0': /* unmapped, sensible */
1734 case 'C': /* C News, RFC 822 conformant (approx.) */
1735 p = memchr(s, '@', siz);
1736 if (p == NULL) /* no local/domain split */
1737 return(NULL); /* assume all local */
1738 else if (p - (s+1) == plen && CISTREQN(s+1, post, plen)) {
1739 /* crazy -- "postmaster" is case-insensitive */
1744 case '=': /* 2.11, neither sensible nor conformant */
1745 return(s); /* all case-insensitive */
1749 DEBUG(("cipoint: unknown case mapping `%c'\n", conf.casemap));
1750 return(NULL); /* just leave it alone */
1754 - dbzdebug - control dbz debugging at run time
1761 register int old = debug;