Lines Matching +full:page +full:- +full:size
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
36 #define F_SET(p, f) (p)->flags |= (f)
37 #define F_CLR(p, f) (p)->flags &= ~(f)
38 #define F_ISSET(p, f) ((p)->flags & (f))
42 #define DEFMINKEYPAGE (2) /* Minimum keys per page */
44 #define MINPSIZE (512) /* Minimum page size */
47 * Page 0 of a btree file contains a copy of the meta-data. This page is also
48 * used as an out-of-band page, i.e. page pointers that point to nowhere point
49 * to page 0. Page 1 is the root of the btree.
51 #define P_INVALID 0 /* Invalid tree page number. */
52 #define P_META 0 /* Tree metadata page number. */
53 #define P_ROOT 1 /* Tree root page number. */
56 * There are five page layouts in the btree: btree internal pages (BINTERNAL),
58 * (RLEAF) and overflow pages. All five page types have a page header (PAGE).
64 pgno_t pgno; /* this page's page number */
68 #define P_BINTERNAL 0x01 /* btree internal page */
69 #define P_BLEAF 0x02 /* leaf page */
70 #define P_OVERFLOW 0x04 /* overflow page */
71 #define P_RINTERNAL 0x08 /* recno internal page */
72 #define P_RLEAF 0x10 /* leaf page */
77 indx_t lower; /* lower bound of free space on page */
78 indx_t upper; /* upper bound of free space on page */
79 indx_t linp[1]; /* indx_t-aligned VAR. LENGTH DATA */
80 } PAGE; typedef
86 #define NEXTINDEX(p) (((p)->lower - BTDATAOFF) / sizeof(indx_t))
90 * rest of the page immediately following the page header. Each offset is to
91 * an item which is unique to the type of page. The h_lower offset is just
92 * past the last filled-in index. The h_upper offset is the first item on the
93 * page. Offsets are from the beginning of the page.
95 * If an item is too big to store on a single page, a flag is set and the item
96 * is a { page, size } pair such that the page is the first page of an overflow
97 * chain with size bytes of item. Overflow pages are simply bytes without any
100 * The page number and size fields in the items are pgno_t-aligned so they can
104 #define LALIGN(n) (((n) + sizeof(pgno_t) - 1) & ~(sizeof(pgno_t) - 1))
110 * on that page. For a tree without duplicate keys, an internal page with two
112 * and less than b stored on the page associated with a. Duplicate keys are
113 * somewhat special and can cause duplicate internal and leaf page records and
117 u_int32_t ksize; /* key size */
118 pgno_t pgno; /* page number stored on */
125 /* Get the page's BINTERNAL structure at index indx. */
127 ((BINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
133 /* Copy a BINTERNAL entry to the page. */
134 #define WR_BINTERNAL(p, size, pgno, flags) { \ argument
135 *(u_int32_t *)p = size; \
144 * For the recno internal pages, the item is a page number with the number of
145 * keys found on that page and below.
149 pgno_t pgno; /* page number stored below */
152 /* Get the page's RINTERNAL structure at index indx. */
154 ((RINTERNAL *)((char *)(pg) + (pg)->linp[indx]))
160 /* Copy a RINTERAL entry to the page. */
169 u_int32_t ksize; /* size of key */
170 u_int32_t dsize; /* size of data */
175 /* Get the page's BLEAF structure at index indx. */
177 ((BLEAF *)((char *)(pg) + (pg)->linp[indx]))
180 #define NBLEAF(p) NBLEAFDBT((p)->ksize, (p)->dsize)
187 /* Copy a BLEAF entry to the page. */
189 *(u_int32_t *)p = key->size; \
191 *(u_int32_t *)p = data->size; \
195 memmove(p, key->data, key->size); \
196 p += key->size; \
197 memmove(p, data->data, data->size); \
202 u_int32_t dsize; /* size of data */
207 /* Get the page's RLEAF structure at index indx. */
209 ((RLEAF *)((char *)(pg) + (pg)->linp[indx]))
212 #define NRLEAF(p) NRLEAFDBT((p)->dsize)
218 /* Copy a RLEAF entry to the page. */
220 *(u_int32_t *)p = data->size; \
224 memmove(p, data->data, data->size); \
228 * A record in the tree is either a pointer to a page and an index in the page
229 * or a page number and an index. These structures are used as a cursor, stack
232 * One comment about searches. Internal page searches must find the largest
233 * record less than key in the tree so that descents work. Leaf page searches
238 pgno_t pgno; /* the page number */
239 indx_t index; /* the index on the page */
243 PAGE *page; /* the (pinned) page */ member
244 indx_t index; /* the index on the page */
248 * About cursors. The cursor (and the page that contained the key/data pair
274 recno_t rcursor; /* R: recno cursor (1-based) */
291 u_int32_t psize; /* page size */
292 u_int32_t free; /* page number of first free page */
299 /* The in-memory btree/recno data structure. */
305 EPG bt_cur; /* current (pinned) page */
306 PAGE *bt_pinned; /* page pinned across calls */
311 t->bt_sp->pgno = p; \
312 t->bt_sp->index = i; \
313 ++t->bt_sp; \
315 #define BT_POP(t) (t->bt_sp == t->bt_stack ? NULL : --t->bt_sp)
316 #define BT_CLR(t) (t->bt_sp = t->bt_stack)
325 pgno_t bt_free; /* next free page */
326 u_int32_t bt_psize; /* page size */
327 indx_t bt_ovflsize; /* cut-off for key/data overflow */
346 size_t bt_msize; /* R: size of mapped region. */
356 #define B_INMEM 0x00001 /* in-memory tree */
360 #define B_RDONLY 0x00010 /* read-only tree */
369 #define R_INMEM 0x00800 /* in-memory file */
371 #define R_RDONLY 0x02000 /* read-only file */