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 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #if defined(LIBC_SCCS) && !defined(lint) 38 static char sccsid[] = "@(#)bt_get.c 8.1 (Berkeley) 6/4/93"; 39 #endif /* LIBC_SCCS and not lint */ 40 41 #include <sys/types.h> 42 43 #include <errno.h> 44 #include <stddef.h> 45 #include <stdio.h> 46 47 #include <db.h> 48 #include "btree.h" 49 50 /* 51 * __BT_GET -- Get a record from the btree. 52 * 53 * Parameters: 54 * dbp: pointer to access method 55 * key: key to find 56 * data: data to return 57 * flag: currently unused 58 * 59 * Returns: 60 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 61 */ 62 int 63 __bt_get(dbp, key, data, flags) 64 const DB *dbp; 65 const DBT *key; 66 DBT *data; 67 u_int flags; 68 { 69 BTREE *t; 70 EPG *e; 71 int exact, status; 72 73 if (flags) { 74 errno = EINVAL; 75 return (RET_ERROR); 76 } 77 t = dbp->internal; 78 if ((e = __bt_search(t, key, &exact)) == NULL) 79 return (RET_ERROR); 80 if (!exact) { 81 mpool_put(t->bt_mp, e->page, 0); 82 return (RET_SPECIAL); 83 } 84 85 /* 86 * A special case is if we found the record but it's flagged for 87 * deletion. In this case, we want to find another record with the 88 * same key, if it exists. Rather than look around the tree we call 89 * __bt_first and have it redo the search, as __bt_first will not 90 * return keys marked for deletion. Slow, but should never happen. 91 */ 92 if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno && 93 e->index == t->bt_bcursor.index) { 94 mpool_put(t->bt_mp, e->page, 0); 95 if ((e = __bt_first(t, key, &exact)) == NULL) 96 return (RET_ERROR); 97 if (!exact) 98 return (RET_SPECIAL); 99 } 100 101 status = __bt_ret(t, e, NULL, data); 102 mpool_put(t->bt_mp, e->page, 0); 103 return (status); 104 } 105 106 /* 107 * __BT_FIRST -- Find the first entry. 108 * 109 * Parameters: 110 * t: the tree 111 * key: the key 112 * 113 * Returns: 114 * The first entry in the tree greater than or equal to key. 115 */ 116 EPG * 117 __bt_first(t, key, exactp) 118 BTREE *t; 119 const DBT *key; 120 int *exactp; 121 { 122 register PAGE *h; 123 register EPG *e; 124 EPG save; 125 pgno_t cpgno, pg; 126 indx_t cindex; 127 int found; 128 129 /* 130 * Find any matching record; __bt_search pins the page. Only exact 131 * matches are tricky, otherwise just return the location of the key 132 * if it were to be inserted into the tree. 133 */ 134 if ((e = __bt_search(t, key, exactp)) == NULL) 135 return (NULL); 136 if (!*exactp) 137 return (e); 138 139 if (ISSET(t, B_DELCRSR)) { 140 cpgno = t->bt_bcursor.pgno; 141 cindex = t->bt_bcursor.index; 142 } else { 143 cpgno = P_INVALID; 144 cindex = 0; /* GCC thinks it's uninitialized. */ 145 } 146 147 /* 148 * Walk backwards, skipping empty pages, as long as the entry matches 149 * and there are keys left in the tree. Save a copy of each match in 150 * case we go too far. A special case is that we don't return a match 151 * on records that the cursor references that have already been flagged 152 * for deletion. 153 */ 154 save = *e; 155 h = e->page; 156 found = 0; 157 do { 158 if (cpgno != h->pgno || cindex != e->index) { 159 if (save.page->pgno != e->page->pgno) { 160 mpool_put(t->bt_mp, save.page, 0); 161 save = *e; 162 } else 163 save.index = e->index; 164 found = 1; 165 } 166 /* 167 * Make a special effort not to unpin the page the last (or 168 * original) match was on, but also make sure it's unpinned 169 * if an error occurs. 170 */ 171 while (e->index == 0) { 172 if (h->prevpg == P_INVALID) 173 goto done1; 174 if (h->pgno != save.page->pgno) 175 mpool_put(t->bt_mp, h, 0); 176 if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) { 177 if (h->pgno == save.page->pgno) 178 mpool_put(t->bt_mp, save.page, 0); 179 return (NULL); 180 } 181 e->page = h; 182 e->index = NEXTINDEX(h); 183 } 184 --e->index; 185 } while (__bt_cmp(t, key, e) == 0); 186 187 /* 188 * Reach here with the last page that was looked at pinned, which may 189 * or may not be the same as the last (or original) match page. If 190 * it's not useful, release it. 191 */ 192 done1: if (h->pgno != save.page->pgno) 193 mpool_put(t->bt_mp, h, 0); 194 195 /* 196 * If still haven't found a record, the only possibility left is the 197 * next one. Move forward one slot, skipping empty pages and check. 198 */ 199 if (!found) { 200 h = save.page; 201 if (++save.index == NEXTINDEX(h)) { 202 do { 203 pg = h->nextpg; 204 mpool_put(t->bt_mp, h, 0); 205 if (pg == P_INVALID) { 206 *exactp = 0; 207 return (e); 208 } 209 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 210 return (NULL); 211 } while ((save.index = NEXTINDEX(h)) == 0); 212 save.page = h; 213 } 214 if (__bt_cmp(t, key, &save) != 0) { 215 *exactp = 0; 216 return (e); 217 } 218 } 219 *e = save; 220 *exactp = 1; 221 return (e); 222 } 223