1 /* $NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Mike Olson. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #if defined(LIBC_SCCS) && !defined(lint) 40 #if 0 41 static char sccsid[] = "@(#)bt_seq.c 8.2 (Berkeley) 9/7/93"; 42 #else 43 static char rcsid[] = "$NetBSD: bt_seq.c,v 1.6 1995/02/27 13:20:51 cgd Exp $"; 44 #endif 45 #endif /* LIBC_SCCS and not lint */ 46 47 #include <sys/types.h> 48 49 #include <errno.h> 50 #include <stddef.h> 51 #include <stdio.h> 52 #include <stdlib.h> 53 54 #include <db.h> 55 #include "btree.h" 56 57 static int bt_seqadv __P((BTREE *, EPG *, int)); 58 static int bt_seqset __P((BTREE *, EPG *, DBT *, int)); 59 60 /* 61 * Sequential scan support. 62 * 63 * The tree can be scanned sequentially, starting from either end of the tree 64 * or from any specific key. A scan request before any scanning is done is 65 * initialized as starting from the least node. 66 * 67 * Each tree has an EPGNO which has the current position of the cursor. The 68 * cursor has to survive deletions/insertions in the tree without losing its 69 * position. This is done by noting deletions without doing them, and then 70 * doing them when the cursor moves (or the tree is closed). 71 */ 72 73 /* 74 * __BT_SEQ -- Btree sequential scan interface. 75 * 76 * Parameters: 77 * dbp: pointer to access method 78 * key: key for positioning and return value 79 * data: data return value 80 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV. 81 * 82 * Returns: 83 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 84 */ 85 int 86 __bt_seq(dbp, key, data, flags) 87 const DB *dbp; 88 DBT *key, *data; 89 u_int flags; 90 { 91 BTREE *t; 92 EPG e; 93 int status; 94 95 t = dbp->internal; 96 97 /* Toss any page pinned across calls. */ 98 if (t->bt_pinned != NULL) { 99 mpool_put(t->bt_mp, t->bt_pinned, 0); 100 t->bt_pinned = NULL; 101 } 102 103 /* 104 * If scan unitialized as yet, or starting at a specific record, set 105 * the scan to a specific key. Both bt_seqset and bt_seqadv pin the 106 * page the cursor references if they're successful. 107 */ 108 switch(flags) { 109 case R_NEXT: 110 case R_PREV: 111 if (ISSET(t, B_SEQINIT)) { 112 status = bt_seqadv(t, &e, flags); 113 break; 114 } 115 /* FALLTHROUGH */ 116 case R_CURSOR: 117 case R_FIRST: 118 case R_LAST: 119 status = bt_seqset(t, &e, key, flags); 120 break; 121 default: 122 errno = EINVAL; 123 return (RET_ERROR); 124 } 125 126 if (status == RET_SUCCESS) { 127 status = __bt_ret(t, &e, key, data); 128 129 /* Update the actual cursor. */ 130 t->bt_bcursor.pgno = e.page->pgno; 131 t->bt_bcursor.index = e.index; 132 133 /* 134 * If the user is doing concurrent access, we copied the 135 * key/data, toss the page. 136 */ 137 if (ISSET(t, B_DB_LOCK)) 138 mpool_put(t->bt_mp, e.page, 0); 139 else 140 t->bt_pinned = e.page; 141 SET(t, B_SEQINIT); 142 } 143 return (status); 144 } 145 146 /* 147 * BT_SEQSET -- Set the sequential scan to a specific key. 148 * 149 * Parameters: 150 * t: tree 151 * ep: storage for returned key 152 * key: key for initial scan position 153 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV 154 * 155 * Side effects: 156 * Pins the page the cursor references. 157 * 158 * Returns: 159 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 160 */ 161 static int 162 bt_seqset(t, ep, key, flags) 163 BTREE *t; 164 EPG *ep; 165 DBT *key; 166 int flags; 167 { 168 EPG *e; 169 PAGE *h; 170 pgno_t pg; 171 int exact; 172 173 /* 174 * Delete any already deleted record that we've been saving because 175 * the cursor pointed to it. Since going to a specific key, should 176 * delete any logically deleted records so they aren't found. 177 */ 178 if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) 179 return (RET_ERROR); 180 181 /* 182 * Find the first, last or specific key in the tree and point the cursor 183 * at it. The cursor may not be moved until a new key has been found. 184 */ 185 switch(flags) { 186 case R_CURSOR: /* Keyed scan. */ 187 /* 188 * Find the first instance of the key or the smallest key which 189 * is greater than or equal to the specified key. If run out 190 * of keys, return RET_SPECIAL. 191 */ 192 if (key->data == NULL || key->size == 0) { 193 errno = EINVAL; 194 return (RET_ERROR); 195 } 196 e = __bt_first(t, key, &exact); /* Returns pinned page. */ 197 if (e == NULL) 198 return (RET_ERROR); 199 /* 200 * If at the end of a page, skip any empty pages and find the 201 * next entry. 202 */ 203 if (e->index == NEXTINDEX(e->page)) { 204 h = e->page; 205 do { 206 pg = h->nextpg; 207 mpool_put(t->bt_mp, h, 0); 208 if (pg == P_INVALID) 209 return (RET_SPECIAL); 210 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 211 return (RET_ERROR); 212 } while (NEXTINDEX(h) == 0); 213 e->index = 0; 214 e->page = h; 215 } 216 *ep = *e; 217 break; 218 case R_FIRST: /* First record. */ 219 case R_NEXT: 220 /* Walk down the left-hand side of the tree. */ 221 for (pg = P_ROOT;;) { 222 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 223 return (RET_ERROR); 224 if (h->flags & (P_BLEAF | P_RLEAF)) 225 break; 226 pg = GETBINTERNAL(h, 0)->pgno; 227 mpool_put(t->bt_mp, h, 0); 228 } 229 230 /* Skip any empty pages. */ 231 while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) { 232 pg = h->nextpg; 233 mpool_put(t->bt_mp, h, 0); 234 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 235 return (RET_ERROR); 236 } 237 238 if (NEXTINDEX(h) == 0) { 239 mpool_put(t->bt_mp, h, 0); 240 return (RET_SPECIAL); 241 } 242 243 ep->page = h; 244 ep->index = 0; 245 break; 246 case R_LAST: /* Last record. */ 247 case R_PREV: 248 /* Walk down the right-hand side of the tree. */ 249 for (pg = P_ROOT;;) { 250 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 251 return (RET_ERROR); 252 if (h->flags & (P_BLEAF | P_RLEAF)) 253 break; 254 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; 255 mpool_put(t->bt_mp, h, 0); 256 } 257 258 /* Skip any empty pages. */ 259 while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) { 260 pg = h->prevpg; 261 mpool_put(t->bt_mp, h, 0); 262 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 263 return (RET_ERROR); 264 } 265 266 if (NEXTINDEX(h) == 0) { 267 mpool_put(t->bt_mp, h, 0); 268 return (RET_SPECIAL); 269 } 270 271 ep->page = h; 272 ep->index = NEXTINDEX(h) - 1; 273 break; 274 } 275 return (RET_SUCCESS); 276 } 277 278 /* 279 * BT_SEQADVANCE -- Advance the sequential scan. 280 * 281 * Parameters: 282 * t: tree 283 * flags: R_NEXT, R_PREV 284 * 285 * Side effects: 286 * Pins the page the new key/data record is on. 287 * 288 * Returns: 289 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. 290 */ 291 static int 292 bt_seqadv(t, e, flags) 293 BTREE *t; 294 EPG *e; 295 int flags; 296 { 297 EPGNO *c, delc; 298 PAGE *h; 299 indx_t index; 300 pgno_t pg; 301 302 /* Save the current cursor if going to delete it. */ 303 c = &t->bt_bcursor; 304 if (ISSET(t, B_DELCRSR)) 305 delc = *c; 306 307 if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) 308 return (RET_ERROR); 309 310 /* 311 * Find the next/previous record in the tree and point the cursor at it. 312 * The cursor may not be moved until a new key has been found. 313 */ 314 index = c->index; 315 switch(flags) { 316 case R_NEXT: /* Next record. */ 317 if (++index == NEXTINDEX(h)) { 318 do { 319 pg = h->nextpg; 320 mpool_put(t->bt_mp, h, 0); 321 if (pg == P_INVALID) 322 return (RET_SPECIAL); 323 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 324 return (RET_ERROR); 325 } while (NEXTINDEX(h) == 0); 326 index = 0; 327 } 328 break; 329 case R_PREV: /* Previous record. */ 330 if (index-- == 0) { 331 do { 332 pg = h->prevpg; 333 mpool_put(t->bt_mp, h, 0); 334 if (pg == P_INVALID) 335 return (RET_SPECIAL); 336 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 337 return (RET_ERROR); 338 } while (NEXTINDEX(h) == 0); 339 index = NEXTINDEX(h) - 1; 340 } 341 break; 342 } 343 344 e->page = h; 345 e->index = index; 346 347 /* 348 * Delete any already deleted record that we've been saving because the 349 * cursor pointed to it. This could cause the new index to be shifted 350 * down by one if the record we're deleting is on the same page and has 351 * a larger index. 352 */ 353 if (ISSET(t, B_DELCRSR)) { 354 CLR(t, B_DELCRSR); /* Don't try twice. */ 355 if (c->pgno == delc.pgno && c->index > delc.index) 356 --c->index; 357 if (__bt_crsrdel(t, &delc)) 358 return (RET_ERROR); 359 } 360 return (RET_SUCCESS); 361 } 362 363 /* 364 * __BT_CRSRDEL -- Delete the record referenced by the cursor. 365 * 366 * Parameters: 367 * t: tree 368 * 369 * Returns: 370 * RET_ERROR, RET_SUCCESS 371 */ 372 int 373 __bt_crsrdel(t, c) 374 BTREE *t; 375 EPGNO *c; 376 { 377 PAGE *h; 378 int status; 379 380 CLR(t, B_DELCRSR); /* Don't try twice. */ 381 if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) 382 return (RET_ERROR); 383 status = __bt_dleaf(t, h, c->index); 384 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 385 return (status); 386 } 387