SQLite4  Check-in [1ecbf355e3]

static int btCsrDescend(BtCursor *pCsr, u32 pgno, BtPage **ppPg){
  int rc;
  if( pCsr->nPg>=BT_MAX_DEPTH ){
    rc = btErrorBkpt(SQLITE4_CORRUPT);
  }else{
    assert( pCsr->nPg>=0 );
    rc = sqlite4BtPageGet(pCsr->base.pDb->pPager, pgno, ppPg);
    assert( ((*ppPg)==0)==(rc!=SQLITE4_OK) );

    pCsr->apPage[pCsr->nPg] = *ppPg;
    pCsr->nPg++;

  }
  return rc;
}

/*
** Move the cursor from the current page to the parent. Return 
** SQLITE4_NOTFOUND if the cursor already points to the root page,

  BtCursor *pCsr,                 /* Cursor object to seek */
  u8 *aPrefix,                    /* 8-byte key prefix, or NULL */
  const void *pK,                 /* Key to seek for */
  int nK,                         /* Size of key pK in bytes */
  int eSeek,                      /* Seek mode (a BT_SEEK_XXX constant) */
  int eCsrseek
){
  BtPager *pPager = pCsr->base.pDb->pPager;
  const int pgsz = sqlite4BtPagerPagesize(pPager);
  u32 pgno;                       /* Page number for next page to load */
  int rc;                         /* Return Code */

  assert( eSeek==BT_SEEK_EQ || eCsrseek!=BT_CSRSEEK_RESEEK );
  assert( eSeek==BT_SEEK_GE || eCsrseek!=BT_CSRSEEK_UPDATE );

  /* Reset the cursor */
  btCsrReset(pCsr, 0);

  /* Figure out the root page number */
  assert( pCsr->iRoot>1 && pCsr->nPg==0 );
  pgno = pCsr->iRoot;

  while( 1 ){
    /* Load page number pgno into the b-tree cursor. */
    BtPage *pPg;
    rc = sqlite4BtPageGet(pPager, pgno, &pPg);
    pCsr->apPage[pCsr->nPg++] = pPg;

    if( rc==SQLITE4_OK ){
      int nCell;                  /* Number of cells on this page */
      int iHi;                    /* pK/nK is <= than cell iHi */
      int iLo;                    /* pK/nK is > than cell (iLo-1) */
      int res;                    /* Result of comparison */

      u8 *aData = btPageData(pPg);
      u16 *aCellPtr = (u16*)btCellPtrFind(aData, pgsz, 0);
      int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);

      iLo = 0;
      iHi = nCell = btCellCount(aData, pgsz);

      if( btFlags(aData) & BT_PGFLAGS_LARGEKEYS ){
        while( iHi>iLo ){
          int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
          u8 *pCell = &aData[btGetU16((u8*)(aCellPtr - iTst))];


          pCsr->aiCell[pCsr->nPg-1] = iTst;
          rc = btCellKeyCompare(pCsr, bLeaf, 0, pK, nK, &res);


          if( res<0 ){
            /* Cell iTst is SMALLER than pK/nK */
            iLo = iTst+1;
          }else{
            /* Cell iTst is LARGER than (or equal to) pK/nK */
            iHi = iTst;
            if( res==0 ){
              iHi += !bLeaf;
              break;
            }
          }
        }
      }else{
        while( iHi>iLo ){
          int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
          u8 *pCell = &aData[btGetU16((u8*)(aCellPtr - iTst))];
          int n = *pCell;


          res = memcmp(&pCell[1], pK, MIN(nK, n));
          if( res<0 || (res==0 && (res = n - nK)<0) ){
            /* Cell iTst is SMALLER than pK/nK */
            iLo = iTst+1;
          }else{
            /* Cell iTst is LARGER than (or equal to) pK/nK */
            iHi = iTst;
            if( res==0 ){
              iHi += !bLeaf;
              break;
            }
          }
        }
      }
      if( rc!=SQLITE4_OK ) break;


      pCsr->aiCell[pCsr->nPg-1] = iHi;

      if( bLeaf==0 ){
        if( iHi==nCell ) pgno = btGetU32(&aData[1]);
        else{
          u8 *pCell = btCellFind(aData, pgsz, iHi);
          pgno = btGetU32(&pCell[1 + (int)*pCell]);
        }
        if( pCsr->nPg==BT_MAX_DEPTH ){
          rc = btErrorBkpt(SQLITE4_CORRUPT);
          break;
        }
      }else{


        if( nCell==0 ){
          rc = SQLITE4_NOTFOUND;
        }else if( res!=0 ){
          if( eSeek==BT_SEEK_EQ ){
            if( eCsrseek==BT_CSRSEEK_RESEEK ){
              rc = SQLITE4_OK;

                  rc = sqlite4BtCsrNext((bt_cursor*)pCsr);
                }
              }
            }
            if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
          }
        }

        /* The cursor now points to a leaf page. Break out of the loop. */
        break;
      }
    }
  }

  if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
    btCsrReset(pCsr, 0);
  }

    pCsr->aiCell[1] = pCsr->aiCell[0];
    pCsr->apPage[1] = pNew;
    pCsr->aiCell[0] = 0;
  }

  return rc;
}

/*
** The cursor passed as the first argument points to a leaf page into
** which the array of KV pairs specified by the second and third arguments
** would be inserted, except that there is insufficient free space on
** the page.
**
** If nKV==1, the tree is more than one level high (i.e. the root is not a
** leaf) and the new key is larger than all existing keys on the page,
** handle this in the same way as an SQLite3 "quick-balance" operation.
** Return SQLITE4_OK if successful, or an error code if an error occurs.
**
** If the quick-balance is not attempted, return SQLITE4_NOTFOUND.
*/
static int btTryAppend(BtCursor *pCsr, int nKV, KeyValue *apKV){
  int rc = SQLITE4_NOTFOUND;
  if( nKV==1 && pCsr->nPg>1 ){
    bt_db *pDb = pCsr->base.pDb;
    const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
    BtPage *pOld = pCsr->apPage[pCsr->nPg-1];
    u8 *aData = btPageData(pOld);
    int nCell = btCellCount(aData, pgsz);
    if( nCell==pCsr->aiCell[pCsr->nPg-1] ){
      KeyValue kv;
      BtPage *pNew = 0;
      rc = btAllocateNonOverflow(pDb, &pNew);
      if( rc==SQLITE4_OK ){
        aData = btPageData(pNew);
        btPutU16(&aData[pgsz-2], 0);
        aData[0] = 0x00;
        pCsr->apPage[pCsr->nPg-1] = pNew;
        pCsr->aiCell[pCsr->nPg-1] = 0;
        rc = btInsertAndBalance(pCsr, 1, apKV);
      }
      if( rc==SQLITE4_OK ){
        rc = btSetChildPgno(pDb, 
            pCsr->apPage[pCsr->nPg-2], pCsr->aiCell[pCsr->nPg-2], 
            sqlite4BtPagePgno(pNew)
        );
      }
      if( rc==SQLITE4_OK ){
        assert( pCsr->apPage[pCsr->nPg-1]==pNew );
        btPrefixKey(pgsz, pOld, pNew, &kv);
        kv.pgno = sqlite4BtPagePgno(pOld);
        kv.pV = 0;
        kv.nV = 0;
        kv.eType = 0;
        rc = btCsrAscend(pCsr, 1);
      }
      if( rc==SQLITE4_OK ){
        rc = btInsertAndBalance(pCsr, 1, &kv);
      }
      if( pNew ) sqlite4BtPageRelease(pOld);
    }
  }
  return rc;
}

/*
** The cursor currently points to a cell on a b-tree page that may or
** may not be a leaf page. This routine modifies the contents of that
** page, balancing the b-tree if necessary. The page is modified as
** follows:
**

        pHdr->iSubBlock = 0;
      }
    }
    if( rc==SQLITE4_OK && pCsr->nPg==1 ){
      rc = btExtendTree(pCsr);
    }
    if( rc==SQLITE4_OK ){
      if( bLeaf==0 || SQLITE4_NOTFOUND==(rc = btTryAppend(pCsr, nKV, apKV)) ){
        rc = btBalance(pCsr, bLeaf, nKV, apKV);
      }
    }
  }

  return rc;
}

static int btDeleteFromPage(BtCursor *pCsr, int nDel){

  BtPage *pNext;
  assert( p->iTransactionLevel>=2 );

  rc = btPagerDbhdrFlush(p);
  btCloseSavepoints(p, 2, 0);

  for(pPg=p->pDirty; rc==SQLITE4_OK && pPg; pPg=pNext){
    int nPg;
    pNext = pPg->pNextDirty;
    nPg = ((pNext==0) ? p->pHdr->nPg : 0);
    rc = sqlite4BtLogWrite(p->pLog, pPg->pgno, pPg->aData, nPg);
    pPg->flags &= ~(BT_PAGE_DIRTY);
    pPg->pNextDirty = 0;




    if( pPg->nRef==0 ) btLruAdd(p, pPg);
  }
  p->pDirty = pPg;
  sqlite4BtLogSnapshotEndWrite(p->pLog);

  nLogsize = sqlite4BtLogSize(p->pLog);

** The sqlite4_mutex_alloc() routine allocates a new
** mutex and returns a pointer to it.  If it returns NULL
** that means that a mutex could not be allocated. 
*/
static sqlite4_mutex *debugMutexAlloc(void *pX, int id){
  sqlite4_env *pEnv = (sqlite4_env*)pX;
  sqlite4DebugMutex *pNew = 0;

  static sqlite4DebugMutex aStaticMutex[] = {
    { { 0 }, 0, 0, 0 }
  };

  if( id==SQLITE4_MUTEX_STATIC_KV ){
    pNew = &aStaticMutex[0];
    pNew->pEnv = pEnv;
    pNew->base.pMutexMethods = sqlite4NoopMutex();
  }else{
    pNew = sqlite4Malloc(pEnv, sizeof(*pNew));
    if( pNew ){
      pNew->id = id;
      pNew->cnt = 0;
      pNew->pEnv = pEnv;
      pNew->base.pMutexMethods = sqlite4NoopMutex();
    }
  }
  return (sqlite4_mutex*)pNew;
}

/*
** This routine deallocates a previously allocated mutex.
*/