Lines Matching defs:leaf
43961 /* only mkdir if leaf dir != "." or "/" or ".." */
55525 ** (b) The page was a freelist leaf page at the start of the transaction.
55559 ** all queries. Note in particular the content of freelist leaf
61032 ** a) When reading a free-list leaf page from the database, and
61774 ** the page has been added as a leaf of the freelist and so its
67631 ** 23 1 Min leaf payload fraction (must be 32)
67667 ** The min leaf payload fraction is like the min embedded payload fraction
67668 ** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
67695 ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
67702 ** The flags define the format of this btree page. The leaf flag means that
67758 ** 4 Page number of the left child. Omitted if leaf flag is set.
67772 ** Freelist pages come in two subtypes: trunk pages and leaf pages. The
67774 ** page points to multiple leaf pages. The content of a leaf page is
67779 ** 4 Number of leaf pointers on this page
67842 u8 intKeyLeaf; /* True if the leaf of an intKey table */
67846 u8 leaf; /* True if a leaf page */
67848 u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */
69188 ** when a page that previously contained data becomes a free-list leaf
69193 ** free-list leaf pages:
69196 ** a free-list leaf page, the page is not written to the database
69197 ** (as free-list leaf pages contain no meaningful data). Sometimes
69201 ** 2) When a free-list leaf page is reused, its content is not read
69215 ** moved to become a free-list leaf page, the corresponding bit is
69216 ** set in the bitvec. Whenever a leaf page is extracted from the free-list,
69239 ** This function is called when a free-list leaf page is removed from the
69786 ** btreeParseCellPtr() => table btree leaf nodes
69800 assert( pPage->leaf==0 );
69821 assert( pPage->leaf==0 || pPage->leaf==1 );
69902 assert( pPage->leaf==0 || pPage->leaf==1 );
69948 ** cellSizePtrTableLeaf() => table leaf nodes
69949 ** cellSizePtr() => all index nodes & table leaf nodes
70335 assert( pPage->cellOffset == hdr + 12 - 4*pPage->leaf );
70531 pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 );
70533 pPage->childPtrSize = 4-4*pPage->leaf;
70540 ** leaf table b-tree page. */
70543 if( pPage->leaf ){
70559 ** leaf index b-tree page. */
70576 "database corruption at page[%u], flagByte[%x], isInit[%u], intKey[%u], intKeyLeaf[%u], leaf[%u], "
70583 pPage->leaf,
70699 if( !pPage->leaf ) iCellLast--;
71422 ** inserting them into a leaf page (function fillInCell()). If
71704 ** freelist leaf pages are not written back to the database. Thus in-page
71708 ** that freelist leaf pages are written back into the database, increasing
71890 ** fractions and the leaf payload fraction values must be 64, 32, and 32.
72324 if( !pPage->leaf ){
72330 if( !pPage->leaf ){
73913 ** Page pParent is an internal (non-leaf) tree page. This function
74048 }else if( !pRoot->leaf ){
74062 ** Move the cursor down to the left-most leaf entry beneath the
74065 ** The left-most leaf is the one with the smallest key - the first
74075 while( rc==SQLITE_OK && !(pPage = pCur->pPage)->leaf ){
74084 ** Move the cursor down to the right-most leaf entry beneath the
74100 while( !(pPage = pCur->pPage)->leaf ){
74156 assert( pCur->pPage->leaf );
74184 ** left pointing at a leaf page which would hold the entry if it
74306 if( !pPage->leaf ){
74320 assert( lwr==upr+1 || !pPage->leaf );
74322 if( pPage->leaf ){
74412 ** left pointing at a leaf page which would hold the entry if it
74471 && pCur->pPage->leaf
74614 assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
74616 if( pPage->leaf ){
74668 ** will always point to a leaf node. */
74670 if( NEVER(pCur->pPage->leaf==0) ) return -1;
74727 if( !pPage->leaf ){
74746 if( pPage->leaf ){
74765 if( pPage->leaf ){
74815 if( !pPage->leaf ){
74833 if( pPage->intKey && !pPage->leaf ){
74849 || pCur->pPage->leaf==0
74970 ** is the number of leaf page pointers to follow. */
75016 ** pointers to free-list leaves. The first leaf becomes a trunk
75054 /* Extract a leaf from the trunk */
75096 TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
75252 ** new free-list trunk page. Otherwise, it will become a leaf of the
75254 ** is possible to add the page as a new free-list leaf.
75257 u32 nLeaf; /* Initial number of leaf cells on trunk page */
75277 ** being freed as a new leaf.
75304 TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
75310 ** the page being freed as a leaf page of the first trunk in the free-list.
75851 ** are used and they point to the leaf pages only, and the ixNx value are:
76245 ** Instead of trying to balance the 3 right-most leaf pages, just add
76252 ** pPage is the leaf page which is the right-most page in the tree.
76384 if( !pPage->leaf ){
76390 if( !pPage->leaf ){
76402 ** on page pFrom to page pTo. If page pFrom was not a leaf page, then
76513 u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */
76514 int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
76667 ** If the siblings are on leaf pages, then the child pointers of the
76674 ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf.
76678 leafCorrection = b.pRef->leaf*4;
76689 /* Verify that all sibling pages are of the same "type" (table-leaf,
76690 ** table-interior, index-leaf, or index-interior).
76755 if( !pOld->leaf ){
77088 if( !pNew->leaf ){
77091 /* If the tree is a leaf-data tree, and the siblings are leaves,
77104 /* Obscure case for non-leaf-data trees: If the cell at pCell was
77105 ** previously stored on a leaf node, and its reported size was 4
77786 assert( pPage->leaf || !pPage->intKey );
77833 if( !pPage->leaf ){
77864 assert( pPage->leaf );
77868 assert( pPage->leaf );
78114 if( !pPage->leaf
78128 /* If the page containing the entry to delete is not a leaf page, move
78135 if( !pPage->leaf ){
78163 /* If the cell deleted was not located on a leaf page, then the cursor
78166 ** node. The cell from the leaf node needs to be moved to the internal
78168 if( !pPage->leaf ){
78197 /* Balance the tree. If the entry deleted was located on a leaf page,
78203 ** pCur is pointing to the leaf page from which a cell was removed to
78205 ** tricky as the leaf node may be underfull, and the internal node may
78207 ** on the leaf node first. If the balance proceeds far enough up the
78209 ** been corrected, so be it. Otherwise, after balancing the leaf node,
78451 if( !pPage->leaf ){
78458 if( !pPage->leaf ){
78733 /* If this is a leaf page or the tree is not an int-key tree, then
78738 if( pPage->leaf || !pPage->intKey ){
78742 /* pPage is a leaf node. This loop navigates the cursor so that it
78752 if( pPage->leaf ){
78922 "freelist leaf count too big on page %d", iPage);
79103 cellStart = hdr + 12 - 4*pPage->leaf;
79107 if( !pPage->leaf ){
79119 /* For leaf pages, the coverage check will occur in the same loop
79173 if( !pPage->leaf ){
79188 /* Populate the coverage-checking heap for leaf pages */
79198 /* For leaf pages, the min-heap has already been initialized and the
79201 if( !pPage->leaf ){
102115 ** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes.
102135 ** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the
102144 int iSeq, /* Sequence number of leaf within tree */
178818 **** Segment leaf nodes ****
178819 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
178821 ** iterate through a single leaf node's data) and LeavesReader (to
178822 ** iterate through a segment's entire leaf layer). Leaf nodes have
178825 ** varint iHeight; (height from leaf level, always 0)
178847 ** New data is spilled to a new leaf node when the current node
178850 ** node (a leaf node with a single term and doclist). The goal of
178857 ** dynamic. For instance, it may make more sense to have a 2.5k leaf
178867 ** SegmentWriter creates new leaf nodes, or when an interior node
178871 ** varint iHeight; (height from leaf level, always >0)
178913 ** This could be either a leaf node or an interior node. If the top
178923 ** start_block - first leaf node
178924 ** leaves_end_block - last leaf node
178928 ** If the root node is a leaf node, then start_block,
178947 ** leaf nodes are written in to the %_segments table in order, this
179522 u32 nLeafAdd; /* Number of leaf blocks added this trans */
181637 ** node for the range of leaf nodes that may contain the specified term
181641 ** left-most leaf node in the tree that may contain the specified term.
181643 ** right-most leaf node that may contain a term for which the specified
181646 ** It is possible that the range of returned leaf nodes does not contain
181650 ** never loads leaf nodes into memory), it is not possible to be sure.
181660 sqlite3_int64 *piLeaf, /* Selected leaf node */
181661 sqlite3_int64 *piLeaf2 /* Selected leaf node */
183164 ** involves updating the leaf block that contains the smallest unmerged
183165 ** entry and each block (if any) between the leaf and the root node. So
183172 ** is only attempted if it will write at least 64 leaf blocks. Hence
184572 ** of data that will fit on a single leaf page of an intkey table in
187130 /* Set $p to point to the left-most leaf in the tree of eType nodes. */
187136 /* This loop runs once for each leaf in the tree of eType nodes. */
187174 /* If that was the last leaf node, break out of the loop */
187177 /* Set $p to point to the next leaf in the tree of eType nodes */
190009 ** a contiguous set of segment b-tree leaf nodes. Although the details of
190029 sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */
190030 sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */
190032 sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */
190083 i64 nLeafData; /* Number of bytes of leaf data written */
190089 ** the leaf nodes). These functions and type are only ever used by code
190227 /* Estimate the upper limit on the number of leaf nodes in a new segment
191250 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
191504 sqlite3_int64 iStartLeaf, /* First leaf to traverse */
191505 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
191860 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */
192056 sqlite3_int64 iLeaf, /* Block id of first leaf node */
192132 i64 nReq; /* Number of bytes required on leaf page */
192181 /* The current leaf node is full. Write it out to the database. */
192190 ** a) be greater than the largest term on the leaf node just written
192194 ** leaf node (zTerm/nTerm).
192281 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
192651 ** b-tree leaf nodes contain more than one term.
193216 ** estimate the number of leaf blocks of content to be written
193599 int nLeafEst; /* Space allocated for leaf blocks */
193600 int nWork; /* Number of leaf pages flushed */
193605 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */
193721 /* Figure out if this is a leaf or an internal node. */
193733 ** This function is called while writing an FTS segment each time a leaf o
193736 ** than or equal to the first key that will be written to the next leaf
193739 ** The block id of the leaf node just written to disk may be found in
193827 ** A node header is a single 0x00 byte for a leaf node, or a height varint
193831 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
193860 ** leaf node, and there must not be a doclist for an internal node. */
193907 int nSpace; /* Total space in bytes required on leaf */
193910 NodeWriter *pLeaf; /* Object used to write leaf nodes */
193931 ** a) be greater than the largest term on the leaf node just written
193935 ** leaf node (zTerm/nTerm).
193994 ** root node. If the segment fits entirely on a single leaf node, iRoot
194019 ** single leaf and a single interior (root) node.
194316 ** maximum number of leaf blocks that may be required is the sum of the
194317 ** number of leaf blocks consumed by the input segments, plus the number
194323 ** array of leaf nodes starts at the first block allocated. The array
194324 ** of interior nodes that are parents of the leaf nodes start at block
194339 int nLeafEst = 0; /* Blocks allocated for leaf nodes */
194488 ** node. The node may be a leaf or an internal node.
194491 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
194505 int bLeaf; /* True for a leaf node */
194597 /* Variable iNewStart now contains the first valid leaf node. */
194792 ** Attempt an incremental merge that writes nMerge leaf blocks.
194798 ** write the quota of nMerge leaf blocks.
194802 int nRem = nMerge; /* Number of leaf pages yet to be written */
194989 ** A and B are integers that decode to be the number of leaf pages
200997 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
201119 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
201187 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
201864 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
202264 ** Check the leaf RTree cell given by pCellData against constraint p.
202716 ** Use nodeAcquire() to obtain the leaf node containing the record with
202799 RtreeSearchPoint *p; /* Search point for the leaf */
203147 RtreeNode **ppLeaf /* OUT: Selected leaf page */
203669 ** rowid of the row to delete, which can be used to find the leaf on which
203670 ** the entry resides (argument pLeaf). Once the leaf is located, this
203919 ** subtree iHeight high (leaf nodes have iHeight==0).
204008 /* Obtain a reference to the leaf node that contains the entry
204019 /* Delete the cell in question from the leaf node. */
204892 int nLeaf; /* Number of leaf cells in table */
204893 int nNonLeaf; /* Number of non-leaf cells in table */
205027 int bLeaf, /* True for a leaf cell, false for interior */
205125 int iDepth, /* Depth of iNode (0==leaf) */
205300 ** c) for leaf nodes, that there is an entry in the %_rowid
205304 ** d) for cells on non-leaf nodes, that there is an entry in the
205309 ** as there are leaf cells in the r-tree structure, and that there
205310 ** is a leaf cell that corresponds to each entry in the %_rowid table.
205313 ** as there are non-leaf cells in the r-tree structure, and that
205314 ** there is a non-leaf cell that corresponds to each entry in the
206712 RtreeSearchPoint *p; /* Search point for the leaf */
208286 ** The problem is that in order to update a b-tree, the leaf page (at least)
208289 ** single leaf that is modified more than once as part of the transaction
208298 ** and all but guarantees each modified leaf page is loaded and stored
214257 " pagetype TEXT," /* 3 'internal', 'leaf', 'overflow', or NULL */
214278 u32 iChildPg; /* Child node (or 0 if this is a leaf) */
214561 if( flags==0x0D ){ /* Table leaf node */
214564 }else{ /* Index interior and leaf nodes */
214876 case 0x0D: /* table leaf */
214877 case 0x0A: /* index leaf */
214878 pCsr->zPagetype = "leaf";
221995 ** field that occurs at the start of each leaf page (see fts5_index.c). */
230034 ** * all segment b-tree leaf data is stored in fixed size page records
230051 #define FTS5_OPT_WORK_UNIT 1000 /* Number of leaf pages per optimize step */
230052 #define FTS5_WORK_UNIT 64 /* Number of leaf pages in unit of work */
230095 ** + first leaf page number (often 1, always greater than 0)
230096 ** + final leaf page number
230109 ** Most of each segment leaf is taken up by term/doclist data. The
230111 ** on the leaf page, is:
230152 ** Each leaf page begins with a 4-byte header containing 2 16-bit
230160 ** size of the leaf page in bytes.
230170 ** term/doclist data fits on a single leaf page. If this is not the case,
230187 ** a single leaf record only. The format of each doclist index leaf page
230191 ** 0x01: Clear if leaf is also the root page, otherwise set.
230193 ** * Page number of fts index leaf page. As a varint.
230228 ** The rowid for each segment leaf is found by passing the segment id and
230229 ** the leaf page number to the FTS5_SEGMENT_ROWID macro. Leaves are numbered
230276 int szLeaf; /* Size of leaf without page-index */
230330 int pgnoFirst; /* First leaf page number in segment */
230331 int pgnoLast; /* Last leaf page number in segment */
230352 Fts5Buffer buf; /* Buffer containing leaf data */
230365 i64 iPrevRowid; /* Previous rowid written to current leaf */
230369 u8 bFirstTermInPage; /* True if next term will be first in leaf */
230370 int nLeafWritten; /* Number of leaf pages written */
230395 ** Current leaf page number within segment.
230398 ** Byte offset within the current leaf that is the first byte of the
230402 ** is the last thing on the leaf page.
230405 ** Buffer containing current leaf page data. Set to NULL at EOF.
230436 int iLeafPgno; /* Current leaf page number */
230437 Fts5Data *pLeaf; /* Current leaf data */
230439 i64 iLeafOffset; /* Byte offset within current leaf */
230468 ** leaf page.
230478 ** Argument is a pointer to an Fts5Data structure that contains a leaf
230479 ** page. This macro evaluates to true if the leaf contains no terms, or
230551 int iLeafPgno; /* Page number of current leaf page */
230552 i64 iRowid; /* First rowid on leaf iLeafPgno */
231051 /* TODO: Do we need this if the leaf-index is appended? Probably... */
231585 ** Load the next leaf page into the segment iterator.
232174 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
232256 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
232276 ** function searches the leaf page for a term matching (pTerm/nTerm).
232449 /* This block sets stack variable iPg to the leaf page number that may
232730 ** It is an error if leaf iLeafPgno does not exist or contains no rowids.
233787 /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written
233799 ** last term on leaf page (pWriter->iBtPage) is completed.
233829 ** This is called once for each leaf page except the first that contains
233832 ** smaller than the first term on the new leaf.
233850 ** This function is called when flushing a leaf page that contains no
233857 /* If there were no rowids on the leaf page either and the doclist-index
233879 ** Rowid iRowid has just been appended to the current leaf page. It is the
233898 ** doclist-index leaf page) up into the next level of the b-tree
233977 /* The new leaf holds no terms or rowids */
234003 /* If the current leaf page is full, flush it to disk. */
234025 /* This is the first term on a leaf that is not the leftmost leaf in
234142 int *pnLeaf /* OUT: Number of leaf pages in b-tree */
234198 /* Initialize the 4-byte leaf-page header to 0x00. */
234229 int iOff = pSeg->iTermLeafOffset; /* Offset on new first leaf page */
234302 int nRem = pnRem ? *pnRem : 0; /* Output leaf pages left to write */
234401 /* Flush the last leaf page to disk. Set the output segment b-tree height
234402 ** and last leaf page number at the same time. */
234494 ** A total of nLeaf leaf pages of data has just been flushed to a level-0
234510 int nRem; /* Number of leaf pages left to write */
234582 int pgnoLast = 0; /* Last leaf page number in segment */
234594 Fts5Buffer *pBuf; /* Buffer in which to assemble leaf page */
234625 /* The entire doclist will fit on the current leaf. */
234632 /* The entire doclist will not fit on this leaf. The following
234668 /* The entire poslist will fit on the current leaf. So copy
234672 /* The entire poslist will not fit on this leaf. So it needs
235826 int iLeaf /* Load doclist-index for this leaf */
236024 /* Now check that the iter.nEmpty leaves following the current leaf
236106 i64 iRow; /* Rowid for this leaf */
236107 Fts5Data *pLeaf; /* Data for this leaf */
236114 /* If the leaf in question has already been trimmed from the segment,
236121 /* Check that the leaf contains at least one term, and that it is equal
236123 ** is also a rowid pointer within the leaf page header, it points to a
236128 int iOff; /* Offset of first term on leaf */
236129 int iRowidOff; /* Offset of first rowid on leaf */
236130 int nTerm; /* Size of term on leaf in bytes */
236149 /* Now check that the iter.nEmpty leaves following the current leaf
236169 /* Check any rowid-less pages that occur before the current leaf. */
236180 /* Check that the leaf page indicated by the iterator really does
236212 /* Page iter.iLeaf must now be the rightmost leaf-page in the segment */