Libc-320.tar.gz

[apple/libc.git] / db / btree / bt_search.c

diff --git a/db/btree/bt_search.c b/db/btree/bt_search.c
index 67a0f6c529bbda82f5275d47bc524ae9bafbb4d2..f9296613555087cfb33bac6a894cc50004276cd8 100644 (file)
--- a/db/btree/bt_search.c
+++ b/db/btree/bt_search.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.

  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 


@@ -22,8 +22,8 @@
  * 
  * @APPLE_LICENSE_HEADER_END@
  */
  * 
  * @APPLE_LICENSE_HEADER_END@
  */

-/*
- * Copyright (c) 1990, 1993
+/*-
+ * Copyright (c) 1990, 1993, 1994

  *     The Regents of the University of California.  All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  *     The Regents of the University of California.  All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by


@@ -58,6 +58,10 @@
  * SUCH DAMAGE.
  */
 
  * SUCH DAMAGE.
  */
 

+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)bt_search.c        8.8 (Berkeley) 7/31/94";
+#endif /* LIBC_SCCS and not lint */
+#include <sys/cdefs.h>

 
 #include <sys/types.h>
 
 
 #include <sys/types.h>
 


@@ -66,11 +70,12 @@
 #include <db.h>
 #include "btree.h"
 
 #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 *));
+static int __bt_snext(BTREE *, PAGE *, const DBT *, int *);
+static int __bt_sprev(BTREE *, PAGE *, const DBT *, int *);

 
 /*
 
 /*

- * __BT_SEARCH -- Search a btree for a key.
+ * __bt_search --
+ *     Search a btree for a key.

  *
  * Parameters:
  *     t:      tree to search
  *
  * Parameters:
  *     t:      tree to search


@@ -116,24 +121,26 @@ __bt_search(t, key, exactp)
                }
 
                /*
                }
 
                /*

-                * 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 it's a leaf page, we're almost done.  If no duplicates
+                * are allowed, or we have an exact match, we're done.  Else,
+                * it's possible that there were matching keys on this page,
+                * which later deleted, and we're on a page with no matches
+                * while there are matches on other pages.  If at the start or
+                * end of a page, check the adjacent page.

                 */
                if (h->flags & P_BLEAF) {
                 */
                if (h->flags & P_BLEAF) {

-                       t->bt_cur.index = base;
-                       *exactp = 0;
-                       if (!ISSET(t, B_NODUPS)) {
+                       if (!F_ISSET(t, B_NODUPS)) {

                                if (base == 0 &&
                                if (base == 0 &&

-                                   bt_sprev(t, h, key, exactp))
+                                   h->prevpg != P_INVALID &&
+                                   __bt_sprev(t, h, key, exactp))

                                        return (&t->bt_cur);
                                if (base == NEXTINDEX(h) &&
                                        return (&t->bt_cur);
                                if (base == NEXTINDEX(h) &&

-                                   bt_snext(t, h, key, exactp))
+                                   h->nextpg != P_INVALID &&
+                                   __bt_snext(t, h, key, exactp))

                                        return (&t->bt_cur);
                        }
                                        return (&t->bt_cur);
                        }

+                       *exactp = 0;
+                       t->bt_cur.index = base;

                        return (&t->bt_cur);
                }
 
                        return (&t->bt_cur);
                }
 


@@ -146,111 +153,86 @@ __bt_search(t, key, exactp)
                 */
                index = base ? base - 1 : base;
 
                 */
                index = base ? base - 1 : base;
 

-next:          if (__bt_push(t, h->pgno, index) == RET_ERROR)
-                       return (NULL);
+next:          BT_PUSH(t, h->pgno, index);

                pg = GETBINTERNAL(h, index)->pgno;
                mpool_put(t->bt_mp, h, 0);
        }
 }
 
 /*
                pg = GETBINTERNAL(h, index)->pgno;
                mpool_put(t->bt_mp, h, 0);
        }
 }
 
 /*

- * BT_SNEXT -- Check for an exact match after the key.
+ * __bt_snext --
+ *     Check for an exact match after the key.

  *
  * Parameters:
  *
  * Parameters:

- *     t:      tree to search
- *     h:      current page.
- *     key:    key to find
+ *     t:      tree
+ *     h:      current page
+ *     key:    key

  *     exactp: pointer to exact match flag
  *
  * Returns:
  *     If an exact match found.
  */
 static int
  *     exactp: pointer to exact match flag
  *
  * Returns:
  *     If an exact match found.
  */
 static int

-bt_snext(t, h, key, exactp)
+__bt_snext(t, h, key, exactp)

        BTREE *t;
        PAGE *h;
        const DBT *key;
        int *exactp;
 {
        EPG e;
        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.
+        * Get the next page.  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);
-               }
+       if ((e.page = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
+               return (0);
+       e.index = 0;
+       if (__bt_cmp(t, key, &e) == 0) {
+               mpool_put(t->bt_mp, h, 0);
+               t->bt_cur = e;
+               *exactp = 1;
+               return (1);

        }
        }

+       mpool_put(t->bt_mp, e.page, 0);

        return (0);
 }
 
 /*
        return (0);
 }
 
 /*

- * BT_SPREV -- Check for an exact match before the key.
+ * __bt_sprev --
+ *     Check for an exact match before the key.

  *
  * Parameters:
  *
  * Parameters:

- *     t:      tree to search
- *     h:      current page.
- *     key:    key to find
+ *     t:      tree
+ *     h:      current page
+ *     key:    key

  *     exactp: pointer to exact match flag
  *
  * Returns:
  *     If an exact match found.
  */
 static int
  *     exactp: pointer to exact match flag
  *
  * Returns:
  *     If an exact match found.
  */
 static int

-bt_sprev(t, h, key, exactp)
+__bt_sprev(t, h, key, exactp)

        BTREE *t;
        PAGE *h;
        const DBT *key;
        int *exactp;
 {
        EPG e;
        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.
+        * Get the previous page.  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);
-               }
+       if ((e.page = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
+               return (0);
+       e.index = NEXTINDEX(e.page) - 1;
+       if (__bt_cmp(t, key, &e) == 0) {
+               mpool_put(t->bt_mp, h, 0);
+               t->bt_cur = e;
+               *exactp = 1;
+               return (1);

        }
        }

+       mpool_put(t->bt_mp, e.page, 0);

        return (0);
 }
        return (0);
 }