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 */
24231 typedef struct unixInodeInfo unixInodeInfo; /* An i-node */
28303 unixInodeInfo *pInode; /* unixInodeInfo that owns this SHM node */
39938 ** node taken from the head of *ppList. A depth of 2 means a tree with
51088 ** root-node and 3 for all other internal nodes.
57311 ** might be less than 8 (leaf-size + pointer) on the interior node. Hence
57569 ** This function is used to copy the contents of the b-tree node stored
57600 /* Copy the b-tree node content from page pFrom to page pTo. */
57659 ** size of a cell stored within an internal node is always less than 1/4
58119 ** previously stored on a leaf node, and its reported size was 4
58334 ** of the node stored on pRoot into the new child page.
58672 int iCellDepth; /* Depth of node containing pCell */
58695 ** from the internal node. The 'previous' entry is used for this instead
58728 ** node. The cell from the leaf node needs to be moved to the internal
58729 ** node to replace the deleted cell. */
58754 ** Otherwise, if the entry deleted was on an internal node page, then
58756 ** replace the cell deleted from the internal node. This is slightly
58757 ** tricky as the leaf node may be underfull, and the internal node may
58759 ** on the leaf node first. If the balance proceeds far enough up the
58760 ** tree that we can be sure that any problem in the internal node has
58761 ** been corrected, so be it. Otherwise, after balancing the leaf node,
58762 ** walk the cursor up the tree to the internal node and balance it as
59249 int iIdx; /* Index of child node in parent */
59261 /* pPage is a leaf node. This loop navigates the cursor so that it
59285 /* Descend to the child node of the cell that the cursor currently
76652 ** Walk an expression tree. Invoke the callback once for each node
76810 ** depth (the Expr.op2 field) by N on every TK_AGG_FUNCTION node.
76811 ** This needs to occur when copying a TK_AGG_FUNCTION node from an
76975 ** expression node refer back to that source column. The following changes
77005 Expr *pExpr /* Make this EXPR node point to the selected column */
77024 /* Initialize the node to no-match */
77381 ** node in the expression tree. Return 0 to continue the search down
78105 ** The node at the root of the subtree is modified as follows:
78309 ** sequence named by pToken. Return a pointer to a new Expr node that
78643 ** Construct a new expression node and return a pointer to it. Memory
78644 ** for this node and for the pToken argument is a single allocation
78646 ** is responsible for making sure the node eventually gets freed.
78652 ** then the EP_DblQuoted flag is set on the expression node.
78706 ** Allocate a new expression node from a zero-terminated token that has
78721 ** Attach subtrees pLeft and pRight to the Expr node pRoot.
78750 ** Allocate a Expr node which joins as many as two subtrees.
78753 ** Expr node. Or, if an OOM error occurs, set pParse->db->mallocFailed,
78829 ** Construct a new expression node for a function with multiple
80712 ** Convert an expression node to a TK_REGISTER
80740 Expr tempX; /* Temporary expression node */
85313 ** This only applies to the root node of pExpr, so the statement:
105686 ** are walked without any actions being taken at each node. Presumably,
110637 ** Think of each WhereLoop object as a node in a graph with arcs
117549 /* This routine constructs a binary expression node out of two ExprSpan
117564 /* Construct an expression node for a unary postfix operator
117567 ExprSpan *pOut, /* Write the new expression node here */
117589 /* Construct an expression node for a unary prefix operator
117592 ExprSpan *pOut, /* Write the new expression node here */
126097 ** iterate through a single leaf node's data) and LeavesReader (to
126120 ** of a node is reached, the next term is in the node with the next
126121 ** greater node id.
126123 ** New data is spilled to a new leaf node when the current node
126126 ** node (a leaf node with a single term and doclist). The goal of
126134 ** node rather than splitting into 2k and .5k nodes. My intuition is
126143 ** SegmentWriter creates new leaf nodes, or when an interior node
126148 ** varint iBlockid; (block id of node's leftmost subtree)
126163 ** An interior node encodes n terms separating n+1 subtrees. The
126174 ** New data is spilled to a new interior node at the same height when
126175 ** the current node exceeds INTERIOR_MAX bytes (default 2048).
126184 ** merging and deleting segments, and also the root node of the
126187 ** The root node is the top node of the segment's tree after encoding
126189 ** This could be either a leaf node or an interior node. If the top
126190 ** node requires more than ROOT_MAX bytes, it is flushed to %_segments
126191 ** and a new root interior node is generated (which should always fit
126199 ** start_block - first leaf node
126200 ** leaves_end_block - last leaf node
126202 ** root - contents of root node
126204 ** If the root node is a leaf node, then start_block,
126772 int nNodeSize; /* Soft limit for node size */
126953 ** when the expression node is.
128565 ** This function is used to process a single interior node when searching
128566 ** a b-tree for a term or term prefix. The node data is passed to this
128571 ** of the child node that heads the sub-tree that may contain the term.
128573 ** If piLast is not NULL, then *piLast is set to the right-most child node
128582 const char *zNode, /* Buffer containing segment interior node */
128584 sqlite3_int64 *piFirst, /* OUT: Selected child node */
128585 sqlite3_int64 *piLast /* OUT: Selected child node */
128588 const char *zCsr = zNode; /* Cursor to iterate through node */
128589 const char *zEnd = &zCsr[nNode];/* End of interior node buffer */
128593 sqlite3_int64 iChild; /* Block id of child node to descend to */
128596 ** interior node. Then load the blockid of the left-child of the b-tree
128597 ** node into variable iChild.
128601 ** root node, then the buffer comes from a SELECT statement. SQLite does
128604 ** contents, or two zero bytes. Or, if the node is read from the %_segments
128620 /* Load the next term on the node into zBuffer. Use realloc() to expand
128648 ** the interior node. If the specified term is greater than or equal
128649 ** to the term from the interior node, then all terms on the sub-tree
128650 ** headed by node iChild are smaller than zTerm. No need to search
128653 ** If the interior node term is larger than the specified term, then
128681 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
128683 ** node for the range of leaf nodes that may contain the specified term
128687 ** left-most leaf node in the tree that may contain the specified term.
128689 ** right-most leaf node that may contain a term for which the specified
128704 const char *zNode, /* Buffer containing segment interior node */
128706 sqlite3_int64 *piLeaf, /* Selected leaf node */
128707 sqlite3_int64 *piLeaf2 /* Selected leaf node */
128710 int iHeight; /* Height of this node in tree */
129639 ** root node, the range of leaves scanned can be reduced. Do this. */
130140 ** entry and each block (if any) between the leaf and the root node. So
131552 ** the cluster with root node pRoot. See comments above the definition
131561 Fts3Expr *pRoot, /* Consider tokens with this root node */
131954 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR
131987 ** The right-hand child of a NEAR node is always a phrase. The
131988 ** left-hand child may be either a phrase or a NEAR node. There are
132346 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
132405 ** expression node for the following information:
132512 /* Check if this phrase descends from an OR expression node. If not,
132515 ** tree that the node is part of has been marked as EOF, but the node
132525 /* This is the descendent of an OR node. In this case we cannot use
133305 ** called, it sets ParseContext.isNot to true if the 'next node' is a
133792 ** expression tree being parsed. pPrev is the expression node most recently
133794 ** operator node, into the expression tree based on the relative precedence
133796 ** of the tree changing, in which case *ppHead is set to the new root node.
133799 Fts3Expr **ppHead, /* Pointer to the root node of a tree */
133800 Fts3Expr *pPrev, /* Node most recently inserted into the tree */
133801 Fts3Expr *pNew /* New binary node to insert into expression tree */
133997 ** new root expression node.
134006 Fts3Expr *pRoot = *pp; /* Initial root node */
134008 int eType = pRoot->eType; /* Type of node in this tree */
134071 /* If that was the last leaf node, break out of the loop */
134087 /* Link pParent into the free node list. It will be used as an
134088 ** internal node of the new tree. */
134257 ** Free a single node of an expression tree.
136764 ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer
136767 ** This means that if we have a pointer into a buffer containing node data,
136769 ** overread, even if the node data is corrupted.
136878 char *aNode; /* Pointer to node data (or NULL) */
136881 sqlite3_blob *pBlob; /* If not NULL, blob handle to read node */
136949 SegmentNode *pParent; /* Parent node (or NULL for root node) */
136951 SegmentNode *pLeftmost; /* Pointer to left-most node of this depth */
136952 int nEntry; /* Number of terms written to node so far */
136958 char *aData; /* Node data */
138093 ** safe (no risk of overread) even if the node data is corrupted. */
138123 ** b-tree node. And that the final byte of the doclist is 0x00. If either
138210 ** position. The exception is if this node is being loaded from disk
138317 const char *zRoot, /* Buffer containing root node */
138318 int nRoot, /* Size of buffer containing root node */
138322 int nExtra = 0; /* Bytes to allocate segment root node */
138341 /* The entire segment is stored in the root node. */
138720 /* First try to append the term to the current node. Return early if
138724 int nData = pTree->nData; /* Current size of node in bytes */
138736 /* An unusual case: this is the first term to be added to the node
138737 ** and the static node buffer (p->nNodeSize bytes) is not large
138751 /* There is no prefix-length field for first term in a node */
138781 ** current node. Create a new node (a right-sibling of the current node).
138782 ** If this is the first node in the tree, the term is added to it.
138784 ** Otherwise, the term is not added to the new node, it is left empty for
138834 ** Write the buffer for the segment node pTree and all of its peers to the
138838 ** Except, if pTree is a root node, do not write it to the database. Instead,
138839 ** set output variables *paRoot and *pnRoot to contain the root node.
138849 int iHeight, /* Height of this node in tree */
138850 sqlite3_int64 iLeaf, /* Block id of first leaf node */
138853 char **paRoot, /* OUT: Data for root node */
138854 int *pnRoot /* OUT: Size of root node in bytes */
138859 /* Root node of the tree. */
138970 /* The current leaf node is full. Write it out to the database. */
138975 /* Add the current term to the interior node tree. The term added to
138978 ** a) be greater than the largest term on the leaf node just written
138982 ** leaf node (zTerm/nTerm).
139067 char *zRoot = NULL; /* Pointer to buffer containing root node */
139081 /* The entire tree fits on the root node. Write it to the segdir table. */
140376 ** FTS segment node. See the following functions:
140387 /* Output variables. Containing the current node entry. */
140388 sqlite3_int64 iChild; /* Pointer to child node */
140417 ** Attempt to advance the node-reader object passed as the first argument to
140418 ** the next entry on the node.
140421 ** Otherwise return SQLITE_OK. If there is no next entry on the node
140427 int bFirst = (p->term.n==0); /* True for first term on the node */
140462 ** Release all dynamic resources held by node-reader object *p.
140469 ** Initialize a node-reader object to read the node in buffer aNode/nNode.
140472 ** point to the first entry on the node (if any). Otherwise, an SQLite
140480 /* Figure out if this is a leaf or an internal node. */
140482 /* An internal node. */
140493 ** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed
140494 ** to be greater than the largest key on the node just written, but smaller
140496 ** node.
140498 ** The block id of the leaf node just written to disk may be found in
140504 const char *zTerm, /* Term to write to internal node */
140520 ** the current node of layer iLayer. Due to the prefix compression,
140521 ** the space required changes depending on which node the key is to
140529 /* If the current node of layer iLayer contains zero keys, or if adding
140556 /* Otherwise, flush the current node of layer iLayer to disk.
140557 ** Then allocate a new, empty sibling node. The key will be written
140558 ** into the parent of this node. */
140579 ** Append a term and (optionally) doclist to the FTS segment node currently
140580 ** stored in blob *pNode. The node need not contain any terms, but the
140583 ** A node header is a single 0x00 byte for a leaf node, or a height varint
140584 ** followed by the left-hand-child varint for an internal node.
140587 ** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
140588 ** node, both aDoclist and nDoclist must be passed 0.
140591 ** term written to the node. Otherwise, pPrev contains a copy of the
140603 Blob *pNode, /* Current node image to append to */
140615 /* Node must have already been started. There must be a doclist for a
140616 ** leaf node, and there must not be a doclist for an internal node. */
140682 /* Add the current term to the parent node. The term added to the
140685 ** a) be greater than the largest term on the leaf node just written
140689 ** leaf node (zTerm/nTerm).
140727 ** all outstanding node buffers held by pWriter to disk.
140744 NodeWriter *pRoot; /* NodeWriter for root node */
140748 ** root node. If the segment fits entirely on a single leaf node, iRoot
140749 ** will be set to 0. If the root node is the parent of the leaves, iRoot
140763 /* The entire output segment fits on a single node. Normally, this means
140764 ** the node would be stored as a blob in the "root" column of the %_segdir
140769 ** segments that fit entirely on the root node with start_block!=0.
140771 ** Instead, create a synthetic root node that contains nothing but a
140772 ** pointer to the single content node. So that the segment consists of a
140773 ** single leaf and a single interior (root) node.
141219 ** node. The node may be a leaf or an internal node.
141221 ** This function creates a new node image in blob object *pNew by copying
141226 const char *aNode, /* Current node image */
141228 Blob *pNew, /* OUT: Write new node image here */
141234 Blob prev = {0, 0, 0}; /* Previous term written to new node */
141236 int bLeaf = aNode[0]=='\0'; /* True for a leaf node */
141243 /* Populate new node buffer */
141325 /* Variable iNewStart now contains the first valid leaf node. */
142538 int eType = pExpr->eType; /* Type of expression node pExpr */
142556 ** For each phrase node found, the supplied callback function is invoked.
143161 Fts3Expr *pExpr, /* Phrase expression node */
143177 Fts3Expr *pExpr, /* Phrase expression node */
143290 Fts3Expr *pExpr, /* Phrase expression node */
144708 ** The data for each node of the r-tree structure is stored in the %_node
144709 ** table. For each node that is not the root node of the r-tree, there is
144710 ** an entry in the %_parent table associating the node with its parent.
144712 ** table that maps from the entries rowid to the id of the node that it
144715 ** The root node of an r-tree always exists, even if the r-tree table is
144716 ** empty. The nodeno of the root node is always 1. All other nodes in the
144717 ** table must be the same size as the root node. The content of each node
144720 ** 1. If the node is the root node (node 1), then the first 2 bytes
144721 ** of the node contain the tree depth as a big-endian integer.
144725 ** stored in the node.
144727 ** 3. The remainder of the node contains the node entries. Each entry
144730 ** of a record. For internal nodes it is the node number of a
144794 int iNodeSize; /* Size in bytes of each node in the node table */
144807 ** headed by the node (leaf nodes have RtreeNode.iNode==0).
144853 ** The id is always a node-id. For iLevel>=1 the id is the node-id of
144854 ** the node that the RtreeSearchPoint represents. When iLevel==0, however,
144855 ** the id is of the parent node and the cell that RtreeSearchPoint
144856 node.
144859 RtreeDValue rScore; /* The score for this node. Smallest goes first. */
144860 sqlite3_int64 id; /* Node ID */
144861 u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */
144863 u8 iCell; /* Cell index within the node */
144867 ** The minimum number of cells allowed for a node is a third of the
144873 ** cells are removed from the overfull node and reinserted into the tree.
144880 ** The smallest possible node-size is (512-64)==448 bytes. And the largest
144911 RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
144969 ** An rtree structure node.
144972 RtreeNode *pParent; /* Parent node */
144973 i64 iNode; /* The node number */
144974 int nRef; /* Number of references to this node */
144975 int isDirty; /* True if the node needs to be written to disk */
144976 u8 *zData; /* Content of the node, as should be on disk */
144977 RtreeNode *pNext; /* Next node in this hash collision chain */
144980 /* Return the number of cells in a node */
144984 ** A single cell from a node, deserialized
144987 i64 iRowid; /* Node or entry ID */
145104 ** Increment the reference count of node p.
145113 ** Clear the content of node p (set all bytes to 0x00).
145121 ** Given a node number iNode, return the corresponding key to use
145129 ** Search the node hash table for node iNode. If found, return a pointer
145139 ** Add node pNode to the node hash table.
145150 ** Remove node pNode from the node hash table.
145163 ** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
145164 ** indicating that node has not yet been assigned a node number. It is
145165 ** assigned a node number when nodeWrite() is called to write the
145166 ** node contents out to the database.
145183 ** Obtain a reference to an r-tree node.
145187 i64 iNode, /* Node number to load */
145188 RtreeNode *pParent, /* Either the parent node or NULL */
145189 RtreeNode **ppNode /* OUT: Acquired node */
145195 /* Check if the requested node is already in the hash table. If so,
145232 /* If the root node was just loaded, set pRtree->iDepth to the height
145234 ** the root node. A height of one means the children of the root node
145235 ** are the leaves, and so on. If the depth as specified on the root node
145246 ** field on the node is too large. If so, set the return code to
145271 ** Overwrite cell iCell of node pNode with the contents of pCell.
145275 RtreeNode *pNode, /* The node into which the cell is to be written */
145289 ** Remove the cell with index iCell from node pNode.
145301 ** Insert the contents of cell pCell into node pNode. If the insert
145308 RtreeNode *pNode, /* Write new cell into this node */
145328 ** If the node is dirty, write it out to the database.
145352 ** Release a reference to a node. If the node is dirty and the reference
145353 ** count drops to zero, the node data is written to the database.
145379 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
145380 ** an internal node, then the 64-bit integer is a child page number.
145384 RtreeNode *pNode, /* The node from which to extract the ID */
145392 node pNode.
145396 RtreeNode *pNode, /* The node from which to extract a coordinate */
145397 int iCell, /* The index of the cell within the node */
145405 ** Deserialize cell iCell of node pNode. Populate the structure pointed
145410 RtreeNode *pNode, /* The node containing the cell to be read */
145411 int iCell, /* Index of the cell within the node */
145624 ** Check the RTree node or entry given by pCellData and p against the MATCH
145671 ** Check the internal RTree node given by pCellData against constraint p.
145672 ** If this constraint cannot be satisfied by any child within the node,
145742 ** One of the cells in node pNode is guaranteed to have a 64-bit
145764 ** Return the index of the cell containing a pointer to node pNode
145765 ** in its parent. If pNode is the root node, return -1.
146121 ** Use nodeAcquire() to obtain the leaf node containing the record with
146122 ** rowid iRowid. If successful, set *ppLeaf to point to the node and
146130 RtreeNode **ppLeaf, /* Write the node here */
146131 sqlite3_int64 *piNode /* Write the node-id here */
146373 ** and then a linear search of an R-Tree node. This should be
146546 /* Select the child node which will be enlarged the least if pCell
146579 ** the node pNode. This function updates the bounding box cells in
146584 RtreeNode *pNode, /* Adjust ancestry of this node. */
146911 ** all cells from node pLeft. Then zero the original node.
146953 /* Ensure both child nodes have node numbers assigned to them by calling
146954 ** nodeWrite(). Node pRight always needs a node number, as it was created
146955 ** by nodeNew() above. But node pLeft sometimes already has a node number.
147027 ** If node pLeaf is not the root of the r-tree and its pParent pointer is
147029 ** the pLeaf->pParent chain all the way up to the root node.
147046 i64 iNode; /* Node number of parent node */
147051 ** the referenced counted node structures.
147106 /* Remove the node from the in-memory hash table and link it into
147142 ** Delete the cell at index iCell of node pNode. After removing the
147153 /* Remove the cell from the node. This call just moves bytes around
147154 ** the in-memory node image, so it cannot fail.
147158 /* If the node is not the tree root and now has less than the minimum
147160 ** cell in the parent node so that it tightly contains the updated
147161 ** node.
147257 /* Find a node to store this cell in. pNode->iNode currently contains
147278 ** Insert cell pCell into node pNode. Node pNode is the head of a
147326 /* Find a node to store this cell in. pNode->iNode currently contains
147360 RtreeNode *pLeaf = 0; /* Leaf node containing record iDelete */
147362 RtreeNode *pRoot; /* Root node of rtree structure */
147365 /* Obtain a reference to the root node to initialize Rtree.iDepth */
147368 /* Obtain a reference to the leaf node that contains the entry
147375 /* Delete the cell in question from the leaf node. */
147395 /* Check if the root node now has exactly one child. If so, remove
147400 ** the root node (the operation that Gutman's paper says to perform
147429 /* Release the reference to the root node. */
147772 ** determine the node-size used by the rtree table being created or connected
147777 ** table already exists. In this case the node-size is determined by inspecting
147778 ** the root node of the tree.
147781 ** This ensures that each node is stored on a single database page. If the
147783 ** would fit in a single node, use a smaller node-size.
147876 /* Figure out the node size to use. */
147926 ** an r-tree node. For a two-dimensional r-tree structure called "rt", to
147932 ** entry for each cell in the r-tree node. Each entry is itself a
147938 RtreeNode node;
147943 memset(&node, 0, sizeof(RtreeNode));
147947 node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
147949 for(ii=0; ii<NCELL(&node); ii++){
147955 nodeGetCell(&tree, &node, ii, &cell);
147982 ** from the front of a blob that is an r-tree node. For example:
147986 ** The depth value is 0 for all nodes other than the root node, and the root
147987 ** node always has nodeno=1, so the example above is the primary use for this
