Documentation Source Text

Check-in [2b4a307362]
Login
Home Timeline Branches Tickets Wiki More...

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

Overview
Comment:Progress on btreemodule.html.
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. 











































































































































































































































































































































































































































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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
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

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

1
2


3
4
5
6
7
8
9

  /* 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] " }



|
>
>








1
2
3
4
5
6
7
8
9
10
11

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

1
2
3
4
5
6

7
8
9
10
11
12

13
14
15


16
17
18
19
20
21
22
23
24
25
26







27
28
29
30
31
32
33
...
141
142
143
144
145
146
147



148
149
150
151
152
153
154
...
400
401
402
403
404
405
406
407
408
409

410
411
412
413
414
415
416
417
...
434
435
436
437
438
439
440
















441
442
443
444
445
446
447
...
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
...
546
547
548
549
550
551
552


553
554
555
556
557
558
559
...
592
593
594
595
596
597
598


599
600
601
602
603
604
605
...
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
...
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693





694

695
696

697
698
699

















700











701
702
703
704
705
706
707
...
767
768
769
770
771
772
773












































































774
775
776
777
778
779
780

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







>
|
|
|
|
<

>



>
>
|





|




>
>
>
>
>
>
>







 







>
>
>







 







|

|
>
|







 







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







 







|







 







>
>







 







>
>







 







|
<
<
<







 







<
<
<
<
<
<









>
>
>
>
>
|
>

|
>



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

>
>
>
>
>
>
>
>
>
>
>







 







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








1
2
3
4
5
6
7
8
9
10
11

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
...
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
...
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
...
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
...
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
...
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
...
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
...
688
689
690
691
692
693
694
695



696
697
698
699
700
701
702
...
703
704
705
706
707
708
709






710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
...
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916

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

130
131
132
133
134
135
136


137


138
139
140
141
142
143
144

    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 {








>
>
|
>
>








130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

    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. 

1365
1366
1367
1368
1369
1370
1371
1372

1373
1374
1375
1376
1377
1378
1379
....
1387
1388
1389
1390
1391
1392
1393
1394


1395
1396
1397
1398
1399
1400
1401

        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.








|
>







 







|
>
>








1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
....
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404

        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. 

288
289
290
291
292
293
294




295




296






297
298
299
300
301
302
303
304
...
378
379
380
381
382
383
384
385














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























>
>
>
>

>
>
>
>

>
>
>
>
>
>
|







 








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

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
...
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411


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.

This page was generated in about 0.01s by Fossil 2.9 [82ad5914f1] 2019-03-24 18:56:57