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              63 : static FifoPage *allocateFifoPage(int nEntry){
      23                 :   FifoPage *pPage;
      24              63 :   if( nEntry>32767 ){
      25               0 :     nEntry = 32767;
      26                 :   }
      27              63 :   pPage = sqliteMallocRaw( sizeof(FifoPage) + sizeof(i64)*(nEntry-1) );
      28              63 :   if( pPage ){
      29              63 :     pPage->nSlot = nEntry;
      30              63 :     pPage->iWrite = 0;
      31              63 :     pPage->iRead = 0;
      32              63 :     pPage->pNext = 0;
      33                 :   }
      34              63 :   return pPage;
      35                 : }
      36                 : 
      37                 : /*
      38                 : ** Initialize a Fifo structure.
      39                 : */
      40            1416 : void sqlite3VdbeFifoInit(Fifo *pFifo){
      41            1416 :   memset(pFifo, 0, sizeof(*pFifo));
      42            1416 : }
      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              63 : int sqlite3VdbeFifoPush(Fifo *pFifo, i64 val){
      50                 :   FifoPage *pPage;
      51              63 :   pPage = pFifo->pLast;
      52              63 :   if( pPage==0 ){
      53              63 :     pPage = pFifo->pLast = pFifo->pFirst = allocateFifoPage(20);
      54              63 :     if( pPage==0 ){
      55               0 :       return SQLITE_NOMEM;
      56                 :     }
      57               0 :   }else if( pPage->iWrite>=pPage->nSlot ){
      58               0 :     pPage->pNext = allocateFifoPage(pFifo->nEntry);
      59               0 :     if( pPage->pNext==0 ){
      60               0 :       return SQLITE_NOMEM;
      61                 :     }
      62               0 :     pPage = pFifo->pLast = pPage->pNext;
      63                 :   }
      64              63 :   pPage->aSlot[pPage->iWrite++] = val;
      65              63 :   pFifo->nEntry++;
      66              63 :   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             130 : int sqlite3VdbeFifoPop(Fifo *pFifo, i64 *pVal){
      75                 :   FifoPage *pPage;
      76             130 :   if( pFifo->nEntry==0 ){
      77              67 :     return SQLITE_DONE;
      78                 :   }
      79                 :   assert( pFifo->nEntry>0 );
      80              63 :   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              63 :   *pVal = pPage->aSlot[pPage->iRead++];
      87              63 :   pFifo->nEntry--;
      88              63 :   if( pPage->iRead>=pPage->iWrite ){
      89              63 :     pFifo->pFirst = pPage->pNext;
      90              63 :     sqliteFree(pPage);
      91              63 :     if( pFifo->nEntry==0 ){
      92                 :       assert( pFifo->pLast==pPage );
      93              63 :       pFifo->pLast = 0;
      94                 :     }else{
      95                 :       assert( pFifo->pFirst!=0 );
      96                 :     }
      97                 :   }else{
      98                 :     assert( pFifo->nEntry>0 );
      99                 :   }
     100              63 :   return SQLITE_OK;
     101                 : }
     102                 : 
     103                 : /*
     104                 : ** Delete all information from a Fifo object.   Free all memory held
     105                 : ** by the Fifo.
     106                 : */
     107            1416 : void sqlite3VdbeFifoClear(Fifo *pFifo){
     108                 :   FifoPage *pPage, *pNextPage;
     109            1416 :   for(pPage=pFifo->pFirst; pPage; pPage=pNextPage){
     110               0 :     pNextPage = pPage->pNext;
     111               0 :     sqliteFree(pPage);
     112                 :   }
     113            1416 :   sqlite3VdbeFifoInit(pFifo);
     114            1416 : }