path: root/innbbsd/dbz.c

/*
 * 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 open\n"));
    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';    /* '\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' unknown\n", 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 config\n"));
    return (-1);
    }
    if (putconf(f, &c) < 0) {
    (void)fclose(f);
    return (-1);
    }
    if (fclose(f) == EOF) {
    DEBUG(("dbzfresh: fclose failure\n"));
    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 file\n"));
    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 %ld\n", n));
    while (!isprime(n))     /* and look for a prime */
    n += 2;
    DEBUG(("dbzsize: final size %ld\n", 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 %ld\n", (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 open\n"));
    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 file\n"));
    return (-1);
    }
    i = getconf(f, (FILE *) NULL, &c);
    (void)fclose(f);
    if (i < 0) {
    DEBUG(("dbzagain: getconf failed\n"));
    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 .dir\n"));
    return (-1);
    }
    i = putconf(f, &c);
    (void)fclose(f);
    if (i < 0) {
    DEBUG(("dbzagain: putconf failed\n"));
    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 file\n"));
    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 once\n"));
    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 file\n"));
    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 failed\n"));
        (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 failed\n"));
    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 failure\n"));
    (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: succeeded\n"));
    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 memory\n", 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) failed\n"));
    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) failed\n"));
    ret = -1;
    }
    if (corepag != NULL)
#ifdef MMAP
    if (munmap((caddr_t) corepag, (int)conf.tsize * SOF) == -1) {
        DEBUG(("dbmclose: munmap failed\n"));
        ret = -1;
    }
#else
    free((POINTER) corepag);
#endif
    corepag = NULL;
    if (basef) {
    if (fclose(basef) == EOF) {
        DEBUG(("dbmclose: fclose(basef) failed\n"));
        ret = -1;
    }
    }
    if (basefname != NULL)
    free((POINTER) basefname);
    basef = NULL;
    pagf = NULL;
    if (fclose(dirf) == EOF) {
    DEBUG(("dbmclose: fclose(dirf) failed\n"));
    ret = -1;
    }
    DEBUG(("dbmclose: %s\n", (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 failed\n"));
        ret = -1;
    }
    }
#endif
    if (!conf.olddbz)
    if (putconf(dirf, &conf) < 0)
        ret = -1;

    DEBUG(("dbzsync: %s\n", (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 %d\n", key.dsize, DBZMAXKEY));
    }
    mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
    buffer[keysize] = '\0'; /* 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 %d\n", 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] == '\0') {
    cmplen--;
    sepp = &buffer[keysize - 1];
    }
    start(&srch, &key, FRESH);
    while ((key_ptr = search(&srch)) != NOTFOUND) {
    DEBUG(("got 0x%lx\n", key_ptr));

    /* fetch the key */
    if (fseek(basef, key_ptr, SEEK_SET) != 0) {
        DEBUG(("fetch: seek failed\n"));
        return (output);
    }
    if (fread((POINTER) buffer, 1, keysize, basef) != keysize) {
        DEBUG(("fetch: read failed\n"));
        return (output);
    }
    /* try it */
    buffer[keysize] = '\0'; /* terminated for DEBUG */
    (void)mapcase(buffer, buffer, keysize);
    DEBUG(("fetch: buffer (%s) looking for (%s) size = %d\n",
           buffer, key.dptr, keysize));
    if (memcmp((POINTER) key.dptr, (POINTER) buffer, cmplen) == 0 &&
        (*sepp == conf.fieldsep || *sepp == '\0')) {
        /* we found it */
        output.dptr = (char *)&key_ptr;
        output.dsize = SOF;
        DEBUG(("fetch: successful\n"));
        return (output);
    }
    }

    /* we didn't find it */
    DEBUG(("fetch: failed\n"));
    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 foulup\n"));
    return (NULL);
    }
    it = fopen(basefname, "r");
    if (it == NULL) {
    DEBUG(("latebase: still can't open base\n"));
    } else {
    DEBUG(("latebase: late open succeeded\n"));
    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] = '\0'; /* 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-only\n"));
    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%lx\n", 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 %ld\n", 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 error\n"));
    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 number\n"));
    *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: EOF\n"));
    *ep = -1;
    } else
    (void)ungetc(c, f);
    *p = '\0';

    if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
    DEBUG(("getno: `%s' non-numeric\n", 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 putconf\n"));
    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 %d\n", 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 char  *it;
#ifdef MMAP
    struct stat     st;

    if (fstat(fileno(f), &st) == -1) {
    DEBUG(("getcore: fstat failed\n"));
    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 failed\n"));
        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 failed\n"));
    return (NULL);
    }
#ifdef MC_ADVISE
    /* not present in all versions of mmap() */
    madvise(it, (size_t) conf.tsize * SOF, MADV_RANDOM);
#endif
#else
    register of_t  *p;
    register size_t i;
    register size_t nread;
    it = malloc((size_t) conf.tsize * SOF);
    if (it == NULL) {
    DEBUG(("getcore: malloc failed\n"));
    return (NULL);
    }
    nread = fread((POINTER) it, SOF, (size_t) conf.tsize, f);
    if (ferror(f)) {
    DEBUG(("getcore: read failed\n"));
    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 putcore\n"));
    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 restarted\n"));
    } else {
    sp->hash = h;
    sp->tag = MKTAG(h / conf.tsize);
    DEBUG(("tag 0x%lx\n", 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 @ %ld\n", place));

    /* get the tagged value */
    if (corepag != NULL && place < conf.tsize) {
        DEBUG(("search: in core\n"));
        value = MAPIN(corepag[place]);
    } else {
        /* seek, if necessary */
        dest = place * SOF;
        if (pagpos != dest) {
        if (fseek(pagf, dest, SEEK_SET) != 0) {
            DEBUG(("search: seek failed\n"));
            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 failed\n"));
        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 slot\n"));
        return (NOTFOUND);
    };

    /* check the tag */
    value = UNBIAS(value);
    DEBUG(("got 0x%lx\n", value));
    if (!HASTAG(value)) {
        DEBUG(("tagless\n"));
        return (value);
    } else if (TAG(value) == sp->tag) {
        DEBUG(("match\n"));
        return (NOTAG(value));
    } else {
        DEBUG(("mismatch 0x%lx\n", 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%lx\n", 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: incore\n"));
#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 failed\n"));
    sp->aborted = 1;
    return (-1);
    }
    /* write in data */
    if (fwrite((POINTER) & value, SOF, 1, pagf) != 1) {
    DEBUG(("set: write failed\n"));
    sp->aborted = 1;
    return (-1);
    }
    /* fflush improves robustness, and buffer re-use is rare anyway */
    if (fflush(pagf) == EOF) {
    DEBUG(("set: fflush failed\n"));
    sp->aborted = 1;
    return (-1);
    }
    DEBUG(("set: succeeded\n"));
    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 %d\n", 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: done\n"));
}

/*
 * - 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 '\0' */
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 != '\0'; lp++, up++) {
    c = *lp;
    cmap[c + OFFSET] = c;
    cmap[*up + OFFSET] = c;
    }
    for (i = 0; i < MAPSIZE; i++)
    if (cmap[i] == '\0')
        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 != '\0' && 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 == '\0' && *p2 == '\0')
    return (0);
    else if (*p1 == '\0')
    return (-1);
    else if (*p2 == '\0')
    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