diff options
Diffstat (limited to 'lib/libc/db/btree/bt_search.c')
| -rw-r--r-- | lib/libc/db/btree/bt_search.c | 152 |
1 files changed, 134 insertions, 18 deletions
diff --git a/lib/libc/db/btree/bt_search.c b/lib/libc/db/btree/bt_search.c index 06aba1126bda8..a164173d01738 100644 --- a/lib/libc/db/btree/bt_search.c +++ b/lib/libc/db/btree/bt_search.c @@ -35,7 +35,7 @@ */ #if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)bt_search.c 8.1 (Berkeley) 6/4/93"; +static char sccsid[] = "@(#)bt_search.c 8.4 (Berkeley) 12/10/93"; #endif /* LIBC_SCCS and not lint */ #include <sys/types.h> @@ -45,6 +45,9 @@ static char sccsid[] = "@(#)bt_search.c 8.1 (Berkeley) 6/4/93"; #include <db.h> #include "btree.h" +static int bt_snext __P((BTREE *, PAGE *, const DBT *, int *)); +static int bt_sprev __P((BTREE *, PAGE *, const DBT *, int *)); + /* * __BT_SEARCH -- Search a btree for a key. * @@ -54,12 +57,9 @@ static char sccsid[] = "@(#)bt_search.c 8.1 (Berkeley) 6/4/93"; * exactp: pointer to exact match flag * * Returns: - * EPG for matching record, if any, or the EPG for the location of the - * key, if it were inserted into the tree. - * - * Warnings: - * The EPG returned is in static memory, and will be overwritten by the - * next search of any kind in any tree. + * The EPG for matching record, if any, or the EPG for the location + * of the key, if it were inserted into the tree, is entered into + * the bt_cur field of the tree. A pointer to the field is returned. */ EPG * __bt_search(t, key, exactp) @@ -67,11 +67,10 @@ __bt_search(t, key, exactp) const DBT *key; int *exactp; { - register indx_t index; - register int base, cmp, lim; - register PAGE *h; + PAGE *h, *n; + indx_t index; pgno_t pg; - static EPG e; + int base, cmp, lim; BT_CLR(t); for (pg = P_ROOT;;) { @@ -79,13 +78,13 @@ __bt_search(t, key, exactp) return (NULL); /* Do a binary search on the current page. */ - e.page = h; + t->bt_cur.page = h; for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { - e.index = index = base + (lim >> 1); - if ((cmp = __bt_cmp(t, key, &e)) == 0) { + t->bt_cur.index = index = base + (lim >> 1); + if ((cmp = __bt_cmp(t, key, &t->bt_cur)) == 0) { if (h->flags & P_BLEAF) { *exactp = 1; - return (&e); + return (&t->bt_cur); } goto next; } @@ -95,11 +94,26 @@ __bt_search(t, key, exactp) } } - /* If it's a leaf page, we're done. */ + /* + * If it's a leaf page, and duplicates aren't allowed, we're + * done. If duplicates are allowed, it's possible that there + * were duplicate keys on duplicate pages, and they were later + * deleted, so we could be on a page with no matches while + * there are matches on other pages. If we're at the start or + * end of a page, check on both sides. + */ if (h->flags & P_BLEAF) { - e.index = base; + t->bt_cur.index = base; *exactp = 0; - return (&e); + if (!ISSET(t, B_NODUPS)) { + if (base == 0 && + bt_sprev(t, h, key, exactp)) + return (&t->bt_cur); + if (base == NEXTINDEX(h) && + bt_snext(t, h, key, exactp)) + return (&t->bt_cur); + } + return (&t->bt_cur); } /* @@ -117,3 +131,105 @@ next: if (__bt_push(t, h->pgno, index) == RET_ERROR) mpool_put(t->bt_mp, h, 0); } } + +/* + * BT_SNEXT -- Check for an exact match after the key. + * + * Parameters: + * t: tree to search + * h: current page. + * key: key to find + * exactp: pointer to exact match flag + * + * Returns: + * If an exact match found. + */ +static int +bt_snext(t, h, key, exactp) + BTREE *t; + PAGE *h; + const DBT *key; + int *exactp; +{ + EPG e; + PAGE *tp; + pgno_t pg; + + /* Skip until reach the end of the tree or a key. */ + for (pg = h->nextpg; pg != P_INVALID;) { + if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { + mpool_put(t->bt_mp, h, 0); + return (NULL); + } + if (NEXTINDEX(tp) != 0) + break; + pg = tp->prevpg; + mpool_put(t->bt_mp, tp, 0); + } + /* + * The key is either an exact match, or not as good as + * the one we already have. + */ + if (pg != P_INVALID) { + e.page = tp; + e.index = NEXTINDEX(tp) - 1; + if (__bt_cmp(t, key, &e) == 0) { + mpool_put(t->bt_mp, h, 0); + t->bt_cur = e; + *exactp = 1; + return (1); + } + } + return (0); +} + +/* + * BT_SPREV -- Check for an exact match before the key. + * + * Parameters: + * t: tree to search + * h: current page. + * key: key to find + * exactp: pointer to exact match flag + * + * Returns: + * If an exact match found. + */ +static int +bt_sprev(t, h, key, exactp) + BTREE *t; + PAGE *h; + const DBT *key; + int *exactp; +{ + EPG e; + PAGE *tp; + pgno_t pg; + + /* Skip until reach the beginning of the tree or a key. */ + for (pg = h->prevpg; pg != P_INVALID;) { + if ((tp = mpool_get(t->bt_mp, pg, 0)) == NULL) { + mpool_put(t->bt_mp, h, 0); + return (NULL); + } + if (NEXTINDEX(tp) != 0) + break; + pg = tp->prevpg; + mpool_put(t->bt_mp, tp, 0); + } + /* + * The key is either an exact match, or not as good as + * the one we already have. + */ + if (pg != P_INVALID) { + e.page = tp; + e.index = NEXTINDEX(tp) - 1; + if (__bt_cmp(t, key, &e) == 0) { + mpool_put(t->bt_mp, h, 0); + t->bt_cur = e; + *exactp = 1; + return (1); + } + } + return (0); +} |