/ Check-in [c060a9a6]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:c060a9a6beca455bdceee9ce6ca71a7262f98a5f
User & Date: danielk1977 2008-07-14 15:37:01
Context
2008-07-14
18:38
Fix a typo in the documentation. Ticket #3219. (CVS 5411) check-in: 3dc72a46 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: c060a9a6 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: 5bfc9625 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
71
72
73
74
75
76
77

78
79
80
81
82
83
84
...
118
119
120
121
122
123
124


125




126
127
128
129
130
131
132
...
144
145
146
147
148
149
150
















151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
...
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
...
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
...
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
...
539
540
541
542
543
544
545
546
547
548
549
550

551
552
553
554
555
556
557
558
559
...
561
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
...
712
713
714
715
716
717
718

719
720
721
722
723
724
725
726
727




728
729
730
731
732
733
734
735
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
...
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
...
931
932
933
934
935
936
937

938

939




940
941
942
943
944
945
946
....
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186

1187
1188
1189






1190
1191
1192
1193
1194
1195
1196
....
1213
1214
1215
1216
1217
1218
1219


1220
1221
1222


1223
1224
1225
1226
1227
1228
1229
....
1615
1616
1617
1618
1619
1620
1621

1622
1623
1624
1625
1626
1627
1628
....
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
....
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
....
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147

2148
2149
2150
2151
2152
2153
2154
2155
....
2383
2384
2385
2386
2387
2388
2389

2390
2391
2392
2393
2394
2395










2396
2397
2398
2399
2400
2401
2402
....
2584
2585
2586
2587
2588
2589
2590
2591

2592
2593
2594
2595
2596
2597
2598
....
2624
2625
2626
2627
2628
2629
2630

2631
2632
2633
2634
2635
2636
2637
....
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
....
2756
2757
2758
2759
2760
2761
2762

2763




2764
2765
2766
2767
2768
2769
2770
**    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.5 2008/06/23 15:55:52 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 
................................................................................
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.
................................................................................
  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
**
................................................................................
  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 */
  float rValue;                     /* Constraint value. */
};

/* Possible values for RtreeConstraint.op */
#define RTREE_EQ 0x41
#define RTREE_LE 0x42
#define RTREE_LT 0x43
#define RTREE_GE 0x44
................................................................................
#define NCELL(pNode) readInt16(&(pNode)->zData[2])

/* 
** Structure to store a deserialized rtree record.
*/
struct RtreeCell {
  i64 iRowid;
  float 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 float readReal32(u8 *p){
  u32 i = (
    (((u32)p[0]) << 24) + 
    (((u32)p[1]) << 16) + 
    (((u32)p[2]) <<  8) + 
    (((u32)p[3]) <<  0)
  );
  return *(float *)&i;
}
static i64 readInt64(u8 *p){
  return (
    (((i64)p[0]) << 56) + 
    (((i64)p[1]) << 48) + 
    (((i64)p[2]) << 40) + 
    (((i64)p[3]) << 32) + 
................................................................................
** 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 writeReal32(u8 *p, float f){
  u32 i;
  assert( sizeof(float)==4 );
  assert( sizeof(u32)==4 );
  i = *(u32 *)&f;
  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){
................................................................................
  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 += writeReal32(p, pCell->aCoord[ii]);
  }
  pNode->isDirty = 1;
}

/*
** Remove cell the cell with index iCell from node pNode.
*/
................................................................................
  assert( iCell<NCELL(pNode) );
  return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
}

/*
** Return coordinate iCoord from cell iCell in node pNode.
*/
static float nodeGetCoord(
  Rtree *pRtree, 
  RtreeNode *pNode, 
  int iCell,
  int iCoord

){
  return readReal32(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord]);
}

/*
** Deserialize cell iCell of node pNode. Populate the structure pointed
** to by pCell with the results.
*/
static void nodeGetCell(
................................................................................
  RtreeNode *pNode, 
  int iCell,
  RtreeCell *pCell
){
  int ii;
  pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
  for(ii=0; ii<pRtree->nDim*2; ii++){
    pCell->aCoord[ii] = nodeGetCoord(pRtree, pNode, iCell, 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
);

/* 
** 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);
}

/* 
** 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);
}

/*
** Increment the r-tree reference count.
*/
static void rtreeReference(Rtree *pRtree){
  pRtree->nBusy++;
................................................................................
** 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);
  for(ii=0; ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];

    float cell_min = cell.aCoord[(p->iCoord>>1)*2];
    float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
    assert( cell_min<=cell_max );





    switch( p->op ){
      case RTREE_LE: case RTREE_LT: {
        if( p->rValue<cell_min ){
          return 1;
        }
        break;
      }

      case RTREE_GE: case RTREE_GT: {
        if( p->rValue>cell_max ){
          return 1;
        }
        break;
      }

      case RTREE_EQ: {
        if( p->rValue>cell_max || p->rValue<cell_min ){
          return 1;
        }
        break;
      }
#ifndef NDEBUG
      default: assert(!"Internal error");
#endif
    }
  }

  return 0;
}

/* 
** 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.
**
................................................................................
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];
    float cell_val = cell.aCoord[p->iCoord];
    int res;



    switch( p->op ){
      case RTREE_LE: res = (cell_val<=p->rValue); break;
      case RTREE_LT: res = (cell_val<p->rValue);  break;
      case RTREE_GE: res = (cell_val>=p->rValue); break;
      case RTREE_GT: res = (cell_val>p->rValue);  break;
      case RTREE_EQ: res = (cell_val==p->rValue); break;
#ifndef NDEBUG
      default: assert(!"Internal error");
#endif
    }

    if( !res ) return 1;
  }

  return 0;
}

/*
................................................................................
  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{

    float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1);

    sqlite3_result_double(ctx, fCoord);




  }

  return SQLITE_OK;
}

/* 
** Use nodeAcquire() to obtain the leaf node containing the record with 
................................................................................
/*
** 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 * (p->aCoord[ii+1] - 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 += (p->aCoord[ii+1] - 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;

  for(ii=0; ii<(pRtree->nDim*2); ii+=2){
    p1->aCoord[ii] = MIN(p1->aCoord[ii], p2->aCoord[ii]);
    p1->aCoord[ii+1] = MAX(p1->aCoord[ii+1], p2->aCoord[ii+1]);






  }
}

/*
** Return the amount cell p would grow by if it were unioned with pCell.
*/
static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
................................................................................
  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){



        float x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]);
        float x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord[jj+1]);



        if( x2<x1 ){
          o = 0.0;
          break;
        }else{
          o = o * (x2-x1);
        }
................................................................................
** 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 iRight = 0;

    int nLeft = nIdx/2;
    int nRight = nIdx-nLeft;
    int *aLeft = aIdx;
    int *aRight = &aIdx[nLeft];

    SortByDimension(aLeft, nLeft, iDim, aCell, aSpare);
    SortByDimension(aRight, nRight, iDim, aCell, aSpare);

    memcpy(aSpare, aLeft, sizeof(int)*nLeft);
    aLeft = aSpare;
    while( iLeft<nLeft || iRight<nRight ){
      float xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2];
      float xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1];
      float xright1 = aCell[aRight[iRight]].aCoord[iDim*2];
      float xright2 = 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{
................................................................................
  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(aaSorted[ii], nCell, ii, aCell, aSpare);
  }

  for(ii=0; ii<pRtree->nDim; ii++){
    float margin = 0.0;
    float fBestOverlap;
    float fBestArea;
    int iBestLeft;
................................................................................
    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] += aCell[ii].aCoord[iDim*2];
      aCenterCoord[iDim] += 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 = aCell[ii].aCoord[iDim*2+1] - aCell[ii].aCoord[iDim*2];
      aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
    }
  }

  SortByDistance(aOrder, nCell, aDistance, aSpare);
  nodeZero(pRtree, pNode);

................................................................................
    /* 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) );

    for(ii=0; ii<(pRtree->nDim*2); ii+=2){
      cell.aCoord[ii] = (float)sqlite3_value_double(azData[ii+3]);
      cell.aCoord[ii+1] = (float)sqlite3_value_double(azData[ii+4]);
      if( cell.aCoord[ii]>cell.aCoord[ii+1] ){
        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{
................................................................................
*/
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 rc = SQLITE_OK;
  int iPageSize = 0;
  Rtree *pRtree;
  int nDb;              /* Length of string argv[1] */
  int nName;            /* Length of string argv[2] */

................................................................................
  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.
  **
................................................................................
    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]);
      nCell = strlen(zCell);
    }

    if( zText ){
      char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
      sqlite3_free(zText);
      zText = zTextNew;
................................................................................
    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 ){

    rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, 0, 0);




  }

  return rc;
}

#if !SQLITE_CORE
int sqlite3_extension_init(







|







 







>







 







>
>

>
>
>
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







|







 







|












|






|







 







|

|

|







 







|







 







|



|
>

|







 







|




|



|












|












|







 







>


|

<
|
|
<

>
>
>
>

|
<
<
<
<
<
<
|
<
<
<
<
<
<
|
|
<
<

<
<
<
<



|







 







|

>
>
>

|
|
|
|
|
<
<
<

>







 







>
|
>
|
>
>
>
>







 







|












|









>
|
|
|
>
>
>
>
>
>







 







>
>

<
<
>
>







 







>







 







|
|




|
|
|
|
<







 







|







 







|
|









>
|







 







>
|
|
|
|
|
|
>
>
>
>
>
>
>
>
>
>







 







|
>







 







>







 







|







 







>
|
>
>
>
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
..
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
...
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
...
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
...
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
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
...
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
...
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
...
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
...
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
...
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
...
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
....
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
....
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245


1246
1247
1248
1249
1250
1251
1252
1253
1254
....
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
....
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673

1674
1675
1676
1677
1678
1679
1680
....
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
....
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
....
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
....
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
....
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
....
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
....
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
**    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 
................................................................................
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.
................................................................................
  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
**
................................................................................
  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
................................................................................
#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) + 
................................................................................
** 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){
................................................................................
  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.
*/
................................................................................
  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(
................................................................................
  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++;
................................................................................
** 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.
**
................................................................................
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;
}

/*
................................................................................
  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 
................................................................................
/*
** 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){
................................................................................
  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);
        }
................................................................................
** 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 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{
................................................................................
  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;
................................................................................
    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);

................................................................................
    /* 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{
................................................................................
*/
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] */

................................................................................
  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.
  **
................................................................................
    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;
................................................................................
    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.

7
8
9
10
11
12
13
14
15
16
17
18
19

20
21
22
23
24
25
26
#    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.4 2008/06/23 16:53:47 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
}

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







|





>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#    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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
#    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.3 2008/06/23 15:55:52 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
................................................................................
set ::NSELECT 100

if {[info exists ISQUICK] && $ISQUICK} {
  set ::NROW 100
  set ::NSELECT 10
}


for {set nDim 1} {$nDim <= 5} {incr nDim} {

  do_test rtree2-$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 rtree(ii, $cols);
      CREATE TABLE t2 (ii, $cols);
    "
  } {}

  do_test rtree2-$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-$nDim.3 {
    rtree_check db t1
  } 0

  set OPS [list < > <= >= =]
  for {set ii 0} {$ii < $::NSELECT} {incr ii} {
    do_test rtree2-$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-$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-$nDim.5.$ii.2 {
      rtree_check db t1




















































    } {0}
  }

  do_test rtree2-$nDim.6 {
    execsql {
      DROP TABLE t1;
      DROP TABLE t2;
    }
  } {}

}

finish_test







|







 







>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<









>
|

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
|
|
|
|
|
|
|
>



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
#    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
................................................................................
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