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