/ Hex Artifact Content
Login

Artifact f6a49f3e9579428024662f6e2931832511f831a1:


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: 20 6e 65 77 20 6d 65 6d 6f 72 79 0a 2a 2a 20 68   new memory.** h
0840: 61 73 20 74 6f 20 62 65 20 61 6c 6c 6f 63 61 74  as to be allocat
0850: 65 64 20 6f 6e 20 61 6e 20 49 4e 53 45 52 54 2e  ed on an INSERT.
0860: 29 20 20 54 68 65 20 63 6f 73 74 20 6f 66 20 61  )  The cost of a
0870: 20 54 45 53 54 20 77 69 74 68 20 61 20 6e 65 77   TEST with a new
0880: 0a 2a 2a 20 62 61 74 63 68 20 6e 75 6d 62 65 72  .** batch number
0890: 20 69 73 20 4f 28 4e 6c 6f 67 4e 29 20 77 68 65   is O(NlogN) whe
08a0: 72 65 20 4e 20 69 73 20 74 68 65 20 6e 75 6d 62  re N is the numb
08b0: 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69  er of elements i
08c0: 6e 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a 2a  n the RowSet..**
08d0: 20 54 68 65 20 63 6f 73 74 20 6f 66 20 61 20 54   The cost of a T
08e0: 45 53 54 20 75 73 69 6e 67 20 74 68 65 20 73 61  EST using the sa
08f0: 6d 65 20 62 61 74 63 68 20 6e 75 6d 62 65 72 20  me batch number 
0900: 69 73 20 4f 28 6c 6f 67 4e 29 2e 20 20 54 68 65  is O(logN).  The
0910: 20 63 6f 73 74 0a 2a 2a 20 6f 66 20 74 68 65 20   cost.** of the 
0920: 66 69 72 73 74 20 53 4d 41 4c 4c 45 53 54 20 69  first SMALLEST i
0930: 73 20 4f 28 4e 6c 6f 67 4e 29 2e 20 20 53 65 63  s O(NlogN).  Sec
0940: 6f 6e 64 20 61 6e 64 20 73 75 62 73 65 71 75 65  ond and subseque
0950: 6e 74 20 53 4d 41 4c 4c 45 53 54 0a 2a 2a 20 70  nt SMALLEST.** p
0960: 72 69 6d 69 74 69 76 65 73 20 61 72 65 20 63 6f  rimitives are co
0970: 6e 73 74 61 6e 74 20 74 69 6d 65 2e 20 20 54 68  nstant time.  Th
0980: 65 20 63 6f 73 74 20 6f 66 20 44 45 53 54 52 4f  e cost of DESTRO
0990: 59 20 69 73 20 4f 28 4e 29 2e 0a 2a 2a 0a 2a 2a  Y is O(N)..**.**
09a0: 20 54 68 65 72 65 20 69 73 20 61 6e 20 61 64 64   There is an add
09b0: 65 64 20 63 6f 73 74 20 6f 66 20 4f 28 4e 29 20  ed cost of O(N) 
09c0: 77 68 65 6e 20 73 77 69 74 63 68 69 6e 67 20 62  when switching b
09d0: 65 74 77 65 65 6e 20 54 45 53 54 20 61 6e 64 0a  etween TEST and.
09e0: 2a 2a 20 53 4d 41 4c 4c 45 53 54 20 70 72 69 6d  ** SMALLEST prim
09f0: 69 74 69 76 65 73 2e 0a 2a 2f 0a 23 69 6e 63 6c  itives..*/.#incl
0a00: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
0a10: 22 0a 0a 0a 2f 2a 0a 2a 2a 20 54 61 72 67 65 74  ".../*.** Target
0a20: 20 73 69 7a 65 20 66 6f 72 20 61 6c 6c 6f 63 61   size for alloca
0a30: 74 69 6f 6e 20 63 68 75 6e 6b 73 2e 0a 2a 2f 0a  tion chunks..*/.
0a40: 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f 41  #define ROWSET_A
0a50: 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49 5a 45 20 31  LLOCATION_SIZE 1
0a60: 30 32 34 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 6e  024../*.** The n
0a70: 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 65 74 20  umber of rowset 
0a80: 65 6e 74 72 69 65 73 20 70 65 72 20 61 6c 6c 6f  entries per allo
0a90: 63 61 74 69 6f 6e 20 63 68 75 6e 6b 2e 0a 2a 2f  cation chunk..*/
0aa0: 0a 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f  .#define ROWSET_
0ab0: 45 4e 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b 20  ENTRY_PER_CHUNK 
0ac0: 20 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   \.             
0ad0: 20 20 20 20 20 20 20 20 20 20 28 28 52 4f 57 53            ((ROWS
0ae0: 45 54 5f 41 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49  ET_ALLOCATION_SI
0af0: 5a 45 2d 38 29 2f 73 69 7a 65 6f 66 28 73 74 72  ZE-8)/sizeof(str
0b00: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 29  uct RowSetEntry)
0b10: 29 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 65 6e  )../*.** Each en
0b20: 74 72 79 20 69 6e 20 61 20 52 6f 77 53 65 74 20  try in a RowSet 
0b30: 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f  is an instance o
0b40: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
0b50: 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 54 68  object..**.** Th
0b60: 69 73 20 73 61 6d 65 20 6f 62 6a 65 63 74 20 69  is same object i
0b70: 73 20 72 65 75 73 65 64 20 74 6f 20 73 74 6f 72  s reused to stor
0b80: 65 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  e a linked list 
0b90: 6f 66 20 74 72 65 65 73 20 6f 66 20 52 6f 77 53  of trees of RowS
0ba0: 65 74 45 6e 74 72 79 0a 2a 2a 20 6f 62 6a 65 63  etEntry.** objec
0bb0: 74 73 2e 20 20 49 6e 20 74 68 61 74 20 61 6c 74  ts.  In that alt
0bc0: 65 72 6e 61 74 69 76 65 20 75 73 65 2c 20 70 52  ernative use, pR
0bd0: 69 67 68 74 20 70 6f 69 6e 74 73 20 74 6f 20 74  ight points to t
0be0: 68 65 20 6e 65 78 74 20 65 6e 74 72 79 0a 2a 2a  he next entry.**
0bf0: 20 69 6e 20 74 68 65 20 6c 69 73 74 2c 20 70 4c   in the list, pL
0c00: 65 66 74 20 70 6f 69 6e 74 73 20 74 6f 20 74 68  eft points to th
0c10: 65 20 74 72 65 65 2c 20 61 6e 64 20 76 20 69 73  e tree, and v is
0c20: 20 75 6e 75 73 65 64 2e 20 20 54 68 65 0a 2a 2a   unused.  The.**
0c30: 20 52 6f 77 53 65 74 2e 70 46 6f 72 65 73 74 20   RowSet.pForest 
0c40: 76 61 6c 75 65 20 70 6f 69 6e 74 73 20 74 6f 20  value points to 
0c50: 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 69 73  the head of this
0c60: 20 66 6f 72 65 73 74 20 6c 69 73 74 2e 0a 2a 2f   forest list..*/
0c70: 0a 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e  .struct RowSetEn
0c80: 74 72 79 20 7b 20 20 20 20 20 20 20 20 20 20 20  try {           
0c90: 20 0a 20 20 69 36 34 20 76 3b 20 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 2f 2a 20 52 4f 57 49 44 20 76 61 6c 75 65    /* ROWID value
0cc0: 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20   for this entry 
0cd0: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
0ce0: 65 74 45 6e 74 72 79 20 2a 70 52 69 67 68 74 3b  etEntry *pRight;
0cf0: 20 20 20 2f 2a 20 52 69 67 68 74 20 73 75 62 74     /* Right subt
0d00: 72 65 65 20 28 6c 61 72 67 65 72 20 65 6e 74 72  ree (larger entr
0d10: 69 65 73 29 20 6f 72 20 6c 69 73 74 20 2a 2f 0a  ies) or list */.
0d20: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
0d30: 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20 20 20 20  ntry *pLeft;    
0d40: 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65 65 20  /* Left subtree 
0d50: 28 73 6d 61 6c 6c 65 72 20 65 6e 74 72 69 65 73  (smaller entries
0d60: 29 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52  ) */.};../*.** R
0d70: 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65 63  owSetEntry objec
0d80: 74 73 20 61 72 65 20 61 6c 6c 6f 63 61 74 65 64  ts are allocated
0d90: 20 69 6e 20 6c 61 72 67 65 20 63 68 75 6e 6b 73   in large chunks
0da0: 20 28 69 6e 73 74 61 6e 63 65 73 20 6f 66 20 74   (instances of t
0db0: 68 65 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20  he.** following 
0dc0: 73 74 72 75 63 74 75 72 65 29 20 74 6f 20 72 65  structure) to re
0dd0: 64 75 63 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  duce memory allo
0de0: 63 61 74 69 6f 6e 20 6f 76 65 72 68 65 61 64 2e  cation overhead.
0df0: 20 20 54 68 65 0a 2a 2a 20 63 68 75 6e 6b 73 20    The.** chunks 
0e00: 61 72 65 20 6b 65 70 74 20 6f 6e 20 61 20 6c 69  are kept on a li
0e10: 6e 6b 65 64 20 6c 69 73 74 20 73 6f 20 74 68 61  nked list so tha
0e20: 74 20 74 68 65 79 20 63 61 6e 20 62 65 20 64 65  t they can be de
0e30: 61 6c 6c 6f 63 61 74 65 64 0a 2a 2a 20 77 68 65  allocated.** whe
0e40: 6e 20 74 68 65 20 52 6f 77 53 65 74 20 69 73 20  n the RowSet is 
0e50: 64 65 73 74 72 6f 79 65 64 2e 0a 2a 2f 0a 73 74  destroyed..*/.st
0e60: 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b  ruct RowSetChunk
0e70: 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53   {.  struct RowS
0e80: 65 74 43 68 75 6e 6b 20 2a 70 4e 65 78 74 43 68  etChunk *pNextCh
0e90: 75 6e 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e  unk;        /* N
0ea0: 65 78 74 20 63 68 75 6e 6b 20 6f 6e 20 6c 69 73  ext chunk on lis
0eb0: 74 20 6f 66 20 74 68 65 6d 20 61 6c 6c 20 2a 2f  t of them all */
0ec0: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
0ed0: 45 6e 74 72 79 20 61 45 6e 74 72 79 5b 52 4f 57  Entry aEntry[ROW
0ee0: 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f 43 48  SET_ENTRY_PER_CH
0ef0: 55 4e 4b 5d 3b 20 2f 2a 20 41 6c 6c 6f 63 61 74  UNK]; /* Allocat
0f00: 65 64 20 65 6e 74 72 69 65 73 20 2a 2f 0a 7d 3b  ed entries */.};
0f10: 0a 0a 2f 2a 0a 2a 2a 20 41 20 52 6f 77 53 65 74  ../*.** A RowSet
0f20: 20 69 6e 20 61 6e 20 69 6e 73 74 61 6e 63 65 20   in an instance 
0f30: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0f40: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
0f50: 2a 20 41 20 74 79 70 65 64 65 66 20 6f 66 20 74  * A typedef of t
0f60: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69 66  his structure if
0f70: 20 66 6f 75 6e 64 20 69 6e 20 73 71 6c 69 74 65   found in sqlite
0f80: 49 6e 74 2e 68 2e 0a 2a 2f 0a 73 74 72 75 63 74  Int.h..*/.struct
0f90: 20 52 6f 77 53 65 74 20 7b 0a 20 20 73 74 72 75   RowSet {.  stru
0fa0: 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a  ct RowSetChunk *
0fb0: 70 43 68 75 6e 6b 3b 20 20 20 20 2f 2a 20 4c 69  pChunk;    /* Li
0fc0: 73 74 20 6f 66 20 61 6c 6c 20 63 68 75 6e 6b 20  st of all chunk 
0fd0: 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 20  allocations */. 
0fe0: 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20 20 20   sqlite3 *db;   
0ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1000: 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  /* The database 
1010: 63 6f 6e 6e 65 63 74 69 6f 6e 20 2a 2f 0a 20 20  connection */.  
1020: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1030: 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 20 20 2f  ry *pEntry;    /
1040: 2a 20 4c 69 73 74 20 6f 66 20 65 6e 74 72 69 65  * List of entrie
1050: 73 20 75 73 69 6e 67 20 70 52 69 67 68 74 20 2a  s using pRight *
1060: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
1070: 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20 20  tEntry *pLast;  
1080: 20 20 20 2f 2a 20 4c 61 73 74 20 65 6e 74 72 79     /* Last entry
1090: 20 6f 6e 20 74 68 65 20 70 45 6e 74 72 79 20 6c   on the pEntry l
10a0: 69 73 74 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ist */.  struct 
10b0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 46 72  RowSetEntry *pFr
10c0: 65 73 68 3b 20 20 20 20 2f 2a 20 53 6f 75 72 63  esh;    /* Sourc
10d0: 65 20 6f 66 20 6e 65 77 20 65 6e 74 72 79 20 6f  e of new entry o
10e0: 62 6a 65 63 74 73 20 2a 2f 0a 20 20 73 74 72 75  bjects */.  stru
10f0: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
1100: 70 46 6f 72 65 73 74 3b 20 20 20 2f 2a 20 4c 69  pForest;   /* Li
1110: 73 74 20 6f 66 20 62 69 6e 61 72 79 20 74 72 65  st of binary tre
1120: 65 73 20 6f 66 20 65 6e 74 72 69 65 73 20 2a 2f  es of entries */
1130: 0a 20 20 75 31 36 20 6e 46 72 65 73 68 3b 20 20  .  u16 nFresh;  
1140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1150: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f    /* Number of o
1160: 62 6a 65 63 74 73 20 6f 6e 20 70 46 72 65 73 68  bjects on pFresh
1170: 20 2a 2f 0a 20 20 75 38 20 72 73 46 6c 61 67 73   */.  u8 rsFlags
1180: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1190: 20 20 20 20 20 2f 2a 20 56 61 72 69 6f 75 73 20       /* Various 
11a0: 66 6c 61 67 73 20 2a 2f 0a 20 20 75 38 20 69 42  flags */.  u8 iB
11b0: 61 74 63 68 3b 20 20 20 20 20 20 20 20 20 20 20  atch;           
11c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
11d0: 72 65 6e 74 20 69 6e 73 65 72 74 20 62 61 74 63  rent insert batc
11e0: 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41  h */.};../*.** A
11f0: 6c 6c 6f 77 65 64 20 76 61 6c 75 65 73 20 66 6f  llowed values fo
1200: 72 20 52 6f 77 53 65 74 2e 72 73 46 6c 61 67 73  r RowSet.rsFlags
1210: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 57 53  .*/.#define ROWS
1220: 45 54 5f 53 4f 52 54 45 44 20 20 30 78 30 31 20  ET_SORTED  0x01 
1230: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 52 6f 77    /* True if Row
1240: 53 65 74 2e 70 45 6e 74 72 79 20 69 73 20 73 6f  Set.pEntry is so
1250: 72 74 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20  rted */.#define 
1260: 52 4f 57 53 45 54 5f 4e 45 58 54 20 20 20 20 30  ROWSET_NEXT    0
1270: 78 30 32 20 20 20 2f 2a 20 54 72 75 65 20 69 66  x02   /* True if
1280: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65   sqlite3RowSetNe
1290: 78 74 28 29 20 68 61 73 20 62 65 65 6e 20 63 61  xt() has been ca
12a0: 6c 6c 65 64 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54  lled */../*.** T
12b0: 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72 79 20  urn bulk memory 
12c0: 69 6e 74 6f 20 61 20 52 6f 77 53 65 74 20 6f 62  into a RowSet ob
12d0: 6a 65 63 74 2e 20 20 4e 20 62 79 74 65 73 20 6f  ject.  N bytes o
12e0: 66 20 6d 65 6d 6f 72 79 0a 2a 2a 20 61 72 65 20  f memory.** are 
12f0: 61 76 61 69 6c 61 62 6c 65 20 61 74 20 70 53 70  available at pSp
1300: 61 63 65 2e 20 20 54 68 65 20 64 62 20 70 6f 69  ace.  The db poi
1310: 6e 74 65 72 20 69 73 20 75 73 65 64 20 61 73 20  nter is used as 
1320: 61 20 6d 65 6d 6f 72 79 20 63 6f 6e 74 65 78 74  a memory context
1330: 0a 2a 2a 20 66 6f 72 20 61 6e 79 20 73 75 62 73  .** for any subs
1340: 65 71 75 65 6e 74 20 61 6c 6c 6f 63 61 74 69 6f  equent allocatio
1350: 6e 73 20 74 68 61 74 20 6e 65 65 64 20 74 6f 20  ns that need to 
1360: 6f 63 63 75 72 2e 0a 2a 2a 20 52 65 74 75 72 6e  occur..** Return
1370: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
1380: 65 20 6e 65 77 20 52 6f 77 53 65 74 20 6f 62 6a  e new RowSet obj
1390: 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 49 74 20 6d 75  ect..**.** It mu
13a0: 73 74 20 62 65 20 74 68 65 20 63 61 73 65 20 74  st be the case t
13b0: 68 61 74 20 4e 20 69 73 20 73 75 66 66 69 63 69  hat N is suffici
13c0: 65 6e 74 20 74 6f 20 6d 61 6b 65 20 61 20 52 6f  ent to make a Ro
13d0: 77 73 65 74 2e 20 20 49 66 20 6e 6f 74 0a 2a 2a  wset.  If not.**
13e0: 20 61 6e 20 61 73 73 65 72 74 69 6f 6e 20 66 61   an assertion fa
13f0: 75 6c 74 20 6f 63 63 75 72 73 2e 0a 2a 2a 20 0a  ult occurs..** .
1400: 2a 2a 20 49 66 20 4e 20 69 73 20 6c 61 72 67 65  ** If N is large
1410: 72 20 74 68 61 6e 20 74 68 65 20 6d 69 6e 69 6d  r than the minim
1420: 75 6d 2c 20 75 73 65 20 74 68 65 20 73 75 72 70  um, use the surp
1430: 6c 75 73 20 61 73 20 61 6e 20 69 6e 69 74 69 61  lus as an initia
1440: 6c 0a 2a 2a 20 61 6c 6c 6f 63 61 74 69 6f 6e 20  l.** allocation 
1450: 6f 66 20 65 6e 74 72 69 65 73 20 61 76 61 69 6c  of entries avail
1460: 61 62 6c 65 20 74 6f 20 62 65 20 66 69 6c 6c 65  able to be fille
1470: 64 2e 0a 2a 2f 0a 52 6f 77 53 65 74 20 2a 73 71  d..*/.RowSet *sq
1480: 6c 69 74 65 33 52 6f 77 53 65 74 49 6e 69 74 28  lite3RowSetInit(
1490: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 76 6f 69  sqlite3 *db, voi
14a0: 64 20 2a 70 53 70 61 63 65 2c 20 75 6e 73 69 67  d *pSpace, unsig
14b0: 6e 65 64 20 69 6e 74 20 4e 29 7b 0a 20 20 52 6f  ned int N){.  Ro
14c0: 77 53 65 74 20 2a 70 3b 0a 20 20 61 73 73 65 72  wSet *p;.  asser
14d0: 74 28 20 4e 20 3e 3d 20 52 4f 55 4e 44 38 28 73  t( N >= ROUND8(s
14e0: 69 7a 65 6f 66 28 2a 70 29 29 20 29 3b 0a 20 20  izeof(*p)) );.  
14f0: 70 20 3d 20 70 53 70 61 63 65 3b 0a 20 20 70 2d  p = pSpace;.  p-
1500: 3e 70 43 68 75 6e 6b 20 3d 20 30 3b 0a 20 20 70  >pChunk = 0;.  p
1510: 2d 3e 64 62 20 3d 20 64 62 3b 0a 20 20 70 2d 3e  ->db = db;.  p->
1520: 70 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 70 2d  pEntry = 0;.  p-
1530: 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20 20 70 2d  >pLast = 0;.  p-
1540: 3e 70 46 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20  >pForest = 0;.  
1550: 70 2d 3e 70 46 72 65 73 68 20 3d 20 28 73 74 72  p->pFresh = (str
1560: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 2a  uct RowSetEntry*
1570: 29 28 52 4f 55 4e 44 38 28 73 69 7a 65 6f 66 28  )(ROUND8(sizeof(
1580: 2a 70 29 29 20 2b 20 28 63 68 61 72 2a 29 70 29  *p)) + (char*)p)
1590: 3b 0a 20 20 70 2d 3e 6e 46 72 65 73 68 20 3d 20  ;.  p->nFresh = 
15a0: 28 75 31 36 29 28 28 4e 20 2d 20 52 4f 55 4e 44  (u16)((N - ROUND
15b0: 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 29 2f 73  8(sizeof(*p)))/s
15c0: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 52 6f 77  izeof(struct Row
15d0: 53 65 74 45 6e 74 72 79 29 29 3b 0a 20 20 70 2d  SetEntry));.  p-
15e0: 3e 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53 45  >rsFlags = ROWSE
15f0: 54 5f 53 4f 52 54 45 44 3b 0a 20 20 70 2d 3e 69  T_SORTED;.  p->i
1600: 42 61 74 63 68 20 3d 20 30 3b 0a 20 20 72 65 74  Batch = 0;.  ret
1610: 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  urn p;.}../*.** 
1620: 44 65 61 6c 6c 6f 63 61 74 65 20 61 6c 6c 20 63  Deallocate all c
1630: 68 75 6e 6b 73 20 66 72 6f 6d 20 61 20 52 6f 77  hunks from a Row
1640: 53 65 74 2e 20 20 54 68 69 73 20 66 72 65 65 73  Set.  This frees
1650: 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 74 68 61 74   all memory that
1660: 0a 2a 2a 20 74 68 65 20 52 6f 77 53 65 74 20 68  .** the RowSet h
1670: 61 73 20 61 6c 6c 6f 63 61 74 65 64 20 6f 76 65  as allocated ove
1680: 72 20 69 74 73 20 6c 69 66 65 74 69 6d 65 2e 20  r its lifetime. 
1690: 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 69 73   This routine is
16a0: 0a 2a 2a 20 74 68 65 20 64 65 73 74 72 75 63 74  .** the destruct
16b0: 6f 72 20 66 6f 72 20 74 68 65 20 52 6f 77 53 65  or for the RowSe
16c0: 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  t..*/.void sqlit
16d0: 65 33 52 6f 77 53 65 74 43 6c 65 61 72 28 52 6f  e3RowSetClear(Ro
16e0: 77 53 65 74 20 2a 70 29 7b 0a 20 20 73 74 72 75  wSet *p){.  stru
16f0: 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a  ct RowSetChunk *
1700: 70 43 68 75 6e 6b 2c 20 2a 70 4e 65 78 74 43 68  pChunk, *pNextCh
1710: 75 6e 6b 3b 0a 20 20 66 6f 72 28 70 43 68 75 6e  unk;.  for(pChun
1720: 6b 3d 70 2d 3e 70 43 68 75 6e 6b 3b 20 70 43 68  k=p->pChunk; pCh
1730: 75 6e 6b 3b 20 70 43 68 75 6e 6b 20 3d 20 70 4e  unk; pChunk = pN
1740: 65 78 74 43 68 75 6e 6b 29 7b 0a 20 20 20 20 70  extChunk){.    p
1750: 4e 65 78 74 43 68 75 6e 6b 20 3d 20 70 43 68 75  NextChunk = pChu
1760: 6e 6b 2d 3e 70 4e 65 78 74 43 68 75 6e 6b 3b 0a  nk->pNextChunk;.
1770: 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 72 65      sqlite3DbFre
1780: 65 28 70 2d 3e 64 62 2c 20 70 43 68 75 6e 6b 29  e(p->db, pChunk)
1790: 3b 0a 20 20 7d 0a 20 20 70 2d 3e 70 43 68 75 6e  ;.  }.  p->pChun
17a0: 6b 20 3d 20 30 3b 0a 20 20 70 2d 3e 6e 46 72 65  k = 0;.  p->nFre
17b0: 73 68 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 45 6e  sh = 0;.  p->pEn
17c0: 74 72 79 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 4c  try = 0;.  p->pL
17d0: 61 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 46  ast = 0;.  p->pF
17e0: 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e  orest = 0;.  p->
17f0: 72 73 46 6c 61 67 73 20 3d 20 52 4f 57 53 45 54  rsFlags = ROWSET
1800: 5f 53 4f 52 54 45 44 3b 0a 7d 0a 0a 2f 2a 0a 2a  _SORTED;.}../*.*
1810: 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e 65 77  * Allocate a new
1820: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a   RowSetEntry obj
1830: 65 63 74 20 74 68 61 74 20 69 73 20 61 73 73 6f  ect that is asso
1840: 63 69 61 74 65 64 20 77 69 74 68 20 74 68 65 0a  ciated with the.
1850: 2a 2a 20 67 69 76 65 6e 20 52 6f 77 53 65 74 2e  ** given RowSet.
1860: 20 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74    Return a point
1870: 65 72 20 74 6f 20 74 68 65 20 6e 65 77 20 61 6e  er to the new an
1880: 64 20 63 6f 6d 70 6c 65 74 65 6c 79 20 75 6e 69  d completely uni
1890: 6e 69 74 69 61 6c 69 7a 65 64 0a 2a 2a 20 6f 62  nitialized.** ob
18a0: 6a 65 63 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 6e  jected..**.** In
18b0: 20 61 6e 20 4f 4f 4d 20 73 69 74 75 61 74 69 6f   an OOM situatio
18c0: 6e 2c 20 74 68 65 20 52 6f 77 53 65 74 2e 64 62  n, the RowSet.db
18d0: 2d 3e 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 20 66  ->mallocFailed f
18e0: 6c 61 67 20 69 73 20 73 65 74 20 61 6e 64 20 74  lag is set and t
18f0: 68 69 73 0a 2a 2a 20 72 6f 75 74 69 6e 65 20 72  his.** routine r
1900: 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 2a 2f 0a  eturns NULL..*/.
1910: 73 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f  static struct Ro
1920: 77 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65  wSetEntry *rowSe
1930: 74 45 6e 74 72 79 41 6c 6c 6f 63 28 52 6f 77 53  tEntryAlloc(RowS
1940: 65 74 20 2a 70 29 7b 0a 20 20 61 73 73 65 72 74  et *p){.  assert
1950: 28 20 70 21 3d 30 20 29 3b 0a 20 20 69 66 28 20  ( p!=0 );.  if( 
1960: 70 2d 3e 6e 46 72 65 73 68 3d 3d 30 20 29 7b 0a  p->nFresh==0 ){.
1970: 20 20 20 20 73 74 72 75 63 74 20 52 6f 77 53 65      struct RowSe
1980: 74 43 68 75 6e 6b 20 2a 70 4e 65 77 3b 0a 20 20  tChunk *pNew;.  
1990: 20 20 70 4e 65 77 20 3d 20 73 71 6c 69 74 65 33    pNew = sqlite3
19a0: 44 62 4d 61 6c 6c 6f 63 52 61 77 28 70 2d 3e 64  DbMallocRaw(p->d
19b0: 62 2c 20 73 69 7a 65 6f 66 28 2a 70 4e 65 77 29  b, sizeof(*pNew)
19c0: 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77 3d  );.    if( pNew=
19d0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 74 75  =0 ){.      retu
19e0: 72 6e 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20 20  rn 0;.    }.    
19f0: 70 4e 65 77 2d 3e 70 4e 65 78 74 43 68 75 6e 6b  pNew->pNextChunk
1a00: 20 3d 20 70 2d 3e 70 43 68 75 6e 6b 3b 0a 20 20   = p->pChunk;.  
1a10: 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d 20 70 4e    p->pChunk = pN
1a20: 65 77 3b 0a 20 20 20 20 70 2d 3e 70 46 72 65 73  ew;.    p->pFres
1a30: 68 20 3d 20 70 4e 65 77 2d 3e 61 45 6e 74 72 79  h = pNew->aEntry
1a40: 3b 0a 20 20 20 20 70 2d 3e 6e 46 72 65 73 68 20  ;.    p->nFresh 
1a50: 3d 20 52 4f 57 53 45 54 5f 45 4e 54 52 59 5f 50  = ROWSET_ENTRY_P
1a60: 45 52 5f 43 48 55 4e 4b 3b 0a 20 20 7d 0a 20 20  ER_CHUNK;.  }.  
1a70: 70 2d 3e 6e 46 72 65 73 68 2d 2d 3b 0a 20 20 72  p->nFresh--;.  r
1a80: 65 74 75 72 6e 20 70 2d 3e 70 46 72 65 73 68 2b  eturn p->pFresh+
1a90: 2b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 73 65  +;.}../*.** Inse
1aa0: 72 74 20 61 20 6e 65 77 20 76 61 6c 75 65 20 69  rt a new value i
1ab0: 6e 74 6f 20 61 20 52 6f 77 53 65 74 2e 0a 2a 2a  nto a RowSet..**
1ac0: 0a 2a 2a 20 54 68 65 20 6d 61 6c 6c 6f 63 46 61  .** The mallocFa
1ad0: 69 6c 65 64 20 66 6c 61 67 20 6f 66 20 74 68 65  iled flag of the
1ae0: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
1af0: 74 69 6f 6e 20 69 73 20 73 65 74 20 69 66 20 61  tion is set if a
1b00: 0a 2a 2a 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63  .** memory alloc
1b10: 61 74 69 6f 6e 20 66 61 69 6c 73 2e 0a 2a 2f 0a  ation fails..*/.
1b20: 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77 53  void sqlite3RowS
1b30: 65 74 49 6e 73 65 72 74 28 52 6f 77 53 65 74 20  etInsert(RowSet 
1b40: 2a 70 2c 20 69 36 34 20 72 6f 77 69 64 29 7b 0a  *p, i64 rowid){.
1b50: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
1b60: 6e 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 2f  ntry *pEntry;  /
1b70: 2a 20 54 68 65 20 6e 65 77 20 65 6e 74 72 79 20  * The new entry 
1b80: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
1b90: 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20  etEntry *pLast; 
1ba0: 20 20 2f 2a 20 54 68 65 20 6c 61 73 74 20 70 72    /* The last pr
1bb0: 69 6f 72 20 65 6e 74 72 79 20 2a 2f 0a 0a 20 20  ior entry */..  
1bc0: 2f 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20  /* This routine 
1bd0: 69 73 20 6e 65 76 65 72 20 63 61 6c 6c 65 64 20  is never called 
1be0: 61 66 74 65 72 20 73 71 6c 69 74 65 33 52 6f 77  after sqlite3Row
1bf0: 53 65 74 4e 65 78 74 28 29 20 2a 2f 0a 20 20 61  SetNext() */.  a
1c00: 73 73 65 72 74 28 20 70 21 3d 30 20 26 26 20 28  ssert( p!=0 && (
1c10: 70 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57  p->rsFlags & ROW
1c20: 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b 0a  SET_NEXT)==0 );.
1c30: 0a 20 20 70 45 6e 74 72 79 20 3d 20 72 6f 77 53  .  pEntry = rowS
1c40: 65 74 45 6e 74 72 79 41 6c 6c 6f 63 28 70 29 3b  etEntryAlloc(p);
1c50: 0a 20 20 69 66 28 20 70 45 6e 74 72 79 3d 3d 30  .  if( pEntry==0
1c60: 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 70 45 6e   ) return;.  pEn
1c70: 74 72 79 2d 3e 76 20 3d 20 72 6f 77 69 64 3b 0a  try->v = rowid;.
1c80: 20 20 70 45 6e 74 72 79 2d 3e 70 52 69 67 68 74    pEntry->pRight
1c90: 20 3d 20 30 3b 0a 20 20 70 4c 61 73 74 20 3d 20   = 0;.  pLast = 
1ca0: 70 2d 3e 70 4c 61 73 74 3b 0a 20 20 69 66 28 20  p->pLast;.  if( 
1cb0: 70 4c 61 73 74 20 29 7b 0a 20 20 20 20 69 66 28  pLast ){.    if(
1cc0: 20 28 70 2d 3e 72 73 46 6c 61 67 73 20 26 20 52   (p->rsFlags & R
1cd0: 4f 57 53 45 54 5f 53 4f 52 54 45 44 29 21 3d 30  OWSET_SORTED)!=0
1ce0: 20 26 26 20 72 6f 77 69 64 3c 3d 70 4c 61 73 74   && rowid<=pLast
1cf0: 2d 3e 76 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e  ->v ){.      p->
1d00: 72 73 46 6c 61 67 73 20 26 3d 20 7e 52 4f 57 53  rsFlags &= ~ROWS
1d10: 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20 20 20 7d  ET_SORTED;.    }
1d20: 0a 20 20 20 20 70 4c 61 73 74 2d 3e 70 52 69 67  .    pLast->pRig
1d30: 68 74 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20 7d  ht = pEntry;.  }
1d40: 65 6c 73 65 7b 0a 20 20 20 20 70 2d 3e 70 45 6e  else{.    p->pEn
1d50: 74 72 79 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20  try = pEntry;.  
1d60: 7d 0a 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20 70  }.  p->pLast = p
1d70: 45 6e 74 72 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  Entry;.}../*.** 
1d80: 4d 65 72 67 65 20 74 77 6f 20 6c 69 73 74 73 20  Merge two lists 
1d90: 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f  of RowSetEntry o
1da0: 62 6a 65 63 74 73 2e 20 20 52 65 6d 6f 76 65 20  bjects.  Remove 
1db0: 64 75 70 6c 69 63 61 74 65 73 2e 0a 2a 2a 0a 2a  duplicates..**.*
1dc0: 2a 20 54 68 65 20 69 6e 70 75 74 20 6c 69 73 74  * The input list
1dd0: 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 64 20  s are connected 
1de0: 76 69 61 20 70 52 69 67 68 74 20 70 6f 69 6e 74  via pRight point
1df0: 65 72 73 20 61 6e 64 20 61 72 65 20 0a 2a 2a 20  ers and are .** 
1e00: 61 73 73 75 6d 65 64 20 74 6f 20 65 61 63 68 20  assumed to each 
1e10: 61 6c 72 65 61 64 79 20 62 65 20 69 6e 20 73 6f  already be in so
1e20: 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2f 0a 73  rted order..*/.s
1e30: 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77  tatic struct Row
1e40: 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74  SetEntry *rowSet
1e50: 45 6e 74 72 79 4d 65 72 67 65 28 0a 20 20 73 74  EntryMerge(.  st
1e60: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1e70: 20 2a 70 41 2c 20 20 20 20 2f 2a 20 46 69 72 73   *pA,    /* Firs
1e80: 74 20 73 6f 72 74 65 64 20 6c 69 73 74 20 74 6f  t sorted list to
1e90: 20 62 65 20 6d 65 72 67 65 64 20 2a 2f 0a 20 20   be merged */.  
1ea0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1eb0: 72 79 20 2a 70 42 20 20 20 20 20 2f 2a 20 53 65  ry *pB     /* Se
1ec0: 63 6f 6e 64 20 73 6f 72 74 65 64 20 6c 69 73 74  cond sorted list
1ed0: 20 74 6f 20 62 65 20 6d 65 72 67 65 64 20 2a 2f   to be merged */
1ee0: 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  .){.  struct Row
1ef0: 53 65 74 45 6e 74 72 79 20 68 65 61 64 3b 0a 20  SetEntry head;. 
1f00: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
1f10: 74 72 79 20 2a 70 54 61 69 6c 3b 0a 0a 20 20 70  try *pTail;..  p
1f20: 54 61 69 6c 20 3d 20 26 68 65 61 64 3b 0a 20 20  Tail = &head;.  
1f30: 77 68 69 6c 65 28 20 70 41 20 26 26 20 70 42 20  while( pA && pB 
1f40: 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70  ){.    assert( p
1f50: 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c 7c 20  A->pRight==0 || 
1f60: 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69 67 68  pA->v<=pA->pRigh
1f70: 74 2d 3e 76 20 29 3b 0a 20 20 20 20 61 73 73 65  t->v );.    asse
1f80: 72 74 28 20 70 42 2d 3e 70 52 69 67 68 74 3d 3d  rt( pB->pRight==
1f90: 30 20 7c 7c 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e  0 || pB->v<=pB->
1fa0: 70 52 69 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20  pRight->v );.   
1fb0: 20 69 66 28 20 70 41 2d 3e 76 3c 70 42 2d 3e 76   if( pA->v<pB->v
1fc0: 20 29 7b 0a 20 20 20 20 20 20 70 54 61 69 6c 2d   ){.      pTail-
1fd0: 3e 70 52 69 67 68 74 20 3d 20 70 41 3b 0a 20 20  >pRight = pA;.  
1fe0: 20 20 20 20 70 41 20 3d 20 70 41 2d 3e 70 52 69      pA = pA->pRi
1ff0: 67 68 74 3b 0a 20 20 20 20 20 20 70 54 61 69 6c  ght;.      pTail
2000: 20 3d 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74   = pTail->pRight
2010: 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20  ;.    }else if( 
2020: 70 42 2d 3e 76 3c 70 41 2d 3e 76 20 29 7b 0a 20  pB->v<pA->v ){. 
2030: 20 20 20 20 20 70 54 61 69 6c 2d 3e 70 52 69 67       pTail->pRig
2040: 68 74 20 3d 20 70 42 3b 0a 20 20 20 20 20 20 70  ht = pB;.      p
2050: 42 20 3d 20 70 42 2d 3e 70 52 69 67 68 74 3b 0a  B = pB->pRight;.
2060: 20 20 20 20 20 20 70 54 61 69 6c 20 3d 20 70 54        pTail = pT
2070: 61 69 6c 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  ail->pRight;.   
2080: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 70 41   }else{.      pA
2090: 20 3d 20 70 41 2d 3e 70 52 69 67 68 74 3b 0a 20   = pA->pRight;. 
20a0: 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70     }.  }.  if( p
20b0: 41 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  A ){.    assert(
20c0: 20 70 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c   pA->pRight==0 |
20d0: 7c 20 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69  | pA->v<=pA->pRi
20e0: 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70 54  ght->v );.    pT
20f0: 61 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 41  ail->pRight = pA
2100: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61  ;.  }else{.    a
2110: 73 73 65 72 74 28 20 70 42 3d 3d 30 20 7c 7c 20  ssert( pB==0 || 
2120: 70 42 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c 7c  pB->pRight==0 ||
2130: 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e 70 52 69 67   pB->v<=pB->pRig
2140: 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70 54 61  ht->v );.    pTa
2150: 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42 3b  il->pRight = pB;
2160: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 65  .  }.  return he
2170: 61 64 2e 70 52 69 67 68 74 3b 0a 7d 0a 0a 2f 2a  ad.pRight;.}../*
2180: 0a 2a 2a 20 53 6f 72 74 20 61 6c 6c 20 65 6c 65  .** Sort all ele
2190: 6d 65 6e 74 73 20 6f 6e 20 74 68 65 20 6c 69 73  ments on the lis
21a0: 74 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79  t of RowSetEntry
21b0: 20 6f 62 6a 65 63 74 73 20 69 6e 74 6f 20 6f 72   objects into or
21c0: 64 65 72 20 6f 66 0a 2a 2a 20 69 6e 63 72 65 61  der of.** increa
21d0: 73 69 6e 67 20 76 2e 0a 2a 2f 20 0a 73 74 61 74  sing v..*/ .stat
21e0: 69 63 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  ic struct RowSet
21f0: 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 45 6e 74  Entry *rowSetEnt
2200: 72 79 53 6f 72 74 28 73 74 72 75 63 74 20 52 6f  rySort(struct Ro
2210: 77 53 65 74 45 6e 74 72 79 20 2a 70 49 6e 29 7b  wSetEntry *pIn){
2220: 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20  .  unsigned int 
2230: 69 3b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  i;.  struct RowS
2240: 65 74 45 6e 74 72 79 20 2a 70 4e 65 78 74 2c 20  etEntry *pNext, 
2250: 2a 61 42 75 63 6b 65 74 5b 34 30 5d 3b 0a 0a 20  *aBucket[40];.. 
2260: 20 6d 65 6d 73 65 74 28 61 42 75 63 6b 65 74 2c   memset(aBucket,
2270: 20 30 2c 20 73 69 7a 65 6f 66 28 61 42 75 63 6b   0, sizeof(aBuck
2280: 65 74 29 29 3b 0a 20 20 77 68 69 6c 65 28 20 70  et));.  while( p
2290: 49 6e 20 29 7b 0a 20 20 20 20 70 4e 65 78 74 20  In ){.    pNext 
22a0: 3d 20 70 49 6e 2d 3e 70 52 69 67 68 74 3b 0a 20  = pIn->pRight;. 
22b0: 20 20 20 70 49 6e 2d 3e 70 52 69 67 68 74 20 3d     pIn->pRight =
22c0: 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d 30 3b   0;.    for(i=0;
22d0: 20 61 42 75 63 6b 65 74 5b 69 5d 3b 20 69 2b 2b   aBucket[i]; i++
22e0: 29 7b 0a 20 20 20 20 20 20 70 49 6e 20 3d 20 72  ){.      pIn = r
22f0: 6f 77 53 65 74 45 6e 74 72 79 4d 65 72 67 65 28  owSetEntryMerge(
2300: 61 42 75 63 6b 65 74 5b 69 5d 2c 20 70 49 6e 29  aBucket[i], pIn)
2310: 3b 0a 20 20 20 20 20 20 61 42 75 63 6b 65 74 5b  ;.      aBucket[
2320: 69 5d 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20  i] = 0;.    }.  
2330: 20 20 61 42 75 63 6b 65 74 5b 69 5d 20 3d 20 70    aBucket[i] = p
2340: 49 6e 3b 0a 20 20 20 20 70 49 6e 20 3d 20 70 4e  In;.    pIn = pN
2350: 65 78 74 3b 0a 20 20 7d 0a 20 20 70 49 6e 20 3d  ext;.  }.  pIn =
2360: 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69   0;.  for(i=0; i
2370: 3c 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74 29  <sizeof(aBucket)
2380: 2f 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74 5b  /sizeof(aBucket[
2390: 30 5d 29 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 70  0]); i++){.    p
23a0: 49 6e 20 3d 20 72 6f 77 53 65 74 45 6e 74 72 79  In = rowSetEntry
23b0: 4d 65 72 67 65 28 70 49 6e 2c 20 61 42 75 63 6b  Merge(pIn, aBuck
23c0: 65 74 5b 69 5d 29 3b 0a 20 20 7d 0a 20 20 72 65  et[i]);.  }.  re
23d0: 74 75 72 6e 20 70 49 6e 3b 0a 7d 0a 0a 0a 2f 2a  turn pIn;.}.../*
23e0: 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74 2c 20 70  .** The input, p
23f0: 49 6e 2c 20 69 73 20 61 20 62 69 6e 61 72 79 20  In, is a binary 
2400: 74 72 65 65 20 28 6f 72 20 73 75 62 74 72 65 65  tree (or subtree
2410: 29 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79  ) of RowSetEntry
2420: 20 6f 62 6a 65 63 74 73 2e 0a 2a 2a 20 43 6f 6e   objects..** Con
2430: 76 65 72 74 20 74 68 69 73 20 74 72 65 65 20 69  vert this tree i
2440: 6e 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73  nto a linked lis
2450: 74 20 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 74  t connected by t
2460: 68 65 20 70 52 69 67 68 74 20 70 6f 69 6e 74 65  he pRight pointe
2470: 72 73 0a 2a 2a 20 61 6e 64 20 72 65 74 75 72 6e  rs.** and return
2480: 20 70 6f 69 6e 74 65 72 73 20 74 6f 20 74 68 65   pointers to the
2490: 20 66 69 72 73 74 20 61 6e 64 20 6c 61 73 74 20   first and last 
24a0: 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20  elements of the 
24b0: 6e 65 77 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  new list..*/.sta
24c0: 74 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74 54  tic void rowSetT
24d0: 72 65 65 54 6f 4c 69 73 74 28 0a 20 20 73 74 72  reeToList(.  str
24e0: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
24f0: 2a 70 49 6e 2c 20 20 20 20 20 20 20 20 20 2f 2a  *pIn,         /*
2500: 20 52 6f 6f 74 20 6f 66 20 74 68 65 20 69 6e 70   Root of the inp
2510: 75 74 20 74 72 65 65 20 2a 2f 0a 20 20 73 74 72  ut tree */.  str
2520: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2530: 2a 2a 70 70 46 69 72 73 74 2c 20 20 20 20 2f 2a  **ppFirst,    /*
2540: 20 57 72 69 74 65 20 68 65 61 64 20 6f 66 20 74   Write head of t
2550: 68 65 20 6f 75 74 70 75 74 20 6c 69 73 74 20 68  he output list h
2560: 65 72 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ere */.  struct 
2570: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a 70 70  RowSetEntry **pp
2580: 4c 61 73 74 20 20 20 20 20 20 2f 2a 20 57 72 69  Last      /* Wri
2590: 74 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20 6f  te tail of the o
25a0: 75 74 70 75 74 20 6c 69 73 74 20 68 65 72 65 20  utput list here 
25b0: 2a 2f 0a 29 7b 0a 20 20 61 73 73 65 72 74 28 20  */.){.  assert( 
25c0: 70 49 6e 21 3d 30 20 29 3b 0a 20 20 69 66 28 20  pIn!=0 );.  if( 
25d0: 70 49 6e 2d 3e 70 4c 65 66 74 20 29 7b 0a 20 20  pIn->pLeft ){.  
25e0: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
25f0: 6e 74 72 79 20 2a 70 3b 0a 20 20 20 20 72 6f 77  ntry *p;.    row
2600: 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70 49  SetTreeToList(pI
2610: 6e 2d 3e 70 4c 65 66 74 2c 20 70 70 46 69 72 73  n->pLeft, ppFirs
2620: 74 2c 20 26 70 29 3b 0a 20 20 20 20 70 2d 3e 70  t, &p);.    p->p
2630: 52 69 67 68 74 20 3d 20 70 49 6e 3b 0a 20 20 7d  Right = pIn;.  }
2640: 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 46 69 72  else{.    *ppFir
2650: 73 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20  st = pIn;.  }.  
2660: 69 66 28 20 70 49 6e 2d 3e 70 52 69 67 68 74 20  if( pIn->pRight 
2670: 29 7b 0a 20 20 20 20 72 6f 77 53 65 74 54 72 65  ){.    rowSetTre
2680: 65 54 6f 4c 69 73 74 28 70 49 6e 2d 3e 70 52 69  eToList(pIn->pRi
2690: 67 68 74 2c 20 26 70 49 6e 2d 3e 70 52 69 67 68  ght, &pIn->pRigh
26a0: 74 2c 20 70 70 4c 61 73 74 29 3b 0a 20 20 7d 65  t, ppLast);.  }e
26b0: 6c 73 65 7b 0a 20 20 20 20 2a 70 70 4c 61 73 74  lse{.    *ppLast
26c0: 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20 61 73   = pIn;.  }.  as
26d0: 73 65 72 74 28 20 28 2a 70 70 4c 61 73 74 29 2d  sert( (*ppLast)-
26e0: 3e 70 52 69 67 68 74 3d 3d 30 20 29 3b 0a 7d 0a  >pRight==0 );.}.
26f0: 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65 72 74 20  ../*.** Convert 
2700: 61 20 73 6f 72 74 65 64 20 6c 69 73 74 20 6f 66  a sorted list of
2710: 20 65 6c 65 6d 65 6e 74 73 20 28 63 6f 6e 6e 65   elements (conne
2720: 63 74 65 64 20 62 79 20 70 52 69 67 68 74 29 20  cted by pRight) 
2730: 69 6e 74 6f 20 61 20 62 69 6e 61 72 79 0a 2a 2a  into a binary.**
2740: 20 74 72 65 65 20 77 69 74 68 20 64 65 70 74 68   tree with depth
2750: 20 6f 66 20 69 44 65 70 74 68 2e 20 20 41 20 64   of iDepth.  A d
2760: 65 70 74 68 20 6f 66 20 31 20 6d 65 61 6e 73 20  epth of 1 means 
2770: 74 68 65 20 74 72 65 65 20 63 6f 6e 74 61 69 6e  the tree contain
2780: 73 20 61 20 73 69 6e 67 6c 65 0a 2a 2a 20 6e 6f  s a single.** no
2790: 64 65 20 74 61 6b 65 6e 20 66 72 6f 6d 20 74 68  de taken from th
27a0: 65 20 68 65 61 64 20 6f 66 20 2a 70 70 4c 69 73  e head of *ppLis
27b0: 74 2e 20 20 41 20 64 65 70 74 68 20 6f 66 20 32  t.  A depth of 2
27c0: 20 6d 65 61 6e 73 20 61 20 74 72 65 65 20 77 69   means a tree wi
27d0: 74 68 0a 2a 2a 20 74 68 72 65 65 20 6e 6f 64 65  th.** three node
27e0: 73 2e 20 20 41 6e 64 20 73 6f 20 66 6f 72 74 68  s.  And so forth
27f0: 2e 0a 2a 2a 0a 2a 2a 20 55 73 65 20 61 73 20 6d  ..**.** Use as m
2800: 61 6e 79 20 65 6e 74 72 69 65 73 20 66 72 6f 6d  any entries from
2810: 20 74 68 65 20 69 6e 70 75 74 20 6c 69 73 74 20   the input list 
2820: 61 73 20 72 65 71 75 69 72 65 64 20 61 6e 64 20  as required and 
2830: 75 70 64 61 74 65 20 74 68 65 0a 2a 2a 20 2a 70  update the.** *p
2840: 70 4c 69 73 74 20 74 6f 20 70 6f 69 6e 74 20 74  pList to point t
2850: 6f 20 74 68 65 20 75 6e 75 73 65 64 20 65 6c 65  o the unused ele
2860: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 6c 69 73  ments of the lis
2870: 74 2e 20 20 49 66 20 74 68 65 20 69 6e 70 75 74  t.  If the input
2880: 0a 2a 2a 20 6c 69 73 74 20 63 6f 6e 74 61 69 6e  .** list contain
2890: 73 20 74 6f 6f 20 66 65 77 20 65 6c 65 6d 65 6e  s too few elemen
28a0: 74 73 2c 20 74 68 65 6e 20 63 6f 6e 73 74 72 75  ts, then constru
28b0: 63 74 20 61 6e 20 69 6e 63 6f 6d 70 6c 65 74 65  ct an incomplete
28c0: 20 74 72 65 65 0a 2a 2a 20 61 6e 64 20 6c 65 61   tree.** and lea
28d0: 76 65 20 2a 70 70 4c 69 73 74 20 73 65 74 20 74  ve *ppList set t
28e0: 6f 20 4e 55 4c 4c 2e 0a 2a 2a 0a 2a 2a 20 52 65  o NULL..**.** Re
28f0: 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  turn a pointer t
2900: 6f 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68  o the root of th
2910: 65 20 63 6f 6e 73 74 72 75 63 74 65 64 20 62 69  e constructed bi
2920: 6e 61 72 79 20 74 72 65 65 2e 0a 2a 2f 0a 73 74  nary tree..*/.st
2930: 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53  atic struct RowS
2940: 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 4e  etEntry *rowSetN
2950: 44 65 65 70 54 72 65 65 28 0a 20 20 73 74 72 75  DeepTree(.  stru
2960: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2970: 2a 70 70 4c 69 73 74 2c 0a 20 20 69 6e 74 20 69  *ppList,.  int i
2980: 44 65 70 74 68 0a 29 7b 0a 20 20 73 74 72 75 63  Depth.){.  struc
2990: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70  t RowSetEntry *p
29a0: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f  ;         /* Roo
29b0: 74 20 6f 66 20 74 68 65 20 6e 65 77 20 74 72 65  t of the new tre
29c0: 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f  e */.  struct Ro
29d0: 77 53 65 74 45 6e 74 72 79 20 2a 70 4c 65 66 74  wSetEntry *pLeft
29e0: 3b 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73 75  ;     /* Left su
29f0: 62 74 72 65 65 20 2a 2f 0a 20 20 69 66 28 20 2a  btree */.  if( *
2a00: 70 70 4c 69 73 74 3d 3d 30 20 29 7b 0a 20 20 20  ppList==0 ){.   
2a10: 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a 20   return 0;.  }. 
2a20: 20 69 66 28 20 69 44 65 70 74 68 3d 3d 31 20 29   if( iDepth==1 )
2a30: 7b 0a 20 20 20 20 70 20 3d 20 2a 70 70 4c 69 73  {.    p = *ppLis
2a40: 74 3b 0a 20 20 20 20 2a 70 70 4c 69 73 74 20 3d  t;.    *ppList =
2a50: 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20   p->pRight;.    
2a60: 70 2d 3e 70 4c 65 66 74 20 3d 20 70 2d 3e 70 52  p->pLeft = p->pR
2a70: 69 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 72 65  ight = 0;.    re
2a80: 74 75 72 6e 20 70 3b 0a 20 20 7d 0a 20 20 70 4c  turn p;.  }.  pL
2a90: 65 66 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65  eft = rowSetNDee
2aa0: 70 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44  pTree(ppList, iD
2ab0: 65 70 74 68 2d 31 29 3b 0a 20 20 70 20 3d 20 2a  epth-1);.  p = *
2ac0: 70 70 4c 69 73 74 3b 0a 20 20 69 66 28 20 70 3d  ppList;.  if( p=
2ad0: 3d 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e  =0 ){.    return
2ae0: 20 70 4c 65 66 74 3b 0a 20 20 7d 0a 20 20 70 2d   pLeft;.  }.  p-
2af0: 3e 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b 0a  >pLeft = pLeft;.
2b00: 20 20 2a 70 70 4c 69 73 74 20 3d 20 70 2d 3e 70    *ppList = p->p
2b10: 52 69 67 68 74 3b 0a 20 20 70 2d 3e 70 52 69 67  Right;.  p->pRig
2b20: 68 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65 70  ht = rowSetNDeep
2b30: 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44 65  Tree(ppList, iDe
2b40: 70 74 68 2d 31 29 3b 0a 20 20 72 65 74 75 72 6e  pth-1);.  return
2b50: 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e   p;.}../*.** Con
2b60: 76 65 72 74 20 61 20 73 6f 72 74 65 64 20 6c 69  vert a sorted li
2b70: 73 74 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69  st of elements i
2b80: 6e 74 6f 20 61 20 62 69 6e 61 72 79 20 74 72 65  nto a binary tre
2b90: 65 2e 20 4d 61 6b 65 20 74 68 65 20 74 72 65 65  e. Make the tree
2ba0: 0a 2a 2a 20 61 73 20 64 65 65 70 20 61 73 20 69  .** as deep as i
2bb0: 74 20 6e 65 65 64 73 20 74 6f 20 62 65 20 69 6e  t needs to be in
2bc0: 20 6f 72 64 65 72 20 74 6f 20 63 6f 6e 74 61 69   order to contai
2bd0: 6e 20 74 68 65 20 65 6e 74 69 72 65 20 6c 69 73  n the entire lis
2be0: 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72  t..*/.static str
2bf0: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2c00: 2a 72 6f 77 53 65 74 4c 69 73 74 54 6f 54 72 65  *rowSetListToTre
2c10: 65 28 73 74 72 75 63 74 20 52 6f 77 53 65 74 45  e(struct RowSetE
2c20: 6e 74 72 79 20 2a 70 4c 69 73 74 29 7b 0a 20 20  ntry *pList){.  
2c30: 69 6e 74 20 69 44 65 70 74 68 3b 20 20 20 20 20  int iDepth;     
2c40: 20 20 20 20 20 20 2f 2a 20 44 65 70 74 68 20 6f        /* Depth o
2c50: 66 20 74 68 65 20 74 72 65 65 20 73 6f 20 66 61  f the tree so fa
2c60: 72 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f  r */.  struct Ro
2c70: 77 53 65 74 45 6e 74 72 79 20 2a 70 3b 20 20 20  wSetEntry *p;   
2c80: 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 74      /* Current t
2c90: 72 65 65 20 72 6f 6f 74 20 2a 2f 0a 20 20 73 74  ree root */.  st
2ca0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2cb0: 20 2a 70 4c 65 66 74 3b 20 20 20 2f 2a 20 4c 65   *pLeft;   /* Le
2cc0: 66 74 20 73 75 62 74 72 65 65 20 2a 2f 0a 0a 20  ft subtree */.. 
2cd0: 20 61 73 73 65 72 74 28 20 70 4c 69 73 74 21 3d   assert( pList!=
2ce0: 30 20 29 3b 0a 20 20 70 20 3d 20 70 4c 69 73 74  0 );.  p = pList
2cf0: 3b 0a 20 20 70 4c 69 73 74 20 3d 20 70 2d 3e 70  ;.  pList = p->p
2d00: 52 69 67 68 74 3b 0a 20 20 70 2d 3e 70 4c 65 66  Right;.  p->pLef
2d10: 74 20 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d 20  t = p->pRight = 
2d20: 30 3b 0a 20 20 66 6f 72 28 69 44 65 70 74 68 3d  0;.  for(iDepth=
2d30: 31 3b 20 70 4c 69 73 74 3b 20 69 44 65 70 74 68  1; pList; iDepth
2d40: 2b 2b 29 7b 0a 20 20 20 20 70 4c 65 66 74 20 3d  ++){.    pLeft =
2d50: 20 70 3b 0a 20 20 20 20 70 20 3d 20 70 4c 69 73   p;.    p = pLis
2d60: 74 3b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20 70  t;.    pList = p
2d70: 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70 2d  ->pRight;.    p-
2d80: 3e 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b 0a  >pLeft = pLeft;.
2d90: 20 20 20 20 70 2d 3e 70 52 69 67 68 74 20 3d 20      p->pRight = 
2da0: 72 6f 77 53 65 74 4e 44 65 65 70 54 72 65 65 28  rowSetNDeepTree(
2db0: 26 70 4c 69 73 74 2c 20 69 44 65 70 74 68 29 3b  &pList, iDepth);
2dc0: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b  .  }.  return p;
2dd0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 61 6b 65 20 61  .}../*.** Take a
2de0: 6c 6c 20 74 68 65 20 65 6e 74 72 69 65 73 20 6f  ll the entries o
2df0: 6e 20 70 2d 3e 70 45 6e 74 72 79 20 61 6e 64 20  n p->pEntry and 
2e00: 6f 6e 20 74 68 65 20 74 72 65 65 73 20 69 6e 20  on the trees in 
2e10: 70 2d 3e 70 46 6f 72 65 73 74 20 61 6e 64 0a 2a  p->pForest and.*
2e20: 2a 20 73 6f 72 74 20 74 68 65 6d 20 61 6c 6c 20  * sort them all 
2e30: 74 6f 67 65 74 68 65 72 20 69 6e 74 6f 20 6f 6e  together into on
2e40: 65 20 62 69 67 20 6f 72 64 65 72 65 64 20 6c 69  e big ordered li
2e50: 73 74 20 6f 6e 20 70 2d 3e 70 45 6e 74 72 79 2e  st on p->pEntry.
2e60: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74  .**.** This rout
2e70: 69 6e 65 20 73 68 6f 75 6c 64 20 6f 6e 6c 79 20  ine should only 
2e80: 62 65 20 63 61 6c 6c 65 64 20 6f 6e 63 65 20 69  be called once i
2e90: 6e 20 74 68 65 20 6c 69 66 65 20 6f 66 20 61 20  n the life of a 
2ea0: 52 6f 77 53 65 74 2e 0a 2a 2f 0a 73 74 61 74 69  RowSet..*/.stati
2eb0: 63 20 76 6f 69 64 20 72 6f 77 53 65 74 54 6f 4c  c void rowSetToL
2ec0: 69 73 74 28 52 6f 77 53 65 74 20 2a 70 29 7b 0a  ist(RowSet *p){.
2ed0: 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f 75 74 69  .  /* This routi
2ee0: 6e 65 20 69 73 20 63 61 6c 6c 65 64 20 6f 6e 6c  ne is called onl
2ef0: 79 20 6f 6e 63 65 20 2a 2f 0a 20 20 61 73 73 65  y once */.  asse
2f00: 72 74 28 20 70 21 3d 30 20 26 26 20 28 70 2d 3e  rt( p!=0 && (p->
2f10: 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53 45 54  rsFlags & ROWSET
2f20: 5f 4e 45 58 54 29 3d 3d 30 20 29 3b 0a 0a 20 20  _NEXT)==0 );..  
2f30: 69 66 28 20 28 70 2d 3e 72 73 46 6c 61 67 73 20  if( (p->rsFlags 
2f40: 26 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44 29  & ROWSET_SORTED)
2f50: 3d 3d 30 20 29 7b 0a 20 20 20 20 70 2d 3e 70 45  ==0 ){.    p->pE
2f60: 6e 74 72 79 20 3d 20 72 6f 77 53 65 74 45 6e 74  ntry = rowSetEnt
2f70: 72 79 53 6f 72 74 28 70 2d 3e 70 45 6e 74 72 79  rySort(p->pEntry
2f80: 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 57 68 69  );.  }..  /* Whi
2f90: 6c 65 20 74 68 69 73 20 6d 6f 64 75 6c 65 20 63  le this module c
2fa0: 6f 75 6c 64 20 74 68 65 6f 72 65 74 69 63 61 6c  ould theoretical
2fb0: 6c 79 20 73 75 70 70 6f 72 74 20 69 74 2c 20 73  ly support it, s
2fc0: 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65 78 74  qlite3RowSetNext
2fd0: 28 29 0a 20 20 2a 2a 20 69 73 20 6e 65 76 65 72  ().  ** is never
2fe0: 20 63 61 6c 6c 65 64 20 61 66 74 65 72 20 73 71   called after sq
2ff0: 6c 69 74 65 33 52 6f 77 53 65 74 54 65 78 74 28  lite3RowSetText(
3000: 29 20 66 6f 72 20 74 68 65 20 73 61 6d 65 20 52  ) for the same R
3010: 6f 77 53 65 74 2e 20 20 53 6f 0a 20 20 2a 2a 20  owSet.  So.  ** 
3020: 74 68 65 72 65 20 69 73 20 6e 65 76 65 72 20 61  there is never a
3030: 20 66 6f 72 65 73 74 20 74 6f 20 64 65 61 6c 20   forest to deal 
3040: 77 69 74 68 2e 20 20 53 68 6f 75 6c 64 20 74 68  with.  Should th
3050: 69 73 20 63 68 61 6e 67 65 2c 20 73 69 6d 70 6c  is change, simpl
3060: 79 0a 20 20 2a 2a 20 72 65 6d 6f 76 65 20 74 68  y.  ** remove th
3070: 65 20 61 73 73 65 72 74 28 29 20 61 6e 64 20 74  e assert() and t
3080: 68 65 20 23 69 66 20 30 2e 20 2a 2f 0a 20 20 61  he #if 0. */.  a
3090: 73 73 65 72 74 28 20 70 2d 3e 70 46 6f 72 65 73  ssert( p->pFores
30a0: 74 3d 3d 30 20 29 3b 0a 23 69 66 20 30 0a 20 20  t==0 );.#if 0.  
30b0: 77 68 69 6c 65 28 20 70 2d 3e 70 46 6f 72 65 73  while( p->pFores
30c0: 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20  t ){.    struct 
30d0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 54 72  RowSetEntry *pTr
30e0: 65 65 20 3d 20 70 2d 3e 70 46 6f 72 65 73 74 2d  ee = p->pForest-
30f0: 3e 70 4c 65 66 74 3b 0a 20 20 20 20 69 66 28 20  >pLeft;.    if( 
3100: 70 54 72 65 65 20 29 7b 0a 20 20 20 20 20 20 73  pTree ){.      s
3110: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
3120: 79 20 2a 70 48 65 61 64 2c 20 2a 70 54 61 69 6c  y *pHead, *pTail
3130: 3b 0a 20 20 20 20 20 20 72 6f 77 53 65 74 54 72  ;.      rowSetTr
3140: 65 65 54 6f 4c 69 73 74 28 70 54 72 65 65 2c 20  eeToList(pTree, 
3150: 26 70 48 65 61 64 2c 20 26 70 54 61 69 6c 29 3b  &pHead, &pTail);
3160: 0a 20 20 20 20 20 20 70 2d 3e 70 45 6e 74 72 79  .      p->pEntry
3170: 20 3d 20 72 6f 77 53 65 74 45 6e 74 72 79 4d 65   = rowSetEntryMe
3180: 72 67 65 28 70 2d 3e 70 45 6e 74 72 79 2c 20 70  rge(p->pEntry, p
3190: 48 65 61 64 29 3b 0a 20 20 20 20 7d 0a 20 20 20  Head);.    }.   
31a0: 20 70 2d 3e 70 46 6f 72 65 73 74 20 3d 20 70 2d   p->pForest = p-
31b0: 3e 70 46 6f 72 65 73 74 2d 3e 70 52 69 67 68 74  >pForest->pRight
31c0: 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 0a 20 20 70  ;.  }.#endif.  p
31d0: 2d 3e 72 73 46 6c 61 67 73 20 7c 3d 20 52 4f 57  ->rsFlags |= ROW
31e0: 53 45 54 5f 4e 45 58 54 3b 20 20 2f 2a 20 56 65  SET_NEXT;  /* Ve
31f0: 72 69 66 79 20 74 68 69 73 20 72 6f 75 74 69 6e  rify this routin
3200: 65 20 69 73 20 6e 65 76 65 72 20 63 61 6c 6c 65  e is never calle
3210: 64 20 61 67 61 69 6e 20 2a 2f 0a 7d 0a 0a 2f 2a  d again */.}../*
3220: 0a 2a 2a 20 45 78 74 72 61 63 74 20 74 68 65 20  .** Extract the 
3230: 73 6d 61 6c 6c 65 73 74 20 65 6c 65 6d 65 6e 74  smallest element
3240: 20 66 72 6f 6d 20 74 68 65 20 52 6f 77 53 65 74   from the RowSet
3250: 2e 0a 2a 2a 20 57 72 69 74 65 20 74 68 65 20 65  ..** Write the e
3260: 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 2a 70 52 6f  lement into *pRo
3270: 77 69 64 2e 20 20 52 65 74 75 72 6e 20 31 20 6f  wid.  Return 1 o
3280: 6e 20 73 75 63 63 65 73 73 2e 20 20 52 65 74 75  n success.  Retu
3290: 72 6e 0a 2a 2a 20 30 20 69 66 20 74 68 65 20 52  rn.** 0 if the R
32a0: 6f 77 53 65 74 20 69 73 20 61 6c 72 65 61 64 79  owSet is already
32b0: 20 65 6d 70 74 79 2e 0a 2a 2a 0a 2a 2a 20 41 66   empty..**.** Af
32c0: 74 65 72 20 74 68 69 73 20 72 6f 75 74 69 6e 65  ter this routine
32d0: 20 68 61 73 20 62 65 65 6e 20 63 61 6c 6c 65 64   has been called
32e0: 2c 20 74 68 65 20 73 71 6c 69 74 65 33 52 6f 77  , the sqlite3Row
32f0: 53 65 74 49 6e 73 65 72 74 28 29 0a 2a 2a 20 72  SetInsert().** r
3300: 6f 75 74 69 6e 65 20 6d 61 79 20 6e 6f 74 20 62  outine may not b
3310: 65 20 63 61 6c 6c 65 64 20 61 67 61 69 6e 2e 20  e called again. 
3320: 20 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33   .*/.int sqlite3
3330: 52 6f 77 53 65 74 4e 65 78 74 28 52 6f 77 53 65  RowSetNext(RowSe
3340: 74 20 2a 70 2c 20 69 36 34 20 2a 70 52 6f 77 69  t *p, i64 *pRowi
3350: 64 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70 21  d){.  assert( p!
3360: 3d 30 20 29 3b 0a 0a 20 20 2f 2a 20 4d 65 72 67  =0 );..  /* Merg
3370: 65 20 74 68 65 20 66 6f 72 65 73 74 20 69 6e 74  e the forest int
3380: 6f 20 61 20 73 69 6e 67 6c 65 20 73 6f 72 74 65  o a single sorte
3390: 64 20 6c 69 73 74 20 6f 6e 20 66 69 72 73 74 20  d list on first 
33a0: 63 61 6c 6c 20 2a 2f 0a 20 20 69 66 28 20 28 70  call */.  if( (p
33b0: 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53  ->rsFlags & ROWS
33c0: 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 20 72 6f  ET_NEXT)==0 ) ro
33d0: 77 53 65 74 54 6f 4c 69 73 74 28 70 29 3b 0a 0a  wSetToList(p);..
33e0: 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65 20    /* Return the 
33f0: 6e 65 78 74 20 65 6e 74 72 79 20 6f 6e 20 74 68  next entry on th
3400: 65 20 6c 69 73 74 20 2a 2f 0a 20 20 69 66 28 20  e list */.  if( 
3410: 70 2d 3e 70 45 6e 74 72 79 20 29 7b 0a 20 20 20  p->pEntry ){.   
3420: 20 2a 70 52 6f 77 69 64 20 3d 20 70 2d 3e 70 45   *pRowid = p->pE
3430: 6e 74 72 79 2d 3e 76 3b 0a 20 20 20 20 70 2d 3e  ntry->v;.    p->
3440: 70 45 6e 74 72 79 20 3d 20 70 2d 3e 70 45 6e 74  pEntry = p->pEnt
3450: 72 79 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20  ry->pRight;.    
3460: 69 66 28 20 70 2d 3e 70 45 6e 74 72 79 3d 3d 30  if( p->pEntry==0
3470: 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65   ){.      sqlite
3480: 33 52 6f 77 53 65 74 43 6c 65 61 72 28 70 29 3b  3RowSetClear(p);
3490: 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72  .    }.    retur
34a0: 6e 20 31 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  n 1;.  }else{.  
34b0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a    return 0;.  }.
34c0: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65 63 6b 20 74  }../*.** Check t
34d0: 6f 20 73 65 65 20 69 66 20 65 6c 65 6d 65 6e 74  o see if element
34e0: 20 69 52 6f 77 69 64 20 77 61 73 20 69 6e 73 65   iRowid was inse
34f0: 72 74 65 64 20 69 6e 74 6f 20 74 68 65 20 74 68  rted into the th
3500: 65 20 72 6f 77 73 65 74 20 61 73 0a 2a 2a 20 70  e rowset as.** p
3510: 61 72 74 20 6f 66 20 61 6e 79 20 69 6e 73 65 72  art of any inser
3520: 74 20 62 61 74 63 68 20 70 72 69 6f 72 20 74 6f  t batch prior to
3530: 20 69 42 61 74 63 68 2e 20 20 52 65 74 75 72 6e   iBatch.  Return
3540: 20 31 20 6f 72 20 30 2e 0a 2a 2a 0a 2a 2a 20 49   1 or 0..**.** I
3550: 66 20 74 68 69 73 20 69 73 20 74 68 65 20 66 69  f this is the fi
3560: 72 73 74 20 74 65 73 74 20 6f 66 20 61 20 6e 65  rst test of a ne
3570: 77 20 62 61 74 63 68 20 61 6e 64 20 69 66 20 74  w batch and if t
3580: 68 65 72 65 20 65 78 69 73 74 20 65 6e 74 69 72  here exist entir
3590: 65 73 0a 2a 2a 20 6f 6e 20 70 52 6f 77 53 65 74  es.** on pRowSet
35a0: 2d 3e 70 45 6e 74 72 79 2c 20 74 68 65 6e 20 73  ->pEntry, then s
35b0: 6f 72 74 20 74 68 6f 73 65 20 65 6e 74 69 72 65  ort those entire
35c0: 73 20 69 6e 74 6f 20 74 68 65 20 66 6f 72 65 73  s into the fores
35d0: 74 20 61 74 0a 2a 2a 20 70 52 6f 77 53 65 74 2d  t at.** pRowSet-
35e0: 3e 70 46 6f 72 65 73 74 20 73 6f 20 74 68 61 74  >pForest so that
35f0: 20 74 68 65 79 20 63 61 6e 20 62 65 20 74 65 73   they can be tes
3600: 74 65 64 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  ted..*/.int sqli
3610: 74 65 33 52 6f 77 53 65 74 54 65 73 74 28 52 6f  te3RowSetTest(Ro
3620: 77 53 65 74 20 2a 70 52 6f 77 53 65 74 2c 20 75  wSet *pRowSet, u
3630: 38 20 69 42 61 74 63 68 2c 20 73 71 6c 69 74 65  8 iBatch, sqlite
3640: 33 5f 69 6e 74 36 34 20 69 52 6f 77 69 64 29 7b  3_int64 iRowid){
3650: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
3660: 45 6e 74 72 79 20 2a 70 2c 20 2a 70 54 72 65 65  Entry *p, *pTree
3670: 3b 0a 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f 75  ;..  /* This rou
3680: 74 69 6e 65 20 69 73 20 6e 65 76 65 72 20 63 61  tine is never ca
3690: 6c 6c 65 64 20 61 66 74 65 72 20 73 71 6c 69 74  lled after sqlit
36a0: 65 33 52 6f 77 53 65 74 4e 65 78 74 28 29 20 2a  e3RowSetNext() *
36b0: 2f 0a 20 20 61 73 73 65 72 74 28 20 70 52 6f 77  /.  assert( pRow
36c0: 53 65 74 21 3d 30 20 26 26 20 28 70 52 6f 77 53  Set!=0 && (pRowS
36d0: 65 74 2d 3e 72 73 46 6c 61 67 73 20 26 20 52 4f  et->rsFlags & RO
36e0: 57 53 45 54 5f 4e 45 58 54 29 3d 3d 30 20 29 3b  WSET_NEXT)==0 );
36f0: 0a 0a 20 20 2f 2a 20 53 6f 72 74 20 65 6e 74 72  ..  /* Sort entr
3700: 69 65 73 20 69 6e 74 6f 20 74 68 65 20 66 6f 72  ies into the for
3710: 65 73 74 20 6f 6e 20 74 68 65 20 66 69 72 73 74  est on the first
3720: 20 74 65 73 74 20 6f 66 20 61 20 6e 65 77 20 62   test of a new b
3730: 61 74 63 68 20 0a 20 20 2a 2f 0a 20 20 69 66 28  atch .  */.  if(
3740: 20 69 42 61 74 63 68 21 3d 70 52 6f 77 53 65 74   iBatch!=pRowSet
3750: 2d 3e 69 42 61 74 63 68 20 29 7b 0a 20 20 20 20  ->iBatch ){.    
3760: 70 20 3d 20 70 52 6f 77 53 65 74 2d 3e 70 45 6e  p = pRowSet->pEn
3770: 74 72 79 3b 0a 20 20 20 20 69 66 28 20 70 20 29  try;.    if( p )
3780: 7b 0a 20 20 20 20 20 20 73 74 72 75 63 74 20 52  {.      struct R
3790: 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a 70 70 50  owSetEntry **ppP
37a0: 72 65 76 54 72 65 65 20 3d 20 26 70 52 6f 77 53  revTree = &pRowS
37b0: 65 74 2d 3e 70 46 6f 72 65 73 74 3b 0a 20 20 20  et->pForest;.   
37c0: 20 20 20 69 66 28 20 28 70 52 6f 77 53 65 74 2d     if( (pRowSet-
37d0: 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53 45  >rsFlags & ROWSE
37e0: 54 5f 53 4f 52 54 45 44 29 3d 3d 30 20 29 7b 0a  T_SORTED)==0 ){.
37f0: 20 20 20 20 20 20 20 20 70 20 3d 20 72 6f 77 53          p = rowS
3800: 65 74 45 6e 74 72 79 53 6f 72 74 28 70 29 3b 0a  etEntrySort(p);.
3810: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 66 6f        }.      fo
3820: 72 28 70 54 72 65 65 20 3d 20 70 52 6f 77 53 65  r(pTree = pRowSe
3830: 74 2d 3e 70 46 6f 72 65 73 74 3b 20 70 54 72 65  t->pForest; pTre
3840: 65 3b 20 70 54 72 65 65 3d 70 54 72 65 65 2d 3e  e; pTree=pTree->
3850: 70 52 69 67 68 74 29 7b 0a 20 20 20 20 20 20 20  pRight){.       
3860: 20 70 70 50 72 65 76 54 72 65 65 20 3d 20 26 70   ppPrevTree = &p
3870: 54 72 65 65 2d 3e 70 52 69 67 68 74 3b 0a 20 20  Tree->pRight;.  
3880: 20 20 20 20 20 20 69 66 28 20 70 54 72 65 65 2d        if( pTree-
3890: 3e 70 4c 65 66 74 3d 3d 30 20 29 7b 0a 20 20 20  >pLeft==0 ){.   
38a0: 20 20 20 20 20 20 20 70 54 72 65 65 2d 3e 70 4c         pTree->pL
38b0: 65 66 74 20 3d 20 72 6f 77 53 65 74 4c 69 73 74  eft = rowSetList
38c0: 54 6f 54 72 65 65 28 70 29 3b 0a 20 20 20 20 20  ToTree(p);.     
38d0: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
38e0: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
38f0: 20 20 20 20 20 73 74 72 75 63 74 20 52 6f 77 53       struct RowS
3900: 65 74 45 6e 74 72 79 20 2a 70 41 75 78 2c 20 2a  etEntry *pAux, *
3910: 70 54 61 69 6c 3b 0a 20 20 20 20 20 20 20 20 20  pTail;.         
3920: 20 72 6f 77 53 65 74 54 72 65 65 54 6f 4c 69 73   rowSetTreeToLis
3930: 74 28 70 54 72 65 65 2d 3e 70 4c 65 66 74 2c 20  t(pTree->pLeft, 
3940: 26 70 41 75 78 2c 20 26 70 54 61 69 6c 29 3b 0a  &pAux, &pTail);.
3950: 20 20 20 20 20 20 20 20 20 20 70 54 72 65 65 2d            pTree-
3960: 3e 70 4c 65 66 74 20 3d 20 30 3b 0a 20 20 20 20  >pLeft = 0;.    
3970: 20 20 20 20 20 20 70 20 3d 20 72 6f 77 53 65 74        p = rowSet
3980: 45 6e 74 72 79 4d 65 72 67 65 28 70 41 75 78 2c  EntryMerge(pAux,
3990: 20 70 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20   p);.        }. 
39a0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 69 66 28       }.      if(
39b0: 20 70 54 72 65 65 3d 3d 30 20 29 7b 0a 20 20 20   pTree==0 ){.   
39c0: 20 20 20 20 20 2a 70 70 50 72 65 76 54 72 65 65       *ppPrevTree
39d0: 20 3d 20 70 54 72 65 65 20 3d 20 72 6f 77 53 65   = pTree = rowSe
39e0: 74 45 6e 74 72 79 41 6c 6c 6f 63 28 70 52 6f 77  tEntryAlloc(pRow
39f0: 53 65 74 29 3b 0a 20 20 20 20 20 20 20 20 69 66  Set);.        if
3a00: 28 20 70 54 72 65 65 20 29 7b 0a 20 20 20 20 20  ( pTree ){.     
3a10: 20 20 20 20 20 70 54 72 65 65 2d 3e 76 20 3d 20       pTree->v = 
3a20: 30 3b 0a 20 20 20 20 20 20 20 20 20 20 70 54 72  0;.          pTr
3a30: 65 65 2d 3e 70 52 69 67 68 74 20 3d 20 30 3b 0a  ee->pRight = 0;.
3a40: 20 20 20 20 20 20 20 20 20 20 70 54 72 65 65 2d            pTree-
3a50: 3e 70 4c 65 66 74 20 3d 20 72 6f 77 53 65 74 4c  >pLeft = rowSetL
3a60: 69 73 74 54 6f 54 72 65 65 28 70 29 3b 0a 20 20  istToTree(p);.  
3a70: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a        }.      }.
3a80: 20 20 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 70        pRowSet->p
3a90: 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 20 20 20  Entry = 0;.     
3aa0: 20 70 52 6f 77 53 65 74 2d 3e 70 4c 61 73 74 20   pRowSet->pLast 
3ab0: 3d 20 30 3b 0a 20 20 20 20 20 20 70 52 6f 77 53  = 0;.      pRowS
3ac0: 65 74 2d 3e 72 73 46 6c 61 67 73 20 7c 3d 20 52  et->rsFlags |= R
3ad0: 4f 57 53 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20  OWSET_SORTED;.  
3ae0: 20 20 7d 0a 20 20 20 20 70 52 6f 77 53 65 74 2d    }.    pRowSet-
3af0: 3e 69 42 61 74 63 68 20 3d 20 69 42 61 74 63 68  >iBatch = iBatch
3b00: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 65 73 74  ;.  }..  /* Test
3b10: 20 74 6f 20 73 65 65 20 69 66 20 74 68 65 20 69   to see if the i
3b20: 52 6f 77 69 64 20 76 61 6c 75 65 20 61 70 70 65  Rowid value appe
3b30: 61 72 73 20 61 6e 79 77 68 65 72 65 20 69 6e 20  ars anywhere in 
3b40: 74 68 65 20 66 6f 72 65 73 74 2e 0a 20 20 2a 2a  the forest..  **
3b50: 20 52 65 74 75 72 6e 20 31 20 69 66 20 69 74 20   Return 1 if it 
3b60: 64 6f 65 73 20 61 6e 64 20 30 20 69 66 20 6e 6f  does and 0 if no
3b70: 74 2e 0a 20 20 2a 2f 0a 20 20 66 6f 72 28 70 54  t..  */.  for(pT
3b80: 72 65 65 20 3d 20 70 52 6f 77 53 65 74 2d 3e 70  ree = pRowSet->p
3b90: 46 6f 72 65 73 74 3b 20 70 54 72 65 65 3b 20 70  Forest; pTree; p
3ba0: 54 72 65 65 3d 70 54 72 65 65 2d 3e 70 52 69 67  Tree=pTree->pRig
3bb0: 68 74 29 7b 0a 20 20 20 20 70 20 3d 20 70 54 72  ht){.    p = pTr
3bc0: 65 65 2d 3e 70 4c 65 66 74 3b 0a 20 20 20 20 77  ee->pLeft;.    w
3bd0: 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 20  hile( p ){.     
3be0: 20 69 66 28 20 70 2d 3e 76 3c 69 52 6f 77 69 64   if( p->v<iRowid
3bf0: 20 29 7b 0a 20 20 20 20 20 20 20 20 70 20 3d 20   ){.        p = 
3c00: 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 20  p->pRight;.     
3c10: 20 7d 65 6c 73 65 20 69 66 28 20 70 2d 3e 76 3e   }else if( p->v>
3c20: 69 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 20 20  iRowid ){.      
3c30: 20 20 70 20 3d 20 70 2d 3e 70 4c 65 66 74 3b 0a    p = p->pLeft;.
3c40: 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20        }else{.   
3c50: 20 20 20 20 20 72 65 74 75 72 6e 20 31 3b 0a 20       return 1;. 
3c60: 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d       }.    }.  }
3c70: 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a     .  return 0;.}.