1 /* 2 ** 2003 Feb 4 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** $Id: btree_rb.c,v 1.24.2.1 2004/06/26 14:40:05 drh Exp $ 13 ** 14 ** This file implements an in-core database using Red-Black balanced 15 ** binary trees. 16 ** 17 ** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC. 18 */ 19 #include "btree.h" 20 #include "sqliteInt.h" 21 #include <assert.h> 22 23 /* 24 ** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is 25 ** defined. This allows a lot of code to be omitted for installations 26 ** that do not need it. 27 */ 28 #ifndef SQLITE_OMIT_INMEMORYDB 29 30 31 typedef struct BtRbTree BtRbTree; 32 typedef struct BtRbNode BtRbNode; 33 typedef struct BtRollbackOp BtRollbackOp; 34 typedef struct Rbtree Rbtree; 35 typedef struct RbtCursor RbtCursor; 36 37 /* Forward declarations */ 38 static BtOps sqliteRbtreeOps; 39 static BtCursorOps sqliteRbtreeCursorOps; 40 41 /* 42 * During each transaction (or checkpoint), a linked-list of 43 * "rollback-operations" is accumulated. If the transaction is rolled back, 44 * then the list of operations must be executed (to restore the database to 45 * it's state before the transaction started). If the transaction is to be 46 * committed, just delete the list. 47 * 48 * Each operation is represented as follows, depending on the value of eOp: 49 * 50 * ROLLBACK_INSERT -> Need to insert (pKey, pData) into table iTab. 51 * ROLLBACK_DELETE -> Need to delete the record (pKey) into table iTab. 52 * ROLLBACK_CREATE -> Need to create table iTab. 53 * ROLLBACK_DROP -> Need to drop table iTab. 54 */ 55 struct BtRollbackOp { 56 u8 eOp; 57 int iTab; 58 int nKey; 59 void *pKey; 60 int nData; 61 void *pData; 62 BtRollbackOp *pNext; 63 }; 64 65 /* 66 ** Legal values for BtRollbackOp.eOp: 67 */ 68 #define ROLLBACK_INSERT 1 /* Insert a record */ 69 #define ROLLBACK_DELETE 2 /* Delete a record */ 70 #define ROLLBACK_CREATE 3 /* Create a table */ 71 #define ROLLBACK_DROP 4 /* Drop a table */ 72 73 struct Rbtree { 74 BtOps *pOps; /* Function table */ 75 int aMetaData[SQLITE_N_BTREE_META]; 76 77 int next_idx; /* next available table index */ 78 Hash tblHash; /* All created tables, by index */ 79 u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */ 80 u8 eTransState; /* State of this Rbtree wrt transactions */ 81 82 BtRollbackOp *pTransRollback; 83 BtRollbackOp *pCheckRollback; 84 BtRollbackOp *pCheckRollbackTail; 85 }; 86 87 /* 88 ** Legal values for Rbtree.eTransState. 89 */ 90 #define TRANS_NONE 0 /* No transaction is in progress */ 91 #define TRANS_INTRANSACTION 1 /* A transaction is in progress */ 92 #define TRANS_INCHECKPOINT 2 /* A checkpoint is in progress */ 93 #define TRANS_ROLLBACK 3 /* We are currently rolling back a checkpoint or 94 * transaction. */ 95 96 struct RbtCursor { 97 BtCursorOps *pOps; /* Function table */ 98 Rbtree *pRbtree; 99 BtRbTree *pTree; 100 int iTree; /* Index of pTree in pRbtree */ 101 BtRbNode *pNode; 102 RbtCursor *pShared; /* List of all cursors on the same Rbtree */ 103 u8 eSkip; /* Determines if next step operation is a no-op */ 104 u8 wrFlag; /* True if this cursor is open for writing */ 105 }; 106 107 /* 108 ** Legal values for RbtCursor.eSkip. 109 */ 110 #define SKIP_NONE 0 /* Always step the cursor */ 111 #define SKIP_NEXT 1 /* The next sqliteRbtreeNext() is a no-op */ 112 #define SKIP_PREV 2 /* The next sqliteRbtreePrevious() is a no-op */ 113 #define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */ 114 115 struct BtRbTree { 116 RbtCursor *pCursors; /* All cursors pointing to this tree */ 117 BtRbNode *pHead; /* Head of the tree, or NULL */ 118 }; 119 120 struct BtRbNode { 121 int nKey; 122 void *pKey; 123 int nData; 124 void *pData; 125 u8 isBlack; /* true for a black node, 0 for a red node */ 126 BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */ 127 BtRbNode *pLeft; /* Nodes left child, or NULL */ 128 BtRbNode *pRight; /* Nodes right child, or NULL */ 129 130 int nBlackHeight; /* Only used during the red-black integrity check */ 131 }; 132 133 /* Forward declarations */ 134 static int memRbtreeMoveto( 135 RbtCursor* pCur, 136 const void *pKey, 137 int nKey, 138 int *pRes 139 ); 140 static int memRbtreeClearTable(Rbtree* tree, int n); 141 static int memRbtreeNext(RbtCursor* pCur, int *pRes); 142 static int memRbtreeLast(RbtCursor* pCur, int *pRes); 143 static int memRbtreePrevious(RbtCursor* pCur, int *pRes); 144 145 146 /* 147 ** This routine checks all cursors that point to the same table 148 ** as pCur points to. If any of those cursors were opened with 149 ** wrFlag==0 then this routine returns SQLITE_LOCKED. If all 150 ** cursors point to the same table were opened with wrFlag==1 151 ** then this routine returns SQLITE_OK. 152 ** 153 ** In addition to checking for read-locks (where a read-lock 154 ** means a cursor opened with wrFlag==0) this routine also NULLs 155 ** out the pNode field of all other cursors. 156 ** This is necessary because an insert 157 ** or delete might change erase the node out from under 158 ** another cursor. 159 */ 160 static int checkReadLocks(RbtCursor *pCur){ 161 RbtCursor *p; 162 assert( pCur->wrFlag ); 163 for(p=pCur->pTree->pCursors; p; p=p->pShared){ 164 if( p!=pCur ){ 165 if( p->wrFlag==0 ) return SQLITE_LOCKED; 166 p->pNode = 0; 167 } 168 } 169 return SQLITE_OK; 170 } 171 172 /* 173 * The key-compare function for the red-black trees. Returns as follows: 174 * 175 * (key1 < key2) -1 176 * (key1 == key2) 0 177 * (key1 > key2) 1 178 * 179 * Keys are compared using memcmp(). If one key is an exact prefix of the 180 * other, then the shorter key is less than the longer key. 181 */ 182 static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2) 183 { 184 int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2); 185 if( mcmp == 0){ 186 if( nKey1 == nKey2 ) return 0; 187 return ((nKey1 < nKey2)?-1:1); 188 } 189 return ((mcmp>0)?1:-1); 190 } 191 192 /* 193 * Perform the LEFT-rotate transformation on node X of tree pTree. This 194 * transform is part of the red-black balancing code. 195 * 196 * | | 197 * X Y 198 * / \ / \ 199 * a Y X c 200 * / \ / \ 201 * b c a b 202 * 203 * BEFORE AFTER 204 */ 205 static void leftRotate(BtRbTree *pTree, BtRbNode *pX) 206 { 207 BtRbNode *pY; 208 BtRbNode *pb; 209 pY = pX->pRight; 210 pb = pY->pLeft; 211 212 pY->pParent = pX->pParent; 213 if( pX->pParent ){ 214 if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY; 215 else pX->pParent->pRight = pY; 216 } 217 pY->pLeft = pX; 218 pX->pParent = pY; 219 pX->pRight = pb; 220 if( pb ) pb->pParent = pX; 221 if( pTree->pHead == pX ) pTree->pHead = pY; 222 } 223 224 /* 225 * Perform the RIGHT-rotate transformation on node X of tree pTree. This 226 * transform is part of the red-black balancing code. 227 * 228 * | | 229 * X Y 230 * / \ / \ 231 * Y c a X 232 * / \ / \ 233 * a b b c 234 * 235 * BEFORE AFTER 236 */ 237 static void rightRotate(BtRbTree *pTree, BtRbNode *pX) 238 { 239 BtRbNode *pY; 240 BtRbNode *pb; 241 pY = pX->pLeft; 242 pb = pY->pRight; 243 244 pY->pParent = pX->pParent; 245 if( pX->pParent ){ 246 if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY; 247 else pX->pParent->pRight = pY; 248 } 249 pY->pRight = pX; 250 pX->pParent = pY; 251 pX->pLeft = pb; 252 if( pb ) pb->pParent = pX; 253 if( pTree->pHead == pX ) pTree->pHead = pY; 254 } 255 256 /* 257 * A string-manipulation helper function for check_redblack_tree(). If (orig == 258 * NULL) a copy of val is returned. If (orig != NULL) then a copy of the * 259 * concatenation of orig and val is returned. The original orig is deleted 260 * (using sqliteFree()). 261 */ 262 static char *append_val(char * orig, char const * val){ 263 char *z; 264 if( !orig ){ 265 z = sqliteStrDup( val ); 266 } else{ 267 z = 0; 268 sqliteSetString(&z, orig, val, (char*)0); 269 sqliteFree( orig ); 270 } 271 return z; 272 } 273 274 /* 275 * Append a string representation of the entire node to orig and return it. 276 * This is used to produce debugging information if check_redblack_tree() finds 277 * a problem with a red-black binary tree. 278 */ 279 static char *append_node(char * orig, BtRbNode *pNode, int indent) 280 { 281 char buf[128]; 282 int i; 283 284 for( i=0; i<indent; i++ ){ 285 orig = append_val(orig, " "); 286 } 287 288 sprintf(buf, "%p", pNode); 289 orig = append_val(orig, buf); 290 291 if( pNode ){ 292 indent += 3; 293 if( pNode->isBlack ){ 294 orig = append_val(orig, " B \n"); 295 }else{ 296 orig = append_val(orig, " R \n"); 297 } 298 orig = append_node( orig, pNode->pLeft, indent ); 299 orig = append_node( orig, pNode->pRight, indent ); 300 }else{ 301 orig = append_val(orig, "\n"); 302 } 303 return orig; 304 } 305 306 /* 307 * Print a representation of a node to stdout. This function is only included 308 * so you can call it from within a debugger if things get really bad. It 309 * is not called from anyplace in the code. 310 */ 311 static void print_node(BtRbNode *pNode) 312 { 313 char * str = append_node(0, pNode, 0); 314 printf("%s", str); 315 316 /* Suppress a warning message about print_node() being unused */ 317 (void)print_node; 318 } 319 320 /* 321 * Check the following properties of the red-black tree: 322 * (1) - If a node is red, both of it's children are black 323 * (2) - Each path from a given node to a leaf (NULL) node passes thru the 324 * same number of black nodes 325 * 326 * If there is a problem, append a description (using append_val() ) to *msg. 327 */ 328 static void check_redblack_tree(BtRbTree * tree, char ** msg) 329 { 330 BtRbNode *pNode; 331 332 /* 0 -> came from parent 333 * 1 -> came from left 334 * 2 -> came from right */ 335 int prev_step = 0; 336 337 pNode = tree->pHead; 338 while( pNode ){ 339 switch( prev_step ){ 340 case 0: 341 if( pNode->pLeft ){ 342 pNode = pNode->pLeft; 343 }else{ 344 prev_step = 1; 345 } 346 break; 347 case 1: 348 if( pNode->pRight ){ 349 pNode = pNode->pRight; 350 prev_step = 0; 351 }else{ 352 prev_step = 2; 353 } 354 break; 355 case 2: 356 /* Check red-black property (1) */ 357 if( !pNode->isBlack && 358 ( (pNode->pLeft && !pNode->pLeft->isBlack) || 359 (pNode->pRight && !pNode->pRight->isBlack) ) 360 ){ 361 char buf[128]; 362 sprintf(buf, "Red node with red child at %p\n", pNode); 363 *msg = append_val(*msg, buf); 364 *msg = append_node(*msg, tree->pHead, 0); 365 *msg = append_val(*msg, "\n"); 366 } 367 368 /* Check red-black property (2) */ 369 { 370 int leftHeight = 0; 371 int rightHeight = 0; 372 if( pNode->pLeft ){ 373 leftHeight += pNode->pLeft->nBlackHeight; 374 leftHeight += (pNode->pLeft->isBlack?1:0); 375 } 376 if( pNode->pRight ){ 377 rightHeight += pNode->pRight->nBlackHeight; 378 rightHeight += (pNode->pRight->isBlack?1:0); 379 } 380 if( leftHeight != rightHeight ){ 381 char buf[128]; 382 sprintf(buf, "Different black-heights at %p\n", pNode); 383 *msg = append_val(*msg, buf); 384 *msg = append_node(*msg, tree->pHead, 0); 385 *msg = append_val(*msg, "\n"); 386 } 387 pNode->nBlackHeight = leftHeight; 388 } 389 390 if( pNode->pParent ){ 391 if( pNode == pNode->pParent->pLeft ) prev_step = 1; 392 else prev_step = 2; 393 } 394 pNode = pNode->pParent; 395 break; 396 default: assert(0); 397 } 398 } 399 } 400 401 /* 402 * Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()). 403 * It is possible that pX is a red node with a red parent, which is a violation 404 * of the red-black tree properties. This function performs rotations and 405 * color changes to rebalance the tree 406 */ 407 static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX) 408 { 409 /* In the first iteration of this loop, pX points to the red node just 410 * inserted in the tree. If the parent of pX exists (pX is not the root 411 * node) and is red, then the properties of the red-black tree are 412 * violated. 413 * 414 * At the start of any subsequent iterations, pX points to a red node 415 * with a red parent. In all other respects the tree is a legal red-black 416 * binary tree. */ 417 while( pX != pTree->pHead && !pX->pParent->isBlack ){ 418 BtRbNode *pUncle; 419 BtRbNode *pGrandparent; 420 421 /* Grandparent of pX must exist and must be black. */ 422 pGrandparent = pX->pParent->pParent; 423 assert( pGrandparent ); 424 assert( pGrandparent->isBlack ); 425 426 /* Uncle of pX may or may not exist. */ 427 if( pX->pParent == pGrandparent->pLeft ) 428 pUncle = pGrandparent->pRight; 429 else 430 pUncle = pGrandparent->pLeft; 431 432 /* If the uncle of pX exists and is red, we do the following: 433 * | | 434 * G(b) G(r) 435 * / \ / \ 436 * U(r) P(r) U(b) P(b) 437 * \ \ 438 * X(r) X(r) 439 * 440 * BEFORE AFTER 441 * pX is then set to G. If the parent of G is red, then the while loop 442 * will run again. */ 443 if( pUncle && !pUncle->isBlack ){ 444 pGrandparent->isBlack = 0; 445 pUncle->isBlack = 1; 446 pX->pParent->isBlack = 1; 447 pX = pGrandparent; 448 }else{ 449 450 if( pX->pParent == pGrandparent->pLeft ){ 451 if( pX == pX->pParent->pRight ){ 452 /* If pX is a right-child, do the following transform, essentially 453 * to change pX into a left-child: 454 * | | 455 * G(b) G(b) 456 * / \ / \ 457 * P(r) U(b) X(r) U(b) 458 * \ / 459 * X(r) P(r) <-- new X 460 * 461 * BEFORE AFTER 462 */ 463 pX = pX->pParent; 464 leftRotate(pTree, pX); 465 } 466 467 /* Do the following transform, which balances the tree :) 468 * | | 469 * G(b) P(b) 470 * / \ / \ 471 * P(r) U(b) X(r) G(r) 472 * / \ 473 * X(r) U(b) 474 * 475 * BEFORE AFTER 476 */ 477 assert( pGrandparent == pX->pParent->pParent ); 478 pGrandparent->isBlack = 0; 479 pX->pParent->isBlack = 1; 480 rightRotate( pTree, pGrandparent ); 481 482 }else{ 483 /* This code is symetric to the illustrated case above. */ 484 if( pX == pX->pParent->pLeft ){ 485 pX = pX->pParent; 486 rightRotate(pTree, pX); 487 } 488 assert( pGrandparent == pX->pParent->pParent ); 489 pGrandparent->isBlack = 0; 490 pX->pParent->isBlack = 1; 491 leftRotate( pTree, pGrandparent ); 492 } 493 } 494 } 495 pTree->pHead->isBlack = 1; 496 } 497 498 /* 499 * A child of pParent, which in turn had child pX, has just been removed from 500 * pTree (the figure below depicts the operation, Z is being removed). pParent 501 * or pX, or both may be NULL. 502 * | | 503 * P P 504 * / \ / \ 505 * Z X 506 * / \ 507 * X nil 508 * 509 * This function is only called if Z was black. In this case the red-black tree 510 * properties have been violated, and pX has an "extra black". This function 511 * performs rotations and color-changes to re-balance the tree. 512 */ 513 static 514 void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent) 515 { 516 BtRbNode *pSib; 517 518 /* TODO: Comment this code! */ 519 while( pX != pTree->pHead && (!pX || pX->isBlack) ){ 520 if( pX == pParent->pLeft ){ 521 pSib = pParent->pRight; 522 if( pSib && !(pSib->isBlack) ){ 523 pSib->isBlack = 1; 524 pParent->isBlack = 0; 525 leftRotate(pTree, pParent); 526 pSib = pParent->pRight; 527 } 528 if( !pSib ){ 529 pX = pParent; 530 }else if( 531 (!pSib->pLeft || pSib->pLeft->isBlack) && 532 (!pSib->pRight || pSib->pRight->isBlack) ) { 533 pSib->isBlack = 0; 534 pX = pParent; 535 }else{ 536 if( (!pSib->pRight || pSib->pRight->isBlack) ){ 537 if( pSib->pLeft ) pSib->pLeft->isBlack = 1; 538 pSib->isBlack = 0; 539 rightRotate( pTree, pSib ); 540 pSib = pParent->pRight; 541 } 542 pSib->isBlack = pParent->isBlack; 543 pParent->isBlack = 1; 544 if( pSib->pRight ) pSib->pRight->isBlack = 1; 545 leftRotate(pTree, pParent); 546 pX = pTree->pHead; 547 } 548 }else{ 549 pSib = pParent->pLeft; 550 if( pSib && !(pSib->isBlack) ){ 551 pSib->isBlack = 1; 552 pParent->isBlack = 0; 553 rightRotate(pTree, pParent); 554 pSib = pParent->pLeft; 555 } 556 if( !pSib ){ 557 pX = pParent; 558 }else if( 559 (!pSib->pLeft || pSib->pLeft->isBlack) && 560 (!pSib->pRight || pSib->pRight->isBlack) ){ 561 pSib->isBlack = 0; 562 pX = pParent; 563 }else{ 564 if( (!pSib->pLeft || pSib->pLeft->isBlack) ){ 565 if( pSib->pRight ) pSib->pRight->isBlack = 1; 566 pSib->isBlack = 0; 567 leftRotate( pTree, pSib ); 568 pSib = pParent->pLeft; 569 } 570 pSib->isBlack = pParent->isBlack; 571 pParent->isBlack = 1; 572 if( pSib->pLeft ) pSib->pLeft->isBlack = 1; 573 rightRotate(pTree, pParent); 574 pX = pTree->pHead; 575 } 576 } 577 pParent = pX->pParent; 578 } 579 if( pX ) pX->isBlack = 1; 580 } 581 582 /* 583 * Create table n in tree pRbtree. Table n must not exist. 584 */ 585 static void btreeCreateTable(Rbtree* pRbtree, int n) 586 { 587 BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree)); 588 sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl); 589 } 590 591 /* 592 * Log a single "rollback-op" for the given Rbtree. See comments for struct 593 * BtRollbackOp. 594 */ 595 static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp) 596 { 597 assert( pRbtree->eTransState == TRANS_INCHECKPOINT || 598 pRbtree->eTransState == TRANS_INTRANSACTION ); 599 if( pRbtree->eTransState == TRANS_INTRANSACTION ){ 600 pRollbackOp->pNext = pRbtree->pTransRollback; 601 pRbtree->pTransRollback = pRollbackOp; 602 } 603 if( pRbtree->eTransState == TRANS_INCHECKPOINT ){ 604 if( !pRbtree->pCheckRollback ){ 605 pRbtree->pCheckRollbackTail = pRollbackOp; 606 } 607 pRollbackOp->pNext = pRbtree->pCheckRollback; 608 pRbtree->pCheckRollback = pRollbackOp; 609 } 610 } 611 612 int sqliteRbtreeOpen( 613 const char *zFilename, 614 int mode, 615 int nPg, 616 Btree **ppBtree 617 ){ 618 Rbtree **ppRbtree = (Rbtree**)ppBtree; 619 *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree)); 620 if( sqlite_malloc_failed ) goto open_no_mem; 621 sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0); 622 623 /* Create a binary tree for the SQLITE_MASTER table at location 2 */ 624 btreeCreateTable(*ppRbtree, 2); 625 if( sqlite_malloc_failed ) goto open_no_mem; 626 (*ppRbtree)->next_idx = 3; 627 (*ppRbtree)->pOps = &sqliteRbtreeOps; 628 /* Set file type to 4; this is so that "attach ':memory:' as ...." does not 629 ** think that the database in uninitialised and refuse to attach 630 */ 631 (*ppRbtree)->aMetaData[2] = 4; 632 633 return SQLITE_OK; 634 635 open_no_mem: 636 *ppBtree = 0; 637 return SQLITE_NOMEM; 638 } 639 640 /* 641 * Create a new table in the supplied Rbtree. Set *n to the new table number. 642 * Return SQLITE_OK if the operation is a success. 643 */ 644 static int memRbtreeCreateTable(Rbtree* tree, int* n) 645 { 646 assert( tree->eTransState != TRANS_NONE ); 647 648 *n = tree->next_idx++; 649 btreeCreateTable(tree, *n); 650 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 651 652 /* Set up the rollback structure (if we are not doing this as part of a 653 * rollback) */ 654 if( tree->eTransState != TRANS_ROLLBACK ){ 655 BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); 656 if( pRollbackOp==0 ) return SQLITE_NOMEM; 657 pRollbackOp->eOp = ROLLBACK_DROP; 658 pRollbackOp->iTab = *n; 659 btreeLogRollbackOp(tree, pRollbackOp); 660 } 661 662 return SQLITE_OK; 663 } 664 665 /* 666 * Delete table n from the supplied Rbtree. 667 */ 668 static int memRbtreeDropTable(Rbtree* tree, int n) 669 { 670 BtRbTree *pTree; 671 assert( tree->eTransState != TRANS_NONE ); 672 673 memRbtreeClearTable(tree, n); 674 pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0); 675 assert(pTree); 676 assert( pTree->pCursors==0 ); 677 sqliteFree(pTree); 678 679 if( tree->eTransState != TRANS_ROLLBACK ){ 680 BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); 681 if( pRollbackOp==0 ) return SQLITE_NOMEM; 682 pRollbackOp->eOp = ROLLBACK_CREATE; 683 pRollbackOp->iTab = n; 684 btreeLogRollbackOp(tree, pRollbackOp); 685 } 686 687 return SQLITE_OK; 688 } 689 690 static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey, 691 int nIgnore, int *pRes) 692 { 693 assert(pCur); 694 695 if( !pCur->pNode ) { 696 *pRes = -1; 697 } else { 698 if( (pCur->pNode->nKey - nIgnore) < 0 ){ 699 *pRes = -1; 700 }else{ 701 *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore, 702 pKey, nKey); 703 } 704 } 705 return SQLITE_OK; 706 } 707 708 /* 709 * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag 710 * parameter indicates that the cursor is open for writing. 711 * 712 * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0. 713 */ 714 static int memRbtreeCursor( 715 Rbtree* tree, 716 int iTable, 717 int wrFlag, 718 RbtCursor **ppCur 719 ){ 720 RbtCursor *pCur; 721 assert(tree); 722 pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor)); 723 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 724 pCur->pTree = sqliteHashFind(&tree->tblHash, 0, iTable); 725 assert( pCur->pTree ); 726 pCur->pRbtree = tree; 727 pCur->iTree = iTable; 728 pCur->pOps = &sqliteRbtreeCursorOps; 729 pCur->wrFlag = wrFlag; 730 pCur->pShared = pCur->pTree->pCursors; 731 pCur->pTree->pCursors = pCur; 732 733 assert( (*ppCur)->pTree ); 734 return SQLITE_OK; 735 } 736 737 /* 738 * Insert a new record into the Rbtree. The key is given by (pKey,nKey) 739 * and the data is given by (pData,nData). The cursor is used only to 740 * define what database the record should be inserted into. The cursor 741 * is left pointing at the new record. 742 * 743 * If the key exists already in the tree, just replace the data. 744 */ 745 static int memRbtreeInsert( 746 RbtCursor* pCur, 747 const void *pKey, 748 int nKey, 749 const void *pDataInput, 750 int nData 751 ){ 752 void * pData; 753 int match; 754 755 /* It is illegal to call sqliteRbtreeInsert() if we are 756 ** not in a transaction */ 757 assert( pCur->pRbtree->eTransState != TRANS_NONE ); 758 759 /* Make sure some other cursor isn't trying to read this same table */ 760 if( checkReadLocks(pCur) ){ 761 return SQLITE_LOCKED; /* The table pCur points to has a read lock */ 762 } 763 764 /* Take a copy of the input data now, in case we need it for the 765 * replace case */ 766 pData = sqliteMallocRaw(nData); 767 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 768 memcpy(pData, pDataInput, nData); 769 770 /* Move the cursor to a node near the key to be inserted. If the key already 771 * exists in the table, then (match == 0). In this case we can just replace 772 * the data associated with the entry, we don't need to manipulate the tree. 773 * 774 * If there is no exact match, then the cursor points at what would be either 775 * the predecessor (match == -1) or successor (match == 1) of the 776 * searched-for key, were it to be inserted. The new node becomes a child of 777 * this node. 778 * 779 * The new node is initially red. 780 */ 781 memRbtreeMoveto( pCur, pKey, nKey, &match); 782 if( match ){ 783 BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode)); 784 if( pNode==0 ) return SQLITE_NOMEM; 785 pNode->nKey = nKey; 786 pNode->pKey = sqliteMallocRaw(nKey); 787 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 788 memcpy(pNode->pKey, pKey, nKey); 789 pNode->nData = nData; 790 pNode->pData = pData; 791 if( pCur->pNode ){ 792 switch( match ){ 793 case -1: 794 assert( !pCur->pNode->pRight ); 795 pNode->pParent = pCur->pNode; 796 pCur->pNode->pRight = pNode; 797 break; 798 case 1: 799 assert( !pCur->pNode->pLeft ); 800 pNode->pParent = pCur->pNode; 801 pCur->pNode->pLeft = pNode; 802 break; 803 default: 804 assert(0); 805 } 806 }else{ 807 pCur->pTree->pHead = pNode; 808 } 809 810 /* Point the cursor at the node just inserted, as per SQLite requirements */ 811 pCur->pNode = pNode; 812 813 /* A new node has just been inserted, so run the balancing code */ 814 do_insert_balancing(pCur->pTree, pNode); 815 816 /* Set up a rollback-op in case we have to roll this operation back */ 817 if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){ 818 BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) ); 819 if( pOp==0 ) return SQLITE_NOMEM; 820 pOp->eOp = ROLLBACK_DELETE; 821 pOp->iTab = pCur->iTree; 822 pOp->nKey = pNode->nKey; 823 pOp->pKey = sqliteMallocRaw( pOp->nKey ); 824 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 825 memcpy( pOp->pKey, pNode->pKey, pOp->nKey ); 826 btreeLogRollbackOp(pCur->pRbtree, pOp); 827 } 828 829 }else{ 830 /* No need to insert a new node in the tree, as the key already exists. 831 * Just clobber the current nodes data. */ 832 833 /* Set up a rollback-op in case we have to roll this operation back */ 834 if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){ 835 BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) ); 836 if( pOp==0 ) return SQLITE_NOMEM; 837 pOp->iTab = pCur->iTree; 838 pOp->nKey = pCur->pNode->nKey; 839 pOp->pKey = sqliteMallocRaw( pOp->nKey ); 840 if( sqlite_malloc_failed ) return SQLITE_NOMEM; 841 memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey ); 842 pOp->nData = pCur->pNode->nData; 843 pOp->pData = pCur->pNode->pData; 844 pOp->eOp = ROLLBACK_INSERT; 845 btreeLogRollbackOp(pCur->pRbtree, pOp); 846 }else{ 847 sqliteFree( pCur->pNode->pData ); 848 } 849 850 /* Actually clobber the nodes data */ 851 pCur->pNode->pData = pData; 852 pCur->pNode->nData = nData; 853 } 854 855 return SQLITE_OK; 856 } 857 858 /* Move the cursor so that it points to an entry near pKey. 859 ** Return a success code. 860 ** 861 ** *pRes<0 The cursor is left pointing at an entry that 862 ** is smaller than pKey or if the table is empty 863 ** and the cursor is therefore left point to nothing. 864 ** 865 ** *pRes==0 The cursor is left pointing at an entry that 866 ** exactly matches pKey. 867 ** 868 ** *pRes>0 The cursor is left pointing at an entry that 869 ** is larger than pKey. 870 */ 871 static int memRbtreeMoveto( 872 RbtCursor* pCur, 873 const void *pKey, 874 int nKey, 875 int *pRes 876 ){ 877 BtRbNode *pTmp = 0; 878 879 pCur->pNode = pCur->pTree->pHead; 880 *pRes = -1; 881 while( pCur->pNode && *pRes ) { 882 *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey); 883 pTmp = pCur->pNode; 884 switch( *pRes ){ 885 case 1: /* cursor > key */ 886 pCur->pNode = pCur->pNode->pLeft; 887 break; 888 case -1: /* cursor < key */ 889 pCur->pNode = pCur->pNode->pRight; 890 break; 891 } 892 } 893 894 /* If (pCur->pNode == NULL), then we have failed to find a match. Set 895 * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the 896 * last node traversed in the search. In either case the relation ship 897 * between pTmp and the searched for key is already stored in *pRes. pTmp is 898 * either the successor or predecessor of the key we tried to move to. */ 899 if( !pCur->pNode ) pCur->pNode = pTmp; 900 pCur->eSkip = SKIP_NONE; 901 902 return SQLITE_OK; 903 } 904 905 906 /* 907 ** Delete the entry that the cursor is pointing to. 908 ** 909 ** The cursor is left pointing at either the next or the previous 910 ** entry. If the cursor is left pointing to the next entry, then 911 ** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 912 ** sqliteRbtreeNext() to be a no-op. That way, you can always call 913 ** sqliteRbtreeNext() after a delete and the cursor will be left 914 ** pointing to the first entry after the deleted entry. Similarly, 915 ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to 916 ** the entry prior to the deleted entry so that a subsequent call to 917 ** sqliteRbtreePrevious() will always leave the cursor pointing at the 918 ** entry immediately before the one that was deleted. 919 */ 920 static int memRbtreeDelete(RbtCursor* pCur) 921 { 922 BtRbNode *pZ; /* The one being deleted */ 923 BtRbNode *pChild; /* The child of the spliced out node */ 924 925 /* It is illegal to call sqliteRbtreeDelete() if we are 926 ** not in a transaction */ 927 assert( pCur->pRbtree->eTransState != TRANS_NONE ); 928 929 /* Make sure some other cursor isn't trying to read this same table */ 930 if( checkReadLocks(pCur) ){ 931 return SQLITE_LOCKED; /* The table pCur points to has a read lock */ 932 } 933 934 pZ = pCur->pNode; 935 if( !pZ ){ 936 return SQLITE_OK; 937 } 938 939 /* If we are not currently doing a rollback, set up a rollback op for this 940 * deletion */ 941 if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){ 942 BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) ); 943 if( pOp==0 ) return SQLITE_NOMEM; 944 pOp->iTab = pCur->iTree; 945 pOp->nKey = pZ->nKey; 946 pOp->pKey = pZ->pKey; 947 pOp->nData = pZ->nData; 948 pOp->pData = pZ->pData; 949 pOp->eOp = ROLLBACK_INSERT; 950 btreeLogRollbackOp(pCur->pRbtree, pOp); 951 } 952 953 /* First do a standard binary-tree delete (node pZ is to be deleted). How 954 * to do this depends on how many children pZ has: 955 * 956 * If pZ has no children or one child, then splice out pZ. If pZ has two 957 * children, splice out the successor of pZ and replace the key and data of 958 * pZ with the key and data of the spliced out successor. */ 959 if( pZ->pLeft && pZ->pRight ){ 960 BtRbNode *pTmp; 961 int dummy; 962 pCur->eSkip = SKIP_NONE; 963 memRbtreeNext(pCur, &dummy); 964 assert( dummy == 0 ); 965 if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){ 966 sqliteFree(pZ->pKey); 967 sqliteFree(pZ->pData); 968 } 969 pZ->pData = pCur->pNode->pData; 970 pZ->nData = pCur->pNode->nData; 971 pZ->pKey = pCur->pNode->pKey; 972 pZ->nKey = pCur->pNode->nKey; 973 pTmp = pZ; 974 pZ = pCur->pNode; 975 pCur->pNode = pTmp; 976 pCur->eSkip = SKIP_NEXT; 977 }else{ 978 int res; 979 pCur->eSkip = SKIP_NONE; 980 memRbtreeNext(pCur, &res); 981 pCur->eSkip = SKIP_NEXT; 982 if( res ){ 983 memRbtreeLast(pCur, &res); 984 memRbtreePrevious(pCur, &res); 985 pCur->eSkip = SKIP_PREV; 986 } 987 if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){ 988 sqliteFree(pZ->pKey); 989 sqliteFree(pZ->pData); 990 } 991 } 992 993 /* pZ now points at the node to be spliced out. This block does the 994 * splicing. */ 995 { 996 BtRbNode **ppParentSlot = 0; 997 assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */ 998 pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight); 999 if( pZ->pParent ){ 1000 assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight ); 1001 ppParentSlot = ((pZ == pZ->pParent->pLeft) 1002 ?&pZ->pParent->pLeft:&pZ->pParent->pRight); 1003 *ppParentSlot = pChild; 1004 }else{ 1005 pCur->pTree->pHead = pChild; 1006 } 1007 if( pChild ) pChild->pParent = pZ->pParent; 1008 } 1009 1010 /* pZ now points at the spliced out node. pChild is the only child of pZ, or 1011 * NULL if pZ has no children. If pZ is black, and not the tree root, then we 1012 * will have violated the "same number of black nodes in every path to a 1013 * leaf" property of the red-black tree. The code in do_delete_balancing() 1014 * repairs this. */ 1015 if( pZ->isBlack ){ 1016 do_delete_balancing(pCur->pTree, pChild, pZ->pParent); 1017 } 1018 1019 sqliteFree(pZ); 1020 return SQLITE_OK; 1021 } 1022 1023 /* 1024 * Empty table n of the Rbtree. 1025 */ 1026 static int memRbtreeClearTable(Rbtree* tree, int n) 1027 { 1028 BtRbTree *pTree; 1029 BtRbNode *pNode; 1030 1031 pTree = sqliteHashFind(&tree->tblHash, 0, n); 1032 assert(pTree); 1033 1034 pNode = pTree->pHead; 1035 while( pNode ){ 1036 if( pNode->pLeft ){ 1037 pNode = pNode->pLeft; 1038 } 1039 else if( pNode->pRight ){ 1040 pNode = pNode->pRight; 1041 } 1042 else { 1043 BtRbNode *pTmp = pNode->pParent; 1044 if( tree->eTransState == TRANS_ROLLBACK ){ 1045 sqliteFree( pNode->pKey ); 1046 sqliteFree( pNode->pData ); 1047 }else{ 1048 BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp)); 1049 if( pRollbackOp==0 ) return SQLITE_NOMEM; 1050 pRollbackOp->eOp = ROLLBACK_INSERT; 1051 pRollbackOp->iTab = n; 1052 pRollbackOp->nKey = pNode->nKey; 1053 pRollbackOp->pKey = pNode->pKey; 1054 pRollbackOp->nData = pNode->nData; 1055 pRollbackOp->pData = pNode->pData; 1056 btreeLogRollbackOp(tree, pRollbackOp); 1057 } 1058 sqliteFree( pNode ); 1059 if( pTmp ){ 1060 if( pTmp->pLeft == pNode ) pTmp->pLeft = 0; 1061 else if( pTmp->pRight == pNode ) pTmp->pRight = 0; 1062 } 1063 pNode = pTmp; 1064 } 1065 } 1066 1067 pTree->pHead = 0; 1068 return SQLITE_OK; 1069 } 1070 1071 static int memRbtreeFirst(RbtCursor* pCur, int *pRes) 1072 { 1073 if( pCur->pTree->pHead ){ 1074 pCur->pNode = pCur->pTree->pHead; 1075 while( pCur->pNode->pLeft ){ 1076 pCur->pNode = pCur->pNode->pLeft; 1077 } 1078 } 1079 if( pCur->pNode ){ 1080 *pRes = 0; 1081 }else{ 1082 *pRes = 1; 1083 } 1084 pCur->eSkip = SKIP_NONE; 1085 return SQLITE_OK; 1086 } 1087 1088 static int memRbtreeLast(RbtCursor* pCur, int *pRes) 1089 { 1090 if( pCur->pTree->pHead ){ 1091 pCur->pNode = pCur->pTree->pHead; 1092 while( pCur->pNode->pRight ){ 1093 pCur->pNode = pCur->pNode->pRight; 1094 } 1095 } 1096 if( pCur->pNode ){ 1097 *pRes = 0; 1098 }else{ 1099 *pRes = 1; 1100 } 1101 pCur->eSkip = SKIP_NONE; 1102 return SQLITE_OK; 1103 } 1104 1105 /* 1106 ** Advance the cursor to the next entry in the database. If 1107 ** successful then set *pRes=0. If the cursor 1108 ** was already pointing to the last entry in the database before 1109 ** this routine was called, then set *pRes=1. 1110 */ 1111 static int memRbtreeNext(RbtCursor* pCur, int *pRes) 1112 { 1113 if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){ 1114 if( pCur->pNode->pRight ){ 1115 pCur->pNode = pCur->pNode->pRight; 1116 while( pCur->pNode->pLeft ) 1117 pCur->pNode = pCur->pNode->pLeft; 1118 }else{ 1119 BtRbNode * pX = pCur->pNode; 1120 pCur->pNode = pX->pParent; 1121 while( pCur->pNode && (pCur->pNode->pRight == pX) ){ 1122 pX = pCur->pNode; 1123 pCur->pNode = pX->pParent; 1124 } 1125 } 1126 } 1127 pCur->eSkip = SKIP_NONE; 1128 1129 if( !pCur->pNode ){ 1130 *pRes = 1; 1131 }else{ 1132 *pRes = 0; 1133 } 1134 1135 return SQLITE_OK; 1136 } 1137 1138 static int memRbtreePrevious(RbtCursor* pCur, int *pRes) 1139 { 1140 if( pCur->pNode && pCur->eSkip != SKIP_PREV ){ 1141 if( pCur->pNode->pLeft ){ 1142 pCur->pNode = pCur->pNode->pLeft; 1143 while( pCur->pNode->pRight ) 1144 pCur->pNode = pCur->pNode->pRight; 1145 }else{ 1146 BtRbNode * pX = pCur->pNode; 1147 pCur->pNode = pX->pParent; 1148 while( pCur->pNode && (pCur->pNode->pLeft == pX) ){ 1149 pX = pCur->pNode; 1150 pCur->pNode = pX->pParent; 1151 } 1152 } 1153 } 1154 pCur->eSkip = SKIP_NONE; 1155 1156 if( !pCur->pNode ){ 1157 *pRes = 1; 1158 }else{ 1159 *pRes = 0; 1160 } 1161 1162 return SQLITE_OK; 1163 } 1164 1165 static int memRbtreeKeySize(RbtCursor* pCur, int *pSize) 1166 { 1167 if( pCur->pNode ){ 1168 *pSize = pCur->pNode->nKey; 1169 }else{ 1170 *pSize = 0; 1171 } 1172 return SQLITE_OK; 1173 } 1174 1175 static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf) 1176 { 1177 if( !pCur->pNode ) return 0; 1178 if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){ 1179 memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt); 1180 }else{ 1181 memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset); 1182 amt = pCur->pNode->nKey-offset; 1183 } 1184 return amt; 1185 } 1186 1187 static int memRbtreeDataSize(RbtCursor* pCur, int *pSize) 1188 { 1189 if( pCur->pNode ){ 1190 *pSize = pCur->pNode->nData; 1191 }else{ 1192 *pSize = 0; 1193 } 1194 return SQLITE_OK; 1195 } 1196 1197 static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf) 1198 { 1199 if( !pCur->pNode ) return 0; 1200 if( (amt + offset) <= pCur->pNode->nData ){ 1201 memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt); 1202 }else{ 1203 memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset); 1204 amt = pCur->pNode->nData-offset; 1205 } 1206 return amt; 1207 } 1208 1209 static int memRbtreeCloseCursor(RbtCursor* pCur) 1210 { 1211 if( pCur->pTree->pCursors==pCur ){ 1212 pCur->pTree->pCursors = pCur->pShared; 1213 }else{ 1214 RbtCursor *p = pCur->pTree->pCursors; 1215 while( p && p->pShared!=pCur ){ p = p->pShared; } 1216 assert( p!=0 ); 1217 if( p ){ 1218 p->pShared = pCur->pShared; 1219 } 1220 } 1221 sqliteFree(pCur); 1222 return SQLITE_OK; 1223 } 1224 1225 static int memRbtreeGetMeta(Rbtree* tree, int* aMeta) 1226 { 1227 memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META ); 1228 return SQLITE_OK; 1229 } 1230 1231 static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta) 1232 { 1233 memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META ); 1234 return SQLITE_OK; 1235 } 1236 1237 /* 1238 * Check that each table in the Rbtree meets the requirements for a red-black 1239 * binary tree. If an error is found, return an explanation of the problem in 1240 * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored. 1241 */ 1242 static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot) 1243 { 1244 char * msg = 0; 1245 HashElem *p; 1246 1247 for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){ 1248 BtRbTree *pTree = sqliteHashData(p); 1249 check_redblack_tree(pTree, &msg); 1250 } 1251 1252 return msg; 1253 } 1254 1255 static int memRbtreeSetCacheSize(Rbtree* tree, int sz) 1256 { 1257 return SQLITE_OK; 1258 } 1259 1260 static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){ 1261 return SQLITE_OK; 1262 } 1263 1264 static int memRbtreeBeginTrans(Rbtree* tree) 1265 { 1266 if( tree->eTransState != TRANS_NONE ) 1267 return SQLITE_ERROR; 1268 1269 assert( tree->pTransRollback == 0 ); 1270 tree->eTransState = TRANS_INTRANSACTION; 1271 return SQLITE_OK; 1272 } 1273 1274 /* 1275 ** Delete a linked list of BtRollbackOp structures. 1276 */ 1277 static void deleteRollbackList(BtRollbackOp *pOp){ 1278 while( pOp ){ 1279 BtRollbackOp *pTmp = pOp->pNext; 1280 sqliteFree(pOp->pData); 1281 sqliteFree(pOp->pKey); 1282 sqliteFree(pOp); 1283 pOp = pTmp; 1284 } 1285 } 1286 1287 static int memRbtreeCommit(Rbtree* tree){ 1288 /* Just delete pTransRollback and pCheckRollback */ 1289 deleteRollbackList(tree->pCheckRollback); 1290 deleteRollbackList(tree->pTransRollback); 1291 tree->pTransRollback = 0; 1292 tree->pCheckRollback = 0; 1293 tree->pCheckRollbackTail = 0; 1294 tree->eTransState = TRANS_NONE; 1295 return SQLITE_OK; 1296 } 1297 1298 /* 1299 * Close the supplied Rbtree. Delete everything associated with it. 1300 */ 1301 static int memRbtreeClose(Rbtree* tree) 1302 { 1303 HashElem *p; 1304 memRbtreeCommit(tree); 1305 while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){ 1306 tree->eTransState = TRANS_ROLLBACK; 1307 memRbtreeDropTable(tree, sqliteHashKeysize(p)); 1308 } 1309 sqliteHashClear(&tree->tblHash); 1310 sqliteFree(tree); 1311 return SQLITE_OK; 1312 } 1313 1314 /* 1315 * Execute and delete the supplied rollback-list on pRbtree. 1316 */ 1317 static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList) 1318 { 1319 BtRollbackOp *pTmp; 1320 RbtCursor cur; 1321 int res; 1322 1323 cur.pRbtree = pRbtree; 1324 cur.wrFlag = 1; 1325 while( pList ){ 1326 switch( pList->eOp ){ 1327 case ROLLBACK_INSERT: 1328 cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab ); 1329 assert(cur.pTree); 1330 cur.iTree = pList->iTab; 1331 cur.eSkip = SKIP_NONE; 1332 memRbtreeInsert( &cur, pList->pKey, 1333 pList->nKey, pList->pData, pList->nData ); 1334 break; 1335 case ROLLBACK_DELETE: 1336 cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab ); 1337 assert(cur.pTree); 1338 cur.iTree = pList->iTab; 1339 cur.eSkip = SKIP_NONE; 1340 memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res); 1341 assert(res == 0); 1342 memRbtreeDelete( &cur ); 1343 break; 1344 case ROLLBACK_CREATE: 1345 btreeCreateTable(pRbtree, pList->iTab); 1346 break; 1347 case ROLLBACK_DROP: 1348 memRbtreeDropTable(pRbtree, pList->iTab); 1349 break; 1350 default: 1351 assert(0); 1352 } 1353 sqliteFree(pList->pKey); 1354 sqliteFree(pList->pData); 1355 pTmp = pList->pNext; 1356 sqliteFree(pList); 1357 pList = pTmp; 1358 } 1359 } 1360 1361 static int memRbtreeRollback(Rbtree* tree) 1362 { 1363 tree->eTransState = TRANS_ROLLBACK; 1364 execute_rollback_list(tree, tree->pCheckRollback); 1365 execute_rollback_list(tree, tree->pTransRollback); 1366 tree->pTransRollback = 0; 1367 tree->pCheckRollback = 0; 1368 tree->pCheckRollbackTail = 0; 1369 tree->eTransState = TRANS_NONE; 1370 return SQLITE_OK; 1371 } 1372 1373 static int memRbtreeBeginCkpt(Rbtree* tree) 1374 { 1375 if( tree->eTransState != TRANS_INTRANSACTION ) 1376 return SQLITE_ERROR; 1377 1378 assert( tree->pCheckRollback == 0 ); 1379 assert( tree->pCheckRollbackTail == 0 ); 1380 tree->eTransState = TRANS_INCHECKPOINT; 1381 return SQLITE_OK; 1382 } 1383 1384 static int memRbtreeCommitCkpt(Rbtree* tree) 1385 { 1386 if( tree->eTransState == TRANS_INCHECKPOINT ){ 1387 if( tree->pCheckRollback ){ 1388 tree->pCheckRollbackTail->pNext = tree->pTransRollback; 1389 tree->pTransRollback = tree->pCheckRollback; 1390 tree->pCheckRollback = 0; 1391 tree->pCheckRollbackTail = 0; 1392 } 1393 tree->eTransState = TRANS_INTRANSACTION; 1394 } 1395 return SQLITE_OK; 1396 } 1397 1398 static int memRbtreeRollbackCkpt(Rbtree* tree) 1399 { 1400 if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK; 1401 tree->eTransState = TRANS_ROLLBACK; 1402 execute_rollback_list(tree, tree->pCheckRollback); 1403 tree->pCheckRollback = 0; 1404 tree->pCheckRollbackTail = 0; 1405 tree->eTransState = TRANS_INTRANSACTION; 1406 return SQLITE_OK; 1407 } 1408 1409 #ifdef SQLITE_TEST 1410 static int memRbtreePageDump(Rbtree* tree, int pgno, int rec) 1411 { 1412 assert(!"Cannot call sqliteRbtreePageDump"); 1413 return SQLITE_OK; 1414 } 1415 1416 static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes) 1417 { 1418 assert(!"Cannot call sqliteRbtreeCursorDump"); 1419 return SQLITE_OK; 1420 } 1421 #endif 1422 1423 static struct Pager *memRbtreePager(Rbtree* tree) 1424 { 1425 return 0; 1426 } 1427 1428 /* 1429 ** Return the full pathname of the underlying database file. 1430 */ 1431 static const char *memRbtreeGetFilename(Rbtree *pBt){ 1432 return 0; /* A NULL return indicates there is no underlying file */ 1433 } 1434 1435 /* 1436 ** The copy file function is not implemented for the in-memory database 1437 */ 1438 static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){ 1439 return SQLITE_INTERNAL; /* Not implemented */ 1440 } 1441 1442 static BtOps sqliteRbtreeOps = { 1443 (int(*)(Btree*)) memRbtreeClose, 1444 (int(*)(Btree*,int)) memRbtreeSetCacheSize, 1445 (int(*)(Btree*,int)) memRbtreeSetSafetyLevel, 1446 (int(*)(Btree*)) memRbtreeBeginTrans, 1447 (int(*)(Btree*)) memRbtreeCommit, 1448 (int(*)(Btree*)) memRbtreeRollback, 1449 (int(*)(Btree*)) memRbtreeBeginCkpt, 1450 (int(*)(Btree*)) memRbtreeCommitCkpt, 1451 (int(*)(Btree*)) memRbtreeRollbackCkpt, 1452 (int(*)(Btree*,int*)) memRbtreeCreateTable, 1453 (int(*)(Btree*,int*)) memRbtreeCreateTable, 1454 (int(*)(Btree*,int)) memRbtreeDropTable, 1455 (int(*)(Btree*,int)) memRbtreeClearTable, 1456 (int(*)(Btree*,int,int,BtCursor**)) memRbtreeCursor, 1457 (int(*)(Btree*,int*)) memRbtreeGetMeta, 1458 (int(*)(Btree*,int*)) memRbtreeUpdateMeta, 1459 (char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck, 1460 (const char*(*)(Btree*)) memRbtreeGetFilename, 1461 (int(*)(Btree*,Btree*)) memRbtreeCopyFile, 1462 (struct Pager*(*)(Btree*)) memRbtreePager, 1463 #ifdef SQLITE_TEST 1464 (int(*)(Btree*,int,int)) memRbtreePageDump, 1465 #endif 1466 }; 1467 1468 static BtCursorOps sqliteRbtreeCursorOps = { 1469 (int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto, 1470 (int(*)(BtCursor*)) memRbtreeDelete, 1471 (int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert, 1472 (int(*)(BtCursor*,int*)) memRbtreeFirst, 1473 (int(*)(BtCursor*,int*)) memRbtreeLast, 1474 (int(*)(BtCursor*,int*)) memRbtreeNext, 1475 (int(*)(BtCursor*,int*)) memRbtreePrevious, 1476 (int(*)(BtCursor*,int*)) memRbtreeKeySize, 1477 (int(*)(BtCursor*,int,int,char*)) memRbtreeKey, 1478 (int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare, 1479 (int(*)(BtCursor*,int*)) memRbtreeDataSize, 1480 (int(*)(BtCursor*,int,int,char*)) memRbtreeData, 1481 (int(*)(BtCursor*)) memRbtreeCloseCursor, 1482 #ifdef SQLITE_TEST 1483 (int(*)(BtCursor*,int*)) memRbtreeCursorDump, 1484 #endif 1485 1486 }; 1487 1488 #endif /* SQLITE_OMIT_INMEMORYDB */ 1489