dbz.c
上传用户:minyiyu
上传日期:2018-12-24
资源大小:864k
文件大小:47k
- /*
- dbz.c V3.2
- Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
- You can use this code in any manner, as long as you leave my name on it
- and don't hold me responsible for any problems with it.
- Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun 5 00:27:08 CDT 1988
- Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
- Major reworking by Henry Spencer as part of the C News project.
- Minor lint and CodeCenter (Saber) fluff removal by Rich $alz (March, 1991).
- Non-portable CloseOnExec() calls added by Rich $alz (September, 1991).
- Added "writethrough" and tagmask calculation code from
- <rob@violet.berkeley.edu> and <leres@ee.lbl.gov> by Rich $alz (December, 1992).
- Merged in MMAP code by David Robinson, formerly <david@elroy.jpl.nasa.gov>
- now <david.robinson@sun.com> (January, 1993).
- These routines replace dbm as used by the usenet news software
- (it's not a full dbm replacement by any means). It's fast and
- simple. It contains no AT&T code.
- In general, dbz's files are 1/20 the size of dbm's. Lookup performance
- is somewhat better, while file creation is spectacularly faster, especially
- if the incore facility is used.
- */
- #include <stdio.h>
- #include <sys/types.h>
- #include <sys/stat.h>
- #include <ctype.h>
- #include <errno.h>
- #ifndef __STDC__
- extern int errno;
- #endif
- #include <dbz.h>
- #include "clibrary.h"
- /*
- * #ifdef index. "LIA" = "leave it alone unless you know what you're doing".
- *
- * FUNNYSEEKS SEEK_SET is not 0, get it from <unistd.h>
- * INDEX_SIZE backward compatibility with old dbz; avoid using this
- * NMEMORY number of days of memory for use in sizing new table (LIA)
- * INCORE backward compatibility with old dbz; use dbzincore() instead
- * DBZDEBUG enable debugging
- * DEFSIZE default table size (not as critical as in old dbz)
- * OLDBNEWS default case mapping as in old B News; set NOBUFFER
- * BNEWS default case mapping as in current B News; set NOBUFFER
- * DEFCASE default case-map algorithm selector
- * NOTAGS fseek offsets are strange, do not do tagging (see below)
- * NPAGBUF size of .pag buffer, in longs (LIA)
- * SHISTBUF size of ASCII-file buffer, in bytes (LIA)
- * MAXRUN length of run which shifts to next table (see below) (LIA)
- * OVERFLOW long-int arithmetic overflow must be avoided, will trap
- * NOBUFFER do not buffer hash-table i/o, B News locking is defective
- * MMAP Use SunOS style mmap() for efficient incore
- */
- /* SUPPRESS 530 *//* Empty body for statement */
- /* SUPPRESS 701 on free *//* Conflicting declaration */
- #ifdef FUNNYSEEKS
- #include <unistd.h>
- #else
- #define SEEK_SET 0
- #endif
- #ifdef OVERFLOW
- #include <limits.h>
- #endif
- static int dbzversion = 3; /* for validating .dir file format */
- /*
- * The dbz database exploits the fact that when news stores a <key,value>
- * tuple, the `value' part is a seek offset into a text file, pointing to
- * a copy of the `key' part. This avoids the need to store a copy of
- * the key in the dbz files. However, the text file *must* exist and be
- * consistent with the dbz files, or things will fail.
- *
- * The basic format of the database is a simple hash table containing the
- * values. A value is stored by indexing into the table using a hash value
- * computed from the key; collisions are resolved by linear probing (just
- * search forward for an empty slot, wrapping around to the beginning of
- * the table if necessary). Linear probing is a performance disaster when
- * the table starts to get full, so a complication is introduced. The
- * database is actually one *or more* tables, stored sequentially in the
- * .pag file, and the length of linear-probe sequences is limited. The
- * search (for an existing item or an empty slot) always starts in the
- * first table, and whenever MAXRUN probes have been done in table N,
- * probing continues in table N+1. This behaves reasonably well even in
- * cases of massive overflow. There are some other small complications
- * added, see comments below.
- *
- * The table size is fixed for any particular database, but is determined
- * dynamically when a database is rebuilt. The strategy is to try to pick
- * the size so the first table will be no more than 2/3 full, that being
- * slightly before the point where performance starts to degrade. (It is
- * desirable to be a bit conservative because the overflow strategy tends
- * to produce files with holes in them, which is a nuisance.)
- */
- /*
- * The following is for backward compatibility.
- */
- #ifdef INDEX_SIZE
- #define DEFSIZE INDEX_SIZE
- #endif
- /*
- * ANSI C says an offset into a file is a long, not an off_t, for some
- * reason. This actually does simplify life a bit, but it's still nice
- * to have a distinctive name for it. Beware, this is just for readability,
- * don't try to change this.
- */
- #define of_t long
- #define SOF (sizeof(of_t))
- /*
- * We assume that unused areas of a binary file are zeros, and that the
- * bit pattern of `(of_t)0' is all zeros. The alternative is rather
- * painful file initialization. Note that okayvalue(), if OVERFLOW is
- * defined, knows what value of an offset would cause overflow.
- */
- #define VACANT ((of_t)0)
- #define BIAS(o) ((o)+1) /* make any valid of_t non-VACANT */
- #define UNBIAS(o) ((o)-1) /* reverse BIAS() effect */
- /*
- * In a Unix implementation, or indeed any in which an of_t is a byte
- * count, there are a bunch of high bits free in an of_t. There is a
- * use for them. Checking a possible hit by looking it up in the base
- * file is relatively expensive, and the cost can be dramatically reduced
- * by using some of those high bits to tag the value with a few more bits
- * of the key's hash. This detects most false hits without the overhead of
- * seek+read+strcmp. We use the top bit to indicate whether the value is
- * tagged or not, and don't tag a value which is using the tag bits itself.
- * We're in trouble if the of_t representation wants to use the top bit.
- * The actual bitmasks and offset come from the configuration stuff,
- * which permits fiddling with them as necessary, and also suppressing
- * them completely (by defining the masks to 0). We build pre-shifted
- * versions of the masks for efficiency.
- */
- static of_t tagbits; /* pre-shifted tag mask */
- static of_t taghere; /* pre-shifted tag-enable bit */
- static of_t tagboth; /* tagbits|taghere */
- #define HASTAG(o) ((o)&taghere)
- #define TAG(o) ((o)&tagbits)
- #define NOTAG(o) ((o)&~tagboth)
- #define CANTAG(o) (((o)&tagboth) == 0)
- #define MKTAG(v) (((v)<<conf.tagshift)&tagbits)
- /*
- * A new, from-scratch database, not built as a rebuild of an old one,
- * needs to know table size, casemap algorithm, and tagging. Normally
- * the user supplies this info, but there have to be defaults.
- */
- #ifndef DEFSIZE
- #define DEFSIZE 120011 /* 300007 might be better */
- #endif
- #ifdef OLDBNEWS
- #define DEFCASE '0' /* B2.10 -- no mapping */
- #define NOBUFFER /* B News locking is defective */
- #endif
- #ifdef BNEWS
- #define DEFCASE '=' /* B2.11 -- all mapped */
- #define NOBUFFER /* B News locking is defective */
- #endif
- #ifndef DEFCASE /* C News compatibility is the default */
- #define DEFCASE 'C' /* C News -- RFC822 mapping */
- #endif
- #ifndef NOTAGS
- #define TAGENB 0x80 /* tag enable is top bit, tag is next 7 */
- #define TAGMASK 0x7f
- #define TAGSHIFT 24
- #else
- #define TAGENB 0 /* no tags */
- #define TAGMASK 0
- #define TAGSHIFT 0
- #endif
- /*
- * We read configuration info from the .dir file into this structure,
- * so we can avoid wired-in assumptions for an existing database.
- *
- * Among the info is a record of recent peak usages, so that a new table
- * size can be chosen intelligently when rebuilding. 10 is a good
- * number of usages to keep, since news displays marked fluctuations
- * in volume on a 7-day cycle.
- */
- struct dbzconfig {
- int olddbz; /* .dir file empty but .pag not? */
- of_t tsize; /* table size */
- #ifndef NMEMORY
- #define NMEMORY 10 /* # days of use info to remember */
- #endif
- #define NUSEDS (1+NMEMORY)
- of_t used[NUSEDS]; /* entries used today, yesterday, ... */
- int valuesize; /* size of table values, == SOF */
- int bytemap[SOF]; /* byte-order map */
- char casemap; /* case-mapping algorithm (see cipoint()) */
- char fieldsep; /* field separator in base file, if any */
- of_t tagenb; /* unshifted tag-enable bit */
- of_t tagmask; /* unshifted tag mask */
- int tagshift; /* shift count for tagmask and tagenb */
- };
- static struct dbzconfig conf;
- static int getconf();
- static long getno();
- static int putconf();
- static void mybytemap();
- static of_t bytemap();
- /*
- * Using mmap() is a more efficent way of keeping the .pag file incore. On
- * average, it cuts the number of system calls and buffer copies in half.
- * It also allows one copy to be shared among many processes without
- * consuming any extra resources.
- */
- #ifdef MMAP
- #include <sys/mman.h>
- #ifdef MAP_FILE
- #define MAP__ARG (MAP_FILE | MAP_SHARED)
- #else
- #define MAP__ARG (MAP_SHARED)
- #endif
- #ifndef INCORE
- #define INCORE
- #endif
- #endif
- /*
- * For a program that makes many, many references to the database, it
- * is a large performance win to keep the table in core, if it will fit.
- * Note that this does hurt robustness in the event of crashes, and
- * dbmclose() *must* be called to flush the in-core database to disk.
- * The code is prepared to deal with the possibility that there isn't
- * enough memory. There *is* an assumption that a size_t is big enough
- * to hold the size (in bytes) of one table, so dbminit() tries to figure
- * out whether this is possible first.
- *
- * The preferred way to ask for an in-core table is to do dbzincore(1)
- * before dbminit(). The default is not to do it, although -DINCORE
- * overrides this for backward compatibility with old dbz.
- *
- * We keep only the first table in core. This greatly simplifies the
- * code, and bounds memory demand. Furthermore, doing this is a large
- * performance win even in the event of massive overflow.
- */
- #ifdef INCORE
- static int incore = 1;
- #else
- static int incore = 0;
- #endif
- /*
- * Write to filesystem even if incore? This replaces a single multi-
- * megabyte write when doing a dbzsync with a multi-byte write each
- * time an article is added. On most systems, this will give an overall
- * performance boost.
- */
- static int writethrough = 0;
- /*
- * Stdio buffer for .pag reads. Buffering more than about 16 does not help
- * significantly at the densities we try to maintain, and the much larger
- * buffers that most stdios default to are much more expensive to fill.
- * With small buffers, stdio is performance-competitive with raw read(),
- * and it's much more portable.
- */
- #ifndef NPAGBUF
- #define NPAGBUF 16
- #endif
- #ifndef NOBUFFER
- #ifdef _IOFBF
- static of_t pagbuf[NPAGBUF]; /* only needed if !NOBUFFER && _IOFBF */
- #endif
- #endif
- /*
- * Stdio buffer for base-file reads. Message-IDs (all news ever needs to
- * read) are essentially never longer than 64 bytes, and the typical stdio
- * buffer is so much larger that it is much more expensive to fill.
- */
- #ifndef SHISTBUF
- #define SHISTBUF 64
- #endif
- #ifdef _IOFBF
- static char basebuf[SHISTBUF]; /* only needed if _IOFBF exists */
- #endif
- /*
- * Data structure for recording info about searches.
- */
- struct searcher {
- of_t place; /* current location in file */
- int tabno; /* which table we're in */
- int run; /* how long we'll stay in this table */
- #ifndef MAXRUN
- #define MAXRUN 100
- #endif
- long hash; /* the key's hash code (for optimization) */
- of_t tag; /* tag we are looking for */
- int seen; /* have we examined current location? */
- int aborted; /* has i/o error aborted search? */
- };
- static void start();
- #define FRESH ((struct searcher *)NULL)
- static of_t search();
- #define NOTFOUND ((of_t)-1)
- static int okayvalue();
- static int set();
- /*
- * Arguably the searcher struct for a given routine ought to be local to
- * it, but a fetch() is very often immediately followed by a store(), and
- * in some circumstances it is a useful performance win to remember where
- * the fetch() completed. So we use a global struct and remember whether
- * it is current.
- */
- static struct searcher srch;
- static struct searcher *prevp; /* &srch or FRESH */
- /* byte-ordering stuff */
- static int mybmap[SOF]; /* my byte order (see mybytemap()) */
- static int bytesame; /* is database order same as mine? */
- #define MAPIN(o) ((bytesame) ? (o) : bytemap((o), conf.bytemap, mybmap))
- #define MAPOUT(o) ((bytesame) ? (o) : bytemap((o), mybmap, conf.bytemap))
- /*
- * The double parentheses needed to make this work are ugly, but the
- * alternative (under most compilers) is to pack around 2K of unused
- * strings -- there's just no way to get rid of them.
- */
- #ifdef DBZDEBUG
- static int debug; /* controlled by dbzdebug() */
- #define DEBUG(args) if (debug) { (void) printf args ; } else
- #else
- #define DEBUG(args) ;
- #endif
- /* externals used */
- #if 0
- extern char *memcpy();
- extern char *memchr();
- extern char *malloc();
- extern char *calloc();
- extern void free(); /* ANSI C; some old implementations say int */
- #endif /* 0 */
- extern int atoi();
- extern long atol();
- extern void CloseOnExec();
- /* misc. forwards */
- static long hash();
- static void crcinit();
- static char *cipoint();
- static char *mapcase();
- static int isprime();
- static FILE *latebase();
- /* file-naming stuff */
- static char dir[] = ".dir";
- static char pag[] = ".pag";
- static char *enstring();
- /* central data structures */
- static FILE *basef; /* descriptor for base file */
- static char *basefname; /* name for not-yet-opened base file */
- static FILE *dirf; /* descriptor for .dir file */
- static int dirronly; /* dirf open read-only? */
- static FILE *pagf = NULL; /* descriptor for .pag file */
- static of_t pagpos; /* posn in pagf; only search may set != -1 */
- static int pagronly; /* pagf open read-only? */
- static of_t *corepag; /* incore version of .pag file, if any */
- static FILE *bufpagf; /* well-buffered pagf, for incore rewrite */
- static of_t *getcore();
- #ifndef MMAP
- static int putcore();
- #endif
- static int written; /* has a store() been done? */
- /*
- - dbzfresh - set up a new database, no historical info
- */
- int /* 0 success, -1 failure */
- dbzfresh(name, size, fs, cmap, tagmask)
- char *name; /* base name; .dir and .pag must exist */
- long size; /* table size (0 means default) */
- int fs; /* field-separator character in base file */
- int cmap; /* case-map algorithm (0 means default) */
- of_t tagmask; /* 0 default, 1 no tags */
- {
- register char *fn;
- struct dbzconfig c;
- register of_t m;
- register FILE *f;
- if (pagf != NULL) {
- DEBUG(("dbzfresh: database already openn"));
- return (-1);
- }
- if (size != 0 && size < 2) {
- DEBUG(("dbzfresh: preposterous size (%ld)n", size));
- return (-1);
- }
- /* get default configuration */
- if (getconf((FILE *) NULL, (FILE *) NULL, &c) < 0)
- return (-1); /* "can't happen" */
- /* and mess with it as specified */
- if (size != 0)
- c.tsize = size;
- c.fieldsep = fs;
- switch (cmap) {
- case 0:
- case '0':
- case 'B': /* 2.10 compat */
- c.casemap = '0';/* ' ' nicer, but '0' printable! */
- break;
- case '=':
- case 'b': /* 2.11 compat */
- c.casemap = '=';
- break;
- case 'C':
- c.casemap = 'C';
- break;
- case '?':
- c.casemap = DEFCASE;
- break;
- default:
- DEBUG(("dbzfresh case map `%c' unknownn", cmap));
- return (-1);
- }
- switch ((int) tagmask) {
- case 0: /* default */
- break;
- case 1: /* no tags */
- c.tagshift = 0;
- c.tagmask = 0;
- c.tagenb = 0;
- break;
- default:
- m = tagmask;
- c.tagshift = 0;
- while (!(m & 01)) {
- m >>= 1;
- c.tagshift++;
- }
- c.tagmask = m;
- c.tagenb = (m << 1) & ~m;
- break;
- }
- /* write it out */
- fn = enstring(name, dir);
- if (fn == NULL)
- return (-1);
- f = fopen(fn, "w");
- free((POINTER) fn);
- if (f == NULL) {
- DEBUG(("dbzfresh: unable to write confign"));
- return (-1);
- }
- if (putconf(f, &c) < 0) {
- (void) fclose(f);
- return (-1);
- }
- if (fclose(f) == EOF) {
- DEBUG(("dbzfresh: fclose failuren"));
- return (-1);
- }
- /* create/truncate .pag */
- fn = enstring(name, pag);
- if (fn == NULL)
- return (-1);
- f = fopen(fn, "w");
- free((POINTER) fn);
- if (f == NULL) {
- DEBUG(("dbzfresh: unable to create/truncate .pag filen"));
- return (-1);
- } else
- (void) fclose(f);
- /* and punt to dbminit for the hard work */
- return (dbminit(name));
- }
- /*
- - dbzsize - what's a good table size to hold this many entries?
- */
- long
- dbzsize(contents)
- long contents; /* 0 means what's the default */
- {
- register long n;
- if (contents <= 0) { /* foulup or default inquiry */
- DEBUG(("dbzsize: preposterous input (%ld)n", contents));
- return (DEFSIZE);
- }
- n = (contents / 2) * 3; /* try to keep table at most 2/3 full */
- if (!(n & 01)) /* make it odd */
- n++;
- DEBUG(("dbzsize: tentative size %ldn", n));
- while (!isprime(n)) /* and look for a prime */
- n += 2;
- DEBUG(("dbzsize: final size %ldn", n));
- return (n);
- }
- /*
- - isprime - is a number prime?
- *
- * This is not a terribly efficient approach.
- */
- static int /* predicate */
- isprime(x)
- register long x;
- {
- static int quick[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0};
- register int *ip;
- register long div;
- register long stop;
- /* hit the first few primes quickly to eliminate easy ones */
- /* this incidentally prevents ridiculously small tables */
- for (ip = quick; (div = *ip) != 0; ip++)
- if (x % div == 0) {
- DEBUG(("isprime: quick result on %ldn", (long) x));
- return (0);
- }
- /* approximate square root of x */
- for (stop = x; x / stop < stop; stop >>= 1)
- continue;
- stop <<= 1;
- /* try odd numbers up to stop */
- for (div = *--ip; div < stop; div += 2)
- if (x % div == 0)
- return (0);
- return (1);
- }
- /*
- - dbzagain - set up a new database to be a rebuild of an old one
- */
- int /* 0 success, -1 failure */
- dbzagain(name, oldname)
- char *name; /* base name; .dir and .pag must exist */
- char *oldname; /* base name; all must exist */
- {
- register char *fn;
- struct dbzconfig c;
- register int i;
- register long top;
- register FILE *f;
- register int newtable;
- register of_t newsize;
- struct stat sb;
- register of_t m;
- if (pagf != NULL) {
- DEBUG(("dbzagain: database already openn"));
- return (-1);
- }
- /* pick up the old configuration */
- fn = enstring(oldname, dir);
- if (fn == NULL)
- return (-1);
- f = fopen(fn, "r");
- free((POINTER) fn);
- if (f == NULL) {
- DEBUG(("dbzagain: cannot open old .dir filen"));
- return (-1);
- }
- i = getconf(f, (FILE *) NULL, &c);
- (void) fclose(f);
- if (i < 0) {
- DEBUG(("dbzagain: getconf failedn"));
- return (-1);
- }
- /* calculate tagging from old file */
- if (stat(oldname, &sb) != -1) {
- for (m = 1, i = 0; m < sb.st_size; i++, m <<= 1)
- continue;
- /* if we had more tags than the default, use the new data */
- if ((c.tagmask | c.tagenb) && m > (1 << TAGSHIFT)) {
- c.tagshift = i;
- c.tagmask = (~(unsigned long) 0) >> (i + 1);
- c.tagenb = (c.tagmask << 1) & ~c.tagmask;
- }
- }
- /* tinker with it */
- top = 0;
- newtable = 0;
- for (i = 0; i < NUSEDS; i++) {
- if (top < c.used[i])
- top = c.used[i];
- if (c.used[i] == 0)
- newtable = 1; /* hasn't got full usage history yet */
- }
- if (top == 0) {
- DEBUG(("dbzagain: old table has no contents!n"));
- newtable = 1;
- }
- for (i = NUSEDS - 1; i > 0; i--)
- c.used[i] = c.used[i - 1];
- c.used[0] = 0;
- newsize = dbzsize(top);
- if (!newtable || newsize > c.tsize) /* don't shrink new table */
- c.tsize = newsize;
- /* write it out */
- fn = enstring(name, dir);
- if (fn == NULL)
- return (-1);
- f = fopen(fn, "w");
- free((POINTER) fn);
- if (f == NULL) {
- DEBUG(("dbzagain: unable to write new .dirn"));
- return (-1);
- }
- i = putconf(f, &c);
- (void) fclose(f);
- if (i < 0) {
- DEBUG(("dbzagain: putconf failedn"));
- return (-1);
- }
- /* create/truncate .pag */
- fn = enstring(name, pag);
- if (fn == NULL)
- return (-1);
- f = fopen(fn, "w");
- free((POINTER) fn);
- if (f == NULL) {
- DEBUG(("dbzagain: unable to create/truncate .pag filen"));
- return (-1);
- } else
- (void) fclose(f);
- /* and let dbminit do the work */
- return (dbminit(name));
- }
- /*
- - dbminit - open a database, creating it (using defaults) if necessary
- *
- * We try to leave errno set plausibly, to the extent that underlying
- * functions permit this, since many people consult it if dbminit() fails.
- */
- int /* 0 success, -1 failure */
- dbminit(name)
- char *name;
- {
- register int i;
- register size_t s;
- register char *dirfname;
- register char *pagfname;
- if (pagf != NULL) {
- DEBUG(("dbminit: dbminit already called oncen"));
- errno = 0;
- return (-1);
- }
- /* open the .dir file */
- dirfname = enstring(name, dir);
- if (dirfname == NULL)
- return (-1);
- dirf = fopen(dirfname, "r+");
- if (dirf == NULL) {
- dirf = fopen(dirfname, "r");
- dirronly = 1;
- } else
- dirronly = 0;
- free((POINTER) dirfname);
- if (dirf == NULL) {
- DEBUG(("dbminit: can't open .dir filen"));
- return (-1);
- }
- CloseOnExec((int) fileno(dirf), 1);
- /* open the .pag file */
- pagfname = enstring(name, pag);
- if (pagfname == NULL) {
- (void) fclose(dirf);
- return (-1);
- }
- pagf = fopen(pagfname, "r+b");
- if (pagf == NULL) {
- pagf = fopen(pagfname, "rb");
- if (pagf == NULL) {
- DEBUG(("dbminit: .pag open failedn"));
- (void) fclose(dirf);
- free((POINTER) pagfname);
- return (-1);
- }
- pagronly = 1;
- } else if (dirronly)
- pagronly = 1;
- else
- pagronly = 0;
- if (pagf != NULL)
- CloseOnExec((int) fileno(pagf), 1);
- #ifdef NOBUFFER
- /*
- * B News does not do adequate locking on its database accesses. Why
- * it doesn't get into trouble using dbm is a mystery. In any case,
- * doing unbuffered i/o does not cure the problem, but does
- * enormously reduce its incidence.
- */
- (void) setbuf(pagf, (char *) NULL);
- #else
- #ifdef _IOFBF
- (void) setvbuf(pagf, (char *) pagbuf, _IOFBF, sizeof(pagbuf));
- #endif
- #endif
- pagpos = -1;
- /* don't free pagfname, need it below */
- /* open the base file */
- basef = fopen(name, "r");
- if (basef == NULL) {
- DEBUG(("dbminit: basefile open failedn"));
- basefname = enstring(name, "");
- if (basefname == NULL) {
- (void) fclose(pagf);
- (void) fclose(dirf);
- free((POINTER) pagfname);
- pagf = NULL;
- return (-1);
- }
- } else
- basefname = NULL;
- if (basef != NULL)
- CloseOnExec((int) fileno(basef), 1);
- #ifdef _IOFBF
- if (basef != NULL)
- (void) setvbuf(basef, basebuf, _IOFBF, sizeof(basebuf));
- #endif
- /* pick up configuration */
- if (getconf(dirf, pagf, &conf) < 0) {
- DEBUG(("dbminit: getconf failuren"));
- (void) fclose(basef);
- (void) fclose(pagf);
- (void) fclose(dirf);
- free((POINTER) pagfname);
- pagf = NULL;
- errno = EDOM; /* kind of a kludge, but very portable */
- return (-1);
- }
- tagbits = conf.tagmask << conf.tagshift;
- taghere = conf.tagenb << conf.tagshift;
- tagboth = tagbits | taghere;
- mybytemap(mybmap);
- bytesame = 1;
- for (i = 0; i < SOF; i++)
- if (mybmap[i] != conf.bytemap[i])
- bytesame = 0;
- /* get first table into core, if it looks desirable and feasible */
- s = (size_t) conf.tsize * SOF;
- if (incore && (of_t) (s / SOF) == conf.tsize) {
- bufpagf = fopen(pagfname, (pagronly) ? "rb" : "r+b");
- if (bufpagf != NULL) {
- corepag = getcore(bufpagf);
- CloseOnExec((int) fileno(bufpagf), 1);
- }
- } else {
- bufpagf = NULL;
- corepag = NULL;
- }
- free((POINTER) pagfname);
- /* misc. setup */
- crcinit();
- written = 0;
- prevp = FRESH;
- DEBUG(("dbminit: succeededn"));
- return (0);
- }
- /*
- - enstring - concatenate two strings into a malloced area
- */
- static char * /* NULL if malloc fails */
- enstring(s1, s2)
- char *s1;
- char *s2;
- {
- register char *p;
- p = malloc((size_t) strlen(s1) + (size_t) strlen(s2) + 1);
- if (p != NULL) {
- (void) strcpy(p, s1);
- (void) strcat(p, s2);
- } else {
- DEBUG(("enstring(%s, %s) out of memoryn", s1, s2));
- }
- return (p);
- }
- /*
- - dbmclose - close a database
- */
- int
- dbmclose()
- {
- register int ret = 0;
- if (pagf == NULL) {
- DEBUG(("dbmclose: not opened!n"));
- return (-1);
- }
- if (fclose(pagf) == EOF) {
- DEBUG(("dbmclose: fclose(pagf) failedn"));
- ret = -1;
- }
- pagf = basef; /* ensure valid pointer; dbzsync checks it */
- if (dbzsync() < 0)
- ret = -1;
- if (bufpagf != NULL && fclose(bufpagf) == EOF) {
- DEBUG(("dbmclose: fclose(bufpagf) failedn"));
- ret = -1;
- }
- if (corepag != NULL)
- #ifdef MMAP
- if (munmap((caddr_t) corepag, (int) conf.tsize * SOF) == -1) {
- DEBUG(("dbmclose: munmap failedn"));
- ret = -1;
- }
- #else
- free((POINTER) corepag);
- #endif
- corepag = NULL;
- if (basef) {
- if (fclose(basef) == EOF) {
- DEBUG(("dbmclose: fclose(basef) failedn"));
- ret = -1;
- }
- }
- if (basefname != NULL)
- free((POINTER) basefname);
- basef = NULL;
- pagf = NULL;
- if (fclose(dirf) == EOF) {
- DEBUG(("dbmclose: fclose(dirf) failedn"));
- ret = -1;
- }
- DEBUG(("dbmclose: %sn", (ret == 0) ? "succeeded" : "failed"));
- return (ret);
- }
- /*
- - dbzsync - push all in-core data out to disk
- */
- int
- dbzsync()
- {
- register int ret = 0;
- if (pagf == NULL) {
- DEBUG(("dbzsync: not opened!n"));
- return (-1);
- }
- if (!written)
- return (0);
- #ifndef MMAP
- if (corepag != NULL && !writethrough) {
- if (putcore(corepag, bufpagf) < 0) {
- DEBUG(("dbzsync: putcore failedn"));
- ret = -1;
- }
- }
- #endif
- if (!conf.olddbz)
- if (putconf(dirf, &conf) < 0)
- ret = -1;
- DEBUG(("dbzsync: %sn", (ret == 0) ? "succeeded" : "failed"));
- return (ret);
- }
- /*
- - dbzcancel - cancel writing of in-core data
- * Mostly for use from child processes.
- * Note that we don't need to futz around with stdio buffers, because we
- * always fflush them immediately anyway and so they never have stale data.
- */
- int
- dbzcancel()
- {
- if (pagf == NULL) {
- DEBUG(("dbzcancel: not opened!n"));
- return (-1);
- }
- written = 0;
- return (0);
- }
- /*
- - dbzfetch - fetch() with case mapping built in
- */
- datum
- dbzfetch(key)
- datum key;
- {
- char buffer[DBZMAXKEY + 1];
- datum mappedkey;
- register size_t keysize;
- DEBUG(("dbzfetch: (%s)n", key.dptr));
- /* Key is supposed to be less than DBZMAXKEY */
- keysize = key.dsize;
- if (keysize >= DBZMAXKEY) {
- keysize = DBZMAXKEY;
- DEBUG(("keysize is %d - truncated to %dn", key.dsize, DBZMAXKEY));
- }
- mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
- buffer[keysize] = ' '; /* just a debug aid */
- mappedkey.dsize = keysize;
- return (fetch(mappedkey));
- }
- /*
- - fetch - get an entry from the database
- *
- * Disgusting fine point, in the name of backward compatibility: if the
- * last character of "key" is a NUL, that character is (effectively) not
- * part of the comparison against the stored keys.
- */
- datum /* dptr NULL, dsize 0 means failure */
- fetch(key)
- datum key;
- {
- char buffer[DBZMAXKEY + 1];
- static of_t key_ptr; /* return value points here */
- datum output;
- register size_t keysize;
- register size_t cmplen;
- register char *sepp;
- DEBUG(("fetch: (%s)n", key.dptr));
- output.dptr = NULL;
- output.dsize = 0;
- prevp = FRESH;
- /* Key is supposed to be less than DBZMAXKEY */
- keysize = key.dsize;
- if (keysize >= DBZMAXKEY) {
- keysize = DBZMAXKEY;
- DEBUG(("keysize is %d - truncated to %dn", key.dsize, DBZMAXKEY));
- }
- if (pagf == NULL) {
- DEBUG(("fetch: database not open!n"));
- return (output);
- } else if (basef == NULL) { /* basef didn't exist yet */
- basef = latebase();
- if (basef == NULL)
- return (output);
- }
- cmplen = keysize;
- sepp = &conf.fieldsep;
- if (key.dptr[keysize - 1] == ' ') {
- cmplen--;
- sepp = &buffer[keysize - 1];
- }
- start(&srch, &key, FRESH);
- while ((key_ptr = search(&srch)) != NOTFOUND) {
- DEBUG(("got 0x%lxn", key_ptr));
- /* fetch the key */
- if (fseek(basef, key_ptr, SEEK_SET) != 0) {
- DEBUG(("fetch: seek failedn"));
- return (output);
- }
- if (fread((POINTER) buffer, 1, keysize, basef) != keysize) {
- DEBUG(("fetch: read failedn"));
- return (output);
- }
- /* try it */
- buffer[keysize] = ' '; /* terminated for DEBUG */
- (void) mapcase(buffer, buffer, keysize);
- DEBUG(("fetch: buffer (%s) looking for (%s) size = %dn",
- buffer, key.dptr, keysize));
- if (memcmp((POINTER) key.dptr, (POINTER) buffer, cmplen) == 0 &&
- (*sepp == conf.fieldsep || *sepp == ' ')) {
- /* we found it */
- output.dptr = (char *) &key_ptr;
- output.dsize = SOF;
- DEBUG(("fetch: successfuln"));
- return (output);
- }
- }
- /* we didn't find it */
- DEBUG(("fetch: failedn"));
- prevp = &srch; /* remember where we stopped */
- return (output);
- }
- /*
- - latebase - try to open a base file that wasn't there at the start
- */
- static FILE *
- latebase()
- {
- register FILE *it;
- if (basefname == NULL) {
- DEBUG(("latebase: name foulupn"));
- return (NULL);
- }
- it = fopen(basefname, "r");
- if (it == NULL) {
- DEBUG(("latebase: still can't open basen"));
- } else {
- DEBUG(("latebase: late open succeededn"));
- free((POINTER) basefname);
- basefname = NULL;
- #ifdef _IOFBF
- (void) setvbuf(it, basebuf, _IOFBF, sizeof(basebuf));
- #endif
- }
- if (it != NULL)
- CloseOnExec((int) fileno(it), 1);
- return (it);
- }
- /*
- - dbzstore - store() with case mapping built in
- */
- int
- dbzstore(key, data)
- datum key;
- datum data;
- {
- char buffer[DBZMAXKEY + 1];
- datum mappedkey;
- register size_t keysize;
- DEBUG(("dbzstore: (%s)n", key.dptr));
- /* Key is supposed to be less than DBZMAXKEY */
- keysize = key.dsize;
- if (keysize >= DBZMAXKEY) {
- DEBUG(("dbzstore: key size too big (%d)n", key.dsize));
- return (-1);
- }
- mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
- buffer[keysize] = ' '; /* just a debug aid */
- mappedkey.dsize = keysize;
- return (store(mappedkey, data));
- }
- /*
- - store - add an entry to the database
- */
- int /* 0 success, -1 failure */
- store(key, data)
- datum key;
- datum data;
- {
- of_t value;
- if (pagf == NULL) {
- DEBUG(("store: database not open!n"));
- return (-1);
- } else if (basef == NULL) { /* basef didn't exist yet */
- basef = latebase();
- if (basef == NULL)
- return (-1);
- }
- if (pagronly) {
- DEBUG(("store: database open read-onlyn"));
- return (-1);
- }
- if (data.dsize != SOF) {
- DEBUG(("store: value size wrong (%d)n", data.dsize));
- return (-1);
- }
- if (key.dsize >= DBZMAXKEY) {
- DEBUG(("store: key size too big (%d)n", key.dsize));
- return (-1);
- }
- /* copy the value in to ensure alignment */
- (void) memcpy((POINTER) & value, (POINTER) data.dptr, SOF);
- DEBUG(("store: (%s, %ld)n", key.dptr, (long) value));
- if (!okayvalue(value)) {
- DEBUG(("store: reserved bit or overflow in 0x%lxn", value));
- return (-1);
- }
- /* find the place, exploiting previous search if possible */
- start(&srch, &key, prevp);
- while (search(&srch) != NOTFOUND)
- continue;
- prevp = FRESH;
- conf.used[0]++;
- DEBUG(("store: used count %ldn", conf.used[0]));
- written = 1;
- return (set(&srch, value));
- }
- /*
- - dbzincore - control attempts to keep .pag file in core
- */
- int /* old setting */
- dbzincore(value)
- int value;
- {
- register int old = incore;
- #ifndef MMAP
- incore = value;
- #endif
- return (old);
- }
- /*
- - dbzwritethrough - write through the pag file in core
- */
- int /* old setting */
- dbzwritethrough(value)
- int value;
- {
- register int old = writethrough;
- writethrough = value;
- return (old);
- }
- /*
- - dbztagmask - calculate the correct tagmask for the given base file size
- */
- long
- dbztagmask(size)
- register long size;
- {
- register long m;
- register long tagmask;
- register int i;
- if (size <= 0)
- return (0L); /* silly size */
- for (m = 1, i = 0; m < size; i++, m <<= 1)
- continue;
- if (m < (1 << TAGSHIFT))
- return (0L); /* not worth tagging */
- tagmask = (~(unsigned long) 0) >> (i + 1);
- tagmask = tagmask << i;
- return (tagmask);
- }
- /*
- - getconf - get configuration from .dir file
- */
- static int /* 0 success, -1 failure */
- getconf(df, pf, cp)
- register FILE *df; /* NULL means just give me the default */
- register FILE *pf; /* NULL means don't care about .pag */
- register struct dbzconfig *cp;
- {
- register int c;
- register int i;
- int err = 0;
- c = (df != NULL) ? getc(df) : EOF;
- if (c == EOF) { /* empty file, no configuration known */
- cp->olddbz = 0;
- if (df != NULL && pf != NULL && getc(pf) != EOF)
- cp->olddbz = 1;
- cp->tsize = DEFSIZE;
- cp->fieldsep = 't';
- for (i = 0; i < NUSEDS; i++)
- cp->used[i] = 0;
- cp->valuesize = SOF;
- mybytemap(cp->bytemap);
- cp->casemap = DEFCASE;
- cp->tagenb = TAGENB;
- cp->tagmask = TAGMASK;
- cp->tagshift = TAGSHIFT;
- DEBUG(("getconf: defaults (%ld, %c, (0x%lx/0x%lx<<%d))n",
- cp->tsize, cp->casemap, cp->tagenb,
- cp->tagmask, cp->tagshift));
- return (0);
- }
- (void) ungetc(c, df);
- /* first line, the vital stuff */
- if (getc(df) != 'd' || getc(df) != 'b' || getc(df) != 'z')
- err = -1;
- if (getno(df, &err) != dbzversion)
- err = -1;
- cp->tsize = getno(df, &err);
- cp->fieldsep = (int) getno(df, &err);
- while ((c = getc(df)) == ' ')
- continue;
- cp->casemap = c;
- cp->tagenb = getno(df, &err);
- cp->tagmask = getno(df, &err);
- cp->tagshift = getno(df, &err);
- cp->valuesize = getno(df, &err);
- if (cp->valuesize != SOF) {
- DEBUG(("getconf: wrong of_t size (%d)n", cp->valuesize));
- err = -1;
- cp->valuesize = SOF; /* to protect the loops below */
- }
- for (i = 0; i < cp->valuesize; i++)
- cp->bytemap[i] = getno(df, &err);
- if (getc(df) != 'n')
- err = -1;
- #ifdef DBZDEBUG
- DEBUG(("size %ld, sep %d, cmap %c, tags 0x%lx/0x%lx<<%d, ", cp->tsize,
- cp->fieldsep, cp->casemap, cp->tagenb, cp->tagmask,
- cp->tagshift));
- DEBUG(("bytemap (%d)", cp->valuesize));
- for (i = 0; i < cp->valuesize; i++) {
- DEBUG((" %d", cp->bytemap[i]));
- }
- DEBUG(("n"));
- #endif
- /* second line, the usages */
- for (i = 0; i < NUSEDS; i++)
- cp->used[i] = getno(df, &err);
- if (getc(df) != 'n')
- err = -1;
- DEBUG(("used %ld %ld %ld...n", cp->used[0], cp->used[1], cp->used[2]));
- if (err < 0) {
- DEBUG(("getconf errorn"));
- return (-1);
- }
- return (0);
- }
- /*
- - getno - get a long
- */
- static long
- getno(f, ep)
- FILE *f;
- int *ep;
- {
- register char *p;
- #define MAXN 50
- char getbuf[MAXN];
- register int c;
- while ((c = getc(f)) == ' ')
- continue;
- if (c == EOF || c == 'n') {
- DEBUG(("getno: missing numbern"));
- *ep = -1;
- return (0);
- }
- p = getbuf;
- *p++ = c;
- while ((c = getc(f)) != EOF && c != 'n' && c != ' ')
- if (p < &getbuf[MAXN - 1])
- *p++ = c;
- if (c == EOF) {
- DEBUG(("getno: EOFn"));
- *ep = -1;
- } else
- (void) ungetc(c, f);
- *p = ' ';
- if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
- DEBUG(("getno: `%s' non-numericn", getbuf));
- *ep = -1;
- }
- return (atol(getbuf));
- }
- /*
- - putconf - write configuration to .dir file
- */
- static int /* 0 success, -1 failure */
- putconf(f, cp)
- register FILE *f;
- register struct dbzconfig *cp;
- {
- register int i;
- register int ret = 0;
- if (fseek(f, (of_t) 0, SEEK_SET) != 0) {
- DEBUG(("fseek failure in putconfn"));
- ret = -1;
- }
- (void) fprintf(f, "dbz %d %ld %d %c %ld %ld %d %d", dbzversion, cp->tsize,
- cp->fieldsep, cp->casemap, cp->tagenb,
- cp->tagmask, cp->tagshift, cp->valuesize);
- for (i = 0; i < cp->valuesize; i++)
- (void) fprintf(f, " %d", cp->bytemap[i]);
- (void) fprintf(f, "n");
- for (i = 0; i < NUSEDS; i++)
- (void) fprintf(f, "%ld%c", cp->used[i], (i < NUSEDS - 1) ? ' ' : 'n');
- (void) fflush(f);
- if (ferror(f))
- ret = -1;
- DEBUG(("putconf status %dn", ret));
- return (ret);
- }
- /*
- - getcore - try to set up an in-core copy of .pag file
- */
- static of_t * /* pointer to copy, or NULL */
- getcore(f)
- FILE *f;
- {
- register of_t *p;
- register size_t i;
- register size_t nread;
- register char *it;
- #ifdef MMAP
- struct stat st;
- if (fstat(fileno(f), &st) == -1) {
- DEBUG(("getcore: fstat failedn"));
- return (NULL);
- }
- if (((size_t) conf.tsize * SOF) > st.st_size) {
- /* file too small; extend it */
- if (ftruncate((int) fileno(f), conf.tsize * SOF) == -1) {
- DEBUG(("getcore: ftruncate failedn"));
- return (NULL);
- }
- }
- it = mmap((caddr_t) 0, (size_t) conf.tsize * SOF,
- pagronly ? PROT_READ : PROT_WRITE | PROT_READ, MAP__ARG,
- (int) fileno(f), (off_t) 0);
- if (it == (char *) -1) {
- DEBUG(("getcore: mmap failedn"));
- return (NULL);
- }
- #ifdef MC_ADVISE
- /* not present in all versions of mmap() */
- madvise(it, (size_t) conf.tsize * SOF, MADV_RANDOM);
- #endif
- #else
- it = malloc((size_t) conf.tsize * SOF);
- if (it == NULL) {
- DEBUG(("getcore: malloc failedn"));
- return (NULL);
- }
- nread = fread((POINTER) it, SOF, (size_t) conf.tsize, f);
- if (ferror(f)) {
- DEBUG(("getcore: read failedn"));
- free((POINTER) it);
- return (NULL);
- }
- /* NOSTRICT *//* Possible pointer alignment problem */
- p = (of_t *) it + nread;
- i = (size_t) conf.tsize - nread;
- while (i-- > 0)
- *p++ = VACANT;
- #endif
- /* NOSTRICT *//* Possible pointer alignment problem */
- return ((of_t *) it);
- }
- #ifndef MMAP
- /*
- - putcore - try to rewrite an in-core table
- */
- static int /* 0 okay, -1 fail */
- putcore(tab, f)
- of_t *tab;
- FILE *f;
- {
- if (fseek(f, (of_t) 0, SEEK_SET) != 0) {
- DEBUG(("fseek failure in putcoren"));
- return (-1);
- }
- (void) fwrite((POINTER) tab, SOF, (size_t) conf.tsize, f);
- (void) fflush(f);
- return ((ferror(f)) ? -1 : 0);
- }
- #endif
- /*
- - start - set up to start or restart a search
- */
- static void
- start(sp, kp, osp)
- register struct searcher *sp;
- register datum *kp;
- register struct searcher *osp; /* may be FRESH, i.e. NULL */
- {
- register long h;
- h = hash(kp->dptr, kp->dsize);
- if (osp != FRESH && osp->hash == h) {
- if (sp != osp)
- *sp = *osp;
- DEBUG(("search restartedn"));
- } else {
- sp->hash = h;
- sp->tag = MKTAG(h / conf.tsize);
- DEBUG(("tag 0x%lxn", sp->tag));
- sp->place = h % conf.tsize;
- sp->tabno = 0;
- sp->run = (conf.olddbz) ? conf.tsize : MAXRUN;
- sp->aborted = 0;
- }
- sp->seen = 0;
- }
- /*
- - search - conduct part of a search
- */
- static of_t /* NOTFOUND if we hit VACANT or error */
- search(sp)
- register struct searcher *sp;
- {
- register of_t dest;
- register of_t value;
- of_t val; /* buffer for value (can't fread register) */
- register of_t place;
- if (sp->aborted)
- return (NOTFOUND);
- for (;;) {
- /* determine location to be examined */
- place = sp->place;
- if (sp->seen) {
- /* go to next location */
- if (--sp->run <= 0) {
- sp->tabno++;
- sp->run = MAXRUN;
- }
- place = (place + 1) % conf.tsize + sp->tabno * conf.tsize;
- sp->place = place;
- } else
- sp->seen = 1; /* now looking at current location */
- DEBUG(("search @ %ldn", place));
- /* get the tagged value */
- if (corepag != NULL && place < conf.tsize) {
- DEBUG(("search: in coren"));
- value = MAPIN(corepag[place]);
- } else {
- /* seek, if necessary */
- dest = place * SOF;
- if (pagpos != dest) {
- if (fseek(pagf, dest, SEEK_SET) != 0) {
- DEBUG(("search: seek failedn"));
- pagpos = -1;
- sp->aborted = 1;
- return (NOTFOUND);
- }
- pagpos = dest;
- }
- /* read it */
- if (fread((POINTER) & val, sizeof(val), 1, pagf) == 1)
- value = MAPIN(val);
- else if (ferror(pagf)) {
- DEBUG(("search: read failedn"));
- pagpos = -1;
- sp->aborted = 1;
- return (NOTFOUND);
- } else
- value = VACANT;
- /* and finish up */
- pagpos += sizeof(val);
- }
- /* vacant slot is always cause to return */
- if (value == VACANT) {
- DEBUG(("search: empty slotn"));
- return (NOTFOUND);
- };
- /* check the tag */
- value = UNBIAS(value);
- DEBUG(("got 0x%lxn", value));
- if (!HASTAG(value)) {
- DEBUG(("taglessn"));
- return (value);
- } else if (TAG(value) == sp->tag) {
- DEBUG(("matchn"));
- return (NOTAG(value));
- } else {
- DEBUG(("mismatch 0x%lxn", TAG(value)));
- }
- }
- /* NOTREACHED */
- }
- /*
- - okayvalue - check that a value can be stored
- */
- static int /* predicate */
- okayvalue(value)
- of_t value;
- {
- if (HASTAG(value))
- return (0);
- #ifdef OVERFLOW
- if (value == LONG_MAX) /* BIAS() and UNBIAS() will overflow */
- return (0);
- #endif
- return (1);
- }
- /*
- - set - store a value into a location previously found by search
- */
- static int /* 0 success, -1 failure */
- set(sp, value)
- register struct searcher *sp;
- of_t value;
- {
- register of_t place = sp->place;
- register of_t v = value;
- if (sp->aborted)
- return (-1);
- if (CANTAG(v) && !conf.olddbz) {
- v |= sp->tag | taghere;
- if (v != UNBIAS(VACANT)) /* BIAS(v) won't look VACANT */
- #ifdef OVERFLOW
- if (v != LONG_MAX) /* and it won't overflow */
- #endif
- value = v;
- }
- DEBUG(("tagged value is 0x%lxn", value));
- value = BIAS(value);
- value = MAPOUT(value);
- /* If we have the index file in memory, use it */
- if (corepag != NULL && place < conf.tsize) {
- corepag[place] = value;
- DEBUG(("set: incoren"));
- #ifdef MMAP
- return (0);
- #else
- if (!writethrough)
- return (0);
- #endif
- }
- /* seek to spot */
- pagpos = -1; /* invalidate position memory */
- if (fseek(pagf, (of_t) (place * SOF), SEEK_SET) != 0) {
- DEBUG(("set: seek failedn"));
- sp->aborted = 1;
- return (-1);
- }
- /* write in data */
- if (fwrite((POINTER) & value, SOF, 1, pagf) != 1) {
- DEBUG(("set: write failedn"));
- sp->aborted = 1;
- return (-1);
- }
- /* fflush improves robustness, and buffer re-use is rare anyway */
- if (fflush(pagf) == EOF) {
- DEBUG(("set: fflush failedn"));
- sp->aborted = 1;
- return (-1);
- }
- DEBUG(("set: succeededn"));
- return (0);
- }
- /*
- - mybytemap - determine this machine's byte map
- *
- * A byte map is an array of ints, sizeof(of_t) of them. The 0th int
- * is the byte number of the high-order byte in my of_t, and so forth.
- */
- static void
- mybytemap(map)
- int map[]; /* -> int[SOF] */
- {
- union {
- of_t o;
- char c[SOF];
- } u;
- register int *mp = &map[SOF];
- register int ntodo;
- register int i;
- u.o = 1;
- for (ntodo = (int) SOF; ntodo > 0; ntodo--) {
- for (i = 0; i < SOF; i++)
- /*
- * SUPPRESS 112 *//* Retrieving char where long is
- * stored
- */
- if (u.c[i] != 0)
- break;
- if (i == SOF) {
- /* trouble -- set it to *something* consistent */
- DEBUG(("mybytemap: nonexistent byte %d!!!n", ntodo));
- for (i = 0; i < SOF; i++)
- map[i] = i;
- return;
- }
- DEBUG(("mybytemap: byte %dn", i));
- *--mp = i;
- /* SUPPRESS 112 *//* Retrieving char where long is stored */
- while (u.c[i] != 0)
- u.o <<= 1;
- }
- }
- /*
- - bytemap - transform an of_t from byte ordering map1 to map2
- */
- static of_t /* transformed result */
- bytemap(ino, map1, map2)
- of_t ino;
- int *map1;
- int *map2;
- {
- union oc {
- of_t o;
- char c[SOF];
- };
- union oc in;
- union oc out;
- register int i;
- in.o = ino;
- for (i = 0; i < SOF; i++)
- out.c[map2[i]] = in.c[map1[i]];
- return (out.o);
- }
- /*
- * This is a simplified version of the pathalias hashing function.
- * Thanks to Steve Belovin and Peter Honeyman
- *
- * hash a string into a long int. 31 bit crc (from andrew appel).
- * the crc table is computed at run time by crcinit() -- we could
- * precompute, but it takes 1 clock tick on a 750.
- *
- * This fast table calculation works only if POLY is a prime polynomial
- * in the field of integers modulo 2. Since the coefficients of a
- * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
- * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
- * 31 down to 25 are zero. Happily, we have candidates, from
- * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
- * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
- * x^31 + x^3 + x^0
- *
- * We reverse the bits to get:
- * 111101010000000000000000000000001 but drop the last 1
- * f 5 0 0 0 0 0 0
- * 010010000000000000000000000000001 ditto, for 31-bit crc
- * 4 8 0 0 0 0 0 0
- */
- #define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */
- static long CrcTable[128];
- /*
- - crcinit - initialize tables for hash function
- */
- static void
- crcinit()
- {
- register int i, j;
- register long sum;
- for (i = 0; i < 128; ++i) {
- sum = 0L;
- for (j = 7 - 1; j >= 0; --j)
- if (i & (1 << j))
- sum ^= POLY >> j;
- CrcTable[i] = sum;
- }
- DEBUG(("crcinit: donen"));
- }
- /*
- - hash - Honeyman's nice hashing function
- */
- static long
- hash(name, size)
- register char *name;
- register int size;
- {
- register long sum = 0L;
- while (size--) {
- sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
- }
- DEBUG(("hash: returns (%ld)n", sum));
- return (sum);
- }
- /*
- * case-mapping stuff
- *
- * Borrowed from C News, by permission of the authors. Somewhat modified.
- *
- * We exploit the fact that we are dealing only with headers here, and
- * headers are limited to the ASCII characters by RFC822. It is barely
- * possible that we might be dealing with a translation into another
- * character set, but in particular it's very unlikely for a header
- * character to be outside -128..255.
- *
- * Life would be a whole lot simpler if tolower() could safely and portably
- * be applied to any char.
- */
- #define OFFSET 128 /* avoid trouble with negative chars */
- /* must call casencmp before invoking TOLOW... */
- #define TOLOW(c) (cmap[(c)+OFFSET])
- /* ...but the use of it in CISTREQN is safe without the preliminary call (!) */
- /* CISTREQN is an optimised case-insensitive strncmp(a,b,n)==0; n > 0 */
- #define CISTREQN(a, b, n)
- (TOLOW((a)[0]) == TOLOW((b)[0]) && casencmp(a, b, n) == 0)
- #define MAPSIZE (256+OFFSET)
- static char cmap[MAPSIZE]; /* relies on init to ' ' */
- static int mprimed = 0; /* has cmap been set up? */
- /*
- - mapprime - set up case-mapping stuff
- */
- static void
- mapprime()
- {
- register char *lp;
- register char *up;
- register int c;
- register int i;
- static char lower[] = "abcdefghijklmnopqrstuvwxyz";
- static char upper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
- for (lp = lower, up = upper; *lp != ' '; lp++, up++) {
- c = *lp;
- cmap[c + OFFSET] = c;
- cmap[*up + OFFSET] = c;
- }
- for (i = 0; i < MAPSIZE; i++)
- if (cmap[i] == ' ')
- cmap[i] = (char) (i - OFFSET);
- mprimed = 1;
- }
- /*
- - casencmp - case-independent strncmp
- */
- static int /* < == > 0 */
- casencmp(s1, s2, len)
- char *s1;
- char *s2;
- int len;
- {
- register char *p1;
- register char *p2;
- register int n;
- if (!mprimed)
- mapprime();
- p1 = s1;
- p2 = s2;
- n = len;
- while (--n >= 0 && *p1 != ' ' && TOLOW(*p1) == TOLOW(*p2)) {
- p1++;
- p2++;
- }
- if (n < 0)
- return (0);
- /*
- * The following case analysis is necessary so that characters which
- * look negative collate low against normal characters but high
- * against the end-of-string NUL.
- */
- if (*p1 == ' ' && *p2 == ' ')
- return (0);
- else if (*p1 == ' ')
- return (-1);
- else if (*p2 == ' ')
- return (1);
- else
- return (TOLOW(*p1) - TOLOW(*p2));
- }
- /*
- - mapcase - do case-mapped copy
- */
- static char * /* returns src or dst */
- mapcase(dst, src, siz)
- char *dst; /* destination, used only if mapping needed */
- char *src; /* source; src == dst is legal */
- size_t siz;
- {
- register char *s;
- register char *d;
- register char *c; /* case break */
- register char *e; /* end of source */
- c = cipoint(src, siz);
- if (c == NULL)
- return (src);
- if (!mprimed)
- mapprime();
- s = src;
- e = s + siz;
- d = dst;
- while (s < c)
- *d++ = *s++;
- while (s < e)
- *d++ = TOLOW(*s++);
- return (dst);
- }
- /*
- - cipoint - where in this message-ID does it become case-insensitive?
- *
- * The RFC822 code is not quite complete. Absolute, total, full RFC822
- * compliance requires a horrible parsing job, because of the arcane
- * quoting conventions -- abc"def"ghi is not equivalent to abc"DEF"ghi,
- * for example. There are three or four things that might occur in the
- * domain part of a message-id that are case-sensitive. They don't seem
- * to ever occur in real news, thank Cthulhu. (What? You were expecting
- * a merciful and forgiving deity to be invoked in connection with RFC822?
- * Forget it; none of them would come near it.)
- */
- static char * /* pointer into s, or NULL for "nowhere" */
- cipoint(s, siz)
- char *s;
- size_t siz;
- {
- register char *p;
- static char post[] = "postmaster";
- static int plen = sizeof(post) - 1;
- switch (conf.casemap) {
- case '0': /* unmapped, sensible */
- return (NULL);
- case 'C': /* C News, RFC 822 conformant (approx.) */
- p = memchr((POINTER) s, '@', siz);
- if (p == NULL) /* no local/domain split */
- return (NULL); /* assume all local */
- if (p - (s + 1) == plen && CISTREQN(s + 1, post, plen)) {
- /* crazy -- "postmaster" is case-insensitive */
- return (s);
- }
- return (p);
- case '=': /* 2.11, neither sensible nor conformant */
- return (s); /* all case-insensitive */
- }
- DEBUG(("cipoint: unknown case mapping `%c'n", conf.casemap));
- return (NULL); /* just leave it alone */
- }
- /*
- - dbzdebug - control dbz debugging at run time
- */
- #ifdef DBZDEBUG
- int /* old value */
- dbzdebug(value)
- int value;
- {
- register int old = debug;
- debug = value;
- return (old);
- }
- #endif