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_get.c 5.4 (Berkeley) 09/12/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <errno.h> 17 #include <db.h> 18 #include <stdio.h> 19 #include <stddef.h> 20 #include "btree.h" 21 22 /* 23 * __BT_GET -- Get a record from the btree. 24 * 25 * Parameters: 26 * dbp: pointer to access method 27 * key: key to find 28 * data: data to return 29 * flag: currently unused 30 * 31 * Returns: 32 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 33 */ 34 int 35 __bt_get(dbp, key, data, flags) 36 const DB *dbp; 37 const DBT *key; 38 DBT *data; 39 u_int flags; 40 { 41 BTREE *t; 42 EPG *e; 43 int exact, status; 44 45 if (flags) { 46 errno = EINVAL; 47 return (RET_ERROR); 48 } 49 t = dbp->internal; 50 if ((e = __bt_search(t, key, &exact)) == NULL) 51 return (RET_ERROR); 52 if (!exact) { 53 mpool_put(t->bt_mp, e->page, 0); 54 return (RET_SPECIAL); 55 } 56 57 /* 58 * A special case is if we found the record but it's flagged for 59 * deletion. In this case, we want to find another record with the 60 * same key, if it exists. Rather than look around the tree we call 61 * __bt_first and have it redo the search, as __bt_first will not 62 * return keys marked for deletion. Slow, but should never happen. 63 */ 64 if (ISSET(t, BTF_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno && 65 e->index == t->bt_bcursor.index) { 66 mpool_put(t->bt_mp, e->page, 0); 67 if ((e = __bt_first(t, key, &exact)) == NULL) 68 return (RET_ERROR); 69 if (!exact) 70 return (RET_SPECIAL); 71 } 72 73 status = __bt_ret(t, e, NULL, data); 74 mpool_put(t->bt_mp, e->page, 0); 75 return (status); 76 } 77 78 /* 79 * __BT_FIRST -- Find the first entry. 80 * 81 * Parameters: 82 * t: the tree 83 * key: the key 84 * 85 * Returns: 86 * The first entry in the tree greater than or equal to key. 87 */ 88 EPG * 89 __bt_first(t, key, exactp) 90 BTREE *t; 91 const DBT *key; 92 int *exactp; 93 { 94 register PAGE *h; 95 register EPG *e; 96 EPG save; 97 pgno_t cpgno, pg; 98 index_t cindex; 99 int found; 100 101 /* 102 * Find any matching record; __bt_search pins the page. Only exact 103 * matches are tricky, otherwise just return the location of the key 104 * if it were to be inserted into the tree. 105 */ 106 if ((e = __bt_search(t, key, exactp)) == NULL) 107 return (NULL); 108 if (!*exactp) 109 return (e); 110 111 if (ISSET(t, BTF_DELCRSR)) { 112 cpgno = t->bt_bcursor.pgno; 113 cindex = t->bt_bcursor.index; 114 } else 115 cpgno = P_INVALID; 116 117 /* 118 * Walk backwards, skipping empty pages, as long as the entry matches 119 * and there are keys left in the tree. Save a copy of each match in 120 * case we go too far. A special case is that we don't return a match 121 * on records that the cursor references that have already been flagged 122 * for deletion. 123 */ 124 save = *e; 125 h = e->page; 126 found = 0; 127 do { 128 if (cpgno != h->pgno || cindex != e->index) { 129 if (save.page->pgno != e->page->pgno) { 130 mpool_put(t->bt_mp, save.page, 0); 131 save = *e; 132 } else 133 save.index = e->index; 134 found = 1; 135 } 136 /* 137 * Make a special effort not to unpin the page the last (or 138 * original) match was on, but also make sure it's unpinned 139 * if an error occurs. 140 */ 141 if (e->index == 0) 142 do { 143 if (h->prevpg == P_INVALID) 144 goto done1; 145 if (h->pgno != save.page->pgno) 146 mpool_put(t->bt_mp, h, 0); 147 if ((h = mpool_get(t->bt_mp, 148 h->prevpg, 0)) == NULL) { 149 if (h->pgno == save.page->pgno) 150 mpool_put(t->bt_mp, 151 save.page, 0); 152 return (NULL); 153 } 154 } while ((e->index = NEXTINDEX(h)) == 0); 155 --e->index; 156 } while (__bt_cmp(t, key, e) == 0); 157 158 /* 159 * Reach here with the last page that was looked at pinned, which may 160 * or may not be the same as the last (or original) match page. If 161 * it's not useful, release it. 162 */ 163 done1: if (h->pgno != save.page->pgno) 164 mpool_put(t->bt_mp, h, 0); 165 166 /* 167 * If still haven't found a record, the only possibility left is the 168 * next one. Move forward one slot, skipping empty pages and check. 169 */ 170 if (!found) { 171 h = save.page; 172 if (++save.index == NEXTINDEX(h)) { 173 do { 174 pg = h->nextpg; 175 mpool_put(t->bt_mp, h, 0); 176 if (pg == P_INVALID) { 177 *exactp = 0; 178 return (e); 179 } 180 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 181 return (NULL); 182 } while ((save.index = NEXTINDEX(h)) == 0); 183 save.page = h; 184 } 185 if (__bt_cmp(t, key, &save) != 0) { 186 *exactp = 0; 187 return (e); 188 } 189 } 190 *e = save; 191 *exactp = 1; 192 return (e); 193 } 194