sl@0: /*
sl@0: ** 2005 June 16
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file implements a FIFO queue of rowids used for processing
sl@0: ** UPDATE and DELETE statements.
sl@0: **
sl@0: ** $Id: vdbefifo.c,v 1.8 2008/07/28 19:34:54 drh Exp $
sl@0: */
sl@0: #include "sqliteInt.h"
sl@0: #include "vdbeInt.h"
sl@0: 
sl@0: /*
sl@0: ** Constants FIFOSIZE_FIRST and FIFOSIZE_MAX are the initial
sl@0: ** number of entries in a fifo page and the maximum number of
sl@0: ** entries in a fifo page.
sl@0: */
sl@0: #define FIFOSIZE_FIRST (((128-sizeof(FifoPage))/8)+1)
sl@0: #ifdef SQLITE_MALLOC_SOFT_LIMIT
sl@0: # define FIFOSIZE_MAX   (((SQLITE_MALLOC_SOFT_LIMIT-sizeof(FifoPage))/8)+1)
sl@0: #else
sl@0: # define FIFOSIZE_MAX   (((262144-sizeof(FifoPage))/8)+1)
sl@0: #endif
sl@0: 
sl@0: /*
sl@0: ** Allocate a new FifoPage and return a pointer to it.  Return NULL if
sl@0: ** we run out of memory.  Leave space on the page for nEntry entries.
sl@0: */
sl@0: static FifoPage *allocateFifoPage(sqlite3 *db, int nEntry){
sl@0:   FifoPage *pPage;
sl@0:   if( nEntry>FIFOSIZE_MAX ){
sl@0:     nEntry = FIFOSIZE_MAX;
sl@0:   }
sl@0:   pPage = sqlite3DbMallocRaw(db, sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );
sl@0:   if( pPage ){
sl@0:     pPage->nSlot = nEntry;
sl@0:     pPage->iWrite = 0;
sl@0:     pPage->iRead = 0;
sl@0:     pPage->pNext = 0;
sl@0:   }
sl@0:   return pPage;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Initialize a Fifo structure.
sl@0: */
sl@0: void sqlite3VdbeFifoInit(Fifo *pFifo, sqlite3 *db){
sl@0:   memset(pFifo, 0, sizeof(*pFifo));
sl@0:   pFifo->db = db;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Push a single 64-bit integer value into the Fifo.  Return SQLITE_OK
sl@0: ** normally.   SQLITE_NOMEM is returned if we are unable to allocate
sl@0: ** memory.
sl@0: */
sl@0: int sqlite3VdbeFifoPush(Fifo *pFifo, i64 val){
sl@0:   FifoPage *pPage;
sl@0:   pPage = pFifo->pLast;
sl@0:   if( pPage==0 ){
sl@0:     pPage = pFifo->pLast = pFifo->pFirst =
sl@0:          allocateFifoPage(pFifo->db, FIFOSIZE_FIRST);
sl@0:     if( pPage==0 ){
sl@0:       return SQLITE_NOMEM;
sl@0:     }
sl@0:   }else if( pPage->iWrite>=pPage->nSlot ){
sl@0:     pPage->pNext = allocateFifoPage(pFifo->db, pFifo->nEntry);
sl@0:     if( pPage->pNext==0 ){
sl@0:       return SQLITE_NOMEM;
sl@0:     }
sl@0:     pPage = pFifo->pLast = pPage->pNext;
sl@0:   }
sl@0:   pPage->aSlot[pPage->iWrite++] = val;
sl@0:   pFifo->nEntry++;
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Extract a single 64-bit integer value from the Fifo.  The integer
sl@0: ** extracted is the one least recently inserted.  If the Fifo is empty
sl@0: ** return SQLITE_DONE.
sl@0: */
sl@0: int sqlite3VdbeFifoPop(Fifo *pFifo, i64 *pVal){
sl@0:   FifoPage *pPage;
sl@0:   if( pFifo->nEntry==0 ){
sl@0:     return SQLITE_DONE;
sl@0:   }
sl@0:   assert( pFifo->nEntry>0 );
sl@0:   pPage = pFifo->pFirst;
sl@0:   assert( pPage!=0 );
sl@0:   assert( pPage->iWrite>pPage->iRead );
sl@0:   assert( pPage->iWrite<=pPage->nSlot );
sl@0:   assert( pPage->iRead<pPage->nSlot );
sl@0:   assert( pPage->iRead>=0 );
sl@0:   *pVal = pPage->aSlot[pPage->iRead++];
sl@0:   pFifo->nEntry--;
sl@0:   if( pPage->iRead>=pPage->iWrite ){
sl@0:     pFifo->pFirst = pPage->pNext;
sl@0:     sqlite3DbFree(pFifo->db, pPage);
sl@0:     if( pFifo->nEntry==0 ){
sl@0:       assert( pFifo->pLast==pPage );
sl@0:       pFifo->pLast = 0;
sl@0:     }else{
sl@0:       assert( pFifo->pFirst!=0 );
sl@0:     }
sl@0:   }else{
sl@0:     assert( pFifo->nEntry>0 );
sl@0:   }
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Delete all information from a Fifo object.   Free all memory held
sl@0: ** by the Fifo.
sl@0: */
sl@0: void sqlite3VdbeFifoClear(Fifo *pFifo){
sl@0:   FifoPage *pPage, *pNextPage;
sl@0:   for(pPage=pFifo->pFirst; pPage; pPage=pNextPage){
sl@0:     pNextPage = pPage->pNext;
sl@0:     sqlite3DbFree(pFifo->db, pPage);
sl@0:   }
sl@0:   sqlite3VdbeFifoInit(pFifo, pFifo->db);
sl@0: }