Lines Matching refs:pRtree
320 (pRtree->eCoordType==RTREE_COORD_REAL32) ? \
614 static void nodeZero(Rtree *pRtree, RtreeNode *p){ in nodeZero() argument
615 memset(&p->zData[2], 0, pRtree->iNodeSize-2); in nodeZero()
631 static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ in nodeHashLookup() argument
633 for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); in nodeHashLookup()
640 static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ in nodeHashInsert() argument
644 pNode->pNext = pRtree->aHash[iHash]; in nodeHashInsert()
645 pRtree->aHash[iHash] = pNode; in nodeHashInsert()
651 static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){ in nodeHashDelete() argument
654 pp = &pRtree->aHash[nodeHash(pNode->iNode)]; in nodeHashDelete()
667 static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){ in nodeNew() argument
669 pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode) + pRtree->iNodeSize); in nodeNew()
671 memset(pNode, 0, sizeof(RtreeNode) + pRtree->iNodeSize); in nodeNew()
674 pRtree->nNodeRef++; in nodeNew()
685 static void nodeBlobReset(Rtree *pRtree){ in nodeBlobReset() argument
686 if( pRtree->pNodeBlob && pRtree->inWrTrans==0 && pRtree->nCursor==0 ){ in nodeBlobReset()
687 sqlite3_blob *pBlob = pRtree->pNodeBlob; in nodeBlobReset()
688 pRtree->pNodeBlob = 0; in nodeBlobReset()
697 Rtree *pRtree, /* R-tree structure */ in nodeAcquire() argument
708 if( (pNode = nodeHashLookup(pRtree, iNode))!=0 ){ in nodeAcquire()
710 RTREE_IS_CORRUPT(pRtree); in nodeAcquire()
718 if( pRtree->pNodeBlob ){ in nodeAcquire()
719 sqlite3_blob *pBlob = pRtree->pNodeBlob; in nodeAcquire()
720 pRtree->pNodeBlob = 0; in nodeAcquire()
722 pRtree->pNodeBlob = pBlob; in nodeAcquire()
724 nodeBlobReset(pRtree); in nodeAcquire()
728 if( pRtree->pNodeBlob==0 ){ in nodeAcquire()
729 char *zTab = sqlite3_mprintf("%s_node", pRtree->zName); in nodeAcquire()
731 rc = sqlite3_blob_open(pRtree->db, pRtree->zDb, zTab, "data", iNode, 0, in nodeAcquire()
732 &pRtree->pNodeBlob); in nodeAcquire()
736 nodeBlobReset(pRtree); in nodeAcquire()
742 RTREE_IS_CORRUPT(pRtree); in nodeAcquire()
744 }else if( pRtree->iNodeSize==sqlite3_blob_bytes(pRtree->pNodeBlob) ){ in nodeAcquire()
745 pNode = (RtreeNode *)sqlite3_malloc64(sizeof(RtreeNode)+pRtree->iNodeSize); in nodeAcquire()
752 pRtree->nNodeRef++; in nodeAcquire()
756 rc = sqlite3_blob_read(pRtree->pNodeBlob, pNode->zData, in nodeAcquire()
757 pRtree->iNodeSize, 0); in nodeAcquire()
768 pRtree->iDepth = readInt16(pNode->zData); in nodeAcquire()
769 if( pRtree->iDepth>RTREE_MAX_DEPTH ){ in nodeAcquire()
771 RTREE_IS_CORRUPT(pRtree); in nodeAcquire()
780 if( NCELL(pNode)>((pRtree->iNodeSize-4)/pRtree->nBytesPerCell) ){ in nodeAcquire()
782 RTREE_IS_CORRUPT(pRtree); in nodeAcquire()
789 nodeHashInsert(pRtree, pNode); in nodeAcquire()
792 RTREE_IS_CORRUPT(pRtree); in nodeAcquire()
797 pRtree->nNodeRef--; in nodeAcquire()
810 Rtree *pRtree, /* The overall R-Tree */ in nodeOverwriteCell() argument
816 u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; in nodeOverwriteCell()
818 for(ii=0; ii<pRtree->nDim2; ii++){ in nodeOverwriteCell()
827 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ in nodeDeleteCell() argument
828 u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; in nodeDeleteCell()
829 u8 *pSrc = &pDst[pRtree->nBytesPerCell]; in nodeDeleteCell()
830 int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell; in nodeDeleteCell()
843 Rtree *pRtree, /* The overall R-Tree */ in nodeInsertCell() argument
850 nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; in nodeInsertCell()
855 nodeOverwriteCell(pRtree, pNode, pCell, nCell); in nodeInsertCell()
866 static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){ in nodeWrite() argument
869 sqlite3_stmt *p = pRtree->pWriteNode; in nodeWrite()
875 sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC); in nodeWrite()
881 pNode->iNode = sqlite3_last_insert_rowid(pRtree->db); in nodeWrite()
882 nodeHashInsert(pRtree, pNode); in nodeWrite()
892 static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){ in nodeRelease() argument
896 assert( pRtree->nNodeRef>0 ); in nodeRelease()
899 pRtree->nNodeRef--; in nodeRelease()
901 pRtree->iDepth = -1; in nodeRelease()
904 rc = nodeRelease(pRtree, pNode->pParent); in nodeRelease()
907 rc = nodeWrite(pRtree, pNode); in nodeRelease()
909 nodeHashDelete(pRtree, pNode); in nodeRelease()
922 Rtree *pRtree, /* The overall R-Tree */ in nodeGetRowid() argument
927 return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); in nodeGetRowid()
934 Rtree *pRtree, /* The overall R-Tree */ in nodeGetCoord() argument
940 readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); in nodeGetCoord()
948 Rtree *pRtree, /* The overall R-Tree */ in nodeGetCell() argument
956 pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); in nodeGetCell()
957 pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); in nodeGetCell()
964 }while( ii<pRtree->nDim2 ); in nodeGetCell()
1004 static void rtreeReference(Rtree *pRtree){ in rtreeReference() argument
1005 pRtree->nBusy++; in rtreeReference()
1012 static void rtreeRelease(Rtree *pRtree){ in rtreeRelease() argument
1013 pRtree->nBusy--; in rtreeRelease()
1014 if( pRtree->nBusy==0 ){ in rtreeRelease()
1015 pRtree->inWrTrans = 0; in rtreeRelease()
1016 assert( pRtree->nCursor==0 ); in rtreeRelease()
1017 nodeBlobReset(pRtree); in rtreeRelease()
1018 assert( pRtree->nNodeRef==0 || pRtree->bCorrupt ); in rtreeRelease()
1019 sqlite3_finalize(pRtree->pWriteNode); in rtreeRelease()
1020 sqlite3_finalize(pRtree->pDeleteNode); in rtreeRelease()
1021 sqlite3_finalize(pRtree->pReadRowid); in rtreeRelease()
1022 sqlite3_finalize(pRtree->pWriteRowid); in rtreeRelease()
1023 sqlite3_finalize(pRtree->pDeleteRowid); in rtreeRelease()
1024 sqlite3_finalize(pRtree->pReadParent); in rtreeRelease()
1025 sqlite3_finalize(pRtree->pWriteParent); in rtreeRelease()
1026 sqlite3_finalize(pRtree->pDeleteParent); in rtreeRelease()
1027 sqlite3_finalize(pRtree->pWriteAux); in rtreeRelease()
1028 sqlite3_free(pRtree->zReadAuxSql); in rtreeRelease()
1029 sqlite3_free(pRtree); in rtreeRelease()
1045 Rtree *pRtree = (Rtree *)pVtab; in rtreeDestroy() local
1051 pRtree->zDb, pRtree->zName, in rtreeDestroy()
1052 pRtree->zDb, pRtree->zName, in rtreeDestroy()
1053 pRtree->zDb, pRtree->zName in rtreeDestroy()
1058 nodeBlobReset(pRtree); in rtreeDestroy()
1059 rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0); in rtreeDestroy()
1063 rtreeRelease(pRtree); in rtreeDestroy()
1074 Rtree *pRtree = (Rtree *)pVTab; in rtreeOpen() local
1082 pRtree->nCursor++; in rtreeOpen()
1094 Rtree *pRtree = (Rtree *)(pCsr->base.pVtab); in resetCursor() local
1109 for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); in resetCursor()
1113 pCsr->base.pVtab = (sqlite3_vtab*)pRtree; in resetCursor()
1122 Rtree *pRtree = (Rtree *)(cur->pVtab); in rtreeClose() local
1124 assert( pRtree->nCursor>0 ); in rtreeClose()
1128 pRtree->nCursor--; in rtreeClose()
1129 nodeBlobReset(pRtree); in rtreeClose()
1358 Rtree *pRtree, in nodeRowidIndex() argument
1367 if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ in nodeRowidIndex()
1372 RTREE_IS_CORRUPT(pRtree); in nodeRowidIndex()
1380 static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){ in nodeParentIndex() argument
1383 return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex); in nodeParentIndex()
1611 Rtree *pRtree = RTREE_OF_CURSOR(pCur); in rtreeStepToLeaf() local
1621 eInt = pRtree->eCoordType==RTREE_COORD_INT32; in rtreeStepToLeaf()
1628 pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell); in rtreeStepToLeaf()
1645 pCellData += pRtree->nBytesPerCell; in rtreeStepToLeaf()
1656 RTREE_IS_CORRUPT(pRtree); in rtreeStepToLeaf()
1723 Rtree *pRtree = (Rtree *)cur->pVtab; in rtreeColumn() local
1733 sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); in rtreeColumn()
1734 }else if( i<=pRtree->nDim2 ){ in rtreeColumn()
1735 nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); in rtreeColumn()
1737 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ in rtreeColumn()
1742 assert( pRtree->eCoordType==RTREE_COORD_INT32 ); in rtreeColumn()
1748 rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0, in rtreeColumn()
1753 nodeGetRowid(pRtree, pNode, p->iCell)); in rtreeColumn()
1764 sqlite3_column_value(pCsr->pReadAux, i - pRtree->nDim2 + 1)); in rtreeColumn()
1777 Rtree *pRtree, /* RTree to search */ in findLeafNode() argument
1784 sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid); in findLeafNode()
1785 if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){ in findLeafNode()
1786 i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0); in findLeafNode()
1788 rc = nodeAcquire(pRtree, iNode, 0, ppLeaf); in findLeafNode()
1789 sqlite3_reset(pRtree->pReadRowid); in findLeafNode()
1791 rc = sqlite3_reset(pRtree->pReadRowid); in findLeafNode()
1837 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; in rtreeFilter() local
1844 rtreeReference(pRtree); in rtreeFilter()
1860 rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); in rtreeFilter()
1871 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); in rtreeFilter()
1881 rc = nodeAcquire(pRtree, 1, 0, &pRoot); in rtreeFilter()
1889 memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); in rtreeFilter()
1906 p->pInfo->nCoord = pRtree->nDim2; in rtreeFilter()
1908 p->pInfo->mxLevel = pRtree->iDepth + 1; in rtreeFilter()
1931 pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1)); in rtreeFilter()
1946 nodeRelease(pRtree, pRoot); in rtreeFilter()
1947 rtreeRelease(pRtree); in rtreeFilter()
1986 Rtree *pRtree = (Rtree*)tab; in rtreeBestIndex() local
2036 && ((p->iColumn>0 && p->iColumn<=pRtree->nDim2) in rtreeBestIndex()
2064 nRow = pRtree->nRowEst >> (iIdx/2); in rtreeBestIndex()
2074 static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){ in cellArea() argument
2076 assert( pRtree->nDim>=1 && pRtree->nDim<=5 ); in cellArea()
2078 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ in cellArea()
2079 switch( pRtree->nDim ){ in cellArea()
2089 switch( pRtree->nDim ){ in cellArea()
2104 static RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){ in cellMargin() argument
2106 int ii = pRtree->nDim2 - 2; in cellMargin()
2117 static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ in cellUnion() argument
2119 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ in cellUnion()
2124 }while( ii<pRtree->nDim2 ); in cellUnion()
2130 }while( ii<pRtree->nDim2 ); in cellUnion()
2138 static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ in cellContains() argument
2140 int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); in cellContains()
2141 for(ii=0; ii<pRtree->nDim2; ii+=2){ in cellContains()
2156 static RtreeDValue cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ in cellGrowth() argument
2160 area = cellArea(pRtree, &cell); in cellGrowth()
2161 cellUnion(pRtree, &cell, pCell); in cellGrowth()
2162 return (cellArea(pRtree, &cell)-area); in cellGrowth()
2166 Rtree *pRtree, in cellOverlap() argument
2176 for(jj=0; jj<pRtree->nDim2; jj+=2){ in cellOverlap()
2198 Rtree *pRtree, /* Rtree table */ in ChooseLeaf() argument
2206 rc = nodeAcquire(pRtree, 1, 0, &pNode); in ChooseLeaf()
2208 for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ in ChooseLeaf()
2229 nodeGetCell(pRtree, pNode, iCell, &cell); in ChooseLeaf()
2230 growth = cellGrowth(pRtree, &cell, pCell); in ChooseLeaf()
2231 area = cellArea(pRtree, &cell); in ChooseLeaf()
2243 rc = nodeAcquire(pRtree, iBest, pNode, &pChild); in ChooseLeaf()
2244 nodeRelease(pRtree, pNode); in ChooseLeaf()
2258 Rtree *pRtree, /* Rtree table */ in AdjustTree() argument
2272 RTREE_IS_CORRUPT(pRtree); in AdjustTree()
2275 rc = nodeParentIndex(pRtree, p, &iCell); in AdjustTree()
2277 RTREE_IS_CORRUPT(pRtree); in AdjustTree()
2281 nodeGetCell(pRtree, pParent, iCell, &cell); in AdjustTree()
2282 if( !cellContains(pRtree, &cell, pCell) ){ in AdjustTree()
2283 cellUnion(pRtree, &cell, pCell); in AdjustTree()
2284 nodeOverwriteCell(pRtree, pParent, &cell, iCell); in AdjustTree()
2295 static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){ in rowidWrite() argument
2296 sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid); in rowidWrite()
2297 sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode); in rowidWrite()
2298 sqlite3_step(pRtree->pWriteRowid); in rowidWrite()
2299 return sqlite3_reset(pRtree->pWriteRowid); in rowidWrite()
2305 static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){ in parentWrite() argument
2306 sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode); in parentWrite()
2307 sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); in parentWrite()
2308 sqlite3_step(pRtree->pWriteParent); in parentWrite()
2309 return sqlite3_reset(pRtree->pWriteParent); in parentWrite()
2399 Rtree *pRtree, in SortByDimension() argument
2416 SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare); in SortByDimension()
2417 SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare); in SortByDimension()
2458 Rtree *pRtree, in splitNodeStartree() argument
2474 sqlite3_int64 nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); in splitNodeStartree()
2481 aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell]; in splitNodeStartree()
2483 for(ii=0; ii<pRtree->nDim; ii++){ in splitNodeStartree()
2485 aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; in splitNodeStartree()
2489 SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); in splitNodeStartree()
2492 for(ii=0; ii<pRtree->nDim; ii++){ in splitNodeStartree()
2500 nLeft=RTREE_MINCELLS(pRtree); in splitNodeStartree()
2501 nLeft<=(nCell-RTREE_MINCELLS(pRtree)); in splitNodeStartree()
2514 cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); in splitNodeStartree()
2516 cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); in splitNodeStartree()
2519 margin += cellMargin(pRtree, &left); in splitNodeStartree()
2520 margin += cellMargin(pRtree, &right); in splitNodeStartree()
2521 overlap = cellOverlap(pRtree, &left, &right, 1); in splitNodeStartree()
2522 area = cellArea(pRtree, &left) + cellArea(pRtree, &right); in splitNodeStartree()
2523 if( (nLeft==RTREE_MINCELLS(pRtree)) in splitNodeStartree()
2546 nodeInsertCell(pRtree, pTarget, pCell); in splitNodeStartree()
2547 cellUnion(pRtree, pBbox, pCell); in splitNodeStartree()
2556 Rtree *pRtree, in updateMapping() argument
2564 RtreeNode *pChild = nodeHashLookup(pRtree, iRowid); in updateMapping()
2570 nodeRelease(pRtree, pChild->pParent); in updateMapping()
2576 return xSetMapping(pRtree, iRowid, pNode->iNode); in updateMapping()
2580 Rtree *pRtree, in SplitNode() argument
2610 nodeGetCell(pRtree, pNode, i, &aCell[i]); in SplitNode()
2612 nodeZero(pRtree, pNode); in SplitNode()
2617 pRight = nodeNew(pRtree, pNode); in SplitNode()
2618 pLeft = nodeNew(pRtree, pNode); in SplitNode()
2619 pRtree->iDepth++; in SplitNode()
2621 writeInt16(pNode->zData, pRtree->iDepth); in SplitNode()
2624 pRight = nodeNew(pRtree, pLeft->pParent); in SplitNode()
2633 memset(pLeft->zData, 0, pRtree->iNodeSize); in SplitNode()
2634 memset(pRight->zData, 0, pRtree->iNodeSize); in SplitNode()
2636 rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight, in SplitNode()
2647 if( SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)) in SplitNode()
2648 || (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft))) in SplitNode()
2657 rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1); in SplitNode()
2664 rc = nodeParentIndex(pRtree, pLeft, &iCell); in SplitNode()
2666 nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell); in SplitNode()
2667 rc = AdjustTree(pRtree, pParent, &leftbbox); in SplitNode()
2674 if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){ in SplitNode()
2679 i64 iRowid = nodeGetRowid(pRtree, pRight, i); in SplitNode()
2680 rc = updateMapping(pRtree, iRowid, pRight, iHeight); in SplitNode()
2690 i64 iRowid = nodeGetRowid(pRtree, pLeft, i); in SplitNode()
2691 rc = updateMapping(pRtree, iRowid, pLeft, iHeight); in SplitNode()
2697 rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight); in SplitNode()
2701 rc = nodeRelease(pRtree, pRight); in SplitNode()
2705 rc = nodeRelease(pRtree, pLeft); in SplitNode()
2710 nodeRelease(pRtree, pRight); in SplitNode()
2711 nodeRelease(pRtree, pLeft); in SplitNode()
2727 static int fixLeafParent(Rtree *pRtree, RtreeNode *pLeaf){ in fixLeafParent() argument
2732 sqlite3_bind_int64(pRtree->pReadParent, 1, pChild->iNode); in fixLeafParent()
2733 rc = sqlite3_step(pRtree->pReadParent); in fixLeafParent()
2743 iNode = sqlite3_column_int64(pRtree->pReadParent, 0); in fixLeafParent()
2746 rc2 = nodeAcquire(pRtree, iNode, 0, &pChild->pParent); in fixLeafParent()
2749 rc = sqlite3_reset(pRtree->pReadParent); in fixLeafParent()
2752 RTREE_IS_CORRUPT(pRtree); in fixLeafParent()
2762 static int removeNode(Rtree *pRtree, RtreeNode *pNode, int iHeight){ in removeNode() argument
2771 rc = nodeParentIndex(pRtree, pNode, &iCell); in removeNode()
2775 rc = deleteCell(pRtree, pParent, iCell, iHeight+1); in removeNode()
2778 rc2 = nodeRelease(pRtree, pParent); in removeNode()
2787 sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode); in removeNode()
2788 sqlite3_step(pRtree->pDeleteNode); in removeNode()
2789 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){ in removeNode()
2794 sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode); in removeNode()
2795 sqlite3_step(pRtree->pDeleteParent); in removeNode()
2796 if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){ in removeNode()
2803 nodeHashDelete(pRtree, pNode); in removeNode()
2805 pNode->pNext = pRtree->pDeleted; in removeNode()
2807 pRtree->pDeleted = pNode; in removeNode()
2812 static int fixBoundingBox(Rtree *pRtree, RtreeNode *pNode){ in fixBoundingBox() argument
2819 nodeGetCell(pRtree, pNode, 0, &box); in fixBoundingBox()
2822 nodeGetCell(pRtree, pNode, ii, &cell); in fixBoundingBox()
2823 cellUnion(pRtree, &box, &cell); in fixBoundingBox()
2826 rc = nodeParentIndex(pRtree, pNode, &ii); in fixBoundingBox()
2828 nodeOverwriteCell(pRtree, pParent, &box, ii); in fixBoundingBox()
2829 rc = fixBoundingBox(pRtree, pParent); in fixBoundingBox()
2839 static int deleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell, int iHeight){ in deleteCell() argument
2843 if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){ in deleteCell()
2850 nodeDeleteCell(pRtree, pNode, iCell); in deleteCell()
2860 if( NCELL(pNode)<RTREE_MINCELLS(pRtree) ){ in deleteCell()
2861 rc = removeNode(pRtree, pNode, iHeight); in deleteCell()
2863 rc = fixBoundingBox(pRtree, pNode); in deleteCell()
2871 Rtree *pRtree, in Reinsert() argument
2912 nodeGetCell(pRtree, pNode, ii, &aCell[ii]); in Reinsert()
2915 for(iDim=0; iDim<pRtree->nDim; iDim++){ in Reinsert()
2920 for(iDim=0; iDim<pRtree->nDim; iDim++){ in Reinsert()
2926 for(iDim=0; iDim<pRtree->nDim; iDim++){ in Reinsert()
2934 nodeZero(pRtree, pNode); in Reinsert()
2936 for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){ in Reinsert()
2938 nodeInsertCell(pRtree, pNode, p); in Reinsert()
2941 rc = rowidWrite(pRtree, p->iRowid, pNode->iNode); in Reinsert()
2943 rc = parentWrite(pRtree, p->iRowid, pNode->iNode); in Reinsert()
2948 rc = fixBoundingBox(pRtree, pNode); in Reinsert()
2956 rc = ChooseLeaf(pRtree, p, iHeight, &pInsert); in Reinsert()
2959 rc = rtreeInsertCell(pRtree, pInsert, p, iHeight); in Reinsert()
2960 rc2 = nodeRelease(pRtree, pInsert); in Reinsert()
2976 Rtree *pRtree, in rtreeInsertCell() argument
2983 RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid); in rtreeInsertCell()
2985 nodeRelease(pRtree, pChild->pParent); in rtreeInsertCell()
2990 if( nodeInsertCell(pRtree, pNode, pCell) ){ in rtreeInsertCell()
2991 if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ in rtreeInsertCell()
2992 rc = SplitNode(pRtree, pNode, pCell, iHeight); in rtreeInsertCell()
2994 pRtree->iReinsertHeight = iHeight; in rtreeInsertCell()
2995 rc = Reinsert(pRtree, pNode, pCell, iHeight); in rtreeInsertCell()
2998 rc = AdjustTree(pRtree, pNode, pCell); in rtreeInsertCell()
3001 rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); in rtreeInsertCell()
3003 rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode); in rtreeInsertCell()
3010 static int reinsertNodeContent(Rtree *pRtree, RtreeNode *pNode){ in reinsertNodeContent() argument
3018 nodeGetCell(pRtree, pNode, ii, &cell); in reinsertNodeContent()
3023 rc = ChooseLeaf(pRtree, &cell, (int)pNode->iNode, &pInsert); in reinsertNodeContent()
3026 rc = rtreeInsertCell(pRtree, pInsert, &cell, (int)pNode->iNode); in reinsertNodeContent()
3027 rc2 = nodeRelease(pRtree, pInsert); in reinsertNodeContent()
3039 static int rtreeNewRowid(Rtree *pRtree, i64 *piRowid){ in rtreeNewRowid() argument
3041 sqlite3_bind_null(pRtree->pWriteRowid, 1); in rtreeNewRowid()
3042 sqlite3_bind_null(pRtree->pWriteRowid, 2); in rtreeNewRowid()
3043 sqlite3_step(pRtree->pWriteRowid); in rtreeNewRowid()
3044 rc = sqlite3_reset(pRtree->pWriteRowid); in rtreeNewRowid()
3045 *piRowid = sqlite3_last_insert_rowid(pRtree->db); in rtreeNewRowid()
3052 static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){ in rtreeDeleteRowid() argument
3060 rc = nodeAcquire(pRtree, 1, 0, &pRoot); in rtreeDeleteRowid()
3066 rc = findLeafNode(pRtree, iDelete, &pLeaf, 0); in rtreeDeleteRowid()
3076 rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell); in rtreeDeleteRowid()
3078 rc = deleteCell(pRtree, pLeaf, iCell, 0); in rtreeDeleteRowid()
3080 rc2 = nodeRelease(pRtree, pLeaf); in rtreeDeleteRowid()
3088 sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete); in rtreeDeleteRowid()
3089 sqlite3_step(pRtree->pDeleteRowid); in rtreeDeleteRowid()
3090 rc = sqlite3_reset(pRtree->pDeleteRowid); in rtreeDeleteRowid()
3101 if( rc==SQLITE_OK && pRtree->iDepth>0 && NCELL(pRoot)==1 ){ in rtreeDeleteRowid()
3104 i64 iChild = nodeGetRowid(pRtree, pRoot, 0); in rtreeDeleteRowid()
3105 rc = nodeAcquire(pRtree, iChild, pRoot, &pChild); /* tag-20210916a */ in rtreeDeleteRowid()
3107 rc = removeNode(pRtree, pChild, pRtree->iDepth-1); in rtreeDeleteRowid()
3109 rc2 = nodeRelease(pRtree, pChild); in rtreeDeleteRowid()
3112 pRtree->iDepth--; in rtreeDeleteRowid()
3113 writeInt16(pRoot->zData, pRtree->iDepth); in rtreeDeleteRowid()
3119 for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){ in rtreeDeleteRowid()
3121 rc = reinsertNodeContent(pRtree, pLeaf); in rtreeDeleteRowid()
3123 pRtree->pDeleted = pLeaf->pNext; in rtreeDeleteRowid()
3124 pRtree->nNodeRef--; in rtreeDeleteRowid()
3130 rc = nodeRelease(pRtree, pRoot); in rtreeDeleteRowid()
3132 nodeRelease(pRtree, pRoot); in rtreeDeleteRowid()
3180 static int rtreeConstraintError(Rtree *pRtree, int iCol){ in rtreeConstraintError() argument
3186 zSql = sqlite3_mprintf("SELECT * FROM %Q.%Q", pRtree->zDb, pRtree->zName); in rtreeConstraintError()
3188 rc = sqlite3_prepare_v2(pRtree->db, zSql, -1, &pStmt, 0); in rtreeConstraintError()
3197 pRtree->base.zErrMsg = sqlite3_mprintf( in rtreeConstraintError()
3198 "UNIQUE constraint failed: %s.%s", pRtree->zName, zCol in rtreeConstraintError()
3203 pRtree->base.zErrMsg = sqlite3_mprintf( in rtreeConstraintError()
3204 "rtree constraint failed: %s.(%s<=%s)", pRtree->zName, zCol1, zCol2 in rtreeConstraintError()
3224 Rtree *pRtree = (Rtree *)pVtab; in rtreeUpdate() local
3229 if( pRtree->nNodeRef ){ in rtreeUpdate()
3235 rtreeReference(pRtree); in rtreeUpdate()
3255 if( nn > pRtree->nDim2 ) nn = pRtree->nDim2; in rtreeUpdate()
3266 if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ in rtreeUpdate()
3271 rc = rtreeConstraintError(pRtree, ii+1); in rtreeUpdate()
3282 rc = rtreeConstraintError(pRtree, ii+1); in rtreeUpdate()
3296 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid); in rtreeUpdate()
3297 steprc = sqlite3_step(pRtree->pReadRowid); in rtreeUpdate()
3298 rc = sqlite3_reset(pRtree->pReadRowid); in rtreeUpdate()
3300 if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){ in rtreeUpdate()
3301 rc = rtreeDeleteRowid(pRtree, cell.iRowid); in rtreeUpdate()
3303 rc = rtreeConstraintError(pRtree, 0); in rtreeUpdate()
3317 rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0])); in rtreeUpdate()
3330 rc = rtreeNewRowid(pRtree, &cell.iRowid); in rtreeUpdate()
3335 rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf); in rtreeUpdate()
3339 pRtree->iReinsertHeight = -1; in rtreeUpdate()
3340 rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0); in rtreeUpdate()
3341 rc2 = nodeRelease(pRtree, pLeaf); in rtreeUpdate()
3346 if( rc==SQLITE_OK && pRtree->nAux ){ in rtreeUpdate()
3347 sqlite3_stmt *pUp = pRtree->pWriteAux; in rtreeUpdate()
3350 for(jj=0; jj<pRtree->nAux; jj++){ in rtreeUpdate()
3351 sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]); in rtreeUpdate()
3359 rtreeRelease(pRtree); in rtreeUpdate()
3367 Rtree *pRtree = (Rtree *)pVtab; in rtreeBeginTransaction() local
3368 assert( pRtree->inWrTrans==0 ); in rtreeBeginTransaction()
3369 pRtree->inWrTrans++; in rtreeBeginTransaction()
3378 Rtree *pRtree = (Rtree *)pVtab; in rtreeEndTransaction() local
3379 pRtree->inWrTrans = 0; in rtreeEndTransaction()
3380 nodeBlobReset(pRtree); in rtreeEndTransaction()
3388 Rtree *pRtree = (Rtree *)pVtab; in rtreeRename() local
3394 , pRtree->zDb, pRtree->zName, zNewName in rtreeRename()
3395 , pRtree->zDb, pRtree->zName, zNewName in rtreeRename()
3396 , pRtree->zDb, pRtree->zName, zNewName in rtreeRename()
3399 nodeBlobReset(pRtree); in rtreeRename()
3400 rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0); in rtreeRename()
3421 Rtree *pRtree = (Rtree *)pVtab; in rtreeSavepoint() local
3422 u8 iwt = pRtree->inWrTrans; in rtreeSavepoint()
3424 pRtree->inWrTrans = 0; in rtreeSavepoint()
3425 nodeBlobReset(pRtree); in rtreeSavepoint()
3426 pRtree->inWrTrans = iwt; in rtreeSavepoint()
3435 static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){ in rtreeQueryStat1() argument
3443 db, pRtree->zDb, "sqlite_stat1",0,0,0,0,0,0 in rtreeQueryStat1()
3446 pRtree->nRowEst = RTREE_DEFAULT_ROWEST; in rtreeQueryStat1()
3449 zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName); in rtreeQueryStat1()
3460 pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST); in rtreeQueryStat1()
3508 Rtree *pRtree, in rtreeSqlInit() argument
3536 pRtree->db = db; in rtreeSqlInit()
3545 for(ii=0; ii<pRtree->nAux; ii++){ in rtreeSqlInit()
3556 zDb, zPrefix, pRtree->iNodeSize); in rtreeSqlInit()
3568 appStmt[0] = &pRtree->pWriteNode; in rtreeSqlInit()
3569 appStmt[1] = &pRtree->pDeleteNode; in rtreeSqlInit()
3570 appStmt[2] = &pRtree->pReadRowid; in rtreeSqlInit()
3571 appStmt[3] = &pRtree->pWriteRowid; in rtreeSqlInit()
3572 appStmt[4] = &pRtree->pDeleteRowid; in rtreeSqlInit()
3573 appStmt[5] = &pRtree->pReadParent; in rtreeSqlInit()
3574 appStmt[6] = &pRtree->pWriteParent; in rtreeSqlInit()
3575 appStmt[7] = &pRtree->pDeleteParent; in rtreeSqlInit()
3577 rc = rtreeQueryStat1(db, pRtree); in rtreeSqlInit()
3581 if( i!=3 || pRtree->nAux==0 ){ in rtreeSqlInit()
3597 if( pRtree->nAux ){ in rtreeSqlInit()
3598 pRtree->zReadAuxSql = sqlite3_mprintf( in rtreeSqlInit()
3601 if( pRtree->zReadAuxSql==0 ){ in rtreeSqlInit()
3608 for(ii=0; ii<pRtree->nAux; ii++){ in rtreeSqlInit()
3611 if( ii<pRtree->nAuxNotNull ){ in rtreeSqlInit()
3624 rc = sqlite3_prepare_v3(db, zSql, -1, f, &pRtree->pWriteAux, 0); in rtreeSqlInit()
3672 Rtree *pRtree, /* Rtree handle */ in getNodeSize() argument
3680 zSql = sqlite3_mprintf("PRAGMA %Q.page_size", pRtree->zDb); in getNodeSize()
3683 pRtree->iNodeSize = iPageSize-64; in getNodeSize()
3684 if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){ in getNodeSize()
3685 pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS; in getNodeSize()
3693 pRtree->zDb, pRtree->zName in getNodeSize()
3695 rc = getIntFromStmt(db, zSql, &pRtree->iNodeSize); in getNodeSize()
3698 }else if( pRtree->iNodeSize<(512-64) ){ in getNodeSize()
3700 RTREE_IS_CORRUPT(pRtree); in getNodeSize()
3702 pRtree->zName); in getNodeSize()
3736 Rtree *pRtree; in rtreeInit() local
3764 pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName+2); in rtreeInit()
3765 if( !pRtree ){ in rtreeInit()
3768 memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); in rtreeInit()
3769 pRtree->nBusy = 1; in rtreeInit()
3770 pRtree->base.pModule = &rtreeModule; in rtreeInit()
3771 pRtree->zDb = (char *)&pRtree[1]; in rtreeInit()
3772 pRtree->zName = &pRtree->zDb[nDb+1]; in rtreeInit()
3773 pRtree->eCoordType = (u8)eCoordType; in rtreeInit()
3774 memcpy(pRtree->zDb, argv[1], nDb); in rtreeInit()
3775 memcpy(pRtree->zName, argv[2], nName); in rtreeInit()
3788 pRtree->nAux++; in rtreeInit()
3790 }else if( pRtree->nAux>0 ){ in rtreeInit()
3794 pRtree->nDim2++; in rtreeInit()
3811 pRtree->nDim = pRtree->nDim2/2; in rtreeInit()
3812 if( pRtree->nDim<1 ){ in rtreeInit()
3814 }else if( pRtree->nDim2>RTREE_MAX_DIMENSIONS*2 ){ in rtreeInit()
3816 }else if( pRtree->nDim2 % 2 ){ in rtreeInit()
3825 pRtree->nBytesPerCell = 8 + pRtree->nDim2*4; in rtreeInit()
3828 rc = getNodeSize(db, pRtree, isCreate, pzErr); in rtreeInit()
3830 rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate); in rtreeInit()
3836 *ppVtab = (sqlite3_vtab *)pRtree; in rtreeInit()
3842 assert( pRtree->nBusy==1 ); in rtreeInit()
3843 rtreeRelease(pRtree); in rtreeInit()