/*

** 2001 September 15

**

** The author disclaims copyright to this source code.  In place of

** a legal notice, here is a blessing:

**

**    May you do good and not evil.

**    May you find forgiveness for yourself and forgive others.

**    May you share freely, never taking more than you give.

**

*************************************************************************

** This file contains code for implementations of the r-tree and r*-tree

** algorithms packaged as an SQLite virtual table module.

**

** $Id: rtree.c,v 1.9 2008/09/08 11:07:03 danielk1977 Exp $

*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*

** This file contains an implementation of a couple of different variants

** of the r-tree algorithm. See the README file for further details. The 

** same data-structure is used for all, but the algorithms for insert and

** delete operations vary. The variants used are selected at compile time 

** by defining the following symbols:

*/

/* Either, both or none of the following may be set to activate 

** r*tree variant algorithms.

*/

#define VARIANT_RSTARTREE_CHOOSESUBTREE 0

#define VARIANT_RSTARTREE_REINSERT      1

/* 

** Exactly one of the following must be set to 1.

*/

#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0

#define VARIANT_GUTTMAN_LINEAR_SPLIT    0

#define VARIANT_RSTARTREE_SPLIT         1

#define VARIANT_GUTTMAN_SPLIT \

        (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)

#if VARIANT_GUTTMAN_QUADRATIC_SPLIT

  #define PickNext QuadraticPickNext

  #define PickSeeds QuadraticPickSeeds

  #define AssignCells splitNodeGuttman

#endif

#if VARIANT_GUTTMAN_LINEAR_SPLIT

  #define PickNext LinearPickNext

  #define PickSeeds LinearPickSeeds

  #define AssignCells splitNodeGuttman

#endif

#if VARIANT_RSTARTREE_SPLIT

  #define AssignCells splitNodeStartree

#endif

#ifndef SQLITE_CORE

  #include "sqlite3ext.h"

  SQLITE_EXTENSION_INIT1

#else

  #include "sqlite3.h"

#endif

#include <string.h>

#include <assert.h>

#ifndef SQLITE_AMALGAMATION

typedef sqlite3_int64 i64;

typedef unsigned char u8;

typedef unsigned int u32;

#endif

typedef struct Rtree Rtree;

typedef struct RtreeCursor RtreeCursor;

typedef struct RtreeNode RtreeNode;

typedef struct RtreeCell RtreeCell;

typedef struct RtreeConstraint RtreeConstraint;

typedef union RtreeCoord RtreeCoord;

/* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */

#define RTREE_MAX_DIMENSIONS 5

/* Size of hash table Rtree.aHash. This hash table is not expected to

** ever contain very many entries, so a fixed number of buckets is 

** used.

*/

#define HASHSIZE 128

/* 

** An rtree virtual-table object.

*/

struct Rtree {

  sqlite3_vtab base;

  sqlite3 *db;                /* Host database connection */

  int iNodeSize;              /* Size in bytes of each node in the node table */

  int nDim;                   /* Number of dimensions */

  int nBytesPerCell;          /* Bytes consumed per cell */

  int iDepth;                 /* Current depth of the r-tree structure */

  char *zDb;                  /* Name of database containing r-tree table */

  char *zName;                /* Name of r-tree table */ 

  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 

  int nBusy;                  /* Current number of users of this structure */

  /* List of nodes removed during a CondenseTree operation. List is

  ** linked together via the pointer normally used for hash chains -

  ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree 

  ** headed by the node (leaf nodes have RtreeNode.iNode==0).

  */

  RtreeNode *pDeleted;

  int iReinsertHeight;        /* Height of sub-trees Reinsert() has run on */

  /* Statements to read/write/delete a record from xxx_node */

  sqlite3_stmt *pReadNode;

  sqlite3_stmt *pWriteNode;

  sqlite3_stmt *pDeleteNode;

  /* Statements to read/write/delete a record from xxx_rowid */

  sqlite3_stmt *pReadRowid;

  sqlite3_stmt *pWriteRowid;

  sqlite3_stmt *pDeleteRowid;

  /* Statements to read/write/delete a record from xxx_parent */

  sqlite3_stmt *pReadParent;

  sqlite3_stmt *pWriteParent;

  sqlite3_stmt *pDeleteParent;

  int eCoordType;

};

/* Possible values for eCoordType: */

#define RTREE_COORD_REAL32 0

#define RTREE_COORD_INT32  1

/*

** The minimum number of cells allowed for a node is a third of the 

** maximum. In Gutman's notation:

**

**     m = M/3

**

** If an R*-tree "Reinsert" operation is required, the same number of

** cells are removed from the overfull node and reinserted into the tree.

*/

#define RTREE_MINCELLS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerCell)/3)

#define RTREE_REINSERT(p) RTREE_MINCELLS(p)

#define RTREE_MAXCELLS 51

/* 

** An rtree cursor object.

*/

struct RtreeCursor {

  sqlite3_vtab_cursor base;

  RtreeNode *pNode;                 /* Node cursor is currently pointing at */

  int iCell;                        /* Index of current cell in pNode */

  int iStrategy;                    /* Copy of idxNum search parameter */

  int nConstraint;                  /* Number of entries in aConstraint */

  RtreeConstraint *aConstraint;     /* Search constraints. */

};

union RtreeCoord {

  float f;

  int i;

};

/*

** The argument is an RtreeCoord. Return the value stored within the RtreeCoord

** formatted as a double. This macro assumes that local variable pRtree points

** to the Rtree structure associated with the RtreeCoord.

*/

#define DCOORD(coord) (                           \

  (pRtree->eCoordType==RTREE_COORD_REAL32) ?      \

    ((double)coord.f) :                           \

    ((double)coord.i)                             \

)

/*

** A search constraint.

*/

struct RtreeConstraint {

  int iCoord;                       /* Index of constrained coordinate */

  int op;                           /* Constraining operation */

  double rValue;                    /* Constraint value. */

};

/* Possible values for RtreeConstraint.op */

#define RTREE_EQ 0x41

#define RTREE_LE 0x42

#define RTREE_LT 0x43

#define RTREE_GE 0x44

#define RTREE_GT 0x45

/* 

** An rtree structure node.

**

** Data format (RtreeNode.zData):

**

**   1. If the node is the root node (node 1), then the first 2 bytes

**      of the node contain the tree depth as a big-endian integer.

**      For non-root nodes, the first 2 bytes are left unused.

**

**   2. The next 2 bytes contain the number of entries currently 

**      stored in the node.

**

**   3. The remainder of the node contains the node entries. Each entry

**      consists of a single 8-byte integer followed by an even number

**      of 4-byte coordinates. For leaf nodes the integer is the rowid

**      of a record. For internal nodes it is the node number of a

**      child page.

*/

struct RtreeNode {

  RtreeNode *pParent;               /* Parent node */

  i64 iNode;

  int nRef;

  int isDirty;

  u8 *zData;

  RtreeNode *pNext;                 /* Next node in this hash chain */

};

#define NCELL(pNode) readInt16(&(pNode)->zData[2])

/* 

** Structure to store a deserialized rtree record.

*/

struct RtreeCell {

  i64 iRowid;

  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];

};

#define MAX(x,y) ((x) < (y) ? (y) : (x))

#define MIN(x,y) ((x) > (y) ? (y) : (x))

/*

** Functions to deserialize a 16 bit integer, 32 bit real number and

** 64 bit integer. The deserialized value is returned.

*/

static int readInt16(u8 *p){

  return (p[0]<<8) + p[1];

}

static void readCoord(u8 *p, RtreeCoord *pCoord){

  u32 i = (

    (((u32)p[0]) << 24) + 

    (((u32)p[1]) << 16) + 

    (((u32)p[2]) <<  8) + 

    (((u32)p[3]) <<  0)

  );

  *(u32 *)pCoord = i;

}

static i64 readInt64(u8 *p){

  return (

    (((i64)p[0]) << 56) + 

    (((i64)p[1]) << 48) + 

    (((i64)p[2]) << 40) + 

    (((i64)p[3]) << 32) + 

    (((i64)p[4]) << 24) + 

    (((i64)p[5]) << 16) + 

    (((i64)p[6]) <<  8) + 

    (((i64)p[7]) <<  0)

  );

}

/*

** Functions to serialize a 16 bit integer, 32 bit real number and

** 64 bit integer. The value returned is the number of bytes written

** to the argument buffer (always 2, 4 and 8 respectively).

*/

static int writeInt16(u8 *p, int i){

  p[0] = (i>> 8)&0xFF;

  p[1] = (i>> 0)&0xFF;

  return 2;

}

static int writeCoord(u8 *p, RtreeCoord *pCoord){

  u32 i;

  assert( sizeof(RtreeCoord)==4 );

  assert( sizeof(u32)==4 );

  i = *(u32 *)pCoord;

  p[0] = (i>>24)&0xFF;

  p[1] = (i>>16)&0xFF;

  p[2] = (i>> 8)&0xFF;

  p[3] = (i>> 0)&0xFF;

  return 4;

}

static int writeInt64(u8 *p, i64 i){

  p[0] = (i>>56)&0xFF;

  p[1] = (i>>48)&0xFF;

  p[2] = (i>>40)&0xFF;

  p[3] = (i>>32)&0xFF;

  p[4] = (i>>24)&0xFF;

  p[5] = (i>>16)&0xFF;

  p[6] = (i>> 8)&0xFF;

  p[7] = (i>> 0)&0xFF;

  return 8;

}

/*

** Increment the reference count of node p.

*/

static void nodeReference(RtreeNode *p){

  if( p ){

    p->nRef++;

  }

}

/*

** Clear the content of node p (set all bytes to 0x00).

*/

static void nodeZero(Rtree *pRtree, RtreeNode *p){

  if( p ){

    memset(&p->zData[2], 0, pRtree->iNodeSize-2);

    p->isDirty = 1;

  }

}

/*

** Given a node number iNode, return the corresponding key to use

** in the Rtree.aHash table.

*/

static int nodeHash(i64 iNode){

  return (

    (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 

    (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)

  ) % HASHSIZE;

}

/*

** Search the node hash table for node iNode. If found, return a pointer

** to it. Otherwise, return 0.

*/

static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){

  RtreeNode *p;

  assert( iNode!=0 );

  for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext);

  return p;

}

/*

** Add node pNode to the node hash table.

*/

static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){

  if( pNode ){

    int iHash;

    assert( pNode->pNext==0 );

    iHash = nodeHash(pNode->iNode);

    pNode->pNext = pRtree->aHash[iHash];

    pRtree->aHash[iHash] = pNode;

  }

}

/*

** Remove node pNode from the node hash table.

*/

static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){

  RtreeNode **pp;

  if( pNode->iNode!=0 ){

    pp = &pRtree->aHash[nodeHash(pNode->iNode)];

    for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); }

    *pp = pNode->pNext;

    pNode->pNext = 0;

  }

}

/*

** Allocate and return new r-tree node. Initially, (RtreeNode.iNode==0),

** indicating that node has not yet been assigned a node number. It is

** assigned a node number when nodeWrite() is called to write the

** node contents out to the database.

*/

static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent, int zero){

  RtreeNode *pNode;

  pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);

  if( pNode ){

    memset(pNode, 0, sizeof(RtreeNode) + (zero?pRtree->iNodeSize:0));

    pNode->zData = (u8 *)&pNode[1];

    pNode->nRef = 1;

    pNode->pParent = pParent;

    pNode->isDirty = 1;

    nodeReference(pParent);

  }

  return pNode;

}

/*

** Obtain a reference to an r-tree node.

*/

static int

nodeAcquire(

  Rtree *pRtree,             /* R-tree structure */

  i64 iNode,                 /* Node number to load */

  RtreeNode *pParent,        /* Either the parent node or NULL */

  RtreeNode **ppNode         /* OUT: Acquired node */

){

  int rc;

  RtreeNode *pNode;

  /* Check if the requested node is already in the hash table. If so,

  ** increase its reference count and return it.

  */

  if( (pNode = nodeHashLookup(pRtree, iNode)) ){

    assert( !pParent || !pNode->pParent || pNode->pParent==pParent );

    if( pParent ){

      pNode->pParent = pParent;

    }

    pNode->nRef++;

    *ppNode = pNode;

    return SQLITE_OK;

  }

  pNode = (RtreeNode *)sqlite3_malloc(sizeof(RtreeNode) + pRtree->iNodeSize);

  if( !pNode ){

    *ppNode = 0;

    return SQLITE_NOMEM;

  }

  pNode->pParent = pParent;

  pNode->zData = (u8 *)&pNode[1];

  pNode->nRef = 1;

  pNode->iNode = iNode;

  pNode->isDirty = 0;

  pNode->pNext = 0;

  sqlite3_bind_int64(pRtree->pReadNode, 1, iNode);

  rc = sqlite3_step(pRtree->pReadNode);

  if( rc==SQLITE_ROW ){

    const u8 *zBlob = sqlite3_column_blob(pRtree->pReadNode, 0);

    memcpy(pNode->zData, zBlob, pRtree->iNodeSize);

    nodeReference(pParent);

  }else{

    sqlite3_free(pNode);

    pNode = 0;

  }

  *ppNode = pNode;

  rc = sqlite3_reset(pRtree->pReadNode);

  if( rc==SQLITE_OK && iNode==1 ){

    pRtree->iDepth = readInt16(pNode->zData);

  }

  assert( (rc==SQLITE_OK && pNode) || (pNode==0 && rc!=SQLITE_OK) );

  nodeHashInsert(pRtree, pNode);

  return rc;

}

/*

** Overwrite cell iCell of node pNode with the contents of pCell.

*/

static void nodeOverwriteCell(

  Rtree *pRtree, 

  RtreeNode *pNode,  

  RtreeCell *pCell, 

  int iCell

){

  int ii;

  u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];

  p += writeInt64(p, pCell->iRowid);

  for(ii=0; ii<(pRtree->nDim*2); ii++){

    p += writeCoord(p, &pCell->aCoord[ii]);

  }

  pNode->isDirty = 1;

}

/*

** Remove cell the cell with index iCell from node pNode.

*/

static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){

  u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];

  u8 *pSrc = &pDst[pRtree->nBytesPerCell];

  int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell;

  memmove(pDst, pSrc, nByte);

  writeInt16(&pNode->zData[2], NCELL(pNode)-1);

  pNode->isDirty = 1;

}

/*

** Insert the contents of cell pCell into node pNode. If the insert

** is successful, return SQLITE_OK.

**

** If there is not enough free space in pNode, return SQLITE_FULL.

*/

static int

nodeInsertCell(

  Rtree *pRtree, 

  RtreeNode *pNode, 

  RtreeCell *pCell 

){

  int nCell;                    /* Current number of cells in pNode */

  int nMaxCell;                 /* Maximum number of cells for pNode */

  nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell;

  nCell = NCELL(pNode);

  assert(nCell<=nMaxCell);

  if( nCell<nMaxCell ){

    nodeOverwriteCell(pRtree, pNode, pCell, nCell);

    writeInt16(&pNode->zData[2], nCell+1);

    pNode->isDirty = 1;

  }

  return (nCell==nMaxCell);

}

/*

** If the node is dirty, write it out to the database.

*/

static int

nodeWrite(Rtree *pRtree, RtreeNode *pNode){

  int rc = SQLITE_OK;

  if( pNode->isDirty ){

    sqlite3_stmt *p = pRtree->pWriteNode;

    if( pNode->iNode ){

      sqlite3_bind_int64(p, 1, pNode->iNode);

    }else{

      sqlite3_bind_null(p, 1);

    }

    sqlite3_bind_blob(p, 2, pNode->zData, pRtree->iNodeSize, SQLITE_STATIC);

    sqlite3_step(p);

    pNode->isDirty = 0;

    rc = sqlite3_reset(p);

    if( pNode->iNode==0 && rc==SQLITE_OK ){

      pNode->iNode = sqlite3_last_insert_rowid(pRtree->db);

      nodeHashInsert(pRtree, pNode);

    }

  }

  return rc;

}

/*

** Release a reference to a node. If the node is dirty and the reference

** count drops to zero, the node data is written to the database.