dbz.c
上传用户:minyiyu
上传日期:2018-12-24
资源大小:864k
文件大小:47k
源码类别:

Telnet服务器

开发平台:

Unix_Linux

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