1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 1996,2008 Oracle. All rights reserved. 5 */ 6/* 7 * Copyright (c) 1990, 1993, 1994, 1995, 1996 8 * Keith Bostic. All rights reserved. 9 */ 10/* 11 * Copyright (c) 1990, 1993, 1994, 1995 12 * The Regents of the University of California. All rights reserved. 13 * 14 * This code is derived from software contributed to Berkeley by 15 * Mike Olson. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 3. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 * 41 * $Id: bt_compare.c,v 12.12 2008/01/08 20:57:59 bostic Exp $ 42 */ 43 44#include "db_config.h" 45 46#include "db_int.h" 47#include "dbinc/db_page.h" 48#include "dbinc/btree.h" 49 50/* 51 * __bam_cmp -- 52 * Compare a key to a given record. 53 * 54 * PUBLIC: int __bam_cmp __P((DB *, DB_THREAD_INFO *, 55 * PUBLIC: DB_TXN *, const DBT *, PAGE *, u_int32_t, 56 * PUBLIC: int (*)(DB *, const DBT *, const DBT *), int *)); 57 */ 58int 59__bam_cmp(dbp, ip, txn, dbt, h, indx, func, cmpp) 60 DB *dbp; 61 DB_THREAD_INFO *ip; 62 DB_TXN *txn; 63 const DBT *dbt; 64 PAGE *h; 65 u_int32_t indx; 66 int (*func)__P((DB *, const DBT *, const DBT *)); 67 int *cmpp; 68{ 69 BINTERNAL *bi; 70 BKEYDATA *bk; 71 BOVERFLOW *bo; 72 DBT pg_dbt; 73 74 /* 75 * Returns: 76 * < 0 if dbt is < page record 77 * = 0 if dbt is = page record 78 * > 0 if dbt is > page record 79 * 80 * !!! 81 * We do not clear the pg_dbt DBT even though it's likely to contain 82 * random bits. That should be okay, because the app's comparison 83 * routine had better not be looking at fields other than data, size 84 * and app_data. We don't clear it because we go through this path a 85 * lot and it's expensive. 86 */ 87 switch (TYPE(h)) { 88 case P_LBTREE: 89 case P_LDUP: 90 case P_LRECNO: 91 bk = GET_BKEYDATA(dbp, h, indx); 92 if (B_TYPE(bk->type) == B_OVERFLOW) 93 bo = (BOVERFLOW *)bk; 94 else { 95 pg_dbt.app_data = NULL; 96 pg_dbt.data = bk->data; 97 pg_dbt.size = bk->len; 98 *cmpp = func(dbp, dbt, &pg_dbt); 99 return (0); 100 } 101 break; 102 case P_IBTREE: 103 /* 104 * The following code guarantees that the left-most key on an 105 * internal page at any place in the tree sorts less than any 106 * user-specified key. The reason is that if we have reached 107 * this internal page, we know the user key must sort greater 108 * than the key we're storing for this page in any internal 109 * pages at levels above us in the tree. It then follows that 110 * any user-specified key cannot sort less than the first page 111 * which we reference, and so there's no reason to call the 112 * comparison routine. While this may save us a comparison 113 * routine call or two, the real reason for this is because 114 * we don't maintain a copy of the smallest key in the tree, 115 * so that we don't have to update all the levels of the tree 116 * should the application store a new smallest key. And, so, 117 * we may not have a key to compare, which makes doing the 118 * comparison difficult and error prone. 119 */ 120 if (indx == 0) { 121 *cmpp = 1; 122 return (0); 123 } 124 125 bi = GET_BINTERNAL(dbp, h, indx); 126 if (B_TYPE(bi->type) == B_OVERFLOW) 127 bo = (BOVERFLOW *)(bi->data); 128 else { 129 pg_dbt.app_data = NULL; 130 pg_dbt.data = bi->data; 131 pg_dbt.size = bi->len; 132 *cmpp = func(dbp, dbt, &pg_dbt); 133 return (0); 134 } 135 break; 136 default: 137 return (__db_pgfmt(dbp->env, PGNO(h))); 138 } 139 140 /* 141 * Overflow. 142 */ 143 return (__db_moff(dbp, ip, txn, dbt, 144 bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, cmpp)); 145} 146 147/* 148 * __bam_defcmp -- 149 * Default comparison routine. 150 * 151 * PUBLIC: int __bam_defcmp __P((DB *, const DBT *, const DBT *)); 152 */ 153int 154__bam_defcmp(dbp, a, b) 155 DB *dbp; 156 const DBT *a, *b; 157{ 158 size_t len; 159 u_int8_t *p1, *p2; 160 161 COMPQUIET(dbp, NULL); 162 163 /* 164 * Returns: 165 * < 0 if a is < b 166 * = 0 if a is = b 167 * > 0 if a is > b 168 * 169 * XXX 170 * If a size_t doesn't fit into a long, or if the difference between 171 * any two characters doesn't fit into an int, this routine can lose. 172 * What we need is a signed integral type that's guaranteed to be at 173 * least as large as a size_t, and there is no such thing. 174 */ 175 len = a->size > b->size ? b->size : a->size; 176 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 177 if (*p1 != *p2) 178 return ((long)*p1 - (long)*p2); 179 return ((long)a->size - (long)b->size); 180} 181 182/* 183 * __bam_defpfx -- 184 * Default prefix routine. 185 * 186 * PUBLIC: size_t __bam_defpfx __P((DB *, const DBT *, const DBT *)); 187 */ 188size_t 189__bam_defpfx(dbp, a, b) 190 DB *dbp; 191 const DBT *a, *b; 192{ 193 size_t cnt, len; 194 u_int8_t *p1, *p2; 195 196 COMPQUIET(dbp, NULL); 197 198 cnt = 1; 199 len = a->size > b->size ? b->size : a->size; 200 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 201 if (*p1 != *p2) 202 return (cnt); 203 204 /* 205 * They match up to the smaller of the two sizes. 206 * Collate the longer after the shorter. 207 */ 208 if (a->size < b->size) 209 return (a->size + 1); 210 if (b->size < a->size) 211 return (b->size + 1); 212 return (b->size); 213} 214