?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
8322 nl: misleading-indentation
[unleashed/tickless.git] / usr / src / cmd / sendmail / db / btree / bt_cursor.c
blob10bc095c9dc854744b4dc15c544c82950de274d1
1 /*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 1997, 1998
5 * Sleepycat Software. All rights reserved.
6 */
7
8 #include "config.h"
9
10 #ifndef lint
11 static const char sccsid[] = "@(#)bt_cursor.c 10.81 (Sleepycat) 12/16/98";
12 #endif /* not lint */
13
14 #ifndef NO_SYSTEM_INCLUDES
15 #include <sys/types.h>
16
17 #include <errno.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #endif
21
22 #include "db_int.h"
23 #include "db_page.h"
24 #include "btree.h"
25 #include "shqueue.h"
26 #include "db_shash.h"
27 #include "lock.h"
28 #include "lock_ext.h"
29
30 static int __bam_c_close __P((DBC *));
31 static int __bam_c_del __P((DBC *, u_int32_t));
32 static int __bam_c_destroy __P((DBC *));
33 static int __bam_c_first __P((DBC *, CURSOR *));
34 static int __bam_c_get __P((DBC *, DBT *, DBT *, u_int32_t));
35 static int __bam_c_getstack __P((DBC *, CURSOR *));
36 static int __bam_c_last __P((DBC *, CURSOR *));
37 static int __bam_c_next __P((DBC *, CURSOR *, int));
38 static int __bam_c_physdel __P((DBC *, CURSOR *, PAGE *));
39 static int __bam_c_prev __P((DBC *, CURSOR *));
40 static int __bam_c_put __P((DBC *, DBT *, DBT *, u_int32_t));
41 static void __bam_c_reset __P((CURSOR *));
42 static int __bam_c_rget __P((DBC *, DBT *, u_int32_t));
43 static int __bam_c_search __P((DBC *, CURSOR *, const DBT *, u_int32_t, int *));
44 static int __bam_dsearch __P((DBC *, CURSOR *, DBT *, u_int32_t *));
45
46 /* Discard the current page/lock held by a cursor. */
47 #undef DISCARD
48 #define DISCARD(dbc, cp) { \
49 if ((cp)->page != NULL) { \
50 (void)memp_fput((dbc)->dbp->mpf, (cp)->page, 0); \
51 (cp)->page = NULL; \
52 } \
53 if ((cp)->lock != LOCK_INVALID) { \
54 (void)__BT_TLPUT((dbc), (cp)->lock); \
55 (cp)->lock = LOCK_INVALID; \
56 } \
57 }
58
59 /* If the cursor references a deleted record. */
60 #undef IS_CUR_DELETED
61 #define IS_CUR_DELETED(cp) \
62 (((cp)->dpgno == PGNO_INVALID && \
63 B_DISSET(GET_BKEYDATA((cp)->page, \
64 (cp)->indx + O_INDX)->type)) || \
65 ((cp)->dpgno != PGNO_INVALID && \
66 B_DISSET(GET_BKEYDATA((cp)->page, (cp)->dindx)->type)))
67
68 /* If the cursor and index combination references a deleted record. */
69 #undef IS_DELETED
70 #define IS_DELETED(cp, indx) \
71 (((cp)->dpgno == PGNO_INVALID && \
72 B_DISSET(GET_BKEYDATA((cp)->page, (indx) + O_INDX)->type)) || \
73 ((cp)->dpgno != PGNO_INVALID && \
74 B_DISSET(GET_BKEYDATA((cp)->page, (indx))->type)))
75
76 /*
77 * Test to see if two cursors could point to duplicates of the same key,
78 * whether on-page or off-page. The leaf page numbers must be the same
79 * in both cases. In the case of off-page duplicates, the key indices
80 * on the leaf page will be the same. In the case of on-page duplicates,
81 * the duplicate page number must not be set, and the key index offsets
82 * must be the same. For the last test, as the saved copy of the cursor
83 * will not have a valid page pointer, we use the cursor's.
84 */
85 #undef POSSIBLE_DUPLICATE
86 #define POSSIBLE_DUPLICATE(cursor, saved_copy) \
87 ((cursor)->pgno == (saved_copy).pgno && \
88 ((cursor)->indx == (saved_copy).indx || \
89 ((cursor)->dpgno == PGNO_INVALID && \
90 (saved_copy).dpgno == PGNO_INVALID && \
91 (cursor)->page->inp[(cursor)->indx] == \
92 (cursor)->page->inp[(saved_copy).indx])))
93
94 /*
95 * __bam_c_reset --
96 * Initialize internal cursor structure.
97 */
98 static void
99 __bam_c_reset(cp)
100 CURSOR *cp;
101 {
102 cp->sp = cp->csp = cp->stack;
103 cp->esp = cp->stack + sizeof(cp->stack) / sizeof(cp->stack[0]);
104 cp->page = NULL;
105 cp->pgno = PGNO_INVALID;
106 cp->indx = 0;
107 cp->dpgno = PGNO_INVALID;
108 cp->dindx = 0;
109 cp->lock = LOCK_INVALID;
110 cp->mode = DB_LOCK_NG;
111 cp->recno = RECNO_OOB;
112 cp->flags = 0;
113 }
114
115 /*
116 * __bam_c_init --
117 * Initialize the access private portion of a cursor
118 *
119 * PUBLIC: int __bam_c_init __P((DBC *));
120 */
121 int
122 __bam_c_init(dbc)
123 DBC *dbc;
124 {
125 DB *dbp;
126 CURSOR *cp;
127 int ret;
128
129 if ((ret = __os_calloc(1, sizeof(CURSOR), &cp)) != 0)
130 return (ret);
131
132 dbp = dbc->dbp;
133 cp->dbc = dbc;
134
135 /*
136 * Logical record numbers are always the same size, and we don't want
137 * to have to check for space every time we return one. Allocate it
138 * in advance.
139 */
140 if (dbp->type == DB_RECNO || F_ISSET(dbp, DB_BT_RECNUM)) {
141 if ((ret = __os_malloc(sizeof(db_recno_t),
142 NULL, &dbc->rkey.data)) != 0) {
143 __os_free(cp, sizeof(CURSOR));
144 return (ret);
145 }
146 dbc->rkey.ulen = sizeof(db_recno_t);
147 }
148
149 /* Initialize methods. */
150 dbc->internal = cp;
151 if (dbp->type == DB_BTREE) {
152 dbc->c_am_close = __bam_c_close;
153 dbc->c_am_destroy = __bam_c_destroy;
154 dbc->c_del = __bam_c_del;
155 dbc->c_get = __bam_c_get;
156 dbc->c_put = __bam_c_put;
157 } else {
158 dbc->c_am_close = __bam_c_close;
159 dbc->c_am_destroy = __bam_c_destroy;
160 dbc->c_del = __ram_c_del;
161 dbc->c_get = __ram_c_get;
162 dbc->c_put = __ram_c_put;
163 }
164
165 /* Initialize dynamic information. */
166 __bam_c_reset(cp);
167
168 return (0);
169 }
170
171 /*
172 * __bam_c_close --
173 * Close down the cursor from a single use.
174 */
175 static int
176 __bam_c_close(dbc)
177 DBC *dbc;
178 {
179 CURSOR *cp;
180 DB *dbp;
181 int ret;
182
183 dbp = dbc->dbp;
184 cp = dbc->internal;
185 ret = 0;
186
187 /*
188 * If a cursor deleted a btree key, perform the actual deletion.
189 * (Recno keys are either deleted immediately or never deleted.)
190 */
191 if (dbp->type == DB_BTREE && F_ISSET(cp, C_DELETED))
192 ret = __bam_c_physdel(dbc, cp, NULL);
193
194 /* Discard any locks not acquired inside of a transaction. */
195 if (cp->lock != LOCK_INVALID) {
196 (void)__BT_TLPUT(dbc, cp->lock);
197 cp->lock = LOCK_INVALID;
198 }
199
200 /* Sanity checks. */
201 #ifdef DIAGNOSTIC
202 if (cp->csp != cp->stack)
203 __db_err(dbp->dbenv, "btree cursor close: stack not empty");
204 #endif
205
206 /* Initialize dynamic information. */
207 __bam_c_reset(cp);
208
209 return (ret);
210 }
211
212 /*
213 * __bam_c_destroy --
214 * Close a single cursor -- internal version.
215 */
216 static int
217 __bam_c_destroy(dbc)
218 DBC *dbc;
219 {
220 /* Discard the structures. */
221 __os_free(dbc->internal, sizeof(CURSOR));
222
223 return (0);
224 }
225
226 /*
227 * __bam_c_del --
228 * Delete using a cursor.
229 */
230 static int
231 __bam_c_del(dbc, flags)
232 DBC *dbc;
233 u_int32_t flags;
234 {
235 CURSOR *cp;
236 DB *dbp;
237 DB_LOCK lock;
238 PAGE *h;
239 db_pgno_t pgno;
240 db_indx_t indx;
241 int ret;
242
243 dbp = dbc->dbp;
244 cp = dbc->internal;
245 h = NULL;
246
247 DB_PANIC_CHECK(dbp);
248
249 /* Check for invalid flags. */
250 if ((ret = __db_cdelchk(dbp, flags,
251 F_ISSET(dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
252 return (ret);
253
254 /*
255 * If we are running CDB, this had better be either a write
256 * cursor or an immediate writer.
257 */
258 if (F_ISSET(dbp, DB_AM_CDB))
259 if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
260 return (EINVAL);
261
262 DEBUG_LWRITE(dbc, dbc->txn, "bam_c_del", NULL, NULL, flags);
263
264 /* If already deleted, return failure. */
265 if (F_ISSET(cp, C_DELETED))
266 return (DB_KEYEMPTY);
267
268 /*
269 * We don't physically delete the record until the cursor moves,
270 * so we have to have a long-lived write lock on the page instead
271 * of a long-lived read lock. Note, we have to have a read lock
272 * to even get here, so we simply discard it.
273 */
274 if (F_ISSET(dbp, DB_AM_LOCKING) && cp->mode != DB_LOCK_WRITE) {
275 if ((ret = __bam_lget(dbc,
276 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
277 goto err;
278 (void)__BT_TLPUT(dbc, cp->lock);
279 cp->lock = lock;
280 cp->mode = DB_LOCK_WRITE;
281 }
282
283 /*
284 * Acquire the underlying page (which may be different from the above
285 * page because it may be a duplicate page), and set the on-page and
286 * in-cursor delete flags. We don't need to lock it as we've already
287 * write-locked the page leading to it.
288 */
289 if (cp->dpgno == PGNO_INVALID) {
290 pgno = cp->pgno;
291 indx = cp->indx;
292 } else {
293 pgno = cp->dpgno;
294 indx = cp->dindx;
295 }
296
297 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
298 goto err;
299
300 /* Log the change. */
301 if (DB_LOGGING(dbc) &&
302 (ret = __bam_cdel_log(dbp->dbenv->lg_info, dbc->txn, &LSN(h),
303 0, dbp->log_fileid, PGNO(h), &LSN(h), indx)) != 0) {
304 (void)memp_fput(dbp->mpf, h, 0);
305 goto err;
306 }
307
308 /*
309 * Set the intent-to-delete flag on the page and update all cursors. */
310 if (cp->dpgno == PGNO_INVALID)
311 B_DSET(GET_BKEYDATA(h, indx + O_INDX)->type);
312 else
313 B_DSET(GET_BKEYDATA(h, indx)->type);
314 (void)__bam_ca_delete(dbp, pgno, indx, 1);
315
316 ret = memp_fput(dbp->mpf, h, DB_MPOOL_DIRTY);
317 h = NULL;
318
319 /*
320 * If the tree has record numbers, we have to adjust the counts.
321 *
322 * !!!
323 * This test is right -- we don't yet support duplicates and record
324 * numbers in the same tree, so ignore duplicates if DB_BT_RECNUM
325 * set.
326 */
327 if (F_ISSET(dbp, DB_BT_RECNUM)) {
328 if ((ret = __bam_c_getstack(dbc, cp)) != 0)
329 goto err;
330 if ((ret = __bam_adjust(dbc, -1)) != 0)
331 goto err;
332 (void)__bam_stkrel(dbc, 0);
333 }
334
335 err: if (h != NULL)
336 (void)memp_fput(dbp->mpf, h, 0);
337 return (ret);
338 }
339
340 /*
341 * __bam_c_get --
342 * Get using a cursor (btree).
343 */
344 static int
345 __bam_c_get(dbc, key, data, flags)
346 DBC *dbc;
347 DBT *key, *data;
348 u_int32_t flags;
349 {
350 CURSOR *cp, copy, start;
351 DB *dbp;
352 PAGE *h;
353 int exact, ret, tmp_rmw;
354
355 dbp = dbc->dbp;
356 cp = dbc->internal;
357
358 DB_PANIC_CHECK(dbp);
359
360 /* Check for invalid flags. */
361 if ((ret = __db_cgetchk(dbp,
362 key, data, flags, cp->pgno != PGNO_INVALID)) != 0)
363 return (ret);
364
365 /* Clear OR'd in additional bits so we can check for flag equality. */
366 tmp_rmw = 0;
367 if (LF_ISSET(DB_RMW)) {
368 if (!F_ISSET(dbp, DB_AM_CDB)) {
369 tmp_rmw = 1;
370 F_SET(dbc, DBC_RMW);
371 }
372 LF_CLR(DB_RMW);
373 }
374
375 DEBUG_LREAD(dbc, dbc->txn, "bam_c_get",
376 flags == DB_SET || flags == DB_SET_RANGE ? key : NULL, NULL, flags);
377
378 /*
379 * Return a cursor's record number. It has nothing to do with the
380 * cursor get code except that it's been rammed into the interface.
381 */
382 if (flags == DB_GET_RECNO) {
383 ret = __bam_c_rget(dbc, data, flags);
384 if (tmp_rmw)
385 F_CLR(dbc, DBC_RMW);
386 return (ret);
387 }
388
389 /*
390 * Initialize the cursor for a new retrieval. Clear the cursor's
391 * page pointer, it was set before this operation, and no longer
392 * has any meaning.
393 */
394 cp->page = NULL;
395 copy = *cp;
396 cp->lock = LOCK_INVALID;
397
398 switch (flags) {
399 case DB_CURRENT:
400 /* It's not possible to return a deleted record. */
401 if (F_ISSET(cp, C_DELETED)) {
402 ret = DB_KEYEMPTY;
403 goto err;
404 }
405
406 /* Acquire the current page. */
407 if ((ret = __bam_lget(dbc,
408 0, cp->pgno, DB_LOCK_READ, &cp->lock)) == 0)
409 ret = memp_fget(dbp->mpf,
410 cp->dpgno == PGNO_INVALID ? &cp->pgno : &cp->dpgno,
411 0, &cp->page);
412 if (ret != 0)
413 goto err;
414 break;
415 case DB_NEXT_DUP:
416 if (cp->pgno == PGNO_INVALID) {
417 ret = EINVAL;
418 goto err;
419 }
420 if ((ret = __bam_c_next(dbc, cp, 1)) != 0)
421 goto err;
422
423 /* Make sure we didn't go past the end of the duplicates. */
424 if (!POSSIBLE_DUPLICATE(cp, copy)) {
425 ret = DB_NOTFOUND;
426 goto err;
427 }
428 break;
429 case DB_NEXT:
430 if (cp->pgno != PGNO_INVALID) {
431 if ((ret = __bam_c_next(dbc, cp, 1)) != 0)
432 goto err;
433 break;
434 }
435 /* FALLTHROUGH */
436 case DB_FIRST:
437 if ((ret = __bam_c_first(dbc, cp)) != 0)
438 goto err;
439 break;
440 case DB_PREV:
441 if (cp->pgno != PGNO_INVALID) {
442 if ((ret = __bam_c_prev(dbc, cp)) != 0)
443 goto err;
444 break;
445 }
446 /* FALLTHROUGH */
447 case DB_LAST:
448 if ((ret = __bam_c_last(dbc, cp)) != 0)
449 goto err;
450 break;
451 case DB_SET:
452 if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
453 goto err;
454
455 /*
456 * We cannot currently be referencing a deleted record, but we
457 * may be referencing off-page duplicates.
458 *
459 * If we're referencing off-page duplicates, move off-page.
460 * If we moved off-page, move to the next non-deleted record.
461 * If we moved to the next non-deleted record, check to make
462 * sure we didn't switch records because our current record
463 * had no non-deleted data items.
464 */
465 start = *cp;
466 if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
467 goto err;
468 if (cp->dpgno != PGNO_INVALID && IS_CUR_DELETED(cp)) {
469 if ((ret = __bam_c_next(dbc, cp, 0)) != 0)
470 goto err;
471 if (!POSSIBLE_DUPLICATE(cp, start)) {
472 ret = DB_NOTFOUND;
473 goto err;
474 }
475 }
476 break;
477 case DB_SET_RECNO:
478 if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
479 goto err;
480 break;
481 case DB_GET_BOTH:
482 if (F_ISSET(dbc, DBC_CONTINUE | DBC_KEYSET)) {
483 /* Acquire the current page. */
484 if ((ret = memp_fget(dbp->mpf,
485 cp->dpgno == PGNO_INVALID ? &cp->pgno : &cp->dpgno,
486 0, &cp->page)) != 0)
487 goto err;
488
489 /* If DBC_CONTINUE, move to the next item. */
490 if (F_ISSET(dbc, DBC_CONTINUE) &&
491 (ret = __bam_c_next(dbc, cp, 1)) != 0)
492 goto err;
493 } else {
494 if ((ret =
495 __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
496 goto err;
497
498 /*
499 * We may be referencing a duplicates page. Move to
500 * the first duplicate.
501 */
502 if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
503 goto err;
504 }
505
506 /* Search for a matching entry. */
507 if ((ret = __bam_dsearch(dbc, cp, data, NULL)) != 0)
508 goto err;
509
510 /* Ignore deleted entries. */
511 if (IS_CUR_DELETED(cp)) {
512 ret = DB_NOTFOUND;
513 goto err;
514 }
515 break;
516 case DB_SET_RANGE:
517 if ((ret = __bam_c_search(dbc, cp, key, flags, &exact)) != 0)
518 goto err;
519
520 /*
521 * As we didn't require an exact match, the search function
522 * may have returned an entry past the end of the page. If
523 * so, move to the next entry.
524 */
525 if (cp->indx == NUM_ENT(cp->page) &&
526 (ret = __bam_c_next(dbc, cp, 0)) != 0)
527 goto err;
528
529 /*
530 * We may be referencing off-page duplicates, if so, move
531 * off-page.
532 */
533 if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
534 goto err;
535
536 /*
537 * We may be referencing a deleted record, if so, move to
538 * the next non-deleted record.
539 */
540 if (IS_CUR_DELETED(cp) && (ret = __bam_c_next(dbc, cp, 0)) != 0)
541 goto err;
542 break;
543 }
544
545 /*
546 * Return the key if the user didn't give us one. If we've moved to
547 * a duplicate page, we may no longer have a pointer to the main page,
548 * so we have to go get it. We know that it's already read-locked,
549 * however, so we don't have to acquire a new lock.
550 */
551 if (flags != DB_SET) {
552 if (cp->dpgno != PGNO_INVALID) {
553 if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0)
554 goto err;
555 } else
556 h = cp->page;
557 ret = __db_ret(dbp,
558 h, cp->indx, key, &dbc->rkey.data, &dbc->rkey.ulen);
559 if (cp->dpgno != PGNO_INVALID)
560 (void)memp_fput(dbp->mpf, h, 0);
561 if (ret)
562 goto err;
563 }
564
565 /* Return the data. */
566 if ((ret = __db_ret(dbp, cp->page,
567 cp->dpgno == PGNO_INVALID ? cp->indx + O_INDX : cp->dindx,
568 data, &dbc->rdata.data, &dbc->rdata.ulen)) != 0)
569 goto err;
570
571 /*
572 * If the previous cursor record has been deleted, physically delete
573 * the entry from the page. We clear the deleted flag before we call
574 * the underlying delete routine so that, if an error occurs, and we
575 * restore the cursor, the deleted flag is cleared. This is because,
576 * if we manage to physically modify the page, and then restore the
577 * cursor, we might try to repeat the page modification when closing
578 * the cursor.
579 */
580 if (F_ISSET(&copy, C_DELETED)) {
581 F_CLR(&copy, C_DELETED);
582 if ((ret = __bam_c_physdel(dbc, &copy, cp->page)) != 0)
583 goto err;
584 }
585 F_CLR(cp, C_DELETED);
586
587 /* Release the previous lock, if any; the current lock is retained. */
588 if (copy.lock != LOCK_INVALID)
589 (void)__BT_TLPUT(dbc, copy.lock);
590
591 /* Release the current page. */
592 if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
593 goto err;
594
595 if (0) {
596 err: if (cp->page != NULL)
597 (void)memp_fput(dbp->mpf, cp->page, 0);
598 if (cp->lock != LOCK_INVALID)
599 (void)__BT_TLPUT(dbc, cp->lock);
600 *cp = copy;
601 }
602
603 /* Release temporary lock upgrade. */
604 if (tmp_rmw)
605 F_CLR(dbc, DBC_RMW);
606
607 return (ret);
608 }
609
610 /*
611 * __bam_dsearch --
612 * Search for a matching data item (or the first data item that's
613 * equal to or greater than the one we're searching for).
614 */
615 static int
616 __bam_dsearch(dbc, cp, data, iflagp)
617 DBC *dbc;
618 CURSOR *cp;
619 DBT *data;
620 u_int32_t *iflagp;
621 {
622 DB *dbp;
623 CURSOR copy, last;
624 int cmp, ret;
625
626 dbp = dbc->dbp;
627
628 /*
629 * If iflagp is non-NULL, we're doing an insert.
630 *
631 * If the duplicates are off-page, use the duplicate search routine.
632 */
633 if (cp->dpgno != PGNO_INVALID) {
634 if ((ret = __db_dsearch(dbc, iflagp != NULL,
635 data, cp->dpgno, &cp->dindx, &cp->page, &cmp)) != 0)
636 return (ret);
637 cp->dpgno = cp->page->pgno;
638
639 if (iflagp == NULL) {
640 if (cmp != 0)
641 return (DB_NOTFOUND);
642 return (0);
643 }
644 *iflagp = DB_BEFORE;
645 return (0);
646 }
647
648 /* Otherwise, do the search ourselves. */
649 copy = *cp;
650 for (;;) {
651 /* Save the last interesting cursor position. */
652 last = *cp;
653
654 /* See if the data item matches the one we're looking for. */
655 if ((cmp = __bam_cmp(dbp, data, cp->page, cp->indx + O_INDX,
656 dbp->dup_compare == NULL ?
657 __bam_defcmp : dbp->dup_compare)) == 0) {
658 if (iflagp != NULL)
659 *iflagp = DB_AFTER;
660 return (0);
661 }
662
663 /*
664 * If duplicate entries are sorted, we're done if we find a
665 * page entry that sorts greater than the application item.
666 * If doing an insert, return success, otherwise DB_NOTFOUND.
667 */
668 if (dbp->dup_compare != NULL && cmp < 0) {
669 if (iflagp == NULL)
670 return (DB_NOTFOUND);
671 *iflagp = DB_BEFORE;
672 return (0);
673 }
674
675 /*
676 * Move to the next item. If we reach the end of the page and
677 * we're doing an insert, set the cursor to the last item and
678 * set the referenced memory location so callers know to insert
679 * after the item, instead of before it. If not inserting, we
680 * return DB_NOTFOUND.
681 */
682 if ((cp->indx += P_INDX) >= NUM_ENT(cp->page)) {
683 if (iflagp == NULL)
684 return (DB_NOTFOUND);
685 goto use_last;
686 }
687
688 /*
689 * Make sure we didn't go past the end of the duplicates. The
690 * error conditions are the same as above.
691 */
692 if (!POSSIBLE_DUPLICATE(cp, copy)) {
693 if (iflagp == NULL)
694 return (DB_NOTFOUND);
695 use_last: *cp = last;
696 *iflagp = DB_AFTER;
697 return (0);
698 }
699 }
700 /* NOTREACHED */
701 }
702
703 /*
704 * __bam_c_rget --
705 * Return the record number for a cursor.
706 */
707 static int
708 __bam_c_rget(dbc, data, flags)
709 DBC *dbc;
710 DBT *data;
711 u_int32_t flags;
712 {
713 CURSOR *cp;
714 DB *dbp;
715 DBT dbt;
716 db_recno_t recno;
717 int exact, ret;
718
719 COMPQUIET(flags, 0);
720 dbp = dbc->dbp;
721 cp = dbc->internal;
722
723 /* Get the page with the current item on it. */
724 if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
725 return (ret);
726
727 /* Get a copy of the key. */
728 memset(&dbt, 0, sizeof(DBT));
729 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
730 if ((ret = __db_ret(dbp, cp->page, cp->indx, &dbt, NULL, NULL)) != 0)
731 goto err;
732
733 exact = 1;
734 if ((ret = __bam_search(dbc, &dbt,
735 F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND,
736 1, &recno, &exact)) != 0)
737 goto err;
738
739 ret = __db_retcopy(data, &recno, sizeof(recno),
740 &dbc->rdata.data, &dbc->rdata.ulen, dbp->db_malloc);
741
742 /* Release the stack. */
743 __bam_stkrel(dbc, 0);
744
745 err: (void)memp_fput(dbp->mpf, cp->page, 0);
746 __os_free(dbt.data, dbt.size);
747 return (ret);
748 }
749
750 /*
751 * __bam_c_put --
752 * Put using a cursor.
753 */
754 static int
755 __bam_c_put(dbc, key, data, flags)
756 DBC *dbc;
757 DBT *key, *data;
758 u_int32_t flags;
759 {
760 CURSOR *cp, copy;
761 DB *dbp;
762 DBT dbt;
763 db_indx_t indx;
764 db_pgno_t pgno;
765 u_int32_t iiflags, iiop;
766 int exact, needkey, ret, stack;
767 void *arg;
768
769 dbp = dbc->dbp;
770 cp = dbc->internal;
771
772 DB_PANIC_CHECK(dbp);
773
774 DEBUG_LWRITE(dbc, dbc->txn, "bam_c_put",
775 flags == DB_KEYFIRST || flags == DB_KEYLAST ? key : NULL,
776 data, flags);
777
778 if ((ret = __db_cputchk(dbp, key, data, flags,
779 F_ISSET(dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
780 return (ret);
781
782 /*
783 * If we are running CDB, this had better be either a write
784 * cursor or an immediate writer. If it's a regular writer,
785 * that means we have an IWRITE lock and we need to upgrade
786 * it to a write lock.
787 */
788 if (F_ISSET(dbp, DB_AM_CDB)) {
789 if (!F_ISSET(dbc, DBC_RMW | DBC_WRITER))
790 return (EINVAL);
791
792 if (F_ISSET(dbc, DBC_RMW) &&
793 (ret = lock_get(dbp->dbenv->lk_info, dbc->locker,
794 DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
795 &dbc->mylock)) != 0)
796 return (EAGAIN);
797 }
798
799 if (0) {
800 split: /*
801 * To split, we need a valid key for the page. Since it's a
802 * cursor, we have to build one.
803 *
804 * Acquire a copy of a key from the page.
805 */
806 if (needkey) {
807 memset(&dbt, 0, sizeof(DBT));
808 if ((ret = __db_ret(dbp, cp->page, indx,
809 &dbt, &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
810 goto err;
811 arg = &dbt;
812 } else
813 arg = key;
814
815 /*
816 * Discard any locks and pinned pages (the locks are discarded
817 * even if we're running with transactions, as they lock pages
818 * that we're sorry we ever acquired). If stack is set and the
819 * cursor entries are valid, they point to the same entries as
820 * the stack, don't free them twice.
821 */
822 if (stack) {
823 (void)__bam_stkrel(dbc, 1);
824 stack = 0;
825 } else
826 DISCARD(dbc, cp);
827
828 /*
829 * Restore the cursor to its original value. This is necessary
830 * for two reasons. First, we are about to copy it in case of
831 * error, again. Second, we adjust cursors during the split,
832 * and we have to ensure this cursor is adjusted appropriately,
833 * along with all the other cursors.
834 */
835 *cp = copy;
836
837 if ((ret = __bam_split(dbc, arg)) != 0)
838 goto err;
839 }
840
841 /*
842 * Initialize the cursor for a new retrieval. Clear the cursor's
843 * page pointer, it was set before this operation, and no longer
844 * has any meaning.
845 */
846 cp->page = NULL;
847 copy = *cp;
848 cp->lock = LOCK_INVALID;
849
850 iiflags = needkey = ret = stack = 0;
851 switch (flags) {
852 case DB_AFTER:
853 case DB_BEFORE:
854 case DB_CURRENT:
855 needkey = 1;
856 if (cp->dpgno == PGNO_INVALID) {
857 pgno = cp->pgno;
858 indx = cp->indx;
859 } else {
860 pgno = cp->dpgno;
861 indx = cp->dindx;
862 }
863
864 /*
865 * !!!
866 * This test is right -- we don't yet support duplicates and
867 * record numbers in the same tree, so ignore duplicates if
868 * DB_BT_RECNUM set.
869 */
870 if (F_ISSET(dbp, DB_BT_RECNUM) &&
871 (flags != DB_CURRENT || F_ISSET(cp, C_DELETED))) {
872 /* Acquire a complete stack. */
873 if ((ret = __bam_c_getstack(dbc, cp)) != 0)
874 goto err;
875 cp->page = cp->csp->page;
876
877 stack = 1;
878 iiflags = BI_DOINCR;
879 } else {
880 /* Acquire the current page. */
881 if ((ret = __bam_lget(dbc,
882 0, cp->pgno, DB_LOCK_WRITE, &cp->lock)) == 0)
883 ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page);
884 if (ret != 0)
885 goto err;
886
887 iiflags = 0;
888 }
889
890 /*
891 * If the user has specified a duplicate comparison function,
892 * we return an error if DB_CURRENT was specified and the
893 * replacement data doesn't compare equal to the current data.
894 * This stops apps from screwing up the duplicate sort order.
895 */
896 if (flags == DB_CURRENT && dbp->dup_compare != NULL)
897 if (__bam_cmp(dbp, data,
898 cp->page, indx, dbp->dup_compare) != 0) {
899 ret = EINVAL;
900 goto err;
901 }
902
903 iiop = flags;
904 break;
905 case DB_KEYFIRST:
906 case DB_KEYLAST:
907 /*
908 * If we have a duplicate comparison function, we position to
909 * the first of any on-page duplicates, and use __bam_dsearch
910 * to search for the right slot. Otherwise, we position to
911 * the first/last of any on-page duplicates based on the flag
912 * value.
913 */
914 if ((ret = __bam_c_search(dbc, cp, key,
915 flags == DB_KEYFIRST || dbp->dup_compare != NULL ?
916 DB_KEYFIRST : DB_KEYLAST, &exact)) != 0)
917 goto err;
918 stack = 1;
919
920 /*
921 * If an exact match:
922 * If duplicates aren't supported, replace the current
923 * item. (When implementing the DB->put function, our
924 * caller has already checked the DB_NOOVERWRITE flag.)
925 *
926 * If there's a duplicate comparison function, find the
927 * correct slot for this duplicate item.
928 *
929 * If there's no duplicate comparison function, set the
930 * insert flag based on the argument flags.
931 *
932 * If there's no match, the search function returned the
933 * smallest slot greater than the key, use it.
934 */
935 if (exact) {
936 if (F_ISSET(dbp, DB_AM_DUP)) {
937 /*
938 * If at off-page duplicate page, move to the
939 * first or last entry -- if a comparison
940 * function was specified, start searching at
941 * the first entry. Otherwise, move based on
942 * the DB_KEYFIRST/DB_KEYLAST flags.
943 */
944 if ((ret = __bam_dup(dbc, cp, cp->indx,
945 dbp->dup_compare == NULL &&
946 flags != DB_KEYFIRST)) != 0)
947 goto err;
948
949 /*
950 * If there's a comparison function, search for
951 * the correct slot. Otherwise, set the insert
952 * flag based on the argment flag.
953 */
954 if (dbp->dup_compare == NULL)
955 iiop = flags == DB_KEYFIRST ?
956 DB_BEFORE : DB_AFTER;
957 else
958 if ((ret = __bam_dsearch(dbc,
959 cp, data, &iiop)) != 0)
960 goto err;
961 } else
962 iiop = DB_CURRENT;
963 iiflags = 0;
964 } else {
965 iiop = DB_BEFORE;
966 iiflags = BI_NEWKEY;
967 }
968
969 if (cp->dpgno == PGNO_INVALID) {
970 pgno = cp->pgno;
971 indx = cp->indx;
972 } else {
973 pgno = cp->dpgno;
974 indx = cp->dindx;
975 }
976 break;
977 }
978
979 ret = __bam_iitem(dbc, &cp->page, &indx, key, data, iiop, iiflags);
980
981 if (ret == DB_NEEDSPLIT)
982 goto split;
983 if (ret != 0)
984 goto err;
985
986 /*
987 * Reset any cursors referencing this item that might have the item
988 * marked for deletion.
989 */
990 if (iiop == DB_CURRENT) {
991 (void)__bam_ca_delete(dbp, pgno, indx, 0);
992
993 /*
994 * It's also possible that we are the cursor that had the
995 * item marked for deletion, in which case we want to make
996 * sure that we don't delete it because we had the delete
997 * flag set already.
998 */
999 if (cp->pgno == copy.pgno && cp->indx == copy.indx &&
1000 cp->dpgno == copy.dpgno && cp->dindx == copy.dindx)
1001 F_CLR(&copy, C_DELETED);
1002 }
1003
1004 /*
1005 * Update the cursor to point to the new entry. The new entry was
1006 * stored on the current page, because we split pages until it was
1007 * possible.
1008 */
1009 if (cp->dpgno == PGNO_INVALID)
1010 cp->indx = indx;
1011 else
1012 cp->dindx = indx;
1013
1014 /*
1015 * If the previous cursor record has been deleted, physically delete
1016 * the entry from the page. We clear the deleted flag before we call
1017 * the underlying delete routine so that, if an error occurs, and we
1018 * restore the cursor, the deleted flag is cleared. This is because,
1019 * if we manage to physically modify the page, and then restore the
1020 * cursor, we might try to repeat the page modification when closing
1021 * the cursor.
1022 */
1023 if (F_ISSET(&copy, C_DELETED)) {
1024 F_CLR(&copy, C_DELETED);
1025 if ((ret = __bam_c_physdel(dbc, &copy, cp->page)) != 0)
1026 goto err;
1027 }
1028 F_CLR(cp, C_DELETED);
1029
1030 /* Release the previous lock, if any; the current lock is retained. */
1031 if (copy.lock != LOCK_INVALID)
1032 (void)__BT_TLPUT(dbc, copy.lock);
1033
1034 /*
1035 * Discard any pages pinned in the tree and their locks, except for
1036 * the leaf page, for which we only discard the pin, not the lock.
1037 *
1038 * Note, the leaf page participated in the stack we acquired, and so
1039 * we have to adjust the stack as necessary. If there was only a
1040 * single page on the stack, we don't have to free further stack pages.
1041 */
1042 if (stack && BT_STK_POP(cp) != NULL)
1043 (void)__bam_stkrel(dbc, 0);
1044
1045 /* Release the current page. */
1046 if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
1047 goto err;
1048
1049 if (0) {
1050 err: /* Discard any pinned pages. */
1051 if (stack)
1052 (void)__bam_stkrel(dbc, 0);
1053 else
1054 DISCARD(dbc, cp);
1055 *cp = copy;
1056 }
1057
1058 if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
1059 (void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
1060 DB_LOCK_IWRITE, 0);
1061
1062 return (ret);
1063 }
1064
1065 /*
1066 * __bam_c_first --
1067 * Return the first record.
1068 */
1069 static int
1070 __bam_c_first(dbc, cp)
1071 DBC *dbc;
1072 CURSOR *cp;
1073 {
1074 DB *dbp;
1075 db_pgno_t pgno;
1076 int ret;
1077
1078 dbp = dbc->dbp;
1079
1080 /* Walk down the left-hand side of the tree. */
1081 for (pgno = PGNO_ROOT;;) {
1082 if ((ret =
1083 __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1084 return (ret);
1085 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1086 return (ret);
1087
1088 /* If we find a leaf page, we're done. */
1089 if (ISLEAF(cp->page))
1090 break;
1091
1092 pgno = GET_BINTERNAL(cp->page, 0)->pgno;
1093 DISCARD(dbc, cp);
1094 }
1095
1096 cp->pgno = cp->page->pgno;
1097 cp->indx = 0;
1098 cp->dpgno = PGNO_INVALID;
1099
1100 /* Check for duplicates. */
1101 if ((ret = __bam_dup(dbc, cp, cp->indx, 0)) != 0)
1102 return (ret);
1103
1104 /* If on an empty page or a deleted record, move to the next one. */
1105 if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(cp))
1106 if ((ret = __bam_c_next(dbc, cp, 0)) != 0)
1107 return (ret);
1108
1109 return (0);
1110 }
1111
1112 /*
1113 * __bam_c_last --
1114 * Return the last record.
1115 */
1116 static int
1117 __bam_c_last(dbc, cp)
1118 DBC *dbc;
1119 CURSOR *cp;
1120 {
1121 DB *dbp;
1122 db_pgno_t pgno;
1123 int ret;
1124
1125 dbp = dbc->dbp;
1126
1127 /* Walk down the right-hand side of the tree. */
1128 for (pgno = PGNO_ROOT;;) {
1129 if ((ret =
1130 __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1131 return (ret);
1132 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1133 return (ret);
1134
1135 /* If we find a leaf page, we're done. */
1136 if (ISLEAF(cp->page))
1137 break;
1138
1139 pgno =
1140 GET_BINTERNAL(cp->page, NUM_ENT(cp->page) - O_INDX)->pgno;
1141 DISCARD(dbc, cp);
1142 }
1143
1144 cp->pgno = cp->page->pgno;
1145 cp->indx = NUM_ENT(cp->page) == 0 ? 0 : NUM_ENT(cp->page) - P_INDX;
1146 cp->dpgno = PGNO_INVALID;
1147
1148 /* Check for duplicates. */
1149 if ((ret = __bam_dup(dbc, cp, cp->indx, 1)) != 0)
1150 return (ret);
1151
1152 /* If on an empty page or a deleted record, move to the next one. */
1153 if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(cp))
1154 if ((ret = __bam_c_prev(dbc, cp)) != 0)
1155 return (ret);
1156
1157 return (0);
1158 }
1159
1160 /*
1161 * __bam_c_next --
1162 * Move to the next record.
1163 */
1164 static int
1165 __bam_c_next(dbc, cp, initial_move)
1166 DBC *dbc;
1167 CURSOR *cp;
1168 int initial_move;
1169 {
1170 DB *dbp;
1171 db_indx_t adjust, indx;
1172 db_pgno_t pgno;
1173 int ret;
1174
1175 dbp = dbc->dbp;
1176
1177 /*
1178 * We're either moving through a page of duplicates or a btree leaf
1179 * page.
1180 */
1181 if (cp->dpgno == PGNO_INVALID) {
1182 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
1183 pgno = cp->pgno;
1184 indx = cp->indx;
1185 } else {
1186 adjust = O_INDX;
1187 pgno = cp->dpgno;
1188 indx = cp->dindx;
1189 }
1190 if (cp->page == NULL) {
1191 if ((ret =
1192 __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1193 return (ret);
1194 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1195 return (ret);
1196 }
1197
1198 /*
1199 * If at the end of the page, move to a subsequent page.
1200 *
1201 * !!!
1202 * Check for >= NUM_ENT. If we're here as the result of a search that
1203 * landed us on NUM_ENT, we'll increment indx before we test.
1204 *
1205 * !!!
1206 * This code handles empty pages and pages with only deleted entries.
1207 */
1208 if (initial_move)
1209 indx += adjust;
1210 for (;;) {
1211 if (indx >= NUM_ENT(cp->page)) {
1212 /*
1213 * If we're in a btree leaf page, we've reached the end
1214 * of the tree. If we've reached the end of a page of
1215 * duplicates, continue from the btree leaf page where
1216 * we found this page of duplicates.
1217 */
1218 pgno = cp->page->next_pgno;
1219 if (pgno == PGNO_INVALID) {
1220 /* If in a btree leaf page, it's EOF. */
1221 if (cp->dpgno == PGNO_INVALID)
1222 return (DB_NOTFOUND);
1223
1224 /* Continue from the last btree leaf page. */
1225 cp->dpgno = PGNO_INVALID;
1226
1227 adjust = P_INDX;
1228 pgno = cp->pgno;
1229 indx = cp->indx + P_INDX;
1230 } else
1231 indx = 0;
1232
1233 DISCARD(dbc, cp);
1234 if ((ret = __bam_lget(dbc,
1235 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1236 return (ret);
1237 if ((ret =
1238 memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1239 return (ret);
1240 continue;
1241 }
1242
1243 /* Ignore deleted records. */
1244 if (IS_DELETED(cp, indx)) {
1245 indx += adjust;
1246 continue;
1247 }
1248
1249 /*
1250 * If we're not in a duplicates page, check to see if we've
1251 * found a page of duplicates, in which case we move to the
1252 * first entry.
1253 */
1254 if (cp->dpgno == PGNO_INVALID) {
1255 cp->pgno = cp->page->pgno;
1256 cp->indx = indx;
1257
1258 if ((ret = __bam_dup(dbc, cp, indx, 0)) != 0)
1259 return (ret);
1260 if (cp->dpgno != PGNO_INVALID) {
1261 indx = cp->dindx;
1262 adjust = O_INDX;
1263 continue;
1264 }
1265 } else {
1266 cp->dpgno = cp->page->pgno;
1267 cp->dindx = indx;
1268 }
1269 break;
1270 }
1271 return (0);
1272 }
1273
1274 /*
1275 * __bam_c_prev --
1276 * Move to the previous record.
1277 */
1278 static int
1279 __bam_c_prev(dbc, cp)
1280 DBC *dbc;
1281 CURSOR *cp;
1282 {
1283 DB *dbp;
1284 db_indx_t indx, adjust;
1285 db_pgno_t pgno;
1286 int ret, set_indx;
1287
1288 dbp = dbc->dbp;
1289
1290 /*
1291 * We're either moving through a page of duplicates or a btree leaf
1292 * page.
1293 */
1294 if (cp->dpgno == PGNO_INVALID) {
1295 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
1296 pgno = cp->pgno;
1297 indx = cp->indx;
1298 } else {
1299 adjust = O_INDX;
1300 pgno = cp->dpgno;
1301 indx = cp->dindx;
1302 }
1303 if (cp->page == NULL) {
1304 if ((ret =
1305 __bam_lget(dbc, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1306 return (ret);
1307 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1308 return (ret);
1309 }
1310
1311 /*
1312 * If at the beginning of the page, move to any previous one.
1313 *
1314 * !!!
1315 * This code handles empty pages and pages with only deleted entries.
1316 */
1317 for (;;) {
1318 if (indx == 0) {
1319 /*
1320 * If we're in a btree leaf page, we've reached the
1321 * beginning of the tree. If we've reached the first
1322 * of a page of duplicates, continue from the btree
1323 * leaf page where we found this page of duplicates.
1324 */
1325 pgno = cp->page->prev_pgno;
1326 if (pgno == PGNO_INVALID) {
1327 /* If in a btree leaf page, it's SOF. */
1328 if (cp->dpgno == PGNO_INVALID)
1329 return (DB_NOTFOUND);
1330
1331 /* Continue from the last btree leaf page. */
1332 cp->dpgno = PGNO_INVALID;
1333
1334 adjust = P_INDX;
1335 pgno = cp->pgno;
1336 indx = cp->indx;
1337 set_indx = 0;
1338 } else
1339 set_indx = 1;
1340
1341 DISCARD(dbc, cp);
1342 if ((ret = __bam_lget(dbc,
1343 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
1344 return (ret);
1345 if ((ret =
1346 memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1347 return (ret);
1348
1349 if (set_indx)
1350 indx = NUM_ENT(cp->page);
1351 if (indx == 0)
1352 continue;
1353 }
1354
1355 /* Ignore deleted records. */
1356 indx -= adjust;
1357 if (IS_DELETED(cp, indx))
1358 continue;
1359
1360 /*
1361 * If we're not in a duplicates page, check to see if we've
1362 * found a page of duplicates, in which case we move to the
1363 * last entry.
1364 */
1365 if (cp->dpgno == PGNO_INVALID) {
1366 cp->pgno = cp->page->pgno;
1367 cp->indx = indx;
1368
1369 if ((ret = __bam_dup(dbc, cp, indx, 1)) != 0)
1370 return (ret);
1371 if (cp->dpgno != PGNO_INVALID) {
1372 indx = cp->dindx + O_INDX;
1373 adjust = O_INDX;
1374 continue;
1375 }
1376 } else {
1377 cp->dpgno = cp->page->pgno;
1378 cp->dindx = indx;
1379 }
1380 break;
1381 }
1382 return (0);
1383 }
1384
1385 /*
1386 * __bam_c_search --
1387 * Move to a specified record.
1388 */
1389 static int
1390 __bam_c_search(dbc, cp, key, flags, exactp)
1391 DBC *dbc;
1392 CURSOR *cp;
1393 const DBT *key;
1394 u_int32_t flags;
1395 int *exactp;
1396 {
1397 BTREE *t;
1398 DB *dbp;
1399 DB_LOCK lock;
1400 PAGE *h;
1401 db_recno_t recno;
1402 db_indx_t indx;
1403 u_int32_t sflags;
1404 int cmp, needexact, ret;
1405
1406 dbp = dbc->dbp;
1407 t = dbp->internal;
1408
1409 /* Find an entry in the database. */
1410 switch (flags) {
1411 case DB_SET_RECNO:
1412 if ((ret = __ram_getno(dbc, key, &recno, 0)) != 0)
1413 return (ret);
1414 sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
1415 needexact = *exactp = 1;
1416 ret = __bam_rsearch(dbc, &recno, sflags, 1, exactp);
1417 break;
1418 case DB_SET:
1419 case DB_GET_BOTH:
1420 sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
1421 needexact = *exactp = 1;
1422 goto search;
1423 case DB_SET_RANGE:
1424 sflags = F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND;
1425 needexact = *exactp = 0;
1426 goto search;
1427 case DB_KEYFIRST:
1428 sflags = S_KEYFIRST;
1429 goto fast_search;
1430 case DB_KEYLAST:
1431 sflags = S_KEYLAST;
1432 fast_search: needexact = *exactp = 0;
1433 /*
1434 * If the application has a history of inserting into the first
1435 * or last pages of the database, we check those pages first to
1436 * avoid doing a full search.
1437 *
1438 * Record numbers can't be fast-tracked, the entire tree has to
1439 * be locked.
1440 */
1441 h = NULL;
1442 lock = LOCK_INVALID;
1443 if (F_ISSET(dbp, DB_BT_RECNUM))
1444 goto search;
1445
1446 /* Check if the application has a history of sorted input. */
1447 if (t->bt_lpgno == PGNO_INVALID)
1448 goto search;
1449
1450 /*
1451 * Lock and retrieve the page on which we did the last insert.
1452 * It's okay if it doesn't exist, or if it's not the page type
1453 * we expected, it just means that the world changed.
1454 */
1455 if (__bam_lget(dbc, 0, t->bt_lpgno, DB_LOCK_WRITE, &lock))
1456 goto fast_miss;
1457 if (memp_fget(dbp->mpf, &t->bt_lpgno, 0, &h))
1458 goto fast_miss;
1459 if (TYPE(h) != P_LBTREE)
1460 goto fast_miss;
1461 if (NUM_ENT(h) == 0)
1462 goto fast_miss;
1463
1464 /*
1465 * What we do here is test to see if we're at the beginning or
1466 * end of the tree and if the new item sorts before/after the
1467 * first/last page entry. We don't try and catch inserts into
1468 * the middle of the tree (although we could, as long as there
1469 * were two keys on the page and we saved both the index and
1470 * the page number of the last insert).
1471 */
1472 if (h->next_pgno == PGNO_INVALID) {
1473 indx = NUM_ENT(h) - P_INDX;
1474 if ((cmp =
1475 __bam_cmp(dbp, key, h, indx, t->bt_compare)) < 0)
1476 goto try_begin;
1477 if (cmp > 0) {
1478 indx += P_INDX;
1479 goto fast_hit;
1480 }
1481
1482 /*
1483 * Found a duplicate. If doing DB_KEYLAST, we're at
1484 * the correct position, otherwise, move to the first
1485 * of the duplicates.
1486 */
1487 if (flags == DB_KEYLAST)
1488 goto fast_hit;
1489 for (;
1490 indx > 0 && h->inp[indx - P_INDX] == h->inp[indx];
1491 indx -= P_INDX)
1492 ;
1493 goto fast_hit;
1494 }
1495 try_begin: if (h->prev_pgno == PGNO_INVALID) {
1496 indx = 0;
1497 if ((cmp =
1498 __bam_cmp(dbp, key, h, indx, t->bt_compare)) > 0)
1499 goto fast_miss;
1500 if (cmp < 0)
1501 goto fast_hit;
1502 /*
1503 * Found a duplicate. If doing DB_KEYFIRST, we're at
1504 * the correct position, otherwise, move to the last
1505 * of the duplicates.
1506 */
1507 if (flags == DB_KEYFIRST)
1508 goto fast_hit;
1509 for (;
1510 indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
1511 h->inp[indx] == h->inp[indx + P_INDX];
1512 indx += P_INDX)
1513 ;
1514 goto fast_hit;
1515 }
1516 goto fast_miss;
1517
1518 fast_hit: /* Set the exact match flag, we may have found a duplicate. */
1519 *exactp = cmp == 0;
1520
1521 /* Enter the entry in the stack. */
1522 BT_STK_CLR(cp);
1523 BT_STK_ENTER(cp, h, indx, lock, ret);
1524 break;
1525
1526 fast_miss: if (h != NULL)
1527 (void)memp_fput(dbp->mpf, h, 0);
1528 if (lock != LOCK_INVALID)
1529 (void)__BT_LPUT(dbc, lock);
1530
1531 search: ret = __bam_search(dbc, key, sflags, 1, NULL, exactp);
1532 break;
1533 default: /* XXX: Impossible. */
1534 abort();
1535 /* NOTREACHED */
1536 }
1537 if (ret != 0)
1538 return (ret);
1539
1540 /*
1541 * Initialize the cursor to reference it. This has to be done
1542 * before we return (even with DB_NOTFOUND) because we have to
1543 * free the page(s) we locked in __bam_search.
1544 */
1545 cp->page = cp->csp->page;
1546 cp->pgno = cp->csp->page->pgno;
1547 cp->indx = cp->csp->indx;
1548 cp->lock = cp->csp->lock;
1549 cp->dpgno = PGNO_INVALID;
1550
1551 /*
1552 * If we inserted a key into the first or last slot of the tree,
1553 * remember where it was so we can do it more quickly next time.
1554 */
1555 if (flags == DB_KEYFIRST || flags == DB_KEYLAST)
1556 t->bt_lpgno =
1557 ((cp->page->next_pgno == PGNO_INVALID &&
1558 cp->indx >= NUM_ENT(cp->page)) ||
1559 (cp->page->prev_pgno == PGNO_INVALID && cp->indx == 0)) ?
1560 cp->pgno : PGNO_INVALID;
1561
1562 /* If we need an exact match and didn't find one, we're done. */
1563 if (needexact && *exactp == 0)
1564 return (DB_NOTFOUND);
1565
1566 return (0);
1567 }
1568
1569 /*
1570 * __bam_dup --
1571 * Check for an off-page duplicates entry, and if found, move to the
1572 * first or last entry.
1573 *
1574 * PUBLIC: int __bam_dup __P((DBC *, CURSOR *, u_int32_t, int));
1575 */
1576 int
1577 __bam_dup(dbc, cp, indx, last_dup)
1578 DBC *dbc;
1579 CURSOR *cp;
1580 u_int32_t indx;
1581 int last_dup;
1582 {
1583 BOVERFLOW *bo;
1584 DB *dbp;
1585 db_pgno_t pgno;
1586 int ret;
1587
1588 dbp = dbc->dbp;
1589
1590 /*
1591 * Check for an overflow entry. If we find one, move to the
1592 * duplicates page, and optionally move to the last record on
1593 * that page.
1594 *
1595 * !!!
1596 * We don't lock duplicates pages, we've already got the correct
1597 * lock on the main page.
1598 */
1599 bo = GET_BOVERFLOW(cp->page, indx + O_INDX);
1600 if (B_TYPE(bo->type) != B_DUPLICATE)
1601 return (0);
1602
1603 pgno = bo->pgno;
1604 if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
1605 return (ret);
1606 cp->page = NULL;
1607 if (last_dup) {
1608 if ((ret = __db_dend(dbc, pgno, &cp->page)) != 0)
1609 return (ret);
1610 indx = NUM_ENT(cp->page) - O_INDX;
1611 } else {
1612 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &cp->page)) != 0)
1613 return (ret);
1614 indx = 0;
1615 }
1616
1617 /* Update the cursor's duplicate information. */
1618 cp->dpgno = cp->page->pgno;
1619 cp->dindx = indx;
1620
1621 return (0);
1622 }
1623
1624 /*
1625 * __bam_c_physdel --
1626 * Actually do the cursor deletion.
1627 */
1628 static int
1629 __bam_c_physdel(dbc, cp, h)
1630 DBC *dbc;
1631 CURSOR *cp;
1632 PAGE *h;
1633 {
1634 enum { DELETE_ITEM, DELETE_PAGE, NOTHING_FURTHER } cmd;
1635 BOVERFLOW bo;
1636 DB *dbp;
1637 DBT dbt;
1638 DB_LOCK lock;
1639 db_indx_t indx;
1640 db_pgno_t pgno, next_pgno, prev_pgno;
1641 int delete_page, local_page, ret;
1642
1643 dbp = dbc->dbp;
1644
1645 delete_page = ret = 0;
1646
1647 /* Figure out what we're deleting. */
1648 if (cp->dpgno == PGNO_INVALID) {
1649 pgno = cp->pgno;
1650 indx = cp->indx;
1651 } else {
1652 pgno = cp->dpgno;
1653 indx = cp->dindx;
1654 }
1655
1656 /*
1657 * If the item is referenced by another cursor, set that cursor's
1658 * delete flag and leave it up to it to do the delete.
1659 *
1660 * !!!
1661 * This test for > 0 is a tricky. There are two ways that we can
1662 * be called here. Either we are closing the cursor or we've moved
1663 * off the page with the deleted entry. In the first case, we've
1664 * already removed the cursor from the active queue, so we won't see
1665 * it in __bam_ca_delete. In the second case, it will be on a different
1666 * item, so we won't bother with it in __bam_ca_delete.
1667 */
1668 if (__bam_ca_delete(dbp, pgno, indx, 1) > 0)
1669 return (0);
1670
1671 /*
1672 * If this is concurrent DB, upgrade the lock if necessary.
1673 */
1674 if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW) &&
1675 (ret = lock_get(dbp->dbenv->lk_info,
1676 dbc->locker, DB_LOCK_UPGRADE, &dbc->lock_dbt, DB_LOCK_WRITE,
1677 &dbc->mylock)) != 0)
1678 return (EAGAIN);
1679
1680 /*
1681 * If we don't already have the page locked, get it and delete the
1682 * items.
1683 */
1684 if ((h == NULL || h->pgno != pgno)) {
1685 if ((ret = __bam_lget(dbc, 0, pgno, DB_LOCK_WRITE, &lock)) != 0)
1686 return (ret);
1687 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
1688 return (ret);
1689 local_page = 1;
1690 } else
1691 local_page = 0;
1692
1693 /*
1694 * If we're deleting a duplicate entry and there are other duplicate
1695 * entries remaining, call the common code to do the work and fix up
1696 * the parent page as necessary. Otherwise, do a normal btree delete.
1697 *
1698 * There are 5 possible cases:
1699 *
1700 * 1. It's not a duplicate item: do a normal btree delete.
1701 * 2. It's a duplicate item:
1702 * 2a: We delete an item from a page of duplicates, but there are
1703 * more items on the page.
1704 * 2b: We delete the last item from a page of duplicates, deleting
1705 * the last duplicate.
1706 * 2c: We delete the last item from a page of duplicates, but there
1707 * is a previous page of duplicates.
1708 * 2d: We delete the last item from a page of duplicates, but there
1709 * is a following page of duplicates.
1710 *
1711 * In the case of:
1712 *
1713 * 1: There's nothing further to do.
1714 * 2a: There's nothing further to do.
1715 * 2b: Do the normal btree delete instead of a duplicate delete, as
1716 * that deletes both the duplicate chain and the parent page's
1717 * entry.
1718 * 2c: There's nothing further to do.
1719 * 2d: Delete the duplicate, and update the parent page's entry.
1720 */
1721 if (TYPE(h) == P_DUPLICATE) {
1722 pgno = PGNO(h);
1723 prev_pgno = PREV_PGNO(h);
1724 next_pgno = NEXT_PGNO(h);
1725
1726 if (NUM_ENT(h) == 1 &&
1727 prev_pgno == PGNO_INVALID && next_pgno == PGNO_INVALID)
1728 cmd = DELETE_PAGE;
1729 else {
1730 cmd = DELETE_ITEM;
1731
1732 /* Delete the duplicate. */
1733 if ((ret = __db_drem(dbc, &h, indx, __bam_free)) != 0)
1734 goto err;
1735
1736 /*
1737 * 2a: h != NULL, h->pgno == pgno
1738 * 2b: We don't reach this clause, as the above test
1739 * was true.
1740 * 2c: h == NULL, prev_pgno != PGNO_INVALID
1741 * 2d: h != NULL, next_pgno != PGNO_INVALID
1742 *
1743 * Test for 2a and 2c: if we didn't empty the current
1744 * page or there was a previous page of duplicates, we
1745 * don't need to touch the parent page.
1746 */
1747 if ((h != NULL && pgno == h->pgno) ||
1748 prev_pgno != PGNO_INVALID)
1749 cmd = NOTHING_FURTHER;
1750 }
1751
1752 /*
1753 * Release any page we're holding and its lock.
1754 *
1755 * !!!
1756 * If there is no subsequent page in the duplicate chain, then
1757 * __db_drem will have put page "h" and set it to NULL.
1758 */
1759 if (local_page) {
1760 if (h != NULL)
1761 (void)memp_fput(dbp->mpf, h, 0);
1762 (void)__BT_TLPUT(dbc, lock);
1763 local_page = 0;
1764 }
1765
1766 if (cmd == NOTHING_FURTHER)
1767 goto done;
1768
1769 /* Acquire the parent page and switch the index to its entry. */
1770 if ((ret =
1771 __bam_lget(dbc, 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
1772 goto err;
1773 if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0) {
1774 (void)__BT_TLPUT(dbc, lock);
1775 goto err;
1776 }
1777 local_page = 1;
1778 indx = cp->indx;
1779
1780 if (cmd == DELETE_PAGE)
1781 goto btd;
1782
1783 /*
1784 * Copy, delete, update, add-back the parent page's data entry.
1785 *
1786 * XXX
1787 * This may be a performance/logging problem. We should add a
1788 * log message which simply logs/updates a random set of bytes
1789 * on a page, and use it instead of doing a delete/add pair.
1790 */
1791 indx += O_INDX;
1792 bo = *GET_BOVERFLOW(h, indx);
1793 (void)__db_ditem(dbc, h, indx, BOVERFLOW_SIZE);
1794 bo.pgno = next_pgno;
1795 memset(&dbt, 0, sizeof(dbt));
1796 dbt.data = &bo;
1797 dbt.size = BOVERFLOW_SIZE;
1798 (void)__db_pitem(dbc, h, indx, BOVERFLOW_SIZE, &dbt, NULL);
1799 (void)memp_fset(dbp->mpf, h, DB_MPOOL_DIRTY);
1800 goto done;
1801 }
1802
1803 btd: /*
1804 * If the page is going to be emptied, delete it. To delete a leaf
1805 * page we need a copy of a key from the page. We use the 0th page
1806 * index since it's the last key that the page held.
1807 *
1808 * We malloc the page information instead of using the return key/data
1809 * memory because we've already set them -- the reason we've already
1810 * set them is because we're (potentially) about to do a reverse split,
1811 * which would make our saved page information useless.
1812 *
1813 * !!!
1814 * The following operations to delete a page might deadlock. I think
1815 * that's OK. The problem is if we're deleting an item because we're
1816 * closing cursors because we've already deadlocked and want to call
1817 * txn_abort(). If we fail due to deadlock, we leave a locked empty
1818 * page in the tree, which won't be empty long because we're going to
1819 * undo the delete.
1820 */
1821 if (NUM_ENT(h) == 2 && h->pgno != PGNO_ROOT) {
1822 memset(&dbt, 0, sizeof(DBT));
1823 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
1824 if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
1825 goto err;
1826 delete_page = 1;
1827 }
1828
1829 /*
1830 * Do a normal btree delete.
1831 *
1832 * !!!
1833 * Delete the key item first, otherwise the duplicate checks in
1834 * __bam_ditem() won't work!
1835 */
1836 if ((ret = __bam_ditem(dbc, h, indx)) != 0)
1837 goto err;
1838 if ((ret = __bam_ditem(dbc, h, indx)) != 0)
1839 goto err;
1840
1841 /* Discard any remaining locks/pages. */
1842 if (local_page) {
1843 (void)memp_fput(dbp->mpf, h, 0);
1844 (void)__BT_TLPUT(dbc, lock);
1845 local_page = 0;
1846 }
1847
1848 /* Delete the page if it was emptied. */
1849 if (delete_page)
1850 ret = __bam_dpage(dbc, &dbt);
1851
1852 err:
1853 done: if (delete_page)
1854 __os_free(dbt.data, dbt.size);
1855
1856 if (local_page) {
1857 /*
1858 * It's possible for h to be NULL, as __db_drem may have
1859 * been relinking pages by the time that it deadlocked.
1860 */
1861 if (h != NULL)
1862 (void)memp_fput(dbp->mpf, h, 0);
1863 (void)__BT_TLPUT(dbc, lock);
1864 }
1865
1866 if (F_ISSET(dbp, DB_AM_CDB) && F_ISSET(dbc, DBC_RMW))
1867 (void)__lock_downgrade(dbp->dbenv->lk_info, dbc->mylock,
1868 DB_LOCK_IWRITE, 0);
1869
1870 return (ret);
1871 }
1872
1873 /*
1874 * __bam_c_getstack --
1875 * Acquire a full stack for a cursor.
1876 */
1877 static int
1878 __bam_c_getstack(dbc, cp)
1879 DBC *dbc;
1880 CURSOR *cp;
1881 {
1882 DB *dbp;
1883 DBT dbt;
1884 PAGE *h;
1885 db_pgno_t pgno;
1886 int exact, ret;
1887
1888 dbp = dbc->dbp;
1889 h = NULL;
1890 memset(&dbt, 0, sizeof(DBT));
1891 ret = 0;
1892
1893 /* Get the page with the current item on it. */
1894 pgno = cp->pgno;
1895 if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
1896 return (ret);
1897
1898 /* Get a copy of a key from the page. */
1899 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
1900 if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
1901 goto err;
1902
1903 /* Get a write-locked stack for that page. */
1904 exact = 0;
1905 ret = __bam_search(dbc, &dbt, S_KEYFIRST, 1, NULL, &exact);
1906
1907 /* We no longer need the key or the page. */
1908 err: if (h != NULL)
1909 (void)memp_fput(dbp->mpf, h, 0);
1910 if (dbt.data != NULL)
1911 __os_free(dbt.data, dbt.size);
1912 return (ret);
1913 }
unleashed repo fork