- /*
- ** 2005 June 16
- **
- ** 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.
- **
- *************************************************************************
- ** This file implements a FIFO queue of rowids used for processing
- ** UPDATE and DELETE statements.
- */
- #include "sqliteInt.h"
- #include "vdbeInt.h"
- /*
- ** Constants FIFOSIZE_FIRST and FIFOSIZE_MAX are the initial
- ** number of entries in a fifo page and the maximum number of
- ** entries in a fifo page.
- */
- #define FIFOSIZE_FIRST (((128-sizeof(FifoPage))/8)+1)
- #ifdef SQLITE_MALLOC_SOFT_LIMIT
- # define FIFOSIZE_MAX (((SQLITE_MALLOC_SOFT_LIMIT-sizeof(FifoPage))/8)+1)
- #else
- # define FIFOSIZE_MAX (((262144-sizeof(FifoPage))/8)+1)
- #endif
- /*
- ** Allocate a new FifoPage and return a pointer to it. Return NULL if
- ** we run out of memory. Leave space on the page for nEntry entries.
- */
- static FifoPage *allocateFifoPage(int nEntry){
- FifoPage *pPage;
- if( nEntry>FIFOSIZE_MAX ){
- nEntry = FIFOSIZE_MAX;
- }
- pPage = sqlite3_malloc( sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );
- if( pPage ){
- pPage->nSlot = nEntry;
- pPage->iWrite = 0;
- pPage->iRead = 0;
- pPage->pNext = 0;
- }
- return pPage;
- }
- /*
- ** Initialize a Fifo structure.
- */
- void sqlite3VdbeFifoInit(Fifo *pFifo){
- memset(pFifo, 0, sizeof(*pFifo));
- }
- /*
- ** Push a single 64-bit integer value into the Fifo. Return SQLITE_OK
- ** normally. SQLITE_NOMEM is returned if we are unable to allocate
- ** memory.
- */
- int sqlite3VdbeFifoPush(Fifo *pFifo, i64 val){
- FifoPage *pPage;
- pPage = pFifo->pLast;
- if( pPage==0 ){
- pPage = pFifo->pLast = pFifo->pFirst = allocateFifoPage(FIFOSIZE_FIRST);
- if( pPage==0 ){
- return SQLITE_NOMEM;
- }
- }else if( pPage->iWrite>=pPage->nSlot ){
- pPage->pNext = allocateFifoPage(pFifo->nEntry);
- if( pPage->pNext==0 ){
- return SQLITE_NOMEM;
- }
- pPage = pFifo->pLast = pPage->pNext;
- }
- pPage->aSlot[pPage->iWrite++] = val;
- pFifo->nEntry++;
- return SQLITE_OK;
- }
- /*
- ** Extract a single 64-bit integer value from the Fifo. The integer
- ** extracted is the one least recently inserted. If the Fifo is empty
- ** return SQLITE_DONE.
- */
- int sqlite3VdbeFifoPop(Fifo *pFifo, i64 *pVal){
- FifoPage *pPage;
- if( pFifo->nEntry==0 ){
- return SQLITE_DONE;
- }
- assert( pFifo->nEntry>0 );
- pPage = pFifo->pFirst;
- assert( pPage!=0 );
- assert( pPage->iWrite>pPage->iRead );
- assert( pPage->iWrite<=pPage->nSlot );
- assert( pPage->iRead<pPage->nSlot );
- assert( pPage->iRead>=0 );
- *pVal = pPage->aSlot[pPage->iRead++];
- pFifo->nEntry--;
- if( pPage->iRead>=pPage->iWrite ){
- pFifo->pFirst = pPage->pNext;
- sqlite3_free(pPage);
- if( pFifo->nEntry==0 ){
- assert( pFifo->pLast==pPage );
- pFifo->pLast = 0;
- }else{
- assert( pFifo->pFirst!=0 );
- }
- }else{
- assert( pFifo->nEntry>0 );
- }
- return SQLITE_OK;
- }
- /*
- ** Delete all information from a Fifo object. Free all memory held
- ** by the Fifo.
- */
- void sqlite3VdbeFifoClear(Fifo *pFifo){
- FifoPage *pPage, *pNextPage;
- for(pPage=pFifo->pFirst; pPage; pPage=pNextPage){
- pNextPage = pPage->pNext;
- sqlite3_free(pPage);
- }
- sqlite3VdbeFifoInit(pFifo);
- }