```   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 {
75:     char **g;
76: }
77: btreenode, *btreeptr;
78:
79: typedef struct innernode {
81:     btreeptr ptr[Maxinner+1]; itemarray iitm;
82: }
83: innernode, *innerptr;
84:
85: typedef struct itexnode {
87:     btreeptr ptr[Maxinner+1]; texitem icitm[Maxinner];
88: }
89: itexnode, *itexptr;
90:
91: typedef struct ilisnode {
93:     btreeptr ptr[Maxinner+1]; lisitem ilitm[Maxinner];
94: }
95: ilisnode, *ilisptr;
96:
97: typedef struct itabnode {
99:     btreeptr ptr[Maxinner+1]; tabitem ititm[Maxinner];
100: }
101: itabnode, *itabptr;
102:
103: typedef struct bottomnode {
105:     itemarray bitm;
106: }
107: bottomnode, *bottomptr;
108:
109: typedef struct btexnode {
111:     texitem bcitm[Maxbottom];
112: }
113: btexnode, *btexptr;
114:
115: typedef struct blisnode {
117:     lisitem blitm[Maxbottom];
118: }
119: blisnode, *blisptr;
120:
121: typedef struct btabnode {
123:     tabitem btitm[Maxbottom];
124: }
125: btabnode, *btabptr;
126:
127: typedef struct rangenode {
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

blisnode defined in line 115; never used
bottomnode defined in line 103; never used
btabnode defined in line 121; never used
btexnode defined in line 109; never used
btrnode defined in line 73; never used
ilisnode defined in line 91; never used
innernode defined in line 79; never used
itabnode defined in line 97; never used
itexnode defined in line 85; never used
onpair defined in line 21; never used
pair defined in line 20; never used
rangenode defined in line 127; never used

#### Defined union's

itm defined in line 22; never used

#### Defined typedef's

blisnode defined in line 119; used 1 times
blisptr defined in line 119; never used
bottomnode defined in line 107; never used
bottomptr defined in line 107; used 1 times
btabnode defined in line 125; used 2 times
btabptr defined in line 125; never used
btexnode defined in line 113; used 1 times
btexptr defined in line 113; used 1 times
btreenode defined in line 77; never used
btreeptr defined in line 77; used 62 times
ilisnode defined in line 95; used 1 times
ilisptr defined in line 95; never used
innernode defined in line 83; never used
innerptr defined in line 83; used 2 times
itabnode defined in line 101; used 2 times
itabptr defined in line 101; never used
item defined in line 26; used 5 times
itemarray defined in line 26; used 2 times
itexnode defined in line 89; used 1 times
itexptr defined in line 89; used 1 times
keysitem defined in line 21; used 1 times
• in line 45
rangenode defined in line 131; used 1 times
rangeptr defined in line 131; used 2 times
tabitem defined in line 20; used 4 times
texitem defined in line 18; used 4 times

#### Defined macros

Biglim defined in line 71; used 1 times
Charval defined in line 28; used 15 times
Crange defined in line 139; used 1 times
Ct defined in line 33; used 11 times
Cw defined in line 42; used 1 times
Ichar defined in line 154; used 7 times
Irange defined in line 138; used 1 times
Keyval defined in line 29; used 28 times
Kt defined in line 36; used 3 times
Kw defined in line 45; used 1 times
Lt defined in line 34; used 5 times
Lw defined in line 43; used 1 times
Lwbchar defined in line 159; used 2 times
Maxbottom defined in line 69; used 12 times
Maxinner defined in line 66; used 15 times
Maxlim defined in line 143; never used
Mininner defined in line 65; used 3 times
Minlim defined in line 142; never used
Sadd2 defined in line 55; never used
Sdecr defined in line 57; never used
Sdiff defined in line 56; never used
SetRangeLim defined in line 144; never used
Sincr defined in line 54; used 1 times
Ssum defined in line 53; used 1 times
Stail defined in line 52; used 3 times
Tt defined in line 35; used 3 times
Tw defined in line 44; used 1 times
Upbchar defined in line 160; used 1 times
reqerr defined in line 12; used 15 times

#### Usage of this include

 Last modified: 1985-08-27 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 3055