btree.h
上传用户:tsgydb
上传日期:2007-04-14
资源大小:10674k
文件大小:11k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996, 1997, 1998, 1999, 2000
  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.  * $Id: btree.h,v 11.37 2001/01/17 17:09:52 bostic Exp $
  43.  */
  44. /* Forward structure declarations. */
  45. struct __btree; typedef struct __btree BTREE;
  46. struct __cursor; typedef struct __cursor BTREE_CURSOR;
  47. struct __epg; typedef struct __epg EPG;
  48. struct __recno; typedef struct __recno RECNO;
  49. #define DEFMINKEYPAGE  (2)
  50. /*
  51.  * A recno order of 0 indicates that we don't have an order, not that we've
  52.  * an order less than 1.
  53.  */
  54. #define INVALID_ORDER 0
  55. #define ISINTERNAL(p) (TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO)
  56. #define ISLEAF(p) (TYPE(p) == P_LBTREE ||
  57.     TYPE(p) == P_LRECNO || TYPE(p) == P_LDUP)
  58. /* Flags for __bam_cadjust_log(). */
  59. #define CAD_UPDATEROOT 0x01 /* Root page count was updated. */
  60. /* Flags for __bam_split_log(). */
  61. #define SPL_NRECS 0x01 /* Split tree has record count. */
  62. /* Flags for __bam_iitem(). */
  63. #define BI_DELETED 0x01 /* Key/data pair only placeholder. */
  64. /* Flags for __bam_stkrel(). */
  65. #define STK_CLRDBC 0x01 /* Clear dbc->page reference. */
  66. #define STK_NOLOCK 0x02 /* Don't retain locks. */
  67. /* Flags for __ram_ca(). These get logged, so make the values explicit. */
  68. typedef enum {
  69. CA_DELETE = 0, /* Delete the current record. */
  70. CA_IAFTER = 1, /* Insert before the current record. */
  71. CA_IBEFORE = 2, /* Insert after the current record. */
  72. CA_ICURRENT = 3 /* Overwrite the current record. */
  73. } ca_recno_arg;
  74. /*
  75.  * Flags for __bam_search() and __bam_rsearch().
  76.  *
  77.  * Note, internal page searches must find the largest record less than key in
  78.  * the tree so that descents work.  Leaf page searches must find the smallest
  79.  * record greater than key so that the returned index is the record's correct
  80.  * position for insertion.
  81.  *
  82.  * The flags parameter to the search routines describes three aspects of the
  83.  * search: the type of locking required (including if we're locking a pair of
  84.  * pages), the item to return in the presence of duplicates and whether or not
  85.  * to return deleted entries.  To simplify both the mnemonic representation
  86.  * and the code that checks for various cases, we construct a set of bitmasks.
  87.  */
  88. #define S_READ 0x00001 /* Read locks. */
  89. #define S_WRITE 0x00002 /* Write locks. */
  90. #define S_APPEND 0x00040 /* Append to the tree. */
  91. #define S_DELNO 0x00080 /* Don't return deleted items. */
  92. #define S_DUPFIRST 0x00100 /* Return first duplicate. */
  93. #define S_DUPLAST 0x00200 /* Return last duplicate. */
  94. #define S_EXACT 0x00400 /* Exact items only. */
  95. #define S_PARENT 0x00800 /* Lock page pair. */
  96. #define S_STACK 0x01000 /* Need a complete stack. */
  97. #define S_PAST_EOF 0x02000 /* If doing insert search (or keyfirst
  98.  * or keylast operations), or a split
  99.  * on behalf of an insert, it's okay to
  100.  * return an entry one past end-of-page.
  101.  */
  102. #define S_STK_ONLY 0x04000 /* Just return info in the stack */
  103. #define S_DELETE (S_WRITE | S_DUPFIRST | S_DELNO | S_EXACT | S_STACK)
  104. #define S_FIND (S_READ | S_DUPFIRST | S_DELNO)
  105. #define S_FIND_WR (S_WRITE | S_DUPFIRST | S_DELNO)
  106. #define S_INSERT (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
  107. #define S_KEYFIRST (S_WRITE | S_DUPFIRST | S_PAST_EOF | S_STACK)
  108. #define S_KEYLAST (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
  109. #define S_WRPAIR (S_WRITE | S_DUPLAST | S_PAST_EOF | S_PARENT)
  110. /*
  111.  * Various routines pass around page references.  A page reference is
  112.  * a pointer to the page, and the indx indicates an item on the page.
  113.  * Each page reference may include a lock.
  114.  */
  115. struct __epg {
  116. PAGE      *page; /* The page. */
  117. db_indx_t     indx; /* The index on the page. */
  118. db_indx_t     entries; /* The number of entries on page */
  119. DB_LOCK       lock; /* The page's lock. */
  120. db_lockmode_t lock_mode; /* The lock mode. */
  121. };
  122. /*
  123.  * We maintain a stack of the pages that we're locking in the tree.  Grow
  124.  * the stack as necessary.
  125.  *
  126.  * XXX
  127.  * Temporary fix for #3243 -- clear the page and lock from the stack entry.
  128.  * The correct fix is to never release a stack that doesn't hold items.
  129.  */
  130. #define BT_STK_CLR(c) do {
  131. (c)->csp = (c)->sp;
  132. (c)->csp->page = NULL;
  133. (c)->csp->lock.off = LOCK_INVALID;
  134. } while (0)
  135. #define BT_STK_ENTER(dbenv, c, pagep, page_indx, l, mode, ret) do {
  136. if ((ret =
  137.     (c)->csp == (c)->esp ? __bam_stkgrow(dbenv, c) : 0) == 0) {
  138. (c)->csp->page = pagep;
  139. (c)->csp->indx = page_indx;
  140. (c)->csp->entries = NUM_ENT(pagep);
  141. (c)->csp->lock = l;
  142. (c)->csp->lock_mode = mode;
  143. }
  144. } while (0)
  145. #define BT_STK_PUSH(dbenv, c, pagep, page_indx, lock, mode, ret) do {
  146. BT_STK_ENTER(dbenv, c, pagep, page_indx, lock, mode, ret);      
  147. ++(c)->csp;
  148. } while (0)
  149. #define BT_STK_NUM(dbenv, c, pagep, page_indx, ret) do {
  150. if ((ret =
  151.     (c)->csp == (c)->esp ? __bam_stkgrow(dbenv, c) : 0) == 0) {
  152. (c)->csp->page = NULL;
  153. (c)->csp->indx = page_indx;
  154. (c)->csp->entries = NUM_ENT(pagep);
  155. (c)->csp->lock.off = LOCK_INVALID;
  156. (c)->csp->lock_mode = DB_LOCK_NG;
  157. }
  158. } while (0)
  159. #define BT_STK_NUMPUSH(dbenv, c, pagep, page_indx,ret) do {
  160. BT_STK_NUM(dbenv, cp, pagep, page_indx, ret);
  161. ++(c)->csp;
  162. } while (0)
  163. #define BT_STK_POP(c)
  164. ((c)->csp == (c)->sp ? NULL : --(c)->csp)
  165. /* Btree/Recno cursor. */
  166. struct __cursor {
  167. /* struct __dbc_internal */
  168. __DBC_INTERNAL
  169. /* btree private part */
  170. EPG *sp; /* Stack pointer. */
  171. EPG *csp; /* Current stack entry. */
  172. EPG *esp; /* End stack pointer. */
  173. EPG  stack[5];
  174. db_indx_t  ovflsize; /* Maximum key/data on-page size. */
  175. db_recno_t  recno; /* Current record number. */
  176. u_int32_t  order; /* Relative order among deleted curs. */
  177. /*
  178.  * Btree:
  179.  * We set a flag in the cursor structure if the underlying object has
  180.  * been deleted.  It's not strictly necessary, we could get the same
  181.  * information by looking at the page itself, but this method doesn't
  182.  * require us to retrieve the page on cursor delete.
  183.  *
  184.  * Recno:
  185.  * When renumbering recno databases during deletes, cursors referencing
  186.  * "deleted" records end up positioned between two records, and so must
  187.  * be specially adjusted on the next operation.
  188.  */
  189. #define C_DELETED 0x0001 /* Record was deleted. */
  190. /*
  191.  * There are three tree types that require maintaining record numbers.
  192.  * Recno AM trees, Btree AM trees for which the DB_RECNUM flag was set,
  193.  * and Btree off-page duplicate trees.
  194.  */
  195. #define C_RECNUM 0x0002 /* Tree requires record counts. */
  196. /*
  197.  * Recno trees have immutable record numbers by default, but optionally
  198.  * support mutable record numbers.  Off-page duplicate Recno trees have
  199.  * mutable record numbers.  All Btrees with record numbers (including
  200.  * off-page duplicate trees) are mutable by design, no flag is needed.
  201.  */
  202. #define C_RENUMBER 0x0004 /* Tree records are mutable. */
  203. u_int32_t  flags;
  204. };
  205. /*
  206.  * Threshhold value, as a function of bt_minkey, of the number of
  207.  * bytes a key/data pair can use before being placed on an overflow
  208.  * page.  Assume every item requires the maximum alignment for
  209.  * padding, out of sheer paranoia.
  210.  */
  211. #define B_MINKEY_TO_OVFLSIZE(minkey, pgsize)
  212. ((u_int16_t)(((pgsize) - P_OVERHEAD) / ((minkey) * P_INDX) -
  213.     (BKEYDATA_PSIZE(0) + ALIGN(1, sizeof(int32_t)))))
  214. /*
  215.  * The maximum space that a single item can ever take up on one page.
  216.  * Used by __bam_split to determine whether a split is still necessary.
  217.  */
  218. #define B_MAX(a,b) (((a) > (b)) ? (a) : (b))
  219. #define B_MAXSIZEONPAGE(ovflsize)
  220. (B_MAX(BOVERFLOW_PSIZE, BKEYDATA_PSIZE(ovflsize)))
  221. /*
  222.  * The in-memory, per-tree btree/recno data structure.
  223.  */
  224. struct __btree { /* Btree access method. */
  225. /*
  226.  * !!!
  227.  * These fields are write-once (when the structure is created) and
  228.  * so are ignored as far as multi-threading is concerned.
  229.  */
  230. db_pgno_t bt_meta; /* Database meta-data page. */
  231. db_pgno_t bt_root; /* Database root page. */
  232. u_int32_t bt_maxkey; /* Maximum keys per page. */
  233. u_int32_t bt_minkey; /* Minimum keys per page. */
  234. /* Btree comparison function. */
  235. int (*bt_compare) __P((DB *, const DBT *, const DBT *));
  236. /* Btree prefix function. */
  237. size_t (*bt_prefix) __P((DB *, const DBT *, const DBT *));
  238. /* Recno access method. */
  239. int   re_pad; /* Fixed-length padding byte. */
  240. int   re_delim; /* Variable-length delimiting byte. */
  241. u_int32_t re_len; /* Length for fixed-length records. */
  242. char  *re_source; /* Source file name. */
  243. /*
  244.  * !!!
  245.  * The bt_lpgno field is NOT protected by any mutex, and for this
  246.  * reason must be advisory only, so, while it is read/written by
  247.  * multiple threads, DB is completely indifferent to the quality
  248.  * of its information.
  249.  */
  250. db_pgno_t bt_lpgno; /* Last insert location. */
  251. /*
  252.  * !!!
  253.  * The re_modified field is NOT protected by any mutex, and for this
  254.  * reason cannot be anything more complicated than a zero/non-zero
  255.  * value.  The actual writing of the backing source file cannot be
  256.  * threaded, so clearing the flag isn't a problem.
  257.  */
  258. int   re_modified; /* If the tree was modified. */
  259. /*
  260.  * !!!
  261.  * These fields are ignored as far as multi-threading is concerned.
  262.  * There are no transaction semantics associated with backing files,
  263.  * nor is there any thread protection.
  264.  */
  265. FILE *re_fp; /* Source file handle. */
  266. int  re_eof; /* Backing source file EOF reached. */
  267. db_recno_t  re_last; /* Last record number read. */
  268. };
  269. /*
  270.  * Modes for the __bam_curadj recovery records (btree_curadj).
  271.  * These appear in log records, so we wire the values and
  272.  * do not leave it up to the compiler.
  273.  */
  274. typedef enum {
  275. DB_CA_DI = 1,
  276. DB_CA_DUP = 2,
  277. DB_CA_RSPLIT = 3,
  278. DB_CA_SPLIT = 4
  279. } db_ca_mode;
  280. #include "btree_auto.h"
  281. #include "btree_ext.h"
  282. #include "db_am.h"