home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / pd / sdbm / pair.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-01  |  5.7 KB  |  313 lines

  1. /* @(#)pd/sdbm/pair.c    1.3 8/1/92 20:02:20 */
  2. /*
  3.  * sdbm - ndbm work-alike hashed database library
  4.  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  5.  * author: oz@nexus.yorku.ca
  6.  * status: public domain.
  7.  *
  8.  * page-level routines
  9.  */
  10.  
  11. #ifndef lint
  12. static char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $";
  13. #endif
  14.  
  15. #include "defs.h"
  16. #include "sdbm.h"
  17. #include "tune.h"
  18. #include "pair.h"
  19.  
  20. #ifdef __STDC__
  21. #define P_(p) p
  22. #else
  23. #define P_(p) ()
  24. #endif
  25.  
  26. #define exhash(item)    dbm_hash((item).dptr, (item).dsize)
  27.  
  28. /* 
  29.  * forward 
  30.  */
  31. static int seepair P_((char *, int, char *, int));
  32.  
  33. /*
  34.  * page format:
  35.  *    +------------------------------+
  36.  * ino    | n | keyoff | datoff | keyoff |
  37.  *     +------------+--------+--------+
  38.  *    | datoff | - - - ---->           |
  39.  *    +--------+---------------------+
  40.  *    |     F R E E A R E A       |
  41.  *    +--------------+---------------+
  42.  *    |  <---- - - - | data          |
  43.  *    +--------+-----+----+----------+
  44.  *    |  key   | data     | key      |
  45.  *    +--------+----------+----------+
  46.  *
  47.  * calculating the offsets for free area:  if the number
  48.  * of entries (ino[0]) is zero, the offset to the END of
  49.  * the free area is the block size. Otherwise, it is the
  50.  * nth (ino[ino[0]]) entry's offset.
  51.  */
  52.  
  53. int
  54. fitpair(pag, need)
  55. char *pag;
  56. int need;
  57. {
  58.     register int n;
  59.     register int off;
  60.     register int free;
  61.     register short *ino = (short *) pag;
  62.  
  63.     off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  64.     free = off - (n + 1) * sizeof(short);
  65.     need += 2 * sizeof(short);
  66.  
  67.     debug(("free %d need %d\n", free, need));
  68.  
  69.     return need <= free;
  70. }
  71.  
  72. void
  73. putpair(pag, key, val)
  74. char *pag;
  75. datum key;
  76. datum val;
  77. {
  78.     register int n;
  79.     register int off;
  80.     register short *ino = (short *) pag;
  81.  
  82.     off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  83. /*
  84.  * enter the key first
  85.  */
  86.     off -= key.dsize;
  87.     (void) memcpy(pag + off, key.dptr, key.dsize);
  88.     ino[n + 1] = off;
  89. /*
  90.  * now the data
  91.  */
  92.     off -= val.dsize;
  93.     (void) memcpy(pag + off, val.dptr, val.dsize);
  94.     ino[n + 2] = off;
  95. /*
  96.  * adjust item count
  97.  */
  98.     ino[0] += 2;
  99. }
  100.  
  101. datum
  102. getpair(pag, key)
  103. char *pag;
  104. datum key;
  105. {
  106.     register int i;
  107.     register int n;
  108.     datum val;
  109.     register short *ino = (short *) pag;
  110.  
  111.     if ((n = ino[0]) == 0)
  112.         return nullitem;
  113.  
  114.     if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
  115.         return nullitem;
  116.  
  117.     val.dptr = pag + ino[i + 1];
  118.     val.dsize = ino[i] - ino[i + 1];
  119.     return val;
  120. }
  121.  
  122. #ifdef SEEDUPS
  123. int
  124. duppair(pag, key)
  125. char *pag;
  126. datum key;
  127. {
  128.     register short *ino = (short *) pag;
  129.     return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
  130. }
  131. #endif
  132.  
  133. datum
  134. getnkey(pag, num)
  135. char *pag;
  136. int num;
  137. {
  138.     datum key;
  139.     register int off;
  140.     register short *ino = (short *) pag;
  141.  
  142.     num = num * 2 - 1;
  143.     if (ino[0] == 0 || num > ino[0])
  144.         return nullitem;
  145.  
  146.     off = (num > 1) ? ino[num - 1] : PBLKSIZ;
  147.  
  148.     key.dptr = pag + ino[num];
  149.     key.dsize = off - ino[num];
  150.  
  151.     return key;
  152. }
  153.  
  154. int
  155. delpair(pag, key)
  156. char *pag;
  157. datum key;
  158. {
  159.     register int n;
  160.     register int i;
  161.     register short *ino = (short *) pag;
  162.  
  163.     if ((n = ino[0]) == 0)
  164.         return 0;
  165.  
  166.     if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
  167.         return 0;
  168. /*
  169.  * found the key. if it is the last entry
  170.  * [i.e. i == n - 1] we just adjust the entry count.
  171.  * hard case: move all data down onto the deleted pair,
  172.  * shift offsets onto deleted offsets, and adjust them.
  173.  * [note: 0 < i < n]
  174.  */
  175.     if (i < n - 1) {
  176.         register int m;
  177.         register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
  178.         register char *src = pag + ino[i + 1];
  179.         register int   zoo = dst - src;
  180.  
  181.         debug(("free-up %d ", zoo));
  182. /*
  183.  * shift data/keys down
  184.  */
  185.         m = ino[i + 1] - ino[n];
  186. #ifdef DUFF
  187. #define MOVB     *--dst = *--src
  188.  
  189.         if (m > 0) {
  190.             register int loop = (m + 8 - 1) >> 3;
  191.  
  192.             switch (m & (8 - 1)) {
  193.             case 0:    do {
  194.                 MOVB;    case 7:    MOVB;
  195.             case 6:    MOVB;    case 5:    MOVB;
  196.             case 4:    MOVB;    case 3:    MOVB;
  197.             case 2:    MOVB;    case 1:    MOVB;
  198.                 } while (--loop);
  199.             }
  200.         }
  201. #else
  202. #if (defined (HAVE_MEMMOVE) || defined(ANSI_C)) && !defined(NO_HAVE_MEMMOVE)
  203.         memmove(dst, src, m);
  204. #else
  205.         while (m--)
  206.             *--dst = *--src;
  207. #endif
  208. #endif
  209. /*
  210.  * adjust offset index up
  211.  */
  212.         while (i < n - 1) {
  213.             ino[i] = ino[i + 2] + zoo;
  214.             i++;
  215.         }
  216.     }
  217.     ino[0] -= 2;
  218.     return 1;
  219. }
  220.  
  221. /*
  222.  * search for the key in the page.
  223.  * return offset index in the range 0 < i < n.
  224.  * return 0 if not found.
  225.  */
  226. static int
  227. seepair(pag, n, key, siz)
  228. char *pag;
  229. register int n;
  230. register char *key;
  231. register int siz;
  232. {
  233.     register int i;
  234.     register int off = PBLKSIZ;
  235.     register short *ino = (short *) pag;
  236.  
  237.     for (i = 1; i < n; i += 2) {
  238.         if (siz == off - ino[i] &&
  239.             memcmp(key, pag + ino[i], siz) == 0)
  240.             return i;
  241.         off = ino[i + 1];
  242.     }
  243.     return 0;
  244. }
  245.  
  246. void
  247. splpage(pag, new, sbit)
  248. char *pag;
  249. char *new;
  250. long sbit;
  251. {
  252.     datum key;
  253.     datum val;
  254.  
  255.     register int n;
  256.     register int off = PBLKSIZ;
  257.     char cur[PBLKSIZ];
  258.     register short *ino = (short *) cur;
  259.  
  260.     (void) memcpy(cur, pag, PBLKSIZ);
  261.     (void) bzero(pag, PBLKSIZ);
  262.     (void) bzero(new, PBLKSIZ);
  263.  
  264.     n = ino[0];
  265.     for (ino++; n > 0; ino += 2) {
  266.         key.dptr = cur + ino[0]; 
  267.         key.dsize = off - ino[0];
  268.         val.dptr = cur + ino[1];
  269.         val.dsize = ino[0] - ino[1];
  270. /*
  271.  * select the page pointer (by looking at sbit) and insert
  272.  */
  273.         (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
  274.  
  275.         off = ino[1];
  276.         n -= 2;
  277.     }
  278.  
  279.     debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
  280.            ((short *) new)[0] / 2,
  281.            ((short *) pag)[0] / 2));
  282. }
  283.  
  284. /*
  285.  * check page sanity: 
  286.  * number of entries should be something
  287.  * reasonable, and all offsets in the index should be in order.
  288.  * this could be made more rigorous.
  289.  */
  290. int
  291. chkpage(pag)
  292. char *pag;
  293. {
  294.     register int n;
  295.     register int off;
  296.     register short *ino = (short *) pag;
  297.  
  298.     if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short)))
  299.         return 0;
  300.  
  301.     if (n > 0) {
  302.         off = PBLKSIZ;
  303.         for (ino++; n > 0; ino += 2) {
  304.             if (ino[0] > off || ino[1] > off ||
  305.                 ino[1] > ino[0])
  306.                 return 0;
  307.             off = ino[1];
  308.             n -= 2;
  309.         }
  310.     }
  311.     return 1;
  312. }
  313.