diff options
Diffstat (limited to 'db2/btree/bt_compare.c')
| -rw-r--r-- | db2/btree/bt_compare.c | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/db2/btree/bt_compare.c b/db2/btree/bt_compare.c new file mode 100644 index 0000000000..e802fd24ab --- /dev/null +++ b/db2/btree/bt_compare.c @@ -0,0 +1,205 @@ +/*- + * See the file LICENSE for redistribution information. + * + * Copyright (c) 1996, 1997 + * Sleepycat Software. All rights reserved. + */ +/* + * Copyright (c) 1990, 1993, 1994, 1995, 1996 + * Keith Bostic. All rights reserved. + */ +/* + * Copyright (c) 1990, 1993, 1994, 1995 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Mike Olson. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "config.h" + +#ifndef lint +static const char sccsid[] = "@(#)bt_compare.c 10.3 (Sleepycat) 7/19/97"; +#endif /* not lint */ + +#ifndef NO_SYSTEM_INCLUDES +#include <sys/types.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#endif + +#include "db_int.h" +#include "db_page.h" +#include "btree.h" + +/* + * __bam_cmp -- + * Compare a key to a given record. + * + * PUBLIC: int __bam_cmp __P((DB *, const DBT *, EPG *)); + */ +int +__bam_cmp(dbp, k1, e) + DB *dbp; + const DBT *k1; + EPG *e; +{ + BINTERNAL *bi; + BKEYDATA *bk; + BOVERFLOW *bo; + BTREE *t; + DBT k2; + PAGE *h; + + t = dbp->internal; + + /* + * Returns: + * < 0 if k1 is < record + * = 0 if k1 is = record + * > 0 if k1 is > record + * + * The left-most key on internal pages, at any level of the tree, is + * guaranteed, by the following code, to be less than any user key. + * This saves us from having to update the leftmost key on an internal + * page when the user inserts a new key in the tree smaller than + * anything we've yet seen. + */ + h = e->page; + if (e->indx == 0 && + h->prev_pgno == PGNO_INVALID && TYPE(h) != P_LBTREE) + return (1); + + bo = NULL; + if (TYPE(h) == P_LBTREE) { + bk = GET_BKEYDATA(h, e->indx); + if (bk->type == B_OVERFLOW) + bo = (BOVERFLOW *)bk; + else { + memset(&k2, 0, sizeof(k2)); + k2.data = bk->data; + k2.size = bk->len; + } + } else { + bi = GET_BINTERNAL(h, e->indx); + if (bi->type == B_OVERFLOW) + bo = (BOVERFLOW *)(bi->data); + else { + memset(&k2, 0, sizeof(k2)); + k2.data = bi->data; + k2.size = bi->len; + } + } + + /* + * XXX + * We ignore system errors; the only recoverable one is ENOMEM, and we + * don't want to require that comparison routines handle random errors. + * We don't want to return a valid comparison, either, so we stop. + */ + if (bo != NULL) { + /* + * If using the default comparison routine, use __db_moff(), + * which compares the overflow key a page at a time. + */ + if (t->bt_compare == __bam_defcmp) + return (__db_moff(dbp, k1, bo->pgno)); + + /* + * Otherwise, we need a contiguous record so we can hand it + * to the user's routine. + */ + if (__db_goff(dbp, &k2, bo->tlen, + bo->pgno, &t->bt_rdata.data, &t->bt_rdata.ulen) != 0) + abort(); + } + return ((*t->bt_compare)(k1, &k2)); +} + +/* + * __bam_defcmp -- + * Default comparison routine. + * + * PUBLIC: int __bam_defcmp __P((const DBT *, const DBT *)); + */ +int +__bam_defcmp(a, b) + const DBT *a, *b; +{ + size_t len; + u_int8_t *p1, *p2; + + /* + * Returns: + * < 0 if a is < b + * = 0 if a is = b + * > 0 if a is > b + * + * XXX + * If a size_t doesn't fit into a long, or if the difference between + * any two characters doesn't fit into an int, this routine can lose. + * What we need is a signed integral type that's guaranteed to be at + * least as large as a size_t, and there is no such thing. + */ + len = a->size > b->size ? b->size : a->size; + for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) + if (*p1 != *p2) + return ((long)*p1 - (long)*p2); + return ((long)a->size - (long)b->size); +} + +/* + * __bam_defpfx -- + * Default prefix routine. + * + * PUBLIC: size_t __bam_defpfx __P((const DBT *, const DBT *)); + */ +size_t +__bam_defpfx(a, b) + const DBT *a, *b; +{ + size_t cnt, len; + u_int8_t *p1, *p2; + + cnt = 1; + len = a->size > b->size ? b->size : a->size; + for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) + if (*p1 != *p2) + return (cnt); + + /* + * We know that a->size must be <= b->size, or they wouldn't be + * in this order. + */ + return (a->size < b->size ? a->size + 1 : a->size); +} |