Lines Matching refs:leaf
45549 /* only mkdir if leaf dir != "." or "/" or ".." */
57152 ** (b) The page was a freelist leaf page at the start of the transaction.
57186 ** all queries. Note in particular the content of freelist leaf
62590 ** a) When reading a free-list leaf page from the database, and
63347 ** the page has been added as a leaf of the freelist and so its
69577 ** 23 1 Min leaf payload fraction (must be 32)
69613 ** The min leaf payload fraction is like the min embedded payload fraction
69614 ** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
69641 ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
69648 ** The flags define the format of this btree page. The leaf flag means that
69704 ** 4 Page number of the left child. Omitted if leaf flag is set.
69718 ** Freelist pages come in two subtypes: trunk pages and leaf pages. The
69720 ** page points to multiple leaf pages. The content of a leaf page is
69725 ** 4 Number of leaf pointers on this page
69788 u8 intKeyLeaf; /* True if the leaf of an intKey table */
69792 u8 leaf; /* True if a leaf page */
69794 u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */
71161 ** when a page that previously contained data becomes a free-list leaf
71166 ** free-list leaf pages:
71169 ** a free-list leaf page, the page is not written to the database
71170 ** (as free-list leaf pages contain no meaningful data). Sometimes
71174 ** 2) When a free-list leaf page is reused, its content is not read
71188 ** moved to become a free-list leaf page, the corresponding bit is
71189 ** set in the bitvec. Whenever a leaf page is extracted from the free-list,
71212 ** This function is called when a free-list leaf page is removed from the
71776 ** btreeParseCellPtr() => table btree leaf nodes
71790 assert( pPage->leaf==0 );
71811 assert( pPage->leaf==0 || pPage->leaf==1 );
71896 assert( pPage->leaf==0 || pPage->leaf==1 );
71942 ** cellSizePtrTableLeaf() => table leaf nodes
71944 ** cellSizeIdxLeaf() => index leaf nodes
72373 assert( pPage->cellOffset == hdr + 12 - 4*pPage->leaf );
72574 pPage->leaf = 1;
72598 pPage->leaf = 0;
72725 if( !pPage->leaf ) iCellLast--;
73420 ** inserting them into a leaf page (function fillInCell()). If
73702 ** freelist leaf pages are not written back to the database. Thus in-page
73706 ** that freelist leaf pages are written back into the database, increasing
73888 ** fractions and the leaf payload fraction values must be 64, 32, and 32.
74349 if( !pPage->leaf ){
74355 if( !pPage->leaf ){
75955 ** Page pParent is an internal (non-leaf) tree page. This function
76090 }else if( !pRoot->leaf ){
76104 ** Move the cursor down to the left-most leaf entry beneath the
76107 ** The left-most leaf is the one with the smallest key - the first
76117 while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
76126 ** Move the cursor down to the right-most leaf entry beneath the
76142 while( !(pPage = pCur->pPage)->leaf ){
76189 return pCur->ix==pCur->pPage->nCell-1 && pCur->pPage->leaf!=0;
76232 ** left pointing at a leaf page which would hold the entry if it
76355 if( !pPage->leaf ){
76369 assert( lwr==upr+1 || !pPage->leaf );
76371 if( pPage->leaf ){
76461 ** left pointing at a leaf page which would hold the entry if it
76520 && pCur->pPage->leaf
76663 assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
76665 if( pPage->leaf ){
76745 if( NEVER(pCur->pPage->leaf==0) ) return -1;
76803 if( !pPage->leaf ){
76822 if( pPage->leaf ){
76841 if( pPage->leaf ){
76894 if( !pPage->leaf ){
76912 if( pPage->intKey && !pPage->leaf ){
76928 || pCur->pPage->leaf==0
77049 ** is the number of leaf page pointers to follow. */
77095 ** pointers to free-list leaves. The first leaf becomes a trunk
77133 /* Extract a leaf from the trunk */
77175 TRACE(("ALLOCATE: %u was leaf %u of %u on trunk %u"
77331 ** new free-list trunk page. Otherwise, it will become a leaf of the
77333 ** is possible to add the page as a new free-list leaf.
77336 u32 nLeaf; /* Initial number of leaf cells on trunk page */
77356 ** being freed as a new leaf.
77383 TRACE(("FREE-PAGE: %u leaf on trunk page %u\n",pPage->pgno,pTrunk->pgno));
77389 ** the page being freed as a leaf page of the first trunk in the free-list.
78018 ** are used and they point to the leaf pages only, and the ixNx value are:
78427 ** Instead of trying to balance the 3 right-most leaf pages, just add
78434 ** pPage is the leaf page which is the right-most page in the tree.
78566 if( !pPage->leaf ){
78572 if( !pPage->leaf ){
78584 ** on page pFrom to page pTo. If page pFrom was not a leaf page, then
78695 u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */
78696 int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
78849 ** If the siblings are on leaf pages, then the child pointers of the
78856 ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf.
78860 leafCorrection = b.pRef->leaf*4;
78871 /* Verify that all sibling pages are of the same "type" (table-leaf,
78872 ** table-interior, index-leaf, or index-interior).
78937 if( !pOld->leaf ){
79272 if( !pNew->leaf ){
79275 /* If the tree is a leaf-data tree, and the siblings are leaves,
79288 /* Obscure case for non-leaf-data trees: If the cell at pCell was
79289 ** previously stored on a leaf node, and its reported size was 4
79994 assert( pPage->leaf || !pPage->intKey );
80047 if( !pPage->leaf ){
80078 assert( pPage->leaf );
80082 assert( pPage->leaf );
80330 if( !pPage->leaf
80344 /* If the page containing the entry to delete is not a leaf page, move
80351 if( !pPage->leaf ){
80379 /* If the cell deleted was not located on a leaf page, then the cursor
80382 ** node. The cell from the leaf node needs to be moved to the internal
80384 if( !pPage->leaf ){
80413 /* Balance the tree. If the entry deleted was located on a leaf page,
80419 ** pCur is pointing to the leaf page from which a cell was removed to
80421 ** tricky as the leaf node may be underfull, and the internal node may
80423 ** on the leaf node first. If the balance proceeds far enough up the
80425 ** been corrected, so be it. Otherwise, after balancing the leaf node,
80667 if( !pPage->leaf ){
80674 if( !pPage->leaf ){
80949 /* If this is a leaf page or the tree is not an int-key tree, then
80954 if( pPage->leaf || !pPage->intKey ){
80958 /* pPage is a leaf node. This loop navigates the cursor so that it
80968 if( pPage->leaf ){
81176 "freelist leaf count too big on page %u", iPage);
81359 if( pPage->leaf || pPage->intKey==0 ){
81365 cellStart = hdr + 12 - 4*pPage->leaf;
81369 if( !pPage->leaf ){
81381 /* For leaf pages, the coverage check will occur in the same loop
81435 if( !pPage->leaf ){
81450 /* Populate the coverage-checking heap for leaf pages */
81460 /* For leaf pages, the min-heap has already been initialized and the
81463 if( !pPage->leaf ){
105138 ** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes.
105158 ** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the
105167 int iSeq, /* Sequence number of leaf within tree */
165418 ** But the leaf pages are full-size, so pProbe->szIdxRow would badly
185332 **** Segment leaf nodes ****
185333 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
185335 ** iterate through a single leaf node's data) and LeavesReader (to
185336 ** iterate through a segment's entire leaf layer). Leaf nodes have
185339 ** varint iHeight; (height from leaf level, always 0)
185361 ** New data is spilled to a new leaf node when the current node
185364 ** node (a leaf node with a single term and doclist). The goal of
185371 ** dynamic. For instance, it may make more sense to have a 2.5k leaf
185381 ** SegmentWriter creates new leaf nodes, or when an interior node
185385 ** varint iHeight; (height from leaf level, always >0)
185427 ** This could be either a leaf node or an interior node. If the top
185437 ** start_block - first leaf node
185438 ** leaves_end_block - last leaf node
185442 ** If the root node is a leaf node, then start_block,
185461 ** leaf nodes are written in to the %_segments table in order, this
186036 u32 nLeafAdd; /* Number of leaf blocks added this trans */
188157 ** node for the range of leaf nodes that may contain the specified term
188161 ** left-most leaf node in the tree that may contain the specified term.
188163 ** right-most leaf node that may contain a term for which the specified
188166 ** It is possible that the range of returned leaf nodes does not contain
188170 ** never loads leaf nodes into memory), it is not possible to be sure.
188180 sqlite3_int64 *piLeaf, /* Selected leaf node */
188181 sqlite3_int64 *piLeaf2 /* Selected leaf node */
189684 ** involves updating the leaf block that contains the smallest unmerged
189685 ** entry and each block (if any) between the leaf and the root node. So
189692 ** is only attempted if it will write at least 64 leaf blocks. Hence
191148 ** of data that will fit on a single leaf page of an intkey table in
193723 /* Set $p to point to the left-most leaf in the tree of eType nodes. */
193729 /* This loop runs once for each leaf in the tree of eType nodes. */
193767 /* If that was the last leaf node, break out of the loop */
193770 /* Set $p to point to the next leaf in the tree of eType nodes */
196603 ** a contiguous set of segment b-tree leaf nodes. Although the details of
196623 sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */
196624 sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */
196626 sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */
196677 i64 nLeafData; /* Number of bytes of leaf data written */
196683 ** the leaf nodes). These functions and type are only ever used by code
196821 /* Estimate the upper limit on the number of leaf nodes in a new segment
197844 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
198098 sqlite3_int64 iStartLeaf, /* First leaf to traverse */
198099 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
198454 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */
198650 sqlite3_int64 iLeaf, /* Block id of first leaf node */
198726 i64 nReq; /* Number of bytes required on leaf page */
198775 /* The current leaf node is full. Write it out to the database. */
198784 ** a) be greater than the largest term on the leaf node just written
198788 ** leaf node (zTerm/nTerm).
198875 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
199247 ** b-tree leaf nodes contain more than one term.
199811 ** estimate the number of leaf blocks of content to be written
200198 int nLeafEst; /* Space allocated for leaf blocks */
200199 int nWork; /* Number of leaf pages flushed */
200204 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */
200320 /* Figure out if this is a leaf or an internal node. */
200332 ** This function is called while writing an FTS segment each time a leaf o
200335 ** than or equal to the first key that will be written to the next leaf
200338 ** The block id of the leaf node just written to disk may be found in
200426 ** A node header is a single 0x00 byte for a leaf node, or a height varint
200430 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
200459 ** leaf node, and there must not be a doclist for an internal node. */
200508 int nSpace; /* Total space in bytes required on leaf */
200511 NodeWriter *pLeaf; /* Object used to write leaf nodes */
200524 ** and if there is still room for another leaf page, write this block out to
200536 ** a) be greater than the largest term on the leaf node just written
200540 ** leaf node (zTerm/nTerm).
200599 ** root node. If the segment fits entirely on a single leaf node, iRoot
200624 ** single leaf and a single interior (root) node.
200922 ** maximum number of leaf blocks that may be required is the sum of the
200923 ** number of leaf blocks consumed by the input segments, plus the number
200929 ** array of leaf nodes starts at the first block allocated. The array
200930 ** of interior nodes that are parents of the leaf nodes start at block
200945 int nLeafEst = 0; /* Blocks allocated for leaf nodes */
201094 ** node. The node may be a leaf or an internal node.
201097 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
201111 int bLeaf; /* True for a leaf node */
201203 /* Variable iNewStart now contains the first valid leaf node. */
201398 ** Attempt an incremental merge that writes nMerge leaf blocks.
201404 ** write the quota of nMerge leaf blocks.
201408 int nRem = nMerge; /* Number of leaf pages yet to be written */
201595 ** A and B are integers that decode to be the number of leaf pages
210374 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
210502 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
210569 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
211248 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
211651 ** Check the leaf RTree cell given by pCellData against constraint p.
212108 ** Use nodeAcquire() to obtain the leaf node containing the record with
212193 RtreeSearchPoint *p; /* Search point for the leaf */
212551 RtreeNode **ppLeaf /* OUT: Selected leaf page */
213016 ** rowid of the row to delete, which can be used to find the leaf on which
213017 ** the entry resides (argument pLeaf). Once the leaf is located, this
213165 ** subtree iHeight high (leaf nodes have iHeight==0).
213249 /* Obtain a reference to the leaf node that contains the entry
213260 /* Delete the cell in question from the leaf node. */
214144 int nLeaf; /* Number of leaf cells in table */
214145 int nNonLeaf; /* Number of non-leaf cells in table */
214279 int bLeaf, /* True for a leaf cell, false for interior */
214377 int iDepth, /* Depth of iNode (0==leaf) */
214561 ** c) for leaf nodes, that there is an entry in the %_rowid
214565 ** d) for cells on non-leaf nodes, that there is an entry in the
214570 ** as there are leaf cells in the r-tree structure, and that there
214571 ** is a leaf cell that corresponds to each entry in the %_rowid table.
214574 ** as there are non-leaf cells in the r-tree structure, and that
214575 ** there is a non-leaf cell that corresponds to each entry in the
215995 RtreeSearchPoint *p; /* Search point for the leaf */
217605 ** The problem is that in order to update a b-tree, the leaf page (at least)
217608 ** single leaf that is modified more than once as part of the transaction
217617 ** and all but guarantees each modified leaf page is loaded and stored
223622 " pagetype TEXT," /* 3 'internal', 'leaf', 'overflow', or NULL */
223643 u32 iChildPg; /* Child node (or 0 if this is a leaf) */
223928 if( flags==0x0D ){ /* Table leaf node */
223931 }else{ /* Index interior and leaf nodes */
224243 case 0x0D: /* table leaf */
224244 case 0x0A: /* index leaf */
224245 pCsr->zPagetype = "leaf";
232122 ** field that occurs at the start of each leaf page (see fts5_index.c). */
236746 ** Distance from this node to furthest leaf. This is always 0 for nodes
236754 int iHeight; /* Distance to tree leaf nodes */
240558 ** * all segment b-tree leaf data is stored in fixed size page records
240575 #define FTS5_OPT_WORK_UNIT 1000 /* Number of leaf pages per optimize step */
240576 #define FTS5_WORK_UNIT 64 /* Number of leaf pages in unit of work */
240639 ** + first leaf page number (often 1, always greater than 0)
240640 ** + final leaf page number
240659 ** Most of each segment leaf is taken up by term/doclist data. The
240661 ** on the leaf page, is:
240702 ** Each leaf page begins with a 4-byte header containing 2 16-bit
240710 ** size of the leaf page in bytes.
240720 ** term/doclist data fits on a single leaf page. If this is not the case,
240737 ** a single leaf record only. The format of each doclist index leaf page
240741 ** 0x01: Clear if leaf is also the root page, otherwise set.
240743 ** * Page number of fts index leaf page. As a varint.
240810 ** The rowid for each segment leaf is found by passing the segment id and
240811 ** the leaf page number to the FTS5_SEGMENT_ROWID macro. Leaves are numbered
240862 int szLeaf; /* Size of leaf without page-index */
240933 int pgnoFirst; /* First leaf page number in segment */
240934 int pgnoLast; /* Last leaf page number in segment */
240963 Fts5Buffer buf; /* Buffer containing leaf data */
240976 i64 iPrevRowid; /* Previous rowid written to current leaf */
240980 u8 bFirstTermInPage; /* True if next term will be first in leaf */
240981 int nLeafWritten; /* Number of leaf pages written */
241006 ** Current leaf page number within segment.
241009 ** Byte offset within the current leaf that is the first byte of the
241013 ** Buffer containing current leaf page data. Set to NULL at EOF.
241051 int iLeafPgno; /* Current leaf page number */
241052 Fts5Data *pLeaf; /* Current leaf data */
241054 i64 iLeafOffset; /* Byte offset within current leaf */
241093 ** leaf page.
241103 ** Argument is a pointer to an Fts5Data structure that contains a leaf
241104 ** page. This macro evaluates to true if the leaf contains no terms, or
241182 int iLeafPgno; /* Page number of current leaf page */
241183 i64 iRowid; /* First rowid on leaf iLeafPgno */
241764 /* TODO: Do we need this if the leaf-index is appended? Probably... */
242293 ** Load the next leaf page into the segment iterator.
242905 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
242987 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
243007 ** function searches the leaf page for a term matching (pTerm/nTerm).
243180 /* This block sets stack variable iPg to the leaf page number that may
243575 ** It is an error if leaf iLeafPgno does not exist. Unless the db is
244728 /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written
244740 ** last term on leaf page (pWriter->iBtPage) is completed.
244770 ** This is called once for each leaf page except the first that contains
244773 ** smaller than the first term on the new leaf.
244791 ** This function is called when flushing a leaf page that contains no
244798 /* If there were no rowids on the leaf page either and the doclist-index
244820 ** Rowid iRowid has just been appended to the current leaf page. It is the
244839 ** doclist-index leaf page) up into the next level of the b-tree
244918 /* The new leaf holds no terms or rowids */
244944 /* If the current leaf page is full, flush it to disk. */
244966 /* This is the first term on a leaf that is not the leftmost leaf in
245083 int *pnLeaf /* OUT: Number of leaf pages in b-tree */
245139 /* Initialize the 4-byte leaf-page header to 0x00. */
245170 int iOff = pSeg->iTermLeafOffset; /* Offset on new first leaf page */
245243 int nRem = pnRem ? *pnRem : 0; /* Output leaf pages left to write */
245348 /* Flush the last leaf page to disk. Set the output segment b-tree height
245349 ** and last leaf page number at the same time. */
245478 ** A total of nLeaf leaf pages of data has just been flushed to a level-0
245494 int nRem; /* Number of leaf pages left to write */
245561 ** from a segment leaf page. In that case the %_idx entry is removed
245748 ** entry overflows onto the next leaf page, this value will be
245942 ** leaf page before writing it back to disk. Input variables are:
245944 ** nPg: Total initial size of leaf page.
246029 int pgnoLast = 0; /* Last leaf page number in segment */
246043 Fts5Buffer *pBuf; /* Buffer in which to assemble leaf page */
246077 /* The entire doclist will fit on the current leaf. */
246085 /* The entire doclist will not fit on this leaf. The following
246160 /* The entire poslist will fit on the current leaf. So copy
246164 /* The entire poslist will not fit on this leaf. So it needs
248266 int iLeaf /* Load doclist-index for this leaf */
248466 /* Now check that the iter.nEmpty leaves following the current leaf
248549 i64 iRow; /* Rowid for this leaf */
248550 Fts5Data *pLeaf; /* Data for this leaf */
248557 /* If the leaf in question has already been trimmed from the segment,
248564 /* Check that the leaf contains at least one term, and that it is equal
248566 ** is also a rowid pointer within the leaf page header, it points to a
248583 int iOff; /* Offset of first term on leaf */
248584 int iRowidOff; /* Offset of first rowid on leaf */
248585 int nTerm; /* Size of term on leaf in bytes */
248604 /* Now check that the iter.nEmpty leaves following the current leaf
248624 /* Check any rowid-less pages that occur before the current leaf. */
248635 /* Check that the leaf page indicated by the iterator really does
248670 /* Page iter.iLeaf must now be the rightmost leaf-page in the segment */