![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to b1btr.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / contrib / B / src / bint|
Return to b1btr.h CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / B / src / bint |
1.1 root 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
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.