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