Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Various speed enhancements. (CVS 1498) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
a0db15bba64af0c529d5be366659bca1 |
User & Date: | drh 2004-05-30 20:46:09.000 |
Context
2004-05-30
| ||
21:14 | Add 3-byte and 6-byte integer serial types. This makes databases smaller and faster. Should we go ahead and add 5- and 7-byte integer types too? (CVS 1499) (check-in: e6685af815 user: drh tags: trunk) | |
20:46 | Various speed enhancements. (CVS 1498) (check-in: a0db15bba6 user: drh tags: trunk) | |
19:19 | Improved comments and speed tweaks to btree.c. (CVS 1497) (check-in: c86b7c065a user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** 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. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** 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.152 2004/05/30 20:46:09 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. |
︙ | ︙ | |||
1731 1732 1733 1734 1735 1736 1737 | return getPayload(pCur, offset, amt, pBuf, 1); } /* ** Return a pointer to payload information from the entry that the ** pCur cursor is pointing to. The pointer is to the beginning of ** the key if skipKey==0 and it points to the beginning of data if | | < < | | | | 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 | return getPayload(pCur, offset, amt, pBuf, 1); } /* ** Return a pointer to payload information from the entry that the ** pCur cursor is pointing to. The pointer is to the beginning of ** the key if skipKey==0 and it points to the beginning of data if ** skipKey==1. The number of bytes of available key/data is written ** into *pAmt. If *pAmt==0, then the value returned will not be ** a valid pointer. ** ** This routine is an optimization. It is common for the entire key ** and data to fit on the local page and for there to be no overflow ** pages. When that is so, this routine can be used to access the ** key and data without making a copy. If the key and/or data spills ** onto overflow pages, then getPayload() must be used to reassembly ** the key/data and copy it into a preallocated buffer. ** ** The pointer returned by this routine looks directly into the cached ** page of the database. The data might change or move the next time ** any btree routine is called. */ static const unsigned char *fetchPayload( BtCursor *pCur, /* Cursor pointing to entry to read from */ int *pAmt, /* Write the number of available bytes here */ int skipKey /* read beginning at data if this is true */ ){ unsigned char *aPayload; MemPage *pPage; Btree *pBt; u32 nKey; int nLocal; |
︙ | ︙ | |||
1776 1777 1778 1779 1780 1781 1782 | nKey = 0; }else{ nKey = pCur->info.nKey; } if( skipKey ){ aPayload += nKey; nLocal = pCur->info.nLocal - nKey; | < < > | < | < < > < | < < < < | > < < < | | | | | 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 | nKey = 0; }else{ nKey = pCur->info.nKey; } if( skipKey ){ aPayload += nKey; nLocal = pCur->info.nLocal - nKey; }else{ nLocal = pCur->info.nLocal; if( nLocal>nKey ){ nLocal = nKey; } } *pAmt = nLocal; return aPayload; } /* ** For the entry that cursor pCur is point to, return as ** many bytes of the key or data as are available on the local ** b-tree page. Write the number of available bytes into *pAmt. ** ** The pointer returned is ephemeral. The key/data may move ** or be destroyed on the next call to any Btree routine. ** ** These routines is used to get quick access to key and data ** in the common case where no overflow pages are used. */ const void *sqlite3BtreeKeyFetch(BtCursor *pCur, int *pAmt){ return (const void*)fetchPayload(pCur, pAmt, 0); } const void *sqlite3BtreeDataFetch(BtCursor *pCur, int *pAmt){ return (const void*)fetchPayload(pCur, pAmt, 1); } /* ** Move the cursor down to a new child page. The newPgno argument is the ** page number of the child page to move to. */ |
︙ | ︙ | |||
2073 2074 2075 2076 2077 2078 2079 | if( nCellKey<nKey ){ c = -1; }else if( nCellKey>nKey ){ c = +1; }else{ c = 0; } | > > | > | | | | | | | | > | 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 | if( nCellKey<nKey ){ c = -1; }else if( nCellKey>nKey ){ c = +1; }else{ c = 0; } }else{ int available; pCellKey = fetchPayload(pCur, &available, 0); if( available>=nCellKey ){ c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); }else{ pCellKey = sqliteMallocRaw( nCellKey ); if( pCellKey==0 ) return SQLITE_NOMEM; rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey); c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); sqliteFree(pCellKey); if( rc ) return rc; } } if( c==0 ){ if( pPage->leafData && !pPage->leaf ){ lwr = pCur->idx; upr = lwr - 1; break; }else{ |
︙ | ︙ |
Changes to src/btree.h.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. See comments in the source code for a detailed description ** of what each interface routine does. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. See comments in the source code for a detailed description ** of what each interface routine does. ** ** @(#) $Id: btree.h,v 1.49 2004/05/30 20:46:09 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* TODO: This definition is just included so other modules compile. It ** needs to be revisited. */ |
︙ | ︙ | |||
88 89 90 91 92 93 94 | int sqlite3BtreeLast(BtCursor*, int *pRes); int sqlite3BtreeNext(BtCursor*, int *pRes); int sqlite3BtreeEof(BtCursor*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePrevious(BtCursor*, int *pRes); int sqlite3BtreeKeySize(BtCursor*, i64 *pSize); int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*); | | | | 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | int sqlite3BtreeLast(BtCursor*, int *pRes); int sqlite3BtreeNext(BtCursor*, int *pRes); int sqlite3BtreeEof(BtCursor*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePrevious(BtCursor*, int *pRes); int sqlite3BtreeKeySize(BtCursor*, i64 *pSize); int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*); const void *sqlite3BtreeKeyFetch(BtCursor*, int *pAmt); const void *sqlite3BtreeDataFetch(BtCursor*, int *pAmt); int sqlite3BtreeDataSize(BtCursor*, u32 *pSize); int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); struct Pager *sqlite3BtreePager(Btree*); |
︙ | ︙ |
Changes to src/test3.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** 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. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** 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.39 2004/05/30 20:46:09 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 | void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ BtCursor *pCur; int n; u64 nKey; 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; sqlite3BtreeKeySize(pCur, &nKey); | > | | | 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 | void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ BtCursor *pCur; int n; int amt; u64 nKey; 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; sqlite3BtreeKeySize(pCur, &nKey); zBuf = sqlite3BtreeKeyFetch(pCur, &amt); if( zBuf && amt>=n ){ assert( nKey<sizeof(zStatic) ); if( n>0 ) nKey = n; memcpy(zStatic, zBuf, (int)nKey); zStatic[nKey] = 0; Tcl_AppendResult(interp, zStatic, 0); } return TCL_OK; |
︙ | ︙ | |||
1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 | void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ BtCursor *pCur; int n; u32 nData; const char *zBuf; char zStatic[1000]; if( argc!=3 ){ Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0], | > | < | | | 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 | void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ BtCursor *pCur; int n; int amt; 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, &amt); if( zBuf && amt>=n ){ assert( nData<sizeof(zStatic) ); if( n>0 ) nData = n; memcpy(zStatic, zBuf, (int)nData); zStatic[nData] = 0; Tcl_AppendResult(interp, zStatic, 0); } return TCL_OK; |
︙ | ︙ |
Changes to src/util.c.
︙ | ︙ | |||
10 11 12 13 14 15 16 | ** ************************************************************************* ** Utility functions used throughout sqlite. ** ** This file contains functions for allocating memory, comparing ** strings, and stuff like that. ** | | | 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | ** ************************************************************************* ** Utility functions used throughout sqlite. ** ** This file contains functions for allocating memory, comparing ** strings, and stuff like that. ** ** $Id: util.c,v 1.95 2004/05/30 20:46:09 drh Exp $ */ #include "sqliteInt.h" #include <stdarg.h> #include <ctype.h> /* ** If malloc() ever fails, this global variable gets set to 1. |
︙ | ︙ | |||
1229 1230 1231 1232 1233 1234 1235 | ** 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; | < | < | < | < | | 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 | ** 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; if( ((c = p[0]) & 0x80)==0 ){ *v = c; return 1; } x = c & 0x7f; if( ((c = p[1]) & 0x80)==0 ){ *v = (x<<7) | c; return 2; } x = (x<<7) | (c&0x7f); if( ((c = p[2]) & 0x80)==0 ){ *v = (x<<7) | c; return 3; } x = (x<<7) | (c&0x7f); if( ((c = p[3]) & 0x80)==0 ){ *v = (x<<7) | c; return 4; } x64 = (x<<7) | (c&0x7f); n = 4; do{ c = p[n++]; |
︙ | ︙ | |||
1271 1272 1273 1274 1275 1276 1277 | } /* ** 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){ | > | | > > > > | | > > > > | > > > | > > > > > > > | 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 | } /* ** 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){ u32 x; int n; unsigned char c; if( ((c = p[0]) & 0x80)==0 ){ *v = c; return 1; } x = c & 0x7f; if( ((c = p[1]) & 0x80)==0 ){ *v = (x<<7) | c; return 2; } x = (x<<7) | (c&0x7f); if( ((c = p[2]) & 0x80)==0 ){ *v = (x<<7) | c; return 3; } x = (x<<7) | (c&0x7f); if( ((c = p[3]) & 0x80)==0 ){ *v = (x<<7) | c; return 4; } n = 4; do{ x = (x<<7) | ((c = p[n++])&0x7f); }while( (c & 0x80)!=0 && n<9 ); *v = x; return n; } /* ** Return the number of bytes that will be needed to store the given ** 64-bit integer. |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
39 40 41 42 43 44 45 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** | | | 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** ** $Id: vdbe.c,v 1.349 2004/05/30 20:46:09 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include <ctype.h> #include "vdbeInt.h" /* |
︙ | ︙ | |||
1527 1528 1529 1530 1531 1532 1533 | pTos++; pTos->flags = MEM_Null; } break; } affinity = (pOp->p1>>8)&0xFF; | | | | > | 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 | pTos++; pTos->flags = MEM_Null; } break; } affinity = (pOp->p1>>8)&0xFF; if( affinity ){ applyAffinity(pNos, affinity, db->enc); applyAffinity(pTos, affinity, db->enc); } assert( pOp->p3type==P3_COLLSEQ || pOp->p3==0 ); res = sqlite3MemCompare(pNos, pTos, (CollSeq*)pOp->p3); switch( pOp->opcode ){ case OP_Eq: res = res==0; break; case OP_Ne: res = res!=0; break; case OP_Lt: res = res<0; break; |
︙ | ︙ | |||
1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 | /* Read and parse the table header. Store the results of the parse ** into the record header cache fields of the cursor. */ if( pC && pC->cacheValid ){ aType = pC->aType; aOffset = pC->aOffset; }else{ if( pC && pC->aType ){ aType = pC->aType; }else{ aType = sqliteMallocRaw( 2*nField*sizeof(aType) ); } aOffset = &aType[nField]; if( aType==0 ){ goto no_mem; } /* Figure out how many bytes are in the header */ if( zRec ){ zData = zRec; }else{ | > < | | | | 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 | /* Read and parse the table header. Store the results of the parse ** into the record header cache fields of the cursor. */ if( pC && pC->cacheValid ){ aType = pC->aType; aOffset = pC->aOffset; }else{ int avail; /* Number of bytes of available data */ if( pC && pC->aType ){ aType = pC->aType; }else{ aType = sqliteMallocRaw( 2*nField*sizeof(aType) ); } aOffset = &aType[nField]; if( aType==0 ){ goto no_mem; } /* Figure out how many bytes are in the header */ if( zRec ){ zData = zRec; }else{ if( pC->keyAsData ){ zData = (char*)sqlite3BtreeKeyFetch(pCrsr, &avail); }else{ zData = (char*)sqlite3BtreeDataFetch(pCrsr, &avail); } } idx = sqlite3GetVarint32(zData, &szHdr); /* Get the complete header text */ if( !zRec && avail<idx ){ rc = sqlite3VdbeMemFromBtree(pCrsr, 0, szHdr, pC->keyAsData, &sMem); if( rc!=SQLITE_OK ){ goto abort_due_to_error; } zData = sMem.z; } |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
1225 1226 1227 1228 1229 1230 1231 | ){ int len; len = sqlite3VdbeSerialTypeLen(serial_type); assert( serial_type!=0 ); if( serial_type<=5 ){ /* Integer and Real */ | > > > > > > > > > > > > > > > | | | | | | | | | | | | | | > | 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 | ){ int len; len = sqlite3VdbeSerialTypeLen(serial_type); assert( serial_type!=0 ); if( serial_type<=5 ){ /* Integer and Real */ if( serial_type<=3 ){ /* 32-bit integer type. This is handled by a special case for ** performance reasons. */ int v = buf[0]; int n; if( v&0x80 ){ v |= -256; } for(n=1; n<len; n++){ v = (v<<8) | buf[n]; } pMem->flags = MEM_Int; pMem->i = v; return n; }else{ u64 v = 0; int n; if( buf[0]&0x80 ){ v = -1; } for(n=0; n<len; n++){ v = (v<<8) | buf[n]; } if( serial_type==5 ){ pMem->flags = MEM_Real; pMem->r = *(double*)&v; }else{ pMem->flags = MEM_Int; pMem->i = *(i64*)&v; } } }else if( serial_type>=12 ){ /* String or blob */ pMem->z = (char *)buf; pMem->n = len; if( serial_type&0x01 ){ pMem->flags = MEM_Str | MEM_Ephem; |
︙ | ︙ |
Changes to src/vdbemem.c.
︙ | ︙ | |||
460 461 462 463 464 465 466 | int sqlite3VdbeMemFromBtree( BtCursor *pCur, /* Cursor pointing at record to retrieve. */ int offset, /* Offset from the start of data to return bytes from. */ int amt, /* Number of bytes to return. */ int key, /* If true, retrieve from the btree key, not data. */ Mem *pMem /* OUT: Return data in this Mem structure. */ ){ | | > | | | | 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 | int sqlite3VdbeMemFromBtree( BtCursor *pCur, /* Cursor pointing at record to retrieve. */ int offset, /* Offset from the start of data to return bytes from. */ int amt, /* Number of bytes to return. */ int key, /* If true, retrieve from the btree key, not data. */ Mem *pMem /* OUT: Return data in this Mem structure. */ ){ char *zData; /* Data from the btree layer */ int available; /* Number of bytes available on the local btree page */ if( key ){ zData = (char *)sqlite3BtreeKeyFetch(pCur, &available); }else{ zData = (char *)sqlite3BtreeDataFetch(pCur, &available); } pMem->n = amt; if( offset+amt<=available ){ pMem->z = &zData[offset]; pMem->flags = MEM_Blob|MEM_Ephem; }else{ int rc; if( amt>NBFS-2 ){ zData = (char *)sqliteMallocRaw(amt+2); if( !zData ){ |
︙ | ︙ |