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