Lines Matching refs:leaf
31942 /* only mkdir if leaf dir != "." or "/" or ".." */
41674 ** (b) The page was a freelist leaf page at the start of the transaction.
41708 ** all queries. Note in particular the content of freelist leaf
46874 ** a) When reading a free-list leaf page from the database, and
47547 ** the page has been added as a leaf of the freelist and so its
52147 ** 23 1 Min leaf payload fraction (must be 32)
52183 ** The min leaf payload fraction is like the min embedded payload fraction
52184 ** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
52211 ** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
52218 ** The flags define the format of this btree page. The leaf flag means that
52274 ** 4 Page number of the left child. Omitted if leaf flag is set.
52288 ** Freelist pages come in two subtypes: trunk pages and leaf pages. The
52290 ** page points to multiple leaf pages. The content of a leaf page is
52295 ** 4 Number of leaf pointers on this page
52347 ** walk up the BTree from any leaf to the root. Care must be taken to
52358 u8 intKeyLeaf; /* True if the leaf of an intKey table */
52360 u8 leaf; /* True if a leaf page */
52362 u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */
53562 ** when a page that previously contained data becomes a free-list leaf
53567 ** free-list leaf pages:
53570 ** a free-list leaf page, the page is not written to the database
53571 ** (as free-list leaf pages contain no meaningful data). Sometimes
53575 ** 2) When a free-list leaf page is reused, its content is not read
53589 ** moved to become a free-list leaf page, the corresponding bit is
53590 ** set in the bitvec. Whenever a leaf page is extracted from the free-list,
53613 ** This function is called when a free-list leaf page is removed from the
54048 assert( pPage->leaf==0 || pPage->leaf==1 );
54388 assert( pPage->cellOffset == hdr + 12 - 4*pPage->leaf );
54561 pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 );
54563 pPage->childPtrSize = 4-4*pPage->leaf;
54569 /* EVIDENCE-OF: R-20501-61796 A value of 13 means the page is a leaf
54573 pPage->intKeyLeaf = pPage->leaf;
54574 pPage->noPayload = !pPage->leaf;
54581 /* EVIDENCE-OF: R-16571-11615 A value of 10 means the page is a leaf
54673 if( !pPage->leaf ) iCellLast--;
54687 if( !pPage->leaf ) iCellLast++;
55278 ** inserting them into a leaf page (function fillInCell()). If
55698 ** fractions and the leaf payload fraction values must be 64, 32, and 32.
56095 if( !pPage->leaf ){
56101 if( !pPage->leaf ){
57582 ** Page pParent is an internal (non-leaf) tree page. This function
57703 }else if( !pRoot->leaf ){
57716 ** Move the cursor down to the left-most leaf entry beneath the
57719 ** The left-most leaf is the one with the smallest key - the first
57729 while( rc==SQLITE_OK && !(pPage = pCur->apPage[pCur->iPage])->leaf ){
57738 ** Move the cursor down to the right-most leaf entry beneath the
57754 while( !(pPage = pCur->apPage[pCur->iPage])->leaf ){
57809 assert( pCur->apPage[pCur->iPage]->leaf );
57842 ** left pointing at a leaf page which would hold the entry if it
57956 if( !pPage->leaf ){
58039 assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
58041 if( pPage->leaf ){
58142 if( !pPage->leaf ){
58162 if( pPage->leaf ){
58183 if( pPage->leaf ){
58243 if( !pPage->leaf ){
58262 if( pPage->intKey && !pPage->leaf ){
58280 || pCur->apPage[pCur->iPage]->leaf==0
58401 ** is the number of leaf page pointers to follow. */
58447 ** pointers to free-list leaves. The first leaf becomes a trunk
58485 /* Extract a leaf from the trunk */
58527 TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d"
58687 ** new free-list trunk page. Otherwise, it will become a leaf of the
58689 ** is possible to add the page as a new free-list leaf.
58692 u32 nLeaf; /* Initial number of leaf cells on trunk page */
58708 ** being freed as a new leaf.
58735 TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
58741 ** the page being freed as a leaf page of the first trunk in the free-list.
59126 ** malformed cell from a leaf page to an interior page, if the cell size
59127 ** wanted to be less than 4 but got rounded up to 4 on the leaf, then size
59128 ** might be less than 8 (leaf-size + pointer) on the interior node. Hence
59471 ** Instead of trying to balance the 3 right-most leaf pages, just add
59478 ** pPage is the leaf page which is the right-most page in the tree.
59596 if( !pPage->leaf ){
59602 if( !pPage->leaf ){
59614 ** on page pFrom to page pTo. If page pFrom was not a leaf page, then
59728 u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */
59729 int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
59883 ** If the siblings are on leaf pages, then the child pointers of the
59890 ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf.
59893 leafCorrection = apOld[0]->leaf*4;
59932 if( !pOld->leaf ){
60207 if( !pNew->leaf ){
60210 /* If the tree is a leaf-data tree, and the siblings are leaves,
60223 /* Obscure case for non-leaf-data trees: If the cell at pCell was
60224 ** previously stored on a leaf node, and its reported size was 4
60671 assert( pPage->leaf || !pPage->intKey );
60692 if( !pPage->leaf ){
60699 assert( pPage->leaf );
60702 assert( pPage->leaf );
60777 /* If the page containing the entry to delete is not a leaf page, move
60784 if( !pPage->leaf ){
60810 /* If the cell deleted was not located on a leaf page, then the cursor
60813 ** node. The cell from the leaf node needs to be moved to the internal
60815 if( !pPage->leaf ){
60832 /* Balance the tree. If the entry deleted was located on a leaf page,
60838 ** pCur is pointing to the leaf page from which a cell was removed to
60840 ** tricky as the leaf node may be underfull, and the internal node may
60842 ** on the leaf node first. If the balance proceeds far enough up the
60844 ** been corrected, so be it. Otherwise, after balancing the leaf node,
61053 if( !pPage->leaf ){
61060 if( !pPage->leaf ){
61352 /* If this is a leaf page or the tree is not an int-key tree, then
61357 if( pPage->leaf || !pPage->intKey ){
61361 /* pPage is a leaf node. This loop navigates the cursor so that it
61371 if( pPage->leaf ){
61549 "freelist leaf count too big on page %d", iPage);
61742 if( !pPage->leaf ){
61757 if( !pPage->leaf ){
61769 /* For intKey leaf pages, check that the min/max keys are in order
61774 if( pPage->leaf && pPage->intKey ){
61825 cellStart = hdr + 12 - 4*pPage->leaf;
80209 ** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes.
80229 ** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the
80238 int iSeq, /* Sequence number of leaf within tree */
80240 MergeEngine *pLeaf /* Leaf to add to tree */
132223 **** Segment leaf nodes ****
132224 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
132226 ** iterate through a single leaf node's data) and LeavesReader (to
132227 ** iterate through a segment's entire leaf layer). Leaf nodes have
132230 ** varint iHeight; (height from leaf level, always 0)
132247 ** Leaf nodes are broken into blocks which are stored contiguously in
132252 ** New data is spilled to a new leaf node when the current node
132255 ** node (a leaf node with a single term and doclist). The goal of
132262 ** dynamic. For instance, it may make more sense to have a 2.5k leaf
132272 ** SegmentWriter creates new leaf nodes, or when an interior node
132276 ** varint iHeight; (height from leaf level, always >0)
132318 ** This could be either a leaf node or an interior node. If the top
132328 ** start_block - first leaf node
132329 ** leaves_end_block - last leaf node
132333 ** If the root node is a leaf node, then start_block,
132352 ** leaf nodes are written in to the %_segments table in order, this
132896 u32 nLeafAdd; /* Number of leaf blocks added this trans */
134856 ** node for the range of leaf nodes that may contain the specified term
134860 ** left-most leaf node in the tree that may contain the specified term.
134862 ** right-most leaf node that may contain a term for which the specified
134865 ** It is possible that the range of returned leaf nodes does not contain
134869 ** never loads leaf nodes into memory), it is not possible to be sure.
134879 sqlite3_int64 *piLeaf, /* Selected leaf node */
134880 sqlite3_int64 *piLeaf2 /* Selected leaf node */
136347 ** involves updating the leaf block that contains the smallest unmerged
136348 ** entry and each block (if any) between the leaf and the root node. So
136355 ** is only attempted if it will write at least 64 leaf blocks. Hence
137720 ** of data that will fit on a single leaf page of an intkey table in
140249 /* Set $p to point to the left-most leaf in the tree of eType nodes. */
140255 /* This loop runs once for each leaf in the tree of eType nodes. */
140293 /* If that was the last leaf node, break out of the loop */
140296 /* Set $p to point to the next leaf in the tree of eType nodes */
143081 ** a contiguous set of segment b-tree leaf nodes. Although the details of
143101 sqlite3_int64 iStartBlock; /* Rowid of first leaf block to traverse */
143102 sqlite3_int64 iLeafEndBlock; /* Rowid of final leaf block to traverse */
143104 sqlite3_int64 iCurrentBlock; /* Current leaf block (or 0) */
143155 i64 nLeafData; /* Number of bytes of leaf data written */
143161 ** the leaf nodes). These functions and type are only ever used by code
143298 /* Estimate the upper limit on the number of leaf nodes in a new segment
144295 /* If iCurrentBlock>=iLeafEndBlock, this is an EOF condition. All leaf
144542 sqlite3_int64 iStartLeaf, /* First leaf to traverse */
144543 sqlite3_int64 iEndLeaf, /* Final leaf to traverse */
144891 sqlite3_int64 nLeafData, /* Bytes of leaf data in segment */
145081 sqlite3_int64 iLeaf, /* Block id of first leaf node */
145157 int nReq; /* Number of bytes required on leaf page */
145201 /* The current leaf node is full. Write it out to the database. */
145209 ** a) be greater than the largest term on the leaf node just written
145213 ** leaf node (zTerm/nTerm).
145297 sqlite3_int64 iLastLeaf; /* Largest leaf block id written to db */
145666 ** b-tree leaf nodes contain more than one term.
146217 ** estimate the number of leaf blocks of content to be written
146595 int nLeafEst; /* Space allocated for leaf blocks */
146596 int nWork; /* Number of leaf pages flushed */
146601 sqlite3_int64 nLeafData; /* Bytes of leaf page data so far */
146712 /* Figure out if this is a leaf or an internal node. */
146724 ** This function is called while writing an FTS segment each time a leaf o
146727 ** than or equal to the first key that will be written to the next leaf
146730 ** The block id of the leaf node just written to disk may be found in
146815 ** A node header is a single 0x00 byte for a leaf node, or a height varint
146819 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
146848 ** leaf node, and there must not be a doclist for an internal node. */
146894 int nSpace; /* Total space in bytes required on leaf */
146897 NodeWriter *pLeaf; /* Object used to write leaf nodes */
146917 ** a) be greater than the largest term on the leaf node just written
146921 ** leaf node (zTerm/nTerm).
146980 ** root node. If the segment fits entirely on a single leaf node, iRoot
147005 ** single leaf and a single interior (root) node.
147279 ** maximum number of leaf blocks that may be required is the sum of the
147280 ** number of leaf blocks consumed by the input segments, plus the number
147286 ** array of leaf nodes starts at the first block allocated. The array
147287 ** of interior nodes that are parents of the leaf nodes start at block
147302 int nLeafEst = 0; /* Blocks allocated for leaf nodes */
147451 ** node. The node may be a leaf or an internal node.
147454 ** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
147468 int bLeaf = aNode[0]=='\0'; /* True for a leaf node */
147557 /* Variable iNewStart now contains the first valid leaf node. */
147746 ** Attempt an incremental merge that writes nMerge leaf blocks.
147752 ** write the quota of nMerge leaf blocks.
147756 int nRem = nMerge; /* Number of leaf pages yet to be written */
147918 ** A and B are integers that decode to be the number of leaf pages
151022 ** of 4-byte coordinates. For leaf nodes the integer is the rowid
151100 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
151154 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
151671 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
152001 ** Check the leaf RTree cell given by pCellData against constraint p.
152412 ** Use nodeAcquire() to obtain the leaf node containing the record with
152513 RtreeNode *pLeaf; /* Leaf on which the required cell resides */
152514 RtreeSearchPoint *p; /* Search point for the the leaf */
152817 RtreeNode **ppLeaf /* OUT: Selected leaf page */
153324 ** rowid of the row to delete, which can be used to find the leaf on which
153325 ** the entry resides (argument pLeaf). Once the leaf is located, this
153570 ** subtree iHeight high (leaf nodes have iHeight==0).
153651 RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */
153659 /* Obtain a reference to the leaf node that contains the entry
153666 /* Delete the cell in question from the leaf node. */
155276 " pagetype STRING, /* 'internal', 'leaf' or 'overflow' */" \
155293 u32 iChildPg; /* Child node (or 0 if this is a leaf) */
155506 if( flags==0x0D ){ /* Table leaf node */
155509 }else{ /* Index interior and leaf nodes */
155748 case 0x0D: /* table leaf */
155749 case 0x0A: /* index leaf */
155750 pCsr->zPagetype = "leaf";
