Lines Matching defs:node
7584 sqlite3_rtree_dbl *aCoord; /* Coordinates of node or entry to check */
7587 int iLevel; /* Level of current node or entry */
7590 sqlite3_rtree_dbl rParentScore; /* Score of parent node */
7591 int eParentWithin; /* Visibility of parent node */
10949 int tnum; /* Root BTree node for this table (see note above) */
11233 ** code for that node.
11287 ** Each node of an expression in the parse tree is an instance
11350 u8 op; /* Operation performed by this node */
11376 int nHeight; /* Height of the tree headed by this node */
11415 #define EP_Constant 0x080000 /* Node is a constant */
24224 typedef struct unixInodeInfo unixInodeInfo; /* An i-node */
28283 unixInodeInfo *pInode; /* unixInodeInfo that owns this SHM node */
39918 ** node taken from the head of *ppList. A depth of 2 means a tree with
51068 ** root-node and 3 for all other internal nodes.
57291 ** might be less than 8 (leaf-size + pointer) on the interior node. Hence
57549 ** This function is used to copy the contents of the b-tree node stored
57580 /* Copy the b-tree node content from page pFrom to page pTo. */
57639 ** size of a cell stored within an internal node is always less than 1/4
58099 ** previously stored on a leaf node, and its reported size was 4
58314 ** of the node stored on pRoot into the new child page.
58652 int iCellDepth; /* Depth of node containing pCell */
58675 ** from the internal node. The 'previous' entry is used for this instead
58708 ** node. The cell from the leaf node needs to be moved to the internal
58709 ** node to replace the deleted cell. */
58734 ** Otherwise, if the entry deleted was on an internal node page, then
58736 ** replace the cell deleted from the internal node. This is slightly
58737 ** tricky as the leaf node may be underfull, and the internal node may
58739 ** on the leaf node first. If the balance proceeds far enough up the
58740 ** tree that we can be sure that any problem in the internal node has
58741 ** been corrected, so be it. Otherwise, after balancing the leaf node,
58742 ** walk the cursor up the tree to the internal node and balance it as
59229 int iIdx; /* Index of child node in parent */
59241 /* pPage is a leaf node. This loop navigates the cursor so that it
59265 /* Descend to the child node of the cell that the cursor currently
76632 ** Walk an expression tree. Invoke the callback once for each node
76790 ** depth (the Expr.op2 field) by N on every TK_AGG_FUNCTION node.
76791 ** This needs to occur when copying a TK_AGG_FUNCTION node from an
76955 ** expression node refer back to that source column. The following changes
76985 Expr *pExpr /* Make this EXPR node point to the selected column */
77004 /* Initialize the node to no-match */
77361 ** node in the expression tree. Return 0 to continue the search down
78085 ** The node at the root of the subtree is modified as follows:
78289 ** sequence named by pToken. Return a pointer to a new Expr node that
78623 ** Construct a new expression node and return a pointer to it. Memory
78624 ** for this node and for the pToken argument is a single allocation
78626 ** is responsible for making sure the node eventually gets freed.
78632 ** then the EP_DblQuoted flag is set on the expression node.
78686 ** Allocate a new expression node from a zero-terminated token that has
78701 ** Attach subtrees pLeft and pRight to the Expr node pRoot.
78730 ** Allocate a Expr node which joins as many as two subtrees.
78733 ** Expr node. Or, if an OOM error occurs, set pParse->db->mallocFailed,
78809 ** Construct a new expression node for a function with multiple
80692 ** Convert an expression node to a TK_REGISTER
80720 Expr tempX; /* Temporary expression node */
85293 ** This only applies to the root node of pExpr, so the statement:
105666 ** are walked without any actions being taken at each node. Presumably,
110617 ** Think of each WhereLoop object as a node in a graph with arcs
117529 /* This routine constructs a binary expression node out of two ExprSpan
117544 /* Construct an expression node for a unary postfix operator
117547 ExprSpan *pOut, /* Write the new expression node here */
117569 /* Construct an expression node for a unary prefix operator
117572 ExprSpan *pOut, /* Write the new expression node here */
126077 ** iterate through a single leaf node's data) and LeavesReader (to
126100 ** of a node is reached, the next term is in the node with the next
126101 ** greater node id.
126103 ** New data is spilled to a new leaf node when the current node
126106 ** node (a leaf node with a single term and doclist). The goal of
126114 ** node rather than splitting into 2k and .5k nodes. My intuition is
126123 ** SegmentWriter creates new leaf nodes, or when an interior node
126128 ** varint iBlockid; (block id of node's leftmost subtree)
126143 ** An interior node encodes n terms separating n+1 subtrees. The
126154 ** New data is spilled to a new interior node at the same height when
126155 ** the current node exceeds INTERIOR_MAX bytes (default 2048).
126164 ** merging and deleting segments, and also the root node of the
126167 ** The root node is the top node of the segment's tree after encoding
126169 ** This could be either a leaf node or an interior node. If the top
126170 ** node requires more than ROOT_MAX bytes, it is flushed to %_segments
126171 ** and a new root interior node is generated (which should always fit
126179 ** start_block - first leaf node
126180 ** leaves_end_block - last leaf node
126182 ** root - contents of root node
126184 ** If the root node is a leaf node, then start_block,
126752 int nNodeSize; /* Soft limit for node size */
126933 ** when the expression node is.
128545 ** This function is used to process a single interior node when searching
128546 ** a b-tree for a term or term prefix. The node data is passed to this
128551 ** of the child node that heads the sub-tree that may contain the term.
128553 ** If piLast is not NULL, then *piLast is set to the right-most child node
128562 const char *zNode, /* Buffer containing segment interior node */
128564 sqlite3_int64 *piFirst, /* OUT: Selected child node */
128565 sqlite3_int64 *piLast /* OUT: Selected child node */
128568 const char *zCsr = zNode; /* Cursor to iterate through node */
128569 const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
128573 sqlite3_int64 iChild; /* Block id of child node to descend to */
128576 ** interior node. Then load the blockid of the left-child of the b-tree
128577 ** node into variable iChild.
128581 ** root node, then the buffer comes from a SELECT statement. SQLite does
128584 ** contents, or two zero bytes. Or, if the node
128600 /* Load the next term on the node into zBuffer. Use realloc() to expand
128628 ** the interior node. If the specified term is greater than or equal
128629 ** to the term from the interior node, then all terms on the sub-tree
128630 ** headed by node iChild are smaller than zTerm. No need to search
128633 ** If the interior node term is larger than the specified term, then
128661 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
128663 ** node for the range of leaf nodes that may contain the specified term
128667 ** left-most leaf node in the tree that may contain the specified term.
128669 ** right-most leaf node that may contain a term for which the specified
128684 const char *zNode, /* Buffer containing segment interior node */
128686 sqlite3_int64 *piLeaf, /* Selected leaf node */
128687 sqlite3_int64 *piLeaf2 /* Selected leaf node */
128690 int iHeight; /* Height of this node in tree */
129619 ** root node, the range of leaves scanned can be reduced. Do this. */
130120 ** entry and each block (if any) between the leaf and the root node. So
131520 node pRoot. See comments above the definition
131529 Fts3Expr *pRoot, /* Consider tokens with this root node */
131922 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR
131955 ** The right-hand child of a NEAR node is always a phrase. The
131956 ** left-hand child may be either a phrase or a NEAR node. There are
132314 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
132373 ** expression node for the following information:
132480 /* Check if this phrase descends from an OR expression node. If not,
132483 ** tree that the node is part of has been marked as EOF, but the node
132493 /* This is the descendent of an OR node. In this case we cannot use
133273 ** called, it sets ParseContext.isNot to true if the 'next node' is a
133760 ** expression tree being parsed. pPrev is the expression node most recently
133762 ** operator node, into the expression tree based on the relative precedence
133764 ** of the tree changing, in which case *ppHead is set to the new root node.
133767 Fts3Expr **ppHead, /* Pointer to the root node of a tree */
133768 Fts3Expr *pPrev, /* Node most recently inserted into the tree */
133769 Fts3Expr *pNew /* New binary node to insert into expression tree */
133965 ** new root expression node.
133974 Fts3Expr *pRoot = *pp; /* Initial root node */
133976 int eType = pRoot->eType; /* Type of node in this tree */
134039 /* If that was the last leaf node, break out of the loop */
134055 /* Link pParent into the free node list. It will be used as an
134056 ** internal node of the new tree. */
134225 ** Free a single node of an expression tree.
136732 ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer
136735 ** This means that if we have a pointer into a buffer containing node data,
136737 ** overread, even if the node data is corrupted.
136846 char *aNode; /* Pointer to node data (or NULL) */
136849 sqlite3_blob *pBlob; /* If not NULL, blob handle to read node */
136917 SegmentNode *pParent; /* Parent node (or NULL for root node) */
136919 SegmentNode *pLeftmost; /* Pointer to left-most node of this depth */
136920 int nEntry; /* Number of terms written to node so far */
136926 char *aData; /* Node data */
138061 ** safe (no risk of overread) even if the node data is corrupted. */
138091 ** b-tree node. And that the final byte of the doclist is 0x00. If either
138178 ** position. The exception is if this node is being loaded from disk
138285 const char *zRoot, /* Buffer containing root node */
138286 int nRoot, /* Size of buffer containing root node */
138290 int nExtra = 0; /* Bytes to allocate segment root node */
138309 /* The entire segment is stored in the root node. */
138688 /* First try to append the term to the current node. Return early if
138692 int nData = pTree->nData; /* Current size of node in bytes */
138704 node
138705 ** and the static node buffer (p->nNodeSize bytes) is not large
138719 /* There is no prefix-length field for first term in a node */
138749 ** current node. Create a new node (a right-sibling of the current node).
138750 ** If this is the first node in the tree, the term is added to it.
138752 ** Otherwise, the term is not added to the new node, it is left empty for
138802 ** Write the buffer for the segment node pTree and all of its peers to the
138806 ** Except, if pTree is a root node, do not write it to the database. Instead,
138807 ** set output variables *paRoot and *pnRoot to contain the root node.
138817 int iHeight, /* Height of this node in tree */
138818 sqlite3_int64 iLeaf, /* Block id of first leaf node */
138821 char **paRoot, /* OUT: Data for root node */
138822 int *pnRoot /* OUT: Size of root node in bytes */
138827 /* Root node of the tree. */
138938 /* The current leaf node is full. Write it out to the database. */
138943 /* Add the current term to the interior node tree. The term added to
138946 ** a) be greater than the largest term on the leaf node just written
138950 ** leaf node (zTerm/nTerm).
139035 char *zRoot = NULL; /* Pointer to buffer containing root node */
139049 /* The entire tree fits on the root node. Write it to the segdir table. */
140344 ** FTS segment node. See the following functions:
140355 /* Output variables. Containing the current node entry. */
140356 sqlite3_int64 iChild; /* Pointer to child node */
140385 ** Attempt to advance the node-reader object passed as the first argument to
140386 ** the next entry on the node.
140389 ** Otherwise return SQLITE_OK. If there is no next entry on the node
140395 int bFirst = (p->term.n==0); /* True for first term on the node */
140430 ** Release all dynamic resources held by node-reader object *p.
140437 ** Initialize a node-reader object to read the node in buffer aNode/nNode.
140440 ** point to the first entry on the node (if any). Otherwise, an SQLite
140448 /* Figure out if this is a leaf or an internal node. */
140450 /* An internal node. */
140461 ** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed
140462 ** to be greater than the largest key on the node just written, but smaller
140464 ** node.
140466 ** The block id of the leaf node just written to disk may be found in
140472 const char *zTerm, /* Term to write to internal node */
140488 ** the current node of layer iLayer. Due to the prefix compression,
140489 ** the space required changes depending on which node the key is to
140497 /* If the current node of layer iLayer contains zero keys, or if adding
140524 /* Otherwise, flush the current node of layer iLayer to disk.
140525 ** Then allocate a new, empty sibling node. The key will be written
140526 ** into the parent of this node. */
140547 ** Append a term and (optionally) doclist to the FTS segment node currently
140548 ** stored in blob *pNode. The node need not contain any terms, but the
140551 ** A node header is a single 0x00 byte for a leaf node, or a height varint
140552 ** followed by the left-hand-child varint for an internal node.
140555 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
140556 ** node, both aDoclist and nDoclist must be passed 0.
140559 ** term written to the node. Otherwise, pPrev contains a copy of the
140571 Blob *pNode, /* Current node image to append to */
140583 /* Node must have already been started. There must be a doclist for a
140584 ** leaf node, and there must not be a doclist for an internal node. */
140650 /* Add the current term to the parent node. The term added to the
140653 ** a) be greater than the largest term on the leaf node just written
140657 ** leaf node (zTerm/nTerm).
140695 ** all outstanding node buffers held by pWriter to disk.
140712 NodeWriter *pRoot; /* NodeWriter for root node */
140716 ** root node. If the segment fits entirely on a single leaf node, iRoot
140717 ** will be set to 0. If the root node is the parent of the leaves, iRoot
140731 /* The entire output segment fits on a single node. Normally, this means
140732 ** the node would be stored as a blob in the "root" column of the %_segdir
140737 ** segments that fit entirely on the root node with start_block!=0.
140739 ** Instead, create a synthetic root node that contains nothing but a
140740 ** pointer to the single content node. So that the segment consists of a
140741 ** single leaf and a single interior (root) node.
141187 ** node. The node may be a leaf or an internal node.
141189 ** This function creates a new node image in blob object *pNew by copying
141194 const char *aNode, /* Current node image */
141196 Blob *pNew, /* OUT: Write new node image here */
141202 Blob prev = {0, 0, 0}; /* Previous term written to new node */
141204 int bLeaf = aNode[0]=='\0'; /* True for a leaf node */
141211 /* Populate new node buffer */
141293 /* Variable iNewStart now contains the first valid leaf node. */
142506 int eType = pExpr->eType; /* Type of expression node pExpr */
142524 ** For each phrase node found, the supplied callback function is invoked.
143129 Fts3Expr *pExpr, /* Phrase expression node */
143145 Fts3Expr *pExpr, /* Phrase expression node */
143258 Fts3Expr *pExpr, /* Phrase expression node */
144676 ** The data for each node of the r-tree structure is stored in the %_node
144677 ** table. For each node that is not the root node of the r-tree, there is
144678 ** an entry in the %_parent table associating the node with its parent.
144680 ** table that maps from the entries rowid to the id of the node that it
144683 ** The root node of an r-tree always exists, even if the r-tree table is
144684 ** empty. The nodeno of the root node is always 1. All other nodes in the
144685 ** table must be the same size as the root node. The content of each node
144688 ** 1. If the node is the root node (node 1), then the first 2 bytes
144689 ** of the node contain the tree depth as a big-endian integer.
144693 ** stored in the node.
144695 ** 3. The remainder of the node contains the node entries. Each entry
144698 ** of a record. For internal nodes it is the node number of a
144762 int iNodeSize; /* Size in bytes of each node in the node table */
144775 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
144821 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
144822 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
144823 ** the id is of the parent node and the cell that RtreeSearchPoint
144824 ** represents is the iCell-th entry in the parent node.
144827 RtreeDValue rScore; /* The score for this node. Smallest goes first. */
144828 sqlite3_int64 id; /* Node ID */
144829 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
144831 u8 iCell; /* Cell index within the node */
144835 ** The minimum number of cells allowed for a node is a third of the
144841 ** cells are removed from the overfull node and reinserted into the tree.
144848 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
144879 RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
144937 ** An rtree structure node.
144940 RtreeNode *pParent; /* Parent node */
144941 i64 iNode; /* The node number */
144942 int nRef; /* Number of references to this node */
144943 int isDirty; /* True if the node needs to be written to disk */
144944 u8 *zData; /* Content of the node, as should be on disk */
144945 RtreeNode *pNext; /* Next node in this hash collision chain */
144948 /* Return the number of cells in a node */
144952 ** A single cell from a node, deserialized
144955 i64 iRowid; /* Node or entry ID */
145072 ** Increment the reference count of node p.
145081 ** Clear the content of node p (set all bytes to 0x00).
145089 ** Given a node number iNode, return the corresponding key to use
145097 ** Search the node hash table for node iNode. If found, return a pointer
145107 ** Add node pNode to the node hash table.
145118 ** Remove node pNode from the node hash table.
145131 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
145132 ** indicating that node has not yet been assigned a node number. It is
145133 ** assigned a node number when nodeWrite() is called to write the
145134 ** node contents out to the database.
145151 ** Obtain a reference to an r-tree node.
145155 i64 iNode, /* Node number to load */
145156 RtreeNode *pParent, /* Either the parent node or NULL */
145157 RtreeNode **ppNode /* OUT: Acquired node */
145163 /* Check if the requested node is already in the hash table. If so,
145200 /* If the root node was just loaded, set pRtree->iDepth to the height
145202 ** the root node. A height of one means the children of the root node
145203 ** are the leaves, and so on. If the depth as specified on the root node
145214 ** field on the node is too large. If so, set the return code to
145239 ** Overwrite cell iCell of node pNode with the contents of pCell.
145243 RtreeNode *pNode, /* The node into which the cell is to be written */
145257 ** Remove the cell with index iCell from node pNode.
145269 ** Insert the contents of cell pCell into node pNode. If the insert
145276 RtreeNode *pNode, /* Write new cell into this node */
145296 ** If the node is dirty, write it out to the database.
145320 ** Release a reference to a node. If the node is dirty and the reference
145321 ** count drops to zero, the node data is written to the database.
145347 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
145348 ** an internal node, then the 64-bit integer is a child page number.
145352 RtreeNode *pNode, /* The node from which to extract the ID */
145360 ** Return coordinate iCoord from cell iCell in node pNode.
145364 RtreeNode *pNode, /* The node from which to extract a coordinate */
145365 int iCell, /* The index of the cell within the node */
145373 ** Deserialize cell iCell of node pNode. Populate the structure pointed
145378 RtreeNode *pNode, /* The node containing the cell to be read */
145379 int iCell, /* Index of the cell within the node */
145592 ** Check the RTree node or entry given by pCellData and p against the MATCH
145639 ** Check the internal RTree node given by pCellData against constraint p.
145640 ** If this constraint cannot be satisfied by any child within the node,
145710 ** One of the cells in node pNode is guaranteed to have a 64-bit
145732 ** Return the index of the cell containing a pointer to node pNode
145733 ** in its parent. If pNode is the root node, return -1.
146089 ** Use nodeAcquire() to obtain the leaf node containing the record with
146090 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
146098 RtreeNode **ppLeaf, /* Write the node here */
146099 sqlite3_int64 *piNode /* Write the node-id here */
146341 ** and then a linear search of an R-Tree node. This should be
146514 /* Select the child node which will be enlarged the least if pCell
146547 ** the node pNode. This function updates the bounding box cells in
146552 RtreeNode *pNode, /* Adjust ancestry of this node. */
146879 ** all cells from node pLeft. Then zero the original node.
146921 /* Ensure both child nodes have node numbers assigned to them by calling
146922 ** nodeWrite(). Node pRight always needs a node number, as it was created
146923 ** by nodeNew() above. But node pLeft sometimes already has a node number.
146995 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
146997 ** the pLeaf->pParent chain all the way up to the root node.
147014 i64 iNode; /* Node number of parent node */
147019 ** the referenced counted node structures.
147074 /* Remove the node from the in-memory hash table and link it into
147110 ** Delete the cell at index iCell of node pNode. After removing the
147121 /* Remove the cell from the node. This call just moves bytes around
147122 ** the in-memory node image, so it cannot fail.
147126 /* If the node is not the tree root and now has less than the minimum
147128 ** cell in the parent node so that it tightly contains the updated
147129 ** node.
147225 /* Find a node to store this cell in. pNode->iNode currently contains
147246 ** Insert cell pCell into node pNode. Node pNode is the head of a
147294 /* Find a node to store this cell in. pNode->iNode currently contains
147328 RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */
147330 RtreeNode *pRoot; /* Root node of rtree structure */
147333 /* Obtain a reference to the root node to initialize Rtree.iDepth */
147336 /* Obtain a reference to the leaf node that contains the entry
147343 /* Delete the cell in question from the leaf node. */
147363 /* Check if the root node now has exactly one child. If so, remove
147368 ** the root node (the operation that Gutman's paper says to perform
147397 /* Release the reference to the root node. */
147740 ** determine the node-size used by the rtree table being created or connected
147745 ** table already exists. In this case the node-size is determined by inspecting
147746 ** the root node of the tree.
147749 ** This ensures that each node is stored on a single database page. If the
147751 ** would fit in a single node, use a smaller node-size.
147844 /* Figure out the node size to use. */
147894 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
147900 ** entry for each cell in the r-tree node. Each entry is itself a
147906 RtreeNode node;
147911 memset(&node, 0, sizeof(RtreeNode));
147915 node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
147917 for(ii=0; ii<NCELL(&node); ii++){
147923 nodeGetCell(&tree, &node, ii, &cell);
147950 ** from the front of a blob that is an r-tree node. For example:
147954 ** The depth value is 0 for all nodes other than the root node, and the root
147955 ** node always has nodeno=1, so the example above is the primary use for this
