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