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 #include "sqliteInt.h"

    16 #include "vdbeInt.h"

    17 

    18 /*

    19 ** Allocate a new FifoPage and return a pointer to it.  Return NULL if

    20 ** we run out of memory.  Leave space on the page for nEntry entries.

    21 */

    22 static FifoPage *allocateFifoPage(int nEntry){

    23   FifoPage *pPage;

    24   if( nEntry>32767 ){

    25     nEntry = 32767;

    26   }

    27   pPage = (FifoPage*)sqlite3_malloc( sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );

    28   if( pPage ){

    29     pPage->nSlot = nEntry;

    30     pPage->iWrite = 0;

    31     pPage->iRead = 0;

    32     pPage->pNext = 0;

    33   }

    34   return pPage;

    35 }

    36 

    37 /*

    38 ** Initialize a Fifo structure.

    39 */

    40 void sqlite3VdbeFifoInit(Fifo *pFifo){

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

    42 }

    43 

    44 /*

    45 ** Push a single 64-bit integer value into the Fifo.  Return SQLITE_OK

    46 ** normally.   SQLITE_NOMEM is returned if we are unable to allocate

    47 ** memory.

    48 */

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

    50   FifoPage *pPage;

    51   pPage = pFifo->pLast;

    52   if( pPage==0 ){

    53     pPage = pFifo->pLast = pFifo->pFirst = allocateFifoPage(20);

    54     if( pPage==0 ){

    55       return SQLITE_NOMEM;

    56     }

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

    58     pPage->pNext = allocateFifoPage(pFifo->nEntry);

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

    60       return SQLITE_NOMEM;

    61     }

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

    63   }

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

    65   pFifo->nEntry++;

    66   return SQLITE_OK;

    67 }

    68 

    69 /*

    70 ** Extract a single 64-bit integer value from the Fifo.  The integer

    71 ** extracted is the one least recently inserted.  If the Fifo is empty

    72 ** return SQLITE_DONE.

    73 */

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

    75   FifoPage *pPage;

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

    77     return SQLITE_DONE;

    78   }

    79   assert( pFifo->nEntry>0 );

    80   pPage = pFifo->pFirst;

    81   assert( pPage!=0 );

    82   assert( pPage->iWrite>pPage->iRead );

    83   assert( pPage->iWrite<=pPage->nSlot );

    84   assert( pPage->iRead<pPage->nSlot );

    85   assert( pPage->iRead>=0 );

    86   *pVal = pPage->aSlot[pPage->iRead++];

    87   pFifo->nEntry--;

    88   if( pPage->iRead>=pPage->iWrite ){

    89     pFifo->pFirst = pPage->pNext;

    90     sqlite3_free(pPage);

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

    92       assert( pFifo->pLast==pPage );

    93       pFifo->pLast = 0;

    94     }else{

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

    96     }

    97   }else{

    98     assert( pFifo->nEntry>0 );

    99   }

   100   return SQLITE_OK;

   101 }

   102 

   103 /*

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

   105 ** by the Fifo.

   106 */

   107 void sqlite3VdbeFifoClear(Fifo *pFifo){

   108   FifoPage *pPage, *pNextPage;

   109   for(pPage=pFifo->pFirst; pPage; pPage=pNextPage){

   110     pNextPage = pPage->pNext;

   111     sqlite3_free(pPage);

   112   }

   113   sqlite3VdbeFifoInit(pFifo);

   114 }