1 /* zzektr31.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__81 = 81;
11 static integer c__3 = 3;
12
13 /* $Procedure ZZEKTR31 ( EK tree, 3-1 merge ) */
zzektr31_(integer * handle,integer * tree)14 /* Subroutine */ int zzektr31_(integer *handle, integer *tree)
15 {
16 /* System generated locals */
17 integer i__1, i__2, i__3;
18
19 /* Builtin functions */
20 integer s_rnge(char *, integer, char *, integer);
21
22 /* Local variables */
23 integer root;
24 extern /* Subroutine */ int zzekpgfr_(integer *, integer *, integer *),
25 zzekpgri_(integer *, integer *, integer *), zzekpgwi_(integer *,
26 integer *, integer *);
27 integer i__, child[2], delta;
28 extern /* Subroutine */ int chkin_(char *, ftnlen);
29 integer rpage[256];
30 extern /* Subroutine */ int movei_(integer *, integer *, integer *);
31 integer c1page[256], c2page[256], middle;
32 extern /* Subroutine */ int sigerr_(char *, ftnlen), chkout_(char *,
33 ftnlen);
34 integer nlkeys, nrkeys;
35 extern /* Subroutine */ int setmsg_(char *, ftnlen), errint_(char *,
36 integer *, ftnlen);
37 integer sum;
38
39 /* $ Abstract */
40
41 /* Execute a 3-1 merge: move the contents of two children into */
42 /* the root node and delete the children. */
43
44 /* $ Disclaimer */
45
46 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
47 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
48 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
49 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
50 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
51 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
52 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
53 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
54 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
55 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
56
57 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
58 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
59 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
60 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
61 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
62 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
63
64 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
65 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
66 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
67 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
68
69 /* $ Required_Reading */
70
71 /* EK */
72
73 /* $ Keywords */
74
75 /* EK */
76 /* PRIVATE */
77
78 /* $ Declarations */
79 /* $ Disclaimer */
80
81 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
82 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
83 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
84 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
85 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
86 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
87 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
88 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
89 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
90 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
91
92 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
93 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
94 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
95 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
96 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
97 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
98
99 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
100 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
101 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
102 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
103
104
105 /* Include Section: EK Tree Parameters */
106
107 /* ektree.inc Version 3 22-OCT-1995 (NJB) */
108
109
110 /* The parameters in this file define the tree structure */
111 /* used by the EK system. This structure is a variant of the */
112 /* B*-tree structure described in Knuth's book, that is */
113
114 /* Knuth, Donald E. "The Art of Computer Programming, */
115 /* Volume 3/Sorting and Searching" 1973, pp 471-479. */
116
117 /* The trees used in the EK system differ from generic B*-trees */
118 /* primarily in the way keys are treated. Rather than storing */
119 /* unique primary key values in each node, EK trees store integer */
120 /* counts that represent the ordinal position of each data value, */
121 /* counting from the lowest indexed element in the subtree whose */
122 /* root is the node in question. Thus the keys are unique within */
123 /* a node but not across multiple nodes: in fact the Nth key in */
124 /* every leaf node is N. The absolute ordinal position of a data */
125 /* item is defined recursively as the sum of the key of the data item */
126 /* and the absolute ordinal position of the data item in the parent */
127 /* node that immediately precedes all elements of the node in */
128 /* question. This data structure allows EK trees to support lookup */
129 /* of data items based on their ordinal position in a data set. The */
130 /* two prime applications of this capability in the EK system are: */
131
132 /* 1) Using trees to index the records in a table, allowing */
133 /* the Nth record to be located efficiently. */
134
135 /* 2) Using trees to implement order vectors that can be */
136 /* maintained when insertions and deletions are done. */
137
138
139
140 /* Root node */
141
142 /* +--------------------------------------------+ */
143 /* | Tree version code | */
144 /* +--------------------------------------------+ */
145 /* | Number of nodes in tree | */
146 /* +--------------------------------------------+ */
147 /* | Number of keys in tree | */
148 /* +--------------------------------------------+ */
149 /* | Depth of tree | */
150 /* +--------------------------------------------+ */
151 /* | Number of keys in root | */
152 /* +--------------------------------------------+ */
153 /* | Space for n keys, | */
154 /* | | */
155 /* | n = 2 * INT( ( 2*m - 2 )/3 ) | */
156 /* | | */
157 /* | where m is the max number of children per | */
158 /* | node in the child nodes | */
159 /* +--------------------------------------------+ */
160 /* | Space for n+1 child pointers, | */
161 /* | where n is as defined above. | */
162 /* +--------------------------------------------+ */
163 /* | Space for n data pointers, | */
164 /* | where n is as defined above. | */
165 /* +--------------------------------------------+ */
166
167
168 /* Child node */
169
170 /* +--------------------------------------------+ */
171 /* | Number of keys present in node | */
172 /* +--------------------------------------------+ */
173 /* | Space for m-1 keys | */
174 /* +--------------------------------------------+ */
175 /* | Space for m child pointers | */
176 /* +--------------------------------------------+ */
177 /* | Space for m-1 data pointers | */
178 /* +--------------------------------------------+ */
179
180
181
182
183 /* The following parameters give the maximum number of children */
184 /* allowed in the root and child nodes. During insertions, the */
185 /* number of children may overflow by 1. */
186
187
188 /* Maximum number of children allowed in a child node: */
189
190
191 /* Maximum number of keys allowed in a child node: */
192
193
194 /* Minimum number of children allowed in a child node: */
195
196
197 /* Minimum number of keys allowed in a child node: */
198
199
200 /* Maximum number of children allowed in the root node: */
201
202
203 /* Maximum number of keys allowed in the root node: */
204
205
206 /* Minimum number of children allowed in the root node: */
207
208
209
210 /* The following parameters indicate positions of elements in the */
211 /* tree node structures shown above. */
212
213
214 /* The following parameters are for the root node only: */
215
216
217 /* Location of version code: */
218
219
220 /* Version code: */
221
222
223 /* Location of node count: */
224
225
226 /* Location of total key count for the tree: */
227
228
229 /* Location of tree depth: */
230
231
232 /* Location of count of keys in root node: */
233
234
235 /* Base address of keys in the root node: */
236
237
238 /* Base address of child pointers in root node: */
239
240
241 /* Base address of data pointers in the root node (allow room for */
242 /* overflow): */
243
244
245 /* Size of root node: */
246
247
248 /* The following parameters are for child nodes only: */
249
250
251 /* Location of number of keys in node: */
252
253
254 /* Base address of keys in child nodes: */
255
256
257 /* Base address of child pointers in child nodes: */
258
259
260 /* Base address of data pointers in child nodes (allow room */
261 /* for overflow): */
262
263
264 /* Size of child node: */
265
266
267 /* A number of EK tree routines must declare stacks of fixed */
268 /* depth; this depth limit imposes a limit on the maximum depth */
269 /* that an EK tree can have. Because of the large branching */
270 /* factor of EK trees, the depth limit is of no practical */
271 /* importance: The number of keys that can be held in an EK */
272 /* tree of depth N is */
273
274 /* N-1 */
275 /* MXKIDC - 1 */
276 /* MXKIDR * ------------- */
277 /* MXKIDC - 1 */
278
279
280 /* This formula yields a capacity of over 1 billion keys for a */
281 /* tree of depth 6. */
282
283
284 /* End Include Section: EK Tree Parameters */
285
286 /* $ Disclaimer */
287
288 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
289 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
290 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
291 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
292 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
293 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
294 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
295 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
296 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
297 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
298
299 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
300 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
301 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
302 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
303 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
304 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
305
306 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
307 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
308 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
309 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
310
311
312 /* Include Section: EK Das Paging Parameters */
313
314 /* ekpage.inc Version 4 25-AUG-1995 (NJB) */
315
316
317
318 /* The EK DAS paging system makes use of the integer portion */
319 /* of an EK file's DAS address space to store the few numbers */
320 /* required to describe the system's state. The allocation */
321 /* of DAS integer addresses is shown below. */
322
323
324 /* DAS integer array */
325
326 /* +--------------------------------------------+ */
327 /* | EK architecture code | Address = 1 */
328 /* +--------------------------------------------+ */
329 /* | Character page size (in DAS words) | */
330 /* +--------------------------------------------+ */
331 /* | Character page base address | */
332 /* +--------------------------------------------+ */
333 /* | Number of character pages in file | */
334 /* +--------------------------------------------+ */
335 /* | Number of character pages on free list | */
336 /* +--------------------------------------------+ */
337 /* | Character free list head pointer | Address = 6 */
338 /* +--------------------------------------------+ */
339 /* | | Addresses = */
340 /* | Metadata for d.p. pages | 7--11 */
341 /* | | */
342 /* +--------------------------------------------+ */
343 /* | | Addresses = */
344 /* | Metadata for integer pages | 12--16 */
345 /* | | */
346 /* +--------------------------------------------+ */
347 /* . */
348 /* . */
349 /* . */
350 /* +--------------------------------------------+ */
351 /* | | End Address = */
352 /* | Unused space | integer page */
353 /* | | end */
354 /* +--------------------------------------------+ */
355 /* | | Start Address = */
356 /* | First integer page | integer page */
357 /* | | base */
358 /* +--------------------------------------------+ */
359 /* . */
360 /* . */
361 /* . */
362 /* +--------------------------------------------+ */
363 /* | | */
364 /* | Last integer page | */
365 /* | | */
366 /* +--------------------------------------------+ */
367
368 /* The following parameters indicate positions of elements in the */
369 /* paging system metadata array: */
370
371
372
373 /* Number of metadata items per data type: */
374
375
376 /* Character metadata indices: */
377
378
379 /* Double precision metadata indices: */
380
381
382 /* Integer metadata indices: */
383
384
385 /* Size of metadata area: */
386
387
388 /* Page sizes, in units of DAS words of the appropriate type: */
389
390
391 /* Default page base addresses: */
392
393
394 /* End Include Section: EK Das Paging Parameters */
395
396 /* $ Disclaimer */
397
398 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
399 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
400 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
401 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
402 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
403 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
404 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
405 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
406 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
407 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
408
409 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
410 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
411 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
412 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
413 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
414 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
415
416 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
417 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
418 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
419 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
420
421
422 /* Include Section: EK Data Types */
423
424 /* ektype.inc Version 1 27-DEC-1994 (NJB) */
425
426
427 /* Within the EK system, data types of EK column contents are */
428 /* represented by integer codes. The codes and their meanings */
429 /* are listed below. */
430
431 /* Integer codes are also used within the DAS system to indicate */
432 /* data types; the EK system makes no assumptions about compatibility */
433 /* between the codes used here and those used in the DAS system. */
434
435
436 /* Character type: */
437
438
439 /* Double precision type: */
440
441
442 /* Integer type: */
443
444
445 /* `Time' type: */
446
447 /* Within the EK system, time values are represented as ephemeris */
448 /* seconds past J2000 (TDB), and double precision numbers are used */
449 /* to store these values. However, since time values require special */
450 /* treatment both on input and output, and since the `TIME' column */
451 /* has a special role in the EK specification and code, time values */
452 /* are identified as a type distinct from double precision numbers. */
453
454
455 /* End Include Section: EK Data Types */
456
457 /* $ Brief_I/O */
458
459 /* Variable I/O Description */
460 /* -------- --- -------------------------------------------------- */
461 /* HANDLE I File handle. */
462 /* TREE I Root of tree. */
463
464 /* $ Detailed_Input */
465
466 /* HANDLE is a file handle of an EK open for write access. */
467
468 /* TREE is the root node number of the tree of interest. */
469
470 /* $ Detailed_Output */
471
472 /* None. See $Particulars for a description of the effect of this */
473 /* routine. */
474
475 /* $ Parameters */
476
477 /* None. */
478
479 /* $ Exceptions */
480
481 /* 1) If HANDLE is invalid, the error will be diagnosed by routines */
482 /* called by this routine. The file will not be modified. */
483
484 /* 2) If an I/O error occurs while reading the indicated file, the */
485 /* error will be diagnosed by routines called by this routine. */
486
487 /* 3) If there is not exactly 1 key in the root at the time this */
488 /* routine is called, the error SPICE(BUG) is signalled. */
489
490 /* $ Files */
491
492 /* See the EK Required Reading for a discussion of the EK file */
493 /* format. */
494
495 /* $ Particulars */
496
497 /* Deletions from an EK tree start at a leaf node. If the node */
498 /* underflows, the EK system attempts to shuffle keys at the leaf */
499 /* level to resolve the underflow. That attempt failing, the system */
500 /* delegates the problem upward to the next higher level. Underflow */
501 /* may occur there as well; if it does, the problem gets passed */
502 /* upward again. If the root has only two children and one of these */
503 /* underflows, the system reduces the height of the tree by */
504 /* executing what's called a `3-1' merge: the root loses its two */
505 /* children, and all of the keys in the children are moved into */
506 /* the root. The former grandchildren of the root become */
507 /* children of the root. */
508
509 /* A tree is eligible for a 3-1 merge only if the root has exactly */
510 /* two children, and the sum of the key counts of the children */
511 /* constitutes an underflow of 1 key: that is, the sum is */
512
513 /* 2*MNKEYC - 1 */
514
515 /* After the 3-1 merge, the tree is balanced and all invariants */
516 /* relating to key counts are restored. */
517
518 /* The tree grows shorter by one level as a result of a 3-1 merge; */
519 /* this is the only circumstance under which the tree grows shorter. */
520
521 /* Below are the gory details concerning the actions of this routine. */
522 /* All of the parameters referred to here (in capital letters) are */
523 /* defined in the include file ektree.inc. */
524
525 /* In a 3-1 merge: */
526
527
528 /* - The keys of the left child are moved into the root. These */
529 /* become the leftmost MNKEYC or MNKEYC-1 keys of the root, */
530 /* depending on whether the underflow occurred in the left */
531 /* child. */
532
533 /* - The data values associated with the keys of the left child */
534 /* of the root are moved into the root along with the keys. */
535
536 /* - The left child pointers associated with the keys of the left */
537 /* child of the root are moved into the root along with the */
538 /* keys. */
539
540 /* - The last right child pointer in the left child of the root */
541 /* the root is moved to location NLEFT+1 in the child pointer */
542 /* array of the root, where NLEFT is the number of keys in */
543 /* the former left child. This pointer overwrites the root's */
544 /* pointer to the left child. */
545
546 /* - The keys of the right child are moved into the root. These */
547 /* become the rightmost MNKEYC or MNKEYC-1 keys of the root, */
548 /* depending on whether the underflow occurred in the right */
549 /* child. */
550
551 /* - The data values associated with the keys of the right child */
552 /* of the root are moved into the root along with the keys. */
553
554 /* - The left child pointers associated with the keys of the right */
555 /* child of the root are moved into the root along with the */
556 /* keys. The first of these pointers overwrites the root's */
557 /* pointer to the right child. */
558
559 /* - The last right child pointer in the right child of the root */
560 /* the root is moved to location 2*MNKEYC+1 in the child pointer */
561 /* array of the root. */
562
563 /* - The former children of the root are deleted. */
564
565 /* As the above list shows, the root contains the maximum allowed */
566 /* number of keys after a 3-1 merge. This is because */
567
568 /* MXKEYR = MXKIDR - 1 */
569
570 /* = 2 * ( (2*MXKIDC - 2)/3 ) */
571
572 /* = 2 * ( (2*MXKIDC + 1)/3 - 1 ) */
573
574 /* = 2 * ( MNKIDC - 1) */
575
576 /* = 2 * MNKEYC */
577
578 /* Our assumptions were that there was one key in the root and */
579 /* that the sum of the key counts of the two children of the root */
580 /* was */
581
582 /* ( 2 * MNKEYC ) - 1 */
583
584 /* Thus the size constraints on the root node are met. */
585
586 /* $ Examples */
587
588 /* See ZZEKTRDL. */
589
590 /* $ Restrictions */
591
592 /* None. */
593
594 /* $ Literature_References */
595
596 /* None. */
597
598 /* $ Author_and_Institution */
599
600 /* N.J. Bachman (JPL) */
601
602 /* $ Version */
603
604 /* - Beta Version 1.0.0, 27-OCT-1995 (NJB) */
605
606 /* -& */
607
608 /* Local variables */
609
610
611 /* Use discovery check-in for speed. */
612
613 root = *tree;
614 zzekpgri_(handle, &root, rpage);
615 nrkeys = rpage[4];
616
617 /* There must be exactly 1 key in the root. */
618
619 if (nrkeys != 1) {
620 chkin_("ZZEKTR31", (ftnlen)8);
621 setmsg_("Number of keys in root = #; should be 1.", (ftnlen)40);
622 errint_("#", &nrkeys, (ftnlen)1);
623 sigerr_("SPICE(BUG)", (ftnlen)10);
624 chkout_("ZZEKTR31", (ftnlen)8);
625 return 0;
626 }
627
628 /* Read in the child pages. Get the key counts for these pages. */
629
630 child[0] = rpage[88];
631 child[1] = rpage[89];
632 zzekpgri_(handle, child, c1page);
633 zzekpgri_(handle, &child[1], c2page);
634 nlkeys = c1page[0];
635 nrkeys = c2page[0];
636 sum = nlkeys + nrkeys;
637
638 /* The sum of the number of keys in the two input nodes must */
639 /* sum exactly to value representing an underflow level of 1 key. */
640
641 if (sum != 81) {
642 chkin_("ZZEKTR31", (ftnlen)8);
643 setmsg_("Number of keys in nodes LEFT = #; in RIGHT = #; counts summ"
644 "ing to # were expected.", (ftnlen)82);
645 errint_("#", &nlkeys, (ftnlen)1);
646 errint_("#", &nrkeys, (ftnlen)1);
647 errint_("#", &c__81, (ftnlen)1);
648 sigerr_("SPICE(BUG)", (ftnlen)10);
649 chkout_("ZZEKTR31", (ftnlen)8);
650 return 0;
651 }
652
653 /* Shift the key and data pointer in the root to right to allow */
654 /* insertion of NLKEYS new entries on the left. The child pointers */
655 /* need not be shifted; they'll be overwritten later. */
656
657 rpage[(i__1 = nlkeys + 5) < 256 && 0 <= i__1 ? i__1 : s_rnge("rpage",
658 i__1, "zzektr31_", (ftnlen)279)] = rpage[5];
659 rpage[(i__1 = nlkeys + 172) < 256 && 0 <= i__1 ? i__1 : s_rnge("rpage",
660 i__1, "zzektr31_", (ftnlen)280)] = rpage[172];
661
662 /* Copy in the keys, data pointers, and child pointers from the */
663 /* left child into the root. The number of predecessors of the */
664 /* new keys is unchanged by this operation. */
665
666 movei_(&c1page[1], &nlkeys, &rpage[5]);
667 movei_(&c1page[128], &nlkeys, &rpage[172]);
668 i__1 = nlkeys + 1;
669 movei_(&c1page[64], &i__1, &rpage[88]);
670
671 /* Copy in the keys, data pointers, and child pointers from the */
672 /* right child into the root. The number of predecessors of the */
673 /* new keys is increased by the value of the last key already */
674 /* present. */
675
676 middle = nlkeys + 1;
677 delta = rpage[(i__1 = middle + 4) < 256 && 0 <= i__1 ? i__1 : s_rnge(
678 "rpage", i__1, "zzektr31_", (ftnlen)298)];
679 i__1 = nrkeys;
680 for (i__ = 1; i__ <= i__1; ++i__) {
681 rpage[(i__2 = middle + 5 + i__ - 1) < 256 && 0 <= i__2 ? i__2 :
682 s_rnge("rpage", i__2, "zzektr31_", (ftnlen)301)] = c2page[(
683 i__3 = i__) < 256 && 0 <= i__3 ? i__3 : s_rnge("c2page", i__3,
684 "zzektr31_", (ftnlen)301)] + delta;
685 }
686 movei_(&c2page[128], &nrkeys, &rpage[(i__1 = middle + 172) < 256 && 0 <=
687 i__1 ? i__1 : s_rnge("rpage", i__1, "zzektr31_", (ftnlen)304)]);
688 i__2 = nrkeys + 1;
689 movei_(&c2page[64], &i__2, &rpage[(i__1 = middle + 88) < 256 && 0 <= i__1
690 ? i__1 : s_rnge("rpage", i__1, "zzektr31_", (ftnlen)305)]);
691
692 /* Now the root must be updated. The root now contains */
693 /* the maximum allowed number of keys. The depth of the tree */
694 /* has decreased, as well as the number of nodes in the tree. */
695
696 rpage[4] = 82;
697 --rpage[3];
698 rpage[1] += -2;
699
700 /* Write out the updated root. */
701
702 zzekpgwi_(handle, &root, rpage);
703
704 /* Free the pages occupied by the deleted children. */
705
706 for (i__ = 1; i__ <= 2; ++i__) {
707 zzekpgfr_(handle, &c__3, &child[(i__1 = i__ - 1) < 2 && 0 <= i__1 ?
708 i__1 : s_rnge("child", i__1, "zzektr31_", (ftnlen)325)]);
709 }
710 return 0;
711 } /* zzektr31_ */
712
713