00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 */ 00007 /* 00008 * Copyright (c) 1990, 1993, 1994, 1995, 1996 00009 * Keith Bostic. All rights reserved. 00010 */ 00011 /* 00012 * Copyright (c) 1990, 1993, 1994, 1995 00013 * The Regents of the University of California. All rights reserved. 00014 * 00015 * This code is derived from software contributed to Berkeley by 00016 * Mike Olson. 00017 * 00018 * Redistribution and use in source and binary forms, with or without 00019 * modification, are permitted provided that the following conditions 00020 * are met: 00021 * 1. Redistributions of source code must retain the above copyright 00022 * notice, this list of conditions and the following disclaimer. 00023 * 2. Redistributions in binary form must reproduce the above copyright 00024 * notice, this list of conditions and the following disclaimer in the 00025 * documentation and/or other materials provided with the distribution. 00026 * 3. Neither the name of the University nor the names of its contributors 00027 * may be used to endorse or promote products derived from this software 00028 * without specific prior written permission. 00029 * 00030 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00031 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00032 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00033 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00034 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00035 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00036 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00037 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00038 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00039 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00040 * SUCH DAMAGE. 00041 */ 00042 00043 #include "config.h" 00044 00045 #ifndef lint 00046 static const char revid[] = "$Id: bt__compare_8c-source.html,v 1.1 2008年06月08日 10:13:29 sebdiaz Exp $"; 00047 #endif /* not lint */ 00048 00049 #ifndef NO_SYSTEM_INCLUDES 00050 #include <sys/types.h> 00051 #endif 00052 00053 #include "db_int.h" 00054 #include "db_page.h" 00055 #include "btree.h" 00056 00057 #ifdef DEBUG 00058 #include "WordMonitor.h" 00059 #endif /* DEBUG */ 00060 00061 /* 00062 * CDB___bam_cmp -- 00063 * Compare a key to a given record. 00064 * 00065 * PUBLIC: int CDB___bam_cmp __P((DB *, const DBT *, 00066 * PUBLIC: PAGE *, u_int32_t, int (*)(const DBT *, const DBT *), int *)); 00067 */ 00068 int 00069 CDB___bam_cmp(dbp, dbt, h, indx, func, cmpp) 00070 DB *dbp; 00071 const DBT *dbt; 00072 PAGE *h; 00073 u_int32_t indx; 00074 int (*func)__P((const DBT *, const DBT *)); 00075 int *cmpp; 00076 { 00077 BINTERNAL *bi; 00078 BKEYDATA *bk; 00079 BOVERFLOW *bo; 00080 DBT pg_dbt; 00081 00082 #ifdef DEBUG 00083 word_monitor_add(DB_MONITOR(dbp->dbenv), WORD_MONITOR_CMP, 1); 00084 #endif /* DEBUG */ 00085 pg_dbt.app_private = dbp->dbenv->app_private; 00086 00087 /* 00088 * Returns: 00089 * < 0 if dbt is < page record 00090 * = 0 if dbt is = page record 00091 * > 0 if dbt is > page record 00092 * 00093 * !!! 00094 * We do not clear the pg_dbt DBT even though it's likely to contain 00095 * random bits. That should be okay, because the app's comparison 00096 * routine had better not be looking at fields other than data/size. 00097 * We don't clear it because we go through this path a lot and it's 00098 * expensive. 00099 */ 00100 switch (TYPE(h)) { 00101 case P_LBTREE: 00102 case P_LDUP: 00103 case P_LRECNO: 00104 bk = GET_BKEYDATA(h, indx); 00105 if (B_TYPE(bk->type) == B_OVERFLOW) 00106 bo = (BOVERFLOW *)bk; 00107 else { 00108 pg_dbt.data = bk->data; 00109 pg_dbt.size = bk->len; 00110 *cmpp = func(dbt, &pg_dbt); 00111 return (0); 00112 } 00113 break; 00114 case P_IBTREE: 00115 /* 00116 * The following code guarantees that the left-most key on an 00117 * internal page at any place in the tree sorts less than any 00118 * user-specified key. The reason is that if we have reached 00119 * this internal page, we know the user key must sort greater 00120 * than the key we're storing for this page in any internal 00121 * pages at levels above us in the tree. It then follows that 00122 * any user-specified key cannot sort less than the first page 00123 * which we reference, and so there's no reason to call the 00124 * comparison routine. While this may save us a comparison 00125 * routine call or two, the real reason for this is because 00126 * we don't maintain a copy of the smallest key in the tree, 00127 * so that we don't have to update all the levels of the tree 00128 * should the application store a new smallest key. And, so, 00129 * we may not have a key to compare, which makes doing the 00130 * comparison difficult and error prone. 00131 */ 00132 if (indx == 0) { 00133 *cmpp = 1; 00134 return (0); 00135 } 00136 00137 bi = GET_BINTERNAL(h, indx); 00138 if (B_TYPE(bi->type) == B_OVERFLOW) 00139 bo = (BOVERFLOW *)(bi->data); 00140 else { 00141 pg_dbt.data = bi->data; 00142 pg_dbt.size = bi->len; 00143 *cmpp = func(dbt, &pg_dbt); 00144 return (0); 00145 } 00146 break; 00147 default: 00148 return (CDB___db_pgfmt(dbp, PGNO(h))); 00149 } 00150 00151 /* 00152 * Overflow. 00153 */ 00154 return (CDB___db_moff(dbp, dbt, 00155 bo->pgno, bo->tlen, func == CDB___bam_defcmp ? NULL : func, cmpp)); 00156 } 00157 00158 /* 00159 * CDB___bam_defcmp -- 00160 * Default comparison routine. 00161 * 00162 * PUBLIC: int CDB___bam_defcmp __P((const DBT *, const DBT *)); 00163 */ 00164 int 00165 CDB___bam_defcmp(a, b) 00166 const DBT *a, *b; 00167 { 00168 size_t len; 00169 u_int8_t *p1, *p2; 00170 00171 /* 00172 * Returns: 00173 * < 0 if a is < b 00174 * = 0 if a is = b 00175 * > 0 if a is > b 00176 * 00177 * XXX 00178 * If a size_t doesn't fit into a long, or if the difference between 00179 * any two characters doesn't fit into an int, this routine can lose. 00180 * What we need is a signed integral type that's guaranteed to be at 00181 * least as large as a size_t, and there is no such thing. 00182 */ 00183 len = a->size > b->size ? b->size : a->size; 00184 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 00185 if (*p1 != *p2) 00186 return ((long)*p1 - (long)*p2); 00187 return ((long)a->size - (long)b->size); 00188 } 00189 00190 /* 00191 * CDB___bam_defpfx -- 00192 * Default prefix routine. 00193 * 00194 * PUBLIC: size_t CDB___bam_defpfx __P((const DBT *, const DBT *)); 00195 */ 00196 size_t 00197 CDB___bam_defpfx(a, b) 00198 const DBT *a, *b; 00199 { 00200 size_t cnt, len; 00201 u_int8_t *p1, *p2; 00202 00203 cnt = 1; 00204 len = a->size > b->size ? b->size : a->size; 00205 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 00206 if (*p1 != *p2) 00207 return (cnt); 00208 00209 /* 00210 * We know that a->size must be <= b->size, or they wouldn't be 00211 * in this order. 00212 */ 00213 return (a->size < b->size ? a->size + 1 : a->size); 00214 }