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
50static 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 */
70int
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 */
145int
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 */
177size_t
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