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