/ Hex Artifact Content
Login

Artifact d977b011993aaea002cab3e0bb2ce50cf346000dff94e944d547b989f4b1fe93:


0000: 2f 2a 0a 2a 2a 20 32 30 30 38 20 44 65 63 65 6d  /*.** 2008 Decem
0010: 62 65 72 20 33 0a 2a 2a 0a 2a 2a 20 54 68 65 20  ber 3.**.** The 
0020: 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73  author disclaims
0030: 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68   copyright to th
0040: 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20  is source code. 
0050: 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20   In place of.** 
0060: 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20  a legal notice, 
0070: 68 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69  here is a blessi
0080: 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79  ng:.**.**    May
0090: 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64   you do good and
00a0: 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20   not evil..**   
00b0: 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f   May you find fo
00c0: 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f  rgiveness for yo
00d0: 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69  urself and forgi
00e0: 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20  ve others..**   
00f0: 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66   May you share f
0100: 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b  reely, never tak
0110: 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f  ing more than yo
0120: 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a  u give..**.*****
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20  ****.**.** This 
0180: 6d 6f 64 75 6c 65 20 69 6d 70 6c 65 6d 65 6e 74  module implement
0190: 73 20 61 6e 20 6f 62 6a 65 63 74 20 77 65 20 63  s an object we c
01a0: 61 6c 6c 20 61 20 22 52 6f 77 53 65 74 22 2e 0a  all a "RowSet"..
01b0: 2a 2a 0a 2a 2a 20 54 68 65 20 52 6f 77 53 65 74  **.** The RowSet
01c0: 20 6f 62 6a 65 63 74 20 69 73 20 61 20 63 6f 6c   object is a col
01d0: 6c 65 63 74 69 6f 6e 20 6f 66 20 72 6f 77 69 64  lection of rowid
01e0: 73 2e 20 20 52 6f 77 69 64 73 0a 2a 2a 20 61 72  s.  Rowids.** ar
01f0: 65 20 69 6e 73 65 72 74 65 64 20 69 6e 74 6f 20  e inserted into 
0200: 74 68 65 20 52 6f 77 53 65 74 20 69 6e 20 61 6e  the RowSet in an
0210: 20 61 72 62 69 74 72 61 72 79 20 6f 72 64 65 72   arbitrary order
0220: 2e 20 20 49 6e 73 65 72 74 73 0a 2a 2a 20 63 61  .  Inserts.** ca
0230: 6e 20 62 65 20 69 6e 74 65 72 6d 69 78 65 64 20  n be intermixed 
0240: 77 69 74 68 20 74 65 73 74 73 20 74 6f 20 73 65  with tests to se
0250: 65 20 69 66 20 61 20 67 69 76 65 6e 20 72 6f 77  e if a given row
0260: 69 64 20 68 61 73 20 62 65 65 6e 0a 2a 2a 20 70  id has been.** p
0270: 72 65 76 69 6f 75 73 6c 79 20 69 6e 73 65 72 74  reviously insert
0280: 65 64 20 69 6e 74 6f 20 74 68 65 20 52 6f 77 53  ed into the RowS
0290: 65 74 2e 0a 2a 2a 0a 2a 2a 20 41 66 74 65 72 20  et..**.** After 
02a0: 61 6c 6c 20 69 6e 73 65 72 74 73 20 61 72 65 20  all inserts are 
02b0: 66 69 6e 69 73 68 65 64 2c 20 69 74 20 69 73 20  finished, it is 
02c0: 70 6f 73 73 69 62 6c 65 20 74 6f 20 65 78 74 72  possible to extr
02d0: 61 63 74 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65  act the.** eleme
02e0: 6e 74 73 20 6f 66 20 74 68 65 20 52 6f 77 53 65  nts of the RowSe
02f0: 74 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  t in sorted orde
0300: 72 2e 20 20 4f 6e 63 65 20 74 68 69 73 20 65 78  r.  Once this ex
0310: 74 72 61 63 74 69 6f 6e 0a 2a 2a 20 70 72 6f 63  traction.** proc
0320: 65 73 73 20 68 61 73 20 73 74 61 72 74 65 64 2c  ess has started,
0330: 20 6e 6f 20 6e 65 77 20 65 6c 65 6d 65 6e 74 73   no new elements
0340: 20 6d 61 79 20 62 65 20 69 6e 73 65 72 74 65 64   may be inserted
0350: 2e 0a 2a 2a 0a 2a 2a 20 48 65 6e 63 65 2c 20 74  ..**.** Hence, t
0360: 68 65 20 70 72 69 6d 69 74 69 76 65 20 6f 70 65  he primitive ope
0370: 72 61 74 69 6f 6e 73 20 66 6f 72 20 61 20 52 6f  rations for a Ro
0380: 77 53 65 74 20 61 72 65 3a 0a 2a 2a 0a 2a 2a 20  wSet are:.**.** 
0390: 20 20 20 43 52 45 41 54 45 0a 2a 2a 20 20 20 20     CREATE.**    
03a0: 49 4e 53 45 52 54 0a 2a 2a 20 20 20 20 54 45 53  INSERT.**    TES
03b0: 54 0a 2a 2a 20 20 20 20 53 4d 41 4c 4c 45 53 54  T.**    SMALLEST
03c0: 0a 2a 2a 20 20 20 20 44 45 53 54 52 4f 59 0a 2a  .**    DESTROY.*
03d0: 2a 0a 2a 2a 20 54 68 65 20 43 52 45 41 54 45 20  *.** The CREATE 
03e0: 61 6e 64 20 44 45 53 54 52 4f 59 20 70 72 69 6d  and DESTROY prim
03f0: 69 74 69 76 65 73 20 61 72 65 20 74 68 65 20 63  itives are the c
0400: 6f 6e 73 74 72 75 63 74 6f 72 20 61 6e 64 20 64  onstructor and d
0410: 65 73 74 72 75 63 74 6f 72 2c 0a 2a 2a 20 6f 62  estructor,.** ob
0420: 76 69 6f 75 73 6c 79 2e 20 20 54 68 65 20 49 4e  viously.  The IN
0430: 53 45 52 54 20 70 72 69 6d 69 74 69 76 65 20 61  SERT primitive a
0440: 64 64 73 20 61 20 6e 65 77 20 65 6c 65 6d 65 6e  dds a new elemen
0450: 74 20 74 6f 20 74 68 65 20 52 6f 77 53 65 74 2e  t to the RowSet.
0460: 0a 2a 2a 20 54 45 53 54 20 63 68 65 63 6b 73 20  .** TEST checks 
0470: 74 6f 20 73 65 65 20 69 66 20 61 6e 20 65 6c 65  to see if an ele
0480: 6d 65 6e 74 20 69 73 20 61 6c 72 65 61 64 79 20  ment is already 
0490: 69 6e 20 74 68 65 20 52 6f 77 53 65 74 2e 20 20  in the RowSet.  
04a0: 53 4d 41 4c 4c 45 53 54 0a 2a 2a 20 65 78 74 72  SMALLEST.** extr
04b0: 61 63 74 73 20 74 68 65 20 6c 65 61 73 74 20 76  acts the least v
04c0: 61 6c 75 65 20 66 72 6f 6d 20 74 68 65 20 52 6f  alue from the Ro
04d0: 77 53 65 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  wSet..**.** The 
04e0: 49 4e 53 45 52 54 20 70 72 69 6d 69 74 69 76 65  INSERT primitive
04f0: 20 6d 69 67 68 74 20 61 6c 6c 6f 63 61 74 65 20   might allocate 
0500: 61 64 64 69 74 69 6f 6e 61 6c 20 6d 65 6d 6f 72  additional memor
0510: 79 2e 20 20 4d 65 6d 6f 72 79 20 69 73 0a 2a 2a  y.  Memory is.**
0520: 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e 20 63 68   allocated in ch
0530: 75 6e 6b 73 20 73 6f 20 6d 6f 73 74 20 49 4e 53  unks so most INS
0540: 45 52 54 73 20 64 6f 20 6e 6f 20 61 6c 6c 6f 63  ERTs do no alloc
0550: 61 74 69 6f 6e 2e 20 20 54 68 65 72 65 20 69 73  ation.  There is
0560: 20 61 6e 20 0a 2a 2a 20 75 70 70 65 72 20 62 6f   an .** upper bo
0570: 75 6e 64 20 6f 6e 20 74 68 65 20 73 69 7a 65 20  und on the size 
0580: 6f 66 20 61 6c 6c 6f 63 61 74 65 64 20 6d 65 6d  of allocated mem
0590: 6f 72 79 2e 20 20 4e 6f 20 6d 65 6d 6f 72 79 20  ory.  No memory 
05a0: 69 73 20 66 72 65 65 64 0a 2a 2a 20 75 6e 74 69  is freed.** unti
05b0: 6c 20 44 45 53 54 52 4f 59 2e 0a 2a 2a 0a 2a 2a  l DESTROY..**.**
05c0: 20 54 68 65 20 54 45 53 54 20 70 72 69 6d 69 74   The TEST primit
05d0: 69 76 65 20 69 6e 63 6c 75 64 65 73 20 61 20 22  ive includes a "
05e0: 62 61 74 63 68 22 20 6e 75 6d 62 65 72 2e 20 20  batch" number.  
05f0: 54 68 65 20 54 45 53 54 20 70 72 69 6d 69 74 69  The TEST primiti
0600: 76 65 0a 2a 2a 20 77 69 6c 6c 20 6f 6e 6c 79 20  ve.** will only 
0610: 73 65 65 20 65 6c 65 6d 65 6e 74 73 20 74 68 61  see elements tha
0620: 74 20 77 65 72 65 20 69 6e 73 65 72 74 65 64 20  t were inserted 
0630: 62 65 66 6f 72 65 20 74 68 65 20 6c 61 73 74 20  before the last 
0640: 63 68 61 6e 67 65 0a 2a 2a 20 69 6e 20 74 68 65  change.** in the
0650: 20 62 61 74 63 68 20 6e 75 6d 62 65 72 2e 20 20   batch number.  
0660: 49 6e 20 6f 74 68 65 72 20 77 6f 72 64 73 2c 20  In other words, 
0670: 69 66 20 61 6e 20 49 4e 53 45 52 54 20 6f 63 63  if an INSERT occ
0680: 75 72 73 20 62 65 74 77 65 65 6e 0a 2a 2a 20 74  urs between.** t
0690: 77 6f 20 54 45 53 54 73 20 77 68 65 72 65 20 74  wo TESTs where t
06a0: 68 65 20 54 45 53 54 73 20 68 61 76 65 20 74 68  he TESTs have th
06b0: 65 20 73 61 6d 65 20 62 61 74 63 68 20 6e 75 62  e same batch nub
06c0: 6d 65 72 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a  mer, then the.**
06d0: 20 76 61 6c 75 65 20 61 64 64 65 64 20 62 79 20   value added by 
06e0: 74 68 65 20 49 4e 53 45 52 54 20 77 69 6c 6c 20  the INSERT will 
06f0: 6e 6f 74 20 62 65 20 76 69 73 69 62 6c 65 20 74  not be visible t
0700: 6f 20 74 68 65 20 73 65 63 6f 6e 64 20 54 45 53  o the second TES
0710: 54 2e 0a 2a 2a 20 54 68 65 20 69 6e 69 74 69 61  T..** The initia
0720: 6c 20 62 61 74 63 68 20 6e 75 6d 62 65 72 20 69  l batch number i
0730: 73 20 7a 65 72 6f 2c 20 73 6f 20 69 66 20 74 68  s zero, so if th
0740: 65 20 76 65 72 79 20 66 69 72 73 74 20 54 45 53  e very first TES
0750: 54 20 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20 61 20  T contains.** a 
0760: 6e 6f 6e 2d 7a 65 72 6f 20 62 61 74 63 68 20 6e  non-zero batch n
0770: 75 6d 62 65 72 2c 20 69 74 20 77 69 6c 6c 20 73  umber, it will s
0780: 65 65 20 61 6c 6c 20 70 72 69 6f 72 20 49 4e 53  ee all prior INS
0790: 45 52 54 73 2e 0a 2a 2a 0a 2a 2a 20 4e 6f 20 49  ERTs..**.** No I
07a0: 4e 53 45 52 54 73 20 6d 61 79 20 6f 63 63 75 72  NSERTs may occur
07b0: 73 20 61 66 74 65 72 20 61 20 53 4d 41 4c 4c 45  s after a SMALLE
07c0: 53 54 2e 20 20 41 6e 20 61 73 73 65 72 74 69 6f  ST.  An assertio
07d0: 6e 20 77 69 6c 6c 20 66 61 69 6c 20 69 66 0a 2a  n will fail if.*
07e0: 2a 20 74 68 61 74 20 69 73 20 61 74 74 65 6d 70  * that is attemp
07f0: 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63  ted..**.** The c
0800: 6f 73 74 20 6f 66 20 61 6e 20 49 4e 53 45 52 54  ost of an INSERT
0810: 20 69 73 20 72 6f 75 67 68 6c 79 20 63 6f 6e 73   is roughly cons
0820: 74 61 6e 74 2e 20 20 28 53 6f 6d 65 74 69 6d 65  tant.  (Sometime
0830: 73 20 6e 65 77 20 6d 65 6d 6f 72 79 0a 2a 2a 20  s new memory.** 
0840: 68 61 73 20 74 6f 20 62 65 20 61 6c 6c 6f 63 61  has to be alloca
0850: 74 65 64 20 6f 6e 20 61 6e 20 49 4e 53 45 52 54  ted on an INSERT
0860: 2e 29 20 20 54 68 65 20 63 6f 73 74 20 6f 66 20  .)  The cost of 
0870: 61 20 54 45 53 54 20 77 69 74 68 20 61 20 6e 65  a TEST with a ne
0880: 77 0a 2a 2a 20 62 61 74 63 68 20 6e 75 6d 62 65  w.** batch numbe
0890: 72 20 69 73 20 4f 28 4e 6c 6f 67 4e 29 20 77 68  r is O(NlogN) wh
08a0: 65 72 65 20 4e 20 69 73 20 74 68 65 20 6e 75 6d  ere N is the num
08b0: 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20  ber of elements 
08c0: 69 6e 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a  in the RowSet..*
08d0: 2a 20 54 68 65 20 63 6f 73 74 20 6f 66 20 61 20  * The cost of a 
08e0: 54 45 53 54 20 75 73 69 6e 67 20 74 68 65 20 73  TEST using the s
08f0: 61 6d 65 20 62 61 74 63 68 20 6e 75 6d 62 65 72  ame batch number
0900: 20 69 73 20 4f 28 6c 6f 67 4e 29 2e 20 20 54 68   is O(logN).  Th
0910: 65 20 63 6f 73 74 0a 2a 2a 20 6f 66 20 74 68 65  e cost.** of the
0920: 20 66 69 72 73 74 20 53 4d 41 4c 4c 45 53 54 20   first SMALLEST 
0930: 69 73 20 4f 28 4e 6c 6f 67 4e 29 2e 20 20 53 65  is O(NlogN).  Se
0940: 63 6f 6e 64 20 61 6e 64 20 73 75 62 73 65 71 75  cond and subsequ
0950: 65 6e 74 20 53 4d 41 4c 4c 45 53 54 0a 2a 2a 20  ent SMALLEST.** 
0960: 70 72 69 6d 69 74 69 76 65 73 20 61 72 65 20 63  primitives are c
0970: 6f 6e 73 74 61 6e 74 20 74 69 6d 65 2e 20 20 54  onstant time.  T
0980: 68 65 20 63 6f 73 74 20 6f 66 20 44 45 53 54 52  he cost of DESTR
0990: 4f 59 20 69 73 20 4f 28 4e 29 2e 0a 2a 2a 0a 2a  OY is O(N)..**.*
09a0: 2a 20 54 45 53 54 20 61 6e 64 20 53 4d 41 4c 4c  * TEST and SMALL
09b0: 45 53 54 20 6d 61 79 20 6e 6f 74 20 62 65 20 75  EST may not be u
09c0: 73 65 64 20 62 79 20 74 68 65 20 73 61 6d 65 20  sed by the same 
09d0: 52 6f 77 53 65 74 2e 20 20 54 68 69 73 20 75 73  RowSet.  This us
09e0: 65 64 20 74 6f 0a 2a 2a 20 62 65 20 70 6f 73 73  ed to.** be poss
09f0: 69 62 6c 65 2c 20 62 75 74 20 74 68 65 20 66 65  ible, but the fe
0a00: 61 74 75 72 65 20 77 61 73 20 6e 6f 74 20 75 73  ature was not us
0a10: 65 64 2c 20 73 6f 20 69 74 20 77 61 73 20 72 65  ed, so it was re
0a20: 6d 6f 76 65 64 20 69 6e 20 6f 72 64 65 72 0a 2a  moved in order.*
0a30: 2a 20 74 6f 20 73 69 6d 70 6c 69 66 79 20 74 68  * to simplify th
0a40: 65 20 63 6f 64 65 2e 0a 2a 2f 0a 23 69 6e 63 6c  e code..*/.#incl
0a50: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
0a60: 22 0a 0a 0a 2f 2a 0a 2a 2a 20 54 61 72 67 65 74  ".../*.** Target
0a70: 20 73 69 7a 65 20 66 6f 72 20 61 6c 6c 6f 63 61   size for alloca
0a80: 74 69 6f 6e 20 63 68 75 6e 6b 73 2e 0a 2a 2f 0a  tion chunks..*/.
0a90: 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f 41  #define ROWSET_A
0aa0: 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49 5a 45 20 31  LLOCATION_SIZE 1
0ab0: 30 32 34 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 6e  024../*.** The n
0ac0: 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 65 74 20  umber of rowset 
0ad0: 65 6e 74 72 69 65 73 20 70 65 72 20 61 6c 6c 6f  entries per allo
0ae0: 63 61 74 69 6f 6e 20 63 68 75 6e 6b 2e 0a 2a 2f  cation chunk..*/
0af0: 0a 23 64 65 66 69 6e 65 20 52 4f 57 53 45 54 5f  .#define ROWSET_
0b00: 45 4e 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b 20  ENTRY_PER_CHUNK 
0b10: 20 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   \.             
0b20: 20 20 20 20 20 20 20 20 20 20 28 28 52 4f 57 53            ((ROWS
0b30: 45 54 5f 41 4c 4c 4f 43 41 54 49 4f 4e 5f 53 49  ET_ALLOCATION_SI
0b40: 5a 45 2d 38 29 2f 73 69 7a 65 6f 66 28 73 74 72  ZE-8)/sizeof(str
0b50: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 29  uct RowSetEntry)
0b60: 29 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 65 6e  )../*.** Each en
0b70: 74 72 79 20 69 6e 20 61 20 52 6f 77 53 65 74 20  try in a RowSet 
0b80: 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f  is an instance o
0b90: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
0ba0: 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 54 68  object..**.** Th
0bb0: 69 73 20 73 61 6d 65 20 6f 62 6a 65 63 74 20 69  is same object i
0bc0: 73 20 72 65 75 73 65 64 20 74 6f 20 73 74 6f 72  s reused to stor
0bd0: 65 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  e a linked list 
0be0: 6f 66 20 74 72 65 65 73 20 6f 66 20 52 6f 77 53  of trees of RowS
0bf0: 65 74 45 6e 74 72 79 0a 2a 2a 20 6f 62 6a 65 63  etEntry.** objec
0c00: 74 73 2e 20 20 49 6e 20 74 68 61 74 20 61 6c 74  ts.  In that alt
0c10: 65 72 6e 61 74 69 76 65 20 75 73 65 2c 20 70 52  ernative use, pR
0c20: 69 67 68 74 20 70 6f 69 6e 74 73 20 74 6f 20 74  ight points to t
0c30: 68 65 20 6e 65 78 74 20 65 6e 74 72 79 0a 2a 2a  he next entry.**
0c40: 20 69 6e 20 74 68 65 20 6c 69 73 74 2c 20 70 4c   in the list, pL
0c50: 65 66 74 20 70 6f 69 6e 74 73 20 74 6f 20 74 68  eft points to th
0c60: 65 20 74 72 65 65 2c 20 61 6e 64 20 76 20 69 73  e tree, and v is
0c70: 20 75 6e 75 73 65 64 2e 20 20 54 68 65 0a 2a 2a   unused.  The.**
0c80: 20 52 6f 77 53 65 74 2e 70 46 6f 72 65 73 74 20   RowSet.pForest 
0c90: 76 61 6c 75 65 20 70 6f 69 6e 74 73 20 74 6f 20  value points to 
0ca0: 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 69 73  the head of this
0cb0: 20 66 6f 72 65 73 74 20 6c 69 73 74 2e 0a 2a 2f   forest list..*/
0cc0: 0a 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e  .struct RowSetEn
0cd0: 74 72 79 20 7b 20 20 20 20 20 20 20 20 20 20 20  try {           
0ce0: 20 0a 20 20 69 36 34 20 76 3b 20 20 20 20 20 20   .  i64 v;      
0cf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0d00: 20 20 2f 2a 20 52 4f 57 49 44 20 76 61 6c 75 65    /* ROWID value
0d10: 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20   for this entry 
0d20: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
0d30: 65 74 45 6e 74 72 79 20 2a 70 52 69 67 68 74 3b  etEntry *pRight;
0d40: 20 20 20 2f 2a 20 52 69 67 68 74 20 73 75 62 74     /* Right subt
0d50: 72 65 65 20 28 6c 61 72 67 65 72 20 65 6e 74 72  ree (larger entr
0d60: 69 65 73 29 20 6f 72 20 6c 69 73 74 20 2a 2f 0a  ies) or list */.
0d70: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
0d80: 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20 20 20 20  ntry *pLeft;    
0d90: 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65 65 20  /* Left subtree 
0da0: 28 73 6d 61 6c 6c 65 72 20 65 6e 74 72 69 65 73  (smaller entries
0db0: 29 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 52  ) */.};../*.** R
0dc0: 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65 63  owSetEntry objec
0dd0: 74 73 20 61 72 65 20 61 6c 6c 6f 63 61 74 65 64  ts are allocated
0de0: 20 69 6e 20 6c 61 72 67 65 20 63 68 75 6e 6b 73   in large chunks
0df0: 20 28 69 6e 73 74 61 6e 63 65 73 20 6f 66 20 74   (instances of t
0e00: 68 65 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20  he.** following 
0e10: 73 74 72 75 63 74 75 72 65 29 20 74 6f 20 72 65  structure) to re
0e20: 64 75 63 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  duce memory allo
0e30: 63 61 74 69 6f 6e 20 6f 76 65 72 68 65 61 64 2e  cation overhead.
0e40: 20 20 54 68 65 0a 2a 2a 20 63 68 75 6e 6b 73 20    The.** chunks 
0e50: 61 72 65 20 6b 65 70 74 20 6f 6e 20 61 20 6c 69  are kept on a li
0e60: 6e 6b 65 64 20 6c 69 73 74 20 73 6f 20 74 68 61  nked list so tha
0e70: 74 20 74 68 65 79 20 63 61 6e 20 62 65 20 64 65  t they can be de
0e80: 61 6c 6c 6f 63 61 74 65 64 0a 2a 2a 20 77 68 65  allocated.** whe
0e90: 6e 20 74 68 65 20 52 6f 77 53 65 74 20 69 73 20  n the RowSet is 
0ea0: 64 65 73 74 72 6f 79 65 64 2e 0a 2a 2f 0a 73 74  destroyed..*/.st
0eb0: 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b  ruct RowSetChunk
0ec0: 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53   {.  struct RowS
0ed0: 65 74 43 68 75 6e 6b 20 2a 70 4e 65 78 74 43 68  etChunk *pNextCh
0ee0: 75 6e 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e  unk;        /* N
0ef0: 65 78 74 20 63 68 75 6e 6b 20 6f 6e 20 6c 69 73  ext chunk on lis
0f00: 74 20 6f 66 20 74 68 65 6d 20 61 6c 6c 20 2a 2f  t of them all */
0f10: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
0f20: 45 6e 74 72 79 20 61 45 6e 74 72 79 5b 52 4f 57  Entry aEntry[ROW
0f30: 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f 43 48  SET_ENTRY_PER_CH
0f40: 55 4e 4b 5d 3b 20 2f 2a 20 41 6c 6c 6f 63 61 74  UNK]; /* Allocat
0f50: 65 64 20 65 6e 74 72 69 65 73 20 2a 2f 0a 7d 3b  ed entries */.};
0f60: 0a 0a 2f 2a 0a 2a 2a 20 41 20 52 6f 77 53 65 74  ../*.** A RowSet
0f70: 20 69 6e 20 61 6e 20 69 6e 73 74 61 6e 63 65 20   in an instance 
0f80: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0f90: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
0fa0: 2a 20 41 20 74 79 70 65 64 65 66 20 6f 66 20 74  * A typedef of t
0fb0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69 66  his structure if
0fc0: 20 66 6f 75 6e 64 20 69 6e 20 73 71 6c 69 74 65   found in sqlite
0fd0: 49 6e 74 2e 68 2e 0a 2a 2f 0a 73 74 72 75 63 74  Int.h..*/.struct
0fe0: 20 52 6f 77 53 65 74 20 7b 0a 20 20 73 74 72 75   RowSet {.  stru
0ff0: 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a  ct RowSetChunk *
1000: 70 43 68 75 6e 6b 3b 20 20 20 20 2f 2a 20 4c 69  pChunk;    /* Li
1010: 73 74 20 6f 66 20 61 6c 6c 20 63 68 75 6e 6b 20  st of all chunk 
1020: 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f 0a 20  allocations */. 
1030: 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20 20 20   sqlite3 *db;   
1040: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1050: 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20  /* The database 
1060: 63 6f 6e 6e 65 63 74 69 6f 6e 20 2a 2f 0a 20 20  connection */.  
1070: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1080: 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 20 20 2f  ry *pEntry;    /
1090: 2a 20 4c 69 73 74 20 6f 66 20 65 6e 74 72 69 65  * List of entrie
10a0: 73 20 75 73 69 6e 67 20 70 52 69 67 68 74 20 2a  s using pRight *
10b0: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
10c0: 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20 20  tEntry *pLast;  
10d0: 20 20 20 2f 2a 20 4c 61 73 74 20 65 6e 74 72 79     /* Last entry
10e0: 20 6f 6e 20 74 68 65 20 70 45 6e 74 72 79 20 6c   on the pEntry l
10f0: 69 73 74 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ist */.  struct 
1100: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 46 72  RowSetEntry *pFr
1110: 65 73 68 3b 20 20 20 20 2f 2a 20 53 6f 75 72 63  esh;    /* Sourc
1120: 65 20 6f 66 20 6e 65 77 20 65 6e 74 72 79 20 6f  e of new entry o
1130: 62 6a 65 63 74 73 20 2a 2f 0a 20 20 73 74 72 75  bjects */.  stru
1140: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
1150: 70 46 6f 72 65 73 74 3b 20 20 20 2f 2a 20 4c 69  pForest;   /* Li
1160: 73 74 20 6f 66 20 62 69 6e 61 72 79 20 74 72 65  st of binary tre
1170: 65 73 20 6f 66 20 65 6e 74 72 69 65 73 20 2a 2f  es of entries */
1180: 0a 20 20 75 31 36 20 6e 46 72 65 73 68 3b 20 20  .  u16 nFresh;  
1190: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11a0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6f    /* Number of o
11b0: 62 6a 65 63 74 73 20 6f 6e 20 70 46 72 65 73 68  bjects on pFresh
11c0: 20 2a 2f 0a 20 20 75 31 36 20 72 73 46 6c 61 67   */.  u16 rsFlag
11d0: 73 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  s;              
11e0: 20 20 20 20 20 2f 2a 20 56 61 72 69 6f 75 73 20       /* Various 
11f0: 66 6c 61 67 73 20 2a 2f 0a 20 20 69 6e 74 20 69  flags */.  int i
1200: 42 61 74 63 68 3b 20 20 20 20 20 20 20 20 20 20  Batch;          
1210: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
1220: 72 65 6e 74 20 69 6e 73 65 72 74 20 62 61 74 63  rent insert batc
1230: 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41  h */.};../*.** A
1240: 6c 6c 6f 77 65 64 20 76 61 6c 75 65 73 20 66 6f  llowed values fo
1250: 72 20 52 6f 77 53 65 74 2e 72 73 46 6c 61 67 73  r RowSet.rsFlags
1260: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 57 53  .*/.#define ROWS
1270: 45 54 5f 53 4f 52 54 45 44 20 20 30 78 30 31 20  ET_SORTED  0x01 
1280: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 52 6f 77    /* True if Row
1290: 53 65 74 2e 70 45 6e 74 72 79 20 69 73 20 73 6f  Set.pEntry is so
12a0: 72 74 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20  rted */.#define 
12b0: 52 4f 57 53 45 54 5f 4e 45 58 54 20 20 20 20 30  ROWSET_NEXT    0
12c0: 78 30 32 20 20 20 2f 2a 20 54 72 75 65 20 69 66  x02   /* True if
12d0: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65   sqlite3RowSetNe
12e0: 78 74 28 29 20 68 61 73 20 62 65 65 6e 20 63 61  xt() has been ca
12f0: 6c 6c 65 64 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 41  lled */../*.** A
1300: 6c 6c 6f 63 61 74 65 20 61 20 52 6f 77 53 65 74  llocate a RowSet
1310: 20 6f 62 6a 65 63 74 2e 20 20 52 65 74 75 72 6e   object.  Return
1320: 20 4e 55 4c 4c 20 69 66 20 61 20 6d 65 6d 6f 72   NULL if a memor
1330: 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 0a 2a 2a 20  y allocation.** 
1340: 65 72 72 6f 72 20 6f 63 63 75 72 73 2e 0a 2a 2f  error occurs..*/
1350: 0a 52 6f 77 53 65 74 20 2a 73 71 6c 69 74 65 33  .RowSet *sqlite3
1360: 52 6f 77 53 65 74 49 6e 69 74 28 73 71 6c 69 74  RowSetInit(sqlit
1370: 65 33 20 2a 64 62 29 7b 0a 20 20 52 6f 77 53 65  e3 *db){.  RowSe
1380: 74 20 2a 70 20 3d 20 73 71 6c 69 74 65 33 44 62  t *p = sqlite3Db
1390: 4d 61 6c 6c 6f 63 52 61 77 4e 4e 28 64 62 2c 20  MallocRawNN(db, 
13a0: 73 69 7a 65 6f 66 28 2a 70 29 29 3b 0a 20 20 69  sizeof(*p));.  i
13b0: 66 28 20 70 20 29 7b 0a 20 20 20 20 69 6e 74 20  f( p ){.    int 
13c0: 4e 20 3d 20 73 71 6c 69 74 65 33 44 62 4d 61 6c  N = sqlite3DbMal
13d0: 6c 6f 63 53 69 7a 65 28 64 62 2c 20 70 29 3b 0a  locSize(db, p);.
13e0: 20 20 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d 20      p->pChunk = 
13f0: 30 3b 0a 20 20 20 20 70 2d 3e 64 62 20 3d 20 64  0;.    p->db = d
1400: 62 3b 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79  b;.    p->pEntry
1410: 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 70 4c 61   = 0;.    p->pLa
1420: 73 74 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 70  st = 0;.    p->p
1430: 46 6f 72 65 73 74 20 3d 20 30 3b 0a 20 20 20 20  Forest = 0;.    
1440: 70 2d 3e 70 46 72 65 73 68 20 3d 20 28 73 74 72  p->pFresh = (str
1450: 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 2a  uct RowSetEntry*
1460: 29 28 52 4f 55 4e 44 38 28 73 69 7a 65 6f 66 28  )(ROUND8(sizeof(
1470: 2a 70 29 29 20 2b 20 28 63 68 61 72 2a 29 70 29  *p)) + (char*)p)
1480: 3b 0a 20 20 20 20 70 2d 3e 6e 46 72 65 73 68 20  ;.    p->nFresh 
1490: 3d 20 28 75 31 36 29 28 28 4e 20 2d 20 52 4f 55  = (u16)((N - ROU
14a0: 4e 44 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 29  ND8(sizeof(*p)))
14b0: 2f 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 52  /sizeof(struct R
14c0: 6f 77 53 65 74 45 6e 74 72 79 29 29 3b 0a 20 20  owSetEntry));.  
14d0: 20 20 70 2d 3e 72 73 46 6c 61 67 73 20 3d 20 52    p->rsFlags = R
14e0: 4f 57 53 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20  OWSET_SORTED;.  
14f0: 20 20 70 2d 3e 69 42 61 74 63 68 20 3d 20 30 3b    p->iBatch = 0;
1500: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b  .  }.  return p;
1510: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 44 65 61 6c 6c 6f  .}../*.** Deallo
1520: 63 61 74 65 20 61 6c 6c 20 63 68 75 6e 6b 73 20  cate all chunks 
1530: 66 72 6f 6d 20 61 20 52 6f 77 53 65 74 2e 20 20  from a RowSet.  
1540: 54 68 69 73 20 66 72 65 65 73 20 61 6c 6c 20 6d  This frees all m
1550: 65 6d 6f 72 79 20 74 68 61 74 0a 2a 2a 20 74 68  emory that.** th
1560: 65 20 52 6f 77 53 65 74 20 68 61 73 20 61 6c 6c  e RowSet has all
1570: 6f 63 61 74 65 64 20 6f 76 65 72 20 69 74 73 20  ocated over its 
1580: 6c 69 66 65 74 69 6d 65 2e 20 20 54 68 69 73 20  lifetime.  This 
1590: 72 6f 75 74 69 6e 65 20 69 73 0a 2a 2a 20 74 68  routine is.** th
15a0: 65 20 64 65 73 74 72 75 63 74 6f 72 20 66 6f 72  e destructor for
15b0: 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a 2f 0a   the RowSet..*/.
15c0: 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77 53  void sqlite3RowS
15d0: 65 74 43 6c 65 61 72 28 76 6f 69 64 20 2a 70 41  etClear(void *pA
15e0: 72 67 29 7b 0a 20 20 52 6f 77 53 65 74 20 2a 70  rg){.  RowSet *p
15f0: 20 3d 20 28 52 6f 77 53 65 74 2a 29 70 41 72 67   = (RowSet*)pArg
1600: 3b 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  ;.  struct RowSe
1610: 74 43 68 75 6e 6b 20 2a 70 43 68 75 6e 6b 2c 20  tChunk *pChunk, 
1620: 2a 70 4e 65 78 74 43 68 75 6e 6b 3b 0a 20 20 66  *pNextChunk;.  f
1630: 6f 72 28 70 43 68 75 6e 6b 3d 70 2d 3e 70 43 68  or(pChunk=p->pCh
1640: 75 6e 6b 3b 20 70 43 68 75 6e 6b 3b 20 70 43 68  unk; pChunk; pCh
1650: 75 6e 6b 20 3d 20 70 4e 65 78 74 43 68 75 6e 6b  unk = pNextChunk
1660: 29 7b 0a 20 20 20 20 70 4e 65 78 74 43 68 75 6e  ){.    pNextChun
1670: 6b 20 3d 20 70 43 68 75 6e 6b 2d 3e 70 4e 65 78  k = pChunk->pNex
1680: 74 43 68 75 6e 6b 3b 0a 20 20 20 20 73 71 6c 69  tChunk;.    sqli
1690: 74 65 33 44 62 46 72 65 65 28 70 2d 3e 64 62 2c  te3DbFree(p->db,
16a0: 20 70 43 68 75 6e 6b 29 3b 0a 20 20 7d 0a 20 20   pChunk);.  }.  
16b0: 70 2d 3e 70 43 68 75 6e 6b 20 3d 20 30 3b 0a 20  p->pChunk = 0;. 
16c0: 20 70 2d 3e 6e 46 72 65 73 68 20 3d 20 30 3b 0a   p->nFresh = 0;.
16d0: 20 20 70 2d 3e 70 45 6e 74 72 79 20 3d 20 30 3b    p->pEntry = 0;
16e0: 0a 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20 30 3b  .  p->pLast = 0;
16f0: 0a 20 20 70 2d 3e 70 46 6f 72 65 73 74 20 3d 20  .  p->pForest = 
1700: 30 3b 0a 20 20 70 2d 3e 72 73 46 6c 61 67 73 20  0;.  p->rsFlags 
1710: 3d 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44 3b  = ROWSET_SORTED;
1720: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 44 65 61 6c 6c 6f  .}../*.** Deallo
1730: 63 61 74 65 20 61 6c 6c 20 63 68 75 6e 6b 73 20  cate all chunks 
1740: 66 72 6f 6d 20 61 20 52 6f 77 53 65 74 2e 20 20  from a RowSet.  
1750: 54 68 69 73 20 66 72 65 65 73 20 61 6c 6c 20 6d  This frees all m
1760: 65 6d 6f 72 79 20 74 68 61 74 0a 2a 2a 20 74 68  emory that.** th
1770: 65 20 52 6f 77 53 65 74 20 68 61 73 20 61 6c 6c  e RowSet has all
1780: 6f 63 61 74 65 64 20 6f 76 65 72 20 69 74 73 20  ocated over its 
1790: 6c 69 66 65 74 69 6d 65 2e 20 20 54 68 69 73 20  lifetime.  This 
17a0: 72 6f 75 74 69 6e 65 20 69 73 0a 2a 2a 20 74 68  routine is.** th
17b0: 65 20 64 65 73 74 72 75 63 74 6f 72 20 66 6f 72  e destructor for
17c0: 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a 2f 0a   the RowSet..*/.
17d0: 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77 53  void sqlite3RowS
17e0: 65 74 44 65 6c 65 74 65 28 76 6f 69 64 20 2a 70  etDelete(void *p
17f0: 41 72 67 29 7b 0a 20 20 73 71 6c 69 74 65 33 52  Arg){.  sqlite3R
1800: 6f 77 53 65 74 43 6c 65 61 72 28 70 41 72 67 29  owSetClear(pArg)
1810: 3b 0a 20 20 73 71 6c 69 74 65 33 44 62 46 72 65  ;.  sqlite3DbFre
1820: 65 28 28 28 52 6f 77 53 65 74 2a 29 70 41 72 67  e(((RowSet*)pArg
1830: 29 2d 3e 64 62 2c 20 70 41 72 67 29 3b 0a 7d 0a  )->db, pArg);.}.
1840: 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20  ./*.** Allocate 
1850: 61 20 6e 65 77 20 52 6f 77 53 65 74 45 6e 74 72  a new RowSetEntr
1860: 79 20 6f 62 6a 65 63 74 20 74 68 61 74 20 69 73  y object that is
1870: 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68   associated with
1880: 20 74 68 65 0a 2a 2a 20 67 69 76 65 6e 20 52 6f   the.** given Ro
1890: 77 53 65 74 2e 20 20 52 65 74 75 72 6e 20 61 20  wSet.  Return a 
18a0: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 6e  pointer to the n
18b0: 65 77 20 61 6e 64 20 63 6f 6d 70 6c 65 74 65 6c  ew and completel
18c0: 79 20 75 6e 69 6e 69 74 69 61 6c 69 7a 65 64 0a  y uninitialized.
18d0: 2a 2a 20 6f 62 6a 65 63 74 65 64 2e 0a 2a 2a 0a  ** objected..**.
18e0: 2a 2a 20 49 6e 20 61 6e 20 4f 4f 4d 20 73 69 74  ** In an OOM sit
18f0: 75 61 74 69 6f 6e 2c 20 74 68 65 20 52 6f 77 53  uation, the RowS
1900: 65 74 2e 64 62 2d 3e 6d 61 6c 6c 6f 63 46 61 69  et.db->mallocFai
1910: 6c 65 64 20 66 6c 61 67 20 69 73 20 73 65 74 20  led flag is set 
1920: 61 6e 64 20 74 68 69 73 0a 2a 2a 20 72 6f 75 74  and this.** rout
1930: 69 6e 65 20 72 65 74 75 72 6e 73 20 4e 55 4c 4c  ine returns NULL
1940: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75  ..*/.static stru
1950: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
1960: 72 6f 77 53 65 74 45 6e 74 72 79 41 6c 6c 6f 63  rowSetEntryAlloc
1970: 28 52 6f 77 53 65 74 20 2a 70 29 7b 0a 20 20 61  (RowSet *p){.  a
1980: 73 73 65 72 74 28 20 70 21 3d 30 20 29 3b 0a 20  ssert( p!=0 );. 
1990: 20 69 66 28 20 70 2d 3e 6e 46 72 65 73 68 3d 3d   if( p->nFresh==
19a0: 30 20 29 7b 20 20 2f 2a 4f 50 54 49 4d 49 5a 41  0 ){  /*OPTIMIZA
19b0: 54 49 4f 4e 2d 49 46 2d 46 41 4c 53 45 2a 2f 0a  TION-IF-FALSE*/.
19c0: 20 20 20 20 2f 2a 20 57 65 20 63 6f 75 6c 64 20      /* We could 
19d0: 61 6c 6c 6f 63 61 74 65 20 61 20 66 72 65 73 68  allocate a fresh
19e0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 65 61 63   RowSetEntry eac
19f0: 68 20 74 69 6d 65 20 6f 6e 65 20 69 73 20 6e 65  h time one is ne
1a00: 65 64 65 64 2c 20 62 75 74 20 69 74 0a 20 20 20  eded, but it.   
1a10: 20 2a 2a 20 69 73 20 6d 6f 72 65 20 65 66 66 69   ** is more effi
1a20: 63 69 65 6e 74 20 74 6f 20 70 75 6c 6c 20 61 20  cient to pull a 
1a30: 70 72 65 61 6c 6c 6f 63 61 74 65 64 20 65 6e 74  preallocated ent
1a40: 72 79 20 66 72 6f 6d 20 74 68 65 20 70 6f 6f 6c  ry from the pool
1a50: 20 2a 2f 0a 20 20 20 20 73 74 72 75 63 74 20 52   */.    struct R
1a60: 6f 77 53 65 74 43 68 75 6e 6b 20 2a 70 4e 65 77  owSetChunk *pNew
1a70: 3b 0a 20 20 20 20 70 4e 65 77 20 3d 20 73 71 6c  ;.    pNew = sql
1a80: 69 74 65 33 44 62 4d 61 6c 6c 6f 63 52 61 77 4e  ite3DbMallocRawN
1a90: 4e 28 70 2d 3e 64 62 2c 20 73 69 7a 65 6f 66 28  N(p->db, sizeof(
1aa0: 2a 70 4e 65 77 29 29 3b 0a 20 20 20 20 69 66 28  *pNew));.    if(
1ab0: 20 70 4e 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20   pNew==0 ){.    
1ac0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 20    return 0;.    
1ad0: 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70 4e 65 78  }.    pNew->pNex
1ae0: 74 43 68 75 6e 6b 20 3d 20 70 2d 3e 70 43 68 75  tChunk = p->pChu
1af0: 6e 6b 3b 0a 20 20 20 20 70 2d 3e 70 43 68 75 6e  nk;.    p->pChun
1b00: 6b 20 3d 20 70 4e 65 77 3b 0a 20 20 20 20 70 2d  k = pNew;.    p-
1b10: 3e 70 46 72 65 73 68 20 3d 20 70 4e 65 77 2d 3e  >pFresh = pNew->
1b20: 61 45 6e 74 72 79 3b 0a 20 20 20 20 70 2d 3e 6e  aEntry;.    p->n
1b30: 46 72 65 73 68 20 3d 20 52 4f 57 53 45 54 5f 45  Fresh = ROWSET_E
1b40: 4e 54 52 59 5f 50 45 52 5f 43 48 55 4e 4b 3b 0a  NTRY_PER_CHUNK;.
1b50: 20 20 7d 0a 20 20 70 2d 3e 6e 46 72 65 73 68 2d    }.  p->nFresh-
1b60: 2d 3b 0a 20 20 72 65 74 75 72 6e 20 70 2d 3e 70  -;.  return p->p
1b70: 46 72 65 73 68 2b 2b 3b 0a 7d 0a 0a 2f 2a 0a 2a  Fresh++;.}../*.*
1b80: 2a 20 49 6e 73 65 72 74 20 61 20 6e 65 77 20 76  * Insert a new v
1b90: 61 6c 75 65 20 69 6e 74 6f 20 61 20 52 6f 77 53  alue into a RowS
1ba0: 65 74 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 61  et..**.** The ma
1bb0: 6c 6c 6f 63 46 61 69 6c 65 64 20 66 6c 61 67 20  llocFailed flag 
1bc0: 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65 20  of the database 
1bd0: 63 6f 6e 6e 65 63 74 69 6f 6e 20 69 73 20 73 65  connection is se
1be0: 74 20 69 66 20 61 0a 2a 2a 20 6d 65 6d 6f 72 79  t if a.** memory
1bf0: 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 66 61 69 6c   allocation fail
1c00: 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  s..*/.void sqlit
1c10: 65 33 52 6f 77 53 65 74 49 6e 73 65 72 74 28 52  e3RowSetInsert(R
1c20: 6f 77 53 65 74 20 2a 70 2c 20 69 36 34 20 72 6f  owSet *p, i64 ro
1c30: 77 69 64 29 7b 0a 20 20 73 74 72 75 63 74 20 52  wid){.  struct R
1c40: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 45 6e 74  owSetEntry *pEnt
1c50: 72 79 3b 20 20 2f 2a 20 54 68 65 20 6e 65 77 20  ry;  /* The new 
1c60: 65 6e 74 72 79 20 2a 2f 0a 20 20 73 74 72 75 63  entry */.  struc
1c70: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70  t RowSetEntry *p
1c80: 4c 61 73 74 3b 20 20 20 2f 2a 20 54 68 65 20 6c  Last;   /* The l
1c90: 61 73 74 20 70 72 69 6f 72 20 65 6e 74 72 79 20  ast prior entry 
1ca0: 2a 2f 0a 0a 20 20 2f 2a 20 54 68 69 73 20 72 6f  */..  /* This ro
1cb0: 75 74 69 6e 65 20 69 73 20 6e 65 76 65 72 20 63  utine is never c
1cc0: 61 6c 6c 65 64 20 61 66 74 65 72 20 73 71 6c 69  alled after sqli
1cd0: 74 65 33 52 6f 77 53 65 74 4e 65 78 74 28 29 20  te3RowSetNext() 
1ce0: 2a 2f 0a 20 20 61 73 73 65 72 74 28 20 70 21 3d  */.  assert( p!=
1cf0: 30 20 26 26 20 28 70 2d 3e 72 73 46 6c 61 67 73  0 && (p->rsFlags
1d00: 20 26 20 52 4f 57 53 45 54 5f 4e 45 58 54 29 3d   & ROWSET_NEXT)=
1d10: 3d 30 20 29 3b 0a 0a 20 20 70 45 6e 74 72 79 20  =0 );..  pEntry 
1d20: 3d 20 72 6f 77 53 65 74 45 6e 74 72 79 41 6c 6c  = rowSetEntryAll
1d30: 6f 63 28 70 29 3b 0a 20 20 69 66 28 20 70 45 6e  oc(p);.  if( pEn
1d40: 74 72 79 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b  try==0 ) return;
1d50: 0a 20 20 70 45 6e 74 72 79 2d 3e 76 20 3d 20 72  .  pEntry->v = r
1d60: 6f 77 69 64 3b 0a 20 20 70 45 6e 74 72 79 2d 3e  owid;.  pEntry->
1d70: 70 52 69 67 68 74 20 3d 20 30 3b 0a 20 20 70 4c  pRight = 0;.  pL
1d80: 61 73 74 20 3d 20 70 2d 3e 70 4c 61 73 74 3b 0a  ast = p->pLast;.
1d90: 20 20 69 66 28 20 70 4c 61 73 74 20 29 7b 0a 20    if( pLast ){. 
1da0: 20 20 20 69 66 28 20 72 6f 77 69 64 3c 3d 70 4c     if( rowid<=pL
1db0: 61 73 74 2d 3e 76 20 29 7b 20 20 2f 2a 4f 50 54  ast->v ){  /*OPT
1dc0: 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41 4c  IMIZATION-IF-FAL
1dd0: 53 45 2a 2f 0a 20 20 20 20 20 20 2f 2a 20 41 76  SE*/.      /* Av
1de0: 6f 69 64 20 75 6e 6e 65 63 65 73 73 61 72 79 20  oid unnecessary 
1df0: 73 6f 72 74 73 20 62 79 20 70 72 65 73 65 72 76  sorts by preserv
1e00: 69 6e 67 20 74 68 65 20 52 4f 57 53 45 54 5f 53  ing the ROWSET_S
1e10: 4f 52 54 45 44 20 66 6c 61 67 73 0a 20 20 20 20  ORTED flags.    
1e20: 20 20 2a 2a 20 77 68 65 72 65 20 70 6f 73 73 69    ** where possi
1e30: 62 6c 65 20 2a 2f 0a 20 20 20 20 20 20 70 2d 3e  ble */.      p->
1e40: 72 73 46 6c 61 67 73 20 26 3d 20 7e 52 4f 57 53  rsFlags &= ~ROWS
1e50: 45 54 5f 53 4f 52 54 45 44 3b 0a 20 20 20 20 7d  ET_SORTED;.    }
1e60: 0a 20 20 20 20 70 4c 61 73 74 2d 3e 70 52 69 67  .    pLast->pRig
1e70: 68 74 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20 7d  ht = pEntry;.  }
1e80: 65 6c 73 65 7b 0a 20 20 20 20 70 2d 3e 70 45 6e  else{.    p->pEn
1e90: 74 72 79 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20  try = pEntry;.  
1ea0: 7d 0a 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20 70  }.  p->pLast = p
1eb0: 45 6e 74 72 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  Entry;.}../*.** 
1ec0: 4d 65 72 67 65 20 74 77 6f 20 6c 69 73 74 73 20  Merge two lists 
1ed0: 6f 66 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f  of RowSetEntry o
1ee0: 62 6a 65 63 74 73 2e 20 20 52 65 6d 6f 76 65 20  bjects.  Remove 
1ef0: 64 75 70 6c 69 63 61 74 65 73 2e 0a 2a 2a 0a 2a  duplicates..**.*
1f00: 2a 20 54 68 65 20 69 6e 70 75 74 20 6c 69 73 74  * The input list
1f10: 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 64 20  s are connected 
1f20: 76 69 61 20 70 52 69 67 68 74 20 70 6f 69 6e 74  via pRight point
1f30: 65 72 73 20 61 6e 64 20 61 72 65 20 0a 2a 2a 20  ers and are .** 
1f40: 61 73 73 75 6d 65 64 20 74 6f 20 65 61 63 68 20  assumed to each 
1f50: 61 6c 72 65 61 64 79 20 62 65 20 69 6e 20 73 6f  already be in so
1f60: 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2f 0a 73  rted order..*/.s
1f70: 74 61 74 69 63 20 73 74 72 75 63 74 20 52 6f 77  tatic struct Row
1f80: 53 65 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74  SetEntry *rowSet
1f90: 45 6e 74 72 79 4d 65 72 67 65 28 0a 20 20 73 74  EntryMerge(.  st
1fa0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1fb0: 20 2a 70 41 2c 20 20 20 20 2f 2a 20 46 69 72 73   *pA,    /* Firs
1fc0: 74 20 73 6f 72 74 65 64 20 6c 69 73 74 20 74 6f  t sorted list to
1fd0: 20 62 65 20 6d 65 72 67 65 64 20 2a 2f 0a 20 20   be merged */.  
1fe0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1ff0: 72 79 20 2a 70 42 20 20 20 20 20 2f 2a 20 53 65  ry *pB     /* Se
2000: 63 6f 6e 64 20 73 6f 72 74 65 64 20 6c 69 73 74  cond sorted list
2010: 20 74 6f 20 62 65 20 6d 65 72 67 65 64 20 2a 2f   to be merged */
2020: 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 52 6f 77  .){.  struct Row
2030: 53 65 74 45 6e 74 72 79 20 68 65 61 64 3b 0a 20  SetEntry head;. 
2040: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
2050: 74 72 79 20 2a 70 54 61 69 6c 3b 0a 0a 20 20 70  try *pTail;..  p
2060: 54 61 69 6c 20 3d 20 26 68 65 61 64 3b 0a 20 20  Tail = &head;.  
2070: 61 73 73 65 72 74 28 20 70 41 21 3d 30 20 26 26  assert( pA!=0 &&
2080: 20 70 42 21 3d 30 20 29 3b 0a 20 20 66 6f 72 28   pB!=0 );.  for(
2090: 3b 3b 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  ;;){.    assert(
20a0: 20 70 41 2d 3e 70 52 69 67 68 74 3d 3d 30 20 7c   pA->pRight==0 |
20b0: 7c 20 70 41 2d 3e 76 3c 3d 70 41 2d 3e 70 52 69  | pA->v<=pA->pRi
20c0: 67 68 74 2d 3e 76 20 29 3b 0a 20 20 20 20 61 73  ght->v );.    as
20d0: 73 65 72 74 28 20 70 42 2d 3e 70 52 69 67 68 74  sert( pB->pRight
20e0: 3d 3d 30 20 7c 7c 20 70 42 2d 3e 76 3c 3d 70 42  ==0 || pB->v<=pB
20f0: 2d 3e 70 52 69 67 68 74 2d 3e 76 20 29 3b 0a 20  ->pRight->v );. 
2100: 20 20 20 69 66 28 20 70 41 2d 3e 76 3c 3d 70 42     if( pA->v<=pB
2110: 2d 3e 76 20 29 7b 0a 20 20 20 20 20 20 69 66 28  ->v ){.      if(
2120: 20 70 41 2d 3e 76 3c 70 42 2d 3e 76 20 29 20 70   pA->v<pB->v ) p
2130: 54 61 69 6c 20 3d 20 70 54 61 69 6c 2d 3e 70 52  Tail = pTail->pR
2140: 69 67 68 74 20 3d 20 70 41 3b 0a 20 20 20 20 20  ight = pA;.     
2150: 20 70 41 20 3d 20 70 41 2d 3e 70 52 69 67 68 74   pA = pA->pRight
2160: 3b 0a 20 20 20 20 20 20 69 66 28 20 70 41 3d 3d  ;.      if( pA==
2170: 30 20 29 7b 0a 20 20 20 20 20 20 20 20 70 54 61  0 ){.        pTa
2180: 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42 3b  il->pRight = pB;
2190: 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a  .        break;.
21a0: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 65 6c 73        }.    }els
21b0: 65 7b 0a 20 20 20 20 20 20 70 54 61 69 6c 20 3d  e{.      pTail =
21c0: 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74 20 3d   pTail->pRight =
21d0: 20 70 42 3b 0a 20 20 20 20 20 20 70 42 20 3d 20   pB;.      pB = 
21e0: 70 42 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20  pB->pRight;.    
21f0: 20 20 69 66 28 20 70 42 3d 3d 30 20 29 7b 0a 20    if( pB==0 ){. 
2200: 20 20 20 20 20 20 20 70 54 61 69 6c 2d 3e 70 52         pTail->pR
2210: 69 67 68 74 20 3d 20 70 41 3b 0a 20 20 20 20 20  ight = pA;.     
2220: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20     break;.      
2230: 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65  }.    }.  }.  re
2240: 74 75 72 6e 20 68 65 61 64 2e 70 52 69 67 68 74  turn head.pRight
2250: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53 6f 72 74 20  ;.}../*.** Sort 
2260: 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 6e 20  all elements on 
2270: 74 68 65 20 6c 69 73 74 20 6f 66 20 52 6f 77 53  the list of RowS
2280: 65 74 45 6e 74 72 79 20 6f 62 6a 65 63 74 73 20  etEntry objects 
2290: 69 6e 74 6f 20 6f 72 64 65 72 20 6f 66 0a 2a 2a  into order of.**
22a0: 20 69 6e 63 72 65 61 73 69 6e 67 20 76 2e 0a 2a   increasing v..*
22b0: 2f 20 0a 73 74 61 74 69 63 20 73 74 72 75 63 74  / .static struct
22c0: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 72 6f   RowSetEntry *ro
22d0: 77 53 65 74 45 6e 74 72 79 53 6f 72 74 28 73 74  wSetEntrySort(st
22e0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
22f0: 20 2a 70 49 6e 29 7b 0a 20 20 75 6e 73 69 67 6e   *pIn){.  unsign
2300: 65 64 20 69 6e 74 20 69 3b 0a 20 20 73 74 72 75  ed int i;.  stru
2310: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2320: 70 4e 65 78 74 2c 20 2a 61 42 75 63 6b 65 74 5b  pNext, *aBucket[
2330: 34 30 5d 3b 0a 0a 20 20 6d 65 6d 73 65 74 28 61  40];..  memset(a
2340: 42 75 63 6b 65 74 2c 20 30 2c 20 73 69 7a 65 6f  Bucket, 0, sizeo
2350: 66 28 61 42 75 63 6b 65 74 29 29 3b 0a 20 20 77  f(aBucket));.  w
2360: 68 69 6c 65 28 20 70 49 6e 20 29 7b 0a 20 20 20  hile( pIn ){.   
2370: 20 70 4e 65 78 74 20 3d 20 70 49 6e 2d 3e 70 52   pNext = pIn->pR
2380: 69 67 68 74 3b 0a 20 20 20 20 70 49 6e 2d 3e 70  ight;.    pIn->p
2390: 52 69 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 66  Right = 0;.    f
23a0: 6f 72 28 69 3d 30 3b 20 61 42 75 63 6b 65 74 5b  or(i=0; aBucket[
23b0: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20  i]; i++){.      
23c0: 70 49 6e 20 3d 20 72 6f 77 53 65 74 45 6e 74 72  pIn = rowSetEntr
23d0: 79 4d 65 72 67 65 28 61 42 75 63 6b 65 74 5b 69  yMerge(aBucket[i
23e0: 5d 2c 20 70 49 6e 29 3b 0a 20 20 20 20 20 20 61  ], pIn);.      a
23f0: 42 75 63 6b 65 74 5b 69 5d 20 3d 20 30 3b 0a 20  Bucket[i] = 0;. 
2400: 20 20 20 7d 0a 20 20 20 20 61 42 75 63 6b 65 74     }.    aBucket
2410: 5b 69 5d 20 3d 20 70 49 6e 3b 0a 20 20 20 20 70  [i] = pIn;.    p
2420: 49 6e 20 3d 20 70 4e 65 78 74 3b 0a 20 20 7d 0a  In = pNext;.  }.
2430: 20 20 70 49 6e 20 3d 20 61 42 75 63 6b 65 74 5b    pIn = aBucket[
2440: 30 5d 3b 0a 20 20 66 6f 72 28 69 3d 31 3b 20 69  0];.  for(i=1; i
2450: 3c 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74 29  <sizeof(aBucket)
2460: 2f 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74 5b  /sizeof(aBucket[
2470: 30 5d 29 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69  0]); i++){.    i
2480: 66 28 20 61 42 75 63 6b 65 74 5b 69 5d 3d 3d 30  f( aBucket[i]==0
2490: 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20   ) continue;.   
24a0: 20 70 49 6e 20 3d 20 70 49 6e 20 3f 20 72 6f 77   pIn = pIn ? row
24b0: 53 65 74 45 6e 74 72 79 4d 65 72 67 65 28 70 49  SetEntryMerge(pI
24c0: 6e 2c 20 61 42 75 63 6b 65 74 5b 69 5d 29 20 3a  n, aBucket[i]) :
24d0: 20 61 42 75 63 6b 65 74 5b 69 5d 3b 0a 20 20 7d   aBucket[i];.  }
24e0: 0a 20 20 72 65 74 75 72 6e 20 70 49 6e 3b 0a 7d  .  return pIn;.}
24f0: 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 69 6e 70  .../*.** The inp
2500: 75 74 2c 20 70 49 6e 2c 20 69 73 20 61 20 62 69  ut, pIn, is a bi
2510: 6e 61 72 79 20 74 72 65 65 20 28 6f 72 20 73 75  nary tree (or su
2520: 62 74 72 65 65 29 20 6f 66 20 52 6f 77 53 65 74  btree) of RowSet
2530: 45 6e 74 72 79 20 6f 62 6a 65 63 74 73 2e 0a 2a  Entry objects..*
2540: 2a 20 43 6f 6e 76 65 72 74 20 74 68 69 73 20 74  * Convert this t
2550: 72 65 65 20 69 6e 74 6f 20 61 20 6c 69 6e 6b 65  ree into a linke
2560: 64 20 6c 69 73 74 20 63 6f 6e 6e 65 63 74 65 64  d list connected
2570: 20 62 79 20 74 68 65 20 70 52 69 67 68 74 20 70   by the pRight p
2580: 6f 69 6e 74 65 72 73 0a 2a 2a 20 61 6e 64 20 72  ointers.** and r
2590: 65 74 75 72 6e 20 70 6f 69 6e 74 65 72 73 20 74  eturn pointers t
25a0: 6f 20 74 68 65 20 66 69 72 73 74 20 61 6e 64 20  o the first and 
25b0: 6c 61 73 74 20 65 6c 65 6d 65 6e 74 73 20 6f 66  last elements of
25c0: 20 74 68 65 20 6e 65 77 20 6c 69 73 74 2e 0a 2a   the new list..*
25d0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72 6f  /.static void ro
25e0: 77 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 0a  wSetTreeToList(.
25f0: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
2600: 6e 74 72 79 20 2a 70 49 6e 2c 20 20 20 20 20 20  ntry *pIn,      
2610: 20 20 20 2f 2a 20 52 6f 6f 74 20 6f 66 20 74 68     /* Root of th
2620: 65 20 69 6e 70 75 74 20 74 72 65 65 20 2a 2f 0a  e input tree */.
2630: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
2640: 6e 74 72 79 20 2a 2a 70 70 46 69 72 73 74 2c 20  ntry **ppFirst, 
2650: 20 20 20 2f 2a 20 57 72 69 74 65 20 68 65 61 64     /* Write head
2660: 20 6f 66 20 74 68 65 20 6f 75 74 70 75 74 20 6c   of the output l
2670: 69 73 74 20 68 65 72 65 20 2a 2f 0a 20 20 73 74  ist here */.  st
2680: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2690: 20 2a 2a 70 70 4c 61 73 74 20 20 20 20 20 20 2f   **ppLast      /
26a0: 2a 20 57 72 69 74 65 20 74 61 69 6c 20 6f 66 20  * Write tail of 
26b0: 74 68 65 20 6f 75 74 70 75 74 20 6c 69 73 74 20  the output list 
26c0: 68 65 72 65 20 2a 2f 0a 29 7b 0a 20 20 61 73 73  here */.){.  ass
26d0: 65 72 74 28 20 70 49 6e 21 3d 30 20 29 3b 0a 20  ert( pIn!=0 );. 
26e0: 20 69 66 28 20 70 49 6e 2d 3e 70 4c 65 66 74 20   if( pIn->pLeft 
26f0: 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20 52 6f  ){.    struct Ro
2700: 77 53 65 74 45 6e 74 72 79 20 2a 70 3b 0a 20 20  wSetEntry *p;.  
2710: 20 20 72 6f 77 53 65 74 54 72 65 65 54 6f 4c 69    rowSetTreeToLi
2720: 73 74 28 70 49 6e 2d 3e 70 4c 65 66 74 2c 20 70  st(pIn->pLeft, p
2730: 70 46 69 72 73 74 2c 20 26 70 29 3b 0a 20 20 20  pFirst, &p);.   
2740: 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 70 49 6e   p->pRight = pIn
2750: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a  ;.  }else{.    *
2760: 70 70 46 69 72 73 74 20 3d 20 70 49 6e 3b 0a 20  ppFirst = pIn;. 
2770: 20 7d 0a 20 20 69 66 28 20 70 49 6e 2d 3e 70 52   }.  if( pIn->pR
2780: 69 67 68 74 20 29 7b 0a 20 20 20 20 72 6f 77 53  ight ){.    rowS
2790: 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70 49 6e  etTreeToList(pIn
27a0: 2d 3e 70 52 69 67 68 74 2c 20 26 70 49 6e 2d 3e  ->pRight, &pIn->
27b0: 70 52 69 67 68 74 2c 20 70 70 4c 61 73 74 29 3b  pRight, ppLast);
27c0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70  .  }else{.    *p
27d0: 70 4c 61 73 74 20 3d 20 70 49 6e 3b 0a 20 20 7d  pLast = pIn;.  }
27e0: 0a 20 20 61 73 73 65 72 74 28 20 28 2a 70 70 4c  .  assert( (*ppL
27f0: 61 73 74 29 2d 3e 70 52 69 67 68 74 3d 3d 30 20  ast)->pRight==0 
2800: 29 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6e  );.}.../*.** Con
2810: 76 65 72 74 20 61 20 73 6f 72 74 65 64 20 6c 69  vert a sorted li
2820: 73 74 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 28  st of elements (
2830: 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 70 52 69  connected by pRi
2840: 67 68 74 29 20 69 6e 74 6f 20 61 20 62 69 6e 61  ght) into a bina
2850: 72 79 0a 2a 2a 20 74 72 65 65 20 77 69 74 68 20  ry.** tree with 
2860: 64 65 70 74 68 20 6f 66 20 69 44 65 70 74 68 2e  depth of iDepth.
2870: 20 20 41 20 64 65 70 74 68 20 6f 66 20 31 20 6d    A depth of 1 m
2880: 65 61 6e 73 20 74 68 65 20 74 72 65 65 20 63 6f  eans the tree co
2890: 6e 74 61 69 6e 73 20 61 20 73 69 6e 67 6c 65 0a  ntains a single.
28a0: 2a 2a 20 6e 6f 64 65 20 74 61 6b 65 6e 20 66 72  ** node taken fr
28b0: 6f 6d 20 74 68 65 20 68 65 61 64 20 6f 66 20 2a  om the head of *
28c0: 70 70 4c 69 73 74 2e 20 20 41 20 64 65 70 74 68  ppList.  A depth
28d0: 20 6f 66 20 32 20 6d 65 61 6e 73 20 61 20 74 72   of 2 means a tr
28e0: 65 65 20 77 69 74 68 0a 2a 2a 20 74 68 72 65 65  ee with.** three
28f0: 20 6e 6f 64 65 73 2e 20 20 41 6e 64 20 73 6f 20   nodes.  And so 
2900: 66 6f 72 74 68 2e 0a 2a 2a 0a 2a 2a 20 55 73 65  forth..**.** Use
2910: 20 61 73 20 6d 61 6e 79 20 65 6e 74 72 69 65 73   as many entries
2920: 20 66 72 6f 6d 20 74 68 65 20 69 6e 70 75 74 20   from the input 
2930: 6c 69 73 74 20 61 73 20 72 65 71 75 69 72 65 64  list as required
2940: 20 61 6e 64 20 75 70 64 61 74 65 20 74 68 65 0a   and update the.
2950: 2a 2a 20 2a 70 70 4c 69 73 74 20 74 6f 20 70 6f  ** *ppList to po
2960: 69 6e 74 20 74 6f 20 74 68 65 20 75 6e 75 73 65  int to the unuse
2970: 64 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68  d elements of th
2980: 65 20 6c 69 73 74 2e 20 20 49 66 20 74 68 65 20  e list.  If the 
2990: 69 6e 70 75 74 0a 2a 2a 20 6c 69 73 74 20 63 6f  input.** list co
29a0: 6e 74 61 69 6e 73 20 74 6f 6f 20 66 65 77 20 65  ntains too few e
29b0: 6c 65 6d 65 6e 74 73 2c 20 74 68 65 6e 20 63 6f  lements, then co
29c0: 6e 73 74 72 75 63 74 20 61 6e 20 69 6e 63 6f 6d  nstruct an incom
29d0: 70 6c 65 74 65 20 74 72 65 65 0a 2a 2a 20 61 6e  plete tree.** an
29e0: 64 20 6c 65 61 76 65 20 2a 70 70 4c 69 73 74 20  d leave *ppList 
29f0: 73 65 74 20 74 6f 20 4e 55 4c 4c 2e 0a 2a 2a 0a  set to NULL..**.
2a00: 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e  ** Return a poin
2a10: 74 65 72 20 74 6f 20 74 68 65 20 72 6f 6f 74 20  ter to the root 
2a20: 6f 66 20 74 68 65 20 63 6f 6e 73 74 72 75 63 74  of the construct
2a30: 65 64 20 62 69 6e 61 72 79 20 74 72 65 65 2e 0a  ed binary tree..
2a40: 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75 63 74  */.static struct
2a50: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 72 6f   RowSetEntry *ro
2a60: 77 53 65 74 4e 44 65 65 70 54 72 65 65 28 0a 20  wSetNDeepTree(. 
2a70: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
2a80: 74 72 79 20 2a 2a 70 70 4c 69 73 74 2c 0a 20 20  try **ppList,.  
2a90: 69 6e 74 20 69 44 65 70 74 68 0a 29 7b 0a 20 20  int iDepth.){.  
2aa0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
2ab0: 72 79 20 2a 70 3b 20 20 20 20 20 20 20 20 20 2f  ry *p;         /
2ac0: 2a 20 52 6f 6f 74 20 6f 66 20 74 68 65 20 6e 65  * Root of the ne
2ad0: 77 20 74 72 65 65 20 2a 2f 0a 20 20 73 74 72 75  w tree */.  stru
2ae0: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2af0: 70 4c 65 66 74 3b 20 20 20 20 20 2f 2a 20 4c 65  pLeft;     /* Le
2b00: 66 74 20 73 75 62 74 72 65 65 20 2a 2f 0a 20 20  ft subtree */.  
2b10: 69 66 28 20 2a 70 70 4c 69 73 74 3d 3d 30 20 29  if( *ppList==0 )
2b20: 7b 20 2f 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e  { /*OPTIMIZATION
2b30: 2d 49 46 2d 54 52 55 45 2a 2f 0a 20 20 20 20 2f  -IF-TRUE*/.    /
2b40: 2a 20 50 72 65 76 65 6e 74 20 75 6e 6e 65 63 65  * Prevent unnece
2b50: 73 73 61 72 79 20 64 65 65 70 20 72 65 63 75 72  ssary deep recur
2b60: 73 69 6f 6e 20 77 68 65 6e 20 77 65 20 72 75 6e  sion when we run
2b70: 20 6f 75 74 20 6f 66 20 65 6e 74 72 69 65 73 20   out of entries 
2b80: 2a 2f 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b  */.    return 0;
2b90: 20 0a 20 20 7d 0a 20 20 69 66 28 20 69 44 65 70   .  }.  if( iDep
2ba0: 74 68 3e 31 20 29 7b 20 20 20 2f 2a 4f 50 54 49  th>1 ){   /*OPTI
2bb0: 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 54 52 55 45  MIZATION-IF-TRUE
2bc0: 2a 2f 0a 20 20 20 20 2f 2a 20 54 68 69 73 20 62  */.    /* This b
2bd0: 72 61 6e 63 68 20 63 61 75 73 65 73 20 61 20 2a  ranch causes a *
2be0: 62 61 6c 61 6e 63 65 64 2a 20 74 72 65 65 20 74  balanced* tree t
2bf0: 6f 20 62 65 20 67 65 6e 65 72 61 74 65 64 2e 20  o be generated. 
2c00: 20 41 20 76 61 6c 69 64 20 74 72 65 65 0a 20 20   A valid tree.  
2c10: 20 20 2a 2a 20 69 73 20 73 74 69 6c 6c 20 67 65    ** is still ge
2c20: 6e 65 72 61 74 65 64 20 77 69 74 68 6f 75 74 20  nerated without 
2c30: 74 68 69 73 20 62 72 61 6e 63 68 2c 20 62 75 74  this branch, but
2c40: 20 74 68 65 20 74 72 65 65 20 69 73 20 77 69 6c   the tree is wil
2c50: 64 6c 79 0a 20 20 20 20 2a 2a 20 75 6e 62 61 6c  dly.    ** unbal
2c60: 61 6e 63 65 64 20 61 6e 64 20 69 6e 65 66 66 69  anced and ineffi
2c70: 63 69 65 6e 74 2e 20 2a 2f 0a 20 20 20 20 70 4c  cient. */.    pL
2c80: 65 66 74 20 3d 20 72 6f 77 53 65 74 4e 44 65 65  eft = rowSetNDee
2c90: 70 54 72 65 65 28 70 70 4c 69 73 74 2c 20 69 44  pTree(ppList, iD
2ca0: 65 70 74 68 2d 31 29 3b 0a 20 20 20 20 70 20 3d  epth-1);.    p =
2cb0: 20 2a 70 70 4c 69 73 74 3b 0a 20 20 20 20 69 66   *ppList;.    if
2cc0: 28 20 70 3d 3d 30 20 29 7b 20 20 20 20 20 2f 2a  ( p==0 ){     /*
2cd0: 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d  OPTIMIZATION-IF-
2ce0: 46 41 4c 53 45 2a 2f 0a 20 20 20 20 20 20 2f 2a  FALSE*/.      /*
2cf0: 20 49 74 20 69 73 20 73 61 66 65 20 74 6f 20 61   It is safe to a
2d00: 6c 77 61 79 73 20 72 65 74 75 72 6e 20 68 65 72  lways return her
2d10: 65 2c 20 62 75 74 20 74 68 65 20 72 65 73 75 6c  e, but the resul
2d20: 74 69 6e 67 20 74 72 65 65 0a 20 20 20 20 20 20  ting tree.      
2d30: 2a 2a 20 77 6f 75 6c 64 20 62 65 20 75 6e 62 61  ** would be unba
2d40: 6c 61 6e 63 65 64 20 2a 2f 0a 20 20 20 20 20 20  lanced */.      
2d50: 72 65 74 75 72 6e 20 70 4c 65 66 74 3b 0a 20 20  return pLeft;.  
2d60: 20 20 7d 0a 20 20 20 20 70 2d 3e 70 4c 65 66 74    }.    p->pLeft
2d70: 20 3d 20 70 4c 65 66 74 3b 0a 20 20 20 20 2a 70   = pLeft;.    *p
2d80: 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52 69 67 68  pList = p->pRigh
2d90: 74 3b 0a 20 20 20 20 70 2d 3e 70 52 69 67 68 74  t;.    p->pRight
2da0: 20 3d 20 72 6f 77 53 65 74 4e 44 65 65 70 54 72   = rowSetNDeepTr
2db0: 65 65 28 70 70 4c 69 73 74 2c 20 69 44 65 70 74  ee(ppList, iDept
2dc0: 68 2d 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  h-1);.  }else{. 
2dd0: 20 20 20 70 20 3d 20 2a 70 70 4c 69 73 74 3b 0a     p = *ppList;.
2de0: 20 20 20 20 2a 70 70 4c 69 73 74 20 3d 20 70 2d      *ppList = p-
2df0: 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 70 2d 3e  >pRight;.    p->
2e00: 70 4c 65 66 74 20 3d 20 70 2d 3e 70 52 69 67 68  pLeft = p->pRigh
2e10: 74 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 72 65 74  t = 0;.  }.  ret
2e20: 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  urn p;.}../*.** 
2e30: 43 6f 6e 76 65 72 74 20 61 20 73 6f 72 74 65 64  Convert a sorted
2e40: 20 6c 69 73 74 20 6f 66 20 65 6c 65 6d 65 6e 74   list of element
2e50: 73 20 69 6e 74 6f 20 61 20 62 69 6e 61 72 79 20  s into a binary 
2e60: 74 72 65 65 2e 20 4d 61 6b 65 20 74 68 65 20 74  tree. Make the t
2e70: 72 65 65 0a 2a 2a 20 61 73 20 64 65 65 70 20 61  ree.** as deep a
2e80: 73 20 69 74 20 6e 65 65 64 73 20 74 6f 20 62 65  s it needs to be
2e90: 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 63 6f 6e   in order to con
2ea0: 74 61 69 6e 20 74 68 65 20 65 6e 74 69 72 65 20  tain the entire 
2eb0: 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  list..*/.static 
2ec0: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
2ed0: 72 79 20 2a 72 6f 77 53 65 74 4c 69 73 74 54 6f  ry *rowSetListTo
2ee0: 54 72 65 65 28 73 74 72 75 63 74 20 52 6f 77 53  Tree(struct RowS
2ef0: 65 74 45 6e 74 72 79 20 2a 70 4c 69 73 74 29 7b  etEntry *pList){
2f00: 0a 20 20 69 6e 74 20 69 44 65 70 74 68 3b 20 20  .  int iDepth;  
2f10: 20 20 20 20 20 20 20 20 20 2f 2a 20 44 65 70 74           /* Dept
2f20: 68 20 6f 66 20 74 68 65 20 74 72 65 65 20 73 6f  h of the tree so
2f30: 20 66 61 72 20 2a 2f 0a 20 20 73 74 72 75 63 74   far */.  struct
2f40: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 3b   RowSetEntry *p;
2f50: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e         /* Curren
2f60: 74 20 74 72 65 65 20 72 6f 6f 74 20 2a 2f 0a 20  t tree root */. 
2f70: 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e   struct RowSetEn
2f80: 74 72 79 20 2a 70 4c 65 66 74 3b 20 20 20 2f 2a  try *pLeft;   /*
2f90: 20 4c 65 66 74 20 73 75 62 74 72 65 65 20 2a 2f   Left subtree */
2fa0: 0a 0a 20 20 61 73 73 65 72 74 28 20 70 4c 69 73  ..  assert( pLis
2fb0: 74 21 3d 30 20 29 3b 0a 20 20 70 20 3d 20 70 4c  t!=0 );.  p = pL
2fc0: 69 73 74 3b 0a 20 20 70 4c 69 73 74 20 3d 20 70  ist;.  pList = p
2fd0: 2d 3e 70 52 69 67 68 74 3b 0a 20 20 70 2d 3e 70  ->pRight;.  p->p
2fe0: 4c 65 66 74 20 3d 20 70 2d 3e 70 52 69 67 68 74  Left = p->pRight
2ff0: 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 44 65 70   = 0;.  for(iDep
3000: 74 68 3d 31 3b 20 70 4c 69 73 74 3b 20 69 44 65  th=1; pList; iDe
3010: 70 74 68 2b 2b 29 7b 0a 20 20 20 20 70 4c 65 66  pth++){.    pLef
3020: 74 20 3d 20 70 3b 0a 20 20 20 20 70 20 3d 20 70  t = p;.    p = p
3030: 4c 69 73 74 3b 0a 20 20 20 20 70 4c 69 73 74 20  List;.    pList 
3040: 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  = p->pRight;.   
3050: 20 70 2d 3e 70 4c 65 66 74 20 3d 20 70 4c 65 66   p->pLeft = pLef
3060: 74 3b 0a 20 20 20 20 70 2d 3e 70 52 69 67 68 74  t;.    p->pRight
3070: 20 3d 20 72 6f 77 53 65 74 4e 44 65 65 70 54 72   = rowSetNDeepTr
3080: 65 65 28 26 70 4c 69 73 74 2c 20 69 44 65 70 74  ee(&pList, iDept
3090: 68 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e  h);.  }.  return
30a0: 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 74   p;.}../*.** Ext
30b0: 72 61 63 74 20 74 68 65 20 73 6d 61 6c 6c 65 73  ract the smalles
30c0: 74 20 65 6c 65 6d 65 6e 74 20 66 72 6f 6d 20 74  t element from t
30d0: 68 65 20 52 6f 77 53 65 74 2e 0a 2a 2a 20 57 72  he RowSet..** Wr
30e0: 69 74 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 20  ite the element 
30f0: 69 6e 74 6f 20 2a 70 52 6f 77 69 64 2e 20 20 52  into *pRowid.  R
3100: 65 74 75 72 6e 20 31 20 6f 6e 20 73 75 63 63 65  eturn 1 on succe
3110: 73 73 2e 20 20 52 65 74 75 72 6e 0a 2a 2a 20 30  ss.  Return.** 0
3120: 20 69 66 20 74 68 65 20 52 6f 77 53 65 74 20 69   if the RowSet i
3130: 73 20 61 6c 72 65 61 64 79 20 65 6d 70 74 79 2e  s already empty.
3140: 0a 2a 2a 0a 2a 2a 20 41 66 74 65 72 20 74 68 69  .**.** After thi
3150: 73 20 72 6f 75 74 69 6e 65 20 68 61 73 20 62 65  s routine has be
3160: 65 6e 20 63 61 6c 6c 65 64 2c 20 74 68 65 20 73  en called, the s
3170: 71 6c 69 74 65 33 52 6f 77 53 65 74 49 6e 73 65  qlite3RowSetInse
3180: 72 74 28 29 0a 2a 2a 20 72 6f 75 74 69 6e 65 20  rt().** routine 
3190: 6d 61 79 20 6e 6f 74 20 62 65 20 63 61 6c 6c 65  may not be calle
31a0: 64 20 61 67 61 69 6e 2e 0a 2a 2a 0a 2a 2a 20 54  d again..**.** T
31b0: 68 69 73 20 72 6f 75 74 69 6e 65 20 6d 61 79 20  his routine may 
31c0: 6e 6f 74 20 62 65 20 63 61 6c 6c 65 64 20 61 66  not be called af
31d0: 74 65 72 20 73 71 6c 69 74 65 33 52 6f 77 53 65  ter sqlite3RowSe
31e0: 74 54 65 73 74 28 29 20 68 61 73 0a 2a 2a 20 62  tTest() has.** b
31f0: 65 65 6e 20 75 73 65 64 2e 20 20 4f 6c 64 65 72  een used.  Older
3200: 20 76 65 72 73 69 6f 6e 73 20 6f 66 20 52 6f 77   versions of Row
3210: 53 65 74 20 61 6c 6c 6f 77 65 64 20 74 68 61 74  Set allowed that
3220: 2c 20 62 75 74 20 61 73 20 74 68 65 0a 2a 2a 20  , but as the.** 
3230: 63 61 70 61 62 69 6c 69 74 79 20 77 61 73 20 6e  capability was n
3240: 6f 74 20 75 73 65 64 20 62 79 20 74 68 65 20 63  ot used by the c
3250: 6f 64 65 20 67 65 6e 65 72 61 74 6f 72 2c 20 69  ode generator, i
3260: 74 20 77 61 73 20 72 65 6d 6f 76 65 64 0a 2a 2a  t was removed.**
3270: 20 66 6f 72 20 63 6f 64 65 20 65 63 6f 6e 6f 6d   for code econom
3280: 79 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65  y..*/.int sqlite
3290: 33 52 6f 77 53 65 74 4e 65 78 74 28 52 6f 77 53  3RowSetNext(RowS
32a0: 65 74 20 2a 70 2c 20 69 36 34 20 2a 70 52 6f 77  et *p, i64 *pRow
32b0: 69 64 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70  id){.  assert( p
32c0: 21 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28  !=0 );.  assert(
32d0: 20 70 2d 3e 70 46 6f 72 65 73 74 3d 3d 30 20 29   p->pForest==0 )
32e0: 3b 20 20 2f 2a 20 43 61 6e 6e 6f 74 20 62 65 20  ;  /* Cannot be 
32f0: 75 73 65 64 20 77 69 74 68 20 73 71 6c 69 74 65  used with sqlite
3300: 33 52 6f 77 53 65 74 54 65 78 74 28 29 20 2a 2f  3RowSetText() */
3310: 0a 0a 20 20 2f 2a 20 4d 65 72 67 65 20 74 68 65  ..  /* Merge the
3320: 20 66 6f 72 65 73 74 20 69 6e 74 6f 20 61 20 73   forest into a s
3330: 69 6e 67 6c 65 20 73 6f 72 74 65 64 20 6c 69 73  ingle sorted lis
3340: 74 20 6f 6e 20 66 69 72 73 74 20 63 61 6c 6c 20  t on first call 
3350: 2a 2f 0a 20 20 69 66 28 20 28 70 2d 3e 72 73 46  */.  if( (p->rsF
3360: 6c 61 67 73 20 26 20 52 4f 57 53 45 54 5f 4e 45  lags & ROWSET_NE
3370: 58 54 29 3d 3d 30 20 29 7b 20 20 2f 2a 4f 50 54  XT)==0 ){  /*OPT
3380: 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41 4c  IMIZATION-IF-FAL
3390: 53 45 2a 2f 0a 20 20 20 20 69 66 28 20 28 70 2d  SE*/.    if( (p-
33a0: 3e 72 73 46 6c 61 67 73 20 26 20 52 4f 57 53 45  >rsFlags & ROWSE
33b0: 54 5f 53 4f 52 54 45 44 29 3d 3d 30 20 29 7b 20  T_SORTED)==0 ){ 
33c0: 20 2f 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d   /*OPTIMIZATION-
33d0: 49 46 2d 46 41 4c 53 45 2a 2f 0a 20 20 20 20 20  IF-FALSE*/.     
33e0: 20 70 2d 3e 70 45 6e 74 72 79 20 3d 20 72 6f 77   p->pEntry = row
33f0: 53 65 74 45 6e 74 72 79 53 6f 72 74 28 70 2d 3e  SetEntrySort(p->
3400: 70 45 6e 74 72 79 29 3b 0a 20 20 20 20 7d 0a 20  pEntry);.    }. 
3410: 20 20 20 70 2d 3e 72 73 46 6c 61 67 73 20 7c 3d     p->rsFlags |=
3420: 20 52 4f 57 53 45 54 5f 53 4f 52 54 45 44 7c 52   ROWSET_SORTED|R
3430: 4f 57 53 45 54 5f 4e 45 58 54 3b 0a 20 20 7d 0a  OWSET_NEXT;.  }.
3440: 0a 20 20 2f 2a 20 52 65 74 75 72 6e 20 74 68 65  .  /* Return the
3450: 20 6e 65 78 74 20 65 6e 74 72 79 20 6f 6e 20 74   next entry on t
3460: 68 65 20 6c 69 73 74 20 2a 2f 0a 20 20 69 66 28  he list */.  if(
3470: 20 70 2d 3e 70 45 6e 74 72 79 20 29 7b 0a 20 20   p->pEntry ){.  
3480: 20 20 2a 70 52 6f 77 69 64 20 3d 20 70 2d 3e 70    *pRowid = p->p
3490: 45 6e 74 72 79 2d 3e 76 3b 0a 20 20 20 20 70 2d  Entry->v;.    p-
34a0: 3e 70 45 6e 74 72 79 20 3d 20 70 2d 3e 70 45 6e  >pEntry = p->pEn
34b0: 74 72 79 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20  try->pRight;.   
34c0: 20 69 66 28 20 70 2d 3e 70 45 6e 74 72 79 3d 3d   if( p->pEntry==
34d0: 30 20 29 7b 20 2f 2a 4f 50 54 49 4d 49 5a 41 54  0 ){ /*OPTIMIZAT
34e0: 49 4f 4e 2d 49 46 2d 54 52 55 45 2a 2f 0a 20 20  ION-IF-TRUE*/.  
34f0: 20 20 20 20 2f 2a 20 46 72 65 65 20 6d 65 6d 6f      /* Free memo
3500: 72 79 20 69 6d 6d 65 64 69 61 74 65 6c 79 2c 20  ry immediately, 
3510: 72 61 74 68 65 72 20 74 68 61 6e 20 77 61 69 74  rather than wait
3520: 69 6e 67 20 6f 6e 20 73 71 6c 69 74 65 33 5f 66  ing on sqlite3_f
3530: 69 6e 61 6c 69 7a 65 28 29 20 2a 2f 0a 20 20 20  inalize() */.   
3540: 20 20 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74     sqlite3RowSet
3550: 43 6c 65 61 72 28 70 29 3b 0a 20 20 20 20 7d 0a  Clear(p);.    }.
3560: 20 20 20 20 72 65 74 75 72 6e 20 31 3b 0a 20 20      return 1;.  
3570: 7d 65 6c 73 65 7b 0a 20 20 20 20 72 65 74 75 72  }else{.    retur
3580: 6e 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a  n 0;.  }.}../*.*
3590: 2a 20 43 68 65 63 6b 20 74 6f 20 73 65 65 20 69  * Check to see i
35a0: 66 20 65 6c 65 6d 65 6e 74 20 69 52 6f 77 69 64  f element iRowid
35b0: 20 77 61 73 20 69 6e 73 65 72 74 65 64 20 69 6e   was inserted in
35c0: 74 6f 20 74 68 65 20 72 6f 77 73 65 74 20 61 73  to the rowset as
35d0: 0a 2a 2a 20 70 61 72 74 20 6f 66 20 61 6e 79 20  .** part of any 
35e0: 69 6e 73 65 72 74 20 62 61 74 63 68 20 70 72 69  insert batch pri
35f0: 6f 72 20 74 6f 20 69 42 61 74 63 68 2e 20 20 52  or to iBatch.  R
3600: 65 74 75 72 6e 20 31 20 6f 72 20 30 2e 0a 2a 2a  eturn 1 or 0..**
3610: 0a 2a 2a 20 49 66 20 74 68 69 73 20 69 73 20 74  .** If this is t
3620: 68 65 20 66 69 72 73 74 20 74 65 73 74 20 6f 66  he first test of
3630: 20 61 20 6e 65 77 20 62 61 74 63 68 20 61 6e 64   a new batch and
3640: 20 69 66 20 74 68 65 72 65 20 65 78 69 73 74 20   if there exist 
3650: 65 6e 74 72 69 65 73 0a 2a 2a 20 6f 6e 20 70 52  entries.** on pR
3660: 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 2c 20 74  owSet->pEntry, t
3670: 68 65 6e 20 73 6f 72 74 20 74 68 6f 73 65 20 65  hen sort those e
3680: 6e 74 72 69 65 73 20 69 6e 74 6f 20 74 68 65 20  ntries into the 
3690: 66 6f 72 65 73 74 20 61 74 0a 2a 2a 20 70 52 6f  forest at.** pRo
36a0: 77 53 65 74 2d 3e 70 46 6f 72 65 73 74 20 73 6f  wSet->pForest so
36b0: 20 74 68 61 74 20 74 68 65 79 20 63 61 6e 20 62   that they can b
36c0: 65 20 74 65 73 74 65 64 2e 0a 2a 2f 0a 69 6e 74  e tested..*/.int
36d0: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 54 65   sqlite3RowSetTe
36e0: 73 74 28 52 6f 77 53 65 74 20 2a 70 52 6f 77 53  st(RowSet *pRowS
36f0: 65 74 2c 20 69 6e 74 20 69 42 61 74 63 68 2c 20  et, int iBatch, 
3700: 73 71 6c 69 74 65 33 5f 69 6e 74 36 34 20 69 52  sqlite3_int64 iR
3710: 6f 77 69 64 29 7b 0a 20 20 73 74 72 75 63 74 20  owid){.  struct 
3720: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 2c 20  RowSetEntry *p, 
3730: 2a 70 54 72 65 65 3b 0a 0a 20 20 2f 2a 20 54 68  *pTree;..  /* Th
3740: 69 73 20 72 6f 75 74 69 6e 65 20 69 73 20 6e 65  is routine is ne
3750: 76 65 72 20 63 61 6c 6c 65 64 20 61 66 74 65 72  ver called after
3760: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 4e 65   sqlite3RowSetNe
3770: 78 74 28 29 20 2a 2f 0a 20 20 61 73 73 65 72 74  xt() */.  assert
3780: 28 20 70 52 6f 77 53 65 74 21 3d 30 20 26 26 20  ( pRowSet!=0 && 
3790: 28 70 52 6f 77 53 65 74 2d 3e 72 73 46 6c 61 67  (pRowSet->rsFlag
37a0: 73 20 26 20 52 4f 57 53 45 54 5f 4e 45 58 54 29  s & ROWSET_NEXT)
37b0: 3d 3d 30 20 29 3b 0a 0a 20 20 2f 2a 20 53 6f 72  ==0 );..  /* Sor
37c0: 74 20 65 6e 74 72 69 65 73 20 69 6e 74 6f 20 74  t entries into t
37d0: 68 65 20 66 6f 72 65 73 74 20 6f 6e 20 74 68 65  he forest on the
37e0: 20 66 69 72 73 74 20 74 65 73 74 20 6f 66 20 61   first test of a
37f0: 20 6e 65 77 20 62 61 74 63 68 2e 0a 20 20 2a 2a   new batch..  **
3800: 20 54 6f 20 73 61 76 65 20 75 6e 6e 65 63 65 73   To save unneces
3810: 73 61 72 79 20 77 6f 72 6b 2c 20 6f 6e 6c 79 20  sary work, only 
3820: 64 6f 20 74 68 69 73 20 77 68 65 6e 20 74 68 65  do this when the
3830: 20 62 61 74 63 68 20 6e 75 6d 62 65 72 20 63 68   batch number ch
3840: 61 6e 67 65 73 2e 0a 20 20 2a 2f 0a 20 20 69 66  anges..  */.  if
3850: 28 20 69 42 61 74 63 68 21 3d 70 52 6f 77 53 65  ( iBatch!=pRowSe
3860: 74 2d 3e 69 42 61 74 63 68 20 29 7b 20 20 2f 2a  t->iBatch ){  /*
3870: 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d  OPTIMIZATION-IF-
3880: 46 41 4c 53 45 2a 2f 0a 20 20 20 20 70 20 3d 20  FALSE*/.    p = 
3890: 70 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 3b  pRowSet->pEntry;
38a0: 0a 20 20 20 20 69 66 28 20 70 20 29 7b 0a 20 20  .    if( p ){.  
38b0: 20 20 20 20 73 74 72 75 63 74 20 52 6f 77 53 65      struct RowSe
38c0: 74 45 6e 74 72 79 20 2a 2a 70 70 50 72 65 76 54  tEntry **ppPrevT
38d0: 72 65 65 20 3d 20 26 70 52 6f 77 53 65 74 2d 3e  ree = &pRowSet->
38e0: 70 46 6f 72 65 73 74 3b 0a 20 20 20 20 20 20 69  pForest;.      i
38f0: 66 28 20 28 70 52 6f 77 53 65 74 2d 3e 72 73 46  f( (pRowSet->rsF
3900: 6c 61 67 73 20 26 20 52 4f 57 53 45 54 5f 53 4f  lags & ROWSET_SO
3910: 52 54 45 44 29 3d 3d 30 20 29 7b 20 2f 2a 4f 50  RTED)==0 ){ /*OP
3920: 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46 2d 46 41  TIMIZATION-IF-FA
3930: 4c 53 45 2a 2f 0a 20 20 20 20 20 20 20 20 2f 2a  LSE*/.        /*
3940: 20 4f 6e 6c 79 20 73 6f 72 74 20 74 68 65 20 63   Only sort the c
3950: 75 72 72 65 6e 74 20 73 65 74 20 6f 66 20 65 6e  urrent set of en
3960: 74 69 72 69 65 73 20 69 66 20 74 68 65 79 20 6e  tiries if they n
3970: 65 65 64 20 69 74 20 2a 2f 0a 20 20 20 20 20 20  eed it */.      
3980: 20 20 70 20 3d 20 72 6f 77 53 65 74 45 6e 74 72    p = rowSetEntr
3990: 79 53 6f 72 74 28 70 29 3b 0a 20 20 20 20 20 20  ySort(p);.      
39a0: 7d 0a 20 20 20 20 20 20 66 6f 72 28 70 54 72 65  }.      for(pTre
39b0: 65 20 3d 20 70 52 6f 77 53 65 74 2d 3e 70 46 6f  e = pRowSet->pFo
39c0: 72 65 73 74 3b 20 70 54 72 65 65 3b 20 70 54 72  rest; pTree; pTr
39d0: 65 65 3d 70 54 72 65 65 2d 3e 70 52 69 67 68 74  ee=pTree->pRight
39e0: 29 7b 0a 20 20 20 20 20 20 20 20 70 70 50 72 65  ){.        ppPre
39f0: 76 54 72 65 65 20 3d 20 26 70 54 72 65 65 2d 3e  vTree = &pTree->
3a00: 70 52 69 67 68 74 3b 0a 20 20 20 20 20 20 20 20  pRight;.        
3a10: 69 66 28 20 70 54 72 65 65 2d 3e 70 4c 65 66 74  if( pTree->pLeft
3a20: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 20  ==0 ){.         
3a30: 20 70 54 72 65 65 2d 3e 70 4c 65 66 74 20 3d 20   pTree->pLeft = 
3a40: 72 6f 77 53 65 74 4c 69 73 74 54 6f 54 72 65 65  rowSetListToTree
3a50: 28 70 29 3b 0a 20 20 20 20 20 20 20 20 20 20 62  (p);.          b
3a60: 72 65 61 6b 3b 0a 20 20 20 20 20 20 20 20 7d 65  reak;.        }e
3a70: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 20 20 73  lse{.          s
3a80: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
3a90: 79 20 2a 70 41 75 78 2c 20 2a 70 54 61 69 6c 3b  y *pAux, *pTail;
3aa0: 0a 20 20 20 20 20 20 20 20 20 20 72 6f 77 53 65  .          rowSe
3ab0: 74 54 72 65 65 54 6f 4c 69 73 74 28 70 54 72 65  tTreeToList(pTre
3ac0: 65 2d 3e 70 4c 65 66 74 2c 20 26 70 41 75 78 2c  e->pLeft, &pAux,
3ad0: 20 26 70 54 61 69 6c 29 3b 0a 20 20 20 20 20 20   &pTail);.      
3ae0: 20 20 20 20 70 54 72 65 65 2d 3e 70 4c 65 66 74      pTree->pLeft
3af0: 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 20 20   = 0;.          
3b00: 70 20 3d 20 72 6f 77 53 65 74 45 6e 74 72 79 4d  p = rowSetEntryM
3b10: 65 72 67 65 28 70 41 75 78 2c 20 70 29 3b 0a 20  erge(pAux, p);. 
3b20: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d         }.      }
3b30: 0a 20 20 20 20 20 20 69 66 28 20 70 54 72 65 65  .      if( pTree
3b40: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 2a  ==0 ){.        *
3b50: 70 70 50 72 65 76 54 72 65 65 20 3d 20 70 54 72  ppPrevTree = pTr
3b60: 65 65 20 3d 20 72 6f 77 53 65 74 45 6e 74 72 79  ee = rowSetEntry
3b70: 41 6c 6c 6f 63 28 70 52 6f 77 53 65 74 29 3b 0a  Alloc(pRowSet);.
3b80: 20 20 20 20 20 20 20 20 69 66 28 20 70 54 72 65          if( pTre
3b90: 65 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 70  e ){.          p
3ba0: 54 72 65 65 2d 3e 76 20 3d 20 30 3b 0a 20 20 20  Tree->v = 0;.   
3bb0: 20 20 20 20 20 20 20 70 54 72 65 65 2d 3e 70 52         pTree->pR
3bc0: 69 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 20 20  ight = 0;.      
3bd0: 20 20 20 20 70 54 72 65 65 2d 3e 70 4c 65 66 74      pTree->pLeft
3be0: 20 3d 20 72 6f 77 53 65 74 4c 69 73 74 54 6f 54   = rowSetListToT
3bf0: 72 65 65 28 70 29 3b 0a 20 20 20 20 20 20 20 20  ree(p);.        
3c00: 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  }.      }.      
3c10: 70 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 20  pRowSet->pEntry 
3c20: 3d 20 30 3b 0a 20 20 20 20 20 20 70 52 6f 77 53  = 0;.      pRowS
3c30: 65 74 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20  et->pLast = 0;. 
3c40: 20 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 72 73       pRowSet->rs
3c50: 46 6c 61 67 73 20 7c 3d 20 52 4f 57 53 45 54 5f  Flags |= ROWSET_
3c60: 53 4f 52 54 45 44 3b 0a 20 20 20 20 7d 0a 20 20  SORTED;.    }.  
3c70: 20 20 70 52 6f 77 53 65 74 2d 3e 69 42 61 74 63    pRowSet->iBatc
3c80: 68 20 3d 20 69 42 61 74 63 68 3b 0a 20 20 7d 0a  h = iBatch;.  }.
3c90: 0a 20 20 2f 2a 20 54 65 73 74 20 74 6f 20 73 65  .  /* Test to se
3ca0: 65 20 69 66 20 74 68 65 20 69 52 6f 77 69 64 20  e if the iRowid 
3cb0: 76 61 6c 75 65 20 61 70 70 65 61 72 73 20 61 6e  value appears an
3cc0: 79 77 68 65 72 65 20 69 6e 20 74 68 65 20 66 6f  ywhere in the fo
3cd0: 72 65 73 74 2e 0a 20 20 2a 2a 20 52 65 74 75 72  rest..  ** Retur
3ce0: 6e 20 31 20 69 66 20 69 74 20 64 6f 65 73 20 61  n 1 if it does a
3cf0: 6e 64 20 30 20 69 66 20 6e 6f 74 2e 0a 20 20 2a  nd 0 if not..  *
3d00: 2f 0a 20 20 66 6f 72 28 70 54 72 65 65 20 3d 20  /.  for(pTree = 
3d10: 70 52 6f 77 53 65 74 2d 3e 70 46 6f 72 65 73 74  pRowSet->pForest
3d20: 3b 20 70 54 72 65 65 3b 20 70 54 72 65 65 3d 70  ; pTree; pTree=p
3d30: 54 72 65 65 2d 3e 70 52 69 67 68 74 29 7b 0a 20  Tree->pRight){. 
3d40: 20 20 20 70 20 3d 20 70 54 72 65 65 2d 3e 70 4c     p = pTree->pL
3d50: 65 66 74 3b 0a 20 20 20 20 77 68 69 6c 65 28 20  eft;.    while( 
3d60: 70 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 70  p ){.      if( p
3d70: 2d 3e 76 3c 69 52 6f 77 69 64 20 29 7b 0a 20 20  ->v<iRowid ){.  
3d80: 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 70 52 69        p = p->pRi
3d90: 67 68 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65  ght;.      }else
3da0: 20 69 66 28 20 70 2d 3e 76 3e 69 52 6f 77 69 64   if( p->v>iRowid
3db0: 20 29 7b 0a 20 20 20 20 20 20 20 20 70 20 3d 20   ){.        p = 
3dc0: 70 2d 3e 70 4c 65 66 74 3b 0a 20 20 20 20 20 20  p->pLeft;.      
3dd0: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 72  }else{.        r
3de0: 65 74 75 72 6e 20 31 3b 0a 20 20 20 20 20 20 7d  eturn 1;.      }
3df0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74  .    }.  }.  ret
3e00: 75 72 6e 20 30 3b 0a 7d 0a                       urn 0;.}.