2
* See the file LICENSE for redistribution information.
4
* Copyright (c) 1996-2003
5
* Sleepycat Software. All rights reserved.
8
* Copyright (c) 1990, 1993, 1994, 1995, 1996
9
* Keith Bostic. All rights reserved.
12
* Copyright (c) 1990, 1993, 1994, 1995
13
* The Regents of the University of California. All rights reserved.
15
* This code is derived from software contributed to Berkeley by
18
* Redistribution and use in source and binary forms, with or without
19
* modification, are permitted provided that the following conditions
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. Neither the name of the University nor the names of its contributors
27
* may be used to endorse or promote products derived from this software
28
* without specific prior written permission.
30
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43
#include "db_config.h"
46
static const char revid[] = "$Id: bt_compare.c,v 11.18 2003/01/08 04:00:56 bostic Exp $";
49
#ifndef NO_SYSTEM_INCLUDES
50
#include <sys/types.h>
54
#include "dbinc/db_page.h"
55
#include "dbinc/btree.h"
59
* Compare a key to a given record.
61
* PUBLIC: int __bam_cmp __P((DB *, const DBT *, PAGE *,
62
* PUBLIC: u_int32_t, int (*)(DB *, const DBT *, const DBT *), int *));
65
__bam_cmp(dbp, dbt, h, indx, func, cmpp)
70
int (*func)__P((DB *, const DBT *, const DBT *));
80
* < 0 if dbt is < page record
81
* = 0 if dbt is = page record
82
* > 0 if dbt is > page record
85
* We do not clear the pg_dbt DBT even though it's likely to contain
86
* random bits. That should be okay, because the app's comparison
87
* routine had better not be looking at fields other than data/size.
88
* We don't clear it because we go through this path a lot and it's
95
bk = GET_BKEYDATA(dbp, h, indx);
96
if (B_TYPE(bk->type) == B_OVERFLOW)
99
pg_dbt.data = bk->data;
100
pg_dbt.size = bk->len;
101
*cmpp = func(dbp, dbt, &pg_dbt);
107
* The following code guarantees that the left-most key on an
108
* internal page at any place in the tree sorts less than any
109
* user-specified key. The reason is that if we have reached
110
* this internal page, we know the user key must sort greater
111
* than the key we're storing for this page in any internal
112
* pages at levels above us in the tree. It then follows that
113
* any user-specified key cannot sort less than the first page
114
* which we reference, and so there's no reason to call the
115
* comparison routine. While this may save us a comparison
116
* routine call or two, the real reason for this is because
117
* we don't maintain a copy of the smallest key in the tree,
118
* so that we don't have to update all the levels of the tree
119
* should the application store a new smallest key. And, so,
120
* we may not have a key to compare, which makes doing the
121
* comparison difficult and error prone.
128
bi = GET_BINTERNAL(dbp, h, indx);
129
if (B_TYPE(bi->type) == B_OVERFLOW)
130
bo = (BOVERFLOW *)(bi->data);
132
pg_dbt.data = bi->data;
133
pg_dbt.size = bi->len;
134
*cmpp = func(dbp, dbt, &pg_dbt);
139
return (__db_pgfmt(dbp->dbenv, PGNO(h)));
145
return (__db_moff(dbp, dbt,
146
bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, cmpp));
151
* Default comparison routine.
153
* PUBLIC: int __bam_defcmp __P((DB *, const DBT *, const DBT *));
156
__bam_defcmp(dbp, a, b)
163
COMPQUIET(dbp, NULL);
172
* If a size_t doesn't fit into a long, or if the difference between
173
* any two characters doesn't fit into an int, this routine can lose.
174
* What we need is a signed integral type that's guaranteed to be at
175
* least as large as a size_t, and there is no such thing.
177
len = a->size > b->size ? b->size : a->size;
178
for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
180
return ((long)*p1 - (long)*p2);
181
return ((long)a->size - (long)b->size);
186
* Default prefix routine.
188
* PUBLIC: size_t __bam_defpfx __P((DB *, const DBT *, const DBT *));
191
__bam_defpfx(dbp, a, b)
198
COMPQUIET(dbp, NULL);
201
len = a->size > b->size ? b->size : a->size;
202
for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
207
* We know that a->size must be <= b->size, or they wouldn't be
210
return (a->size < b->size ? a->size + 1 : a->size);