Lines Matching defs:pNode
212 RtreeNode *pNode; /* Node cursor is currently pointing at */
213 int iCell; /* Index of current cell in pNode */
265 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
417 ** Add node pNode to the node hash table.
419 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){
421 assert( pNode->pNext==0 );
422 iHash = nodeHash(pNode->iNode);
423 pNode->pNext = pRtree->aHash[iHash];
424 pRtree->aHash[iHash] = pNode;
428 ** Remove node pNode from the node hash table.
430 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){
432 if( pNode->iNode!=0 ){
433 pp = &pRtree->aHash[nodeHash(pNode->iNode)];
434 for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }
435 *pp = pNode->pNext;
436 pNode->pNext = 0;
447 RtreeNode *pNode;
448 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
449 if( pNode ){
450 memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize);
451 pNode->zData = (u8 *)&pNode[1];
452 pNode->nRef = 1;
453 pNode->pParent = pParent;
454 pNode->isDirty = 1;
457 return pNode;
472 RtreeNode *pNode;
477 if( (pNode = nodeHashLookup(pRtree, iNode)) ){
478 assert( !pParent || !pNode->pParent || pNode->pParent==pParent );
479 if( pParent && !pNode->pParent ){
481 pNode->pParent = pParent;
483 pNode->nRef++;
484 *ppNode = pNode;
493 pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode)+pRtree->iNodeSize);
494 if( !pNode ){
497 pNode->pParent = pParent;
498 pNode->zData = (u8 *)&pNode[1];
499 pNode->nRef = 1;
500 pNode->iNode = iNode;
501 pNode->isDirty = 0;
502 pNode->pNext = 0;
503 memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
517 if( pNode && iNode==1 ){
518 pRtree->iDepth = readInt16(pNode->zData);
528 if( pNode && rc==SQLITE_OK ){
529 if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){
535 if( pNode!=0 ){
536 nodeHashInsert(pRtree, pNode);
540 *ppNode = pNode;
542 sqlite3_free(pNode);
550 ** Overwrite cell iCell of node pNode with the contents of pCell.
554 RtreeNode *pNode,
559 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
564 pNode->isDirty = 1;
568 ** Remove cell the cell with index iCell from node pNode.
570 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
571 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
573 int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
575 writeInt16(&pNode->zData[2], NCELL(pNode)-1);
576 pNode->isDirty = 1;
580 ** Insert the contents of cell pCell into node pNode. If the insert
583 ** If there is not enough free space in pNode, return SQLITE_FULL.
588 RtreeNode *pNode,
591 int nCell; /* Current number of cells in pNode */
592 int nMaxCell; /* Maximum number of cells for pNode */
595 nCell = NCELL(pNode);
599 nodeOverwriteCell(pRtree, pNode, pCell, nCell);
600 writeInt16(&pNode->zData[2], nCell+1);
601 pNode->isDirty = 1;
611 nodeWrite(Rtree *pRtree, RtreeNode *pNode){
613 if( pNode->isDirty ){
615 if( pNode->iNode ){
616 sqlite3_bind_int64(p, 1, pNode->iNode);
620 sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
622 pNode->isDirty = 0;
624 if( pNode->iNode==0 && rc==SQLITE_OK ){
625 pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
626 nodeHashInsert(pRtree, pNode);
637 nodeRelease(Rtree *pRtree, RtreeNode *pNode){
639 if( pNode ){
640 assert( pNode->nRef>0 );
641 pNode->nRef--;
642 if( pNode->nRef==0 ){
643 if( pNode->iNode==1 ){
646 if( pNode->pParent ){
647 rc = nodeRelease(pRtree, pNode->pParent);
650 rc = nodeWrite(pRtree, pNode);
652 nodeHashDelete(pRtree, pNode);
653 sqlite3_free(pNode);
661 ** node pNode. If pNode is a leaf node, this is a rowid. If it is
666 RtreeNode *pNode,
669 assert( iCell<NCELL(pNode) );
670 return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
674 ** Return coordinate iCoord from cell iCell in node pNode.
678 RtreeNode *pNode,
683 readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
687 ** Deserialize cell iCell of node pNode. Populate the structure pointed
692 RtreeNode *pNode,
697 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
699 nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
844 rc = nodeRelease(pRtree, pCsr->pNode);
857 return (pCsr->pNode==0);
898 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
951 nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
1003 RtreeNode *pSavedNode = pCursor->pNode;
1017 iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
1018 rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
1023 nodeRelease(pRtree, pCursor->pNode);
1024 pCursor->pNode = pChild;
1035 assert( pCursor->pNode==pChild );
1038 pCursor->pNode = pSavedNode;
1048 ** One of the cells in node pNode is guaranteed to have a 64-bit
1053 RtreeNode *pNode,
1058 int nCell = NCELL(pNode);
1060 if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
1069 ** Return the index of the cell containing a pointer to node pNode
1070 ** in its parent. If pNode is the root node, return -1.
1072 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
1073 RtreeNode *pParent = pNode->pParent;
1075 return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
1089 /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
1093 assert( pCsr->pNode );
1097 nodeRelease(pRtree, pCsr->pNode);
1098 pCsr->pNode = 0;
1102 while( pCsr->pNode ){
1103 RtreeNode *pNode = pCsr->pNode;
1104 int nCell = NCELL(pNode);
1112 pCsr->pNode = pNode->pParent;
1113 rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
1117 nodeReference(pCsr->pNode);
1118 nodeRelease(pRtree, pNode);
1133 assert(pCsr->pNode);
1134 *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1147 i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
1151 nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
1255 pCsr->pNode = pLeaf;
1293 pCsr->pNode = 0;
1299 pCsr->pNode = pRoot;
1301 assert( pCsr->pNode==pRoot );
1308 assert( pCsr->pNode==pRoot );
1310 pCsr->pNode = 0;
1312 assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
1563 RtreeNode *pNode;
1564 rc = nodeAcquire(pRtree, 1, 0, &pNode);
1574 int nCell = NCELL(pNode);
1586 nodeRelease(pRtree, pNode);
1587 pNode = 0;
1591 nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
1605 nodeGetCell(pRtree, pNode, iCell, &cell);
1634 rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
1635 nodeRelease(pRtree, pNode);
1636 pNode = pChild;
1639 *ppLeaf = pNode;
1645 ** the node pNode. This function updates the bounding box cells in
1650 RtreeNode *pNode, /* Adjust ancestry of this node. */
1653 RtreeNode *p = pNode;
2146 RtreeNode *pNode,
2155 nodeReference(pNode);
2156 pChild->pParent = pNode;
2159 return xSetMapping(pRtree, iRowid, pNode->iNode);
2164 RtreeNode *pNode,
2172 int nCell = NCELL(pNode);
2193 nodeGetCell(pRtree, pNode, i, &aCell[i]);
2195 nodeZero(pRtree, pNode);
2199 if( pNode->iNode==1 ){
2200 pRight = nodeNew(pRtree, pNode);
2201 pLeft = nodeNew(pRtree, pNode);
2203 pNode->isDirty = 1;
2204 writeInt16(pNode->zData, pRtree->iDepth);
2206 pLeft = pNode;
2238 if( pNode->iNode==1 ){
2269 if( pNode->iNode==1 ){
2340 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){
2346 assert( pNode->nRef==1 );
2349 rc = nodeParentIndex(pRtree, pNode, &iCell);
2351 pParent = pNode->pParent;
2352 pNode->pParent = 0;
2364 sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
2371 sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
2380 nodeHashDelete(pRtree, pNode);
2381 pNode->iNode = iHeight;
2382 pNode->pNext = pRtree->pDeleted;
2383 pNode->nRef++;
2384 pRtree->pDeleted = pNode;
2389 static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){
2390 RtreeNode *pParent = pNode->pParent;
2394 int nCell = NCELL(pNode);
2395 RtreeCell box; /* Bounding box for pNode */
2396 nodeGetCell(pRtree, pNode, 0, &box);
2399 nodeGetCell(pRtree, pNode, ii, &cell);
2402 box.iRowid = pNode->iNode;
2403 rc = nodeParentIndex(pRtree, pNode, &ii);
2413 ** Delete the cell at index iCell of node pNode. After removing the
2416 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){
2420 if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
2427 nodeDeleteCell(pRtree, pNode, iCell);
2434 pParent = pNode->pParent;
2435 assert( pParent || pNode->iNode==1 );
2437 if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){
2438 rc = removeNode(pRtree, pNode, iHeight);
2440 rc = fixBoundingBox(pRtree, pNode);
2449 RtreeNode *pNode,
2465 nCell = NCELL(pNode)+1;
2487 nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
2509 nodeZero(pRtree, pNode);
2513 nodeInsertCell(pRtree, pNode, p);
2516 rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
2518 rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
2523 rc = fixBoundingBox(pRtree, pNode);
2526 /* Find a node to store this cell in. pNode->iNode currently contains
2547 ** Insert cell pCell into node pNode. Node pNode is the head of a
2552 RtreeNode *pNode,
2561 nodeReference(pNode);
2562 pChild->pParent = pNode;
2565 if( nodeInsertCell(pRtree, pNode, pCell) ){
2567 if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
2568 rc = SplitNode(pRtree, pNode, pCell, iHeight);
2571 rc = Reinsert(pRtree, pNode, pCell, iHeight);
2574 rc = SplitNode(pRtree, pNode, pCell, iHeight);
2577 rc = AdjustTree(pRtree, pNode, pCell);
2580 rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
2582 rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
2589 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){
2592 int nCell = NCELL(pNode);
2597 nodeGetCell(pRtree, pNode, ii, &cell);
2599 /* Find a node to store this cell in. pNode->iNode currently contains
2602 rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
2605 rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);