btree.src 6 KB
Newer Older
unknown's avatar
unknown committed
1 2 3
/*-
 * See the file LICENSE for redistribution information.
 *
unknown's avatar
unknown committed
4
 * Copyright (c) 1996-2005
unknown's avatar
unknown committed
5 6
 *	Sleepycat Software.  All rights reserved.
 *
unknown's avatar
unknown committed
7
 * $Id: btree.src,v 12.3 2005/08/08 03:37:05 ubell Exp $
unknown's avatar
unknown committed
8 9
 */

unknown's avatar
unknown committed
10 11
PREFIX	__bam
DBPRIVATE
unknown's avatar
unknown committed
12 13 14 15 16 17 18 19 20

INCLUDE #ifndef NO_SYSTEM_INCLUDES
INCLUDE #include <sys/types.h>
INCLUDE
INCLUDE #include <ctype.h>
INCLUDE #include <string.h>
INCLUDE #endif
INCLUDE
INCLUDE #include "db_int.h"
unknown's avatar
unknown committed
21 22 23 24 25 26 27
INCLUDE #include "dbinc/crypto.h"
INCLUDE #include "dbinc/db_page.h"
INCLUDE #include "dbinc/db_dispatch.h"
INCLUDE #include "dbinc/db_am.h"
INCLUDE #include "dbinc/btree.h"
INCLUDE #include "dbinc/log.h"
INCLUDE #include "dbinc/txn.h"
unknown's avatar
unknown committed
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
INCLUDE

/*
 * BTREE-split: used to log a page split.
 *
 * left:	the page number for the low-order contents.
 * llsn:	the left page's original LSN.
 * right:	the page number for the high-order contents.
 * rlsn:	the right page's original LSN.
 * indx:	the number of entries that went to the left page.
 * npgno:	the next page number
 * nlsn:	the next page's original LSN (or 0 if no next page).
 * root_pgno:	the root page number
 * pg:		the split page's contents before the split.
 * opflags:	SPL_NRECS: if splitting a tree that maintains a record count.
 */
BEGIN split		62
unknown's avatar
unknown committed
45
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
46
ARG	left		db_pgno_t	lu
unknown's avatar
unknown committed
47
POINTER	llsn		DB_LSN *	lu
unknown's avatar
unknown committed
48
ARG	right		db_pgno_t	lu
unknown's avatar
unknown committed
49 50 51 52
POINTER	rlsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
ARG	npgno		db_pgno_t	lu
POINTER	nlsn		DB_LSN *	lu
unknown's avatar
unknown committed
53
ARG	root_pgno	db_pgno_t	lu
unknown's avatar
unknown committed
54
PGDBT	pg		DBT		s
unknown's avatar
unknown committed
55 56 57 58 59 60 61 62 63 64 65 66 67 68
ARG	opflags		u_int32_t	lu
END

/*
 * BTREE-rsplit: used to log a reverse-split
 *
 * pgno:	the page number of the page copied over the root.
 * pgdbt:	the page being copied on the root page.
 * root_pgno:	the root page number.
 * nrec:	the tree's record count.
 * rootent:	last entry on the root page.
 * rootlsn:	the root page's original lsn.
 */
BEGIN rsplit		63
unknown's avatar
unknown committed
69
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
70
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
71
PGDBT	pgdbt		DBT		s
unknown's avatar
unknown committed
72
ARG	root_pgno	db_pgno_t	lu
unknown's avatar
unknown committed
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
ARG	nrec		db_pgno_t	lu
DBT	rootent		DBT		s
POINTER rootlsn		DB_LSN *	lu
END

/*
 * BTREE-adj: used to log the adjustment of an index.
 *
 * pgno:	the page modified.
 * lsn:		the page's original lsn.
 * indx:	the index adjusted.
 * indx_copy:	the index to copy if inserting.
 * is_insert:	0 if a delete, 1 if an insert.
 */
BEGIN adj		55
unknown's avatar
unknown committed
88
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
89
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
POINTER	lsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
ARG	indx_copy	u_int32_t	lu
ARG	is_insert	u_int32_t	lu
END

/*
 * BTREE-cadjust: used to adjust the count change in an internal page.
 *
 * pgno:	the page modified.
 * lsn:		the page's original lsn.
 * indx:	the index to be adjusted.
 * adjust:	the signed adjustment.
 * opflags:	CAD_UPDATEROOT: if root page count was adjusted.
 */
BEGIN cadjust		56
unknown's avatar
unknown committed
106
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
107
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
108 109 110 111 112 113 114 115 116 117 118 119 120 121
POINTER	lsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
ARG	adjust		int32_t		ld
ARG	opflags		u_int32_t	lu
END

/*
 * BTREE-cdel: used to log the intent-to-delete of a cursor record.
 *
 * pgno:	the page modified.
 * lsn:		the page's original lsn.
 * indx:	the index to be deleted.
 */
BEGIN cdel		57
unknown's avatar
unknown committed
122
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
123
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
124 125 126 127 128 129 130 131 132
POINTER	lsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
END

/*
 * BTREE-repl: used to log the replacement of an item.
 *
 * pgno:	the page modified.
 * lsn:		the page's original lsn.
unknown's avatar
unknown committed
133 134
 * indx:	the index to be replaced.
 * isdeleted:	set if the record was previously deleted.
unknown's avatar
unknown committed
135
 * orig:	the original data.
unknown's avatar
unknown committed
136 137 138
 * repl:	the replacement data.
 * prefix:	the prefix of the replacement that matches the original.
 * suffix:	the suffix of the replacement that matches the original.
unknown's avatar
unknown committed
139 140
 */
BEGIN repl		58
unknown's avatar
unknown committed
141
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
142
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
143 144 145 146 147 148 149 150 151 152 153 154 155
POINTER	lsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
ARG	isdeleted	u_int32_t	lu
DBT	orig		DBT		s
DBT	repl		DBT		s
ARG	prefix		u_int32_t	lu
ARG	suffix		u_int32_t	lu
END

/*
 * BTREE-root: log the assignment of a root btree page.
 */
BEGIN root		59
unknown's avatar
unknown committed
156
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
157 158
ARG	meta_pgno	db_pgno_t	lu
ARG	root_pgno	db_pgno_t	lu
unknown's avatar
unknown committed
159 160 161 162 163 164 165 166 167 168 169 170
POINTER	meta_lsn	DB_LSN *	lu
END

/*
 * BTREE-curadj: undo cursor adjustments on txn abort.
 *     Should only be processed during DB_TXN_ABORT.
 * NOTE: the first_indx field gets used to hold
 *	signed index adjustment in one case.
 *	care should be taken if its size is changed.
 */
BEGIN curadj		64
/* Fileid of db affected. */
unknown's avatar
unknown committed
171
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
/* Which adjustment. */
ARG	mode		db_ca_mode	ld
/* Page entry is from. */
ARG	from_pgno	db_pgno_t	lu
/* Page entry  went to. */
ARG	to_pgno		db_pgno_t	lu
/* Left page of root split. */
ARG	left_pgno	db_pgno_t	lu
/* First index of dup set. Also used as adjustment. */
ARG	first_indx	u_int32_t	lu
/* Index entry is from. */
ARG	from_indx	u_int32_t	lu
/* Index where entry went. */
ARG	to_indx		u_int32_t	lu
END

/*
 * BTREE-rcuradj: undo cursor adjustments on txn abort in
 *     renumbering recno trees.
 *     Should only be processed during DB_TXN_ABORT.
 */
BEGIN rcuradj	65
/* Fileid of db affected. */
unknown's avatar
unknown committed
195
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
196 197 198 199 200 201 202 203 204
/* Which adjustment. */
ARG	mode		ca_recno_arg	ld
/* Root page number. */
ARG	root		db_pgno_t	ld
/* Recno of the adjustment. */
ARG	recno		db_recno_t	ld
/* Order number of the adjustment. */
ARG	order		u_int32_t	ld
END
unknown's avatar
unknown committed
205 206 207 208 209 210 211 212

/*
 * BTREE-relink -- Handles relinking around a deleted leaf page.
 *
 */
BEGIN relink		147
/* Fileid of db affected. */
DB	fileid		int32_t		ld
unknown's avatar
unknown committed
213
/* The page being removed. */
unknown's avatar
unknown committed
214
ARG	pgno		db_pgno_t	lu
unknown's avatar
unknown committed
215 216
/* The new page number, if any. */
ARG	new_pgno	db_pgno_t	lu
unknown's avatar
unknown committed
217 218 219 220 221 222 223 224 225
/* The previous page. */
ARG	prev		db_pgno_t	lu
/* The previous page's original lsn. */
POINTER	lsn_prev	DB_LSN *	lu
/* The next page. */
ARG	next		db_pgno_t	lu
/* The previous page's original lsn. */
POINTER	lsn_next	DB_LSN *	lu
END
unknown's avatar
unknown committed
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

/*
 * BTREE-merge -- Handles merging of pages during a compaction.
 */
BEGIN merge		148
DB	fileid		int32_t		ld
ARG	pgno		db_pgno_t	lu
POINTER	lsn		DB_LSN *	lu
ARG	npgno		db_pgno_t	lu
POINTER nlsn		DB_LSN *	lu
DBT	hdr		DBT		s
DBT	data		DBT		s
DBT	ind		DBT		s
END

/*
 * BTREE-pgno -- Handles replacing a page number in the record
 * refernece on pgno by indx.
 */
BEGIN pgno		149
DB	fileid		int32_t		ld
ARG	pgno		db_pgno_t	lu
POINTER	lsn		DB_LSN *	lu
ARG	indx		u_int32_t	lu
ARG	opgno		db_pgno_t	lu
ARG	npgno		db_pgno_t	lu
END