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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
|
/*-
* See the file LICENSE for redistribution information.
*
* Copyright (c) 1996, 1997
* 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. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. 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 10.16 (Sleepycat) 8/24/97
*/
/* Forward structure declarations. */
struct __btree; typedef struct __btree BTREE;
struct __cursor; typedef struct __cursor CURSOR;
struct __epg; typedef struct __epg EPG;
struct __rcursor; typedef struct __rcursor RCURSOR;
struct __recno; typedef struct __recno RECNO;
#undef DEFMINKEYPAGE /* Minimum keys per page */
#define DEFMINKEYPAGE (2)
#undef ISINTERNAL /* If an internal page. */
#define ISINTERNAL(p) (TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO)
#undef ISLEAF /* If a leaf page. */
#define ISLEAF(p) (TYPE(p) == P_LBTREE || TYPE(p) == P_LRECNO)
/* Allocate and discard thread structures. */
#define GETHANDLE(dbp, set_txn, dbpp, ret) { \
if (F_ISSET(dbp, DB_AM_THREAD)) { \
if ((ret = __db_gethandle(dbp, __bam_bdup, dbpp)) != 0) \
return (ret); \
} else \
*dbpp = dbp; \
*dbpp->txn = set_txn; \
}
#define PUTHANDLE(dbp) { \
dbp->txn = NULL; \
if (F_ISSET(dbp, DB_AM_THREAD)) \
__db_puthandle(dbp); \
}
/*
* If doing transactions we have to hold the locks associated with a data item
* from a page for the entire transaction. However, we don't have to hold the
* locks associated with walking the tree. Distinguish between the two so that
* we don't tie up the internal pages of the tree longer than necessary.
*/
#define __BT_LPUT(dbp, lock) \
(F_ISSET((dbp), DB_AM_LOCKING) ? \
lock_put((dbp)->dbenv->lk_info, lock) : 0)
#define __BT_TLPUT(dbp, lock) \
(F_ISSET((dbp), DB_AM_LOCKING) && (dbp)->txn == NULL ? \
lock_put((dbp)->dbenv->lk_info, lock) : 0)
/*
* Flags to __bt_search() and __rec_search().
*
* 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 0x0001 /* Read locks. */
#define S_WRITE 0x0002 /* Write locks. */
#define S_APPEND 0x0040 /* Append to the tree. */
#define S_DELNO 0x0080 /* Don't return deleted items. */
#define S_DUPFIRST 0x0100 /* Return first duplicate. */
#define S_DUPLAST 0x0200 /* Return last duplicate. */
#define S_EXACT 0x0400 /* Exact items only. */
#define S_PARENT 0x0800 /* Lock page pair. */
#define S_DELETE (S_WRITE | S_DUPFIRST | S_DELNO | S_EXACT)
#define S_FIND (S_READ | S_DUPFIRST | S_DELNO)
#define S_INSERT (S_WRITE | S_DUPLAST)
#define S_KEYFIRST (S_WRITE | S_DUPFIRST)
#define S_KEYLAST (S_WRITE | S_DUPLAST)
#define S_WRPAIR (S_WRITE | S_DUPLAST | S_PARENT)
/*
* Flags to __bam_iitem().
*/
#define BI_NEWKEY 0x01 /* New key. */
#define BI_DELETED 0x02 /* Key/data pair only placeholder. */
/*
* Various routines pass around page references. A page reference can be a
* pointer to the page or a page number; for either, an indx can designate
* an item on the page.
*/
struct __epg {
PAGE *page; /* The page. */
db_indx_t indx; /* The index on the page. */
DB_LOCK lock; /* The page's lock. */
};
/*
* Btree cursor.
*
* Arguments passed to __bam_ca_replace().
*/
typedef enum {
REPLACE_SETUP,
REPLACE_SUCCESS,
REPLACE_FAILED
} ca_replace_arg;
struct __cursor {
DBC *dbc; /* Enclosing DBC. */
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 read lock. */
db_lockmode_t mode; /* Lock mode. */
/*
* If a cursor record is deleted, the key/data pair has to remain on
* the page so that subsequent inserts/deletes don't interrupt the
* cursor progression through the file. This results in interesting
* cases when "standard" operations, e.g., dbp->put() are done in the
* context of "deleted" cursors.
*
* C_DELETED -- The item referenced by the cursor has been "deleted"
* but not physically removed from the page.
* C_REPLACE -- The "deleted" item referenced by a cursor has been
* replaced by a dbp->put(), so the cursor is no longer
* responsible for physical removal from the page.
* C_REPLACE_SETUP --
* We are about to overwrite a "deleted" item, flag any
* cursors referencing it for transition to C_REPLACE
* state.
*/
#define C_DELETED 0x0001
#define C_REPLACE 0x0002
#define C_REPLACE_SETUP 0x0004
u_int32_t flags;
};
/*
* Recno cursor.
*
* Arguments passed to __ram_ca().
*/
typedef enum {
CA_DELETE,
CA_IAFTER,
CA_IBEFORE
} ca_recno_arg;
struct __rcursor {
DBC *dbc; /* Enclosing DBC. */
db_recno_t recno; /* Current record number. */
/*
* Cursors referencing "deleted" records are positioned between
* two records, and so must be specially adjusted until they are
* moved.
*/
#define CR_DELETED 0x0001 /* Record deleted. */
u_int32_t flags;
};
/*
* 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.
*/
#undef BT_STK_CLR
#define BT_STK_CLR(t) \
((t)->bt_csp = (t)->bt_sp)
#undef BT_STK_ENTER
#define BT_STK_ENTER(t, pagep, page_indx, lock, ret) do { \
if ((ret = \
(t)->bt_csp == (t)->bt_esp ? __bam_stkgrow(t) : 0) == 0) { \
(t)->bt_csp->page = pagep; \
(t)->bt_csp->indx = page_indx; \
(t)->bt_csp->lock = lock; \
} \
} while (0)
#undef BT_STK_PUSH
#define BT_STK_PUSH(t, pagep, page_indx, lock, ret) do { \
BT_STK_ENTER(t, pagep, page_indx, lock, ret); \
++(t)->bt_csp; \
} while (0)
#undef BT_STK_POP
#define BT_STK_POP(t) \
((t)->bt_csp == (t)->bt_stack ? NULL : --(t)->bt_csp)
/*
* The in-memory recno data structure.
*
* !!!
* 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.
*/
#undef RECNO_OOB
#define RECNO_OOB 0 /* Illegal record number. */
struct __recno {
int re_delim; /* Variable-length delimiting byte. */
int re_pad; /* Fixed-length padding byte. */
u_int32_t re_len; /* Length for fixed-length records. */
char *re_source; /* Source file name. */
int re_fd; /* Source file descriptor */
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((DB *, db_recno_t));
#define RECNO_EOF 0x0001 /* EOF on backing source file. */
#define RECNO_MODIFIED 0x0002 /* Tree was modified. */
u_int32_t flags;
};
/*
* The in-memory btree data structure.
*/
struct __btree {
/*
* These fields are per-thread and are initialized when the BTREE structure
* is created.
*/
db_pgno_t bt_lpgno; /* Last insert location. */
DBT bt_rkey; /* Returned key. */
DBT bt_rdata; /* Returned data. */
EPG *bt_sp; /* Stack pointer. */
EPG *bt_csp; /* Current stack entry. */
EPG *bt_esp; /* End stack pointer. */
EPG bt_stack[5];
RECNO *bt_recno; /* Private recno structure. */
DB_BTREE_LSTAT lstat; /* Btree local statistics. */
/*
* These fields are copied from the original BTREE structure and never
* change.
*/
db_indx_t bt_maxkey; /* Maximum keys per page. */
db_indx_t bt_minkey; /* Minimum keys per page. */
int (*bt_compare) /* Comparison function. */
__P((const DBT *, const DBT *));
size_t(*bt_prefix) /* Prefix function. */
__P((const DBT *, const DBT *));
db_indx_t bt_ovflsize; /* Maximum key/data on-page size. */
};
#include "btree_auto.h"
#include "btree_ext.h"
#include "db_am.h"
#include "common_ext.h"
|