home *** CD-ROM | disk | FTP | other *** search
/ Frostbyte's 1980s DOS Shareware Collection / floppyshareware.zip / floppyshareware / DOOG / CBASE09.ZIP / BTREE.ZIP / BTREE.H < prev    next >
Text File  |  1989-08-31  |  5KB  |  141 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "btree.h    1.1 - 89/07/03" */
  5.  
  6. /*man---------------------------------------------------------------------------
  7. NAME
  8.      btree - B-tree file management library
  9.  
  10. SYNOPSIS
  11.      #include <btree.h>
  12.  
  13. DESCRIPTION
  14.      The btree library consists of a set of routines for the creation and
  15.      manipulation of file-based B-tree structures.  The B+-tree variety
  16.      of B-tree is used to provide efficient sequential as well as random
  17.      access.
  18.  
  19.      btree uses the blkio library for file access and buffering.  Therefore
  20.      bexit should be used in place of exit when using btree.
  21.  
  22. SEE ALSO
  23.      btclose, btcreate, btcursor, btdelcur, btdelete, btfirst, btgetcur,
  24.      btgetk, btgetlck, btinsert, btkeycnt, btkeysize, btlast, btlock,
  25.      btnext, btopen, btprev, btsearch, btsetbuf, btsetcur, btsetvbuf,
  26.      btsync.
  27.  
  28. ------------------------------------------------------------------------------*/
  29. #ifndef BTREE_H            /* prevent multiple includes */
  30. #define BTREE_H
  31.  
  32. #include <blkio.h>
  33. /* #include <stddef.h> */
  34.  
  35. /* btree constants */
  36. #define BTOPEN_MAX    BOPEN_MAX    /* max # btrees open at once */
  37. #define BTBUFCNT    ((size_t)4)    /* default # of nodes to buffer */
  38.  
  39. /* macro to calculate buffer size needed by a btree */
  40. #define    BTBUFSIZ(M, KEYSIZE, BUFCNT)    (sizeof(bthdr_t) + ((BUFCNT) *    \
  41.                     (offsetof(btnode_t, key_p) +    \
  42.             (((M) - 1) * (KEYSIZE)) + ((M) * sizeof(bpos_t)))))
  43.  
  44. /* btree type definitions */
  45. typedef struct {        /* btree position */
  46.     bpos_t node;        /* block number of node */
  47.     size_t key;        /* key number in node */
  48. } btpos_t;
  49.  
  50. typedef struct {        /* btree node */
  51.     size_t n;        /* number of keys in node  (n <= (m - 1)) */
  52.     bpos_t lsib;        /* block number of left sibling */
  53.     bpos_t rsib;        /* block number of right sibling */
  54.     void *key_p;        /* pointer to m keys */
  55.     bpos_t *child_p;    /* pointer to (m + 1) child block numbers */
  56. } btnode_t;
  57.  
  58. typedef struct {        /* (key, child) tuple */
  59.     void *key_p;        /* pointer to one key */
  60.     bpos_t child;        /* child block number */
  61. } bttuple_t;
  62.  
  63. typedef struct {        /* btree file header */
  64.     bpos_t flh;        /* block number of free list head */
  65.     size_t m;        /* m-way search tree */
  66.     size_t keysize;        /* size of keys */
  67.     int flags;        /* flags */
  68.     bpos_t root;        /* block number of root node */
  69.     bpos_t first;        /* block number of first key */
  70.     bpos_t last;        /* block number of last key */
  71.     size_t keycnt;        /* number of keys currently stored in btree */
  72.     size_t height;        /* current height of tree */
  73. } bthdr_t;
  74.  
  75. typedef struct {        /* btree control structure */
  76.     bthdr_t bthdr;        /* header record */
  77.     BLKFILE *bp;        /* block file */
  78.     int (*cmp_p)();        /* key compare function */
  79.     int flags;        /* status flags */
  80.     btpos_t cbtpos;        /* current btree position */
  81.     btnode_t *cbtnp;    /* current node */
  82.     btpos_t *sp;        /* search path to current position */
  83. } btree_t;
  84. extern btree_t btb[BTOPEN_MAX];    /* btree control structure table declaration */
  85.  
  86. /* bthdr flag bits */
  87. #define BTHMOD          (01)    /* btree file being modified */
  88.  
  89. /* btb flag bits */
  90. #define BTOPEN          (03)    /* open status bits */
  91. #define BTREAD          (01)    /* btree is open for reading */
  92. #define BTWRITE          (02)    /* btree is open for writing */
  93. #define BTLOCKS         (030)    /* lock status bits */
  94. #define BTRDLCK         (010)    /* btree is read locked */
  95. #define BTWRLCK         (020)    /* btree is write locked */
  96. #define BTERR        (0100)    /* error has occurred on this btree */
  97.  
  98. /* function declarations */
  99. int        btclose(/* btree_t *btp */);
  100. int        btcreate(/* char *filename, size_t m, size_t keysize */);
  101. #define        btcursor(BTP)    ((void *)(((BTP)->cbtpos.node == 0) ? NULL : ~NULL))
  102. int        btdelcur(/* btree_t *btp, void *buf */);
  103. int        btdelete(/* btree_t *btp, void *buf */);
  104. int        btfirst(/* btree_t *btp */);
  105. int        btgetcur(/* btree_t *btp, btpos_t *btpos_p);
  106. int        btgetk(/* btree_t *btp, void *buf */);
  107. int        btgetlck(/* btree_t *btp */);
  108. int        btinsert(/* btree_t *btp, void *buf */);
  109. #define        btkeycnt(BTP)    ((BTP)->bthdr.keycnt)
  110. #define        btkeysize(BTP)    ((BTP)->bthdr.keysize)
  111. int        btlast(/* btree_t *btp */);
  112. int        btlock(/* btree_t *btp, int l_type */);
  113. int        btnext(/* btree_t *btp */);
  114. btree_t *    btopen(/* char *filename, char *type, int (*cmp_p)() */);
  115. int        btprev(/* btree_t *btp */);
  116. int        btsearch(/* btree_t *btp, void *buf */);
  117. int        btsetbuf(/* btree_t *btp, void *buf */);
  118. int        btsetcur(/* btree_t *btp, btpos_t *btpos_p */);
  119. int        btsetvbuf(/* btree_t *btp, void *buf, size_t bufcnt */);
  120. int        btsync(/* btree_t *btp */);
  121.  
  122. /* btree lock types */
  123. #define BT_UNLCK    (0)    /* unlock */
  124. #define BT_RDLCK    (1)    /* read lock */
  125. #define BT_WRLCK    (2)    /* write lock */
  126. #define BT_RDLKW    (3)    /* read lock, wait */
  127. #define BT_WRLKW    (4)    /* write lock, wait */
  128.  
  129. /* btree error codes */
  130. #define BTEOS        (-100)    /* start of btree error code domain */
  131. #define BTEMFILE    (BTEOS - 1)    /* too many open btrees */
  132. #define BTECORRUPT    (BTEOS - 2)    /* btree is corrupt */
  133. #define BTENOPEN    (BTEOS - 3)    /* btree is not open */
  134. #define BTENBUF        (BTEOS - 4)    /* buffering is off */
  135. #define BTELOCK        (BTEOS - 5)    /* incorrect lock type */
  136. #define BTENKEY        (BTEOS - 6)    /* no key */
  137. #define BTEDUPKEY    (BTEOS - 7)    /* duplicate key */
  138. #define BTEPANIC    (BTEOS - 10)    /* internal btree error */
  139.  
  140. #endif        /* #ifndef BTREE_H */
  141.