Commit | Line | Data |
---|---|---|
45b53c4e MO |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Mike Olson. | |
7 | * | |
8 | * %sccs.include.redist.c% | |
9 | */ | |
10 | ||
11 | #if defined(LIBC_SCCS) && !defined(lint) | |
491176fb | 12 | static char sccsid[] = "@(#)bt_search.c 5.9 (Berkeley) %G%"; |
45b53c4e MO |
13 | #endif /* LIBC_SCCS and not lint */ |
14 | ||
15 | #include <sys/types.h> | |
9f252354 | 16 | |
91b5c9e5 | 17 | #include <stdio.h> |
9f252354 | 18 | |
94ac72c5 | 19 | #include <db.h> |
45b53c4e MO |
20 | #include "btree.h" |
21 | ||
22 | /* | |
91b5c9e5 | 23 | * __BT_SEARCH -- Search a btree for a key. |
45b53c4e | 24 | * |
91b5c9e5 KB |
25 | * Parameters: |
26 | * t: tree to search | |
27 | * key: key to find | |
28 | * exactp: pointer to exact match flag | |
45b53c4e | 29 | * |
91b5c9e5 KB |
30 | * Returns: |
31 | * EPG for matching record, if any, or the EPG for the location of the | |
32 | * key, if it were inserted into the tree. | |
45b53c4e | 33 | * |
91b5c9e5 KB |
34 | * Warnings: |
35 | * The EPG returned is in static memory, and will be overwritten by the | |
36 | * next search of any kind in any tree. | |
45b53c4e | 37 | */ |
91b5c9e5 KB |
38 | EPG * |
39 | __bt_search(t, key, exactp) | |
40 | BTREE *t; | |
41 | const DBT *key; | |
42 | int *exactp; | |
45b53c4e | 43 | { |
491176fb | 44 | register indx_t index; |
91b5c9e5 KB |
45 | register int base, cmp, lim; |
46 | register PAGE *h; | |
47 | pgno_t pg; | |
48 | static EPG e; | |
49 | ||
5e370e87 | 50 | BT_CLR(t); |
91b5c9e5 KB |
51 | for (pg = P_ROOT;;) { |
52 | if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) | |
53 | return (NULL); | |
54 | ||
55 | /* Do a binary search on the current page. */ | |
56 | e.page = h; | |
57 | for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { | |
58 | e.index = index = base + (lim >> 1); | |
59 | if ((cmp = __bt_cmp(t, key, &e)) == 0) { | |
60 | if (h->flags & P_BLEAF) { | |
61 | *exactp = 1; | |
62 | return (&e); | |
63 | } | |
64 | goto next; | |
45b53c4e | 65 | } |
91b5c9e5 KB |
66 | if (cmp > 0) { |
67 | base = index + 1; | |
68 | --lim; | |
45b53c4e MO |
69 | } |
70 | } | |
45b53c4e | 71 | |
91b5c9e5 KB |
72 | /* If it's a leaf page, we're done. */ |
73 | if (h->flags & P_BLEAF) { | |
f94169b2 | 74 | e.index = base; |
91b5c9e5 KB |
75 | *exactp = 0; |
76 | return (&e); | |
45b53c4e | 77 | } |
45b53c4e | 78 | |
f94169b2 KB |
79 | /* |
80 | * No match found. Base is the smallest index greater than | |
81 | * key and may be zero or a last + 1 index. If it's non-zero, | |
82 | * decrement by one, and record the internal page which should | |
83 | * be a parent page for the key. If a split later occurs, the | |
84 | * inserted page will be to the right of the saved page. | |
85 | */ | |
86 | index = base ? base - 1 : base; | |
87 | ||
84290f7c | 88 | next: if (__bt_push(t, h->pgno, index) == RET_ERROR) |
91b5c9e5 KB |
89 | return (NULL); |
90 | pg = GETBINTERNAL(h, index)->pgno; | |
91 | mpool_put(t->bt_mp, h, 0); | |
45b53c4e | 92 | } |
45b53c4e | 93 | } |