1 /*

     2 ** 2005 June 16

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     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.

    10 **

    11 *************************************************************************

    12 ** This file implements a FIFO queue of rowids used for processing

    13 ** UPDATE and DELETE statements.

    14 **

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

    16 */

    17 #include "sqliteInt.h"

    18 #include "vdbeInt.h"

    19 

    20 /*

    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.

    24 */

    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)

    28 #else

    29 # define FIFOSIZE_MAX   (((262144-sizeof(FifoPage))/8)+1)

    30 #endif

    31 

    32 /*

    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.

    35 */

    36 static FifoPage *allocateFifoPage(sqlite3 *db, int nEntry){

    37   FifoPage *pPage;

    38   if( nEntry>FIFOSIZE_MAX ){

    39     nEntry = FIFOSIZE_MAX;

    40   }

    41   pPage = sqlite3DbMallocRaw(db, sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );

    42   if( pPage ){

    43     pPage->nSlot = nEntry;

    44     pPage->iWrite = 0;

    45     pPage->iRead = 0;

    46     pPage->pNext = 0;

    47   }

    48   return pPage;

    49 }

    50 

    51 /*

    52 ** Initialize a Fifo structure.

    53 */

    54 void sqlite3VdbeFifoInit(Fifo *pFifo, sqlite3 *db){

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

    56   pFifo->db = db;

    57 }

    58 

    59 /*

    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

    62 ** memory.

    63 */

    64 int sqlite3VdbeFifoPush(Fifo *pFifo, i64 val){

    65   FifoPage *pPage;

    66   pPage = pFifo->pLast;

    67   if( pPage==0 ){

    68     pPage = pFifo->pLast = pFifo->pFirst =

    69          allocateFifoPage(pFifo->db, FIFOSIZE_FIRST);

    70     if( pPage==0 ){

    71       return SQLITE_NOMEM;

    72     }

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

    74     pPage->pNext = allocateFifoPage(pFifo->db, pFifo->nEntry);

    75     if( pPage->pNext==0 ){

    76       return SQLITE_NOMEM;

    77     }

    78     pPage = pFifo->pLast = pPage->pNext;

    79   }

    80   pPage->aSlot[pPage->iWrite++] = val;

    81   pFifo->nEntry++;

    82   return SQLITE_OK;

    83 }

    84 

    85 /*

    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.

    89 */

    90 int sqlite3VdbeFifoPop(Fifo *pFifo, i64 *pVal){

    91   FifoPage *pPage;

    92   if( pFifo->nEntry==0 ){

    93     return SQLITE_DONE;

    94   }

    95   assert( pFifo->nEntry>0 );

    96   pPage = pFifo->pFirst;

    97   assert( pPage!=0 );

    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++];

   103   pFifo->nEntry--;

   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 );

   109       pFifo->pLast = 0;

   110     }else{

   111       assert( pFifo->pFirst!=0 );

   112     }

   113   }else{

   114     assert( pFifo->nEntry>0 );

   115   }

   116   return SQLITE_OK;

   117 }

   118 

   119 /*

   120 ** Delete all information from a Fifo object.   Free all memory held

   121 ** by the Fifo.

   122 */

   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);

   128   }

   129   sqlite3VdbeFifoInit(pFifo, pFifo->db);

   130 }