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