Symaptic: os/persistentdata/persistentstorage/sqlite3api/SQLite/rtree.c@260cb5ec6c19 (annotated)

sl@0	1	/*
sl@0	2	** 2001 September 15
sl@0	3	**
sl@0	4	** The author disclaims copyright to this source code. In place of
sl@0	5	** a legal notice, here is a blessing:
sl@0	6	**
sl@0	7	** May you do good and not evil.
sl@0	8	** May you find forgiveness for yourself and forgive others.
sl@0	9	** May you share freely, never taking more than you give.
sl@0	10	**
sl@0	11	*************************************************************************
sl@0	12	** This file contains code for implementations of the r-tree and r*-tree
sl@0	13	** algorithms packaged as an SQLite virtual table module.
sl@0	14	**
sl@0	15	** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $
sl@0	16	*/
sl@0	17
sl@0	18	#if !defined(SQLITE_CORE) \|\| defined(SQLITE_ENABLE_RTREE)
sl@0	19
sl@0	20	/*
sl@0	21	** This file contains an implementation of a couple of different variants
sl@0	22	** of the r-tree algorithm. See the README file for further details. The
sl@0	23	** same data-structure is used for all, but the algorithms for insert and
sl@0	24	** delete operations vary. The variants used are selected at compile time
sl@0	25	** by defining the following symbols:
sl@0	26	*/
sl@0	27
sl@0	28	/* Either, both or none of the following may be set to activate
sl@0	29	** r*tree variant algorithms.
sl@0	30	*/
sl@0	31	#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
sl@0	32	#define VARIANT_RSTARTREE_REINSERT 1
sl@0	33
sl@0	34	/*
sl@0	35	** Exactly one of the following must be set to 1.
sl@0	36	*/
sl@0	37	#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
sl@0	38	#define VARIANT_GUTTMAN_LINEAR_SPLIT 0
sl@0	39	#define VARIANT_RSTARTREE_SPLIT 1
sl@0	40
sl@0	41	#define VARIANT_GUTTMAN_SPLIT \
sl@0	42	(VARIANT_GUTTMAN_LINEAR_SPLIT\|\|VARIANT_GUTTMAN_QUADRATIC_SPLIT)
sl@0	43
sl@0	44	#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
sl@0	45	#define PickNext QuadraticPickNext
sl@0	46	#define PickSeeds QuadraticPickSeeds
sl@0	47	#define AssignCells splitNodeGuttman
sl@0	48	#endif
sl@0	49	#if VARIANT_GUTTMAN_LINEAR_SPLIT
sl@0	50	#define PickNext LinearPickNext
sl@0	51	#define PickSeeds LinearPickSeeds
sl@0	52	#define AssignCells splitNodeGuttman
sl@0	53	#endif
sl@0	54	#if VARIANT_RSTARTREE_SPLIT
sl@0	55	#define AssignCells splitNodeStartree
sl@0	56	#endif
sl@0	57
sl@0	58
sl@0	59	#ifndef SQLITE_CORE
sl@0	60	#include "sqlite3ext.h"
sl@0	61	SQLITE_EXTENSION_INIT1
sl@0	62	#else
sl@0	63	#include "sqlite3.h"
sl@0	64	#endif
sl@0	65
sl@0	66	#include <string.h>
sl@0	67	#include <assert.h>
sl@0	68
sl@0	69	#ifndef SQLITE_AMALGAMATION
sl@0	70	typedef sqlite3_int64 i64;
sl@0	71	typedef unsigned char u8;
sl@0	72	typedef unsigned int u32;
sl@0	73	#endif
sl@0	74
sl@0	75	typedef struct Rtree Rtree;
sl@0	76	typedef struct RtreeCursor RtreeCursor;
sl@0	77	typedef struct RtreeNode RtreeNode;
sl@0	78	typedef struct RtreeCell RtreeCell;
sl@0	79	typedef struct RtreeConstraint RtreeConstraint;
sl@0	80	typedef union RtreeCoord RtreeCoord;
sl@0	81
sl@0	82	/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
sl@0	83	#define RTREE_MAX_DIMENSIONS 5
sl@0	84
sl@0	85	/* Size of hash table Rtree.aHash. This hash table is not expected to
sl@0	86	** ever contain very many entries, so a fixed number of buckets is
sl@0	87	** used.
sl@0	88	*/
sl@0	89	#define HASHSIZE 128
sl@0	90
sl@0	91	/*
sl@0	92	** An rtree virtual-table object.
sl@0	93	*/
sl@0	94	struct Rtree {
sl@0	95	sqlite3_vtab base;
sl@0	96	sqlite3 db; / Host database connection */
sl@0	97	int iNodeSize; /* Size in bytes of each node in the node table */
sl@0	98	int nDim; /* Number of dimensions */
sl@0	99	int nBytesPerCell; /* Bytes consumed per cell */
sl@0	100	int iDepth; /* Current depth of the r-tree structure */
sl@0	101	char zDb; / Name of database containing r-tree table */
sl@0	102	char zName; / Name of r-tree table */
sl@0	103	RtreeNode aHash[HASHSIZE]; / Hash table of in-memory nodes. */
sl@0	104	int nBusy; /* Current number of users of this structure */
sl@0	105
sl@0	106	/* List of nodes removed during a CondenseTree operation. List is
sl@0	107	** linked together via the pointer normally used for hash chains -
sl@0	108	** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree
sl@0	109	** headed by the node (leaf nodes have RtreeNode.iNode==0).
sl@0	110	*/
sl@0	111	RtreeNode *pDeleted;
sl@0	112	int iReinsertHeight; /* Height of sub-trees Reinsert() has run on */
sl@0	113
sl@0	114	/* Statements to read/write/delete a record from xxx_node */
sl@0	115	sqlite3_stmt *pReadNode;
sl@0	116	sqlite3_stmt *pWriteNode;
sl@0	117	sqlite3_stmt *pDeleteNode;
sl@0	118
sl@0	119	/* Statements to read/write/delete a record from xxx_rowid */
sl@0	120	sqlite3_stmt *pReadRowid;
sl@0	121	sqlite3_stmt *pWriteRowid;
sl@0	122	sqlite3_stmt *pDeleteRowid;
sl@0	123
sl@0	124	/* Statements to read/write/delete a record from xxx_parent */
sl@0	125	sqlite3_stmt *pReadParent;
sl@0	126	sqlite3_stmt *pWriteParent;
sl@0	127	sqlite3_stmt *pDeleteParent;
sl@0	128
sl@0	129	int eCoordType;
sl@0	130	};
sl@0	131
sl@0	132	/* Possible values for eCoordType: */
sl@0	133	#define RTREE_COORD_REAL32 0
sl@0	134	#define RTREE_COORD_INT32 1
sl@0	135
sl@0	136	/*
sl@0	137	** The minimum number of cells allowed for a node is a third of the
sl@0	138	** maximum. In Gutman's notation:
sl@0	139	**
sl@0	140	** m = M/3
sl@0	141	**
sl@0	142	** If an R*-tree "Reinsert" operation is required, the same number of
sl@0	143	** cells are removed from the overfull node and reinserted into the tree.
sl@0	144	*/
sl@0	145	#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)
sl@0	146	#define RTREE_REINSERT(p) RTREE_MINCELLS(p)
sl@0	147	#define RTREE_MAXCELLS 51
sl@0	148
sl@0	149	/*
sl@0	150	** An rtree cursor object.
sl@0	151	*/
sl@0	152	struct RtreeCursor {
sl@0	153	sqlite3_vtab_cursor base;
sl@0	154	RtreeNode pNode; / Node cursor is currently pointing at */
sl@0	155	int iCell; /* Index of current cell in pNode */
sl@0	156	int iStrategy; /* Copy of idxNum search parameter */
sl@0	157	int nConstraint; /* Number of entries in aConstraint */
sl@0	158	RtreeConstraint aConstraint; / Search constraints. */
sl@0	159	};
sl@0	160
sl@0	161	union RtreeCoord {
sl@0	162	float f;
sl@0	163	int i;
sl@0	164	};
sl@0	165
sl@0	166	/*
sl@0	167	** The argument is an RtreeCoord. Return the value stored within the RtreeCoord
sl@0	168	** formatted as a double. This macro assumes that local variable pRtree points
sl@0	169	** to the Rtree structure associated with the RtreeCoord.
sl@0	170	*/
sl@0	171	#define DCOORD(coord) ( \
sl@0	172	(pRtree->eCoordType==RTREE_COORD_REAL32) ? \
sl@0	173	((double)coord.f) : \
sl@0	174	((double)coord.i) \
sl@0	175	)
sl@0	176
sl@0	177	/*
sl@0	178	** A search constraint.
sl@0	179	*/
sl@0	180	struct RtreeConstraint {
sl@0	181	int iCoord; /* Index of constrained coordinate */
sl@0	182	int op; /* Constraining operation */
sl@0	183	double rValue; /* Constraint value. */
sl@0	184	};
sl@0	185
sl@0	186	/* Possible values for RtreeConstraint.op */
sl@0	187	#define RTREE_EQ 0x41
sl@0	188	#define RTREE_LE 0x42
sl@0	189	#define RTREE_LT 0x43
sl@0	190	#define RTREE_GE 0x44
sl@0	191	#define RTREE_GT 0x45
sl@0	192
sl@0	193	/*
sl@0	194	** An rtree structure node.
sl@0	195	**
sl@0	196	** Data format (RtreeNode.zData):
sl@0	197	**
sl@0	198	** 1. If the node is the root node (node 1), then the first 2 bytes
sl@0	199	** of the node contain the tree depth as a big-endian integer.
sl@0	200	** For non-root nodes, the first 2 bytes are left unused.
sl@0	201	**
sl@0	202	** 2. The next 2 bytes contain the number of entries currently
sl@0	203	** stored in the node.
sl@0	204	**
sl@0	205	** 3. The remainder of the node contains the node entries. Each entry
sl@0	206	** consists of a single 8-byte integer followed by an even number
sl@0	207	** of 4-byte coordinates. For leaf nodes the integer is the rowid
sl@0	208	** of a record. For internal nodes it is the node number of a
sl@0	209	** child page.
sl@0	210	*/
sl@0	211	struct RtreeNode {
sl@0	212	RtreeNode pParent; / Parent node */
sl@0	213	i64 iNode;
sl@0	214	int nRef;
sl@0	215	int isDirty;
sl@0	216	u8 *zData;
sl@0	217	RtreeNode pNext; / Next node in this hash chain */
sl@0	218	};
sl@0	219	#define NCELL(pNode) readInt16(&(pNode)->zData[2])
sl@0	220
sl@0	221	/*
sl@0	222	** Structure to store a deserialized rtree record.
sl@0	223	*/
sl@0	224	struct RtreeCell {
sl@0	225	i64 iRowid;
sl@0	226	RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
sl@0	227	};
sl@0	228
sl@0	229	#define MAX(x,y) ((x) < (y) ? (y) : (x))
sl@0	230	#define MIN(x,y) ((x) > (y) ? (y) : (x))
sl@0	231
sl@0	232	/*
sl@0	233	** Functions to deserialize a 16 bit integer, 32 bit real number and
sl@0	234	** 64 bit integer. The deserialized value is returned.
sl@0	235	*/
sl@0	236	static int readInt16(u8 *p){
sl@0	237	return (p[0]<<8) + p[1];
sl@0	238	}
sl@0	239	static void readCoord(u8 p, RtreeCoord pCoord){
sl@0	240	u32 i = (
sl@0	241	(((u32)p[0]) << 24) +
sl@0	242	(((u32)p[1]) << 16) +
sl@0	243	(((u32)p[2]) << 8) +
sl@0	244	(((u32)p[3]) << 0)
sl@0	245	);
sl@0	246	(u32 )pCoord = i;
sl@0	247	}
sl@0	248	static i64 readInt64(u8 *p){
sl@0	249	return (
sl@0	250	(((i64)p[0]) << 56) +
sl@0	251	(((i64)p[1]) << 48) +
sl@0	252	(((i64)p[2]) << 40) +
sl@0	253	(((i64)p[3]) << 32) +
sl@0	254	(((i64)p[4]) << 24) +
sl@0	255	(((i64)p[5]) << 16) +
sl@0	256	(((i64)p[6]) << 8) +
sl@0	257	(((i64)p[7]) << 0)
sl@0	258	);
sl@0	259	}
sl@0	260
sl@0	261	/*
sl@0	262	** Functions to serialize a 16 bit integer, 32 bit real number and
sl@0	263	** 64 bit integer. The value returned is the number of bytes written
sl@0	264	** to the argument buffer (always 2, 4 and 8 respectively).
sl@0	265	*/
sl@0	266	static int writeInt16(u8 *p, int i){
sl@0	267	p[0] = (i>> 8)&0xFF;
sl@0	268	p[1] = (i>> 0)&0xFF;
sl@0	269	return 2;
sl@0	270	}
sl@0	271	static int writeCoord(u8 p, RtreeCoord pCoord){
sl@0	272	u32 i;
sl@0	273	assert( sizeof(RtreeCoord)==4 );
sl@0	274	assert( sizeof(u32)==4 );
sl@0	275	i = (u32 )pCoord;
sl@0	276	p[0] = (i>>24)&0xFF;
sl@0	277	p[1] = (i>>16)&0xFF;
sl@0	278	p[2] = (i>> 8)&0xFF;
sl@0	279	p[3] = (i>> 0)&0xFF;
sl@0	280	return 4;
sl@0	281	}
sl@0	282	static int writeInt64(u8 *p, i64 i){
sl@0	283	p[0] = (i>>56)&0xFF;
sl@0	284	p[1] = (i>>48)&0xFF;
sl@0	285	p[2] = (i>>40)&0xFF;
sl@0	286	p[3] = (i>>32)&0xFF;
sl@0	287	p[4] = (i>>24)&0xFF;
sl@0	288	p[5] = (i>>16)&0xFF;
sl@0	289	p[6] = (i>> 8)&0xFF;
sl@0	290	p[7] = (i>> 0)&0xFF;
sl@0	291	return 8;
sl@0	292	}
sl@0	293
sl@0	294	/*
sl@0	295	** Increment the reference count of node p.
sl@0	296	*/
sl@0	297	static void nodeReference(RtreeNode *p){
sl@0	298	if( p ){
sl@0	299	p->nRef++;
sl@0	300	}
sl@0	301	}
sl@0	302
sl@0	303	/*
sl@0	304	** Clear the content of node p (set all bytes to 0x00).
sl@0	305	*/
sl@0	306	static void nodeZero(Rtree pRtree, RtreeNode p){
sl@0	307	if( p ){
sl@0	308	memset(&p->zData[2], 0, pRtree->iNodeSize-2);
sl@0	309	p->isDirty = 1;
sl@0	310	}
sl@0	311	}
sl@0	312
sl@0	313	/*
sl@0	314	** Given a node number iNode, return the corresponding key to use
sl@0	315	** in the Rtree.aHash table.
sl@0	316	*/
sl@0	317	static int nodeHash(i64 iNode){
sl@0	318	return (
sl@0	319	(iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^
sl@0	320	(iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
sl@0	321	) % HASHSIZE;
sl@0	322	}
sl@0	323
sl@0	324	/*
sl@0	325	** Search the node hash table for node iNode. If found, return a pointer
sl@0	326	** to it. Otherwise, return 0.
sl@0	327	*/
sl@0	328	static RtreeNode nodeHashLookup(Rtree pRtree, i64 iNode){
sl@0	329	RtreeNode *p;
sl@0	330	assert( iNode!=0 );
sl@0	331	for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);
sl@0	332	return p;
sl@0	333	}
sl@0	334
sl@0	335	/*
sl@0	336	** Add node pNode to the node hash table.
sl@0	337	*/
sl@0	338	static void nodeHashInsert(Rtree pRtree, RtreeNode pNode){
sl@0	339	if( pNode ){
sl@0	340	int iHash;
sl@0	341	assert( pNode->pNext==0 );
sl@0	342	iHash = nodeHash(pNode->iNode);
sl@0	343	pNode->pNext = pRtree->aHash[iHash];
sl@0	344	pRtree->aHash[iHash] = pNode;
sl@0	345	}
sl@0	346	}
sl@0	347
sl@0	348	/*
sl@0	349	** Remove node pNode from the node hash table.
sl@0	350	*/
sl@0	351	static void nodeHashDelete(Rtree pRtree, RtreeNode pNode){
sl@0	352	RtreeNode **pp;
sl@0	353	if( pNode->iNode!=0 ){
sl@0	354	pp = &pRtree->aHash[nodeHash(pNode->iNode)];
sl@0	355	for( ; (pp)!=pNode; pp = &(pp)->pNext){ assert(*pp); }
sl@0	356	*pp = pNode->pNext;
sl@0	357	pNode->pNext = 0;
sl@0	358	}
sl@0	359	}
sl@0	360
sl@0	361	/*
sl@0	362	** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),
sl@0	363	** indicating that node has not yet been assigned a node number. It is
sl@0	364	** assigned a node number when nodeWrite() is called to write the
sl@0	365	** node contents out to the database.
sl@0	366	*/
sl@0	367	static RtreeNode nodeNew(Rtree pRtree, RtreeNode *pParent, int zero){
sl@0	368	RtreeNode *pNode;
sl@0	369	pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
sl@0	370	if( pNode ){
sl@0	371	memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));
sl@0	372	pNode->zData = (u8 *)&pNode[1];
sl@0	373	pNode->nRef = 1;
sl@0	374	pNode->pParent = pParent;
sl@0	375	pNode->isDirty = 1;
sl@0	376	nodeReference(pParent);
sl@0	377	}
sl@0	378	return pNode;
sl@0	379	}
sl@0	380
sl@0	381	/*
sl@0	382	** Obtain a reference to an r-tree node.
sl@0	383	*/
sl@0	384	static int
sl@0	385	nodeAcquire(
sl@0	386	Rtree pRtree, / R-tree structure */
sl@0	387	i64 iNode, /* Node number to load */
sl@0	388	RtreeNode pParent, / Either the parent node or NULL */
sl@0	389	RtreeNode *ppNode / OUT: Acquired node */
sl@0	390	){
sl@0	391	int rc;
sl@0	392	RtreeNode *pNode;
sl@0	393
sl@0	394	/* Check if the requested node is already in the hash table. If so,
sl@0	395	** increase its reference count and return it.
sl@0	396	*/
sl@0	397	if( (pNode = nodeHashLookup(pRtree, iNode)) ){
sl@0	398	assert( !pParent \|\| !pNode->pParent \|\| pNode->pParent==pParent );
sl@0	399	if( pParent ){
sl@0	400	pNode->pParent = pParent;
sl@0	401	}
sl@0	402	pNode->nRef++;
sl@0	403	*ppNode = pNode;
sl@0	404	return SQLITE_OK;
sl@0	405	}
sl@0	406
sl@0	407	pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);
sl@0	408	if( !pNode ){
sl@0	409	*ppNode = 0;
sl@0	410	return SQLITE_NOMEM;
sl@0	411	}
sl@0	412	pNode->pParent = pParent;
sl@0	413	pNode->zData = (u8 *)&pNode[1];
sl@0	414	pNode->nRef = 1;
sl@0	415	pNode->iNode = iNode;
sl@0	416	pNode->isDirty = 0;
sl@0	417	pNode->pNext = 0;
sl@0	418
sl@0	419	sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);
sl@0	420	rc = sqlite3_step(pRtree->pReadNode);
sl@0	421	if( rc==SQLITE_ROW ){
sl@0	422	const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);
sl@0	423	memcpy(pNode->zData, zBlob, pRtree->iNodeSize);
sl@0	424	nodeReference(pParent);
sl@0	425	}else{
sl@0	426	sqlite3_free(pNode);
sl@0	427	pNode = 0;
sl@0	428	}
sl@0	429
sl@0	430	*ppNode = pNode;
sl@0	431	rc = sqlite3_reset(pRtree->pReadNode);
sl@0	432
sl@0	433	if( rc==SQLITE_OK && iNode==1 ){
sl@0	434	pRtree->iDepth = readInt16(pNode->zData);
sl@0	435	}
sl@0	436
sl@0	437	assert( (rc==SQLITE_OK && pNode) \|\| (pNode==0 && rc!=SQLITE_OK) );
sl@0	438	nodeHashInsert(pRtree, pNode);
sl@0	439
sl@0	440	return rc;
sl@0	441	}
sl@0	442
sl@0	443	/*
sl@0	444	** Overwrite cell iCell of node pNode with the contents of pCell.
sl@0	445	*/
sl@0	446	static void nodeOverwriteCell(
sl@0	447	Rtree *pRtree,
sl@0	448	RtreeNode *pNode,
sl@0	449	RtreeCell *pCell,
sl@0	450	int iCell
sl@0	451	){
sl@0	452	int ii;
sl@0	453	u8 p = &pNode->zData[4 + pRtree->nBytesPerCelliCell];
sl@0	454	p += writeInt64(p, pCell->iRowid);
sl@0	455	for(ii=0; ii<(pRtree->nDim*2); ii++){
sl@0	456	p += writeCoord(p, &pCell->aCoord[ii]);
sl@0	457	}
sl@0	458	pNode->isDirty = 1;
sl@0	459	}
sl@0	460
sl@0	461	/*
sl@0	462	** Remove cell the cell with index iCell from node pNode.
sl@0	463	*/
sl@0	464	static void nodeDeleteCell(Rtree pRtree, RtreeNode pNode, int iCell){
sl@0	465	u8 pDst = &pNode->zData[4 + pRtree->nBytesPerCelliCell];
sl@0	466	u8 *pSrc = &pDst[pRtree->nBytesPerCell];
sl@0	467	int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;
sl@0	468	memmove(pDst, pSrc, nByte);
sl@0	469	writeInt16(&pNode->zData[2], NCELL(pNode)-1);
sl@0	470	pNode->isDirty = 1;
sl@0	471	}
sl@0	472
sl@0	473	/*
sl@0	474	** Insert the contents of cell pCell into node pNode. If the insert
sl@0	475	** is successful, return SQLITE_OK.
sl@0	476	**
sl@0	477	** If there is not enough free space in pNode, return SQLITE_FULL.
sl@0	478	*/
sl@0	479	static int
sl@0	480	nodeInsertCell(
sl@0	481	Rtree *pRtree,
sl@0	482	RtreeNode *pNode,
sl@0	483	RtreeCell *pCell
sl@0	484	){
sl@0	485	int nCell; /* Current number of cells in pNode */
sl@0	486	int nMaxCell; /* Maximum number of cells for pNode */
sl@0	487
sl@0	488	nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;
sl@0	489	nCell = NCELL(pNode);
sl@0	490
sl@0	491	assert(nCell<=nMaxCell);
sl@0	492
sl@0	493	if( nCell<nMaxCell ){
sl@0	494	nodeOverwriteCell(pRtree, pNode, pCell, nCell);
sl@0	495	writeInt16(&pNode->zData[2], nCell+1);
sl@0	496	pNode->isDirty = 1;
sl@0	497	}
sl@0	498
sl@0	499	return (nCell==nMaxCell);
sl@0	500	}
sl@0	501
sl@0	502	/*
sl@0	503	** If the node is dirty, write it out to the database.
sl@0	504	*/
sl@0	505	static int
sl@0	506	nodeWrite(Rtree pRtree, RtreeNode pNode){
sl@0	507	int rc = SQLITE_OK;
sl@0	508	if( pNode->isDirty ){
sl@0	509	sqlite3_stmt *p = pRtree->pWriteNode;
sl@0	510	if( pNode->iNode ){
sl@0	511	sqlite3_bind_int64(p, 1, pNode->iNode);
sl@0	512	}else{
sl@0	513	sqlite3_bind_null(p, 1);
sl@0	514	}
sl@0	515	sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);
sl@0	516	sqlite3_step(p);
sl@0	517	pNode->isDirty = 0;
sl@0	518	rc = sqlite3_reset(p);
sl@0	519	if( pNode->iNode==0 && rc==SQLITE_OK ){
sl@0	520	pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);
sl@0	521	nodeHashInsert(pRtree, pNode);
sl@0	522	}
sl@0	523	}
sl@0	524	return rc;
sl@0	525	}
sl@0	526
sl@0	527	/*
sl@0	528	** Release a reference to a node. If the node is dirty and the reference
sl@0	529	** count drops to zero, the node data is written to the database.
sl@0	530	*/
sl@0	531	static int
sl@0	532	nodeRelease(Rtree pRtree, RtreeNode pNode){
sl@0	533	int rc = SQLITE_OK;
sl@0	534	if( pNode ){
sl@0	535	assert( pNode->nRef>0 );
sl@0	536	pNode->nRef--;
sl@0	537	if( pNode->nRef==0 ){
sl@0	538	if( pNode->iNode==1 ){
sl@0	539	pRtree->iDepth = -1;
sl@0	540	}
sl@0	541	if( pNode->pParent ){
sl@0	542	rc = nodeRelease(pRtree, pNode->pParent);
sl@0	543	}
sl@0	544	if( rc==SQLITE_OK ){
sl@0	545	rc = nodeWrite(pRtree, pNode);
sl@0	546	}
sl@0	547	nodeHashDelete(pRtree, pNode);
sl@0	548	sqlite3_free(pNode);
sl@0	549	}
sl@0	550	}
sl@0	551	return rc;
sl@0	552	}
sl@0	553
sl@0	554	/*
sl@0	555	** Return the 64-bit integer value associated with cell iCell of
sl@0	556	** node pNode. If pNode is a leaf node, this is a rowid. If it is
sl@0	557	** an internal node, then the 64-bit integer is a child page number.
sl@0	558	*/
sl@0	559	static i64 nodeGetRowid(
sl@0	560	Rtree *pRtree,
sl@0	561	RtreeNode *pNode,
sl@0	562	int iCell
sl@0	563	){
sl@0	564	assert( iCell<NCELL(pNode) );
sl@0	565	return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
sl@0	566	}
sl@0	567
sl@0	568	/*
sl@0	569	** Return coordinate iCoord from cell iCell in node pNode.
sl@0	570	*/
sl@0	571	static void nodeGetCoord(
sl@0	572	Rtree *pRtree,
sl@0	573	RtreeNode *pNode,
sl@0	574	int iCell,
sl@0	575	int iCoord,
sl@0	576	RtreeCoord pCoord / Space to write result to */
sl@0	577	){
sl@0	578	readCoord(&pNode->zData[12 + pRtree->nBytesPerCelliCell + 4iCoord], pCoord);
sl@0	579	}
sl@0	580
sl@0	581	/*
sl@0	582	** Deserialize cell iCell of node pNode. Populate the structure pointed
sl@0	583	** to by pCell with the results.
sl@0	584	*/
sl@0	585	static void nodeGetCell(
sl@0	586	Rtree *pRtree,
sl@0	587	RtreeNode *pNode,
sl@0	588	int iCell,
sl@0	589	RtreeCell *pCell
sl@0	590	){
sl@0	591	int ii;
sl@0	592	pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
sl@0	593	for(ii=0; ii<pRtree->nDim*2; ii++){
sl@0	594	nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
sl@0	595	}
sl@0	596	}
sl@0	597
sl@0	598
sl@0	599	/* Forward declaration for the function that does the work of
sl@0	600	** the virtual table module xCreate() and xConnect() methods.
sl@0	601	*/
sl@0	602	static int rtreeInit(
sl@0	603	sqlite3 , void , int, const char const, sqlite3_vtab , char , int, int
sl@0	604	);
sl@0	605
sl@0	606	/*
sl@0	607	** Rtree virtual table module xCreate method.
sl@0	608	*/
sl@0	609	static int rtreeCreate(
sl@0	610	sqlite3 *db,
sl@0	611	void *pAux,
sl@0	612	int argc, const char constargv,
sl@0	613	sqlite3_vtab **ppVtab,
sl@0	614	char **pzErr
sl@0	615	){
sl@0	616	return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux);
sl@0	617	}
sl@0	618
sl@0	619	/*
sl@0	620	** Rtree virtual table module xConnect method.
sl@0	621	*/
sl@0	622	static int rtreeConnect(
sl@0	623	sqlite3 *db,
sl@0	624	void *pAux,
sl@0	625	int argc, const char constargv,
sl@0	626	sqlite3_vtab **ppVtab,
sl@0	627	char **pzErr
sl@0	628	){
sl@0	629	return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux);
sl@0	630	}
sl@0	631
sl@0	632	/*
sl@0	633	** Increment the r-tree reference count.
sl@0	634	*/
sl@0	635	static void rtreeReference(Rtree *pRtree){
sl@0	636	pRtree->nBusy++;
sl@0	637	}
sl@0	638
sl@0	639	/*
sl@0	640	** Decrement the r-tree reference count. When the reference count reaches
sl@0	641	** zero the structure is deleted.
sl@0	642	*/
sl@0	643	static void rtreeRelease(Rtree *pRtree){
sl@0	644	pRtree->nBusy--;
sl@0	645	if( pRtree->nBusy==0 ){
sl@0	646	sqlite3_finalize(pRtree->pReadNode);
sl@0	647	sqlite3_finalize(pRtree->pWriteNode);
sl@0	648	sqlite3_finalize(pRtree->pDeleteNode);
sl@0	649	sqlite3_finalize(pRtree->pReadRowid);
sl@0	650	sqlite3_finalize(pRtree->pWriteRowid);
sl@0	651	sqlite3_finalize(pRtree->pDeleteRowid);
sl@0	652	sqlite3_finalize(pRtree->pReadParent);
sl@0	653	sqlite3_finalize(pRtree->pWriteParent);
sl@0	654	sqlite3_finalize(pRtree->pDeleteParent);
sl@0	655	sqlite3_free(pRtree);
sl@0	656	}
sl@0	657	}
sl@0	658
sl@0	659	/*
sl@0	660	** Rtree virtual table module xDisconnect method.
sl@0	661	*/
sl@0	662	static int rtreeDisconnect(sqlite3_vtab *pVtab){
sl@0	663	rtreeRelease((Rtree *)pVtab);
sl@0	664	return SQLITE_OK;
sl@0	665	}
sl@0	666
sl@0	667	/*
sl@0	668	** Rtree virtual table module xDestroy method.
sl@0	669	*/
sl@0	670	static int rtreeDestroy(sqlite3_vtab *pVtab){
sl@0	671	Rtree pRtree = (Rtree )pVtab;
sl@0	672	int rc;
sl@0	673	char *zCreate = sqlite3_mprintf(
sl@0	674	"DROP TABLE '%q'.'%q_node';"
sl@0	675	"DROP TABLE '%q'.'%q_rowid';"
sl@0	676	"DROP TABLE '%q'.'%q_parent';",
sl@0	677	pRtree->zDb, pRtree->zName,
sl@0	678	pRtree->zDb, pRtree->zName,
sl@0	679	pRtree->zDb, pRtree->zName
sl@0	680	);
sl@0	681	if( !zCreate ){
sl@0	682	rc = SQLITE_NOMEM;
sl@0	683	}else{
sl@0	684	rc = sqlite3_exec(pRtree->db, zCreate, 0, 0, 0);
sl@0	685	sqlite3_free(zCreate);
sl@0	686	}
sl@0	687	if( rc==SQLITE_OK ){
sl@0	688	rtreeRelease(pRtree);
sl@0	689	}
sl@0	690
sl@0	691	return rc;
sl@0	692	}
sl@0	693
sl@0	694	/*
sl@0	695	** Rtree virtual table module xOpen method.
sl@0	696	*/
sl@0	697	static int rtreeOpen(sqlite3_vtab pVTab, sqlite3_vtab_cursor *ppCursor){
sl@0	698	int rc = SQLITE_NOMEM;
sl@0	699	RtreeCursor *pCsr;
sl@0	700
sl@0	701	pCsr = (RtreeCursor *)sqlite3_malloc(sizeof(RtreeCursor));
sl@0	702	if( pCsr ){
sl@0	703	memset(pCsr, 0, sizeof(RtreeCursor));
sl@0	704	pCsr->base.pVtab = pVTab;
sl@0	705	rc = SQLITE_OK;
sl@0	706	}
sl@0	707	ppCursor = (sqlite3_vtab_cursor )pCsr;
sl@0	708
sl@0	709	return rc;
sl@0	710	}
sl@0	711
sl@0	712	/*
sl@0	713	** Rtree virtual table module xClose method.
sl@0	714	*/
sl@0	715	static int rtreeClose(sqlite3_vtab_cursor *cur){
sl@0	716	Rtree pRtree = (Rtree )(cur->pVtab);
sl@0	717	int rc;
sl@0	718	RtreeCursor pCsr = (RtreeCursor )cur;
sl@0	719	sqlite3_free(pCsr->aConstraint);
sl@0	720	rc = nodeRelease(pRtree, pCsr->pNode);
sl@0	721	sqlite3_free(pCsr);
sl@0	722	return rc;
sl@0	723	}
sl@0	724
sl@0	725	/*
sl@0	726	** Rtree virtual table module xEof method.
sl@0	727	**
sl@0	728	** Return non-zero if the cursor does not currently point to a valid
sl@0	729	** record (i.e if the scan has finished), or zero otherwise.
sl@0	730	*/
sl@0	731	static int rtreeEof(sqlite3_vtab_cursor *cur){
sl@0	732	RtreeCursor pCsr = (RtreeCursor )cur;
sl@0	733	return (pCsr->pNode==0);
sl@0	734	}
sl@0	735
sl@0	736	/*
sl@0	737	** Cursor pCursor currently points to a cell in a non-leaf page.
sl@0	738	** Return true if the sub-tree headed by the cell is filtered
sl@0	739	** (excluded) by the constraints in the pCursor->aConstraint[]
sl@0	740	** array, or false otherwise.
sl@0	741	*/
sl@0	742	static int testRtreeCell(Rtree pRtree, RtreeCursor pCursor){
sl@0	743	RtreeCell cell;
sl@0	744	int ii;
sl@0	745	int bRes = 0;
sl@0	746
sl@0	747	nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
sl@0	748	for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
sl@0	749	RtreeConstraint *p = &pCursor->aConstraint[ii];
sl@0	750	double cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
sl@0	751	double cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
sl@0	752
sl@0	753	assert(p->op==RTREE_LE \|\| p->op==RTREE_LT \|\| p->op==RTREE_GE
sl@0	754	\|\| p->op==RTREE_GT \|\| p->op==RTREE_EQ
sl@0	755	);
sl@0	756
sl@0	757	switch( p->op ){
sl@0	758	case RTREE_LE: case RTREE_LT: bRes = p->rValue<cell_min; break;
sl@0	759	case RTREE_GE: case RTREE_GT: bRes = p->rValue>cell_max; break;
sl@0	760	case RTREE_EQ:
sl@0	761	bRes = (p->rValue>cell_max \|\| p->rValue<cell_min);
sl@0	762	break;
sl@0	763	}
sl@0	764	}
sl@0	765
sl@0	766	return bRes;
sl@0	767	}
sl@0	768
sl@0	769	/*
sl@0	770	** Return true if the cell that cursor pCursor currently points to
sl@0	771	** would be filtered (excluded) by the constraints in the
sl@0	772	** pCursor->aConstraint[] array, or false otherwise.
sl@0	773	**
sl@0	774	** This function assumes that the cell is part of a leaf node.
sl@0	775	*/
sl@0	776	static int testRtreeEntry(Rtree pRtree, RtreeCursor pCursor){
sl@0	777	RtreeCell cell;
sl@0	778	int ii;
sl@0	779
sl@0	780	nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
sl@0	781	for(ii=0; ii<pCursor->nConstraint; ii++){
sl@0	782	RtreeConstraint *p = &pCursor->aConstraint[ii];
sl@0	783	double coord = DCOORD(cell.aCoord[p->iCoord]);
sl@0	784	int res;
sl@0	785	assert(p->op==RTREE_LE \|\| p->op==RTREE_LT \|\| p->op==RTREE_GE
sl@0	786	\|\| p->op==RTREE_GT \|\| p->op==RTREE_EQ
sl@0	787	);
sl@0	788	switch( p->op ){
sl@0	789	case RTREE_LE: res = (coord<=p->rValue); break;
sl@0	790	case RTREE_LT: res = (coord<p->rValue); break;
sl@0	791	case RTREE_GE: res = (coord>=p->rValue); break;
sl@0	792	case RTREE_GT: res = (coord>p->rValue); break;
sl@0	793	case RTREE_EQ: res = (coord==p->rValue); break;
sl@0	794	}
sl@0	795
sl@0	796	if( !res ) return 1;
sl@0	797	}
sl@0	798
sl@0	799	return 0;
sl@0	800	}
sl@0	801
sl@0	802	/*
sl@0	803	** Cursor pCursor currently points at a node that heads a sub-tree of
sl@0	804	** height iHeight (if iHeight==0, then the node is a leaf). Descend
sl@0	805	** to point to the left-most cell of the sub-tree that matches the
sl@0	806	** configured constraints.
sl@0	807	*/
sl@0	808	static int descendToCell(
sl@0	809	Rtree *pRtree,
sl@0	810	RtreeCursor *pCursor,
sl@0	811	int iHeight,
sl@0	812	int pEof / OUT: Set to true if cannot descend */
sl@0	813	){
sl@0	814	int isEof;
sl@0	815	int rc;
sl@0	816	int ii;
sl@0	817	RtreeNode *pChild;
sl@0	818	sqlite3_int64 iRowid;
sl@0	819
sl@0	820	RtreeNode *pSavedNode = pCursor->pNode;
sl@0	821	int iSavedCell = pCursor->iCell;
sl@0	822
sl@0	823	assert( iHeight>=0 );
sl@0	824
sl@0	825	if( iHeight==0 ){
sl@0	826	isEof = testRtreeEntry(pRtree, pCursor);
sl@0	827	}else{
sl@0	828	isEof = testRtreeCell(pRtree, pCursor);
sl@0	829	}
sl@0	830	if( isEof \|\| iHeight==0 ){
sl@0	831	*pEof = isEof;
sl@0	832	return SQLITE_OK;
sl@0	833	}
sl@0	834
sl@0	835	iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
sl@0	836	rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
sl@0	837	if( rc!=SQLITE_OK ){
sl@0	838	return rc;
sl@0	839	}
sl@0	840
sl@0	841	nodeRelease(pRtree, pCursor->pNode);
sl@0	842	pCursor->pNode = pChild;
sl@0	843	isEof = 1;
sl@0	844	for(ii=0; isEof && ii<NCELL(pChild); ii++){
sl@0	845	pCursor->iCell = ii;
sl@0	846	rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
sl@0	847	if( rc!=SQLITE_OK ){
sl@0	848	return rc;
sl@0	849	}
sl@0	850	}
sl@0	851
sl@0	852	if( isEof ){
sl@0	853	assert( pCursor->pNode==pChild );
sl@0	854	nodeReference(pSavedNode);
sl@0	855	nodeRelease(pRtree, pChild);
sl@0	856	pCursor->pNode = pSavedNode;
sl@0	857	pCursor->iCell = iSavedCell;
sl@0	858	}
sl@0	859
sl@0	860	*pEof = isEof;
sl@0	861	return SQLITE_OK;
sl@0	862	}
sl@0	863
sl@0	864	/*
sl@0	865	** One of the cells in node pNode is guaranteed to have a 64-bit
sl@0	866	** integer value equal to iRowid. Return the index of this cell.
sl@0	867	*/
sl@0	868	static int nodeRowidIndex(Rtree pRtree, RtreeNode pNode, i64 iRowid){
sl@0	869	int ii;
sl@0	870	for(ii=0; nodeGetRowid(pRtree, pNode, ii)!=iRowid; ii++){
sl@0	871	assert( ii<(NCELL(pNode)-1) );
sl@0	872	}
sl@0	873	return ii;
sl@0	874	}
sl@0	875
sl@0	876	/*
sl@0	877	** Return the index of the cell containing a pointer to node pNode
sl@0	878	** in its parent. If pNode is the root node, return -1.
sl@0	879	*/
sl@0	880	static int nodeParentIndex(Rtree pRtree, RtreeNode pNode){
sl@0	881	RtreeNode *pParent = pNode->pParent;
sl@0	882	if( pParent ){
sl@0	883	return nodeRowidIndex(pRtree, pParent, pNode->iNode);
sl@0	884	}
sl@0	885	return -1;
sl@0	886	}
sl@0	887
sl@0	888	/*
sl@0	889	** Rtree virtual table module xNext method.
sl@0	890	*/
sl@0	891	static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
sl@0	892	Rtree pRtree = (Rtree )(pVtabCursor->pVtab);
sl@0	893	RtreeCursor pCsr = (RtreeCursor )pVtabCursor;
sl@0	894	int rc = SQLITE_OK;
sl@0	895
sl@0	896	if( pCsr->iStrategy==1 ){
sl@0	897	/* This "scan" is a direct lookup by rowid. There is no next entry. */
sl@0	898	nodeRelease(pRtree, pCsr->pNode);
sl@0	899	pCsr->pNode = 0;
sl@0	900	}
sl@0	901
sl@0	902	else if( pCsr->pNode ){
sl@0	903	/* Move to the next entry that matches the configured constraints. */
sl@0	904	int iHeight = 0;
sl@0	905	while( pCsr->pNode ){
sl@0	906	RtreeNode *pNode = pCsr->pNode;
sl@0	907	int nCell = NCELL(pNode);
sl@0	908	for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
sl@0	909	int isEof;
sl@0	910	rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
sl@0	911	if( rc!=SQLITE_OK \|\| !isEof ){
sl@0	912	return rc;
sl@0	913	}
sl@0	914	}
sl@0	915	pCsr->pNode = pNode->pParent;
sl@0	916	pCsr->iCell = nodeParentIndex(pRtree, pNode);
sl@0	917	nodeReference(pCsr->pNode);
sl@0	918	nodeRelease(pRtree, pNode);
sl@0	919	iHeight++;
sl@0	920	}
sl@0	921	}
sl@0	922
sl@0	923	return rc;
sl@0	924	}
sl@0	925
sl@0	926	/*
sl@0	927	** Rtree virtual table module xRowid method.
sl@0	928	*/
sl@0	929	static int rtreeRowid(sqlite3_vtab_cursor pVtabCursor, sqlite_int64 pRowid){
sl@0	930	Rtree pRtree = (Rtree )pVtabCursor->pVtab;
sl@0	931	RtreeCursor pCsr = (RtreeCursor )pVtabCursor;
sl@0	932
sl@0	933	assert(pCsr->pNode);
sl@0	934	*pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
sl@0	935
sl@0	936	return SQLITE_OK;
sl@0	937	}
sl@0	938
sl@0	939	/*
sl@0	940	** Rtree virtual table module xColumn method.
sl@0	941	*/
sl@0	942	static int rtreeColumn(sqlite3_vtab_cursor cur, sqlite3_context ctx, int i){
sl@0	943	Rtree pRtree = (Rtree )cur->pVtab;
sl@0	944	RtreeCursor pCsr = (RtreeCursor )cur;
sl@0	945
sl@0	946	if( i==0 ){
sl@0	947	i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
sl@0	948	sqlite3_result_int64(ctx, iRowid);
sl@0	949	}else{
sl@0	950	RtreeCoord c;
sl@0	951	nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
sl@0	952	if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0	953	sqlite3_result_double(ctx, c.f);
sl@0	954	}else{
sl@0	955	assert( pRtree->eCoordType==RTREE_COORD_INT32 );
sl@0	956	sqlite3_result_int(ctx, c.i);
sl@0	957	}
sl@0	958	}
sl@0	959
sl@0	960	return SQLITE_OK;
sl@0	961	}
sl@0	962
sl@0	963	/*
sl@0	964	** Use nodeAcquire() to obtain the leaf node containing the record with
sl@0	965	** rowid iRowid. If successful, set *ppLeaf to point to the node and
sl@0	966	** return SQLITE_OK. If there is no such record in the table, set
sl@0	967	** ppLeaf to 0 and return SQLITE_OK. If an error occurs, set ppLeaf
sl@0	968	** to zero and return an SQLite error code.
sl@0	969	*/
sl@0	970	static int findLeafNode(Rtree pRtree, i64 iRowid, RtreeNode *ppLeaf){
sl@0	971	int rc;
sl@0	972	*ppLeaf = 0;
sl@0	973	sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
sl@0	974	if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
sl@0	975	i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
sl@0	976	rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
sl@0	977	sqlite3_reset(pRtree->pReadRowid);
sl@0	978	}else{
sl@0	979	rc = sqlite3_reset(pRtree->pReadRowid);
sl@0	980	}
sl@0	981	return rc;
sl@0	982	}
sl@0	983
sl@0	984
sl@0	985	/*
sl@0	986	** Rtree virtual table module xFilter method.
sl@0	987	*/
sl@0	988	static int rtreeFilter(
sl@0	989	sqlite3_vtab_cursor *pVtabCursor,
sl@0	990	int idxNum, const char *idxStr,
sl@0	991	int argc, sqlite3_value **argv
sl@0	992	){
sl@0	993	Rtree pRtree = (Rtree )pVtabCursor->pVtab;
sl@0	994	RtreeCursor pCsr = (RtreeCursor )pVtabCursor;
sl@0	995
sl@0	996	RtreeNode *pRoot = 0;
sl@0	997	int ii;
sl@0	998	int rc = SQLITE_OK;
sl@0	999
sl@0	1000	rtreeReference(pRtree);
sl@0	1001
sl@0	1002	sqlite3_free(pCsr->aConstraint);
sl@0	1003	pCsr->aConstraint = 0;
sl@0	1004	pCsr->iStrategy = idxNum;
sl@0	1005
sl@0	1006	if( idxNum==1 ){
sl@0	1007	/* Special case - lookup by rowid. */
sl@0	1008	RtreeNode pLeaf; / Leaf on which the required cell resides */
sl@0	1009	i64 iRowid = sqlite3_value_int64(argv[0]);
sl@0	1010	rc = findLeafNode(pRtree, iRowid, &pLeaf);
sl@0	1011	pCsr->pNode = pLeaf;
sl@0	1012	if( pLeaf && rc==SQLITE_OK ){
sl@0	1013	pCsr->iCell = nodeRowidIndex(pRtree, pLeaf, iRowid);
sl@0	1014	}
sl@0	1015	}else{
sl@0	1016	/* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
sl@0	1017	** with the configured constraints.
sl@0	1018	*/
sl@0	1019	if( argc>0 ){
sl@0	1020	pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
sl@0	1021	pCsr->nConstraint = argc;
sl@0	1022	if( !pCsr->aConstraint ){
sl@0	1023	rc = SQLITE_NOMEM;
sl@0	1024	}else{
sl@0	1025	assert( (idxStr==0 && argc==0) \|\| strlen(idxStr)==argc*2 );
sl@0	1026	for(ii=0; ii<argc; ii++){
sl@0	1027	RtreeConstraint *p = &pCsr->aConstraint[ii];
sl@0	1028	p->op = idxStr[ii*2];
sl@0	1029	p->iCoord = idxStr[ii*2+1]-'a';
sl@0	1030	p->rValue = sqlite3_value_double(argv[ii]);
sl@0	1031	}
sl@0	1032	}
sl@0	1033	}
sl@0	1034
sl@0	1035	if( rc==SQLITE_OK ){
sl@0	1036	pCsr->pNode = 0;
sl@0	1037	rc = nodeAcquire(pRtree, 1, 0, &pRoot);
sl@0	1038	}
sl@0	1039	if( rc==SQLITE_OK ){
sl@0	1040	int isEof = 1;
sl@0	1041	int nCell = NCELL(pRoot);
sl@0	1042	pCsr->pNode = pRoot;
sl@0	1043	for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
sl@0	1044	assert( pCsr->pNode==pRoot );
sl@0	1045	rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
sl@0	1046	if( !isEof ){
sl@0	1047	break;
sl@0	1048	}
sl@0	1049	}
sl@0	1050	if( rc==SQLITE_OK && isEof ){
sl@0	1051	assert( pCsr->pNode==pRoot );
sl@0	1052	nodeRelease(pRtree, pRoot);
sl@0	1053	pCsr->pNode = 0;
sl@0	1054	}
sl@0	1055	assert( rc!=SQLITE_OK \|\| !pCsr->pNode \|\| pCsr->iCell<NCELL(pCsr->pNode) );
sl@0	1056	}
sl@0	1057	}
sl@0	1058
sl@0	1059	rtreeRelease(pRtree);
sl@0	1060	return rc;
sl@0	1061	}
sl@0	1062
sl@0	1063	/*
sl@0	1064	** Rtree virtual table module xBestIndex method. There are three
sl@0	1065	** table scan strategies to choose from (in order from most to
sl@0	1066	** least desirable):
sl@0	1067	**
sl@0	1068	** idxNum idxStr Strategy
sl@0	1069	** ------------------------------------------------
sl@0	1070	** 1 Unused Direct lookup by rowid.
sl@0	1071	** 2 See below R-tree query.
sl@0	1072	** 3 Unused Full table scan.
sl@0	1073	** ------------------------------------------------
sl@0	1074	**
sl@0	1075	** If strategy 1 or 3 is used, then idxStr is not meaningful. If strategy
sl@0	1076	** 2 is used, idxStr is formatted to contain 2 bytes for each
sl@0	1077	** constraint used. The first two bytes of idxStr correspond to
sl@0	1078	** the constraint in sqlite3_index_info.aConstraintUsage[] with
sl@0	1079	** (argvIndex==1) etc.
sl@0	1080	**
sl@0	1081	** The first of each pair of bytes in idxStr identifies the constraint
sl@0	1082	** operator as follows:
sl@0	1083	**
sl@0	1084	** Operator Byte Value
sl@0	1085	** ----------------------
sl@0	1086	** = 0x41 ('A')
sl@0	1087	** <= 0x42 ('B')
sl@0	1088	** < 0x43 ('C')
sl@0	1089	** >= 0x44 ('D')
sl@0	1090	** > 0x45 ('E')
sl@0	1091	** ----------------------
sl@0	1092	**
sl@0	1093	** The second of each pair of bytes identifies the coordinate column
sl@0	1094	** to which the constraint applies. The leftmost coordinate column
sl@0	1095	** is 'a', the second from the left 'b' etc.
sl@0	1096	*/
sl@0	1097	static int rtreeBestIndex(sqlite3_vtab tab, sqlite3_index_info pIdxInfo){
sl@0	1098	int rc = SQLITE_OK;
sl@0	1099	int ii, cCol;
sl@0	1100
sl@0	1101	int iIdx = 0;
sl@0	1102	char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
sl@0	1103	memset(zIdxStr, 0, sizeof(zIdxStr));
sl@0	1104
sl@0	1105	assert( pIdxInfo->idxStr==0 );
sl@0	1106	for(ii=0; ii<pIdxInfo->nConstraint; ii++){
sl@0	1107	struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
sl@0	1108
sl@0	1109	if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
sl@0	1110	/* We have an equality constraint on the rowid. Use strategy 1. */
sl@0	1111	int jj;
sl@0	1112	for(jj=0; jj<ii; jj++){
sl@0	1113	pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
sl@0	1114	pIdxInfo->aConstraintUsage[jj].omit = 0;
sl@0	1115	}
sl@0	1116	pIdxInfo->idxNum = 1;
sl@0	1117	pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
sl@0	1118	pIdxInfo->aConstraintUsage[jj].omit = 1;
sl@0	1119
sl@0	1120	/* This strategy involves a two rowid lookups on an B-Tree structures
sl@0	1121	** and then a linear search of an R-Tree node. This should be
sl@0	1122	** considered almost as quick as a direct rowid lookup (for which
sl@0	1123	** sqlite uses an internal cost of 0.0).
sl@0	1124	*/
sl@0	1125	pIdxInfo->estimatedCost = 10.0;
sl@0	1126	return SQLITE_OK;
sl@0	1127	}
sl@0	1128
sl@0	1129	if( p->usable && p->iColumn>0 ){
sl@0	1130	u8 op = 0;
sl@0	1131	switch( p->op ){
sl@0	1132	case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
sl@0	1133	case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
sl@0	1134	case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
sl@0	1135	case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
sl@0	1136	case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
sl@0	1137	}
sl@0	1138	if( op ){
sl@0	1139	/* Make sure this particular constraint has not been used before.
sl@0	1140	** If it has been used before, ignore it.
sl@0	1141	**
sl@0	1142	** A <= or < can be used if there is a prior >= or >.
sl@0	1143	** A >= or > can be used if there is a prior < or <=.
sl@0	1144	** A <= or < is disqualified if there is a prior <=, <, or ==.
sl@0	1145	** A >= or > is disqualified if there is a prior >=, >, or ==.
sl@0	1146	** A == is disqualifed if there is any prior constraint.
sl@0	1147	*/
sl@0	1148	int j, opmsk;
sl@0	1149	static const unsigned char compatible[] = { 0, 0, 1, 1, 2, 2 };
sl@0	1150	assert( compatible[RTREE_EQ & 7]==0 );
sl@0	1151	assert( compatible[RTREE_LT & 7]==1 );
sl@0	1152	assert( compatible[RTREE_LE & 7]==1 );
sl@0	1153	assert( compatible[RTREE_GT & 7]==2 );
sl@0	1154	assert( compatible[RTREE_GE & 7]==2 );
sl@0	1155	cCol = p->iColumn - 1 + 'a';
sl@0	1156	opmsk = compatible[op & 7];
sl@0	1157	for(j=0; j<iIdx; j+=2){
sl@0	1158	if( zIdxStr[j+1]==cCol && (compatible[zIdxStr[j] & 7] & opmsk)!=0 ){
sl@0	1159	op = 0;
sl@0	1160	break;
sl@0	1161	}
sl@0	1162	}
sl@0	1163	}
sl@0	1164	if( op ){
sl@0	1165	assert( iIdx<sizeof(zIdxStr)-1 );
sl@0	1166	zIdxStr[iIdx++] = op;
sl@0	1167	zIdxStr[iIdx++] = cCol;
sl@0	1168	pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
sl@0	1169	pIdxInfo->aConstraintUsage[ii].omit = 1;
sl@0	1170	}
sl@0	1171	}
sl@0	1172	}
sl@0	1173
sl@0	1174	pIdxInfo->idxNum = 2;
sl@0	1175	pIdxInfo->needToFreeIdxStr = 1;
sl@0	1176	if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
sl@0	1177	return SQLITE_NOMEM;
sl@0	1178	}
sl@0	1179	assert( iIdx>=0 );
sl@0	1180	pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
sl@0	1181	return rc;
sl@0	1182	}
sl@0	1183
sl@0	1184	/*
sl@0	1185	** Return the N-dimensional volumn of the cell stored in *p.
sl@0	1186	*/
sl@0	1187	static float cellArea(Rtree pRtree, RtreeCell p){
sl@0	1188	float area = 1.0;
sl@0	1189	int ii;
sl@0	1190	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	1191	area = area * (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
sl@0	1192	}
sl@0	1193	return area;
sl@0	1194	}
sl@0	1195
sl@0	1196	/*
sl@0	1197	** Return the margin length of cell p. The margin length is the sum
sl@0	1198	** of the objects size in each dimension.
sl@0	1199	*/
sl@0	1200	static float cellMargin(Rtree pRtree, RtreeCell p){
sl@0	1201	float margin = 0.0;
sl@0	1202	int ii;
sl@0	1203	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	1204	margin += (DCOORD(p->aCoord[ii+1]) - DCOORD(p->aCoord[ii]));
sl@0	1205	}
sl@0	1206	return margin;
sl@0	1207	}
sl@0	1208
sl@0	1209	/*
sl@0	1210	** Store the union of cells p1 and p2 in p1.
sl@0	1211	*/
sl@0	1212	static void cellUnion(Rtree pRtree, RtreeCell p1, RtreeCell *p2){
sl@0	1213	int ii;
sl@0	1214	if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0	1215	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	1216	p1->aCoord[ii].f = MIN(p1->aCoord[ii].f, p2->aCoord[ii].f);
sl@0	1217	p1->aCoord[ii+1].f = MAX(p1->aCoord[ii+1].f, p2->aCoord[ii+1].f);
sl@0	1218	}
sl@0	1219	}else{
sl@0	1220	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	1221	p1->aCoord[ii].i = MIN(p1->aCoord[ii].i, p2->aCoord[ii].i);
sl@0	1222	p1->aCoord[ii+1].i = MAX(p1->aCoord[ii+1].i, p2->aCoord[ii+1].i);
sl@0	1223	}
sl@0	1224	}
sl@0	1225	}
sl@0	1226
sl@0	1227	/*
sl@0	1228	** Return true if the area covered by p2 is a subset of the area covered
sl@0	1229	** by p1. False otherwise.
sl@0	1230	*/
sl@0	1231	static int cellContains(Rtree pRtree, RtreeCell p1, RtreeCell *p2){
sl@0	1232	int ii;
sl@0	1233	int isInt = (pRtree->eCoordType==RTREE_COORD_INT32);
sl@0	1234	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	1235	RtreeCoord *a1 = &p1->aCoord[ii];
sl@0	1236	RtreeCoord *a2 = &p2->aCoord[ii];
sl@0	1237	if( (!isInt && (a2[0].f<a1[0].f \|\| a2[1].f>a1[1].f))
sl@0	1238	\|\| ( isInt && (a2[0].i<a1[0].i \|\| a2[1].i>a1[1].i))
sl@0	1239	){
sl@0	1240	return 0;
sl@0	1241	}
sl@0	1242	}
sl@0	1243	return 1;
sl@0	1244	}
sl@0	1245
sl@0	1246	/*
sl@0	1247	** Return the amount cell p would grow by if it were unioned with pCell.
sl@0	1248	*/
sl@0	1249	static float cellGrowth(Rtree pRtree, RtreeCell p, RtreeCell *pCell){
sl@0	1250	float area;
sl@0	1251	RtreeCell cell;
sl@0	1252	memcpy(&cell, p, sizeof(RtreeCell));
sl@0	1253	area = cellArea(pRtree, &cell);
sl@0	1254	cellUnion(pRtree, &cell, pCell);
sl@0	1255	return (cellArea(pRtree, &cell)-area);
sl@0	1256	}
sl@0	1257
sl@0	1258	#if VARIANT_RSTARTREE_CHOOSESUBTREE \|\| VARIANT_RSTARTREE_SPLIT
sl@0	1259	static float cellOverlap(
sl@0	1260	Rtree *pRtree,
sl@0	1261	RtreeCell *p,
sl@0	1262	RtreeCell *aCell,
sl@0	1263	int nCell,
sl@0	1264	int iExclude
sl@0	1265	){
sl@0	1266	int ii;
sl@0	1267	float overlap = 0.0;
sl@0	1268	for(ii=0; ii<nCell; ii++){
sl@0	1269	if( ii!=iExclude ){
sl@0	1270	int jj;
sl@0	1271	float o = 1.0;
sl@0	1272	for(jj=0; jj<(pRtree->nDim*2); jj+=2){
sl@0	1273	double x1;
sl@0	1274	double x2;
sl@0	1275
sl@0	1276	x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
sl@0	1277	x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
sl@0	1278
sl@0	1279	if( x2<x1 ){
sl@0	1280	o = 0.0;
sl@0	1281	break;
sl@0	1282	}else{
sl@0	1283	o = o * (x2-x1);
sl@0	1284	}
sl@0	1285	}
sl@0	1286	overlap += o;
sl@0	1287	}
sl@0	1288	}
sl@0	1289	return overlap;
sl@0	1290	}
sl@0	1291	#endif
sl@0	1292
sl@0	1293	#if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0	1294	static float cellOverlapEnlargement(
sl@0	1295	Rtree *pRtree,
sl@0	1296	RtreeCell *p,
sl@0	1297	RtreeCell *pInsert,
sl@0	1298	RtreeCell *aCell,
sl@0	1299	int nCell,
sl@0	1300	int iExclude
sl@0	1301	){
sl@0	1302	float before;
sl@0	1303	float after;
sl@0	1304	before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
sl@0	1305	cellUnion(pRtree, p, pInsert);
sl@0	1306	after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
sl@0	1307	return after-before;
sl@0	1308	}
sl@0	1309	#endif
sl@0	1310
sl@0	1311
sl@0	1312	/*
sl@0	1313	** This function implements the ChooseLeaf algorithm from Gutman[84].
sl@0	1314	** ChooseSubTree in r*tree terminology.
sl@0	1315	*/
sl@0	1316	static int ChooseLeaf(
sl@0	1317	Rtree pRtree, / Rtree table */
sl@0	1318	RtreeCell pCell, / Cell to insert into rtree */
sl@0	1319	int iHeight, /* Height of sub-tree rooted at pCell */
sl@0	1320	RtreeNode *ppLeaf / OUT: Selected leaf page */
sl@0	1321	){
sl@0	1322	int rc;
sl@0	1323	int ii;
sl@0	1324	RtreeNode *pNode;
sl@0	1325	rc = nodeAcquire(pRtree, 1, 0, &pNode);
sl@0	1326
sl@0	1327	for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){
sl@0	1328	int iCell;
sl@0	1329	sqlite3_int64 iBest;
sl@0	1330
sl@0	1331	float fMinGrowth;
sl@0	1332	float fMinArea;
sl@0	1333	float fMinOverlap;
sl@0	1334
sl@0	1335	int nCell = NCELL(pNode);
sl@0	1336	RtreeCell cell;
sl@0	1337	RtreeNode *pChild;
sl@0	1338
sl@0	1339	RtreeCell *aCell = 0;
sl@0	1340
sl@0	1341	#if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0	1342	if( ii==(pRtree->iDepth-1) ){
sl@0	1343	int jj;
sl@0	1344	aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
sl@0	1345	if( !aCell ){
sl@0	1346	rc = SQLITE_NOMEM;
sl@0	1347	nodeRelease(pRtree, pNode);
sl@0	1348	pNode = 0;
sl@0	1349	continue;
sl@0	1350	}
sl@0	1351	for(jj=0; jj<nCell; jj++){
sl@0	1352	nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
sl@0	1353	}
sl@0	1354	}
sl@0	1355	#endif
sl@0	1356
sl@0	1357	/* Select the child node which will be enlarged the least if pCell
sl@0	1358	** is inserted into it. Resolve ties by choosing the entry with
sl@0	1359	** the smallest area.
sl@0	1360	*/
sl@0	1361	for(iCell=0; iCell<nCell; iCell++){
sl@0	1362	float growth;
sl@0	1363	float area;
sl@0	1364	float overlap = 0.0;
sl@0	1365	nodeGetCell(pRtree, pNode, iCell, &cell);
sl@0	1366	growth = cellGrowth(pRtree, &cell, pCell);
sl@0	1367	area = cellArea(pRtree, &cell);
sl@0	1368	#if VARIANT_RSTARTREE_CHOOSESUBTREE
sl@0	1369	if( ii==(pRtree->iDepth-1) ){
sl@0	1370	overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
sl@0	1371	}
sl@0	1372	#endif
sl@0	1373	if( (iCell==0)
sl@0	1374	\|\| (overlap<fMinOverlap)
sl@0	1375	\|\| (overlap==fMinOverlap && growth<fMinGrowth)
sl@0	1376	\|\| (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
sl@0	1377	){
sl@0	1378	fMinOverlap = overlap;
sl@0	1379	fMinGrowth = growth;
sl@0	1380	fMinArea = area;
sl@0	1381	iBest = cell.iRowid;
sl@0	1382	}
sl@0	1383	}
sl@0	1384
sl@0	1385	sqlite3_free(aCell);
sl@0	1386	rc = nodeAcquire(pRtree, iBest, pNode, &pChild);
sl@0	1387	nodeRelease(pRtree, pNode);
sl@0	1388	pNode = pChild;
sl@0	1389	}
sl@0	1390
sl@0	1391	*ppLeaf = pNode;
sl@0	1392	return rc;
sl@0	1393	}
sl@0	1394
sl@0	1395	/*
sl@0	1396	** A cell with the same content as pCell has just been inserted into
sl@0	1397	** the node pNode. This function updates the bounding box cells in
sl@0	1398	** all ancestor elements.
sl@0	1399	*/
sl@0	1400	static void AdjustTree(
sl@0	1401	Rtree pRtree, / Rtree table */
sl@0	1402	RtreeNode pNode, / Adjust ancestry of this node. */
sl@0	1403	RtreeCell pCell / This cell was just inserted */
sl@0	1404	){
sl@0	1405	RtreeNode *p = pNode;
sl@0	1406	while( p->pParent ){
sl@0	1407	RtreeCell cell;
sl@0	1408	RtreeNode *pParent = p->pParent;
sl@0	1409	int iCell = nodeParentIndex(pRtree, p);
sl@0	1410
sl@0	1411	nodeGetCell(pRtree, pParent, iCell, &cell);
sl@0	1412	if( !cellContains(pRtree, &cell, pCell) ){
sl@0	1413	cellUnion(pRtree, &cell, pCell);
sl@0	1414	nodeOverwriteCell(pRtree, pParent, &cell, iCell);
sl@0	1415	}
sl@0	1416
sl@0	1417	p = pParent;
sl@0	1418	}
sl@0	1419	}
sl@0	1420
sl@0	1421	/*
sl@0	1422	** Write mapping (iRowid->iNode) to the <rtree>_rowid table.
sl@0	1423	*/
sl@0	1424	static int rowidWrite(Rtree *pRtree, sqlite3_int64 iRowid, sqlite3_int64 iNode){
sl@0	1425	sqlite3_bind_int64(pRtree->pWriteRowid, 1, iRowid);
sl@0	1426	sqlite3_bind_int64(pRtree->pWriteRowid, 2, iNode);
sl@0	1427	sqlite3_step(pRtree->pWriteRowid);
sl@0	1428	return sqlite3_reset(pRtree->pWriteRowid);
sl@0	1429	}
sl@0	1430
sl@0	1431	/*
sl@0	1432	** Write mapping (iNode->iPar) to the <rtree>_parent table.
sl@0	1433	*/
sl@0	1434	static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
sl@0	1435	sqlite3_bind_int64(pRtree->pWriteParent, 1, iNode);
sl@0	1436	sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar);
sl@0	1437	sqlite3_step(pRtree->pWriteParent);
sl@0	1438	return sqlite3_reset(pRtree->pWriteParent);
sl@0	1439	}
sl@0	1440
sl@0	1441	static int rtreeInsertCell(Rtree , RtreeNode , RtreeCell *, int);
sl@0	1442
sl@0	1443	#if VARIANT_GUTTMAN_LINEAR_SPLIT
sl@0	1444	/*
sl@0	1445	** Implementation of the linear variant of the PickNext() function from
sl@0	1446	** Guttman[84].
sl@0	1447	*/
sl@0	1448	static RtreeCell *LinearPickNext(
sl@0	1449	Rtree *pRtree,
sl@0	1450	RtreeCell *aCell,
sl@0	1451	int nCell,
sl@0	1452	RtreeCell *pLeftBox,
sl@0	1453	RtreeCell *pRightBox,
sl@0	1454	int *aiUsed
sl@0	1455	){
sl@0	1456	int ii;
sl@0	1457	for(ii=0; aiUsed[ii]; ii++);
sl@0	1458	aiUsed[ii] = 1;
sl@0	1459	return &aCell[ii];
sl@0	1460	}
sl@0	1461
sl@0	1462	/*
sl@0	1463	** Implementation of the linear variant of the PickSeeds() function from
sl@0	1464	** Guttman[84].
sl@0	1465	*/
sl@0	1466	static void LinearPickSeeds(
sl@0	1467	Rtree *pRtree,
sl@0	1468	RtreeCell *aCell,
sl@0	1469	int nCell,
sl@0	1470	int *piLeftSeed,
sl@0	1471	int *piRightSeed
sl@0	1472	){
sl@0	1473	int i;
sl@0	1474	int iLeftSeed = 0;
sl@0	1475	int iRightSeed = 1;
sl@0	1476	float maxNormalInnerWidth = 0.0;
sl@0	1477
sl@0	1478	/* Pick two "seed" cells from the array of cells. The algorithm used
sl@0	1479	** here is the LinearPickSeeds algorithm from Gutman[1984]. The
sl@0	1480	** indices of the two seed cells in the array are stored in local
sl@0	1481	** variables iLeftSeek and iRightSeed.
sl@0	1482	*/
sl@0	1483	for(i=0; i<pRtree->nDim; i++){
sl@0	1484	float x1 = aCell[0].aCoord[i*2];
sl@0	1485	float x2 = aCell[0].aCoord[i*2+1];
sl@0	1486	float x3 = x1;
sl@0	1487	float x4 = x2;
sl@0	1488	int jj;
sl@0	1489
sl@0	1490	int iCellLeft = 0;
sl@0	1491	int iCellRight = 0;
sl@0	1492
sl@0	1493	for(jj=1; jj<nCell; jj++){
sl@0	1494	float left = aCell[jj].aCoord[i*2];
sl@0	1495	float right = aCell[jj].aCoord[i*2+1];
sl@0	1496
sl@0	1497	if( left<x1 ) x1 = left;
sl@0	1498	if( right>x4 ) x4 = right;
sl@0	1499	if( left>x3 ){
sl@0	1500	x3 = left;
sl@0	1501	iCellRight = jj;
sl@0	1502	}
sl@0	1503	if( right<x2 ){
sl@0	1504	x2 = right;
sl@0	1505	iCellLeft = jj;
sl@0	1506	}
sl@0	1507	}
sl@0	1508
sl@0	1509	if( x4!=x1 ){
sl@0	1510	float normalwidth = (x3 - x2) / (x4 - x1);
sl@0	1511	if( normalwidth>maxNormalInnerWidth ){
sl@0	1512	iLeftSeed = iCellLeft;
sl@0	1513	iRightSeed = iCellRight;
sl@0	1514	}
sl@0	1515	}
sl@0	1516	}
sl@0	1517
sl@0	1518	*piLeftSeed = iLeftSeed;
sl@0	1519	*piRightSeed = iRightSeed;
sl@0	1520	}
sl@0	1521	#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
sl@0	1522
sl@0	1523	#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
sl@0	1524	/*
sl@0	1525	** Implementation of the quadratic variant of the PickNext() function from
sl@0	1526	** Guttman[84].
sl@0	1527	*/
sl@0	1528	static RtreeCell *QuadraticPickNext(
sl@0	1529	Rtree *pRtree,
sl@0	1530	RtreeCell *aCell,
sl@0	1531	int nCell,
sl@0	1532	RtreeCell *pLeftBox,
sl@0	1533	RtreeCell *pRightBox,
sl@0	1534	int *aiUsed
sl@0	1535	){
sl@0	1536	#define FABS(a) ((a)<0.0?-1.0*(a):(a))
sl@0	1537
sl@0	1538	int iSelect = -1;
sl@0	1539	float fDiff;
sl@0	1540	int ii;
sl@0	1541	for(ii=0; ii<nCell; ii++){
sl@0	1542	if( aiUsed[ii]==0 ){
sl@0	1543	float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
sl@0	1544	float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
sl@0	1545	float diff = FABS(right-left);
sl@0	1546	if( iSelect<0 \|\| diff>fDiff ){
sl@0	1547	fDiff = diff;
sl@0	1548	iSelect = ii;
sl@0	1549	}
sl@0	1550	}
sl@0	1551	}
sl@0	1552	aiUsed[iSelect] = 1;
sl@0	1553	return &aCell[iSelect];
sl@0	1554	}
sl@0	1555
sl@0	1556	/*
sl@0	1557	** Implementation of the quadratic variant of the PickSeeds() function from
sl@0	1558	** Guttman[84].
sl@0	1559	*/
sl@0	1560	static void QuadraticPickSeeds(
sl@0	1561	Rtree *pRtree,
sl@0	1562	RtreeCell *aCell,
sl@0	1563	int nCell,
sl@0	1564	int *piLeftSeed,
sl@0	1565	int *piRightSeed
sl@0	1566	){
sl@0	1567	int ii;
sl@0	1568	int jj;
sl@0	1569
sl@0	1570	int iLeftSeed = 0;
sl@0	1571	int iRightSeed = 1;
sl@0	1572	float fWaste = 0.0;
sl@0	1573
sl@0	1574	for(ii=0; ii<nCell; ii++){
sl@0	1575	for(jj=ii+1; jj<nCell; jj++){
sl@0	1576	float right = cellArea(pRtree, &aCell[jj]);
sl@0	1577	float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
sl@0	1578	float waste = growth - right;
sl@0	1579
sl@0	1580	if( waste>fWaste ){
sl@0	1581	iLeftSeed = ii;
sl@0	1582	iRightSeed = jj;
sl@0	1583	fWaste = waste;
sl@0	1584	}
sl@0	1585	}
sl@0	1586	}
sl@0	1587
sl@0	1588	*piLeftSeed = iLeftSeed;
sl@0	1589	*piRightSeed = iRightSeed;
sl@0	1590	}
sl@0	1591	#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
sl@0	1592
sl@0	1593	/*
sl@0	1594	** Arguments aIdx, aDistance and aSpare all point to arrays of size
sl@0	1595	** nIdx. The aIdx array contains the set of integers from 0 to
sl@0	1596	** (nIdx-1) in no particular order. This function sorts the values
sl@0	1597	** in aIdx according to the indexed values in aDistance. For
sl@0	1598	** example, assuming the inputs:
sl@0	1599	**
sl@0	1600	** aIdx = { 0, 1, 2, 3 }
sl@0	1601	** aDistance = { 5.0, 2.0, 7.0, 6.0 }
sl@0	1602	**
sl@0	1603	** this function sets the aIdx array to contain:
sl@0	1604	**
sl@0	1605	** aIdx = { 0, 1, 2, 3 }
sl@0	1606	**
sl@0	1607	** The aSpare array is used as temporary working space by the
sl@0	1608	** sorting algorithm.
sl@0	1609	*/
sl@0	1610	static void SortByDistance(
sl@0	1611	int *aIdx,
sl@0	1612	int nIdx,
sl@0	1613	float *aDistance,
sl@0	1614	int *aSpare
sl@0	1615	){
sl@0	1616	if( nIdx>1 ){
sl@0	1617	int iLeft = 0;
sl@0	1618	int iRight = 0;
sl@0	1619
sl@0	1620	int nLeft = nIdx/2;
sl@0	1621	int nRight = nIdx-nLeft;
sl@0	1622	int *aLeft = aIdx;
sl@0	1623	int *aRight = &aIdx[nLeft];
sl@0	1624
sl@0	1625	SortByDistance(aLeft, nLeft, aDistance, aSpare);
sl@0	1626	SortByDistance(aRight, nRight, aDistance, aSpare);
sl@0	1627
sl@0	1628	memcpy(aSpare, aLeft, sizeof(int)*nLeft);
sl@0	1629	aLeft = aSpare;
sl@0	1630
sl@0	1631	while( iLeft<nLeft \|\| iRight<nRight ){
sl@0	1632	if( iLeft==nLeft ){
sl@0	1633	aIdx[iLeft+iRight] = aRight[iRight];
sl@0	1634	iRight++;
sl@0	1635	}else if( iRight==nRight ){
sl@0	1636	aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0	1637	iLeft++;
sl@0	1638	}else{
sl@0	1639	float fLeft = aDistance[aLeft[iLeft]];
sl@0	1640	float fRight = aDistance[aRight[iRight]];
sl@0	1641	if( fLeft<fRight ){
sl@0	1642	aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0	1643	iLeft++;
sl@0	1644	}else{
sl@0	1645	aIdx[iLeft+iRight] = aRight[iRight];
sl@0	1646	iRight++;
sl@0	1647	}
sl@0	1648	}
sl@0	1649	}
sl@0	1650
sl@0	1651	#if 0
sl@0	1652	/* Check that the sort worked */
sl@0	1653	{
sl@0	1654	int jj;
sl@0	1655	for(jj=1; jj<nIdx; jj++){
sl@0	1656	float left = aDistance[aIdx[jj-1]];
sl@0	1657	float right = aDistance[aIdx[jj]];
sl@0	1658	assert( left<=right );
sl@0	1659	}
sl@0	1660	}
sl@0	1661	#endif
sl@0	1662	}
sl@0	1663	}
sl@0	1664
sl@0	1665	/*
sl@0	1666	** Arguments aIdx, aCell and aSpare all point to arrays of size
sl@0	1667	** nIdx. The aIdx array contains the set of integers from 0 to
sl@0	1668	** (nIdx-1) in no particular order. This function sorts the values
sl@0	1669	** in aIdx according to dimension iDim of the cells in aCell. The
sl@0	1670	** minimum value of dimension iDim is considered first, the
sl@0	1671	** maximum used to break ties.
sl@0	1672	**
sl@0	1673	** The aSpare array is used as temporary working space by the
sl@0	1674	** sorting algorithm.
sl@0	1675	*/
sl@0	1676	static void SortByDimension(
sl@0	1677	Rtree *pRtree,
sl@0	1678	int *aIdx,
sl@0	1679	int nIdx,
sl@0	1680	int iDim,
sl@0	1681	RtreeCell *aCell,
sl@0	1682	int *aSpare
sl@0	1683	){
sl@0	1684	if( nIdx>1 ){
sl@0	1685
sl@0	1686	int iLeft = 0;
sl@0	1687	int iRight = 0;
sl@0	1688
sl@0	1689	int nLeft = nIdx/2;
sl@0	1690	int nRight = nIdx-nLeft;
sl@0	1691	int *aLeft = aIdx;
sl@0	1692	int *aRight = &aIdx[nLeft];
sl@0	1693
sl@0	1694	SortByDimension(pRtree, aLeft, nLeft, iDim, aCell, aSpare);
sl@0	1695	SortByDimension(pRtree, aRight, nRight, iDim, aCell, aSpare);
sl@0	1696
sl@0	1697	memcpy(aSpare, aLeft, sizeof(int)*nLeft);
sl@0	1698	aLeft = aSpare;
sl@0	1699	while( iLeft<nLeft \|\| iRight<nRight ){
sl@0	1700	double xleft1 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2]);
sl@0	1701	double xleft2 = DCOORD(aCell[aLeft[iLeft]].aCoord[iDim*2+1]);
sl@0	1702	double xright1 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2]);
sl@0	1703	double xright2 = DCOORD(aCell[aRight[iRight]].aCoord[iDim*2+1]);
sl@0	1704	if( (iLeft!=nLeft) && ((iRight==nRight)
sl@0	1705	\|\| (xleft1<xright1)
sl@0	1706	\|\| (xleft1==xright1 && xleft2<xright2)
sl@0	1707	)){
sl@0	1708	aIdx[iLeft+iRight] = aLeft[iLeft];
sl@0	1709	iLeft++;
sl@0	1710	}else{
sl@0	1711	aIdx[iLeft+iRight] = aRight[iRight];
sl@0	1712	iRight++;
sl@0	1713	}
sl@0	1714	}
sl@0	1715
sl@0	1716	#if 0
sl@0	1717	/* Check that the sort worked */
sl@0	1718	{
sl@0	1719	int jj;
sl@0	1720	for(jj=1; jj<nIdx; jj++){
sl@0	1721	float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
sl@0	1722	float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
sl@0	1723	float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
sl@0	1724	float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
sl@0	1725	assert( xleft1<=xright1 && (xleft1<xright1 \|\| xleft2<=xright2) );
sl@0	1726	}
sl@0	1727	}
sl@0	1728	#endif
sl@0	1729	}
sl@0	1730	}
sl@0	1731
sl@0	1732	#if VARIANT_RSTARTREE_SPLIT
sl@0	1733	/*
sl@0	1734	** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
sl@0	1735	*/
sl@0	1736	static int splitNodeStartree(
sl@0	1737	Rtree *pRtree,
sl@0	1738	RtreeCell *aCell,
sl@0	1739	int nCell,
sl@0	1740	RtreeNode *pLeft,
sl@0	1741	RtreeNode *pRight,
sl@0	1742	RtreeCell *pBboxLeft,
sl@0	1743	RtreeCell *pBboxRight
sl@0	1744	){
sl@0	1745	int **aaSorted;
sl@0	1746	int *aSpare;
sl@0	1747	int ii;
sl@0	1748
sl@0	1749	int iBestDim;
sl@0	1750	int iBestSplit;
sl@0	1751	float fBestMargin;
sl@0	1752
sl@0	1753	int nByte = (pRtree->nDim+1)(sizeof(int)+nCell*sizeof(int));
sl@0	1754
sl@0	1755	aaSorted = (int **)sqlite3_malloc(nByte);
sl@0	1756	if( !aaSorted ){
sl@0	1757	return SQLITE_NOMEM;
sl@0	1758	}
sl@0	1759
sl@0	1760	aSpare = &((int )&aaSorted[pRtree->nDim])[pRtree->nDimnCell];
sl@0	1761	memset(aaSorted, 0, nByte);
sl@0	1762	for(ii=0; ii<pRtree->nDim; ii++){
sl@0	1763	int jj;
sl@0	1764	aaSorted[ii] = &((int )&aaSorted[pRtree->nDim])[iinCell];
sl@0	1765	for(jj=0; jj<nCell; jj++){
sl@0	1766	aaSorted[ii][jj] = jj;
sl@0	1767	}
sl@0	1768	SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare);
sl@0	1769	}
sl@0	1770
sl@0	1771	for(ii=0; ii<pRtree->nDim; ii++){
sl@0	1772	float margin = 0.0;
sl@0	1773	float fBestOverlap;
sl@0	1774	float fBestArea;
sl@0	1775	int iBestLeft;
sl@0	1776	int nLeft;
sl@0	1777
sl@0	1778	for(
sl@0	1779	nLeft=RTREE_MINCELLS(pRtree);
sl@0	1780	nLeft<=(nCell-RTREE_MINCELLS(pRtree));
sl@0	1781	nLeft++
sl@0	1782	){
sl@0	1783	RtreeCell left;
sl@0	1784	RtreeCell right;
sl@0	1785	int kk;
sl@0	1786	float overlap;
sl@0	1787	float area;
sl@0	1788
sl@0	1789	memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
sl@0	1790	memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof(RtreeCell));
sl@0	1791	for(kk=1; kk<(nCell-1); kk++){
sl@0	1792	if( kk<nLeft ){
sl@0	1793	cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]);
sl@0	1794	}else{
sl@0	1795	cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]);
sl@0	1796	}
sl@0	1797	}
sl@0	1798	margin += cellMargin(pRtree, &left);
sl@0	1799	margin += cellMargin(pRtree, &right);
sl@0	1800	overlap = cellOverlap(pRtree, &left, &right, 1, -1);
sl@0	1801	area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
sl@0	1802	if( (nLeft==RTREE_MINCELLS(pRtree))
sl@0	1803	\|\| (overlap<fBestOverlap)
sl@0	1804	\|\| (overlap==fBestOverlap && area<fBestArea)
sl@0	1805	){
sl@0	1806	iBestLeft = nLeft;
sl@0	1807	fBestOverlap = overlap;
sl@0	1808	fBestArea = area;
sl@0	1809	}
sl@0	1810	}
sl@0	1811
sl@0	1812	if( ii==0 \|\| margin<fBestMargin ){
sl@0	1813	iBestDim = ii;
sl@0	1814	fBestMargin = margin;
sl@0	1815	iBestSplit = iBestLeft;
sl@0	1816	}
sl@0	1817	}
sl@0	1818
sl@0	1819	memcpy(pBboxLeft, &aCell[aaSorted[iBestDim][0]], sizeof(RtreeCell));
sl@0	1820	memcpy(pBboxRight, &aCell[aaSorted[iBestDim][iBestSplit]], sizeof(RtreeCell));
sl@0	1821	for(ii=0; ii<nCell; ii++){
sl@0	1822	RtreeNode *pTarget = (ii<iBestSplit)?pLeft:pRight;
sl@0	1823	RtreeCell *pBbox = (ii<iBestSplit)?pBboxLeft:pBboxRight;
sl@0	1824	RtreeCell *pCell = &aCell[aaSorted[iBestDim][ii]];
sl@0	1825	nodeInsertCell(pRtree, pTarget, pCell);
sl@0	1826	cellUnion(pRtree, pBbox, pCell);
sl@0	1827	}
sl@0	1828
sl@0	1829	sqlite3_free(aaSorted);
sl@0	1830	return SQLITE_OK;
sl@0	1831	}
sl@0	1832	#endif
sl@0	1833
sl@0	1834	#if VARIANT_GUTTMAN_SPLIT
sl@0	1835	/*
sl@0	1836	** Implementation of the regular R-tree SplitNode from Guttman[1984].
sl@0	1837	*/
sl@0	1838	static int splitNodeGuttman(
sl@0	1839	Rtree *pRtree,
sl@0	1840	RtreeCell *aCell,
sl@0	1841	int nCell,
sl@0	1842	RtreeNode *pLeft,
sl@0	1843	RtreeNode *pRight,
sl@0	1844	RtreeCell *pBboxLeft,
sl@0	1845	RtreeCell *pBboxRight
sl@0	1846	){
sl@0	1847	int iLeftSeed = 0;
sl@0	1848	int iRightSeed = 1;
sl@0	1849	int *aiUsed;
sl@0	1850	int i;
sl@0	1851
sl@0	1852	aiUsed = sqlite3_malloc(sizeof(int)*nCell);
sl@0	1853	memset(aiUsed, 0, sizeof(int)*nCell);
sl@0	1854
sl@0	1855	PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
sl@0	1856
sl@0	1857	memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
sl@0	1858	memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
sl@0	1859	nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
sl@0	1860	nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
sl@0	1861	aiUsed[iLeftSeed] = 1;
sl@0	1862	aiUsed[iRightSeed] = 1;
sl@0	1863
sl@0	1864	for(i=nCell-2; i>0; i--){
sl@0	1865	RtreeCell *pNext;
sl@0	1866	pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
sl@0	1867	float diff =
sl@0	1868	cellGrowth(pRtree, pBboxLeft, pNext) -
sl@0	1869	cellGrowth(pRtree, pBboxRight, pNext)
sl@0	1870	;
sl@0	1871	if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
sl@0	1872	\|\| (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
sl@0	1873	){
sl@0	1874	nodeInsertCell(pRtree, pRight, pNext);
sl@0	1875	cellUnion(pRtree, pBboxRight, pNext);
sl@0	1876	}else{
sl@0	1877	nodeInsertCell(pRtree, pLeft, pNext);
sl@0	1878	cellUnion(pRtree, pBboxLeft, pNext);
sl@0	1879	}
sl@0	1880	}
sl@0	1881
sl@0	1882	sqlite3_free(aiUsed);
sl@0	1883	return SQLITE_OK;
sl@0	1884	}
sl@0	1885	#endif
sl@0	1886
sl@0	1887	static int updateMapping(
sl@0	1888	Rtree *pRtree,
sl@0	1889	i64 iRowid,
sl@0	1890	RtreeNode *pNode,
sl@0	1891	int iHeight
sl@0	1892	){
sl@0	1893	int (xSetMapping)(Rtree , sqlite3_int64, sqlite3_int64);
sl@0	1894	xSetMapping = ((iHeight==0)?rowidWrite:parentWrite);
sl@0	1895	if( iHeight>0 ){
sl@0	1896	RtreeNode *pChild = nodeHashLookup(pRtree, iRowid);
sl@0	1897	if( pChild ){
sl@0	1898	nodeRelease(pRtree, pChild->pParent);
sl@0	1899	nodeReference(pNode);
sl@0	1900	pChild->pParent = pNode;
sl@0	1901	}
sl@0	1902	}
sl@0	1903	return xSetMapping(pRtree, iRowid, pNode->iNode);
sl@0	1904	}
sl@0	1905
sl@0	1906	static int SplitNode(
sl@0	1907	Rtree *pRtree,
sl@0	1908	RtreeNode *pNode,
sl@0	1909	RtreeCell *pCell,
sl@0	1910	int iHeight
sl@0	1911	){
sl@0	1912	int i;
sl@0	1913	int newCellIsRight = 0;
sl@0	1914
sl@0	1915	int rc = SQLITE_OK;
sl@0	1916	int nCell = NCELL(pNode);
sl@0	1917	RtreeCell *aCell;
sl@0	1918	int *aiUsed;
sl@0	1919
sl@0	1920	RtreeNode *pLeft = 0;
sl@0	1921	RtreeNode *pRight = 0;
sl@0	1922
sl@0	1923	RtreeCell leftbbox;
sl@0	1924	RtreeCell rightbbox;
sl@0	1925
sl@0	1926	/* Allocate an array and populate it with a copy of pCell and
sl@0	1927	** all cells from node pLeft. Then zero the original node.
sl@0	1928	*/
sl@0	1929	aCell = sqlite3_malloc((sizeof(RtreeCell)+sizeof(int))*(nCell+1));
sl@0	1930	if( !aCell ){
sl@0	1931	rc = SQLITE_NOMEM;
sl@0	1932	goto splitnode_out;
sl@0	1933	}
sl@0	1934	aiUsed = (int *)&aCell[nCell+1];
sl@0	1935	memset(aiUsed, 0, sizeof(int)*(nCell+1));
sl@0	1936	for(i=0; i<nCell; i++){
sl@0	1937	nodeGetCell(pRtree, pNode, i, &aCell[i]);
sl@0	1938	}
sl@0	1939	nodeZero(pRtree, pNode);
sl@0	1940	memcpy(&aCell[nCell], pCell, sizeof(RtreeCell));
sl@0	1941	nCell++;
sl@0	1942
sl@0	1943	if( pNode->iNode==1 ){
sl@0	1944	pRight = nodeNew(pRtree, pNode, 1);
sl@0	1945	pLeft = nodeNew(pRtree, pNode, 1);
sl@0	1946	pRtree->iDepth++;
sl@0	1947	pNode->isDirty = 1;
sl@0	1948	writeInt16(pNode->zData, pRtree->iDepth);
sl@0	1949	}else{
sl@0	1950	pLeft = pNode;
sl@0	1951	pRight = nodeNew(pRtree, pLeft->pParent, 1);
sl@0	1952	nodeReference(pLeft);
sl@0	1953	}
sl@0	1954
sl@0	1955	if( !pLeft \|\| !pRight ){
sl@0	1956	rc = SQLITE_NOMEM;
sl@0	1957	goto splitnode_out;
sl@0	1958	}
sl@0	1959
sl@0	1960	memset(pLeft->zData, 0, pRtree->iNodeSize);
sl@0	1961	memset(pRight->zData, 0, pRtree->iNodeSize);
sl@0	1962
sl@0	1963	rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
sl@0	1964	if( rc!=SQLITE_OK ){
sl@0	1965	goto splitnode_out;
sl@0	1966	}
sl@0	1967
sl@0	1968	/* Ensure both child nodes have node numbers assigned to them. */
sl@0	1969	if( (0==pRight->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pRight)))
sl@0	1970	\|\| (0==pLeft->iNode && SQLITE_OK!=(rc = nodeWrite(pRtree, pLeft)))
sl@0	1971	){
sl@0	1972	goto splitnode_out;
sl@0	1973	}
sl@0	1974
sl@0	1975	rightbbox.iRowid = pRight->iNode;
sl@0	1976	leftbbox.iRowid = pLeft->iNode;
sl@0	1977
sl@0	1978	if( pNode->iNode==1 ){
sl@0	1979	rc = rtreeInsertCell(pRtree, pLeft->pParent, &leftbbox, iHeight+1);
sl@0	1980	if( rc!=SQLITE_OK ){
sl@0	1981	goto splitnode_out;
sl@0	1982	}
sl@0	1983	}else{
sl@0	1984	RtreeNode *pParent = pLeft->pParent;
sl@0	1985	int iCell = nodeParentIndex(pRtree, pLeft);
sl@0	1986	nodeOverwriteCell(pRtree, pParent, &leftbbox, iCell);
sl@0	1987	AdjustTree(pRtree, pParent, &leftbbox);
sl@0	1988	}
sl@0	1989	if( (rc = rtreeInsertCell(pRtree, pRight->pParent, &rightbbox, iHeight+1)) ){
sl@0	1990	goto splitnode_out;
sl@0	1991	}
sl@0	1992
sl@0	1993	for(i=0; i<NCELL(pRight); i++){
sl@0	1994	i64 iRowid = nodeGetRowid(pRtree, pRight, i);
sl@0	1995	rc = updateMapping(pRtree, iRowid, pRight, iHeight);
sl@0	1996	if( iRowid==pCell->iRowid ){
sl@0	1997	newCellIsRight = 1;
sl@0	1998	}
sl@0	1999	if( rc!=SQLITE_OK ){
sl@0	2000	goto splitnode_out;
sl@0	2001	}
sl@0	2002	}
sl@0	2003	if( pNode->iNode==1 ){
sl@0	2004	for(i=0; i<NCELL(pLeft); i++){
sl@0	2005	i64 iRowid = nodeGetRowid(pRtree, pLeft, i);
sl@0	2006	rc = updateMapping(pRtree, iRowid, pLeft, iHeight);
sl@0	2007	if( rc!=SQLITE_OK ){
sl@0	2008	goto splitnode_out;
sl@0	2009	}
sl@0	2010	}
sl@0	2011	}else if( newCellIsRight==0 ){
sl@0	2012	rc = updateMapping(pRtree, pCell->iRowid, pLeft, iHeight);
sl@0	2013	}
sl@0	2014
sl@0	2015	if( rc==SQLITE_OK ){
sl@0	2016	rc = nodeRelease(pRtree, pRight);
sl@0	2017	pRight = 0;
sl@0	2018	}
sl@0	2019	if( rc==SQLITE_OK ){
sl@0	2020	rc = nodeRelease(pRtree, pLeft);
sl@0	2021	pLeft = 0;
sl@0	2022	}
sl@0	2023
sl@0	2024	splitnode_out:
sl@0	2025	nodeRelease(pRtree, pRight);
sl@0	2026	nodeRelease(pRtree, pLeft);
sl@0	2027	sqlite3_free(aCell);
sl@0	2028	return rc;
sl@0	2029	}
sl@0	2030
sl@0	2031	static int fixLeafParent(Rtree pRtree, RtreeNode pLeaf){
sl@0	2032	int rc = SQLITE_OK;
sl@0	2033	if( pLeaf->iNode!=1 && pLeaf->pParent==0 ){
sl@0	2034	sqlite3_bind_int64(pRtree->pReadParent, 1, pLeaf->iNode);
sl@0	2035	if( sqlite3_step(pRtree->pReadParent)==SQLITE_ROW ){
sl@0	2036	i64 iNode = sqlite3_column_int64(pRtree->pReadParent, 0);
sl@0	2037	rc = nodeAcquire(pRtree, iNode, 0, &pLeaf->pParent);
sl@0	2038	}else{
sl@0	2039	rc = SQLITE_ERROR;
sl@0	2040	}
sl@0	2041	sqlite3_reset(pRtree->pReadParent);
sl@0	2042	if( rc==SQLITE_OK ){
sl@0	2043	rc = fixLeafParent(pRtree, pLeaf->pParent);
sl@0	2044	}
sl@0	2045	}
sl@0	2046	return rc;
sl@0	2047	}
sl@0	2048
sl@0	2049	static int deleteCell(Rtree , RtreeNode , int, int);
sl@0	2050
sl@0	2051	static int removeNode(Rtree pRtree, RtreeNode pNode, int iHeight){
sl@0	2052	int rc;
sl@0	2053	RtreeNode *pParent;
sl@0	2054	int iCell;
sl@0	2055
sl@0	2056	assert( pNode->nRef==1 );
sl@0	2057
sl@0	2058	/* Remove the entry in the parent cell. */
sl@0	2059	iCell = nodeParentIndex(pRtree, pNode);
sl@0	2060	pParent = pNode->pParent;
sl@0	2061	pNode->pParent = 0;
sl@0	2062	if( SQLITE_OK!=(rc = deleteCell(pRtree, pParent, iCell, iHeight+1))
sl@0	2063	\|\| SQLITE_OK!=(rc = nodeRelease(pRtree, pParent))
sl@0	2064	){
sl@0	2065	return rc;
sl@0	2066	}
sl@0	2067
sl@0	2068	/* Remove the xxx_node entry. */
sl@0	2069	sqlite3_bind_int64(pRtree->pDeleteNode, 1, pNode->iNode);
sl@0	2070	sqlite3_step(pRtree->pDeleteNode);
sl@0	2071	if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteNode)) ){
sl@0	2072	return rc;
sl@0	2073	}
sl@0	2074
sl@0	2075	/* Remove the xxx_parent entry. */
sl@0	2076	sqlite3_bind_int64(pRtree->pDeleteParent, 1, pNode->iNode);
sl@0	2077	sqlite3_step(pRtree->pDeleteParent);
sl@0	2078	if( SQLITE_OK!=(rc = sqlite3_reset(pRtree->pDeleteParent)) ){
sl@0	2079	return rc;
sl@0	2080	}
sl@0	2081
sl@0	2082	/* Remove the node from the in-memory hash table and link it into
sl@0	2083	** the Rtree.pDeleted list. Its contents will be re-inserted later on.
sl@0	2084	*/
sl@0	2085	nodeHashDelete(pRtree, pNode);
sl@0	2086	pNode->iNode = iHeight;
sl@0	2087	pNode->pNext = pRtree->pDeleted;
sl@0	2088	pNode->nRef++;
sl@0	2089	pRtree->pDeleted = pNode;
sl@0	2090
sl@0	2091	return SQLITE_OK;
sl@0	2092	}
sl@0	2093
sl@0	2094	static void fixBoundingBox(Rtree pRtree, RtreeNode pNode){
sl@0	2095	RtreeNode *pParent = pNode->pParent;
sl@0	2096	if( pParent ){
sl@0	2097	int ii;
sl@0	2098	int nCell = NCELL(pNode);
sl@0	2099	RtreeCell box; /* Bounding box for pNode */
sl@0	2100	nodeGetCell(pRtree, pNode, 0, &box);
sl@0	2101	for(ii=1; ii<nCell; ii++){
sl@0	2102	RtreeCell cell;
sl@0	2103	nodeGetCell(pRtree, pNode, ii, &cell);
sl@0	2104	cellUnion(pRtree, &box, &cell);
sl@0	2105	}
sl@0	2106	box.iRowid = pNode->iNode;
sl@0	2107	ii = nodeParentIndex(pRtree, pNode);
sl@0	2108	nodeOverwriteCell(pRtree, pParent, &box, ii);
sl@0	2109	fixBoundingBox(pRtree, pParent);
sl@0	2110	}
sl@0	2111	}
sl@0	2112
sl@0	2113	/*
sl@0	2114	** Delete the cell at index iCell of node pNode. After removing the
sl@0	2115	** cell, adjust the r-tree data structure if required.
sl@0	2116	*/
sl@0	2117	static int deleteCell(Rtree pRtree, RtreeNode pNode, int iCell, int iHeight){
sl@0	2118	int rc;
sl@0	2119
sl@0	2120	if( SQLITE_OK!=(rc = fixLeafParent(pRtree, pNode)) ){
sl@0	2121	return rc;
sl@0	2122	}
sl@0	2123
sl@0	2124	/* Remove the cell from the node. This call just moves bytes around
sl@0	2125	** the in-memory node image, so it cannot fail.
sl@0	2126	*/
sl@0	2127	nodeDeleteCell(pRtree, pNode, iCell);
sl@0	2128
sl@0	2129	/* If the node is not the tree root and now has less than the minimum
sl@0	2130	** number of cells, remove it from the tree. Otherwise, update the
sl@0	2131	** cell in the parent node so that it tightly contains the updated
sl@0	2132	** node.
sl@0	2133	*/
sl@0	2134	if( pNode->iNode!=1 ){
sl@0	2135	RtreeNode *pParent = pNode->pParent;
sl@0	2136	if( (pParent->iNode!=1 \|\| NCELL(pParent)!=1)
sl@0	2137	&& (NCELL(pNode)<RTREE_MINCELLS(pRtree))
sl@0	2138	){
sl@0	2139	rc = removeNode(pRtree, pNode, iHeight);
sl@0	2140	}else{
sl@0	2141	fixBoundingBox(pRtree, pNode);
sl@0	2142	}
sl@0	2143	}
sl@0	2144
sl@0	2145	return rc;
sl@0	2146	}
sl@0	2147
sl@0	2148	static int Reinsert(
sl@0	2149	Rtree *pRtree,
sl@0	2150	RtreeNode *pNode,
sl@0	2151	RtreeCell *pCell,
sl@0	2152	int iHeight
sl@0	2153	){
sl@0	2154	int *aOrder;
sl@0	2155	int *aSpare;
sl@0	2156	RtreeCell *aCell;
sl@0	2157	float *aDistance;
sl@0	2158	int nCell;
sl@0	2159	float aCenterCoord[RTREE_MAX_DIMENSIONS];
sl@0	2160	int iDim;
sl@0	2161	int ii;
sl@0	2162	int rc = SQLITE_OK;
sl@0	2163
sl@0	2164	memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
sl@0	2165
sl@0	2166	nCell = NCELL(pNode)+1;
sl@0	2167
sl@0	2168	/* Allocate the buffers used by this operation. The allocation is
sl@0	2169	** relinquished before this function returns.
sl@0	2170	*/
sl@0	2171	aCell = (RtreeCell )sqlite3_malloc(nCell (
sl@0	2172	sizeof(RtreeCell) + /* aCell array */
sl@0	2173	sizeof(int) + /* aOrder array */
sl@0	2174	sizeof(int) + /* aSpare array */
sl@0	2175	sizeof(float) /* aDistance array */
sl@0	2176	));
sl@0	2177	if( !aCell ){
sl@0	2178	return SQLITE_NOMEM;
sl@0	2179	}
sl@0	2180	aOrder = (int *)&aCell[nCell];
sl@0	2181	aSpare = (int *)&aOrder[nCell];
sl@0	2182	aDistance = (float *)&aSpare[nCell];
sl@0	2183
sl@0	2184	for(ii=0; ii<nCell; ii++){
sl@0	2185	if( ii==(nCell-1) ){
sl@0	2186	memcpy(&aCell[ii], pCell, sizeof(RtreeCell));
sl@0	2187	}else{
sl@0	2188	nodeGetCell(pRtree, pNode, ii, &aCell[ii]);
sl@0	2189	}
sl@0	2190	aOrder[ii] = ii;
sl@0	2191	for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0	2192	aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2]);
sl@0	2193	aCenterCoord[iDim] += DCOORD(aCell[ii].aCoord[iDim*2+1]);
sl@0	2194	}
sl@0	2195	}
sl@0	2196	for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0	2197	aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
sl@0	2198	}
sl@0	2199
sl@0	2200	for(ii=0; ii<nCell; ii++){
sl@0	2201	aDistance[ii] = 0.0;
sl@0	2202	for(iDim=0; iDim<pRtree->nDim; iDim++){
sl@0	2203	float coord = DCOORD(aCell[ii].aCoord[iDim*2+1]) -
sl@0	2204	DCOORD(aCell[ii].aCoord[iDim*2]);
sl@0	2205	aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
sl@0	2206	}
sl@0	2207	}
sl@0	2208
sl@0	2209	SortByDistance(aOrder, nCell, aDistance, aSpare);
sl@0	2210	nodeZero(pRtree, pNode);
sl@0	2211
sl@0	2212	for(ii=0; rc==SQLITE_OK && ii<(nCell-(RTREE_MINCELLS(pRtree)+1)); ii++){
sl@0	2213	RtreeCell *p = &aCell[aOrder[ii]];
sl@0	2214	nodeInsertCell(pRtree, pNode, p);
sl@0	2215	if( p->iRowid==pCell->iRowid ){
sl@0	2216	if( iHeight==0 ){
sl@0	2217	rc = rowidWrite(pRtree, p->iRowid, pNode->iNode);
sl@0	2218	}else{
sl@0	2219	rc = parentWrite(pRtree, p->iRowid, pNode->iNode);
sl@0	2220	}
sl@0	2221	}
sl@0	2222	}
sl@0	2223	if( rc==SQLITE_OK ){
sl@0	2224	fixBoundingBox(pRtree, pNode);
sl@0	2225	}
sl@0	2226	for(; rc==SQLITE_OK && ii<nCell; ii++){
sl@0	2227	/* Find a node to store this cell in. pNode->iNode currently contains
sl@0	2228	** the height of the sub-tree headed by the cell.
sl@0	2229	*/
sl@0	2230	RtreeNode *pInsert;
sl@0	2231	RtreeCell *p = &aCell[aOrder[ii]];
sl@0	2232	rc = ChooseLeaf(pRtree, p, iHeight, &pInsert);
sl@0	2233	if( rc==SQLITE_OK ){
sl@0	2234	int rc2;
sl@0	2235	rc = rtreeInsertCell(pRtree, pInsert, p, iHeight);
sl@0	2236	rc2 = nodeRelease(pRtree, pInsert);
sl@0	2237	if( rc==SQLITE_OK ){
sl@0	2238	rc = rc2;
sl@0	2239	}
sl@0	2240	}
sl@0	2241	}
sl@0	2242
sl@0	2243	sqlite3_free(aCell);
sl@0	2244	return rc;
sl@0	2245	}
sl@0	2246
sl@0	2247	/*
sl@0	2248	** Insert cell pCell into node pNode. Node pNode is the head of a
sl@0	2249	** subtree iHeight high (leaf nodes have iHeight==0).
sl@0	2250	*/
sl@0	2251	static int rtreeInsertCell(
sl@0	2252	Rtree *pRtree,
sl@0	2253	RtreeNode *pNode,
sl@0	2254	RtreeCell *pCell,
sl@0	2255	int iHeight
sl@0	2256	){
sl@0	2257	int rc = SQLITE_OK;
sl@0	2258	if( iHeight>0 ){
sl@0	2259	RtreeNode *pChild = nodeHashLookup(pRtree, pCell->iRowid);
sl@0	2260	if( pChild ){
sl@0	2261	nodeRelease(pRtree, pChild->pParent);
sl@0	2262	nodeReference(pNode);
sl@0	2263	pChild->pParent = pNode;
sl@0	2264	}
sl@0	2265	}
sl@0	2266	if( nodeInsertCell(pRtree, pNode, pCell) ){
sl@0	2267	#if VARIANT_RSTARTREE_REINSERT
sl@0	2268	if( iHeight<=pRtree->iReinsertHeight \|\| pNode->iNode==1){
sl@0	2269	rc = SplitNode(pRtree, pNode, pCell, iHeight);
sl@0	2270	}else{
sl@0	2271	pRtree->iReinsertHeight = iHeight;
sl@0	2272	rc = Reinsert(pRtree, pNode, pCell, iHeight);
sl@0	2273	}
sl@0	2274	#else
sl@0	2275	rc = SplitNode(pRtree, pNode, pCell, iHeight);
sl@0	2276	#endif
sl@0	2277	}else{
sl@0	2278	AdjustTree(pRtree, pNode, pCell);
sl@0	2279	if( iHeight==0 ){
sl@0	2280	rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode);
sl@0	2281	}else{
sl@0	2282	rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode);
sl@0	2283	}
sl@0	2284	}
sl@0	2285	return rc;
sl@0	2286	}
sl@0	2287
sl@0	2288	static int reinsertNodeContent(Rtree pRtree, RtreeNode pNode){
sl@0	2289	int ii;
sl@0	2290	int rc = SQLITE_OK;
sl@0	2291	int nCell = NCELL(pNode);
sl@0	2292
sl@0	2293	for(ii=0; rc==SQLITE_OK && ii<nCell; ii++){
sl@0	2294	RtreeNode *pInsert;
sl@0	2295	RtreeCell cell;
sl@0	2296	nodeGetCell(pRtree, pNode, ii, &cell);
sl@0	2297
sl@0	2298	/* Find a node to store this cell in. pNode->iNode currently contains
sl@0	2299	** the height of the sub-tree headed by the cell.
sl@0	2300	*/
sl@0	2301	rc = ChooseLeaf(pRtree, &cell, pNode->iNode, &pInsert);
sl@0	2302	if( rc==SQLITE_OK ){
sl@0	2303	int rc2;
sl@0	2304	rc = rtreeInsertCell(pRtree, pInsert, &cell, pNode->iNode);
sl@0	2305	rc2 = nodeRelease(pRtree, pInsert);
sl@0	2306	if( rc==SQLITE_OK ){
sl@0	2307	rc = rc2;
sl@0	2308	}
sl@0	2309	}
sl@0	2310	}
sl@0	2311	return rc;
sl@0	2312	}
sl@0	2313
sl@0	2314	/*
sl@0	2315	** Select a currently unused rowid for a new r-tree record.
sl@0	2316	*/
sl@0	2317	static int newRowid(Rtree pRtree, i64 piRowid){
sl@0	2318	int rc;
sl@0	2319	sqlite3_bind_null(pRtree->pWriteRowid, 1);
sl@0	2320	sqlite3_bind_null(pRtree->pWriteRowid, 2);
sl@0	2321	sqlite3_step(pRtree->pWriteRowid);
sl@0	2322	rc = sqlite3_reset(pRtree->pWriteRowid);
sl@0	2323	*piRowid = sqlite3_last_insert_rowid(pRtree->db);
sl@0	2324	return rc;
sl@0	2325	}
sl@0	2326
sl@0	2327	#ifndef NDEBUG
sl@0	2328	static int hashIsEmpty(Rtree *pRtree){
sl@0	2329	int ii;
sl@0	2330	for(ii=0; ii<HASHSIZE; ii++){
sl@0	2331	assert( !pRtree->aHash[ii] );
sl@0	2332	}
sl@0	2333	return 1;
sl@0	2334	}
sl@0	2335	#endif
sl@0	2336
sl@0	2337	/*
sl@0	2338	** The xUpdate method for rtree module virtual tables.
sl@0	2339	*/
sl@0	2340	int rtreeUpdate(
sl@0	2341	sqlite3_vtab *pVtab,
sl@0	2342	int nData,
sl@0	2343	sqlite3_value **azData,
sl@0	2344	sqlite_int64 *pRowid
sl@0	2345	){
sl@0	2346	Rtree pRtree = (Rtree )pVtab;
sl@0	2347	int rc = SQLITE_OK;
sl@0	2348
sl@0	2349	rtreeReference(pRtree);
sl@0	2350
sl@0	2351	assert(nData>=1);
sl@0	2352	assert(hashIsEmpty(pRtree));
sl@0	2353
sl@0	2354	/* If azData[0] is not an SQL NULL value, it is the rowid of a
sl@0	2355	** record to delete from the r-tree table. The following block does
sl@0	2356	** just that.
sl@0	2357	*/
sl@0	2358	if( sqlite3_value_type(azData[0])!=SQLITE_NULL ){
sl@0	2359	i64 iDelete; /* The rowid to delete */
sl@0	2360	RtreeNode pLeaf; / Leaf node containing record iDelete */
sl@0	2361	int iCell; /* Index of iDelete cell in pLeaf */
sl@0	2362	RtreeNode *pRoot;
sl@0	2363
sl@0	2364	/* Obtain a reference to the root node to initialise Rtree.iDepth */
sl@0	2365	rc = nodeAcquire(pRtree, 1, 0, &pRoot);
sl@0	2366
sl@0	2367	/* Obtain a reference to the leaf node that contains the entry
sl@0	2368	** about to be deleted.
sl@0	2369	*/
sl@0	2370	if( rc==SQLITE_OK ){
sl@0	2371	iDelete = sqlite3_value_int64(azData[0]);
sl@0	2372	rc = findLeafNode(pRtree, iDelete, &pLeaf);
sl@0	2373	}
sl@0	2374
sl@0	2375	/* Delete the cell in question from the leaf node. */
sl@0	2376	if( rc==SQLITE_OK ){
sl@0	2377	int rc2;
sl@0	2378	iCell = nodeRowidIndex(pRtree, pLeaf, iDelete);
sl@0	2379	rc = deleteCell(pRtree, pLeaf, iCell, 0);
sl@0	2380	rc2 = nodeRelease(pRtree, pLeaf);
sl@0	2381	if( rc==SQLITE_OK ){
sl@0	2382	rc = rc2;
sl@0	2383	}
sl@0	2384	}
sl@0	2385
sl@0	2386	/* Delete the corresponding entry in the <rtree>_rowid table. */
sl@0	2387	if( rc==SQLITE_OK ){
sl@0	2388	sqlite3_bind_int64(pRtree->pDeleteRowid, 1, iDelete);
sl@0	2389	sqlite3_step(pRtree->pDeleteRowid);
sl@0	2390	rc = sqlite3_reset(pRtree->pDeleteRowid);
sl@0	2391	}
sl@0	2392
sl@0	2393	/* Check if the root node now has exactly one child. If so, remove
sl@0	2394	** it, schedule the contents of the child for reinsertion and
sl@0	2395	** reduce the tree height by one.
sl@0	2396	**
sl@0	2397	** This is equivalent to copying the contents of the child into
sl@0	2398	** the root node (the operation that Gutman's paper says to perform
sl@0	2399	** in this scenario).
sl@0	2400	*/
sl@0	2401	if( rc==SQLITE_OK && pRtree->iDepth>0 ){
sl@0	2402	if( rc==SQLITE_OK && NCELL(pRoot)==1 ){
sl@0	2403	RtreeNode *pChild;
sl@0	2404	i64 iChild = nodeGetRowid(pRtree, pRoot, 0);
sl@0	2405	rc = nodeAcquire(pRtree, iChild, pRoot, &pChild);
sl@0	2406	if( rc==SQLITE_OK ){
sl@0	2407	rc = removeNode(pRtree, pChild, pRtree->iDepth-1);
sl@0	2408	}
sl@0	2409	if( rc==SQLITE_OK ){
sl@0	2410	pRtree->iDepth--;
sl@0	2411	writeInt16(pRoot->zData, pRtree->iDepth);
sl@0	2412	pRoot->isDirty = 1;
sl@0	2413	}
sl@0	2414	}
sl@0	2415	}
sl@0	2416
sl@0	2417	/* Re-insert the contents of any underfull nodes removed from the tree. */
sl@0	2418	for(pLeaf=pRtree->pDeleted; pLeaf; pLeaf=pRtree->pDeleted){
sl@0	2419	if( rc==SQLITE_OK ){
sl@0	2420	rc = reinsertNodeContent(pRtree, pLeaf);
sl@0	2421	}
sl@0	2422	pRtree->pDeleted = pLeaf->pNext;
sl@0	2423	sqlite3_free(pLeaf);
sl@0	2424	}
sl@0	2425
sl@0	2426	/* Release the reference to the root node. */
sl@0	2427	if( rc==SQLITE_OK ){
sl@0	2428	rc = nodeRelease(pRtree, pRoot);
sl@0	2429	}else{
sl@0	2430	nodeRelease(pRtree, pRoot);
sl@0	2431	}
sl@0	2432	}
sl@0	2433
sl@0	2434	/* If the azData[] array contains more than one element, elements
sl@0	2435	** (azData[2]..azData[argc-1]) contain a new record to insert into
sl@0	2436	** the r-tree structure.
sl@0	2437	*/
sl@0	2438	if( rc==SQLITE_OK && nData>1 ){
sl@0	2439	/* Insert a new record into the r-tree */
sl@0	2440	RtreeCell cell;
sl@0	2441	int ii;
sl@0	2442	RtreeNode *pLeaf;
sl@0	2443
sl@0	2444	/* Populate the cell.aCoord[] array. The first coordinate is azData[3]. */
sl@0	2445	assert( nData==(pRtree->nDim*2 + 3) );
sl@0	2446	if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
sl@0	2447	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	2448	cell.aCoord[ii].f = (float)sqlite3_value_double(azData[ii+3]);
sl@0	2449	cell.aCoord[ii+1].f = (float)sqlite3_value_double(azData[ii+4]);
sl@0	2450	if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
sl@0	2451	rc = SQLITE_CONSTRAINT;
sl@0	2452	goto constraint;
sl@0	2453	}
sl@0	2454	}
sl@0	2455	}else{
sl@0	2456	for(ii=0; ii<(pRtree->nDim*2); ii+=2){
sl@0	2457	cell.aCoord[ii].i = sqlite3_value_int(azData[ii+3]);
sl@0	2458	cell.aCoord[ii+1].i = sqlite3_value_int(azData[ii+4]);
sl@0	2459	if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
sl@0	2460	rc = SQLITE_CONSTRAINT;
sl@0	2461	goto constraint;
sl@0	2462	}
sl@0	2463	}
sl@0	2464	}
sl@0	2465
sl@0	2466	/* Figure out the rowid of the new row. */
sl@0	2467	if( sqlite3_value_type(azData[2])==SQLITE_NULL ){
sl@0	2468	rc = newRowid(pRtree, &cell.iRowid);
sl@0	2469	}else{
sl@0	2470	cell.iRowid = sqlite3_value_int64(azData[2]);
sl@0	2471	sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
sl@0	2472	if( SQLITE_ROW==sqlite3_step(pRtree->pReadRowid) ){
sl@0	2473	sqlite3_reset(pRtree->pReadRowid);
sl@0	2474	rc = SQLITE_CONSTRAINT;
sl@0	2475	goto constraint;
sl@0	2476	}
sl@0	2477	rc = sqlite3_reset(pRtree->pReadRowid);
sl@0	2478	}
sl@0	2479
sl@0	2480	if( rc==SQLITE_OK ){
sl@0	2481	rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
sl@0	2482	}
sl@0	2483	if( rc==SQLITE_OK ){
sl@0	2484	int rc2;
sl@0	2485	pRtree->iReinsertHeight = -1;
sl@0	2486	rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
sl@0	2487	rc2 = nodeRelease(pRtree, pLeaf);
sl@0	2488	if( rc==SQLITE_OK ){
sl@0	2489	rc = rc2;
sl@0	2490	}
sl@0	2491	}
sl@0	2492	}
sl@0	2493
sl@0	2494	constraint:
sl@0	2495	rtreeRelease(pRtree);
sl@0	2496	return rc;
sl@0	2497	}
sl@0	2498
sl@0	2499	/*
sl@0	2500	** The xRename method for rtree module virtual tables.
sl@0	2501	*/
sl@0	2502	static int rtreeRename(sqlite3_vtab pVtab, const char zNewName){
sl@0	2503	Rtree pRtree = (Rtree )pVtab;
sl@0	2504	int rc = SQLITE_NOMEM;
sl@0	2505	char *zSql = sqlite3_mprintf(
sl@0	2506	"ALTER TABLE %Q.'%q_node' RENAME TO \"%w_node\";"
sl@0	2507	"ALTER TABLE %Q.'%q_parent' RENAME TO \"%w_parent\";"
sl@0	2508	"ALTER TABLE %Q.'%q_rowid' RENAME TO \"%w_rowid\";"
sl@0	2509	, pRtree->zDb, pRtree->zName, zNewName
sl@0	2510	, pRtree->zDb, pRtree->zName, zNewName
sl@0	2511	, pRtree->zDb, pRtree->zName, zNewName
sl@0	2512	);
sl@0	2513	if( zSql ){
sl@0	2514	rc = sqlite3_exec(pRtree->db, zSql, 0, 0, 0);
sl@0	2515	sqlite3_free(zSql);
sl@0	2516	}
sl@0	2517	return rc;
sl@0	2518	}
sl@0	2519
sl@0	2520	static sqlite3_module rtreeModule = {
sl@0	2521	0, /* iVersion */
sl@0	2522	rtreeCreate, /* xCreate - create a table */
sl@0	2523	rtreeConnect, /* xConnect - connect to an existing table */
sl@0	2524	rtreeBestIndex, /* xBestIndex - Determine search strategy */
sl@0	2525	rtreeDisconnect, /* xDisconnect - Disconnect from a table */
sl@0	2526	rtreeDestroy, /* xDestroy - Drop a table */
sl@0	2527	rtreeOpen, /* xOpen - open a cursor */
sl@0	2528	rtreeClose, /* xClose - close a cursor */
sl@0	2529	rtreeFilter, /* xFilter - configure scan constraints */
sl@0	2530	rtreeNext, /* xNext - advance a cursor */
sl@0	2531	rtreeEof, /* xEof */
sl@0	2532	rtreeColumn, /* xColumn - read data */
sl@0	2533	rtreeRowid, /* xRowid - read data */
sl@0	2534	rtreeUpdate, /* xUpdate - write data */
sl@0	2535	0, /* xBegin - begin transaction */
sl@0	2536	0, /* xSync - sync transaction */
sl@0	2537	0, /* xCommit - commit transaction */
sl@0	2538	0, /* xRollback - rollback transaction */
sl@0	2539	0, /* xFindFunction - function overloading */
sl@0	2540	rtreeRename /* xRename - rename the table */
sl@0	2541	};
sl@0	2542
sl@0	2543	static int rtreeSqlInit(
sl@0	2544	Rtree *pRtree,
sl@0	2545	sqlite3 *db,
sl@0	2546	const char *zDb,
sl@0	2547	const char *zPrefix,
sl@0	2548	int isCreate
sl@0	2549	){
sl@0	2550	int rc = SQLITE_OK;
sl@0	2551
sl@0	2552	#define N_STATEMENT 9
sl@0	2553	static const char *azSql[N_STATEMENT] = {
sl@0	2554	/* Read and write the xxx_node table */
sl@0	2555	"SELECT data FROM '%q'.'%q_node' WHERE nodeno = :1",
sl@0	2556	"INSERT OR REPLACE INTO '%q'.'%q_node' VALUES(:1, :2)",
sl@0	2557	"DELETE FROM '%q'.'%q_node' WHERE nodeno = :1",
sl@0	2558
sl@0	2559	/* Read and write the xxx_rowid table */
sl@0	2560	"SELECT nodeno FROM '%q'.'%q_rowid' WHERE rowid = :1",
sl@0	2561	"INSERT OR REPLACE INTO '%q'.'%q_rowid' VALUES(:1, :2)",
sl@0	2562	"DELETE FROM '%q'.'%q_rowid' WHERE rowid = :1",
sl@0	2563
sl@0	2564	/* Read and write the xxx_parent table */
sl@0	2565	"SELECT parentnode FROM '%q'.'%q_parent' WHERE nodeno = :1",
sl@0	2566	"INSERT OR REPLACE INTO '%q'.'%q_parent' VALUES(:1, :2)",
sl@0	2567	"DELETE FROM '%q'.'%q_parent' WHERE nodeno = :1"
sl@0	2568	};
sl@0	2569	sqlite3_stmt **appStmt[N_STATEMENT];
sl@0	2570	int i;
sl@0	2571
sl@0	2572	pRtree->db = db;
sl@0	2573
sl@0	2574	if( isCreate ){
sl@0	2575	char *zCreate = sqlite3_mprintf(
sl@0	2576	"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
sl@0	2577	"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
sl@0	2578	"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
sl@0	2579	"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
sl@0	2580	zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
sl@0	2581	);
sl@0	2582	if( !zCreate ){
sl@0	2583	return SQLITE_NOMEM;
sl@0	2584	}
sl@0	2585	rc = sqlite3_exec(db, zCreate, 0, 0, 0);
sl@0	2586	sqlite3_free(zCreate);
sl@0	2587	if( rc!=SQLITE_OK ){
sl@0	2588	return rc;
sl@0	2589	}
sl@0	2590	}
sl@0	2591
sl@0	2592	appStmt[0] = &pRtree->pReadNode;
sl@0	2593	appStmt[1] = &pRtree->pWriteNode;
sl@0	2594	appStmt[2] = &pRtree->pDeleteNode;
sl@0	2595	appStmt[3] = &pRtree->pReadRowid;
sl@0	2596	appStmt[4] = &pRtree->pWriteRowid;
sl@0	2597	appStmt[5] = &pRtree->pDeleteRowid;
sl@0	2598	appStmt[6] = &pRtree->pReadParent;
sl@0	2599	appStmt[7] = &pRtree->pWriteParent;
sl@0	2600	appStmt[8] = &pRtree->pDeleteParent;
sl@0	2601
sl@0	2602	for(i=0; i<N_STATEMENT && rc==SQLITE_OK; i++){
sl@0	2603	char *zSql = sqlite3_mprintf(azSql[i], zDb, zPrefix);
sl@0	2604	if( zSql ){
sl@0	2605	rc = sqlite3_prepare_v2(db, zSql, -1, appStmt[i], 0);
sl@0	2606	}else{
sl@0	2607	rc = SQLITE_NOMEM;
sl@0	2608	}
sl@0	2609	sqlite3_free(zSql);
sl@0	2610	}
sl@0	2611
sl@0	2612	return rc;
sl@0	2613	}
sl@0	2614
sl@0	2615	/*
sl@0	2616	** This routine queries database handle db for the page-size used by
sl@0	2617	** database zDb. If successful, the page-size in bytes is written to
sl@0	2618	** *piPageSize and SQLITE_OK returned. Otherwise, and an SQLite error
sl@0	2619	** code is returned.
sl@0	2620	*/
sl@0	2621	static int getPageSize(sqlite3 db, const char zDb, int *piPageSize){
sl@0	2622	int rc = SQLITE_NOMEM;
sl@0	2623	char *zSql;
sl@0	2624	sqlite3_stmt *pStmt = 0;
sl@0	2625
sl@0	2626	zSql = sqlite3_mprintf("PRAGMA %Q.page_size", zDb);
sl@0	2627	if( !zSql ){
sl@0	2628	return SQLITE_NOMEM;
sl@0	2629	}
sl@0	2630
sl@0	2631	rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
sl@0	2632	sqlite3_free(zSql);
sl@0	2633	if( rc!=SQLITE_OK ){
sl@0	2634	return rc;
sl@0	2635	}
sl@0	2636
sl@0	2637	if( SQLITE_ROW==sqlite3_step(pStmt) ){
sl@0	2638	*piPageSize = sqlite3_column_int(pStmt, 0);
sl@0	2639	}
sl@0	2640	return sqlite3_finalize(pStmt);
sl@0	2641	}
sl@0	2642
sl@0	2643	/*
sl@0	2644	** This function is the implementation of both the xConnect and xCreate
sl@0	2645	** methods of the r-tree virtual table.
sl@0	2646	**
sl@0	2647	** argv[0] -> module name
sl@0	2648	** argv[1] -> database name
sl@0	2649	** argv[2] -> table name
sl@0	2650	** argv[...] -> column names...
sl@0	2651	*/
sl@0	2652	static int rtreeInit(
sl@0	2653	sqlite3 db, / Database connection */
sl@0	2654	void pAux, / Pointer to head of rtree list */
sl@0	2655	int argc, const char constargv, /* Parameters to CREATE TABLE statement */
sl@0	2656	sqlite3_vtab *ppVtab, / OUT: New virtual table */
sl@0	2657	char *pzErr, / OUT: Error message, if any */
sl@0	2658	int isCreate, /* True for xCreate, false for xConnect */
sl@0	2659	int eCoordType /* One of the RTREE_COORD_* constants */
sl@0	2660	){
sl@0	2661	int rc = SQLITE_OK;
sl@0	2662	int iPageSize = 0;
sl@0	2663	Rtree *pRtree;
sl@0	2664	int nDb; /* Length of string argv[1] */
sl@0	2665	int nName; /* Length of string argv[2] */
sl@0	2666
sl@0	2667	const char *aErrMsg[] = {
sl@0	2668	0, /* 0 */
sl@0	2669	"Wrong number of columns for an rtree table", /* 1 */
sl@0	2670	"Too few columns for an rtree table", /* 2 */
sl@0	2671	"Too many columns for an rtree table" /* 3 */
sl@0	2672	};
sl@0	2673
sl@0	2674	int iErr = (argc<6) ? 2 : argc>(RTREE_MAX_DIMENSIONS*2+4) ? 3 : argc%2;
sl@0	2675	if( aErrMsg[iErr] ){
sl@0	2676	*pzErr = sqlite3_mprintf("%s", aErrMsg[iErr]);
sl@0	2677	return SQLITE_ERROR;
sl@0	2678	}
sl@0	2679
sl@0	2680	rc = getPageSize(db, argv[1], &iPageSize);
sl@0	2681	if( rc!=SQLITE_OK ){
sl@0	2682	return rc;
sl@0	2683	}
sl@0	2684
sl@0	2685	/* Allocate the sqlite3_vtab structure */
sl@0	2686	nDb = strlen(argv[1]);
sl@0	2687	nName = strlen(argv[2]);
sl@0	2688	pRtree = (Rtree *)sqlite3_malloc(sizeof(Rtree)+nDb+nName+2);
sl@0	2689	if( !pRtree ){
sl@0	2690	return SQLITE_NOMEM;
sl@0	2691	}
sl@0	2692	memset(pRtree, 0, sizeof(Rtree)+nDb+nName+2);
sl@0	2693	pRtree->nBusy = 1;
sl@0	2694	pRtree->base.pModule = &rtreeModule;
sl@0	2695	pRtree->zDb = (char *)&pRtree[1];
sl@0	2696	pRtree->zName = &pRtree->zDb[nDb+1];
sl@0	2697	pRtree->nDim = (argc-4)/2;
sl@0	2698	pRtree->nBytesPerCell = 8 + pRtree->nDim42;
sl@0	2699	pRtree->eCoordType = eCoordType;
sl@0	2700	memcpy(pRtree->zDb, argv[1], nDb);
sl@0	2701	memcpy(pRtree->zName, argv[2], nName);
sl@0	2702
sl@0	2703	/* Figure out the node size to use. By default, use 64 bytes less than
sl@0	2704	** the database page-size. This ensures that each node is stored on
sl@0	2705	** a single database page.
sl@0	2706	**
sl@0	2707	** If the databasd page-size is so large that more than RTREE_MAXCELLS
sl@0	2708	** entries would fit in a single node, use a smaller node-size.
sl@0	2709	*/
sl@0	2710	pRtree->iNodeSize = iPageSize-64;
sl@0	2711	if( (4+pRtree->nBytesPerCell*RTREE_MAXCELLS)<pRtree->iNodeSize ){
sl@0	2712	pRtree->iNodeSize = 4+pRtree->nBytesPerCell*RTREE_MAXCELLS;
sl@0	2713	}
sl@0	2714
sl@0	2715	/* Create/Connect to the underlying relational database schema. If
sl@0	2716	** that is successful, call sqlite3_declare_vtab() to configure
sl@0	2717	** the r-tree table schema.
sl@0	2718	*/
sl@0	2719	if( (rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate)) ){
sl@0	2720	*pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
sl@0	2721	}else{
sl@0	2722	char *zSql = sqlite3_mprintf("CREATE TABLE x(%s", argv[3]);
sl@0	2723	char *zTmp;
sl@0	2724	int ii;
sl@0	2725	for(ii=4; zSql && ii<argc; ii++){
sl@0	2726	zTmp = zSql;
sl@0	2727	zSql = sqlite3_mprintf("%s, %s", zTmp, argv[ii]);
sl@0	2728	sqlite3_free(zTmp);
sl@0	2729	}
sl@0	2730	if( zSql ){
sl@0	2731	zTmp = zSql;
sl@0	2732	zSql = sqlite3_mprintf("%s);", zTmp);
sl@0	2733	sqlite3_free(zTmp);
sl@0	2734	}
sl@0	2735	if( !zSql \|\| sqlite3_declare_vtab(db, zSql) ){
sl@0	2736	rc = SQLITE_NOMEM;
sl@0	2737	}
sl@0	2738	sqlite3_free(zSql);
sl@0	2739	}
sl@0	2740
sl@0	2741	if( rc==SQLITE_OK ){
sl@0	2742	ppVtab = (sqlite3_vtab )pRtree;
sl@0	2743	}else{
sl@0	2744	rtreeRelease(pRtree);
sl@0	2745	}
sl@0	2746	return rc;
sl@0	2747	}
sl@0	2748
sl@0	2749
sl@0	2750	/*
sl@0	2751	** Implementation of a scalar function that decodes r-tree nodes to
sl@0	2752	** human readable strings. This can be used for debugging and analysis.
sl@0	2753	**
sl@0	2754	** The scalar function takes two arguments, a blob of data containing
sl@0	2755	** an r-tree node, and the number of dimensions the r-tree indexes.
sl@0	2756	** For a two-dimensional r-tree structure called "rt", to deserialize
sl@0	2757	** all nodes, a statement like:
sl@0	2758	**
sl@0	2759	** SELECT rtreenode(2, data) FROM rt_node;
sl@0	2760	**
sl@0	2761	** The human readable string takes the form of a Tcl list with one
sl@0	2762	** entry for each cell in the r-tree node. Each entry is itself a
sl@0	2763	** list, containing the 8-byte rowid/pageno followed by the
sl@0	2764	** <num-dimension>*2 coordinates.
sl@0	2765	*/
sl@0	2766	static void rtreenode(sqlite3_context ctx, int nArg, sqlite3_value *apArg){
sl@0	2767	char *zText = 0;
sl@0	2768	RtreeNode node;
sl@0	2769	Rtree tree;
sl@0	2770	int ii;
sl@0	2771
sl@0	2772	memset(&node, 0, sizeof(RtreeNode));
sl@0	2773	memset(&tree, 0, sizeof(Rtree));
sl@0	2774	tree.nDim = sqlite3_value_int(apArg[0]);
sl@0	2775	tree.nBytesPerCell = 8 + 8 * tree.nDim;
sl@0	2776	node.zData = (u8 *)sqlite3_value_blob(apArg[1]);
sl@0	2777
sl@0	2778	for(ii=0; ii<NCELL(&node); ii++){
sl@0	2779	char zCell[512];
sl@0	2780	int nCell = 0;
sl@0	2781	RtreeCell cell;
sl@0	2782	int jj;
sl@0	2783
sl@0	2784	nodeGetCell(&tree, &node, ii, &cell);
sl@0	2785	sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid);
sl@0	2786	nCell = strlen(zCell);
sl@0	2787	for(jj=0; jj<tree.nDim*2; jj++){
sl@0	2788	sqlite3_snprintf(512-nCell,&zCell[nCell]," %f",(double)cell.aCoord[jj].f);
sl@0	2789	nCell = strlen(zCell);
sl@0	2790	}
sl@0	2791
sl@0	2792	if( zText ){
sl@0	2793	char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell);
sl@0	2794	sqlite3_free(zText);
sl@0	2795	zText = zTextNew;
sl@0	2796	}else{
sl@0	2797	zText = sqlite3_mprintf("{%s}", zCell);
sl@0	2798	}
sl@0	2799	}
sl@0	2800
sl@0	2801	sqlite3_result_text(ctx, zText, -1, sqlite3_free);
sl@0	2802	}
sl@0	2803
sl@0	2804	static void rtreedepth(sqlite3_context ctx, int nArg, sqlite3_value *apArg){
sl@0	2805	if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB
sl@0	2806	\|\| sqlite3_value_bytes(apArg[0])<2
sl@0	2807	){
sl@0	2808	sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1);
sl@0	2809	}else{
sl@0	2810	u8 zBlob = (u8 )sqlite3_value_blob(apArg[0]);
sl@0	2811	sqlite3_result_int(ctx, readInt16(zBlob));
sl@0	2812	}
sl@0	2813	}
sl@0	2814
sl@0	2815	/*
sl@0	2816	** Register the r-tree module with database handle db. This creates the
sl@0	2817	** virtual table module "rtree" and the debugging/analysis scalar
sl@0	2818	** function "rtreenode".
sl@0	2819	*/
sl@0	2820	int sqlite3RtreeInit(sqlite3 *db){
sl@0	2821	int rc = SQLITE_OK;
sl@0	2822
sl@0	2823	if( rc==SQLITE_OK ){
sl@0	2824	int utf8 = SQLITE_UTF8;
sl@0	2825	rc = sqlite3_create_function(db, "rtreenode", 2, utf8, 0, rtreenode, 0, 0);
sl@0	2826	}
sl@0	2827	if( rc==SQLITE_OK ){
sl@0	2828	int utf8 = SQLITE_UTF8;
sl@0	2829	rc = sqlite3_create_function(db, "rtreedepth", 1, utf8, 0,rtreedepth, 0, 0);
sl@0	2830	}
sl@0	2831	if( rc==SQLITE_OK ){
sl@0	2832	void c = (void )RTREE_COORD_REAL32;
sl@0	2833	rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
sl@0	2834	}
sl@0	2835	if( rc==SQLITE_OK ){
sl@0	2836	void c = (void )RTREE_COORD_INT32;
sl@0	2837	rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
sl@0	2838	}
sl@0	2839
sl@0	2840	return rc;
sl@0	2841	}
sl@0	2842
sl@0	2843	#if !SQLITE_CORE
sl@0	2844	int sqlite3_extension_init(
sl@0	2845	sqlite3 *db,
sl@0	2846	char **pzErrMsg,
sl@0	2847	const sqlite3_api_routines *pApi
sl@0	2848	){
sl@0	2849	SQLITE_EXTENSION_INIT2(pApi)
sl@0	2850	return sqlite3RtreeInit(db);
sl@0	2851	}
sl@0	2852	#endif
sl@0	2853
sl@0	2854	#endif

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--