2.11BSD#431 - /usr/src/new/PORT/B/src/bint/b1btr.h

   1: /* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1985. */
   2: 
   3: /*
   4:   $Header: b1btr.h,v 1.4 85/08/22 16:41:40 timo Exp $
   5: */
   6: 
   7: /* Private definitions for the b-tree module */
   8: 
   9: #ifndef INTEGRATION
  10: 
  11: extern bool comp_ok;
  12: #define reqerr(s) error(s)
  13: 
  14: /*********************************************************************/
  15: /* items
  16: /*********************************************************************/
  17: 
  18: typedef char texitem;
  19: typedef value lisitem;
  20: typedef struct pair {value k, a;} tabitem;
  21: typedef struct onpair {value ka, u;} keysitem;
  22: typedef union itm {
  23:     texitem c;
  24:     lisitem l;
  25:     tabitem t;
  26: } item, *itemarray, *itemptr;
  27: 
  28: #define Charval(pitm) ((pitm)->c)
  29: #define Keyval(pitm) ((pitm)->l)
  30: #define Ascval(pitm) ((pitm)->t.a)
  31: 
  32: /* Xt = itemtype, do not change these, their order is used */
  33: #define Ct (0)
  34: #define Lt (1)
  35: #define Tt (2)
  36: #define Kt (3)
  37: 
  38: /* Itemwidth, used for offset in btreenodes */
  39: typedef char width;
  40: #define Itemwidth(it) (itemwidth[it])
  41: extern char itemwidth[];    /*  uses: */
  42: #define Cw (sizeof(texitem))
  43: #define Lw (sizeof(lisitem))
  44: #define Tw (sizeof(tabitem))
  45: #define Kw (sizeof(keysitem))
  46: 
  47: /*********************************************************************/
  48: /* sizes of btrees
  49: /*********************************************************************/
  50: 
  51: #define Bigsize (-1)
  52: #define Stail(r,s) ((r) > Maxint - (s) ? Bigsize : (r)+(s))
  53: #define Ssum(r,s)  ((r) EQ Bigsize || (s) EQ Bigsize ? Bigsize : Stail(r,s))
  54: #define Sincr(r)   ((r) EQ Bigsize ? Bigsize : Stail(r,1))
  55: #define Sadd2(r)   ((r) EQ Bigsize ? Bigsize : Stail(r,2))
  56: #define Sdiff(r,s) ((r) EQ Bigsize || (s) EQ Bigsize ? Bigsize : (r)-(s))
  57: #define Sdecr(r)   ((r) EQ Bigsize ? Bigsize : (r)-(1))
  58: value treesize();   /* btreeptr pnode */
  59: 
  60: /*********************************************************************/
  61: /* (A,B)-btrees
  62: /*********************************************************************/
  63: 
  64: /* innernodes: using A=6 B=12 */
  65: #define Mininner 5      /* A - 1 */
  66: #define Maxinner 11             /* B - 1 */
  67: /* bottomnodes */
  68: #define Minbottom 11
  69: #define Maxbottom 22
  70: /* rangenodes */
  71: #define Biglim      (Maxbottom+1)
  72: 
  73: typedef struct btrnode {
  74:     HEADER; int size;
  75:     char **g;
  76: }
  77: btreenode, *btreeptr;
  78: 
  79: typedef struct innernode {
  80:     HEADER; int size;
  81:     btreeptr ptr[Maxinner+1]; itemarray iitm;
  82: }
  83: innernode, *innerptr;
  84: 
  85: typedef struct itexnode {
  86:     HEADER; int size;
  87:     btreeptr ptr[Maxinner+1]; texitem icitm[Maxinner];
  88: }
  89: itexnode, *itexptr;
  90: 
  91: typedef struct ilisnode {
  92:     HEADER; int size;
  93:     btreeptr ptr[Maxinner+1]; lisitem ilitm[Maxinner];
  94: }
  95: ilisnode, *ilisptr;
  96: 
  97: typedef struct itabnode {
  98:     HEADER; int size;
  99:     btreeptr ptr[Maxinner+1]; tabitem ititm[Maxinner];
 100: }
 101: itabnode, *itabptr;
 102: 
 103: typedef struct bottomnode {
 104:     HEADER; int size;
 105:     itemarray bitm;
 106: }
 107: bottomnode, *bottomptr;
 108: 
 109: typedef struct btexnode {
 110:     HEADER; int size;
 111:     texitem bcitm[Maxbottom];
 112: }
 113: btexnode, *btexptr;
 114: 
 115: typedef struct blisnode {
 116:     HEADER; int size;
 117:     lisitem blitm[Maxbottom];
 118: }
 119: blisnode, *blisptr;
 120: 
 121: typedef struct btabnode {
 122:     HEADER; int size;
 123:     tabitem btitm[Maxbottom];
 124: }
 125: btabnode, *btabptr;
 126: 
 127: typedef struct rangenode {
 128:     HEADER; int size;
 129:     lisitem lwb, upb;
 130: }
 131: rangenode, *rangeptr;
 132: 
 133: #define Bnil ((btreeptr) 0)
 134: 
 135: #define Flag(pnode) ((pnode)->type)
 136: #define Inner   'i'
 137: #define Bottom  'b'
 138: #define Irange  '.'
 139: #define Crange  '\''
 140: 
 141: #define Lim(pnode)  ((pnode)->len)
 142: #define Minlim(pnode)   (Flag(pnode) EQ Inner ? Mininner : Minbottom)
 143: #define Maxlim(pnode)   (Flag(pnode) EQ Inner ? Maxinner : Maxbottom)
 144: #define SetRangeLim(pnode) (Size(pnode) EQ Bigsize || Size(pnode) > Maxbottom\
 145:                 ? Biglim : Size(pnode))
 146: 
 147: #define Size(pnode) ((pnode)->size)
 148: 
 149: #define Ptr(pnode,l)    (((innerptr) (pnode))->ptr[l])
 150: /* pointer to item in innernode: */
 151: #define Piitm(pnode,l,w) ((itemptr) (((char*)&(((innerptr) (pnode))->iitm)) + ((l)*(w))))
 152: /* pointer to item in bottomnode: */
 153: #define Pbitm(pnode,l,w) ((itemptr) (((char*)&(((bottomptr) (pnode))->bitm)) + ((l)*(w))))
 154: #define Ichar(pnode,l)  (((itexptr) (pnode))->icitm[l])
 155: #define Bchar(pnode,l)  (((btexptr) (pnode))->bcitm[l])
 156: 
 157: #define Lwbval(pnode)   (((rangeptr) (pnode))->lwb)
 158: #define Upbval(pnode)   (((rangeptr) (pnode))->upb)
 159: #define Lwbchar(pnode)  (Bchar(Root(Lwbval(pnode)), 0))
 160: #define Upbchar(pnode)  (Bchar(Root(Upbval(pnode)), 0))
 161: 
 162: #define Maxheight 20        /* should be some function of B */
 163: 
 164: /* Procedure merge(); */
 165:     /* btreeptr pleft; itemptr pitm; btreeptr pright; literal it; */
 166: bool rebalance();
 167:     /* btreeptr *pptr1; itemptr pitm; btreeptr pptr2;
 168:        intlet minlim, maxlim; literal it; */
 169: /* Procedure restore_child(); */
 170:     /* btreeptr pparent; intlet ichild, minl, maxl; literal it; */
 171: bool inodeinsert();
 172:     /* btreeptr pnode, *pptr; itemptr pitm; intlet at; literal it; */
 173: bool bnodeinsert();
 174:     /* btreeptr pnode, *pptr; itemptr pitm; intlet at; literal it; */
 175: bool i_search();
 176:     /* btreeptr pnode; value key; intlet *pl; width iw; */
 177: bool b_search();
 178:     /* btreeptr pnode; value key; intlet *pl; width iw; */
 179: 
 180: /*********************************************************************/
 181: /* texts only (mbte.c)
 182: /*********************************************************************/
 183: 
 184: btreeptr trimbtextnode(); /* btreeptr pnode, intlet from,to */
 185: btreeptr trimitextnode(); /* btreeptr pnode, intlet from,to */
 186: bool join_itm();
 187:     /* btreeptr pnode, *pptr; itemptr pitm; bool after */
 188: 
 189: /*********************************************************************/
 190: /* lists only (mbli.c)
 191: /*********************************************************************/
 192: 
 193: btreeptr spawncrangenode(); /* value lwb, upb */
 194: /* Procedure set_size_and_lim(); */     /* btreeptr pnode */
 195: /* PRrocedure ir_to_bottomnode(); */    /* btreeptr *pptr; */
 196: bool ins_itm();
 197:     /* btreeptr *pptr1; itemptr pitm; btreeptr *pptr2; literal it; */
 198: /* Procedure rem_greatest(); */
 199:     /* btreeptr *pptr; itemptr prepl_itm; literal it; */
 200: bool rem_itm();
 201:     /* btreeptr *pptr1; itemptr pitm;
 202:        itemptr p_insitm; btreeptr *pptr2; bool *psplit;
 203:        literal it; */
 204: 
 205: /*********************************************************************/
 206: /* tables only (mbla.c)
 207: /*********************************************************************/
 208: 
 209: bool rpl_itm();
 210:     /* btreeptr *pptr1, *pptr2; itemptr pitm; bool *p_added */
 211: bool del_itm();
 212:     /* btreeptr *pptr1; itemptr pitm */
 213: value assocval();   /* btreeptr pnode; value key; */
 214: bool assocloc();
 215:     /* value **ploc; btreeptr pnode; value key; */
 216: bool u_assoc(); /* btreeptr pnode; value key; */
 217: 
 218: /***************** Texts, lists and tables ********************/
 219: /* Procedure move_itm(); */     /* itemptr pdes, psrc; literal it; */
 220: bool get_th_item(); /* itemptr pitm; value num, v; */
 221: 
 222: #endif !INTEGRATION

Defined struct's

Defined union's

Defined typedef's

Defined macros

Usage of this include