Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Further improvements to the RTREE_DECODE_COORD() method, to take advantage of known processor byte orders when available. This makes the code 3% faster, according to valgrind. Also add test cases to make sure the on-disk representation is correct. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | rtree-enhancements |
| Files: | files | file ages | folders |
| SHA1: |
6f3e94f4b1b403cd7bfc5e8e0ffbd61b |
| User & Date: | drh 2014-04-18 01:37:08 |
Context
|
2014-04-21
| ||
| 15:21 | Fix an off-by-one error in setting the "iLevel" field of the sqlite3_rtree_query_info structure passed into the RTree query callback. check-in: d708f159 user: drh tags: rtree-enhancements | |
|
2014-04-18
| ||
| 01:37 | Further improvements to the RTREE_DECODE_COORD() method, to take advantage of known processor byte orders when available. This makes the code 3% faster, according to valgrind. Also add test cases to make sure the on-disk representation is correct. check-in: 6f3e94f4 user: drh tags: rtree-enhancements | |
| 01:14 | Merge the latest changes from sessions. check-in: d9eef5b0 user: drh tags: rtree-enhancements | |
Changes
Changes to ext/rtree/rtree.c.
900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 .... 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 .... 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 |
static int rtreeEof(sqlite3_vtab_cursor *cur){
RtreeCursor *pCsr = (RtreeCursor *)cur;
return pCsr->atEOF;
}
/*
** Convert raw bits from the on-disk RTree record into a coordinate value.
** The on-disk format is big-endian and needs to be converted for little-endian
** platforms. The on-disk record stores integer coordinates if eInt is true
** and it stores 32-bit floating point records if eInt is false. a[] is the four
** bytes of the on-disk record to be decoded. Store the results in "r".
**
** The first version of this macro is fast on x86, x86_64 and ARM, all of which
** are little-endian. The second version of this macro is cross-platform but
** takes twice as long, according to valgrind on linux x64.
*/
#if defined(__x86) || defined(__x86_64) || defined(__arm__) || defined(_MSC_VER)
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
memcpy(&c.u,a,4); \
c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#else
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
+((u32)a[2]<<8) + a[3]; \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#endif
/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.
*/
static int rtreeCallbackConstraint(
RtreeConstraint *pConstraint, /* The constraint to test */
................................................................................
rc = SQLITE_NOMEM;
goto splitnode_out;
}
memset(pLeft->zData, 0, pRtree->iNodeSize);
memset(pRight->zData, 0, pRtree->iNodeSize);
rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,&leftbbox,&rightbbox);
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
/* Ensure both child nodes have node numbers assigned to them by calling
** nodeWrite(). Node pRight always needs a node number, as it was created
** by nodeNew() above. But node pLeft sometimes already has a node number.
................................................................................
pRtree->db = db;
if( isCreate ){
char *zCreate = sqlite3_mprintf(
"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
);
if( !zCreate ){
return SQLITE_NOMEM;
}
rc = sqlite3_exec(db, zCreate, 0, 0, 0);
|
| | | | > < | | > > > > > < > > > > > > > < | > | > |
900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 .... 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 .... 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 |
static int rtreeEof(sqlite3_vtab_cursor *cur){
RtreeCursor *pCsr = (RtreeCursor *)cur;
return pCsr->atEOF;
}
/*
** Convert raw bits from the on-disk RTree record into a coordinate value.
** The on-disk format is big-endian and needs to be converted for little-
** endian platforms. The on-disk record stores integer coordinates if
** eInt is true and it stores 32-bit floating point records if eInt is
** false. a[] is the four bytes of the on-disk record to be decoded.
** Store the results in "r".
**
** There are three versions of this macro, one each for little-endian and
** big-endian processors and a third generic implementation. The endian-
** specific implementations are much faster and are preferred if the
** processor endianness is known at compile-time. The SQLITE_BYTEORDER
** macro is part of sqliteInt.h and hence the endian-specific
** implementation will only be used if this module is compiled as part
** of the amalgamation.
*/
#if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
memcpy(&c.u,a,4); \
c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \
((c.u&0xff)<<24)|((c.u&0xff00)<<8); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
memcpy(&c.u,a,4); \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#else
#define RTREE_DECODE_COORD(eInt, a, r) { \
RtreeCoord c; /* Coordinate decoded */ \
c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \
+((u32)a[2]<<8) + a[3]; \
r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#endif
/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.
*/
static int rtreeCallbackConstraint(
RtreeConstraint *pConstraint, /* The constraint to test */
................................................................................
rc = SQLITE_NOMEM;
goto splitnode_out;
}
memset(pLeft->zData, 0, pRtree->iNodeSize);
memset(pRight->zData, 0, pRtree->iNodeSize);
rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
&leftbbox, &rightbbox);
if( rc!=SQLITE_OK ){
goto splitnode_out;
}
/* Ensure both child nodes have node numbers assigned to them by calling
** nodeWrite(). Node pRight always needs a node number, as it was created
** by nodeNew() above. But node pLeft sometimes already has a node number.
................................................................................
pRtree->db = db;
if( isCreate ){
char *zCreate = sqlite3_mprintf(
"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
" parentnode INTEGER);"
"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
);
if( !zCreate ){
return SQLITE_NOMEM;
}
rc = sqlite3_exec(db, zCreate, 0, 0, 0);
|
Changes to ext/rtree/rtree1.test.
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
...
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
|
}
return $out
}
# Test that it is possible to open an existing database that contains
# r-tree tables.
#
do_test rtree-1.4.1 {
execsql {
CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
INSERT INTO t1 VALUES(1, 5.0, 10.0);
INSERT INTO t1 VALUES(2, 15.0, 20.0);
}
} {}
do_test rtree-1.4.2 {
db close
sqlite3 db test.db
execsql_intout { SELECT * FROM t1 ORDER BY ii }
} {1 5 10 2 15 20}
do_test rtree-1.4.3 {
................................................................................
}
} {2}
#-------------------------------------------------------------------------
# Test on-conflict clause handling.
#
db_delete_and_reopen
do_execsql_test 12.0 {
CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
INSERT INTO t1 VALUES(1, 1, 2, 3, 4);
INSERT INTO t1 VALUES(2, 2, 3, 4, 5);
INSERT INTO t1 VALUES(3, 3, 4, 5, 6);
CREATE TABLE source(idx, x1, x2, y1, y2);
INSERT INTO source VALUES(5, 8, 8, 8, 8);
INSERT INTO source VALUES(2, 7, 7, 7, 7);
}
db_save_and_close
foreach {tn sql_template testdata} {
1 "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" {
ROLLBACK 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6}
ABORT 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7}
IGNORE 0 0 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7}
|
|
<
|
|
>
>
>
|
<
|
>
>
>
<
|
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
...
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
|
} return $out } # Test that it is possible to open an existing database that contains # r-tree tables. # do_execsql_test rtree-1.4.1a { CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2); INSERT INTO t1 VALUES(1, 5.0, 10.0); SELECT substr(hex(data),1,40) FROM t1_node; } {00000001000000000000000140A0000041200000} do_execsql_test rtree-1.4.1b { INSERT INTO t1 VALUES(2, 15.0, 20.0); } {} do_test rtree-1.4.2 { db close sqlite3 db test.db execsql_intout { SELECT * FROM t1 ORDER BY ii } } {1 5 10 2 15 20} do_test rtree-1.4.3 { ................................................................................ } } {2} #------------------------------------------------------------------------- # Test on-conflict clause handling. # db_delete_and_reopen do_execsql_test 12.0.1 { CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2); INSERT INTO t1 VALUES(1, 1, 2, 3, 4); SELECT substr(hex(data),1,56) FROM t1_node; } {00000001000000000000000100000001000000020000000300000004} do_execsql_test 12.0.2 { INSERT INTO t1 VALUES(2, 2, 3, 4, 5); INSERT INTO t1 VALUES(3, 3, 4, 5, 6); CREATE TABLE source(idx, x1, x2, y1, y2); INSERT INTO source VALUES(5, 8, 8, 8, 8); INSERT INTO source VALUES(2, 7, 7, 7, 7); } db_save_and_close foreach {tn sql_template testdata} { 1 "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" { ROLLBACK 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6} ABORT 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7} IGNORE 0 0 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7} |