1 /*- 2 * Copyright (c) 1990, 1993 3 * The Regents of the University of California. 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) 12 static char sccsid[] = "@(#)bt_search.c 8.6 (Berkeley) 03/15/94"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 17 #include <stdio.h> 18 19 #include <db.h> 20 #include "btree.h" 21 22 static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); 23 static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); 24 25 /* 26 * __BT_SEARCH -- Search a btree for a key. 27 * 28 * Parameters: 29 * t: tree to search 30 * key: key to find 31 * exactp: pointer to exact match flag 32 * 33 * Returns: 34 * The EPG for matching record, if any, or the EPG for the location 35 * of the key, if it were inserted into the tree, is entered into 36 * the bt_cur field of the tree. A pointer to the field is returned. 37 */ 38 EPG * 39 __bt_search(t, key, exactp) 40 BTREE *t; 41 const DBT *key; 42 int *exactp; 43 { 44 PAGE *h; 45 indx_t base, index, lim; 46 pgno_t pg; 47 int cmp; 48 49 BT_CLR(t); 50 for (pg = P_ROOT;;) { 51 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 52 return (NULL); 53 54 /* Do a binary search on the current page. */ 55 t->bt_cur.page = h; 56 for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { 57 t->bt_cur.index = index = base + (lim >> 1); 58 if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { 59 if (h->flags & P_BLEAF) { 60 *exactp = 1; 61 return (&t->bt_cur); 62 } 63 goto next; 64 } 65 if (cmp > 0) { 66 base = index + 1; 67 --lim; 68 } 69 } 70 71 /* 72 * If it's a leaf page, and duplicates aren't allowed, we're 73 * done. If duplicates are allowed, it's possible that there 74 * were duplicate keys on duplicate pages, and they were later 75 * deleted, so we could be on a page with no matches while 76 * there are matches on other pages. If we're at the start or 77 * end of a page, check on both sides. 78 */ 79 if (h->flags & P_BLEAF) { 80 t->bt_cur.index = base; 81 *exactp = 0; 82 if (!ISSET(t, B_NODUPS)) { 83 if (base == 0 && 84 bt_sprev(t, h, key, exactp)) 85 return (&t->bt_cur); 86 if (base == NEXTINDEX(h) && 87 bt_snext(t, h, key, exactp)) 88 return (&t->bt_cur); 89 } 90 return (&t->bt_cur); 91 } 92 93 /* 94 * No match found. Base is the smallest index greater than 95 * key and may be zero or a last + 1 index. If it's non-zero, 96 * decrement by one, and record the internal page which should 97 * be a parent page for the key. If a split later occurs, the 98 * inserted page will be to the right of the saved page. 99 */ 100 index = base ? base - 1 : base; 101 102 next: if (__bt_push(t, h->pgno, index) == RET_ERROR) 103 return (NULL); 104 pg = GETBINTERNAL(h, index)->pgno; 105 mpool_put(t->bt_mp, h, 0); 106 } 107 } 108 109 /* 110 * BT_SNEXT -- Check for an exact match after the key. 111 * 112 * Parameters: 113 * t: tree to search 114 * h: current page. 115 * key: key to find 116 * exactp: pointer to exact match flag 117 * 118 * Returns: 119 * If an exact match found. 120 */ 121 static int 122 bt_snext(t, h, key, exactp) 123 BTREE *t; 124 PAGE *h; 125 const DBT *key; 126 int *exactp; 127 { 128 EPG e; 129 PAGE *tp; 130 pgno_t pg; 131 132 /* Skip until reach the end of the tree or a key. */ 133 for (pg = h->nextpg; pg != P_INVALID;) { 134 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { 135 mpool_put(t->bt_mp, h, 0); 136 return (NULL); 137 } 138 if (NEXTINDEX(tp) != 0) 139 break; 140 pg = tp->prevpg; 141 mpool_put(t->bt_mp, tp, 0); 142 } 143 /* 144 * The key is either an exact match, or not as good as 145 * the one we already have. 146 */ 147 if (pg != P_INVALID) { 148 e.page = tp; 149 e.index = NEXTINDEX(tp) - 1; 150 if (__bt_cmp(t, key, &e) == 0) { 151 mpool_put(t->bt_mp, h, 0); 152 t->bt_cur = e; 153 *exactp = 1; 154 return (1); 155 } 156 } 157 return (0); 158 } 159 160 /* 161 * BT_SPREV -- Check for an exact match before the key. 162 * 163 * Parameters: 164 * t: tree to search 165 * h: current page. 166 * key: key to find 167 * exactp: pointer to exact match flag 168 * 169 * Returns: 170 * If an exact match found. 171 */ 172 static int 173 bt_sprev(t, h, key, exactp) 174 BTREE *t; 175 PAGE *h; 176 const DBT *key; 177 int *exactp; 178 { 179 EPG e; 180 PAGE *tp; 181 pgno_t pg; 182 183 /* Skip until reach the beginning of the tree or a key. */ 184 for (pg = h->prevpg; pg != P_INVALID;) { 185 if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { 186 mpool_put(t->bt_mp, h, 0); 187 return (NULL); 188 } 189 if (NEXTINDEX(tp) != 0) 190 break; 191 pg = tp->prevpg; 192 mpool_put(t->bt_mp, tp, 0); 193 } 194 /* 195 * The key is either an exact match, or not as good as 196 * the one we already have. 197 */ 198 if (pg != P_INVALID) { 199 e.page = tp; 200 e.index = NEXTINDEX(tp) - 1; 201 if (__bt_cmp(t, key, &e) == 0) { 202 mpool_put(t->bt_mp, h, 0); 203 t->bt_cur = e; 204 *exactp = 1; 205 return (1); 206 } 207 } 208 return (0); 209 } 210