Lines Matching refs:page
71 * Split a page.
95 * When __bam_split is first called, we know that a leaf page was too
96 * full for an insert. We don't know what leaf page it was, but we
98 * reacquire the leaf page, but this time get both the leaf page and
99 * its parent, locked. We then split the leaf page and see if the new
100 * internal key will fit into the parent page. If it will, we're done.
103 * only this time acquiring the parent page and its parent, locked.
105 * root page as the final resort. The entire process then repeats,
106 * as necessary, until we split a leaf page.
111 * stack is correct by storing the page's LSN when it was searched and
119 * Acquire a page and its parent, locked.
128 * Split the page if it still needs it (it's possible another
129 * thread of control has already split the page). If we are
130 * guaranteed that two items will fit on the page, the split
134 (db_indx_t)P_FREESPACE(cp->csp[0].page)) {
138 ret = cp->csp[0].page->pgno == PGNO_ROOT ?
145 /* Once we've split the leaf page, we're done. */
156 * threads may be modifying the tree, or the page usage
172 * Split the root page of a btree.
187 if (cp->page->level >= MAXBTREELEVEL) {
194 if ((ret = __bam_new(dbc, TYPE(cp->page), &lp)) != 0 ||
195 (ret = __bam_new(dbc, TYPE(cp->page), &rp)) != 0)
198 PGNO_INVALID, ISINTERNAL(cp->page) ? PGNO_INVALID : rp->pgno,
199 cp->page->level, TYPE(cp->page));
201 ISINTERNAL(cp->page) ? PGNO_INVALID : lp->pgno, PGNO_INVALID,
202 cp->page->level, TYPE(cp->page));
204 /* Split the page. */
213 __a.data = cp->page;
217 &LSN(cp->page), 0, dbp->log_fileid, PGNO(lp), &LSN(lp),
221 LSN(lp) = LSN(rp) = LSN(cp->page);
224 /* Clean up the new root page. */
226 __ram_root(dbc, cp->page, lp, rp) :
227 __bam_broot(dbc, cp->page, lp, rp))) != 0)
231 __bam_ca_split(dbp, cp->page->pgno, lp->pgno, rp->pgno, split, 1);
234 (void)memp_fput(dbp->mpf, cp->page, DB_MPOOL_DIRTY);
245 (void)memp_fput(dbp->mpf, cp->page, 0);
252 * Split the non-root page of a btree.
269 /* Create new right page for the split. */
270 if ((ret = __bam_new(dbc, TYPE(cp->page), &rp)) != 0)
273 ISINTERNAL(cp->page) ? PGNO_INVALID : cp->page->pgno,
274 ISINTERNAL(cp->page) ? PGNO_INVALID : cp->page->next_pgno,
275 cp->page->level, TYPE(cp->page));
277 /* Create new left page for the split. */
280 P_INIT(lp, dbp->pgsize, cp->page->pgno,
281 ISINTERNAL(cp->page) ? PGNO_INVALID : cp->page->prev_pgno,
282 ISINTERNAL(cp->page) ? PGNO_INVALID : rp->pgno,
283 cp->page->level, TYPE(cp->page));
289 * Only the indices are sorted on the page, i.e., the key/data pairs
290 * aren't, so it's simpler to copy the data from the split page onto
291 * two new pages instead of copying half the data to the right page
292 * and compacting the left page in place. Since the left page can't
293 * change, we swap the original and the allocated left page after the
300 * Fix up the previous pointer of any leaf page following the split
301 * page.
305 * page that's not in our direct ancestry. Consider a cursor walking
306 * through the leaf pages, that has the previous page read-locked and
307 * is waiting on a lock for the page we just split. It will deadlock
310 * the page we're splitting.
312 if (TYPE(cp->page) == P_LBTREE && rp->next_pgno != PGNO_INVALID) {
320 /* Insert the new pages into the parent page. */
329 __a.data = cp->page;
334 &cp->page->lsn, 0, dbp->log_fileid, PGNO(cp->page),
335 &LSN(cp->page), PGNO(rp), &LSN(rp), (u_int32_t)NUM_ENT(lp),
340 LSN(lp) = LSN(rp) = LSN(cp->page);
342 LSN(tp) = LSN(cp->page);
345 /* Copy the allocated page into place. */
346 memcpy(cp->page, lp, LOFFSET(lp));
347 memcpy((u_int8_t *)cp->page + HOFFSET(lp),
352 /* Finish the next-page link. */
357 __bam_ca_split(dbp, cp->page->pgno, cp->page->pgno, rp->pgno, split, 0);
360 (void)memp_fput(dbp->mpf, pp->page, DB_MPOOL_DIRTY);
362 (void)memp_fput(dbp->mpf, cp->page, DB_MPOOL_DIRTY);
382 (void)memp_fput(dbp->mpf, pp->page, 0);
387 (void)memp_fput(dbp->mpf, cp->page, 0);
397 * Fix up the btree root page after it has been split.
413 * If the root page was a leaf page, change it into an internal page.
415 * a leaf page) to the new root page.
443 /* Copy the first key of the child page onto the root page. */
468 /* Copy the first key of the child page onto the root page. */
522 * Fix up the recno root page after it has been split.
536 /* Initialize the page. */
561 * Insert a new key into a parent page, completing the split.
583 ppage = parent->page;
585 /* If handling record numbers, count records split to the right page. */
590 * Now we insert the new page's first key into the parent page, which
591 * completes the split. The parent points to a PAGE and a page index
596 * Some btree algorithms replace the key for the old page as well as
597 * the new page. We don't, as there's no reason to believe that the
598 * first key on the old page is any better than the key we have, and,
605 * Calculate the space needed on the parent page.
609 * the LAST entry on the page to its left. If the keys compare equal,
611 * must be retained for the next-to-leftmost key on the leftmost page
624 /* Add a new record for the right page. */
728 /* Add a new record for the right page. */
742 /* Adjust the parent page's left page record count. */
752 /* Update the left page count. */
764 * Do the real work of splitting the page.
779 pp = cp->page;
783 * If we're splitting the first (last) page on a level because we're
785 * sorted. Moving a single item to the new page is less work and can
791 ((ISINTERNAL(pp) && cp->indx == NUM_ENT(cp->page) - 1) ||
792 (!ISINTERNAL(pp) && cp->indx == NUM_ENT(cp->page))))
793 off = NUM_ENT(cp->page) - adjust;
807 * It's possible to try and split past the last record on the page if
808 * there's a very large record at the end of the page. Make sure this
810 * the page.
812 * Note, we try and split half the data present on the page. This is
813 * because another process may have already split the page and left
815 * how much space we're going to need on the page, and we may need up
816 * to half the page for a big item, so there's no easy test to decide
890 * no duplicate set can take up more than about 25% of the page,
892 * page set. So, this loop can't be unbounded.
925 * Copy a set of records from one page to another.
938 * Copy the rest of the data to the right page. Nxt is the next
939 * offset placed on the target page.