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) 12 static char sccsid[] = "@(#)bt_search.c 5.1 (Berkeley) 01/23/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <db.h> 17 #include "btree.h" 18 19 /* 20 * _BT_FIRST -- Find the first item in the tree that matches the supplied 21 * key. 22 * 23 * This routine supports deletion. When the user supplies a key to 24 * be deleted, we find the first one, and iteratively delete all the 25 * matching ones that follow it. 26 * 27 * Parameters: 28 * t -- btree in which to find first occurrence 29 * key -- key to find 30 * 31 * Returns: 32 * The BTITEM for the matching item. If there's no match, 33 * this may point to the first item > than the supplied key, 34 * or off the end of the page. 35 * 36 * Warnings: 37 * The BTITEM returned is in static space and will be overwritten 38 * by the next search of any kind in any btree. 39 */ 40 41 BTITEM * 42 _bt_first(t, key) 43 BTREE_P t; 44 DBT *key; 45 { 46 BTHEADER *h; 47 BTITEM *item; 48 index_t next; 49 int r; 50 51 /* find any matching item */ 52 item = _bt_search(t, key); 53 h = t->bt_curpage; 54 next = NEXTINDEX(h); 55 56 /* if we're off the end of the page, search failed and we're done */ 57 if (item->bti_index >= next) 58 return (item); 59 60 /* as long as we have an exact match, walk backwards */ 61 while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) { 62 63 /* at start of page? */ 64 if (item->bti_index == 0) { 65 66 /* if no prev page, we're done */ 67 if (h->h_prevpg == P_NONE) 68 return (item); 69 70 /* walk backward, skipping empty pages */ 71 do { 72 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR) 73 return ((BTITEM *) NULL); 74 h = t->bt_curpage; 75 } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE); 76 77 if (NEXTINDEX(h) != 0) 78 item->bti_index = NEXTINDEX(h) - 1; 79 else 80 item->bti_index = 0; 81 82 item->bti_pgno = h->h_pgno; 83 } else { 84 item->bti_index--; 85 } 86 } 87 88 /* if we went too far backwards, step forward one entry */ 89 if (r > 0) { 90 if (++(item->bti_index) >= NEXTINDEX(h) 91 && h->h_nextpg != P_NONE) { 92 93 /* walk forward, skipping empty pages */ 94 do { 95 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) 96 return ((BTITEM *) NULL); 97 h = t->bt_curpage; 98 } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0); 99 100 item->bti_index = 0; 101 item->bti_pgno = h->h_pgno; 102 } 103 } 104 105 /* got it */ 106 return (item); 107 } 108 109 /* 110 * _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree. 111 * 112 * Parameters: 113 * t -- btree in which to search 114 * key -- key to find 115 * 116 * Returns: 117 * BTITEM for matching item, if any, or the BTITEM for the 118 * location of the key, if it were in the tree. 119 * 120 * Warnings: 121 * The BTITEM returned is in static memory, and will be 122 * overwritten by the next search of any kind in any tree. 123 */ 124 125 BTITEM * 126 _bt_search(t, key) 127 BTREE_P t; 128 DBT *key; 129 { 130 /* we want to start all of our searches at the root */ 131 if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR) 132 return ((BTITEM *) NULL); 133 134 return (_bt_searchr(t, key)); 135 } 136 137 BTITEM * 138 _bt_searchr(t, key) 139 BTREE_P t; 140 DBT *key; 141 { 142 BTHEADER *h = t->bt_curpage; 143 index_t index; 144 IDATUM *id; 145 DATUM *d; 146 static BTITEM item; 147 148 /* do a binary search on the current page */ 149 index = _bt_binsrch(t, &(key->data[0])); 150 151 /* 152 * At this point, the binary search terminated because the endpoints 153 * got too close together, or we have a match. Figure out which 154 * case applies and decide what to do based on the page type. 155 */ 156 if (h->h_flags & F_LEAF) { 157 item.bti_pgno = h->h_pgno; 158 item.bti_index = index; 159 if (index < NEXTINDEX(h)) 160 d = (DATUM *) GETDATUM(h,index); 161 else 162 d = (DATUM *) NULL; 163 164 item.bti_datum = d; 165 return(&item); 166 } else { 167 id = (IDATUM *) GETDATUM(h, index); 168 if (_bt_push(t, h->h_pgno) == RET_ERROR) 169 return ((BTITEM *) NULL); 170 if (_bt_getpage(t, id->i_pgno) == RET_ERROR) 171 return ((BTITEM *) NULL); 172 return (_bt_searchr(t, key)); 173 } 174 } 175 176 /* 177 * _BT_BINSRCH -- Do a binary search for a given key on the current page. 178 * 179 * Searches on internal pages are handled slightly differently from 180 * searches on leaf pages. This is because internal page searches 181 * find the largest item <= key in the tree, and leaf searches find 182 * the smallest item >= key. This guarantees that leaf page searches 183 * leave us pointing at the item's correct position, and internal 184 * searches descend the tree correctly. 185 * 186 * Parameters: 187 * t -- tree to search 188 * key -- key we're looking for 189 * 190 * Returns: 191 * Index of the line pointer array entry for the (closest) 192 * match to key on the current page, with "closest" as defined 193 * above. 194 */ 195 196 index_t 197 _bt_binsrch(t, key) 198 BTREE_P t; 199 char *key; 200 { 201 index_t lbound, ubound, cur; 202 BTHEADER *h = t->bt_curpage; 203 int match = 0; 204 int r; 205 206 lbound = 0; 207 ubound = NEXTINDEX(h); 208 if (ubound > 0) 209 --ubound; 210 211 /* do a binary search on the current page */ 212 while ((ubound - lbound) > 1) { 213 cur = lbound + ((ubound - lbound) / 2); 214 r = _bt_cmp(t, key, cur); 215 216 if (r > 0) 217 lbound = cur + 1; 218 else if (r < 0) 219 ubound = cur; 220 else { 221 match++; 222 break; 223 } 224 } 225 226 /* 227 * At this point, the binary search terminated because the endpoints 228 * got too close together, or we have a match. Figure out which 229 * case applies, decide what to do based on the page type (leaf or 230 * internal), and do the right thing. 231 */ 232 if (match) { 233 return (cur); 234 } else if (ubound != lbound) { 235 if (h->h_flags & F_LEAF) { 236 r = _bt_cmp(t, key, lbound); 237 if (r <= 0) { 238 return (lbound); 239 } 240 } else { 241 r = _bt_cmp(t, key, ubound); 242 243 /* for internal nodes, move as far left as possible */ 244 if (r < 0) { 245 r = _bt_cmp(t, key, lbound); 246 if (r < 0 && lbound > 0) 247 --lbound; 248 return (lbound); 249 } else { 250 return (ubound); 251 } 252 } 253 } 254 255 if (h->h_flags & F_LEAF) { 256 if (ubound < NEXTINDEX(h)) { 257 r = _bt_cmp(t, key, ubound); 258 if (r > 0) 259 ubound++; 260 } 261 } else { 262 /* for internal pages, move as far left as possible */ 263 if (ubound == NEXTINDEX(h)) 264 ubound--; 265 266 while (_bt_cmp(t, key, ubound) < 0) 267 ubound--; 268 } 269 return (ubound); 270 } 271