/ Check-in [8b600ed0]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix a bug in r-tree related to internal nodes with one or more dimensions of size zero. Ticket #3363. (CVS 5682)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:8b600ed083d48784df4b1da1320a01bebbf233d7
User & Date: danielk1977 2008-09-08 11:07:03
Context
2008-09-08
15:35
Fix a C++ism in pager.c (variable useAtomicWrite not declard at the top of its scope). (CVS 5683) check-in: a6dee85b user: danielk1977 tags: trunk
11:07
Fix a bug in r-tree related to internal nodes with one or more dimensions of size zero. Ticket #3363. (CVS 5682) check-in: 8b600ed0 user: danielk1977 tags: trunk
09:06
If the 'rootpage' column of the sqlite_master table contains a NULL value, return SQLITE_CORRUPT to the caller. (CVS 5681) check-in: a7b7b126 user: danielk1977 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
....
1219
1220
1221
1222
1223
1224
1225



















1226
1227
1228
1229
1230
1231
1232
....
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
**    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.8 2008/09/01 12:47:00 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 
................................................................................
  }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){
  float area;
  RtreeCell cell;
................................................................................
  RtreeNode *p = pNode;
  while( p->pParent ){
    RtreeCell cell;
    RtreeNode *pParent = p->pParent;
    int iCell = nodeParentIndex(pRtree, p);

    nodeGetCell(pRtree, pParent, iCell, &cell);
    if( cellGrowth(pRtree, &cell, pCell)>0.0 ){
      cellUnion(pRtree, &cell, pCell);
      nodeOverwriteCell(pRtree, pParent, &cell, iCell);
    }
 
    p = pParent;
  }
}







|







 







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







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
....
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
**    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.9 2008/09/08 11:07:03 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 
................................................................................
  }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;
    }
  }
  return 1;
}

/*
** Return the amount cell p would grow by if it were unioned with pCell.
*/
static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
  float area;
  RtreeCell cell;
................................................................................
  RtreeNode *p = pNode;
  while( p->pParent ){
    RtreeCell cell;
    RtreeNode *pParent = p->pParent;
    int iCell = nodeParentIndex(pRtree, p);

    nodeGetCell(pRtree, pParent, iCell, &cell);
    if( !cellContains(pRtree, &cell, pCell) ){
      cellUnion(pRtree, &cell, pCell);
      nodeOverwriteCell(pRtree, pParent, &cell, iCell);
    }
 
    p = pParent;
  }
}

Added ext/rtree/tkt3363.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
# 2008 Sep 08
#
# 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 that ticket #3363 is fixed.
#
# $Id: tkt3363.test,v 1.1 2008/09/08 11:07:03 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

ifcapable !rtree {
  finish_test
  return
}

do_test tkt3363.1.1 {
  execsql { CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2) }
} {}

do_test tkt3363.1.2 {
  for {set ii 1} {$ii < 50} {incr ii} {
    set x 1000000
    set y [expr 4000000 + $ii*10]
    execsql { INSERT INTO t1 VALUES($ii, $x, $x, $y, $y) }
  }
} {}

do_test tkt3363.1.3 {
  execsql { 
    SELECT count(*) FROM t1 WHERE +y2>4000425.0;
  }
} {7}

do_test tkt3363.1.4 {
  execsql { 
    SELECT count(*) FROM t1 WHERE y2>4000425.0;
  }
} {7}

finish_test