1 /* zzektrlk.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 /* $Procedure ZZEKTRLK ( EK tree, locate key ) */
zzektrlk_(integer * handle,integer * tree,integer * key,integer * idx,integer * node,integer * noffst,integer * level,integer * value)9 /* Subroutine */ int zzektrlk_(integer *handle, integer *tree, integer *key,
10 integer *idx, integer *node, integer *noffst, integer *level, integer
11 *value)
12 {
13 /* Initialized data */
14
15 static logical first = TRUE_;
16 static integer oldval = 0;
17 static integer page[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
18 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
19 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
20 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
21 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
22 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
23 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
24 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
25 0,0,0 };
26 static integer oldhan = 0;
27 static integer oldidx = 0;
28 static integer oldkey = 0;
29 static integer oldlvl = 0;
30 static integer oldmax = 0;
31 static integer oldnod = 0;
32 static integer oldnof = 0;
33 static integer oldtre = 0;
34
35 /* System generated locals */
36 integer i__1;
37
38 /* Builtin functions */
39 integer s_cmp(char *, char *, ftnlen, ftnlen), s_rnge(char *, integer,
40 char *, integer);
41
42 /* Local variables */
43 static logical leaf;
44 static integer prev, plus;
45 extern /* Subroutine */ int zzekpgri_(integer *, integer *, integer *);
46 static integer child;
47 extern /* Subroutine */ int chkin_(char *, ftnlen);
48 static integer depth;
49 static logical found;
50 static integer minus;
51 static char access[15];
52 static integer datbas;
53 extern /* Subroutine */ int dasham_(integer *, char *, ftnlen);
54 extern integer lstlei_(integer *, integer *, integer *);
55 static integer newkey, prvkey, totkey;
56 static logical samkey, samtre, rdonly;
57 extern /* Subroutine */ int setmsg_(char *, ftnlen), errint_(char *,
58 integer *, ftnlen), errhan_(char *, integer *, ftnlen), sigerr_(
59 char *, ftnlen), chkout_(char *, ftnlen);
60
61 /* $ Abstract */
62
63 /* Locate a specified key. Return metadata describing the node */
64 /* containing the key. */
65
66 /* $ Disclaimer */
67
68 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
69 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
70 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
71 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
72 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
73 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
74 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
75 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
76 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
77 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
78
79 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
80 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
81 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
82 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
83 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
84 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
85
86 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
87 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
88 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
89 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
90
91 /* $ Required_Reading */
92
93 /* EK */
94
95 /* $ Keywords */
96
97 /* EK */
98 /* PRIVATE */
99
100 /* $ Declarations */
101 /* $ Disclaimer */
102
103 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
104 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
105 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
106 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
107 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
108 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
109 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
110 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
111 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
112 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
113
114 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
115 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
116 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
117 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
118 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
119 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
120
121 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
122 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
123 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
124 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
125
126
127 /* Include Section: EK Das Paging Parameters */
128
129 /* ekpage.inc Version 4 25-AUG-1995 (NJB) */
130
131
132
133 /* The EK DAS paging system makes use of the integer portion */
134 /* of an EK file's DAS address space to store the few numbers */
135 /* required to describe the system's state. The allocation */
136 /* of DAS integer addresses is shown below. */
137
138
139 /* DAS integer array */
140
141 /* +--------------------------------------------+ */
142 /* | EK architecture code | Address = 1 */
143 /* +--------------------------------------------+ */
144 /* | Character page size (in DAS words) | */
145 /* +--------------------------------------------+ */
146 /* | Character page base address | */
147 /* +--------------------------------------------+ */
148 /* | Number of character pages in file | */
149 /* +--------------------------------------------+ */
150 /* | Number of character pages on free list | */
151 /* +--------------------------------------------+ */
152 /* | Character free list head pointer | Address = 6 */
153 /* +--------------------------------------------+ */
154 /* | | Addresses = */
155 /* | Metadata for d.p. pages | 7--11 */
156 /* | | */
157 /* +--------------------------------------------+ */
158 /* | | Addresses = */
159 /* | Metadata for integer pages | 12--16 */
160 /* | | */
161 /* +--------------------------------------------+ */
162 /* . */
163 /* . */
164 /* . */
165 /* +--------------------------------------------+ */
166 /* | | End Address = */
167 /* | Unused space | integer page */
168 /* | | end */
169 /* +--------------------------------------------+ */
170 /* | | Start Address = */
171 /* | First integer page | integer page */
172 /* | | base */
173 /* +--------------------------------------------+ */
174 /* . */
175 /* . */
176 /* . */
177 /* +--------------------------------------------+ */
178 /* | | */
179 /* | Last integer page | */
180 /* | | */
181 /* +--------------------------------------------+ */
182
183 /* The following parameters indicate positions of elements in the */
184 /* paging system metadata array: */
185
186
187
188 /* Number of metadata items per data type: */
189
190
191 /* Character metadata indices: */
192
193
194 /* Double precision metadata indices: */
195
196
197 /* Integer metadata indices: */
198
199
200 /* Size of metadata area: */
201
202
203 /* Page sizes, in units of DAS words of the appropriate type: */
204
205
206 /* Default page base addresses: */
207
208
209 /* End Include Section: EK Das Paging Parameters */
210
211 /* $ Disclaimer */
212
213 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
214 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
215 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
216 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
217 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
218 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
219 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
220 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
221 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
222 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
223
224 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
225 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
226 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
227 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
228 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
229 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
230
231 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
232 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
233 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
234 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
235
236
237 /* Include Section: EK Tree Parameters */
238
239 /* ektree.inc Version 3 22-OCT-1995 (NJB) */
240
241
242 /* The parameters in this file define the tree structure */
243 /* used by the EK system. This structure is a variant of the */
244 /* B*-tree structure described in Knuth's book, that is */
245
246 /* Knuth, Donald E. "The Art of Computer Programming, */
247 /* Volume 3/Sorting and Searching" 1973, pp 471-479. */
248
249 /* The trees used in the EK system differ from generic B*-trees */
250 /* primarily in the way keys are treated. Rather than storing */
251 /* unique primary key values in each node, EK trees store integer */
252 /* counts that represent the ordinal position of each data value, */
253 /* counting from the lowest indexed element in the subtree whose */
254 /* root is the node in question. Thus the keys are unique within */
255 /* a node but not across multiple nodes: in fact the Nth key in */
256 /* every leaf node is N. The absolute ordinal position of a data */
257 /* item is defined recursively as the sum of the key of the data item */
258 /* and the absolute ordinal position of the data item in the parent */
259 /* node that immediately precedes all elements of the node in */
260 /* question. This data structure allows EK trees to support lookup */
261 /* of data items based on their ordinal position in a data set. The */
262 /* two prime applications of this capability in the EK system are: */
263
264 /* 1) Using trees to index the records in a table, allowing */
265 /* the Nth record to be located efficiently. */
266
267 /* 2) Using trees to implement order vectors that can be */
268 /* maintained when insertions and deletions are done. */
269
270
271
272 /* Root node */
273
274 /* +--------------------------------------------+ */
275 /* | Tree version code | */
276 /* +--------------------------------------------+ */
277 /* | Number of nodes in tree | */
278 /* +--------------------------------------------+ */
279 /* | Number of keys in tree | */
280 /* +--------------------------------------------+ */
281 /* | Depth of tree | */
282 /* +--------------------------------------------+ */
283 /* | Number of keys in root | */
284 /* +--------------------------------------------+ */
285 /* | Space for n keys, | */
286 /* | | */
287 /* | n = 2 * INT( ( 2*m - 2 )/3 ) | */
288 /* | | */
289 /* | where m is the max number of children per | */
290 /* | node in the child nodes | */
291 /* +--------------------------------------------+ */
292 /* | Space for n+1 child pointers, | */
293 /* | where n is as defined above. | */
294 /* +--------------------------------------------+ */
295 /* | Space for n data pointers, | */
296 /* | where n is as defined above. | */
297 /* +--------------------------------------------+ */
298
299
300 /* Child node */
301
302 /* +--------------------------------------------+ */
303 /* | Number of keys present in node | */
304 /* +--------------------------------------------+ */
305 /* | Space for m-1 keys | */
306 /* +--------------------------------------------+ */
307 /* | Space for m child pointers | */
308 /* +--------------------------------------------+ */
309 /* | Space for m-1 data pointers | */
310 /* +--------------------------------------------+ */
311
312
313
314
315 /* The following parameters give the maximum number of children */
316 /* allowed in the root and child nodes. During insertions, the */
317 /* number of children may overflow by 1. */
318
319
320 /* Maximum number of children allowed in a child node: */
321
322
323 /* Maximum number of keys allowed in a child node: */
324
325
326 /* Minimum number of children allowed in a child node: */
327
328
329 /* Minimum number of keys allowed in a child node: */
330
331
332 /* Maximum number of children allowed in the root node: */
333
334
335 /* Maximum number of keys allowed in the root node: */
336
337
338 /* Minimum number of children allowed in the root node: */
339
340
341
342 /* The following parameters indicate positions of elements in the */
343 /* tree node structures shown above. */
344
345
346 /* The following parameters are for the root node only: */
347
348
349 /* Location of version code: */
350
351
352 /* Version code: */
353
354
355 /* Location of node count: */
356
357
358 /* Location of total key count for the tree: */
359
360
361 /* Location of tree depth: */
362
363
364 /* Location of count of keys in root node: */
365
366
367 /* Base address of keys in the root node: */
368
369
370 /* Base address of child pointers in root node: */
371
372
373 /* Base address of data pointers in the root node (allow room for */
374 /* overflow): */
375
376
377 /* Size of root node: */
378
379
380 /* The following parameters are for child nodes only: */
381
382
383 /* Location of number of keys in node: */
384
385
386 /* Base address of keys in child nodes: */
387
388
389 /* Base address of child pointers in child nodes: */
390
391
392 /* Base address of data pointers in child nodes (allow room */
393 /* for overflow): */
394
395
396 /* Size of child node: */
397
398
399 /* A number of EK tree routines must declare stacks of fixed */
400 /* depth; this depth limit imposes a limit on the maximum depth */
401 /* that an EK tree can have. Because of the large branching */
402 /* factor of EK trees, the depth limit is of no practical */
403 /* importance: The number of keys that can be held in an EK */
404 /* tree of depth N is */
405
406 /* N-1 */
407 /* MXKIDC - 1 */
408 /* MXKIDR * ------------- */
409 /* MXKIDC - 1 */
410
411
412 /* This formula yields a capacity of over 1 billion keys for a */
413 /* tree of depth 6. */
414
415
416 /* End Include Section: EK Tree Parameters */
417
418 /* $ Disclaimer */
419
420 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
421 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
422 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
423 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
424 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
425 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
426 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
427 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
428 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
429 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
430
431 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
432 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
433 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
434 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
435 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
436 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
437
438 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
439 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
440 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
441 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
442
443
444 /* Include Section: EK Data Types */
445
446 /* ektype.inc Version 1 27-DEC-1994 (NJB) */
447
448
449 /* Within the EK system, data types of EK column contents are */
450 /* represented by integer codes. The codes and their meanings */
451 /* are listed below. */
452
453 /* Integer codes are also used within the DAS system to indicate */
454 /* data types; the EK system makes no assumptions about compatibility */
455 /* between the codes used here and those used in the DAS system. */
456
457
458 /* Character type: */
459
460
461 /* Double precision type: */
462
463
464 /* Integer type: */
465
466
467 /* `Time' type: */
468
469 /* Within the EK system, time values are represented as ephemeris */
470 /* seconds past J2000 (TDB), and double precision numbers are used */
471 /* to store these values. However, since time values require special */
472 /* treatment both on input and output, and since the `TIME' column */
473 /* has a special role in the EK specification and code, time values */
474 /* are identified as a type distinct from double precision numbers. */
475
476
477 /* End Include Section: EK Data Types */
478
479 /* $ Brief_I/O */
480
481 /* Variable I/O Description */
482 /* -------- --- -------------------------------------------------- */
483 /* HANDLE I File handle. */
484 /* TREE I Root of tree. */
485 /* KEY I Key corresponding to value. */
486 /* IDX O Node-relative index of KEY. */
487 /* NODE O Node containing key. */
488 /* NOFFST O Offset of NODE. */
489 /* LEVEL O Level of NODE. */
490 /* VALUE O Value associated with KEY. */
491
492 /* $ Detailed_Input */
493
494 /* HANDLE is a file handle of an EK open for write access. */
495
496 /* TREE is the root node number of the tree of interest. */
497
498 /* KEY is an absolute key. In EK trees, absolute keys are */
499 /* just ordinal positions relative to the leftmost */
500 /* element of the tree, with the leftmost element */
501 /* having position 1. So setting KEY to 10, for */
502 /* example, indicates that the output VALUE is the */
503 /* 10th item in the tree. */
504
505 /* KEY must be in the range 1 : NKEYS, where */
506 /* NKEYS is the number of keys in the tree. */
507
508 /* $ Detailed_Output */
509
510 /* IDX is the node-relative index of KEY: this is the */
511 /* ordinal position of KEY relative to other keys */
512 /* in the same node. */
513
514 /* NODE is the number of the node containing KEY. */
515
516 /* NOFFST is the offset of NODE. This is the count of the */
517 /* keys that precede every key in the subtree headed */
518 /* by NODE. Adding NOFFST to any relative key stored */
519 /* in NODE will convert that key to an absolute key. */
520
521 /* LEVEL is the level of NODE in the tree. The root is at */
522 /* level 1, children of the root are at level 2, and */
523 /* so on. */
524
525 /* VALUE is the integer value associated with the input key. */
526 /* Normally, this value is a data pointer. */
527
528 /* $ Parameters */
529
530 /* None. */
531
532 /* $ Exceptions */
533
534 /* 1) If HANDLE is invalid, the error will be diagnosed by routines */
535 /* called by this routine. The file will not be modified. */
536
537 /* 2) If an I/O error occurs while reading or writing the indicated */
538 /* file, the error will be diagnosed by routines called by this */
539 /* routine. */
540
541 /* 3) If the input key is out of range, the error */
542 /* SPICE(INDEXOUTOFRANGE) is signaled. */
543
544
545 /* 4) If the tree traversal fails to terminate at the leaf node */
546 /* level, the error SPICE(BUG) is signaled. */
547
548 /* 5) If the key is in range, but the key is not found, the error */
549 /* SPICE(BUG) is signaled. */
550
551 /* $ Files */
552
553 /* See the EK Required Reading for a discussion of the EK file */
554 /* format. */
555
556 /* $ Particulars */
557
558 /* This routine obtains the value associated with a key, and also */
559 /* returns metadata describing the node containing the key and the */
560 /* key's position in the node. */
561
562 /* $ Examples */
563
564 /* See ZZEKTRUI. */
565
566 /* $ Restrictions */
567
568 /* None. */
569
570 /* $ Literature_References */
571
572 /* 1) Knuth, Donald E. "The Art of Computer Programming, Volume */
573 /* 3/Sorting and Searching" 1973, pp 471-479. */
574
575 /* EK trees are closely related to the B* trees described by */
576 /* Knuth. */
577
578 /* $ Author_and_Institution */
579
580 /* N.J. Bachman (JPL) */
581
582 /* $ Version */
583
584 /* - SPICELIB Version 1.1.0, 09-FEB-2015 (NJB) */
585
586 /* Now uses ERRHAN to insert DAS file name into */
587 /* long error messages. */
588
589 /* Added initializers for variables used to save old */
590 /* values. */
591
592 /* - Beta Version 1.0.0, 26-OCT-1995 (NJB) */
593
594 /* -& */
595
596 /* SPICELIB functions */
597
598
599 /* Local parameters */
600
601
602 /* Local variables */
603
604
605 /* Saved variables */
606
607
608 /* Initial values */
609
610
611 /* Use discovery check-in in this puppy. */
612
613 /* Nothing found to begin with. */
614
615 found = FALSE_;
616 if (first) {
617
618 /* Find out the access method for the current file. */
619
620 dasham_(handle, access, (ftnlen)15);
621 rdonly = s_cmp(access, "READ", (ftnlen)15, (ftnlen)4) == 0;
622 samkey = FALSE_;
623 samtre = FALSE_;
624 leaf = FALSE_;
625 first = FALSE_;
626 } else {
627
628 /* See whether we're looking at the same key, or at least */
629 /* the same tree, as last time. Note that for the tree to */
630 /* be guaranteed to be the same, it must belong to a file open */
631 /* for read access only. */
632
633 if (*handle != oldhan) {
634 dasham_(handle, access, (ftnlen)15);
635 rdonly = s_cmp(access, "READ", (ftnlen)15, (ftnlen)4) == 0;
636 samtre = FALSE_;
637 samkey = FALSE_;
638 } else {
639 samtre = *tree == oldtre && rdonly;
640 samkey = *key == oldkey && samtre;
641 }
642 }
643
644 /* If we're lucky enough to be getting a request for the previously */
645 /* returned key, we're set. If we've been asked for a key that is */
646 /* very close to the previously requested key, we still may make */
647 /* out pretty well. */
648
649 if (samkey) {
650
651 /* It's the same key as last time. */
652
653 *idx = oldidx;
654 *node = oldnod;
655 *noffst = oldnof;
656 *level = oldlvl;
657 *value = oldval;
658 return 0;
659 } else if (samtre && leaf) {
660
661 /* Compute the margins around the old key. Keys that fall within */
662 /* the interval defined by the old key and these margins are on */
663 /* the same page as the old key. */
664
665 plus = oldmax - oldidx;
666 minus = oldidx - 1;
667 if (*key <= oldkey + plus && *key >= oldkey - minus) {
668
669 /* The requested key lies on the same page as the old key. */
670
671 *level = oldlvl;
672 if (*level == 1) {
673 datbas = 172;
674 } else {
675 datbas = 128;
676 }
677 *idx = oldidx + (*key - oldkey);
678 *node = oldnod;
679 *noffst = oldnof;
680 *value = page[(i__1 = datbas + *idx - 1) < 256 && 0 <= i__1 ?
681 i__1 : s_rnge("page", i__1, "zzektrlk_", (ftnlen)332)];
682 oldidx = *idx;
683 oldkey = *key;
684 oldval = *value;
685 return 0;
686 }
687 }
688
689 /* If we arrived here, we have some actual work to do. */
690 /* Start out by looking at the root page. Save the tree depth; */
691 /* we'll use this for error checking. */
692
693 zzekpgri_(handle, tree, page);
694 depth = page[3];
695 *level = 1;
696
697 /* Find out how many keys are in the tree. If KEY is outside */
698 /* this range, we won't find it. */
699
700 totkey = page[2];
701 if (*key < 1 || *key > totkey) {
702 chkin_("ZZEKTRLK", (ftnlen)8);
703 setmsg_("Key = #; valid range = 1:#. Tree = #, file = #", (ftnlen)46);
704 errint_("#", key, (ftnlen)1);
705 errint_("#", &totkey, (ftnlen)1);
706 errint_("#", tree, (ftnlen)1);
707 errhan_("#", handle, (ftnlen)1);
708 sigerr_("SPICE(INDEXOUTOFRANGE)", (ftnlen)22);
709 chkout_("ZZEKTRLK", (ftnlen)8);
710 return 0;
711 }
712
713 /* Find the last key at this level that is less than or equal to */
714 /* the requested key. */
715
716 prev = lstlei_(key, &page[4], &page[5]);
717 if (prev > 0) {
718 prvkey = page[(i__1 = prev + 4) < 256 && 0 <= i__1 ? i__1 : s_rnge(
719 "page", i__1, "zzektrlk_", (ftnlen)381)];
720 } else {
721 prvkey = 0;
722 }
723
724 /* If we were lucky enough to get an exact match, set our outputs */
725 /* and return. The key offset in the root is zero. */
726
727 if (prvkey == *key) {
728 *noffst = 0;
729 *idx = prev;
730 *node = *tree;
731 *value = page[(i__1 = *idx + 171) < 256 && 0 <= i__1 ? i__1 : s_rnge(
732 "page", i__1, "zzektrlk_", (ftnlen)395)];
733 oldhan = *handle;
734 oldtre = *tree;
735 oldkey = *key;
736 oldnof = *noffst;
737 oldnod = *node;
738 oldidx = *idx;
739 oldlvl = *level;
740 oldval = *value;
741 oldmax = page[4];
742 leaf = *level == depth;
743
744 /* The root has no parent or siblings, so these values */
745 /* remain set to zero. The same is true of the parent keys. */
746
747 return 0;
748 }
749
750 /* Still here? Traverse the pointer path until we find the key */
751 /* or run out of progeny. */
752
753 child = page[(i__1 = prev + 88) < 256 && 0 <= i__1 ? i__1 : s_rnge("page",
754 i__1, "zzektrlk_", (ftnlen)421)];
755 *noffst = prvkey;
756 while(child > 0 && ! found) {
757
758 /* Look up the child node. */
759
760 zzekpgri_(handle, &child, page);
761 ++(*level);
762 if (*level > depth) {
763 chkin_("ZZEKTRLK", (ftnlen)8);
764 setmsg_("Runaway node pointer chain. Key = #; valid range = 1:#"
765 ". Tree = #, file = #", (ftnlen)75);
766 errint_("#", key, (ftnlen)1);
767 errint_("#", &totkey, (ftnlen)1);
768 errint_("#", tree, (ftnlen)1);
769 errhan_("#", handle, (ftnlen)1);
770 sigerr_("SPICE(BUG)", (ftnlen)10);
771 chkout_("ZZEKTRLK", (ftnlen)8);
772 return 0;
773 }
774
775 /* Find the last key at this level that is less than or equal to */
776 /* the requested key. Since the keys we're looking at now are */
777 /* ordinal positions relative to the subtree whose root is the */
778 /* current node, we must subtract from KEY the position of the */
779 /* node preceding the first key of this subtree. */
780
781 newkey = *key - *noffst;
782 prev = lstlei_(&newkey, page, &page[1]);
783 if (prev > 0) {
784 prvkey = page[(i__1 = prev) < 256 && 0 <= i__1 ? i__1 : s_rnge(
785 "page", i__1, "zzektrlk_", (ftnlen)460)];
786 } else {
787 prvkey = 0;
788 }
789
790 /* If we were lucky enough to get an exact match, set our outputs */
791 /* and return. The key offset for the current node is stored */
792 /* in NOFFST. */
793
794 if (prvkey == newkey) {
795 found = TRUE_;
796 *idx = prev;
797 *node = child;
798 *value = page[(i__1 = *idx + 127) < 256 && 0 <= i__1 ? i__1 :
799 s_rnge("page", i__1, "zzektrlk_", (ftnlen)475)];
800 oldhan = *handle;
801 oldtre = *tree;
802 oldkey = *key;
803 oldnof = *noffst;
804 oldnod = *node;
805 oldidx = *idx;
806 oldlvl = *level;
807 oldval = *value;
808 oldmax = page[0];
809 leaf = *level == depth;
810 } else {
811 child = page[(i__1 = prev + 64) < 256 && 0 <= i__1 ? i__1 :
812 s_rnge("page", i__1, "zzektrlk_", (ftnlen)491)];
813 *noffst = prvkey + *noffst;
814 }
815 }
816
817 /* If we found the key, our outputs are already set. If not, we've */
818 /* got trouble. */
819
820 if (! found) {
821 chkin_("ZZEKTRLK", (ftnlen)8);
822 setmsg_("Key #; valid range = 1:#. Tree = #, file = #. Key was not "
823 "found. This probably indicates a corrupted file or a bug in"
824 " the EK code.", (ftnlen)132);
825 errint_("#", key, (ftnlen)1);
826 errint_("#", &totkey, (ftnlen)1);
827 errint_("#", tree, (ftnlen)1);
828 errhan_("#", handle, (ftnlen)1);
829 sigerr_("SPICE(BUG)", (ftnlen)10);
830 chkout_("ZZEKTRLK", (ftnlen)8);
831 return 0;
832 }
833 return 0;
834 } /* zzektrlk_ */
835
836