1N/A/*-
1N/A * See the file LICENSE for redistribution information.
1N/A *
1N/A * Copyright (c) 1996, 1997, 1998
1N/A * Sleepycat Software. All rights reserved.
1N/A */
1N/A/*
1N/A * Copyright (c) 1990, 1993, 1994, 1995, 1996
1N/A * Keith Bostic. All rights reserved.
1N/A */
1N/A/*
1N/A * Copyright (c) 1990, 1993, 1994, 1995
1N/A * The Regents of the University of California. All rights reserved.
1N/A *
1N/A * This code is derived from software contributed to Berkeley by
1N/A * Mike Olson.
1N/A *
1N/A * Redistribution and use in source and binary forms, with or without
1N/A * modification, are permitted provided that the following conditions
1N/A * are met:
1N/A * 1. Redistributions of source code must retain the above copyright
1N/A * notice, this list of conditions and the following disclaimer.
1N/A * 2. Redistributions in binary form must reproduce the above copyright
1N/A * notice, this list of conditions and the following disclaimer in the
1N/A * documentation and/or other materials provided with the distribution.
1N/A * 3. All advertising materials mentioning features or use of this software
1N/A * must display the following acknowledgement:
1N/A * This product includes software developed by the University of
1N/A * California, Berkeley and its contributors.
1N/A * 4. Neither the name of the University nor the names of its contributors
1N/A * may be used to endorse or promote products derived from this software
1N/A * without specific prior written permission.
1N/A *
1N/A * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1N/A * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1N/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1N/A * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1N/A * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1N/A * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1N/A * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1N/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1N/A * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1N/A * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1N/A * SUCH DAMAGE.
1N/A */
1N/A
1N/A#include "config.h"
1N/A
1N/A#ifndef lint
1N/Astatic const char sccsid[] = "@(#)bt_compare.c 10.14 (Sleepycat) 10/9/98";
1N/A#endif /* not lint */
1N/A
1N/A#ifndef NO_SYSTEM_INCLUDES
1N/A#include <sys/types.h>
1N/A
1N/A#include <string.h>
1N/A#endif
1N/A
1N/A#include "db_int.h"
1N/A#include "db_page.h"
1N/A#include "btree.h"
1N/A
1N/A/*
1N/A * __bam_cmp --
1N/A * Compare a key to a given record.
1N/A *
1N/A * PUBLIC: int __bam_cmp __P((DB *, const DBT *,
1N/A * PUBLIC: PAGE *, u_int32_t, int (*)(const DBT *, const DBT *)));
1N/A */
1N/Aint
1N/A__bam_cmp(dbp, dbt, h, indx, func)
1N/A DB *dbp;
1N/A const DBT *dbt;
1N/A PAGE *h;
1N/A u_int32_t indx;
1N/A int (*func)__P((const DBT *, const DBT *));
1N/A{
1N/A BINTERNAL *bi;
1N/A BKEYDATA *bk;
1N/A BOVERFLOW *bo;
1N/A DBT pg_dbt;
1N/A int ret;
1N/A
1N/A /*
1N/A * Returns:
1N/A * < 0 if dbt is < page record
1N/A * = 0 if dbt is = page record
1N/A * > 0 if dbt is > page record
1N/A *
1N/A * !!!
1N/A * We do not clear the pg_dbt DBT even though it's likely to contain
1N/A * random bits. That should be okay, because the app's comparison
1N/A * routine had better not be looking at fields other than data/size.
1N/A * We don't clear it because we go through this path a lot and it's
1N/A * expensive.
1N/A */
1N/A if (TYPE(h) == P_LBTREE || TYPE(h) == P_DUPLICATE) {
1N/A bk = GET_BKEYDATA(h, indx);
1N/A if (B_TYPE(bk->type) == B_OVERFLOW)
1N/A bo = (BOVERFLOW *)bk;
1N/A else {
1N/A pg_dbt.data = bk->data;
1N/A pg_dbt.size = bk->len;
1N/A return (func(dbt, &pg_dbt));
1N/A }
1N/A } else {
1N/A /*
1N/A * The following code guarantees that the left-most key on an
1N/A * internal page at any level of the btree is less than any
1N/A * user specified key. This saves us from having to update the
1N/A * leftmost key on an internal page when the user inserts a new
1N/A * key in the tree smaller than anything we've seen before.
1N/A */
1N/A if (indx == 0 && h->prev_pgno == PGNO_INVALID)
1N/A return (1);
1N/A
1N/A bi = GET_BINTERNAL(h, indx);
1N/A if (B_TYPE(bi->type) == B_OVERFLOW)
1N/A bo = (BOVERFLOW *)(bi->data);
1N/A else {
1N/A pg_dbt.data = bi->data;
1N/A pg_dbt.size = bi->len;
1N/A return (func(dbt, &pg_dbt));
1N/A }
1N/A }
1N/A
1N/A /*
1N/A * Overflow.
1N/A *
1N/A * XXX
1N/A * We ignore __db_moff() errors, because we have no way of returning
1N/A * them.
1N/A */
1N/A (void) __db_moff(dbp,
1N/A dbt, bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, &ret);
1N/A return (ret);
1N/A}
1N/A
1N/A/*
1N/A * __bam_defcmp --
1N/A * Default comparison routine.
1N/A *
1N/A * PUBLIC: int __bam_defcmp __P((const DBT *, const DBT *));
1N/A */
1N/Aint
1N/A__bam_defcmp(a, b)
1N/A const DBT *a, *b;
1N/A{
1N/A size_t len;
1N/A u_int8_t *p1, *p2;
1N/A
1N/A /*
1N/A * Returns:
1N/A * < 0 if a is < b
1N/A * = 0 if a is = b
1N/A * > 0 if a is > b
1N/A *
1N/A * XXX
1N/A * If a size_t doesn't fit into a long, or if the difference between
1N/A * any two characters doesn't fit into an int, this routine can lose.
1N/A * What we need is a signed integral type that's guaranteed to be at
1N/A * least as large as a size_t, and there is no such thing.
1N/A */
1N/A len = a->size > b->size ? b->size : a->size;
1N/A for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
1N/A if (*p1 != *p2)
1N/A return ((long)*p1 - (long)*p2);
1N/A return ((long)a->size - (long)b->size);
1N/A}
1N/A
1N/A/*
1N/A * __bam_defpfx --
1N/A * Default prefix routine.
1N/A *
1N/A * PUBLIC: size_t __bam_defpfx __P((const DBT *, const DBT *));
1N/A */
1N/Asize_t
1N/A__bam_defpfx(a, b)
1N/A const DBT *a, *b;
1N/A{
1N/A size_t cnt, len;
1N/A u_int8_t *p1, *p2;
1N/A
1N/A cnt = 1;
1N/A len = a->size > b->size ? b->size : a->size;
1N/A for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
1N/A if (*p1 != *p2)
1N/A return (cnt);
1N/A
1N/A /*
1N/A * We know that a->size must be <= b->size, or they wouldn't be
1N/A * in this order.
1N/A */
1N/A return (a->size < b->size ? a->size + 1 : a->size);
1N/A}