src/btree.h

   1 /*
   2 ** 2001 September 15
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This header file defines the interface that the sqlite B-Tree file
  13 ** subsystem.  See comments in the source code for a detailed description
  14 ** of what each interface routine does.
  15 */
  16 #ifndef SQLITE_BTREE_H
  17 #define SQLITE_BTREE_H
  18
  19 /* TODO: This definition is just included so other modules compile. It
  20 ** needs to be revisited.
  21 */
  22 #define SQLITE_N_BTREE_META 16
  23
  24 /*
  25 ** If defined as non-zero, auto-vacuum is enabled by default. Otherwise
  26 ** it must be turned on for each database using "PRAGMA auto_vacuum = 1".
  27 */
  28 #ifndef SQLITE_DEFAULT_AUTOVACUUM
  29   #define SQLITE_DEFAULT_AUTOVACUUM 0
  30 #endif
  31
  32 #define BTREE_AUTOVACUUM_NONE 0        /* Do not do auto-vacuum */
  33 #define BTREE_AUTOVACUUM_FULL 1        /* Do full auto-vacuum */
  34 #define BTREE_AUTOVACUUM_INCR 2        /* Incremental vacuum */
  35
  36 /*
  37 ** Forward declarations of structure
  38 */
  39 typedef struct Btree Btree;
  40 typedef struct BtCursor BtCursor;
  41 typedef struct BtShared BtShared;
  42 typedef struct BtreePayload BtreePayload;
  43
  44
  45 int sqlite3BtreeOpen(
  46   sqlite3_vfs *pVfs,       /* VFS to use with this b-tree */
  47   const char *zFilename,   /* Name of database file to open */
  48   sqlite3 *db,             /* Associated database connection */
  49   Btree **ppBtree,         /* Return open Btree* here */
  50   int flags,               /* Flags */
  51   int vfsFlags             /* Flags passed through to VFS open */
  52 );
  53
  54 /* The flags parameter to sqlite3BtreeOpen can be the bitwise or of the
  55 ** following values.
  56 **
  57 ** NOTE:  These values must match the corresponding PAGER_ values in
  58 ** pager.h.
  59 */
  60 #define BTREE_OMIT_JOURNAL  1  /* Do not create or use a rollback journal */
  61 #define BTREE_MEMORY        2  /* This is an in-memory DB */
  62 #define BTREE_SINGLE        4  /* The file contains at most 1 b-tree */
  63 #define BTREE_UNORDERED     8  /* Use of a hash implementation is OK */
  64
  65 int sqlite3BtreeClose(Btree*);
  66 int sqlite3BtreeSetCacheSize(Btree*,int);
  67 int sqlite3BtreeSetSpillSize(Btree*,int);
  68 #if SQLITE_MAX_MMAP_SIZE>0
  69   int sqlite3BtreeSetMmapLimit(Btree*,sqlite3_int64);
  70 #endif
  71 int sqlite3BtreeSetPagerFlags(Btree*,unsigned);
  72 int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix);
  73 int sqlite3BtreeGetPageSize(Btree*);
  74 Pgno sqlite3BtreeMaxPageCount(Btree*,Pgno);
  75 Pgno sqlite3BtreeLastPage(Btree*);
  76 int sqlite3BtreeSecureDelete(Btree*,int);
  77 int sqlite3BtreeGetRequestedReserve(Btree*);
  78 int sqlite3BtreeGetReserveNoMutex(Btree *p);
  79 int sqlite3BtreeSetAutoVacuum(Btree *, int);
  80 int sqlite3BtreeGetAutoVacuum(Btree *);
  81 int sqlite3BtreeBeginTrans(Btree*,int,int*);
  82 int sqlite3BtreeCommitPhaseOne(Btree*, const char*);
  83 int sqlite3BtreeCommitPhaseTwo(Btree*, int);
  84 int sqlite3BtreeCommit(Btree*);
  85 int sqlite3BtreeRollback(Btree*,int,int);
  86 int sqlite3BtreeBeginStmt(Btree*,int);
  87 int sqlite3BtreeCreateTable(Btree*, Pgno*, int flags);
  88 int sqlite3BtreeTxnState(Btree*);
  89 int sqlite3BtreeIsInBackup(Btree*);
  90
  91 void *sqlite3BtreeSchema(Btree *, int, void(*)(void *));
  92 int sqlite3BtreeSchemaLocked(Btree *pBtree);
  93 #ifndef SQLITE_OMIT_SHARED_CACHE
  94 int sqlite3BtreeLockTable(Btree *pBtree, int iTab, u8 isWriteLock);
  95 #endif
  96
  97 /* Savepoints are named, nestable SQL transactions mostly implemented */
  98 /* in vdbe.c and pager.c See https://sqlite.org/lang_savepoint.html */
  99 int sqlite3BtreeSavepoint(Btree *, int, int);
 100
 101 /* "Checkpoint" only refers to WAL. See https://sqlite.org/wal.html#ckpt */
 102 #ifndef SQLITE_OMIT_WAL
 103   int sqlite3BtreeCheckpoint(Btree*, int, int *, int *);
 104 #endif
 105
 106 const char *sqlite3BtreeGetFilename(Btree *);
 107 const char *sqlite3BtreeGetJournalname(Btree *);
 108 int sqlite3BtreeCopyFile(Btree *, Btree *);
 109
 110 int sqlite3BtreeIncrVacuum(Btree *);
 111
 112 /* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
 113 ** of the flags shown below.
 114 **
 115 ** Every SQLite table must have either BTREE_INTKEY or BTREE_BLOBKEY set.
 116 ** With BTREE_INTKEY, the table key is a 64-bit integer and arbitrary data
 117 ** is stored in the leaves.  (BTREE_INTKEY is used for SQL tables.)  With
 118 ** BTREE_BLOBKEY, the key is an arbitrary BLOB and no content is stored
 119 ** anywhere - the key is the content.  (BTREE_BLOBKEY is used for SQL
 120 ** indices.)
 121 */
 122 #define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
 123 #define BTREE_BLOBKEY    2    /* Table has keys only - no data */
 124
 125 int sqlite3BtreeDropTable(Btree*, int, int*);
 126 int sqlite3BtreeClearTable(Btree*, int, i64*);
 127 int sqlite3BtreeClearTableOfCursor(BtCursor*);
 128 int sqlite3BtreeTripAllCursors(Btree*, int, int);
 129
 130 void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue);
 131 int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);
 132
 133 int sqlite3BtreeNewDb(Btree *p);
 134
 135 /*
 136 ** The second parameter to sqlite3BtreeGetMeta or sqlite3BtreeUpdateMeta
 137 ** should be one of the following values. The integer values are assigned
 138 ** to constants so that the offset of the corresponding field in an
 139 ** SQLite database header may be found using the following formula:
 140 **
 141 **   offset = 36 + (idx * 4)
 142 **
 143 ** For example, the free-page-count field is located at byte offset 36 of
 144 ** the database file header. The incr-vacuum-flag field is located at
 145 ** byte offset 64 (== 36+4*7).
 146 **
 147 ** The BTREE_DATA_VERSION value is not really a value stored in the header.
 148 ** It is a read-only number computed by the pager.  But we merge it with
 149 ** the header value access routines since its access pattern is the same.
 150 ** Call it a "virtual meta value".
 151 */
 152 #define BTREE_FREE_PAGE_COUNT     0
 153 #define BTREE_SCHEMA_VERSION      1
 154 #define BTREE_FILE_FORMAT         2
 155 #define BTREE_DEFAULT_CACHE_SIZE  3
 156 #define BTREE_LARGEST_ROOT_PAGE   4
 157 #define BTREE_TEXT_ENCODING       5
 158 #define BTREE_USER_VERSION        6
 159 #define BTREE_INCR_VACUUM         7
 160 #define BTREE_APPLICATION_ID      8
 161 #define BTREE_DATA_VERSION        15  /* A virtual meta-value */
 162
 163 /*
 164 ** Kinds of hints that can be passed into the sqlite3BtreeCursorHint()
 165 ** interface.
 166 **
 167 ** BTREE_HINT_RANGE  (arguments: Expr*, Mem*)
 168 **
 169 **     The first argument is an Expr* (which is guaranteed to be constant for
 170 **     the lifetime of the cursor) that defines constraints on which rows
 171 **     might be fetched with this cursor.  The Expr* tree may contain
 172 **     TK_REGISTER nodes that refer to values stored in the array of registers
 173 **     passed as the second parameter.  In other words, if Expr.op==TK_REGISTER
 174 **     then the value of the node is the value in Mem[pExpr.iTable].  Any
 175 **     TK_COLUMN node in the expression tree refers to the Expr.iColumn-th
 176 **     column of the b-tree of the cursor.  The Expr tree will not contain
 177 **     any function calls nor subqueries nor references to b-trees other than
 178 **     the cursor being hinted.
 179 **
 180 **     The design of the _RANGE hint is aid b-tree implementations that try
 181 **     to prefetch content from remote machines - to provide those
 182 **     implementations with limits on what needs to be prefetched and thereby
 183 **     reduce network bandwidth.
 184 **
 185 ** Note that BTREE_HINT_FLAGS with BTREE_BULKLOAD is the only hint used by
 186 ** standard SQLite.  The other hints are provided for extensions that use
 187 ** the SQLite parser and code generator but substitute their own storage
 188 ** engine.
 189 */
 190 #define BTREE_HINT_RANGE 0       /* Range constraints on queries */
 191
 192 /*
 193 ** Values that may be OR'd together to form the argument to the
 194 ** BTREE_HINT_FLAGS hint for sqlite3BtreeCursorHint():
 195 **
 196 ** The BTREE_BULKLOAD flag is set on index cursors when the index is going
 197 ** to be filled with content that is already in sorted order.
 198 **
 199 ** The BTREE_SEEK_EQ flag is set on cursors that will get OP_SeekGE or
 200 ** OP_SeekLE opcodes for a range search, but where the range of entries
 201 ** selected will all have the same key.  In other words, the cursor will
 202 ** be used only for equality key searches.
 203 **
 204 */
 205 #define BTREE_BULKLOAD 0x00000001  /* Used to full index in sorted order */
 206 #define BTREE_SEEK_EQ  0x00000002  /* EQ seeks only - no range seeks */
 207
 208 /*
 209 ** Flags passed as the third argument to sqlite3BtreeCursor().
 210 **
 211 ** For read-only cursors the wrFlag argument is always zero. For read-write
 212 ** cursors it may be set to either (BTREE_WRCSR|BTREE_FORDELETE) or just
 213 ** (BTREE_WRCSR). If the BTREE_FORDELETE bit is set, then the cursor will
 214 ** only be used by SQLite for the following:
 215 **
 216 **   * to seek to and then delete specific entries, and/or
 217 **
 218 **   * to read values that will be used to create keys that other
 219 **     BTREE_FORDELETE cursors will seek to and delete.
 220 **
 221 ** The BTREE_FORDELETE flag is an optimization hint.  It is not used by
 222 ** by this, the native b-tree engine of SQLite, but it is available to
 223 ** alternative storage engines that might be substituted in place of this
 224 ** b-tree system.  For alternative storage engines in which a delete of
 225 ** the main table row automatically deletes corresponding index rows,
 226 ** the FORDELETE flag hint allows those alternative storage engines to
 227 ** skip a lot of work.  Namely:  FORDELETE cursors may treat all SEEK
 228 ** and DELETE operations as no-ops, and any READ operation against a
 229 ** FORDELETE cursor may return a null row: 0x01 0x00.
 230 */
 231 #define BTREE_WRCSR     0x00000004     /* read-write cursor */
 232 #define BTREE_FORDELETE 0x00000008     /* Cursor is for seek/delete only */
 233
 234 int sqlite3BtreeCursor(
 235   Btree*,                              /* BTree containing table to open */
 236   Pgno iTable,                         /* Index of root page */
 237   int wrFlag,                          /* 1 for writing.  0 for read-only */
 238   struct KeyInfo*,                     /* First argument to compare function */
 239   BtCursor *pCursor                    /* Space to write cursor structure */
 240 );
 241 BtCursor *sqlite3BtreeFakeValidCursor(void);
 242 int sqlite3BtreeCursorSize(void);
 243 void sqlite3BtreeCursorZero(BtCursor*);
 244 void sqlite3BtreeCursorHintFlags(BtCursor*, unsigned);
 245 #ifdef SQLITE_ENABLE_CURSOR_HINTS
 246 void sqlite3BtreeCursorHint(BtCursor*, int, ...);
 247 #endif
 248
 249 int sqlite3BtreeCloseCursor(BtCursor*);
 250 int sqlite3BtreeTableMoveto(
 251   BtCursor*,
 252   i64 intKey,
 253   int bias,
 254   int *pRes
 255 );
 256 int sqlite3BtreeIndexMoveto(
 257   BtCursor*,
 258   UnpackedRecord *pUnKey,
 259   int *pRes
 260 );
 261 int sqlite3BtreeCursorHasMoved(BtCursor*);
 262 int sqlite3BtreeCursorRestore(BtCursor*, int*);
 263 int sqlite3BtreeDelete(BtCursor*, u8 flags);
 264
 265 /* Allowed flags for sqlite3BtreeDelete() and sqlite3BtreeInsert() */
 266 #define BTREE_SAVEPOSITION 0x02  /* Leave cursor pointing at NEXT or PREV */
 267 #define BTREE_AUXDELETE    0x04  /* not the primary delete operation */
 268 #define BTREE_APPEND       0x08  /* Insert is likely an append */
 269 #define BTREE_PREFORMAT    0x80  /* Inserted data is a preformated cell */
 270
 271 /* An instance of the BtreePayload object describes the content of a single
 272 ** entry in either an index or table btree.
 273 **
 274 ** Index btrees (used for indexes and also WITHOUT ROWID tables) contain
 275 ** an arbitrary key and no data.  These btrees have pKey,nKey set to the
 276 ** key and the pData,nData,nZero fields are uninitialized.  The aMem,nMem
 277 ** fields give an array of Mem objects that are a decomposition of the key.
 278 ** The nMem field might be zero, indicating that no decomposition is available.
 279 **
 280 ** Table btrees (used for rowid tables) contain an integer rowid used as
 281 ** the key and passed in the nKey field.  The pKey field is zero.
 282 ** pData,nData hold the content of the new entry.  nZero extra zero bytes
 283 ** are appended to the end of the content when constructing the entry.
 284 ** The aMem,nMem fields are uninitialized for table btrees.
 285 **
 286 ** Field usage summary:
 287 **
 288 **               Table BTrees                   Index Btrees
 289 **
 290 **   pKey        always NULL                    encoded key
 291 **   nKey        the ROWID                      length of pKey
 292 **   pData       data                           not used
 293 **   aMem        not used                       decomposed key value
 294 **   nMem        not used                       entries in aMem
 295 **   nData       length of pData                not used
 296 **   nZero       extra zeros after pData        not used
 297 **
 298 ** This object is used to pass information into sqlite3BtreeInsert().  The
 299 ** same information used to be passed as five separate parameters.  But placing
 300 ** the information into this object helps to keep the interface more
 301 ** organized and understandable, and it also helps the resulting code to
 302 ** run a little faster by using fewer registers for parameter passing.
 303 */
 304 struct BtreePayload {
 305   const void *pKey;       /* Key content for indexes.  NULL for tables */
 306   sqlite3_int64 nKey;     /* Size of pKey for indexes.  PRIMARY KEY for tabs */
 307   const void *pData;      /* Data for tables. */
 308   sqlite3_value *aMem;    /* First of nMem value in the unpacked pKey */
 309   u16 nMem;               /* Number of aMem[] value.  Might be zero */
 310   int nData;              /* Size of pData.  0 if none. */
 311   int nZero;              /* Extra zero data appended after pData,nData */
 312 };
 313
 314 int sqlite3BtreeInsert(BtCursor*, const BtreePayload *pPayload,
 315                        int flags, int seekResult);
 316 int sqlite3BtreeFirst(BtCursor*, int *pRes);
 317 int sqlite3BtreeLast(BtCursor*, int *pRes);
 318 int sqlite3BtreeNext(BtCursor*, int flags);
 319 int sqlite3BtreeEof(BtCursor*);
 320 int sqlite3BtreePrevious(BtCursor*, int flags);
 321 i64 sqlite3BtreeIntegerKey(BtCursor*);
 322 void sqlite3BtreeCursorPin(BtCursor*);
 323 void sqlite3BtreeCursorUnpin(BtCursor*);
 324 i64 sqlite3BtreeOffset(BtCursor*);
 325 int sqlite3BtreePayload(BtCursor*, u32 offset, u32 amt, void*);
 326 const void *sqlite3BtreePayloadFetch(BtCursor*, u32 *pAmt);
 327 u32 sqlite3BtreePayloadSize(BtCursor*);
 328 sqlite3_int64 sqlite3BtreeMaxRecordSize(BtCursor*);
 329
 330 int sqlite3BtreeIntegrityCheck(
 331   sqlite3 *db,  /* Database connection that is running the check */
 332   Btree *p,     /* The btree to be checked */
 333   Pgno *aRoot,  /* An array of root pages numbers for individual trees */
 334   sqlite3_value *aCnt,  /* OUT: entry counts for each btree in aRoot[] */
 335   int nRoot,    /* Number of entries in aRoot[] */
 336   int mxErr,    /* Stop reporting errors after this many */
 337   int *pnErr,   /* OUT: Write number of errors seen to this variable */
 338   char **pzOut  /* OUT: Write the error message string here */
 339 );
 340 struct Pager *sqlite3BtreePager(Btree*);
 341 i64 sqlite3BtreeRowCountEst(BtCursor*);
 342
 343 #ifndef SQLITE_OMIT_INCRBLOB
 344 int sqlite3BtreePayloadChecked(BtCursor*, u32 offset, u32 amt, void*);
 345 int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
 346 void sqlite3BtreeIncrblobCursor(BtCursor *);
 347 #endif
 348 void sqlite3BtreeClearCursor(BtCursor *);
 349 int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);
 350 int sqlite3BtreeCursorHasHint(BtCursor*, unsigned int mask);
 351 int sqlite3BtreeIsReadonly(Btree *pBt);
 352 int sqlite3HeaderSizeBtree(void);
 353
 354 #ifdef SQLITE_DEBUG
 355 sqlite3_uint64 sqlite3BtreeSeekCount(Btree*);
 356 #else
 357 # define sqlite3BtreeSeekCount(X) 0
 358 #endif
 359
 360 #ifndef NDEBUG
 361 int sqlite3BtreeCursorIsValid(BtCursor*);
 362 #endif
 363 int sqlite3BtreeCursorIsValidNN(BtCursor*);
 364
 365 int sqlite3BtreeCount(sqlite3*, BtCursor*, i64*);
 366
 367 #ifdef SQLITE_TEST
 368 int sqlite3BtreeCursorInfo(BtCursor*, int*, int);
 369 void sqlite3BtreeCursorList(Btree*);
 370 #endif
 371
 372 #ifndef SQLITE_OMIT_WAL
 373   int sqlite3BtreeCheckpoint(Btree*, int, int *, int *);
 374 #endif
 375
 376 int sqlite3BtreeTransferRow(BtCursor*, BtCursor*, i64);
 377
 378 void sqlite3BtreeClearCache(Btree*);
 379
 380 /*
 381 ** If we are not using shared cache, then there is no need to
 382 ** use mutexes to access the BtShared structures.  So make the
 383 ** Enter and Leave procedures no-ops.
 384 */
 385 #ifndef SQLITE_OMIT_SHARED_CACHE
 386   void sqlite3BtreeEnter(Btree*);
 387   void sqlite3BtreeEnterAll(sqlite3*);
 388   int sqlite3BtreeSharable(Btree*);
 389   void sqlite3BtreeEnterCursor(BtCursor*);
 390   int sqlite3BtreeConnectionCount(Btree*);
 391 #else
 392 # define sqlite3BtreeEnter(X)
 393 # define sqlite3BtreeEnterAll(X)
 394 # define sqlite3BtreeSharable(X) 0
 395 # define sqlite3BtreeEnterCursor(X)
 396 # define sqlite3BtreeConnectionCount(X) 1
 397 #endif
 398
 399 #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
 400   void sqlite3BtreeLeave(Btree*);
 401   void sqlite3BtreeLeaveCursor(BtCursor*);
 402   void sqlite3BtreeLeaveAll(sqlite3*);
 403 #ifndef NDEBUG
 404   /* These routines are used inside assert() statements only. */
 405   int sqlite3BtreeHoldsMutex(Btree*);
 406   int sqlite3BtreeHoldsAllMutexes(sqlite3*);
 407   int sqlite3SchemaMutexHeld(sqlite3*,int,Schema*);
 408 #endif
 409 #else
 410
 411 # define sqlite3BtreeLeave(X)
 412 # define sqlite3BtreeLeaveCursor(X)
 413 # define sqlite3BtreeLeaveAll(X)
 414
 415 # define sqlite3BtreeHoldsMutex(X) 1
 416 # define sqlite3BtreeHoldsAllMutexes(X) 1
 417 # define sqlite3SchemaMutexHeld(X,Y,Z) 1
 418 #endif
 419
 420
 421 #endif /* SQLITE_BTREE_H */