Artifact
c64dafba1f9fd876836c8db8682966b9d197eb1f:
- File
src/rowset.c
— part of check-in
[fc64f850]
at
2009-05-22 01:00:13
on branch trunk
— Fix an 8-byte alignment problem on HP/UX. Ticket #3869 (CVS 6666)
(user:
drh
size: 12538)
[more...]
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;.}.