/*- * Copyright (c) 1990 The Regents of the University of California. * All rights reserved. * * This code is derived from software contributed to Berkeley by * Mike Olson. * * %sccs.include.redist.c% */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)bt_search.c 5.1 (Berkeley) 01/23/91"; #endif /* LIBC_SCCS and not lint */ #include #include #include "btree.h" /* * _BT_FIRST -- Find the first item in the tree that matches the supplied * key. * * This routine supports deletion. When the user supplies a key to * be deleted, we find the first one, and iteratively delete all the * matching ones that follow it. * * Parameters: * t -- btree in which to find first occurrence * key -- key to find * * Returns: * The BTITEM for the matching item. If there's no match, * this may point to the first item > than the supplied key, * or off the end of the page. * * Warnings: * The BTITEM returned is in static space and will be overwritten * by the next search of any kind in any btree. */ BTITEM * _bt_first(t, key) BTREE_P t; DBT *key; { BTHEADER *h; BTITEM *item; index_t next; int r; /* find any matching item */ item = _bt_search(t, key); h = t->bt_curpage; next = NEXTINDEX(h); /* if we're off the end of the page, search failed and we're done */ if (item->bti_index >= next) return (item); /* as long as we have an exact match, walk backwards */ while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) { /* at start of page? */ if (item->bti_index == 0) { /* if no prev page, we're done */ if (h->h_prevpg == P_NONE) return (item); /* walk backward, skipping empty pages */ do { if (_bt_getpage(t, h->h_prevpg) == RET_ERROR) return ((BTITEM *) NULL); h = t->bt_curpage; } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE); if (NEXTINDEX(h) != 0) item->bti_index = NEXTINDEX(h) - 1; else item->bti_index = 0; item->bti_pgno = h->h_pgno; } else { item->bti_index--; } } /* if we went too far backwards, step forward one entry */ if (r > 0) { if (++(item->bti_index) >= NEXTINDEX(h) && h->h_nextpg != P_NONE) { /* walk forward, skipping empty pages */ do { if (_bt_getpage(t, h->h_nextpg) == RET_ERROR) return ((BTITEM *) NULL); h = t->bt_curpage; } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0); item->bti_index = 0; item->bti_pgno = h->h_pgno; } } /* got it */ return (item); } /* * _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree. * * Parameters: * t -- btree in which to search * key -- key to find * * Returns: * BTITEM for matching item, if any, or the BTITEM for the * location of the key, if it were in the tree. * * Warnings: * The BTITEM returned is in static memory, and will be * overwritten by the next search of any kind in any tree. */ BTITEM * _bt_search(t, key) BTREE_P t; DBT *key; { /* we want to start all of our searches at the root */ if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR) return ((BTITEM *) NULL); return (_bt_searchr(t, key)); } BTITEM * _bt_searchr(t, key) BTREE_P t; DBT *key; { BTHEADER *h = t->bt_curpage; index_t index; IDATUM *id; DATUM *d; static BTITEM item; /* do a binary search on the current page */ index = _bt_binsrch(t, &(key->data[0])); /* * At this point, the binary search terminated because the endpoints * got too close together, or we have a match. Figure out which * case applies and decide what to do based on the page type. */ if (h->h_flags & F_LEAF) { item.bti_pgno = h->h_pgno; item.bti_index = index; if (index < NEXTINDEX(h)) d = (DATUM *) GETDATUM(h,index); else d = (DATUM *) NULL; item.bti_datum = d; return(&item); } else { id = (IDATUM *) GETDATUM(h, index); if (_bt_push(t, h->h_pgno) == RET_ERROR) return ((BTITEM *) NULL); if (_bt_getpage(t, id->i_pgno) == RET_ERROR) return ((BTITEM *) NULL); return (_bt_searchr(t, key)); } } /* * _BT_BINSRCH -- Do a binary search for a given key on the current page. * * Searches on internal pages are handled slightly differently from * searches on leaf pages. This is because internal page searches * find the largest item <= key in the tree, and leaf searches find * the smallest item >= key. This guarantees that leaf page searches * leave us pointing at the item's correct position, and internal * searches descend the tree correctly. * * Parameters: * t -- tree to search * key -- key we're looking for * * Returns: * Index of the line pointer array entry for the (closest) * match to key on the current page, with "closest" as defined * above. */ index_t _bt_binsrch(t, key) BTREE_P t; char *key; { index_t lbound, ubound, cur; BTHEADER *h = t->bt_curpage; int match = 0; int r; lbound = 0; ubound = NEXTINDEX(h); if (ubound > 0) --ubound; /* do a binary search on the current page */ while ((ubound - lbound) > 1) { cur = lbound + ((ubound - lbound) / 2); r = _bt_cmp(t, key, cur); if (r > 0) lbound = cur + 1; else if (r < 0) ubound = cur; else { match++; break; } } /* * At this point, the binary search terminated because the endpoints * got too close together, or we have a match. Figure out which * case applies, decide what to do based on the page type (leaf or * internal), and do the right thing. */ if (match) { return (cur); } else if (ubound != lbound) { if (h->h_flags & F_LEAF) { r = _bt_cmp(t, key, lbound); if (r <= 0) { return (lbound); } } else { r = _bt_cmp(t, key, ubound); /* for internal nodes, move as far left as possible */ if (r < 0) { r = _bt_cmp(t, key, lbound); if (r < 0 && lbound > 0) --lbound; return (lbound); } else { return (ubound); } } } if (h->h_flags & F_LEAF) { if (ubound < NEXTINDEX(h)) { r = _bt_cmp(t, key, ubound); if (r > 0) ubound++; } } else { /* for internal pages, move as far left as possible */ if (ubound == NEXTINDEX(h)) ubound--; while (_bt_cmp(t, key, ubound) < 0) ubound--; } return (ubound); }