Documentation Source Text

proc btree_api_defn {args} {

  foreach api $args {

    set re_head {\n[^\n]*}
    if { [string match BTREE* $api] } {
      set re_tail {[^\n]*\n}
    } else {
      set re_tail {[^;]*;}
    }

    regexp $re_head$api$re_tail $::btree_h api_defn
    lappend ret [string trim $api_defn]
  }
  return "<pre class=api>[join $ret "\n"]</pre>"
}
................................................................................
    the interfaces and sub-systems described in this document are not stable.
    They may be changed in any way with each new SQLite release. Any 
    external software development that uses these interfaces must be prepared
    to adapt to interface refactoring without notice.

  [h2 "Document and Requirements Organization"]





     [Table]
        [Tr] <th> Requirement ids <th> Contents
        [Tr] <td> H50**** <td> Requirement statements specifying the functionality required of the B-Tree module.
        [Tr] <td> H51**** <td> Requirement statements specifying the API provided by the B-Tree module.
        [Tr] <td> L****** <td> Requirement statements specifying some details of the internal workings of the B-Tree module.
      </table>

  [h2 "Glossary"]

    <table id=glossary>


      [Glossary "B-Tree Database Connection" {
        A B-Tree database connection is a single client connection to an in-memory 
        page cache, through which a single temporary or persistent database may
        be accessed. This term is used throughout this document to avoid confusing
	such connections with SQL level SQLite client connections, which are
        sometime simply termed "database connections".
      }]
................................................................................
      zero pages in size.

      [fancyformat_import_requirement H50080]
      [fancyformat_import_requirement H50090]

    [h3 "Transaction and Savepoint Functions"]

  <ul>
    <li> Begin transaction.




















    <li> Rollback transaction.


    <li> Commit transaction.
    <li> Query for transaction state (no-transaction, readonly, read-write).



    <li> Begin savepoint(s).
    <li> Release savepoint(s).
    <li> Rollback savepoint(s).
  </ul>










    <p>











  <ul>
    <li> CommitPhaseOne()/CommitPhaseTwo().








  </ul>

    [h3 "Reading From the Database Image"]





























































  <ul>
    <li> Open b-tree cursor.
    <li> Close b-tree cursor.
    <li> Seek cursor (and all of its variants).
    <li> Next/Prev cursor operations.
    <li> Retrieve current key/data pointed to by cursor.
    <li> Read selected database header fields.




  </ul>

    [h3 "Writing to the Database Image"]
  <ul>
    <li> Create new b-tree structure.
    <li> Drop existing b-tree structure.
    <li> Clear b-tree structure contents.
    <li> Incremental vacuum step.
    <li> Write selected database header fields.
    <li> Delete entry pointed to by cursor.
    <li> Insert new entry into b-tree.
  </ul>

    [h3 "Backup/Vacuum API Requirements"]
  <ul>
    <li> Callbacks for backup module.
    <li> Page read/write APIs for backup module.
  </ul>

    [h3 "Configuration Requirements"]

  <ul>
    <li> Set codec function (encryption).
    <li> Set/get the current locking_mode (exclusive or normal).
    <li> Set/get the current journal_mode (delete, persist, off, truncate or memory).
    <li> Set/get the current journal file size-limit.
................................................................................
    <li> Mutexes/thread-safety features.
    <li> Lock on schema memory object.
    <li> Locks on b-tree tables.
    <li> "Unlock notify" feature.
  </ul>

    <p class=todo>
      The b-tree module preventing deadlock (by always grabbing mutexes in order of BtShared pointer) should be required here.








  [h2 "Other Requirements"]

    [h3 "Caching and Memory Management Requirements"]
  <ul>
    <li> Memory allocation related features (pcache, scratch memory, other...).
    <li> Default pcache implementation (sqlite3_release_memory()).
................................................................................
    <p>
      And functions to query the current configuration:

      [btree_api_defn sqlite3BtreeSyncDisabled]

    [h2 "Query Interfaces"]

      [btree_api_defn sqlite3BtreeGetFilename sqlite3BtreeGetJournalname]
















    [h2 "Mutex Functions"]

<pre class=api>struct BtreeMutexArray {
  int nMutex;
  Btree *aBtree\[SQLITE_MAX_ATTACHED+1\];
};</pre>

      [btree_api_defn sqlite3BtreeEnter sqlite3BtreeEnterAll sqlite3BtreeLeave sqlite3BtreeEnterCursor sqlite3BtreeLeaveCursor sqlite3BtreeLeaveAll sqlite3BtreeMutexArrayEnter sqlite3BtreeMutexArrayLeave sqlite3BtreeMutexArrayInsert]










    [h2 "Reading and Traversing the Database Image"]

      [btree_api_defn BtCursor]

      [btree_api_defn sqlite3BtreeCursor sqlite3BtreeCursorSize sqlite3BtreeCloseCursor sqlite3BtreeClearCursor]

      [btree_api_defn sqlite3BtreeMoveto sqlite3BtreeMovetoUnpacked]




      [btree_api_defn sqlite3BtreeFirst sqlite3BtreeLast sqlite3BtreeNext sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

      [btree_api_defn sqlite3BtreeGetMeta]
................................................................................

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]

      [btree_api_defn sqlite3BtreeDelete sqlite3BtreeInsert sqlite3BtreeCursorHasMoved sqlite3BtreePutData]

      [btree_api_defn sqlite3BtreeIncrVacuum]

    [h2 "Transaction and Savepoint API"]

      [btree_api_defn sqlite3BtreeBeginTrans sqlite3BtreeCommitPhaseOne sqlite3BtreeCommitPhaseTwo sqlite3BtreeCommit sqlite3BtreeRollback]

      [btree_api_defn sqlite3BtreeBeginStmt sqlite3BtreeSavepoint]

      [btree_api_defn sqlite3BtreeIsInTrans sqlite3BtreeIsInReadTrans sqlite3BtreeIsInBackup]

    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.

proc btree_api_defn {args} {

  foreach api $args {

    set re_head {\n[^\n]*}
    if { [string match BTREE* $api] } {
      set re_tail {[^A-Za-z][^\n]*\n}
    } else {
      set re_tail {[^;A-Za-z][^;]*;}
    }

    regexp $re_head$api$re_tail $::btree_h api_defn
    lappend ret [string trim $api_defn]
  }
  return "<pre class=api>[join $ret "\n"]</pre>"
}
................................................................................
    the interfaces and sub-systems described in this document are not stable.
    They may be changed in any way with each new SQLite release. Any 
    external software development that uses these interfaces must be prepared
    to adapt to interface refactoring without notice.

  [h2 "Document and Requirements Organization"]

     <p class=todo>
       Change the following so that those requirements that describe the API
       are "low-level" requirements.

     [Table]
        [Tr] <th> Requirement ids <th> Contents
        [Tr] <td> H50**** <td> Requirement statements specifying the functionality required of the B-Tree module.
        [Tr] <td> H51**** <td> Requirement statements specifying the API provided by the B-Tree module.
        [Tr] <td> L****** <td> Requirement statements specifying some details of the internal workings of the B-Tree module.
      </table>

  [h2 "Glossary"]

    <table id=glossary>
      [Glossary "B-Tree Cursor" {
      }]
      [Glossary "B-Tree Database Connection" {
        A B-Tree database connection is a single client connection to an in-memory 
        page cache, through which a single temporary or persistent database may
        be accessed. This term is used throughout this document to avoid confusing
	such connections with SQL level SQLite client connections, which are
        sometime simply termed "database connections".
      }]
................................................................................
      zero pages in size.

      [fancyformat_import_requirement H50080]
      [fancyformat_import_requirement H50090]

    [h3 "Transaction and Savepoint Functions"]

     <p class=todo>
       This needs a lot of work...

    <p>
      All read and write operations performed on a database image via the
      B-Tree module interfaces occur within the context of a read or write
      transaction. <span class=todo>Something about the ACID nature of
      transactions and how this applies to read and write transactions</span>)

    <p>

      [fancyformat_import_requirement H50100]
      [fancyformat_import_requirement H50101]

    <p>
      Read/write:

      [fancyformat_import_requirement H50102]
      [fancyformat_import_requirement H50103]
      [fancyformat_import_requirement H50104]

    <p class=todo>
      Multi-file transaction support.

    <p>
      Transaction state query:

      [fancyformat_import_requirement H50108]

    <p>
      Savepoints:




    <p class=todo>
      Define "savepoint transactions" and fix the following requirements.

      [fancyformat_import_requirement H50105]
      [fancyformat_import_requirement H50106]
      [fancyformat_import_requirement H50107]

    [h3 "Reading From the Database Image"]

    <p>
      The B-Tree module allows the user to read a subset of the fields from the
      database image header. Each such field is stored in the header as a 4-byte 
      unsigned big-endian integer. A complete description of each field and its 
      interpretation may be found in <cite>ref_file_format</cite>. 

      [fancyformat_import_requirement H50109]

    <p>
      In other words, the database image header fields that may be read via
      this module are:

    <ul>

      <li> The number of free pages in the database image,
      <li> The database image schema version (schema cookie).
      <li> The database image schema layer file-format.
      <li> The default page-cache size.
      <li> The "auto-vacuum last root-page" field.
      <li> The database image text-encoding field.
      <li> The database image user-cookie value.
      <li> The database image incremental-vacuum flag.
    </ul>


    <p>
      With the exception of the database image header fields described above,
      all data is read from the database image using B-Tree cursors. A B-Tree
      cursor is a control structure for traversing the contents of a single
      table or index b-tree structure within a database image. As well as
      "forward" and "back" operations, a B-Tree cursor supports fast seeking to
      a table entry identified by key value, or to the first or last entry in
      the table.

    <p>
      When a B-Tree cursor is created, the specific table or index b-tree that
      it is used to traverse is identified by the database image page number 
      of its root page. Since the root-page of the schema table is always page
      1, and the contents of the schema table includes the root page numbers of all
      other index and table b-tree structures in the database image, it is
      possible for the application to determine the set of valid root-page
      numbers by first traversing the schema table.

      [fancyformat_import_requirement H50110]
      [fancyformat_import_requirement H50111]
      [fancyformat_import_requirement H50112]
      [fancyformat_import_requirement H50113]
      [fancyformat_import_requirement H50114]
      [fancyformat_import_requirement H50115]
      [fancyformat_import_requirement H50116]
      [fancyformat_import_requirement H50117]
      [fancyformat_import_requirement H50118]

    <p>
      As well as traversing a b-tree structure using the operations enumerated
      by the above requirements, it is also possible to use a cursor to search
      a b-tree structure for a specified key value. If the key value can be
      found, the cursor is left pointing at the entry with the specified key
      value. Otherwise, the cursor is left pointing at either the entry with the 
      largest key that is smaller than the specified key, or to the entry with 
      the smallest key that is larger than the specified key. For table b-tree
      structures, where the key values are 64-bit integers, the definition of
      smaller, larger and equal to is straightforward. For index b-tree
      structures, where the key values are database records, the manner in
      which key values must be compared is more complicated. Refer to
      <cite>ref_file_format</cite> for a full explanation.

    <p class=todo>
      There is a specific section in <cite>ref_file_format</cite> devoted to
      record sort order in index b-tree structures. There needs to be some way to
      point to it. Or, better, to the requirement or range of requirements.

    <p class=todo>
      Maybe a system that automatically links text like H30100 to the
      corresponding requirement. Within a document if it can find it, or a
      summary page (hlreq.html for example).

    <p class=todo>
      Requirements for seek.

      [fancyformat_import_requirement H50119]
      [fancyformat_import_requirement H50120]
      [fancyformat_import_requirement H50121]

    <p>
      Variants for index b-tree structures:
    <ul>






      <li> Ignore rowid.
      <li> Incr key.
      <li> Prefix match.
      <li> Prefix search.
    </ul>

    [h3 "Writing to the Database Image"]
  <ul>
    <li> Create new b-tree structure.
    <li> Drop existing b-tree structure.
    <li> Clear b-tree structure contents.
    <li> Incremental vacuum step.
    <li> Write selected database header fields.
    <li> Delete entry pointed to by cursor.
    <li> Insert new entry into b-tree.
  </ul>







    [h3 "Configuration Requirements"]

  <ul>
    <li> Set codec function (encryption).
    <li> Set/get the current locking_mode (exclusive or normal).
    <li> Set/get the current journal_mode (delete, persist, off, truncate or memory).
    <li> Set/get the current journal file size-limit.
................................................................................
    <li> Mutexes/thread-safety features.
    <li> Lock on schema memory object.
    <li> Locks on b-tree tables.
    <li> "Unlock notify" feature.
  </ul>

    <p class=todo>
      The b-tree module preventing deadlock (by always grabbing mutexes in
      order of BtShared pointer) should be required here.

    [h3 "Backup/Vacuum API Requirements"]
  <ul>
    <li> Callbacks for backup module.
    <li> Page read/write APIs for backup module.
  </ul>

  [h2 "Other Requirements"]

    [h3 "Caching and Memory Management Requirements"]
  <ul>
    <li> Memory allocation related features (pcache, scratch memory, other...).
    <li> Default pcache implementation (sqlite3_release_memory()).
................................................................................
    <p>
      And functions to query the current configuration:

      [btree_api_defn sqlite3BtreeSyncDisabled]

    [h2 "Query Interfaces"]

      [btree_api_defn sqlite3BtreeGetFilename]

      [fancyformat_import_requirement H51011]
      [fancyformat_import_requirement H51012]

      [btree_api_defn sqlite3BtreeGetJournalname]

      [fancyformat_import_requirement H51013]
      [fancyformat_import_requirement H51014]

    <p>
      Requirement H51013 holds true even if the B-Tree database connection is
      configured to use an in-memory journal file or no journal file at all
      (<span class=todo>ref requirements</span>). In these cases the buffer returned
      contains the full-path of the journal file that would be used if the
      connection were configured to use a journal file.

    [h2 "Mutex Functions"]

<pre class=api>struct BtreeMutexArray {
  int nMutex;
  Btree *aBtree\[SQLITE_MAX_ATTACHED+1\];
};</pre>

      [btree_api_defn sqlite3BtreeEnter sqlite3BtreeEnterAll sqlite3BtreeLeave sqlite3BtreeEnterCursor sqlite3BtreeLeaveCursor sqlite3BtreeLeaveAll sqlite3BtreeMutexArrayEnter sqlite3BtreeMutexArrayLeave sqlite3BtreeMutexArrayInsert]

    [h2 "Transaction and Savepoint API"]

      [btree_api_defn sqlite3BtreeBeginTrans sqlite3BtreeCommitPhaseOne sqlite3BtreeCommitPhaseTwo sqlite3BtreeCommit sqlite3BtreeRollback]

      [btree_api_defn sqlite3BtreeBeginStmt sqlite3BtreeSavepoint]

      [btree_api_defn sqlite3BtreeIsInTrans sqlite3BtreeIsInReadTrans sqlite3BtreeIsInBackup]


    [h2 "Reading and Traversing the Database Image"]

      [btree_api_defn BtCursor]

      [btree_api_defn sqlite3BtreeCursor sqlite3BtreeCursorSize sqlite3BtreeCloseCursor sqlite3BtreeClearCursor]

      [btree_api_defn sqlite3BtreeMoveto sqlite3BtreeMovetoUnpacked]

      <p class=todo>
        sqlite3BtreeMoveto is never called from outside of the b-tree layer. It could/should be removed from the API.

      [btree_api_defn sqlite3BtreeFirst sqlite3BtreeLast sqlite3BtreeNext sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

      [btree_api_defn sqlite3BtreeGetMeta]
................................................................................

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]

      [btree_api_defn sqlite3BtreeDelete sqlite3BtreeInsert sqlite3BtreeCursorHasMoved sqlite3BtreePutData]

      [btree_api_defn sqlite3BtreeIncrVacuum]









    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.

new database image. 

HLR H50090
The B-Tree module shall provide an interface to configure whether or not a new
database image is auto-vacuum capable.






































































































HLR H51001
If successful, a call to the sqlite3BtreeOpen function shall return SQLITE_OK
and set the value of *ppBtree to contain a new B-Tree database connection
handle.

................................................................................
sqlite3BtreeClose, just as if their handles were passed to
sqlite3BtreeCloseCursor.

new database image. 

HLR H50090
The B-Tree module shall provide an interface to configure whether or not a new
database image is auto-vacuum capable.


HLR H50100
The B-Tree module shall provide an interface to open (start) a read-only transaction.

HLR H50101
The B-Tree module shall provide an interface to close (finish) a read-only transaction.

HLR H50102
The B-Tree module shall provide an interface to open a read/write transaction
or to upgrade from a read-only transaction to a read/write transaction.

HLR H50103
The B-Tree module shall provide an interface to commit a read/write transaction.

HLR H50104
The B-Tree module shall provide an interface to rollback a read/write transaction.

HLR H50105
The B-Tree module shall provide an interface to open savepoint transactions.

HLR H50106
The B-Tree module shall provide an interface to commit savepoint transactions.

HLR H50107
The B-Tree module shall provide an interface to rollback savepoint transactions.

HLR H50108
The B-Tree module shall provide an interface to query a B-Tree database
connection to determine if there is an open transaction, and if so if the open
transaction is read-only or read/write.



HLR H50109
The B-Tree module shall provide an interface to read the value of any of the
4-byte unsigned big-endian integer fields beginning at byte offset 36 of the
database image.

HLR H50110
The B-Tree module shall provide an interface to open a B-Tree cursor on any table or
index b-tree within the database image, given its root page number.

HLR H50111
The B-Tree module shall provide an interface to close a B-Tree cursor.

HLR H50112
The B-Tree module shall provide an interface to move an open B-Tree cursor to
the entry associated with the largest key in the open b-tree structure.

HLR H50113
The B-Tree module shall provide an interface to move an open B-Tree cursor to
the entry associated with the smallest key in the open b-tree structure.


HLR H50114
The B-Tree module shall provide an interface to move an open B-Tree cursor that
currently points at a valid b-tree entry to the next entry in the b-tree
structure, sorted in order of key value, if any.

HLR H50115
The B-Tree module shall provide an interface to move an open B-Tree cursor that
currently points at a valid b-tree entry to the previous entry in the b-tree
structure, sorted in order of key value, if any.

HLR H50116
The B-Tree module shall provide an interface to retrieve the key value 
associated with the b-tree structure entry that a B-Tree cursor is pointing to,
if any.

HLR H50117
The B-Tree module shall provide an interface to retrieve the blob of data (the
database record) associated with the b-tree structure entry that a B-Tree
cursor open on a table b-tree is pointing to, if any.

HLR H50118
The B-Tree module shall provide an interface to return the number of entries
currently stored in the b-tree structure that a B-Tree cursor is open on.


HLR H50119
Given a key value, the B-Tree module shall provide an interface to move a
B-Tree cursor open on a table b-tree to the B-Tree entry with the matching
key value, if such an entry exists.

HLR H50120
If the interface required by H50119 is used to search for a key value that is
not present in the b-tree structure and the b-tree is not empty, the cursor shall
be moved to an existing entry that would be adjacent to a hypothetical
entry with the specified key value. 

HLR H50121
The interface required by H50119 shall provide an indication to the caller as
to whether the cursor is left pointing at an entry with a key value that is
smaller, larger or equal to the requested value, or if it is pointing to no
entry at all (because the b-tree structure is empty).






HLR H51001
If successful, a call to the sqlite3BtreeOpen function shall return SQLITE_OK
and set the value of *ppBtree to contain a new B-Tree database connection
handle.

................................................................................
sqlite3BtreeClose, just as if their handles were passed to
sqlite3BtreeCloseCursor.





HLR H51011
A call to the sqlite3BtreeGetFilename function with a valid B-Tree database
connection handle opened on a persistent database as the first argument shall
return a pointer to a buffer containing the full-path of the database file
formatted as a nul-terminated, UTF-8 string.

HLR H51012
A call to the sqlite3BtreeGetFilename function with a valid B-Tree database
connection handle opened on a temporary database as the first argument shall
return a pointer to a buffer to a nul-terminated string zero bytes in length
(i.e. the first byte of the buffer shall be 0x00).

HLR H51013
A call to the sqlite3BtreeGetJournalname function with a valid B-Tree database
connection handle opened on a persistent database as the first argument shall
return a pointer to a buffer containing the full-path of the journal file
formatted as a nul-terminated, UTF-8 string.

HLR H51014
A call to the sqlite3BtreeGetJournalname function with a valid B-Tree database
connection handle opened on a temporary database as the first argument shall
return a pointer to a buffer to a nul-terminated string zero bytes in length
(i.e. the first byte of the buffer shall be 0x00).