1 /* zzektrbn.f -- translated by f2c (version 19980913).
2 You must link the resulting object file with the libraries:
3 -lf2c -lm (in that order)
4 */
5
6 #include "f2c.h"
7
8 /* Table of constant values */
9
10 static integer c__82 = 82;
11 static integer c__124 = 124;
12
13 /* $Procedure ZZEKTRBN ( EK tree, balance nodes ) */
zzektrbn_(integer * handle,integer * tree,integer * left,integer * right,integer * parent,integer * pkidx)14 /* Subroutine */ int zzektrbn_(integer *handle, integer *tree, integer *left,
15 integer *right, integer *parent, integer *pkidx)
16 {
17 integer root;
18 extern integer zzektrnk_(integer *, integer *, integer *);
19 extern /* Subroutine */ int zzektrrk_(integer *, integer *, integer *,
20 integer *, integer *, integer *, integer *), chkin_(char *,
21 ftnlen);
22 integer schlep;
23 extern /* Subroutine */ int sigerr_(char *, ftnlen), chkout_(char *,
24 ftnlen), setmsg_(char *, ftnlen);
25 integer lnkeys;
26 extern /* Subroutine */ int errint_(char *, integer *, ftnlen);
27 integer rnkeys, sum;
28
29 /* $ Abstract */
30
31 /* Solve overflow in a node by balancing the node */
32 /* with one of its sibling nodes. */
33
34 /* $ Disclaimer */
35
36 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
37 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
38 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
39 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
40 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
41 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
42 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
43 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
44 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
45 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
46
47 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
48 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
49 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
50 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
51 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
52 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
53
54 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
55 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
56 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
57 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
58
59 /* $ Required_Reading */
60
61 /* EK */
62
63 /* $ Keywords */
64
65 /* EK */
66 /* PRIVATE */
67
68 /* $ Declarations */
69 /* $ Disclaimer */
70
71 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
72 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
73 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
74 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
75 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
76 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
77 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
78 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
79 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
80 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
81
82 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
83 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
84 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
85 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
86 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
87 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
88
89 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
90 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
91 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
92 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
93
94
95 /* Include Section: EK Tree Parameters */
96
97 /* ektree.inc Version 3 22-OCT-1995 (NJB) */
98
99
100 /* The parameters in this file define the tree structure */
101 /* used by the EK system. This structure is a variant of the */
102 /* B*-tree structure described in Knuth's book, that is */
103
104 /* Knuth, Donald E. "The Art of Computer Programming, */
105 /* Volume 3/Sorting and Searching" 1973, pp 471-479. */
106
107 /* The trees used in the EK system differ from generic B*-trees */
108 /* primarily in the way keys are treated. Rather than storing */
109 /* unique primary key values in each node, EK trees store integer */
110 /* counts that represent the ordinal position of each data value, */
111 /* counting from the lowest indexed element in the subtree whose */
112 /* root is the node in question. Thus the keys are unique within */
113 /* a node but not across multiple nodes: in fact the Nth key in */
114 /* every leaf node is N. The absolute ordinal position of a data */
115 /* item is defined recursively as the sum of the key of the data item */
116 /* and the absolute ordinal position of the data item in the parent */
117 /* node that immediately precedes all elements of the node in */
118 /* question. This data structure allows EK trees to support lookup */
119 /* of data items based on their ordinal position in a data set. The */
120 /* two prime applications of this capability in the EK system are: */
121
122 /* 1) Using trees to index the records in a table, allowing */
123 /* the Nth record to be located efficiently. */
124
125 /* 2) Using trees to implement order vectors that can be */
126 /* maintained when insertions and deletions are done. */
127
128
129
130 /* Root node */
131
132 /* +--------------------------------------------+ */
133 /* | Tree version code | */
134 /* +--------------------------------------------+ */
135 /* | Number of nodes in tree | */
136 /* +--------------------------------------------+ */
137 /* | Number of keys in tree | */
138 /* +--------------------------------------------+ */
139 /* | Depth of tree | */
140 /* +--------------------------------------------+ */
141 /* | Number of keys in root | */
142 /* +--------------------------------------------+ */
143 /* | Space for n keys, | */
144 /* | | */
145 /* | n = 2 * INT( ( 2*m - 2 )/3 ) | */
146 /* | | */
147 /* | where m is the max number of children per | */
148 /* | node in the child nodes | */
149 /* +--------------------------------------------+ */
150 /* | Space for n+1 child pointers, | */
151 /* | where n is as defined above. | */
152 /* +--------------------------------------------+ */
153 /* | Space for n data pointers, | */
154 /* | where n is as defined above. | */
155 /* +--------------------------------------------+ */
156
157
158 /* Child node */
159
160 /* +--------------------------------------------+ */
161 /* | Number of keys present in node | */
162 /* +--------------------------------------------+ */
163 /* | Space for m-1 keys | */
164 /* +--------------------------------------------+ */
165 /* | Space for m child pointers | */
166 /* +--------------------------------------------+ */
167 /* | Space for m-1 data pointers | */
168 /* +--------------------------------------------+ */
169
170
171
172
173 /* The following parameters give the maximum number of children */
174 /* allowed in the root and child nodes. During insertions, the */
175 /* number of children may overflow by 1. */
176
177
178 /* Maximum number of children allowed in a child node: */
179
180
181 /* Maximum number of keys allowed in a child node: */
182
183
184 /* Minimum number of children allowed in a child node: */
185
186
187 /* Minimum number of keys allowed in a child node: */
188
189
190 /* Maximum number of children allowed in the root node: */
191
192
193 /* Maximum number of keys allowed in the root node: */
194
195
196 /* Minimum number of children allowed in the root node: */
197
198
199
200 /* The following parameters indicate positions of elements in the */
201 /* tree node structures shown above. */
202
203
204 /* The following parameters are for the root node only: */
205
206
207 /* Location of version code: */
208
209
210 /* Version code: */
211
212
213 /* Location of node count: */
214
215
216 /* Location of total key count for the tree: */
217
218
219 /* Location of tree depth: */
220
221
222 /* Location of count of keys in root node: */
223
224
225 /* Base address of keys in the root node: */
226
227
228 /* Base address of child pointers in root node: */
229
230
231 /* Base address of data pointers in the root node (allow room for */
232 /* overflow): */
233
234
235 /* Size of root node: */
236
237
238 /* The following parameters are for child nodes only: */
239
240
241 /* Location of number of keys in node: */
242
243
244 /* Base address of keys in child nodes: */
245
246
247 /* Base address of child pointers in child nodes: */
248
249
250 /* Base address of data pointers in child nodes (allow room */
251 /* for overflow): */
252
253
254 /* Size of child node: */
255
256
257 /* A number of EK tree routines must declare stacks of fixed */
258 /* depth; this depth limit imposes a limit on the maximum depth */
259 /* that an EK tree can have. Because of the large branching */
260 /* factor of EK trees, the depth limit is of no practical */
261 /* importance: The number of keys that can be held in an EK */
262 /* tree of depth N is */
263
264 /* N-1 */
265 /* MXKIDC - 1 */
266 /* MXKIDR * ------------- */
267 /* MXKIDC - 1 */
268
269
270 /* This formula yields a capacity of over 1 billion keys for a */
271 /* tree of depth 6. */
272
273
274 /* End Include Section: EK Tree Parameters */
275
276 /* $ Brief_I/O */
277
278 /* Variable I/O Description */
279 /* -------- --- -------------------------------------------------- */
280 /* HANDLE I File handle. */
281 /* TREE I Root of tree. */
282 /* LEFT I Left node of pair to be balanced. */
283 /* RIGHT I Right node of pair to be balanced. */
284 /* PARENT I Parent node of pair to be balanced. */
285 /* PKIDX I Parent key index. */
286
287 /* $ Detailed_Input */
288
289 /* HANDLE is a file handle of an EK open for write access. */
290
291 /* TREE is the root node number of the tree of interest. */
292
293 /* LEFT, */
294 /* RIGHT are the node numbers of a pair of nodes to */
295 /* be balanced. LEFT and RIGHT must be neighboring */
296 /* subnodes of a common parent. */
297
298 /* PARENT is the node number of the common parent node of */
299 /* nodes LEFT, RIGHT. */
300
301 /* PKIDX is the `parent key index', that is, the */
302 /* node-relative index of the key in the parent that */
303 /* sits between PARENT's child node pointers to */
304 /* nodes LEFT and RIGHT. The key at location PKIDX */
305 /* is the immediate successor of the greatest key in */
306 /* the subnode headed by LEFT. It is the immediate */
307 /* predecessor of the least key in the subnode headed */
308 /* by RIGHT. */
309
310 /* $ Detailed_Output */
311
312 /* None. See $Particulars for a description of the effect of this */
313 /* routine. */
314
315 /* $ Parameters */
316
317 /* None. */
318
319 /* $ Exceptions */
320
321 /* 1) If HANDLE is invalid, the error will be diagnosed by routines */
322 /* called by this routine. The file will not be modified. */
323
324 /* 2) If an I/O error occurs while reading or writing the indicated */
325 /* file, the error will be diagnosed by routines called by this */
326 /* routine. */
327
328 /* 3) If either LEFT or RIGHT are actually the root, the error */
329 /* SPICE(BUG) is signalled. */
330
331 /* 4) If LEFT and RIGHT are not neighboring sibling nodes, the */
332 /* error will be diagnosed by routines called by this routine. */
333
334
335 /* 5) The sum of the key counts in LEFT and RIGHT must be between */
336 /* 2*MNKEYC and 2*MXKEYC; otherwise the key count invariants */
337 /* cannot be satisfied by balancing. If the sum fails to meet */
338 /* this condition, the error SPICE(BUG) is signalled. */
339
340 /* $ Files */
341
342 /* See the EK Required Reading for a discussion of the EK file */
343 /* format. */
344
345 /* $ Particulars */
346
347 /* Insertions into and deletions from EK trees can result in */
348 /* overflows or underflows of keys in nodes affected by these */
349 /* operations. Many times key count invariants can be restored by */
350 /* moving keys from one node into an adjacent sibling node. This */
351 /* maneuver is called `balancing' the nodes. After balancing, the */
352 /* key counts of the affected nodes differ by at most 1. */
353
354 /* The balancing process also affects the parent node of the */
355 /* neighboring children because one key of the parent sits between */
356 /* the children. This `parent key' gets moved into one of the */
357 /* children as keys are shifted. If the shift is to the right, the */
358 /* parent key is the largest key of the shifted set; if the shift */
359 /* is to the left, the parent key is the least of the shifted set. */
360
361 /* When keys are shifted, their data values move along with them. */
362 /* In general, child pointers move along with keys, but there are */
363 /* some tricky points: */
364
365 /* - The left and right child pointers of the parent key don't */
366 /* get updated; they continue to point to the two children */
367 /* LEFT and RIGHT. */
368
369 /* - On a right shift, the right child pointer of the key that */
370 /* gets moved into the parent key's original position becomes */
371 /* the first left child pointer of the right sibling. The left */
372 /* child pointer of this key doesn't get moved at all. */
373
374 /* - On a left shift, the left child pointer of the key that */
375 /* gets moved into the parent key's original position becomes */
376 /* the last right child pointer of the left sibling. The right */
377 /* child pointer of this key becomes the left child pointer of */
378 /* the first key of RIGHT. */
379
380 /* $ Examples */
381
382 /* See ZZEKTRIN. */
383
384 /* $ Restrictions */
385
386 /* None. */
387
388 /* $ Literature_References */
389
390 /* 1) Knuth, Donald E. "The Art of Computer Programming, Volume */
391 /* 3/Sorting and Searching" 1973, pp 471-479. */
392
393 /* EK trees are closely related to the B* trees described by */
394 /* Knuth. */
395
396 /* $ Author_and_Institution */
397
398 /* N.J. Bachman (JPL) */
399
400 /* $ Version */
401
402 /* - Beta Version 1.0.0, 27-OCT-1995 (NJB) */
403
404 /* -& */
405
406 /* Non-SPICELIB functions */
407
408
409 /* Local variables */
410
411
412 /* Use discovery check-in for speed. */
413
414 root = *tree;
415 if (*left == root || *right == root) {
416 chkin_("ZZEKTRBN", (ftnlen)8);
417 setmsg_("Input node is root; only children can be balanced.", (ftnlen)
418 50);
419 sigerr_("SPICE(BUG)", (ftnlen)10);
420 chkout_("ZZEKTRBN", (ftnlen)8);
421 }
422
423 /* Get the key counts for the left and right nodes. */
424
425 lnkeys = zzektrnk_(handle, tree, left);
426 rnkeys = zzektrnk_(handle, tree, right);
427
428 /* Balancing the nodes should give each of them a key count in */
429 /* the range of */
430
431 /* MNKEYC : MXKEYC */
432
433 /* If that's not possible, we have a serious problem. */
434
435 sum = lnkeys + rnkeys;
436 if (sum > 124 || sum < 82) {
437 chkin_("ZZEKTRBN", (ftnlen)8);
438 setmsg_("Node # and right sibling # contain # and # keys respectivel"
439 "y; count sum should be in range #:#.", (ftnlen)95);
440 errint_("#", left, (ftnlen)1);
441 errint_("#", right, (ftnlen)1);
442 errint_("#", &lnkeys, (ftnlen)1);
443 errint_("#", &rnkeys, (ftnlen)1);
444 errint_("#", &c__82, (ftnlen)1);
445 errint_("#", &c__124, (ftnlen)1);
446 sigerr_("SPICE(BUG)", (ftnlen)10);
447 chkout_("ZZEKTRBN", (ftnlen)8);
448 return 0;
449 }
450
451 /* Now, the actions we take depend on whether we must schlep keys */
452 /* to the right or left. */
453
454 if (lnkeys > rnkeys) {
455 schlep = lnkeys - (sum + 1) / 2;
456 } else if (lnkeys < rnkeys) {
457 schlep = -(rnkeys - (sum + 1) / 2);
458 } else {
459 schlep = 0;
460 }
461
462 /* Rotate the requested number of keys. */
463
464 zzektrrk_(handle, tree, left, right, parent, pkidx, &schlep);
465 return 0;
466 } /* zzektrbn_ */
467
468