/ Hex Artifact Content
Login

Artifact c64dafba1f9fd876836c8db8682966b9d197eb1f:


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 2a 0a 2a 2a 20 24 49  itives..**.** $I
0a00: 64 3a 20 72 6f 77 73 65 74 2e 63 2c 76 20 31 2e  d: rowset.c,v 1.
0a10: 37 20 32 30 30 39 2f 30 35 2f 32 32 20 30 31 3a  7 2009/05/22 01:
0a20: 30 30 3a 31 33 20 64 72 68 20 45 78 70 20 24 0a  00:13 drh Exp $.
0a30: 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c  */.#include "sql
0a40: 69 74 65 49 6e 74 2e 68 22 0a 0a 0a 2f 2a 0a 2a  iteInt.h".../*.*
0a50: 2a 20 54 61 72 67 65 74 20 73 69 7a 65 20 66 6f  * Target size fo
0a60: 72 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 63 68 75  r allocation chu
0a70: 6e 6b 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  nks..*/.#define 
0a80: 52 4f 57 53 45 54 5f 41 4c 4c 4f 43 41 54 49 4f  ROWSET_ALLOCATIO
0a90: 4e 5f 53 49 5a 45 20 31 30 32 34 0a 0a 2f 2a 0a  N_SIZE 1024../*.
0aa0: 2a 2a 20 54 68 65 20 6e 75 6d 62 65 72 20 6f 66  ** The number of
0ab0: 20 72 6f 77 73 65 74 20 65 6e 74 72 69 65 73 20   rowset entries 
0ac0: 70 65 72 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 63  per allocation c
0ad0: 68 75 6e 6b 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  hunk..*/.#define
0ae0: 20 52 4f 57 53 45 54 5f 45 4e 54 52 59 5f 50 45   ROWSET_ENTRY_PE
0af0: 52 5f 43 48 55 4e 4b 20 20 5c 0a 20 20 20 20 20  R_CHUNK  \.     
0b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0b10: 20 20 28 28 52 4f 57 53 45 54 5f 41 4c 4c 4f 43    ((ROWSET_ALLOC
0b20: 41 54 49 4f 4e 5f 53 49 5a 45 2d 38 29 2f 73 69  ATION_SIZE-8)/si
0b30: 7a 65 6f 66 28 73 74 72 75 63 74 20 52 6f 77 53  zeof(struct RowS
0b40: 65 74 45 6e 74 72 79 29 29 0a 0a 2f 2a 0a 2a 2a  etEntry))../*.**
0b50: 20 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20 61   Each entry in a
0b60: 20 52 6f 77 53 65 74 20 69 73 20 61 6e 20 69 6e   RowSet is an in
0b70: 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66 6f  stance of the fo
0b80: 6c 6c 6f 77 69 6e 67 20 6f 62 6a 65 63 74 2e 0a  llowing object..
0b90: 2a 2f 0a 73 74 72 75 63 74 20 52 6f 77 53 65 74  */.struct RowSet
0ba0: 45 6e 74 72 79 20 7b 20 20 20 20 20 20 20 20 20  Entry {         
0bb0: 20 20 20 0a 20 20 69 36 34 20 76 3b 20 20 20 20     .  i64 v;    
0bc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0bd0: 20 20 20 20 2f 2a 20 52 4f 57 49 44 20 76 61 6c      /* ROWID val
0be0: 75 65 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72  ue for this entr
0bf0: 79 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f  y */.  struct Ro
0c00: 77 53 65 74 45 6e 74 72 79 20 2a 70 52 69 67 68  wSetEntry *pRigh
0c10: 74 3b 20 20 20 2f 2a 20 52 69 67 68 74 20 73 75  t;   /* Right su
0c20: 62 74 72 65 65 20 28 6c 61 72 67 65 72 20 65 6e  btree (larger en
0c30: 74 72 69 65 73 29 20 6f 72 20 6c 69 73 74 20 2a  tries) or list *
0c40: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
0c50: 74 45 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20 20  tEntry *pLeft;  
0c60: 20 20 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65    /* Left subtre
0c70: 65 20 28 73 6d 61 6c 6c 65 72 20 65 6e 74 72 69  e (smaller entri
0c80: 65 73 29 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  es) */.};../*.**
0c90: 20 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a   RowSetEntry obj
0ca0: 65 63 74 73 20 61 72 65 20 61 6c 6c 6f 63 61 74  ects are allocat
0cb0: 65 64 20 69 6e 20 6c 61 72 67 65 20 63 68 75 6e  ed in large chun
0cc0: 6b 73 20 28 69 6e 73 74 61 6e 63 65 73 20 6f 66  ks (instances of
0cd0: 20 74 68 65 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e   the.** followin
0ce0: 67 20 73 74 72 75 63 74 75 72 65 29 20 74 6f 20  g structure) to 
0cf0: 72 65 64 75 63 65 20 6d 65 6d 6f 72 79 20 61 6c  reduce memory al
0d00: 6c 6f 63 61 74 69 6f 6e 20 6f 76 65 72 68 65 61  location overhea
0d10: 64 2e 20 20 54 68 65 0a 2a 2a 20 63 68 75 6e 6b  d.  The.** chunk
0d20: 73 20 61 72 65 20 6b 65 70 74 20 6f 6e 20 61 20  s are kept on a 
0d30: 6c 69 6e 6b 65 64 20 6c 69 73 74 20 73 6f 20 74  linked list so t
0d40: 68 61 74 20 74 68 65 79 20 63 61 6e 20 62 65 20  hat they can be 
0d50: 64 65 61 6c 6c 6f 63 61 74 65 64 0a 2a 2a 20 77  deallocated.** w
0d60: 68 65 6e 20 74 68 65 20 52 6f 77 53 65 74 20 69  hen the RowSet i
0d70: 73 20 64 65 73 74 72 6f 79 65 64 2e 0a 2a 2f 0a  s destroyed..*/.
0d80: 73 74 72 75 63 74 20 52 6f 77 53 65 74 43 68 75  struct RowSetChu
0d90: 6e 6b 20 7b 0a 20 20 73 74 72 75 63 74 20 52 6f  nk {.  struct Ro
0da0: 77 53 65 74 43 68 75 6e 6b 20 2a 70 4e 65 78 74  wSetChunk *pNext
0db0: 43 68 75 6e 6b 3b 20 20 20 20 20 20 20 20 2f 2a  Chunk;        /*
0dc0: 20 4e 65 78 74 20 63 68 75 6e 6b 20 6f 6e 20 6c   Next chunk on l
0dd0: 69 73 74 20 6f 66 20 74 68 65 6d 20 61 6c 6c 20  ist of them all 
0de0: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
0df0: 65 74 45 6e 74 72 79 20 61 45 6e 74 72 79 5b 52  etEntry aEntry[R
0e00: 4f 57 53 45 54 5f 45 4e 54 52 59 5f 50 45 52 5f  OWSET_ENTRY_PER_
0e10: 43 48 55 4e 4b 5d 3b 20 2f 2a 20 41 6c 6c 6f 63  CHUNK]; /* Alloc
0e20: 61 74 65 64 20 65 6e 74 72 69 65 73 20 2a 2f 0a  ated entries */.
0e30: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 52 6f 77 53  };../*.** A RowS
0e40: 65 74 20 69 6e 20 61 6e 20 69 6e 73 74 61 6e 63  et in an instanc
0e50: 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69  e of the followi
0e60: 6e 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a  ng structure..**
0e70: 0a 2a 2a 20 41 20 74 79 70 65 64 65 66 20 6f 66  .** A typedef of
0e80: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20   this structure 
0e90: 69 66 20 66 6f 75 6e 64 20 69 6e 20 73 71 6c 69  if found in sqli
0ea0: 74 65 49 6e 74 2e 68 2e 0a 2a 2f 0a 73 74 72 75  teInt.h..*/.stru
0eb0: 63 74 20 52 6f 77 53 65 74 20 7b 0a 20 20 73 74  ct RowSet {.  st
0ec0: 72 75 63 74 20 52 6f 77 53 65 74 43 68 75 6e 6b  ruct RowSetChunk
0ed0: 20 2a 70 43 68 75 6e 6b 3b 20 20 20 20 2f 2a 20   *pChunk;    /* 
0ee0: 4c 69 73 74 20 6f 66 20 61 6c 6c 20 63 68 75 6e  List of all chun
0ef0: 6b 20 61 6c 6c 6f 63 61 74 69 6f 6e 73 20 2a 2f  k allocations */
0f00: 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 3b 20  .  sqlite3 *db; 
0f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0f20: 20 20 2f 2a 20 54 68 65 20 64 61 74 61 62 61 73    /* The databas
0f30: 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 2a 2f 0a  e connection */.
0f40: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
0f50: 6e 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 20  ntry *pEntry;   
0f60: 20 2f 2a 20 4c 69 73 74 20 6f 66 20 65 6e 74 72   /* List of entr
0f70: 69 65 73 20 75 73 69 6e 67 20 70 52 69 67 68 74  ies using pRight
0f80: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77   */.  struct Row
0f90: 53 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b  SetEntry *pLast;
0fa0: 20 20 20 20 20 2f 2a 20 4c 61 73 74 20 65 6e 74       /* Last ent
0fb0: 72 79 20 6f 6e 20 74 68 65 20 70 45 6e 74 72 79  ry on the pEntry
0fc0: 20 6c 69 73 74 20 2a 2f 0a 20 20 73 74 72 75 63   list */.  struc
0fd0: 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70  t RowSetEntry *p
0fe0: 46 72 65 73 68 3b 20 20 20 20 2f 2a 20 53 6f 75  Fresh;    /* Sou
0ff0: 72 63 65 20 6f 66 20 6e 65 77 20 65 6e 74 72 79  rce of new entry
1000: 20 6f 62 6a 65 63 74 73 20 2a 2f 0a 20 20 73 74   objects */.  st
1010: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1020: 20 2a 70 54 72 65 65 3b 20 20 20 20 20 2f 2a 20   *pTree;     /* 
1030: 42 69 6e 61 72 79 20 74 72 65 65 20 6f 66 20 65  Binary tree of e
1040: 6e 74 72 69 65 73 20 2a 2f 0a 20 20 75 31 36 20  ntries */.  u16 
1050: 6e 46 72 65 73 68 3b 20 20 20 20 20 20 20 20 20  nFresh;         
1060: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
1070: 6d 62 65 72 20 6f 66 20 6f 62 6a 65 63 74 73 20  mber of objects 
1080: 6f 6e 20 70 46 72 65 73 68 20 2a 2f 0a 20 20 75  on pFresh */.  u
1090: 38 20 69 73 53 6f 72 74 65 64 3b 20 20 20 20 20  8 isSorted;     
10a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
10b0: 20 54 72 75 65 20 69 66 20 70 45 6e 74 72 79 20   True if pEntry 
10c0: 69 73 20 73 6f 72 74 65 64 20 2a 2f 0a 20 20 75  is sorted */.  u
10d0: 38 20 69 42 61 74 63 68 3b 20 20 20 20 20 20 20  8 iBatch;       
10e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
10f0: 20 43 75 72 72 65 6e 74 20 69 6e 73 65 72 74 20   Current insert 
1100: 62 61 74 63 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a  batch */.};../*.
1110: 2a 2a 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d  ** Turn bulk mem
1120: 6f 72 79 20 69 6e 74 6f 20 61 20 52 6f 77 53 65  ory into a RowSe
1130: 74 20 6f 62 6a 65 63 74 2e 20 20 4e 20 62 79 74  t object.  N byt
1140: 65 73 20 6f 66 20 6d 65 6d 6f 72 79 0a 2a 2a 20  es of memory.** 
1150: 61 72 65 20 61 76 61 69 6c 61 62 6c 65 20 61 74  are available at
1160: 20 70 53 70 61 63 65 2e 20 20 54 68 65 20 64 62   pSpace.  The db
1170: 20 70 6f 69 6e 74 65 72 20 69 73 20 75 73 65 64   pointer is used
1180: 20 61 73 20 61 20 6d 65 6d 6f 72 79 20 63 6f 6e   as a memory con
1190: 74 65 78 74 0a 2a 2a 20 66 6f 72 20 61 6e 79 20  text.** for any 
11a0: 73 75 62 73 65 71 75 65 6e 74 20 61 6c 6c 6f 63  subsequent alloc
11b0: 61 74 69 6f 6e 73 20 74 68 61 74 20 6e 65 65 64  ations that need
11c0: 20 74 6f 20 6f 63 63 75 72 2e 0a 2a 2a 20 52 65   to occur..** Re
11d0: 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  turn a pointer t
11e0: 6f 20 74 68 65 20 6e 65 77 20 52 6f 77 53 65 74  o the new RowSet
11f0: 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 49   object..**.** I
1200: 74 20 6d 75 73 74 20 62 65 20 74 68 65 20 63 61  t must be the ca
1210: 73 65 20 74 68 61 74 20 4e 20 69 73 20 73 75 66  se that N is suf
1220: 66 69 63 69 65 6e 74 20 74 6f 20 6d 61 6b 65 20  ficient to make 
1230: 61 20 52 6f 77 73 65 74 2e 20 20 49 66 20 6e 6f  a Rowset.  If no
1240: 74 0a 2a 2a 20 61 6e 20 61 73 73 65 72 74 69 6f  t.** an assertio
1250: 6e 20 66 61 75 6c 74 20 6f 63 63 75 72 73 2e 0a  n fault occurs..
1260: 2a 2a 20 0a 2a 2a 20 49 66 20 4e 20 69 73 20 6c  ** .** If N is l
1270: 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 6d  arger than the m
1280: 69 6e 69 6d 75 6d 2c 20 75 73 65 20 74 68 65 20  inimum, use the 
1290: 73 75 72 70 6c 75 73 20 61 73 20 61 6e 20 69 6e  surplus as an in
12a0: 69 74 69 61 6c 0a 2a 2a 20 61 6c 6c 6f 63 61 74  itial.** allocat
12b0: 69 6f 6e 20 6f 66 20 65 6e 74 72 69 65 73 20 61  ion of entries a
12c0: 76 61 69 6c 61 62 6c 65 20 74 6f 20 62 65 20 66  vailable to be f
12d0: 69 6c 6c 65 64 2e 0a 2a 2f 0a 52 6f 77 53 65 74  illed..*/.RowSet
12e0: 20 2a 73 71 6c 69 74 65 33 52 6f 77 53 65 74 49   *sqlite3RowSetI
12f0: 6e 69 74 28 73 71 6c 69 74 65 33 20 2a 64 62 2c  nit(sqlite3 *db,
1300: 20 76 6f 69 64 20 2a 70 53 70 61 63 65 2c 20 75   void *pSpace, u
1310: 6e 73 69 67 6e 65 64 20 69 6e 74 20 4e 29 7b 0a  nsigned int N){.
1320: 20 20 52 6f 77 53 65 74 20 2a 70 3b 0a 20 20 61    RowSet *p;.  a
1330: 73 73 65 72 74 28 20 4e 20 3e 3d 20 52 4f 55 4e  ssert( N >= ROUN
1340: 44 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 20 29  D8(sizeof(*p)) )
1350: 3b 0a 20 20 70 20 3d 20 70 53 70 61 63 65 3b 0a  ;.  p = pSpace;.
1360: 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d 20 30 3b    p->pChunk = 0;
1370: 0a 20 20 70 2d 3e 64 62 20 3d 20 64 62 3b 0a 20  .  p->db = db;. 
1380: 20 70 2d 3e 70 45 6e 74 72 79 20 3d 20 30 3b 0a   p->pEntry = 0;.
1390: 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a    p->pLast = 0;.
13a0: 20 20 70 2d 3e 70 54 72 65 65 20 3d 20 30 3b 0a    p->pTree = 0;.
13b0: 20 20 70 2d 3e 70 46 72 65 73 68 20 3d 20 28 73    p->pFresh = (s
13c0: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
13d0: 79 2a 29 28 52 4f 55 4e 44 38 28 73 69 7a 65 6f  y*)(ROUND8(sizeo
13e0: 66 28 2a 70 29 29 20 2b 20 28 63 68 61 72 2a 29  f(*p)) + (char*)
13f0: 70 29 3b 0a 20 20 70 2d 3e 6e 46 72 65 73 68 20  p);.  p->nFresh 
1400: 3d 20 28 75 31 36 29 28 28 4e 20 2d 20 52 4f 55  = (u16)((N - ROU
1410: 4e 44 38 28 73 69 7a 65 6f 66 28 2a 70 29 29 29  ND8(sizeof(*p)))
1420: 2f 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 52  /sizeof(struct R
1430: 6f 77 53 65 74 45 6e 74 72 79 29 29 3b 0a 20 20  owSetEntry));.  
1440: 70 2d 3e 69 73 53 6f 72 74 65 64 20 3d 20 31 3b  p->isSorted = 1;
1450: 0a 20 20 70 2d 3e 69 42 61 74 63 68 20 3d 20 30  .  p->iBatch = 0
1460: 3b 0a 20 20 72 65 74 75 72 6e 20 70 3b 0a 7d 0a  ;.  return p;.}.
1470: 0a 2f 2a 0a 2a 2a 20 44 65 61 6c 6c 6f 63 61 74  ./*.** Deallocat
1480: 65 20 61 6c 6c 20 63 68 75 6e 6b 73 20 66 72 6f  e all chunks fro
1490: 6d 20 61 20 52 6f 77 53 65 74 2e 20 20 54 68 69  m a RowSet.  Thi
14a0: 73 20 66 72 65 65 73 20 61 6c 6c 20 6d 65 6d 6f  s frees all memo
14b0: 72 79 20 74 68 61 74 0a 2a 2a 20 74 68 65 20 52  ry that.** the R
14c0: 6f 77 53 65 74 20 68 61 73 20 61 6c 6c 6f 63 61  owSet has alloca
14d0: 74 65 64 20 6f 76 65 72 20 69 74 73 20 6c 69 66  ted over its lif
14e0: 65 74 69 6d 65 2e 20 20 54 68 69 73 20 72 6f 75  etime.  This rou
14f0: 74 69 6e 65 20 69 73 0a 2a 2a 20 74 68 65 20 64  tine is.** the d
1500: 65 73 74 72 75 63 74 6f 72 20 66 6f 72 20 74 68  estructor for th
1510: 65 20 52 6f 77 53 65 74 2e 0a 2a 2f 0a 76 6f 69  e RowSet..*/.voi
1520: 64 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 43  d sqlite3RowSetC
1530: 6c 65 61 72 28 52 6f 77 53 65 74 20 2a 70 29 7b  lear(RowSet *p){
1540: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
1550: 43 68 75 6e 6b 20 2a 70 43 68 75 6e 6b 2c 20 2a  Chunk *pChunk, *
1560: 70 4e 65 78 74 43 68 75 6e 6b 3b 0a 20 20 66 6f  pNextChunk;.  fo
1570: 72 28 70 43 68 75 6e 6b 3d 70 2d 3e 70 43 68 75  r(pChunk=p->pChu
1580: 6e 6b 3b 20 70 43 68 75 6e 6b 3b 20 70 43 68 75  nk; pChunk; pChu
1590: 6e 6b 20 3d 20 70 4e 65 78 74 43 68 75 6e 6b 29  nk = pNextChunk)
15a0: 7b 0a 20 20 20 20 70 4e 65 78 74 43 68 75 6e 6b  {.    pNextChunk
15b0: 20 3d 20 70 43 68 75 6e 6b 2d 3e 70 4e 65 78 74   = pChunk->pNext
15c0: 43 68 75 6e 6b 3b 0a 20 20 20 20 73 71 6c 69 74  Chunk;.    sqlit
15d0: 65 33 44 62 46 72 65 65 28 70 2d 3e 64 62 2c 20  e3DbFree(p->db, 
15e0: 70 43 68 75 6e 6b 29 3b 0a 20 20 7d 0a 20 20 70  pChunk);.  }.  p
15f0: 2d 3e 70 43 68 75 6e 6b 20 3d 20 30 3b 0a 20 20  ->pChunk = 0;.  
1600: 70 2d 3e 6e 46 72 65 73 68 20 3d 20 30 3b 0a 20  p->nFresh = 0;. 
1610: 20 70 2d 3e 70 45 6e 74 72 79 20 3d 20 30 3b 0a   p->pEntry = 0;.
1620: 20 20 70 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a    p->pLast = 0;.
1630: 20 20 70 2d 3e 70 54 72 65 65 20 3d 20 30 3b 0a    p->pTree = 0;.
1640: 20 20 70 2d 3e 69 73 53 6f 72 74 65 64 20 3d 20    p->isSorted = 
1650: 31 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 73 65  1;.}../*.** Inse
1660: 72 74 20 61 20 6e 65 77 20 76 61 6c 75 65 20 69  rt a new value i
1670: 6e 74 6f 20 61 20 52 6f 77 53 65 74 2e 0a 2a 2a  nto a RowSet..**
1680: 0a 2a 2a 20 54 68 65 20 6d 61 6c 6c 6f 63 46 61  .** The mallocFa
1690: 69 6c 65 64 20 66 6c 61 67 20 6f 66 20 74 68 65  iled flag of the
16a0: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
16b0: 74 69 6f 6e 20 69 73 20 73 65 74 20 69 66 20 61  tion is set if a
16c0: 0a 2a 2a 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63  .** memory alloc
16d0: 61 74 69 6f 6e 20 66 61 69 6c 73 2e 0a 2a 2f 0a  ation fails..*/.
16e0: 76 6f 69 64 20 73 71 6c 69 74 65 33 52 6f 77 53  void sqlite3RowS
16f0: 65 74 49 6e 73 65 72 74 28 52 6f 77 53 65 74 20  etInsert(RowSet 
1700: 2a 70 2c 20 69 36 34 20 72 6f 77 69 64 29 7b 0a  *p, i64 rowid){.
1710: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
1720: 6e 74 72 79 20 2a 70 45 6e 74 72 79 3b 20 20 2f  ntry *pEntry;  /
1730: 2a 20 54 68 65 20 6e 65 77 20 65 6e 74 72 79 20  * The new entry 
1740: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
1750: 65 74 45 6e 74 72 79 20 2a 70 4c 61 73 74 3b 20  etEntry *pLast; 
1760: 20 20 2f 2a 20 54 68 65 20 6c 61 73 74 20 70 72    /* The last pr
1770: 69 6f 72 20 65 6e 74 72 79 20 2a 2f 0a 20 20 61  ior entry */.  a
1780: 73 73 65 72 74 28 20 70 21 3d 30 20 29 3b 0a 20  ssert( p!=0 );. 
1790: 20 69 66 28 20 70 2d 3e 6e 46 72 65 73 68 3d 3d   if( p->nFresh==
17a0: 30 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20  0 ){.    struct 
17b0: 52 6f 77 53 65 74 43 68 75 6e 6b 20 2a 70 4e 65  RowSetChunk *pNe
17c0: 77 3b 0a 20 20 20 20 70 4e 65 77 20 3d 20 73 71  w;.    pNew = sq
17d0: 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 52 61 77  lite3DbMallocRaw
17e0: 28 70 2d 3e 64 62 2c 20 73 69 7a 65 6f 66 28 2a  (p->db, sizeof(*
17f0: 70 4e 65 77 29 29 3b 0a 20 20 20 20 69 66 28 20  pNew));.    if( 
1800: 70 4e 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20 20  pNew==0 ){.     
1810: 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 7d 0a 20   return;.    }. 
1820: 20 20 20 70 4e 65 77 2d 3e 70 4e 65 78 74 43 68     pNew->pNextCh
1830: 75 6e 6b 20 3d 20 70 2d 3e 70 43 68 75 6e 6b 3b  unk = p->pChunk;
1840: 0a 20 20 20 20 70 2d 3e 70 43 68 75 6e 6b 20 3d  .    p->pChunk =
1850: 20 70 4e 65 77 3b 0a 20 20 20 20 70 2d 3e 70 46   pNew;.    p->pF
1860: 72 65 73 68 20 3d 20 70 4e 65 77 2d 3e 61 45 6e  resh = pNew->aEn
1870: 74 72 79 3b 0a 20 20 20 20 70 2d 3e 6e 46 72 65  try;.    p->nFre
1880: 73 68 20 3d 20 52 4f 57 53 45 54 5f 45 4e 54 52  sh = ROWSET_ENTR
1890: 59 5f 50 45 52 5f 43 48 55 4e 4b 3b 0a 20 20 7d  Y_PER_CHUNK;.  }
18a0: 0a 20 20 70 45 6e 74 72 79 20 3d 20 70 2d 3e 70  .  pEntry = p->p
18b0: 46 72 65 73 68 2b 2b 3b 0a 20 20 70 2d 3e 6e 46  Fresh++;.  p->nF
18c0: 72 65 73 68 2d 2d 3b 0a 20 20 70 45 6e 74 72 79  resh--;.  pEntry
18d0: 2d 3e 76 20 3d 20 72 6f 77 69 64 3b 0a 20 20 70  ->v = rowid;.  p
18e0: 45 6e 74 72 79 2d 3e 70 52 69 67 68 74 20 3d 20  Entry->pRight = 
18f0: 30 3b 0a 20 20 70 4c 61 73 74 20 3d 20 70 2d 3e  0;.  pLast = p->
1900: 70 4c 61 73 74 3b 0a 20 20 69 66 28 20 70 4c 61  pLast;.  if( pLa
1910: 73 74 20 29 7b 0a 20 20 20 20 69 66 28 20 70 2d  st ){.    if( p-
1920: 3e 69 73 53 6f 72 74 65 64 20 26 26 20 72 6f 77  >isSorted && row
1930: 69 64 3c 3d 70 4c 61 73 74 2d 3e 76 20 29 7b 0a  id<=pLast->v ){.
1940: 20 20 20 20 20 20 70 2d 3e 69 73 53 6f 72 74 65        p->isSorte
1950: 64 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 20  d = 0;.    }.   
1960: 20 70 4c 61 73 74 2d 3e 70 52 69 67 68 74 20 3d   pLast->pRight =
1970: 20 70 45 6e 74 72 79 3b 0a 20 20 7d 65 6c 73 65   pEntry;.  }else
1980: 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 2d  {.    assert( p-
1990: 3e 70 45 6e 74 72 79 3d 3d 30 20 29 3b 20 2f 2a  >pEntry==0 ); /*
19a0: 20 46 69 72 65 73 20 69 66 20 49 4e 53 45 52 54   Fires if INSERT
19b0: 20 61 66 74 65 72 20 53 4d 41 4c 4c 45 53 54 20   after SMALLEST 
19c0: 2a 2f 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79  */.    p->pEntry
19d0: 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20 7d 0a 20   = pEntry;.  }. 
19e0: 20 70 2d 3e 70 4c 61 73 74 20 3d 20 70 45 6e 74   p->pLast = pEnt
19f0: 72 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 4d 65 72  ry;.}../*.** Mer
1a00: 67 65 20 74 77 6f 20 6c 69 73 74 73 20 6f 66 20  ge two lists of 
1a10: 52 6f 77 53 65 74 45 6e 74 72 79 20 6f 62 6a 65  RowSetEntry obje
1a20: 63 74 73 2e 20 20 52 65 6d 6f 76 65 20 64 75 70  cts.  Remove dup
1a30: 6c 69 63 61 74 65 73 2e 0a 2a 2a 0a 2a 2a 20 54  licates..**.** T
1a40: 68 65 20 69 6e 70 75 74 20 6c 69 73 74 73 20 61  he input lists a
1a50: 72 65 20 63 6f 6e 6e 65 63 74 65 64 20 76 69 61  re connected via
1a60: 20 70 52 69 67 68 74 20 70 6f 69 6e 74 65 72 73   pRight pointers
1a70: 20 61 6e 64 20 61 72 65 20 0a 2a 2a 20 61 73 73   and are .** ass
1a80: 75 6d 65 64 20 74 6f 20 65 61 63 68 20 61 6c 72  umed to each alr
1a90: 65 61 64 79 20 62 65 20 69 6e 20 73 6f 72 74 65  eady be in sorte
1aa0: 64 20 6f 72 64 65 72 2e 0a 2a 2f 0a 73 74 61 74  d order..*/.stat
1ab0: 69 63 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  ic struct RowSet
1ac0: 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 4d 65 72  Entry *rowSetMer
1ad0: 67 65 28 0a 20 20 73 74 72 75 63 74 20 52 6f 77  ge(.  struct Row
1ae0: 53 65 74 45 6e 74 72 79 20 2a 70 41 2c 20 20 20  SetEntry *pA,   
1af0: 20 2f 2a 20 46 69 72 73 74 20 73 6f 72 74 65 64   /* First sorted
1b00: 20 6c 69 73 74 20 74 6f 20 62 65 20 6d 65 72 67   list to be merg
1b10: 65 64 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 52  ed */.  struct R
1b20: 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 42 20 20  owSetEntry *pB  
1b30: 20 20 20 2f 2a 20 53 65 63 6f 6e 64 20 73 6f 72     /* Second sor
1b40: 74 65 64 20 6c 69 73 74 20 74 6f 20 62 65 20 6d  ted list to be m
1b50: 65 72 67 65 64 20 2a 2f 0a 29 7b 0a 20 20 73 74  erged */.){.  st
1b60: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1b70: 20 68 65 61 64 3b 0a 20 20 73 74 72 75 63 74 20   head;.  struct 
1b80: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 54 61  RowSetEntry *pTa
1b90: 69 6c 3b 0a 0a 20 20 70 54 61 69 6c 20 3d 20 26  il;..  pTail = &
1ba0: 68 65 61 64 3b 0a 20 20 77 68 69 6c 65 28 20 70  head;.  while( p
1bb0: 41 20 26 26 20 70 42 20 29 7b 0a 20 20 20 20 61  A && pB ){.    a
1bc0: 73 73 65 72 74 28 20 70 41 2d 3e 70 52 69 67 68  ssert( pA->pRigh
1bd0: 74 3d 3d 30 20 7c 7c 20 70 41 2d 3e 76 3c 3d 70  t==0 || pA->v<=p
1be0: 41 2d 3e 70 52 69 67 68 74 2d 3e 76 20 29 3b 0a  A->pRight->v );.
1bf0: 20 20 20 20 61 73 73 65 72 74 28 20 70 42 2d 3e      assert( pB->
1c00: 70 52 69 67 68 74 3d 3d 30 20 7c 7c 20 70 42 2d  pRight==0 || pB-
1c10: 3e 76 3c 3d 70 42 2d 3e 70 52 69 67 68 74 2d 3e  >v<=pB->pRight->
1c20: 76 20 29 3b 0a 20 20 20 20 69 66 28 20 70 41 2d  v );.    if( pA-
1c30: 3e 76 3c 70 42 2d 3e 76 20 29 7b 0a 20 20 20 20  >v<pB->v ){.    
1c40: 20 20 70 54 61 69 6c 2d 3e 70 52 69 67 68 74 20    pTail->pRight 
1c50: 3d 20 70 41 3b 0a 20 20 20 20 20 20 70 41 20 3d  = pA;.      pA =
1c60: 20 70 41 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20   pA->pRight;.   
1c70: 20 20 20 70 54 61 69 6c 20 3d 20 70 54 61 69 6c     pTail = pTail
1c80: 2d 3e 70 52 69 67 68 74 3b 0a 20 20 20 20 7d 65  ->pRight;.    }e
1c90: 6c 73 65 20 69 66 28 20 70 42 2d 3e 76 3c 70 41  lse if( pB->v<pA
1ca0: 2d 3e 76 20 29 7b 0a 20 20 20 20 20 20 70 54 61  ->v ){.      pTa
1cb0: 69 6c 2d 3e 70 52 69 67 68 74 20 3d 20 70 42 3b  il->pRight = pB;
1cc0: 0a 20 20 20 20 20 20 70 42 20 3d 20 70 42 2d 3e  .      pB = pB->
1cd0: 70 52 69 67 68 74 3b 0a 20 20 20 20 20 20 70 54  pRight;.      pT
1ce0: 61 69 6c 20 3d 20 70 54 61 69 6c 2d 3e 70 52 69  ail = pTail->pRi
1cf0: 67 68 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a  ght;.    }else{.
1d00: 20 20 20 20 20 20 70 41 20 3d 20 70 41 2d 3e 70        pA = pA->p
1d10: 52 69 67 68 74 3b 0a 20 20 20 20 7d 0a 20 20 7d  Right;.    }.  }
1d20: 0a 20 20 69 66 28 20 70 41 20 29 7b 0a 20 20 20  .  if( pA ){.   
1d30: 20 61 73 73 65 72 74 28 20 70 41 2d 3e 70 52 69   assert( pA->pRi
1d40: 67 68 74 3d 3d 30 20 7c 7c 20 70 41 2d 3e 76 3c  ght==0 || pA->v<
1d50: 3d 70 41 2d 3e 70 52 69 67 68 74 2d 3e 76 20 29  =pA->pRight->v )
1d60: 3b 0a 20 20 20 20 70 54 61 69 6c 2d 3e 70 52 69  ;.    pTail->pRi
1d70: 67 68 74 20 3d 20 70 41 3b 0a 20 20 7d 65 6c 73  ght = pA;.  }els
1d80: 65 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70  e{.    assert( p
1d90: 42 3d 3d 30 20 7c 7c 20 70 42 2d 3e 70 52 69 67  B==0 || pB->pRig
1da0: 68 74 3d 3d 30 20 7c 7c 20 70 42 2d 3e 76 3c 3d  ht==0 || pB->v<=
1db0: 70 42 2d 3e 70 52 69 67 68 74 2d 3e 76 20 29 3b  pB->pRight->v );
1dc0: 0a 20 20 20 20 70 54 61 69 6c 2d 3e 70 52 69 67  .    pTail->pRig
1dd0: 68 74 20 3d 20 70 42 3b 0a 20 20 7d 0a 20 20 72  ht = pB;.  }.  r
1de0: 65 74 75 72 6e 20 68 65 61 64 2e 70 52 69 67 68  eturn head.pRigh
1df0: 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53 6f 72 74  t;.}../*.** Sort
1e00: 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 6e   all elements on
1e10: 20 74 68 65 20 70 45 6e 74 72 79 20 6c 69 73 74   the pEntry list
1e20: 20 6f 66 20 74 68 65 20 52 6f 77 53 65 74 20 69   of the RowSet i
1e30: 6e 74 6f 20 61 73 63 65 6e 64 69 6e 67 20 6f 72  nto ascending or
1e40: 64 65 72 2e 0a 2a 2f 20 0a 73 74 61 74 69 63 20  der..*/ .static 
1e50: 76 6f 69 64 20 72 6f 77 53 65 74 53 6f 72 74 28  void rowSetSort(
1e60: 52 6f 77 53 65 74 20 2a 70 29 7b 0a 20 20 75 6e  RowSet *p){.  un
1e70: 73 69 67 6e 65 64 20 69 6e 74 20 69 3b 0a 20 20  signed int i;.  
1e80: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
1e90: 72 79 20 2a 70 45 6e 74 72 79 3b 0a 20 20 73 74  ry *pEntry;.  st
1ea0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
1eb0: 20 2a 61 42 75 63 6b 65 74 5b 34 30 5d 3b 0a 0a   *aBucket[40];..
1ec0: 20 20 61 73 73 65 72 74 28 20 70 2d 3e 69 73 53    assert( p->isS
1ed0: 6f 72 74 65 64 3d 3d 30 20 29 3b 0a 20 20 6d 65  orted==0 );.  me
1ee0: 6d 73 65 74 28 61 42 75 63 6b 65 74 2c 20 30 2c  mset(aBucket, 0,
1ef0: 20 73 69 7a 65 6f 66 28 61 42 75 63 6b 65 74 29   sizeof(aBucket)
1f00: 29 3b 0a 20 20 77 68 69 6c 65 28 20 70 2d 3e 70  );.  while( p->p
1f10: 45 6e 74 72 79 20 29 7b 0a 20 20 20 20 70 45 6e  Entry ){.    pEn
1f20: 74 72 79 20 3d 20 70 2d 3e 70 45 6e 74 72 79 3b  try = p->pEntry;
1f30: 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79 20 3d  .    p->pEntry =
1f40: 20 70 45 6e 74 72 79 2d 3e 70 52 69 67 68 74 3b   pEntry->pRight;
1f50: 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 70 52 69  .    pEntry->pRi
1f60: 67 68 74 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72  ght = 0;.    for
1f70: 28 69 3d 30 3b 20 61 42 75 63 6b 65 74 5b 69 5d  (i=0; aBucket[i]
1f80: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 70 45  ; i++){.      pE
1f90: 6e 74 72 79 20 3d 20 72 6f 77 53 65 74 4d 65 72  ntry = rowSetMer
1fa0: 67 65 28 61 42 75 63 6b 65 74 5b 69 5d 2c 20 70  ge(aBucket[i], p
1fb0: 45 6e 74 72 79 29 3b 0a 20 20 20 20 20 20 61 42  Entry);.      aB
1fc0: 75 63 6b 65 74 5b 69 5d 20 3d 20 30 3b 0a 20 20  ucket[i] = 0;.  
1fd0: 20 20 7d 0a 20 20 20 20 61 42 75 63 6b 65 74 5b    }.    aBucket[
1fe0: 69 5d 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20 7d  i] = pEntry;.  }
1ff0: 0a 20 20 70 45 6e 74 72 79 20 3d 20 30 3b 0a 20  .  pEntry = 0;. 
2000: 20 66 6f 72 28 69 3d 30 3b 20 69 3c 73 69 7a 65   for(i=0; i<size
2010: 6f 66 28 61 42 75 63 6b 65 74 29 2f 73 69 7a 65  of(aBucket)/size
2020: 6f 66 28 61 42 75 63 6b 65 74 5b 30 5d 29 3b 20  of(aBucket[0]); 
2030: 69 2b 2b 29 7b 0a 20 20 20 20 70 45 6e 74 72 79  i++){.    pEntry
2040: 20 3d 20 72 6f 77 53 65 74 4d 65 72 67 65 28 70   = rowSetMerge(p
2050: 45 6e 74 72 79 2c 20 61 42 75 63 6b 65 74 5b 69  Entry, aBucket[i
2060: 5d 29 3b 0a 20 20 7d 0a 20 20 70 2d 3e 70 45 6e  ]);.  }.  p->pEn
2070: 74 72 79 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20  try = pEntry;.  
2080: 70 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20 20  p->pLast = 0;.  
2090: 70 2d 3e 69 73 53 6f 72 74 65 64 20 3d 20 31 3b  p->isSorted = 1;
20a0: 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 69  .}.../*.** The i
20b0: 6e 70 75 74 2c 20 70 49 6e 2c 20 69 73 20 61 20  nput, pIn, is a 
20c0: 62 69 6e 61 72 79 20 74 72 65 65 20 28 6f 72 20  binary tree (or 
20d0: 73 75 62 74 72 65 65 29 20 6f 66 20 52 6f 77 53  subtree) of RowS
20e0: 65 74 45 6e 74 72 79 20 6f 62 6a 65 63 74 73 2e  etEntry objects.
20f0: 0a 2a 2a 20 43 6f 6e 76 65 72 74 20 74 68 69 73  .** Convert this
2100: 20 74 72 65 65 20 69 6e 74 6f 20 61 20 6c 69 6e   tree into a lin
2110: 6b 65 64 20 6c 69 73 74 20 63 6f 6e 6e 65 63 74  ked list connect
2120: 65 64 20 62 79 20 74 68 65 20 70 52 69 67 68 74  ed by the pRight
2130: 20 70 6f 69 6e 74 65 72 73 0a 2a 2a 20 61 6e 64   pointers.** and
2140: 20 72 65 74 75 72 6e 20 70 6f 69 6e 74 65 72 73   return pointers
2150: 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 61 6e   to the first an
2160: 64 20 6c 61 73 74 20 65 6c 65 6d 65 6e 74 73 20  d last elements 
2170: 6f 66 20 74 68 65 20 6e 65 77 20 6c 69 73 74 2e  of the new list.
2180: 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .*/.static void 
2190: 72 6f 77 53 65 74 54 72 65 65 54 6f 4c 69 73 74  rowSetTreeToList
21a0: 28 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  (.  struct RowSe
21b0: 74 45 6e 74 72 79 20 2a 70 49 6e 2c 20 20 20 20  tEntry *pIn,    
21c0: 20 20 20 20 20 2f 2a 20 52 6f 6f 74 20 6f 66 20       /* Root of 
21d0: 74 68 65 20 69 6e 70 75 74 20 74 72 65 65 20 2a  the input tree *
21e0: 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65  /.  struct RowSe
21f0: 74 45 6e 74 72 79 20 2a 2a 70 70 46 69 72 73 74  tEntry **ppFirst
2200: 2c 20 20 20 20 2f 2a 20 57 72 69 74 65 20 68 65  ,    /* Write he
2210: 61 64 20 6f 66 20 74 68 65 20 6f 75 74 70 75 74  ad of the output
2220: 20 6c 69 73 74 20 68 65 72 65 20 2a 2f 0a 20 20   list here */.  
2230: 73 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74  struct RowSetEnt
2240: 72 79 20 2a 2a 70 70 4c 61 73 74 20 20 20 20 20  ry **ppLast     
2250: 20 2f 2a 20 57 72 69 74 65 20 74 61 69 6c 20 6f   /* Write tail o
2260: 66 20 74 68 65 20 6f 75 74 70 75 74 20 6c 69 73  f the output lis
2270: 74 20 68 65 72 65 20 2a 2f 0a 29 7b 0a 20 20 61  t here */.){.  a
2280: 73 73 65 72 74 28 20 70 49 6e 21 3d 30 20 29 3b  ssert( pIn!=0 );
2290: 0a 20 20 69 66 28 20 70 49 6e 2d 3e 70 4c 65 66  .  if( pIn->pLef
22a0: 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20  t ){.    struct 
22b0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 3b 0a  RowSetEntry *p;.
22c0: 20 20 20 20 72 6f 77 53 65 74 54 72 65 65 54 6f      rowSetTreeTo
22d0: 4c 69 73 74 28 70 49 6e 2d 3e 70 4c 65 66 74 2c  List(pIn->pLeft,
22e0: 20 70 70 46 69 72 73 74 2c 20 26 70 29 3b 0a 20   ppFirst, &p);. 
22f0: 20 20 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 70     p->pRight = p
2300: 49 6e 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  In;.  }else{.   
2310: 20 2a 70 70 46 69 72 73 74 20 3d 20 70 49 6e 3b   *ppFirst = pIn;
2320: 0a 20 20 7d 0a 20 20 69 66 28 20 70 49 6e 2d 3e  .  }.  if( pIn->
2330: 70 52 69 67 68 74 20 29 7b 0a 20 20 20 20 72 6f  pRight ){.    ro
2340: 77 53 65 74 54 72 65 65 54 6f 4c 69 73 74 28 70  wSetTreeToList(p
2350: 49 6e 2d 3e 70 52 69 67 68 74 2c 20 26 70 49 6e  In->pRight, &pIn
2360: 2d 3e 70 52 69 67 68 74 2c 20 70 70 4c 61 73 74  ->pRight, ppLast
2370: 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  );.  }else{.    
2380: 2a 70 70 4c 61 73 74 20 3d 20 70 49 6e 3b 0a 20  *ppLast = pIn;. 
2390: 20 7d 0a 20 20 61 73 73 65 72 74 28 20 28 2a 70   }.  assert( (*p
23a0: 70 4c 61 73 74 29 2d 3e 70 52 69 67 68 74 3d 3d  pLast)->pRight==
23b0: 30 20 29 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 43  0 );.}.../*.** C
23c0: 6f 6e 76 65 72 74 20 61 20 73 6f 72 74 65 64 20  onvert a sorted 
23d0: 6c 69 73 74 20 6f 66 20 65 6c 65 6d 65 6e 74 73  list of elements
23e0: 20 28 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 70   (connected by p
23f0: 52 69 67 68 74 29 20 69 6e 74 6f 20 61 20 62 69  Right) into a bi
2400: 6e 61 72 79 0a 2a 2a 20 74 72 65 65 20 77 69 74  nary.** tree wit
2410: 68 20 64 65 70 74 68 20 6f 66 20 69 44 65 70 74  h depth of iDept
2420: 68 2e 20 20 41 20 64 65 70 74 68 20 6f 66 20 31  h.  A depth of 1
2430: 20 6d 65 61 6e 73 20 74 68 65 20 74 72 65 65 20   means the tree 
2440: 63 6f 6e 74 61 69 6e 73 20 61 20 73 69 6e 67 6c  contains a singl
2450: 65 0a 2a 2a 20 6e 6f 64 65 20 74 61 6b 65 6e 20  e.** node taken 
2460: 66 72 6f 6d 20 74 68 65 20 68 65 61 64 20 6f 66  from the head of
2470: 20 2a 70 70 4c 69 73 74 2e 20 20 41 20 64 65 70   *ppList.  A dep
2480: 74 68 20 6f 66 20 32 20 6d 65 61 6e 73 20 61 20  th of 2 means a 
2490: 74 72 65 65 20 77 69 74 68 0a 2a 2a 20 74 68 72  tree with.** thr
24a0: 65 65 20 6e 6f 64 65 73 2e 20 20 41 6e 64 20 73  ee nodes.  And s
24b0: 6f 20 66 6f 72 74 68 2e 0a 2a 2a 0a 2a 2a 20 55  o forth..**.** U
24c0: 73 65 20 61 73 20 6d 61 6e 79 20 65 6e 74 72 69  se as many entri
24d0: 65 73 20 66 72 6f 6d 20 74 68 65 20 69 6e 70 75  es from the inpu
24e0: 74 20 6c 69 73 74 20 61 73 20 72 65 71 75 69 72  t list as requir
24f0: 65 64 20 61 6e 64 20 75 70 64 61 74 65 20 74 68  ed and update th
2500: 65 0a 2a 2a 20 2a 70 70 4c 69 73 74 20 74 6f 20  e.** *ppList to 
2510: 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 75 6e 75  point to the unu
2520: 73 65 64 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20  sed elements of 
2530: 74 68 65 20 6c 69 73 74 2e 20 20 49 66 20 74 68  the list.  If th
2540: 65 20 69 6e 70 75 74 0a 2a 2a 20 6c 69 73 74 20  e input.** list 
2550: 63 6f 6e 74 61 69 6e 73 20 74 6f 6f 20 66 65 77  contains too few
2560: 20 65 6c 65 6d 65 6e 74 73 2c 20 74 68 65 6e 20   elements, then 
2570: 63 6f 6e 73 74 72 75 63 74 20 61 6e 20 69 6e 63  construct an inc
2580: 6f 6d 70 6c 65 74 65 20 74 72 65 65 0a 2a 2a 20  omplete tree.** 
2590: 61 6e 64 20 6c 65 61 76 65 20 2a 70 70 4c 69 73  and leave *ppLis
25a0: 74 20 73 65 74 20 74 6f 20 4e 55 4c 4c 2e 0a 2a  t set to NULL..*
25b0: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f  *.** Return a po
25c0: 69 6e 74 65 72 20 74 6f 20 74 68 65 20 72 6f 6f  inter to the roo
25d0: 74 20 6f 66 20 74 68 65 20 63 6f 6e 73 74 72 75  t of the constru
25e0: 63 74 65 64 20 62 69 6e 61 72 79 20 74 72 65 65  cted binary tree
25f0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 73 74 72 75  ..*/.static stru
2600: 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79 20 2a  ct RowSetEntry *
2610: 72 6f 77 53 65 74 4e 44 65 65 70 54 72 65 65 28  rowSetNDeepTree(
2620: 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74  .  struct RowSet
2630: 45 6e 74 72 79 20 2a 2a 70 70 4c 69 73 74 2c 0a  Entry **ppList,.
2640: 20 20 69 6e 74 20 69 44 65 70 74 68 0a 29 7b 0a    int iDepth.){.
2650: 20 20 73 74 72 75 63 74 20 52 6f 77 53 65 74 45    struct RowSetE
2660: 6e 74 72 79 20 2a 70 3b 20 20 20 20 20 20 20 20  ntry *p;        
2670: 20 2f 2a 20 52 6f 6f 74 20 6f 66 20 74 68 65 20   /* Root of the 
2680: 6e 65 77 20 74 72 65 65 20 2a 2f 0a 20 20 73 74  new tree */.  st
2690: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
26a0: 20 2a 70 4c 65 66 74 3b 20 20 20 20 20 2f 2a 20   *pLeft;     /* 
26b0: 4c 65 66 74 20 73 75 62 74 72 65 65 20 2a 2f 0a  Left subtree */.
26c0: 20 20 69 66 28 20 2a 70 70 4c 69 73 74 3d 3d 30    if( *ppList==0
26d0: 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 30   ){.    return 0
26e0: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 69 44 65 70  ;.  }.  if( iDep
26f0: 74 68 3d 3d 31 20 29 7b 0a 20 20 20 20 70 20 3d  th==1 ){.    p =
2700: 20 2a 70 70 4c 69 73 74 3b 0a 20 20 20 20 2a 70   *ppList;.    *p
2710: 70 4c 69 73 74 20 3d 20 70 2d 3e 70 52 69 67 68  pList = p->pRigh
2720: 74 3b 0a 20 20 20 20 70 2d 3e 70 4c 65 66 74 20  t;.    p->pLeft 
2730: 3d 20 70 2d 3e 70 52 69 67 68 74 20 3d 20 30 3b  = p->pRight = 0;
2740: 0a 20 20 20 20 72 65 74 75 72 6e 20 70 3b 0a 20  .    return p;. 
2750: 20 7d 0a 20 20 70 4c 65 66 74 20 3d 20 72 6f 77   }.  pLeft = row
2760: 53 65 74 4e 44 65 65 70 54 72 65 65 28 70 70 4c  SetNDeepTree(ppL
2770: 69 73 74 2c 20 69 44 65 70 74 68 2d 31 29 3b 0a  ist, iDepth-1);.
2780: 20 20 70 20 3d 20 2a 70 70 4c 69 73 74 3b 0a 20    p = *ppList;. 
2790: 20 69 66 28 20 70 3d 3d 30 20 29 7b 0a 20 20 20   if( p==0 ){.   
27a0: 20 72 65 74 75 72 6e 20 70 4c 65 66 74 3b 0a 20   return pLeft;. 
27b0: 20 7d 0a 20 20 70 2d 3e 70 4c 65 66 74 20 3d 20   }.  p->pLeft = 
27c0: 70 4c 65 66 74 3b 0a 20 20 2a 70 70 4c 69 73 74  pLeft;.  *ppList
27d0: 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20   = p->pRight;.  
27e0: 70 2d 3e 70 52 69 67 68 74 20 3d 20 72 6f 77 53  p->pRight = rowS
27f0: 65 74 4e 44 65 65 70 54 72 65 65 28 70 70 4c 69  etNDeepTree(ppLi
2800: 73 74 2c 20 69 44 65 70 74 68 2d 31 29 3b 0a 20  st, iDepth-1);. 
2810: 20 72 65 74 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a   return p;.}../*
2820: 0a 2a 2a 20 43 6f 6e 76 65 72 74 20 61 20 73 6f  .** Convert a so
2830: 72 74 65 64 20 6c 69 73 74 20 6f 66 20 65 6c 65  rted list of ele
2840: 6d 65 6e 74 73 20 69 6e 74 6f 20 61 20 62 69 6e  ments into a bin
2850: 61 72 79 20 74 72 65 65 2e 20 4d 61 6b 65 20 74  ary tree. Make t
2860: 68 65 20 74 72 65 65 0a 2a 2a 20 61 73 20 64 65  he tree.** as de
2870: 65 70 20 61 73 20 69 74 20 6e 65 65 64 73 20 74  ep as it needs t
2880: 6f 20 62 65 20 69 6e 20 6f 72 64 65 72 20 74 6f  o be in order to
2890: 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 65 6e 74   contain the ent
28a0: 69 72 65 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  ire list..*/.sta
28b0: 74 69 63 20 73 74 72 75 63 74 20 52 6f 77 53 65  tic struct RowSe
28c0: 74 45 6e 74 72 79 20 2a 72 6f 77 53 65 74 4c 69  tEntry *rowSetLi
28d0: 73 74 54 6f 54 72 65 65 28 73 74 72 75 63 74 20  stToTree(struct 
28e0: 52 6f 77 53 65 74 45 6e 74 72 79 20 2a 70 4c 69  RowSetEntry *pLi
28f0: 73 74 29 7b 0a 20 20 69 6e 74 20 69 44 65 70 74  st){.  int iDept
2900: 68 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  h;           /* 
2910: 44 65 70 74 68 20 6f 66 20 74 68 65 20 74 72 65  Depth of the tre
2920: 65 20 73 6f 20 66 61 72 20 2a 2f 0a 20 20 73 74  e so far */.  st
2930: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2940: 20 2a 70 3b 20 20 20 20 20 20 20 2f 2a 20 43 75   *p;       /* Cu
2950: 72 72 65 6e 74 20 74 72 65 65 20 72 6f 6f 74 20  rrent tree root 
2960: 2a 2f 0a 20 20 73 74 72 75 63 74 20 52 6f 77 53  */.  struct RowS
2970: 65 74 45 6e 74 72 79 20 2a 70 4c 65 66 74 3b 20  etEntry *pLeft; 
2980: 20 20 2f 2a 20 4c 65 66 74 20 73 75 62 74 72 65    /* Left subtre
2990: 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  e */..  assert( 
29a0: 70 4c 69 73 74 21 3d 30 20 29 3b 0a 20 20 70 20  pList!=0 );.  p 
29b0: 3d 20 70 4c 69 73 74 3b 0a 20 20 70 4c 69 73 74  = pList;.  pList
29c0: 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b 0a 20 20   = p->pRight;.  
29d0: 70 2d 3e 70 4c 65 66 74 20 3d 20 70 2d 3e 70 52  p->pLeft = p->pR
29e0: 69 67 68 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28  ight = 0;.  for(
29f0: 69 44 65 70 74 68 3d 31 3b 20 70 4c 69 73 74 3b  iDepth=1; pList;
2a00: 20 69 44 65 70 74 68 2b 2b 29 7b 0a 20 20 20 20   iDepth++){.    
2a10: 70 4c 65 66 74 20 3d 20 70 3b 0a 20 20 20 20 70  pLeft = p;.    p
2a20: 20 3d 20 70 4c 69 73 74 3b 0a 20 20 20 20 70 4c   = pList;.    pL
2a30: 69 73 74 20 3d 20 70 2d 3e 70 52 69 67 68 74 3b  ist = p->pRight;
2a40: 0a 20 20 20 20 70 2d 3e 70 4c 65 66 74 20 3d 20  .    p->pLeft = 
2a50: 70 4c 65 66 74 3b 0a 20 20 20 20 70 2d 3e 70 52  pLeft;.    p->pR
2a60: 69 67 68 74 20 3d 20 72 6f 77 53 65 74 4e 44 65  ight = rowSetNDe
2a70: 65 70 54 72 65 65 28 26 70 4c 69 73 74 2c 20 69  epTree(&pList, i
2a80: 44 65 70 74 68 29 3b 0a 20 20 7d 0a 20 20 72 65  Depth);.  }.  re
2a90: 74 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  turn p;.}../*.**
2aa0: 20 43 6f 6e 76 65 72 74 20 74 68 65 20 6c 69 73   Convert the lis
2ab0: 74 20 69 6e 20 70 2d 3e 70 45 6e 74 72 79 20 69  t in p->pEntry i
2ac0: 6e 74 6f 20 61 20 73 6f 72 74 65 64 20 6c 69 73  nto a sorted lis
2ad0: 74 20 69 66 20 69 74 20 69 73 20 6e 6f 74 0a 2a  t if it is not.*
2ae0: 2a 20 73 6f 72 74 65 64 20 61 6c 72 65 61 64 79  * sorted already
2af0: 2e 20 20 49 66 20 74 68 65 72 65 20 69 73 20 61  .  If there is a
2b00: 20 62 69 6e 61 72 79 20 74 72 65 65 20 6f 6e 20   binary tree on 
2b10: 70 2d 3e 70 54 72 65 65 2c 20 74 68 65 6e 0a 2a  p->pTree, then.*
2b20: 2a 20 63 6f 6e 76 65 72 74 20 69 74 20 69 6e 74  * convert it int
2b30: 6f 20 61 20 6c 69 73 74 20 74 6f 6f 20 61 6e 64  o a list too and
2b40: 20 6d 65 72 67 65 20 69 74 20 69 6e 74 6f 20 74   merge it into t
2b50: 68 65 20 70 2d 3e 70 45 6e 74 72 79 20 6c 69 73  he p->pEntry lis
2b60: 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  t..*/.static voi
2b70: 64 20 72 6f 77 53 65 74 54 6f 4c 69 73 74 28 52  d rowSetToList(R
2b80: 6f 77 53 65 74 20 2a 70 29 7b 0a 20 20 69 66 28  owSet *p){.  if(
2b90: 20 21 70 2d 3e 69 73 53 6f 72 74 65 64 20 29 7b   !p->isSorted ){
2ba0: 0a 20 20 20 20 72 6f 77 53 65 74 53 6f 72 74 28  .    rowSetSort(
2bb0: 70 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d  p);.  }.  if( p-
2bc0: 3e 70 54 72 65 65 20 29 7b 0a 20 20 20 20 73 74  >pTree ){.    st
2bd0: 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72 79  ruct RowSetEntry
2be0: 20 2a 70 48 65 61 64 2c 20 2a 70 54 61 69 6c 3b   *pHead, *pTail;
2bf0: 0a 20 20 20 20 72 6f 77 53 65 74 54 72 65 65 54  .    rowSetTreeT
2c00: 6f 4c 69 73 74 28 70 2d 3e 70 54 72 65 65 2c 20  oList(p->pTree, 
2c10: 26 70 48 65 61 64 2c 20 26 70 54 61 69 6c 29 3b  &pHead, &pTail);
2c20: 0a 20 20 20 20 70 2d 3e 70 54 72 65 65 20 3d 20  .    p->pTree = 
2c30: 30 3b 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79  0;.    p->pEntry
2c40: 20 3d 20 72 6f 77 53 65 74 4d 65 72 67 65 28 70   = rowSetMerge(p
2c50: 2d 3e 70 45 6e 74 72 79 2c 20 70 48 65 61 64 29  ->pEntry, pHead)
2c60: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45  ;.  }.}../*.** E
2c70: 78 74 72 61 63 74 20 74 68 65 20 73 6d 61 6c 6c  xtract the small
2c80: 65 73 74 20 65 6c 65 6d 65 6e 74 20 66 72 6f 6d  est element from
2c90: 20 74 68 65 20 52 6f 77 53 65 74 2e 0a 2a 2a 20   the RowSet..** 
2ca0: 57 72 69 74 65 20 74 68 65 20 65 6c 65 6d 65 6e  Write the elemen
2cb0: 74 20 69 6e 74 6f 20 2a 70 52 6f 77 69 64 2e 20  t into *pRowid. 
2cc0: 20 52 65 74 75 72 6e 20 31 20 6f 6e 20 73 75 63   Return 1 on suc
2cd0: 63 65 73 73 2e 20 20 52 65 74 75 72 6e 0a 2a 2a  cess.  Return.**
2ce0: 20 30 20 69 66 20 74 68 65 20 52 6f 77 53 65 74   0 if the RowSet
2cf0: 20 69 73 20 61 6c 72 65 61 64 79 20 65 6d 70 74   is already empt
2d00: 79 2e 0a 2a 2a 0a 2a 2a 20 41 66 74 65 72 20 74  y..**.** After t
2d10: 68 69 73 20 72 6f 75 74 69 6e 65 20 68 61 73 20  his routine has 
2d20: 62 65 65 6e 20 63 61 6c 6c 65 64 2c 20 74 68 65  been called, the
2d30: 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 49 6e   sqlite3RowSetIn
2d40: 73 65 72 74 28 29 0a 2a 2a 20 72 6f 75 74 69 6e  sert().** routin
2d50: 65 20 6d 61 79 20 6e 6f 74 20 62 65 20 63 61 6c  e may not be cal
2d60: 6c 65 64 20 61 67 61 69 6e 2e 20 20 0a 2a 2f 0a  led again.  .*/.
2d70: 69 6e 74 20 73 71 6c 69 74 65 33 52 6f 77 53 65  int sqlite3RowSe
2d80: 74 4e 65 78 74 28 52 6f 77 53 65 74 20 2a 70 2c  tNext(RowSet *p,
2d90: 20 69 36 34 20 2a 70 52 6f 77 69 64 29 7b 0a 20   i64 *pRowid){. 
2da0: 20 72 6f 77 53 65 74 54 6f 4c 69 73 74 28 70 29   rowSetToList(p)
2db0: 3b 0a 20 20 69 66 28 20 70 2d 3e 70 45 6e 74 72  ;.  if( p->pEntr
2dc0: 79 20 29 7b 0a 20 20 20 20 2a 70 52 6f 77 69 64  y ){.    *pRowid
2dd0: 20 3d 20 70 2d 3e 70 45 6e 74 72 79 2d 3e 76 3b   = p->pEntry->v;
2de0: 0a 20 20 20 20 70 2d 3e 70 45 6e 74 72 79 20 3d  .    p->pEntry =
2df0: 20 70 2d 3e 70 45 6e 74 72 79 2d 3e 70 52 69 67   p->pEntry->pRig
2e00: 68 74 3b 0a 20 20 20 20 69 66 28 20 70 2d 3e 70  ht;.    if( p->p
2e10: 45 6e 74 72 79 3d 3d 30 20 29 7b 0a 20 20 20 20  Entry==0 ){.    
2e20: 20 20 73 71 6c 69 74 65 33 52 6f 77 53 65 74 43    sqlite3RowSetC
2e30: 6c 65 61 72 28 70 29 3b 0a 20 20 20 20 7d 0a 20  lear(p);.    }. 
2e40: 20 20 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 7d     return 1;.  }
2e50: 65 6c 73 65 7b 0a 20 20 20 20 72 65 74 75 72 6e  else{.    return
2e60: 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a   0;.  }.}../*.**
2e70: 20 43 68 65 63 6b 20 74 6f 20 73 65 65 20 69 66   Check to see if
2e80: 20 65 6c 65 6d 65 6e 74 20 69 52 6f 77 69 64 20   element iRowid 
2e90: 77 61 73 20 69 6e 73 65 72 74 65 64 20 69 6e 74  was inserted int
2ea0: 6f 20 74 68 65 20 74 68 65 20 72 6f 77 73 65 74  o the the rowset
2eb0: 20 61 73 0a 2a 2a 20 70 61 72 74 20 6f 66 20 61   as.** part of a
2ec0: 6e 79 20 69 6e 73 65 72 74 20 62 61 74 63 68 20  ny insert batch 
2ed0: 70 72 69 6f 72 20 74 6f 20 69 42 61 74 63 68 2e  prior to iBatch.
2ee0: 20 20 52 65 74 75 72 6e 20 31 20 6f 72 20 30 2e    Return 1 or 0.
2ef0: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 52  .*/.int sqlite3R
2f00: 6f 77 53 65 74 54 65 73 74 28 52 6f 77 53 65 74  owSetTest(RowSet
2f10: 20 2a 70 52 6f 77 53 65 74 2c 20 75 38 20 69 42   *pRowSet, u8 iB
2f20: 61 74 63 68 2c 20 73 71 6c 69 74 65 33 5f 69 6e  atch, sqlite3_in
2f30: 74 36 34 20 69 52 6f 77 69 64 29 7b 0a 20 20 73  t64 iRowid){.  s
2f40: 74 72 75 63 74 20 52 6f 77 53 65 74 45 6e 74 72  truct RowSetEntr
2f50: 79 20 2a 70 3b 0a 20 20 69 66 28 20 69 42 61 74  y *p;.  if( iBat
2f60: 63 68 21 3d 70 52 6f 77 53 65 74 2d 3e 69 42 61  ch!=pRowSet->iBa
2f70: 74 63 68 20 29 7b 0a 20 20 20 20 69 66 28 20 70  tch ){.    if( p
2f80: 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 20 29  RowSet->pEntry )
2f90: 7b 0a 20 20 20 20 20 20 72 6f 77 53 65 74 54 6f  {.      rowSetTo
2fa0: 4c 69 73 74 28 70 52 6f 77 53 65 74 29 3b 0a 20  List(pRowSet);. 
2fb0: 20 20 20 20 20 70 52 6f 77 53 65 74 2d 3e 70 54       pRowSet->pT
2fc0: 72 65 65 20 3d 20 72 6f 77 53 65 74 4c 69 73 74  ree = rowSetList
2fd0: 54 6f 54 72 65 65 28 70 52 6f 77 53 65 74 2d 3e  ToTree(pRowSet->
2fe0: 70 45 6e 74 72 79 29 3b 0a 20 20 20 20 20 20 70  pEntry);.      p
2ff0: 52 6f 77 53 65 74 2d 3e 70 45 6e 74 72 79 20 3d  RowSet->pEntry =
3000: 20 30 3b 0a 20 20 20 20 20 20 70 52 6f 77 53 65   0;.      pRowSe
3010: 74 2d 3e 70 4c 61 73 74 20 3d 20 30 3b 0a 20 20  t->pLast = 0;.  
3020: 20 20 7d 0a 20 20 20 20 70 52 6f 77 53 65 74 2d    }.    pRowSet-
3030: 3e 69 42 61 74 63 68 20 3d 20 69 42 61 74 63 68  >iBatch = iBatch
3040: 3b 0a 20 20 7d 0a 20 20 70 20 3d 20 70 52 6f 77  ;.  }.  p = pRow
3050: 53 65 74 2d 3e 70 54 72 65 65 3b 0a 20 20 77 68  Set->pTree;.  wh
3060: 69 6c 65 28 20 70 20 29 7b 0a 20 20 20 20 69 66  ile( p ){.    if
3070: 28 20 70 2d 3e 76 3c 69 52 6f 77 69 64 20 29 7b  ( p->v<iRowid ){
3080: 0a 20 20 20 20 20 20 70 20 3d 20 70 2d 3e 70 52  .      p = p->pR
3090: 69 67 68 74 3b 0a 20 20 20 20 7d 65 6c 73 65 20  ight;.    }else 
30a0: 69 66 28 20 70 2d 3e 76 3e 69 52 6f 77 69 64 20  if( p->v>iRowid 
30b0: 29 7b 0a 20 20 20 20 20 20 70 20 3d 20 70 2d 3e  ){.      p = p->
30c0: 70 4c 65 66 74 3b 0a 20 20 20 20 7d 65 6c 73 65  pLeft;.    }else
30d0: 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 31  {.      return 1
30e0: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65  ;.    }.  }.  re
30f0: 74 75 72 6e 20 30 3b 0a 7d 0a                    turn 0;.}.