home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 1 / GoldFishApril1994_CD2.img / d4xx / d473 / cnewssrc / cnews_src.lzh / libfake / dbz.c next >
C/C++ Source or Header  |  1990-07-04  |  43KB  |  1,738 lines
  1. /* :ts=4
  2.  *    dbz.c  V3.0
  3.  *
  4.  *    Copyright 1988 Jon Zeeff (zeeff@b-tech.ann-arbor.mi.us)
  5.  *    You can use this code in any manner, as long as you leave my name
  6.  *    on it and don't hold me responsible for any problems with it.
  7.  *
  8.  *    Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun  5 00:27:08 CDT 1988
  9.  *
  10.  *    Various improvments + INCORE by moraes@ai.toronto.edu (Mark Moraes)
  11.  *
  12.  *    Major reworking by Henry Spencer as part of the C News project.
  13.  *
  14.  *    These routines replace dbm as used by the usenet news software
  15.  *    (it's not a full dbm replacement by any means).  It's fast and
  16.  *    simple.  It contains no AT&T code.
  17.  *
  18.  *    In general, dbz's files are 1/20 the size of dbm's.  Lookup performance
  19.  *    is somewhat better, while file creation is spectacularly faster,
  20.  *    especially if the incore facility is used.
  21.  */
  22.  
  23. #include <stdio.h>
  24. #ifdef unix
  25. # include <sys/types.h>
  26. #endif /* unix */
  27. #include <string.h>
  28. #include <ctype.h>
  29. #include <dbz.h>
  30.  
  31. /*
  32.  * #ifdef index.  "LIA" = "leave it alone unless you know what you're doing".
  33.  *
  34.  * FUNNYSEEKS    SEEK_SET is not 0, get it from <unistd.h>
  35.  * INDEX_SIZE    backward compatibility with old dbz; avoid using this
  36.  * NMEMORY    number of days of memory for use in sizing new table (LIA)
  37.  * INCORE    backward compatibility with old dbz; use dbzincore() instead
  38.  * DBZDEBUG    enable debugging
  39.  * DEFSIZE    default table size (not as critical as in old dbz)
  40.  * OLDBNEWS    default case mapping as in old B News
  41.  * BNEWS    default case mapping as in current B News
  42.  * DEFCASE    default case-map algorithm selector
  43.  * NOTAGS    fseek offsets are strange, do not do tagging (see below)
  44.  * NPAGBUF    size of .pag buffer, in longs (LIA)
  45.  * SHISTBUF    size of ASCII-file buffer, in bytes (LIA)
  46.  * MAXRUN    length of run which shifts to next table (see below) (LIA)
  47.  * OVERFLOW    long-int arithmetic overflow must be avoided, will trap
  48.  */
  49.  
  50. #ifdef FUNNYSEEKS
  51. #include <unistd.h>
  52. #else
  53. #define    SEEK_SET    0
  54. #endif
  55. #ifdef OVERFLOW
  56. #include <limits.h>
  57. #endif
  58.  
  59. static int dbzversion = 3;    /* for validating .dir file format */
  60.  
  61. /*
  62.  * The dbz database exploits the fact that when news stores a <key,value>
  63.  * tuple, the `value' part is a seek offset into a text file, pointing to
  64.  * a copy of the `key' part.  This avoids the need to store a copy of
  65.  * the key in the dbz files.  However, the text file *must* exist and be
  66.  * consistent with the dbz files, or things will fail.
  67.  *
  68.  * The basic format of the database is a simple hash table containing the
  69.  * values.  A value is stored by indexing into the table using a hash value
  70.  * computed from the key; collisions are resolved by linear probing (just
  71.  * search forward for an empty slot, wrapping around to the beginning of
  72.  * the table if necessary).  Linear probing is a performance disaster when
  73.  * the table starts to get full, so a complication is introduced.  The
  74.  * database is actually one *or more* tables, stored sequentially in the
  75.  * .pag file, and the length of linear-probe sequences is limited.  The
  76.  * search (for an existing item or an empty slot) always starts in the
  77.  * first table, and whenever MAXRUN probes have been done in table N,
  78.  * probing continues in table N+1.  This behaves reasonably well even in
  79.  * cases of massive overflow.  There are some other small complications
  80.  * added, see comments below.
  81.  *
  82.  * The table size is fixed for any particular database, but is determined
  83.  * dynamically when a database is rebuilt.  The strategy is to try to pick
  84.  * the size so the first table will be no more than 75% full, that being
  85.  * about the point where performance starts to degrade.
  86.  */
  87.  
  88. /*
  89.  * The following is for backward compatibility.
  90.  */
  91. #ifdef INDEX_SIZE
  92. #define    DEFSIZE    INDEX_SIZE
  93. #endif
  94.  
  95. /*
  96.  * ANSI C says an offset into a file is a long, not an off_t, for some
  97.  * reason.  This actually does simplify life a bit, but it's still nice
  98.  * to have a distinctive name for it.  Beware, this is just for readability,
  99.  * don't try to change this.
  100.  */
  101. #define    of_t    long
  102. #define    SOF    (sizeof(of_t))
  103.  
  104. /*
  105.  * We assume that unused areas of a binary file are zeros, and that the
  106.  * bit pattern of `(of_t)0' is all zeros.  The alternative is rather
  107.  * painful file initialization.  Note that okayvalue(), if OVERFLOW is
  108.  * defined, knows what value of an offset would cause overflow.
  109.  */
  110. #define    VACANT        ((of_t)0)
  111. #define    BIAS(o)        ((o)+1)        /* make any valid of_t non-VACANT */
  112. #define    UNBIAS(o)    ((o)-1)        /* reverse BIAS() effect */
  113.  
  114. /*
  115.  * In a Unix implementation, or indeed any in which an of_t is a byte
  116.  * count, there are a bunch of high bits free in an of_t.  There is a
  117.  * use for them.  Checking a possible hit by looking it up in the base
  118.  * file is relatively expensive, and the cost can be dramatically reduced
  119.  * by using some of those high bits to tag the value with a few more bits
  120.  * of the key's hash.  This detects most false hits without the overhead of
  121.  * seek+read+strcmp.  We use the top bit to indicate whether the value is
  122.  * tagged or not, and don't tag a value which is using the tag bits itself.
  123.  * We're in trouble if the of_t representation wants to use the top bit.
  124.  * The actual bitmasks and offset come from the configuration stuff,
  125.  * which permits fiddling with them as necessary, and also suppressing
  126.  * them completely (by defining the masks to 0).  We build pre-shifted
  127.  * versions of the masks for efficiency.
  128.  */
  129. static of_t tagbits;        /* pre-shifted tag mask */
  130. static of_t taghere;        /* pre-shifted tag-enable bit */
  131. static of_t tagboth;        /* tagbits|taghere */
  132. #define    HASTAG(o)    ((o)&taghere)
  133. #define    TAG(o)        ((o)&tagbits)
  134. #define    NOTAG(o)    ((o)&~tagboth)
  135. #define    CANTAG(o)    (((o)&tagboth) == 0)
  136. #define    MKTAG(v)    (((v)<<conf.tagshift)&tagbits)
  137.  
  138. /*
  139.  * A new, from-scratch database, not built as a rebuild of an old one,
  140.  * needs to know table size, casemap algorithm, and tagging.  Normally
  141.  * the user supplies this info, but there have to be defaults.
  142.  */
  143. #ifndef DEFSIZE
  144. #define    DEFSIZE    120011        /* 300007 might be better */
  145. #endif
  146. #ifdef OLDBNEWS
  147. #define    DEFCASE    '0'        /* B2.10 -- no mapping */
  148. #endif
  149. #ifdef BNEWS
  150. #define    DEFCASE    '='        /* B2.11 -- all mapped */
  151. #endif
  152. #ifndef DEFCASE            /* C News compatibility is the default */
  153. #define    DEFCASE    'C'        /* C News -- RFC822 mapping */
  154. #endif
  155. #ifndef NOTAGS
  156. #define    TAGENB    0x80        /* tag enable is top bit, tag is next 7 */
  157. #define    TAGMASK    0x7f
  158. #define    TAGSHIFT    24
  159. #else
  160. #define    TAGENB    0        /* no tags */
  161. #define    TAGMASK    0
  162. #define    TAGSHIFT    0
  163. #endif
  164.  
  165. /*
  166.  * We read configuration info from the .dir file into this structure,
  167.  * so we can avoid wired-in assumptions for an existing database.
  168.  *
  169.  * Among the info is a record of recent peak usages, so that a new table
  170.  * size can be chosen intelligently when rebuilding.  10 is a good
  171.  * number of usages to keep, since news displays marked fluctuations
  172.  * in volume on a 7-day cycle.
  173.  */
  174. struct dbzconfig {
  175.     int olddbz;        /* .dir file empty but .pag not? */
  176.     of_t tsize;        /* table size */
  177. #    ifndef NMEMORY
  178. #    define    NMEMORY    10    /* # days of use info to remember */
  179. #    endif
  180. #    define    NUSEDS    (1+NMEMORY)
  181.     of_t used[NUSEDS];    /* entries used today, yesterday, ... */
  182.     int valuesize;        /* size of table values, == SOF */
  183.     int bytemap[SOF];    /* byte-order map */
  184.     char casemap;        /* case-mapping algorithm (see cipoint()) */
  185.     char fieldsep;        /* field separator in base file, if any */
  186.     of_t tagenb;        /* unshifted tag-enable bit */
  187.     of_t tagmask;        /* unshifted tag mask */
  188.     int tagshift;        /* shift count for tagmask and tagenb */
  189. };
  190. static struct dbzconfig conf;
  191. static int getconf();
  192. static long getno();
  193. static int putconf();
  194. static void mybytemap();
  195. static of_t bytemap();
  196.  
  197. /* 
  198.  * For a program that makes many, many references to the database, it
  199.  * is a large performance win to keep the table in core, if it will fit.
  200.  * Note that this does hurt robustness in the event of crashes, and
  201.  * dbmclose() *must* be called to flush the in-core database to disk.
  202.  * The code is prepared to deal with the possibility that there isn't
  203.  * enough memory.  There *is* an assumption that a size_t is big enough
  204.  * to hold the size (in bytes) of one table, so dbminit() tries to figure
  205.  * out whether this is possible first.
  206.  *
  207.  * The preferred way to ask for an in-core table is to do dbzincore(1)
  208.  * before dbminit().  The default is not to do it, although -DINCORE
  209.  * overrides this for backward compatibility with old dbz.
  210.  *
  211.  * We keep only the first table in core.  This greatly simplifies the
  212.  * code, and bounds memory demand.  Furthermore, doing this is a large
  213.  * performance win even in the event of massive overflow.
  214.  */
  215. #ifdef INCORE
  216. static int incore = 1;
  217. #else
  218. static int incore = 0;
  219. #endif
  220.  
  221. /*
  222.  * Stdio buffer for .pag reads.  Buffering more than about 16 does not help
  223.  * significantly at the densities we try to maintain, and the much larger
  224.  * buffers that most stdios default to are much more expensive to fill.
  225.  * With small buffers, stdio is performance-competitive with raw read(),
  226.  * and it's much more portable.
  227.  */
  228. #ifndef NPAGBUF
  229. #define    NPAGBUF    16
  230. #endif
  231. static of_t pagbuf[NPAGBUF];
  232.  
  233. /*
  234.  * Stdio buffer for base-file reads.  Message-IDs (all news ever needs to
  235.  * read) are essentially never longer than 64 bytes, and the typical stdio
  236.  * buffer is so much larger that it is much more expensive to fill.
  237.  */
  238. #ifndef SHISTBUF
  239. #define    SHISTBUF    64
  240. #endif
  241. static char basebuf[SHISTBUF];
  242.  
  243. /*
  244.  * Data structure for recording info about searches.
  245.  */
  246. struct searcher {
  247.     of_t place;        /* current location in file */
  248.     int tabno;        /* which table we're in */
  249.     int run;        /* how long we'll stay in this table */
  250. #        ifndef MAXRUN
  251. #        define    MAXRUN    100
  252. #        endif
  253.     long hash;        /* the key's hash code (for optimization) */
  254.     of_t tag;        /* tag we are looking for */
  255.     int seen;        /* have we examined current location? */
  256.     int aborted;        /* has i/o error aborted search? */
  257. };
  258. static void start();
  259. #define    FRESH    ((struct searcher *)NULL)
  260. static of_t search();
  261. #define    NOTFOUND    ((of_t)-1)
  262. static int okayvalue();
  263. static int set();
  264.  
  265. /*
  266.  * Arguably the searcher struct for a given routine ought to be local to
  267.  * it, but a fetch() is very often immediately followed by a store(), and
  268.  * in some circumstances it is a useful performance win to remember where
  269.  * the fetch() completed.  So we use a global struct and remember whether
  270.  * it is current.
  271.  */
  272. static struct searcher srch;
  273. static struct searcher *prevp;    /* &srch or FRESH */
  274.  
  275. /* byte-ordering stuff */
  276. static int mybmap[SOF];            /* my byte order (see mybytemap()) */
  277. static int bytesame;            /* is database order same as mine? */
  278. #define    MAPIN(o)    ((bytesame) ? (o) : bytemap((o), conf.bytemap, mybmap))
  279. #define    MAPOUT(o)    ((bytesame) ? (o) : bytemap((o), mybmap, conf.bytemap))
  280.  
  281. /*
  282.  * The double parentheses needed to make this work are ugly, but the
  283.  * alternative (under most compilers) is to pack around 2K of unused
  284.  * strings -- there's just no way to get rid of them.
  285.  */
  286. static int debug;            /* controlled by dbzdebug() */
  287. #ifdef DBZDEBUG
  288. #define DEBUG(args) if (debug) { (void) printf args ; }
  289. #else
  290. #define    DEBUG(args)    ;
  291. #endif
  292.  
  293. /* externals used */
  294. extern char *malloc();
  295. extern char *calloc();
  296. extern void free();        /* ANSI C; some old implementations say int */
  297. extern int atoi();
  298. extern long atol();
  299. #ifdef unix
  300. extern char *memcpy();        /* in case string.h doesn't do mem fns */
  301. extern char *memchr();
  302. #endif /* unix */
  303.  
  304. /* misc. forwards */
  305. static long hash();
  306. static void crcinit();
  307. static char *cipoint();
  308. static char *mapcase();
  309. static int isprime();
  310. static FILE *latebase();
  311.  
  312. /* file-naming stuff */
  313. static char dir[] = ".dir";
  314. static char pag[] = ".pag";
  315. static char *enstring();
  316.  
  317. /* central data structures */
  318. static FILE *basef;        /* descriptor for base file */
  319. static char *basefname;        /* name for not-yet-opened base file */
  320. static FILE *dirf;        /* descriptor for .dir file */
  321. static int dirronly;        /* dirf open read-only? */
  322. static FILE *pagf = NULL;    /* descriptor for .pag file */
  323. static of_t pagpos;        /* posn in pagf; only search may set != -1 */
  324. static int pagronly;        /* pagf open read-only? */
  325. static of_t *corepag;        /* incore version of .pag file, if any */
  326. static FILE *bufpagf;        /* well-buffered pagf, for incore rewrite */
  327. static of_t *getcore();
  328. static int putcore();
  329. static int written;        /* has a store() been done? */
  330.  
  331. /*
  332.  - dbzfresh - set up a new database, no historical info
  333.  */
  334. int                /* 0 success, -1 failure */
  335. dbzfresh(name, size, fs, cmap, tagmask)
  336. char *name;            /* base name; .dir and .pag must exist */
  337. long size;            /* table size (0 means default) */
  338. int fs;                /* field-separator character in base file */
  339. int cmap;            /* case-map algorithm (0 means default) */
  340. of_t tagmask;            /* 0 default, 1 no tags */
  341. {
  342.     register char *fn;
  343.     struct dbzconfig c;
  344.     register of_t m;
  345.     register FILE *f;
  346.  
  347.     if (pagf != NULL) {
  348.         DEBUG(("dbzfresh: database already open\n"));
  349.         return(-1);
  350.     }
  351.     if (size != 0 && size < 2) {
  352.         DEBUG(("dbzfresh: preposterous size (%ld)\n", size));
  353.         return(-1);
  354.     }
  355.  
  356.     /* get default configuration */
  357.     if (getconf((FILE *)NULL, (FILE *)NULL, &c) < 0)
  358.         return(-1);    /* "can't happen" */
  359.  
  360.     /* and mess with it as specified */
  361.     if (size != 0)
  362.         c.tsize = size;
  363.     c.fieldsep = fs;
  364.     switch (cmap) {
  365.     case 0:
  366.     case '0':
  367.     case 'B':        /* 2.10 compat */
  368.         c.casemap = '0';    /* '\0' nicer, but '0' printable! */
  369.         break;
  370.     case '=':
  371.     case 'b':        /* 2.11 compat */
  372.         c.casemap = '=';
  373.         break;
  374.     case 'C':
  375.         c.casemap = 'C';
  376.         break;
  377.     case '?':
  378.         c.casemap = DEFCASE;
  379.         break;
  380.     default:
  381.         DEBUG(("dbzfresh case map `%c' unknown\n", cmap));
  382.         return(-1);
  383.         break;
  384.     }
  385.     switch (tagmask) {
  386.     case 0:            /* default */
  387.         break;
  388.     case 1:            /* no tags */
  389.         c.tagshift = 0;
  390.         c.tagmask = 0;
  391.         c.tagenb = 0;
  392.         break;
  393.     default:
  394.         m = tagmask;
  395.         c.tagshift = 0;
  396.         while (!(m&01)) {
  397.             m >>= 1;
  398.             c.tagshift++;
  399.         }
  400.         c.tagmask = m;
  401.         c.tagenb = (m << 1) & ~m;
  402.         break;
  403.     }
  404.  
  405.     /* write it out */
  406.     fn = enstring(name, dir);
  407.     if (fn == NULL)
  408.         return(-1);
  409.     f = fopen(fn, "w");
  410.     free(fn);
  411.     if (f == NULL) {
  412.         DEBUG(("dbzfresh: unable to write config\n"));
  413.         return(-1);
  414.     }
  415.     if (putconf(f, &c) < 0) {
  416.         (void) fclose(f);
  417.         return(-1);
  418.     }
  419.     if (fclose(f) == EOF) {
  420.         DEBUG(("dbzfresh: fclose failure\n"));
  421.         return(-1);
  422.     }
  423.  
  424.     /* create/truncate .pag */
  425.     fn = enstring(name, pag);
  426.     if (fn == NULL)
  427.         return(-1);
  428.     f = fopen(fn, "w");
  429.     free(fn);
  430.     if (f == NULL) {
  431.         DEBUG(("dbzfresh: unable to create/truncate .pag file\n"));
  432.         return(-1);
  433.     } else
  434.         (void) fclose(f);
  435.  
  436.     /* and punt to dbminit for the hard work */
  437.     return(dbminit(name));
  438. }
  439.  
  440. /*
  441.  - dbzsize - what's a good table size to hold this many entries?
  442.  */
  443. long
  444. dbzsize(contents)
  445. long contents;            /* 0 means what's the default */
  446. {
  447.     register long n;
  448.  
  449.     if (contents <= 0) {    /* foulup or default inquiry */
  450.         DEBUG(("dbzsize: preposterous input (%ld)\n", contents));
  451.         return(DEFSIZE);
  452.     }
  453.     n = (contents/3)*4;    /* try to keep table at most 75% full */
  454.     if (!(n&01))        /* make it odd */
  455.         n++;
  456.     DEBUG(("dbzsize: tentative size %ld\n", n));
  457.     while (!isprime(n))    /* and look for a prime */
  458.         n += 2;
  459.     DEBUG(("dbzsize: final size %ld\n", n));
  460.  
  461.     return(n);
  462. }
  463.  
  464. /*
  465.  - isprime - is a number prime?
  466.  *
  467.  * This is not a terribly efficient approach.
  468.  */
  469. static int            /* predicate */
  470. isprime(x)
  471. register long x;
  472. {
  473.     static int quick[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0 };
  474.     register int *ip;
  475.     register long div;
  476.     register long stop;
  477.  
  478.     /* hit the first few primes quickly to eliminate easy ones */
  479.     /* this incidentally prevents ridiculously small tables */
  480.     for (ip = quick; (div = *ip) != 0; ip++)
  481.         if (x%div == 0) {
  482.             DEBUG(("isprime: quick result on %ld\n", (long)x));
  483.             return(0);
  484.         }
  485.  
  486.     /* approximate square root of x */
  487.     for (stop = x; x/stop < stop; stop >>= 1)
  488.         continue;
  489.     stop <<= 1;
  490.  
  491.     /* try odd numbers up to stop */
  492.     for (div = *--ip; div < stop; div += 2)
  493.         if (x%div == 0)
  494.             return(0);
  495.  
  496.     return(1);
  497. }
  498.  
  499. /*
  500.  - dbzagain - set up a new database to be a rebuild of an old one
  501.  */
  502. int                        /* 0 success, -1 failure */
  503. dbzagain(name, oldname)
  504. char *name;                /* base name; .dir and .pag must exist */
  505. char *oldname;            /* base name; all must exist */
  506. {
  507.     register char *fn;
  508.     struct dbzconfig c;
  509.     register int i;
  510.     register long top;
  511.     register FILE *f;
  512.  
  513.     if (pagf != NULL) {
  514.         DEBUG(("dbzagain: database already open\n"));
  515.         return(-1);
  516.     }
  517.  
  518.     /* pick up the old configuration */
  519.     fn = enstring(oldname, dir);
  520.     if (fn == NULL)
  521.         return(-1);
  522.     f = fopen(fn, "r");
  523.     free(fn);
  524.     if (f == NULL) {
  525.         DEBUG(("dbzagain: cannot open old .dir file\n"));
  526.         return(-1);
  527.     }
  528.     i = getconf(f, (FILE *)NULL, &c);
  529.     (void) fclose(f);
  530.     if (i < 0) {
  531.         DEBUG(("dbzagain: getconf failed\n"));
  532.         return(-1);
  533.     }
  534.  
  535.     /* tinker with it */
  536.     top = 0;
  537.     for (i = 0; i < NUSEDS; i++)
  538.         if (top < c.used[i])
  539.             top = c.used[i];
  540.     if (top == 0) {
  541.         DEBUG(("dbzagain: old table has no contents!\n"));
  542.         top = c.tsize/4*3;    /* and cross fingers */
  543.     }
  544.     for (i = NUSEDS-1; i > 0; i--)
  545.         c.used[i] = c.used[i-1];
  546.     c.used[0] = 0;
  547.     c.tsize = dbzsize(top);
  548.  
  549.     /* write it out */
  550.     fn = enstring(name, dir);
  551.     if (fn == NULL)
  552.         return(-1);
  553.     f = fopen(fn, "w");
  554.     free(fn);
  555.     if (f == NULL) {
  556.         DEBUG(("dbzagain: unable to write new .dir\n"));
  557.         return(-1);
  558.     }
  559.     i = putconf(f, &c);
  560.     (void) fclose(f);
  561.     if (i < 0) {
  562.         DEBUG(("dbzagain: putconf failed\n"));
  563.         return(-1);
  564.     }
  565.  
  566.     /* create/truncate .pag */
  567.     fn = enstring(name, pag);
  568.     if (fn == NULL)
  569.         return(-1);
  570.     f = fopen(fn, "w");
  571.     free(fn);
  572.     if (f == NULL) {
  573.         DEBUG(("dbzagain: unable to create/truncate .pag file\n"));
  574.         return(-1);
  575.     } else
  576.         (void) fclose(f);
  577.  
  578.     /* and let dbminit do the work */
  579.     return(dbminit(name));
  580. }
  581.  
  582. /*
  583.  - dbminit - open a database, creating it (using defaults) if necessary
  584.  */
  585. int                 /* 0 success, -1 failure */
  586. dbminit(name)
  587. char *name;
  588. {
  589.     register int i;
  590.     register size_t s;
  591.     register char *dirfname;
  592.     register char *pagfname;
  593.  
  594.     if (pagf != NULL) {
  595.         DEBUG(("dbminit: dbminit already called once\n"));
  596.         return(-1);
  597.     }
  598.  
  599.     /* open the .dir file */
  600.     dirfname = enstring(name, dir);
  601.     if (dirfname == NULL)
  602.         return(-1);
  603.     dirf = fopen(dirfname, "r+");
  604.     if (dirf == NULL) {
  605.         dirf = fopen(dirfname, "r");
  606.         dirronly = 1;
  607.     } else
  608.         dirronly = 0;
  609.     free(dirfname);
  610.     if (dirf == NULL) {
  611.         DEBUG(("dbminit: can't open .dir file\n"));
  612.         return(-1);
  613.     }
  614.  
  615.     /* open the .pag file */
  616.     pagfname = enstring(name, pag);
  617.     if (pagfname == NULL) {
  618.         (void) fclose(dirf);
  619.         return(-1);
  620.     }
  621.     pagf = fopen(pagfname, "r+b");
  622.     if (pagf == NULL) {
  623.         pagf = fopen(pagfname, "rb");
  624.         if (pagf == NULL) {
  625.             DEBUG(("dbminit: .pag open failed\n"));
  626.             (void) fclose(dirf);
  627.             free(pagfname);
  628.             return(-1);
  629.         }
  630.         pagronly = 1;
  631.     } else if (dirronly)
  632.         pagronly = 1;
  633.     else
  634.         pagronly = 0;
  635. #ifdef _IOFBF
  636.     (void) setvbuf(pagf, (char *)pagbuf, _IOFBF, sizeof(pagbuf));
  637. #endif
  638.     pagpos = -1;
  639.     /* don't free pagfname, need it below */
  640.  
  641.     /* open the base file */
  642.     basef = fopen(name, "r");
  643.     if (basef == NULL) {
  644.         DEBUG(("dbminit: basefile open failed\n"));
  645.         basefname = enstring(name, "");
  646.         if (basefname == NULL) {
  647.             (void) fclose(pagf);
  648.             (void) fclose(dirf);
  649.             free(pagfname);
  650.             return(-1);
  651.         }
  652.     } else
  653.         basefname = NULL;
  654. #ifdef _IOFBF
  655.     if (basef != NULL)
  656.         (void) setvbuf(basef, basebuf, _IOFBF, sizeof(basebuf));
  657. #endif
  658.  
  659.     /* pick up configuration */
  660.     if (getconf(dirf, pagf, &conf) < 0) {
  661.         DEBUG(("dbminit: getconf failure\n"));
  662.         (void) fclose(basef);
  663.         (void) fclose(pagf);
  664.         (void) fclose(dirf);
  665.         free(pagfname);
  666.         return(-1);
  667.     }
  668.     tagbits = conf.tagmask << conf.tagshift;
  669.     taghere = conf.tagenb << conf.tagshift;
  670.     tagboth = tagbits | taghere;
  671.     mybytemap(mybmap);
  672.     bytesame = 1;
  673.     for (i = 0; i < SOF; i++)
  674.         if (mybmap[i] != conf.bytemap[i])
  675.             bytesame = 0;
  676.  
  677.     /* get first table into core, if it looks desirable and feasible */
  678.     s = (size_t)conf.tsize * SOF;
  679.     if (incore && (of_t)(s/SOF) == conf.tsize) {
  680.         bufpagf = fopen(pagfname, (pagronly) ? "rb" : "r+b");
  681.         if (bufpagf != NULL)
  682.             corepag = getcore(bufpagf);
  683.     } else {
  684.         bufpagf = NULL;
  685.         corepag = NULL;
  686.     }
  687.     free(pagfname);
  688.  
  689.     /* misc. setup */
  690.     crcinit();
  691.     written = 0;
  692.     prevp = FRESH;
  693.     DEBUG(("dbminit: succeeded\n"));
  694.     return(0);
  695. }
  696.  
  697. /*
  698.  - enstring - concatenate two strings into a malloced area
  699.  */
  700. static char *            /* NULL if malloc fails */
  701. enstring(s1, s2)
  702. char *s1;
  703. char *s2;
  704. {
  705.     register char *p;
  706.  
  707.     p = malloc((size_t)strlen(s1) + (size_t)strlen(s2) + 1);
  708.     if (p != NULL) {
  709.         (void) strcpy(p, s1);
  710.         (void) strcat(p, s2);
  711.     } else {
  712.         DEBUG(("enstring(%s, %s) out of memory\n", s1, s2));
  713.     }
  714.     return(p);
  715. }
  716.  
  717. /*
  718.  - dbmclose - close a database
  719.  */
  720. int
  721. dbmclose()
  722. {
  723.     register int ret = 0;
  724.  
  725.     if (pagf == NULL) {
  726.         DEBUG(("dbmclose: not opened!\n"));
  727.         return(-1);
  728.     }
  729.  
  730.     if (fclose(pagf) == EOF) {
  731.         DEBUG(("dbmclose: fclose(pagf) failed\n"));
  732.         ret = -1;
  733.     }
  734.     if (dbzsync() < 0)
  735.         ret = -1;
  736.     if (bufpagf != NULL && fclose(bufpagf) == EOF) {
  737.         DEBUG(("dbmclose: fclose(bufpagf) failed\n"));
  738.         ret = -1;
  739.     }
  740.     if (corepag != NULL)
  741.         free((char *)corepag);
  742.     corepag = NULL;
  743.     if (fclose(basef) == EOF) {
  744.         DEBUG(("dbmclose: fclose(basef) failed\n"));
  745.         ret = -1;
  746.     }
  747.     if (basefname != NULL)
  748.         free(basefname);
  749.     basef = NULL;
  750.     pagf = NULL;
  751.     if (fclose(dirf) == EOF) {
  752.         DEBUG(("dbmclose: fclose(dirf) failed\n"));
  753.         ret = -1;
  754.     }
  755.  
  756.     DEBUG(("dbmclose: %s\n", (ret == 0) ? "succeeded" : "failed"));
  757.     return(ret);
  758. }
  759.  
  760. /*
  761.  - dbzsync - push all in-core data out to disk
  762.  */
  763. int
  764. dbzsync()
  765. {
  766.     register int ret = 0;
  767.  
  768.     if (pagf == NULL) {
  769.         DEBUG(("dbzsync: not opened!\n"));
  770.         return(-1);
  771.     }
  772.     if (!written)
  773.         return(0);
  774.  
  775.     if (corepag != NULL) {
  776.         if (putcore(corepag, bufpagf) < 0) {
  777.             DEBUG(("dbzsync: putcore failed\n"));
  778.             ret = -1;
  779.         }
  780.     }
  781.     if (!conf.olddbz)
  782.         if (putconf(dirf, &conf) < 0)
  783.             ret = -1;
  784.  
  785.     DEBUG(("dbzsync: %s\n", (ret == 0) ? "succeeded" : "failed"));
  786.     return(ret);
  787. }
  788.  
  789. /*
  790.  - dbzfetch - fetch() with case mapping built in
  791.  */
  792. datum
  793. dbzfetch(key)
  794. datum key;
  795. {
  796.     char buffer[DBZMAXKEY + 1];
  797.     datum mappedkey;
  798.     register size_t keysize;
  799.  
  800.     DEBUG(("dbzfetch: (%s)\n", key.dptr));
  801.  
  802.     /* Key is supposed to be less than DBZMAXKEY */
  803.     keysize = key.dsize;
  804.     if (keysize >= DBZMAXKEY) {
  805.         keysize = DBZMAXKEY;
  806.         DEBUG(("keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
  807.     }
  808.  
  809.     mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
  810.     buffer[keysize] = '\0';    /* just a debug aid */
  811.     mappedkey.dsize = keysize;
  812.  
  813.     return(fetch(mappedkey));
  814. }
  815.  
  816. /*
  817.  - fetch - get an entry from the database
  818.  *
  819.  * Disgusting fine point, in the name of backward compatibility:  if the
  820.  * last character of "key" is a NUL, that character is (effectively) not
  821.  * part of the comparison against the stored keys.
  822.  */
  823. datum                /* dptr NULL, dsize 0 means failure */
  824. fetch(key)
  825. datum key;
  826. {
  827.     char buffer[DBZMAXKEY + 1];
  828.     static of_t key_ptr;        /* return value points here */
  829.     datum output;
  830.     register size_t keysize;
  831.     register size_t cmplen;
  832.     register char *sepp;
  833.  
  834.     DEBUG(("fetch: (%s)\n", key.dptr));
  835.     output.dptr = NULL;
  836.     output.dsize = 0;
  837.     prevp = FRESH;
  838.  
  839.     /* Key is supposed to be less than DBZMAXKEY */
  840.     keysize = key.dsize;
  841.     if (keysize >= DBZMAXKEY) {
  842.         keysize = DBZMAXKEY;
  843.         DEBUG(("keysize is %d - truncated to %d\n", key.dsize, DBZMAXKEY));
  844.     }
  845.  
  846.     if (pagf == NULL) {
  847.         DEBUG(("fetch: database not open!\n"));
  848.         return(output);
  849.     } else if (basef == NULL) {    /* basef didn't exist yet */
  850.         basef = latebase();
  851.         if (basef == NULL)
  852.             return(output);
  853.     }
  854.  
  855.     cmplen = keysize;
  856.     sepp = &conf.fieldsep;
  857.     if (key.dptr[keysize-1] == '\0') {
  858.         cmplen--;
  859.         sepp = &buffer[keysize-1];
  860.     }
  861.     start(&srch, &key, FRESH);
  862.     while ((key_ptr = search(&srch)) != NOTFOUND) {
  863.         DEBUG(("got 0x%lx\n", key_ptr));
  864.  
  865.         /* fetch the key */
  866.         if (fseek(basef, key_ptr, SEEK_SET) != 0) {
  867.             DEBUG(("fetch: seek failed\n"));
  868.             return(output);
  869.         }
  870.         if (fread(buffer, 1, keysize, basef) != keysize) {
  871.             DEBUG(("fetch: read failed\n"));
  872.             return(output);
  873.         }
  874.  
  875.         /* try it */
  876.         buffer[keysize] = '\0';        /* terminated for DEBUG */
  877.         (void) mapcase(buffer, buffer, keysize);
  878.         DEBUG(("fetch: buffer (%s) looking for (%s) size = %d\n", 
  879.                         buffer, key.dptr, keysize));
  880.         if (memcmp(key.dptr, buffer, cmplen) == 0 &&
  881.                 (*sepp == conf.fieldsep || *sepp == '\0')) {
  882.             /* we found it */
  883.             output.dptr = (char *)&key_ptr;
  884.             output.dsize = SOF;
  885.             DEBUG(("fetch: successful\n"));
  886.             return(output);
  887.         }
  888.     }
  889.  
  890.     /* we didn't find it */
  891.     DEBUG(("fetch: failed\n"));
  892.     prevp = &srch;            /* remember where we stopped */
  893.     return(output);
  894. }
  895.  
  896. /*
  897.  - latebase - try to open a base file that wasn't there at the start
  898.  */
  899. static FILE *
  900. latebase()
  901. {
  902.     register FILE *it;
  903.  
  904.     if (basefname == NULL) {
  905.         DEBUG(("latebase: name foulup\n"));
  906.         return(NULL);
  907.     }
  908.     it = fopen(basefname, "r");
  909.     if (it == NULL) {
  910.         DEBUG(("latebase: still can't open base\n"));
  911.     } else {
  912.         DEBUG(("latebase: late open succeeded\n"));
  913.         free(basefname);
  914.         basefname = NULL;
  915. #ifdef _IOFBF
  916.         (void) setvbuf(it, basebuf, _IOFBF, sizeof(basebuf));
  917. #endif
  918.     }
  919.     return(it);
  920. }
  921.  
  922. /*
  923.  - dbzstore - store() with case mapping built in
  924.  */
  925. int
  926. dbzstore(key, data)
  927. datum key;
  928. datum data;
  929. {
  930.     char buffer[DBZMAXKEY + 1];
  931.     datum mappedkey;
  932.     register size_t keysize;
  933.  
  934.     DEBUG(("dbzstore: (%s)\n", key.dptr));
  935.  
  936.     /* Key is supposed to be less than DBZMAXKEY */
  937.     keysize = key.dsize;
  938.     if (keysize >= DBZMAXKEY) {
  939.         DEBUG(("dbzstore: key size too big (%d)\n", key.dsize));
  940.         return(-1);
  941.     }
  942.  
  943.     mappedkey.dptr = mapcase(buffer, key.dptr, keysize);
  944.     buffer[keysize] = '\0';    /* just a debug aid */
  945.     mappedkey.dsize = keysize;
  946.  
  947.     return(store(mappedkey, data));
  948. }
  949.  
  950. /*
  951.  - store - add an entry to the database
  952.  */
  953. int                /* 0 success, -1 failure */
  954. store(key, data)
  955. datum key;
  956. datum data;
  957. {
  958.     of_t value;
  959.  
  960.     if (pagf == NULL) {
  961.         DEBUG(("store: database not open!\n"));
  962.         return(-1);
  963.     } else if (basef == NULL) {    /* basef didn't exist yet */
  964.         basef = latebase();
  965.         if (basef == NULL)
  966.             return(-1);
  967.     }
  968.     if (pagronly) {
  969.         DEBUG(("store: database open read-only\n"));
  970.         return(-1);
  971.     }
  972.     if (data.dsize != SOF) {
  973.         DEBUG(("store: value size wrong (%d)\n", data.dsize));
  974.         return(-1);
  975.     }
  976.     if (key.dsize >= DBZMAXKEY) {
  977.         DEBUG(("store: key size too big (%d)\n", key.dsize));
  978.         return(-1);
  979.     }
  980.  
  981.     /* copy the value in to ensure alignment */
  982.     (void) memcpy((char *)&value, data.dptr, SOF);
  983.     DEBUG(("store: (%s, %ld)\n", key.dptr, (long)value));
  984.     if (!okayvalue(value)) {
  985.         DEBUG(("store: reserved bit or overflow in 0x%lx\n", value));
  986.         return(-1);
  987.     }
  988.  
  989.     /* find the place, exploiting previous search if possible */
  990.     start(&srch, &key, prevp);
  991.     while (search(&srch) != NOTFOUND)
  992.         continue;
  993.  
  994.     prevp = FRESH;
  995.     conf.used[0]++;
  996.     DEBUG(("store: used count %ld\n", conf.used[0]));
  997.     written = 1;
  998.     return(set(&srch, value));
  999. }
  1000.  
  1001. /*
  1002.  - dbzincore - control attempts to keep .pag file in core
  1003.  */
  1004. int                /* old setting */
  1005. dbzincore(value)
  1006. int value;
  1007. {
  1008.     register int old = incore;
  1009.  
  1010.     incore = value;
  1011.     return(old);
  1012. }
  1013.  
  1014. /*
  1015.  - getconf - get configuration from .dir file
  1016.  */
  1017. static int                /* 0 success, -1 failure */
  1018. getconf(df, pf, cp)
  1019. register FILE *df;        /* NULL means just give me the default */
  1020. register FILE *pf;        /* NULL means don't care about .pag */
  1021. register struct dbzconfig *cp;
  1022. {
  1023.     register int c;
  1024.     register int i;
  1025.     int err = 0;
  1026.  
  1027.     c = (df != NULL) ? getc(df) : EOF;
  1028.     if (c == EOF) {        /* empty file, no configuration known */
  1029.         cp->olddbz = 0;
  1030.         if (df != NULL && pf != NULL && getc(pf) != EOF)
  1031.             cp->olddbz = 1;
  1032.         cp->tsize = DEFSIZE;
  1033.         cp->fieldsep = '\t';
  1034.         for (i = 0; i < NUSEDS; i++)
  1035.             cp->used[i] = 0;
  1036.         cp->valuesize = SOF;
  1037.         mybytemap(cp->bytemap);
  1038.         cp->casemap = DEFCASE;
  1039.         cp->tagenb = TAGENB;
  1040.         cp->tagmask = TAGMASK;
  1041.         cp->tagshift = TAGSHIFT;
  1042.         DEBUG(("getconf: defaults (%ld, %c, (0x%lx/0x%lx<<%d))\n",
  1043.             cp->tsize, cp->casemap, cp->tagenb, 
  1044.             cp->tagmask, cp->tagshift));
  1045.         return(0);
  1046.     }
  1047.     (void) ungetc(c, df);
  1048.  
  1049.     /* first line, the vital stuff */
  1050.     if (getc(df) != 'd' || getc(df) != 'b' || getc(df) != 'z')
  1051.         err = -1;
  1052.     if (getno(df, &err) != dbzversion)
  1053.         err = -1;
  1054.     cp->tsize = getno(df, &err);
  1055.     cp->fieldsep = getno(df, &err);
  1056.     while ((c = getc(df)) == ' ')
  1057.         continue;
  1058.     cp->casemap = c;
  1059.     cp->tagenb = getno(df, &err);
  1060.     cp->tagmask = getno(df, &err);
  1061.     cp->tagshift = getno(df, &err);
  1062.     cp->valuesize = getno(df, &err);
  1063.     if (cp->valuesize != SOF) {
  1064.         DEBUG(("getconf: wrong of_t size (%d)\n", cp->valuesize));
  1065.         err = -1;
  1066.     }
  1067.     for (i = 0; i < cp->valuesize; i++)
  1068.         cp->bytemap[i] = getno(df, &err);
  1069.     if (getc(df) != '\n')
  1070.         err = -1;
  1071.     DEBUG(("size %ld, sep %d, cmap %c, tags 0x%lx/0x%lx<<%d, ", cp->tsize,
  1072.             cp->fieldsep, cp->casemap, cp->tagenb, cp->tagmask,
  1073.             cp->tagshift));
  1074.     DEBUG(("bytemap (%d)", cp->valuesize));
  1075.     for (i = 0; i < cp->valuesize; i++) {
  1076.         DEBUG((" %d", cp->bytemap[i]));
  1077.     }
  1078.     DEBUG(("\n"));
  1079.  
  1080.     /* second line, the usages */
  1081.     for (i = 0; i < NUSEDS; i++)
  1082.         cp->used[i] = getno(df, &err);
  1083.     if (getc(df) != '\n')
  1084.         err = -1;
  1085.     DEBUG(("used %ld %ld %ld...\n", cp->used[0], cp->used[1], cp->used[2]));
  1086.  
  1087.     if (err < 0) {
  1088.         DEBUG(("getconf error\n"));
  1089.         return(-1);
  1090.     }
  1091.     return(0);
  1092. }
  1093.  
  1094. /*
  1095.  - getno - get a long
  1096.  */
  1097. static long
  1098. getno(f, ep)
  1099. FILE *f;
  1100. int *ep;
  1101. {
  1102.     register char *p;
  1103. #    define    MAXN    50
  1104.     char getbuf[MAXN];
  1105.     register int c;
  1106.  
  1107.     while ((c = getc(f)) == ' ')
  1108.         continue;
  1109.     if (c == EOF || c == '\n') {
  1110.         DEBUG(("getno: missing number\n"));
  1111.         *ep = -1;
  1112.         return(0);
  1113.     }
  1114.     p = getbuf;
  1115.     *p++ = c;
  1116.     while ((c = getc(f)) != EOF && c != '\n' && c != ' ')
  1117.         if (p < &getbuf[MAXN-1])
  1118.             *p++ = c;
  1119.     if (c == EOF) {
  1120.         DEBUG(("getno: EOF\n"));
  1121.         *ep = -1;
  1122.     } else
  1123.         (void) ungetc(c, f);
  1124.     *p = '\0';
  1125.  
  1126.     if (strspn(getbuf, "-1234567890") != strlen(getbuf)) {
  1127.         DEBUG(("getno: `%s' non-numeric\n", getbuf));
  1128.         *ep = -1;
  1129.     }
  1130.     return(atol(getbuf));
  1131. }
  1132.  
  1133. /*
  1134.  - putconf - write configuration to .dir file
  1135.  */
  1136. static int            /* 0 success, -1 failure */
  1137. putconf(f, cp)
  1138. register FILE *f;
  1139. register struct dbzconfig *cp;
  1140. {
  1141.     register int i;
  1142.     register int ret = 0;
  1143.  
  1144.     if (fseek(f, (of_t)0, SEEK_SET) != 0) {
  1145.         DEBUG(("fseek failure in putconf\n"));
  1146.         ret = -1;
  1147.     }
  1148.     fprintf(f, "dbz %d %ld %d %c %ld %ld %d %d", dbzversion, cp->tsize,
  1149.                 cp->fieldsep, cp->casemap, cp->tagenb,
  1150.                 cp->tagmask, cp->tagshift, cp->valuesize);
  1151.     for (i = 0; i < cp->valuesize; i++)
  1152.         fprintf(f, " %d", cp->bytemap[i]);
  1153.     fprintf(f, "\n");
  1154.     for (i = 0; i < NUSEDS; i++)
  1155.         fprintf(f, "%ld%c", cp->used[i], (i < NUSEDS-1) ? ' ' : '\n');
  1156.  
  1157.     (void) fflush(f);
  1158.     if (ferror(f))
  1159.         ret = -1;
  1160.  
  1161.     DEBUG(("putconf status %d\n", ret));
  1162.     return(ret);
  1163. }
  1164.  
  1165. /*
  1166.  - getcore - try to set up an in-core copy of .pag file
  1167.  */
  1168. static of_t *            /* pointer to copy, or NULL */
  1169. getcore(f)
  1170. FILE *f;
  1171. {
  1172.     register of_t *p;
  1173.     register size_t i;
  1174.     register size_t nread;
  1175.     register char *it;
  1176.  
  1177.     it = malloc((size_t)conf.tsize * SOF);
  1178.     if (it == NULL) {
  1179.         DEBUG(("getcore: malloc failed\n"));
  1180.         return(NULL);
  1181.     }
  1182.  
  1183.     nread = fread(it, SOF, (size_t)conf.tsize, f);
  1184.     if (ferror(f)) {
  1185.         DEBUG(("getcore: read failed\n"));
  1186.         free(it);
  1187.         return(NULL);
  1188.     }
  1189.  
  1190.     p = (of_t *)it + nread;
  1191.     i = (size_t)conf.tsize - nread;
  1192.     while (i-- > 0)
  1193.         *p++ = VACANT;
  1194.     return((of_t *)it);
  1195. }
  1196.  
  1197. /*
  1198.  - putcore - try to rewrite an in-core table
  1199.  */
  1200. static int            /* 0 okay, -1 fail */
  1201. putcore(tab, f)
  1202. of_t *tab;
  1203. FILE *f;
  1204. {
  1205.     if (fseek(f, (of_t)0, SEEK_SET) != 0) {
  1206.         DEBUG(("fseek failure in putcore\n"));
  1207.         return(-1);
  1208.     }
  1209.     (void) fwrite((char *)tab, SOF, (size_t)conf.tsize, f);
  1210.     (void) fflush(f);
  1211.     return((ferror(f)) ? -1 : 0);
  1212. }
  1213.  
  1214. /*
  1215.  - start - set up to start or restart a search
  1216.  */
  1217. static void
  1218. start(sp, kp, osp)
  1219. register struct searcher *sp;
  1220. register datum *kp;
  1221. register struct searcher *osp;        /* may be FRESH, i.e. NULL */
  1222. {
  1223.     register long h;
  1224.  
  1225.     h = hash(kp->dptr, kp->dsize);
  1226.     if (osp != FRESH && osp->hash == h) {
  1227.         if (sp != osp)
  1228.             *sp = *osp;
  1229.         DEBUG(("search restarted\n"));
  1230.     } else {
  1231.         sp->hash = h;
  1232.         sp->tag = MKTAG(h / conf.tsize);
  1233.         DEBUG(("tag 0x%lx\n", sp->tag));
  1234.         sp->place = h % conf.tsize;
  1235.         sp->tabno = 0;
  1236.         sp->run = (conf.olddbz) ? conf.tsize : MAXRUN;
  1237.         sp->aborted = 0;
  1238.     }
  1239.     sp->seen = 0;
  1240. }
  1241.  
  1242. /*
  1243.  - search - conduct part of a search
  1244.  */
  1245. static of_t            /* NOTFOUND if we hit VACANT or error */
  1246. search(sp)
  1247. register struct searcher *sp;
  1248. {
  1249.     register of_t dest;
  1250.     register of_t value;
  1251.     of_t val;        /* buffer for value (can't fread register) */
  1252.     register of_t place;
  1253.  
  1254.     if (sp->aborted)
  1255.         return(NOTFOUND);
  1256.  
  1257.     for (;;) {
  1258.         /* determine location to be examined */
  1259.         place = sp->place;
  1260.         if (sp->seen) {
  1261.             /* go to next location */
  1262.             if (--sp->run <= 0) {
  1263.                 sp->tabno++;
  1264.                 sp->run = MAXRUN;
  1265.             }
  1266.             place = (place+1)%conf.tsize + sp->tabno*conf.tsize;
  1267.             sp->place = place;
  1268.         } else
  1269.             sp->seen = 1;    /* now looking at current location */
  1270.         DEBUG(("search @ %ld\n", place));
  1271.  
  1272.         /* get the tagged value */
  1273.         if (corepag != NULL && place < conf.tsize) {
  1274.             DEBUG(("search: in core\n"));
  1275.             value = MAPIN(corepag[place]);
  1276.         } else {
  1277.             /* seek, if necessary */
  1278.             dest = place * SOF;
  1279.             if (pagpos != dest) {
  1280.                 if (fseek(pagf, dest, SEEK_SET) != 0) {
  1281.                     DEBUG(("search: seek failed\n"));
  1282.                     pagpos = -1;
  1283.                     sp->aborted = 2;
  1284.                     return(NOTFOUND);
  1285.                 }
  1286.                 pagpos = dest;
  1287.             }
  1288.  
  1289.             /* read it */
  1290.             if (fread((char *)&val, sizeof(val), 1, pagf) == 1)
  1291.                 value = MAPIN(val);
  1292.             else if (ferror(pagf)) {
  1293.                 DEBUG(("search: read failed\n"));
  1294.                 pagpos = -1;
  1295.                 sp->aborted = 2;
  1296.                 return(NOTFOUND);
  1297.             } else
  1298.                 value = VACANT;
  1299.  
  1300.             /* and finish up */
  1301.             pagpos += sizeof(val);
  1302.         }
  1303.  
  1304.         /* vacant slot is always cause to return */
  1305.         if (value == VACANT) {
  1306.             DEBUG(("search: empty slot\n"));
  1307.             return(NOTFOUND);
  1308.         };
  1309.  
  1310.         /* check the tag */
  1311.         value = UNBIAS(value);
  1312.         DEBUG(("got 0x%lx\n", value));
  1313.         if (!HASTAG(value)) {
  1314.             DEBUG(("tagless\n"));
  1315.             return(value);
  1316.         } else if (TAG(value) == sp->tag) {
  1317.             DEBUG(("match\n"));
  1318.             return(NOTAG(value));
  1319.         } else {
  1320.             DEBUG(("mismatch 0x%lx\n", TAG(value)));
  1321.         }
  1322.     }
  1323.     /* NOTREACHED */
  1324. }
  1325.  
  1326. /*
  1327.  - okayvalue - check that a value can be stored
  1328.  */
  1329. static int            /* predicate */
  1330. okayvalue(value)
  1331. of_t value;
  1332. {
  1333.     if (HASTAG(value))
  1334.         return(0);
  1335. #ifdef OVERFLOW
  1336.     if (value == LONG_MAX)    /* BIAS() and UNBIAS() will overflow */
  1337.         return(0);
  1338. #endif
  1339.     return(1);
  1340. }
  1341.  
  1342. /*
  1343.  - set - store a value into a location previously found by search
  1344.  */
  1345. static int            /* 0 success, -1 failure */
  1346. set(sp, value)
  1347. register struct searcher *sp;
  1348. of_t value;
  1349. {
  1350.     register of_t place = sp->place;
  1351.     register of_t v = value;
  1352.  
  1353.     if (sp->aborted == 1)    /* 2 if search() failed in fseek() or fread() */
  1354.         return(-1);
  1355.  
  1356.     if (CANTAG(v) && !conf.olddbz) {
  1357.         v |= sp->tag | taghere;
  1358.         if (v != UNBIAS(VACANT))    /* BIAS(v) won't look VACANT */
  1359. #ifdef OVERFLOW
  1360.             if (v != LONG_MAX)    /* and it won't overflow */
  1361. #endif
  1362.             value = v;
  1363.     }
  1364.     DEBUG(("tagged value is 0x%lx\n", value));
  1365.     value = BIAS(value);
  1366.     value = MAPOUT(value);
  1367.  
  1368.     /* If we have the index file in memory, use it */
  1369.     if (corepag != NULL && place < conf.tsize) {
  1370.         corepag[place] = value;
  1371.         DEBUG(("set: incore\n"));
  1372.         return(0);
  1373.     }
  1374.  
  1375.     /* seek to spot */
  1376.     pagpos = -1;        /* invalidate position memory */
  1377.     if (fseek(pagf, place * SOF, SEEK_SET) != 0) {
  1378.         DEBUG(("set: seek failed\n"));
  1379. #ifdef AMIGA
  1380.         /*
  1381.          *    On the Amiga, we must actually write out the zero bytes
  1382.          *    required to bring the file to its new size.
  1383.          */
  1384.         {
  1385.             long cnt;
  1386.             void *tmp;
  1387.  
  1388.             fseek(pagf, 0L, SEEK_END);
  1389.             fgetpos(pagf, &cnt);
  1390.             cnt = (sizeof(VACANT) * place) - cnt;
  1391.             if (tmp = malloc(cnt)) {
  1392.                 memset(tmp, VACANT, cnt);
  1393.                 fwrite(tmp, cnt, 1, pagf);
  1394.                 free(tmp);
  1395.             } else {
  1396.                 static long array[4] = { VACANT, VACANT, VACANT, VACANT };
  1397.                 cnt >>= 4;
  1398.                 do {
  1399.                     fwrite(array, sizeof(array), 1, pagf);
  1400.                 } while (--cnt > 0);
  1401.             }
  1402.         }
  1403.         if (fseek(pagf, place * SOF, SEEK_SET))
  1404. #endif /* AMIGA */
  1405.         {
  1406.             sp->aborted = 1;
  1407.             return(-1);
  1408.         }
  1409.     }
  1410.     /* write in data */
  1411.     if (fwrite((char *)&value, SOF, 1, pagf) != 1) {
  1412.         DEBUG(("set: write failed\n"));
  1413.         sp->aborted = 1;
  1414.         return(-1);
  1415.     }
  1416.     /* fflush improves robustness, and buffer re-use is rare anyway */
  1417.     if (fflush(pagf) == EOF) {
  1418.         DEBUG(("set: fflush failed\n"));
  1419.         sp->aborted = 1;
  1420.         return(-1);
  1421.     }
  1422.  
  1423.     DEBUG(("set: succeeded\n"));
  1424.     return(0);
  1425. }
  1426.  
  1427. /*
  1428.  - mybytemap - determine this machine's byte map
  1429.  *
  1430.  * A byte map is an array of ints, sizeof(of_t) of them.  The 0th int
  1431.  * is the byte number of the high-order byte in my of_t, and so forth.
  1432.  */
  1433. static void
  1434. mybytemap(map)
  1435. int map[];            /* -> int[SOF] */
  1436. {
  1437.     union {
  1438.         of_t o;
  1439.         char c[SOF];
  1440.     } u;
  1441.     register int *mp = &map[SOF];
  1442.     register int ntodo;
  1443.     register int i;
  1444.  
  1445.     u.o = 1;
  1446.     for (ntodo = (int)SOF; ntodo > 0; ntodo--) {
  1447.         for (i = 0; i < SOF; i++)
  1448.             if (u.c[i] != 0)
  1449.                 break;
  1450.         if (i == SOF) {
  1451.             /* trouble -- set it to *something* consistent */
  1452.             DEBUG(("mybytemap: nonexistent byte %d!!!\n", ntodo));
  1453.             for (i = 0; i < SOF; i++)
  1454.                 map[i] = i;
  1455.             return;
  1456.         }
  1457.         DEBUG(("mybytemap: byte %d\n", i));
  1458.         *--mp = i;
  1459.         while (u.c[i] != 0)
  1460.             u.o <<= 1;
  1461.     }
  1462. }
  1463.  
  1464. /*
  1465.  - bytemap - transform an of_t from byte ordering map1 to map2
  1466.  */
  1467. static of_t            /* transformed result */
  1468. bytemap(ino, map1, map2)
  1469. of_t ino;
  1470. int *map1;
  1471. int *map2;
  1472. {
  1473.     union oc {
  1474.         of_t o;
  1475.         char c[SOF];
  1476.     };
  1477.     union oc in;
  1478.     union oc out;
  1479.     register int i;
  1480.  
  1481.     in.o = ino;
  1482.     for (i = 0; i < SOF; i++)
  1483.         out.c[map2[i]] = in.c[map1[i]];
  1484.     return(out.o);
  1485. }
  1486.  
  1487. /*
  1488.  * This is a simplified version of the pathalias hashing function.
  1489.  * Thanks to Steve Belovin and Peter Honeyman
  1490.  *
  1491.  * hash a string into a long int.  31 bit crc (from andrew appel).
  1492.  * the crc table is computed at run time by crcinit() -- we could
  1493.  * precompute, but it takes 1 clock tick on a 750.
  1494.  *
  1495.  * This fast table calculation works only if POLY is a prime polynomial
  1496.  * in the field of integers modulo 2.  Since the coefficients of a
  1497.  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
  1498.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  1499.  * 31 down to 25 are zero.  Happily, we have candidates, from
  1500.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  1501.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  1502.  *    x^31 + x^3 + x^0
  1503.  *
  1504.  * We reverse the bits to get:
  1505.  *    111101010000000000000000000000001 but drop the last 1
  1506.  *         f   5   0   0   0   0   0   0
  1507.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  1508.  *       4   8   0   0   0   0   0   0
  1509.  */
  1510.  
  1511. #define POLY 0x48000000L    /* 31-bit polynomial (avoids sign problems) */
  1512.  
  1513. static long CrcTable[128];
  1514.  
  1515. /*
  1516.  - crcinit - initialize tables for hash function
  1517.  */
  1518. static void
  1519. crcinit()
  1520. {
  1521.     register int i, j;
  1522.     register long sum;
  1523.  
  1524.     for (i = 0; i < 128; ++i) {
  1525.         sum = 0L;
  1526.         for (j = 7 - 1; j >= 0; --j)
  1527.             if (i & (1 << j))
  1528.                 sum ^= POLY >> j;
  1529.         CrcTable[i] = sum;
  1530.     }
  1531.     DEBUG(("crcinit: done\n"));
  1532. }
  1533.  
  1534. /*
  1535.  - hash - Honeyman's nice hashing function
  1536.  */
  1537. static long
  1538. hash(name, size)
  1539. register char *name;
  1540. register int size;
  1541. {
  1542.     register long sum = 0L;
  1543.  
  1544.     while (size--) {
  1545.         sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
  1546.     }
  1547.     DEBUG(("hash: returns (%ld)\n", sum));
  1548.     return(sum);
  1549. }
  1550.  
  1551. /*
  1552.  * case-mapping stuff
  1553.  *
  1554.  * Borrowed from C News, by permission of the authors.  Somewhat modified.
  1555.  *
  1556.  * We exploit the fact that we are dealing only with headers here, and
  1557.  * headers are limited to the ASCII characters by RFC822.  It is barely
  1558.  * possible that we might be dealing with a translation into another
  1559.  * character set, but in particular it's very unlikely for a header
  1560.  * character to be outside -128..255.
  1561.  *
  1562.  * Life would be a whole lot simpler if tolower() could safely and portably
  1563.  * be applied to any char.
  1564.  */
  1565.  
  1566. #define    OFFSET    128        /* avoid trouble with negative chars */
  1567.  
  1568. /* must call casencmp before invoking TOLOW... */
  1569. #define    TOLOW(c)    (cmap[(c)+OFFSET])
  1570.  
  1571. /* ...but the use of it in CISTREQN is safe without the preliminary call (!) */
  1572. /* CISTREQN is an optimised case-insensitive strncmp(a,b,n)==0; n > 0 */
  1573. #define CISTREQN(a, b, n) \
  1574.     (TOLOW((a)[0]) == TOLOW((b)[0]) && casencmp(a, b, n) == 0)
  1575.  
  1576. #define    MAPSIZE    (256+OFFSET)
  1577. static char cmap[MAPSIZE];    /* relies on init to '\0' */
  1578. static int mprimed = 0;        /* has cmap been set up? */
  1579.  
  1580. /*
  1581.  - mapprime - set up case-mapping stuff
  1582.  */
  1583. static void
  1584. mapprime()
  1585. {
  1586.     register char *lp;
  1587.     register char *up;
  1588.     register int c;
  1589.     register int i;
  1590.     static char lower[] = "abcdefghijklmnopqrstuvwxyz";
  1591.     static char upper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  1592.  
  1593.     for (lp = lower, up = upper; *lp != '\0'; lp++, up++) {
  1594.         c = *lp;
  1595.         cmap[c+OFFSET] = c;
  1596.         cmap[*up+OFFSET] = c;
  1597.     }
  1598.     for (i = 0; i < MAPSIZE; i++)
  1599.         if (cmap[i] == '\0')
  1600.             cmap[i] = (char)(i-OFFSET);
  1601.     mprimed = 1;
  1602. }
  1603.  
  1604. /*
  1605.  - casencmp - case-independent strncmp
  1606.  */
  1607. static int            /* < == > 0 */
  1608. casencmp(s1, s2, len)
  1609. char *s1;
  1610. char *s2;
  1611. int len;
  1612. {
  1613.     register char *p1;
  1614.     register char *p2;
  1615.     register int n;
  1616.  
  1617.     if (!mprimed)
  1618.         mapprime();
  1619.  
  1620.     p1 = s1;
  1621.     p2 = s2;
  1622.     n = len;
  1623.     while (--n >= 0 && *p1 != '\0' && TOLOW(*p1) == TOLOW(*p2)) {
  1624.         p1++;
  1625.         p2++;
  1626.     }
  1627.     if (n < 0)
  1628.         return(0);
  1629.  
  1630.     /*
  1631.      * The following case analysis is necessary so that characters
  1632.      * which look negative collate low against normal characters but
  1633.      * high against the end-of-string NUL.
  1634.      */
  1635.     if (*p1 == '\0' && *p2 == '\0')
  1636.         return(0);
  1637.     else if (*p1 == '\0')
  1638.         return(-1);
  1639.     else if (*p2 == '\0')
  1640.         return(1);
  1641.     else
  1642.         return(TOLOW(*p1) - TOLOW(*p2));
  1643. }
  1644.  
  1645. /*
  1646.  - mapcase - do case-mapped copy
  1647.  */
  1648. static char *            /* returns src or dst */
  1649. mapcase(dst, src, siz)
  1650. char *dst;            /* destination, used only if mapping needed */
  1651. char *src;            /* source; src == dst is legal */
  1652. size_t siz;
  1653. {
  1654.     register char *s;
  1655.     register char *d;
  1656.     register char *c;    /* case break */
  1657.     register char *e;    /* end of source */
  1658.  
  1659.  
  1660.     c = cipoint(src, siz);
  1661.     if (c == NULL)
  1662.         return(src);
  1663.  
  1664.     if (!mprimed)
  1665.         mapprime();
  1666.     s = src;
  1667.     e = s + siz;
  1668.     d = dst;
  1669.  
  1670.     while (s < c)
  1671.         *d++ = *s++;
  1672.     while (s < e)
  1673.         *d++ = TOLOW(*s++);
  1674.  
  1675.     return(dst);
  1676. }
  1677.  
  1678. /*
  1679.  - cipoint - where in this message-ID does it become case-insensitive?
  1680.  *
  1681.  * The RFC822 code is not quite complete.  Absolute, total, full RFC822
  1682.  * compliance requires a horrible parsing job, because of the arcane
  1683.  * quoting conventions -- abc"def"ghi is not equivalent to abc"DEF"ghi,
  1684.  * for example.  There are three or four things that might occur in the
  1685.  * domain part of a message-id that are case-sensitive.  They don't seem
  1686.  * to ever occur in real news, thank Cthulhu.  (What?  You were expecting
  1687.  * a merciful and forgiving deity to be invoked in connection with RFC822?
  1688.  * Forget it; none of them would come near it.)
  1689.  */
  1690. static char *            /* pointer into s, or NULL for "nowhere" */
  1691. cipoint(s, siz)
  1692. char *s;
  1693. size_t siz;
  1694. {
  1695.     register char *p;
  1696.     static char post[] = "postmaster";
  1697.     static int plen = sizeof(post)-1;
  1698.  
  1699.     switch (conf.casemap) {
  1700.     case '0':        /* unmapped, sensible */
  1701.         return(NULL);
  1702.         break;
  1703.     case 'C':        /* C News, RFC 822 conformant (approx.) */
  1704.         p = memchr(s, '@', siz);
  1705.         if (p == NULL)            /* no local/domain split */
  1706.             return(NULL);        /* assume all local */
  1707.         else if    (p - (s+1) == plen && CISTREQN(s+1, post, plen)) {
  1708.             /* crazy -- "postmaster" is case-insensitive */
  1709.             return(s);
  1710.         } else
  1711.             return(p);
  1712.         break;
  1713.     case '=':        /* 2.11, neither sensible nor conformant */
  1714.         return(s);    /* all case-insensitive */
  1715.         break;
  1716.     }
  1717.  
  1718.     DEBUG(("cipoint: unknown case mapping `%c'\n", conf.casemap));
  1719.     return(NULL);        /* just leave it alone */
  1720. }
  1721.  
  1722. /*
  1723.  - dbzdebug - control dbz debugging at run time
  1724.  */
  1725. int                /* old value */
  1726. dbzdebug(value)
  1727. int value;
  1728. {
  1729. #ifdef DBZDEBUG
  1730.     register int old = debug;
  1731.  
  1732.     debug = value;
  1733.     return(old);
  1734. #else
  1735.     return(-1);
  1736. #endif
  1737. }
  1738.