1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 1996, 1997, 1998, 1999
* Sleepycat Software. All rights reserved.
*/
/*
* Copyright (c) 1990, 1993, 1994, 1995, 1996
* Keith Bostic. All rights reserved.
*/
/*
* Copyright (c) 1990, 1993, 1994, 1995
* The Regents of the University of California. All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Mike Olson.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* @(#)btree.h 11.8 (Sleepycat) 9/20/99
*/
/* Forward structure declarations. */
struct __btree; typedef struct __btree BTREE;
struct __cursor; typedef struct __cursor BTREE_CURSOR;
struct __epg; typedef struct __epg EPG;
struct __recno; typedef struct __recno RECNO;
#define DEFMINKEYPAGE (2)
#define ISINTERNAL(p) (TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO)
#define ISLEAF(p) (TYPE(p) == P_LBTREE || TYPE(p) == P_LRECNO)
/*
* Flags to CDB___bam_search() and CDB___bam_rsearch().
*
* Note, internal page searches must find the largest record less than key in
* the tree so that descents work. Leaf page searches must find the smallest
* record greater than key so that the returned index is the record's correct
* position for insertion.
*
* The flags parameter to the search routines describes three aspects of the
* search: the type of locking required (including if we're locking a pair of
* pages), the item to return in the presence of duplicates and whether or not
* to return deleted entries. To simplify both the mnemonic representation
* and the code that checks for various cases, we construct a set of bitmasks.
*/
#define S_READ 0x00001 /* Read locks. */
#define S_WRITE 0x00002 /* Write locks. */
#define S_APPEND 0x00040 /* Append to the tree. */
#define S_DELNO 0x00080 /* Don't return deleted items. */
#define S_DUPFIRST 0x00100 /* Return first duplicate. */
#define S_DUPLAST 0x00200 /* Return last duplicate. */
#define S_EXACT 0x00400 /* Exact items only. */
#define S_PARENT 0x00800 /* Lock page pair. */
#define S_STACK 0x01000 /* Need a complete stack. */
#define S_PAST_EOF 0x02000 /* If doing insert search (or keyfirst
* or keylast operations), or a split
* on behalf of an insert, it's okay to
* return an entry one past end-of-page.
*/
#define S_DELETE (S_WRITE | S_DUPFIRST | S_DELNO | S_EXACT | S_STACK)
#define S_FIND (S_READ | S_DUPFIRST | S_DELNO)
#define S_FIND_WR (S_WRITE | S_DUPFIRST | S_DELNO)
#define S_INSERT (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
#define S_KEYFIRST (S_WRITE | S_DUPFIRST | S_PAST_EOF | S_STACK)
#define S_KEYLAST (S_WRITE | S_DUPLAST | S_PAST_EOF | S_STACK)
#define S_WRPAIR (S_WRITE | S_DUPLAST | S_PAST_EOF | S_PARENT)
/*
* Flags to CDB___bam_iitem().
*/
#define BI_DELETED 0x01 /* Key/data pair only placeholder. */
/*
* Various routines pass around page references. A page reference is
* a pointer to the page, and the indx indicates an item on the page.
* Each page reference may include a lock.
*/
struct __epg {
PAGE *page; /* The page. */
db_indx_t indx; /* The index on the page. */
DB_LOCK lock; /* The page's lock. */
db_lockmode_t lock_mode; /* The lock mode. */
};
/*
* We maintain a stack of the pages that we're locking in the tree. Btree's
* (currently) only save two levels of the tree at a time, so the default
* stack is always large enough. Recno trees have to lock the entire tree to
* do inserts/deletes, however. Grow the stack as necessary.
*/
#define BT_STK_CLR(c) \
((c)->csp = (c)->sp)
#define BT_STK_ENTER(c, pagep, page_indx, lock, mode, ret) do { \
if ((ret = \
(c)->csp == (c)->esp ? CDB___bam_stkgrow(c) : 0) == 0) { \
(c)->csp->page = pagep; \
(c)->csp->indx = page_indx; \
(c)->csp->lock = lock; \
(c)->csp->lock_mode = mode; \
} \
} while (0)
#define BT_STK_PUSH(c, pagep, page_indx, lock, mode, ret) do { \
BT_STK_ENTER(c, pagep, page_indx, lock, mode, ret); \
++(c)->csp; \
} while (0)
#define BT_STK_POP(c) \
((c)->csp == (c)->stack ? NULL : --(c)->csp)
/*
* Arguments passed to __bam_ca_replace().
*/
typedef enum {
REPLACE_SETUP,
REPLACE_SUCCESS,
REPLACE_FAILED
} ca_replace_arg;
/* Arguments passed to CDB___ram_ca(). */
typedef enum {
CA_DELETE,
CA_IAFTER,
CA_IBEFORE
} ca_recno_arg;
/* Btree/Recno cursor. */
struct __cursor {
/* Per-thread information: shared by btree/recno. */
EPG *sp; /* Stack pointer. */
EPG *csp; /* Current stack entry. */
EPG *esp; /* End stack pointer. */
EPG stack[5];
/* Per-thread information: btree private. */
PAGE *page; /* Cursor page. */
db_pgno_t pgno; /* Page. */
db_indx_t indx; /* Page item ref'd by the cursor. */
db_pgno_t dpgno; /* Duplicate page. */
db_indx_t dindx; /* Page item ref'd by the cursor. */
DB_LOCK lock; /* Cursor lock. */
db_lockmode_t lock_mode; /* Lock mode. */
/* Per-thread information: recno private. */
db_recno_t recno; /* Current record number. */
/*
* Btree:
* We set a flag in the cursor structure if the underlying object has
* been deleted. It's not strictly necessary, we could get the same
* information by looking at the page itself.
*
* Recno:
* When renumbering recno databases during deletes, cursors referencing
* "deleted" records end up positioned between two records, and so must
* be specially adjusted on the next operation.
*/
#define C_DELETED 0x0001 /* Record was deleted. */
u_int32_t flags;
};
/*
* The in-memory, per-tree btree/recno data structure.
*/
struct __btree {
/* Btree access method. */
db_pgno_t bt_lpgno; /* Last insert location. */
db_indx_t bt_ovflsize; /* Maximum key/data on-page size. */
db_pgno_t bt_meta; /* Database meta-data page. */
db_pgno_t bt_root; /* Database root page. */
u_int32_t bt_maxkey; /* Maximum keys per page. */
u_int32_t bt_minkey; /* Minimum keys per page. */
/* Btree comparison function. */
int (*bt_compare) __P((const DBT *, const DBT *));
/* Prefix function. */
size_t (*bt_prefix) __P((const DBT *, const DBT *));
/* Recno access method. */
int re_pad; /* Fixed-length padding byte. */
int re_delim; /* Variable-length delimiting byte. */
u_int32_t re_len; /* Length for fixed-length records. */
char *re_source; /* Source file name. */
/*
* !!!
* These fields are ignored as far as multi-threading is concerned.
* There are no transaction semantics associated with backing files,
* nor is there any thread protection.
*/
DB_FH re_fh; /* Source file handle. */
db_recno_t re_last; /* Last record number read. */
void *re_cmap; /* Current point in mapped space. */
void *re_smap; /* Start of mapped space. */
void *re_emap; /* End of mapped space. */
size_t re_msize; /* Size of mapped region. */
/* Recno input function. */
int (*re_irec) __P((DBC *, db_recno_t));
#define RECNO_EOF 0x01 /* EOF on backing source file. */
#define RECNO_MODIFIED 0x02 /* Tree was modified. */
u_int32_t flags;
};
#include "btree_auto.h"
#include "btree_ext.h"
#include "db_am.h"
|
