1*0Sstevel@tonic-gate /*-
2*0Sstevel@tonic-gate * See the file LICENSE for redistribution information.
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * Copyright (c) 1996, 1997, 1998
5*0Sstevel@tonic-gate * Sleepycat Software. All rights reserved.
6*0Sstevel@tonic-gate */
7*0Sstevel@tonic-gate /*
8*0Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994, 1995, 1996
9*0Sstevel@tonic-gate * Keith Bostic. All rights reserved.
10*0Sstevel@tonic-gate */
11*0Sstevel@tonic-gate /*
12*0Sstevel@tonic-gate * Copyright (c) 1990, 1993, 1994, 1995
13*0Sstevel@tonic-gate * The Regents of the University of California. All rights reserved.
14*0Sstevel@tonic-gate *
15*0Sstevel@tonic-gate * This code is derived from software contributed to Berkeley by
16*0Sstevel@tonic-gate * Mike Olson.
17*0Sstevel@tonic-gate *
18*0Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without
19*0Sstevel@tonic-gate * modification, are permitted provided that the following conditions
20*0Sstevel@tonic-gate * are met:
21*0Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright
22*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer.
23*0Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright
24*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the
25*0Sstevel@tonic-gate * documentation and/or other materials provided with the distribution.
26*0Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software
27*0Sstevel@tonic-gate * must display the following acknowledgement:
28*0Sstevel@tonic-gate * This product includes software developed by the University of
29*0Sstevel@tonic-gate * California, Berkeley and its contributors.
30*0Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors
31*0Sstevel@tonic-gate * may be used to endorse or promote products derived from this software
32*0Sstevel@tonic-gate * without specific prior written permission.
33*0Sstevel@tonic-gate *
34*0Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35*0Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36*0Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37*0Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38*0Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39*0Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40*0Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41*0Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42*0Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43*0Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44*0Sstevel@tonic-gate * SUCH DAMAGE.
45*0Sstevel@tonic-gate */
46*0Sstevel@tonic-gate
47*0Sstevel@tonic-gate #include "config.h"
48*0Sstevel@tonic-gate
49*0Sstevel@tonic-gate #ifndef lint
50*0Sstevel@tonic-gate static const char sccsid[] = "@(#)bt_compare.c 10.14 (Sleepycat) 10/9/98";
51*0Sstevel@tonic-gate #endif /* not lint */
52*0Sstevel@tonic-gate
53*0Sstevel@tonic-gate #ifndef NO_SYSTEM_INCLUDES
54*0Sstevel@tonic-gate #include <sys/types.h>
55*0Sstevel@tonic-gate
56*0Sstevel@tonic-gate #include <string.h>
57*0Sstevel@tonic-gate #endif
58*0Sstevel@tonic-gate
59*0Sstevel@tonic-gate #include "db_int.h"
60*0Sstevel@tonic-gate #include "db_page.h"
61*0Sstevel@tonic-gate #include "btree.h"
62*0Sstevel@tonic-gate
63*0Sstevel@tonic-gate /*
64*0Sstevel@tonic-gate * __bam_cmp --
65*0Sstevel@tonic-gate * Compare a key to a given record.
66*0Sstevel@tonic-gate *
67*0Sstevel@tonic-gate * PUBLIC: int __bam_cmp __P((DB *, const DBT *,
68*0Sstevel@tonic-gate * PUBLIC: PAGE *, u_int32_t, int (*)(const DBT *, const DBT *)));
69*0Sstevel@tonic-gate */
70*0Sstevel@tonic-gate int
__bam_cmp(dbp,dbt,h,indx,func)71*0Sstevel@tonic-gate __bam_cmp(dbp, dbt, h, indx, func)
72*0Sstevel@tonic-gate DB *dbp;
73*0Sstevel@tonic-gate const DBT *dbt;
74*0Sstevel@tonic-gate PAGE *h;
75*0Sstevel@tonic-gate u_int32_t indx;
76*0Sstevel@tonic-gate int (*func)__P((const DBT *, const DBT *));
77*0Sstevel@tonic-gate {
78*0Sstevel@tonic-gate BINTERNAL *bi;
79*0Sstevel@tonic-gate BKEYDATA *bk;
80*0Sstevel@tonic-gate BOVERFLOW *bo;
81*0Sstevel@tonic-gate DBT pg_dbt;
82*0Sstevel@tonic-gate int ret;
83*0Sstevel@tonic-gate
84*0Sstevel@tonic-gate /*
85*0Sstevel@tonic-gate * Returns:
86*0Sstevel@tonic-gate * < 0 if dbt is < page record
87*0Sstevel@tonic-gate * = 0 if dbt is = page record
88*0Sstevel@tonic-gate * > 0 if dbt is > page record
89*0Sstevel@tonic-gate *
90*0Sstevel@tonic-gate * !!!
91*0Sstevel@tonic-gate * We do not clear the pg_dbt DBT even though it's likely to contain
92*0Sstevel@tonic-gate * random bits. That should be okay, because the app's comparison
93*0Sstevel@tonic-gate * routine had better not be looking at fields other than data/size.
94*0Sstevel@tonic-gate * We don't clear it because we go through this path a lot and it's
95*0Sstevel@tonic-gate * expensive.
96*0Sstevel@tonic-gate */
97*0Sstevel@tonic-gate if (TYPE(h) == P_LBTREE || TYPE(h) == P_DUPLICATE) {
98*0Sstevel@tonic-gate bk = GET_BKEYDATA(h, indx);
99*0Sstevel@tonic-gate if (B_TYPE(bk->type) == B_OVERFLOW)
100*0Sstevel@tonic-gate bo = (BOVERFLOW *)bk;
101*0Sstevel@tonic-gate else {
102*0Sstevel@tonic-gate pg_dbt.data = bk->data;
103*0Sstevel@tonic-gate pg_dbt.size = bk->len;
104*0Sstevel@tonic-gate return (func(dbt, &pg_dbt));
105*0Sstevel@tonic-gate }
106*0Sstevel@tonic-gate } else {
107*0Sstevel@tonic-gate /*
108*0Sstevel@tonic-gate * The following code guarantees that the left-most key on an
109*0Sstevel@tonic-gate * internal page at any level of the btree is less than any
110*0Sstevel@tonic-gate * user specified key. This saves us from having to update the
111*0Sstevel@tonic-gate * leftmost key on an internal page when the user inserts a new
112*0Sstevel@tonic-gate * key in the tree smaller than anything we've seen before.
113*0Sstevel@tonic-gate */
114*0Sstevel@tonic-gate if (indx == 0 && h->prev_pgno == PGNO_INVALID)
115*0Sstevel@tonic-gate return (1);
116*0Sstevel@tonic-gate
117*0Sstevel@tonic-gate bi = GET_BINTERNAL(h, indx);
118*0Sstevel@tonic-gate if (B_TYPE(bi->type) == B_OVERFLOW)
119*0Sstevel@tonic-gate bo = (BOVERFLOW *)(bi->data);
120*0Sstevel@tonic-gate else {
121*0Sstevel@tonic-gate pg_dbt.data = bi->data;
122*0Sstevel@tonic-gate pg_dbt.size = bi->len;
123*0Sstevel@tonic-gate return (func(dbt, &pg_dbt));
124*0Sstevel@tonic-gate }
125*0Sstevel@tonic-gate }
126*0Sstevel@tonic-gate
127*0Sstevel@tonic-gate /*
128*0Sstevel@tonic-gate * Overflow.
129*0Sstevel@tonic-gate *
130*0Sstevel@tonic-gate * XXX
131*0Sstevel@tonic-gate * We ignore __db_moff() errors, because we have no way of returning
132*0Sstevel@tonic-gate * them.
133*0Sstevel@tonic-gate */
134*0Sstevel@tonic-gate (void) __db_moff(dbp,
135*0Sstevel@tonic-gate dbt, bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, &ret);
136*0Sstevel@tonic-gate return (ret);
137*0Sstevel@tonic-gate }
138*0Sstevel@tonic-gate
139*0Sstevel@tonic-gate /*
140*0Sstevel@tonic-gate * __bam_defcmp --
141*0Sstevel@tonic-gate * Default comparison routine.
142*0Sstevel@tonic-gate *
143*0Sstevel@tonic-gate * PUBLIC: int __bam_defcmp __P((const DBT *, const DBT *));
144*0Sstevel@tonic-gate */
145*0Sstevel@tonic-gate int
__bam_defcmp(a,b)146*0Sstevel@tonic-gate __bam_defcmp(a, b)
147*0Sstevel@tonic-gate const DBT *a, *b;
148*0Sstevel@tonic-gate {
149*0Sstevel@tonic-gate size_t len;
150*0Sstevel@tonic-gate u_int8_t *p1, *p2;
151*0Sstevel@tonic-gate
152*0Sstevel@tonic-gate /*
153*0Sstevel@tonic-gate * Returns:
154*0Sstevel@tonic-gate * < 0 if a is < b
155*0Sstevel@tonic-gate * = 0 if a is = b
156*0Sstevel@tonic-gate * > 0 if a is > b
157*0Sstevel@tonic-gate *
158*0Sstevel@tonic-gate * XXX
159*0Sstevel@tonic-gate * If a size_t doesn't fit into a long, or if the difference between
160*0Sstevel@tonic-gate * any two characters doesn't fit into an int, this routine can lose.
161*0Sstevel@tonic-gate * What we need is a signed integral type that's guaranteed to be at
162*0Sstevel@tonic-gate * least as large as a size_t, and there is no such thing.
163*0Sstevel@tonic-gate */
164*0Sstevel@tonic-gate len = a->size > b->size ? b->size : a->size;
165*0Sstevel@tonic-gate for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
166*0Sstevel@tonic-gate if (*p1 != *p2)
167*0Sstevel@tonic-gate return ((long)*p1 - (long)*p2);
168*0Sstevel@tonic-gate return ((long)a->size - (long)b->size);
169*0Sstevel@tonic-gate }
170*0Sstevel@tonic-gate
171*0Sstevel@tonic-gate /*
172*0Sstevel@tonic-gate * __bam_defpfx --
173*0Sstevel@tonic-gate * Default prefix routine.
174*0Sstevel@tonic-gate *
175*0Sstevel@tonic-gate * PUBLIC: size_t __bam_defpfx __P((const DBT *, const DBT *));
176*0Sstevel@tonic-gate */
177*0Sstevel@tonic-gate size_t
__bam_defpfx(a,b)178*0Sstevel@tonic-gate __bam_defpfx(a, b)
179*0Sstevel@tonic-gate const DBT *a, *b;
180*0Sstevel@tonic-gate {
181*0Sstevel@tonic-gate size_t cnt, len;
182*0Sstevel@tonic-gate u_int8_t *p1, *p2;
183*0Sstevel@tonic-gate
184*0Sstevel@tonic-gate cnt = 1;
185*0Sstevel@tonic-gate len = a->size > b->size ? b->size : a->size;
186*0Sstevel@tonic-gate for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
187*0Sstevel@tonic-gate if (*p1 != *p2)
188*0Sstevel@tonic-gate return (cnt);
189*0Sstevel@tonic-gate
190*0Sstevel@tonic-gate /*
191*0Sstevel@tonic-gate * We know that a->size must be <= b->size, or they wouldn't be
192*0Sstevel@tonic-gate * in this order.
193*0Sstevel@tonic-gate */
194*0Sstevel@tonic-gate return (a->size < b->size ? a->size + 1 : a->size);
195*0Sstevel@tonic-gate }
196