/* * A child of pParent, which in turn had child pX, has just been removed from  * pTree (the figure below depicts the operation, Z is being removed). pParent * or pX, or both may be NULL.   *                |           | *                P           P *               / \         / \ *              Z           X *             / \ *            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;}/* * Create table n in tree pRbtree. Table n must not exist. */static void btreeCreateTable(Rbtree* pRbtree, int n){  BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));  sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);}/* * Log a single "rollback-op" for the given Rbtree. See comments for struct * BtRollbackOp. */static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp){  assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||      pRbtree->eTransState == TRANS_INTRANSACTION );  if( pRbtree->eTransState == TRANS_INTRANSACTION ){    pRollbackOp->pNext = pRbtree->pTransRollback;    pRbtree->pTransRollback = pRollbackOp;  }  if( pRbtree->eTransState == TRANS_INCHECKPOINT ){    if( !pRbtree->pCheckRollback ){      pRbtree->pCheckRollbackTail = pRollbackOp;    }    pRollbackOp->pNext = pRbtree->pCheckRollback;    pRbtree->pCheckRollback = pRollbackOp;  }}int sqliteRbtreeOpen(  const char *zFilename,  int mode,  int nPg,  Btree **ppBtree){  Rbtree **ppRbtree = (Rbtree**)ppBtree;  *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));  if( sqlite_malloc_failed ) goto open_no_mem;  sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);  /* Create a binary tree for the SQLITE_MASTER table at location 2 */  btreeCreateTable(*ppRbtree, 2);  if( sqlite_malloc_failed ) goto open_no_mem;  (*ppRbtree)->next_idx = 3;  (*ppRbtree)->pOps = &sqliteRbtreeOps;  /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not  ** think that the database in uninitialised and refuse to attach  */  (*ppRbtree)->aMetaData[2] = 4;    return SQLITE_OK;open_no_mem:  *ppBtree = 0;  return SQLITE_NOMEM;}/* * Create a new table in the supplied Rbtree. Set *n to the new table number. * Return SQLITE_OK if the operation is a success. */static int memRbtreeCreateTable(Rbtree* tree, int* n){  assert( tree->eTransState != TRANS_NONE );  *n = tree->next_idx++;  btreeCreateTable(tree, *n);  if( sqlite_malloc_failed ) return SQLITE_NOMEM;  /* Set up the rollback structure (if we are not doing this as part of a   * rollback) */  if( tree->eTransState != TRANS_ROLLBACK ){    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));    if( pRollbackOp==0 ) return SQLITE_NOMEM;    pRollbackOp->eOp = ROLLBACK_DROP;    pRollbackOp->iTab = *n;    btreeLogRollbackOp(tree, pRollbackOp);  }  return SQLITE_OK;}/* * Delete table n from the supplied Rbtree.  */static int memRbtreeDropTable(Rbtree* tree, int n){  BtRbTree *pTree;  assert( tree->eTransState != TRANS_NONE );  memRbtreeClearTable(tree, n);  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);  assert(pTree);  assert( pTree->pCursors==0 );  sqliteFree(pTree);  if( tree->eTransState != TRANS_ROLLBACK ){    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));    if( pRollbackOp==0 ) return SQLITE_NOMEM;    pRollbackOp->eOp = ROLLBACK_CREATE;    pRollbackOp->iTab = n;    btreeLogRollbackOp(tree, pRollbackOp);  }  return SQLITE_OK;}static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,                                 int nIgnore, int *pRes){  assert(pCur);  if( !pCur->pNode ) {    *pRes = -1;  } else {    if( (pCur->pNode->nKey - nIgnore) < 0 ){      *pRes = -1;    }else{      *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore,           pKey, nKey);    }  }  return SQLITE_OK;}/* * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag * parameter indicates that the cursor is open for writing. * * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0. */static int memRbtreeCursor(  Rbtree* tree,  int iTable,  int wrFlag,  RbtCursor **ppCur){  RbtCursor *pCur;  assert(tree);  pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));  if( sqlite_malloc_failed ) return SQLITE_NOMEM;  pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);  assert( pCur->pTree );  pCur->pRbtree = tree;  pCur->iTree  = iTable;  pCur->pOps = &sqliteRbtreeCursorOps;  pCur->wrFlag = wrFlag;  pCur->pShared = pCur->pTree->pCursors;  pCur->pTree->pCursors = pCur;  assert( (*ppCur)->pTree );  return SQLITE_OK;}/* * Insert a new record into the Rbtree.  The key is given by (pKey,nKey) * and the data is given by (pData,nData).  The cursor is used only to * define what database the record should be inserted into.  The cursor * is left pointing at the new record. * * If the key exists already in the tree, just replace the data.  */static int memRbtreeInsert(  RbtCursor* pCur,  const void *pKey,  int nKey,  const void *pDataInput,  int nData){  void * pData;  int match;  /* It is illegal to call sqliteRbtreeInsert() if we are  ** not in a transaction */  assert( pCur->pRbtree->eTransState != TRANS_NONE );  /* Make sure some other cursor isn't trying to read this same table */  if( checkReadLocks(pCur) ){    return SQLITE_LOCKED; /* The table pCur points to has a read lock */  }  /* Take a copy of the input data now, in case we need it for the    * replace case */  pData = sqliteMallocRaw(nData);  if( sqlite_malloc_failed ) return SQLITE_NOMEM;  memcpy(pData, pDataInput, nData);  /* Move the cursor to a node near the key to be inserted. If the key already   * exists in the table, then (match == 0). In this case we can just replace   * the data associated with the entry, we don't need to manipulate the tree.   *    * If there is no exact match, then the cursor points at what would be either   * the predecessor (match == -1) or successor (match == 1) of the   * searched-for key, were it to be inserted. The new node becomes a child of   * this node.   *    * The new node is initially red.   */  memRbtreeMoveto( pCur, pKey, nKey, &match);  if( match ){    BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));    if( pNode==0 ) return SQLITE_NOMEM;    pNode->nKey = nKey;    pNode->pKey = sqliteMallocRaw(nKey);    if( sqlite_malloc_failed ) return SQLITE_NOMEM;    memcpy(pNode->pKey, pKey, nKey);    pNode->nData = nData;    pNode->pData = pData;     if( pCur->pNode ){      switch( match ){        case -1:          assert( !pCur->pNode->pRight );          pNode->pParent = pCur->pNode;          pCur->pNode->pRight = pNode;          break;        case 1:          assert( !pCur->pNode->pLeft );          pNode->pParent = pCur->pNode;          pCur->pNode->pLeft = pNode;          break;        default:          assert(0);      }    }else{      pCur->pTree->pHead = pNode;    }    /* Point the cursor at the node just inserted, as per SQLite requirements */    pCur->pNode = pNode;    /* A new node has just been inserted, so run the balancing code */    do_insert_balancing(pCur->pTree, pNode);    /* Set up a rollback-op in case we have to roll this operation back */    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );      if( pOp==0 ) return SQLITE_NOMEM;      pOp->eOp = ROLLBACK_DELETE;      pOp->iTab = pCur->iTree;      pOp->nKey = pNode->nKey;      pOp->pKey = sqliteMallocRaw( pOp->nKey );      if( sqlite_malloc_failed ) return SQLITE_NOMEM;      memcpy( pOp->pKey, pNode->pKey, pOp->nKey );      btreeLogRollbackOp(pCur->pRbtree, pOp);    }  }else{     /* No need to insert a new node in the tree, as the key already exists.     * Just clobber the current nodes data. */    /* Set up a rollback-op in case we have to roll this operation back */    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );      if( pOp==0 ) return SQLITE_NOMEM;      pOp->iTab = pCur->iTree;      pOp->nKey = pCur->pNode->nKey;      pOp->pKey = sqliteMallocRaw( pOp->nKey );      if( sqlite_malloc_failed ) return SQLITE_NOMEM;      memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );      pOp->nData = pCur->pNode->nData;      pOp->pData = pCur->pNode->pData;      pOp->eOp = ROLLBACK_INSERT;      btreeLogRollbackOp(pCur->pRbtree, pOp);    }else{      sqliteFree( pCur->pNode->pData );    }    /* Actually clobber the nodes data */    pCur->pNode->pData = pData;    pCur->pNode->nData = nData;  }  return SQLITE_OK;}/* Move the cursor so that it points to an entry near pKey.** Return a success code.****     *pRes<0      The cursor is left pointing at an entry that**                  is smaller than pKey or if the table is empty**                  and the cursor is therefore left point to nothing.****     *pRes==0     The cursor is left pointing at an entry that**                  exactly matches pKey.****     *pRes>0      The cursor is left pointing at an entry that**                  is larger than pKey.*/static int memRbtreeMoveto(  RbtCursor* pCur,  const void *pKey,  int nKey,  int *pRes){  BtRbNode *pTmp = 0;  pCur->pNode = pCur->pTree->pHead;  *pRes = -1;  while( pCur->pNode && *pRes ) {    *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);    pTmp = pCur->pNode;    switch( *pRes ){      case 1:    /* cursor > key */        pCur->pNode = pCur->pNode->pLeft;        break;      case -1:   /* cursor < key */        pCur->pNode = pCur->pNode->pRight;        break;    }  }   /* If (pCur->pNode == NULL), then we have failed to find a match. Set   * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the   * last node traversed in the search. In either case the relation ship   * between pTmp and the searched for key is already stored in *pRes. pTmp is   * either the successor or predecessor of the key we tried to move to. */  if( !pCur->pNode ) pCur->pNode = pTmp;  pCur->eSkip = SKIP_NONE;  return SQLITE_OK;}/*** Delete the entry that the cursor is pointing to.**** The cursor is left pointing at either the next or the previous** entry.  If the cursor is left pointing to the next entry, then ** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to ** sqliteRbtreeNext() to be a no-op.  That way, you can always call** sqliteRbtreeNext() after a delete and the cursor will be left** pointing to the first entry after the deleted entry.  Similarly,** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to** the entry prior to the deleted entry so that a subsequent call to** sqliteRbtreePrevious() will always leave the cursor pointing at the** entry immediately before the one that was deleted.*/static int memRbtreeDelete(RbtCursor* pCur){  BtRbNode *pZ;      /* The one being deleted */  BtRbNode *pChild;  /* The child of the spliced out node */  /* It is illegal to call sqliteRbtreeDelete() if we are  ** not in a transaction */  assert( pCur->pRbtree->eTransState != TRANS_NONE );  /* Make sure some other cursor isn't trying to read this same table */  if( checkReadLocks(pCur) ){    return SQLITE_LOCKED; /* The table pCur points to has a read lock */  }  pZ = pCur->pNode;  if( !pZ ){    return SQLITE_OK;  }  /* If we are not currently doing a rollback, set up a rollback op for this    * deletion */  if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){    BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );    if( pOp==0 ) return SQLITE_NOMEM;    pOp->iTab = pCur->iTree;    pOp->nKey = pZ->nKey;    pOp->pKey = pZ->pKey;    pOp->nData = pZ->nData;    pOp->pData = pZ->pData;    pOp->eOp = ROLLBACK_INSERT;    btreeLogRollbackOp(pCur->pRbtree, pOp);  }  /* First do a standard binary-tree delete (node pZ is to be deleted). How   * to do this depends on how many children pZ has:   *   * If pZ has no children or one child, then splice out pZ.  If pZ has two   * children, splice out the successor of pZ and replace the key and data of   * pZ with the key and data of the spliced out successor.  */  if( pZ->pLeft && pZ->pRight ){    BtRbNode *pTmp;    int dummy;    pCur->eSkip = SKIP_NONE;    memRbtreeNext(pCur, &dummy);    assert( dummy == 0 );    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){      sqliteFree(pZ->pKey);      sqliteFree(pZ->pData);    }    pZ->pData = pCur->pNode->pData;    pZ->nData = pCur->pNode->nData;    pZ->pKey = pCur->pNode->pKey;    pZ->nKey = pCur->pNode->nKey;    pTmp = pZ;    pZ = pCur->pNode;    pCur->pNode = pTmp;    pCur->eSkip = SKIP_NEXT;  }else{    int res;    pCur->eSkip = SKIP_NONE;    memRbtreeNext(pCur, &res);    pCur->eSkip = SKIP_NEXT;    if( res ){      memRbtreeLast(pCur, &res);      memRbtreePrevious(pCur, &res);      pCur->eSkip = SKIP_PREV;    }    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){        sqliteFree(pZ->pKey);        sqliteFree(pZ->pData);    }  }  /* pZ now points at the node to be spliced out. This block does the    * splicing. */