home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / c / cbase.zoo / btree101.zoo / btree_.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-20  |  4.8 KB  |  158 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)btree_.h    1.4 - 90/06/20" */
  5.  
  6. /*man---------------------------------------------------------------------------
  7. NAME
  8.      btree_.h - private header file for btree library
  9.  
  10. SYNOPSIS
  11.      #include "btree_.h"
  12.  
  13. DESCRIPTION
  14.      This is a private header file included by the btree library
  15.      modules.  It contains function declarations and macros for
  16.      internal use by the btree library.
  17.  
  18. ------------------------------------------------------------------------------*/
  19. #ifndef BTREE_H_    /* prevent multiple includes */
  20. #define BTREE_H_
  21.  
  22. /*#define DEBUG        /* switch to enable debugging for btree library */
  23.  
  24. #include <bool.h>
  25. /*#include <string.h>*/
  26. #include "btree.h"
  27.  
  28. /* type definitions */
  29. typedef struct {        /* (key, child) tuple */
  30.     void *keyp;        /* pointer to single key */
  31.     bpos_t child;        /* child link */
  32. } bttpl_t;
  33.  
  34. /* tables */
  35. extern btree_t btb[BTOPEN_MAX];    /* btree control structure table declaration */
  36.  
  37. /* bthdr_t bit flags */
  38. #define BTHMOD          (01)    /* btree file being modified */
  39.  
  40. /* btree_t bit flags */
  41. #define BTOPEN          (03)    /* open status bits */
  42. #define BTREAD          (01)    /* btree is open for reading */
  43. #define BTWRITE          (02)    /* btree is open for writing */
  44. #define BTLOCKS         (030)    /* lock status bits */
  45. #define BTRDLCK         (010)    /* btree is read locked */
  46. #define BTWRLCK         (020)    /* btree is write locked */
  47. #define BTERR        (0100)    /* error has occurred on this btree */
  48.  
  49. /* function declarations */
  50. #ifdef AC_PROTO
  51. int        bt_alloc(btree_t *btp);
  52. void        bt_free(btree_t *btp);
  53. bool        bt_fvalid(size_t keysize, int fldc, const btfield_t fldv[]);
  54. int        bt_grow(btree_t *btp, const bttpl_t *bttplp);
  55. int        bt_search(btree_t *btp, const void *buf);
  56. int        bt_shrink(btree_t *btp, const bpos_t *newrootp);
  57. bool        bt_valid(btree_t *btp);
  58.  
  59. btnode_t *    bt_ndalloc(btree_t *btp);
  60. int        bt_ndcopy(btree_t *btp, btnode_t *tbtnp, const btnode_t *sbtnp);
  61. int        bt_nddelkey(btree_t *btp, btnode_t *btnp, int kn);
  62. void        bt_ndfree(btnode_t *btnp);
  63. int        bt_ndfuse(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp,
  64.             btnode_t *pbtnp, int pkn);
  65. int        bt_ndget(btree_t *btp, bpos_t node, btnode_t *btnp);
  66. void        bt_ndinit(btree_t *btp, btnode_t *btnp);
  67. int        bt_ndinskey(btree_t *btp, btnode_t *btnp, int kn,
  68.             const bttpl_t *bttplp);
  69. int        bt_ndput(btree_t *btp, bpos_t node, const btnode_t *btnp);
  70. int        bt_ndsearch(btree_t *btp, const btnode_t *btnp, const void *buf,
  71.             int *knp);
  72. int        bt_ndshift(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp,
  73.             btnode_t *pbtnp, int pkn, bpos_t pnode);
  74. int        bt_ndsplit(btree_t *btp, bpos_t node, btnode_t *btnp,
  75.             btnode_t *rbtnp, bttpl_t *bttplp);
  76.  
  77. int        bt_kymvleft(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp,
  78.             int nm);
  79. int        bt_kymvright(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp,
  80.             int nm);
  81. int        bt_kyread(btree_t *btp, const btnode_t *btnp, int kn,
  82.             bttpl_t *bttplp);
  83. int        bt_kyshift(btree_t *btp, btnode_t *btnp, int kn, int ns);
  84. int        bt_kywrite(btree_t *btp, btnode_t *btnp, int kn,
  85.             const bttpl_t *bttplp);
  86.  
  87. void        bt_dgbtp(btree_t *btp, FILE *fp);
  88. int        bt_dgbtree(btree_t *btp, bpos_t node, FILE *fp);
  89. void        bt_dgnode(btree_t *btp, btnode_t *btnp, FILE *fp);
  90. void        bt_dgtuple(btree_t *btp, bttpl_t *bttplp, FILE *fp);
  91. #else
  92. int        bt_alloc();
  93. void        bt_free();
  94. bool        bt_fvalid();
  95. int        bt_grow();
  96. int        bt_search();
  97. int        bt_shrink();
  98. bool        bt_valid();
  99. btnode_t *    bt_ndalloc();
  100. int        bt_ndcopy();
  101. int        bt_nddelkey();
  102. void        bt_ndfree();
  103. int        bt_ndfuse();
  104. int        bt_ndget();
  105. void        bt_ndinit();
  106. int        bt_ndinskey();
  107. int        bt_ndput();
  108. int        bt_ndsearch();
  109. int        bt_ndshift();
  110. int        bt_ndsplit();
  111. int        bt_kymvleft();
  112. int        bt_kymvright();
  113. int        bt_kyread();
  114. int        bt_kyshift();
  115. int        bt_kywrite();
  116. void        bt_dgbtp();
  117. int        bt_dgbtree();
  118. void        bt_dgnode();
  119. void        bt_dgtuple();
  120. #endif    /* #ifdef AC_PROTO */
  121.  
  122. /* macros */
  123. #define bt_blksize(BTP) ((size_t)(                    \
  124.     offsetof(btnode_t, keyv) +                    \
  125.     ((BTP)->bthdr.m - 1) * (BTP)->bthdr.keysize +            \
  126.     (BTP)->bthdr.m * sizeof(bpos_t)                    \
  127. ))
  128. #define    bt_ndleaf(BTNP)    (*bt_kychildp(BTNP, 0) == NIL)
  129. #define    bt_ndmax(BTP)    ((int)((BTP)->bthdr.m - 1))
  130. #define    bt_ndmin(BTP)    ((int)((((BTP)->bthdr.m + 1) / 2) - 1))
  131. #define bt_kychildp(BTNP, N) ((bpos_t *)(                \
  132.             (char *)(BTNP)->childv +            \
  133.             (size_t)(N) * sizeof(bpos_t)            \
  134. ))
  135. #define bt_kykeyp(BTP, BTNP, N) ((void *)(                \
  136.             (char *)(BTNP)->keyv +                \
  137.             ((size_t)(N) - 1) * (BTP)->bthdr.keysize    \
  138. ))
  139. #define bt_kykfp(BTP, BTNP, N, F) ((void *)(                \
  140.             (char *)bt_kykeyp((BTP), (BTNP), (N)) +        \
  141.             (BTP)->fldv[(F)].offset                \
  142. ))
  143.  
  144. /* btree open types */
  145. #define BT_READ        ("r")
  146. #define BT_RDWR        ("r+")
  147.  
  148. #ifdef DEBUG
  149. #define    BTEPRINT {                            \
  150.     fprintf(stderr, "btree error line %d of %s.  errno = %d.\n",    \
  151.         __LINE__, __FILE__, errno);                \
  152. }
  153. #else
  154. #define BTEPRINT
  155. #endif
  156.  
  157. #endif        /* #ifndef BTREE_H_ */
  158.