<commit_before>#include <assert.h>
#include <string.h>
#include <stdio.h>

#include <sqlite3ext.h>
extern const sqlite3_api_routines *sqlite3_api;

#include "chemicalite.h"
#include "bfp_ops.h"
#include "bitstring.h"
#include "rdtree.h"

/* 
** This index data structure is *heavily* copied from the SQLite's
** r-tree and r*-tree implementation, with the necessary variation on the 
** algorithms which are required to turn it into an rd-tree.
*/

/*
** Database Format of RD-Tree Tables
** ---------------------------------
**
** The data structure for a single virtual rd-tree table is stored in three 
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the rd-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** The data for each node of the rd-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.
**
** The root node of an rd-tree always exists, even if the rd-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   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 64-bits integer followed by a binary fingerprint. 
**      For leaf nodes the integer is the rowid of a record. For internal
**      nodes it is the node number of a child page.
*/

typedef sqlite3_int64 i64;

typedef struct RDtree RDtree;
typedef struct RDtreeNode RDtreeNode;
typedef struct RDtreeItem RDtreeItem;

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

/* Size of hash table RDtree.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 rd-tree virtual-table object.
*/
struct RDtree {
  sqlite3_vtab base;
  sqlite3 *db;                 /* Host database connection */
  int iBfpSize;                /* Size (bytes) of the binary fingerprint */
  int nBytesPerItem;           /* Bytes consumed per item */
  int iNodeSize;               /* Size (bytes) of each node in the node table */
  int iNodeCapacity;           /* Size (items) of each node */
  int iDepth;                  /* Current depth of the rd-tree structure */
  char *zDb;                   /* Name of database containing rd-tree table */
  char *zName;                 /* Name of rd-tree table */ 
  RDtreeNode *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 -
  ** RDtreeNode.pNext. RDtreeNode.iNode stores the depth of the sub-tree 
  ** headed by the node (leaf nodes have RDtreeNode.iNode==0).
  */
  RDtreeNode *pDeleted;
  int iReinsertHeight;  /* Height of sub-trees Reinsert() has run on DELME? */

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

/*
** The minimum number of cells allowed for a node is a third of the 
** maximum. In Gutman's notation:
**
**     m = M/3
**
** If an RD-tree "Reinsert" operation is required, the same number of
** cells are removed from the overfull node and reinserted into the tree.
*/
#define RDTREE_MINITEMS(p) ((((p)->iNodeSize-4)/(p)->nBytesPerItem)/3)
#define RDTREE_REINSERT(p) RDTREE_MINITEMS(p)
#define RDTREE_MAXITEMS 51

/*
** The smallest possible node-size is (512-64)==448 bytes. And the largest
** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
** Therefore all non-root nodes must contain at least 3 entries. Since 
** 3^40 is greater than 2^64, an rd-tree structure always has a depth of
** 40 or less.
*/
/* FIXME FIXME FIXME */
#define RDTREE_MAX_DEPTH 40

/* 
** An rd-tree structure node.
*/
struct RDtreeNode {
  RDtreeNode *pParent; /* Parent node in the tree */
  i64 iNode;
  int nRef;
  int isDirty;
  u8 *zData;
  RDtreeNode *pNext;   /* Next node in this hash chain */
};
#define NITEM(pNode) readInt16(&(pNode)->zData[2])

/* 
** Structure to store a deserialized rd-tree record.
*/
struct RDtreeItem {
  i64 iRowid;
  u8 aBfp[MAX_BITSTRING_SIZE];
};

static int itemWeight(RDtree *pRDtree, RDtreeItem *pItem)
{
  return bfp_op_weight(pRDtree->iBfpSize, pItem->aBfp);
}

/*
** Store the union of items p1 and p2 in p1.<commit_msg>some first info about database page size and number of items per node<commit_after>#include <assert.h>
#include <string.h>
#include <stdio.h>

#include <sqlite3ext.h>
extern const sqlite3_api_routines *sqlite3_api;

#include "chemicalite.h"
#include "bfp_ops.h"
#include "bitstring.h"
#include "rdtree.h"

/* 
** This index data structure is *heavily* copied from the SQLite's
** r-tree and r*-tree implementation, with the necessary variation on the 
** algorithms which are required to turn it into an rd-tree.
*/

/*
** Database Format of RD-Tree Tables
** ---------------------------------
**
** The data structure for a single virtual rd-tree table is stored in three 
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the rd-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** The data for each node of the rd-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.
**
** The root node of an rd-tree always exists, even if the rd-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   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 64-bits integer followed by a binary fingerprint. 
**      For leaf nodes the integer is the rowid of a record. For internal
**      nodes it is the node number of a child page.
*/

typedef sqlite3_int64 i64;

typedef struct RDtree RDtree;
typedef struct RDtreeNode RDtreeNode;
typedef struct RDtreeItem RDtreeItem;

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

/* Size of hash table RDtree.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 rd-tree virtual-table object.
*/
struct RDtree {
  sqlite3_vtab base;
  sqlite3 *db;                 /* Host database connection */
  int iBfpSize;                /* Size (bytes) of the binary fingerprint */
  int nBytesPerItem;           /* Bytes consumed per item */
  int iNodeSize;               /* Size (bytes) of each node in the node table */
  int iNodeCapacity;           /* Size (items) of each node */
  int iDepth;                  /* Current depth of the rd-tree structure */
  char *zDb;                   /* Name of database containing rd-tree table */
  char *zName;                 /* Name of rd-tree table */ 
  RDtreeNode *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 -
  ** RDtreeNode.pNext. RDtreeNode.iNode stores the depth of the sub-tree 
  ** headed by the node (leaf nodes have RDtreeNode.iNode==0).
  */
  RDtreeNode *pDeleted;
  int iReinsertHeight;  /* Height of sub-trees Reinsert() has run on DELME? */

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

/*
** The minimum number of cells allowed for a node is a third of the 
** maximum. In Gutman's notation:
**
**     m = M/3
**
** If an RD-tree "Reinsert" operation is required, the same number of
** cells are removed from the overfull node and reinserted into the tree.
*/
#define RDTREE_MINITEMS(p) ((p)->iNodeCapacity/3)
#define RDTREE_REINSERT(p) RDTREE_MINITEMS(p)
#define RDTREE_MAXITEMS 51

/*
** The largest supported item size is 264 bytes (8 byte rowid + 256 bytes 
** fingerprint). Assuming that a database page size of at least 2048 bytes is
** in use, then all non-root nodes must contain at least 2 entries.
** An rd-tree structure therefore always has a depth of 64 or less.
**
** The same proportion holds for the default bfp size (128 bytes) and the 
** most common database default page size on unix workstations (1024 bytes).
**
** While these look like the minimal lower bounds, the optimal page size is to 
** be investigated.
*/
#define RDTREE_MAX_DEPTH 64

/* 
** An rd-tree structure node.
*/
struct RDtreeNode {
  RDtreeNode *pParent; /* Parent node in the tree */
  i64 iNode;
  int nRef;
  int isDirty;
  u8 *zData;
  RDtreeNode *pNext;   /* Next node in this hash chain */
};
#define NITEM(pNode) readInt16(&(pNode)->zData[2])

/* 
** Structure to store a deserialized rd-tree record.
*/
struct RDtreeItem {
  i64 iRowid;
  u8 aBfp[MAX_BITSTRING_SIZE];
};

static int itemWeight(RDtree *pRDtree, RDtreeItem *pItem)
{
  return bfp_op_weight(pRDtree->iBfpSize, pItem->aBfp);
}

/*
** Store the union of items p1 and p2 in p1.
{'fraction_non_alphanumeric': 0.1186733849740543, 'fraction_numerical': 0.027449800706926375, 'mean_word_length': 3.133664905191172, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 60, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2286237', 'n_tokens_mistral': 4763, 'n_tokens_neox': 4354, 'n_words': 1758}