Documentation Source Text

        [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" {
        <span class=todo>Define this.
      }]
      [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".
      }]
      [Glossary "Lazy-write cache" {
        <span class=todo>Define this.
      }]
      [Glossary "Page cache" {
        <span class=todo>Define this.
      }]
      [Glossary "Persistent database" {
        <span class=todo>Define this.
      }]
      [Glossary "Read-through cache" {
        <span class=todo>Define this.
      }]
      [Glossary "Shared-cache mode" {
        <span class=todo>Define this.
      }]
      [Glossary "SQLite Error Code" {
        <span class=todo>Define this.
      }]
      [Glossary "Temporary database" {
        <span class=todo>Define this.
      }]
    </table>
   

  [h1 "Module Requirements"]

  <p>

      are only applicable to new database images. For the purposes of the
      following requirements, a "new database image" is defined as one that is
      zero pages in size.

      [fancyformat_import_requirement H50080]
      [fancyformat_import_requirement H50090]

    [h3 "Transaction and Savepoint Functions" hlr_transactions]

     <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>)



      [fancyformat_import_requirement H50100]
      [fancyformat_import_requirement H50101]

    <p>
      Read/write:

      [fancyformat_import_requirement H50102]

    <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" hlr_reading_data]

    <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>. 

      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).




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

    <p class=todo>
      Does it depend on the structure of the tree whether the cursor is left
      pointing to a smaller or larger entry after a failed search? Or is it
      possible to determine which it will be based only on the set of keys
      stored in the tree?

    <p>
      As well as the standard search operation described by the above
      requirements, cursors open on index b-tree structures are required to
      support several variants, as follows:

    <ul>
      <li> <b>Ignore rowid search mode</b>. The final value in a database
	   record used as an index-btree key is always an integer "rowid"
	   field. A search in this mode proceeds as if each key in the b-tree
           was missing this field.

      <li> <b>Increment key mode</b>.
      <li> <b>Prefix match mode</b>.
      <li> <b>Prefix search mode</b>.
    </ul>

    <p class=todo>
      Finish the bullet points above and add HLR for each search mode.

    [h3 "Writing to the Database Image"]

    <p>
      The B-Tree module allows the user to write values to a subset of the
      fields from the database image header. The set of writable fields is
      the same as the set of fields enumerated in section
      <cite>hlr_reading_data</cite> that the B-Tree module is required to
      provide read access to by requirement H50109.

      [fancyformat_import_requirement H50122]

    <p>
      The B-Tree module also supports operations to create new b-tree 
      structures within the database image. Existing b-tree structures may be
      deleted from the database image entirely, or their entire contents may be
      deleted, leaving an empty b-tree structure.

      [fancyformat_import_requirement H50123]
      [fancyformat_import_requirement H50124]
      [fancyformat_import_requirement H50125]


    <p>
      As one would expect, the B-Tree module also provides an interface to
      insert and delete entries from b-tree structures. These operations are
      performed using a B-Tree write cursor, a special type of B-Tree cursor
      (see section <cite>hlr_reading_data</cite>).

      [fancyformat_import_requirement H50126]
      [fancyformat_import_requirement H50127]
      [fancyformat_import_requirement H50128]

    <p class=todo>
      Incremental vacuum step.

    <p class=todo>
      This section should include how open cursors may be affected by database
      writes (i.e. if the current b-tree entry or the whole b-tree structure is
      modified or deleted).

    [h3 "Page-Cache Configuration Requirements"]

    <p>
      A page-cache has a number of operational parameters that may be configured
      at run-time via an open b-tree database connection. Note that even though the
      interfaces provided by this module allow these parameters to be set via a
      b-tree database connection, they are properties of the page-cache, not
      the b-tree database connection. In situations where more than one b-tree
      database connection is connected to a single page-cache, writes made via
      one b-tree database connection may overwrite the values set by another.
      The following table summarizes the available configuration parameters.

    [Table]
      [Tr] <th>Parameter <th>Description  <th>Requirements
      [Tr] <td>Locking-mode 
           <td><span class=todo>This!</span> 
           <td>H50138, H50139, H50140
      [Tr] <td>Journal-mode 
           <td><span class=todo>This!</span> 
           <td>H50141, H50142, H50143, H50144, H50145, H50146
      [Tr] <td>Journal-file size limit
	   <td>The journal-file size limit parameter may be set to any integer
	       value within the range of a 64-bit signed integer. Any negative
	       values is interpreted as "no limit". Otherwise, if the
	       journal-file size limit is set to zero or a positive number, it
	       represents an upper limit on the size of the journal file in
	       bytes. If the application executes a database write operation that
	       would normally cause the journal file to grow larger than this
	       configured limit, the operation fails and an error is returned
	       to the user. The default value of this parameter is -1 (no
               limit).
           <td>H50147, H50148, H50149
      [Tr] <td style="white-space:nowrap">Database-file size limit
	   <td>The database-image size limit parameter may be set to any integer
	       value greater than zero within the range of a 32-bit signed
               integer. The configured value represents an upper limit on the size of
	       the database image in pages. If the application executes a
               database write operation that would normally cause the database image to
	       grow larger than this configured limit, the operation fails and
               an error is returned to the user.
           <td>H50150, H50151, H50152
      [Tr] <td>Cache size
	   <td>The cache-size parameter may be set to any integer value. How it
               affects operation depends on the specific P-Cache implementation used
	       by the page-cache. <span class=todo>Refer to details for the
               behaviour of the built-in default P-Cache.</span>
           <td>
      [Tr] <td>Safety level
           <td><span class=todo>This!</span> 
           <td>
    </table>

      [fancyformat_import_requirement H50138]
      [fancyformat_import_requirement H50139]
      [fancyformat_import_requirement H50140]

    <p class=todo>
      And if a read/write transaction is downgraded to a read-only transaction?
      This scenario should also be dealt with in section <cite>hlr_transactions</cite>.

      [fancyformat_import_requirement H50141]
      [fancyformat_import_requirement H50142]
      [fancyformat_import_requirement H50143]
      [fancyformat_import_requirement H50144]
      [fancyformat_import_requirement H50145]
      [fancyformat_import_requirement H50146]

    <p class=todo>
      The difference in functionality provided by "off", "memory" and the 3
      modes that use a real journal file should also feature in
      <cite>hlr_transactions</cite>.

      [fancyformat_import_requirement H50147]
      [fancyformat_import_requirement H50148]
      [fancyformat_import_requirement H50149]

      [fancyformat_import_requirement H50150]
      [fancyformat_import_requirement H50151]
      [fancyformat_import_requirement H50152]

    <p class=todo>
      Interface to set the codec function (encryption).

    <p class=todo>
      The busy-handler. Where exactly does this come in? Transactions and
      savepoints section?

    <p>
      The six page-cache operational parameters listed above may also be
      queried. The following requirements specify the required query
      interfaces.

      [fancyformat_import_requirement H50132]
      [fancyformat_import_requirement H50133]
      [fancyformat_import_requirement H50134]
      [fancyformat_import_requirement H50135]
      [fancyformat_import_requirement H50136]
      [fancyformat_import_requirement H50137]

    <p>
      It is also possible to interrogate a b-tree database handle to determine
      if it was opened on a temporary or persistent database. An b-tree
      database handle opened on a persistent database may be queried for the
      name of (full-path to) either the database or journal file associated
      with the open database.

      [fancyformat_import_requirement H50131]
      [fancyformat_import_requirement H50129]
      [fancyformat_import_requirement H50130]

    [h3 "Multi-User Database Requirements"]
  <ul>

    <li> Lock on schema memory object.
    <li> Locks on b-tree tables.
    <li> "Unlock notify" feature.
    <li> Mutexes/thread-safety features.
  </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"]

      [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.

      <p class=todo>
	The "bias" argument to sqlite3BtreeMovetoUnpacked is only ever true
        when it is called from within sqlite3BtreeInsert. This argument could/should 
        also be removed from the API, if only to make it simpler to describe.

      [btree_api_defn sqlite3BtreeFirst sqlite3BtreeLast sqlite3BtreeNext sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

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 b-tree structure 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 H50122
The B-Tree module shall provide an interface to write a value to any of the
4-byte unsigned big-endian integer fields beginning at byte offset 36 of the
database image.

HLR H50123
The B-Tree module shall provide an interface to create a new index or table
b-tree structures within the database image. The interface shall automatically
assign a root-page to the new b-tree structure.

HLR H50124
The B-Tree module shall provide an interface to remove an existing index or 
table b-tree structure from the database image, given the root page number of
the b-tree to remove.

HLR H50125
The B-Tree module shall provide an interface to remove all entries from (delete
the contents of) an index or table b-tree, given the root page number of the
b-tree to empty.

HLR H50126
When opening a B-Tree cursor using the interface required by H50110, it shall
be possible to specify that the new cursor be a write cursor, or an ordinary
read-only cursor.

HLR H50127
The B-Tree module shall provide an interface that allows the user to delete the
b-tree entry that a write cursor points to, if any.

HLR H50128
The B-Tree module shall provide an interface to insert new entries into a table
or index B-Tree, given a write cursor open on the table or index b-tree the new
entry is to be inserted into.


HLR H50129
The B-Tree module shall provide an interface allowing the application to query
a b-tree database connection open on a persistent database for the name of the
underlying database file within the file-system.

HLR H50130
The B-Tree module shall provide an interface allowing the application to query
a b-tree database connection open on a persistent database for the name of the
underlying journal file within the file-system.

HLR H50131
The B-Tree module shall provide an interface to query an open b-tree database
handle to determine if the underlying database is a persistent database or a
temporary database.


HLR H50132
The B-Tree module shall provide an interface to query the current locking-mode
of a page-cache, given an open b-tree database connection to that page-cache.

HLR H50133
The B-Tree module shall provide an interface to query the current journal-mode
of a page-cache, given an open b-tree database connection to that page-cache.

HLR H50134
The B-Tree module shall provide an interface to query the current journal file
size-limit of a page-cache, given an open b-tree database connection to that
page-cache.

HLR H50135
The B-Tree module shall provide an interface to query the current database file
size-limit of a page-cache, given an open b-tree database connection to that
page-cache.

HLR H50136
The B-Tree module shall provide an interface to query the current cache-size
of a page-cache, given an open b-tree database connection to that page-cache.

HLR H50137
The B-Tree module shall provide an interface to query the current safety-level
of a page-cache, given an open b-tree database connection to that page-cache.


HLR H50138
The B-Tree module shall provide an interface allowing the application to set
the locking-mode of a page-cache to either "normal" or "exclusive", given an
open b-tree database connection to that page-cache.

HLR H50139
If the locking-mode of a page-cache is set to "normal" when a read/write 
or read-only transaction is ended, any locks held on the database file-system
representation by the page-cache shall be relinquished.

HLR H50140
If the locking-mode of a page-cache is set to "exclusive" when a read/write 
or read-only transaction is ended, any locks held on the database file-system
representation by the page-cache shall be retained.


HLR H50141
The B-Tree module shall provide an interface allowing the application to set
the journal-mode of a page-cache to one of "off", "memory", "delete",
"persist", or "truncate", given an open b-tree database connection to that
page-cache.

HLR H50142
If the journal-mode of a page-cache is set to "off" when a read/write
transaction is opened, then the transaction shall use no journal file.

HLR H50143
If the journal-mode of a page-cache is set to "memory" when a read/write
transaction is opened, then instead of using the journal file located in the
file-system, journal-file data shall be stored in main-memory.

HLR H50144
If the journal-mode of a page-cache is set to "delete" when a read/write
transaction is opened, then any journal file used by the transaction shall
be deleted at the conclusion of the transaction.

HLR H50145
If the journal-mode of a page-cache is set to "truncate" when a read/write
transaction is opened, then any journal file used by the transaction shall
be truncated to zero bytes in size at the conclusion of the transaction.

HLR H50146
If the journal-mode of a page-cache is set to "persist" when a read/write
transaction is opened, then any journal file used by the transaction shall
remain in the file-system at the conclusion of the transaction.


HLR H50147
The B-Tree module shall provide an interface to set the value of the
journal-file size limit configuration parameter of a page-cache, given
an open b-tree database connection to that page-cache.

HLR H50148
The default value assigned to the journal-file size limit configuration of a
page-cache shall be -1.

HLR H50149
If the journal-file size limit parameter is set to a non-negative value, and
the user executes a write operation that would otherwise require the journal
file to be extended to a size greater than the configured value in bytes, then
the operation shall fail and an error be returned to the user.


HLR H50150
The B-Tree module shall provide an interface to set the value of the
database-image size limit configuration parameter of a page-cache, given
an open b-tree database connection to that page-cache.

HLR H50151
The default value assigned to the database-image size limit configuration of a
page-cache shall be the value of the compile time symbol SQLITE_MAX_PAGE_COUNT
(1073741823 by default).

HLR H50152
If the database-image size limit parameter is set to a non-negative value, and
the user executes a write operation that would otherwise require the journal
file to be extended to a size greater than the configured value in bytes, then
the operation shall fail and an error be returned to the user.



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.