/ Hex Artifact Content
Login

Artifact 69afa95a97c524ba6faf3805e717b5b7ae85a697:


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 2f 0a 73 74 72 75 63  object..*/.struc
0b60: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 7b 20  t RowSetEntry { 
0b70: 20 20 20 20 20 20 20 20 20 20 20 0a 20 20 69 36             .  i6
0b80: 34 20 76 3b 20 20 20 20 20 20 20 20 20 20 20 20  4 v;            
0b90: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
0ba0: 4f 57 49 44 20 76 61 6c 75 65 20 66 6f 72 20 74  OWID value for t
0bb0: 68 69 73 20 65 6e 74 72 79 20 2a 2f 0a 20 20 73  his entry */.  s
0bc0: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
0bd0: 79 20 2a 70 52 69 67 68 74 3b 20 20 20 2f 2a 20  y *pRight;   /* 
0be0: 52 69 67 68 74 20 73 75 62 74 72 65 65 20 28 6c  Right subtree (l
0bf0: 61 72 67 65 72 20 65 6e 74 72 69 65 73 29 20 6f  arger entries) o
0c00: 72 20 6c 69 73 74 20 2a 2f 0a 20 20 73 74 72 75  r list */.  stru
0c10: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
0c20: 70 4c 65 66 74 3b 20 20 20 20 2f 2a 20 4c 65 66  pLeft;    /* Lef
0c30: 74 20 73 75 62 74 72 65 65 20 28 73 6d 61 6c 6c  t subtree (small
0c40: 65 72 20 65 6e 74 72 69 65 73 29 20 2a 2f 0a 7d  er entries) */.}
0c50: 3b 0a 0a 2f 2a 0a 2a 2a 20 52 6f 77 53 65 74 45  ;../*.** RowSetE
0c60: 6e 74 72 79 20 6f 62 6a 65 63 74 73 20 61 72 65  ntry objects are
0c70: 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e 20 6c 61   allocated in la
0c80: 72 67 65 20 63 68 75 6e 6b 73 20 28 69 6e 73 74  rge chunks (inst
0c90: 61 6e 63 65 73 20 6f 66 20 74 68 65 0a 2a 2a 20  ances of the.** 
0ca0: 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74  following struct
0cb0: 75 72 65 29 20 74 6f 20 72 65 64 75 63 65 20 6d  ure) to reduce m
0cc0: 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e  emory allocation
0cd0: 20 6f 76 65 72 68 65 61 64 2e 20 20 54 68 65 0a   overhead.  The.
0ce0: 2a 2a 20 63 68 75 6e 6b 73 20 61 72 65 20 6b 65  ** chunks are ke
0cf0: 70 74 20 6f 6e 20 61 20 6c 69 6e 6b 65 64 20 6c  pt on a linked l
0d00: 69 73 74 20 73 6f 20 74 68 61 74 20 74 68 65 79  ist so that they
0d10: 20 63 61 6e 20 62 65 20 64 65 61 6c 6c 6f 63 61   can be dealloca
0d20: 74 65 64 0a 2a 2a 20 77 68 65 6e 20 74 68 65 20  ted.** when the 
0d30: 52 6f 77 53 65 74 20 69 73 20 64 65 73 74 72 6f  RowSet is destro
0d40: 79 65 64 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 52  yed..*/.struct R
0d50: 6f 77 53 65 74 43 68 75 6e 6b 20 7b 0a 20 20 73  owSetChunk {.  s
0d60: 74 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e  truct RowSetChun
0d70: 6b 20 2a 70 4e 65 78 74 43 68 75 6e 6b 3b 20 20  k *pNextChunk;  
0d80: 20 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 63 68        /* Next ch
0d90: 75 6e 6b 20 6f 6e 20 6c 69 73 74 20 6f 66 20 74  unk on list of t
0da0: 68 65 6d 20 61 6c 6c 20 2a 2f 0a 20 20 73 74 72  hem all */.  str
0db0: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
0dc0: 61 45 6e 74 72 79 5b 52 4f 57 53 45 54 5f 45 4e  aEntry[ROWSET_EN
0dd0: 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b 5d 3b 20  TRY_PER_CHUNK]; 
0de0: 2f 2a 20 41 6c 6c 6f 63 61 74 65 64 20 65 6e 74  /* Allocated ent
0df0: 72 69 65 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a  ries */.};../*.*
0e00: 2a 20 41 20 52 6f 77 53 65 74 20 69 6e 20 61 6e  * A RowSet in an
0e10: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65   instance of the
0e20: 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63   following struc
0e30: 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 41 20 74 79  ture..**.** A ty
0e40: 70 65 64 65 66 20 6f 66 20 74 68 69 73 20 73 74  pedef of this st
0e50: 72 75 63 74 75 72 65 20 69 66 20 66 6f 75 6e 64  ructure if found
0e60: 20 69 6e 20 73 71 6c 69 74 65 49 6e 74 2e 68 2e   in sqliteInt.h.
0e70: 0a 2a 2f 0a 73 74 72 75 63 74 20 52 6f 77 53 65  .*/.struct RowSe
0e80: 74 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  t {.  struct Row
0e90: 53 65 74 43 68 75 6e 6b 20 2a 70 43 68 75 6e 6b  SetChunk *pChunk
0ea0: 3b 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66 20  ;    /* List of 
0eb0: 61 6c 6c 20 63 68 75 6e 6b 20 61 6c 6c 6f 63 61  all chunk alloca
0ec0: 74 69 6f 6e 73 20 2a 2f 0a 20 20 73 71 6c 69 74  tions */.  sqlit
0ed0: 65 33 20 2a 64 62 3b 20 20 20 20 20 20 20 20 20  e3 *db;         
0ee0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65            /* The
0ef0: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
0f00: 74 69 6f 6e 20 2a 2f 0a 20 20 73 74 72 75 63 74  tion */.  struct
0f10: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 45   RowSetEntry *pE
0f20: 6e 74 72 79 3b 20 20 20 20 2f 2a 20 4c 69 73 74  ntry;    /* List
0f30: 20 6f 66 20 65 6e 74 72 69 65 73 20 75 73 69 6e   of entries usin
0f40: 67 20 70 52 69 67 68 74 20 2a 2f 0a 20 20 73 74  g pRight */.  st
0f50: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
0f60: 20 2a 70 4c 61 73 74 3b 20 20 20 20 20 2f 2a 20   *pLast;     /* 
0f70: 4c 61 73 74 20 65 6e 74 72 79 20 6f 6e 20 74 68  Last entry on th
0f80: 65 20 70 45 6e 74 72 79 20 6c 69 73 74 20 2a 2f  e pEntry list */
0f90: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
0fa0: 45 6e 74 72 79 20 2a 70 46 72 65 73 68 3b 20 20  Entry *pFresh;  
0fb0: 20 20 2f 2a 20 53 6f 75 72 63 65 20 6f 66 20 6e    /* Source of n
0fc0: 65 77 20 65 6e 74 72 79 20 6f 62 6a 65 63 74 73  ew entry objects
0fd0: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
0fe0: 53 65 74 45 6e 74 72 79 20 2a 70 54 72 65 65 3b  SetEntry *pTree;
0ff0: 20 20 20 20 20 2f 2a 20 42 69 6e 61 72 79 20 74       /* Binary t
1000: 72 65 65 20 6f 66 20 65 6e 74 72 69 65 73 20 2a  ree of entries *
1010: 2f 0a 20 20 75 31 36 20 6e 46 72 65 73 68 3b 20  /.  u16 nFresh; 
1020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1030: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1040: 6f 62 6a 65 63 74 73 20 6f 6e 20 70 46 72 65 73  objects on pFres
1050: 68 20 2a 2f 0a 20 20 75 38 20 69 73 53 6f 72 74  h */.  u8 isSort
1060: 65 64 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ed;             
1070: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
1080: 20 70 45 6e 74 72 79 20 69 73 20 73 6f 72 74 65   pEntry is sorte
1090: 64 20 2a 2f 0a 20 20 75 38 20 69 42 61 74 63 68  d */.  u8 iBatch
10a0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
10b0: 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74        /* Current
10c0: 20 69 6e 73 65 72 74 20 62 61 74 63 68 20 2a 2f   insert batch */
10d0: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 75 72 6e 20  .};../*.** Turn 
10e0: 62 75 6c 6b 20 6d 65 6d 6f 72 79 20 69 6e 74 6f  bulk memory into
10f0: 20 61 20 52 6f 77 53 65 74 20 6f 62 6a 65 63 74   a RowSet object
1100: 2e 20 20 4e 20 62 79 74 65 73 20 6f 66 20 6d 65  .  N bytes of me
1110: 6d 6f 72 79 0a 2a 2a 20 61 72 65 20 61 76 61 69  mory.** are avai
1120: 6c 61 62 6c 65 20 61 74 20 70 53 70 61 63 65 2e  lable at pSpace.
1130: 20 20 54 68 65 20 64 62 20 70 6f 69 6e 74 65 72    The db pointer
1140: 20 69 73 20 75 73 65 64 20 61 73 20 61 20 6d 65   is used as a me
1150: 6d 6f 72 79 20 63 6f 6e 74 65 78 74 0a 2a 2a 20  mory context.** 
1160: 66 6f 72 20 61 6e 79 20 73 75 62 73 65 71 75 65  for any subseque
1170: 6e 74 20 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 74  nt allocations t
1180: 68 61 74 20 6e 65 65 64 20 74 6f 20 6f 63 63 75  hat need to occu
1190: 72 2e 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70  r..** Return a p
11a0: 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 6e 65  ointer to the ne
11b0: 77 20 52 6f 77 53 65 74 20 6f 62 6a 65 63 74 2e  w RowSet object.
11c0: 0a 2a 2a 0a 2a 2a 20 49 74 20 6d 75 73 74 20 62  .**.** It must b
11d0: 65 20 74 68 65 20 63 61 73 65 20 74 68 61 74 20  e the case that 
11e0: 4e 20 69 73 20 73 75 66 66 69 63 69 65 6e 74 20  N is sufficient 
11f0: 74 6f 20 6d 61 6b 65 20 61 20 52 6f 77 73 65 74  to make a Rowset
1200: 2e 20 20 49 66 20 6e 6f 74 0a 2a 2a 20 61 6e 20  .  If not.** an 
1210: 61 73 73 65 72 74 69 6f 6e 20 66 61 75 6c 74 20  assertion fault 
1220: 6f 63 63 75 72 73 2e 0a 2a 2a 20 0a 2a 2a 20 49  occurs..** .** I
1230: 66 20 4e 20 69 73 20 6c 61 72 67 65 72 20 74 68  f N is larger th
1240: 61 6e 20 74 68 65 20 6d 69 6e 69 6d 75 6d 2c 20  an the minimum, 
1250: 75 73 65 20 74 68 65 20 73 75 72 70 6c 75 73 20  use the surplus 
1260: 61 73 20 61 6e 20 69 6e 69 74 69 61 6c 0a 2a 2a  as an initial.**
1270: 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 6f 66 20 65   allocation of e
1280: 6e 74 72 69 65 73 20 61 76 61 69 6c 61 62 6c 65  ntries available
1290: 20 74 6f 20 62 65 20 66 69 6c 6c 65 64 2e 0a 2a   to be filled..*
12a0: 2f 0a 52 6f 77 53 65 74 20 2a 73 71 6c 69 74 65  /.RowSet *sqlite
12b0: 33 52 6f 77 53 65 74 49 6e 69 74 28 73 71 6c 69  3RowSetInit(sqli
12c0: 74 65 33 20 2a 64 62 2c 20 76 6f 69 64 20 2a 70  te3 *db, void *p
12d0: 53 70 61 63 65 2c 20 75 6e 73 69 67 6e 65 64 20  Space, unsigned 
12e0: 69 6e 74 20 4e 29 7b 0a 20 20 52 6f 77 53 65 74  int N){.  RowSet
12f0: 20 2a 70 3b 0a 20 20 61 73 73 65 72 74 28 20 4e   *p;.  assert( N
1300: 20 3e 3d 20 52 4f 55 4e 44 38 28 73 69 7a 65 6f   >= ROUND8(sizeo
1310: 66 28 2a 70 29 29 20 29 3b 0a 20 20 70 20 3d 20  f(*p)) );.  p = 
1320: 70 53 70 61 63 65 3b 0a 20 20 70 2d 3e 70 43 68  pSpace;.  p->pCh
1330: 75 6e 6b 20 3d 20 30 3b 0a 20 20 70 2d 3e 64 62  unk = 0;.  p->db
1340: 20 3d 20 64 62 3b 0a 20 20 70 2d 3e 70 45 6e 74   = db;.  p->pEnt
1350: 72 79 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 4c 61  ry = 0;.  p->pLa
1360: 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 54 72  st = 0;.  p->pTr
1370: 65 65 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 46 72  ee = 0;.  p->pFr
1380: 65 73 68 20 3d 20 28 73 74 72 75 63 74 20 52 6f  esh = (struct Ro
1390: 77 53 65 74 45 6e 74 72 79 2a 29 28 52 4f 55 4e  wSetEntry*)(ROUN
13a0: 44 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 20 2b  D8(sizeof(*p)) +
13b0: 20 28 63 68 61 72 2a 29 70 29 3b 0a 20 20 70 2d   (char*)p);.  p-
13c0: 3e 6e 46 72 65 73 68 20 3d 20 28 75 31 36 29 28  >nFresh = (u16)(
13d0: 28 4e 20 2d 20 52 4f 55 4e 44 38 28 73 69 7a 65  (N - ROUND8(size
13e0: 6f 66 28 2a 70 29 29 29 2f 73 69 7a 65 6f 66 28  of(*p)))/sizeof(
13f0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1400: 72 79 29 29 3b 0a 20 20 70 2d 3e 69 73 53 6f 72  ry));.  p->isSor
1410: 74 65 64 20 3d 20 31 3b 0a 20 20 70 2d 3e 69 42  ted = 1;.  p->iB
1420: 61 74 63 68 20 3d 20 30 3b 0a 20 20 72 65 74 75  atch = 0;.  retu
1430: 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 44  rn p;.}../*.** D
1440: 65 61 6c 6c 6f 63 61 74 65 20 61 6c 6c 20 63 68  eallocate all ch
1450: 75 6e 6b 73 20 66 72 6f 6d 20 61 20 52 6f 77 53  unks from a RowS
1460: 65 74 2e 20 20 54 68 69 73 20 66 72 65 65 73 20  et.  This frees 
1470: 61 6c 6c 20 6d 65 6d 6f 72 79 20 74 68 61 74 0a  all memory that.
1480: 2a 2a 20 74 68 65 20 52 6f 77 53 65 74 20 68 61  ** the RowSet ha
1490: 73 20 61 6c 6c 6f 63 61 74 65 64 20 6f 76 65 72  s allocated over
14a0: 20 69 74 73 20 6c 69 66 65 74 69 6d 65 2e 20 20   its lifetime.  
14b0: 54 68 69 73 20 72 6f 75 74 69 6e 65 20 69 73 0a  This routine is.
14c0: 2a 2a 20 74 68 65 20 64 65 73 74 72 75 63 74 6f  ** the destructo
14d0: 72 20 66 6f 72 20 74 68 65 20 52 6f 77 53 65 74  r for the RowSet
14e0: 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65  ..*/.void sqlite
14f0: 33 52 6f 77 53 65 74 43 6c 65 61 72 28 52 6f 77  3RowSetClear(Row
1500: 53 65 74 20 2a 70 29 7b 0a 20 20 73 74 72 75 63  Set *p){.  struc
1510: 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a 70  t RowSetChunk *p
1520: 43 68 75 6e 6b 2c 20 2a 70 4e 65 78 74 43 68 75  Chunk, *pNextChu
1530: 6e 6b 3b 0a 20 20 66 6f 72 28 70 43 68 75 6e 6b  nk;.  for(pChunk
1540: 3d 70 2d 3e 70 43 68 75 6e 6b 3b 20 70 43 68 75  =p->pChunk; pChu
1550: 6e 6b 3b 20 70 43 68 75 6e 6b 20 3d 20 70 4e 65  nk; pChunk = pNe
1560: 78 74 43 68 75 6e 6b 29 7b 0a 20 20 20 20 70 4e  xtChunk){.    pN
1570: 65 78 74 43 68 75 6e 6b 20 3d 20 70 43 68 75 6e  extChunk = pChun
1580: 6b 2d 3e 70 4e 65 78 74 43 68 75 6e 6b 3b 0a 20  k->pNextChunk;. 
1590: 20 20 20 73 71 6c 69 74 65 33 44 62 46 72 65 65     sqlite3DbFree
15a0: 28 70 2d 3e 64 62 2c 20 70 43 68 75 6e 6b 29 3b  (p->db, pChunk);
15b0: 0a 20 20 7d 0a 20 20 70 2d 3e 70 43 68 75 6e 6b  .  }.  p->pChunk
15c0: 20 3d 20 30 3b 0a 20 20 70 2d 3e 6e 46 72 65 73   = 0;.  p->nFres
15d0: 68 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 45 6e 74  h = 0;.  p->pEnt
15e0: 72 79 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 4c 61  ry = 0;.  p->pLa
15f0: 73 74 20 3d 20 30 3b 0a 20 20 70 2d 3e 70 54 72  st = 0;.  p->pTr
1600: 65 65 20 3d 20 30 3b 0a 20 20 70 2d 3e 69 73 53  ee = 0;.  p->isS
1610: 6f 72 74 65 64 20 3d 20 31 3b 0a 7d 0a 0a 2f 2a  orted = 1;.}../*
1620: 0a 2a 2a 20 49 6e 73 65 72 74 20 61 20 6e 65 77  .** Insert a new
1630: 20 76 61 6c 75 65 20 69 6e 74 6f 20 61 20 52 6f   value into a Ro
1640: 77 53 65 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  wSet..**.** The 
1650: 6d 61 6c 6c 6f 63 46 61 69 6c 65 64 20 66 6c 61  mallocFailed fla
1660: 67 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73  g of the databas
1670: 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 69 73 20  e connection is 
1680: 73 65 74 20 69 66 20 61 0a 2a 2a 20 6d 65 6d 6f  set if a.** memo
1690: 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 66 61  ry allocation fa
16a0: 69 6c 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c  ils..*/.void sql
16b0: 69 74 65 33 52 6f 77 53 65 74 49 6e 73 65 72 74  ite3RowSetInsert
16c0: 28 52 6f 77 53 65 74 20 2a 70 2c 20 69 36 34 20  (RowSet *p, i64 
16d0: 72 6f 77 69 64 29 7b 0a 20 20 73 74 72 75 63 74  rowid){.  struct
16e0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 45   RowSetEntry *pE
16f0: 6e 74 72 79 3b 20 20 2f 2a 20 54 68 65 20 6e 65  ntry;  /* The ne
1700: 77 20 65 6e 74 72 79 20 2a 2f 0a 20 20 73 74 72  w entry */.  str
1710: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
1720: 2a 70 4c 61 73 74 3b 20 20 20 2f 2a 20 54 68 65  *pLast;   /* The
1730: 20 6c 61 73 74 20 70 72 69 6f 72 20 65 6e 74 72   last prior entr
1740: 79 20 2a 2f 0a 20 20 61 73 73 65 72 74 28 20 70  y */.  assert( p
1750: 21 3d 30 20 29 3b 0a 20 20 69 66 28 20 70 2d 3e  !=0 );.  if( p->
1760: 6e 46 72 65 73 68 3d 3d 30 20 29 7b 0a 20 20 20  nFresh==0 ){.   
1770: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 43 68   struct RowSetCh
1780: 75 6e 6b 20 2a 70 4e 65 77 3b 0a 20 20 20 20 70  unk *pNew;.    p
1790: 4e 65 77 20 3d 20 73 71 6c 69 74 65 33 44 62 4d  New = sqlite3DbM
17a0: 61 6c 6c 6f 63 52 61 77 28 70 2d 3e 64 62 2c 20  allocRaw(p->db, 
17b0: 73 69 7a 65 6f 66 28 2a 70 4e 65 77 29 29 3b 0a  sizeof(*pNew));.
17c0: 20 20 20 20 69 66 28 20 70 4e 65 77 3d 3d 30 20      if( pNew==0 
17d0: 29 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 3b  ){.      return;
17e0: 0a 20 20 20 20 7d 0a 20 20 20 20 70 4e 65 77 2d  .    }.    pNew-
17f0: 3e 70 4e 65 78 74 43 68 75 6e 6b 20 3d 20 70 2d  >pNextChunk = p-
1800: 3e 70 43 68 75 6e 6b 3b 0a 20 20 20 20 70 2d 3e  >pChunk;.    p->
1810: 70 43 68 75 6e 6b 20 3d 20 70 4e 65 77 3b 0a 20  pChunk = pNew;. 
1820: 20 20 20 70 2d 3e 70 46 72 65 73 68 20 3d 20 70     p->pFresh = p
1830: 4e 65 77 2d 3e 61 45 6e 74 72 79 3b 0a 20 20 20  New->aEntry;.   
1840: 20 70 2d 3e 6e 46 72 65 73 68 20 3d 20 52 4f 57   p->nFresh = ROW
1850: 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f 43 48  SET_ENTRY_PER_CH
1860: 55 4e 4b 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72  UNK;.  }.  pEntr
1870: 79 20 3d 20 70 2d 3e 70 46 72 65 73 68 2b 2b 3b  y = p->pFresh++;
1880: 0a 20 20 70 2d 3e 6e 46 72 65 73 68 2d 2d 3b 0a  .  p->nFresh--;.
1890: 20 20 70 45 6e 74 72 79 2d 3e 76 20 3d 20 72 6f    pEntry->v = ro
18a0: 77 69 64 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 70  wid;.  pEntry->p
18b0: 52 69 67 68 74 20 3d 20 30 3b 0a 20 20 70 4c 61  Right = 0;.  pLa
18c0: 73 74 20 3d 20 70 2d 3e 70 4c 61 73 74 3b 0a 20  st = p->pLast;. 
18d0: 20 69 66 28 20 70 4c 61 73 74 20 29 7b 0a 20 20   if( pLast ){.  
18e0: 20 20 69 66 28 20 70 2d 3e 69 73 53 6f 72 74 65    if( p->isSorte
18f0: 64 20 26 26 20 72 6f 77 69 64 3c 3d 70 4c 61 73  d && rowid<=pLas
1900: 74 2d 3e 76 20 29 7b 0a 20 20 20 20 20 20 70 2d  t->v ){.      p-
1910: 3e 69 73 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20  >isSorted = 0;. 
1920: 20 20 20 7d 0a 20 20 20 20 70 4c 61 73 74 2d 3e     }.    pLast->
1930: 70 52 69 67 68 74 20 3d 20 70 45 6e 74 72 79 3b  pRight = pEntry;
1940: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73  .  }else{.    as
1950: 73 65 72 74 28 20 70 2d 3e 70 45 6e 74 72 79 3d  sert( p->pEntry=
1960: 3d 30 20 29 3b 20 2f 2a 20 46 69 72 65 73 20 69  =0 ); /* Fires i
1970: 66 20 49 4e 53 45 52 54 20 61 66 74 65 72 20 53  f INSERT after S
1980: 4d 41 4c 4c 45 53 54 20 2a 2f 0a 20 20 20 20 70  MALLEST */.    p
1990: 2d 3e 70 45 6e 74 72 79 20 3d 20 70 45 6e 74 72  ->pEntry = pEntr
19a0: 79 3b 0a 20 20 7d 0a 20 20 70 2d 3e 70 4c 61 73  y;.  }.  p->pLas
19b0: 74 20 3d 20 70 45 6e 74 72 79 3b 0a 7d 0a 0a 2f  t = pEntry;.}../
19c0: 2a 0a 2a 2a 20 4d 65 72 67 65 20 74 77 6f 20 6c  *.** Merge two l
19d0: 69 73 74 73 20 6f 66 20 52 6f 77 53 65 74 45 6e  ists of RowSetEn
19e0: 74 72 79 20 6f 62 6a 65 63 74 73 2e 20 20 52 65  try objects.  Re
19f0: 6d 6f 76 65 20 64 75 70 6c 69 63 61 74 65 73 2e  move duplicates.
1a00: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74  .**.** The input
1a10: 20 6c 69 73 74 73 20 61 72 65 20 63 6f 6e 6e 65   lists are conne
1a20: 63 74 65 64 20 76 69 61 20 70 52 69 67 68 74 20  cted via pRight 
1a30: 70 6f 69 6e 74 65 72 73 20 61 6e 64 20 61 72 65  pointers and are
1a40: 20 0a 2a 2a 20 61 73 73 75 6d 65 64 20 74 6f 20   .** assumed to 
1a50: 65 61 63 68 20 61 6c 72 65 61 64 79 20 62 65 20  each already be 
1a60: 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e  in sorted order.
1a70: 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75 63  .*/.static struc
1a80: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 72  t RowSetEntry *r
1a90: 6f 77 53 65 74 4d 65 72 67 65 28 0a 20 20 73 74  owSetMerge(.  st
1aa0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1ab0: 20 2a 70 41 2c 20 20 20 20 2f 2a 20 46 69 72 73   *pA,    /* Firs
1ac0: 74 20 73 6f 72 74 65 64 20 6c 69 73 74 20 74 6f  t sorted list to
1ad0: 20 62 65 20 6d 65 72 67 65 64 20 2a 2f 0a 20 20   be merged */.  
1ae0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1af0: 72 79 20 2a 70 42 20 20 20 20 20 2f 2a 20 53 65  ry *pB     /* Se
1b00: 63 6f 6e 64 20 73 6f 72 74 65 64 20 6c 69 73 74  cond sorted list
1b10: 20 74 6f 20 62 65 20 6d 65 72 67 65 64 20 2a 2f   to be merged */
1b20: 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  .){.  struct Row
1b30: 53 65 74 45 6e 74 72 79 20 68 65 61 64 3b 0a 20  SetEntry head;. 
1b40: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
1b50: 74 72 79 20 2a 70 54 61 69 6c 3b 0a 0a 20 20 70  try *pTail;..  p
1b60: 54 61 69 6c 20 3d 20 26 68 65 61 64 3b 0a 20 20  Tail = &head;.  
1b70: 77 68 69 6c 65 28 20 70 41 20 26 26 20 70 42 20  while( pA && pB 
1b80: 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70  ){.    assert( p
1b90: 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c 7c 20  A->pRight==0 || 
1ba0: 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69 67 68  pA->v<=pA->pRigh
1bb0: 74 2d 3e 76 20 29 3b 0a 20 20 20 20 61 73 73 65  t->v );.    asse
1bc0: 72 74 28 20 70 42 2d 3e 70 52 69 67 68 74 3d 3d  rt( pB->pRight==
1bd0: 30 20 7c 7c 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e  0 || pB->v<=pB->
1be0: 70 52 69 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20  pRight->v );.   
1bf0: 20 69 66 28 20 70 41 2d 3e 76 3c 70 42 2d 3e 76   if( pA->v<pB->v
1c00: 20 29 7b 0a 20 20 20 20 20 20 70 54 61 69 6c 2d   ){.      pTail-
1c10: 3e 70 52 69 67 68 74 20 3d 20 70 41 3b 0a 20 20  >pRight = pA;.  
1c20: 20 20 20 20 70 41 20 3d 20 70 41 2d 3e 70 52 69      pA = pA->pRi
1c30: 67 68 74 3b 0a 20 20 20 20 20 20 70 54 61 69 6c  ght;.      pTail
1c40: 20 3d 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74   = pTail->pRight
1c50: 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20  ;.    }else if( 
1c60: 70 42 2d 3e 76 3c 70 41 2d 3e 76 20 29 7b 0a 20  pB->v<pA->v ){. 
1c70: 20 20 20 20 20 70 54 61 69 6c 2d 3e 70 52 69 67       pTail->pRig
1c80: 68 74 20 3d 20 70 42 3b 0a 20 20 20 20 20 20 70  ht = pB;.      p
1c90: 42 20 3d 20 70 42 2d 3e 70 52 69 67 68 74 3b 0a  B = pB->pRight;.
1ca0: 20 20 20 20 20 20 70 54 61 69 6c 20 3d 20 70 54        pTail = pT
1cb0: 61 69 6c 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  ail->pRight;.   
1cc0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 70 41   }else{.      pA
1cd0: 20 3d 20 70 41 2d 3e 70 52 69 67 68 74 3b 0a 20   = pA->pRight;. 
1ce0: 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70     }.  }.  if( p
1cf0: 41 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  A ){.    assert(
1d00: 20 70 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c   pA->pRight==0 |
1d10: 7c 20 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69  | pA->v<=pA->pRi
1d20: 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70 54  ght->v );.    pT
1d30: 61 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 41  ail->pRight = pA
1d40: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61  ;.  }else{.    a
1d50: 73 73 65 72 74 28 20 70 42 3d 3d 30 20 7c 7c 20  ssert( pB==0 || 
1d60: 70 42 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c 7c  pB->pRight==0 ||
1d70: 20 70 42 2d 3e 76 3c 3d 70 42 2d 3e 70 52 69 67   pB->v<=pB->pRig
1d80: 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 70 54 61  ht->v );.    pTa
1d90: 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42 3b  il->pRight = pB;
1da0: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 65  .  }.  return he
1db0: 61 64 2e 70 52 69 67 68 74 3b 0a 7d 0a 0a 2f 2a  ad.pRight;.}../*
1dc0: 0a 2a 2a 20 53 6f 72 74 20 61 6c 6c 20 65 6c 65  .** Sort all ele
1dd0: 6d 65 6e 74 73 20 6f 6e 20 74 68 65 20 70 45 6e  ments on the pEn
1de0: 74 72 79 20 6c 69 73 74 20 6f 66 20 74 68 65 20  try list of the 
1df0: 52 6f 77 53 65 74 20 69 6e 74 6f 20 61 73 63 65  RowSet into asce
1e00: 6e 64 69 6e 67 20 6f 72 64 65 72 2e 0a 2a 2f 20  nding order..*/ 
1e10: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72 6f 77  .static void row
1e20: 53 65 74 53 6f 72 74 28 52 6f 77 53 65 74 20 2a  SetSort(RowSet *
1e30: 70 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69  p){.  unsigned i
1e40: 6e 74 20 69 3b 0a 20 20 73 74 72 75 63 74 20 52  nt i;.  struct R
1e50: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 45 6e 74  owSetEntry *pEnt
1e60: 72 79 3b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  ry;.  struct Row
1e70: 53 65 74 45 6e 74 72 79 20 2a 61 42 75 63 6b 65  SetEntry *aBucke
1e80: 74 5b 34 30 5d 3b 0a 0a 20 20 61 73 73 65 72 74  t[40];..  assert
1e90: 28 20 70 2d 3e 69 73 53 6f 72 74 65 64 3d 3d 30  ( p->isSorted==0
1ea0: 20 29 3b 0a 20 20 6d 65 6d 73 65 74 28 61 42 75   );.  memset(aBu
1eb0: 63 6b 65 74 2c 20 30 2c 20 73 69 7a 65 6f 66 28  cket, 0, sizeof(
1ec0: 61 42 75 63 6b 65 74 29 29 3b 0a 20 20 77 68 69  aBucket));.  whi
1ed0: 6c 65 28 20 70 2d 3e 70 45 6e 74 72 79 20 29 7b  le( p->pEntry ){
1ee0: 0a 20 20 20 20 70 45 6e 74 72 79 20 3d 20 70 2d  .    pEntry = p-
1ef0: 3e 70 45 6e 74 72 79 3b 0a 20 20 20 20 70 2d 3e  >pEntry;.    p->
1f00: 70 45 6e 74 72 79 20 3d 20 70 45 6e 74 72 79 2d  pEntry = pEntry-
1f10: 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70 45 6e  >pRight;.    pEn
1f20: 74 72 79 2d 3e 70 52 69 67 68 74 20 3d 20 30 3b  try->pRight = 0;
1f30: 0a 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 61 42  .    for(i=0; aB
1f40: 75 63 6b 65 74 5b 69 5d 3b 20 69 2b 2b 29 7b 0a  ucket[i]; i++){.
1f50: 20 20 20 20 20 20 70 45 6e 74 72 79 20 3d 20 72        pEntry = r
1f60: 6f 77 53 65 74 4d 65 72 67 65 28 61 42 75 63 6b  owSetMerge(aBuck
1f70: 65 74 5b 69 5d 2c 20 70 45 6e 74 72 79 29 3b 0a  et[i], pEntry);.
1f80: 20 20 20 20 20 20 61 42 75 63 6b 65 74 5b 69 5d        aBucket[i]
1f90: 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20 20   = 0;.    }.    
1fa0: 61 42 75 63 6b 65 74 5b 69 5d 20 3d 20 70 45 6e  aBucket[i] = pEn
1fb0: 74 72 79 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72  try;.  }.  pEntr
1fc0: 79 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30  y = 0;.  for(i=0
1fd0: 3b 20 69 3c 73 69 7a 65 6f 66 28 61 42 75 63 6b  ; i<sizeof(aBuck
1fe0: 65 74 29 2f 73 69 7a 65 6f 66 28 61 42 75 63 6b  et)/sizeof(aBuck
1ff0: 65 74 5b 30 5d 29 3b 20 69 2b 2b 29 7b 0a 20 20  et[0]); i++){.  
2000: 20 20 70 45 6e 74 72 79 20 3d 20 72 6f 77 53 65    pEntry = rowSe
2010: 74 4d 65 72 67 65 28 70 45 6e 74 72 79 2c 20 61  tMerge(pEntry, a
2020: 42 75 63 6b 65 74 5b 69 5d 29 3b 0a 20 20 7d 0a  Bucket[i]);.  }.
2030: 20 20 70 2d 3e 70 45 6e 74 72 79 20 3d 20 70 45    p->pEntry = pE
2040: 6e 74 72 79 3b 0a 20 20 70 2d 3e 70 4c 61 73 74  ntry;.  p->pLast
2050: 20 3d 20 30 3b 0a 20 20 70 2d 3e 69 73 53 6f 72   = 0;.  p->isSor
2060: 74 65 64 20 3d 20 31 3b 0a 7d 0a 0a 0a 2f 2a 0a  ted = 1;.}.../*.
2070: 2a 2a 20 54 68 65 20 69 6e 70 75 74 2c 20 70 49  ** The input, pI
2080: 6e 2c 20 69 73 20 61 20 62 69 6e 61 72 79 20 74  n, is a binary t
2090: 72 65 65 20 28 6f 72 20 73 75 62 74 72 65 65 29  ree (or subtree)
20a0: 20 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79 20   of RowSetEntry 
20b0: 6f 62 6a 65 63 74 73 2e 0a 2a 2a 20 43 6f 6e 76  objects..** Conv
20c0: 65 72 74 20 74 68 69 73 20 74 72 65 65 20 69 6e  ert this tree in
20d0: 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  to a linked list
20e0: 20 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 74 68   connected by th
20f0: 65 20 70 52 69 67 68 74 20 70 6f 69 6e 74 65 72  e pRight pointer
2100: 73 0a 2a 2a 20 61 6e 64 20 72 65 74 75 72 6e 20  s.** and return 
2110: 70 6f 69 6e 74 65 72 73 20 74 6f 20 74 68 65 20  pointers to the 
2120: 66 69 72 73 74 20 61 6e 64 20 6c 61 73 74 20 65  first and last e
2130: 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 6e  lements of the n
2140: 65 77 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 74  ew list..*/.stat
2150: 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74 54 72  ic void rowSetTr
2160: 65 65 54 6f 4c 69 73 74 28 0a 20 20 73 74 72 75  eeToList(.  stru
2170: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2180: 70 49 6e 2c 20 20 20 20 20 20 20 20 20 2f 2a 20  pIn,         /* 
2190: 52 6f 6f 74 20 6f 66 20 74 68 65 20 69 6e 70 75  Root of the inpu
21a0: 74 20 74 72 65 65 20 2a 2f 0a 20 20 73 74 72 75  t tree */.  stru
21b0: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
21c0: 2a 70 70 46 69 72 73 74 2c 20 20 20 20 2f 2a 20  *ppFirst,    /* 
21d0: 57 72 69 74 65 20 68 65 61 64 20 6f 66 20 74 68  Write head of th
21e0: 65 20 6f 75 74 70 75 74 20 6c 69 73 74 20 68 65  e output list he
21f0: 72 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52  re */.  struct R
2200: 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a 70 70 4c  owSetEntry **ppL
2210: 61 73 74 20 20 20 20 20 20 2f 2a 20 57 72 69 74  ast      /* Writ
2220: 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20 6f 75  e tail of the ou
2230: 74 70 75 74 20 6c 69 73 74 20 68 65 72 65 20 2a  tput list here *
2240: 2f 0a 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70  /.){.  assert( p
2250: 49 6e 21 3d 30 20 29 3b 0a 20 20 69 66 28 20 70  In!=0 );.  if( p
2260: 49 6e 2d 3e 70 4c 65 66 74 20 29 7b 0a 20 20 20  In->pLeft ){.   
2270: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
2280: 74 72 79 20 2a 70 3b 0a 20 20 20 20 72 6f 77 53  try *p;.    rowS
2290: 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70 49 6e  etTreeToList(pIn
22a0: 2d 3e 70 4c 65 66 74 2c 20 70 70 46 69 72 73 74  ->pLeft, ppFirst
22b0: 2c 20 26 70 29 3b 0a 20 20 20 20 70 2d 3e 70 52  , &p);.    p->pR
22c0: 69 67 68 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 65  ight = pIn;.  }e
22d0: 6c 73 65 7b 0a 20 20 20 20 2a 70 70 46 69 72 73  lse{.    *ppFirs
22e0: 74 20 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20 69  t = pIn;.  }.  i
22f0: 66 28 20 70 49 6e 2d 3e 70 52 69 67 68 74 20 29  f( pIn->pRight )
2300: 7b 0a 20 20 20 20 72 6f 77 53 65 74 54 72 65 65  {.    rowSetTree
2310: 54 6f 4c 69 73 74 28 70 49 6e 2d 3e 70 52 69 67  ToList(pIn->pRig
2320: 68 74 2c 20 26 70 49 6e 2d 3e 70 52 69 67 68 74  ht, &pIn->pRight
2330: 2c 20 70 70 4c 61 73 74 29 3b 0a 20 20 7d 65 6c  , ppLast);.  }el
2340: 73 65 7b 0a 20 20 20 20 2a 70 70 4c 61 73 74 20  se{.    *ppLast 
2350: 3d 20 70 49 6e 3b 0a 20 20 7d 0a 20 20 61 73 73  = pIn;.  }.  ass
2360: 65 72 74 28 20 28 2a 70 70 4c 61 73 74 29 2d 3e  ert( (*ppLast)->
2370: 70 52 69 67 68 74 3d 3d 30 20 29 3b 0a 7d 0a 0a  pRight==0 );.}..
2380: 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65 72 74 20 61  ./*.** Convert a
2390: 20 73 6f 72 74 65 64 20 6c 69 73 74 20 6f 66 20   sorted list of 
23a0: 65 6c 65 6d 65 6e 74 73 20 28 63 6f 6e 6e 65 63  elements (connec
23b0: 74 65 64 20 62 79 20 70 52 69 67 68 74 29 20 69  ted by pRight) i
23c0: 6e 74 6f 20 61 20 62 69 6e 61 72 79 0a 2a 2a 20  nto a binary.** 
23d0: 74 72 65 65 20 77 69 74 68 20 64 65 70 74 68 20  tree with depth 
23e0: 6f 66 20 69 44 65 70 74 68 2e 20 20 41 20 64 65  of iDepth.  A de
23f0: 70 74 68 20 6f 66 20 31 20 6d 65 61 6e 73 20 74  pth of 1 means t
2400: 68 65 20 74 72 65 65 20 63 6f 6e 74 61 69 6e 73  he tree contains
2410: 20 61 20 73 69 6e 67 6c 65 0a 2a 2a 20 6e 6f 64   a single.** nod
2420: 65 20 74 61 6b 65 6e 20 66 72 6f 6d 20 74 68 65  e taken from the
2430: 20 68 65 61 64 20 6f 66 20 2a 70 70 4c 69 73 74   head of *ppList
2440: 2e 20 20 41 20 64 65 70 74 68 20 6f 66 20 32 20  .  A depth of 2 
2450: 6d 65 61 6e 73 20 61 20 74 72 65 65 20 77 69 74  means a tree wit
2460: 68 0a 2a 2a 20 74 68 72 65 65 20 6e 6f 64 65 73  h.** three nodes
2470: 2e 20 20 41 6e 64 20 73 6f 20 66 6f 72 74 68 2e  .  And so forth.
2480: 0a 2a 2a 0a 2a 2a 20 55 73 65 20 61 73 20 6d 61  .**.** Use as ma
2490: 6e 79 20 65 6e 74 72 69 65 73 20 66 72 6f 6d 20  ny entries from 
24a0: 74 68 65 20 69 6e 70 75 74 20 6c 69 73 74 20 61  the input list a
24b0: 73 20 72 65 71 75 69 72 65 64 20 61 6e 64 20 75  s required and u
24c0: 70 64 61 74 65 20 74 68 65 0a 2a 2a 20 2a 70 70  pdate the.** *pp
24d0: 4c 69 73 74 20 74 6f 20 70 6f 69 6e 74 20 74 6f  List to point to
24e0: 20 74 68 65 20 75 6e 75 73 65 64 20 65 6c 65 6d   the unused elem
24f0: 65 6e 74 73 20 6f 66 20 74 68 65 20 6c 69 73 74  ents of the list
2500: 2e 20 20 49 66 20 74 68 65 20 69 6e 70 75 74 0a  .  If the input.
2510: 2a 2a 20 6c 69 73 74 20 63 6f 6e 74 61 69 6e 73  ** list contains
2520: 20 74 6f 6f 20 66 65 77 20 65 6c 65 6d 65 6e 74   too few element
2530: 73 2c 20 74 68 65 6e 20 63 6f 6e 73 74 72 75 63  s, then construc
2540: 74 20 61 6e 20 69 6e 63 6f 6d 70 6c 65 74 65 20  t an incomplete 
2550: 74 72 65 65 0a 2a 2a 20 61 6e 64 20 6c 65 61 76  tree.** and leav
2560: 65 20 2a 70 70 4c 69 73 74 20 73 65 74 20 74 6f  e *ppList set to
2570: 20 4e 55 4c 4c 2e 0a 2a 2a 0a 2a 2a 20 52 65 74   NULL..**.** Ret
2580: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
2590: 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65   the root of the
25a0: 20 63 6f 6e 73 74 72 75 63 74 65 64 20 62 69 6e   constructed bin
25b0: 61 72 79 20 74 72 65 65 2e 0a 2a 2f 0a 73 74 61  ary tree..*/.sta
25c0: 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53 65  tic struct RowSe
25d0: 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 4e 44  tEntry *rowSetND
25e0: 65 65 70 54 72 65 65 28 0a 20 20 73 74 72 75 63  eepTree(.  struc
25f0: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 2a  t RowSetEntry **
2600: 70 70 4c 69 73 74 2c 0a 20 20 69 6e 74 20 69 44  ppList,.  int iD
2610: 65 70 74 68 0a 29 7b 0a 20 20 73 74 72 75 63 74  epth.){.  struct
2620: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 3b   RowSetEntry *p;
2630: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f 74           /* Root
2640: 20 6f 66 20 74 68 65 20 6e 65 77 20 74 72 65 65   of the new tree
2650: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
2660: 53 65 74 45 6e 74 72 79 20 2a 70 4c 65 66 74 3b  SetEntry *pLeft;
2670: 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73 75 62       /* Left sub
2680: 74 72 65 65 20 2a 2f 0a 20 20 69 66 28 20 2a 70  tree */.  if( *p
2690: 70 4c 69 73 74 3d 3d 30 20 29 7b 0a 20 20 20 20  pList==0 ){.    
26a0: 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a 20 20  return 0;.  }.  
26b0: 69 66 28 20 69 44 65 70 74 68 3d 3d 31 20 29 7b  if( iDepth==1 ){
26c0: 0a 20 20 20 20 70 20 3d 20 2a 70 70 4c 69 73 74  .    p = *ppList
26d0: 3b 0a 20 20 20 20 2a 70 70 4c 69 73 74 20 3d 20  ;.    *ppList = 
26e0: 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70  p->pRight;.    p
26f0: 2d 3e 70 4c 65 66 74 20 3d 20 70 2d 3e 70 52 69  ->pLeft = p->pRi
2700: 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 72 65 74  ght = 0;.    ret
2710: 75 72 6e 20 70 3b 0a 20 20 7d 0a 20 20 70 4c 65  urn p;.  }.  pLe
2720: 66 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65 70  ft = rowSetNDeep
2730: 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44 65  Tree(ppList, iDe
2740: 70 74 68 2d 31 29 3b 0a 20 20 70 20 3d 20 2a 70  pth-1);.  p = *p
2750: 70 4c 69 73 74 3b 0a 20 20 69 66 28 20 70 3d 3d  pList;.  if( p==
2760: 30 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20  0 ){.    return 
2770: 70 4c 65 66 74 3b 0a 20 20 7d 0a 20 20 70 2d 3e  pLeft;.  }.  p->
2780: 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b 0a 20  pLeft = pLeft;. 
2790: 20 2a 70 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52   *ppList = p->pR
27a0: 69 67 68 74 3b 0a 20 20 70 2d 3e 70 52 69 67 68  ight;.  p->pRigh
27b0: 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65 70 54  t = rowSetNDeepT
27c0: 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44 65 70  ree(ppList, iDep
27d0: 74 68 2d 31 29 3b 0a 20 20 72 65 74 75 72 6e 20  th-1);.  return 
27e0: 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76  p;.}../*.** Conv
27f0: 65 72 74 20 61 20 73 6f 72 74 65 64 20 6c 69 73  ert a sorted lis
2800: 74 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e  t of elements in
2810: 74 6f 20 61 20 62 69 6e 61 72 79 20 74 72 65 65  to a binary tree
2820: 2e 20 4d 61 6b 65 20 74 68 65 20 74 72 65 65 0a  . Make the tree.
2830: 2a 2a 20 61 73 20 64 65 65 70 20 61 73 20 69 74  ** as deep as it
2840: 20 6e 65 65 64 73 20 74 6f 20 62 65 20 69 6e 20   needs to be in 
2850: 6f 72 64 65 72 20 74 6f 20 63 6f 6e 74 61 69 6e  order to contain
2860: 20 74 68 65 20 65 6e 74 69 72 65 20 6c 69 73 74   the entire list
2870: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75  ..*/.static stru
2880: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2890: 72 6f 77 53 65 74 4c 69 73 74 54 6f 54 72 65 65  rowSetListToTree
28a0: 28 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e  (struct RowSetEn
28b0: 74 72 79 20 2a 70 4c 69 73 74 29 7b 0a 20 20 69  try *pList){.  i
28c0: 6e 74 20 69 44 65 70 74 68 3b 20 20 20 20 20 20  nt iDepth;      
28d0: 20 20 20 20 20 2f 2a 20 44 65 70 74 68 20 6f 66       /* Depth of
28e0: 20 74 68 65 20 74 72 65 65 20 73 6f 20 66 61 72   the tree so far
28f0: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
2900: 53 65 74 45 6e 74 72 79 20 2a 70 3b 20 20 20 20  SetEntry *p;    
2910: 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 74 72     /* Current tr
2920: 65 65 20 72 6f 6f 74 20 2a 2f 0a 20 20 73 74 72  ee root */.  str
2930: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20  uct RowSetEntry 
2940: 2a 70 4c 65 66 74 3b 20 20 20 2f 2a 20 4c 65 66  *pLeft;   /* Lef
2950: 74 20 73 75 62 74 72 65 65 20 2a 2f 0a 0a 20 20  t subtree */..  
2960: 61 73 73 65 72 74 28 20 70 4c 69 73 74 21 3d 30  assert( pList!=0
2970: 20 29 3b 0a 20 20 70 20 3d 20 70 4c 69 73 74 3b   );.  p = pList;
2980: 0a 20 20 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52  .  pList = p->pR
2990: 69 67 68 74 3b 0a 20 20 70 2d 3e 70 4c 65 66 74  ight;.  p->pLeft
29a0: 20 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 30   = p->pRight = 0
29b0: 3b 0a 20 20 66 6f 72 28 69 44 65 70 74 68 3d 31  ;.  for(iDepth=1
29c0: 3b 20 70 4c 69 73 74 3b 20 69 44 65 70 74 68 2b  ; pList; iDepth+
29d0: 2b 29 7b 0a 20 20 20 20 70 4c 65 66 74 20 3d 20  +){.    pLeft = 
29e0: 70 3b 0a 20 20 20 20 70 20 3d 20 70 4c 69 73 74  p;.    p = pList
29f0: 3b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20 70 2d  ;.    pList = p-
2a00: 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70 2d 3e  >pRight;.    p->
2a10: 70 4c 65 66 74 20 3d 20 70 4c 65 66 74 3b 0a 20  pLeft = pLeft;. 
2a20: 20 20 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 72     p->pRight = r
2a30: 6f 77 53 65 74 4e 44 65 65 70 54 72 65 65 28 26  owSetNDeepTree(&
2a40: 70 4c 69 73 74 2c 20 69 44 65 70 74 68 29 3b 0a  pList, iDepth);.
2a50: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b 0a    }.  return p;.
2a60: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e 76 65 72 74  }../*.** Convert
2a70: 20 74 68 65 20 6c 69 73 74 20 69 6e 20 70 2d 3e   the list in p->
2a80: 70 45 6e 74 72 79 20 69 6e 74 6f 20 61 20 73 6f  pEntry into a so
2a90: 72 74 65 64 20 6c 69 73 74 20 69 66 20 69 74 20  rted list if it 
2aa0: 69 73 20 6e 6f 74 0a 2a 2a 20 73 6f 72 74 65 64  is not.** sorted
2ab0: 20 61 6c 72 65 61 64 79 2e 20 20 49 66 20 74 68   already.  If th
2ac0: 65 72 65 20 69 73 20 61 20 62 69 6e 61 72 79 20  ere is a binary 
2ad0: 74 72 65 65 20 6f 6e 20 70 2d 3e 70 54 72 65 65  tree on p->pTree
2ae0: 2c 20 74 68 65 6e 0a 2a 2a 20 63 6f 6e 76 65 72  , then.** conver
2af0: 74 20 69 74 20 69 6e 74 6f 20 61 20 6c 69 73 74  t it into a list
2b00: 20 74 6f 6f 20 61 6e 64 20 6d 65 72 67 65 20 69   too and merge i
2b10: 74 20 69 6e 74 6f 20 74 68 65 20 70 2d 3e 70 45  t into the p->pE
2b20: 6e 74 72 79 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74  ntry list..*/.st
2b30: 61 74 69 63 20 76 6f 69 64 20 72 6f 77 53 65 74  atic void rowSet
2b40: 54 6f 4c 69 73 74 28 52 6f 77 53 65 74 20 2a 70  ToList(RowSet *p
2b50: 29 7b 0a 20 20 69 66 28 20 21 70 2d 3e 69 73 53  ){.  if( !p->isS
2b60: 6f 72 74 65 64 20 29 7b 0a 20 20 20 20 72 6f 77  orted ){.    row
2b70: 53 65 74 53 6f 72 74 28 70 29 3b 0a 20 20 7d 0a  SetSort(p);.  }.
2b80: 20 20 69 66 28 20 70 2d 3e 70 54 72 65 65 20 29    if( p->pTree )
2b90: 7b 0a 20 20 20 20 73 74 72 75 63 74 20 52 6f 77  {.    struct Row
2ba0: 53 65 74 45 6e 74 72 79 20 2a 70 48 65 61 64 2c  SetEntry *pHead,
2bb0: 20 2a 70 54 61 69 6c 3b 0a 20 20 20 20 72 6f 77   *pTail;.    row
2bc0: 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70 2d  SetTreeToList(p-
2bd0: 3e 70 54 72 65 65 2c 20 26 70 48 65 61 64 2c 20  >pTree, &pHead, 
2be0: 26 70 54 61 69 6c 29 3b 0a 20 20 20 20 70 2d 3e  &pTail);.    p->
2bf0: 70 54 72 65 65 20 3d 20 30 3b 0a 20 20 20 20 70  pTree = 0;.    p
2c00: 2d 3e 70 45 6e 74 72 79 20 3d 20 72 6f 77 53 65  ->pEntry = rowSe
2c10: 74 4d 65 72 67 65 28 70 2d 3e 70 45 6e 74 72 79  tMerge(p->pEntry
2c20: 2c 20 70 48 65 61 64 29 3b 0a 20 20 7d 0a 7d 0a  , pHead);.  }.}.
2c30: 0a 2f 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20 74  ./*.** Extract t
2c40: 68 65 20 73 6d 61 6c 6c 65 73 74 20 65 6c 65 6d  he smallest elem
2c50: 65 6e 74 20 66 72 6f 6d 20 74 68 65 20 52 6f 77  ent from the Row
2c60: 53 65 74 2e 0a 2a 2a 20 57 72 69 74 65 20 74 68  Set..** Write th
2c70: 65 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 2a  e element into *
2c80: 70 52 6f 77 69 64 2e 20 20 52 65 74 75 72 6e 20  pRowid.  Return 
2c90: 31 20 6f 6e 20 73 75 63 63 65 73 73 2e 20 20 52  1 on success.  R
2ca0: 65 74 75 72 6e 0a 2a 2a 20 30 20 69 66 20 74 68  eturn.** 0 if th
2cb0: 65 20 52 6f 77 53 65 74 20 69 73 20 61 6c 72 65  e RowSet is alre
2cc0: 61 64 79 20 65 6d 70 74 79 2e 0a 2a 2a 0a 2a 2a  ady empty..**.**
2cd0: 20 41 66 74 65 72 20 74 68 69 73 20 72 6f 75 74   After this rout
2ce0: 69 6e 65 20 68 61 73 20 62 65 65 6e 20 63 61 6c  ine has been cal
2cf0: 6c 65 64 2c 20 74 68 65 20 73 71 6c 69 74 65 33  led, the sqlite3
2d00: 52 6f 77 53 65 74 49 6e 73 65 72 74 28 29 0a 2a  RowSetInsert().*
2d10: 2a 20 72 6f 75 74 69 6e 65 20 6d 61 79 20 6e 6f  * routine may no
2d20: 74 20 62 65 20 63 61 6c 6c 65 64 20 61 67 61 69  t be called agai
2d30: 6e 2e 20 20 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  n.  .*/.int sqli
2d40: 74 65 33 52 6f 77 53 65 74 4e 65 78 74 28 52 6f  te3RowSetNext(Ro
2d50: 77 53 65 74 20 2a 70 2c 20 69 36 34 20 2a 70 52  wSet *p, i64 *pR
2d60: 6f 77 69 64 29 7b 0a 20 20 72 6f 77 53 65 74 54  owid){.  rowSetT
2d70: 6f 4c 69 73 74 28 70 29 3b 0a 20 20 69 66 28 20  oList(p);.  if( 
2d80: 70 2d 3e 70 45 6e 74 72 79 20 29 7b 0a 20 20 20  p->pEntry ){.   
2d90: 20 2a 70 52 6f 77 69 64 20 3d 20 70 2d 3e 70 45   *pRowid = p->pE
2da0: 6e 74 72 79 2d 3e 76 3b 0a 20 20 20 20 70 2d 3e  ntry->v;.    p->
2db0: 70 45 6e 74 72 79 20 3d 20 70 2d 3e 70 45 6e 74  pEntry = p->pEnt
2dc0: 72 79 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20  ry->pRight;.    
2dd0: 69 66 28 20 70 2d 3e 70 45 6e 74 72 79 3d 3d 30  if( p->pEntry==0
2de0: 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65   ){.      sqlite
2df0: 33 52 6f 77 53 65 74 43 6c 65 61 72 28 70 29 3b  3RowSetClear(p);
2e00: 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72  .    }.    retur
2e10: 6e 20 31 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  n 1;.  }else{.  
2e20: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 7d 0a    return 0;.  }.
2e30: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65 63 6b 20 74  }../*.** Check t
2e40: 6f 20 73 65 65 20 69 66 20 65 6c 65 6d 65 6e 74  o see if element
2e50: 20 69 52 6f 77 69 64 20 77 61 73 20 69 6e 73 65   iRowid was inse
2e60: 72 74 65 64 20 69 6e 74 6f 20 74 68 65 20 74 68  rted into the th
2e70: 65 20 72 6f 77 73 65 74 20 61 73 0a 2a 2a 20 70  e rowset as.** p
2e80: 61 72 74 20 6f 66 20 61 6e 79 20 69 6e 73 65 72  art of any inser
2e90: 74 20 62 61 74 63 68 20 70 72 69 6f 72 20 74 6f  t batch prior to
2ea0: 20 69 42 61 74 63 68 2e 20 20 52 65 74 75 72 6e   iBatch.  Return
2eb0: 20 31 20 6f 72 20 30 2e 0a 2a 2f 0a 69 6e 74 20   1 or 0..*/.int 
2ec0: 73 71 6c 69 74 65 33 52 6f 77 53 65 74 54 65 73  sqlite3RowSetTes
2ed0: 74 28 52 6f 77 53 65 74 20 2a 70 52 6f 77 53 65  t(RowSet *pRowSe
2ee0: 74 2c 20 75 38 20 69 42 61 74 63 68 2c 20 73 71  t, u8 iBatch, sq
2ef0: 6c 69 74 65 33 5f 69 6e 74 36 34 20 69 52 6f 77  lite3_int64 iRow
2f00: 69 64 29 7b 0a 20 20 73 74 72 75 63 74 20 52 6f  id){.  struct Ro
2f10: 77 53 65 74 45 6e 74 72 79 20 2a 70 3b 0a 20 20  wSetEntry *p;.  
2f20: 69 66 28 20 69 42 61 74 63 68 21 3d 70 52 6f 77  if( iBatch!=pRow
2f30: 53 65 74 2d 3e 69 42 61 74 63 68 20 29 7b 0a 20  Set->iBatch ){. 
2f40: 20 20 20 69 66 28 20 70 52 6f 77 53 65 74 2d 3e     if( pRowSet->
2f50: 70 45 6e 74 72 79 20 29 7b 0a 20 20 20 20 20 20  pEntry ){.      
2f60: 72 6f 77 53 65 74 54 6f 4c 69 73 74 28 70 52 6f  rowSetToList(pRo
2f70: 77 53 65 74 29 3b 0a 20 20 20 20 20 20 70 52 6f  wSet);.      pRo
2f80: 77 53 65 74 2d 3e 70 54 72 65 65 20 3d 20 72 6f  wSet->pTree = ro
2f90: 77 53 65 74 4c 69 73 74 54 6f 54 72 65 65 28 70  wSetListToTree(p
2fa0: 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 29 3b  RowSet->pEntry);
2fb0: 0a 20 20 20 20 20 20 70 52 6f 77 53 65 74 2d 3e  .      pRowSet->
2fc0: 70 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 20 20  pEntry = 0;.    
2fd0: 20 20 70 52 6f 77 53 65 74 2d 3e 70 4c 61 73 74    pRowSet->pLast
2fe0: 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20 20   = 0;.    }.    
2ff0: 70 52 6f 77 53 65 74 2d 3e 69 42 61 74 63 68 20  pRowSet->iBatch 
3000: 3d 20 69 42 61 74 63 68 3b 0a 20 20 7d 0a 20 20  = iBatch;.  }.  
3010: 70 20 3d 20 70 52 6f 77 53 65 74 2d 3e 70 54 72  p = pRowSet->pTr
3020: 65 65 3b 0a 20 20 77 68 69 6c 65 28 20 70 20 29  ee;.  while( p )
3030: 7b 0a 20 20 20 20 69 66 28 20 70 2d 3e 76 3c 69  {.    if( p->v<i
3040: 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 20 20 70  Rowid ){.      p
3050: 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20   = p->pRight;.  
3060: 20 20 7d 65 6c 73 65 20 69 66 28 20 70 2d 3e 76    }else if( p->v
3070: 3e 69 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 20  >iRowid ){.     
3080: 20 70 20 3d 20 70 2d 3e 70 4c 65 66 74 3b 0a 20   p = p->pLeft;. 
3090: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20     }else{.      
30a0: 72 65 74 75 72 6e 20 31 3b 0a 20 20 20 20 7d 0a  return 1;.    }.
30b0: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a    }.  return 0;.
30c0: 7d 0a                                            }.