Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Work on b-tree requirements. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
fdf074286be78765c5a55154fe610f8e |
User & Date: | dan 2009-06-01 12:04:08.000 |
Context
2009-06-02
| ||
01:37 | Fix a typo in download.html reported as cvstrac ticket #3892. (check-in: 0f6eae0c0d user: dan tags: trunk) | |
2009-06-01
| ||
12:04 | Work on b-tree requirements. (check-in: fdf074286b user: dan tags: trunk) | |
2009-05-30
| ||
11:45 | Progress on btreemodule.html (check-in: 7274af9a66 user: dan tags: trunk) | |
Changes
Changes to pages/btreemodule.in.
︙ | ︙ | |||
10 11 12 13 14 15 16 | proc btree_api_defn {args} { foreach api $args { set re_head {\n[^\n]*} if { [string match BTREE* $api] } { | | | | 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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>" } |
︙ | ︙ | |||
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | 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". }] | > > > > > > | 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | 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". }] |
︙ | ︙ | |||
158 159 160 161 162 163 164 | zero pages in size. [fancyformat_import_requirement H50080] [fancyformat_import_requirement H50090] [h3 "Transaction and Savepoint Functions"] | > > | > > > | | | > | > > | > | | > > > | > > > > | > | > > | > > > > > > > > > > > > > > > > | > > > > > > > > > | > > > > > > > > | > > > > > > > > | > > > > > > > > > | > > > > > > > > > > > > > | > > > > | > > > > > > > > > > > > > > > > > > > | < < < < < < | 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 | 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. |
︙ | ︙ | |||
225 226 227 228 229 230 231 | <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> | | > > > > > > > | 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 | <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()). |
︙ | ︙ | |||
380 381 382 383 384 385 386 | <p> And functions to query the current configuration: [btree_api_defn sqlite3BtreeSyncDisabled] [h2 "Query Interfaces"] | | > > > > > > > > > > > > > > > > > > > > > > > > > > > < < < < < < < < | 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 | <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] [h2 "Modifying the Database Image"] [btree_api_defn sqlite3BtreeCreateTable] [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA] [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. |
︙ | ︙ |
Changes to req/hlr50000.txt.
︙ | ︙ | |||
35 36 37 38 39 40 41 42 43 44 45 46 47 48 | 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. | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | 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. |
︙ | ︙ | |||
100 101 102 103 104 105 106 107 108 109 | sqlite3BtreeClose, just as if their handles were passed to sqlite3BtreeCloseCursor. | > > > > > > > > > > > > > > > > > > > > > > > | 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 | 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). |