Lines Matching defs:tree
142 ** The maximum depth of an expression tree. This is limited to
657 ** hash of the entire source tree.
3289 ** <dd>The maximum depth of the parse tree on any expression.</dd>)^
7964 sqlite3_vfs *pVfs, /* VFS to use with this b-tree */
7981 #define BTREE_SINGLE 8 /* The file contains at most 1 b-tree */
10228 ** Each node of an expression in the parse tree is an instance
10235 ** tree.
10329 int nHeight; /* Height of the tree headed by this node */
10420 ** the parse tree for an expression and the span of input text for an
10424 Expr *pExpr; /* The expression parse tree */
10908 int nHeight; /* Expression tree height of current sub-select */
11035 ** routines as they walk the parse tree to make database references
11115 ** Context pointer passed down through the tree-walk.
11135 ** Return code from the parse-tree walking primitives and their
11140 #define WRC_Abort 2 /* Abandon the tree walk */
37095 struct RowSetEntry *pTree; /* Binary tree of entries */
37256 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
37257 ** Convert this tree into a linked list connected by the pRight pointers
37261 struct RowSetEntry *pIn, /* Root of the input tree */
37284 ** tree with depth of iDepth. A depth of 1 means the tree contains a single
37285 ** node taken from the head of *ppList. A depth of 2 means a tree with
37290 ** list contains too few elements, then construct an incomplete tree
37293 ** Return a pointer to the root of the constructed binary tree.
37299 struct RowSetEntry *p; /* Root of the new tree */
37322 ** Convert a sorted list of elements into a binary tree. Make the tree
37326 int iDepth; /* Depth of the tree so far */
37327 struct RowSetEntry *p; /* Current tree root */
37346 ** sorted already. If there is a binary tree on p->pTree, then
37857 ** In other cases, the error is returned to the b-tree layer. The b-tree
37863 ** code were simply returned to the user, the b-tree layer would not
39781 ** problem. When the page is next fetched by the b-tree layer, it
42242 /* This routine is only called from b-tree and only when there are no
47376 ** disk where M is the number of entries in the tree.
47434 ** B-tree (non-LEAFDATA) tables. A value of 255 means 100%. The default
47444 ** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
47445 ** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
47798 u16 nSize; /* Size of the cell content on the main b-tree page */
47807 ** If a tree that appears to be taller than this is encountered, it is
47814 ** b-tree within a database file.
47831 Pgno pgnoRoot; /* The root page of this tree */
47969 BtShared *pBt; /* The tree being checked out */
48382 Pgno iRoot, /* Root page of b-tree */
48383 int isIndex, /* True if iRoot is the root of an index b-tree */
48410 ** b-trees, this is just the root page of the b-tree being read or
48568 /* This function should only be called on a sharable b-tree after it
48569 ** has been determined that no other b-tree holds a conflicting lock. */
49961 sqlite3_vfs *pVfs, /* VFS to use for this b-tree */
51437 ** is non-zero then this b-tree transaction is part of a multi-file
51441 ** reset the b-tree objects internal state to indicate that the write
51700 ** root page of a b-tree. If it is not, then the cursor acquired
51713 BtShared *pBt = p->pBt; /* Shared b-tree handle */
51719 ** b-tree database, the connection is holding the required table locks,
52334 ** b-tree page. Write the number of available bytes into *pAmt.
52402 ** Page pParent is an internal (non-leaf) tree page. This function
52445 ** Move the cursor to point to the root page of its b-tree structure.
52452 ** If the b-tree structure is empty, the cursor state is set to
52459 ** kind of b-tree page (i.e. if when opening the cursor the caller did not
52461 ** indicating a table b-tree, or if the caller did specify a KeyInfo
52463 ** b-tree).
52501 ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is
52502 ** NULL, the caller expects a table b-tree. If this is not the case,
52626 ** to the last entry in the b-tree. */
52732 ** be the right kind (index or table) of b-tree page. Otherwise
52772 ** stored entirely within the b-tree page by inspecting the first
52779 ** b-tree page. */
52785 ** fits entirely on the main b-tree page. */
53870 ** tree, in other words, when the new entry will become the largest
53871 ** entry in the tree.
53875 ** that page. This leaves the right side of the tree somewhat
53880 ** pPage is the leaf page which is the right-most page in the tree.
54014 ** This function is used to copy the contents of the b-tree node stored
54045 /* Copy the b-tree node content from page pFrom to page pTo. */
54063 ** for any b-tree or overflow pages that pTo now contains the pointers to.
54126 int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
54535 /* If the tree is a leaf-data tree, and the siblings are leaves,
54584 /* The root page of the b-tree now contains no cells. The only sibling
54587 ** b-tree structure by one. This is described as the "balance-shallower"
54648 ** intkey b-tree, then cell i was a divider cell. */
54671 ** intkey b-tree, then cell i is a divider cell. */
54730 ** This function is called when the root page of a b-tree structure is
54757 /* Make pRoot, the root page of the b-tree, writable. Allocate a new
54795 ** tree needs to be balanced, and if so calls the appropriate balancing
54817 /* The root page of the b-tree is overfull. In this case call the
54965 ** expecting an index b-tree, then the caller should be inserting blob
54971 /* If this is an insert into a table b-tree, invalidate any incrblob
55038 ** to redistribute the cells within the tree. Since balance() may move
55049 ** multiple records into an intkey b-tree using a single cursor (as can
55052 ** the b-tree if possible. If the cursor is left pointing to the last
55101 /* If this is a delete operation to remove a row from a table b-tree,
55113 ** the cursor to the largest entry in the tree that is smaller than
55117 ** sub-tree headed by the child page of the cell being deleted. This makes
55118 ** balancing the tree following the delete operation easier. */
55139 ** is currently pointing to the largest entry in the sub-tree headed
55162 /* Balance the tree. If the entry deleted was located on a leaf page,
55164 ** call to balance() repairs the tree, and the if(...) condition is
55173 ** tree that we can be sure that any problem in the internal node has
55175 ** walk the cursor up the tree to the internal node and balance it as
55414 ** is the root of a table b-tree - if it is not, the following call is
55559 ** This function may only be called if the b-tree connection already
55621 ** The first argument, pCur, is a cursor opened on some b-tree. Count the
55622 ** number of entries in the b-tree and write the result to *pnEntry.
55643 MemPage *pPage; /* Current page of the b-tree */
55645 /* If this is a leaf page or the tree is not an int-key tree, then
55656 ** the next page in the tree that has not yet been visited. The
55661 ** If all pages in the tree have been visited, return SQLITE_OK to the
55667 /* All pages of the b-tree have been visited. Return successfully. */
55858 ** Do various sanity checks on a single page of a tree. Return
55859 ** the tree depth. Root pages return 0. Parents of root pages
55873 ** the root of the tree.
55930 "On tree page %d cell %d: ", iPage, i);
56154 checkTreePage(&sCheck, aRoot[i], "List of tree roots: ", NULL, NULL);
56474 Btree *pDest; /* Destination b-tree file */
56480 Btree *pSrc; /* Source b-tree file */
56769 ** Copy nPage pages from the source b-tree to the destination.
67181 ** Cursor P1 is open on an index b-tree - that is to say, a btree which
68061 ** P3 is a flag that provides a hint to the b-tree layer that this
69845 ** the b-tree cursor associated with blob handle p to point to row iRow.
69856 ** If an error does occur, then the b-tree cursor is closed. All subsequent
69929 ** of writing code to use the b-tree layer directly is that the
69934 ** Code external to the Vdbe then "borrows" the b-tree cursor and
69939 ** which closes the b-tree cursor and (possibly) commits the
70361 ** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree.
70615 ** multiple b-tree segments. Parameter iOut is the index of the aTree[]
70984 /* Write the current b-tree to a PMA. Close the b-tree cursor. */
71675 ** This file contains routines used for walking the parser tree for
71683 ** Walk an expression tree. Invoke the callback once for each node
71690 ** WRC_Continue Continue descending down the tree.
71698 ** The return value from this routine is WRC_Abort to abandon the tree walk
71756 ** and on any subqueries further down in the tree. Return
71814 ** This file contains routines used for walking the parser tree and
72232 ** node in the expression tree. Return 0 to continue the search down
72233 ** the tree or 2 to abort the tree walk.
72907 ** This routine walks an expression tree and resolves references to
72936 ** tree. For example, in:
73292 "Expression tree is too large (maximum depth %d)", mxHeight
73301 ** of any expression tree referenced by the structure passed as the
73366 ** Return the maximum height of any expression tree referenced
73634 ** Recursively delete an expression tree.
73670 ** to store a copy of an expression or expression tree. They differ in
73671 ** how much of the tree is measured.
73698 ** to reduce a pristine expression tree from the parser. The implementation
73743 ** space to duplicate all Expr nodes in the tree formed by Expr.pLeft
74184 ** Walk an expression tree. Return 1 if the expression is constant
74196 ** Walk an expression tree. Return 1 if the expression is constant
74206 ** Walk an expression tree. Return 1 if the expression is constant
74397 ** It's job is to find or create a b-tree structure that may be used
74401 ** The index of the cursor opened on the b-tree (database table, database index
74403 ** The returned value of this function indicates the b-tree type, as follows:
74410 ** An existing b-tree may only be used if the SELECT is of the simple
74415 ** If the prNotFound parameter is 0, then the b-tree will be used to iterate
74421 ** If the prNotFound parameter is not 0, then the b-tree will be used
74426 ** When the b-tree is being used for membership tests, the calling function
74533 /* Could not found an existing table or index to use as the RHS b-tree.
74858 /* In this case, the RHS is the ROWID of table b-tree
74863 /* In this case, the RHS is an index b-tree.
76548 ** This is the xExprCallback for a tree walker. It is used to
77840 ** the index b-tree. */
78769 ** The following set of routines walk through the parse tree and assign
83522 ** Generate an expression tree to implement the WHERE, ORDER BY,
83543 Select *pSelect = NULL; /* Complete SELECT tree */
83562 /* Generate a select expression tree to enforce the limit/offset
83576 /* duplicate the FROM clause as it is needed by both the DELETE/UPDATE tree
83584 /* generate the SELECT expression tree. */
88143 ** the triggers and remove both the table and index b-tree entries.
88147 ** GenerateRowIndexDelete(). This removes the index b-tree entries
88148 ** only. The table b-tree entry will be replaced by the new entry
90048 ** backed temporary databases, 2 for the Red-Black tree in memory database
91094 /* Do the b-tree integrity checks */
91706 ** on the b-tree database, open one now. If a transaction is opened, it
91945 ** on the b-tree database, open one now. If a transaction is opened, it
95749 ** No-op routine for the parse-tree walker.
95755 ** subquery in the parser tree.
96160 ** tree refered to by this, the parent select. The child select
96691 const int iCsr = pParse->nTab++; /* Cursor to scan b-tree */
96695 int iRoot = pTab->tnum; /* Root page of scanned b-tree */
96704 ** In this case set iRoot to the root page number of the index b-tree
99465 ** shared b-tree databases opened using connection db are held by the
100771 ** This routine walks (recursively) an expression tree and generates
100773 ** tree.
103343 ** two queries requires table b-tree lookups in order to find the value
110804 ** at the b-tree/pager level.
111603 ** associated with the specific b-tree being checkpointed is taken by
113459 /* The full-text index is stored in a series of b+tree (-like)
113632 ** interior nodes and making the tree too skinny. The interior nodes
113640 ** segment's tree.
113642 ** The root node is the top node of the segment's tree after encoding
114080 ** It is possible to determine which index a b+-tree belongs to based on the
114082 ** that the b+-tree belongs to is (L<<10). In other words, all b+-trees with
114333 ** A tree of these objects forms the RHS of a MATCH operator.
115573 ** a b-tree for a term or term prefix. The node data is passed to this
115578 ** of the child node that heads the sub-tree that may contain the term.
115581 ** that heads a sub-tree that may contain a term for which zTerm/nTerm is
115603 ** interior node. Then load the blockid of the left-child of the b-tree
115655 ** to the term from the interior node, then all terms on the sub-tree
115660 ** the tree headed by iChild may contain the specified term.
115687 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
115688 ** contains a term. This function searches the sub-tree headed by the zNode
115693 ** left-most leaf node in the tree that may contain the specified term.
115716 int iHeight; /* Height of this node in tree */
117513 ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple
117515 ** within the union of all segments of a b-tree. Hence the name.
117518 ** segment b-tree (if the term is not a prefix or it is a prefix for which
117519 ** there exists prefix b-tree of the right length) then it may be traversed
118509 ** which is represented in tree form as:
120067 ** expression tree being parsed. pPrev is the expression node most recently
120068 ** inserted into the tree. This function adds pNew, which is always a binary
120069 ** operator node, into the expression tree based on the relative precedence
120070 ** of pNew and the existing nodes of the tree. This may result in the head
120071 ** of the tree changing, in which case *ppHead is set to the new root node.
120074 Fts3Expr **ppHead, /* Pointer to the root node of a tree */
120075 Fts3Expr *pPrev, /* Node most recently inserted into the tree */
120076 Fts3Expr *pNew /* New binary node to insert into expression tree */
120245 ** query expression and create a tree of Fts3Expr structures representing the
120247 ** of the parsed expression tree and SQLITE_OK is returned. If an error
122275 ** tables. It also contains code to merge FTS3 b-tree segments. Some
122299 ** Under certain circumstances, b-tree nodes (doclists) can be loaded into
122305 ** Incremental loading is used for b-tree nodes FTS3_NODE_CHUNK_THRESHOLD
122355 ** a contiguous set of segment b-tree leaf nodes. Although the details of
122408 ** An instance of this structure is used to create a segment b-tree in the
122417 SegmentNode *pTree; /* Pointer to interior tree structure */
122431 ** the interior part of the segment b+-tree structures (everything except
122439 ** When a b+tree is written to the database (either as a result of a merge
122442 ** the tree is assembled in memory and written out only once all leaves have
122443 ** been populated and stored. This is Ok, as the b+-tree fanout is usually
122444 ** very large, meaning that the interior of the tree consumes relatively
123431 ** b-tree node. And that the final byte of the doclist is 0x00. If either
124059 ** If this is the first node in the tree, the term is added to it.
124126 int iHeight, /* Height of this node in tree */
124136 /* Root node of the tree. */
124165 ** Free all memory allocations associated with the tree pTree.
124251 /* Add the current term to the interior node tree. The term added to
124252 ** the interior tree must:
124354 /* The entire tree fits on the root node. Write it to the segdir table. */
124635 ** b-tree leaf nodes contain more than one term.
125691 ** are part of a sub-tree that is the right-hand-side of a NOT operator.
127043 ** This file contains code for implementations of the r-tree and r*-tree
127051 ** The data structure for a single virtual r-tree table is stored in three
127053 ** in the table name is replaced with the user-supplied name of the r-tree
127060 ** The data for each node of the r-tree structure is stored in the %_node
127061 ** table. For each node that is not the root node of the r-tree, there is
127067 ** The root node of an r-tree always exists, even if the r-tree table is
127073 ** of the node contain the tree depth as a big-endian integer.
127090 ** of the r-tree algorithm. See the README file for further details. The
127097 ** r*tree variant algorithms.
127178 int iDepth; /* Current depth of the r-tree structure */
127179 char *zDb; /* Name of database containing r-tree table */
127180 char *zName; /* Name of r-tree table */
127186 ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
127220 ** If an R*-tree "Reinsert" operation is required, the same number of
127221 ** cells are removed from the overfull node and reinserted into the tree.
127231 ** 2^40 is greater than 2^64, an r-tree structure always has a depth of
127315 ** r-tree query.
127470 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
127490 ** Obtain a reference to an r-tree node.
127494 Rtree *pRtree, /* R-tree structure */
127541 ** of the r-tree structure. A height of zero means all data is stored on
127544 ** is greater than RTREE_MAX_DEPTH, the r-tree structure must be corrupt.
127767 ** Increment the r-tree reference count.
127774 ** Decrement the r-tree reference count. When the reference count reaches
127890 ** The r-tree constraint passed as the second argument to this function is
127914 ** Set *pbEof to true if the sub-tree headed by the cell is filtered
128015 ** Cursor pCursor currently points at a node that heads a sub-tree of
128017 ** to point to the left-most cell of the sub-tree that matches the
128290 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
128357 ** 2 See below R-tree query or full-table scan.
128582 ** ChooseSubTree in r*tree terminology.
128587 int iHeight, /* Height of sub-tree rooted at pCell */
129016 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
129118 ** Implementation of the regular R-tree SplitNode from Guttman[1984].
129327 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
129443 ** cell, adjust the r-tree data structure if required.
129458 /* If the node is not the tree root and now has less than the minimum
129459 ** number of cells, remove it from the tree. Otherwise, update the
129556 ** the height of the sub-tree headed by the cell.
129629 ** the height of the sub-tree headed by the cell.
129645 ** Select a currently unused rowid for a new r-tree record.
129658 ** Remove the entry with rowid=iDelete from the r-tree structure.
129699 ** reduce the tree height by one.
129722 /* Re-insert the contents of any underfull nodes removed from the tree. */
129758 /* Constraint handling. A write operation on an r-tree table may return
129819 ** record to delete from the r-tree table. The following block does
129828 ** the r-tree structure.
129831 /* Insert the new record into the r-tree */
130008 ** the root node of the tree.
130046 ** methods of the r-tree virtual table.
130105 ** the r-tree table schema.
130143 ** Implementation of a scalar function that decodes r-tree nodes to
130147 ** an r-tree node, and the number of dimensions the r-tree indexes.
130148 ** For a two-dimensional r-tree structure called "rt", to deserialize
130154 ** entry for each cell in the r-tree node. Each entry is itself a
130161 Rtree tree;
130166 memset(&tree, 0, sizeof(Rtree));
130167 tree.nDim = sqlite3_value_int(apArg[0]);
130168 tree.nBytesPerCell = 8 + 8 * tree.nDim;
130177 nodeGetCell(&tree, &node, ii, &cell);
130180 for(jj=0; jj<tree.nDim*2; jj++){
130210 ** Register the r-tree module with database handle db. This creates the
130249 ** The scalar user functions return a blob that is interpreted by r-tree
130275 ** Register a new geometry function for use with the r-tree MATCH operator.