/*

** 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.

**

** $Id: vdbefifo.c,v 1.8 2008/07/28 19:34:54 drh Exp $

*/

#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(sqlite3 *db, int nEntry){

  FifoPage *pPage;

  if( nEntry>FIFOSIZE_MAX ){

    nEntry = FIFOSIZE_MAX;

  }

  pPage = sqlite3DbMallocRaw(db, 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, sqlite3 *db){

  memset(pFifo, 0, sizeof(*pFifo));

  pFifo->db = db;

}

/*

** 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(pFifo->db, FIFOSIZE_FIRST);

    if( pPage==0 ){

      return SQLITE_NOMEM;

    }

  }else if( pPage->iWrite>=pPage->nSlot ){

    pPage->pNext = allocateFifoPage(pFifo->db, 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;

    sqlite3DbFree(pFifo->db, 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;

    sqlite3DbFree(pFifo->db, pPage);

  }

  sqlite3VdbeFifoInit(pFifo, pFifo->db);

}