src/btree.h

/*
** 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 header file defines the interface to the sqlite B-Tree storage
** subsystem. All SQLite database operations become calls to the B-Tree 
** storage layer. The B-Tree layer requires a key-value store underneath 
** that is capable of MVCC - that is, transaction commit and rollback, 
** locking and concurrent access. See comments in btree.c for a detailed 
** description of each interface routine.
**
** The btree module organises an SQL database of tables and rows into 
** multiple key-value pair stores, which in turn are represented as 
** fixed-size pages in the memory-based page cache. The BTree functions 
** operate on pages in the page cache. A separate B-tree is used for each 
** table and each index in the database. Databases are stored in an on-disk 
** Database Image, which the B-Tree module knows nothing about except for 
** opening and closing.
**
** The architecture is described at https://www.sqlite.org/arch.html .
**
** A Btree record is also called a payload in SQLite source. A Btree
** record for table data contains only two fields: the unique key value
** ROWID, and the table row data. A Btree record for an index btree or 
** a WITHOUT ROWID table contain an arbitary key and no (uninitialised) data.
** Btree pages are a fixed size. There will usually be multiple payloads 
** per page, but large payloads (eg BLOB data) may spill over to multiple
** pages.
**
** Functions in this header file are grouped according to their logical task:
**
**      Opening and Closing Database Connections
**
**      Database Image Configuration and Querying
**
**      Btree Connection Configuration and Querying
**
**      Mutex Function Wrappers
**
**      Transaction and Savepoint Functions
**
**      Cursors and Cursor Functions
**
**      Record and Payload Handling Functions
**
**      Table Functions
**
**      Reading and Writing Metadata
**
*/

#ifndef SQLITE_BTREE_H
#define SQLITE_BTREE_H

/*
** Forward declarations of structure
*/
typedef struct Btree Btree;
typedef struct BtCursor BtCursor;
typedef struct BtShared BtShared;
typedef struct BtreePayload BtreePayload;

/*
********************************************
*   Opening and Closing Database Connections
********************************************
*/

int sqlite3BtreeOpen(
  sqlite3_vfs *pVfs,       /* VFS to use with this b-tree */
  const char *zFilename,   /* Name of database file to open */
  sqlite3 *db,             /* Associated database connection */
  Btree **ppBtree,         /* Return open Btree* here */
  int flags,               /* Flags */
  int vfsFlags             /* Flags passed through to VFS open */
);

/* The flags parameter to sqlite3BtreeOpen can be the bitwise OR of the
** following values.
**
** NOTE:  These values must match the corresponding PAGER_ values in
** pager.h.
*/

#define BTREE_OMIT_JOURNAL  1  /* No create/use journal in temp databases */
#define BTREE_MEMORY        2  /* This is an in-memory DB */
#define BTREE_SINGLE        4  /* The file contains at most 1 b-tree */
#define BTREE_UNORDERED     8  /* Use of a hash implementation is OK */
                               /* Only a BTREE_SINGLE can be BTREE_UNORDERED */

int sqlite3BtreeClose(Btree*);

/* 
**********************************************
**   Database Image Configuration and Querying
**********************************************
*/

/*
** If defined as non-zero, auto-vacuum is enabled by default. Otherwise
** it must be turned on for each database using "PRAGMA auto_vacuum = 1".
*/
#ifndef SQLITE_DEFAULT_AUTOVACUUM
  #define SQLITE_DEFAULT_AUTOVACUUM 0
#endif

#define BTREE_AUTOVACUUM_NONE 0        /* Do not do auto-vacuum */
#define BTREE_AUTOVACUUM_FULL 1        /* Do full auto-vacuum */
#define BTREE_AUTOVACUUM_INCR 2        /* Incremental vacuum */

int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix);
int sqlite3BtreeGetPageSize(Btree*);

int sqlite3BtreeSetAutoVacuum(Btree *, int);
int sqlite3BtreeGetAutoVacuum(Btree *);

int sqlite3BtreeSetSpillSize(Btree*,int);
#if SQLITE_MAX_MMAP_SIZE>0
  int sqlite3BtreeSetMmapLimit(Btree*,sqlite3_int64);
#endif
int sqlite3BtreeSetPagerFlags(Btree*,unsigned);
int sqlite3BtreeSecureDelete(Btree*,int);
int sqlite3BtreeGetRequestedReserve(Btree*);
int sqlite3BtreeGetReserveNoMutex(Btree *p);

/* Implements PRAGMA integrity_check on a Btree and its associated file.
 * Only called from vdbe.c/OP_IntegrityCk */
char *sqlite3BtreeIntegrityCheck(sqlite3*,Btree*,Pgno*aRoot,int nRoot,int,int*);

/* A single step of an incremental vacuum. For PRAGMA incremental_vacuum(N) */
/* Neither autovacuum mode nor the VACUUM SQLite command use this function. */
int sqlite3BtreeIncrVacuum(Btree *);

/* Copy a complete Btree into another Btree, ie from one file into another */
/* Used only in the case of a backup and vacuum operations */
int sqlite3BtreeCopyFile(Btree *, Btree *);


/*
************************************************
**   Btree Connection Configuration and Querying
************************************************
*/


int sqlite3BtreeSetCacheSize(Btree*,int);
Pgno sqlite3BtreeMaxPageCount(Btree*,Pgno);
Pgno sqlite3BtreeLastPage(Btree*);
const char *sqlite3BtreeGetFilename(Btree *);
const char *sqlite3BtreeGetJournalname(Btree *);

int sqlite3BtreeIsReadonly(Btree *pBt);

/* Estimate number of rows in table
 * called only by OP IsSmaller, from PRAGMA optimize
*/
i64 sqlite3BtreeRowCountEst(BtCursor*);  

/* Return the pager associated with a BTree */
struct Pager *sqlite3BtreePager(Btree*);


/*
****************************
**   Mutex Function Wrappers 
****************************
**
** Every lock applies to an entire BTree. These functions are
** wrappers for the sqlite3_mutex* functions, which are called  
** outside btree.c
*/

/*
** If we are not using shared cache, then there is no need to
** use mutexes to access the BtShared structures.  So make the
** Enter and Leave procedures no-ops.
*/
#ifndef SQLITE_OMIT_SHARED_CACHE
  void sqlite3BtreeEnter(Btree*);
  void sqlite3BtreeEnterAll(sqlite3*);
  int sqlite3BtreeSharable(Btree*);
  void sqlite3BtreeEnterCursor(BtCursor*);
  int sqlite3BtreeConnectionCount(Btree*);
#else
# define sqlite3BtreeEnter(X) 
# define sqlite3BtreeEnterAll(X)
# define sqlite3BtreeSharable(X) 0
# define sqlite3BtreeEnterCursor(X)
# define sqlite3BtreeConnectionCount(X) 1
#endif

#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
  void sqlite3BtreeLeave(Btree*);
  void sqlite3BtreeLeaveCursor(BtCursor*);
  void sqlite3BtreeLeaveAll(sqlite3*);
#ifndef NDEBUG
  /* These routines are used inside assert() statements only. */
  int sqlite3BtreeHoldsMutex(Btree*);
  int sqlite3BtreeHoldsAllMutexes(sqlite3*);
  int sqlite3SchemaMutexHeld(sqlite3*,int,Schema*);
#endif
#else

# define sqlite3BtreeLeave(X)
# define sqlite3BtreeLeaveCursor(X)
# define sqlite3BtreeLeaveAll(X)

# define sqlite3BtreeHoldsMutex(X) 1
# define sqlite3BtreeHoldsAllMutexes(X) 1
# define sqlite3SchemaMutexHeld(X,Y,Z) 1
#endif


/*
****************************************
**   Transaction and SavePoint Functions
****************************************
*/

int sqlite3BtreeBeginTrans(Btree*,int,int*);
int sqlite3BtreeCommitPhaseOne(Btree*, const char *zMaster);
int sqlite3BtreeCommitPhaseTwo(Btree*, int);
int sqlite3BtreeCommit(Btree*);
int sqlite3BtreeRollback(Btree*,int,int);
int sqlite3BtreeCreateTable(Btree*, Pgno*, int flags);
int sqlite3BtreeTxnState(Btree*);
int sqlite3BtreeIsInBackup(Btree*);

/* Savepoints are named, nestable SQL transactions mostly implemented */
/* in vdbe.c and pager.c See https://sqlite.org/lang_savepoint.html */
int sqlite3BtreeSavepoint(Btree *, int, int);

/* A statement sub-transaction is an internal-only transaction used */
/* only by OP_Transaction, see comments in vdbe.c. A statement */
/* sub-transaction is implemented as an anonymous savepoint. */
int sqlite3BtreeBeginStmt(Btree*,int);

/* A checkpoint refers to only to WAL. See https://sqlite.org/wal.html#ckpt */
#ifndef SQLITE_OMIT_WAL
  int sqlite3BtreeCheckpoint(Btree*, int, int *, int *);  
#endif

/* Set all relevant cursors to error state on transaction rollback */
int sqlite3BtreeTripAllCursors(Btree*, int, int);


/*
*********************************
**   Cursors and Cursor functions
*********************************
**
*/

/*
** Kinds of hints that can be passed into the sqlite3BtreeCursorHint()
** interface.
**
** BTREE_HINT_RANGE  (arguments: Expr*, Mem*)
**
**     The first argument is an Expr* (which is guaranteed to be constant for
**     the lifetime of the cursor) that defines constraints on which rows
**     might be fetched with this cursor.  The Expr* tree may contain
**     TK_REGISTER nodes that refer to values stored in the array of registers
**     passed as the second parameter.  In other words, if Expr.op==TK_REGISTER
**     then the value of the node is the value in Mem[pExpr.iTable].  Any
**     TK_COLUMN node in the expression tree refers to the Expr.iColumn-th
**     column of the b-tree of the cursor.  The Expr tree will not contain
**     any function calls nor subqueries nor references to b-trees other than
**     the cursor being hinted.
**
**     The design of the _RANGE hint is aid b-tree implementations that try
**     to prefetch content from remote machines - to provide those
**     implementations with limits on what needs to be prefetched and thereby
**     reduce network bandwidth.
**
** Note that BTREE_HINT_FLAGS with BTREE_BULKLOAD is the only hint used by
** standard SQLite.  The other hints are provided for extentions that use
** the SQLite parser and code generator but substitute their own storage
** engine.
*/
#define BTREE_HINT_RANGE 0       /* Range constraints on queries */

/*
** Values that may be OR'd together to form the argument to the
** BTREE_HINT_FLAGS hint for sqlite3BtreeCursorHint():
**
** The BTREE_BULKLOAD flag is set on index cursors when the index is going
** to be filled with content that is already in sorted order.
**
** The BTREE_SEEK_EQ flag is set on cursors that will get OP_SeekGE or
** OP_SeekLE opcodes for a range search, but where the range of entries
** selected will all have the same key.  In other words, the cursor will
** be used only for equality key searches.
**
*/
#define BTREE_BULKLOAD 0x00000001  /* Used to full index in sorted order */
#define BTREE_SEEK_EQ  0x00000002  /* EQ seeks only - no range seeks */

/* 
** Flags passed as the third argument to sqlite3BtreeCursor().
**
** For read-only cursors the wrFlag argument is always zero. For read-write
** cursors it may be set to either (BTREE_WRCSR|BTREE_FORDELETE) or just
** (BTREE_WRCSR). If the BTREE_FORDELETE bit is set, then the cursor will
** only be used by SQLite for the following:
**
**   * to seek to and then delete specific entries, and/or
**
**   * to read values that will be used to create keys that other
**     BTREE_FORDELETE cursors will seek to and delete.
**
** The BTREE_FORDELETE flag is an optimization hint.  It is not used by
** by this, the native b-tree engine of SQLite, but it is available to
** alternative storage engines that might be substituted in place of this
** b-tree system.  For alternative storage engines in which a delete of
** the main table row automatically deletes corresponding index rows,
** the FORDELETE flag hint allows those alternative storage engines to
** skip a lot of work.  Namely:  FORDELETE cursors may treat all SEEK
** and DELETE operations as no-ops, and any READ operation against a
** FORDELETE cursor may return a null row: 0x01 0x00.
*/
#define BTREE_WRCSR     0x00000004     /* read-write cursor */
#define BTREE_FORDELETE 0x00000008     /* Cursor is for seek/delete only */

int sqlite3BtreeCursor(
  Btree*,                              /* BTree containing table to open */
  Pgno iTable,                          /* Index of root page */
  int wrFlag,                          /* 1 for writing.  0 for read-only */
  struct KeyInfo*,                     /* First argument to compare function */
  BtCursor *pCursor                    /* Space to write cursor structure */
);

/* True if hint specified, used in or around assert statements only */
int sqlite3BtreeCursorHasHint(BtCursor*, unsigned int mask); 

BtCursor *sqlite3BtreeFakeValidCursor(void);

#ifdef SQLITE_DEBUG
sqlite3_uint64 sqlite3BtreeSeekCount(Btree*);
#else
# define sqlite3BtreeSeekCount(X) 0
#endif

#ifndef NDEBUG
int sqlite3BtreeCursorIsValid(BtCursor*); 
#endif
int sqlite3BtreeCursorIsValidNN(BtCursor*);

int sqlite3BtreeCursorSize(void);
void sqlite3BtreeCursorZero(BtCursor*);
void sqlite3BtreeCursorHintFlags(BtCursor*, unsigned);
#ifdef SQLITE_ENABLE_CURSOR_HINTS
void sqlite3BtreeCursorHint(BtCursor*, int, ...);
#endif

void sqlite3BtreeClearCursor(BtCursor *);
int sqlite3BtreeCloseCursor(BtCursor*);

/* Cursor seek to a specified rowid in the Btree */
int sqlite3BtreeMovetoUnpacked(
  BtCursor*,
  UnpackedRecord *pUnKey,
  i64 intKey,
  int bias,
  int *pRes
);

int sqlite3BtreeFirst(BtCursor*, int *pRes);
int sqlite3BtreeLast(BtCursor*, int *pRes);
int sqlite3BtreeNext(BtCursor*, int flags);
int sqlite3BtreeEof(BtCursor*);
int sqlite3BtreePrevious(BtCursor*, int flags);
i64 sqlite3BtreeIntegerKey(BtCursor*); 

int sqlite3BtreeCount(sqlite3*, BtCursor*, i64*);


void *sqlite3BtreeSchema(Btree *, int, void(*)(void *));
int sqlite3BtreeSchemaLocked(Btree *pBtree);
#ifndef SQLITE_OMIT_SHARED_CACHE
int sqlite3BtreeLockTable(Btree *pBtree, int iTab, u8 isWriteLock);
#endif
void sqlite3BtreeCursorPin(BtCursor*);  
void sqlite3BtreeCursorUnpin(BtCursor*); 

int sqlite3BtreeCursorHasMoved(BtCursor*);  
int sqlite3BtreeCursorRestore(BtCursor*, int*); 

#ifdef SQLITE_TEST
int sqlite3BtreeCursorInfo(BtCursor*, int*, int);  
void sqlite3BtreeCursorList(Btree*);
#endif

/*
******************************************
**   Record and Payload handling functions
******************************************
**
** A Btree record is a key-value pair consisting of a rowid key, and arbitary 
** data value. The record is also called a payload.
**
*/

/* Allowed flags for sqlite3BtreeDelete() and sqlite3BtreeInsert() */
#define BTREE_SAVEPOSITION 0x02  /* Leave cursor pointing at NEXT or PREV */
#define BTREE_AUXDELETE    0x04  /* not the primary delete operation */
#define BTREE_APPEND       0x08  /* Insert is likely an append */

/* An instance of the BtreePayload object describes the content of a single
** entry in either an index or table btree.
**
** Index btrees (used for indexes and also WITHOUT ROWID tables) contain
** an arbitrary key and no data.  These btrees have pKey,nKey set to the
** key and the pData,nData,nZero fields are uninitialized.  The aMem,nMem
** fields give an array of Mem objects that are a decomposition of the key.
** The nMem field might be zero, indicating that no decomposition is available.
**
** Table btrees (used for rowid tables) contain an integer rowid used as
** the key and passed in the nKey field.  The pKey field is zero.  
** pData,nData hold the content of the new entry.  nZero extra zero bytes
** are appended to the end of the content when constructing the entry.
** The aMem,nMem fields are uninitialized for table btrees.
**
** Field usage summary:
**
**               Table BTrees                   Index Btrees
**
**   pKey        always NULL                    encoded key
**   nKey        the ROWID                      length of pKey
**   pData       data                           not used
**   aMem        not used                       decomposed key value
**   nMem        not used                       entries in aMem
**   nData       length of pData                not used
**   nZero       extra zeros after pData        not used
**
** This object is used to pass information into sqlite3BtreeInsert().  The
** same information used to be passed as five separate parameters.  But placing
** the information into this object helps to keep the interface more 
** organized and understandable, and it also helps the resulting code to
** run a little faster by using fewer registers for parameter passing.
*/
struct BtreePayload {
  const void *pKey;       /* Key content for indexes.  NULL for tables */
  sqlite3_int64 nKey;     /* Size of pKey for indexes.  PRIMARY KEY for tabs */
  const void *pData;      /* Data for tables. */
  sqlite3_value *aMem;    /* First of nMem value in the unpacked pKey */
  u16 nMem;               /* Number of aMem[] value.  Might be zero */
  int nData;              /* Size of pData.  0 if none. */
  int nZero;              /* Extra zero data appended after pData,nData */
};

int sqlite3BtreeInsert(BtCursor*, const BtreePayload *pPayload,
                       int flags, int seekResult);

int sqlite3BtreeDelete(BtCursor*, u8 flags);

#ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
i64 sqlite3BtreeOffset(BtCursor*);
#endif
int sqlite3BtreePayload(BtCursor*, u32 offset, u32 amt, void*);
const void *sqlite3BtreePayloadFetch(BtCursor*, u32 *pAmt);
u32 sqlite3BtreePayloadSize(BtCursor*);

/* These functions deal with arbitary-sized binary blobs in a Btree */
#ifndef SQLITE_OMIT_INCRBLOB
int sqlite3BtreePayloadChecked(BtCursor*, u32 offset, u32 amt, void*);
int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
void sqlite3BtreeIncrblobCursor(BtCursor *);
#endif



/*
********************
**   Table functions
********************
**
*/

/* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
** of the flags shown below.
**
** Every SQLite table must have either BTREE_INTKEY or BTREE_BLOBKEY set.
** With BTREE_INTKEY, the table key is a 64-bit integer and arbitrary data
** is stored in the leaves.  (BTREE_INTKEY is used for SQL tables.)  With
** BTREE_BLOBKEY, the key is an arbitrary BLOB and no content is stored
** anywhere - the key is the content.  (BTREE_BLOBKEY is used for SQL
** indices.)
*/

#define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
#define BTREE_BLOBKEY    2    /* Table has keys only - no data */

int sqlite3BtreeDropTable(Btree*, int, int*);
int sqlite3BtreeClearTable(Btree*, int, int*);
int sqlite3BtreeClearTableOfCursor(BtCursor*);


/*
*********************************
**   Reading and Writing Metadata
*********************************
**
** Note there is metadata which is not in the first database page
** including (as below) some visible via the os.h API
*/


/*
** The second parameter to sqlite3BtreeGetMeta or sqlite3BtreeUpdateMeta
** should be one of the following values. The integer values are assigned 
** to constants so that the offset of the corresponding field in an
** SQLite database header may be found using the following formula:
**
**   offset = 36 + (idx * 4)
**
** For example, the free-page-count field is located at byte offset 36 of
** the database file header. The incr-vacuum-flag field is located at
** byte offset 64 (== 36+4*7).
**
** The BTREE_DATA_VERSION value is not really a value stored in the header.
** It is a read-only number computed by the pager.  But we merge it with
** the header value access routines since its access pattern is the same.
** Call it a "virtual meta value".
*/
#define BTREE_FREE_PAGE_COUNT     0
#define BTREE_SCHEMA_VERSION      1
#define BTREE_FILE_FORMAT         2
#define BTREE_DEFAULT_CACHE_SIZE  3
#define BTREE_LARGEST_ROOT_PAGE   4
#define BTREE_TEXT_ENCODING       5
#define BTREE_USER_VERSION        6
#define BTREE_INCR_VACUUM         7
#define BTREE_APPLICATION_ID      8
#define BTREE_DATA_VERSION        15  /* A virtual meta-value */


/* Refers to the size of the per-page header, not per-database header */
/* Used for configuring the size of the pages in the page cache */
int sqlite3HeaderSizeBtree(void);

/* TODO: This definition is only used in asserts to determine whether 
 * the metadata index (second parameter of Get/UpdateMeta functions) 
 * is out of range. It is only included here so other modules compile. It
 * ** needs to be revisited.
 * */
#define SQLITE_N_BTREE_META 16

void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue);
int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);

/* This returns the size of the current database file, ie the same */
/* result as sqlite3OsFileSize in os.h . */
sqlite3_int64 sqlite3BtreeMaxRecordSize(BtCursor*);

/* Version number of the file format must be either 1 or 2 */
/* 1=legacy, 2=WAL . Read and write versions set to same value */
int sqlite3BtreeSetVersion(Btree *pBt, int iVersion); 

/* Initialize the first page of the database file and return */
int sqlite3BtreeNewDb(Btree *p);


#endif /* SQLITE_BTREE_H */