home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / gnu / libg++-2.6.2.lha / libg++-2.6.2 / libio / dbz / dbz.c < prev    next >
C/C++ Source or Header  |  1993-08-20  |  44KB  |  1,767 lines
  1. /*
  2.  
  3. dbz.c  V3.2
  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 on it
  7. 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, especially
  21. if the incore facility is used.
  22.  
  23. */
  24.  
  25. #include <stdio.h>
  26. #include <sys/types.h>
  27. #include <string.h>
  28. #include <ctype.h>
  29. #include <errno.h>
  30. #ifndef __STDC__
  31. extern int errno;
  32. #endif
  33. #include <dbz.h>
  34.  
  35. /*
  36.  * #ifdef index.  "LIA" = "leave it alone unless you know what you're doing".
  37.  *
  38.  * FUNNYSEEKS    SEEK_SET is not 0, get it from <unistd.h>
  39.  * INDEX_SIZE    backward compatibility with old dbz; avoid using this
  40.  * NMEMORY    number of days of memory for use in sizing new table (LIA)
  41.  * INCORE    backward compatibility with old dbz; use dbzincore() instead
  42.  * DBZDEBUG    enable debugging
  43.  * DEFSIZE    default table size (not as critical as in old dbz)
  44.  * OLDBNEWS    default case mapping as in old B News; set NOBUFFER
  45.  * BNEWS    default case mapping as in current B News; set NOBUFFER
  46.  * DEFCASE    default case-map algorithm selector
  47.  * NOTAGS    fseek offsets are strange, do not do tagging (see below)
  48.  * NPAGBUF    size of .pag buffer, in longs (LIA)
  49.  * SHISTBUF    size of ASCII-file buffer, in bytes (LIA)
  50.  * MAXRUN    length of run which shifts to next table (see below) (LIA)
  51.  * OVERFLOW    long-int arithmetic overflow must be avoided, will trap
  52.  * NOBUFFER    do not buffer hash-table i/o, B News locking is defective
  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 2/3 full, that being
  90.  * slightly before the point where performance starts to degrade.  (It is
  91.  * desirable to be a bit conservative because the overflow strategy tends
  92.  * to produce files with holes in them, which is a nuisance.)
  93.  */
  94.  
  95. /*
  96.  * The following is for backward compatibility.
  97.  */
  98. #ifdef INDEX_SIZE
  99. #define    DEFSIZE    INDEX_SIZE
  100. #endif
  101.  
  102. /*
  103.  * ANSI C says an offset into a file is a long, not an off_t, for some
  104.  * reason.  This actually does simplify life a bit, but it's still nice
  105.  * to have a distinctive name for it.  Beware, this is just for readability,
  106.  * don't try to change this.
  107.  */
  108. #define    of_t    long
  109. #define    SOF    (sizeof(of_t))
  110.  
  111. /*
  112.  * We assume that unused areas of a binary file are zeros, and that the
  113.  * bit pattern of `(of_t)0' is all zeros.  The alternative is rather
  114.  * painful file initialization.  Note that okayvalue(), if OVERFLOW is
  115.  * defined, knows what value of an offset would cause overflow.
  116.  */
  117. #define    VACANT        ((of_t)0)
  118. #define    BIAS(o)        ((o)+1)        /* make any valid of_t non-VACANT */
  119. #define    UNBIAS(o)    ((o)-1)        /* reverse BIAS() effect */
  120.  
  121. /*
  122.  * In a Unix implementation, or indeed any in which an of_t is a byte
  123.  * count, there are a bunch of high bits free in an of_t.  There is a
  124.  * use for them.  Checking a possible hit by looking it up in the base
  125.  * file is relatively expensive, and the cost can be dramatically reduced
  126.  * by using some of those high bits to tag the value with a few more bits
  127.  * of the key's hash.  This detects most false hits without the overhead of
  128.  * seek+read+strcmp.  We use the top bit to indicate whether the value is
  129.  * tagged or not, and don't tag a value which is using the tag bits itself.
  130.  * We're in trouble if the of_t representation wants to use the top bit.
  131.  * The actual bitmasks and offset come from the configuration stuff,
  132.  * which permits fiddling with them as necessary, and also suppressing
  133.  * them completely (by defining the masks to 0).  We build pre-shifted
  134.  * versions of the masks for efficiency.
  135.  */
  136. static of_t tagbits;        /* pre-shifted tag mask */
  137. static of_t taghere;        /* pre-shifted tag-enable bit */
  138. static of_t tagboth;        /* tagbits|taghere */
  139. #define    HASTAG(o)    ((o)&taghere)
  140. #define    TAG(o)        ((o)&tagbits)
  141. #define    NOTAG(o)    ((o)&~tagboth)
  142. #define    CANTAG(o)    (((o)&tagboth) == 0)
  143. #define    MKTAG(v)    (((v)<<conf.tagshift)&tagbits)
  144.  
  145. /*
  146.  * A new, from-scratch database, not built as a rebuild of an old one,
  147.  * needs to know table size, casemap algorithm, and tagging.  Normally
  148.  * the user supplies this info, but there have to be defaults.
  149.  */
  150. #ifndef DEFSIZE
  151. #define    DEFSIZE    120011        /* 300007 might be better */
  152. #endif
  153. #ifdef OLDBNEWS
  154. #define    DEFCASE    '0'        /* B2.10 -- no mapping */
  155. #define    NOBUFFER        /* B News locking is defective */
  156. #endif
  157. #ifdef BNEWS
  158. #define    DEFCASE    '='        /* B2.11 -- all mapped */
  159. #define    NOBUFFER        /* B News locking is defective */
  160. #endif
  161. #ifndef DEFCASE            /* C News compatibility is the default */
  162. #define    DEFCASE    'C'        /* C News -- RFC822 mapping */
  163. #endif
  164. #ifndef NOTAGS
  165. #define    TAGENB    0x80        /* tag enable is top bit, tag is next 7 */
  166. #define    TAGMASK    0x7f
  167. #define    TAGSHIFT    24
  168. #else
  169. #define    TAGENB    0        /* no tags */
  170. #define    TAGMASK    0
  171. #define    TAGSHIFT    0
  172. #endif
  173.  
  174. /*
  175.  * We read configuration info from the .dir file into this structure,
  176.  * so we can avoid wired-in assumptions for an existing database.
  177.  *
  178.  * Among the info is a record of recent peak usages, so that a new table
  179.  * size can be chosen intelligently when rebuilding.  10 is a good
  180.  * number of usages to keep, since news displays marked fluctuations
  181.  * in volume on a 7-day cycle.
  182.  */
  183. struct dbzconfig {
  184.     int olddbz;        /* .dir file empty but .pag not? */
  185.     of_t tsize;        /* table size */
  186. #    ifndef NMEMORY
  187. #    define    NMEMORY    10    /* # days of use info to remember */
  188. #    endif
  189. #    define    NUSEDS    (1+NMEMORY)
  190.     of_t used[NUSEDS];    /* entries used today, yesterday, ... */
  191.     int valuesize;        /* size of table values, == SOF */
  192.     int bytemap[SOF];    /* byte-order map */
  193.     char casemap;        /* case-mapping algorithm (see cipoint()) */
  194.     char fieldsep;        /* field separator in base file, if any */
  195.     of_t tagenb;        /* unshifted tag-enable bit */
  196.     of_t tagmask;        /* unshifted tag mask */
  197.     int tagshift;        /* shift count for tagmask and tagenb */
  198. };
  199. static struct dbzconfig conf;
  200. static int getconf();
  201. static long getno();
  202. static int putconf();
  203. static void mybytemap();
  204. static of_t bytemap();
  205.  
  206. /* 
  207.  * For a program that makes many, many references to the database, it
  208.  * is a large performance win to keep the table in core, if it will fit.
  209.  * Note that this does hurt robustness in the event of crashes, and
  210.  * dbmclose() *must* be called to flush the in-core database to disk.
  211.  * The code is prepar