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