Lines Matching refs:tree
119 RbtCursor *pCursors; /* All cursors pointing to this tree */
120 BtRbNode *pHead; /* Head of the tree, or NULL */
129 BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
143 static int memRbtreeClearTable(Rbtree* tree, int n);
196 * Perform the LEFT-rotate transformation on node X of tree pTree. This
228 * Perform the RIGHT-rotate transformation on node X of tree pTree. This
280 * a problem with a red-black binary tree.
324 * Check the following properties of the red-black tree:
331 static void check_redblack_tree(BtRbTree * tree, char ** msg)
340 pNode = tree->pHead;
367 *msg = append_node(*msg, tree->pHead, 0);
387 *msg = append_node(*msg, tree->pHead, 0);
407 * of the red-black tree properties. This function performs rotations and
408 * color changes to rebalance the tree
413 * inserted in the tree. If the parent of pX exists (pX is not the root
414 * node) and is red, then the properties of the red-black tree are
418 * with a red parent. In all other respects the tree is a legal red-black
419 * binary tree. */
470 /* Do the following transform, which balances the tree :)
512 * This function is only called if Z was black. In this case the red-black tree
514 * performs rotations and color-changes to re-balance the tree.
586 * Create table n in tree pRbtree. Table n must not exist.
626 /* Create a binary tree for the SQLITE_MASTER table at location 2 */
647 static int memRbtreeCreateTable(Rbtree* tree, int* n)
649 assert( tree->eTransState != TRANS_NONE );
651 *n = tree->next_idx++;
652 btreeCreateTable(tree, *n);
657 if( tree->eTransState != TRANS_ROLLBACK ){
662 btreeLogRollbackOp(tree, pRollbackOp);
671 static int memRbtreeDropTable(Rbtree* tree, int n)
674 assert( tree->eTransState != TRANS_NONE );
676 memRbtreeClearTable(tree, n);
677 pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
682 if( tree->eTransState != TRANS_ROLLBACK ){
687 btreeLogRollbackOp(tree, pRollbackOp);
718 Rbtree* tree,
724 assert(tree);
727 pCur->pTree = sqliteHashFind(&tree->tblHash, 0, iTable);
729 pCur->pRbtree = tree;
746 * If the key exists already in the tree, just replace the data.
775 * the data associated with the entry, we don't need to manipulate the tree.
833 /* No need to insert a new node in the tree, as the key already exists.
898 * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
956 /* First do a standard binary-tree delete (node pZ is to be deleted). How
1014 * NULL if pZ has no children. If pZ is black, and not the tree root, then we
1016 * leaf" property of the red-black tree. The code in do_delete_balancing()
1029 static int memRbtreeClearTable(Rbtree* tree, int n)
1034 pTree = sqliteHashFind(&tree->tblHash, 0, n);
1047 if( tree->eTransState == TRANS_ROLLBACK ){
1059 btreeLogRollbackOp(tree, pRollbackOp);
1228 static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
1230 memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
1234 static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
1236 memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
1242 * binary tree. If an error is found, return an explanation of the problem in
1245 static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot)
1250 for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
1258 static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
1267 static int memRbtreeBeginTrans(Rbtree* tree)
1269 if( tree->eTransState != TRANS_NONE )
1272 assert( tree->pTransRollback == 0 );
1273 tree->eTransState = TRANS_INTRANSACTION;
1290 static int memRbtreeCommit(Rbtree* tree){
1292 deleteRollbackList(tree->pCheckRollback);
1293 deleteRollbackList(tree->pTransRollback);
1294 tree->pTransRollback = 0;
1295 tree->pCheckRollback = 0;
1296 tree->pCheckRollbackTail = 0;
1297 tree->eTransState = TRANS_NONE;
1304 static int memRbtreeClose(Rbtree* tree)
1307 memRbtreeCommit(tree);
1308 while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
1309 tree->eTransState = TRANS_ROLLBACK;
1310 memRbtreeDropTable(tree, sqliteHashKeysize(p));
1312 sqliteHashClear(&tree->tblHash);
1313 sqliteFree(tree);
1364 static int memRbtreeRollback(Rbtree* tree)
1366 tree->eTransState = TRANS_ROLLBACK;
1367 execute_rollback_list(tree, tree->pCheckRollback);
1368 execute_rollback_list(tree, tree->pTransRollback);
1369 tree->pTransRollback = 0;
1370 tree->pCheckRollback = 0;
1371 tree->pCheckRollbackTail = 0;
1372 tree->eTransState = TRANS_NONE;
1376 static int memRbtreeBeginCkpt(Rbtree* tree)
1378 if( tree->eTransState != TRANS_INTRANSACTION )
1381 assert( tree->pCheckRollback == 0 );
1382 assert( tree->pCheckRollbackTail == 0 );
1383 tree->eTransState = TRANS_INCHECKPOINT;
1387 static int memRbtreeCommitCkpt(Rbtree* tree)
1389 if( tree->eTransState == TRANS_INCHECKPOINT ){
1390 if( tree->pCheckRollback ){
1391 tree->pCheckRollbackTail->pNext = tree->pTransRollback;
1392 tree->pTransRollback = tree->pCheckRollback;
1393 tree->pCheckRollback = 0;
1394 tree->pCheckRollbackTail = 0;
1396 tree->eTransState = TRANS_INTRANSACTION;
1401 static int memRbtreeRollbackCkpt(Rbtree* tree)
1403 if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
1404 tree->eTransState = TRANS_ROLLBACK;
1405 execute_rollback_list(tree, tree->pCheckRollback);
1406 tree->pCheckRollback = 0;
1407 tree->pCheckRollbackTail = 0;
1408 tree->eTransState = TRANS_INTRANSACTION;
1413 static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
1426 static struct Pager *memRbtreePager(Rbtree* tree)