Lines Matching defs:leaf
35848 /* only mkdir if leaf dir != "." or "/" or ".." */
46321 ** (b) The page was a freelist leaf page at the start of the transaction.
46355 ** all queries. Note in particular the content of freelist leaf
51563 ** a) When reading a free-list leaf page from the database, and
52261 ** the page has been added as a leaf of the freelist and so its
57207 ** 23 1 Min leaf payload fraction (must be 32)
57243 ** The min leaf payload fraction is like the min embedded payload fraction
57244 ** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
57271 ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
57278 ** The flags define the format of this btree page. The leaf flag means that
57334 ** 4 Page number of the left child. Omitted if leaf flag is set.
57348 ** Freelist pages come in two subtypes: trunk pages and leaf pages. The
57350 ** page points to multiple leaf pages. The content of a leaf page is
57355 ** 4 Number of leaf pointers on this page
57409 ** walk up the BTree from any leaf to the root. Care must be taken to
57420 u8 intKeyLeaf; /* True if the leaf of an intKey table */
57421 u8 leaf; /* True if a leaf page */
57423 u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */
58662 ** when a page that previously contained data becomes a free-list leaf
58667 ** free-list leaf pages:
58670 ** a free-list leaf page, the page is not written to the database
58671 ** (as free-list leaf pages contain no meaningful data). Sometimes
58675 ** 2) When a free-list leaf page is reused, its content is not read
58689 ** moved to become a free-list leaf page, the corresponding bit is
58690 ** set in the bitvec. Whenever a leaf page is extracted from the free-list,
58713 ** This function is called when a free-list leaf page is removed from the
59210 ** btreeParseCellPtr() => table btree leaf nodes
59224 assert( pPage->leaf==0 );
59245 assert( pPage->leaf==0 || pPage->leaf==1 );
59312 assert( pPage->leaf==0 || pPage->leaf==1 );
59358 ** cellSizePtr() => all index nodes & table leaf nodes
59637 assert( pPage->cellOffset == hdr + 12 - 4*pPage->leaf );
59816 pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 );
59818 pPage->childPtrSize = 4-4*pPage->leaf;
59826 ** leaf table b-tree page. */
59829 if( pPage->leaf ){
59844 ** leaf index b-tree page. */
59936 if( !pPage->leaf ) iCellLast--;
59950 if( !pPage->leaf ) iCellLast++;
60603 ** inserting them into a leaf page (function fillInCell()). If
61036 ** fractions and the leaf payload fraction values must be 64, 32, and 32.
61435 if( !pPage->leaf ){
61441 if( !pPage->leaf ){
62911 ** Page pParent is an internal (non-leaf) tree page. This function
63035 }else if( !pRoot->leaf ){
63048 ** Move the cursor down to the left-most leaf entry beneath the
63051 ** The left-most leaf is the one with the smallest key - the first
63061 while( rc==SQLITE_OK && !(pPage = pCur->apPage[pCur->iPage])->leaf ){
63070 ** Move the cursor down to the right-most leaf entry beneath the
63086 while( !(pPage = pCur->apPage[pCur->iPage])->leaf ){
63141 assert( pCur->apPage[pCur->iPage]->leaf );
63174 ** left pointing at a leaf page which would hold the entry if it
63292 if( !pPage->leaf ){
63388 assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
63390 if( pPage->leaf ){
63491 if( !pPage->leaf ){
63511 if( pPage->leaf ){
63532 if( pPage->leaf ){
63592 if( !pPage->leaf ){
63611 if( pPage->intKey && !pPage->leaf ){
63629 || pCur->apPage[pCur->iPage]->leaf==0
63750 ** is the number of leaf page pointers to follow. */
63796 ** pointers to free-list leaves. The first leaf becomes a trunk
63834 /* Extract a leaf from the trunk */
63876 TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
64030 ** new free-list trunk page. Otherwise, it will become a leaf of the
64032 ** is possible to add the page as a new free-list leaf.
64035 u32 nLeaf; /* Initial number of leaf cells on trunk page */
64051 ** being freed as a new leaf.
64078 TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
64084 ** the page being freed as a leaf page of the first trunk in the free-list.
64458 ** malformed cell from a leaf page to an interior page, if the cell size
64459 ** wanted to be less than 4 but got rounded up to 4 on the leaf, then size
64460 ** might be less than 8 (leaf-size + pointer) on the interior node. Hence
64870 ** Instead of trying to balance the 3 right-most leaf pages, just add
64877 ** pPage is the leaf page which is the right-most page in the tree.
64998 if( !pPage->leaf ){
65004 if( !pPage->leaf ){
65016 ** on page pFrom to page pTo. If page pFrom was not a leaf page, then
65126 u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */
65127 int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
65281 ** If the siblings are on leaf pages, then the child pointers of the
65288 ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf.
65292 leafCorrection = b.pRef->leaf*4;
65302 /* Verify that all sibling pages are of the same "type" (table-leaf,
65303 ** table-interior, index-leaf, or index-interior).
65363 if( !pOld->leaf ){
65680 if( !pNew->leaf ){
65683 /* If the tree is a leaf-data tree, and the siblings are leaves,
65696 /* Obscure case for non-leaf-data trees: If the cell at pCell was
65697 ** previously stored on a leaf node, and its reported size was 4
66152 assert( pPage->leaf || !pPage->intKey );
66173 if( !pPage->leaf ){
66180 assert( pPage->leaf );
66183 assert( pPage->leaf );
66282 if( !pPage->leaf
66294 /* If the page containing the entry to delete is not a leaf page, move
66301 if( !pPage->leaf ){
66329 /* If the cell deleted was not located on a leaf page, then the cursor
66332 ** node. The cell from the leaf node needs to be moved to the internal
66334 if( !pPage->leaf ){
66354 /* Balance the tree. If the entry deleted was located on a leaf page,
66360 ** pCur is pointing to the leaf page from which a cell was removed to
66362 ** tricky as the leaf node may be underfull, and the internal node may
66364 ** on the leaf node first. If the balance proceeds far enough up the
66366 ** been corrected, so be it. Otherwise, after balancing the leaf node,
66592 if( !pPage->leaf ){
66599 if( !pPage->leaf ){
66891 /* If this is a leaf page or the tree is not an int-key tree, then
66896 if( pPage->leaf || !pPage->intKey ){
66900 /* pPage is a leaf node. This loop navigates the cursor so that it
66910 if( pPage->leaf ){
67086 "freelist leaf count too big on page %d", iPage);
67260 cellStart = hdr + 12 - 4*pPage->leaf;
67264 if( !pPage->leaf ){
67276 /* For leaf pages, the coverage check will occur in the same loop
67329 if( !pPage->leaf ){
67344 /* Populate the coverage-checking heap for leaf pages */
67354 /* For leaf pages, the min-heap has already been initialized and the
67357 if( !pPage->leaf ){
86944 ** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes.
86964 ** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the
86973 int iSeq, /* Sequence number of leaf within tree */
140967 **** Segment leaf nodes ****
140968 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
140970 ** iterate through a single leaf node's data) and LeavesReader (to
140971 ** iterate through a segment's entire leaf layer). Leaf nodes have
140974 ** varint iHeight; (height from leaf level, always 0)
140996 ** New data is spilled to a new leaf node when the current node
140999 ** node (a leaf node with a single term and doclist). The goal of
141006 ** dynamic. For instance, it may make more sense to have a 2.5k leaf
141016 ** SegmentWriter creates new leaf nodes, or when an interior node
141020 ** varint iHeight; (height from leaf level, always >0)
141062 ** This could be either a leaf node or an interior node. If the top
141072 ** start_block - first leaf node
141073 ** leaves_end_block - last leaf node
141077 ** If the root node is a leaf node, then start_block,
141096 ** leaf nodes are written in to the %_segments table in order, this
141651 u32 nLeafAdd; /* Number of leaf blocks added this trans */
143632 ** node for the range of leaf nodes that may contain the specified term
143636 ** left-most leaf node in the tree that may contain the specified term.
143638 ** right-most leaf node that may contain a term for which the specified
143641 ** It is possible that the range of returned leaf nodes does not contain
143645 ** never loads leaf nodes into memory), it is not possible to be sure.
143655 sqlite3_int64 *piLeaf, /* Selected leaf node */
143656 sqlite3_int64 *piLeaf2 /* Selected leaf node */
145123 ** involves updating the leaf block that contains the smallest unmerged
145124 ** entry and each block (if any) between the leaf and the root node. So
145131 ** is only attempted if it will write at least 64 leaf blocks. Hence
146496 ** of data that will fit on a single leaf page of an intkey table in
149043 /* Set $p to point to the left-most leaf in the tree of eType nodes. */
149049 /* This loop runs once for each leaf in the tree of eType nodes. */
149087 /* If that was the last leaf node, break out of the loop */
149090 /* Set $p to point to the next leaf in the tree of eType nodes */
151931 ** a contiguous set of segment b-tree leaf nodes. Although the details of
151951 sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */
151952 sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */
151954 sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */
152005 i64 nLeafData; /* Number of bytes of leaf data written */
152011 ** the leaf nodes). These functions and type are only ever used by code
152149 /* Estimate the upper limit on the number of leaf nodes in a new segment
153156 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
153405 sqlite3_int64 iStartLeaf, /* First leaf to traverse */
153406 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
153754 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */
153944 sqlite3_int64 iLeaf, /* Block id of first leaf node */
154020 int nReq; /* Number of bytes required on leaf page */
154064 /* The current leaf node is full. Write it out to the database. */
154072 ** a) be greater than the largest term on the leaf node just written
154076 ** leaf node (zTerm/nTerm).
154160 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
154529 ** b-tree leaf nodes contain more than one term.
155080 ** estimate the number of leaf blocks of content to be written
155458 int nLeafEst; /* Space allocated for leaf blocks */
155459 int nWork; /* Number of leaf pages flushed */
155464 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */
155575 /* Figure out if this is a leaf or an internal node. */
155587 ** This function is called while writing an FTS segment each time a leaf o
155590 ** than or equal to the first key that will be written to the next leaf
155593 ** The block id of the leaf node just written to disk may be found in
155678 ** A node header is a single 0x00 byte for a leaf node, or a height varint
155682 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
155711 ** leaf node, and there must not be a doclist for an internal node. */
155757 int nSpace; /* Total space in bytes required on leaf */
155760 NodeWriter *pLeaf; /* Object used to write leaf nodes */
155780 ** a) be greater than the largest term on the leaf node just written
155784 ** leaf node (zTerm/nTerm).
155843 ** root node. If the segment fits entirely on a single leaf node, iRoot
155868 ** single leaf and a single interior (root) node.
156142 ** maximum number of leaf blocks that may be required is the sum of the
156143 ** number of leaf blocks consumed by the input segments, plus the number
156149 ** array of leaf nodes starts at the first block allocated. The array
156150 ** of interior nodes that are parents of the leaf nodes start at block
156165 int nLeafEst = 0; /* Blocks allocated for leaf nodes */
156314 ** node. The node may be a leaf or an internal node.
156317 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
156331 int bLeaf = aNode[0]=='\0'; /* True for a leaf node */
156420 /* Variable iNewStart now contains the first valid leaf node. */
156609 ** Attempt an incremental merge that writes nMerge leaf blocks.
156615 ** write the quota of nMerge leaf blocks.
156619 int nRem = nMerge; /* Number of leaf pages yet to be written */
156782 ** A and B are integers that decode to be the number of leaf pages
160013 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
160093 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
160147 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
160665 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
160995 ** Check the leaf RTree cell given by pCellData against constraint p.
161406 ** Use nodeAcquire() to obtain the leaf node containing the record with
161508 RtreeSearchPoint *p; /* Search point for the the leaf */
161824 RtreeNode **ppLeaf /* OUT: Selected leaf page */
162331 ** rowid of the row to delete, which can be used to find the leaf on which
162332 ** the entry resides (argument pLeaf). Once the leaf is located, this
162577 ** subtree iHeight high (leaf nodes have iHeight==0).
162666 /* Obtain a reference to the leaf node that contains the entry
162673 /* Delete the cell in question from the leaf node. */
164460 ** The problem is that in order to update a b-tree, the leaf page (at least)
164463 ** single leaf that is modified more than once as part of the transaction
164472 ** and all but guarantees each modified leaf page is loaded and stored
169703 " pagetype TEXT, /* 'internal', 'leaf' or 'overflow' */" \
169721 u32 iChildPg; /* Child node (or 0 if this is a leaf) */
169942 if( flags==0x0D ){ /* Table leaf node */
169945 }else{ /* Index interior and leaf nodes */
170184 case 0x0D: /* table leaf */
170185 case 0x0A: /* index leaf */
170186 pCsr->zPagetype = "leaf";
177847 ** field that occurs at the start of each leaf page (see fts5_index.c). */
184973 ** * all segment b-tree leaf data is stored in fixed size page records
184990 #define FTS5_OPT_WORK_UNIT 1000 /* Number of leaf pages per optimize step */
184991 #define FTS5_WORK_UNIT 64 /* Number of leaf pages in unit of work */
185034 ** + first leaf page number (often 1, always greater than 0)
185035 ** + final leaf page number
185048 ** Most of each segment leaf is taken up by term/doclist data. The
185050 ** on the leaf page, is:
185091 ** Each leaf page begins with a 4-byte header containing 2 16-bit
185099 ** size of the leaf page in bytes.
185109 ** term/doclist data fits on a single leaf page. If this is not the case,
185126 ** a single leaf record only. The format of each doclist index leaf page
185130 ** 0x01: Clear if leaf is also the root page, otherwise set.
185132 ** * Page number of fts index leaf page. As a varint.
185167 ** The rowid for each segment leaf is found by passing the segment id and
185168 ** the leaf page number to the FTS5_SEGMENT_ROWID macro. Leaves are numbered
185220 int szLeaf; /* Size of leaf without page-index */
185274 int pgnoFirst; /* First leaf page number in segment */
185275 int pgnoLast; /* Last leaf page number in segment */
185296 Fts5Buffer buf; /* Buffer containing leaf data */
185309 i64 iPrevRowid; /* Previous rowid written to current leaf */
185313 u8 bFirstTermInPage; /* True if next term will be first in leaf */
185314 int nLeafWritten; /* Number of leaf pages written */
185339 ** Current leaf page number within segment.
185342 ** Byte offset within the current leaf that is the first byte of the
185346 ** is the last thing on the leaf page.
185349 ** Buffer containing current leaf page data. Set to NULL at EOF.
185380 int iLeafPgno; /* Current leaf page number */
185381 Fts5Data *pLeaf; /* Current leaf data */
185383 int iLeafOffset; /* Byte offset within current leaf */
185412 ** leaf page.
185422 ** Argument is a pointer to an Fts5Data structure that contains a leaf
185423 ** page. This macro evaluates to true if the leaf contains no terms, or
185496 int iLeafPgno; /* Page number of current leaf page */
185497 i64 iRowid; /* First rowid on leaf iLeafPgno */
185918 /* TODO: Do we need this if the leaf-index is appended? Probably... */
186452 ** Load the next leaf page into the segment iterator.
187040 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
187119 Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */
187139 ** function searches the leaf page for a term matching (pTerm/nTerm).
187304 /* This block sets stack variable iPg to the leaf page number that may
187575 ** It is an error if leaf iLeafPgno does not exist or contains no rowids.
188604 /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written
188616 ** last term on leaf page (pWriter->iBtPage) is completed.
188645 ** This is called once for each leaf page except the first that contains
188648 ** smaller than the first term on the new leaf.
188664 ** This function is called when flushing a leaf page that contains no
188671 /* If there were no rowids on the leaf page either and the doclist-index
188693 ** Rowid iRowid has just been appended to the current leaf page. It is the
188712 ** doclist-index leaf page) up into the next level of the b-tree
188794 /* The new leaf holds no terms or rowids */
188819 /* If the current leaf page is full, flush it to disk. */
188840 /* This is the first term on a leaf that is not the leftmost leaf in
188954 int *pnLeaf /* OUT: Number of leaf pages in b-tree */
189010 /* Initialize the 4-byte leaf-page header to 0x00. */
189041 int iOff = pSeg->iTermLeafOffset; /* Offset on new first leaf page */
189105 int nRem = pnRem ? *pnRem : 0; /* Output leaf pages left to write */
189199 /* Flush the last leaf page to disk. Set the output segment b-tree height
189200 ** and last leaf page number at the same time. */
189291 ** A total of nLeaf leaf pages of data has just been flushed to a level-0
189307 int nRem; /* Number of leaf pages left to write */
189379 int pgnoLast = 0; /* Last leaf page number in segment */
189391 Fts5Buffer *pBuf; /* Buffer in which to assemble leaf page */
189421 /* The entire doclist will fit on the current leaf. */
189428 /* The entire doclist will not fit on this leaf. The following
189463 /* The entire poslist will fit on the current leaf. So copy
189467 /* The entire poslist will not fit on this leaf. So it needs
190493 int iLeaf /* Load doclist-index for this leaf */
190654 /* Now check that the iter.nEmpty leaves following the current leaf
190735 i64 iRow; /* Rowid for this leaf */
190736 Fts5Data *pLeaf; /* Data for this leaf */
190743 /* If the leaf in question has already been trimmed from the segment,
190750 /* Check that the leaf contains at least one term, and that it is equal
190752 ** is also a rowid pointer within the leaf page header, it points to a
190757 int iOff; /* Offset of first term on leaf */
190758 int iRowidOff; /* Offset of first rowid on leaf */
190759 int nTerm; /* Size of term on leaf in bytes */
190778 /* Now check that the iter.nEmpty leaves following the current leaf
190798 /* Check any rowid-less pages that occur before the current leaf. */
190809 /* Check that the leaf page indicated by the iterator really does
190841 /* Page iter.iLeaf must now be the rightmost leaf-page in the segment */