/ Hex Artifact Content
Login

Artifact eccf6af6d620aaa4579bd3b72c1b6395d9e9fa1e:


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 68 65 72 65 20 69 73 20 61 6e 20 61 64  * There is an ad
09b0: 64 65 64 20 63 6f 73 74 20 6f 66 20 4f 28 4e 29  ded cost of O(N)
09c0: 20 77 68 65 6e 20 73 77 69 74 63 68 69 6e 67 20   when switching 
09d0: 62 65 74 77 65 65 6e 20 54 45 53 54 20 61 6e 64  between TEST and
09e0: 0a 2a 2a 20 53 4d 41 4c 4c 45 53 54 20 70 72 69  .** SMALLEST pri
09f0: 6d 69 74 69 76 65 73 2e 0a 2a 2f 0a 23 69 6e 63  mitives..*/.#inc
0a00: 6c 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e  lude "sqliteInt.
0a10: 68 22 0a 0a 0a 2f 2a 0a 2a 2a 20 54 61 72 67 65  h".../*.** Targe
0a20: 74 20 73 69 7a 65 20 66 6f 72 20 61 6c 6c 6f 63  t size for alloc
0a30: 61 74 69 6f 6e 20 63 68 75 6e 6b 73 2e 0a 2a 2f  ation chunks..*/
0a40: 0a 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f  .#define ROWSET_
0a50: 41 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49 5a 45 20  ALLOCATION_SIZE 
0a60: 31 30 32 34 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  1024../*.** The 
0a70: 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 65 74  number of rowset
0a80: 20 65 6e 74 72 69 65 73 20 70 65 72 20 61 6c 6c   entries per all
0a90: 6f 63 61 74 69 6f 6e 20 63 68 75 6e 6b 2e 0a 2a  ocation chunk..*
0aa0: 2f 0a 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54  /.#define ROWSET
0ab0: 5f 45 4e 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b  _ENTRY_PER_CHUNK
0ac0: 20 20 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20    \.            
0ad0: 20 20 20 20 20 20 20 20 20 20 20 28 28 52 4f 57             ((ROW
0ae0: 53 45 54 5f 41 4c 4c 4f 43 41 54 49 4f 4e 5f 53  SET_ALLOCATION_S
0af0: 49 5a 45 2d 38 29 2f 73 69 7a 65 6f 66 28 73 74  IZE-8)/sizeof(st
0b00: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
0b10: 29 29 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 65  ))../*.** Each e
0b20: 6e 74 72 79 20 69 6e 20 61 20 52 6f 77 53 65 74  ntry in a RowSet
0b30: 20 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20   is an instance 
0b40: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0b50: 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 54   object..**.** T
0b60: 68 69 73 20 73 61 6d 65 20 6f 62 6a 65 63 74 20  his same object 
0b70: 69 73 20 72 65 75 73 65 64 20 74 6f 20 73 74 6f  is reused to sto
0b80: 72 65 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  re a linked list
0b90: 20 6f 66 20 74 72 65 65 73 20 6f 66 20 52 6f 77   of trees of Row
0ba0: 53 65 74 45 6e 74 72 79 0a 2a 2a 20 6f 62 6a 65  SetEntry.** obje
0bb0: 63 74 73 2e 20 20 49 6e 20 74 68 61 74 20 61 6c  cts.  In that al
0bc0: 74 65 72 6e 61 74 69 76 65 20 75 73 65 2c 20 70  ternative use, p
0bd0: 52 69 67 68 74 20 70 6f 69 6e 74 73 20 74 6f 20  Right points to 
0be0: 74 68 65 20 6e 65 78 74 20 65 6e 74 72 79 0a 2a  the next entry.*
0bf0: 2a 20 69 6e 20 74 68 65 20 6c 69 73 74 2c 20 70  * in the list, p
0c00: 4c 65 66 74 20 70 6f 69 6e 74 73 20 74 6f 20 74  Left points to t
0c10: 68 65 20 74 72 65 65 2c 20 61 6e 64 20 76 20 69  he tree, and v i
0c20: 73 20 75 6e 75 73 65 64 2e 20 20 54 68 65 0a 2a  s unused.  The.*
0c30: 2a 20 52 6f 77 53 65 74 2e 70 46 6f 72 65 73 74  * RowSet.pForest
0c40: 20 76 61 6c 75 65 20 70 6f 69 6e 74 73 20 74 6f   value points to
0c50: 20 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 69   the head of thi
0c60: 73 20 66 6f 72 65 73 74 20 6c 69 73 74 2e 0a 2a  s forest list..*
0c70: 2f 0a 73 74 72 75 63 74 20 52 6f 77 53 65 74 45  /.struct RowSetE
0c80: 6e 74 72 79 20 7b 20 20 20 20 20 20 20 20 20 20  ntry {          
0c90: 20 20 0a 20 20 69 36 34 20 76 3b 20 20 20 20 20    .  i64 v;     
0ca0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0cb0: 20 20 20 2f 2a 20 52 4f 57 49 44 20 76 61 6c 75     /* ROWID valu
0cc0: 65 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79  e for this entry
0cd0: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
0ce0: 53 65 74 45 6e 74 72 79 20 2a 70 52 69 67 68 74  SetEntry *pRight
0cf0: 3b 20 20 20 2f 2a 20 52 69 67 68 74 20 73 75 62  ;   /* Right sub
0d00: 74 72 65 65 20 28 6c 61 72 67 65 72 20 65 6e 74  tree (larger ent
0d10: 72 69 65 73 29 20 6f 72 20 6c 69 73 74 20 2a 2f  ries) or list */
0d20: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
0d30: 45 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20 20 20  Entry *pLeft;   
0d40: 20 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65 65   /* Left subtree
0d50: 20 28 73 6d 61 6c 6c 65 72 20 65 6e 74 72 69 65   (smaller entrie
0d60: 73 29 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  s) */.};../*.** 
0d70: 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65  RowSetEntry obje
0d80: 63 74 73 20 61 72 65 20 61 6c 6c 6f 63 61 74 65  cts are allocate
0d90: 64 20 69 6e 20 6c 61 72 67 65 20 63 68 75 6e 6b  d in large chunk
0da0: 73 20 28 69 6e 73 74 61 6e 63 65 73 20 6f 66 20  s (instances of 
0db0: 74 68 65 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67  the.** following
0dc0: 20 73 74 72 75 63 74 75 72 65 29 20 74 6f 20 72   structure) to r
0dd0: 65 64 75 63 65 20 6d 65 6d 6f 72 79 20 61 6c 6c  educe memory all
0de0: 6f 63 61 74 69 6f 6e 20 6f 76 65 72 68 65 61 64  ocation overhead
0df0: 2e 20 20 54 68 65 0a 2a 2a 20 63 68 75 6e 6b 73  .  The.** chunks
0e00: 20 61 72 65 20 6b 65 70 74 20 6f 6e 20 61 20 6c   are kept on a l
0e10: 69 6e 6b 65 64 20 6c 69 73 74 20 73 6f 20 74 68  inked list so th
0e20: 61 74 20 74 68 65 79 20 63 61 6e 20 62 65 20 64  at they can be d
0e30: 65 61 6c 6c 6f 63 61 74 65 64 0a 2a 2a 20 77 68  eallocated.** wh
0e40: 65 6e 20 74 68 65 20 52 6f 77 53 65 74 20 69 73  en the RowSet is
0e50: 20 64 65 73 74 72 6f 79 65 64 2e 0a 2a 2f 0a 73   destroyed..*/.s
0e60: 74 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e  truct RowSetChun
0e70: 6b 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  k {.  struct Row
0e80: 53 65 74 43 68 75 6e 6b 20 2a 70 4e 65 78 74 43  SetChunk *pNextC
0e90: 68 75 6e 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20  hunk;        /* 
0ea0: 4e 65 78 74 20 63 68 75 6e 6b 20 6f 6e 20 6c 69  Next chunk on li
0eb0: 73 74 20 6f 66 20 74 68 65 6d 20 61 6c 6c 20 2a  st of them all *
0ec0: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
0ed0: 74 45 6e 74 72 79 20 61 45 6e 74 72 79 5b 52 4f  tEntry aEntry[RO
0ee0: 57 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f 43  WSET_ENTRY_PER_C
0ef0: 48 55 4e 4b 5d 3b 20 2f 2a 20 41 6c 6c 6f 63 61  HUNK]; /* Alloca
0f00: 74 65 64 20 65 6e 74 72 69 65 73 20 2a 2f 0a 7d  ted entries */.}
0f10: 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 52 6f 77 53 65  ;../*.** A RowSe
0f20: 74 20 69 6e 20 61 6e 20 69 6e 73 74 61 6e 63 65  t in an instance
0f30: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
0f40: 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a  g structure..**.
0f50: 2a 2a 20 41 20 74 79 70 65 64 65 66 20 6f 66 20  ** A typedef of 
0f60: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69  this structure i
0f70: 66 20 66 6f 75 6e 64 20 69 6e 20 73 71 6c 69 74  f found in sqlit
0f80: 65 49 6e 74 2e 68 2e 0a 2a 2f 0a 73 74 72 75 63  eInt.h..*/.struc
0f90: 74 20 52 6f 77 53 65 74 20 7b 0a 20 20 73 74 72  t RowSet {.  str
0fa0: 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20  uct RowSetChunk 
0fb0: 2a 70 43 68 75 6e 6b 3b 20 20 20 20 2f 2a 20 4c  *pChunk;    /* L
0fc0: 69 73 74 20 6f 66 20 61 6c 6c 20 63 68 75 6e 6b  ist of all chunk
0fd0: 20 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a   allocations */.
0fe0: 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20 20    sqlite3 *db;  
0ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1000: 20 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73 65   /* The database
1010: 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 2a 2f 0a 20   connection */. 
1020: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
1030: 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 20 20  try *pEntry;    
1040: 2f 2a 20 4c 69 73 74 20 6f 66 20 65 6e 74 72 69  /* List of entri
1050: 65 73 20 75 73 69 6e 67 20 70 52 69 67 68 74 20  es using pRight 
1060: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
1070: 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20  etEntry *pLast; 
1080: 20 20 20 20 2f 2a 20 4c 61 73 74 20 65 6e 74 72      /* Last entr
1090: 79 20 6f 6e 20 74 68 65 20 70 45 6e 74 72 79 20  y on the pEntry 
10a0: 6c 69 73 74 20 2a 2f 0a 20 20 73 74 72 75 63 74  list */.  struct
10b0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 46   RowSetEntry *pF
10c0: 72 65 73 68 3b 20 20 20 20 2f 2a 20 53 6f 75 72  resh;    /* Sour
10d0: 63 65 20 6f 66 20 6e 65 77 20 65 6e 74 72 79 20  ce of new entry 
10e0: 6f 62 6a 65 63 74 73 20 2a 2f 0a 20 20 73 74 72  objects */.  str
10f0: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
1100: 2a 70 46 6f 72 65 73 74 3b 20 20 20 2f 2a 20 4c  *pForest;   /* L
1110: 69 73 74 20 6f 66 20 62 69 6e 61 72 79 20 74 72  ist of binary tr
1120: 65 65 73 20 6f 66 20 65 6e 74 72 69 65 73 20 2a  ees of entries *
1130: 2f 0a 20 20 75 31 36 20 6e 46 72 65 73 68 3b 20  /.  u16 nFresh; 
1140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1150: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1160: 6f 62 6a 65 63 74 73 20 6f 6e 20 70 46 72 65 73  objects on pFres
1170: 68 20 2a 2f 0a 20 20 75 31 36 20 72 73 46 6c 61  h */.  u16 rsFla
1180: 67 73 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  gs;             
1190: 20 20 20 20 20 20 2f 2a 20 56 61 72 69 6f 75 73        /* Various
11a0: 20 66 6c 61 67 73 20 2a 2f 0a 20 20 69 6e 74 20   flags */.  int 
11b0: 69 42 61 74 63 68 3b 20 20 20 20 20 20 20 20 20  iBatch;         
11c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75             /* Cu
11d0: 72 72 65 6e 74 20 69 6e 73 65 72 74 20 62 61 74  rrent insert bat
11e0: 63 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  ch */.};../*.** 
11f0: 41 6c 6c 6f 77 65 64 20 76 61 6c 75 65 73 20 66  Allowed values f
1200: 6f 72 20 52 6f 77 53 65 74 2e 72 73 46 6c 61 67  or RowSet.rsFlag
1210: 73 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 57  s.*/.#define ROW
1220: 53 45 54 5f 53 4f 52 54 45 44 20 20 30 78 30 31  SET_SORTED  0x01
1230: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 52 6f     /* True if Ro
1240: 77 53 65 74 2e 70 45 6e 74 72 79 20 69 73 20 73  wSet.pEntry is s
1250: 6f 72 74 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65  orted */.#define
1260: 20 52 4f 57 53 45 54 5f 4e 45 58 54 20 20 20 20   ROWSET_NEXT    
1270: 30 78 30 32 20 20 20 2f 2a 20 54 72 75 65 20 69  0x02   /* True i
1280: 66 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e  f sqlite3RowSetN
1290: 65 78 74 28 29 20 68 61 73 20 62 65 65 6e 20 63  ext() has been c
12a0: 61 6c 6c 65 64 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20  alled */../*.** 
12b0: 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72 79  Turn bulk memory
12c0: 20 69 6e 74 6f 20 61 20 52 6f 77 53 65 74 20 6f   into a RowSet o
12d0: 62 6a 65 63 74 2e 20 20 4e 20 62 79 74 65 73 20  bject.  N bytes 
12e0: 6f 66 20 6d 65 6d 6f 72 79 0a 2a 2a 20 61 72 65  of memory.** are
12f0: 20 61 76 61 69 6c 61 62 6c 65 20 61 74 20 70 53   available at pS
1300: 70 61 63 65 2e 20 20 54 68 65 20 64 62 20 70 6f  pace.  The db po
1310: 69 6e 74 65 72 20 69 73 20 75 73 65 64 20 61 73  inter is used as
1320: 20 61 20 6d 65 6d 6f 72 79 20 63 6f 6e 74 65 78   a memory contex
1330: 74 0a 2a 2a 20 66 6f 72 20 61 6e 79 20 73 75 62  t.** for any sub
1340: 73 65 71 75 65 6e 74 20 61 6c 6c 6f 63 61 74 69  sequent allocati
1350: 6f 6e 73 20 74 68 61 74 20 6e 65 65 64 20 74 6f  ons that need to
1360: 20 6f 63 63 75 72 2e 0a 2a 2a 20 52 65 74 75 72   occur..** Retur
1370: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
1380: 68 65 20 6e 65 77 20 52 6f 77 53 65 74 20 6f 62  he new RowSet ob
1390: 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 49 74 20 6d  ject..**.** It m
13a0: 75 73 74 20 62 65 20 74 68 65 20 63 61 73 65 20  ust be the case 
13b0: 74 68 61 74 20 4e 20 69 73 20 73 75 66 66 69 63  that N is suffic
13c0: 69 65 6e 74 20 74 6f 20 6d 61 6b 65 20 61 20 52  ient to make a R
13d0: 6f 77 73 65 74 2e 20 20 49 66 20 6e 6f 74 0a 2a  owset.  If not.*
13e0: 2a 20 61 6e 20 61 73 73 65 72 74 69 6f 6e 20 66  * an assertion f
13f0: 61 75 6c 74 20 6f 63 63 75 72 73 2e 0a 2a 2a 20  ault occurs..** 
1400: 0a 2a 2a 20 49 66 20 4e 20 69 73 20 6c 61 72 67  .** If N is larg
1410: 65 72 20 74 68 61 6e 20 74 68 65 20 6d 69 6e 69  er than the mini
1420: 6d 75 6d 2c 20 75 73 65 20 74 68 65 20 73 75 72  mum, use the sur
1430: 70 6c 75 73 20 61 73 20 61 6e 20 69 6e 69 74 69  plus as an initi
1440: 61 6c 0a 2a 2a 20 61 6c 6c 6f 63 61 74 69 6f 6e  al.** allocation
1450: 20 6f 66 20 65 6e 74 72 69 65 73 20 61 76 61 69   of entries avai
1460: 6c 61 62 6c 65 20 74 6f 20 62 65 20 66 69 6c 6c  lable to be fill
1470: 65 64 2e 0a 2a 2f 0a 52 6f 77 53 65 74 20 2a 73  ed..*/.RowSet *s
1480: 71 6c 69 74 65 33 52 6f 77 53 65 74 49 6e 69 74  qlite3RowSetInit
1490: 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 76 6f  (sqlite3 *db, vo
14a0: 69 64 20 2a 70 53 70 61 63 65 2c 20 75 6e 73 69  id *pSpace, unsi
14b0: 67 6e 65 64 20 69 6e 74 20 4e 29 7b 0a 20 20 52  gned int N){.  R
14c0: 6f 77 53 65 74 20 2a 70 3b 0a 20 20 61 73 73 65  owSet *p;.  asse
14d0: 72 74 28 20 4e 20 3e 3d 20 52 4f 55 4e 44 38 28  rt( N >= ROUND8(
14e0: 73 69 7a 65 6f 66 28 2a 70 29 29 20 29 3b 0a 20  sizeof(*p)) );. 
14f0: 20 70 20 3d 20 70 53 70 61 63 65 3b 0a 20 20 70   p = pSpace;.  p
1500: 2d 3e 70 43 68 75 6e 6b 20 3d 20 30 3b 0a 20 20  ->pChunk = 0;.  
1510: 70 2d 3e 64 62 20 3d 20 64 62 3b 0a 20 20 70 2d  p->db = db;.  p-
1520: 3e 70 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 70  >pEntry = 0;.  p
1530: 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20 20 70  ->pLast = 0;.  p
1540: 2d 3e 70 46 6f 72 65 73 74 20 3d 20 30 3b 0a 20  ->pForest = 0;. 
1550: 20 70 2d 3e 70 46 72 65 73 68 20 3d 20 28 73 74   p->pFresh = (st
1560: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1570: 2a 29 28 52 4f 55 4e 44 38 28 73 69 7a 65 6f 66  *)(ROUND8(sizeof
1580: 28 2a 70 29 29 20 2b 20 28 63 68 61 72 2a 29 70  (*p)) + (char*)p
1590: 29 3b 0a 20 20 70 2d 3e 6e 46 72 65 73 68 20 3d  );.  p->nFresh =
15a0: 20 28 75 31 36 29 28 28 4e 20 2d 20 52 4f 55 4e   (u16)((N - ROUN
15b0: 44 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 29 2f  D8(sizeof(*p)))/
15c0: 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 52 6f  sizeof(struct Ro
15d0: 77 53 65 74 45 6e 74 72 79 29 29 3b 0a 20 20 70  wSetEntry));.  p
15e0: 2d 3e 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53  ->rsFlags = ROWS
15f0: 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20 70 2d 3e  ET_SORTED;.  p->
1600: 69 42 61 74 63 68 20 3d 20 30 3b 0a 20 20 72 65  iBatch = 0;.  re
1610: 74 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  turn p;.}../*.**
1620: 20 44 65 61 6c 6c 6f 63 61 74 65 20 61 6c 6c 20   Deallocate all 
1630: 63 68 75 6e 6b 73 20 66 72 6f 6d 20 61 20 52 6f  chunks from a Ro
1640: 77 53 65 74 2e 20 20 54 68 69 73 20 66 72 65 65  wSet.  This free
1650: 73 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 74 68 61  s all memory tha
1660: 74 0a 2a 2a 20 74 68 65 20 52 6f 77 53 65 74 20  t.** the RowSet 
1670: 68 61 73 20 61 6c 6c 6f 63 61 74 65 64 20 6f 76  has allocated ov
1680: 65 72 20 69 74 73 20 6c 69 66 65 74 69 6d 65 2e  er its lifetime.
1690: 20 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 69    This routine i
16a0: 73 0a 2a 2a 20 74 68 65 20 64 65 73 74 72 75 63  s.** the destruc
16b0: 74 6f 72 20 66 6f 72 20 74 68 65 20 52 6f 77 53  tor for the RowS
16c0: 65 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69  et..*/.void sqli
16d0: 74 65 33 52 6f 77 53 65 74 43 6c 65 61 72 28 52  te3RowSetClear(R
16e0: 6f 77 53 65 74 20 2a 70 29 7b 0a 20 20 73 74 72  owSet *p){.  str
16f0: 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20  uct RowSetChunk 
1700: 2a 70 43 68 75 6e 6b 2c 20 2a 70 4e 65 78 74 43  *pChunk, *pNextC
1710: 68 75 6e 6b 3b 0a 20 20 66 6f 72 28 70 43 68 75  hunk;.  for(pChu
1720: 6e 6b 3d 70 2d 3e 70 43 68 75 6e 6b 3b 20 70 43  nk=p->pChunk; pC
1730: 68 75 6e 6b 3b 20 70 43 68 75 6e 6b 20 3d 20 70  hunk; pChunk = p
1740: 4e 65 78 74 43 68 75 6e 6b 29 7b 0a 20 20 20 20  NextChunk){.    
1750: 70 4e 65 78 74 43 68 75 6e 6b 20 3d 20 70 43 68  pNextChunk = pCh
1760: 75 6e 6b 2d 3e 70 4e 65 78 74 43 68 75 6e 6b 3b  unk->pNextChunk;
1770: 0a 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 72  .    sqlite3DbFr
1780: 65 65 28 70 2d 3e 64 62 2c 20 70 43 68 75 6e 6b  ee(p->db, pChunk
1790: 29 3b 0a 20 20 7d 0a 20 20 70 2d 3e 70 43 68 75  );.  }.  p->pChu
17a0: 6e 6b 20 3d 20 30 3b 0a 20 20 70 2d 3e 6e 46 72  nk = 0;.  p->nFr
17b0: 65 73 68 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 45  esh = 0;.  p->pE
17c0: 6e 74 72 79 20 3d 20 30 3b 0a 20 20 70 2d 3e 70  ntry = 0;.  p->p
17d0: 4c 61 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e 70  Last = 0;.  p->p
17e0: 46 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20 70 2d  Forest = 0;.  p-
17f0: 3e 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53 45  >rsFlags = ROWSE
1800: 54 5f 53 4f 52 54 45 44 3b 0a 7d 0a 0a 2f 2a 0a  T_SORTED;.}../*.
1810: 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e 65  ** Allocate a ne
1820: 77 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62  w RowSetEntry ob
1830: 6a 65 63 74 20 74 68 61 74 20 69 73 20 61 73 73  ject that is ass
1840: 6f 63 69 61 74 65 64 20 77 69 74 68 20 74 68 65  ociated with the
1850: 0a 2a 2a 20 67 69 76 65 6e 20 52 6f 77 53 65 74  .** given RowSet
1860: 2e 20 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e  .  Return a poin
1870: 74 65 72 20 74 6f 20 74 68 65 20 6e 65 77 20 61  ter to the new a
1880: 6e 64 20 63 6f 6d 70 6c 65 74 65 6c 79 20 75 6e  nd completely un
1890: 69 6e 69 74 69 61 6c 69 7a 65 64 0a 2a 2a 20 6f  initialized.** o
18a0: 62 6a 65 63 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 49  bjected..**.** I
18b0: 6e 20 61 6e 20 4f 4f 4d 20 73 69 74 75 61 74 69  n an OOM situati
18c0: 6f 6e 2c 20 74 68 65 20 52 6f 77 53 65 74 2e 64  on, the RowSet.d
18d0: 62 2d 3e 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 20  b->mallocFailed 
18e0: 66 6c 61 67 20 69 73 20 73 65 74 20 61 6e 64 20  flag is set and 
18f0: 74 68 69 73 0a 2a 2a 20 72 6f 75 74 69 6e 65 20  this.** routine 
1900: 72 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 2a 2f  returns NULL..*/
1910: 0a 73 74 61 74 69 63 20 73 74 72 75 63 74 20 52  .static struct R
1920: 6f 77 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53  owSetEntry *rowS
1930: 65 74 45 6e 74 72 79 41 6c 6c 6f 63 28 52 6f 77  etEntryAlloc(Row
1940: 53 65 74 20 2a 70 29 7b 0a 20 20 61 73 73 65 72  Set *p){.  asser
1950: 74 28 20 70 21 3d 30 20 29 3b 0a 20 20 69 66 28  t( p!=0 );.  if(
1960: 20 70 2d 3e 6e 46 72 65 73 68 3d 3d 30 20 29 7b   p->nFresh==0 ){
1970: 0a 20 20 20 20 73 74 72 75 63 74 20 52 6f 77 53  .    struct RowS
1980: 65 74 43 68 75 6e 6b 20 2a 70 4e 65 77 3b 0a 20  etChunk *pNew;. 
1990: 20 20 20 70 4e 65 77 20 3d 20 73 71 6c 69 74 65     pNew = sqlite
19a0: 33 44 62 4d 61 6c 6c 6f 63 52 61 77 28 70 2d 3e  3DbMallocRaw(p->
19b0: 64 62 2c 20 73 69 7a 65 6f 66 28 2a 70 4e 65 77  db, sizeof(*pNew
19c0: 29 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77  ));.    if( pNew
19d0: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 74  ==0 ){.      ret
19e0: 75 72 6e 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20  urn 0;.    }.   
19f0: 20 70 4e 65 77 2d 3e 70 4e 65 78 74 43 68 75 6e   pNew->pNextChun
1a00: 6b 20 3d 20 70 2d 3e 70 43 68 75 6e 6b 3b 0a 20  k = p->pChunk;. 
1a10: 20 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d 20 70     p->pChunk = p
1a20: 4e 65 77 3b 0a 20 20 20 20 70 2d 3e 70 46 72 65  New;.    p->pFre
1a30: 73 68 20 3d 20 70 4e 65 77 2d 3e 61 45 6e 74 72  sh = pNew->aEntr
1a40: 79 3b 0a 20 20 20 20 70 2d 3e 6e 46 72 65 73 68  y;.    p->nFresh
1a50: 20 3d 20 52 4f 57 53 45 54 5f 45 4e 54 52 59 5f   = ROWSET_ENTRY_
1a60: 50 45 52 5f 43 48 55 4e 4b 3b 0a 20 20 7d 0a 20  PER_CHUNK;.  }. 
1a70: 20 70 2d 3e 6e 46 72 65 73 68 2d 2d 3b 0a 20 20   p->nFresh--;.  
1a80: 72 65 74 75 72 6e 20 70 2d 3e 70 46 72 65 73 68  return p->pFresh
1a90: 2b 2b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 73  ++;.}../*.** Ins
1aa0: 65 72 74 20 61 20 6e 65 77 20 76 61 6c 75 65 20  ert a new value 
1ab0: 69 6e 74 6f 20 61 20 52 6f 77 53 65 74 2e 0a 2a  into a RowSet..*
1ac0: 2a 0a 2a 2a 20 54 68 65 20 6d 61 6c 6c 6f 63 46  *.** The mallocF
1ad0: 61 69 6c 65 64 20 66 6c 61 67 20 6f 66 20 74 68  ailed flag of th
1ae0: 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  e database conne
1af0: 63 74 69 6f 6e 20 69 73 20 73 65 74 20 69 66 20  ction is set if 
1b00: 61 0a 2a 2a 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  a.** memory allo
1b10: 63 61 74 69 6f 6e 20 66 61 69 6c 73 2e 0a 2a 2f  cation fails..*/
1b20: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77  .void sqlite3Row
1b30: 53 65 74 49 6e 73 65 72 74 28 52 6f 77 53 65 74  SetInsert(RowSet
1b40: 20 2a 70 2c 20 69 36 34 20 72 6f 77 69 64 29 7b   *p, i64 rowid){
1b50: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
1b60: 45 6e 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20  Entry *pEntry;  
1b70: 2f 2a 20 54 68 65 20 6e 65 77 20 65 6e 74 72 79  /* The new entry
1b80: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
1b90: 53 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b  SetEntry *pLast;
1ba0: 20 20 20 2f 2a 20 54 68 65 20 6c 61 73 74 20 70     /* The last p
1bb0: 72 69 6f 72 20 65 6e 74 72 79 20 2a 2f 0a 0a 20  rior entry */.. 
1bc0: 20 2f 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65   /* This routine
1bd0: 20 69 73 20 6e 65 76 65 72 20 63 61 6c 6c 65 64   is never called
1be0: 20 61 66 74 65 72 20 73 71 6c 69 74 65 33 52 6f   after sqlite3Ro
1bf0: 77 53 65 74 4e 65 78 74 28 29 20 2a 2f 0a 20 20  wSetNext() */.  
1c00: 61 73 73 65 72 74 28 20 70 21 3d 30 20 26 26 20  assert( p!=0 && 
1c10: 28 70 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f  (p->rsFlags & RO
1c20: 57 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b  WSET_NEXT)==0 );
1c30: 0a 0a 20 20 70 45 6e 74 72 79 20 3d 20 72 6f 77  ..  pEntry = row
1c40: 53 65 74 45 6e 74 72 79 41 6c 6c 6f 63 28 70 29  SetEntryAlloc(p)
1c50: 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79 3d 3d  ;.  if( pEntry==
1c60: 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 70 45  0 ) return;.  pE
1c70: 6e 74 72 79 2d 3e 76 20 3d 20 72 6f 77 69 64 3b  ntry->v = rowid;
1c80: 0a 20 20 70 45 6e 74 72 79 2d 3e 70 52 69 67 68  .  pEntry->pRigh
1c90: 74 20 3d 20 30 3b 0a 20 20 70 4c 61 73 74 20 3d  t = 0;.  pLast =
1ca0: 20 70 2d 3e 70 4c 61 73 74 3b 0a 20 20 69 66 28   p->pLast;.  if(
1cb0: 20 70 4c 61 73 74 20 29 7b 0a 20 20 20 20 69 66   pLast ){.    if
1cc0: 28 20 28 70 2d 3e 72 73 46 6c 61 67 73 20 26 20  ( (p->rsFlags & 
1cd0: 52 4f 57 53 45 54 5f 53 4f 52 54 45 44 29 21 3d  ROWSET_SORTED)!=
1ce0: 30 20 26 26 20 72 6f 77 69 64 3c 3d 70 4c 61 73  0 && rowid<=pLas
1cf0: 74 2d 3e 76 20 29 7b 0a 20 20 20 20 20 20 70 2d  t->v ){.      p-
1d00: 3e 72 73 46 6c 61 67 73 20 26 3d 20 7e 52 4f 57  >rsFlags &= ~ROW
1d10: 53 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20 20 20  SET_SORTED;.    
1d20: 7d 0a 20 20 20 20 70 4c 61 73 74 2d 3e 70 52 69  }.    pLast->pRi
1d30: 67 68 74 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20  ght = pEntry;.  
1d40: 7d 65 6c 73 65 7b 0a 20 20 20 20 70 2d 3e 70 45  }else{.    p->pE
1d50: 6e 74 72 79 20 3d 20 70 45 6e 74 72 79 3b 0a 20  ntry = pEntry;. 
1d60: 20 7d 0a 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20   }.  p->pLast = 
1d70: 70 45 6e 74 72 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  pEntry;.}../*.**
1d80: 20 4d 65 72 67 65 20 74 77 6f 20 6c 69 73 74 73   Merge two lists
1d90: 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79 20   of RowSetEntry 
1da0: 6f 62 6a 65 63 74 73 2e 20 20 52 65 6d 6f 76 65  objects.  Remove
1db0: 20 64 75 70 6c 69 63 61 74 65 73 2e 0a 2a 2a 0a   duplicates..**.
1dc0: 2a 2a 20 54 68 65 20 69 6e 70 75 74 20 6c 69 73  ** The input lis
1dd0: 74 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 64  ts are connected
1de0: 20 76 69 61 20 70 52 69 67 68 74 20 70 6f 69 6e   via pRight poin
1df0: 74 65 72 73 20 61 6e 64 20 61 72 65 20 0a 2a 2a  ters and are .**
1e00: 20 61 73 73 75 6d 65 64 20 74 6f 20 65 61 63 68   assumed to each
1e10: 20 61 6c 72 65 61 64 79 20 62 65 20 69 6e 20 73   already be in s
1e20: 6f 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2f 0a  orted order..*/.
1e30: 73 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f  static struct Ro
1e40: 77 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65  wSetEntry *rowSe
1e50: 74 45 6e 74 72 79 4d 65 72 67 65 28 0a 20 20 73  tEntryMerge(.  s
1e60: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
1e70: 79 20 2a 70 41 2c 20 20 20 20 2f 2a 20 46 69 72  y *pA,    /* Fir
1e80: 73 74 20 73 6f 72 74 65 64 20 6c 69 73 74 20 74  st sorted list t
1e90: 6f 20 62 65 20 6d 65 72 67 65 64 20 2a 2f 0a 20  o be merged */. 
1ea0: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
1eb0: 74 72 79 20 2a 70 42 20 20 20 20 20 2f 2a 20 53  try *pB     /* S
1ec0: 65 63 6f 6e 64 20 73 6f 72 74 65 64 20 6c 69 73  econd sorted lis
1ed0: 74 20 74 6f 20 62 65 20 6d 65 72 67 65 64 20 2a  t to be merged *
1ee0: 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 52 6f  /.){.  struct Ro
1ef0: 77 53 65 74 45 6e 74 72 79 20 68 65 61 64 3b 0a  wSetEntry head;.
1f00: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
1f10: 6e 74 72 79 20 2a 70 54 61 69 6c 3b 0a 0a 20 20  ntry *pTail;..  
1f20: 70 54 61 69 6c 20 3d 20 26 68 65 61 64 3b 0a 20  pTail = &head;. 
1f30: 20 77 68 69 6c 65 28 20 70 41 20 26 26 20 70 42   while( pA && pB
1f40: 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20   ){.    assert( 
1f50: 70 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c 7c  pA->pRight==0 ||
1f60: 20 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69 67   pA->v<=pA->pRig
1f70: 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 61 73 73  ht->v );.    ass
1f80: 65 72 74 28 20 70 42 2d 3e 70 52 69 67 68 74 3d  ert( pB->pRight=
1f90: 3d 30 20 7c 7c 20 70 42 2d 3e 76 3c 3d 70 42 2d  =0 || pB->v<=pB-
1fa0: 3e 70 52 69 67 68 74 2d 3e 76 20 29 3b 0a 20 20  >pRight->v );.  
1fb0: 20 20 69 66 28 20 70 41 2d 3e 76 3c 70 42 2d 3e    if( pA->v<pB->
1fc0: 76 20 29 7b 0a 20 20 20 20 20 20 70 54 61 69 6c  v ){.      pTail
1fd0: 2d 3e 70 52 69 67 68 74 20 3d 20 70 41 3b 0a 20  ->pRight = pA;. 
1fe0: 20 20 20 20 20 70 41 20 3d 20 70 41 2d 3e 70 52       pA = pA->pR
1ff0: 69 67 68 74 3b 0a 20 20 20 20 20 20 70 54 61 69  ight;.      pTai
2000: 6c 20 3d 20 70 54 61 69 6c 2d 3e 70 52 69 67 68  l = pTail->pRigh
2010: 74 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28  t;.    }else if(
2020: 20 70 42 2d 3e 76 3c 70 41 2d 3e 76 20 29 7b 0a   pB->v<pA->v ){.
2030: 20 20 20 20 20 20 70 54 61 69 6c 2d 3e 70 52 69        pTail->pRi
2040: 67 68 74 20 3d 20 70 42 3b 0a 20 20 20 20 20 20  ght = pB;.      
2050: 70 42 20 3d 20 70 42 2d 3e 70 52 69 67 68 74 3b  pB = pB->pRight;
2060: 0a 20 20 20 20 20 20 70 54 61 69 6c 20 3d 20 70  .      pTail = p
2070: 54 61 69 6c 2d 3e 70 52 69 67 68 74 3b 0a 20 20  Tail->pRight;.  
2080: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 70    }else{.      p
2090: 41 20 3d 20 70 41 2d 3e 70 52 69 67 68 74 3b 0a  A = pA->pRight;.
20a0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20      }.  }.  if( 
20b0: 70 41 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74  pA ){.    assert
20c0: 28 20 70 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20  ( pA->pRight==0 
20d0: 7c 7c 20 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52  || pA->v<=pA->pR
20e0: 69 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70  ight->v );.    p
20f0: 54 61 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70  Tail->pRight = p
2100: 41 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  A;.  }else{.    
2110: 61 73 73 65 72 74 28 20 70 42 3d 3d 30 20 7c 7c  assert( pB==0 ||
2120: 20 70 42 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c   pB->pRight==0 |
2130: 7c 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e 70 52 69  | pB->v<=pB->pRi
2140: 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70 54  ght->v );.    pT
2150: 61 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42  ail->pRight = pB
2160: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68  ;.  }.  return h
2170: 65 61 64 2e 70 52 69 67 68 74 3b 0a 7d 0a 0a 2f  ead.pRight;.}../
2180: 2a 0a 2a 2a 20 53 6f 72 74 20 61 6c 6c 20 65 6c  *.** Sort all el
2190: 65 6d 65 6e 74 73 20 6f 6e 20 74 68 65 20 6c 69  ements on the li
21a0: 73 74 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72  st of RowSetEntr
21b0: 79 20 6f 62 6a 65 63 74 73 20 69 6e 74 6f 20 6f  y objects into o
21c0: 72 64 65 72 20 6f 66 0a 2a 2a 20 69 6e 63 72 65  rder of.** incre
21d0: 61 73 69 6e 67 20 76 2e 0a 2a 2f 20 0a 73 74 61  asing v..*/ .sta
21e0: 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53 65  tic struct RowSe
21f0: 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 45 6e  tEntry *rowSetEn
2200: 74 72 79 53 6f 72 74 28 73 74 72 75 63 74 20 52  trySort(struct R
2210: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 49 6e 29  owSetEntry *pIn)
2220: 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  {.  unsigned int
2230: 20 69 3b 0a 20 20 73 74 72 75 63 74 20 52 6f 77   i;.  struct Row
2240: 53 65 74 45 6e 74 72 79 20 2a 70 4e 65 78 74 2c  SetEntry *pNext,
2250: 20 2a 61 42 75 63 6b 65 74 5b 34 30 5d 3b 0a 0a   *aBucket[40];..
2260: 20 20 6d 65 6d 73 65 74 28 61 42 75 63 6b 65 74    memset(aBucket
2270: 2c 20 30 2c 20 73 69 7a 65 6f 66 28 61 42 75 63  , 0, sizeof(aBuc
2280: 6b 65 74 29 29 3b 0a 20 20 77 68 69 6c 65 28 20  ket));.  while( 
2290: 70 49 6e 20 29 7b 0a 20 20 20 20 70 4e 65 78 74  pIn ){.    pNext
22a0: 20 3d 20 70 49 6e 2d 3e 70 52 69 67 68 74 3b 0a   = pIn->pRight;.
22b0: 20 20 20 20 70 49 6e 2d 3e 70 52 69 67 68 74 20      pIn->pRight 
22c0: 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d 30  = 0;.    for(i=0
22d0: 3b 20 61 42 75 63 6b 65 74 5b 69 5d 3b 20 69 2b  ; aBucket[i]; i+
22e0: 2b 29 7b 0a 20 20 20 20 20 20 70 49 6e 20 3d 20  +){.      pIn = 
22f0: 72 6f 77 53 65 74 45 6e 74 72 79 4d 65 72 67 65  rowSetEntryMerge
2300: 28 61 42 75 63 6b 65 74 5b 69 5d 2c 20 70 49 6e  (aBucket[i], pIn
2310: 29 3b 0a 20 20 20 20 20 20 61 42 75 63 6b 65 74  );.      aBucket
2320: 5b 69 5d 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20  [i] = 0;.    }. 
2330: 20 20 20 61 42 75 63 6b 65 74 5b 69 5d 20 3d 20     aBucket[i] = 
2340: 70 49 6e 3b 0a 20 20 20 20 70 49 6e 20 3d 20 70  pIn;.    pIn = p
2350: 4e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 49 6e 20  Next;.  }.  pIn 
2360: 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20  = 0;.  for(i=0; 
2370: 69 3c 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74  i<sizeof(aBucket
2380: 29 2f 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74  )/sizeof(aBucket
2390: 5b 30 5d 29 3b 20 69 2b 2b 29 7b 0a 20 20 20 20  [0]); i++){.    
23a0: 70 49 6e 20 3d 20 72 6f 77 53 65 74 45 6e 74 72  pIn = rowSetEntr
23b0: 79 4d 65 72 67 65 28 70 49 6e 2c 20 61 42 75 63  yMerge(pIn, aBuc
23c0: 6b 65 74 5b 69 5d 29 3b 0a 20 20 7d 0a 20 20 72  ket[i]);.  }.  r
23d0: 65 74 75 72 6e 20 70 49 6e 3b 0a 7d 0a 0a 0a 2f  eturn pIn;.}.../
23e0: 2a 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74 2c 20  *.** The input, 
23f0: 70 49 6e 2c 20 69 73 20 61 20 62 69 6e 61 72 79  pIn, is a binary
2400: 20 74 72 65 65 20 28 6f 72 20 73 75 62 74 72 65   tree (or subtre
2410: 65 29 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72  e) of RowSetEntr
2420: 79 20 6f 62 6a 65 63 74 73 2e 0a 2a 2a 20 43 6f  y objects..** Co
2430: 6e 76 65 72 74 20 74 68 69 73 20 74 72 65 65 20  nvert this tree 
2440: 69 6e 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69  into a linked li
2450: 73 74 20 63 6f 6e 6e 65 63 74 65 64 20 62 79 20  st connected by 
2460: 74 68 65 20 70 52 69 67 68 74 20 70 6f 69 6e 74  the pRight point
2470: 65 72 73 0a 2a 2a 20 61 6e 64 20 72 65 74 75 72  ers.** and retur
2480: 6e 20 70 6f 69 6e 74 65 72 73 20 74 6f 20 74 68  n pointers to th
2490: 65 20 66 69 72 73 74 20 61 6e 64 20 6c 61 73 74  e first and last
24a0: 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65   elements of the
24b0: 20 6e 65 77 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74   new list..*/.st
24c0: 61 74 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74  atic void rowSet
24d0: 54 72 65 65 54 6f 4c 69 73 74 28 0a 20 20 73 74  TreeToList(.  st
24e0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
24f0: 20 2a 70 49 6e 2c 20 20 20 20 20 20 20 20 20 2f   *pIn,         /
2500: 2a 20 52 6f 6f 74 20 6f 66 20 74 68 65 20 69 6e  * Root of the in
2510: 70 75 74 20 74 72 65 65 20 2a 2f 0a 20 20 73 74  put tree */.  st
2520: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2530: 20 2a 2a 70 70 46 69 72 73 74 2c 20 20 20 20 2f   **ppFirst,    /
2540: 2a 20 57 72 69 74 65 20 68 65 61 64 20 6f 66 20  * Write head of 
2550: 74 68 65 20 6f 75 74 70 75 74 20 6c 69 73 74 20  the output list 
2560: 68 65 72 65 20 2a 2f 0a 20 20 73 74 72 75 63 74  here */.  struct
2570: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a 70   RowSetEntry **p
2580: 70 4c 61 73 74 20 20 20 20 20 20 2f 2a 20 57 72  pLast      /* Wr
2590: 69 74 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20  ite tail of the 
25a0: 6f 75 74 70 75 74 20 6c 69 73 74 20 68 65 72 65  output list here
25b0: 20 2a 2f 0a 29 7b 0a 20 20 61 73 73 65 72 74 28   */.){.  assert(
25c0: 20 70 49 6e 21 3d 30 20 29 3b 0a 20 20 69 66 28   pIn!=0 );.  if(
25d0: 20 70 49 6e 2d 3e 70 4c 65 66 74 20 29 7b 0a 20   pIn->pLeft ){. 
25e0: 20 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74     struct RowSet
25f0: 45 6e 74 72 79 20 2a 70 3b 0a 20 20 20 20 72 6f  Entry *p;.    ro
2600: 77 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70  wSetTreeToList(p
2610: 49 6e 2d 3e 70 4c 65 66 74 2c 20 70 70 46 69 72  In->pLeft, ppFir
2620: 73 74 2c 20 26 70 29 3b 0a 20 20 20 20 70 2d 3e  st, &p);.    p->
2630: 70 52 69 67 68 74 20 3d 20 70 49 6e 3b 0a 20 20  pRight = pIn;.  
2640: 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 46 69  }else{.    *ppFi
2650: 72 73 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20  rst = pIn;.  }. 
2660: 20 69 66 28 20 70 49 6e 2d 3e 70 52 69 67 68 74   if( pIn->pRight
2670: 20 29 7b 0a 20 20 20 20 72 6f 77 53 65 74 54 72   ){.    rowSetTr
2680: 65 65 54 6f 4c 69 73 74 28 70 49 6e 2d 3e 70 52  eeToList(pIn->pR
2690: 69 67 68 74 2c 20 26 70 49 6e 2d 3e 70 52 69 67  ight, &pIn->pRig
26a0: 68 74 2c 20 70 70 4c 61 73 74 29 3b 0a 20 20 7d  ht, ppLast);.  }
26b0: 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 4c 61 73  else{.    *ppLas
26c0: 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20 61  t = pIn;.  }.  a
26d0: 73 73 65 72 74 28 20 28 2a 70 70 4c 61 73 74 29  ssert( (*ppLast)
26e0: 2d 3e 70 52 69 67 68 74 3d 3d 30 20 29 3b 0a 7d  ->pRight==0 );.}
26f0: 0a 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65 72 74  .../*.** Convert
2700: 20 61 20 73 6f 72 74 65 64 20 6c 69 73 74 20 6f   a sorted list o
2710: 66 20 65 6c 65 6d 65 6e 74 73 20 28 63 6f 6e 6e  f elements (conn
2720: 65 63 74 65 64 20 62 79 20 70 52 69 67 68 74 29  ected by pRight)
2730: 20 69 6e 74 6f 20 61 20 62 69 6e 61 72 79 0a 2a   into a binary.*
2740: 2a 20 74 72 65 65 20 77 69 74 68 20 64 65 70 74  * tree with dept
2750: 68 20 6f 66 20 69 44 65 70 74 68 2e 20 20 41 20  h of iDepth.  A 
2760: 64 65 70 74 68 20 6f 66 20 31 20 6d 65 61 6e 73  depth of 1 means
2770: 20 74 68 65 20 74 72 65 65 20 63 6f 6e 74 61 69   the tree contai
2780: 6e 73 20 61 20 73 69 6e 67 6c 65 0a 2a 2a 20 6e  ns a single.** n
2790: 6f 64 65 20 74 61 6b 65 6e 20 66 72 6f 6d 20 74  ode taken from t
27a0: 68 65 20 68 65 61 64 20 6f 66 20 2a 70 70 4c 69  he head of *ppLi
27b0: 73 74 2e 20 20 41 20 64 65 70 74 68 20 6f 66 20  st.  A depth of 
27c0: 32 20 6d 65 61 6e 73 20 61 20 74 72 65 65 20 77  2 means a tree w
27d0: 69 74 68 0a 2a 2a 20 74 68 72 65 65 20 6e 6f 64  ith.** three nod
27e0: 65 73 2e 20 20 41 6e 64 20 73 6f 20 66 6f 72 74  es.  And so fort
27f0: 68 2e 0a 2a 2a 0a 2a 2a 20 55 73 65 20 61 73 20  h..**.** Use as 
2800: 6d 61 6e 79 20 65 6e 74 72 69 65 73 20 66 72 6f  many entries fro
2810: 6d 20 74 68 65 20 69 6e 70 75 74 20 6c 69 73 74  m the input list
2820: 20 61 73 20 72 65 71 75 69 72 65 64 20 61 6e 64   as required and
2830: 20 75 70 64 61 74 65 20 74 68 65 0a 2a 2a 20 2a   update the.** *
2840: 70 70 4c 69 73 74 20 74 6f 20 70 6f 69 6e 74 20  ppList to point 
2850: 74 6f 20 74 68 65 20 75 6e 75 73 65 64 20 65 6c  to the unused el
2860: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 6c 69  ements of the li
2870: 73 74 2e 20 20 49 66 20 74 68 65 20 69 6e 70 75  st.  If the inpu
2880: 74 0a 2a 2a 20 6c 69 73 74 20 63 6f 6e 74 61 69  t.** list contai
2890: 6e 73 20 74 6f 6f 20 66 65 77 20 65 6c 65 6d 65  ns too few eleme
28a0: 6e 74 73 2c 20 74 68 65 6e 20 63 6f 6e 73 74 72  nts, then constr
28b0: 75 63 74 20 61 6e 20 69 6e 63 6f 6d 70 6c 65 74  uct an incomplet
28c0: 65 20 74 72 65 65 0a 2a 2a 20 61 6e 64 20 6c 65  e tree.** and le
28d0: 61 76 65 20 2a 70 70 4c 69 73 74 20 73 65 74 20  ave *ppList set 
28e0: 74 6f 20 4e 55 4c 4c 2e 0a 2a 2a 0a 2a 2a 20 52  to NULL..**.** R
28f0: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20  eturn a pointer 
2900: 74 6f 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74  to the root of t
2910: 68 65 20 63 6f 6e 73 74 72 75 63 74 65 64 20 62  he constructed b
2920: 69 6e 61 72 79 20 74 72 65 65 2e 0a 2a 2f 0a 73  inary tree..*/.s
2930: 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77  tatic struct Row
2940: 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74  SetEntry *rowSet
2950: 4e 44 65 65 70 54 72 65 65 28 0a 20 20 73 74 72  NDeepTree(.  str
2960: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2970: 2a 2a 70 70 4c 69 73 74 2c 0a 20 20 69 6e 74 20  **ppList,.  int 
2980: 69 44 65 70 74 68 0a 29 7b 0a 20 20 73 74 72 75  iDepth.){.  stru
2990: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
29a0: 70 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f  p;         /* Ro
29b0: 6f 74 20 6f 66 20 74 68 65 20 6e 65 77 20 74 72  ot of the new tr
29c0: 65 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52  ee */.  struct R
29d0: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 4c 65 66  owSetEntry *pLef
29e0: 74 3b 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73  t;     /* Left s
29f0: 75 62 74 72 65 65 20 2a 2f 0a 20 20 69 66 28 20  ubtree */.  if( 
2a00: 2a 70 70 4c 69 73 74 3d 3d 30 20 29 7b 0a 20 20  *ppList==0 ){.  
2a10: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a    return 0;.  }.
2a20: 20 20 69 66 28 20 69 44 65 70 74 68 3d 3d 31 20    if( iDepth==1 
2a30: 29 7b 0a 20 20 20 20 70 20 3d 20 2a 70 70 4c 69  ){.    p = *ppLi
2a40: 73 74 3b 0a 20 20 20 20 2a 70 70 4c 69 73 74 20  st;.    *ppList 
2a50: 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  = p->pRight;.   
2a60: 20 70 2d 3e 70 4c 65 66 74 20 3d 20 70 2d 3e 70   p->pLeft = p->p
2a70: 52 69 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 72  Right = 0;.    r
2a80: 65 74 75 72 6e 20 70 3b 0a 20 20 7d 0a 20 20 70  eturn p;.  }.  p
2a90: 4c 65 66 74 20 3d 20 72 6f 77 53 65 74 4e 44 65  Left = rowSetNDe
2aa0: 65 70 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69  epTree(ppList, i
2ab0: 44 65 70 74 68 2d 31 29 3b 0a 20 20 70 20 3d 20  Depth-1);.  p = 
2ac0: 2a 70 70 4c 69 73 74 3b 0a 20 20 69 66 28 20 70  *ppList;.  if( p
2ad0: 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72  ==0 ){.    retur
2ae0: 6e 20 70 4c 65 66 74 3b 0a 20 20 7d 0a 20 20 70  n pLeft;.  }.  p
2af0: 2d 3e 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b  ->pLeft = pLeft;
2b00: 0a 20 20 2a 70 70 4c 69 73 74 20 3d 20 70 2d 3e  .  *ppList = p->
2b10: 70 52 69 67 68 74 3b 0a 20 20 70 2d 3e 70 52 69  pRight;.  p->pRi
2b20: 67 68 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65  ght = rowSetNDee
2b30: 70 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44  pTree(ppList, iD
2b40: 65 70 74 68 2d 31 29 3b 0a 20 20 72 65 74 75 72  epth-1);.  retur
2b50: 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f  n p;.}../*.** Co
2b60: 6e 76 65 72 74 20 61 20 73 6f 72 74 65 64 20 6c  nvert a sorted l
2b70: 69 73 74 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20  ist of elements 
2b80: 69 6e 74 6f 20 61 20 62 69 6e 61 72 79 20 74 72  into a binary tr
2b90: 65 65 2e 20 4d 61 6b 65 20 74 68 65 20 74 72 65  ee. Make the tre
2ba0: 65 0a 2a 2a 20 61 73 20 64 65 65 70 20 61 73 20  e.** as deep as 
2bb0: 69 74 20 6e 65 65 64 73 20 74 6f 20 62 65 20 69  it needs to be i
2bc0: 6e 20 6f 72 64 65 72 20 74 6f 20 63 6f 6e 74 61  n order to conta
2bd0: 69 6e 20 74 68 65 20 65 6e 74 69 72 65 20 6c 69  in the entire li
2be0: 73 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74  st..*/.static st
2bf0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2c00: 20 2a 72 6f 77 53 65 74 4c 69 73 74 54 6f 54 72   *rowSetListToTr
2c10: 65 65 28 73 74 72 75 63 74 20 52 6f 77 53 65 74  ee(struct RowSet
2c20: 45 6e 74 72 79 20 2a 70 4c 69 73 74 29 7b 0a 20  Entry *pList){. 
2c30: 20 69 6e 74 20 69 44 65 70 74 68 3b 20 20 20 20   int iDepth;    
2c40: 20 20 20 20 20 20 20 2f 2a 20 44 65 70 74 68 20         /* Depth 
2c50: 6f 66 20 74 68 65 20 74 72 65 65 20 73 6f 20 66  of the tree so f
2c60: 61 72 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52  ar */.  struct R
2c70: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 3b 20 20  owSetEntry *p;  
2c80: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
2c90: 74 72 65 65 20 72 6f 6f 74 20 2a 2f 0a 20 20 73  tree root */.  s
2ca0: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
2cb0: 79 20 2a 70 4c 65 66 74 3b 20 20 20 2f 2a 20 4c  y *pLeft;   /* L
2cc0: 65 66 74 20 73 75 62 74 72 65 65 20 2a 2f 0a 0a  eft subtree */..
2cd0: 20 20 61 73 73 65 72 74 28 20 70 4c 69 73 74 21    assert( pList!
2ce0: 3d 30 20 29 3b 0a 20 20 70 20 3d 20 70 4c 69 73  =0 );.  p = pLis
2cf0: 74 3b 0a 20 20 70 4c 69 73 74 20 3d 20 70 2d 3e  t;.  pList = p->
2d00: 70 52 69 67 68 74 3b 0a 20 20 70 2d 3e 70 4c 65  pRight;.  p->pLe
2d10: 66 74 20 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d  ft = p->pRight =
2d20: 20 30 3b 0a 20 20 66 6f 72 28 69 44 65 70 74 68   0;.  for(iDepth
2d30: 3d 31 3b 20 70 4c 69 73 74 3b 20 69 44 65 70 74  =1; pList; iDept
2d40: 68 2b 2b 29 7b 0a 20 20 20 20 70 4c 65 66 74 20  h++){.    pLeft 
2d50: 3d 20 70 3b 0a 20 20 20 20 70 20 3d 20 70 4c 69  = p;.    p = pLi
2d60: 73 74 3b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20  st;.    pList = 
2d70: 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70  p->pRight;.    p
2d80: 2d 3e 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b  ->pLeft = pLeft;
2d90: 0a 20 20 20 20 70 2d 3e 70 52 69 67 68 74 20 3d  .    p->pRight =
2da0: 20 72 6f 77 53 65 74 4e 44 65 65 70 54 72 65 65   rowSetNDeepTree
2db0: 28 26 70 4c 69 73 74 2c 20 69 44 65 70 74 68 29  (&pList, iDepth)
2dc0: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70  ;.  }.  return p
2dd0: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 61 6b 65 20  ;.}../*.** Take 
2de0: 61 6c 6c 20 74 68 65 20 65 6e 74 72 69 65 73 20  all the entries 
2df0: 6f 6e 20 70 2d 3e 70 45 6e 74 72 79 20 61 6e 64  on p->pEntry and
2e00: 20 6f 6e 20 74 68 65 20 74 72 65 65 73 20 69 6e   on the trees in
2e10: 20 70 2d 3e 70 46 6f 72 65 73 74 20 61 6e 64 0a   p->pForest and.
2e20: 2a 2a 20 73 6f 72 74 20 74 68 65 6d 20 61 6c 6c  ** sort them all
2e30: 20 74 6f 67 65 74 68 65 72 20 69 6e 74 6f 20 6f   together into o
2e40: 6e 65 20 62 69 67 20 6f 72 64 65 72 65 64 20 6c  ne big ordered l
2e50: 69 73 74 20 6f 6e 20 70 2d 3e 70 45 6e 74 72 79  ist on p->pEntry
2e60: 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75  ..**.** This rou
2e70: 74 69 6e 65 20 73 68 6f 75 6c 64 20 6f 6e 6c 79  tine should only
2e80: 20 62 65 20 63 61 6c 6c 65 64 20 6f 6e 63 65 20   be called once 
2e90: 69 6e 20 74 68 65 20 6c 69 66 65 20 6f 66 20 61  in the life of a
2ea0: 20 52 6f 77 53 65 74 2e 0a 2a 2f 0a 73 74 61 74   RowSet..*/.stat
2eb0: 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74 54 6f  ic void rowSetTo
2ec0: 4c 69 73 74 28 52 6f 77 53 65 74 20 2a 70 29 7b  List(RowSet *p){
2ed0: 0a 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f 75 74  ..  /* This rout
2ee0: 69 6e 65 20 69 73 20 63 61 6c 6c 65 64 20 6f 6e  ine is called on
2ef0: 6c 79 20 6f 6e 63 65 20 2a 2f 0a 20 20 61 73 73  ly once */.  ass
2f00: 65 72 74 28 20 70 21 3d 30 20 26 26 20 28 70 2d  ert( p!=0 && (p-
2f10: 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53 45  >rsFlags & ROWSE
2f20: 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b 0a 0a 20  T_NEXT)==0 );.. 
2f30: 20 69 66 28 20 28 70 2d 3e 72 73 46 6c 61 67 73   if( (p->rsFlags
2f40: 20 26 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44   & ROWSET_SORTED
2f50: 29 3d 3d 30 20 29 7b 0a 20 20 20 20 70 2d 3e 70  )==0 ){.    p->p
2f60: 45 6e 74 72 79 20 3d 20 72 6f 77 53 65 74 45 6e  Entry = rowSetEn
2f70: 74 72 79 53 6f 72 74 28 70 2d 3e 70 45 6e 74 72  trySort(p->pEntr
2f80: 79 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 68  y);.  }..  /* Wh
2f90: 69 6c 65 20 74 68 69 73 20 6d 6f 64 75 6c 65 20  ile this module 
2fa0: 63 6f 75 6c 64 20 74 68 65 6f 72 65 74 69 63 61  could theoretica
2fb0: 6c 6c 79 20 73 75 70 70 6f 72 74 20 69 74 2c 20  lly support it, 
2fc0: 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65 78  sqlite3RowSetNex
2fd0: 74 28 29 0a 20 20 2a 2a 20 69 73 20 6e 65 76 65  t().  ** is neve
2fe0: 72 20 63 61 6c 6c 65 64 20 61 66 74 65 72 20 73  r called after s
2ff0: 71 6c 69 74 65 33 52 6f 77 53 65 74 54 65 78 74  qlite3RowSetText
3000: 28 29 20 66 6f 72 20 74 68 65 20 73 61 6d 65 20  () for the same 
3010: 52 6f 77 53 65 74 2e 20 20 53 6f 0a 20 20 2a 2a  RowSet.  So.  **
3020: 20 74 68 65 72 65 20 69 73 20 6e 65 76 65 72 20   there is never 
3030: 61 20 66 6f 72 65 73 74 20 74 6f 20 64 65 61 6c  a forest to deal
3040: 20 77 69 74 68 2e 20 20 53 68 6f 75 6c 64 20 74   with.  Should t
3050: 68 69 73 20 63 68 61 6e 67 65 2c 20 73 69 6d 70  his change, simp
3060: 6c 79 0a 20 20 2a 2a 20 72 65 6d 6f 76 65 20 74  ly.  ** remove t
3070: 68 65 20 61 73 73 65 72 74 28 29 20 61 6e 64 20  he assert() and 
3080: 74 68 65 20 23 69 66 20 30 2e 20 2a 2f 0a 20 20  the #if 0. */.  
3090: 61 73 73 65 72 74 28 20 70 2d 3e 70 46 6f 72 65  assert( p->pFore
30a0: 73 74 3d 3d 30 20 29 3b 0a 23 69 66 20 30 0a 20  st==0 );.#if 0. 
30b0: 20 77 68 69 6c 65 28 20 70 2d 3e 70 46 6f 72 65   while( p->pFore
30c0: 73 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74  st ){.    struct
30d0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 54   RowSetEntry *pT
30e0: 72 65 65 20 3d 20 70 2d 3e 70 46 6f 72 65 73 74  ree = p->pForest
30f0: 2d 3e 70 4c 65 66 74 3b 0a 20 20 20 20 69 66 28  ->pLeft;.    if(
3100: 20 70 54 72 65 65 20 29 7b 0a 20 20 20 20 20 20   pTree ){.      
3110: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
3120: 72 79 20 2a 70 48 65 61 64 2c 20 2a 70 54 61 69  ry *pHead, *pTai
3130: 6c 3b 0a 20 20 20 20 20 20 72 6f 77 53 65 74 54  l;.      rowSetT
3140: 72 65 65 54 6f 4c 69 73 74 28 70 54 72 65 65 2c  reeToList(pTree,
3150: 20 26 70 48 65 61 64 2c 20 26 70 54 61 69 6c 29   &pHead, &pTail)
3160: 3b 0a 20 20 20 20 20 20 70 2d 3e 70 45 6e 74 72  ;.      p->pEntr
3170: 79 20 3d 20 72 6f 77 53 65 74 45 6e 74 72 79 4d  y = rowSetEntryM
3180: 65 72 67 65 28 70 2d 3e 70 45 6e 74 72 79 2c 20  erge(p->pEntry, 
3190: 70 48 65 61 64 29 3b 0a 20 20 20 20 7d 0a 20 20  pHead);.    }.  
31a0: 20 20 70 2d 3e 70 46 6f 72 65 73 74 20 3d 20 70    p->pForest = p
31b0: 2d 3e 70 46 6f 72 65 73 74 2d 3e 70 52 69 67 68  ->pForest->pRigh
31c0: 74 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 0a 20 20  t;.  }.#endif.  
31d0: 70 2d 3e 72 73 46 6c 61 67 73 20 7c 3d 20 52 4f  p->rsFlags |= RO
31e0: 57 53 45 54 5f 4e 45 58 54 3b 20 20 2f 2a 20 56  WSET_NEXT;  /* V
31f0: 65 72 69 66 79 20 74 68 69 73 20 72 6f 75 74 69  erify this routi
3200: 6e 65 20 69 73 20 6e 65 76 65 72 20 63 61 6c 6c  ne is never call
3210: 65 64 20 61 67 61 69 6e 20 2a 2f 0a 7d 0a 0a 2f  ed again */.}../
3220: 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20 74 68 65  *.** Extract the
3230: 20 73 6d 61 6c 6c 65 73 74 20 65 6c 65 6d 65 6e   smallest elemen
3240: 74 20 66 72 6f 6d 20 74 68 65 20 52 6f 77 53 65  t from the RowSe
3250: 74 2e 0a 2a 2a 20 57 72 69 74 65 20 74 68 65 20  t..** Write the 
3260: 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 2a 70 52  element into *pR
3270: 6f 77 69 64 2e 20 20 52 65 74 75 72 6e 20 31 20  owid.  Return 1 
3280: 6f 6e 20 73 75 63 63 65 73 73 2e 20 20 52 65 74  on success.  Ret
3290: 75 72 6e 0a 2a 2a 20 30 20 69 66 20 74 68 65 20  urn.** 0 if the 
32a0: 52 6f 77 53 65 74 20 69 73 20 61 6c 72 65 61 64  RowSet is alread
32b0: 79 20 65 6d 70 74 79 2e 0a 2a 2a 0a 2a 2a 20 41  y empty..**.** A
32c0: 66 74 65 72 20 74 68 69 73 20 72 6f 75 74 69 6e  fter this routin
32d0: 65 20 68 61 73 20 62 65 65 6e 20 63 61 6c 6c 65  e has been calle
32e0: 64 2c 20 74 68 65 20 73 71 6c 69 74 65 33 52 6f  d, the sqlite3Ro
32f0: 77 53 65 74 49 6e 73 65 72 74 28 29 0a 2a 2a 20  wSetInsert().** 
3300: 72 6f 75 74 69 6e 65 20 6d 61 79 20 6e 6f 74 20  routine may not 
3310: 62 65 20 63 61 6c 6c 65 64 20 61 67 61 69 6e 2e  be called again.
3320: 20 20 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65    .*/.int sqlite
3330: 33 52 6f 77 53 65 74 4e 65 78 74 28 52 6f 77 53  3RowSetNext(RowS
3340: 65 74 20 2a 70 2c 20 69 36 34 20 2a 70 52 6f 77  et *p, i64 *pRow
3350: 69 64 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70  id){.  assert( p
3360: 21 3d 30 20 29 3b 0a 0a 20 20 2f 2a 20 4d 65 72  !=0 );..  /* Mer
3370: 67 65 20 74 68 65 20 66 6f 72 65 73 74 20 69 6e  ge the forest in
3380: 74 6f 20 61 20 73 69 6e 67 6c 65 20 73 6f 72 74  to a single sort
3390: 65 64 20 6c 69 73 74 20 6f 6e 20 66 69 72 73 74  ed list on first
33a0: 20 63 61 6c 6c 20 2a 2f 0a 20 20 69 66 28 20 28   call */.  if( (
33b0: 70 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57  p->rsFlags & ROW
33c0: 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 20 72  SET_NEXT)==0 ) r
33d0: 6f 77 53 65 74 54 6f 4c 69 73 74 28 70 29 3b 0a  owSetToList(p);.
33e0: 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65  .  /* Return the
33f0: 20 6e 65 78 74 20 65 6e 74 72 79 20 6f 6e 20 74   next entry on t
3400: 68 65 20 6c 69 73 74 20 2a 2f 0a 20 20 69 66 28  he list */.  if(
3410: 20 70 2d 3e 70 45 6e 74 72 79 20 29 7b 0a 20 20   p->pEntry ){.  
3420: 20 20 2a 70 52 6f 77 69 64 20 3d 20 70 2d 3e 70    *pRowid = p->p
3430: 45 6e 74 72 79 2d 3e 76 3b 0a 20 20 20 20 70 2d  Entry->v;.    p-
3440: 3e 70 45 6e 74 72 79 20 3d 20 70 2d 3e 70 45 6e  >pEntry = p->pEn
3450: 74 72 79 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  try->pRight;.   
3460: 20 69 66 28 20 70 2d 3e 70 45 6e 74 72 79 3d 3d   if( p->pEntry==
3470: 30 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74  0 ){.      sqlit
3480: 65 33 52 6f 77 53 65 74 43 6c 65 61 72 28 70 29  e3RowSetClear(p)
3490: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75  ;.    }.    retu
34a0: 72 6e 20 31 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  rn 1;.  }else{. 
34b0: 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d     return 0;.  }
34c0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65 63 6b 20  .}../*.** Check 
34d0: 74 6f 20 73 65 65 20 69 66 20 65 6c 65 6d 65 6e  to see if elemen
34e0: 74 20 69 52 6f 77 69 64 20 77 61 73 20 69 6e 73  t iRowid was ins
34f0: 65 72 74 65 64 20 69 6e 74 6f 20 74 68 65 20 72  erted into the r
3500: 6f 77 73 65 74 20 61 73 0a 2a 2a 20 70 61 72 74  owset as.** part
3510: 20 6f 66 20 61 6e 79 20 69 6e 73 65 72 74 20 62   of any insert b
3520: 61 74 63 68 20 70 72 69 6f 72 20 74 6f 20 69 42  atch prior to iB
3530: 61 74 63 68 2e 20 20 52 65 74 75 72 6e 20 31 20  atch.  Return 1 
3540: 6f 72 20 30 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74  or 0..**.** If t
3550: 68 69 73 20 69 73 20 74 68 65 20 66 69 72 73 74  his is the first
3560: 20 74 65 73 74 20 6f 66 20 61 20 6e 65 77 20 62   test of a new b
3570: 61 74 63 68 20 61 6e 64 20 69 66 20 74 68 65 72  atch and if ther
3580: 65 20 65 78 69 73 74 20 65 6e 74 72 69 65 73 0a  e exist entries.
3590: 2a 2a 20 6f 6e 20 70 52 6f 77 53 65 74 2d 3e 70  ** on pRowSet->p
35a0: 45 6e 74 72 79 2c 20 74 68 65 6e 20 73 6f 72 74  Entry, then sort
35b0: 20 74 68 6f 73 65 20 65 6e 74 72 69 65 73 20 69   those entries i
35c0: 6e 74 6f 20 74 68 65 20 66 6f 72 65 73 74 20 61  nto the forest a
35d0: 74 0a 2a 2a 20 70 52 6f 77 53 65 74 2d 3e 70 46  t.** pRowSet->pF
35e0: 6f 72 65 73 74 20 73 6f 20 74 68 61 74 20 74 68  orest so that th
35f0: 65 79 20 63 61 6e 20 62 65 20 74 65 73 74 65 64  ey can be tested
3600: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
3610: 52 6f 77 53 65 74 54 65 73 74 28 52 6f 77 53 65  RowSetTest(RowSe
3620: 74 20 2a 70 52 6f 77 53 65 74 2c 20 69 6e 74 20  t *pRowSet, int 
3630: 69 42 61 74 63 68 2c 20 73 71 6c 69 74 65 33 5f  iBatch, sqlite3_
3640: 69 6e 74 36 34 20 69 52 6f 77 69 64 29 7b 0a 20  int64 iRowid){. 
3650: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
3660: 74 72 79 20 2a 70 2c 20 2a 70 54 72 65 65 3b 0a  try *p, *pTree;.
3670: 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f 75 74 69  .  /* This routi
3680: 6e 65 20 69 73 20 6e 65 76 65 72 20 63 61 6c 6c  ne is never call
3690: 65 64 20 61 66 74 65 72 20 73 71 6c 69 74 65 33  ed after sqlite3
36a0: 52 6f 77 53 65 74 4e 65 78 74 28 29 20 2a 2f 0a  RowSetNext() */.
36b0: 20 20 61 73 73 65 72 74 28 20 70 52 6f 77 53 65    assert( pRowSe
36c0: 74 21 3d 30 20 26 26 20 28 70 52 6f 77 53 65 74  t!=0 && (pRowSet
36d0: 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53  ->rsFlags & ROWS
36e0: 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b 0a 0a  ET_NEXT)==0 );..
36f0: 20 20 2f 2a 20 53 6f 72 74 20 65 6e 74 72 69 65    /* Sort entrie
3700: 73 20 69 6e 74 6f 20 74 68 65 20 66 6f 72 65 73  s into the fores
3710: 74 20 6f 6e 20 74 68 65 20 66 69 72 73 74 20 74  t on the first t
3720: 65 73 74 20 6f 66 20 61 20 6e 65 77 20 62 61 74  est of a new bat
3730: 63 68 20 0a 20 20 2a 2f 0a 20 20 69 66 28 20 69  ch .  */.  if( i
3740: 42 61 74 63 68 21 3d 70 52 6f 77 53 65 74 2d 3e  Batch!=pRowSet->
3750: 69 42 61 74 63 68 20 29 7b 0a 20 20 20 20 70 20  iBatch ){.    p 
3760: 3d 20 70 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72  = pRowSet->pEntr
3770: 79 3b 0a 20 20 20 20 69 66 28 20 70 20 29 7b 0a  y;.    if( p ){.
3780: 20 20 20 20 20 20 73 74 72 75 63 74 20 52 6f 77        struct Row
3790: 53 65 74 45 6e 74 72 79 20 2a 2a 70 70 50 72 65  SetEntry **ppPre
37a0: 76 54 72 65 65 20 3d 20 26 70 52 6f 77 53 65 74  vTree = &pRowSet
37b0: 2d 3e 70 46 6f 72 65 73 74 3b 0a 20 20 20 20 20  ->pForest;.     
37c0: 20 69 66 28 20 28 70 52 6f 77 53 65 74 2d 3e 72   if( (pRowSet->r
37d0: 73 46 6c 61 67 73 20 26 20 52 4f 57 53 45 54 5f  sFlags & ROWSET_
37e0: 53 4f 52 54 45 44 29 3d 3d 30 20 29 7b 0a 20 20  SORTED)==0 ){.  
37f0: 20 20 20 20 20 20 70 20 3d 20 72 6f 77 53 65 74        p = rowSet
3800: 45 6e 74 72 79 53 6f 72 74 28 70 29 3b 0a 20 20  EntrySort(p);.  
3810: 20 20 20 20 7d 0a 20 20 20 20 20 20 66 6f 72 28      }.      for(
3820: 70 54 72 65 65 20 3d 20 70 52 6f 77 53 65 74 2d  pTree = pRowSet-
3830: 3e 70 46 6f 72 65 73 74 3b 20 70 54 72 65 65 3b  >pForest; pTree;
3840: 20 70 54 72 65 65 3d 70 54 72 65 65 2d 3e 70 52   pTree=pTree->pR
3850: 69 67 68 74 29 7b 0a 20 20 20 20 20 20 20 20 70  ight){.        p
3860: 70 50 72 65 76 54 72 65 65 20 3d 20 26 70 54 72  pPrevTree = &pTr
3870: 65 65 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20  ee->pRight;.    
3880: 20 20 20 20 69 66 28 20 70 54 72 65 65 2d 3e 70      if( pTree->p
3890: 4c 65 66 74 3d 3d 30 20 29 7b 0a 20 20 20 20 20  Left==0 ){.     
38a0: 20 20 20 20 20 70 54 72 65 65 2d 3e 70 4c 65 66       pTree->pLef
38b0: 74 20 3d 20 72 6f 77 53 65 74 4c 69 73 74 54 6f  t = rowSetListTo
38c0: 54 72 65 65 28 70 29 3b 0a 20 20 20 20 20 20 20  Tree(p);.       
38d0: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
38e0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20    }else{.       
38f0: 20 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74     struct RowSet
3900: 45 6e 74 72 79 20 2a 70 41 75 78 2c 20 2a 70 54  Entry *pAux, *pT
3910: 61 69 6c 3b 0a 20 20 20 20 20 20 20 20 20 20 72  ail;.          r
3920: 6f 77 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28  owSetTreeToList(
3930: 70 54 72 65 65 2d 3e 70 4c 65 66 74 2c 20 26 70  pTree->pLeft, &p
3940: 41 75 78 2c 20 26 70 54 61 69 6c 29 3b 0a 20 20  Aux, &pTail);.  
3950: 20 20 20 20 20 20 20 20 70 54 72 65 65 2d 3e 70          pTree->p
3960: 4c 65 66 74 20 3d 20 30 3b 0a 20 20 20 20 20 20  Left = 0;.      
3970: 20 20 20 20 70 20 3d 20 72 6f 77 53 65 74 45 6e      p = rowSetEn
3980: 74 72 79 4d 65 72 67 65 28 70 41 75 78 2c 20 70  tryMerge(pAux, p
3990: 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  );.        }.   
39a0: 20 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 70     }.      if( p
39b0: 54 72 65 65 3d 3d 30 20 29 7b 0a 20 20 20 20 20  Tree==0 ){.     
39c0: 20 20 20 2a 70 70 50 72 65 76 54 72 65 65 20 3d     *ppPrevTree =
39d0: 20 70 54 72 65 65 20 3d 20 72 6f 77 53 65 74 45   pTree = rowSetE
39e0: 6e 74 72 79 41 6c 6c 6f 63 28 70 52 6f 77 53 65  ntryAlloc(pRowSe
39f0: 74 29 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20  t);.        if( 
3a00: 70 54 72 65 65 20 29 7b 0a 20 20 20 20 20 20 20  pTree ){.       
3a10: 20 20 20 70 54 72 65 65 2d 3e 76 20 3d 20 30 3b     pTree->v = 0;
3a20: 0a 20 20 20 20 20 20 20 20 20 20 70 54 72 65 65  .          pTree
3a30: 2d 3e 70 52 69 67 68 74 20 3d 20 30 3b 0a 20 20  ->pRight = 0;.  
3a40: 20 20 20 20 20 20 20 20 70 54 72 65 65 2d 3e 70          pTree->p
3a50: 4c 65 66 74 20 3d 20 72 6f 77 53 65 74 4c 69 73  Left = rowSetLis
3a60: 74 54 6f 54 72 65 65 28 70 29 3b 0a 20 20 20 20  tToTree(p);.    
3a70: 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20      }.      }.  
3a80: 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 70 45 6e      pRowSet->pEn
3a90: 74 72 79 20 3d 20 30 3b 0a 20 20 20 20 20 20 70  try = 0;.      p
3aa0: 52 6f 77 53 65 74 2d 3e 70 4c 61 73 74 20 3d 20  RowSet->pLast = 
3ab0: 30 3b 0a 20 20 20 20 20 20 70 52 6f 77 53 65 74  0;.      pRowSet
3ac0: 2d 3e 72 73 46 6c 61 67 73 20 7c 3d 20 52 4f 57  ->rsFlags |= ROW
3ad0: 53 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20 20 20  SET_SORTED;.    
3ae0: 7d 0a 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 69  }.    pRowSet->i
3af0: 42 61 74 63 68 20 3d 20 69 42 61 74 63 68 3b 0a  Batch = iBatch;.
3b00: 20 20 7d 0a 0a 20 20 2f 2a 20 54 65 73 74 20 74    }..  /* Test t
3b10: 6f 20 73 65 65 20 69 66 20 74 68 65 20 69 52 6f  o see if the iRo
3b20: 77 69 64 20 76 61 6c 75 65 20 61 70 70 65 61 72  wid value appear
3b30: 73 20 61 6e 79 77 68 65 72 65 20 69 6e 20 74 68  s anywhere in th
3b40: 65 20 66 6f 72 65 73 74 2e 0a 20 20 2a 2a 20 52  e forest..  ** R
3b50: 65 74 75 72 6e 20 31 20 69 66 20 69 74 20 64 6f  eturn 1 if it do
3b60: 65 73 20 61 6e 64 20 30 20 69 66 20 6e 6f 74 2e  es and 0 if not.
3b70: 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 70 54 72 65  .  */.  for(pTre
3b80: 65 20 3d 20 70 52 6f 77 53 65 74 2d 3e 70 46 6f  e = pRowSet->pFo
3b90: 72 65 73 74 3b 20 70 54 72 65 65 3b 20 70 54 72  rest; pTree; pTr
3ba0: 65 65 3d 70 54 72 65 65 2d 3e 70 52 69 67 68 74  ee=pTree->pRight
3bb0: 29 7b 0a 20 20 20 20 70 20 3d 20 70 54 72 65 65  ){.    p = pTree
3bc0: 2d 3e 70 4c 65 66 74 3b 0a 20 20 20 20 77 68 69  ->pLeft;.    whi
3bd0: 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 20 20 69  le( p ){.      i
3be0: 66 28 20 70 2d 3e 76 3c 69 52 6f 77 69 64 20 29  f( p->v<iRowid )
3bf0: 7b 0a 20 20 20 20 20 20 20 20 70 20 3d 20 70 2d  {.        p = p-
3c00: 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 20 20 7d  >pRight;.      }
3c10: 65 6c 73 65 20 69 66 28 20 70 2d 3e 76 3e 69 52  else if( p->v>iR
3c20: 6f 77 69 64 20 29 7b 0a 20 20 20 20 20 20 20 20  owid ){.        
3c30: 70 20 3d 20 70 2d 3e 70 4c 65 66 74 3b 0a 20 20  p = p->pLeft;.  
3c40: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
3c50: 20 20 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 20     return 1;.   
3c60: 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 20     }.    }.  }. 
3c70: 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a            return 0;.}.