Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Have the rtree extension publish two virtual table types: "rtree" and "rtree_i32". rtree_i32 stores coordinate data as 32-bit signed integers. rtree uses 32-bit real (floating point) values. (CVS 5410) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
c060a9a6beca455bdceee9ce6ca71a72 |
User & Date: | danielk1977 2008-07-14 15:37:01.000 |
Context
2008-07-14
| ||
18:38 | Fix a typo in the documentation. Ticket #3219. (CVS 5411) (check-in: 3dc72a4617 user: drh tags: trunk) | |
15:37 | Have the rtree extension publish two virtual table types: "rtree" and "rtree_i32". rtree_i32 stores coordinate data as 32-bit signed integers. rtree uses 32-bit real (floating point) values. (CVS 5410) (check-in: c060a9a6be user: danielk1977 tags: trunk) | |
15:11 | Remove the malloc2.test script since it was designed for use in versions of SQLite that predate SQLite's ability to recover from out-of-memory errors automatically. Removing this script causes no reduction in test coverage and removes potential problems reported by ticket #3213. (CVS 5409) (check-in: 5bfc962533 user: drh tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
8 9 10 11 12 13 14 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains code for implementations of the r-tree and r*-tree ** algorithms packaged as an SQLite virtual table module. ** | | | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains code for implementations of the r-tree and r*-tree ** algorithms packaged as an SQLite virtual table module. ** ** $Id: rtree.c,v 1.6 2008/07/14 15:37:01 danielk1977 Exp $ */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) /* ** This file contains an implementation of a couple of different variants ** of the r-tree algorithm. See the README file for further details. The |
︙ | ︙ | |||
71 72 73 74 75 76 77 78 79 80 81 82 83 84 | typedef unsigned int u32; typedef struct Rtree Rtree; typedef struct RtreeCursor RtreeCursor; typedef struct RtreeNode RtreeNode; typedef struct RtreeCell RtreeCell; typedef struct RtreeConstraint RtreeConstraint; /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ #define RTREE_MAX_DIMENSIONS 5 /* Size of hash table Rtree.aHash. This hash table is not expected to ** ever contain very many entries, so a fixed number of buckets is ** used. | > | 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | typedef unsigned int u32; typedef struct Rtree Rtree; typedef struct RtreeCursor RtreeCursor; typedef struct RtreeNode RtreeNode; typedef struct RtreeCell RtreeCell; typedef struct RtreeConstraint RtreeConstraint; typedef union RtreeCoord RtreeCoord; /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ #define RTREE_MAX_DIMENSIONS 5 /* Size of hash table Rtree.aHash. This hash table is not expected to ** ever contain very many entries, so a fixed number of buckets is ** used. |
︙ | ︙ | |||
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | sqlite3_stmt *pWriteRowid; sqlite3_stmt *pDeleteRowid; /* Statements to read/write/delete a record from xxx_parent */ sqlite3_stmt *pReadParent; sqlite3_stmt *pWriteParent; sqlite3_stmt *pDeleteParent; }; /* ** The minimum number of cells allowed for a node is a third of the ** maximum. In Gutman's notation: ** ** m = M/3 ** | > > > > > > | 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | sqlite3_stmt *pWriteRowid; sqlite3_stmt *pDeleteRowid; /* Statements to read/write/delete a record from xxx_parent */ sqlite3_stmt *pReadParent; sqlite3_stmt *pWriteParent; sqlite3_stmt *pDeleteParent; int eCoordType; }; /* Possible values for eCoordType: */ #define RTREE_COORD_REAL32 0 #define RTREE_COORD_INT32 1 /* ** The minimum number of cells allowed for a node is a third of the ** maximum. In Gutman's notation: ** ** m = M/3 ** |
︙ | ︙ | |||
144 145 146 147 148 149 150 151 152 153 154 155 156 157 | sqlite3_vtab_cursor base; RtreeNode *pNode; /* Node cursor is currently pointing at */ int iCell; /* Index of current cell in pNode */ int iStrategy; /* Copy of idxNum search parameter */ int nConstraint; /* Number of entries in aConstraint */ RtreeConstraint *aConstraint; /* Search constraints. */ }; /* ** A search constraint. */ struct RtreeConstraint { int iCoord; /* Index of constrained coordinate */ int op; /* Constraining operation */ | > > > > > > > > > > > > > > > > | | 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | sqlite3_vtab_cursor base; RtreeNode *pNode; /* Node cursor is currently pointing at */ int iCell; /* Index of current cell in pNode */ int iStrategy; /* Copy of idxNum search parameter */ int nConstraint; /* Number of entries in aConstraint */ RtreeConstraint *aConstraint; /* Search constraints. */ }; union RtreeCoord { float f; int i; }; /* ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord ** formatted as a double. This macro assumes that local variable pRtree points ** to the Rtree structure associated with the RtreeCoord. */ #define DCOORD(coord) ( \ (pRtree->eCoordType==RTREE_COORD_REAL32) ? \ ((double)coord.f) : \ ((double)coord.i) \ ) /* ** A search constraint. */ struct RtreeConstraint { int iCoord; /* Index of constrained coordinate */ int op; /* Constraining operation */ double rValue; /* Constraint value. */ }; /* Possible values for RtreeConstraint.op */ #define RTREE_EQ 0x41 #define RTREE_LE 0x42 #define RTREE_LT 0x43 #define RTREE_GE 0x44 |
︙ | ︙ | |||
194 195 196 197 198 199 200 | #define NCELL(pNode) readInt16(&(pNode)->zData[2]) /* ** Structure to store a deserialized rtree record. */ struct RtreeCell { i64 iRowid; | | | | | 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 | #define NCELL(pNode) readInt16(&(pNode)->zData[2]) /* ** Structure to store a deserialized rtree record. */ struct RtreeCell { i64 iRowid; RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; }; #define MAX(x,y) ((x) < (y) ? (y) : (x)) #define MIN(x,y) ((x) > (y) ? (y) : (x)) /* ** Functions to deserialize a 16 bit integer, 32 bit real number and ** 64 bit integer. The deserialized value is returned. */ static int readInt16(u8 *p){ return (p[0]<<8) + p[1]; } static void readCoord(u8 *p, RtreeCoord *pCoord){ u32 i = ( (((u32)p[0]) << 24) + (((u32)p[1]) << 16) + (((u32)p[2]) << 8) + (((u32)p[3]) << 0) ); *(u32 *)pCoord = i; } static i64 readInt64(u8 *p){ return ( (((i64)p[0]) << 56) + (((i64)p[1]) << 48) + (((i64)p[2]) << 40) + (((i64)p[3]) << 32) + |
︙ | ︙ | |||
239 240 241 242 243 244 245 | ** to the argument buffer (always 2, 4 and 8 respectively). */ static int writeInt16(u8 *p, int i){ p[0] = (i>> 8)&0xFF; p[1] = (i>> 0)&0xFF; return 2; } | | | | | 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 | ** to the argument buffer (always 2, 4 and 8 respectively). */ static int writeInt16(u8 *p, int i){ p[0] = (i>> 8)&0xFF; p[1] = (i>> 0)&0xFF; return 2; } static int writeCoord(u8 *p, RtreeCoord *pCoord){ u32 i; assert( sizeof(RtreeCoord)==4 ); assert( sizeof(u32)==4 ); i = *(u32 *)pCoord; p[0] = (i>>24)&0xFF; p[1] = (i>>16)&0xFF; p[2] = (i>> 8)&0xFF; p[3] = (i>> 0)&0xFF; return 4; } static int writeInt64(u8 *p, i64 i){ |
︙ | ︙ | |||
424 425 426 427 428 429 430 | RtreeCell *pCell, int iCell ){ int ii; u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; p += writeInt64(p, pCell->iRowid); for(ii=0; ii<(pRtree->nDim*2); ii++){ | | | 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 | RtreeCell *pCell, int iCell ){ int ii; u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; p += writeInt64(p, pCell->iRowid); for(ii=0; ii<(pRtree->nDim*2); ii++){ p += writeCoord(p, &pCell->aCoord[ii]); } pNode->isDirty = 1; } /* ** Remove cell the cell with index iCell from node pNode. */ |
︙ | ︙ | |||
539 540 541 542 543 544 545 | assert( iCell<NCELL(pNode) ); return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); } /* ** Return coordinate iCoord from cell iCell in node pNode. */ | | | > | | | | | | | 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 | assert( iCell<NCELL(pNode) ); return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); } /* ** Return coordinate iCoord from cell iCell in node pNode. */ static void nodeGetCoord( Rtree *pRtree, RtreeNode *pNode, int iCell, int iCoord, RtreeCoord *pCoord /* Space to write result to */ ){ readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); } /* ** Deserialize cell iCell of node pNode. Populate the structure pointed ** to by pCell with the results. */ static void nodeGetCell( Rtree *pRtree, RtreeNode *pNode, int iCell, RtreeCell *pCell ){ int ii; pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); for(ii=0; ii<pRtree->nDim*2; ii++){ nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]); } } /* Forward declaration for the function that does the work of ** the virtual table module xCreate() and xConnect() methods. */ static int rtreeInit( sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int ); /* ** Rtree virtual table module xCreate method. */ static int rtreeCreate( sqlite3 *db, void *pAux, int argc, const char *const*argv, sqlite3_vtab **ppVtab, char **pzErr ){ return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux); } /* ** Rtree virtual table module xConnect method. */ static int rtreeConnect( sqlite3 *db, void *pAux, int argc, const char *const*argv, sqlite3_vtab **ppVtab, char **pzErr ){ return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux); } /* ** Increment the r-tree reference count. */ static void rtreeReference(Rtree *pRtree){ pRtree->nBusy++; |
︙ | ︙ | |||
712 713 714 715 716 717 718 719 720 | ** Return true if the sub-tree headed by the cell is filtered ** (excluded) by the constraints in the pCursor->aConstraint[] ** array, or false otherwise. */ static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){ RtreeCell cell; int ii; nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); | > | < | | | > > > | < < < < < < | < < < < < < | | < < | < < < | | < | | > > > | | | | | < < < > | 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 | ** Return true if the sub-tree headed by the cell is filtered ** (excluded) by the constraints in the pCursor->aConstraint[] ** array, or false otherwise. */ static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor){ RtreeCell cell; int ii; int bRes = 0; nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){ RtreeConstraint *p = &pCursor->aConstraint[ii]; double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]); double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]); assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE || p->op==RTREE_GT || p->op==RTREE_EQ ); switch( p->op ){ case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break; case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break; case RTREE_EQ: bRes = (p->rValue>cell_max || p->rValue<cell_min); break; } } return bRes; } /* ** Return true if the cell that cursor pCursor currently points to ** would be filtered (excluded) by the constraints in the ** pCursor->aConstraint[] array, or false otherwise. ** ** This function assumes that the cell is part of a leaf node. */ static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor){ RtreeCell cell; int ii; nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); for(ii=0; ii<pCursor->nConstraint; ii++){ RtreeConstraint *p = &pCursor->aConstraint[ii]; double coord = DCOORD(cell.aCoord[p->iCoord]); int res; assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE || p->op==RTREE_GT || p->op==RTREE_EQ ); switch( p->op ){ case RTREE_LE: res = (coord<=p->rValue); break; case RTREE_LT: res = (coord<p->rValue); break; case RTREE_GE: res = (coord>=p->rValue); break; case RTREE_GT: res = (coord>p->rValue); break; case RTREE_EQ: res = (coord==p->rValue); break; } if( !res ) return 1; } return 0; } /* |
︙ | ︙ | |||
931 932 933 934 935 936 937 | Rtree *pRtree = (Rtree *)cur->pVtab; RtreeCursor *pCsr = (RtreeCursor *)cur; if( i==0 ){ i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); sqlite3_result_int64(ctx, iRowid); }else{ | > | > | > > > > | 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 | Rtree *pRtree = (Rtree *)cur->pVtab; RtreeCursor *pCsr = (RtreeCursor *)cur; if( i==0 ){ i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); sqlite3_result_int64(ctx, iRowid); }else{ RtreeCoord c; nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c); if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ sqlite3_result_double(ctx, c.f); }else{ assert( pRtree->eCoordType==RTREE_COORD_INT32 ); sqlite3_result_int(ctx, c.i); } } return SQLITE_OK; } /* ** Use nodeAcquire() to obtain the leaf node containing the record with |
︙ | ︙ | |||
1157 1158 1159 1160 1161 1162 1163 | /* ** Return the N-dimensional volumn of the cell stored in *p. */ static float cellArea(Rtree *pRtree, RtreeCell *p){ float area = 1.0; int ii; for(ii=0; ii<(pRtree->nDim*2); ii+=2){ | | | > | | | > > > > > > | 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 | /* ** Return the N-dimensional volumn of the cell stored in *p. */ static float cellArea(Rtree *pRtree, RtreeCell *p){ float area = 1.0; int ii; for(ii=0; ii<(pRtree->nDim*2); ii+=2){ area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); } return area; } /* ** Return the margin length of cell p. The margin length is the sum ** of the objects size in each dimension. */ static float cellMargin(Rtree *pRtree, RtreeCell *p){ float margin = 0.0; int ii; for(ii=0; ii<(pRtree->nDim*2); ii+=2){ margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii])); } return margin; } /* ** Store the union of cells p1 and p2 in p1. */ static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ int ii; if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ for(ii=0; ii<(pRtree->nDim*2); ii+=2){ p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f); p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f); } }else{ for(ii=0; ii<(pRtree->nDim*2); ii+=2){ p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i); p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i); } } } /* ** Return the amount cell p would grow by if it were unioned with pCell. */ static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ |
︙ | ︙ | |||
1213 1214 1215 1216 1217 1218 1219 1220 | int ii; float overlap = 0.0; for(ii=0; ii<nCell; ii++){ if( ii!=iExclude ){ int jj; float o = 1.0; for(jj=0; jj<(pRtree->nDim*2); jj+=2){ | > > | | | 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 | int ii; float overlap = 0.0; for(ii=0; ii<nCell; ii++){ if( ii!=iExclude ){ int jj; float o = 1.0; for(jj=0; jj<(pRtree->nDim*2); jj+=2){ double x1; double x2; x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); if( x2<x1 ){ o = 0.0; break; }else{ o = o * (x2-x1); } |
︙ | ︙ | |||
1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 | ** minimum value of dimension iDim is considered first, the ** maximum used to break ties. ** ** The aSpare array is used as temporary working space by the ** sorting algorithm. */ static void SortByDimension( int *aIdx, int nIdx, int iDim, RtreeCell *aCell, int *aSpare ){ if( nIdx>1 ){ int iLeft = 0; int iRight = 0; int nLeft = nIdx/2; int nRight = nIdx-nLeft; int *aLeft = aIdx; int *aRight = &aIdx[nLeft]; | > | | | | | | < | 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 | ** minimum value of dimension iDim is considered first, the ** maximum used to break ties. ** ** The aSpare array is used as temporary working space by the ** sorting algorithm. */ static void SortByDimension( Rtree *pRtree, int *aIdx, int nIdx, int iDim, RtreeCell *aCell, int *aSpare ){ if( nIdx>1 ){ int iLeft = 0; int iRight = 0; int nLeft = nIdx/2; int nRight = nIdx-nLeft; int *aLeft = aIdx; int *aRight = &aIdx[nLeft]; SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare); SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare); memcpy(aSpare, aLeft, sizeof(int)*nLeft); aLeft = aSpare; while( iLeft<nLeft || iRight<nRight ){ double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]); double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]); double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]); double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]); if( (iLeft!=nLeft) && ((iRight==nRight) || (xleft1<xright1) || (xleft1==xright1 && xleft2<xright2) )){ aIdx[iLeft+iRight] = aLeft[iLeft]; iLeft++; }else{ |
︙ | ︙ | |||
1706 1707 1708 1709 1710 1711 1712 | memset(aaSorted, 0, nByte); for(ii=0; ii<pRtree->nDim; ii++){ int jj; aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; for(jj=0; jj<nCell; jj++){ aaSorted[ii][jj] = jj; } | | | 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 | memset(aaSorted, 0, nByte); for(ii=0; ii<pRtree->nDim; ii++){ int jj; aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; for(jj=0; jj<nCell; jj++){ aaSorted[ii][jj] = jj; } SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); } for(ii=0; ii<pRtree->nDim; ii++){ float margin = 0.0; float fBestOverlap; float fBestArea; int iBestLeft; |
︙ | ︙ | |||
2130 2131 2132 2133 2134 2135 2136 | if( ii==(nCell-1) ){ memcpy(&aCell[ii], pCell, sizeof(RtreeCell)); }else{ nodeGetCell(pRtree, pNode, ii, &aCell[ii]); } aOrder[ii] = ii; for(iDim=0; iDim<pRtree->nDim; iDim++){ | | | > | | 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 | if( ii==(nCell-1) ){ memcpy(&aCell[ii], pCell, sizeof(RtreeCell)); }else{ nodeGetCell(pRtree, pNode, ii, &aCell[ii]); } aOrder[ii] = ii; for(iDim=0; iDim<pRtree->nDim; iDim++){ aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]); aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]); } } for(iDim=0; iDim<pRtree->nDim; iDim++){ aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0); } for(ii=0; ii<nCell; ii++){ aDistance[ii] = 0.0; for(iDim=0; iDim<pRtree->nDim; iDim++){ float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) - DCOORD(aCell[ii].aCoord[iDim*2]); aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]); } } SortByDistance(aOrder, nCell, aDistance, aSpare); nodeZero(pRtree, pNode); |
︙ | ︙ | |||
2383 2384 2385 2386 2387 2388 2389 | /* Insert a new record into the r-tree */ RtreeCell cell; int ii; RtreeNode *pLeaf; /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */ assert( nData==(pRtree->nDim*2 + 3) ); | > | | | | | | > > > > > > > > > > | 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 | /* Insert a new record into the r-tree */ RtreeCell cell; int ii; RtreeNode *pLeaf; /* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */ assert( nData==(pRtree->nDim*2 + 3) ); if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ for(ii=0; ii<(pRtree->nDim*2); ii+=2){ cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]); cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]); if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){ rc = SQLITE_CONSTRAINT; goto constraint; } } }else{ for(ii=0; ii<(pRtree->nDim*2); ii+=2){ cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]); cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]); if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){ rc = SQLITE_CONSTRAINT; goto constraint; } } } /* Figure out the rowid of the new row. */ if( sqlite3_value_type(azData[2])==SQLITE_NULL ){ rc = newRowid(pRtree, &cell.iRowid); }else{ |
︙ | ︙ | |||
2584 2585 2586 2587 2588 2589 2590 | */ static int rtreeInit( sqlite3 *db, /* Database connection */ void *pAux, /* Pointer to head of rtree list */ int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ sqlite3_vtab **ppVtab, /* OUT: New virtual table */ char **pzErr, /* OUT: Error message, if any */ | | > | 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 | */ static int rtreeInit( sqlite3 *db, /* Database connection */ void *pAux, /* Pointer to head of rtree list */ int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ sqlite3_vtab **ppVtab, /* OUT: New virtual table */ char **pzErr, /* OUT: Error message, if any */ int isCreate, /* True for xCreate, false for xConnect */ int eCoordType /* One of the RTREE_COORD_* constants */ ){ int rc = SQLITE_OK; int iPageSize = 0; Rtree *pRtree; int nDb; /* Length of string argv[1] */ int nName; /* Length of string argv[2] */ |
︙ | ︙ | |||
2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 | memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); pRtree->nBusy = 1; pRtree->base.pModule = &rtreeModule; pRtree->zDb = (char *)&pRtree[1]; pRtree->zName = &pRtree->zDb[nDb+1]; pRtree->nDim = (argc-4)/2; pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2; memcpy(pRtree->zDb, argv[1], nDb); memcpy(pRtree->zName, argv[2], nName); /* Figure out the node size to use. By default, use 64 bytes less than ** the database page-size. This ensures that each node is stored on ** a single database page. ** | > | 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 | memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2); pRtree->nBusy = 1; pRtree->base.pModule = &rtreeModule; pRtree->zDb = (char *)&pRtree[1]; pRtree->zName = &pRtree->zDb[nDb+1]; pRtree->nDim = (argc-4)/2; pRtree->nBytesPerCell = 8 + pRtree->nDim*4*2; pRtree->eCoordType = eCoordType; memcpy(pRtree->zDb, argv[1], nDb); memcpy(pRtree->zName, argv[2], nName); /* Figure out the node size to use. By default, use 64 bytes less than ** the database page-size. This ensures that each node is stored on ** a single database page. ** |
︙ | ︙ | |||
2712 2713 2714 2715 2716 2717 2718 | RtreeCell cell; int jj; nodeGetCell(&tree, &node, ii, &cell); sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid); nCell = strlen(zCell); for(jj=0; jj<tree.nDim*2; jj++){ | | | 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 | RtreeCell cell; int jj; nodeGetCell(&tree, &node, ii, &cell); sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid); nCell = strlen(zCell); for(jj=0; jj<tree.nDim*2; jj++){ sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f); nCell = strlen(zCell); } if( zText ){ char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell); sqlite3_free(zText); zText = zTextNew; |
︙ | ︙ | |||
2756 2757 2758 2759 2760 2761 2762 | rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0); } if( rc==SQLITE_OK ){ int utf8 = SQLITE_UTF8; rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0); } if( rc==SQLITE_OK ){ | > | > > > > | 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 | rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0); } if( rc==SQLITE_OK ){ int utf8 = SQLITE_UTF8; rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0); } if( rc==SQLITE_OK ){ void *c = (void *)RTREE_COORD_REAL32; rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0); } if( rc==SQLITE_OK ){ void *c = (void *)RTREE_COORD_INT32; rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } #if !SQLITE_CORE int sqlite3_extension_init( |
︙ | ︙ |
Changes to ext/rtree/rtree1.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2008 Feb 19 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # The focus of this file is testing the r-tree extension. # | | > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | # 2008 Feb 19 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # The focus of this file is testing the r-tree extension. # # $Id: rtree1.test,v 1.5 2008/07/14 15:37:01 danielk1977 Exp $ # if {![info exists testdir]} { set testdir [file join [file dirname $argv0] .. .. test] } source [file join [file dirname [info script]] rtree_util.tcl] source $testdir/tester.tcl # Test plan: # # rtree-1.*: Creating/destroying r-tree tables. # rtree-2.*: Test the implicit constraints - unique rowid and # (coord[N]<=coord[N+1]) for even values of N. Also |
︙ | ︙ |
Changes to ext/rtree/rtree2.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2008 Feb 19 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # The focus of this file is testing the r-tree extension. # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 2008 Feb 19 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # The focus of this file is testing the r-tree extension. # # $Id: rtree2.test,v 1.4 2008/07/14 15:37:01 danielk1977 Exp $ # if {![info exists testdir]} { set testdir [file join [file dirname $argv0] .. .. test] } source [file join [file dirname [info script]] rtree_util.tcl] source $testdir/tester.tcl |
︙ | ︙ | |||
30 31 32 33 34 35 36 | set ::NSELECT 100 if {[info exists ISQUICK] && $ISQUICK} { set ::NROW 100 set ::NSELECT 10 } | > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | | | | | | > | 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 | set ::NSELECT 100 if {[info exists ISQUICK] && $ISQUICK} { set ::NROW 100 set ::NSELECT 10 } foreach module {rtree_i32 rtree} { for {set nDim 1} {$nDim <= 5} {incr nDim} { do_test rtree2-$module.$nDim.1 { set cols [list] foreach c [list c0 c1 c2 c3 c4 c5 c6 c7 c8 c9] { lappend cols "$c REAL" } set cols [join [lrange $cols 0 [expr {$nDim*2-1}]] ", "] execsql " CREATE VIRTUAL TABLE t1 USING ${module}(ii, $cols); CREATE TABLE t2 (ii, $cols); " } {} do_test rtree2-$module.$nDim.2 { db transaction { for {set ii 0} {$ii < $::NROW} {incr ii} { #puts "Row $ii" set values [list] for {set jj 0} {$jj<$nDim*2} {incr jj} { lappend values [expr int(rand()*1000)] } set values [join $values ,] #puts [rtree_treedump db t1] #puts "INSERT INTO t2 VALUES($ii, $values)" set rc [catch {db eval "INSERT INTO t1 VALUES($ii, $values)"}] if {$rc} { incr ii -1 } else { db eval "INSERT INTO t2 VALUES($ii, $values)" } #if {[rtree_check db t1]} { #puts [rtree_treedump db t1] #exit #} } } set t1 [execsql {SELECT * FROM t1 ORDER BY ii}] set t2 [execsql {SELECT * FROM t2 ORDER BY ii}] set rc [expr {$t1 eq $t2}] if {$rc != 1} { puts $t1 puts $t2 } set rc } {1} do_test rtree2-$module.$nDim.3 { rtree_check db t1 } 0 set OPS [list < > <= >= =] for {set ii 0} {$ii < $::NSELECT} {incr ii} { do_test rtree2-$module.$nDim.4.$ii.1 { set where [list] foreach look_three_dots! {. . .} { set colidx [expr int(rand()*($nDim*2+1))-1] if {$colidx<0} { set col ii } else { set col "c$colidx" } set op [lindex $OPS [expr int(rand()*[llength $OPS])]] set val [expr int(rand()*1000)] lappend where "$col $op $val" } set where [join $where " AND "] set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"] set t2 [execsql "SELECT * FROM t2 WHERE $where ORDER BY ii"] set rc [expr {$t1 eq $t2}] if {$rc != 1} { #puts $where puts $t1 puts $t2 #puts [rtree_treedump db t1] #breakpoint #set t1 [execsql "SELECT * FROM t1 WHERE $where ORDER BY ii"] #exit } set rc } {1} } for {set ii 0} {$ii < $::NROW} {incr ii $::NDEL} { #puts [rtree_treedump db t1] do_test rtree2-$module.$nDim.5.$ii.1 { execsql "DELETE FROM t2 WHERE ii <= $::ii" execsql "DELETE FROM t1 WHERE ii <= $::ii" set t1 [execsql {SELECT * FROM t1 ORDER BY ii}] set t2 [execsql {SELECT * FROM t2 ORDER BY ii}] set rc [expr {$t1 eq $t2}] if {$rc != 1} { puts $t1 puts $t2 } set rc } {1} do_test rtree2-$module.$nDim.5.$ii.2 { rtree_check db t1 } {0} } do_test rtree2-$module.$nDim.6 { execsql { DROP TABLE t1; DROP TABLE t2; } } {} } } finish_test |
Added ext/rtree/rtree5.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | # 2008 Jul 14 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # The focus of this file is testing the r-tree extension when it is # configured to store values as 32 bit integers. # # $Id: rtree5.test,v 1.1 2008/07/14 15:37:01 danielk1977 Exp $ # if {![info exists testdir]} { set testdir [file join [file dirname $argv0] .. .. test] } source $testdir/tester.tcl ifcapable !rtree { finish_test return } do_test rtree5-1.0 { execsql { CREATE VIRTUAL TABLE t1 USING rtree_i32(id, x1, x2, y1, y2) } } {} do_test rtree5-1.1 { execsql { INSERT INTO t1 VALUES(1, 5, 10, 4, 11.2) } } {} do_test rtree5-1.2 { execsql { SELECT * FROM t1 } } {1 5 10 4 11} do_test rtree5-1.3 { execsql { SELECT typeof(x1) FROM t1 } } {integer} do_test rtree5-1.4 { execsql { SELECT x1==5 FROM t1 } } {1} do_test rtree5-1.5 { execsql { SELECT x1==5.2 FROM t1 } } {0} do_test rtree5-1.6 { execsql { SELECT x1==5.0 FROM t1 } } {1} do_test rtree5-1.7 { execsql { SELECT count(*) FROM t1 WHERE x1==5 } } {1} do_test rtree5-1.8 { execsql { SELECT count(*) FROM t1 WHERE x1==5.2 } } {0} do_test rtree5-1.9 { execsql { SELECT count(*) FROM t1 WHERE x1==5.0 } } {1} do_test rtree5-1.10 { execsql { SELECT (1<<31)-5, (1<<31)-1, -1*(1<<31), -1*(1<<31)+5 } } {2147483643 2147483647 -2147483648 -2147483643} do_test rtree5-1.10 { execsql { INSERT INTO t1 VALUES(2, (1<<31)-5, (1<<31)-1, -1*(1<<31), -1*(1<<31)+5) } } {} do_test rtree5-1.12 { execsql { SELECT * FROM t1 WHERE id=2 } } {2 2147483643 2147483647 -2147483648 -2147483643} do_test rtree5-1.13 { execsql { SELECT * FROM t1 WHERE x1=2147483643 AND x2=2147483647 AND y1=-2147483648 AND y2=-2147483643 } } {2 2147483643 2147483647 -2147483648 -2147483643} finish_test |