Documentation Source Text: Check-in [2b4a307362]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview

Comment:	Progress on btreemodule.html.
Downloads:	Tarball \| ZIP archive \| SQL archive
Timelines:	family \| ancestors \| descendants \| both \| trunk
Files:	files \| file ages \| folders
SHA1:	2b4a307362b604ae9b8f4050679ed4fc11c43114
User & Date:	dan 2009-06-06 12:06:11

Context

2009-06-07
00:01		Add a rough draft of the document describing how to use fossil to maintain a private branch of SQLite. (check-in: ce4ee2b8d3 user: drh tags: trunk)
2009-06-06
12:06		Progress on btreemodule.html. (check-in: 2b4a307362 user: dan tags: trunk)
2009-06-02
19:19		Fix a typo on the Documents page. (check-in: ee05430080 user: drh tags: trunk)

Changes

Hide Diffs Unified Diffs Ignore Whitespace Patch

Added images/btreemodule_balance_shallower.svg.

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!-- Created with Inkscape (http://www.inkscape.org/) -->
<svg
   xmlns:dc="http://purl.org/dc/elements/1.1/"
   xmlns:cc="http://creativecommons.org/ns#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
   width="700.07031"
   height="195"
   id="svg2553"
   sodipodi:version="0.32"
   inkscape:version="0.46"
   sodipodi:docname="btreemodule_balance_shallower.svg"
   inkscape:output_extension="org.inkscape.output.svg.inkscape"
   version="1.0">
  <defs
     id="defs2555">
    <marker
       inkscape:stockid="Arrow1Lend"
       orient="auto"
       refY="0"
       refX="0"
       id="Arrow1Lend"
       style="overflow:visible">
      <path
         id="path3355"
         d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
         transform="matrix(-0.8,0,0,-0.8,-10,0)" />
    </marker>
    <inkscape:perspective
       sodipodi:type="inkscape:persp3d"
       inkscape:vp_x="0 : 526.18109 : 1"
       inkscape:vp_y="0 : 1000 : 0"
       inkscape:vp_z="744.09448 : 526.18109 : 1"
       inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
       id="perspective2561" />
  </defs>
  <sodipodi:namedview
     id="base"
     pagecolor="#ffffff"
     bordercolor="#666666"
     borderopacity="1.0"
     gridtolerance="10000"
     guidetolerance="10"
     objecttolerance="10"
     inkscape:pageopacity="0.0"
     inkscape:pageshadow="2"
     inkscape:zoom="1.41"
     inkscape:cx="375.00663"
     inkscape:cy="25.984926"
     inkscape:document-units="px"
     inkscape:current-layer="layer1"
     showgrid="true"
     inkscape:snap-global="true"
     inkscape:window-width="1514"
     inkscape:window-height="972"
     inkscape:window-x="114"
     inkscape:window-y="18">
    <inkscape:grid
       type="xygrid"
       id="grid3339"
       visible="true"
       enabled="true" />
  </sodipodi:namedview>
  <metadata
     id="metadata2558">
    <rdf:RDF>
      <cc:Work
         rdf:about="">
        <dc:format>image/svg+xml</dc:format>
        <dc:type
           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
      </cc:Work>
    </rdf:RDF>
  </metadata>
  <g
     inkscape:label="Layer 1"
     inkscape:groupmode="layer"
     id="layer1"
     transform="translate(78.807861,-42.225464)">
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect3337"
       width="129.91663"
       height="19.862286"
       x="-49.916626"
       y="67.716751" />
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="129.81812"
       y="107.37309"
       id="text3343"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan3345"
         x="129.81812"
         y="107.37309"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">Right-child pointer</tspan></text>
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 79.901489,87.510812 L 89.901489,127.51081"
       id="path3347"
       sodipodi:nodetypes="cc" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect4127"
       width="129.91663"
       height="19.862286"
       x="29.90148"
       y="137.5108" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 49.818119,167.37311 L 39.818119,207.3731"
       id="path4129"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 89.818119,167.3731 L 89.818119,207.3731"
       id="path4131"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 129.81812,167.37311 L 139.81812,207.3731"
       id="path4133"
       sodipodi:nodetypes="cc" />
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="19.818121"
       y="227.37309"
       id="text4135"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan4137"
         x="19.818121"
         y="227.37309"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">Rest of Tree Content</tspan></text>
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="-78.807861"
       y="58.216755"
       id="text4143"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan4145"
         x="-78.807861"
         y="58.216755"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">     Root page of b-tree</tspan></text>
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 124.81812,102.3731 L 89.818119,102.3731 L 89.818119,102.3731"
       id="path4147"
       sodipodi:nodetypes="ccc" />
    <rect
       style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       id="rect4157"
       width="129.91663"
       height="19.862286"
       x="471.27551"
       y="68.354477" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 491.19214,98.216766 L 481.19214,138.21676"
       id="path4159"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 531.19214,98.216756 L 531.19214,138.21676"
       id="path4161"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
       d="M 571.19214,98.216766 L 581.19214,138.21676"
       id="path4163"
       sodipodi:nodetypes="cc" />
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="461.19214"
       y="158.21675"
       id="text4165"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan4167"
         x="461.19214"
         y="158.21675"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">Rest of Tree Content     </tspan></text>
    <text
       xml:space="preserve"
       style="font-size:40px;font-style:normal;font-weight:normal;line-height:125%;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;font-family:Bitstream Vera Sans"
       x="461.19214"
       y="58.216759"
       id="text4169"
       sodipodi:linespacing="125%"><tspan
         sodipodi:role="line"
         id="tspan4171"
         x="461.19214"
         y="58.216759"
         style="font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;writing-mode:lr-tb;text-anchor:start;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;font-family:Sans;-inkscape-font-specification:Sans">Root page of b-tree</tspan></text>
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       d="M 410,-5 L 410,195"
       id="path4219"
       transform="translate(-78.807861,42.225464)" />
  </g>
</svg>

Changes to images/fileformat/rtdocs.css.

  /* Style for requirements paragraph. */
  .req       { margin: 1.0em 10ex; color: darkblue }


  .subreq    { margin: 1.0em 5ex 1.0em 15ex; color: darkblue }
  .subsubreq { margin: 1.0em 5ex 1.0em 20ex; color: darkblue }

  .req:before { color: black; content: "[" attr(id) "] "}
  .subreq:before { color: black; content: "[" attr(id) "] "}
  .subsubreq:before { color: black; content: "[SUBSUBREQ] " }


|
>
>

  /* Style for requirements paragraph. */
  .req       { margin: 1.0em 10ex; }
  .req span  { color: darkblue }

  .subreq    { margin: 1.0em 5ex 1.0em 15ex; color: darkblue }
  .subsubreq { margin: 1.0em 5ex 1.0em 20ex; color: darkblue }

  .req:before { color: black; content: "[" attr(id) "] "}
  .subreq:before { color: black; content: "[" attr(id) "] "}
  .subsubreq:before { color: black; content: "[SUBSUBREQ] " }

Changes to pages/btreemodule.in.

<title>SQLite B-Tree Module</title>
<tcl>

hd_keywords {btree design}
source [file join $::DOC pages fancyformat.tcl]


set fd [open [file join $SRC src btree.h]]
set btree_h [read $fd]
close $fd

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>"
}








fancyformat_document "SQLite B-Tree Module" hlr50000.txt {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

................................................................................

    [h2 "Functional Requirements"]

    <p>
      This section contains requirements describing the functionality required 
      from the B-Tree module.




    [h3 "Opening and Closing Connections"]
  
    <p>
      The B-Tree module provides an interface to open new b-tree database connections.

      [fancyformat_import_requirement H50010]
      [fancyformat_import_requirement H50020]
................................................................................
               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>
................................................................................
      [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?

................................................................................
  <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()).
    <li> Schema memory object allocation (destructor registration).
  </ul>

    [h3 "Fault Tolerance Requirements"]
................................................................................
      SQLite sub-systems to open and close B-Tree database connections.

      [btree_api_defn Btree]

    <p>
      A B-Tree database connection is accessed by other SQLite sub-systems
      using an opaque handle, modelled in C code using the type "Btree*".



      [btree_api_defn sqlite3BtreeOpen] 

      [fancyformat_import_requirement H51001]
      [fancyformat_import_requirement H51002]

      [fancyformat_import_requirement H51003]
................................................................................
      H50050.

      [fancyformat_import_requirement H51007]
      [fancyformat_import_requirement H51008]

    <p class=todo>
      Requirements explaining how the db parameter to sqlite3BtreeOpen is used. Must be there for something.



      [btree_api_defn sqlite3BtreeClose]

      [fancyformat_import_requirement H51009]

    <p>
      If a call to sqlite3BtreeClose is made with a value that is not a valid
................................................................................
      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.

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


















      [btree_api_defn sqlite3BtreeGetMeta]












    [h2 "Modifying the Database Image"]

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

................................................................................
  [h2 "Database Image Traversal and Manipulation"]

     <p class=todo>
       This section should describe exactly how bits and bytes are shifted
       around when the database image is traversed and modified. i.e. how
       a cursor seek is implemented, how the b-tree balancing works, deleting
       an internal cell from an index b-tree etc.













































































  [h2 "Transactions and Savepoints"]

     <p class=todo>
       Requirements surrounding how transactions are made atomic and isolated.
       Also how savepoints are implemented. What happens to active cursors after
       a rollback or savepoint-rollback.







>
|
|
|
|
<

>



>
>
|





|




>
>
>
>
>
>
>







 







>
>
>







 







|

|
>
|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|







 







>
>







 







>
>







 







|
<
<
<







 







<
<
<
<
<
<









>
>
>
>
>
|
>

|
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

<title>SQLite B-Tree Module</title>
<tcl>

hd_keywords {btree design}
source [file join $::DOC pages fancyformat.tcl]

foreach header {btree.h sqliteInt.h} {
  set fd [open [file join $SRC src $header]]
  set headers($header) [read $fd]
  close $fd
}


proc header_api_defn {header args} {
  foreach api $args {

    set re_head {\n[^\n]*}
    if { [string match struct* $api] } {
      set re_tail {[^\{]*\};\n}
    } elseif { [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 $::headers($header) api_defn
    lappend ret [string trim $api_defn]
  }
  return "<pre class=api>[join $ret "\n"]</pre>"
}

proc btree_api_defn {args} {
  eval header_api_defn btree.h $args
}
proc sqliteint_api_defn {args} {
  eval header_api_defn sqliteInt.h $args
}

fancyformat_document "SQLite B-Tree Module" hlr50000.txt {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

................................................................................

    [h2 "Functional Requirements"]

    <p>
      This section contains requirements describing the functionality required 
      from the B-Tree module.

    <p class=todo>
      Figure out where integrity-check goes.

    [h3 "Opening and Closing Connections"]
  
    <p>
      The B-Tree module provides an interface to open new b-tree database connections.

      [fancyformat_import_requirement H50010]
      [fancyformat_import_requirement H50020]
................................................................................
               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>H50153
      [Tr] <td>Safety level
	   <td>The safety-level parameter may be set to "none", "normal" or "full".
               <span class=todo> Where will the effect of this defined/required?</span>
           <td>H50154, H50155
    </table>

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

    <p class=todo>
................................................................................
      [fancyformat_import_requirement H50148]
      [fancyformat_import_requirement H50149]

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

      [fancyformat_import_requirement H50153]

    <p>
      See section <cite>hlr_memory</cite> for a description of and requirements
      specifying how the value of the cache-size parameter affects the
      operation of a page-cache. <span class=todo>Check this reference is
      relevant after it is written. Refer to a specific requirement if possible
      too.</span>

      [fancyformat_import_requirement H50154]
      [fancyformat_import_requirement H50155]

    <p class=todo>
      Description of what the safety-level actually does. Or pointer to where a
      description and requirements can be found (transactions section?).

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

................................................................................
  <ul>
    <li> Callbacks for backup module.
    <li> Page read/write APIs for backup module.
  </ul>

  [h2 "Other Requirements"]

    [h3 "Caching and Memory Management Requirements" hlr_memory]
  <ul>
    <li> Memory allocation related features (pcache, scratch memory, other...).
    <li> Default pcache implementation (sqlite3_release_memory()).
    <li> Schema memory object allocation (destructor registration).
  </ul>

    [h3 "Fault Tolerance Requirements"]
................................................................................
      SQLite sub-systems to open and close B-Tree database connections.

      [btree_api_defn Btree]

    <p>
      A B-Tree database connection is accessed by other SQLite sub-systems
      using an opaque handle, modelled in C code using the type "Btree*".

    [h3 sqlite3BtreeOpen]

      [btree_api_defn sqlite3BtreeOpen] 

      [fancyformat_import_requirement H51001]
      [fancyformat_import_requirement H51002]

      [fancyformat_import_requirement H51003]
................................................................................
      H50050.

      [fancyformat_import_requirement H51007]
      [fancyformat_import_requirement H51008]

    <p class=todo>
      Requirements explaining how the db parameter to sqlite3BtreeOpen is used. Must be there for something.

    [h3 sqlite3BtreeClose]

      [btree_api_defn sqlite3BtreeClose]

      [fancyformat_import_requirement H51009]

    <p>
      If a call to sqlite3BtreeClose is made with a value that is not a valid
................................................................................
      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"]

      [btree_api_defn {typedef struct BtreeMutexArray} {struct BtreeMutexArray \{}]




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







      <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 BtCursor]

      [btree_api_defn sqlite3BtreeCursor sqlite3BtreeCursorSize]
      [btree_api_defn sqlite3BtreeCloseCursor sqlite3BtreeClearCursor]

      [btree_api_defn sqlite3BtreeFirst sqlite3BtreeLast sqlite3BtreeNext \
                      sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \
                      sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

      [btree_api_defn sqlite3BtreeMovetoUnpacked]

      <p class=todo>
	Not clear how to deal with these. Define an external module to
	encapsulate these and define sorting order etc.? That's tricky as things are
	because the UnpackedRecord.flags field defines the "search mode" used
        by sqlite3BtreeMovetoUnpacked.

      [sqliteint_api_defn {typedef struct KeyInfo} {struct KeyInfo \{}]
      [sqliteint_api_defn {typedef struct UnpackedRecord} {struct UnpackedRecord \{}]

    [h3 sqlite3BtreeGetMeta]

      <p>
	The sqlite3BtreeGetMeta interface may be used to retrieve the current
        value of certain fields from the database image header.

      [btree_api_defn sqlite3BtreeGetMeta]

      [fancyformat_import_requirement H51015]

      [btree_api_defn BTREE_FREE_PAGE_COUNT BTREE_SCHEMA_VERSION BTREE_FILE_FORMAT \
                      BTREE_DEFAULT_CACHE_SIZE BTREE_LARGEST_ROOT_PAGE BTREE_TEXT_ENCODING \
                      BTREE_USER_VERSION BTREE_INCR_VACUUM]

      [fancyformat_import_requirement H51016]




    [h2 "Modifying the Database Image"]

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

................................................................................
  [h2 "Database Image Traversal and Manipulation"]

     <p class=todo>
       This section should describe exactly how bits and bytes are shifted
       around when the database image is traversed and modified. i.e. how
       a cursor seek is implemented, how the b-tree balancing works, deleting
       an internal cell from an index b-tree etc.
   
    [h3 "B-Tree Insert"]
    [h3 "B-Tree Delete"]
    [h3 "B-Tree Balancing Algorithm"]


     <ul>
       <li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of
           a b-tree is overfull. It creates a new page and copies the
           entire contents of the overfull root page to it. The root page
           is then zeroed and the new page installed as its only child.
           The balancing algorithm is then run on the new child page (in case
	   it is overfull).

       <li><p>The <b>balance shallower</b> sub-algorithm is used when the root page 
           of a b-tree has only a single child page. If possible, the data from
           the child page is copied into the root-page and the child page discarded.

       <li><p>The <b>balance intkey append</b> sub-algorithm is used in a very specific,
           but common scenario. It is used only for table b-trees, when a new entry that
           has a key value greater than all existing keys in the b-tree is inserted and
           causes the right-most leaf page of the b-tree structure to become overfull.

       <li><p>The <b>balance siblings</b> sub-algorithm is run when a b-tree page that
           is not the root-page of its table is either overfull or underfull.



     </ul>

    [h4 "Balance Deeper"]
      <ol>
        <li> Allocate a new page (the child-page).
        <li> Copy page data from root-page to child-page (including overflow cells).
        <li> Fix pointer map entries associated with new child-page content.
        <li> Zero the root-page.
        <li> Set the right-child pointer of the root-page to point to the new child-page.
        <li> Set the pointer map entry for the new child page.
        <li> Execute the balance procedure on the new child page.
      </ol>

    [h4 "Balance Shallower"]

      <ol>
        <li> Copy page data from child-page to root-page.
        <li> Fix pointer map entries associated with new root-page content.
        <li> Move child-page to database image free-list.
      </ol>

      [Figure btreemodule_balance_shallower.svg figure_balance_shallower "Example Balance Shallower Transform"]

    [h4 "Balance Intkey Append"]

      <ol>
        <li> Allocate a new page (the new sibling-page).

        <li> Populate the new sibling page with the new b-tree entry.

	<li> Add a new divider cell to the parent. The divider cell contains a
             pointer to the page that is currently the right-child of the parent.
             The key in the new divider cell is a copy of the largest key in the
             page that is currently the right-child of the parent.

        <li> Set the right-child of the parent page to point to the new sibling page.

	<li> If the database is an auto-vacuum database, set the pointer map
	     entry associated with the new sibling page. If the cell on the new
             sibling page contains a pointer to an overflow page, set the pointer map
	     entry associated with the overflow page.
      </ol>

    [h4 "Balance Siblings"]


  [h3 "Page Allocation and Deallocation"]


  [h2 "Transactions and Savepoints"]

     <p class=todo>
       Requirements surrounding how transactions are made atomic and isolated.
       Also how savepoints are implemented. What happens to active cursors after
       a rollback or savepoint-rollback.

Changes to pages/fancyformat.tcl.

    return "<tr style=\"background-color:#DDDDDD\">"
  } else {
    return "<tr>"
  }
}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid


  return "<p class=req id=$reqid>[lindex $::ffreq($reqid) 1]</p>"


}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq
  foreach f $lReqfile {








>
>
|
>
>

    return "<tr style=\"background-color:#DDDDDD\">"
  } else {
    return "<tr>"
  }
}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>"
  if {[llength [lindex $::ffreq($reqid) 0]]} {
    append ret " (P: [lindex $::ffreq($reqid) 0])"
  } 
  append ret "</p>"
}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq
  foreach f $lReqfile {

Changes to pages/fileformat.in.

        offset of the cell containing the smallest record on the page,
        according to the comparison function defined in section 
        <cite>index_btree_compare_func</cite>.
      <p>
        As well as the block of unused space between the cell offset array and
        the cell content area, which may be any size, there may be small blocks
        of free space interspersed with the B-Tree cells within the cell
        content area. These are classified into two classes, depending on their         size:

      <ul>
        <li>Blocks of free-space consisting of 3 bytes or less are called
            <b>fragments</b>. The total number of bytes consumed by all
            fragments on a page is stored in the 1 byte unsigned integer at
            byte offset 7 of the page header. The total number of fragmented
            bytes on a single page is never greater than 255.
        <li>Blocks of free-space consisting of more than 3 bytes of contiguous
................................................................................
            unsigned integer. The first two bytes of the final block in the 
            list are set to zero. The third and fourth bytes of each free
            block contain the total size of the free block in bytes, stored
            as a 2 byte big-endian unsigned integer.
      </ul>

      <p class=todo>
        The list of free blocks is kept in order, sorted by offset. Right?



          [fancyformat_import_requirement H30810]
          [fancyformat_import_requirement H30820]

      <p>
        The following requirements describe the <i>B-Tree page header</i>
        present at the start of both index and table B-Tree pages.

        offset of the cell containing the smallest record on the page,
        according to the comparison function defined in section 
        <cite>index_btree_compare_func</cite>.
      <p>
        As well as the block of unused space between the cell offset array and
        the cell content area, which may be any size, there may be small blocks
        of free space interspersed with the B-Tree cells within the cell
        content area. These are classified into two classes, depending on their
        size:
      <ul>
        <li>Blocks of free-space consisting of 3 bytes or less are called
            <b>fragments</b>. The total number of bytes consumed by all
            fragments on a page is stored in the 1 byte unsigned integer at
            byte offset 7 of the page header. The total number of fragmented
            bytes on a single page is never greater than 255.
        <li>Blocks of free-space consisting of more than 3 bytes of contiguous
................................................................................
            unsigned integer. The first two bytes of the final block in the 
            list are set to zero. The third and fourth bytes of each free
            block contain the total size of the free block in bytes, stored
            as a 2 byte big-endian unsigned integer.
      </ul>

      <p class=todo>
	The list of free blocks is kept in order, sorted by offset. Right?
	Later: True statement. SQLite function sqlite3BtreeInitPage() returns
        SQLITE_CORRUPT if they are not.

          [fancyformat_import_requirement H30810]
          [fancyformat_import_requirement H30820]

      <p>
        The following requirements describe the <i>B-Tree page header</i>
        present at the start of both index and table B-Tree pages.

Changes to req/hlr50000.txt.


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.

HLR H51002
If unsuccessful, a call to the sqlite3BtreeOpen function shall return an SQLite
error code other than SQLITE_OK indicating the reason for the failure. The
................................................................................
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).








>
>
>
>

>
>
>
>

>
>
>
>
>
>
|







 








>
>
>
>
>
>
>
>
>
>
>
>


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 H50153
The B-Tree module shall provide an interface to set the value of the
cache-size configuration parameter of a page-cache, given an open b-tree
database connection to that page-cache.

HLR H50154
The B-Tree module shall provide an interface allowing the application to set
the safety-level of a page-cache to one of "off", "normal" or "full",
given an open b-tree database connection to that page-cache.

HLR H50155
The default value assigned to the safety-level configuration parameter of a
page-cache shall be "full".



HLR H51001      H50010
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.

HLR H51002
If unsuccessful, a call to the sqlite3BtreeOpen function shall return an SQLite
error code other than SQLITE_OK indicating the reason for the failure. The
................................................................................
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).



HLR H51015       H50109
If successful, a call to the sqlite3BtreeGetMeta function shall set the
value of *pValue to the current value of the specified 32-bit unsigned 
integer in the database image database header and return SQLITE_OK.

HLR H51016       H50109
The database header field read from the database image by a call to
sqlite3BtreeGetMeta shall be the 32-bit unsigned integer header field stored at
byte offset (36 + 4 * idx) of the database header, where idx is the value of
the second parameter passed to sqlite3BtreeGetMeta.