--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/sql/SQLite/vdbefifo.c	Fri Jan 22 11:06:30 2010 +0200
@@ -0,0 +1,130 @@
+/*
+** 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);
+}