Annotation of embedaddon/php/ext/sqlite/libsqlite/src/btree_rb.c, revision 1.1
1.1 ! misho 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 195361 2005-09-07 15:11:33Z iliaa $
! 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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to btree_rb.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / sqlite / libsqlite / src