Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Precompute the nDim2 value in the Rtree object and use that to make loops over coordinates faster. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
f1f3c8cc733a05c12dd980f2dfa0ab4c |
| User & Date: | drh 2017-02-01 15:49:02 |
Context
|
2017-02-01
| ||
| 16:41 | Completely unroll the dimension loop inside of cellArea() in RTREE. (check-in: 3c4c0126 user: drh tags: trunk) | |
| 15:49 | Precompute the nDim2 value in the Rtree object and use that to make loops over coordinates faster. (check-in: f1f3c8cc user: drh tags: trunk) | |
| 15:24 | Use compiler intrinsic functions (when available) for byteswapping in RTREE. (check-in: 82fcd54a user: drh tags: trunk) | |
Changes
Changes to ext/rtree/rtree.c.
112 113 114 115 116 117 118 119 120 121 122 123 124 125 ... 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 ... 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 .... 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 .... 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 .... 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 .... 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 .... 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 .... 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 |
** An rtree virtual-table object.
*/
struct Rtree {
sqlite3_vtab base; /* Base class. Must be first */
sqlite3 *db; /* Host database connection */
int iNodeSize; /* Size in bytes of each node in the node table */
u8 nDim; /* Number of dimensions */
u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
u8 nBytesPerCell; /* Bytes consumed per cell */
int iDepth; /* Current depth of the r-tree structure */
char *zDb; /* Name of database containing r-tree table */
char *zName; /* Name of r-tree table */
int nBusy; /* Current number of users of this structure */
i64 nRowEst; /* Estimated number of rows in this table */
................................................................................
RtreeNode *pNode, /* The node into which the cell is to be written */
RtreeCell *pCell, /* The cell to write */
int iCell /* Index into pNode into which pCell is written */
){
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 the cell with index iCell from node pNode.
................................................................................
pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
pCoord = pCell->aCoord;
do{
readCoord(pData, &pCoord[ii]);
readCoord(pData+4, &pCoord[ii+1]);
pData += 8;
ii += 2;
}while( ii<pRtree->nDim*2 );
}
/* Forward declaration for the function that does the work of
** the virtual table module xCreate() and xConnect() methods.
*/
static int rtreeInit(
................................................................................
** can be cast into an RtreeMatchArg object. One created using
** an sqlite3_rtree_geometry_callback() SQL user function.
*/
rc = deserializeGeometry(argv[ii], p);
if( rc!=SQLITE_OK ){
break;
}
p->pInfo->nCoord = pRtree->nDim*2;
p->pInfo->anQueue = pCsr->anQueue;
p->pInfo->mxLevel = pRtree->iDepth + 1;
}else{
#ifdef SQLITE_RTREE_INT_ONLY
p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
p->u.rValue = sqlite3_value_double(argv[ii]);
................................................................................
return rc;
}
/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){
RtreeDValue area = (RtreeDValue)1;
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 RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
RtreeDValue margin = (RtreeDValue)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 true if the area covered by p2 is a subset of the area covered
** by p1. False otherwise.
*/
static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
int ii;
int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
for(ii=0; ii<(pRtree->nDim*2); ii+=2){
RtreeCoord *a1 = &p1->aCoord[ii];
RtreeCoord *a2 = &p2->aCoord[ii];
if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f))
|| ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i))
){
return 0;
}
................................................................................
int nCell
){
int ii;
RtreeDValue overlap = RTREE_ZERO;
for(ii=0; ii<nCell; ii++){
int jj;
RtreeDValue o = (RtreeDValue)1;
for(jj=0; jj<(pRtree->nDim*2); jj+=2){
RtreeDValue x1, 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 = (RtreeDValue)0;
break;
}else{
................................................................................
**
** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
** with "column" that are interpreted as table constraints.
** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
** This problem was discovered after years of use, so we silently ignore
** these kinds of misdeclared tables to avoid breaking any legacy.
*/
assert( nData<=(pRtree->nDim*2 + 3) );
#ifndef SQLITE_RTREE_INT_ONLY
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
for(ii=0; ii<nData-4; ii+=2){
cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]);
cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]);
if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
................................................................................
}
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. */
rc = getNodeSize(db, pRtree, isCreate, pzErr);
................................................................................
Rtree tree;
int ii;
UNUSED_PARAMETER(nArg);
memset(&node, 0, sizeof(RtreeNode));
memset(&tree, 0, sizeof(Rtree));
tree.nDim = sqlite3_value_int(apArg[0]);
tree.nBytesPerCell = 8 + 8 * tree.nDim;
node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
for(ii=0; ii<NCELL(&node); ii++){
char zCell[512];
int nCell = 0;
RtreeCell cell;
int jj;
nodeGetCell(&tree, &node, ii, &cell);
sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
nCell = (int)strlen(zCell);
for(jj=0; jj<tree.nDim*2; jj++){
#ifndef SQLITE_RTREE_INT_ONLY
sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
(double)cell.aCoord[jj].f);
#else
sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
cell.aCoord[jj].i);
#endif
|
> | | | | | > | | | > | | < > > < > < > > | | | > | > | |
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 ... 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 ... 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 .... 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 .... 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 .... 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 .... 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 .... 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 .... 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 |
** An rtree virtual-table object.
*/
struct Rtree {
sqlite3_vtab base; /* Base class. Must be first */
sqlite3 *db; /* Host database connection */
int iNodeSize; /* Size in bytes of each node in the node table */
u8 nDim; /* Number of dimensions */
u8 nDim2; /* Twice the number of dimensions */
u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
u8 nBytesPerCell; /* Bytes consumed per cell */
int iDepth; /* Current depth of the r-tree structure */
char *zDb; /* Name of database containing r-tree table */
char *zName; /* Name of r-tree table */
int nBusy; /* Current number of users of this structure */
i64 nRowEst; /* Estimated number of rows in this table */
................................................................................
RtreeNode *pNode, /* The node into which the cell is to be written */
RtreeCell *pCell, /* The cell to write */
int iCell /* Index into pNode into which pCell is written */
){
int ii;
u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
p += writeInt64(p, pCell->iRowid);
for(ii=0; ii<pRtree->nDim2; ii++){
p += writeCoord(p, &pCell->aCoord[ii]);
}
pNode->isDirty = 1;
}
/*
** Remove the cell with index iCell from node pNode.
................................................................................
pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
pCoord = pCell->aCoord;
do{
readCoord(pData, &pCoord[ii]);
readCoord(pData+4, &pCoord[ii+1]);
pData += 8;
ii += 2;
}while( ii<pRtree->nDim2 );
}
/* Forward declaration for the function that does the work of
** the virtual table module xCreate() and xConnect() methods.
*/
static int rtreeInit(
................................................................................
** can be cast into an RtreeMatchArg object. One created using
** an sqlite3_rtree_geometry_callback() SQL user function.
*/
rc = deserializeGeometry(argv[ii], p);
if( rc!=SQLITE_OK ){
break;
}
p->pInfo->nCoord = pRtree->nDim2;
p->pInfo->anQueue = pCsr->anQueue;
p->pInfo->mxLevel = pRtree->iDepth + 1;
}else{
#ifdef SQLITE_RTREE_INT_ONLY
p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
p->u.rValue = sqlite3_value_double(argv[ii]);
................................................................................
return rc;
}
/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
static RtreeDValue cellArea(Rtree *pRtree, RtreeCell *p){
RtreeDValue area;
int ii;
area = DCOORD(p->aCoord[1]) - DCOORD(p->aCoord[0]);
for(ii=2; ii<pRtree->nDim2; ii+=2){
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 RtreeDValue cellMargin(Rtree *pRtree, RtreeCell *p){
RtreeDValue margin;
int ii;
margin = DCOORD(p->aCoord[1]) - DCOORD(p->aCoord[0]);
for(ii=2; ii<pRtree->nDim2; 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 = 0;
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
do{
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);
ii += 2;
}while( ii<pRtree->nDim2 );
}else{
do{
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);
ii += 2;
}while( ii<pRtree->nDim2 );
}
}
/*
** Return true if the area covered by p2 is a subset of the area covered
** by p1. False otherwise.
*/
static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){
int ii;
int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
for(ii=0; ii<pRtree->nDim2; ii+=2){
RtreeCoord *a1 = &p1->aCoord[ii];
RtreeCoord *a2 = &p2->aCoord[ii];
if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f))
|| ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i))
){
return 0;
}
................................................................................
int nCell
){
int ii;
RtreeDValue overlap = RTREE_ZERO;
for(ii=0; ii<nCell; ii++){
int jj;
RtreeDValue o = (RtreeDValue)1;
for(jj=0; jj<pRtree->nDim2; jj+=2){
RtreeDValue x1, 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 = (RtreeDValue)0;
break;
}else{
................................................................................
**
** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
** with "column" that are interpreted as table constraints.
** Example: CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
** This problem was discovered after years of use, so we silently ignore
** these kinds of misdeclared tables to avoid breaking any legacy.
*/
assert( nData<=(pRtree->nDim2 + 3) );
#ifndef SQLITE_RTREE_INT_ONLY
if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
for(ii=0; ii<nData-4; ii+=2){
cell.aCoord[ii].f = rtreeValueDown(azData[ii+3]);
cell.aCoord[ii+1].f = rtreeValueUp(azData[ii+4]);
if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
................................................................................
}
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->nDim2 = argc - 4;
pRtree->nBytesPerCell = 8 + pRtree->nDim2*4;
pRtree->eCoordType = eCoordType;
memcpy(pRtree->zDb, argv[1], nDb);
memcpy(pRtree->zName, argv[2], nName);
/* Figure out the node size to use. */
rc = getNodeSize(db, pRtree, isCreate, pzErr);
................................................................................
Rtree tree;
int ii;
UNUSED_PARAMETER(nArg);
memset(&node, 0, sizeof(RtreeNode));
memset(&tree, 0, sizeof(Rtree));
tree.nDim = sqlite3_value_int(apArg[0]);
tree.nDim2 = tree.nDim*2;
tree.nBytesPerCell = 8 + 8 * tree.nDim;
node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
for(ii=0; ii<NCELL(&node); ii++){
char zCell[512];
int nCell = 0;
RtreeCell cell;
int jj;
nodeGetCell(&tree, &node, ii, &cell);
sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
nCell = (int)strlen(zCell);
for(jj=0; jj<tree.nDim2; jj++){
#ifndef SQLITE_RTREE_INT_ONLY
sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
(double)cell.aCoord[jj].f);
#else
sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
cell.aCoord[jj].i);
#endif
|