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.3 (Berkeley) 09/04/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 DBT *key, *data; 38 u_int flags; 39 { 40 BTREE *t; 41 EPG *e; 42 int exact, status; 43 44 if (flags) { 45 errno = EINVAL; 46 return (RET_ERROR); 47 } 48 t = dbp->internal; 49 if ((e = __bt_search(t, key, &exact)) == NULL) 50 return (RET_ERROR); 51 if (!exact) { 52 mpool_put(t->bt_mp, e->page, 0); 53 return (RET_SPECIAL); 54 } 55 56 /* 57 * A special case is if we found the record but it's flagged for 58 * deletion. In this case, we want to find another record with the 59 * same key, if it exists. Rather than look around the tree we call 60 * __bt_first and have it redo the search as __bt_first will not 61 * return keys marked for deletion. Slow, but should never happen. 62 */ 63 if (ISSET(t, BTF_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno && 64 e->index == t->bt_bcursor.index) { 65 mpool_put(t->bt_mp, e->page, 0); 66 if ((e = __bt_first(t, key, &exact)) == NULL) 67 return (RET_ERROR); 68 if (!exact) 69 return (RET_SPECIAL); 70 } 71 72 status = __bt_ret(t, e, data, key); 73 mpool_put(t->bt_mp, e->page, 0); 74 return (status); 75 } 76 77 /* 78 * __BT_FIRST -- Find the first record in the tree matching the key. 79 * 80 * Parameters: 81 * t: the tree 82 * key: the key 83 * 84 * Returns: 85 * The first matching record. 86 */ 87 EPG * 88 __bt_first(t, key, exactp) 89 BTREE *t; 90 DBT *key; 91 int *exactp; 92 { 93 register PAGE *h; 94 register EPG *e; 95 EPG save; 96 pgno_t cpgno, pg; 97 index_t cindex; 98 int found; 99 100 /* 101 * Find any matching record; __bt_search pins the page. Only exact 102 * matches are interesting. 103 */ 104 if ((e = __bt_search(t, key, exactp)) == NULL) 105 return (NULL); 106 if (!*exactp) { 107 mpool_put(t->bt_mp, e->page, 0); 108 return (e); 109 } 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