/ Check-in [d4e0933d]
Login

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

Overview
Comment:Optimized varint routines and tests added. (CVS 1380)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d4e0933dc72b66157164610e0b03f339bc535fb9
User & Date: drh 2004-05-14 16:50:06
Context
2004-05-14
19:08
More speed improvements. (CVS 1381) check-in: cf75cac9 user: drh tags: trunk
16:50
Optimized varint routines and tests added. (CVS 1380) check-in: d4e0933d user: drh tags: trunk
15:27
Performance improvements (CVS 1379) check-in: cad47917 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
330
331
332
333
334
335
336
337
338
339

340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.136 2004/05/14 15:27:28 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}

/*
** Read a variable-length integer.  Store the result in *pResult.
** Return the number of bytes in the integer.
*/

static unsigned int getVarint(unsigned char *p, u64 *pResult){
  u64 x = 0;
  int n = 0;
  unsigned char c;
  do{
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }while( (c & 0x80)!=0 );
  *pResult = x;
  return n;
}
static unsigned int getVarint32(unsigned char *p, u32 *pResult){
  u32 x = 0;
  int n = 0;
  unsigned char c;
  do{
    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }while( (c & 0x80)!=0 );
  *pResult = x;
  return n;
}

/*
** Write a variable length integer with value v into p[].  Return
** the number of bytes written.
*/
static unsigned int putVarint(unsigned char *p, u64 v){
  int i, j, n;
  u8 buf[10];
  n = 0;
  do{
    buf[n++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  buf[0] &= 0x7f;
  for(i=0, j=n-1; j>=0; j--, i++){
    p[i] = buf[j];
  }
  return n;
}

/*
** Parse a cell header and fill in the CellInfo structure.
*/
static void parseCell(
  MemPage *pPage,         /* Page containing the cell */
  unsigned char *pCell,   /* The cell */







|







 







|
<

>
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
330
331
332
333
334
335
336
337

338
339
340
341







































342
343
344
345
346
347
348
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.137 2004/05/14 16:50:06 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  p[0] = v>>24;
  p[1] = v>>16;
  p[2] = v>>8;
  p[3] = v;
}

/*
** Routines to read and write variable-length integers.

*/
#define getVarint    sqlite3GetVarint
#define getVarint32  sqlite3GetVarint32
#define putVarint    sqlite3PutVarint








































/*
** Parse a cell header and fill in the CellInfo structure.
*/
static void parseCell(
  MemPage *pPage,         /* Page containing the cell */
  unsigned char *pCell,   /* The cell */

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1285
1286
1287
1288
1289
1290
1291

1292
1293
1294
1295
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.232 2004/05/14 11:00:53 danielk1977 Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "parse.h"
#include <stdio.h>
#include <stdlib.h>
................................................................................
unsigned char *sqlite3utf16to8(const void *pData, int N);
void *sqlite3utf8to16be(const unsigned char *pIn, int N);
void *sqlite3utf8to16le(const unsigned char *pIn, int N);
void sqlite3utf16to16le(void *pData, int N);
void sqlite3utf16to16be(void *pData, int N);
int sqlite3PutVarint(unsigned char *, u64);
int sqlite3GetVarint(const unsigned char *, u64 *);

int sqlite3VarintLen(u64 v);
int sqlite3AddRecordType(Vdbe*, Table*);









|







 







>


<
<
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294


**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.233 2004/05/14 16:50:06 drh Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "parse.h"
#include <stdio.h>
#include <stdlib.h>
................................................................................
unsigned char *sqlite3utf16to8(const void *pData, int N);
void *sqlite3utf8to16be(const unsigned char *pIn, int N);
void *sqlite3utf8to16le(const unsigned char *pIn, int N);
void sqlite3utf16to16le(void *pData, int N);
void sqlite3utf16to16be(void *pData, int N);
int sqlite3PutVarint(unsigned char *, u64);
int sqlite3GetVarint(const unsigned char *, u64 *);
int sqlite3GetVarint32(const unsigned char *, u32 *);
int sqlite3VarintLen(u64 v);
int sqlite3AddRecordType(Vdbe*, Table*);


Changes to src/test3.c.

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
1025
1026
1027
1028
1029
1030
1031
1032

1033
1034
1035
1036
1037
1038
1039
....
1140
1141
1142
1143
1144
1145
1146
























































1147
1148
1149
1150
1151
1152
1153
....
1184
1185
1186
1187
1188
1189
1190

1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.36 2004/05/11 02:10:07 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  int n;
  u32 nData;
  const char *zBuf;
  char zStatic[1000];

  if( argc!=3 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID AMT \"", 0);

    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[2], &n) ) return TCL_ERROR;
  sqlite3BtreeDataSize(pCur, &nData);
  zBuf = sqlite3BtreeDataFetch(pCur, n);
  if( zBuf ){
................................................................................
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  return TCL_OK;
}


























































/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){
  extern int sqlite3_btree_trace;
  static struct {
................................................................................
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_info",        (Tcl_CmdProc*)btree_cursor_info        },
     { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },

  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  Tcl_LinkVar(interp, "btree_trace", (char*)&sqlite3_btree_trace,
     TCL_LINK_INT);
  return TCL_OK;
}







|







 







|
>







 







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







 







>












9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
....
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
....
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
....
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.37 2004/05/14 16:50:06 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  int n;
  u32 nData;
  const char *zBuf;
  char zStatic[1000];

  if( argc!=3 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " ID AMT
\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[2], &n) ) return TCL_ERROR;
  sqlite3BtreeDataSize(pCur, &nData);
  zBuf = sqlite3BtreeDataFetch(pCur, n);
  if( zBuf ){
................................................................................
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  return TCL_OK;
}

/*
** usage:   varint_test  START  MULTIPLIER  COUNT  INCREMENT
**
** This command tests the sqlite3PutVarint() and sqlite3GetVarint()
** routines, both for accuracy and for speed.
**
** An integer is written using PutVarint() and read back with
** GetVarint() and varified to be unchanged.  This repeats COUNT
** times.  The first integer is START*MULTIPLIER.  Each iteration
** increases the integer by INCREMENT.
**
** This command returns nothing if it works.  It returns an error message
** if something goes wrong.
*/
static int btree_varint_test(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  u32 start, mult, count, incr;
  u64 in, out;
  int n1, n2, i;
  unsigned char zBuf[100];
  if( argc!=5 ){
    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
       " START MULTIPLIER COUNT INCREMENT\"", 0);
    return TCL_ERROR;
  }
  if( Tcl_GetInt(interp, argv[1], (int*)&start) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[2], (int*)&mult) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[3], (int*)&count) ) return TCL_ERROR;
  if( Tcl_GetInt(interp, argv[4], (int*)&incr) ) return TCL_ERROR;
  in = start;
  in *= mult;
  for(i=0; i<count; i++){
    n1 = sqlite3PutVarint(zBuf, in);
    if( n1>9 || n1<1 ){
      Tcl_AppendResult(interp, "PutVarint returned value out of range", 0);
      return TCL_ERROR;
    }
    n2 = sqlite3GetVarint(zBuf, &out);
    if( n1!=n2 ){
      Tcl_AppendResult(interp, \
         "GetVarint returned value different from PutVarint", 0);
      return TCL_ERROR;
    }
    if( in!=out ){
      Tcl_AppendResult(interp, \
         "Value read is different from value written", 0);
      return TCL_ERROR;
    }
    in += incr;
  }
  return TCL_OK;
}

/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){
  extern int sqlite3_btree_trace;
  static struct {
................................................................................
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_info",        (Tcl_CmdProc*)btree_cursor_info        },
     { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
     { "btree_varint_test",        (Tcl_CmdProc*)btree_varint_test        },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  Tcl_LinkVar(interp, "btree_trace", (char*)&sqlite3_btree_trace,
     TCL_LINK_INT);
  return TCL_OK;
}

Changes to src/util.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1135
1136
1137
1138
1139
1140
1141









1142


1143
1144
1145
1146
1147
1148



1149
1150
1151




1152




1153





































1154


1155
1156


1157
1158
1159
1160
1161




1162
1163
1164
1165
1166
1167
1168
1169
1170
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.81 2004/05/14 11:00:53 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................
  if( db->pVdbe!=0 ){
    db->magic = SQLITE_MAGIC_ERROR;
    return 1;
  }
  return 0;
}










int sqlite3PutVarint(unsigned char *p, u64 v){


  int i = 0;
  do{
    p[i++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  p[i-1] &= 0x7f;



  return i;
}





int sqlite3GetVarint(const unsigned char *p, u64 *v){




  u64 x = p[0] & 0x7f;





































  int n = 0;


  while( (p[n++]&0x80)!=0 ){
    x |= ((u64)(p[n]&0x7f))<<(n*7);


  }
  *v = x;
  return n;
}





int sqlite3VarintLen(u64 v){
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 );
  return i;
}








|







 







>
>
>
>
>
>
>
>
>

>
>
|

|


|
>
>
>
|


>
>
>
>

>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
|
<
>
>





>
>
>
>








<
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
....
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216

1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.82 2004/05/14 16:50:06 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................
  if( db->pVdbe!=0 ){
    db->magic = SQLITE_MAGIC_ERROR;
    return 1;
  }
  return 0;
}

/*
** Write a 64-bit variable-length integer to memory starting at p[0].
** The length of data write will be between 1 and 9 bytes.  The number
** of bytes written is returned.
**
** A variable-length integer consists of the lower 7 bits of each byte
** for all bytes that have the 8th bit set and one byte with the 8th
** bit clear.
*/
int sqlite3PutVarint(unsigned char *p, u64 v){
  int i, j, n;
  u8 buf[10];
  n = 0;
  do{
    buf[n++] = (v & 0x7f) | 0x80;
    v >>= 7;
  }while( v!=0 );
  buf[0] &= 0x7f;
  for(i=0, j=n-1; j>=0; j--, i++){
    p[i] = buf[j];
  }
  return n;
}

/*
** Read a 64-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint(const unsigned char *p, u64 *v){
  u32 x;
  u64 x64;
  int n;
  unsigned char c;
  c = p[0];
  if( (c & 0x80)==0 ){
    *v = c;
    return 1;
  }
  x = c & 0x7f;
  c = p[1];
  if( (c & 0x80)==0 ){
    *v = (x<<7) | c;
    return 2;
  }
  x = (x<<7) | (c&0x7f);
  c = p[2];
  if( (c & 0x80)==0 ){
    *v = (x<<7) | c;
    return 3;
  }
  x = (x<<7) | (c&0x7f);
  c = p[3];
  if( (c & 0x80)==0 ){
    *v = (x<<7) | c;
    return 4;
  }
  x64 = (x<<7) | (c&0x7f);
  n = 4;
  do{
    c = p[n++];
    x64 = (x64<<7) | (c&0x7f);
  }while( (c & 0x80)!=0 );
  *v = x64;
  return n;
}

/*
** Read a 32-bit variable-length integer from memory starting at p[0].
** Return the number of bytes read.  The value is stored in *v.
*/
int sqlite3GetVarint32(const unsigned char *p, u32 *v){
  int n = 1;
  unsigned char c = p[0];
  u32 x = c & 0x7f;
  while( (c & 0x80)!=0 ){

    c = p[n++];
    x = (x<<7) | (c & 0x7f);
  }
  *v = x;
  return n;
}

/*
** Return the number of bytes that will be needed to store the given
** 64-bit integer.
*/
int sqlite3VarintLen(u64 v){
  int i = 0;
  do{
    i++;
    v >>= 7;
  }while( v!=0 );
  return i;
}

Changes to test/btree.test.

7
8
9
10
11
12
13
14
15
16
17
18















19
20
21
22
23
24
25
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.23 2004/05/09 11:51:40 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl
















# Basic functionality.  Open and close a database.
#
do_test btree-1.1 {
  file delete -force test1.bt
  file delete -force test1.bt-journal
  set rc [catch {btree_open test1.bt 2000 0} ::b1]







|




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







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
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.24 2004/05/14 16:50:07 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Testing of varint reading writing.
#
do_test btree-0.1 {
  btree_varint_test 0 0 500 1
} {}
do_test btree-0.2 {
  btree_varint_test 1024 1 500 1
} {}
do_test btree-0.3 {
  btree_varint_test -1 1 500 1
} {}
do_test btree-0.4 {
  btree_varint_test -1 100000 500 1
} {}

# Basic functionality.  Open and close a database.
#
do_test btree-1.1 {
  file delete -force test1.bt
  file delete -force test1.bt-journal
  set rc [catch {btree_open test1.bt 2000 0} ::b1]