source: trunk/third/db/btree/bt_compare.c @ 17055

Revision 17055, 5.9 KB checked in by ghudson, 23 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r17054, which included commits to RCS files with non-trunk default branches.
Line 
1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 1997, 1998, 1999, 2000
5 *      Sleepycat Software.  All rights reserved.
6 */
7/*
8 * Copyright (c) 1990, 1993, 1994, 1995, 1996
9 *      Keith Bostic.  All rights reserved.
10 */
11/*
12 * Copyright (c) 1990, 1993, 1994, 1995
13 *      The Regents of the University of California.  All rights reserved.
14 *
15 * This code is derived from software contributed to Berkeley by
16 * Mike Olson.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 *    notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 *    notice, this list of conditions and the following disclaimer in the
25 *    documentation and/or other materials provided with the distribution.
26 * 3. Neither the name of the University nor the names of its contributors
27 *    may be used to endorse or promote products derived from this software
28 *    without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 */
42
43#include "db_config.h"
44
45#ifndef lint
46static const char revid[] = "$Id: bt_compare.c,v 1.1.1.2 2002-02-11 16:30:02 ghudson Exp $";
47#endif /* not lint */
48
49#ifndef NO_SYSTEM_INCLUDES
50#include <sys/types.h>
51#endif
52
53#include "db_int.h"
54#include "db_page.h"
55#include "btree.h"
56
57/*
58 * __bam_cmp --
59 *      Compare a key to a given record.
60 *
61 * PUBLIC: int __bam_cmp __P((DB *, const DBT *,
62 * PUBLIC:    PAGE *, u_int32_t, int (*)(const DBT *, const DBT *), int *));
63 */
64int
65__bam_cmp(dbp, dbt, h, indx, func, cmpp)
66        DB *dbp;
67        const DBT *dbt;
68        PAGE *h;
69        u_int32_t indx;
70        int (*func)__P((const DBT *, const DBT *));
71        int *cmpp;
72{
73        BINTERNAL *bi;
74        BKEYDATA *bk;
75        BOVERFLOW *bo;
76        DBT pg_dbt;
77
78        /*
79         * Returns:
80         *      < 0 if dbt is < page record
81         *      = 0 if dbt is = page record
82         *      > 0 if dbt is > page record
83         *
84         * !!!
85         * We do not clear the pg_dbt DBT even though it's likely to contain
86         * random bits.  That should be okay, because the app's comparison
87         * routine had better not be looking at fields other than data/size.
88         * We don't clear it because we go through this path a lot and it's
89         * expensive.
90         */
91        switch (TYPE(h)) {
92        case P_LBTREE:
93        case P_LDUP:
94        case P_LRECNO:
95                bk = GET_BKEYDATA(h, indx);
96                if (B_TYPE(bk->type) == B_OVERFLOW)
97                        bo = (BOVERFLOW *)bk;
98                else {
99                        pg_dbt.data = bk->data;
100                        pg_dbt.size = bk->len;
101                        pg_dbt.app_private = NULL;
102                        *cmpp = func(dbt, &pg_dbt);
103                        return (0);
104                }
105                break;
106        case P_IBTREE:
107                /*
108                 * The following code guarantees that the left-most key on an
109                 * internal page at any place in the tree sorts less than any
110                 * user-specified key.  The reason is that if we have reached
111                 * this internal page, we know the user key must sort greater
112                 * than the key we're storing for this page in any internal
113                 * pages at levels above us in the tree.  It then follows that
114                 * any user-specified key cannot sort less than the first page
115                 * which we reference, and so there's no reason to call the
116                 * comparison routine.  While this may save us a comparison
117                 * routine call or two, the real reason for this is because
118                 * we don't maintain a copy of the smallest key in the tree,
119                 * so that we don't have to update all the levels of the tree
120                 * should the application store a new smallest key.  And, so,
121                 * we may not have a key to compare, which makes doing the
122                 * comparison difficult and error prone.
123                 */
124                if (indx == 0) {
125                        *cmpp = 1;
126                        return (0);
127                }
128
129                bi = GET_BINTERNAL(h, indx);
130                if (B_TYPE(bi->type) == B_OVERFLOW)
131                        bo = (BOVERFLOW *)(bi->data);
132                else {
133                        pg_dbt.data = bi->data;
134                        pg_dbt.size = bi->len;
135                        pg_dbt.app_private = NULL;
136                        *cmpp = func(dbt, &pg_dbt);
137                        return (0);
138                }
139                break;
140        default:
141                return (__db_pgfmt(dbp, PGNO(h)));
142        }
143
144        /*
145         * Overflow.
146         */
147        return (__db_moff(dbp, dbt,
148            bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, cmpp));
149}
150
151/*
152 * __bam_defcmp --
153 *      Default comparison routine.
154 *
155 * PUBLIC: int __bam_defcmp __P((const DBT *, const DBT *));
156 */
157int
158__bam_defcmp(a, b)
159        const DBT *a, *b;
160{
161        size_t len;
162        u_int8_t *p1, *p2;
163
164        /*
165         * Returns:
166         *      < 0 if a is < b
167         *      = 0 if a is = b
168         *      > 0 if a is > b
169         *
170         * XXX
171         * If a size_t doesn't fit into a long, or if the difference between
172         * any two characters doesn't fit into an int, this routine can lose.
173         * What we need is a signed integral type that's guaranteed to be at
174         * least as large as a size_t, and there is no such thing.
175         */
176        len = a->size > b->size ? b->size : a->size;
177        for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
178                if (*p1 != *p2)
179                        return ((long)*p1 - (long)*p2);
180        return ((long)a->size - (long)b->size);
181}
182
183/*
184 * __bam_defpfx --
185 *      Default prefix routine.
186 *
187 * PUBLIC: size_t __bam_defpfx __P((const DBT *, const DBT *));
188 */
189size_t
190__bam_defpfx(a, b)
191        const DBT *a, *b;
192{
193        size_t cnt, len;
194        u_int8_t *p1, *p2;
195
196        cnt = 1;
197        len = a->size > b->size ? b->size : a->size;
198        for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
199                if (*p1 != *p2)
200                        return (cnt);
201
202        /*
203         * We know that a->size must be <= b->size, or they wouldn't be
204         * in this order.
205         */
206        return (a->size < b->size ? a->size + 1 : a->size);
207}
Note: See TracBrowser for help on using the repository browser.