/ Check-in [624ccbca]
Login

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

Overview
Comment::-) (CVS 215)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:624ccbca98be33a26c2af72d2d91c78f8a06ae9c
User & Date: drh 2001-04-29 23:32:56
Context
2001-05-11
11:02
:-) (CVS 216) check-in: c3e52119 user: drh tags: trunk
2001-04-29
23:32
:-) (CVS 215) check-in: 624ccbca user: drh tags: trunk
2001-04-28
16:52
:-) (CVS 214) check-in: 73a1ed61 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32




























33
34
35
36
37
38
39
..
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
..
83
84
85
86
87
88
89

90
91
92
93
94
95
96
97
98
99
100
101
...
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
...
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
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.2 2001/04/28 16:52:41 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

typedef unsigned int u32;





























/*
** The maximum number of database entries that can be held in a single
** page of the database.  Each entry has a 16-byte header consisting of
** 4 unsigned 32-bit numbers, as follows:
**
**       nKey       Number of byte in the key
**       nData      Number of byte in the data
................................................................................
**       next       index in MemPage.aPage[] of the next entry in sorted order
**
** The key and data follow this header.  The key and data are packed together
** and the total rounded up to the next multiple of 4 bytes.  There must
** be at least 4 bytes in the key/data packet, so each entry consumes at
** least 20 bytes of space on the page.
*/
#define MX_CELL (SQLITE_PAGE_SIZE/20)

/*
** Freeblocks are divided by cells, so there can be at most one more
** free block than there are cells.
*/
#define MX_FREE (MX_CELL+1)

/*
** The maximum amount of data (in bytes) that can be stored locally for a
** database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
*/
#define MX_LOCAL_PAYLOAD ((SQLITE_PAGE_SIZE-20-4*24)/4)
................................................................................
  unsigned char validUp;                    /* True if MemPage.up is valid */
  unsigned char validLeft;                  /* True if MemPage.left is valid */
  unsigned char validRight;                 /* True if MemPage.right is valid */
  Pgno up;                     /* The parent page.  0 means this is the root */
  Pgno left;                   /* Left sibling page.  0==none */
  Pgno right;                  /* Right sibling page.  0==none */
  int idxStart;                /* Index in aPage[] of real data */

  int nCell;                   /* Number of entries on this page */
  u32 *aCell[MX_CELL];         /* All entires in sorted order */
  int nFree;                   /* Number of free blocks on this page */
  int nFreeSlot;               /* Number of free elements of aPage[] */
  FreeBlk aFree[MX_FREE];      /* Free blocks in no particular order */
}
typedef struct MemPage;

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
................................................................................
  BtCursor *pPrev, *pNext;      /* Linked list of all cursors */
  int valid;                    /* True if the cursor points to something */
  int nLevel;                   /* Number of levels of indexing used */
  BtIdxpt *pLevel;              /* Pointer to aLevel[nLevel] */
  BtIdxpt aLevel[MX_LEVEL];     /* The index levels */
};

/*
** The first page contains the following additional information:
**
**      MAGIC-1
**      MAGIC-2
**      First free block
*/
#define EXTRA_PAGE_1_CELLS  3
#define MAGIC_1  0x7264dc61
#define MAGIC_2  0x54e55d9e

/*
** Each database page has a header as follows:
**
**      page1_header          Extra numbers found on page 1 only.
**      leftmost_pgno         Page number of the leftmost child
**      first_cell            Index into MemPage.aPage of first cell
**
** MemPage.pStart always points to the leftmost_pgno.
*/

/*
** Mark a section of the memory block as in-use.
*/
static void useSpace(MemPage *pPage, int start, int size){
  int i;
  FreeBlk *p;

................................................................................
      *p = pPage->aFree[pPage->nFree-1];
      pPage->nFree--;
    }
  }else if( p->idx+p->size==start+size ){
    /* Space at the end of the block */
    p->size -= size;
  }else{
    /* Space in the middle of the freeblock.  We have to split the
    ** freeblock in two */
    /******* TBD *********/



  }
  pPage->nFreeSlot -= size;
}

/*
** Return a section of the MemPage.aPage[] to the freelist.
*/
static void freeSpace(MemPage *pPage, int start, int size){




















}

/*
** Defragment the freespace
*/
static void defragmentSpace(MemPage *pPage){
}







|








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







 







|
<
<
<
<
<
<







 







>


<
<
<







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|
|
|
>
>
>








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







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
..
69
70
71
72
73
74
75
76






77
78
79
80
81
82
83
...
105
106
107
108
109
110
111
112
113
114



115
116
117
118
119
120
121
...
159
160
161
162
163
164
165





















166
167
168
169
170
171
172
...
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
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.3 2001/04/29 23:32:56 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

typedef unsigned int u32;


/*
** The first page contains the following additional information:
**
**      MAGIC-1
**      MAGIC-2
**      First free block
*/
#define EXTRA_PAGE_1_CELLS  3
#define MAGIC_1  0x7264dc61
#define MAGIC_2  0x54e55d9e

/*
** Each database page has a header as follows:
**
**      page1_header          Extra numbers found on page 1 only.
**      leftmost_pgno         Page number of the leftmost child
**      first_cell            Index into MemPage.aPage of first cell
**      first_free            Index of first free block
**
** MemPage.pStart always points to the leftmost_pgno.  First_free is
** 0 if there is no free space on this page.  Otherwise it points to
** an area like this:
**
**      nByte                 Number of free bytes in this block
**      next_free             Next free block or 0 if this is the end
*/

/*
** The maximum number of database entries that can be held in a single
** page of the database.  Each entry has a 16-byte header consisting of
** 4 unsigned 32-bit numbers, as follows:
**
**       nKey       Number of byte in the key
**       nData      Number of byte in the data
................................................................................
**       next       index in MemPage.aPage[] of the next entry in sorted order
**
** The key and data follow this header.  The key and data are packed together
** and the total rounded up to the next multiple of 4 bytes.  There must
** be at least 4 bytes in the key/data packet, so each entry consumes at
** least 20 bytes of space on the page.
*/
#define MX_CELL ((SQLITE_PAGE_SIZE-12)/20)







/*
** The maximum amount of data (in bytes) that can be stored locally for a
** database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
*/
#define MX_LOCAL_PAYLOAD ((SQLITE_PAGE_SIZE-20-4*24)/4)
................................................................................
  unsigned char validUp;                    /* True if MemPage.up is valid */
  unsigned char validLeft;                  /* True if MemPage.left is valid */
  unsigned char validRight;                 /* True if MemPage.right is valid */
  Pgno up;                     /* The parent page.  0 means this is the root */
  Pgno left;                   /* Left sibling page.  0==none */
  Pgno right;                  /* Right sibling page.  0==none */
  int idxStart;                /* Index in aPage[] of real data */
  int nFree;                   /* Number of free elements of aPage[] */
  int nCell;                   /* Number of entries on this page */
  u32 *aCell[MX_CELL];         /* All entires in sorted order */



}
typedef struct MemPage;

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
................................................................................
  BtCursor *pPrev, *pNext;      /* Linked list of all cursors */
  int valid;                    /* True if the cursor points to something */
  int nLevel;                   /* Number of levels of indexing used */
  BtIdxpt *pLevel;              /* Pointer to aLevel[nLevel] */
  BtIdxpt aLevel[MX_LEVEL];     /* The index levels */
};






















/*
** Mark a section of the memory block as in-use.
*/
static void useSpace(MemPage *pPage, int start, int size){
  int i;
  FreeBlk *p;

................................................................................
      *p = pPage->aFree[pPage->nFree-1];
      pPage->nFree--;
    }
  }else if( p->idx+p->size==start+size ){
    /* Space at the end of the block */
    p->size -= size;
  }else{
    /* Space in the middle of the freeblock. */
    FreeBlk *pNew;
    assert( p->nFreeSlot < MX_FREE );
    pNew->idx = start+size;
    pNew->size = p->idx+p->size - pNew->idx;
    p->size = start - p->idx;
  }
  pPage->nFreeSlot -= size;
}

/*
** Return a section of the MemPage.aPage[] to the freelist.
*/
static void freeSpace(MemPage *pPage, int start, int size){
  int end = start+size;
  int i;
  FreeBlk *pMatch = 0;
  FreeBlk *
  for(i=0; i<pPage->nFreeSlot; i++){
    FreeBlk *p = &pPage->aFree[i];
    if( p->idx==end+1 ){
      if( pMatch ){
        
      }else{
        p->idx = start;
        p->size += size;
        pMatch = p;
      }
    }
    if( p->idx+p->size+1==start ){
      p->size += size;
      break;
    }
  }
}

/*
** Defragment the freespace
*/
static void defragmentSpace(MemPage *pPage){
}