bt_compare.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:6k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996-2002
  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. 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.
  29.  *
  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
  40.  * SUCH DAMAGE.
  41.  */
  42. #include "db_config.h"
  43. #ifndef lint
  44. static const char revid[] = "$Id: bt_compare.c,v 11.17 2002/03/27 04:30:42 bostic Exp $";
  45. #endif /* not lint */
  46. #ifndef NO_SYSTEM_INCLUDES
  47. #include <sys/types.h>
  48. #endif
  49. #include "db_int.h"
  50. #include "dbinc/db_page.h"
  51. #include "dbinc/btree.h"
  52. /*
  53.  * __bam_cmp --
  54.  * Compare a key to a given record.
  55.  *
  56.  * PUBLIC: int __bam_cmp __P((DB *, const DBT *, PAGE *,
  57.  * PUBLIC:    u_int32_t, int (*)(DB *, const DBT *, const DBT *), int *));
  58.  */
  59. int
  60. __bam_cmp(dbp, dbt, h, indx, func, cmpp)
  61. DB *dbp;
  62. const DBT *dbt;
  63. PAGE *h;
  64. u_int32_t indx;
  65. int (*func)__P((DB *, const DBT *, const DBT *));
  66. int *cmpp;
  67. {
  68. BINTERNAL *bi;
  69. BKEYDATA *bk;
  70. BOVERFLOW *bo;
  71. DBT pg_dbt;
  72. /*
  73.  * Returns:
  74.  * < 0 if dbt is < page record
  75.  * = 0 if dbt is = page record
  76.  * > 0 if dbt is > page record
  77.  *
  78.  * !!!
  79.  * We do not clear the pg_dbt DBT even though it's likely to contain
  80.  * random bits.  That should be okay, because the app's comparison
  81.  * routine had better not be looking at fields other than data/size.
  82.  * We don't clear it because we go through this path a lot and it's
  83.  * expensive.
  84.  */
  85. switch (TYPE(h)) {
  86. case P_LBTREE:
  87. case P_LDUP:
  88. case P_LRECNO:
  89. bk = GET_BKEYDATA(dbp, h, indx);
  90. if (B_TYPE(bk->type) == B_OVERFLOW)
  91. bo = (BOVERFLOW *)bk;
  92. else {
  93. pg_dbt.data = bk->data;
  94. pg_dbt.size = bk->len;
  95. *cmpp = func(dbp, dbt, &pg_dbt);
  96. return (0);
  97. }
  98. break;
  99. case P_IBTREE:
  100. /*
  101.  * The following code guarantees that the left-most key on an
  102.  * internal page at any place in the tree sorts less than any
  103.  * user-specified key.  The reason is that if we have reached
  104.  * this internal page, we know the user key must sort greater
  105.  * than the key we're storing for this page in any internal
  106.  * pages at levels above us in the tree.  It then follows that
  107.  * any user-specified key cannot sort less than the first page
  108.  * which we reference, and so there's no reason to call the
  109.  * comparison routine.  While this may save us a comparison
  110.  * routine call or two, the real reason for this is because
  111.  * we don't maintain a copy of the smallest key in the tree,
  112.  * so that we don't have to update all the levels of the tree
  113.  * should the application store a new smallest key.  And, so,
  114.  * we may not have a key to compare, which makes doing the
  115.  * comparison difficult and error prone.
  116.  */
  117. if (indx == 0) {
  118. *cmpp = 1;
  119. return (0);
  120. }
  121. bi = GET_BINTERNAL(dbp, h, indx);
  122. if (B_TYPE(bi->type) == B_OVERFLOW)
  123. bo = (BOVERFLOW *)(bi->data);
  124. else {
  125. pg_dbt.data = bi->data;
  126. pg_dbt.size = bi->len;
  127. *cmpp = func(dbp, dbt, &pg_dbt);
  128. return (0);
  129. }
  130. break;
  131. default:
  132. return (__db_pgfmt(dbp->dbenv, PGNO(h)));
  133. }
  134. /*
  135.  * Overflow.
  136.  */
  137. return (__db_moff(dbp, dbt,
  138.     bo->pgno, bo->tlen, func == __bam_defcmp ? NULL : func, cmpp));
  139. }
  140. /*
  141.  * __bam_defcmp --
  142.  * Default comparison routine.
  143.  *
  144.  * PUBLIC: int __bam_defcmp __P((DB *, const DBT *, const DBT *));
  145.  */
  146. int
  147. __bam_defcmp(dbp, a, b)
  148. DB *dbp;
  149. const DBT *a, *b;
  150. {
  151. size_t len;
  152. u_int8_t *p1, *p2;
  153. COMPQUIET(dbp, NULL);
  154. /*
  155.  * Returns:
  156.  * < 0 if a is < b
  157.  * = 0 if a is = b
  158.  * > 0 if a is > b
  159.  *
  160.  * XXX
  161.  * If a size_t doesn't fit into a long, or if the difference between
  162.  * any two characters doesn't fit into an int, this routine can lose.
  163.  * What we need is a signed integral type that's guaranteed to be at
  164.  * least as large as a size_t, and there is no such thing.
  165.  */
  166. len = a->size > b->size ? b->size : a->size;
  167. for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
  168. if (*p1 != *p2)
  169. return ((long)*p1 - (long)*p2);
  170. return ((long)a->size - (long)b->size);
  171. }
  172. /*
  173.  * __bam_defpfx --
  174.  * Default prefix routine.
  175.  *
  176.  * PUBLIC: size_t __bam_defpfx __P((DB *, const DBT *, const DBT *));
  177.  */
  178. size_t
  179. __bam_defpfx(dbp, a, b)
  180. DB *dbp;
  181. const DBT *a, *b;
  182. {
  183. size_t cnt, len;
  184. u_int8_t *p1, *p2;
  185. COMPQUIET(dbp, NULL);
  186. cnt = 1;
  187. len = a->size > b->size ? b->size : a->size;
  188. for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
  189. if (*p1 != *p2)
  190. return (cnt);
  191. /*
  192.  * We know that a->size must be <= b->size, or they wouldn't be
  193.  * in this order.
  194.  */
  195. return (a->size < b->size ? a->size + 1 : a->size);
  196. }