Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | fix a memory leak in btree_rb.c. (CVS 918) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
1e3d0d094776c2a429fa2a3eebc036a0 |
User & Date: | drh 2003-04-18 22:52:39.000 |
Context
2003-04-19
| ||
16:34 | Bug in WHERE clause processing fixed. Ticket #298. (CVS 919) (check-in: 9b619c98b5 user: drh tags: trunk) | |
2003-04-18
| ||
22:52 | fix a memory leak in btree_rb.c. (CVS 918) (check-in: 1e3d0d0947 user: drh tags: trunk) | |
17:45 | Fix for ticket #297 - bug in sqliteSortCompare(). (CVS 917) (check-in: 4ded1965eb user: drh tags: trunk) | |
Changes
Changes to src/btree_rb.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2003 Feb 4 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 2003 Feb 4 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree_rb.c,v 1.4 2003/04/18 22:52:39 drh Exp $ ** ** This file implements an in-core database using Red-Black balanced ** binary trees. ** ** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC. */ #include "btree.h" |
︙ | ︙ | |||
65 66 67 68 69 70 71 | */ #define ROLLBACK_INSERT 1 /* Insert a record */ #define ROLLBACK_DELETE 2 /* Delete a record */ #define ROLLBACK_CREATE 3 /* Create a table */ #define ROLLBACK_DROP 4 /* Drop a table */ struct Btree { | | | | | 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | */ #define ROLLBACK_INSERT 1 /* Insert a record */ #define ROLLBACK_DELETE 2 /* Delete a record */ #define ROLLBACK_CREATE 3 /* Create a table */ #define ROLLBACK_DROP 4 /* Drop a table */ struct Btree { BtOps *pOps; /* Function table */ int aMetaData[SQLITE_N_BTREE_META]; int next_idx; /* next available table index */ Hash tblHash; /* All created tables, by index */ u8 isAnonymous; /* True if this Btree is to be deleted when closed */ u8 eTransState; /* State of this Btree wrt transactions */ BtRollbackOp *pTransRollback; BtRollbackOp *pCheckRollback; BtRollbackOp *pCheckRollbackTail; }; /* ** Legal values for Btree.eTransState. */ #define TRANS_NONE 0 /* No transaction is in progress */ #define TRANS_INTRANSACTION 1 /* A transaction is in progress */ #define TRANS_INCHECKPOINT 2 /* A checkpoint is in progress */ #define TRANS_ROLLBACK 3 /* We are currently rolling back a checkpoint or * transaction. */ struct BtCursor { BtCursorOps *pOps; /* Function table */ Btree *pBtree; BtRbTree *pTree; int iTree; /* Index of pTree in pBtree */ BtRbNode *pNode; u8 eSkip; /* Determines if next step operation is a no-op */ }; |
︙ | ︙ | |||
294 295 296 297 298 299 300 | * 2 -> came from right */ int prev_step = 0; pNode = tree->pHead; while( pNode ){ switch( prev_step ){ case 0: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 | * 2 -> came from right */ int prev_step = 0; pNode = tree->pHead; while( pNode ){ switch( prev_step ){ case 0: if( pNode->pLeft ){ pNode = pNode->pLeft; }else{ prev_step = 1; } break; case 1: if( pNode->pRight ){ pNode = pNode->pRight; prev_step = 0; }else{ prev_step = 2; } break; case 2: /* Check red-black property (1) */ if( !pNode->isBlack && ( (pNode->pLeft && !pNode->pLeft->isBlack) || (pNode->pRight && !pNode->pRight->isBlack) ) ){ char buf[128]; sprintf(buf, "Red node with red child at %p\n", pNode); *msg = append_val(*msg, buf); *msg = append_node(*msg, tree->pHead, 0); *msg = append_val(*msg, "\n"); } /* Check red-black property (2) */ { int leftHeight = 0; int rightHeight = 0; if( pNode->pLeft ){ leftHeight += pNode->pLeft->nBlackHeight; leftHeight += (pNode->pLeft->isBlack?1:0); } if( pNode->pRight ){ rightHeight += pNode->pRight->nBlackHeight; rightHeight += (pNode->pRight->isBlack?1:0); } if( leftHeight != rightHeight ){ char buf[128]; sprintf(buf, "Different black-heights at %p\n", pNode); *msg = append_val(*msg, buf); *msg = append_node(*msg, tree->pHead, 0); *msg = append_val(*msg, "\n"); } pNode->nBlackHeight = leftHeight; } if( pNode->pParent ){ if( pNode == pNode->pParent->pLeft ) prev_step = 1; else prev_step = 2; } pNode = pNode->pParent; break; default: assert(0); } } } /* * Node pX has just been inserted into pTree (by code in sqliteBtreeInsert()). |
︙ | ︙ | |||
404 405 406 407 408 409 410 | pGrandparent->isBlack = 0; pUncle->isBlack = 1; pX->pParent->isBlack = 1; pX = pGrandparent; }else{ if( pX->pParent == pGrandparent->pLeft ){ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 | pGrandparent->isBlack = 0; pUncle->isBlack = 1; pX->pParent->isBlack = 1; pX = pGrandparent; }else{ if( pX->pParent == pGrandparent->pLeft ){ if( pX == pX->pParent->pRight ){ /* If pX is a right-child, do the following transform, essentially * to change pX into a left-child: * | | * G(b) G(b) * / \ / \ * P(r) U(b) X(r) U(b) * \ / * X(r) P(r) <-- new X * * BEFORE AFTER */ pX = pX->pParent; leftRotate(pTree, pX); } /* Do the following transform, which balances the tree :) * | | * G(b) P(b) * / \ / \ * P(r) U(b) X(r) G(r) * / \ * X(r) U(b) * * BEFORE AFTER */ assert( pGrandparent == pX->pParent->pParent ); pGrandparent->isBlack = 0; pX->pParent->isBlack = 1; rightRotate( pTree, pGrandparent ); }else{ /* This code is symetric to the illustrated case above. */ if( pX == pX->pParent->pLeft ){ pX = pX->pParent; rightRotate(pTree, pX); } assert( pGrandparent == pX->pParent->pParent ); pGrandparent->isBlack = 0; pX->pParent->isBlack = 1; leftRotate( pTree, pGrandparent ); } } } pTree->pHead->isBlack = 1; } /* |
︙ | ︙ | |||
466 467 468 469 470 471 472 | * / \ * X nil * * This function is only called if Z was black. In this case the red-black tree * properties have been violated, and pX has an "extra black". This function * performs rotations and color-changes to re-balance the tree. */ | > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 | * / \ * X nil * * This function is only called if Z was black. In this case the red-black tree * properties have been violated, and pX has an "extra black". This function * performs rotations and color-changes to re-balance the tree. */ static void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent) { BtRbNode *pSib; /* TODO: Comment this code! */ while( pX != pTree->pHead && (!pX || pX->isBlack) ){ if( pX == pParent->pLeft ){ pSib = pParent->pRight; if( pSib && !(pSib->isBlack) ){ pSib->isBlack = 1; pParent->isBlack = 0; leftRotate(pTree, pParent); pSib = pParent->pRight; } if( !pSib ){ pX = pParent; }else if( (!pSib->pLeft || pSib->pLeft->isBlack) && (!pSib->pRight || pSib->pRight->isBlack) ) { pSib->isBlack = 0; pX = pParent; }else{ if( (!pSib->pRight || pSib->pRight->isBlack) ){ if( pSib->pLeft ) pSib->pLeft->isBlack = 1; pSib->isBlack = 0; rightRotate( pTree, pSib ); pSib = pParent->pRight; } pSib->isBlack = pParent->isBlack; pParent->isBlack = 1; if( pSib->pRight ) pSib->pRight->isBlack = 1; leftRotate(pTree, pParent); pX = pTree->pHead; } }else{ pSib = pParent->pLeft; if( pSib && !(pSib->isBlack) ){ pSib->isBlack = 1; pParent->isBlack = 0; rightRotate(pTree, pParent); pSib = pParent->pLeft; } if( !pSib ){ pX = pParent; }else if( (!pSib->pLeft || pSib->pLeft->isBlack) && (!pSib->pRight || pSib->pRight->isBlack) ){ pSib->isBlack = 0; pX = pParent; }else{ if( (!pSib->pLeft || pSib->pLeft->isBlack) ){ if( pSib->pRight ) pSib->pRight->isBlack = 1; pSib->isBlack = 0; leftRotate( pTree, pSib ); pSib = pParent->pLeft; } pSib->isBlack = pParent->isBlack; pParent->isBlack = 1; if( pSib->pLeft ) pSib->pLeft->isBlack = 1; rightRotate(pTree, pParent); pX = pTree->pHead; } } pParent = pX->pParent; } if( pX ) pX->isBlack = 1; } |
︙ | ︙ | |||
569 570 571 572 573 574 575 | } int sqliteRBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree) { *ppBtree = (Btree *)sqliteMalloc(sizeof(Btree)); sqliteHashInit(&(*ppBtree)->tblHash, SQLITE_HASH_INT, 0); | | < < < | 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 | } int sqliteRBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree) { *ppBtree = (Btree *)sqliteMalloc(sizeof(Btree)); sqliteHashInit(&(*ppBtree)->tblHash, SQLITE_HASH_INT, 0); /* Create a binary tree for the SQLITE_MASTER table at location 2 */ btreeCreateTable(*ppBtree, 2); (*ppBtree)->next_idx = 3; (*ppBtree)->pOps = &sqliteBtreeOps; /* Set file type to 4; this is so that "attach ':memory:' as ...." does not ** think that the database in uninitialised and refuse to attach */ (*ppBtree)->aMetaData[2] = 4; |
︙ | ︙ | |||
616 617 618 619 620 621 622 | */ static int memBtreeDropTable(Btree* tree, int n) { BtRbTree *pTree; assert( tree->eTransState != TRANS_NONE ); memBtreeClearTable(tree, n); | | < | | | 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 | */ static int memBtreeDropTable(Btree* tree, int n) { BtRbTree *pTree; assert( tree->eTransState != TRANS_NONE ); memBtreeClearTable(tree, n); pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0); assert(pTree); sqliteFree(pTree); if( tree->eTransState != TRANS_ROLLBACK ){ BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); pRollbackOp->eOp = ROLLBACK_CREATE; pRollbackOp->iTab = n; btreeLogRollbackOp(tree, pRollbackOp); } return SQLITE_OK; } static int memBtreeKeyCompare(BtCursor* pCur, const void *pKey, int nKey, int nIgnore, int *pRes) { assert(pCur); if( !pCur->pNode ) { *pRes = -1; } else { if( (pCur->pNode->nKey - nIgnore) < 0 ){ *pRes = -1; }else{ *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore, pKey, nKey); } } return SQLITE_OK; } /* * Get a new cursor for table iTable of the supplied Btree. The wrFlag |
︙ | ︙ | |||
677 678 679 680 681 682 683 | * and the data is given by (pData,nData). The cursor is used only to * define what database the record should be inserted into. The cursor * is left pointing at the new record. * * If the key exists already in the tree, just replace the data. */ static int memBtreeInsert(BtCursor* pCur, const void *pKey, int nKey, | | | 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 | * and the data is given by (pData,nData). The cursor is used only to * define what database the record should be inserted into. The cursor * is left pointing at the new record. * * If the key exists already in the tree, just replace the data. */ static int memBtreeInsert(BtCursor* pCur, const void *pKey, int nKey, const void *pDataInput, int nData) { void * pData; int match; /* It is illegal to call sqliteBtreeInsert() if we are not in a transaction */ assert( pCur->pBtree->eTransState != TRANS_NONE ); |
︙ | ︙ | |||
711 712 713 714 715 716 717 | pNode->nKey = nKey; pNode->pKey = sqliteMalloc(nKey); memcpy(pNode->pKey, pKey, nKey); pNode->nData = nData; pNode->pData = pData; if( pCur->pNode ){ switch( match ){ | | | | | | | | | | | | | | 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 | pNode->nKey = nKey; pNode->pKey = sqliteMalloc(nKey); memcpy(pNode->pKey, pKey, nKey); pNode->nData = nData; pNode->pData = pData; if( pCur->pNode ){ switch( match ){ case -1: assert( !pCur->pNode->pRight ); pNode->pParent = pCur->pNode; pCur->pNode->pRight = pNode; break; case 1: assert( !pCur->pNode->pLeft ); pNode->pParent = pCur->pNode; pCur->pNode->pLeft = pNode; break; default: assert(0); } }else{ pCur->pTree->pHead = pNode; } /* Point the cursor at the node just inserted, as per SQLite requirements */ pCur->pNode = pNode; |
︙ | ︙ | |||
796 797 798 799 800 801 802 | pCur->pNode = pCur->pTree->pHead; *pRes = -1; while( pCur->pNode && *pRes ) { *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey); pTmp = pCur->pNode; switch( *pRes ){ case 1: /* cursor > key */ | | | | | | 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 | pCur->pNode = pCur->pTree->pHead; *pRes = -1; while( pCur->pNode && *pRes ) { *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey); pTmp = pCur->pNode; switch( *pRes ){ case 1: /* cursor > key */ pCur->pNode = pCur->pNode->pLeft; break; case -1: /* cursor < key */ pCur->pNode = pCur->pNode->pRight; break; } } /* If (pCur->pNode == NULL), then we have failed to find a match. Set * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the * last node traversed in the search. In either case the relation ship * between pTmp and the searched for key is already stored in *pRes. pTmp is |
︙ | ︙ | |||
890 891 892 893 894 895 896 | pCur->eSkip = SKIP_NEXT; if( res ){ memBtreeLast(pCur, &res); memBtreePrevious(pCur, &res); pCur->eSkip = SKIP_PREV; } if( pCur->pBtree->eTransState == TRANS_ROLLBACK ){ | | | | | 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 | pCur->eSkip = SKIP_NEXT; if( res ){ memBtreeLast(pCur, &res); memBtreePrevious(pCur, &res); pCur->eSkip = SKIP_PREV; } if( pCur->pBtree->eTransState == TRANS_ROLLBACK ){ sqliteFree(pZ->pKey); sqliteFree(pZ->pData); } } /* pZ now points at the node to be spliced out. This block does the * splicing. */ { BtRbNode **ppParentSlot = 0; assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */ pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight); if( pZ->pParent ){ assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight ); ppParentSlot = ((pZ == pZ->pParent->pLeft) ?&pZ->pParent->pLeft:&pZ->pParent->pRight); *ppParentSlot = pChild; }else{ pCur->pTree->pHead = pChild; } if( pChild ) pChild->pParent = pZ->pParent; } |
︙ | ︙ | |||
947 948 949 950 951 952 953 | } else if( pNode->pRight ){ pNode = pNode->pRight; } else { BtRbNode *pTmp = pNode->pParent; if( tree->eTransState == TRANS_ROLLBACK ){ | | | | | | | | | | | | | | 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 | } else if( pNode->pRight ){ pNode = pNode->pRight; } else { BtRbNode *pTmp = pNode->pParent; if( tree->eTransState == TRANS_ROLLBACK ){ sqliteFree( pNode->pKey ); sqliteFree( pNode->pData ); }else{ BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); pRollbackOp->eOp = ROLLBACK_INSERT; pRollbackOp->iTab = n; pRollbackOp->nKey = pNode->nKey; pRollbackOp->pKey = pNode->pKey; pRollbackOp->nData = pNode->nData; pRollbackOp->pData = pNode->pData; btreeLogRollbackOp(tree, pRollbackOp); } sqliteFree( pNode ); if( pTmp ){ if( pTmp->pLeft == pNode ) pTmp->pLeft = 0; else if( pTmp->pRight == pNode ) pTmp->pRight = 0; } pNode = pTmp; } } pTree->pHead = 0; return SQLITE_OK; |
︙ | ︙ | |||
1012 1013 1014 1015 1016 1017 1018 | static int memBtreeNext(BtCursor* pCur, int *pRes) { if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){ if( pCur->pNode->pRight ){ pCur->pNode = pCur->pNode->pRight; while( pCur->pNode->pLeft ) | | | | | | | | 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 | static int memBtreeNext(BtCursor* pCur, int *pRes) { if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){ if( pCur->pNode->pRight ){ pCur->pNode = pCur->pNode->pRight; while( pCur->pNode->pLeft ) pCur->pNode = pCur->pNode->pLeft; }else{ BtRbNode * pX = pCur->pNode; pCur->pNode = pX->pParent; while( pCur->pNode && (pCur->pNode->pRight == pX) ){ pX = pCur->pNode; pCur->pNode = pX->pParent; } } } pCur->eSkip = SKIP_NONE; if( !pCur->pNode ){ *pRes = 1; }else{ *pRes = 0; } return SQLITE_OK; } static int memBtreePrevious(BtCursor* pCur, int *pRes) { if( pCur->pNode && pCur->eSkip != SKIP_PREV ){ if( pCur->pNode->pLeft ){ pCur->pNode = pCur->pNode->pLeft; while( pCur->pNode->pRight ) pCur->pNode = pCur->pNode->pRight; }else{ BtRbNode * pX = pCur->pNode; pCur->pNode = pX->pParent; while( pCur->pNode && (pCur->pNode->pLeft == pX) ){ pX = pCur->pNode; pCur->pNode = pX->pParent; } } } pCur->eSkip = SKIP_NONE; if( !pCur->pNode ){ *pRes = 1; |
︙ | ︙ | |||
1148 1149 1150 1151 1152 1153 1154 | /* * Close the supplied Btree. Delete everything associated with it. */ static int memBtreeClose(Btree* tree) { HashElem *p; | | | < > | 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 | /* * Close the supplied Btree. Delete everything associated with it. */ static int memBtreeClose(Btree* tree) { HashElem *p; while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){ tree->eTransState = TRANS_ROLLBACK; memBtreeDropTable(tree, sqliteHashKeysize(p)); } sqliteHashClear(&tree->tblHash); sqliteFree(tree); return SQLITE_OK; } static int memBtreeSetCacheSize(Btree* tree, int sz) { return SQLITE_OK; |
︙ | ︙ | |||
1216 1217 1218 1219 1220 1221 1222 | BtCursor cur; int res; cur.pBtree = pBtree; while( pList ){ switch( pList->eOp ){ case ROLLBACK_INSERT: | | | | | | | | | | | | | | | | | | | | | | 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 | BtCursor cur; int res; cur.pBtree = pBtree; while( pList ){ switch( pList->eOp ){ case ROLLBACK_INSERT: cur.pTree = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab ); assert(cur.pTree); cur.iTree = pList->iTab; cur.eSkip = SKIP_NONE; memBtreeInsert( &cur, pList->pKey, pList->nKey, pList->pData, pList->nData ); break; case ROLLBACK_DELETE: cur.pTree = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab ); assert(cur.pTree); cur.iTree = pList->iTab; cur.eSkip = SKIP_NONE; memBtreeMoveto(&cur, pList->pKey, pList->nKey, &res); assert(res == 0); memBtreeDelete( &cur ); break; case ROLLBACK_CREATE: btreeCreateTable(pBtree, pList->iTab); break; case ROLLBACK_DROP: memBtreeDropTable(pBtree, pList->iTab); break; default: assert(0); } sqliteFree(pList->pKey); sqliteFree(pList->pData); pTmp = pList->pNext; sqliteFree(pList); pList = pTmp; } |
︙ | ︙ |