Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Change the "TK_" macro prefix in lsm_tree.c to "TKV_" in order to avoid name collisions with "TK_" macros generated by the parser. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
b81bc323b954f4e53bb88875d165e259 |
| User & Date: | drh 2012-10-20 13:01:32 |
Context
|
2012-10-20
| ||
| 13:13 | Rename "storage.c" to "kv.c". Similar renames for test modules. This is to match the rename of "storage.h" to "kv.h" in a prior check-in. check-in: 7d290a04e8 user: drh tags: trunk | |
| 13:01 | Change the "TK_" macro prefix in lsm_tree.c to "TKV_" in order to avoid name collisions with "TK_" macros generated by the parser. check-in: b81bc323b9 user: drh tags: trunk | |
| 12:57 | Change the name of "storage.h" to "kv.h". Other minor edits to comments and typedefs. check-in: 8132a601e8 user: drh tags: trunk | |
Changes
Changes to src/lsm_tree.c.
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 ... 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 ... 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 ... 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 ... 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 ... 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 .... 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 .... 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 .... 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 .... 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 .... 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 .... 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 .... 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 .... 2440 2441 2442 2443 2444 2445 2446 2447 2448 |
*/
struct TreeKey {
int nKey; /* Size of pKey in bytes */
int nValue; /* Size of pValue. Or negative. */
u8 flags; /* Various LSM_XXX flags */
};
#define TK_KEY(p) ((void *)&(p)[1])
#define TK_VAL(p) ((void *)(((u8 *)&(p)[1]) + (p)->nKey))
/*
** A single tree node. A node structure may contain up to 3 key/value
** pairs. Internal (non-leaf) nodes have up to 4 children.
**
** TODO: Update the format of this to be more compact. Get it working
** first though...
................................................................................
assert( p==pNode || rc!=LSM_OK );
}
#else
# define assertIsWorkingChild(w,x,y,z)
#endif
/* Values for the third argument to treeShmkey(). */
#define TK_LOADKEY 1
#define TK_LOADVAL 2
static TreeKey *treeShmkey(
lsm_db *pDb, /* Database handle */
u32 iPtr, /* Shmptr to TreeKey struct */
int eLoad, /* Either zero or a TREEKEY_LOADXXX value */
TreeBlob *pBlob, /* Used if dynamic memory is required */
int *pRc /* IN/OUT: Error code */
){
TreeKey *pRet;
assert( eLoad==TK_LOADKEY || eLoad==TK_LOADVAL );
pRet = (TreeKey *)treeShmptr(pDb, iPtr, pRc);
if( pRet ){
int nReq; /* Bytes of space required at pRet */
int nAvail; /* Bytes of space available at pRet */
nReq = sizeof(TreeKey) + pRet->nKey;
if( eLoad==TK_LOADVAL && pRet->nValue>0 ){
nReq += pRet->nValue;
}
assert( LSM_SHM_CHUNK_SIZE==(1<<15) );
nAvail = LSM_SHM_CHUNK_SIZE - (iPtr & (LSM_SHM_CHUNK_SIZE-1));
if( nAvail<nReq ){
if( tblobGrow(pDb, pBlob, nReq, pRc)==0 ){
................................................................................
/* Append the nIndent bytes of space to string s. */
lsmStringInit(&s, pDb->pEnv);
/* Append each key to string s. */
for(i=0; i<3; i++){
u32 iPtr = pNode->aiKeyPtr[i];
if( iPtr ){
TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc);
strAppendFlags(&s, pKey->flags);
lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey);
lsmStringAppend(&s, " ", -1);
}
}
printf("% 6d %.*sleaf%.*s: %s\n",
iNode, nPath, zPath, 20-nPath-4, zSpace, s.z
);
................................................................................
zPath[nPath] = i+'0';
zPath[nPath+1] = '/';
if( iPtr ){
dump_node_contents(pDb, iPtr, zPath, nPath+2, nHeight-1);
}
if( i!=3 && pNode->aiKeyPtr[i] ){
TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc);
lsmStringInit(&s, pDb->pEnv);
strAppendFlags(&s, pKey->flags);
lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey);
printf("% 6d %.*s%.*s: %s\n",
iNode, nPath+1, zPath, 20-nPath-1, zSpace, s.z);
lsmStringClear(&s);
}
}
}
................................................................................
/*
** Return a pointer to the mapping of the TreeKey object that the cursor
** is pointing to.
*/
static TreeKey *csrGetKey(TreeCursor *pCsr, TreeBlob *pBlob, int *pRc){
TreeKey *pRet = (TreeKey *)treeShmkey(pCsr->pDb,
pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]],
TK_LOADVAL, pBlob, pRc
);
assert( pRet==0 || assertFlagsOk(pRet->flags) );
return pRet;
}
/*
** Save the current position of tree cursor pCsr.
................................................................................
*/
static int treeCursorRestore(TreeCursor *pCsr, int *pRes){
int rc = LSM_OK;
if( pCsr->pSave ){
TreeKey *pKey = pCsr->pSave;
pCsr->pSave = 0;
if( pRes ){
rc = lsmTreeCursorSeek(pCsr, TK_KEY(pKey), pKey->nKey, pRes);
}
}
return rc;
}
/*
** Allocate nByte bytes of space within the *-shm file. If successful,
................................................................................
goto insert_entry_out;
}
}
if( res==0 && (flags & (LSM_END_DELETE|LSM_START_DELETE)) ){
if( pRes->flags & LSM_INSERT ){
nVal = pRes->nValue;
pVal = TK_VAL(pRes);
}
flags = flags | pRes->flags;
}
if( flags & (LSM_INSERT|LSM_POINT_DELETE) ){
if( (res<0 && (pRes->flags & LSM_START_DELETE))
|| (res>0 && (pRes->flags & LSM_END_DELETE))
................................................................................
lsmTreeCursorNext(&csr);
assert( csr.iNode==(p->nHeight-1) );
iKey = csr.apTreeNode[csr.iNode]->aiKeyPtr[csr.aiCell[csr.iNode]];
lsmTreeCursorPrev(&csr);
treeOverwriteKey(db, &csr, iKey, &rc);
pKey = treeShmkey(db, iKey, TK_LOADKEY, &blob, &rc);
if( pKey ){
rc = lsmTreeCursorSeek(&csr, TK_KEY(pKey), pKey->nKey, &res);
}
if( rc==LSM_OK ){
assert( res==0 && csr.iNode==iNode );
rc = lsmTreeCursorNext(&csr);
if( rc==LSM_OK ){
rc = treeDeleteEntry(db, &csr, 0);
}
................................................................................
static int treeCsrCompare(TreeCursor *pCsr, void *pKey, int nKey){
TreeKey *p;
int cmp = 0;
int rc = LSM_OK;
assert( pCsr->iNode>=0 );
p = csrGetKey(pCsr, &pCsr->blob, &rc);
if( p ){
cmp = pCsr->pDb->xCmp(TK_KEY(p), p->nKey, pKey, nKey);
}
return cmp;
}
#endif
/*
................................................................................
pNode = (TreeNode *)treeShmptr(pDb, iNodePtr, &rc);
iNode++;
pCsr->apTreeNode[iNode] = pNode;
/* Compare (pKey/nKey) with the key in the middle slot of B-tree node
** pNode. The middle slot is never empty. If the comparison is a match,
** then the search is finished. Break out of the loop. */
pTreeKey = treeShmkey(pDb, pNode->aiKeyPtr[1], TK_LOADKEY, &b, &rc);
if( rc!=LSM_OK ) break;
res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey);
if( res==0 ){
pCsr->aiCell[iNode] = 1;
break;
}
/* Based on the results of the previous comparison, compare (pKey/nKey)
** to either the left or right key of the B-tree node, if such a key
** exists. */
iTest = (res>0 ? 0 : 2);
pTreeKey = treeShmkey(pDb, pNode->aiKeyPtr[iTest], TK_LOADKEY, &b, &rc);
if( rc ) break;
if( pTreeKey==0 ){
iTest = 1;
}else{
res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey);
if( res==0 ){
pCsr->aiCell[iNode] = iTest;
................................................................................
if( iCell<3 && pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[iCell] ) break;
}
}
#ifndef NDEBUG
if( pCsr->iNode>=0 ){
TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc);
assert( rc || pDb->xCmp(TK_KEY(pK2),pK2->nKey,TK_KEY(pK1),pK1->nKey)>=0 );
}
tblobFree(pDb, &key1);
#endif
return rc;
}
................................................................................
}while( (--pCsr->iNode)>=0 );
pCsr->aiCell[pCsr->iNode] = iCell;
}
#ifndef NDEBUG
if( pCsr->iNode>=0 ){
TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc);
assert( rc || pDb->xCmp(TK_KEY(pK2), pK2->nKey, TK_KEY(pK1), pK1->nKey)<0 );
}
tblobFree(pDb, &key1);
#endif
return rc;
}
................................................................................
rc = treeCursorRestore(pCsr, &res);
if( res==0 ){
TreeKey *pTreeKey = csrGetKey(pCsr, &pCsr->blob, &rc);
if( rc==LSM_OK ){
if( pTreeKey->flags & LSM_INSERT ){
*pnVal = pTreeKey->nValue;
*ppVal = TK_VAL(pTreeKey);
}else{
*ppVal = 0;
*pnVal = -1;
}
}
}else{
*ppVal = 0;
................................................................................
}
tblobFree(csr.pDb, &csr.blob);
return nEntry;
}
#endif
|
| | | | | | | | | | | | | | | | | | | | | < < |
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 ... 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 ... 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 ... 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 ... 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 ... 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 .... 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 .... 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 .... 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 .... 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 .... 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 .... 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 .... 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 .... 2440 2441 2442 2443 2444 2445 2446 |
*/
struct TreeKey {
int nKey; /* Size of pKey in bytes */
int nValue; /* Size of pValue. Or negative. */
u8 flags; /* Various LSM_XXX flags */
};
#define TKV_KEY(p) ((void *)&(p)[1])
#define TKV_VAL(p) ((void *)(((u8 *)&(p)[1]) + (p)->nKey))
/*
** A single tree node. A node structure may contain up to 3 key/value
** pairs. Internal (non-leaf) nodes have up to 4 children.
**
** TODO: Update the format of this to be more compact. Get it working
** first though...
................................................................................
assert( p==pNode || rc!=LSM_OK );
}
#else
# define assertIsWorkingChild(w,x,y,z)
#endif
/* Values for the third argument to treeShmkey(). */
#define TKV_LOADKEY 1
#define TKV_LOADVAL 2
static TreeKey *treeShmkey(
lsm_db *pDb, /* Database handle */
u32 iPtr, /* Shmptr to TreeKey struct */
int eLoad, /* Either zero or a TREEKEY_LOADXXX value */
TreeBlob *pBlob, /* Used if dynamic memory is required */
int *pRc /* IN/OUT: Error code */
){
TreeKey *pRet;
assert( eLoad==TKV_LOADKEY || eLoad==TKV_LOADVAL );
pRet = (TreeKey *)treeShmptr(pDb, iPtr, pRc);
if( pRet ){
int nReq; /* Bytes of space required at pRet */
int nAvail; /* Bytes of space available at pRet */
nReq = sizeof(TreeKey) + pRet->nKey;
if( eLoad==TKV_LOADVAL && pRet->nValue>0 ){
nReq += pRet->nValue;
}
assert( LSM_SHM_CHUNK_SIZE==(1<<15) );
nAvail = LSM_SHM_CHUNK_SIZE - (iPtr & (LSM_SHM_CHUNK_SIZE-1));
if( nAvail<nReq ){
if( tblobGrow(pDb, pBlob, nReq, pRc)==0 ){
................................................................................
/* Append the nIndent bytes of space to string s. */
lsmStringInit(&s, pDb->pEnv);
/* Append each key to string s. */
for(i=0; i<3; i++){
u32 iPtr = pNode->aiKeyPtr[i];
if( iPtr ){
TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i],TKV_LOADKEY, &b,&rc);
strAppendFlags(&s, pKey->flags);
lsmAppendStrBlob(&s, TKV_KEY(pKey), pKey->nKey);
lsmStringAppend(&s, " ", -1);
}
}
printf("% 6d %.*sleaf%.*s: %s\n",
iNode, nPath, zPath, 20-nPath-4, zSpace, s.z
);
................................................................................
zPath[nPath] = i+'0';
zPath[nPath+1] = '/';
if( iPtr ){
dump_node_contents(pDb, iPtr, zPath, nPath+2, nHeight-1);
}
if( i!=3 && pNode->aiKeyPtr[i] ){
TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TKV_LOADKEY,&b,&rc);
lsmStringInit(&s, pDb->pEnv);
strAppendFlags(&s, pKey->flags);
lsmAppendStrBlob(&s, TKV_KEY(pKey), pKey->nKey);
printf("% 6d %.*s%.*s: %s\n",
iNode, nPath+1, zPath, 20-nPath-1, zSpace, s.z);
lsmStringClear(&s);
}
}
}
................................................................................
/*
** Return a pointer to the mapping of the TreeKey object that the cursor
** is pointing to.
*/
static TreeKey *csrGetKey(TreeCursor *pCsr, TreeBlob *pBlob, int *pRc){
TreeKey *pRet = (TreeKey *)treeShmkey(pCsr->pDb,
pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]],
TKV_LOADVAL, pBlob, pRc
);
assert( pRet==0 || assertFlagsOk(pRet->flags) );
return pRet;
}
/*
** Save the current position of tree cursor pCsr.
................................................................................
*/
static int treeCursorRestore(TreeCursor *pCsr, int *pRes){
int rc = LSM_OK;
if( pCsr->pSave ){
TreeKey *pKey = pCsr->pSave;
pCsr->pSave = 0;
if( pRes ){
rc = lsmTreeCursorSeek(pCsr, TKV_KEY(pKey), pKey->nKey, pRes);
}
}
return rc;
}
/*
** Allocate nByte bytes of space within the *-shm file. If successful,
................................................................................
goto insert_entry_out;
}
}
if( res==0 && (flags & (LSM_END_DELETE|LSM_START_DELETE)) ){
if( pRes->flags & LSM_INSERT ){
nVal = pRes->nValue;
pVal = TKV_VAL(pRes);
}
flags = flags | pRes->flags;
}
if( flags & (LSM_INSERT|LSM_POINT_DELETE) ){
if( (res<0 && (pRes->flags & LSM_START_DELETE))
|| (res>0 && (pRes->flags & LSM_END_DELETE))
................................................................................
lsmTreeCursorNext(&csr);
assert( csr.iNode==(p->nHeight-1) );
iKey = csr.apTreeNode[csr.iNode]->aiKeyPtr[csr.aiCell[csr.iNode]];
lsmTreeCursorPrev(&csr);
treeOverwriteKey(db, &csr, iKey, &rc);
pKey = treeShmkey(db, iKey, TKV_LOADKEY, &blob, &rc);
if( pKey ){
rc = lsmTreeCursorSeek(&csr, TKV_KEY(pKey), pKey->nKey, &res);
}
if( rc==LSM_OK ){
assert( res==0 && csr.iNode==iNode );
rc = lsmTreeCursorNext(&csr);
if( rc==LSM_OK ){
rc = treeDeleteEntry(db, &csr, 0);
}
................................................................................
static int treeCsrCompare(TreeCursor *pCsr, void *pKey, int nKey){
TreeKey *p;
int cmp = 0;
int rc = LSM_OK;
assert( pCsr->iNode>=0 );
p = csrGetKey(pCsr, &pCsr->blob, &rc);
if( p ){
cmp = pCsr->pDb->xCmp(TKV_KEY(p), p->nKey, pKey, nKey);
}
return cmp;
}
#endif
/*
................................................................................
pNode = (TreeNode *)treeShmptr(pDb, iNodePtr, &rc);
iNode++;
pCsr->apTreeNode[iNode] = pNode;
/* Compare (pKey/nKey) with the key in the middle slot of B-tree node
** pNode. The middle slot is never empty. If the comparison is a match,
** then the search is finished. Break out of the loop. */
pTreeKey = treeShmkey(pDb, pNode->aiKeyPtr[1], TKV_LOADKEY, &b, &rc);
if( rc!=LSM_OK ) break;
res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey);
if( res==0 ){
pCsr->aiCell[iNode] = 1;
break;
}
/* Based on the results of the previous comparison, compare (pKey/nKey)
** to either the left or right key of the B-tree node, if such a key
** exists. */
iTest = (res>0 ? 0 : 2);
pTreeKey = treeShmkey(pDb, pNode->aiKeyPtr[iTest], TKV_LOADKEY, &b, &rc);
if( rc ) break;
if( pTreeKey==0 ){
iTest = 1;
}else{
res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey);
if( res==0 ){
pCsr->aiCell[iNode] = iTest;
................................................................................
if( iCell<3 && pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[iCell] ) break;
}
}
#ifndef NDEBUG
if( pCsr->iNode>=0 ){
TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc);
assert( rc || pDb->xCmp(TKV_KEY(pK2),pK2->nKey,TKV_KEY(pK1),pK1->nKey)>=0 );
}
tblobFree(pDb, &key1);
#endif
return rc;
}
................................................................................
}while( (--pCsr->iNode)>=0 );
pCsr->aiCell[pCsr->iNode] = iCell;
}
#ifndef NDEBUG
if( pCsr->iNode>=0 ){
TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc);
assert( rc || pDb->xCmp(TKV_KEY(pK2), pK2->nKey, TKV_KEY(pK1), pK1->nKey)<0 );
}
tblobFree(pDb, &key1);
#endif
return rc;
}
................................................................................
rc = treeCursorRestore(pCsr, &res);
if( res==0 ){
TreeKey *pTreeKey = csrGetKey(pCsr, &pCsr->blob, &rc);
if( rc==LSM_OK ){
if( pTreeKey->flags & LSM_INSERT ){
*pnVal = pTreeKey->nValue;
*ppVal = TKV_VAL(pTreeKey);
}else{
*ppVal = 0;
*pnVal = -1;
}
}
}else{
*ppVal = 0;
................................................................................
}
tblobFree(csr.pDb, &csr.blob);
return nEntry;
}
#endif
|