4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
11 *************************************************************************
12 ** This file implements a FIFO queue of rowids used for processing
13 ** UPDATE and DELETE statements.
15 ** $Id: vdbefifo.c,v 1.8 2008/07/28 19:34:54 drh Exp $
17 #include "sqliteInt.h"
21 ** Constants FIFOSIZE_FIRST and FIFOSIZE_MAX are the initial
22 ** number of entries in a fifo page and the maximum number of
23 ** entries in a fifo page.
25 #define FIFOSIZE_FIRST (((128-sizeof(FifoPage))/8)+1)
26 #ifdef SQLITE_MALLOC_SOFT_LIMIT
27 # define FIFOSIZE_MAX (((SQLITE_MALLOC_SOFT_LIMIT-sizeof(FifoPage))/8)+1)
29 # define FIFOSIZE_MAX (((262144-sizeof(FifoPage))/8)+1)
33 ** Allocate a new FifoPage and return a pointer to it. Return NULL if
34 ** we run out of memory. Leave space on the page for nEntry entries.
36 static FifoPage *allocateFifoPage(sqlite3 *db, int nEntry){
38 if( nEntry>FIFOSIZE_MAX ){
39 nEntry = FIFOSIZE_MAX;
41 pPage = sqlite3DbMallocRaw(db, sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );
43 pPage->nSlot = nEntry;
52 ** Initialize a Fifo structure.
54 void sqlite3VdbeFifoInit(Fifo *pFifo, sqlite3 *db){
55 memset(pFifo, 0, sizeof(*pFifo));
60 ** Push a single 64-bit integer value into the Fifo. Return SQLITE_OK
61 ** normally. SQLITE_NOMEM is returned if we are unable to allocate
64 int sqlite3VdbeFifoPush(Fifo *pFifo, i64 val){
68 pPage = pFifo->pLast = pFifo->pFirst =
69 allocateFifoPage(pFifo->db, FIFOSIZE_FIRST);
73 }else if( pPage->iWrite>=pPage->nSlot ){
74 pPage->pNext = allocateFifoPage(pFifo->db, pFifo->nEntry);
75 if( pPage->pNext==0 ){
78 pPage = pFifo->pLast = pPage->pNext;
80 pPage->aSlot[pPage->iWrite++] = val;
86 ** Extract a single 64-bit integer value from the Fifo. The integer
87 ** extracted is the one least recently inserted. If the Fifo is empty
88 ** return SQLITE_DONE.
90 int sqlite3VdbeFifoPop(Fifo *pFifo, i64 *pVal){
92 if( pFifo->nEntry==0 ){
95 assert( pFifo->nEntry>0 );
96 pPage = pFifo->pFirst;
98 assert( pPage->iWrite>pPage->iRead );
99 assert( pPage->iWrite<=pPage->nSlot );
100 assert( pPage->iRead<pPage->nSlot );
101 assert( pPage->iRead>=0 );
102 *pVal = pPage->aSlot[pPage->iRead++];
104 if( pPage->iRead>=pPage->iWrite ){
105 pFifo->pFirst = pPage->pNext;
106 sqlite3DbFree(pFifo->db, pPage);
107 if( pFifo->nEntry==0 ){
108 assert( pFifo->pLast==pPage );
111 assert( pFifo->pFirst!=0 );
114 assert( pFifo->nEntry>0 );
120 ** Delete all information from a Fifo object. Free all memory held
123 void sqlite3VdbeFifoClear(Fifo *pFifo){
124 FifoPage *pPage, *pNextPage;
125 for(pPage=pFifo->pFirst; pPage; pPage=pNextPage){
126 pNextPage = pPage->pNext;
127 sqlite3DbFree(pFifo->db, pPage);
129 sqlite3VdbeFifoInit(pFifo, pFifo->db);