/ Hex Artifact Content
Login

Artifact 7b7e7e479212e65b723bf40128c7b36dc5afdfac:


0000: 2f 2a 0a 2a 2a 20 32 30 30 38 20 44 65 63 65 6d  /*.** 2008 Decem
0010: 62 65 72 20 33 0a 2a 2a 0a 2a 2a 20 54 68 65 20  ber 3.**.** The 
0020: 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73  author disclaims
0030: 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68   copyright to th
0040: 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20  is source code. 
0050: 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20   In place of.** 
0060: 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20  a legal notice, 
0070: 68 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69  here is a blessi
0080: 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79  ng:.**.**    May
0090: 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64   you do good and
00a0: 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20   not evil..**   
00b0: 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f   May you find fo
00c0: 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f  rgiveness for yo
00d0: 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69  urself and forgi
00e0: 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20  ve others..**   
00f0: 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66   May you share f
0100: 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b  reely, never tak
0110: 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f  ing more than yo
0120: 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a  u give..**.*****
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 2a 2a 2a 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20  ****.**.** This 
0180: 6d 6f 64 75 6c 65 20 69 6d 70 6c 65 6d 65 6e 74  module implement
0190: 73 20 61 6e 20 6f 62 6a 65 63 74 20 77 65 20 63  s an object we c
01a0: 61 6c 6c 20 61 20 22 52 6f 77 53 65 74 22 2e 0a  all a "RowSet"..
01b0: 2a 2a 0a 2a 2a 20 54 68 65 20 52 6f 77 53 65 74  **.** The RowSet
01c0: 20 6f 62 6a 65 63 74 20 69 73 20 61 20 63 6f 6c   object is a col
01d0: 6c 65 63 74 69 6f 6e 20 6f 66 20 72 6f 77 69 64  lection of rowid
01e0: 73 2e 20 20 52 6f 77 69 64 73 0a 2a 2a 20 61 72  s.  Rowids.** ar
01f0: 65 20 69 6e 73 65 72 74 65 64 20 69 6e 74 6f 20  e inserted into 
0200: 74 68 65 20 52 6f 77 53 65 74 20 69 6e 20 61 6e  the RowSet in an
0210: 20 61 72 62 69 74 72 61 72 79 20 6f 72 64 65 72   arbitrary order
0220: 2e 20 20 49 6e 73 65 72 74 73 0a 2a 2a 20 63 61  .  Inserts.** ca
0230: 6e 20 62 65 20 69 6e 74 65 72 6d 69 78 65 64 20  n be intermixed 
0240: 77 69 74 68 20 74 65 73 74 73 20 74 6f 20 73 65  with tests to se
0250: 65 20 69 66 20 61 20 67 69 76 65 6e 20 72 6f 77  e if a given row
0260: 69 64 20 68 61 73 20 62 65 65 6e 0a 2a 2a 20 70  id has been.** p
0270: 72 65 76 69 6f 75 73 6c 79 20 69 6e 73 65 72 74  reviously insert
0280: 65 64 20 69 6e 74 6f 20 74 68 65 20 52 6f 77 53  ed into the RowS
0290: 65 74 2e 0a 2a 2a 0a 2a 2a 20 41 66 74 65 72 20  et..**.** After 
02a0: 61 6c 6c 20 69 6e 73 65 72 74 73 20 61 72 65 20  all inserts are 
02b0: 66 69 6e 69 73 68 65 64 2c 20 69 74 20 69 73 20  finished, it is 
02c0: 70 6f 73 73 69 62 6c 65 20 74 6f 20 65 78 74 72  possible to extr
02d0: 61 63 74 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65  act the.** eleme
02e0: 6e 74 73 20 6f 66 20 74 68 65 20 52 6f 77 53 65  nts of the RowSe
02f0: 74 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  t in sorted orde
0300: 72 2e 20 20 4f 6e 63 65 20 74 68 69 73 20 65 78  r.  Once this ex
0310: 74 72 61 63 74 69 6f 6e 0a 2a 2a 20 70 72 6f 63  traction.** proc
0320: 65 73 73 20 68 61 73 20 73 74 61 72 74 65 64 2c  ess has started,
0330: 20 6e 6f 20 6e 65 77 20 65 6c 65 6d 65 6e 74 73   no new elements
0340: 20 6d 61 79 20 62 65 20 69 6e 73 65 72 74 65 64   may be inserted
0350: 2e 0a 2a 2a 0a 2a 2a 20 48 65 6e 63 65 2c 20 74  ..**.** Hence, t
0360: 68 65 20 70 72 69 6d 69 74 69 76 65 20 6f 70 65  he primitive ope
0370: 72 61 74 69 6f 6e 73 20 66 6f 72 20 61 20 52 6f  rations for a Ro
0380: 77 53 65 74 20 61 72 65 3a 0a 2a 2a 0a 2a 2a 20  wSet are:.**.** 
0390: 20 20 20 43 52 45 41 54 45 0a 2a 2a 20 20 20 20     CREATE.**    
03a0: 49 4e 53 45 52 54 0a 2a 2a 20 20 20 20 54 45 53  INSERT.**    TES
03b0: 54 0a 2a 2a 20 20 20 20 53 4d 41 4c 4c 45 53 54  T.**    SMALLEST
03c0: 0a 2a 2a 20 20 20 20 44 45 53 54 52 4f 59 0a 2a  .**    DESTROY.*
03d0: 2a 0a 2a 2a 20 54 68 65 20 43 52 45 41 54 45 20  *.** The CREATE 
03e0: 61 6e 64 20 44 45 53 54 52 4f 59 20 70 72 69 6d  and DESTROY prim
03f0: 69 74 69 76 65 73 20 61 72 65 20 74 68 65 20 63  itives are the c
0400: 6f 6e 73 74 72 75 63 74 6f 72 20 61 6e 64 20 64  onstructor and d
0410: 65 73 74 72 75 63 74 6f 72 2c 0a 2a 2a 20 6f 62  estructor,.** ob
0420: 76 69 6f 75 73 6c 79 2e 20 20 54 68 65 20 49 4e  viously.  The IN
0430: 53 45 52 54 20 70 72 69 6d 69 74 69 76 65 20 61  SERT primitive a
0440: 64 64 73 20 61 20 6e 65 77 20 65 6c 65 6d 65 6e  dds a new elemen
0450: 74 20 74 6f 20 74 68 65 20 52 6f 77 53 65 74 2e  t to the RowSet.
0460: 0a 2a 2a 20 54 45 53 54 20 63 68 65 63 6b 73 20  .** TEST checks 
0470: 74 6f 20 73 65 65 20 69 66 20 61 6e 20 65 6c 65  to see if an ele
0480: 6d 65 6e 74 20 69 73 20 61 6c 72 65 61 64 79 20  ment is already 
0490: 69 6e 20 74 68 65 20 52 6f 77 53 65 74 2e 20 20  in the RowSet.  
04a0: 53 4d 41 4c 4c 45 53 54 0a 2a 2a 20 65 78 74 72  SMALLEST.** extr
04b0: 61 63 74 73 20 74 68 65 20 6c 65 61 73 74 20 76  acts the least v
04c0: 61 6c 75 65 20 66 72 6f 6d 20 74 68 65 20 52 6f  alue from the Ro
04d0: 77 53 65 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  wSet..**.** The 
04e0: 49 4e 53 45 52 54 20 70 72 69 6d 69 74 69 76 65  INSERT primitive
04f0: 20 6d 69 67 68 74 20 61 6c 6c 6f 63 61 74 65 20   might allocate 
0500: 61 64 64 69 74 69 6f 6e 61 6c 20 6d 65 6d 6f 72  additional memor
0510: 79 2e 20 20 4d 65 6d 6f 72 79 20 69 73 0a 2a 2a  y.  Memory is.**
0520: 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e 20 63 68   allocated in ch
0530: 75 6e 6b 73 20 73 6f 20 6d 6f 73 74 20 49 4e 53  unks so most INS
0540: 45 52 54 73 20 64 6f 20 6e 6f 20 61 6c 6c 6f 63  ERTs do no alloc
0550: 61 74 69 6f 6e 2e 20 20 54 68 65 72 65 20 69 73  ation.  There is
0560: 20 61 6e 20 0a 2a 2a 20 75 70 70 65 72 20 62 6f   an .** upper bo
0570: 75 6e 64 20 6f 6e 20 74 68 65 20 73 69 7a 65 20  und on the size 
0580: 6f 66 20 61 6c 6c 6f 63 61 74 65 64 20 6d 65 6d  of allocated mem
0590: 6f 72 79 2e 20 20 4e 6f 20 6d 65 6d 6f 72 79 20  ory.  No memory 
05a0: 69 73 20 66 72 65 65 64 0a 2a 2a 20 75 6e 74 69  is freed.** unti
05b0: 6c 20 44 45 53 54 52 4f 59 2e 0a 2a 2a 0a 2a 2a  l DESTROY..**.**
05c0: 20 54 68 65 20 54 45 53 54 20 70 72 69 6d 69 74   The TEST primit
05d0: 69 76 65 20 69 6e 63 6c 75 64 65 73 20 61 20 22  ive includes a "
05e0: 62 61 74 63 68 22 20 6e 75 6d 62 65 72 2e 20 20  batch" number.  
05f0: 54 68 65 20 54 45 53 54 20 70 72 69 6d 69 74 69  The TEST primiti
0600: 76 65 0a 2a 2a 20 77 69 6c 6c 20 6f 6e 6c 79 20  ve.** will only 
0610: 73 65 65 20 65 6c 65 6d 65 6e 74 73 20 74 68 61  see elements tha
0620: 74 20 77 65 72 65 20 69 6e 73 65 72 74 65 64 20  t were inserted 
0630: 62 65 66 6f 72 65 20 74 68 65 20 6c 61 73 74 20  before the last 
0640: 63 68 61 6e 67 65 0a 2a 2a 20 69 6e 20 74 68 65  change.** in the
0650: 20 62 61 74 63 68 20 6e 75 6d 62 65 72 2e 20 20   batch number.  
0660: 49 6e 20 6f 74 68 65 72 20 77 6f 72 64 73 2c 20  In other words, 
0670: 69 66 20 61 6e 20 49 4e 53 45 52 54 20 6f 63 63  if an INSERT occ
0680: 75 72 73 20 62 65 74 77 65 65 6e 0a 2a 2a 20 74  urs between.** t
0690: 77 6f 20 54 45 53 54 73 20 77 68 65 72 65 20 74  wo TESTs where t
06a0: 68 65 20 54 45 53 54 73 20 68 61 76 65 20 74 68  he TESTs have th
06b0: 65 20 73 61 6d 65 20 62 61 74 63 68 20 6e 75 62  e same batch nub
06c0: 6d 65 72 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a  mer, then the.**
06d0: 20 76 61 6c 75 65 20 61 64 64 65 64 20 62 79 20   value added by 
06e0: 74 68 65 20 49 4e 53 45 52 54 20 77 69 6c 6c 20  the INSERT will 
06f0: 6e 6f 74 20 62 65 20 76 69 73 69 62 6c 65 20 74  not be visible t
0700: 6f 20 74 68 65 20 73 65 63 6f 6e 64 20 54 45 53  o the second TES
0710: 54 2e 0a 2a 2a 20 54 68 65 20 69 6e 69 74 69 61  T..** The initia
0720: 6c 20 62 61 74 63 68 20 6e 75 6d 62 65 72 20 69  l batch number i
0730: 73 20 7a 65 72 6f 2c 20 73 6f 20 69 66 20 74 68  s zero, so if th
0740: 65 20 76 65 72 79 20 66 69 72 73 74 20 54 45 53  e very first TES
0750: 54 20 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20 61 20  T contains.** a 
0760: 6e 6f 6e 2d 7a 65 72 6f 20 62 61 74 63 68 20 6e  non-zero batch n
0770: 75 6d 62 65 72 2c 20 69 74 20 77 69 6c 6c 20 73  umber, it will s
0780: 65 65 20 61 6c 6c 20 70 72 69 6f 72 20 49 4e 53  ee all prior INS
0790: 45 52 54 73 2e 0a 2a 2a 0a 2a 2a 20 4e 6f 20 49  ERTs..**.** No I
07a0: 4e 53 45 52 54 73 20 6d 61 79 20 6f 63 63 75 72  NSERTs may occur
07b0: 73 20 61 66 74 65 72 20 61 20 53 4d 41 4c 4c 45  s after a SMALLE
07c0: 53 54 2e 20 20 41 6e 20 61 73 73 65 72 74 69 6f  ST.  An assertio
07d0: 6e 20 77 69 6c 6c 20 66 61 69 6c 20 69 66 0a 2a  n will fail if.*
07e0: 2a 20 74 68 61 74 20 69 73 20 61 74 74 65 6d 70  * that is attemp
07f0: 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63  ted..**.** The c
0800: 6f 73 74 20 6f 66 20 61 6e 20 49 4e 53 45 52 54  ost of an INSERT
0810: 20 69 73 20 72 6f 75 67 68 6c 79 20 63 6f 6e 73   is roughly cons
0820: 74 61 6e 74 2e 20 20 28 53 6f 6d 65 74 69 6d 65  tant.  (Sometime
0830: 73 20 6e 65 77 20 6d 65 6d 6f 72 79 0a 2a 2a 20  s new memory.** 
0840: 68 61 73 20 74 6f 20 62 65 20 61 6c 6c 6f 63 61  has to be alloca
0850: 74 65 64 20 6f 6e 20 61 6e 20 49 4e 53 45 52 54  ted on an INSERT
0860: 2e 29 20 20 54 68 65 20 63 6f 73 74 20 6f 66 20  .)  The cost of 
0870: 61 20 54 45 53 54 20 77 69 74 68 20 61 20 6e 65  a TEST with a ne
0880: 77 0a 2a 2a 20 62 61 74 63 68 20 6e 75 6d 62 65  w.** batch numbe
0890: 72 20 69 73 20 4f 28 4e 6c 6f 67 4e 29 20 77 68  r is O(NlogN) wh
08a0: 65 72 65 20 4e 20 69 73 20 74 68 65 20 6e 75 6d  ere N is the num
08b0: 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20  ber of elements 
08c0: 69 6e 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a  in the RowSet..*
08d0: 2a 20 54 68 65 20 63 6f 73 74 20 6f 66 20 61 20  * The cost of a 
08e0: 54 45 53 54 20 75 73 69 6e 67 20 74 68 65 20 73  TEST using the s
08f0: 61 6d 65 20 62 61 74 63 68 20 6e 75 6d 62 65 72  ame batch number
0900: 20 69 73 20 4f 28 6c 6f 67 4e 29 2e 20 20 54 68   is O(logN).  Th
0910: 65 20 63 6f 73 74 0a 2a 2a 20 6f 66 20 74 68 65  e cost.** of the
0920: 20 66 69 72 73 74 20 53 4d 41 4c 4c 45 53 54 20   first SMALLEST 
0930: 69 73 20 4f 28 4e 6c 6f 67 4e 29 2e 20 20 53 65  is O(NlogN).  Se
0940: 63 6f 6e 64 20 61 6e 64 20 73 75 62 73 65 71 75  cond and subsequ
0950: 65 6e 74 20 53 4d 41 4c 4c 45 53 54 0a 2a 2a 20  ent SMALLEST.** 
0960: 70 72 69 6d 69 74 69 76 65 73 20 61 72 65 20 63  primitives are c
0970: 6f 6e 73 74 61 6e 74 20 74 69 6d 65 2e 20 20 54  onstant time.  T
0980: 68 65 20 63 6f 73 74 20 6f 66 20 44 45 53 54 52  he cost of DESTR
0990: 4f 59 20 69 73 20 4f 28 4e 29 2e 0a 2a 2a 0a 2a  OY is O(N)..**.*
09a0: 2a 20 54 45 53 54 20 61 6e 64 20 53 4d 41 4c 4c  * TEST and SMALL
09b0: 45 53 54 20 6d 61 79 20 6e 6f 74 20 62 65 20 75  EST may not be u
09c0: 73 65 64 20 62 79 20 74 68 65 20 73 61 6d 65 20  sed by the same 
09d0: 52 6f 77 53 65 74 2e 20 20 54 68 69 73 20 75 73  RowSet.  This us
09e0: 65 64 20 74 6f 0a 2a 2a 20 62 65 20 70 6f 73 73  ed to.** be poss
09f0: 69 62 6c 65 2c 20 62 75 74 20 74 68 65 20 66 65  ible, but the fe
0a00: 61 74 75 72 65 20 77 61 73 20 6e 6f 74 20 75 73  ature was not us
0a10: 65 64 2c 20 73 6f 20 69 74 20 77 61 73 20 72 65  ed, so it was re
0a20: 6d 6f 76 65 64 20 69 6e 20 6f 72 64 65 72 0a 2a  moved in order.*
0a30: 2a 20 74 6f 20 73 69 6d 70 6c 69 66 79 20 74 68  * to simplify th
0a40: 65 20 63 6f 64 65 2e 0a 2a 2f 0a 23 69 6e 63 6c  e code..*/.#incl
0a50: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
0a60: 22 0a 0a 0a 2f 2a 0a 2a 2a 20 54 61 72 67 65 74  ".../*.** Target
0a70: 20 73 69 7a 65 20 66 6f 72 20 61 6c 6c 6f 63 61   size for alloca
0a80: 74 69 6f 6e 20 63 68 75 6e 6b 73 2e 0a 2a 2f 0a  tion chunks..*/.
0a90: 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f 41  #define ROWSET_A
0aa0: 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49 5a 45 20 31  LLOCATION_SIZE 1
0ab0: 30 32 34 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 6e  024../*.** The n
0ac0: 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 65 74 20  umber of rowset 
0ad0: 65 6e 74 72 69 65 73 20 70 65 72 20 61 6c 6c 6f  entries per allo
0ae0: 63 61 74 69 6f 6e 20 63 68 75 6e 6b 2e 0a 2a 2f  cation chunk..*/
0af0: 0a 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f  .#define ROWSET_
0b00: 45 4e 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b 20  ENTRY_PER_CHUNK 
0b10: 20 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   \.             
0b20: 20 20 20 20 20 20 20 20 20 20 28 28 52 4f 57 53            ((ROWS
0b30: 45 54 5f 41 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49  ET_ALLOCATION_SI
0b40: 5a 45 2d 38 29 2f 73 69 7a 65 6f 66 28 73 74 72  ZE-8)/sizeof(str
0b50: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 29  uct RowSetEntry)
0b60: 29 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 65 6e  )../*.** Each en
0b70: 74 72 79 20 69 6e 20 61 20 52 6f 77 53 65 74 20  try in a RowSet 
0b80: 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f  is an instance o
0b90: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
0ba0: 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 54 68  object..**.** Th
0bb0: 69 73 20 73 61 6d 65 20 6f 62 6a 65 63 74 20 69  is same object i
0bc0: 73 20 72 65 75 73 65 64 20 74 6f 20 73 74 6f 72  s reused to stor
0bd0: 65 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  e a linked list 
0be0: 6f 66 20 74 72 65 65 73 20 6f 66 20 52 6f 77 53  of trees of RowS
0bf0: 65 74 45 6e 74 72 79 0a 2a 2a 20 6f 62 6a 65 63  etEntry.** objec
0c00: 74 73 2e 20 20 49 6e 20 74 68 61 74 20 61 6c 74  ts.  In that alt
0c10: 65 72 6e 61 74 69 76 65 20 75 73 65 2c 20 70 52  ernative use, pR
0c20: 69 67 68 74 20 70 6f 69 6e 74 73 20 74 6f 20 74  ight points to t
0c30: 68 65 20 6e 65 78 74 20 65 6e 74 72 79 0a 2a 2a  he next entry.**
0c40: 20 69 6e 20 74 68 65 20 6c 69 73 74 2c 20 70 4c   in the list, pL
0c50: 65 66 74 20 70 6f 69 6e 74 73 20 74 6f 20 74 68  eft points to th
0c60: 65 20 74 72 65 65 2c 20 61 6e 64 20 76 20 69 73  e tree, and v is
0c70: 20 75 6e 75 73 65 64 2e 20 20 54 68 65 0a 2a 2a   unused.  The.**
0c80: 20 52 6f 77 53 65 74 2e 70 46 6f 72 65 73 74 20   RowSet.pForest 
0c90: 76 61 6c 75 65 20 70 6f 69 6e 74 73 20 74 6f 20  value points to 
0ca0: 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 69 73  the head of this
0cb0: 20 66 6f 72 65 73 74 20 6c 69 73 74 2e 0a 2a 2f   forest list..*/
0cc0: 0a 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e  .struct RowSetEn
0cd0: 74 72 79 20 7b 20 20 20 20 20 20 20 20 20 20 20  try {           
0ce0: 20 0a 20 20 69 36 34 20 76 3b 20 20 20 20 20 20   .  i64 v;      
0cf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0d00: 20 20 2f 2a 20 52 4f 57 49 44 20 76 61 6c 75 65    /* ROWID value
0d10: 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20   for this entry 
0d20: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
0d30: 65 74 45 6e 74 72 79 20 2a 70 52 69 67 68 74 3b  etEntry *pRight;
0d40: 20 20 20 2f 2a 20 52 69 67 68 74 20 73 75 62 74     /* Right subt
0d50: 72 65 65 20 28 6c 61 72 67 65 72 20 65 6e 74 72  ree (larger entr
0d60: 69 65 73 29 20 6f 72 20 6c 69 73 74 20 2a 2f 0a  ies) or list */.
0d70: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
0d80: 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20 20 20 20  ntry *pLeft;    
0d90: 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65 65 20  /* Left subtree 
0da0: 28 73 6d 61 6c 6c 65 72 20 65 6e 74 72 69 65 73  (smaller entries
0db0: 29 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52  ) */.};../*.** R
0dc0: 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65 63  owSetEntry objec
0dd0: 74 73 20 61 72 65 20 61 6c 6c 6f 63 61 74 65 64  ts are allocated
0de0: 20 69 6e 20 6c 61 72 67 65 20 63 68 75 6e 6b 73   in large chunks
0df0: 20 28 69 6e 73 74 61 6e 63 65 73 20 6f 66 20 74   (instances of t
0e00: 68 65 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20  he.** following 
0e10: 73 74 72 75 63 74 75 72 65 29 20 74 6f 20 72 65  structure) to re
0e20: 64 75 63 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  duce memory allo
0e30: 63 61 74 69 6f 6e 20 6f 76 65 72 68 65 61 64 2e  cation overhead.
0e40: 20 20 54 68 65 0a 2a 2a 20 63 68 75 6e 6b 73 20    The.** chunks 
0e50: 61 72 65 20 6b 65 70 74 20 6f 6e 20 61 20 6c 69  are kept on a li
0e60: 6e 6b 65 64 20 6c 69 73 74 20 73 6f 20 74 68 61  nked list so tha
0e70: 74 20 74 68 65 79 20 63 61 6e 20 62 65 20 64 65  t they can be de
0e80: 61 6c 6c 6f 63 61 74 65 64 0a 2a 2a 20 77 68 65  allocated.** whe
0e90: 6e 20 74 68 65 20 52 6f 77 53 65 74 20 69 73 20  n the RowSet is 
0ea0: 64 65 73 74 72 6f 79 65 64 2e 0a 2a 2f 0a 73 74  destroyed..*/.st
0eb0: 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b  ruct RowSetChunk
0ec0: 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53   {.  struct RowS
0ed0: 65 74 43 68 75 6e 6b 20 2a 70 4e 65 78 74 43 68  etChunk *pNextCh
0ee0: 75 6e 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e  unk;        /* N
0ef0: 65 78 74 20 63 68 75 6e 6b 20 6f 6e 20 6c 69 73  ext chunk on lis
0f00: 74 20 6f 66 20 74 68 65 6d 20 61 6c 6c 20 2a 2f  t of them all */
0f10: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
0f20: 45 6e 74 72 79 20 61 45 6e 74 72 79 5b 52 4f 57  Entry aEntry[ROW
0f30: 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f 43 48  SET_ENTRY_PER_CH
0f40: 55 4e 4b 5d 3b 20 2f 2a 20 41 6c 6c 6f 63 61 74  UNK]; /* Allocat
0f50: 65 64 20 65 6e 74 72 69 65 73 20 2a 2f 0a 7d 3b  ed entries */.};
0f60: 0a 0a 2f 2a 0a 2a 2a 20 41 20 52 6f 77 53 65 74  ../*.** A RowSet
0f70: 20 69 6e 20 61 6e 20 69 6e 73 74 61 6e 63 65 20   in an instance 
0f80: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0f90: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
0fa0: 2a 20 41 20 74 79 70 65 64 65 66 20 6f 66 20 74  * A typedef of t
0fb0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69 66  his structure if
0fc0: 20 66 6f 75 6e 64 20 69 6e 20 73 71 6c 69 74 65   found in sqlite
0fd0: 49 6e 74 2e 68 2e 0a 2a 2f 0a 73 74 72 75 63 74  Int.h..*/.struct
0fe0: 20 52 6f 77 53 65 74 20 7b 0a 20 20 73 74 72 75   RowSet {.  stru
0ff0: 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a  ct RowSetChunk *
1000: 70 43 68 75 6e 6b 3b 20 20 20 20 2f 2a 20 4c 69  pChunk;    /* Li
1010: 73 74 20 6f 66 20 61 6c 6c 20 63 68 75 6e 6b 20  st of all chunk 
1020: 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 20  allocations */. 
1030: 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20 20 20   sqlite3 *db;   
1040: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1050: 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  /* The database 
1060: 63 6f 6e 6e 65 63 74 69 6f 6e 20 2a 2f 0a 20 20  connection */.  
1070: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1080: 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 20 20 2f  ry *pEntry;    /
1090: 2a 20 4c 69 73 74 20 6f 66 20 65 6e 74 72 69 65  * List of entrie
10a0: 73 20 75 73 69 6e 67 20 70 52 69 67 68 74 20 2a  s using pRight *
10b0: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
10c0: 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20 20  tEntry *pLast;  
10d0: 20 20 20 2f 2a 20 4c 61 73 74 20 65 6e 74 72 79     /* Last entry
10e0: 20 6f 6e 20 74 68 65 20 70 45 6e 74 72 79 20 6c   on the pEntry l
10f0: 69 73 74 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ist */.  struct 
1100: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 46 72  RowSetEntry *pFr
1110: 65 73 68 3b 20 20 20 20 2f 2a 20 53 6f 75 72 63  esh;    /* Sourc
1120: 65 20 6f 66 20 6e 65 77 20 65 6e 74 72 79 20 6f  e of new entry o
1130: 62 6a 65 63 74 73 20 2a 2f 0a 20 20 73 74 72 75  bjects */.  stru
1140: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
1150: 70 46 6f 72 65 73 74 3b 20 20 20 2f 2a 20 4c 69  pForest;   /* Li
1160: 73 74 20 6f 66 20 62 69 6e 61 72 79 20 74 72 65  st of binary tre
1170: 65 73 20 6f 66 20 65 6e 74 72 69 65 73 20 2a 2f  es of entries */
1180: 0a 20 20 75 31 36 20 6e 46 72 65 73 68 3b 20 20  .  u16 nFresh;  
1190: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11a0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f    /* Number of o
11b0: 62 6a 65 63 74 73 20 6f 6e 20 70 46 72 65 73 68  bjects on pFresh
11c0: 20 2a 2f 0a 20 20 75 31 36 20 72 73 46 6c 61 67   */.  u16 rsFlag
11d0: 73 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  s;              
11e0: 20 20 20 20 20 2f 2a 20 56 61 72 69 6f 75 73 20       /* Various 
11f0: 66 6c 61 67 73 20 2a 2f 0a 20 20 69 6e 74 20 69  flags */.  int i
1200: 42 61 74 63 68 3b 20 20 20 20 20 20 20 20 20 20  Batch;          
1210: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
1220: 72 65 6e 74 20 69 6e 73 65 72 74 20 62 61 74 63  rent insert batc
1230: 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41  h */.};../*.** A
1240: 6c 6c 6f 77 65 64 20 76 61 6c 75 65 73 20 66 6f  llowed values fo
1250: 72 20 52 6f 77 53 65 74 2e 72 73 46 6c 61 67 73  r RowSet.rsFlags
1260: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 57 53  .*/.#define ROWS
1270: 45 54 5f 53 4f 52 54 45 44 20 20 30 78 30 31 20  ET_SORTED  0x01 
1280: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 52 6f 77    /* True if Row
1290: 53 65 74 2e 70 45 6e 74 72 79 20 69 73 20 73 6f  Set.pEntry is so
12a0: 72 74 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20  rted */.#define 
12b0: 52 4f 57 53 45 54 5f 4e 45 58 54 20 20 20 20 30  ROWSET_NEXT    0
12c0: 78 30 32 20 20 20 2f 2a 20 54 72 75 65 20 69 66  x02   /* True if
12d0: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65   sqlite3RowSetNe
12e0: 78 74 28 29 20 68 61 73 20 62 65 65 6e 20 63 61  xt() has been ca
12f0: 6c 6c 65 64 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54  lled */../*.** T
1300: 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72 79 20  urn bulk memory 
1310: 69 6e 74 6f 20 61 20 52 6f 77 53 65 74 20 6f 62  into a RowSet ob
1320: 6a 65 63 74 2e 20 20 4e 20 62 79 74 65 73 20 6f  ject.  N bytes o
1330: 66 20 6d 65 6d 6f 72 79 0a 2a 2a 20 61 72 65 20  f memory.** are 
1340: 61 76 61 69 6c 61 62 6c 65 20 61 74 20 70 53 70  available at pSp
1350: 61 63 65 2e 20 20 54 68 65 20 64 62 20 70 6f 69  ace.  The db poi
1360: 6e 74 65 72 20 69 73 20 75 73 65 64 20 61 73 20  nter is used as 
1370: 61 20 6d 65 6d 6f 72 79 20 63 6f 6e 74 65 78 74  a memory context
1380: 0a 2a 2a 20 66 6f 72 20 61 6e 79 20 73 75 62 73  .** for any subs
1390: 65 71 75 65 6e 74 20 61 6c 6c 6f 63 61 74 69 6f  equent allocatio
13a0: 6e 73 20 74 68 61 74 20 6e 65 65 64 20 74 6f 20  ns that need to 
13b0: 6f 63 63 75 72 2e 0a 2a 2a 20 52 65 74 75 72 6e  occur..** Return
13c0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
13d0: 65 20 6e 65 77 20 52 6f 77 53 65 74 20 6f 62 6a  e new RowSet obj
13e0: 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 49 74 20 6d 75  ect..**.** It mu
13f0: 73 74 20 62 65 20 74 68 65 20 63 61 73 65 20 74  st be the case t
1400: 68 61 74 20 4e 20 69 73 20 73 75 66 66 69 63 69  hat N is suffici
1410: 65 6e 74 20 74 6f 20 6d 61 6b 65 20 61 20 52 6f  ent to make a Ro
1420: 77 73 65 74 2e 20 20 49 66 20 6e 6f 74 0a 2a 2a  wset.  If not.**
1430: 20 61 6e 20 61 73 73 65 72 74 69 6f 6e 20 66 61   an assertion fa
1440: 75 6c 74 20 6f 63 63 75 72 73 2e 0a 2a 2a 20 0a  ult occurs..** .
1450: 2a 2a 20 49 66 20 4e 20 69 73 20 6c 61 72 67 65  ** If N is large
1460: 72 20 74 68 61 6e 20 74 68 65 20 6d 69 6e 69 6d  r than the minim
1470: 75 6d 2c 20 75 73 65 20 74 68 65 20 73 75 72 70  um, use the surp
1480: 6c 75 73 20 61 73 20 61 6e 20 69 6e 69 74 69 61  lus as an initia
1490: 6c 0a 2a 2a 20 61 6c 6c 6f 63 61 74 69 6f 6e 20  l.** allocation 
14a0: 6f 66 20 65 6e 74 72 69 65 73 20 61 76 61 69 6c  of entries avail
14b0: 61 62 6c 65 20 74 6f 20 62 65 20 66 69 6c 6c 65  able to be fille
14c0: 64 2e 0a 2a 2f 0a 52 6f 77 53 65 74 20 2a 73 71  d..*/.RowSet *sq
14d0: 6c 69 74 65 33 52 6f 77 53 65 74 49 6e 69 74 28  lite3RowSetInit(
14e0: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 76 6f 69  sqlite3 *db, voi
14f0: 64 20 2a 70 53 70 61 63 65 2c 20 75 6e 73 69 67  d *pSpace, unsig
1500: 6e 65 64 20 69 6e 74 20 4e 29 7b 0a 20 20 52 6f  ned int N){.  Ro
1510: 77 53 65 74 20 2a 70 3b 0a 20 20 61 73 73 65 72  wSet *p;.  asser
1520: 74 28 20 4e 20 3e 3d 20 52 4f 55 4e 44 38 28 73  t( N >= ROUND8(s
1530: 69 7a 65 6f 66 28 2a 70 29 29 20 29 3b 0a 20 20  izeof(*p)) );.  
1540: 70 20 3d 20 70 53 70 61 63 65 3b 0a 20 20 70 2d  p = pSpace;.  p-
1550: 3e 70 43 68 75 6e 6b 20 3d 20 30 3b 0a 20 20 70  >pChunk = 0;.  p
1560: 2d 3e 64 62 20 3d 20 64 62 3b 0a 20 20 70 2d 3e  ->db = db;.  p->
1570: 70 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 70 2d  pEntry = 0;.  p-
1580: 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20 20 70 2d  >pLast = 0;.  p-
1590: 3e 70 46 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20  >pForest = 0;.  
15a0: 70 2d 3e 70 46 72 65 73 68 20 3d 20 28 73 74 72  p->pFresh = (str
15b0: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 2a  uct RowSetEntry*
15c0: 29 28 52 4f 55 4e 44 38 28 73 69 7a 65 6f 66 28  )(ROUND8(sizeof(
15d0: 2a 70 29 29 20 2b 20 28 63 68 61 72 2a 29 70 29  *p)) + (char*)p)
15e0: 3b 0a 20 20 70 2d 3e 6e 46 72 65 73 68 20 3d 20  ;.  p->nFresh = 
15f0: 28 75 31 36 29 28 28 4e 20 2d 20 52 4f 55 4e 44  (u16)((N - ROUND
1600: 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 29 2f 73  8(sizeof(*p)))/s
1610: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 52 6f 77  izeof(struct Row
1620: 53 65 74 45 6e 74 72 79 29 29 3b 0a 20 20 70 2d  SetEntry));.  p-
1630: 3e 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53 45  >rsFlags = ROWSE
1640: 54 5f 53 4f 52 54 45 44 3b 0a 20 20 70 2d 3e 69  T_SORTED;.  p->i
1650: 42 61 74 63 68 20 3d 20 30 3b 0a 20 20 72 65 74  Batch = 0;.  ret
1660: 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  urn p;.}../*.** 
1670: 44 65 61 6c 6c 6f 63 61 74 65 20 61 6c 6c 20 63  Deallocate all c
1680: 68 75 6e 6b 73 20 66 72 6f 6d 20 61 20 52 6f 77  hunks from a Row
1690: 53 65 74 2e 20 20 54 68 69 73 20 66 72 65 65 73  Set.  This frees
16a0: 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 74 68 61 74   all memory that
16b0: 0a 2a 2a 20 74 68 65 20 52 6f 77 53 65 74 20 68  .** the RowSet h
16c0: 61 73 20 61 6c 6c 6f 63 61 74 65 64 20 6f 76 65  as allocated ove
16d0: 72 20 69 74 73 20 6c 69 66 65 74 69 6d 65 2e 20  r its lifetime. 
16e0: 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 69 73   This routine is
16f0: 0a 2a 2a 20 74 68 65 20 64 65 73 74 72 75 63 74  .** the destruct
1700: 6f 72 20 66 6f 72 20 74 68 65 20 52 6f 77 53 65  or for the RowSe
1710: 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  t..*/.void sqlit
1720: 65 33 52 6f 77 53 65 74 43 6c 65 61 72 28 52 6f  e3RowSetClear(Ro
1730: 77 53 65 74 20 2a 70 29 7b 0a 20 20 73 74 72 75  wSet *p){.  stru
1740: 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a  ct RowSetChunk *
1750: 70 43 68 75 6e 6b 2c 20 2a 70 4e 65 78 74 43 68  pChunk, *pNextCh
1760: 75 6e 6b 3b 0a 20 20 66 6f 72 28 70 43 68 75 6e  unk;.  for(pChun
1770: 6b 3d 70 2d 3e 70 43 68 75 6e 6b 3b 20 70 43 68  k=p->pChunk; pCh
1780: 75 6e 6b 3b 20 70 43 68 75 6e 6b 20 3d 20 70 4e  unk; pChunk = pN
1790: 65 78 74 43 68 75 6e 6b 29 7b 0a 20 20 20 20 70  extChunk){.    p
17a0: 4e 65 78 74 43 68 75 6e 6b 20 3d 20 70 43 68 75  NextChunk = pChu
17b0: 6e 6b 2d 3e 70 4e 65 78 74 43 68 75 6e 6b 3b 0a  nk->pNextChunk;.
17c0: 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 72 65      sqlite3DbFre
17d0: 65 28 70 2d 3e 64 62 2c 20 70 43 68 75 6e 6b 29  e(p->db, pChunk)
17e0: 3b 0a 20 20 7d 0a 20 20 70 2d 3e 70 43 68 75 6e  ;.  }.  p->pChun
17f0: 6b 20 3d 20 30 3b 0a 20 20 70 2d 3e 6e 46 72 65  k = 0;.  p->nFre
1800: 73 68 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 45 6e  sh = 0;.  p->pEn
1810: 74 72 79 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 4c  try = 0;.  p->pL
1820: 61 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 46  ast = 0;.  p->pF
1830: 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e  orest = 0;.  p->
1840: 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53 45 54  rsFlags = ROWSET
1850: 5f 53 4f 52 54 45 44 3b 0a 7d 0a 0a 2f 2a 0a 2a  _SORTED;.}../*.*
1860: 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e 65 77  * Allocate a new
1870: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a   RowSetEntry obj
1880: 65 63 74 20 74 68 61 74 20 69 73 20 61 73 73 6f  ect that is asso
1890: 63 69 61 74 65 64 20 77 69 74 68 20 74 68 65 0a  ciated with the.
18a0: 2a 2a 20 67 69 76 65 6e 20 52 6f 77 53 65 74 2e  ** given RowSet.
18b0: 20 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74    Return a point
18c0: 65 72 20 74 6f 20 74 68 65 20 6e 65 77 20 61 6e  er to the new an
18d0: 64 20 63 6f 6d 70 6c 65 74 65 6c 79 20 75 6e 69  d completely uni
18e0: 6e 69 74 69 61 6c 69 7a 65 64 0a 2a 2a 20 6f 62  nitialized.** ob
18f0: 6a 65 63 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 6e  jected..**.** In
1900: 20 61 6e 20 4f 4f 4d 20 73 69 74 75 61 74 69 6f   an OOM situatio
1910: 6e 2c 20 74 68 65 20 52 6f 77 53 65 74 2e 64 62  n, the RowSet.db
1920: 2d 3e 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 20 66  ->mallocFailed f
1930: 6c 61 67 20 69 73 20 73 65 74 20 61 6e 64 20 74  lag is set and t
1940: 68 69 73 0a 2a 2a 20 72 6f 75 74 69 6e 65 20 72  his.** routine r
1950: 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 2a 2f 0a  eturns NULL..*/.
1960: 73 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f  static struct Ro
1970: 77 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65  wSetEntry *rowSe
1980: 74 45 6e 74 72 79 41 6c 6c 6f 63 28 52 6f 77 53  tEntryAlloc(RowS
1990: 65 74 20 2a 70 29 7b 0a 20 20 61 73 73 65 72 74  et *p){.  assert
19a0: 28 20 70 21 3d 30 20 29 3b 0a 20 20 69 66 28 20  ( p!=0 );.  if( 
19b0: 70 2d 3e 6e 46 72 65 73 68 3d 3d 30 20 29 7b 20  p->nFresh==0 ){ 
19c0: 20 2f 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d   /*OPTIMIZATION-
19d0: 49 46 2d 46 41 4c 53 45 2a 2f 0a 20 20 20 20 2f  IF-FALSE*/.    /
19e0: 2a 20 57 65 20 63 6f 75 6c 64 20 61 6c 6c 6f 63  * We could alloc
19f0: 61 74 65 20 61 20 66 72 65 73 68 20 52 6f 77 53  ate a fresh RowS
1a00: 65 74 45 6e 74 72 79 20 65 61 63 68 20 74 69 6d  etEntry each tim
1a10: 65 20 6f 6e 65 20 69 73 20 6e 65 65 64 65 64 2c  e one is needed,
1a20: 20 62 75 74 20 69 74 0a 20 20 20 20 2a 2a 20 69   but it.    ** i
1a30: 73 20 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74  s more efficient
1a40: 20 74 6f 20 70 75 6c 6c 20 61 20 70 72 65 61 6c   to pull a preal
1a50: 6c 6f 63 61 74 65 64 20 65 6e 74 72 79 20 66 72  located entry fr
1a60: 6f 6d 20 74 68 65 20 70 6f 6f 6c 20 2a 2f 0a 20  om the pool */. 
1a70: 20 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74     struct RowSet
1a80: 43 68 75 6e 6b 20 2a 70 4e 65 77 3b 0a 20 20 20  Chunk *pNew;.   
1a90: 20 70 4e 65 77 20 3d 20 73 71 6c 69 74 65 33 44   pNew = sqlite3D
1aa0: 62 4d 61 6c 6c 6f 63 52 61 77 4e 4e 28 70 2d 3e  bMallocRawNN(p->
1ab0: 64 62 2c 20 73 69 7a 65 6f 66 28 2a 70 4e 65 77  db, sizeof(*pNew
1ac0: 29 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77  ));.    if( pNew
1ad0: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 74  ==0 ){.      ret
1ae0: 75 72 6e 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20  urn 0;.    }.   
1af0: 20 70 4e 65 77 2d 3e 70 4e 65 78 74 43 68 75 6e   pNew->pNextChun
1b00: 6b 20 3d 20 70 2d 3e 70 43 68 75 6e 6b 3b 0a 20  k = p->pChunk;. 
1b10: 20 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d 20 70     p->pChunk = p
1b20: 4e 65 77 3b 0a 20 20 20 20 70 2d 3e 70 46 72 65  New;.    p->pFre
1b30: 73 68 20 3d 20 70 4e 65 77 2d 3e 61 45 6e 74 72  sh = pNew->aEntr
1b40: 79 3b 0a 20 20 20 20 70 2d 3e 6e 46 72 65 73 68  y;.    p->nFresh
1b50: 20 3d 20 52 4f 57 53 45 54 5f 45 4e 54 52 59 5f   = ROWSET_ENTRY_
1b60: 50 45 52 5f 43 48 55 4e 4b 3b 0a 20 20 7d 0a 20  PER_CHUNK;.  }. 
1b70: 20 70 2d 3e 6e 46 72 65 73 68 2d 2d 3b 0a 20 20   p->nFresh--;.  
1b80: 72 65 74 75 72 6e 20 70 2d 3e 70 46 72 65 73 68  return p->pFresh
1b90: 2b 2b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 73  ++;.}../*.** Ins
1ba0: 65 72 74 20 61 20 6e 65 77 20 76 61 6c 75 65 20  ert a new value 
1bb0: 69 6e 74 6f 20 61 20 52 6f 77 53 65 74 2e 0a 2a  into a RowSet..*
1bc0: 2a 0a 2a 2a 20 54 68 65 20 6d 61 6c 6c 6f 63 46  *.** The mallocF
1bd0: 61 69 6c 65 64 20 66 6c 61 67 20 6f 66 20 74 68  ailed flag of th
1be0: 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  e database conne
1bf0: 63 74 69 6f 6e 20 69 73 20 73 65 74 20 69 66 20  ction is set if 
1c00: 61 0a 2a 2a 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  a.** memory allo
1c10: 63 61 74 69 6f 6e 20 66 61 69 6c 73 2e 0a 2a 2f  cation fails..*/
1c20: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77  .void sqlite3Row
1c30: 53 65 74 49 6e 73 65 72 74 28 52 6f 77 53 65 74  SetInsert(RowSet
1c40: 20 2a 70 2c 20 69 36 34 20 72 6f 77 69 64 29 7b   *p, i64 rowid){
1c50: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
1c60: 45 6e 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20  Entry *pEntry;  
1c70: 2f 2a 20 54 68 65 20 6e 65 77 20 65 6e 74 72 79  /* The new entry
1c80: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
1c90: 53 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b  SetEntry *pLast;
1ca0: 20 20 20 2f 2a 20 54 68 65 20 6c 61 73 74 20 70     /* The last p
1cb0: 72 69 6f 72 20 65 6e 74 72 79 20 2a 2f 0a 0a 20  rior entry */.. 
1cc0: 20 2f 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65   /* This routine
1cd0: 20 69 73 20 6e 65 76 65 72 20 63 61 6c 6c 65 64   is never called
1ce0: 20 61 66 74 65 72 20 73 71 6c 69 74 65 33 52 6f   after sqlite3Ro
1cf0: 77 53 65 74 4e 65 78 74 28 29 20 2a 2f 0a 20 20  wSetNext() */.  
1d00: 61 73 73 65 72 74 28 20 70 21 3d 30 20 26 26 20  assert( p!=0 && 
1d10: 28 70 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f  (p->rsFlags & RO
1d20: 57 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b  WSET_NEXT)==0 );
1d30: 0a 0a 20 20 70 45 6e 74 72 79 20 3d 20 72 6f 77  ..  pEntry = row
1d40: 53 65 74 45 6e 74 72 79 41 6c 6c 6f 63 28 70 29  SetEntryAlloc(p)
1d50: 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79 3d 3d  ;.  if( pEntry==
1d60: 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 70 45  0 ) return;.  pE
1d70: 6e 74 72 79 2d 3e 76 20 3d 20 72 6f 77 69 64 3b  ntry->v = rowid;
1d80: 0a 20 20 70 45 6e 74 72 79 2d 3e 70 52 69 67 68  .  pEntry->pRigh
1d90: 74 20 3d 20 30 3b 0a 20 20 70 4c 61 73 74 20 3d  t = 0;.  pLast =
1da0: 20 70 2d 3e 70 4c 61 73 74 3b 0a 20 20 69 66 28   p->pLast;.  if(
1db0: 20 70 4c 61 73 74 20 29 7b 0a 20 20 20 20 69 66   pLast ){.    if
1dc0: 28 20 72 6f 77 69 64 3c 3d 70 4c 61 73 74 2d 3e  ( rowid<=pLast->
1dd0: 76 20 29 7b 20 20 2f 2a 4f 50 54 49 4d 49 5a 41  v ){  /*OPTIMIZA
1de0: 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45 2a 2f 0a  TION-IF-FALSE*/.
1df0: 20 20 20 20 20 20 2f 2a 20 41 76 6f 69 64 20 75        /* Avoid u
1e00: 6e 6e 65 63 65 73 73 61 72 79 20 73 6f 72 74 73  nnecessary sorts
1e10: 20 62 79 20 70 72 65 73 65 72 76 69 6e 67 20 74   by preserving t
1e20: 68 65 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44  he ROWSET_SORTED
1e30: 20 66 6c 61 67 73 0a 20 20 20 20 20 20 2a 2a 20   flags.      ** 
1e40: 77 68 65 72 65 20 70 6f 73 73 69 62 6c 65 20 2a  where possible *
1e50: 2f 0a 20 20 20 20 20 20 70 2d 3e 72 73 46 6c 61  /.      p->rsFla
1e60: 67 73 20 26 3d 20 7e 52 4f 57 53 45 54 5f 53 4f  gs &= ~ROWSET_SO
1e70: 52 54 45 44 3b 0a 20 20 20 20 7d 0a 20 20 20 20  RTED;.    }.    
1e80: 70 4c 61 73 74 2d 3e 70 52 69 67 68 74 20 3d 20  pLast->pRight = 
1e90: 70 45 6e 74 72 79 3b 0a 20 20 7d 65 6c 73 65 7b  pEntry;.  }else{
1ea0: 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79 20 3d  .    p->pEntry =
1eb0: 20 70 45 6e 74 72 79 3b 0a 20 20 7d 0a 20 20 70   pEntry;.  }.  p
1ec0: 2d 3e 70 4c 61 73 74 20 3d 20 70 45 6e 74 72 79  ->pLast = pEntry
1ed0: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 4d 65 72 67 65  ;.}../*.** Merge
1ee0: 20 74 77 6f 20 6c 69 73 74 73 20 6f 66 20 52 6f   two lists of Ro
1ef0: 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65 63 74  wSetEntry object
1f00: 73 2e 20 20 52 65 6d 6f 76 65 20 64 75 70 6c 69  s.  Remove dupli
1f10: 63 61 74 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  cates..**.** The
1f20: 20 69 6e 70 75 74 20 6c 69 73 74 73 20 61 72 65   input lists are
1f30: 20 63 6f 6e 6e 65 63 74 65 64 20 76 69 61 20 70   connected via p
1f40: 52 69 67 68 74 20 70 6f 69 6e 74 65 72 73 20 61  Right pointers a
1f50: 6e 64 20 61 72 65 20 0a 2a 2a 20 61 73 73 75 6d  nd are .** assum
1f60: 65 64 20 74 6f 20 65 61 63 68 20 61 6c 72 65 61  ed to each alrea
1f70: 64 79 20 62 65 20 69 6e 20 73 6f 72 74 65 64 20  dy be in sorted 
1f80: 6f 72 64 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63  order..*/.static
1f90: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
1fa0: 74 72 79 20 2a 72 6f 77 53 65 74 45 6e 74 72 79  try *rowSetEntry
1fb0: 4d 65 72 67 65 28 0a 20 20 73 74 72 75 63 74 20  Merge(.  struct 
1fc0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 41 2c  RowSetEntry *pA,
1fd0: 20 20 20 20 2f 2a 20 46 69 72 73 74 20 73 6f 72      /* First sor
1fe0: 74 65 64 20 6c 69 73 74 20 74 6f 20 62 65 20 6d  ted list to be m
1ff0: 65 72 67 65 64 20 2a 2f 0a 20 20 73 74 72 75 63  erged */.  struc
2000: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70  t RowSetEntry *p
2010: 42 20 20 20 20 20 2f 2a 20 53 65 63 6f 6e 64 20  B     /* Second 
2020: 73 6f 72 74 65 64 20 6c 69 73 74 20 74 6f 20 62  sorted list to b
2030: 65 20 6d 65 72 67 65 64 20 2a 2f 0a 29 7b 0a 20  e merged */.){. 
2040: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
2050: 74 72 79 20 68 65 61 64 3b 0a 20 20 73 74 72 75  try head;.  stru
2060: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2070: 70 54 61 69 6c 3b 0a 0a 20 20 70 54 61 69 6c 20  pTail;..  pTail 
2080: 3d 20 26 68 65 61 64 3b 0a 20 20 61 73 73 65 72  = &head;.  asser
2090: 74 28 20 70 41 21 3d 30 20 26 26 20 70 42 21 3d  t( pA!=0 && pB!=
20a0: 30 20 29 3b 0a 20 20 66 6f 72 28 3b 3b 29 7b 0a  0 );.  for(;;){.
20b0: 20 20 20 20 61 73 73 65 72 74 28 20 70 41 2d 3e      assert( pA->
20c0: 70 52 69 67 68 74 3d 3d 30 20 7c 7c 20 70 41 2d  pRight==0 || pA-
20d0: 3e 76 3c 3d 70 41 2d 3e 70 52 69 67 68 74 2d 3e  >v<=pA->pRight->
20e0: 76 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  v );.    assert(
20f0: 20 70 42 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c   pB->pRight==0 |
2100: 7c 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e 70 52 69  | pB->v<=pB->pRi
2110: 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 69 66  ght->v );.    if
2120: 28 20 70 41 2d 3e 76 3c 3d 70 42 2d 3e 76 20 29  ( pA->v<=pB->v )
2130: 7b 0a 20 20 20 20 20 20 69 66 28 20 70 41 2d 3e  {.      if( pA->
2140: 76 3c 70 42 2d 3e 76 20 29 20 70 54 61 69 6c 20  v<pB->v ) pTail 
2150: 3d 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74 20  = pTail->pRight 
2160: 3d 20 70 41 3b 0a 20 20 20 20 20 20 70 41 20 3d  = pA;.      pA =
2170: 20 70 41 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20   pA->pRight;.   
2180: 20 20 20 69 66 28 20 70 41 3d 3d 30 20 29 7b 0a     if( pA==0 ){.
2190: 20 20 20 20 20 20 20 20 70 54 61 69 6c 2d 3e 70          pTail->p
21a0: 52 69 67 68 74 20 3d 20 70 42 3b 0a 20 20 20 20  Right = pB;.    
21b0: 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20      break;.     
21c0: 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20   }.    }else{.  
21d0: 20 20 20 20 70 54 61 69 6c 20 3d 20 70 54 61 69      pTail = pTai
21e0: 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42 3b 0a  l->pRight = pB;.
21f0: 20 20 20 20 20 20 70 42 20 3d 20 70 42 2d 3e 70        pB = pB->p
2200: 52 69 67 68 74 3b 0a 20 20 20 20 20 20 69 66 28  Right;.      if(
2210: 20 70 42 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20   pB==0 ){.      
2220: 20 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74 20    pTail->pRight 
2230: 3d 20 70 41 3b 0a 20 20 20 20 20 20 20 20 62 72  = pA;.        br
2240: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  eak;.      }.   
2250: 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20   }.  }.  return 
2260: 68 65 61 64 2e 70 52 69 67 68 74 3b 0a 7d 0a 0a  head.pRight;.}..
2270: 2f 2a 0a 2a 2a 20 53 6f 72 74 20 61 6c 6c 20 65  /*.** Sort all e
2280: 6c 65 6d 65 6e 74 73 20 6f 6e 20 74 68 65 20 6c  lements on the l
2290: 69 73 74 20 6f 66 20 52 6f 77 53 65 74 45 6e 74  ist of RowSetEnt
22a0: 72 79 20 6f 62 6a 65 63 74 73 20 69 6e 74 6f 20  ry objects into 
22b0: 6f 72 64 65 72 20 6f 66 0a 2a 2a 20 69 6e 63 72  order of.** incr
22c0: 65 61 73 69 6e 67 20 76 2e 0a 2a 2f 20 0a 73 74  easing v..*/ .st
22d0: 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53  atic struct RowS
22e0: 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 45  etEntry *rowSetE
22f0: 6e 74 72 79 53 6f 72 74 28 73 74 72 75 63 74 20  ntrySort(struct 
2300: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 49 6e  RowSetEntry *pIn
2310: 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  ){.  unsigned in
2320: 74 20 69 3b 0a 20 20 73 74 72 75 63 74 20 52 6f  t i;.  struct Ro
2330: 77 53 65 74 45 6e 74 72 79 20 2a 70 4e 65 78 74  wSetEntry *pNext
2340: 2c 20 2a 61 42 75 63 6b 65 74 5b 34 30 5d 3b 0a  , *aBucket[40];.
2350: 0a 20 20 6d 65 6d 73 65 74 28 61 42 75 63 6b 65  .  memset(aBucke
2360: 74 2c 20 30 2c 20 73 69 7a 65 6f 66 28 61 42 75  t, 0, sizeof(aBu
2370: 63 6b 65 74 29 29 3b 0a 20 20 77 68 69 6c 65 28  cket));.  while(
2380: 20 70 49 6e 20 29 7b 0a 20 20 20 20 70 4e 65 78   pIn ){.    pNex
2390: 74 20 3d 20 70 49 6e 2d 3e 70 52 69 67 68 74 3b  t = pIn->pRight;
23a0: 0a 20 20 20 20 70 49 6e 2d 3e 70 52 69 67 68 74  .    pIn->pRight
23b0: 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d   = 0;.    for(i=
23c0: 30 3b 20 61 42 75 63 6b 65 74 5b 69 5d 3b 20 69  0; aBucket[i]; i
23d0: 2b 2b 29 7b 0a 20 20 20 20 20 20 70 49 6e 20 3d  ++){.      pIn =
23e0: 20 72 6f 77 53 65 74 45 6e 74 72 79 4d 65 72 67   rowSetEntryMerg
23f0: 65 28 61 42 75 63 6b 65 74 5b 69 5d 2c 20 70 49  e(aBucket[i], pI
2400: 6e 29 3b 0a 20 20 20 20 20 20 61 42 75 63 6b 65  n);.      aBucke
2410: 74 5b 69 5d 20 3d 20 30 3b 0a 20 20 20 20 7d 0a  t[i] = 0;.    }.
2420: 20 20 20 20 61 42 75 63 6b 65 74 5b 69 5d 20 3d      aBucket[i] =
2430: 20 70 49 6e 3b 0a 20 20 20 20 70 49 6e 20 3d 20   pIn;.    pIn = 
2440: 70 4e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 49 6e  pNext;.  }.  pIn
2450: 20 3d 20 61 42 75 63 6b 65 74 5b 30 5d 3b 0a 20   = aBucket[0];. 
2460: 20 66 6f 72 28 69 3d 31 3b 20 69 3c 73 69 7a 65   for(i=1; i<size
2470: 6f 66 28 61 42 75 63 6b 65 74 29 2f 73 69 7a 65  of(aBucket)/size
2480: 6f 66 28 61 42 75 63 6b 65 74 5b 30 5d 29 3b 20  of(aBucket[0]); 
2490: 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 20 61 42  i++){.    if( aB
24a0: 75 63 6b 65 74 5b 69 5d 3d 3d 30 20 29 20 63 6f  ucket[i]==0 ) co
24b0: 6e 74 69 6e 75 65 3b 0a 20 20 20 20 70 49 6e 20  ntinue;.    pIn 
24c0: 3d 20 70 49 6e 20 3f 20 72 6f 77 53 65 74 45 6e  = pIn ? rowSetEn
24d0: 74 72 79 4d 65 72 67 65 28 70 49 6e 2c 20 61 42  tryMerge(pIn, aB
24e0: 75 63 6b 65 74 5b 69 5d 29 20 3a 20 61 42 75 63  ucket[i]) : aBuc
24f0: 6b 65 74 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72 65  ket[i];.  }.  re
2500: 74 75 72 6e 20 70 49 6e 3b 0a 7d 0a 0a 0a 2f 2a  turn pIn;.}.../*
2510: 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74 2c 20 70  .** The input, p
2520: 49 6e 2c 20 69 73 20 61 20 62 69 6e 61 72 79 20  In, is a binary 
2530: 74 72 65 65 20 28 6f 72 20 73 75 62 74 72 65 65  tree (or subtree
2540: 29 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79  ) of RowSetEntry
2550: 20 6f 62 6a 65 63 74 73 2e 0a 2a 2a 20 43 6f 6e   objects..** Con
2560: 76 65 72 74 20 74 68 69 73 20 74 72 65 65 20 69  vert this tree i
2570: 6e 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73  nto a linked lis
2580: 74 20 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 74  t connected by t
2590: 68 65 20 70 52 69 67 68 74 20 70 6f 69 6e 74 65  he pRight pointe
25a0: 72 73 0a 2a 2a 20 61 6e 64 20 72 65 74 75 72 6e  rs.** and return
25b0: 20 70 6f 69 6e 74 65 72 73 20 74 6f 20 74 68 65   pointers to the
25c0: 20 66 69 72 73 74 20 61 6e 64 20 6c 61 73 74 20   first and last 
25d0: 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20  elements of the 
25e0: 6e 65 77 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  new list..*/.sta
25f0: 74 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74 54  tic void rowSetT
2600: 72 65 65 54 6f 4c 69 73 74 28 0a 20 20 73 74 72  reeToList(.  str
2610: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2620: 2a 70 49 6e 2c 20 20 20 20 20 20 20 20 20 2f 2a  *pIn,         /*
2630: 20 52 6f 6f 74 20 6f 66 20 74 68 65 20 69 6e 70   Root of the inp
2640: 75 74 20 74 72 65 65 20 2a 2f 0a 20 20 73 74 72  ut tree */.  str
2650: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2660: 2a 2a 70 70 46 69 72 73 74 2c 20 20 20 20 2f 2a  **ppFirst,    /*
2670: 20 57 72 69 74 65 20 68 65 61 64 20 6f 66 20 74   Write head of t
2680: 68 65 20 6f 75 74 70 75 74 20 6c 69 73 74 20 68  he output list h
2690: 65 72 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ere */.  struct 
26a0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a 70 70  RowSetEntry **pp
26b0: 4c 61 73 74 20 20 20 20 20 20 2f 2a 20 57 72 69  Last      /* Wri
26c0: 74 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20 6f  te tail of the o
26d0: 75 74 70 75 74 20 6c 69 73 74 20 68 65 72 65 20  utput list here 
26e0: 2a 2f 0a 29 7b 0a 20 20 61 73 73 65 72 74 28 20  */.){.  assert( 
26f0: 70 49 6e 21 3d 30 20 29 3b 0a 20 20 69 66 28 20  pIn!=0 );.  if( 
2700: 70 49 6e 2d 3e 70 4c 65 66 74 20 29 7b 0a 20 20  pIn->pLeft ){.  
2710: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
2720: 6e 74 72 79 20 2a 70 3b 0a 20 20 20 20 72 6f 77  ntry *p;.    row
2730: 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70 49  SetTreeToList(pI
2740: 6e 2d 3e 70 4c 65 66 74 2c 20 70 70 46 69 72 73  n->pLeft, ppFirs
2750: 74 2c 20 26 70 29 3b 0a 20 20 20 20 70 2d 3e 70  t, &p);.    p->p
2760: 52 69 67 68 74 20 3d 20 70 49 6e 3b 0a 20 20 7d  Right = pIn;.  }
2770: 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 46 69 72  else{.    *ppFir
2780: 73 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20  st = pIn;.  }.  
2790: 69 66 28 20 70 49 6e 2d 3e 70 52 69 67 68 74 20  if( pIn->pRight 
27a0: 29 7b 0a 20 20 20 20 72 6f 77 53 65 74 54 72 65  ){.    rowSetTre
27b0: 65 54 6f 4c 69 73 74 28 70 49 6e 2d 3e 70 52 69  eToList(pIn->pRi
27c0: 67 68 74 2c 20 26 70 49 6e 2d 3e 70 52 69 67 68  ght, &pIn->pRigh
27d0: 74 2c 20 70 70 4c 61 73 74 29 3b 0a 20 20 7d 65  t, ppLast);.  }e
27e0: 6c 73 65 7b 0a 20 20 20 20 2a 70 70 4c 61 73 74  lse{.    *ppLast
27f0: 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20 61 73   = pIn;.  }.  as
2800: 73 65 72 74 28 20 28 2a 70 70 4c 61 73 74 29 2d  sert( (*ppLast)-
2810: 3e 70 52 69 67 68 74 3d 3d 30 20 29 3b 0a 7d 0a  >pRight==0 );.}.
2820: 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65 72 74 20  ../*.** Convert 
2830: 61 20 73 6f 72 74 65 64 20 6c 69 73 74 20 6f 66  a sorted list of
2840: 20 65 6c 65 6d 65 6e 74 73 20 28 63 6f 6e 6e 65   elements (conne
2850: 63 74 65 64 20 62 79 20 70 52 69 67 68 74 29 20  cted by pRight) 
2860: 69 6e 74 6f 20 61 20 62 69 6e 61 72 79 0a 2a 2a  into a binary.**
2870: 20 74 72 65 65 20 77 69 74 68 20 64 65 70 74 68   tree with depth
2880: 20 6f 66 20 69 44 65 70 74 68 2e 20 20 41 20 64   of iDepth.  A d
2890: 65 70 74 68 20 6f 66 20 31 20 6d 65 61 6e 73 20  epth of 1 means 
28a0: 74 68 65 20 74 72 65 65 20 63 6f 6e 74 61 69 6e  the tree contain
28b0: 73 20 61 20 73 69 6e 67 6c 65 0a 2a 2a 20 6e 6f  s a single.** no
28c0: 64 65 20 74 61 6b 65 6e 20 66 72 6f 6d 20 74 68  de taken from th
28d0: 65 20 68 65 61 64 20 6f 66 20 2a 70 70 4c 69 73  e head of *ppLis
28e0: 74 2e 20 20 41 20 64 65 70 74 68 20 6f 66 20 32  t.  A depth of 2
28f0: 20 6d 65 61 6e 73 20 61 20 74 72 65 65 20 77 69   means a tree wi
2900: 74 68 0a 2a 2a 20 74 68 72 65 65 20 6e 6f 64 65  th.** three node
2910: 73 2e 20 20 41 6e 64 20 73 6f 20 66 6f 72 74 68  s.  And so forth
2920: 2e 0a 2a 2a 0a 2a 2a 20 55 73 65 20 61 73 20 6d  ..**.** Use as m
2930: 61 6e 79 20 65 6e 74 72 69 65 73 20 66 72 6f 6d  any entries from
2940: 20 74 68 65 20 69 6e 70 75 74 20 6c 69 73 74 20   the input list 
2950: 61 73 20 72 65 71 75 69 72 65 64 20 61 6e 64 20  as required and 
2960: 75 70 64 61 74 65 20 74 68 65 0a 2a 2a 20 2a 70  update the.** *p
2970: 70 4c 69 73 74 20 74 6f 20 70 6f 69 6e 74 20 74  pList to point t
2980: 6f 20 74 68 65 20 75 6e 75 73 65 64 20 65 6c 65  o the unused ele
2990: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 6c 69 73  ments of the lis
29a0: 74 2e 20 20 49 66 20 74 68 65 20 69 6e 70 75 74  t.  If the input
29b0: 0a 2a 2a 20 6c 69 73 74 20 63 6f 6e 74 61 69 6e  .** list contain
29c0: 73 20 74 6f 6f 20 66 65 77 20 65 6c 65 6d 65 6e  s too few elemen
29d0: 74 73 2c 20 74 68 65 6e 20 63 6f 6e 73 74 72 75  ts, then constru
29e0: 63 74 20 61 6e 20 69 6e 63 6f 6d 70 6c 65 74 65  ct an incomplete
29f0: 20 74 72 65 65 0a 2a 2a 20 61 6e 64 20 6c 65 61   tree.** and lea
2a00: 76 65 20 2a 70 70 4c 69 73 74 20 73 65 74 20 74  ve *ppList set t
2a10: 6f 20 4e 55 4c 4c 2e 0a 2a 2a 0a 2a 2a 20 52 65  o NULL..**.** Re
2a20: 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  turn a pointer t
2a30: 6f 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68  o the root of th
2a40: 65 20 63 6f 6e 73 74 72 75 63 74 65 64 20 62 69  e constructed bi
2a50: 6e 61 72 79 20 74 72 65 65 2e 0a 2a 2f 0a 73 74  nary tree..*/.st
2a60: 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53  atic struct RowS
2a70: 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 4e  etEntry *rowSetN
2a80: 44 65 65 70 54 72 65 65 28 0a 20 20 73 74 72 75  DeepTree(.  stru
2a90: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2aa0: 2a 70 70 4c 69 73 74 2c 0a 20 20 69 6e 74 20 69  *ppList,.  int i
2ab0: 44 65 70 74 68 0a 29 7b 0a 20 20 73 74 72 75 63  Depth.){.  struc
2ac0: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70  t RowSetEntry *p
2ad0: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f  ;         /* Roo
2ae0: 74 20 6f 66 20 74 68 65 20 6e 65 77 20 74 72 65  t of the new tre
2af0: 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f  e */.  struct Ro
2b00: 77 53 65 74 45 6e 74 72 79 20 2a 70 4c 65 66 74  wSetEntry *pLeft
2b10: 3b 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73 75  ;     /* Left su
2b20: 62 74 72 65 65 20 2a 2f 0a 20 20 69 66 28 20 2a  btree */.  if( *
2b30: 70 70 4c 69 73 74 3d 3d 30 20 29 7b 20 2f 2a 4f  ppList==0 ){ /*O
2b40: 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 54  PTIMIZATION-IF-T
2b50: 52 55 45 2a 2f 0a 20 20 20 20 2f 2a 20 50 72 65  RUE*/.    /* Pre
2b60: 76 65 6e 74 20 75 6e 6e 65 63 65 73 73 61 72 79  vent unnecessary
2b70: 20 64 65 65 70 20 72 65 63 75 72 73 69 6f 6e 20   deep recursion 
2b80: 77 68 65 6e 20 77 65 20 72 75 6e 20 6f 75 74 20  when we run out 
2b90: 6f 66 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20  of entries */.  
2ba0: 20 20 72 65 74 75 72 6e 20 30 3b 20 0a 20 20 7d    return 0; .  }
2bb0: 0a 20 20 69 66 28 20 69 44 65 70 74 68 3e 31 20  .  if( iDepth>1 
2bc0: 29 7b 20 20 20 2f 2a 4f 50 54 49 4d 49 5a 41 54  ){   /*OPTIMIZAT
2bd0: 49 4f 4e 2d 49 46 2d 54 52 55 45 2a 2f 0a 20 20  ION-IF-TRUE*/.  
2be0: 20 20 2f 2a 20 54 68 69 73 20 62 72 61 6e 63 68    /* This branch
2bf0: 20 63 61 75 73 65 73 20 61 20 2a 62 61 6c 61 6e   causes a *balan
2c00: 63 65 64 2a 20 74 72 65 65 20 74 6f 20 62 65 20  ced* tree to be 
2c10: 67 65 6e 65 72 61 74 65 64 2e 20 20 41 20 76 61  generated.  A va
2c20: 6c 69 64 20 74 72 65 65 0a 20 20 20 20 2a 2a 20  lid tree.    ** 
2c30: 69 73 20 73 74 69 6c 6c 20 67 65 6e 65 72 61 74  is still generat
2c40: 65 64 20 77 69 74 68 6f 75 74 20 74 68 69 73 20  ed without this 
2c50: 62 72 61 6e 63 68 2c 20 62 75 74 20 74 68 65 20  branch, but the 
2c60: 74 72 65 65 20 69 73 20 77 69 6c 64 6c 79 0a 20  tree is wildly. 
2c70: 20 20 20 2a 2a 20 75 6e 62 61 6c 61 6e 63 65 64     ** unbalanced
2c80: 20 61 6e 64 20 69 6e 65 66 66 69 63 69 65 6e 74   and inefficient
2c90: 2e 20 2a 2f 0a 20 20 20 20 70 4c 65 66 74 20 3d  . */.    pLeft =
2ca0: 20 72 6f 77 53 65 74 4e 44 65 65 70 54 72 65 65   rowSetNDeepTree
2cb0: 28 70 70 4c 69 73 74 2c 20 69 44 65 70 74 68 2d  (ppList, iDepth-
2cc0: 31 29 3b 0a 20 20 20 20 70 20 3d 20 2a 70 70 4c  1);.    p = *ppL
2cd0: 69 73 74 3b 0a 20 20 20 20 69 66 28 20 70 3d 3d  ist;.    if( p==
2ce0: 30 20 29 7b 20 20 20 20 20 2f 2a 4f 50 54 49 4d  0 ){     /*OPTIM
2cf0: 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45  IZATION-IF-FALSE
2d00: 2a 2f 0a 20 20 20 20 20 20 2f 2a 20 49 74 20 69  */.      /* It i
2d10: 73 20 73 61 66 65 20 74 6f 20 61 6c 77 61 79 73  s safe to always
2d20: 20 72 65 74 75 72 6e 20 68 65 72 65 2c 20 62 75   return here, bu
2d30: 74 20 74 68 65 20 72 65 73 75 6c 74 69 6e 67 20  t the resulting 
2d40: 74 72 65 65 0a 20 20 20 20 20 20 2a 2a 20 77 6f  tree.      ** wo
2d50: 75 6c 64 20 62 65 20 75 6e 62 61 6c 61 6e 63 65  uld be unbalance
2d60: 64 20 2a 2f 0a 20 20 20 20 20 20 72 65 74 75 72  d */.      retur
2d70: 6e 20 70 4c 65 66 74 3b 0a 20 20 20 20 7d 0a 20  n pLeft;.    }. 
2d80: 20 20 20 70 2d 3e 70 4c 65 66 74 20 3d 20 70 4c     p->pLeft = pL
2d90: 65 66 74 3b 0a 20 20 20 20 2a 70 70 4c 69 73 74  eft;.    *ppList
2da0: 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20   = p->pRight;.  
2db0: 20 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 72 6f    p->pRight = ro
2dc0: 77 53 65 74 4e 44 65 65 70 54 72 65 65 28 70 70  wSetNDeepTree(pp
2dd0: 4c 69 73 74 2c 20 69 44 65 70 74 68 2d 31 29 3b  List, iDepth-1);
2de0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 20  .  }else{.    p 
2df0: 3d 20 2a 70 70 4c 69 73 74 3b 0a 20 20 20 20 2a  = *ppList;.    *
2e00: 70 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52 69 67  ppList = p->pRig
2e10: 68 74 3b 0a 20 20 20 20 70 2d 3e 70 4c 65 66 74  ht;.    p->pLeft
2e20: 20 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 30   = p->pRight = 0
2e30: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70  ;.  }.  return p
2e40: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65  ;.}../*.** Conve
2e50: 72 74 20 61 20 73 6f 72 74 65 64 20 6c 69 73 74  rt a sorted list
2e60: 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e 74   of elements int
2e70: 6f 20 61 20 62 69 6e 61 72 79 20 74 72 65 65 2e  o a binary tree.
2e80: 20 4d 61 6b 65 20 74 68 65 20 74 72 65 65 0a 2a   Make the tree.*
2e90: 2a 20 61 73 20 64 65 65 70 20 61 73 20 69 74 20  * as deep as it 
2ea0: 6e 65 65 64 73 20 74 6f 20 62 65 20 69 6e 20 6f  needs to be in o
2eb0: 72 64 65 72 20 74 6f 20 63 6f 6e 74 61 69 6e 20  rder to contain 
2ec0: 74 68 65 20 65 6e 74 69 72 65 20 6c 69 73 74 2e  the entire list.
2ed0: 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75 63  .*/.static struc
2ee0: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 72  t RowSetEntry *r
2ef0: 6f 77 53 65 74 4c 69 73 74 54 6f 54 72 65 65 28  owSetListToTree(
2f00: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
2f10: 72 79 20 2a 70 4c 69 73 74 29 7b 0a 20 20 69 6e  ry *pList){.  in
2f20: 74 20 69 44 65 70 74 68 3b 20 20 20 20 20 20 20  t iDepth;       
2f30: 20 20 20 20 2f 2a 20 44 65 70 74 68 20 6f 66 20      /* Depth of 
2f40: 74 68 65 20 74 72 65 65 20 73 6f 20 66 61 72 20  the tree so far 
2f50: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
2f60: 65 74 45 6e 74 72 79 20 2a 70 3b 20 20 20 20 20  etEntry *p;     
2f70: 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 74 72 65    /* Current tre
2f80: 65 20 72 6f 6f 74 20 2a 2f 0a 20 20 73 74 72 75  e root */.  stru
2f90: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2fa0: 70 4c 65 66 74 3b 20 20 20 2f 2a 20 4c 65 66 74  pLeft;   /* Left
2fb0: 20 73 75 62 74 72 65 65 20 2a 2f 0a 0a 20 20 61   subtree */..  a
2fc0: 73 73 65 72 74 28 20 70 4c 69 73 74 21 3d 30 20  ssert( pList!=0 
2fd0: 29 3b 0a 20 20 70 20 3d 20 70 4c 69 73 74 3b 0a  );.  p = pList;.
2fe0: 20 20 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52 69    pList = p->pRi
2ff0: 67 68 74 3b 0a 20 20 70 2d 3e 70 4c 65 66 74 20  ght;.  p->pLeft 
3000: 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 30 3b  = p->pRight = 0;
3010: 0a 20 20 66 6f 72 28 69 44 65 70 74 68 3d 31 3b  .  for(iDepth=1;
3020: 20 70 4c 69 73 74 3b 20 69 44 65 70 74 68 2b 2b   pList; iDepth++
3030: 29 7b 0a 20 20 20 20 70 4c 65 66 74 20 3d 20 70  ){.    pLeft = p
3040: 3b 0a 20 20 20 20 70 20 3d 20 70 4c 69 73 74 3b  ;.    p = pList;
3050: 0a 20 20 20 20 70 4c 69 73 74 20 3d 20 70 2d 3e  .    pList = p->
3060: 70 52 69 67 68 74 3b 0a 20 20 20 20 70 2d 3e 70  pRight;.    p->p
3070: 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b 0a 20 20  Left = pLeft;.  
3080: 20 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 72 6f    p->pRight = ro
3090: 77 53 65 74 4e 44 65 65 70 54 72 65 65 28 26 70  wSetNDeepTree(&p
30a0: 4c 69 73 74 2c 20 69 44 65 70 74 68 29 3b 0a 20  List, iDepth);. 
30b0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b 0a 7d   }.  return p;.}
30c0: 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20  ../*.** Extract 
30d0: 74 68 65 20 73 6d 61 6c 6c 65 73 74 20 65 6c 65  the smallest ele
30e0: 6d 65 6e 74 20 66 72 6f 6d 20 74 68 65 20 52 6f  ment from the Ro
30f0: 77 53 65 74 2e 0a 2a 2a 20 57 72 69 74 65 20 74  wSet..** Write t
3100: 68 65 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20  he element into 
3110: 2a 70 52 6f 77 69 64 2e 20 20 52 65 74 75 72 6e  *pRowid.  Return
3120: 20 31 20 6f 6e 20 73 75 63 63 65 73 73 2e 20 20   1 on success.  
3130: 52 65 74 75 72 6e 0a 2a 2a 20 30 20 69 66 20 74  Return.** 0 if t
3140: 68 65 20 52 6f 77 53 65 74 20 69 73 20 61 6c 72  he RowSet is alr
3150: 65 61 64 79 20 65 6d 70 74 79 2e 0a 2a 2a 0a 2a  eady empty..**.*
3160: 2a 20 41 66 74 65 72 20 74 68 69 73 20 72 6f 75  * After this rou
3170: 74 69 6e 65 20 68 61 73 20 62 65 65 6e 20 63 61  tine has been ca
3180: 6c 6c 65 64 2c 20 74 68 65 20 73 71 6c 69 74 65  lled, the sqlite
3190: 33 52 6f 77 53 65 74 49 6e 73 65 72 74 28 29 0a  3RowSetInsert().
31a0: 2a 2a 20 72 6f 75 74 69 6e 65 20 6d 61 79 20 6e  ** routine may n
31b0: 6f 74 20 62 65 20 63 61 6c 6c 65 64 20 61 67 61  ot be called aga
31c0: 69 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 72  in..**.** This r
31d0: 6f 75 74 69 6e 65 20 6d 61 79 20 6e 6f 74 20 62  outine may not b
31e0: 65 20 63 61 6c 6c 65 64 20 61 66 74 65 72 20 73  e called after s
31f0: 71 6c 69 74 65 33 52 6f 77 53 65 74 54 65 73 74  qlite3RowSetTest
3200: 28 29 20 68 61 73 0a 2a 2a 20 62 65 65 6e 20 75  () has.** been u
3210: 73 65 64 2e 20 20 4f 6c 64 65 72 20 76 65 72 73  sed.  Older vers
3220: 69 6f 6e 73 20 6f 66 20 52 6f 77 53 65 74 20 61  ions of RowSet a
3230: 6c 6c 6f 77 65 64 20 74 68 61 74 2c 20 62 75 74  llowed that, but
3240: 20 61 73 20 74 68 65 0a 2a 2a 20 63 61 70 61 62   as the.** capab
3250: 69 6c 69 74 79 20 77 61 73 20 6e 6f 74 20 75 73  ility was not us
3260: 65 64 20 62 79 20 74 68 65 20 63 6f 64 65 20 67  ed by the code g
3270: 65 6e 65 72 61 74 6f 72 2c 20 69 74 20 77 61 73  enerator, it was
3280: 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 6f 72 20   removed.** for 
3290: 63 6f 64 65 20 65 63 6f 6e 6f 6d 79 2e 0a 2a 2f  code economy..*/
32a0: 0a 69 6e 74 20 73 71 6c 69 74 65 33 52 6f 77 53  .int sqlite3RowS
32b0: 65 74 4e 65 78 74 28 52 6f 77 53 65 74 20 2a 70  etNext(RowSet *p
32c0: 2c 20 69 36 34 20 2a 70 52 6f 77 69 64 29 7b 0a  , i64 *pRowid){.
32d0: 20 20 61 73 73 65 72 74 28 20 70 21 3d 30 20 29    assert( p!=0 )
32e0: 3b 0a 20 20 61 73 73 65 72 74 28 20 70 2d 3e 70  ;.  assert( p->p
32f0: 46 6f 72 65 73 74 3d 3d 30 20 29 3b 20 20 2f 2a  Forest==0 );  /*
3300: 20 43 61 6e 6e 6f 74 20 62 65 20 75 73 65 64 20   Cannot be used 
3310: 77 69 74 68 20 73 71 6c 69 74 65 33 52 6f 77 53  with sqlite3RowS
3320: 65 74 54 65 78 74 28 29 20 2a 2f 0a 0a 20 20 2f  etText() */..  /
3330: 2a 20 4d 65 72 67 65 20 74 68 65 20 66 6f 72 65  * Merge the fore
3340: 73 74 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65  st into a single
3350: 20 73 6f 72 74 65 64 20 6c 69 73 74 20 6f 6e 20   sorted list on 
3360: 66 69 72 73 74 20 63 61 6c 6c 20 2a 2f 0a 20 20  first call */.  
3370: 69 66 28 20 28 70 2d 3e 72 73 46 6c 61 67 73 20  if( (p->rsFlags 
3380: 26 20 52 4f 57 53 45 54 5f 4e 45 58 54 29 3d 3d  & ROWSET_NEXT)==
3390: 30 20 29 7b 20 20 2f 2a 4f 50 54 49 4d 49 5a 41  0 ){  /*OPTIMIZA
33a0: 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45 2a 2f 0a  TION-IF-FALSE*/.
33b0: 20 20 20 20 69 66 28 20 28 70 2d 3e 72 73 46 6c      if( (p->rsFl
33c0: 61 67 73 20 26 20 52 4f 57 53 45 54 5f 53 4f 52  ags & ROWSET_SOR
33d0: 54 45 44 29 3d 3d 30 20 29 7b 20 20 2f 2a 4f 50  TED)==0 ){  /*OP
33e0: 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41  TIMIZATION-IF-FA
33f0: 4c 53 45 2a 2f 0a 20 20 20 20 20 20 70 2d 3e 70  LSE*/.      p->p
3400: 45 6e 74 72 79 20 3d 20 72 6f 77 53 65 74 45 6e  Entry = rowSetEn
3410: 74 72 79 53 6f 72 74 28 70 2d 3e 70 45 6e 74 72  trySort(p->pEntr
3420: 79 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 2d  y);.    }.    p-
3430: 3e 72 73 46 6c 61 67 73 20 7c 3d 20 52 4f 57 53  >rsFlags |= ROWS
3440: 45 54 5f 53 4f 52 54 45 44 7c 52 4f 57 53 45 54  ET_SORTED|ROWSET
3450: 5f 4e 45 58 54 3b 0a 20 20 7d 0a 0a 20 20 2f 2a  _NEXT;.  }..  /*
3460: 20 52 65 74 75 72 6e 20 74 68 65 20 6e 65 78 74   Return the next
3470: 20 65 6e 74 72 79 20 6f 6e 20 74 68 65 20 6c 69   entry on the li
3480: 73 74 20 2a 2f 0a 20 20 69 66 28 20 70 2d 3e 70  st */.  if( p->p
3490: 45 6e 74 72 79 20 29 7b 0a 20 20 20 20 2a 70 52  Entry ){.    *pR
34a0: 6f 77 69 64 20 3d 20 70 2d 3e 70 45 6e 74 72 79  owid = p->pEntry
34b0: 2d 3e 76 3b 0a 20 20 20 20 70 2d 3e 70 45 6e 74  ->v;.    p->pEnt
34c0: 72 79 20 3d 20 70 2d 3e 70 45 6e 74 72 79 2d 3e  ry = p->pEntry->
34d0: 70 52 69 67 68 74 3b 0a 20 20 20 20 69 66 28 20  pRight;.    if( 
34e0: 70 2d 3e 70 45 6e 74 72 79 3d 3d 30 20 29 7b 20  p->pEntry==0 ){ 
34f0: 2f 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49  /*OPTIMIZATION-I
3500: 46 2d 54 52 55 45 2a 2f 0a 20 20 20 20 20 20 2f  F-TRUE*/.      /
3510: 2a 20 46 72 65 65 20 6d 65 6d 6f 72 79 20 69 6d  * Free memory im
3520: 6d 65 64 69 61 74 65 6c 79 2c 20 72 61 74 68 65  mediately, rathe
3530: 72 20 74 68 61 6e 20 77 61 69 74 69 6e 67 20 6f  r than waiting o
3540: 6e 20 73 71 6c 69 74 65 33 5f 66 69 6e 61 6c 69  n sqlite3_finali
3550: 7a 65 28 29 20 2a 2f 0a 20 20 20 20 20 20 73 71  ze() */.      sq
3560: 6c 69 74 65 33 52 6f 77 53 65 74 43 6c 65 61 72  lite3RowSetClear
3570: 28 70 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72  (p);.    }.    r
3580: 65 74 75 72 6e 20 31 3b 0a 20 20 7d 65 6c 73 65  eturn 1;.  }else
3590: 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a  {.    return 0;.
35a0: 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65    }.}../*.** Che
35b0: 63 6b 20 74 6f 20 73 65 65 20 69 66 20 65 6c 65  ck to see if ele
35c0: 6d 65 6e 74 20 69 52 6f 77 69 64 20 77 61 73 20  ment iRowid was 
35d0: 69 6e 73 65 72 74 65 64 20 69 6e 74 6f 20 74 68  inserted into th
35e0: 65 20 72 6f 77 73 65 74 20 61 73 0a 2a 2a 20 70  e rowset as.** p
35f0: 61 72 74 20 6f 66 20 61 6e 79 20 69 6e 73 65 72  art of any inser
3600: 74 20 62 61 74 63 68 20 70 72 69 6f 72 20 74 6f  t batch prior to
3610: 20 69 42 61 74 63 68 2e 20 20 52 65 74 75 72 6e   iBatch.  Return
3620: 20 31 20 6f 72 20 30 2e 0a 2a 2a 0a 2a 2a 20 49   1 or 0..**.** I
3630: 66 20 74 68 69 73 20 69 73 20 74 68 65 20 66 69  f this is the fi
3640: 72 73 74 20 74 65 73 74 20 6f 66 20 61 20 6e 65  rst test of a ne
3650: 77 20 62 61 74 63 68 20 61 6e 64 20 69 66 20 74  w batch and if t
3660: 68 65 72 65 20 65 78 69 73 74 20 65 6e 74 72 69  here exist entri
3670: 65 73 0a 2a 2a 20 6f 6e 20 70 52 6f 77 53 65 74  es.** on pRowSet
3680: 2d 3e 70 45 6e 74 72 79 2c 20 74 68 65 6e 20 73  ->pEntry, then s
3690: 6f 72 74 20 74 68 6f 73 65 20 65 6e 74 72 69 65  ort those entrie
36a0: 73 20 69 6e 74 6f 20 74 68 65 20 66 6f 72 65 73  s into the fores
36b0: 74 20 61 74 0a 2a 2a 20 70 52 6f 77 53 65 74 2d  t at.** pRowSet-
36c0: 3e 70 46 6f 72 65 73 74 20 73 6f 20 74 68 61 74  >pForest so that
36d0: 20 74 68 65 79 20 63 61 6e 20 62 65 20 74 65 73   they can be tes
36e0: 74 65 64 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  ted..*/.int sqli
36f0: 74 65 33 52 6f 77 53 65 74 54 65 73 74 28 52 6f  te3RowSetTest(Ro
3700: 77 53 65 74 20 2a 70 52 6f 77 53 65 74 2c 20 69  wSet *pRowSet, i
3710: 6e 74 20 69 42 61 74 63 68 2c 20 73 71 6c 69 74  nt iBatch, sqlit
3720: 65 33 5f 69 6e 74 36 34 20 69 52 6f 77 69 64 29  e3_int64 iRowid)
3730: 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  {.  struct RowSe
3740: 74 45 6e 74 72 79 20 2a 70 2c 20 2a 70 54 72 65  tEntry *p, *pTre
3750: 65 3b 0a 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f  e;..  /* This ro
3760: 75 74 69 6e 65 20 69 73 20 6e 65 76 65 72 20 63  utine is never c
3770: 61 6c 6c 65 64 20 61 66 74 65 72 20 73 71 6c 69  alled after sqli
3780: 74 65 33 52 6f 77 53 65 74 4e 65 78 74 28 29 20  te3RowSetNext() 
3790: 2a 2f 0a 20 20 61 73 73 65 72 74 28 20 70 52 6f  */.  assert( pRo
37a0: 77 53 65 74 21 3d 30 20 26 26 20 28 70 52 6f 77  wSet!=0 && (pRow
37b0: 53 65 74 2d 3e 72 73 46 6c 61 67 73 20 26 20 52  Set->rsFlags & R
37c0: 4f 57 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29  OWSET_NEXT)==0 )
37d0: 3b 0a 0a 20 20 2f 2a 20 53 6f 72 74 20 65 6e 74  ;..  /* Sort ent
37e0: 72 69 65 73 20 69 6e 74 6f 20 74 68 65 20 66 6f  ries into the fo
37f0: 72 65 73 74 20 6f 6e 20 74 68 65 20 66 69 72 73  rest on the firs
3800: 74 20 74 65 73 74 20 6f 66 20 61 20 6e 65 77 20  t test of a new 
3810: 62 61 74 63 68 2e 0a 20 20 2a 2a 20 54 6f 20 73  batch..  ** To s
3820: 61 76 65 20 75 6e 6e 65 63 65 73 73 61 72 79 20  ave unnecessary 
3830: 77 6f 72 6b 2c 20 6f 6e 6c 79 20 64 6f 20 74 68  work, only do th
3840: 69 73 20 77 68 65 6e 20 74 68 65 20 62 61 74 63  is when the batc
3850: 68 20 6e 75 6d 62 65 72 20 63 68 61 6e 67 65 73  h number changes
3860: 2e 0a 20 20 2a 2f 0a 20 20 69 66 28 20 69 42 61  ..  */.  if( iBa
3870: 74 63 68 21 3d 70 52 6f 77 53 65 74 2d 3e 69 42  tch!=pRowSet->iB
3880: 61 74 63 68 20 29 7b 20 20 2f 2a 4f 50 54 49 4d  atch ){  /*OPTIM
3890: 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45  IZATION-IF-FALSE
38a0: 2a 2f 0a 20 20 20 20 70 20 3d 20 70 52 6f 77 53  */.    p = pRowS
38b0: 65 74 2d 3e 70 45 6e 74 72 79 3b 0a 20 20 20 20  et->pEntry;.    
38c0: 69 66 28 20 70 20 29 7b 0a 20 20 20 20 20 20 73  if( p ){.      s
38d0: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
38e0: 79 20 2a 2a 70 70 50 72 65 76 54 72 65 65 20 3d  y **ppPrevTree =
38f0: 20 26 70 52 6f 77 53 65 74 2d 3e 70 46 6f 72 65   &pRowSet->pFore
3900: 73 74 3b 0a 20 20 20 20 20 20 69 66 28 20 28 70  st;.      if( (p
3910: 52 6f 77 53 65 74 2d 3e 72 73 46 6c 61 67 73 20  RowSet->rsFlags 
3920: 26 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44 29  & ROWSET_SORTED)
3930: 3d 3d 30 20 29 7b 20 2f 2a 4f 50 54 49 4d 49 5a  ==0 ){ /*OPTIMIZ
3940: 41 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45 2a 2f  ATION-IF-FALSE*/
3950: 0a 20 20 20 20 20 20 20 20 2f 2a 20 4f 6e 6c 79  .        /* Only
3960: 20 73 6f 72 74 20 74 68 65 20 63 75 72 72 65 6e   sort the curren
3970: 74 20 73 65 74 20 6f 66 20 65 6e 74 69 72 69 65  t set of entirie
3980: 73 20 69 66 20 74 68 65 79 20 6e 65 65 64 20 69  s if they need i
3990: 74 20 2a 2f 0a 20 20 20 20 20 20 20 20 70 20 3d  t */.        p =
39a0: 20 72 6f 77 53 65 74 45 6e 74 72 79 53 6f 72 74   rowSetEntrySort
39b0: 28 70 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  (p);.      }.   
39c0: 20 20 20 66 6f 72 28 70 54 72 65 65 20 3d 20 70     for(pTree = p
39d0: 52 6f 77 53 65 74 2d 3e 70 46 6f 72 65 73 74 3b  RowSet->pForest;
39e0: 20 70 54 72 65 65 3b 20 70 54 72 65 65 3d 70 54   pTree; pTree=pT
39f0: 72 65 65 2d 3e 70 52 69 67 68 74 29 7b 0a 20 20  ree->pRight){.  
3a00: 20 20 20 20 20 20 70 70 50 72 65 76 54 72 65 65        ppPrevTree
3a10: 20 3d 20 26 70 54 72 65 65 2d 3e 70 52 69 67 68   = &pTree->pRigh
3a20: 74 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20 70  t;.        if( p
3a30: 54 72 65 65 2d 3e 70 4c 65 66 74 3d 3d 30 20 29  Tree->pLeft==0 )
3a40: 7b 0a 20 20 20 20 20 20 20 20 20 20 70 54 72 65  {.          pTre
3a50: 65 2d 3e 70 4c 65 66 74 20 3d 20 72 6f 77 53 65  e->pLeft = rowSe
3a60: 74 4c 69 73 74 54 6f 54 72 65 65 28 70 29 3b 0a  tListToTree(p);.
3a70: 20 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b            break;
3a80: 0a 20 20 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a  .        }else{.
3a90: 20 20 20 20 20 20 20 20 20 20 73 74 72 75 63 74            struct
3aa0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 41   RowSetEntry *pA
3ab0: 75 78 2c 20 2a 70 54 61 69 6c 3b 0a 20 20 20 20  ux, *pTail;.    
3ac0: 20 20 20 20 20 20 72 6f 77 53 65 74 54 72 65 65        rowSetTree
3ad0: 54 6f 4c 69 73 74 28 70 54 72 65 65 2d 3e 70 4c  ToList(pTree->pL
3ae0: 65 66 74 2c 20 26 70 41 75 78 2c 20 26 70 54 61  eft, &pAux, &pTa
3af0: 69 6c 29 3b 0a 20 20 20 20 20 20 20 20 20 20 70  il);.          p
3b00: 54 72 65 65 2d 3e 70 4c 65 66 74 20 3d 20 30 3b  Tree->pLeft = 0;
3b10: 0a 20 20 20 20 20 20 20 20 20 20 70 20 3d 20 72  .          p = r
3b20: 6f 77 53 65 74 45 6e 74 72 79 4d 65 72 67 65 28  owSetEntryMerge(
3b30: 70 41 75 78 2c 20 70 29 3b 0a 20 20 20 20 20 20  pAux, p);.      
3b40: 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20 20    }.      }.    
3b50: 20 20 69 66 28 20 70 54 72 65 65 3d 3d 30 20 29    if( pTree==0 )
3b60: 7b 0a 20 20 20 20 20 20 20 20 2a 70 70 50 72 65  {.        *ppPre
3b70: 76 54 72 65 65 20 3d 20 70 54 72 65 65 20 3d 20  vTree = pTree = 
3b80: 72 6f 77 53 65 74 45 6e 74 72 79 41 6c 6c 6f 63  rowSetEntryAlloc
3b90: 28 70 52 6f 77 53 65 74 29 3b 0a 20 20 20 20 20  (pRowSet);.     
3ba0: 20 20 20 69 66 28 20 70 54 72 65 65 20 29 7b 0a     if( pTree ){.
3bb0: 20 20 20 20 20 20 20 20 20 20 70 54 72 65 65 2d            pTree-
3bc0: 3e 76 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  >v = 0;.        
3bd0: 20 20 70 54 72 65 65 2d 3e 70 52 69 67 68 74 20    pTree->pRight 
3be0: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20 70  = 0;.          p
3bf0: 54 72 65 65 2d 3e 70 4c 65 66 74 20 3d 20 72 6f  Tree->pLeft = ro
3c00: 77 53 65 74 4c 69 73 74 54 6f 54 72 65 65 28 70  wSetListToTree(p
3c10: 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  );.        }.   
3c20: 20 20 20 7d 0a 20 20 20 20 20 20 70 52 6f 77 53     }.      pRowS
3c30: 65 74 2d 3e 70 45 6e 74 72 79 20 3d 20 30 3b 0a  et->pEntry = 0;.
3c40: 20 20 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 70        pRowSet->p
3c50: 4c 61 73 74 20 3d 20 30 3b 0a 20 20 20 20 20 20  Last = 0;.      
3c60: 70 52 6f 77 53 65 74 2d 3e 72 73 46 6c 61 67 73  pRowSet->rsFlags
3c70: 20 7c 3d 20 52 4f 57 53 45 54 5f 53 4f 52 54 45   |= ROWSET_SORTE
3c80: 44 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 52 6f  D;.    }.    pRo
3c90: 77 53 65 74 2d 3e 69 42 61 74 63 68 20 3d 20 69  wSet->iBatch = i
3ca0: 42 61 74 63 68 3b 0a 20 20 7d 0a 0a 20 20 2f 2a  Batch;.  }..  /*
3cb0: 20 54 65 73 74 20 74 6f 20 73 65 65 20 69 66 20   Test to see if 
3cc0: 74 68 65 20 69 52 6f 77 69 64 20 76 61 6c 75 65  the iRowid value
3cd0: 20 61 70 70 65 61 72 73 20 61 6e 79 77 68 65 72   appears anywher
3ce0: 65 20 69 6e 20 74 68 65 20 66 6f 72 65 73 74 2e  e in the forest.
3cf0: 0a 20 20 2a 2a 20 52 65 74 75 72 6e 20 31 20 69  .  ** Return 1 i
3d00: 66 20 69 74 20 64 6f 65 73 20 61 6e 64 20 30 20  f it does and 0 
3d10: 69 66 20 6e 6f 74 2e 0a 20 20 2a 2f 0a 20 20 66  if not..  */.  f
3d20: 6f 72 28 70 54 72 65 65 20 3d 20 70 52 6f 77 53  or(pTree = pRowS
3d30: 65 74 2d 3e 70 46 6f 72 65 73 74 3b 20 70 54 72  et->pForest; pTr
3d40: 65 65 3b 20 70 54 72 65 65 3d 70 54 72 65 65 2d  ee; pTree=pTree-
3d50: 3e 70 52 69 67 68 74 29 7b 0a 20 20 20 20 70 20  >pRight){.    p 
3d60: 3d 20 70 54 72 65 65 2d 3e 70 4c 65 66 74 3b 0a  = pTree->pLeft;.
3d70: 20 20 20 20 77 68 69 6c 65 28 20 70 20 29 7b 0a      while( p ){.
3d80: 20 20 20 20 20 20 69 66 28 20 70 2d 3e 76 3c 69        if( p->v<i
3d90: 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 20 20 20  Rowid ){.       
3da0: 20 70 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a   p = p->pRight;.
3db0: 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20        }else if( 
3dc0: 70 2d 3e 76 3e 69 52 6f 77 69 64 20 29 7b 0a 20  p->v>iRowid ){. 
3dd0: 20 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 70 4c         p = p->pL
3de0: 65 66 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65  eft;.      }else
3df0: 7b 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e  {.        return
3e00: 20 31 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20   1;.      }.    
3e10: 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  }.  }.  return 0
3e20: 3b 0a 7d 0a                                      ;.}.