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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
b81bc323b954f4e53bb88875d165e259 |
User & Date: | drh 2012-10-20 13:01:32.466 |
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 | */ struct TreeKey { int nKey; /* Size of pKey in bytes */ int nValue; /* Size of pValue. Or negative. */ u8 flags; /* Various LSM_XXX flags */ }; | | | | 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | */ 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... |
︙ | ︙ | |||
331 332 333 334 335 336 337 | assert( p==pNode || rc!=LSM_OK ); } #else # define assertIsWorkingChild(w,x,y,z) #endif /* Values for the third argument to treeShmkey(). */ | | | | | | 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 | 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 ){ |
︙ | ︙ | |||
498 499 500 501 502 503 504 | /* 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 ){ | | | | | | 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 | /* 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 ); lsmStringClear(&s); }else{ for(i=0; i<4 && nHeight>0; i++){ u32 iPtr = getChildPtr(pNode, pDb->treehdr.root.iTransId, i); 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); } } } |
︙ | ︙ | |||
568 569 570 571 572 573 574 | /* ** 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]], | | | 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 | /* ** 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. |
︙ | ︙ | |||
598 599 600 601 602 603 604 | */ static int treeCursorRestore(TreeCursor *pCsr, int *pRes){ int rc = LSM_OK; if( pCsr->pSave ){ TreeKey *pKey = pCsr->pSave; pCsr->pSave = 0; if( pRes ){ | | | 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 | */ 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, |
︙ | ︙ | |||
1476 1477 1478 1479 1480 1481 1482 | goto insert_entry_out; } } if( res==0 && (flags & (LSM_END_DELETE|LSM_START_DELETE)) ){ if( pRes->flags & LSM_INSERT ){ nVal = pRes->nValue; | | | 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 | 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)) |
︙ | ︙ | |||
1840 1841 1842 1843 1844 1845 1846 | 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); | | | | 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 | 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); } |
︙ | ︙ | |||
1932 1933 1934 1935 1936 1937 1938 | 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 ){ | | | 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 | 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 /* |
︙ | ︙ | |||
1986 1987 1988 1989 1990 1991 1992 | 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. */ | | | | 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 | 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; |
︙ | ︙ | |||
2092 2093 2094 2095 2096 2097 2098 | if( iCell<3 && pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[iCell] ) break; } } #ifndef NDEBUG if( pCsr->iNode>=0 ){ TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc); | | | 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 | 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; } |
︙ | ︙ | |||
2160 2161 2162 2163 2164 2165 2166 | }while( (--pCsr->iNode)>=0 ); pCsr->aiCell[pCsr->iNode] = iCell; } #ifndef NDEBUG if( pCsr->iNode>=0 ){ TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc); | | | 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 | }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; } |
︙ | ︙ | |||
2252 2253 2254 2255 2256 2257 2258 | 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; | | | 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 | 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; |
︙ | ︙ | |||
2440 2441 2442 2443 2444 2445 2446 | } tblobFree(csr.pDb, &csr.blob); return nEntry; } #endif | < < | 2440 2441 2442 2443 2444 2445 2446 | } tblobFree(csr.pDb, &csr.blob); return nEntry; } #endif |