DBD-SQLite2
view release on metacpan or search on metacpan
* During each transaction (or checkpoint), a linked-list of
* "rollback-operations" is accumulated. If the transaction is rolled back,
* then the list of operations must be executed (to restore the database to
* it's state before the transaction started). If the transaction is to be
* committed, just delete the list.
*
* Each operation is represented as follows, depending on the value of eOp:
*
* ROLLBACK_INSERT -> Need to insert (pKey, pData) into table iTab.
* ROLLBACK_DELETE -> Need to delete the record (pKey) into table iTab.
* ROLLBACK_CREATE -> Need to create table iTab.
* ROLLBACK_DROP -> Need to drop table iTab.
*/
struct BtRollbackOp {
u8 eOp;
int iTab;
int nKey;
void *pKey;
int nData;
void *pData;
BtRollbackOp *pNext;
};
/*
** Legal values for BtRollbackOp.eOp:
*/
#define ROLLBACK_INSERT 1 /* Insert a record */
#define ROLLBACK_DELETE 2 /* Delete a record */
#define ROLLBACK_CREATE 3 /* Create a table */
#define ROLLBACK_DROP 4 /* Drop a table */
struct Rbtree {
BtOps *pOps; /* Function table */
int aMetaData[SQLITE_N_BTREE_META];
int next_idx; /* next available table index */
Hash tblHash; /* All created tables, by index */
u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */
u8 eTransState; /* State of this Rbtree wrt transactions */
BtRollbackOp *pTransRollback;
BtRollbackOp *pCheckRollback;
BtRollbackOp *pCheckRollbackTail;
};
/*
** Legal values for Rbtree.eTransState.
*/
#define TRANS_NONE 0 /* No transaction is in progress */
#define TRANS_INTRANSACTION 1 /* A transaction is in progress */
#define TRANS_INCHECKPOINT 2 /* A checkpoint is in progress */
#define TRANS_ROLLBACK 3 /* We are currently rolling back a checkpoint or
* transaction. */
struct RbtCursor {
BtCursorOps *pOps; /* Function table */
Rbtree *pRbtree;
BtRbTree *pTree;
int iTree; /* Index of pTree in pRbtree */
BtRbNode *pNode;
RbtCursor *pShared; /* List of all cursors on the same Rbtree */
u8 eSkip; /* Determines if next step operation is a no-op */
u8 wrFlag; /* True if this cursor is open for writing */
};
/*
** Legal values for RbtCursor.eSkip.
*/
#define SKIP_NONE 0 /* Always step the cursor */
#define SKIP_NEXT 1 /* The next sqliteRbtreeNext() is a no-op */
#define SKIP_PREV 2 /* The next sqliteRbtreePrevious() is a no-op */
#define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */
struct BtRbTree {
RbtCursor *pCursors; /* All cursors pointing to this tree */
BtRbNode *pHead; /* Head of the tree, or NULL */
};
struct BtRbNode {
int nKey;
void *pKey;
int nData;
void *pData;
u8 isBlack; /* true for a black node, 0 for a red node */
BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
BtRbNode *pLeft; /* Nodes left child, or NULL */
BtRbNode *pRight; /* Nodes right child, or NULL */
int nBlackHeight; /* Only used during the red-black integrity check */
};
/* Forward declarations */
static int memRbtreeMoveto(
RbtCursor* pCur,
const void *pKey,
int nKey,
int *pRes
);
static int memRbtreeClearTable(Rbtree* tree, int n);
static int memRbtreeNext(RbtCursor* pCur, int *pRes);
static int memRbtreeLast(RbtCursor* pCur, int *pRes);
static int memRbtreePrevious(RbtCursor* pCur, int *pRes);
/*
** This routine checks all cursors that point to the same table
** as pCur points to. If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED. If all
** cursors point to the same table were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock
** means a cursor opened with wrFlag==0) this routine also NULLs
** out the pNode field of all other cursors.
** This is necessary because an insert
** or delete might change erase the node out from under
** another cursor.
*/
static int checkReadLocks(RbtCursor *pCur){
RbtCursor *p;
assert( pCur->wrFlag );
for(p=pCur->pTree->pCursors; p; p=p->pShared){
if( p!=pCur ){
if( p->wrFlag==0 ) return SQLITE_LOCKED;
p->pNode = 0;
}
}
return SQLITE_OK;
}
/*
* The key-compare function for the red-black trees. Returns as follows:
*
* (key1 < key2) -1
* (key1 == key2) 0
* (key1 > key2) 1
*
* Keys are compared using memcmp(). If one key is an exact prefix of the
* other, then the shorter key is less than the longer key.
*/
static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
{
int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
if( mcmp == 0){
if( nKey1 == nKey2 ) return 0;
return ((nKey1 < nKey2)?-1:1);
}
return ((mcmp>0)?1:-1);
}
/*
* Perform the LEFT-rotate transformation on node X of tree pTree. This
* transform is part of the red-black balancing code.
*
* | |
* X Y
* / \ / \
* a Y X c
* / \ / \
* b c a b
*
* BEFORE AFTER
*/
static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
{
BtRbNode *pY;
BtRbNode *pb;
pY = pX->pRight;
pb = pY->pLeft;
pY->pParent = pX->pParent;
if( pX->pParent ){
if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
else pX->pParent->pRight = pY;
}
pY->pLeft = pX;
pX->pParent = pY;
btreeCreateTable(tree, *n);
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
/* Set up the rollback structure (if we are not doing this as part of a
* rollback) */
if( tree->eTransState != TRANS_ROLLBACK ){
BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->eOp = ROLLBACK_DROP;
pRollbackOp->iTab = *n;
btreeLogRollbackOp(tree, pRollbackOp);
}
return SQLITE_OK;
}
/*
* Delete table n from the supplied Rbtree.
*/
static int memRbtreeDropTable(Rbtree* tree, int n)
{
BtRbTree *pTree;
assert( tree->eTransState != TRANS_NONE );
memRbtreeClearTable(tree, n);
pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
assert(pTree);
assert( pTree->pCursors==0 );
sqliteFree(pTree);
if( tree->eTransState != TRANS_ROLLBACK ){
BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->eOp = ROLLBACK_CREATE;
pRollbackOp->iTab = n;
btreeLogRollbackOp(tree, pRollbackOp);
}
return SQLITE_OK;
}
static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
int nIgnore, int *pRes)
{
assert(pCur);
if( !pCur->pNode ) {
*pRes = -1;
} else {
if( (pCur->pNode->nKey - nIgnore) < 0 ){
*pRes = -1;
}else{
*pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore,
pKey, nKey);
}
}
return SQLITE_OK;
}
/*
* Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
* parameter indicates that the cursor is open for writing.
*
* Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
*/
static int memRbtreeCursor(
Rbtree* tree,
int iTable,
int wrFlag,
RbtCursor **ppCur
){
RbtCursor *pCur;
assert(tree);
pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
pCur->pTree = sqliteHashFind(&tree->tblHash, 0, iTable);
assert( pCur->pTree );
pCur->pRbtree = tree;
pCur->iTree = iTable;
pCur->pOps = &sqliteRbtreeCursorOps;
pCur->wrFlag = wrFlag;
pCur->pShared = pCur->pTree->pCursors;
pCur->pTree->pCursors = pCur;
assert( (*ppCur)->pTree );
return SQLITE_OK;
}
/*
* Insert a new record into the Rbtree. The key is given by (pKey,nKey)
* and the data is given by (pData,nData). The cursor is used only to
* define what database the record should be inserted into. The cursor
* is left pointing at the new record.
*
* If the key exists already in the tree, just replace the data.
*/
static int memRbtreeInsert(
RbtCursor* pCur,
const void *pKey,
int nKey,
const void *pDataInput,
int nData
){
void * pData;
int match;
/* It is illegal to call sqliteRbtreeInsert() if we are
** not in a transaction */
assert( pCur->pRbtree->eTransState != TRANS_NONE );
/* Make sure some other cursor isn't trying to read this same table */
if( checkReadLocks(pCur) ){
return SQLITE_LOCKED; /* The table pCur points to has a read lock */
}
/* Take a copy of the input data now, in case we need it for the
* replace case */
pData = sqliteMallocRaw(nData);
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
memcpy(pData, pDataInput, nData);
/* Move the cursor to a node near the key to be inserted. If the key already
* exists in the table, then (match == 0). In this case we can just replace
* the data associated with the entry, we don't need to manipulate the tree.
*
* If there is no exact match, then the cursor points at what would be either
* the predecessor (match == -1) or successor (match == 1) of the
* searched-for key, were it to be inserted. The new node becomes a child of
* this node.
*
* The new node is initially red.
*/
memRbtreeMoveto( pCur, pKey, nKey, &match);
if( match ){
BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
if( pNode==0 ) return SQLITE_NOMEM;
pNode->nKey = nKey;
pNode->pKey = sqliteMallocRaw(nKey);
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
memcpy(pNode->pKey, pKey, nKey);
pNode->nData = nData;
pNode->pData = pData;
if( pCur->pNode ){
switch( match ){
case -1:
assert( !pCur->pNode->pRight );
pNode->pParent = pCur->pNode;
pCur->pNode->pRight = pNode;
break;
case 1:
assert( !pCur->pNode->pLeft );
pNode->pParent = pCur->pNode;
pCur->pNode->pLeft = pNode;
break;
default:
assert(0);
}
}else{
pCur->pTree->pHead = pNode;
}
/* Point the cursor at the node just inserted, as per SQLite requirements */
pCur->pNode = pNode;
/* A new node has just been inserted, so run the balancing code */
do_insert_balancing(pCur->pTree, pNode);
/* Set up a rollback-op in case we have to roll this operation back */
if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
if( pOp==0 ) return SQLITE_NOMEM;
pOp->eOp = ROLLBACK_DELETE;
pOp->iTab = pCur->iTree;
pOp->nKey = pNode->nKey;
pOp->pKey = sqliteMallocRaw( pOp->nKey );
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
btreeLogRollbackOp(pCur->pRbtree, pOp);
}
}else{
/* No need to insert a new node in the tree, as the key already exists.
* Just clobber the current nodes data. */
/* Set up a rollback-op in case we have to roll this operation back */
if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
if( pOp==0 ) return SQLITE_NOMEM;
pOp->iTab = pCur->iTree;
pOp->nKey = pCur->pNode->nKey;
pOp->pKey = sqliteMallocRaw( pOp->nKey );
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
pOp->nData = pCur->pNode->nData;
pOp->pData = pCur->pNode->pData;
pOp->eOp = ROLLBACK_INSERT;
btreeLogRollbackOp(pCur->pRbtree, pOp);
}else{
sqliteFree( pCur->pNode->pData );
}
/* Actually clobber the nodes data */
pCur->pNode->pData = pData;
pCur->pNode->nData = nData;
}
return SQLITE_OK;
}
/* Move the cursor so that it points to an entry near pKey.
** Return a success code.
**
** *pRes<0 The cursor is left pointing at an entry that
** is smaller than pKey or if the table is empty
** and the cursor is therefore left point to nothing.
**
** *pRes==0 The cursor is left pointing at an entry that
** exactly matches pKey.
**
** *pRes>0 The cursor is left pointing at an entry that
** is larger than pKey.
*/
static int memRbtreeMoveto(
RbtCursor* pCur,
const void *pKey,
int nKey,
int *pRes
){
BtRbNode *pTmp = 0;
pCur->pNode = pCur->pTree->pHead;
*pRes = -1;
while( pCur->pNode && *pRes ) {
*pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
pTmp = pCur->pNode;
switch( *pRes ){
case 1: /* cursor > key */
pCur->pNode = pCur->pNode->pLeft;
break;
case -1: /* cursor < key */
pCur->pNode = pCur->pNode->pRight;
break;
}
}
/* If (pCur->pNode == NULL), then we have failed to find a match. Set
* pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
* last node traversed in the search. In either case the relation ship
* between pTmp and the searched for key is already stored in *pRes. pTmp is
* either the successor or predecessor of the key we tried to move to. */
if( !pCur->pNode ) pCur->pNode = pTmp;
pCur->eSkip = SKIP_NONE;
return SQLITE_OK;
}
/*
** Delete the entry that the cursor is pointing to.
**
** The cursor is left pointing at either the next or the previous
** entry. If the cursor is left pointing to the next entry, then
** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to
** sqliteRbtreeNext() to be a no-op. That way, you can always call
** sqliteRbtreeNext() after a delete and the cursor will be left
** pointing to the first entry after the deleted entry. Similarly,
** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
** the entry prior to the deleted entry so that a subsequent call to
** sqliteRbtreePrevious() will always leave the cursor pointing at the
** entry immediately before the one that was deleted.
*/
static int memRbtreeDelete(RbtCursor* pCur)
{
BtRbNode *pZ; /* The one being deleted */
BtRbNode *pChild; /* The child of the spliced out node */
/* It is illegal to call sqliteRbtreeDelete() if we are
** not in a transaction */
assert( pCur->pRbtree->eTransState != TRANS_NONE );
/* Make sure some other cursor isn't trying to read this same table */
if( checkReadLocks(pCur) ){
return SQLITE_LOCKED; /* The table pCur points to has a read lock */
}
pZ = pCur->pNode;
if( !pZ ){
return SQLITE_OK;
}
/* If we are not currently doing a rollback, set up a rollback op for this
* deletion */
if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
if( pOp==0 ) return SQLITE_NOMEM;
pOp->iTab = pCur->iTree;
pOp->nKey = pZ->nKey;
pOp->pKey = pZ->pKey;
pOp->nData = pZ->nData;
pOp->pData = pZ->pData;
pOp->eOp = ROLLBACK_INSERT;
btreeLogRollbackOp(pCur->pRbtree, pOp);
}
/* First do a standard binary-tree delete (node pZ is to be deleted). How
* to do this depends on how many children pZ has:
*
* If pZ has no children or one child, then splice out pZ. If pZ has two
* children, splice out the successor of pZ and replace the key and data of
* pZ with the key and data of the spliced out successor. */
if( pZ->pLeft && pZ->pRight ){
BtRbNode *pTmp;
int dummy;
pCur->eSkip = SKIP_NONE;
memRbtreeNext(pCur, &dummy);
assert( dummy == 0 );
if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
sqliteFree(pZ->pKey);
sqliteFree(pZ->pData);
}
pZ->pData = pCur->pNode->pData;
pZ->nData = pCur->pNode->nData;
pZ->pKey = pCur->pNode->pKey;
pZ->nKey = pCur->pNode->nKey;
pTmp = pZ;
pZ = pCur->pNode;
pCur->pNode = pTmp;
pCur->eSkip = SKIP_NEXT;
}else{
int res;
pCur->eSkip = SKIP_NONE;
memRbtreeNext(pCur, &res);
pCur->eSkip = SKIP_NEXT;
if( res ){
memRbtreeLast(pCur, &res);
memRbtreePrevious(pCur, &res);
pCur->eSkip = SKIP_PREV;
}
if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
sqliteFree(pZ->pKey);
sqliteFree(pZ->pData);
sqliteFree( pNode->pData );
}else{
BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->eOp = ROLLBACK_INSERT;
pRollbackOp->iTab = n;
pRollbackOp->nKey = pNode->nKey;
pRollbackOp->pKey = pNode->pKey;
pRollbackOp->nData = pNode->nData;
pRollbackOp->pData = pNode->pData;
btreeLogRollbackOp(tree, pRollbackOp);
}
sqliteFree( pNode );
if( pTmp ){
if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
}
pNode = pTmp;
}
}
pTree->pHead = 0;
return SQLITE_OK;
}
static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
{
if( pCur->pTree->pHead ){
pCur->pNode = pCur->pTree->pHead;
while( pCur->pNode->pLeft ){
pCur->pNode = pCur->pNode->pLeft;
}
}
if( pCur->pNode ){
*pRes = 0;
}else{
*pRes = 1;
}
pCur->eSkip = SKIP_NONE;
return SQLITE_OK;
}
static int memRbtreeLast(RbtCursor* pCur, int *pRes)
{
if( pCur->pTree->pHead ){
pCur->pNode = pCur->pTree->pHead;
while( pCur->pNode->pRight ){
pCur->pNode = pCur->pNode->pRight;
}
}
if( pCur->pNode ){
*pRes = 0;
}else{
*pRes = 1;
}
pCur->eSkip = SKIP_NONE;
return SQLITE_OK;
}
/*
** Advance the cursor to the next entry in the database. If
** successful then set *pRes=0. If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
static int memRbtreeNext(RbtCursor* pCur, int *pRes)
{
if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
if( pCur->pNode->pRight ){
pCur->pNode = pCur->pNode->pRight;
while( pCur->pNode->pLeft )
pCur->pNode = pCur->pNode->pLeft;
}else{
BtRbNode * pX = pCur->pNode;
pCur->pNode = pX->pParent;
while( pCur->pNode && (pCur->pNode->pRight == pX) ){
pX = pCur->pNode;
pCur->pNode = pX->pParent;
}
}
}
pCur->eSkip = SKIP_NONE;
if( !pCur->pNode ){
*pRes = 1;
}else{
*pRes = 0;
}
return SQLITE_OK;
}
static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
{
if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
if( pCur->pNode->pLeft ){
pCur->pNode = pCur->pNode->pLeft;
while( pCur->pNode->pRight )
pCur->pNode = pCur->pNode->pRight;
}else{
BtRbNode * pX = pCur->pNode;
pCur->pNode = pX->pParent;
while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
pX = pCur->pNode;
pCur->pNode = pX->pParent;
}
}
}
pCur->eSkip = SKIP_NONE;
if( !pCur->pNode ){
*pRes = 1;
}else{
*pRes = 0;
}
return SQLITE_OK;
}
static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
{
if( pCur->pNode ){
( run in 1.003 second using v1.01-cache-2.11-cpan-13bb782fe5a )