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 sqlite3BtreeIsInTrans(Btree*);
  89 int sqlite3BtreeIsInReadTrans(Btree*);
  90 int sqlite3BtreeIsInBackup(Btree*);
  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 int sqlite3BtreeSavepoint(Btree *, int, int);
  97
  98 const char *sqlite3BtreeGetFilename(Btree *);
  99 const char *sqlite3BtreeGetJournalname(Btree *);
 100 int sqlite3BtreeCopyFile(Btree *, Btree *);
 101
 102 int sqlite3BtreeIncrVacuum(Btree *);
 103
 104 /* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR
 105 ** of the flags shown below.
 106 **
 107 ** Every SQLite table must have either BTREE_INTKEY or BTREE_BLOBKEY set.
 108 ** With BTREE_INTKEY, the table key is a 64-bit integer and arbitrary data
 109 ** is stored in the leaves.  (BTREE_INTKEY is used for SQL tables.)  With
 110 ** BTREE_BLOBKEY, the key is an arbitrary BLOB and no content is stored
 111 ** anywhere - the key is the content.  (BTREE_BLOBKEY is used for SQL
 112 ** indices.)
 113 */
 114 #define BTREE_INTKEY     1    /* Table has only 64-bit signed integer keys */
 115 #define BTREE_BLOBKEY    2    /* Table has keys only - no data */
 116
 117 int sqlite3BtreeDropTable(Btree*, int, int*);
 118 int sqlite3BtreeClearTable(Btree*, int, int*);
 119 int sqlite3BtreeClearTableOfCursor(BtCursor*);
 120 int sqlite3BtreeTripAllCursors(Btree*, int, int);
 121
 122 void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue);
 123 int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);
 124
 125 int sqlite3BtreeNewDb(Btree *p);
 126
 127 /*
 128 ** The second parameter to sqlite3BtreeGetMeta or sqlite3BtreeUpdateMeta
 129 ** should be one of the following values. The integer values are assigned
 130 ** to constants so that the offset of the corresponding field in an
 131 ** SQLite database header may be found using the following formula:
 132 **
 133 **   offset = 36 + (idx * 4)
 134 **
 135 ** For example, the free-page-count field is located at byte offset 36 of
 136 ** the database file header. The incr-vacuum-flag field is located at
 137 ** byte offset 64 (== 36+4*7).
 138 **
 139 ** The BTREE_DATA_VERSION value is not really a value stored in the header.
 140 ** It is a read-only number computed by the pager.  But we merge it with
 141 ** the header value access routines since its access pattern is the same.
 142 ** Call it a "virtual meta value".
 143 */
 144 #define BTREE_FREE_PAGE_COUNT     0
 145 #define BTREE_SCHEMA_VERSION      1
 146 #define BTREE_FILE_FORMAT         2
 147 #define BTREE_DEFAULT_CACHE_SIZE  3
 148 #define BTREE_LARGEST_ROOT_PAGE   4
 149 #define BTREE_TEXT_ENCODING       5
 150 #define BTREE_USER_VERSION        6
 151 #define BTREE_INCR_VACUUM         7
 152 #define BTREE_APPLICATION_ID      8
 153 #define BTREE_DATA_VERSION        15  /* A virtual meta-value */
 154
 155 /*
 156 ** Kinds of hints that can be passed into the sqlite3BtreeCursorHint()
 157 ** interface.
 158 **
 159 ** BTREE_HINT_RANGE  (arguments: Expr*, Mem*)
 160 **
 161 **     The first argument is an Expr* (which is guaranteed to be constant for
 162 **     the lifetime of the cursor) that defines constraints on which rows
 163 **     might be fetched with this cursor.  The Expr* tree may contain
 164 **     TK_REGISTER nodes that refer to values stored in the array of registers
 165 **     passed as the second parameter.  In other words, if Expr.op==TK_REGISTER
 166 **     then the value of the node is the value in Mem[pExpr.iTable].  Any
 167 **     TK_COLUMN node in the expression tree refers to the Expr.iColumn-th
 168 **     column of the b-tree of the cursor.  The Expr tree will not contain
 169 **     any function calls nor subqueries nor references to b-trees other than
 170 **     the cursor being hinted.
 171 **
 172 **     The design of the _RANGE hint is aid b-tree implementations that try
 173 **     to prefetch content from remote machines - to provide those
 174 **     implementations with limits on what needs to be prefetched and thereby
 175 **     reduce network bandwidth.
 176 **
 177 ** Note that BTREE_HINT_FLAGS with BTREE_BULKLOAD is the only hint used by
 178 ** standard SQLite.  The other hints are provided for extentions that use
 179 ** the SQLite parser and code generator but substitute their own storage
 180 ** engine.
 181 */
 182 #define BTREE_HINT_RANGE 0       /* Range constraints on queries */
 183
 184 /*
 185 ** Values that may be OR'd together to form the argument to the
 186 ** BTREE_HINT_FLAGS hint for sqlite3BtreeCursorHint():
 187 **
 188 ** The BTREE_BULKLOAD flag is set on index cursors when the index is going
 189 ** to be filled with content that is already in sorted order.
 190 **
 191 ** The BTREE_SEEK_EQ flag is set on cursors that will get OP_SeekGE or
 192 ** OP_SeekLE opcodes for a range search, but where the range of entries
 193 ** selected will all have the same key.  In other words, the cursor will
 194 ** be used only for equality key searches.
 195 **
 196 */
 197 #define BTREE_BULKLOAD 0x00000001  /* Used to full index in sorted order */
 198 #define BTREE_SEEK_EQ  0x00000002  /* EQ seeks only - no range seeks */
 199
 200 /*
 201 ** Flags passed as the third argument to sqlite3BtreeCursor().
 202 **
 203 ** For read-only cursors the wrFlag argument is always zero. For read-write
 204 ** cursors it may be set to either (BTREE_WRCSR|BTREE_FORDELETE) or just
 205 ** (BTREE_WRCSR). If the BTREE_FORDELETE bit is set, then the cursor will
 206 ** only be used by SQLite for the following:
 207 **
 208 **   * to seek to and then delete specific entries, and/or
 209 **
 210 **   * to read values that will be used to create keys that other
 211 **     BTREE_FORDELETE cursors will seek to and delete.
 212 **
 213 ** The BTREE_FORDELETE flag is an optimization hint.  It is not used by
 214 ** by this, the native b-tree engine of SQLite, but it is available to
 215 ** alternative storage engines that might be substituted in place of this
 216 ** b-tree system.  For alternative storage engines in which a delete of
 217 ** the main table row automatically deletes corresponding index rows,
 218 ** the FORDELETE flag hint allows those alternative storage engines to
 219 ** skip a lot of work.  Namely:  FORDELETE cursors may treat all SEEK
 220 ** and DELETE operations as no-ops, and any READ operation against a
 221 ** FORDELETE cursor may return a null row: 0x01 0x00.
 222 */
 223 #define BTREE_WRCSR     0x00000004     /* read-write cursor */
 224 #define BTREE_FORDELETE 0x00000008     /* Cursor is for seek/delete only */
 225
 226 int sqlite3BtreeCursor(
 227   Btree*,                              /* BTree containing table to open */
 228   Pgno iTable,                         /* Index of root page */
 229   int wrFlag,                          /* 1 for writing.  0 for read-only */
 230   struct KeyInfo*,                     /* First argument to compare function */
 231   BtCursor *pCursor                    /* Space to write cursor structure */
 232 );
 233 BtCursor *sqlite3BtreeFakeValidCursor(void);
 234 int sqlite3BtreeCursorSize(void);
 235 void sqlite3BtreeCursorZero(BtCursor*);
 236 void sqlite3BtreeCursorHintFlags(BtCursor*, unsigned);
 237 #ifdef SQLITE_ENABLE_CURSOR_HINTS
 238 void sqlite3BtreeCursorHint(BtCursor*, int, ...);
 239 #endif
 240
 241 int sqlite3BtreeCloseCursor(BtCursor*);
 242 int sqlite3BtreeMovetoUnpacked(
 243   BtCursor*,
 244   UnpackedRecord *pUnKey,
 245   i64 intKey,
 246   int bias,
 247   int *pRes
 248 );
 249 int sqlite3BtreeCursorHasMoved(BtCursor*);
 250 int sqlite3BtreeCursorRestore(BtCursor*, int*);
 251 int sqlite3BtreeDelete(BtCursor*, u8 flags);
 252
 253 /* Allowed flags for sqlite3BtreeDelete() and sqlite3BtreeInsert() */
 254 #define BTREE_SAVEPOSITION 0x02  /* Leave cursor pointing at NEXT or PREV */
 255 #define BTREE_AUXDELETE    0x04  /* not the primary delete operation */
 256 #define BTREE_APPEND       0x08  /* Insert is likely an append */
 257
 258 /* An instance of the BtreePayload object describes the content of a single
 259 ** entry in either an index or table btree.
 260 **
 261 ** Index btrees (used for indexes and also WITHOUT ROWID tables) contain
 262 ** an arbitrary key and no data.  These btrees have pKey,nKey set to the
 263 ** key and the pData,nData,nZero fields are uninitialized.  The aMem,nMem
 264 ** fields give an array of Mem objects that are a decomposition of the key.
 265 ** The nMem field might be zero, indicating that no decomposition is available.
 266 **
 267 ** Table btrees (used for rowid tables) contain an integer rowid used as
 268 ** the key and passed in the nKey field.  The pKey field is zero.
 269 ** pData,nData hold the content of the new entry.  nZero extra zero bytes
 270 ** are appended to the end of the content when constructing the entry.
 271 ** The aMem,nMem fields are uninitialized for table btrees.
 272 **
 273 ** Field usage summary:
 274 **
 275 **               Table BTrees                   Index Btrees
 276 **
 277 **   pKey        always NULL                    encoded key
 278 **   nKey        the ROWID                      length of pKey
 279 **   pData       data                           not used
 280 **   aMem        not used                       decomposed key value
 281 **   nMem        not used                       entries in aMem
 282 **   nData       length of pData                not used
 283 **   nZero       extra zeros after pData        not used
 284 **
 285 ** This object is used to pass information into sqlite3BtreeInsert().  The
 286 ** same information used to be passed as five separate parameters.  But placing
 287 ** the information into this object helps to keep the interface more
 288 ** organized and understandable, and it also helps the resulting code to
 289 ** run a little faster by using fewer registers for parameter passing.
 290 */
 291 struct BtreePayload {
 292   const void *pKey;       /* Key content for indexes.  NULL for tables */
 293   sqlite3_int64 nKey;     /* Size of pKey for indexes.  PRIMARY KEY for tabs */
 294   const void *pData;      /* Data for tables. */
 295   sqlite3_value *aMem;    /* First of nMem value in the unpacked pKey */
 296   u16 nMem;               /* Number of aMem[] value.  Might be zero */
 297   int nData;              /* Size of pData.  0 if none. */
 298   int nZero;              /* Extra zero data appended after pData,nData */
 299 };
 300
 301 int sqlite3BtreeInsert(BtCursor*, const BtreePayload *pPayload,
 302                        int flags, int seekResult);
 303 int sqlite3BtreeFirst(BtCursor*, int *pRes);
 304 int sqlite3BtreeLast(BtCursor*, int *pRes);
 305 int sqlite3BtreeNext(BtCursor*, int flags);
 306 int sqlite3BtreeEof(BtCursor*);
 307 int sqlite3BtreePrevious(BtCursor*, int flags);
 308 i64 sqlite3BtreeIntegerKey(BtCursor*);
 309 void sqlite3BtreeCursorPin(BtCursor*);
 310 void sqlite3BtreeCursorUnpin(BtCursor*);
 311 #ifdef SQLITE_ENABLE_OFFSET_SQL_FUNC
 312 i64 sqlite3BtreeOffset(BtCursor*);
 313 #endif
 314 int sqlite3BtreePayload(BtCursor*, u32 offset, u32 amt, void*);
 315 const void *sqlite3BtreePayloadFetch(BtCursor*, u32 *pAmt);
 316 u32 sqlite3BtreePayloadSize(BtCursor*);
 317 sqlite3_int64 sqlite3BtreeMaxRecordSize(BtCursor*);
 318
 319 char *sqlite3BtreeIntegrityCheck(sqlite3*,Btree*,Pgno*aRoot,int nRoot,int,int*);
 320 struct Pager *sqlite3BtreePager(Btree*);
 321 i64 sqlite3BtreeRowCountEst(BtCursor*);
 322
 323 #ifndef SQLITE_OMIT_INCRBLOB
 324 int sqlite3BtreePayloadChecked(BtCursor*, u32 offset, u32 amt, void*);
 325 int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);
 326 void sqlite3BtreeIncrblobCursor(BtCursor *);
 327 #endif
 328 void sqlite3BtreeClearCursor(BtCursor *);
 329 int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);
 330 int sqlite3BtreeCursorHasHint(BtCursor*, unsigned int mask);
 331 int sqlite3BtreeIsReadonly(Btree *pBt);
 332 int sqlite3HeaderSizeBtree(void);
 333
 334 #ifndef NDEBUG
 335 int sqlite3BtreeCursorIsValid(BtCursor*);
 336 #endif
 337 int sqlite3BtreeCursorIsValidNN(BtCursor*);
 338
 339 int sqlite3BtreeCount(sqlite3*, BtCursor*, i64*);
 340
 341 #ifdef SQLITE_TEST
 342 int sqlite3BtreeCursorInfo(BtCursor*, int*, int);
 343 void sqlite3BtreeCursorList(Btree*);
 344 #endif
 345
 346 #ifndef SQLITE_OMIT_WAL
 347   int sqlite3BtreeCheckpoint(Btree*, int, int *, int *);
 348 #endif
 349
 350 /*
 351 ** If we are not using shared cache, then there is no need to
 352 ** use mutexes to access the BtShared structures.  So make the
 353 ** Enter and Leave procedures no-ops.
 354 */
 355 #ifndef SQLITE_OMIT_SHARED_CACHE
 356   void sqlite3BtreeEnter(Btree*);
 357   void sqlite3BtreeEnterAll(sqlite3*);
 358   int sqlite3BtreeSharable(Btree*);
 359   void sqlite3BtreeEnterCursor(BtCursor*);
 360   int sqlite3BtreeConnectionCount(Btree*);
 361 #else
 362 # define sqlite3BtreeEnter(X)
 363 # define sqlite3BtreeEnterAll(X)
 364 # define sqlite3BtreeSharable(X) 0
 365 # define sqlite3BtreeEnterCursor(X)
 366 # define sqlite3BtreeConnectionCount(X) 1
 367 #endif
 368
 369 #if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
 370   void sqlite3BtreeLeave(Btree*);
 371   void sqlite3BtreeLeaveCursor(BtCursor*);
 372   void sqlite3BtreeLeaveAll(sqlite3*);
 373 #ifndef NDEBUG
 374   /* These routines are used inside assert() statements only. */
 375   int sqlite3BtreeHoldsMutex(Btree*);
 376   int sqlite3BtreeHoldsAllMutexes(sqlite3*);
 377   int sqlite3SchemaMutexHeld(sqlite3*,int,Schema*);
 378 #endif
 379 #else
 380
 381 # define sqlite3BtreeLeave(X)
 382 # define sqlite3BtreeLeaveCursor(X)
 383 # define sqlite3BtreeLeaveAll(X)
 384
 385 # define sqlite3BtreeHoldsMutex(X) 1
 386 # define sqlite3BtreeHoldsAllMutexes(X) 1
 387 # define sqlite3SchemaMutexHeld(X,Y,Z) 1
 388 #endif
 389
 390
 391 #endif /* SQLITE_BTREE_H */