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 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 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 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