/ Hex Artifact Content
Login

Artifact 334c838c8f42d61a94813d136019ee566b5dc2f6:


0000: 2f 2a 0a 2a 2a 20 32 30 30 35 20 4a 75 6e 65 20  /*.** 2005 June 
0010: 31 36 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74  16.**.** The aut
0020: 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f  hor disclaims co
0030: 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20  pyright to this 
0040: 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e  source code.  In
0050: 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c   place of.** a l
0060: 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72  egal notice, her
0070: 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a  e is a blessing:
0080: 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f  .**.**    May yo
0090: 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f  u do good and no
00a0: 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61  t evil..**    Ma
00b0: 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69  y you find forgi
00c0: 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73  veness for yours
00d0: 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20  elf and forgive 
00e0: 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61  others..**    Ma
00f0: 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65  y you share free
0100: 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67  ly, never taking
0110: 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67   more than you g
0120: 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a  ive..**.********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 69  *.** This file i
0180: 6d 70 6c 65 6d 65 6e 74 73 20 61 20 46 49 46 4f  mplements a FIFO
0190: 20 71 75 65 75 65 20 6f 66 20 72 6f 77 69 64 73   queue of rowids
01a0: 20 75 73 65 64 20 66 6f 72 20 70 72 6f 63 65 73   used for proces
01b0: 73 69 6e 67 0a 2a 2a 20 55 50 44 41 54 45 20 61  sing.** UPDATE a
01c0: 6e 64 20 44 45 4c 45 54 45 20 73 74 61 74 65 6d  nd DELETE statem
01d0: 65 6e 74 73 2e 0a 2a 2f 0a 23 69 6e 63 6c 75 64  ents..*/.#includ
01e0: 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a  e "sqliteInt.h".
01f0: 23 69 6e 63 6c 75 64 65 20 22 76 64 62 65 49 6e  #include "vdbeIn
0200: 74 2e 68 22 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f  t.h"../*.** Allo
0210: 63 61 74 65 20 61 20 6e 65 77 20 46 69 66 6f 50  cate a new FifoP
0220: 61 67 65 20 61 6e 64 20 72 65 74 75 72 6e 20 61  age and return a
0230: 20 70 6f 69 6e 74 65 72 20 74 6f 20 69 74 2e 20   pointer to it. 
0240: 20 52 65 74 75 72 6e 20 4e 55 4c 4c 20 69 66 0a   Return NULL if.
0250: 2a 2a 20 77 65 20 72 75 6e 20 6f 75 74 20 6f 66  ** we run out of
0260: 20 6d 65 6d 6f 72 79 2e 20 20 4c 65 61 76 65 20   memory.  Leave 
0270: 73 70 61 63 65 20 6f 6e 20 74 68 65 20 70 61 67  space on the pag
0280: 65 20 66 6f 72 20 6e 45 6e 74 72 79 20 65 6e 74  e for nEntry ent
0290: 72 69 65 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  ries..*/.static 
02a0: 46 69 66 6f 50 61 67 65 20 2a 61 6c 6c 6f 63 61  FifoPage *alloca
02b0: 74 65 46 69 66 6f 50 61 67 65 28 69 6e 74 20 6e  teFifoPage(int n
02c0: 45 6e 74 72 79 29 7b 0a 20 20 46 69 66 6f 50 61  Entry){.  FifoPa
02d0: 67 65 20 2a 70 50 61 67 65 3b 0a 20 20 69 66 28  ge *pPage;.  if(
02e0: 20 6e 45 6e 74 72 79 3e 33 32 37 36 37 20 29 7b   nEntry>32767 ){
02f0: 0a 20 20 20 20 6e 45 6e 74 72 79 20 3d 20 33 32  .    nEntry = 32
0300: 37 36 37 3b 0a 20 20 7d 0a 20 20 70 50 61 67 65  767;.  }.  pPage
0310: 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f   = sqlite3_mallo
0320: 63 28 20 73 69 7a 65 6f 66 28 46 69 66 6f 50 61  c( sizeof(FifoPa
0330: 67 65 29 20 2b 20 73 69 7a 65 6f 66 28 69 36 34  ge) + sizeof(i64
0340: 29 2a 28 6e 45 6e 74 72 79 2d 31 29 20 29 3b 0a  )*(nEntry-1) );.
0350: 20 20 69 66 28 20 70 50 61 67 65 20 29 7b 0a 20    if( pPage ){. 
0360: 20 20 20 70 50 61 67 65 2d 3e 6e 53 6c 6f 74 20     pPage->nSlot 
0370: 3d 20 6e 45 6e 74 72 79 3b 0a 20 20 20 20 70 50  = nEntry;.    pP
0380: 61 67 65 2d 3e 69 57 72 69 74 65 20 3d 20 30 3b  age->iWrite = 0;
0390: 0a 20 20 20 20 70 50 61 67 65 2d 3e 69 52 65 61  .    pPage->iRea
03a0: 64 20 3d 20 30 3b 0a 20 20 20 20 70 50 61 67 65  d = 0;.    pPage
03b0: 2d 3e 70 4e 65 78 74 20 3d 20 30 3b 0a 20 20 7d  ->pNext = 0;.  }
03c0: 0a 20 20 72 65 74 75 72 6e 20 70 50 61 67 65 3b  .  return pPage;
03d0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61  .}../*.** Initia
03e0: 6c 69 7a 65 20 61 20 46 69 66 6f 20 73 74 72 75  lize a Fifo stru
03f0: 63 74 75 72 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73  cture..*/.void s
0400: 71 6c 69 74 65 33 56 64 62 65 46 69 66 6f 49 6e  qlite3VdbeFifoIn
0410: 69 74 28 46 69 66 6f 20 2a 70 46 69 66 6f 29 7b  it(Fifo *pFifo){
0420: 0a 20 20 6d 65 6d 73 65 74 28 70 46 69 66 6f 2c  .  memset(pFifo,
0430: 20 30 2c 20 73 69 7a 65 6f 66 28 2a 70 46 69 66   0, sizeof(*pFif
0440: 6f 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 50 75  o));.}../*.** Pu
0450: 73 68 20 61 20 73 69 6e 67 6c 65 20 36 34 2d 62  sh a single 64-b
0460: 69 74 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65  it integer value
0470: 20 69 6e 74 6f 20 74 68 65 20 46 69 66 6f 2e 20   into the Fifo. 
0480: 20 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   Return SQLITE_O
0490: 4b 0a 2a 2a 20 6e 6f 72 6d 61 6c 6c 79 2e 20 20  K.** normally.  
04a0: 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 20 69 73   SQLITE_NOMEM is
04b0: 20 72 65 74 75 72 6e 65 64 20 69 66 20 77 65 20   returned if we 
04c0: 61 72 65 20 75 6e 61 62 6c 65 20 74 6f 20 61 6c  are unable to al
04d0: 6c 6f 63 61 74 65 0a 2a 2a 20 6d 65 6d 6f 72 79  locate.** memory
04e0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
04f0: 56 64 62 65 46 69 66 6f 50 75 73 68 28 46 69 66  VdbeFifoPush(Fif
0500: 6f 20 2a 70 46 69 66 6f 2c 20 69 36 34 20 76 61  o *pFifo, i64 va
0510: 6c 29 7b 0a 20 20 46 69 66 6f 50 61 67 65 20 2a  l){.  FifoPage *
0520: 70 50 61 67 65 3b 0a 20 20 70 50 61 67 65 20 3d  pPage;.  pPage =
0530: 20 70 46 69 66 6f 2d 3e 70 4c 61 73 74 3b 0a 20   pFifo->pLast;. 
0540: 20 69 66 28 20 70 50 61 67 65 3d 3d 30 20 29 7b   if( pPage==0 ){
0550: 0a 20 20 20 20 70 50 61 67 65 20 3d 20 70 46 69  .    pPage = pFi
0560: 66 6f 2d 3e 70 4c 61 73 74 20 3d 20 70 46 69 66  fo->pLast = pFif
0570: 6f 2d 3e 70 46 69 72 73 74 20 3d 20 61 6c 6c 6f  o->pFirst = allo
0580: 63 61 74 65 46 69 66 6f 50 61 67 65 28 32 30 29  cateFifoPage(20)
0590: 3b 0a 20 20 20 20 69 66 28 20 70 50 61 67 65 3d  ;.    if( pPage=
05a0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 74 75  =0 ){.      retu
05b0: 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b  rn SQLITE_NOMEM;
05c0: 0a 20 20 20 20 7d 0a 20 20 7d 65 6c 73 65 20 69  .    }.  }else i
05d0: 66 28 20 70 50 61 67 65 2d 3e 69 57 72 69 74 65  f( pPage->iWrite
05e0: 3e 3d 70 50 61 67 65 2d 3e 6e 53 6c 6f 74 20 29  >=pPage->nSlot )
05f0: 7b 0a 20 20 20 20 70 50 61 67 65 2d 3e 70 4e 65  {.    pPage->pNe
0600: 78 74 20 3d 20 61 6c 6c 6f 63 61 74 65 46 69 66  xt = allocateFif
0610: 6f 50 61 67 65 28 70 46 69 66 6f 2d 3e 6e 45 6e  oPage(pFifo->nEn
0620: 74 72 79 29 3b 0a 20 20 20 20 69 66 28 20 70 50  try);.    if( pP
0630: 61 67 65 2d 3e 70 4e 65 78 74 3d 3d 30 20 29 7b  age->pNext==0 ){
0640: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 53 51  .      return SQ
0650: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20  LITE_NOMEM;.    
0660: 7d 0a 20 20 20 20 70 50 61 67 65 20 3d 20 70 46  }.    pPage = pF
0670: 69 66 6f 2d 3e 70 4c 61 73 74 20 3d 20 70 50 61  ifo->pLast = pPa
0680: 67 65 2d 3e 70 4e 65 78 74 3b 0a 20 20 7d 0a 20  ge->pNext;.  }. 
0690: 20 70 50 61 67 65 2d 3e 61 53 6c 6f 74 5b 70 50   pPage->aSlot[pP
06a0: 61 67 65 2d 3e 69 57 72 69 74 65 2b 2b 5d 20 3d  age->iWrite++] =
06b0: 20 76 61 6c 3b 0a 20 20 70 46 69 66 6f 2d 3e 6e   val;.  pFifo->n
06c0: 45 6e 74 72 79 2b 2b 3b 0a 20 20 72 65 74 75 72  Entry++;.  retur
06d0: 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a  n SQLITE_OK;.}..
06e0: 2f 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20 61 20  /*.** Extract a 
06f0: 73 69 6e 67 6c 65 20 36 34 2d 62 69 74 20 69 6e  single 64-bit in
0700: 74 65 67 65 72 20 76 61 6c 75 65 20 66 72 6f 6d  teger value from
0710: 20 74 68 65 20 46 69 66 6f 2e 20 20 54 68 65 20   the Fifo.  The 
0720: 69 6e 74 65 67 65 72 0a 2a 2a 20 65 78 74 72 61  integer.** extra
0730: 63 74 65 64 20 69 73 20 74 68 65 20 6f 6e 65 20  cted is the one 
0740: 6c 65 61 73 74 20 72 65 63 65 6e 74 6c 79 20 69  least recently i
0750: 6e 73 65 72 74 65 64 2e 20 20 49 66 20 74 68 65  nserted.  If the
0760: 20 46 69 66 6f 20 69 73 20 65 6d 70 74 79 0a 2a   Fifo is empty.*
0770: 2a 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  * return SQLITE_
0780: 44 4f 4e 45 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  DONE..*/.int sql
0790: 69 74 65 33 56 64 62 65 46 69 66 6f 50 6f 70 28  ite3VdbeFifoPop(
07a0: 46 69 66 6f 20 2a 70 46 69 66 6f 2c 20 69 36 34  Fifo *pFifo, i64
07b0: 20 2a 70 56 61 6c 29 7b 0a 20 20 46 69 66 6f 50   *pVal){.  FifoP
07c0: 61 67 65 20 2a 70 50 61 67 65 3b 0a 20 20 69 66  age *pPage;.  if
07d0: 28 20 70 46 69 66 6f 2d 3e 6e 45 6e 74 72 79 3d  ( pFifo->nEntry=
07e0: 3d 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e  =0 ){.    return
07f0: 20 53 51 4c 49 54 45 5f 44 4f 4e 45 3b 0a 20 20   SQLITE_DONE;.  
0800: 7d 0a 20 20 61 73 73 65 72 74 28 20 70 46 69 66  }.  assert( pFif
0810: 6f 2d 3e 6e 45 6e 74 72 79 3e 30 20 29 3b 0a 20  o->nEntry>0 );. 
0820: 20 70 50 61 67 65 20 3d 20 70 46 69 66 6f 2d 3e   pPage = pFifo->
0830: 70 46 69 72 73 74 3b 0a 20 20 61 73 73 65 72 74  pFirst;.  assert
0840: 28 20 70 50 61 67 65 21 3d 30 20 29 3b 0a 20 20  ( pPage!=0 );.  
0850: 61 73 73 65 72 74 28 20 70 50 61 67 65 2d 3e 69  assert( pPage->i
0860: 57 72 69 74 65 3e 70 50 61 67 65 2d 3e 69 52 65  Write>pPage->iRe
0870: 61 64 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  ad );.  assert( 
0880: 70 50 61 67 65 2d 3e 69 57 72 69 74 65 3c 3d 70  pPage->iWrite<=p
0890: 50 61 67 65 2d 3e 6e 53 6c 6f 74 20 29 3b 0a 20  Page->nSlot );. 
08a0: 20 61 73 73 65 72 74 28 20 70 50 61 67 65 2d 3e   assert( pPage->
08b0: 69 52 65 61 64 3c 70 50 61 67 65 2d 3e 6e 53 6c  iRead<pPage->nSl
08c0: 6f 74 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  ot );.  assert( 
08d0: 70 50 61 67 65 2d 3e 69 52 65 61 64 3e 3d 30 20  pPage->iRead>=0 
08e0: 29 3b 0a 20 20 2a 70 56 61 6c 20 3d 20 70 50 61  );.  *pVal = pPa
08f0: 67 65 2d 3e 61 53 6c 6f 74 5b 70 50 61 67 65 2d  ge->aSlot[pPage-
0900: 3e 69 52 65 61 64 2b 2b 5d 3b 0a 20 20 70 46 69  >iRead++];.  pFi
0910: 66 6f 2d 3e 6e 45 6e 74 72 79 2d 2d 3b 0a 20 20  fo->nEntry--;.  
0920: 69 66 28 20 70 50 61 67 65 2d 3e 69 52 65 61 64  if( pPage->iRead
0930: 3e 3d 70 50 61 67 65 2d 3e 69 57 72 69 74 65 20  >=pPage->iWrite 
0940: 29 7b 0a 20 20 20 20 70 46 69 66 6f 2d 3e 70 46  ){.    pFifo->pF
0950: 69 72 73 74 20 3d 20 70 50 61 67 65 2d 3e 70 4e  irst = pPage->pN
0960: 65 78 74 3b 0a 20 20 20 20 73 71 6c 69 74 65 33  ext;.    sqlite3
0970: 5f 66 72 65 65 28 70 50 61 67 65 29 3b 0a 20 20  _free(pPage);.  
0980: 20 20 69 66 28 20 70 46 69 66 6f 2d 3e 6e 45 6e    if( pFifo->nEn
0990: 74 72 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20  try==0 ){.      
09a0: 61 73 73 65 72 74 28 20 70 46 69 66 6f 2d 3e 70  assert( pFifo->p
09b0: 4c 61 73 74 3d 3d 70 50 61 67 65 20 29 3b 0a 20  Last==pPage );. 
09c0: 20 20 20 20 20 70 46 69 66 6f 2d 3e 70 4c 61 73       pFifo->pLas
09d0: 74 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65  t = 0;.    }else
09e0: 7b 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20  {.      assert( 
09f0: 70 46 69 66 6f 2d 3e 70 46 69 72 73 74 21 3d 30  pFifo->pFirst!=0
0a00: 20 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 65 6c 73   );.    }.  }els
0a10: 65 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70  e{.    assert( p
0a20: 46 69 66 6f 2d 3e 6e 45 6e 74 72 79 3e 30 20 29  Fifo->nEntry>0 )
0a30: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 53  ;.  }.  return S
0a40: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a  QLITE_OK;.}../*.
0a50: 2a 2a 20 44 65 6c 65 74 65 20 61 6c 6c 20 69 6e  ** Delete all in
0a60: 66 6f 72 6d 61 74 69 6f 6e 20 66 72 6f 6d 20 61  formation from a
0a70: 20 46 69 66 6f 20 6f 62 6a 65 63 74 2e 20 20 20   Fifo object.   
0a80: 46 72 65 65 20 61 6c 6c 20 6d 65 6d 6f 72 79 20  Free all memory 
0a90: 68 65 6c 64 0a 2a 2a 20 62 79 20 74 68 65 20 46  held.** by the F
0aa0: 69 66 6f 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c  ifo..*/.void sql
0ab0: 69 74 65 33 56 64 62 65 46 69 66 6f 43 6c 65 61  ite3VdbeFifoClea
0ac0: 72 28 46 69 66 6f 20 2a 70 46 69 66 6f 29 7b 0a  r(Fifo *pFifo){.
0ad0: 20 20 46 69 66 6f 50 61 67 65 20 2a 70 50 61 67    FifoPage *pPag
0ae0: 65 2c 20 2a 70 4e 65 78 74 50 61 67 65 3b 0a 20  e, *pNextPage;. 
0af0: 20 66 6f 72 28 70 50 61 67 65 3d 70 46 69 66 6f   for(pPage=pFifo
0b00: 2d 3e 70 46 69 72 73 74 3b 20 70 50 61 67 65 3b  ->pFirst; pPage;
0b10: 20 70 50 61 67 65 3d 70 4e 65 78 74 50 61 67 65   pPage=pNextPage
0b20: 29 7b 0a 20 20 20 20 70 4e 65 78 74 50 61 67 65  ){.    pNextPage
0b30: 20 3d 20 70 50 61 67 65 2d 3e 70 4e 65 78 74 3b   = pPage->pNext;
0b40: 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65  .    sqlite3_fre
0b50: 65 28 70 50 61 67 65 29 3b 0a 20 20 7d 0a 20 20  e(pPage);.  }.  
0b60: 73 71 6c 69 74 65 33 56 64 62 65 46 69 66 6f 49  sqlite3VdbeFifoI
0b70: 6e 69 74 28 70 46 69 66 6f 29 3b 0a 7d 0a        nit(pFifo);.}.