0000: 2f 2a 0a 2a 2a 20 32 30 31 31 20 4a 75 6c 79 20 /*.** 2011 July
0010: 39 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68 9.**.** The auth
0020: 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 or disclaims cop
0030: 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73 yright to this s
0040: 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 ource code. In
0050: 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65 place of.** a le
0060: 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65 gal notice, here
0070: 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a is a blessing:.
0080: 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75 **.** May you
0090: 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74 do good and not
00a0: 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79 evil..** May
00b0: 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76 you find forgiv
00c0: 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65 eness for yourse
00d0: 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f lf and forgive o
00e0: 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79 thers..** May
00f0: 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c you share freel
0100: 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20 y, never taking
0110: 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69 more than you gi
0120: 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a ve..**.*********
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: 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63 6f .** This file co
0180: 6e 74 61 69 6e 73 20 63 6f 64 65 20 66 6f 72 20 ntains code for
0190: 74 68 65 20 56 64 62 65 53 6f 72 74 65 72 20 6f the VdbeSorter o
01a0: 62 6a 65 63 74 2c 20 75 73 65 64 20 69 6e 20 63 bject, used in c
01b0: 6f 6e 63 65 72 74 20 77 69 74 68 0a 2a 2a 20 61 oncert with.** a
01c0: 20 56 64 62 65 43 75 72 73 6f 72 20 74 6f 20 73 VdbeCursor to s
01d0: 6f 72 74 20 6c 61 72 67 65 20 6e 75 6d 62 65 72 ort large number
01e0: 73 20 6f 66 20 6b 65 79 73 20 28 61 73 20 6d 61 s of keys (as ma
01f0: 79 20 62 65 20 72 65 71 75 69 72 65 64 2c 20 66 y be required, f
0200: 6f 72 0a 2a 2a 20 65 78 61 6d 70 6c 65 2c 20 62 or.** example, b
0210: 79 20 43 52 45 41 54 45 20 49 4e 44 45 58 20 73 y CREATE INDEX s
0220: 74 61 74 65 6d 65 6e 74 73 20 6f 6e 20 74 61 62 tatements on tab
0230: 6c 65 73 20 74 6f 6f 20 6c 61 72 67 65 20 74 6f les too large to
0240: 20 66 69 74 20 69 6e 20 6d 61 69 6e 0a 2a 2a 20 fit in main.**
0250: 6d 65 6d 6f 72 79 29 2e 0a 2a 2f 0a 0a 23 69 6e memory)..*/..#in
0260: 63 6c 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 clude "sqliteInt
0270: 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 76 64 .h".#include "vd
0280: 62 65 49 6e 74 2e 68 22 0a 0a 23 69 66 6e 64 65 beInt.h"..#ifnde
0290: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 4d 45 f SQLITE_OMIT_ME
02a0: 52 47 45 5f 53 4f 52 54 0a 0a 74 79 70 65 64 65 RGE_SORT..typede
02b0: 66 20 73 74 72 75 63 74 20 56 64 62 65 53 6f 72 f struct VdbeSor
02c0: 74 65 72 49 74 65 72 20 56 64 62 65 53 6f 72 74 terIter VdbeSort
02d0: 65 72 49 74 65 72 3b 0a 74 79 70 65 64 65 66 20 erIter;.typedef
02e0: 73 74 72 75 63 74 20 53 6f 72 74 65 72 52 65 63 struct SorterRec
02f0: 6f 72 64 20 53 6f 72 74 65 72 52 65 63 6f 72 64 ord SorterRecord
0300: 3b 0a 0a 2f 2a 0a 2a 2a 20 4e 4f 54 45 53 20 4f ;../*.** NOTES O
0310: 4e 20 44 41 54 41 20 53 54 52 55 43 54 55 52 45 N DATA STRUCTURE
0320: 20 55 53 45 44 20 46 4f 52 20 4e 2d 57 41 59 20 USED FOR N-WAY
0330: 4d 45 52 47 45 53 3a 0a 2a 2a 0a 2a 2a 20 41 73 MERGES:.**.** As
0340: 20 6b 65 79 73 20 61 72 65 20 61 64 64 65 64 20 keys are added
0350: 74 6f 20 74 68 65 20 73 6f 72 74 65 72 2c 20 74 to the sorter, t
0360: 68 65 79 20 61 72 65 20 77 72 69 74 74 65 6e 20 hey are written
0370: 74 6f 20 64 69 73 6b 20 69 6e 20 61 20 73 65 72 to disk in a ser
0380: 69 65 73 0a 2a 2a 20 6f 66 20 73 6f 72 74 65 64 ies.** of sorted
0390: 20 70 61 63 6b 65 64 2d 6d 65 6d 6f 72 79 2d 61 packed-memory-a
03a0: 72 72 61 79 73 20 28 50 4d 41 73 29 2e 20 54 68 rrays (PMAs). Th
03b0: 65 20 73 69 7a 65 20 6f 66 20 65 61 63 68 20 50 e size of each P
03c0: 4d 41 20 69 73 20 72 6f 75 67 68 6c 79 0a 2a 2a MA is roughly.**
03d0: 20 74 68 65 20 73 61 6d 65 20 61 73 20 74 68 65 the same as the
03e0: 20 63 61 63 68 65 2d 73 69 7a 65 20 61 6c 6c 6f cache-size allo
03f0: 77 65 64 20 66 6f 72 20 74 65 6d 70 6f 72 61 72 wed for temporar
0400: 79 20 64 61 74 61 62 61 73 65 73 2e 20 49 6e 20 y databases. In
0410: 6f 72 64 65 72 0a 2a 2a 20 74 6f 20 61 6c 6c 6f order.** to allo
0420: 77 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20 w the caller to
0430: 65 78 74 72 61 63 74 20 6b 65 79 73 20 66 72 6f extract keys fro
0440: 6d 20 74 68 65 20 73 6f 72 74 65 72 20 69 6e 20 m the sorter in
0450: 73 6f 72 74 65 64 20 6f 72 64 65 72 2c 0a 2a 2a sorted order,.**
0460: 20 61 6c 6c 20 50 4d 41 73 20 63 75 72 72 65 6e all PMAs curren
0470: 74 6c 79 20 73 74 6f 72 65 64 20 6f 6e 20 64 69 tly stored on di
0480: 73 6b 20 6d 75 73 74 20 62 65 20 6d 65 72 67 65 sk must be merge
0490: 64 20 74 6f 67 65 74 68 65 72 2e 20 54 68 69 73 d together. This
04a0: 20 63 6f 6d 6d 65 6e 74 0a 2a 2a 20 64 65 73 63 comment.** desc
04b0: 72 69 62 65 73 20 74 68 65 20 64 61 74 61 20 73 ribes the data s
04c0: 74 72 75 63 74 75 72 65 20 75 73 65 64 20 74 6f tructure used to
04d0: 20 64 6f 20 73 6f 2e 20 54 68 65 20 73 74 72 75 do so. The stru
04e0: 63 74 75 72 65 20 73 75 70 70 6f 72 74 73 20 0a cture supports .
04f0: 2a 2a 20 6d 65 72 67 69 6e 67 20 61 6e 79 20 6e ** merging any n
0500: 75 6d 62 65 72 20 6f 66 20 61 72 72 61 79 73 20 umber of arrays
0510: 69 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73 in a single pass
0520: 20 77 69 74 68 20 6e 6f 20 72 65 64 75 6e 64 61 with no redunda
0530: 6e 74 20 63 6f 6d 70 61 72 69 73 6f 6e 20 0a 2a nt comparison .*
0540: 2a 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 2a 2a * operations..**
0550: 0a 2a 2a 20 54 68 65 20 61 49 74 65 72 5b 5d 20 .** The aIter[]
0560: 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20 61 array contains a
0570: 6e 20 69 74 65 72 61 74 6f 72 20 66 6f 72 20 65 n iterator for e
0580: 61 63 68 20 6f 66 20 74 68 65 20 50 4d 41 73 20 ach of the PMAs
0590: 62 65 69 6e 67 20 6d 65 72 67 65 64 2e 0a 2a 2a being merged..**
05a0: 20 41 6e 20 61 49 74 65 72 5b 5d 20 69 74 65 72 An aIter[] iter
05b0: 61 74 6f 72 20 65 69 74 68 65 72 20 70 6f 69 6e ator either poin
05c0: 74 73 20 74 6f 20 61 20 76 61 6c 69 64 20 6b 65 ts to a valid ke
05d0: 79 20 6f 72 20 65 6c 73 65 20 69 73 20 61 74 20 y or else is at
05e0: 45 4f 46 2e 20 46 6f 72 20 0a 2a 2a 20 74 68 65 EOF. For .** the
05f0: 20 70 75 72 70 6f 73 65 73 20 6f 66 20 74 68 65 purposes of the
0600: 20 70 61 72 61 67 72 61 70 68 73 20 62 65 6c 6f paragraphs belo
0610: 77 2c 20 77 65 20 61 73 73 75 6d 65 20 74 68 61 w, we assume tha
0620: 74 20 74 68 65 20 61 72 72 61 79 20 69 73 20 61 t the array is a
0630: 63 74 75 61 6c 6c 79 20 0a 2a 2a 20 4e 20 65 6c ctually .** N el
0640: 65 6d 65 6e 74 73 20 69 6e 20 73 69 7a 65 2c 20 ements in size,
0650: 77 68 65 72 65 20 4e 20 69 73 20 74 68 65 20 73 where N is the s
0660: 6d 61 6c 6c 65 73 74 20 70 6f 77 65 72 20 6f 66 mallest power of
0670: 20 32 20 67 72 65 61 74 65 72 20 74 6f 20 6f 72 2 greater to or
0680: 20 65 71 75 61 6c 20 0a 2a 2a 20 74 6f 20 74 68 equal .** to th
0690: 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 74 65 72 e number of iter
06a0: 61 74 6f 72 73 20 62 65 69 6e 67 20 6d 65 72 67 ators being merg
06b0: 65 64 2e 20 54 68 65 20 65 78 74 72 61 20 61 49 ed. The extra aI
06c0: 74 65 72 5b 5d 20 65 6c 65 6d 65 6e 74 73 20 61 ter[] elements a
06d0: 72 65 20 0a 2a 2a 20 74 72 65 61 74 65 64 20 61 re .** treated a
06e0: 73 20 69 66 20 74 68 65 79 20 61 72 65 20 65 6d s if they are em
06f0: 70 74 79 20 28 61 6c 77 61 79 73 20 61 74 20 45 pty (always at E
0700: 4f 46 29 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 OF)..**.** The a
0710: 54 72 65 65 5b 5d 20 61 72 72 61 79 20 69 73 20 Tree[] array is
0720: 61 6c 73 6f 20 4e 20 65 6c 65 6d 65 6e 74 73 20 also N elements
0730: 69 6e 20 73 69 7a 65 2e 20 54 68 65 20 76 61 6c in size. The val
0740: 75 65 20 6f 66 20 4e 20 69 73 20 73 74 6f 72 65 ue of N is store
0750: 64 20 69 6e 0a 2a 2a 20 74 68 65 20 56 64 62 65 d in.** the Vdbe
0760: 53 6f 72 74 65 72 2e 6e 54 72 65 65 20 76 61 72 Sorter.nTree var
0770: 69 61 62 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 iable..**.** The
0780: 20 66 69 6e 61 6c 20 28 4e 2f 32 29 20 65 6c 65 final (N/2) ele
0790: 6d 65 6e 74 73 20 6f 66 20 61 54 72 65 65 5b 5d ments of aTree[]
07a0: 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 72 65 73 contain the res
07b0: 75 6c 74 73 20 6f 66 20 63 6f 6d 70 61 72 69 6e ults of comparin
07c0: 67 0a 2a 2a 20 70 61 69 72 73 20 6f 66 20 69 74 g.** pairs of it
07d0: 65 72 61 74 6f 72 20 6b 65 79 73 20 74 6f 67 65 erator keys toge
07e0: 74 68 65 72 2e 20 45 6c 65 6d 65 6e 74 20 69 20 ther. Element i
07f0: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 72 65 73 contains the res
0800: 75 6c 74 20 6f 66 20 0a 2a 2a 20 63 6f 6d 70 61 ult of .** compa
0810: 72 69 6e 67 20 61 49 74 65 72 5b 32 2a 69 2d 4e ring aIter[2*i-N
0820: 5d 20 61 6e 64 20 61 49 74 65 72 5b 32 2a 69 2d ] and aIter[2*i-
0830: 4e 2b 31 5d 2e 20 57 68 69 63 68 65 76 65 72 20 N+1]. Whichever
0840: 6b 65 79 20 69 73 20 73 6d 61 6c 6c 65 72 2c 20 key is smaller,
0850: 74 68 65 0a 2a 2a 20 61 54 72 65 65 20 65 6c 65 the.** aTree ele
0860: 6d 65 6e 74 20 69 73 20 73 65 74 20 74 6f 20 74 ment is set to t
0870: 68 65 20 69 6e 64 65 78 20 6f 66 20 69 74 2e 20 he index of it.
0880: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 74 68 65 20 70 .**.** For the p
0890: 75 72 70 6f 73 65 73 20 6f 66 20 74 68 69 73 20 urposes of this
08a0: 63 6f 6d 70 61 72 69 73 6f 6e 2c 20 45 4f 46 20 comparison, EOF
08b0: 69 73 20 63 6f 6e 73 69 64 65 72 65 64 20 67 72 is considered gr
08c0: 65 61 74 65 72 20 74 68 61 6e 20 61 6e 79 0a 2a eater than any.*
08d0: 2a 20 6f 74 68 65 72 20 6b 65 79 20 76 61 6c 75 * other key valu
08e0: 65 2e 20 49 66 20 74 68 65 20 6b 65 79 73 20 61 e. If the keys a
08f0: 72 65 20 65 71 75 61 6c 20 28 6f 6e 6c 79 20 70 re equal (only p
0900: 6f 73 73 69 62 6c 65 20 77 69 74 68 20 74 77 6f ossible with two
0910: 20 45 4f 46 0a 2a 2a 20 76 61 6c 75 65 73 29 2c EOF.** values),
0920: 20 69 74 20 64 6f 65 73 6e 27 74 20 6d 61 74 74 it doesn't matt
0930: 65 72 20 77 68 69 63 68 20 69 6e 64 65 78 20 69 er which index i
0940: 73 20 73 74 6f 72 65 64 2e 0a 2a 2a 0a 2a 2a 20 s stored..**.**
0950: 54 68 65 20 28 4e 2f 34 29 20 65 6c 65 6d 65 6e The (N/4) elemen
0960: 74 73 20 6f 66 20 61 54 72 65 65 5b 5d 20 74 68 ts of aTree[] th
0970: 61 74 20 70 72 65 63 65 65 64 20 74 68 65 20 66 at preceed the f
0980: 69 6e 61 6c 20 28 4e 2f 32 29 20 64 65 73 63 72 inal (N/2) descr
0990: 69 62 65 64 20 0a 2a 2a 20 61 62 6f 76 65 20 63 ibed .** above c
09a0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64 65 ontains the inde
09b0: 78 20 6f 66 20 74 68 65 20 73 6d 61 6c 6c 65 73 x of the smalles
09c0: 74 20 6f 66 20 65 61 63 68 20 62 6c 6f 63 6b 20 t of each block
09d0: 6f 66 20 34 20 69 74 65 72 61 74 6f 72 73 2e 0a of 4 iterators..
09e0: 2a 2a 20 41 6e 64 20 73 6f 20 6f 6e 2e 20 53 6f ** And so on. So
09f0: 20 74 68 61 74 20 61 54 72 65 65 5b 31 5d 20 63 that aTree[1] c
0a00: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64 65 ontains the inde
0a10: 78 20 6f 66 20 74 68 65 20 69 74 65 72 61 74 6f x of the iterato
0a20: 72 20 74 68 61 74 20 0a 2a 2a 20 63 75 72 72 65 r that .** curre
0a30: 6e 74 6c 79 20 70 6f 69 6e 74 73 20 74 6f 20 74 ntly points to t
0a40: 68 65 20 73 6d 61 6c 6c 65 73 74 20 6b 65 79 20 he smallest key
0a50: 76 61 6c 75 65 2e 20 61 54 72 65 65 5b 30 5d 20 value. aTree[0]
0a60: 69 73 20 75 6e 75 73 65 64 2e 0a 2a 2a 0a 2a 2a is unused..**.**
0a70: 20 45 78 61 6d 70 6c 65 3a 0a 2a 2a 0a 2a 2a 20 Example:.**.**
0a80: 20 20 20 20 61 49 74 65 72 5b 30 5d 20 2d 3e 20 aIter[0] ->
0a90: 42 61 6e 61 6e 61 0a 2a 2a 20 20 20 20 20 61 49 Banana.** aI
0aa0: 74 65 72 5b 31 5d 20 2d 3e 20 46 65 69 6a 6f 61 ter[1] -> Feijoa
0ab0: 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 32 5d .** aIter[2]
0ac0: 20 2d 3e 20 45 6c 64 65 72 62 65 72 72 79 0a 2a -> Elderberry.*
0ad0: 2a 20 20 20 20 20 61 49 74 65 72 5b 33 5d 20 2d * aIter[3] -
0ae0: 3e 20 43 75 72 72 61 6e 74 0a 2a 2a 20 20 20 20 > Currant.**
0af0: 20 61 49 74 65 72 5b 34 5d 20 2d 3e 20 47 72 61 aIter[4] -> Gra
0b00: 70 65 66 72 75 69 74 0a 2a 2a 20 20 20 20 20 61 pefruit.** a
0b10: 49 74 65 72 5b 35 5d 20 2d 3e 20 41 70 70 6c 65 Iter[5] -> Apple
0b20: 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 36 5d .** aIter[6]
0b30: 20 2d 3e 20 44 75 72 69 61 6e 0a 2a 2a 20 20 20 -> Durian.**
0b40: 20 20 61 49 74 65 72 5b 37 5d 20 2d 3e 20 45 4f aIter[7] -> EO
0b50: 46 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 54 72 65 F.**.** aTre
0b60: 65 5b 5d 20 3d 20 7b 20 58 2c 20 35 20 20 20 30 e[] = { X, 5 0
0b70: 2c 20 35 20 20 20 20 30 2c 20 33 2c 20 35 2c 20 , 5 0, 3, 5,
0b80: 36 20 7d 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 75 6 }.**.** The cu
0b90: 72 72 65 6e 74 20 65 6c 65 6d 65 6e 74 20 69 73 rrent element is
0ba0: 20 22 41 70 70 6c 65 22 20 28 74 68 65 20 76 61 "Apple" (the va
0bb0: 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79 20 69 lue of the key i
0bc0: 6e 64 69 63 61 74 65 64 20 62 79 20 0a 2a 2a 20 ndicated by .**
0bd0: 69 74 65 72 61 74 6f 72 20 35 29 2e 20 57 68 65 iterator 5). Whe
0be0: 6e 20 74 68 65 20 4e 65 78 74 28 29 20 6f 70 65 n the Next() ope
0bf0: 72 61 74 69 6f 6e 20 69 73 20 69 6e 76 6f 6b 65 ration is invoke
0c00: 64 2c 20 69 74 65 72 61 74 6f 72 20 35 20 77 69 d, iterator 5 wi
0c10: 6c 6c 0a 2a 2a 20 62 65 20 61 64 76 61 6e 63 65 ll.** be advance
0c20: 64 20 74 6f 20 74 68 65 20 6e 65 78 74 20 6b 65 d to the next ke
0c30: 79 20 69 6e 20 69 74 73 20 73 65 67 6d 65 6e 74 y in its segment
0c40: 2e 20 53 61 79 20 74 68 65 20 6e 65 78 74 20 6b . Say the next k
0c50: 65 79 20 69 73 0a 2a 2a 20 22 45 67 67 70 6c 61 ey is.** "Eggpla
0c60: 6e 74 22 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 nt":.**.** a
0c70: 49 74 65 72 5b 35 5d 20 2d 3e 20 45 67 67 70 6c Iter[5] -> Eggpl
0c80: 61 6e 74 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f ant.**.** The co
0c90: 6e 74 65 6e 74 73 20 6f 66 20 61 54 72 65 65 5b ntents of aTree[
0ca0: 5d 20 61 72 65 20 75 70 64 61 74 65 64 20 66 69 ] are updated fi
0cb0: 72 73 74 20 62 79 20 63 6f 6d 70 61 72 69 6e 67 rst by comparing
0cc0: 20 74 68 65 20 6e 65 77 20 69 74 65 72 61 74 6f the new iterato
0cd0: 72 0a 2a 2a 20 35 20 6b 65 79 20 74 6f 20 74 68 r.** 5 key to th
0ce0: 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 6f 66 e current key of
0cf0: 20 69 74 65 72 61 74 6f 72 20 34 20 28 73 74 69 iterator 4 (sti
0d00: 6c 6c 20 22 47 72 61 70 65 66 72 75 69 74 22 29 ll "Grapefruit")
0d10: 2e 20 54 68 65 20 69 74 65 72 61 74 6f 72 0a 2a . The iterator.*
0d20: 2a 20 35 20 76 61 6c 75 65 20 69 73 20 73 74 69 * 5 value is sti
0d30: 6c 6c 20 73 6d 61 6c 6c 65 72 2c 20 73 6f 20 61 ll smaller, so a
0d40: 54 72 65 65 5b 36 5d 20 69 73 20 73 65 74 20 74 Tree[6] is set t
0d50: 6f 20 35 2e 20 41 6e 64 20 73 6f 20 6f 6e 20 75 o 5. And so on u
0d60: 70 20 74 68 65 20 74 72 65 65 2e 0a 2a 2a 20 54 p the tree..** T
0d70: 68 65 20 76 61 6c 75 65 20 6f 66 20 69 74 65 72 he value of iter
0d80: 61 74 6f 72 20 36 20 2d 20 22 44 75 72 69 61 6e ator 6 - "Durian
0d90: 22 20 2d 20 69 73 20 6e 6f 77 20 73 6d 61 6c 6c " - is now small
0da0: 65 72 20 74 68 61 6e 20 74 68 61 74 20 6f 66 20 er than that of
0db0: 69 74 65 72 61 74 6f 72 0a 2a 2a 20 35 2c 20 73 iterator.** 5, s
0dc0: 6f 20 61 54 72 65 65 5b 33 5d 20 69 73 20 73 65 o aTree[3] is se
0dd0: 74 20 74 6f 20 36 2e 20 4b 65 79 20 30 20 69 73 t to 6. Key 0 is
0de0: 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 6b 65 smaller than ke
0df0: 79 20 36 20 28 42 61 6e 61 6e 61 3c 44 75 72 69 y 6 (Banana<Duri
0e00: 61 6e 29 2c 0a 2a 2a 20 73 6f 20 74 68 65 20 76 an),.** so the v
0e10: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 69 6e 74 alue written int
0e20: 6f 20 65 6c 65 6d 65 6e 74 20 31 20 6f 66 20 74 o element 1 of t
0e30: 68 65 20 61 72 72 61 79 20 69 73 20 30 2e 20 41 he array is 0. A
0e40: 73 20 66 6f 6c 6c 6f 77 73 3a 0a 2a 2a 0a 2a 2a s follows:.**.**
0e50: 20 20 20 20 20 61 54 72 65 65 5b 5d 20 3d 20 7b aTree[] = {
0e60: 20 58 2c 20 30 20 20 20 30 2c 20 36 20 20 20 20 X, 0 0, 6
0e70: 30 2c 20 33 2c 20 35 2c 20 36 20 7d 0a 2a 2a 0a 0, 3, 5, 6 }.**.
0e80: 2a 2a 20 49 6e 20 6f 74 68 65 72 20 77 6f 72 64 ** In other word
0e90: 73 2c 20 65 61 63 68 20 74 69 6d 65 20 77 65 20 s, each time we
0ea0: 61 64 76 61 6e 63 65 20 74 6f 20 74 68 65 20 6e advance to the n
0eb0: 65 78 74 20 73 6f 72 74 65 72 20 65 6c 65 6d 65 ext sorter eleme
0ec0: 6e 74 2c 20 6c 6f 67 32 28 4e 29 0a 2a 2a 20 6b nt, log2(N).** k
0ed0: 65 79 20 63 6f 6d 70 61 72 69 73 6f 6e 20 6f 70 ey comparison op
0ee0: 65 72 61 74 69 6f 6e 73 20 61 72 65 20 72 65 71 erations are req
0ef0: 75 69 72 65 64 2c 20 77 68 65 72 65 20 4e 20 69 uired, where N i
0f00: 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 s the number of
0f10: 73 65 67 6d 65 6e 74 73 0a 2a 2a 20 62 65 69 6e segments.** bein
0f20: 67 20 6d 65 72 67 65 64 20 28 72 6f 75 6e 64 65 g merged (rounde
0f30: 64 20 75 70 20 74 6f 20 74 68 65 20 6e 65 78 74 d up to the next
0f40: 20 70 6f 77 65 72 20 6f 66 20 32 29 2e 0a 2a 2f power of 2)..*/
0f50: 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f 72 74 .struct VdbeSort
0f60: 65 72 20 7b 0a 20 20 69 6e 74 20 6e 49 6e 4d 65 er {. int nInMe
0f70: 6d 6f 72 79 3b 20 20 20 20 20 20 20 20 20 20 20 mory;
0f80: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e /* Curren
0f90: 74 20 73 69 7a 65 20 6f 66 20 70 52 65 63 6f 72 t size of pRecor
0fa0: 64 20 6c 69 73 74 20 61 73 20 50 4d 41 20 2a 2f d list as PMA */
0fb0: 0a 20 20 69 6e 74 20 6e 54 72 65 65 3b 20 20 20 . int nTree;
0fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0fd0: 20 20 20 2f 2a 20 55 73 65 64 20 73 69 7a 65 20 /* Used size
0fe0: 6f 66 20 61 54 72 65 65 2f 61 49 74 65 72 20 28 of aTree/aIter (
0ff0: 70 6f 77 65 72 20 6f 66 20 32 29 20 2a 2f 0a 20 power of 2) */.
1000: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 VdbeSorterIter
1010: 2a 61 49 74 65 72 3b 20 20 20 20 20 20 20 20 20 *aIter;
1020: 20 2f 2a 20 41 72 72 61 79 20 6f 66 20 69 74 65 /* Array of ite
1030: 72 61 74 6f 72 73 20 74 6f 20 6d 65 72 67 65 20 rators to merge
1040: 2a 2f 0a 20 20 69 6e 74 20 2a 61 54 72 65 65 3b */. int *aTree;
1050: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1060: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 /* Current
1070: 73 74 61 74 65 20 6f 66 20 69 6e 63 72 65 6d 65 state of increme
1080: 6e 74 61 6c 20 6d 65 72 67 65 20 2a 2f 0a 20 20 ntal merge */.
1090: 69 36 34 20 69 57 72 69 74 65 4f 66 66 3b 20 20 i64 iWriteOff;
10a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
10b0: 2f 2a 20 43 75 72 72 65 6e 74 20 77 72 69 74 65 /* Current write
10c0: 20 6f 66 66 73 65 74 20 77 69 74 68 69 6e 20 66 offset within f
10d0: 69 6c 65 20 70 54 65 6d 70 31 20 2a 2f 0a 20 20 ile pTemp1 */.
10e0: 69 36 34 20 69 52 65 61 64 4f 66 66 3b 20 20 20 i64 iReadOff;
10f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1100: 2f 2a 20 43 75 72 72 65 6e 74 20 72 65 61 64 20 /* Current read
1110: 6f 66 66 73 65 74 20 77 69 74 68 69 6e 20 66 69 offset within fi
1120: 6c 65 20 70 54 65 6d 70 31 20 2a 2f 0a 20 20 73 le pTemp1 */. s
1130: 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 54 65 qlite3_file *pTe
1140: 6d 70 31 3b 20 20 20 20 20 20 20 20 20 20 20 2f mp1; /
1150: 2a 20 50 4d 41 20 66 69 6c 65 20 31 20 2a 2f 0a * PMA file 1 */.
1160: 20 20 69 6e 74 20 6e 50 4d 41 3b 20 20 20 20 20 int nPMA;
1170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1180: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 50 /* Number of P
1190: 4d 41 73 20 73 74 6f 72 65 64 20 69 6e 20 70 54 MAs stored in pT
11a0: 65 6d 70 31 20 2a 2f 0a 20 20 53 6f 72 74 65 72 emp1 */. Sorter
11b0: 52 65 63 6f 72 64 20 2a 70 52 65 63 6f 72 64 3b Record *pRecord;
11c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 65 61 /* Hea
11d0: 64 20 6f 66 20 69 6e 2d 6d 65 6d 6f 72 79 20 72 d of in-memory r
11e0: 65 63 6f 72 64 20 6c 69 73 74 20 2a 2f 0a 20 20 ecord list */.
11f0: 69 6e 74 20 6d 6e 50 6d 61 53 69 7a 65 3b 20 20 int mnPmaSize;
1200: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1210: 2f 2a 20 4d 69 6e 69 6d 75 6d 20 50 4d 41 20 73 /* Minimum PMA s
1220: 69 7a 65 2c 20 69 6e 20 62 79 74 65 73 20 2a 2f ize, in bytes */
1230: 0a 20 20 69 6e 74 20 6d 78 50 6d 61 53 69 7a 65 . int mxPmaSize
1240: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
1250: 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 50 4d /* Maximum PM
1260: 41 20 73 69 7a 65 2c 20 69 6e 20 62 79 74 65 73 A size, in bytes
1270: 2e 20 20 30 3d 3d 6e 6f 20 6c 69 6d 69 74 20 2a . 0==no limit *
1280: 2f 0a 20 20 55 6e 70 61 63 6b 65 64 52 65 63 6f /. UnpackedReco
1290: 72 64 20 2a 70 55 6e 70 61 63 6b 65 64 3b 20 20 rd *pUnpacked;
12a0: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 75 /* Used to u
12b0: 6e 70 61 63 6b 20 6b 65 79 73 20 2a 2f 0a 7d 3b npack keys */.};
12c0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c ../*.** The foll
12d0: 6f 77 69 6e 67 20 74 79 70 65 20 69 73 20 61 6e owing type is an
12e0: 20 69 74 65 72 61 74 6f 72 20 66 6f 72 20 61 20 iterator for a
12f0: 50 4d 41 2e 20 49 74 20 63 61 63 68 65 73 20 74 PMA. It caches t
1300: 68 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 69 he current key i
1310: 6e 20 0a 2a 2a 20 76 61 72 69 61 62 6c 65 73 20 n .** variables
1320: 6e 4b 65 79 2f 61 4b 65 79 2e 20 49 66 20 74 68 nKey/aKey. If th
1330: 65 20 69 74 65 72 61 74 6f 72 20 69 73 20 61 74 e iterator is at
1340: 20 45 4f 46 2c 20 70 46 69 6c 65 3d 3d 30 2e 0a EOF, pFile==0..
1350: 2a 2f 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f */.struct VdbeSo
1360: 72 74 65 72 49 74 65 72 20 7b 0a 20 20 69 36 34 rterIter {. i64
1370: 20 69 52 65 61 64 4f 66 66 3b 20 20 20 20 20 20 iReadOff;
1380: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
1390: 43 75 72 72 65 6e 74 20 72 65 61 64 20 6f 66 66 Current read off
13a0: 73 65 74 20 2a 2f 0a 20 20 69 36 34 20 69 45 6f set */. i64 iEo
13b0: 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 f;
13c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 31 20 62 79 /* 1 by
13d0: 74 65 20 70 61 73 74 20 45 4f 46 20 66 6f 72 20 te past EOF for
13e0: 74 68 69 73 20 69 74 65 72 61 74 6f 72 20 2a 2f this iterator */
13f0: 0a 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 . sqlite3_file
1400: 2a 70 46 69 6c 65 3b 20 20 20 20 20 20 20 20 20 *pFile;
1410: 20 20 20 2f 2a 20 46 69 6c 65 20 69 74 65 72 61 /* File itera
1420: 74 6f 72 20 69 73 20 72 65 61 64 69 6e 67 20 66 tor is reading f
1430: 72 6f 6d 20 2a 2f 0a 20 20 69 6e 74 20 6e 41 6c rom */. int nAl
1440: 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20 20 loc;
1450: 20 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65 /* Byte
1460: 73 20 6f 66 20 73 70 61 63 65 20 61 74 20 61 41 s of space at aA
1470: 6c 6c 6f 63 20 2a 2f 0a 20 20 75 38 20 2a 61 41 lloc */. u8 *aA
1480: 6c 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20 lloc;
1490: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6c 6c /* All
14a0: 6f 63 61 74 65 64 20 73 70 61 63 65 20 2a 2f 0a ocated space */.
14b0: 20 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 20 20 int nKey;
14c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
14d0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 /* Number of b
14e0: 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a 20 ytes in key */.
14f0: 20 75 38 20 2a 61 4b 65 79 3b 20 20 20 20 20 20 u8 *aKey;
1500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1510: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 63 /* Pointer to c
1520: 75 72 72 65 6e 74 20 6b 65 79 20 2a 2f 0a 7d 3b urrent key */.};
1530: 0a 0a 2f 2a 0a 2a 2a 20 41 20 73 74 72 75 63 74 ../*.** A struct
1540: 75 72 65 20 74 6f 20 73 74 6f 72 65 20 61 20 73 ure to store a s
1550: 69 6e 67 6c 65 20 72 65 63 6f 72 64 2e 20 41 6c ingle record. Al
1560: 6c 20 69 6e 2d 6d 65 6d 6f 72 79 20 72 65 63 6f l in-memory reco
1570: 72 64 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 rds are connecte
1580: 64 0a 2a 2a 20 74 6f 67 65 74 68 65 72 20 69 6e d.** together in
1590: 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 to a linked list
15a0: 20 68 65 61 64 65 64 20 61 74 20 56 64 62 65 53 headed at VdbeS
15b0: 6f 72 74 65 72 2e 70 52 65 63 6f 72 64 20 75 73 orter.pRecord us
15c0: 69 6e 67 20 74 68 65 20 0a 2a 2a 20 53 6f 72 74 ing the .** Sort
15d0: 65 72 52 65 63 6f 72 64 2e 70 4e 65 78 74 20 70 erRecord.pNext p
15e0: 6f 69 6e 74 65 72 2e 0a 2a 2f 0a 73 74 72 75 63 ointer..*/.struc
15f0: 74 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 7b t SorterRecord {
1600: 0a 20 20 76 6f 69 64 20 2a 70 56 61 6c 3b 0a 20 . void *pVal;.
1610: 20 69 6e 74 20 6e 56 61 6c 3b 0a 20 20 53 6f 72 int nVal;. Sor
1620: 74 65 72 52 65 63 6f 72 64 20 2a 70 4e 65 78 74 terRecord *pNext
1630: 3b 0a 7d 3b 0a 0a 2f 2a 20 4d 69 6e 69 6d 75 6d ;.};../* Minimum
1640: 20 61 6c 6c 6f 77 61 62 6c 65 20 76 61 6c 75 65 allowable value
1650: 20 66 6f 72 20 74 68 65 20 56 64 62 65 53 6f 72 for the VdbeSor
1660: 74 65 72 2e 6e 57 6f 72 6b 69 6e 67 20 76 61 72 ter.nWorking var
1670: 69 61 62 6c 65 20 2a 2f 0a 23 64 65 66 69 6e 65 iable */.#define
1680: 20 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b SORTER_MIN_WORK
1690: 49 4e 47 20 31 30 0a 0a 2f 2a 20 4d 61 78 69 6d ING 10../* Maxim
16a0: 75 6d 20 6e 75 6d 62 65 72 20 6f 66 20 73 65 67 um number of seg
16b0: 6d 65 6e 74 73 20 74 6f 20 6d 65 72 67 65 20 69 ments to merge i
16c0: 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73 2e n a single pass.
16d0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 4f 52 54 */.#define SORT
16e0: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 ER_MAX_MERGE_COU
16f0: 4e 54 20 31 36 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 NT 16../*.** Fre
1700: 65 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 62 65 6c e all memory bel
1710: 6f 6e 67 69 6e 67 20 74 6f 20 74 68 65 20 56 64 onging to the Vd
1720: 62 65 53 6f 72 74 65 72 49 74 65 72 20 6f 62 6a beSorterIter obj
1730: 65 63 74 20 70 61 73 73 65 64 20 61 73 20 74 68 ect passed as th
1740: 65 20 73 65 63 6f 6e 64 0a 2a 2a 20 61 72 67 75 e second.** argu
1750: 6d 65 6e 74 2e 20 41 6c 6c 20 73 74 72 75 63 74 ment. All struct
1760: 75 72 65 20 66 69 65 6c 64 73 20 61 72 65 20 73 ure fields are s
1770: 65 74 20 74 6f 20 7a 65 72 6f 20 62 65 66 6f 72 et to zero befor
1780: 65 20 72 65 74 75 72 6e 69 6e 67 2e 0a 2a 2f 0a e returning..*/.
1790: 73 74 61 74 69 63 20 76 6f 69 64 20 76 64 62 65 static void vdbe
17a0: 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 73 SorterIterZero(s
17b0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 qlite3 *db, Vdbe
17c0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65 SorterIter *pIte
17d0: 72 29 7b 0a 20 20 73 71 6c 69 74 65 33 44 62 46 r){. sqlite3DbF
17e0: 72 65 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61 ree(db, pIter->a
17f0: 41 6c 6c 6f 63 29 3b 0a 20 20 6d 65 6d 73 65 74 Alloc);. memset
1800: 28 70 49 74 65 72 2c 20 30 2c 20 73 69 7a 65 6f (pIter, 0, sizeo
1810: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 f(VdbeSorterIter
1820: 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76 ));.}../*.** Adv
1830: 61 6e 63 65 20 69 74 65 72 61 74 6f 72 20 70 49 ance iterator pI
1840: 74 65 72 20 74 6f 20 74 68 65 20 6e 65 78 74 20 ter to the next
1850: 6b 65 79 20 69 6e 20 69 74 73 20 50 4d 41 2e 20 key in its PMA.
1860: 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b Return SQLITE_OK
1870: 20 69 66 0a 2a 2a 20 6e 6f 20 65 72 72 6f 72 20 if.** no error
1880: 6f 63 63 75 72 73 2c 20 6f 72 20 61 6e 20 53 51 occurs, or an SQ
1890: 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20 Lite error code
18a0: 69 66 20 6f 6e 65 20 64 6f 65 73 2e 0a 2a 2f 0a if one does..*/.
18b0: 73 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53 static int vdbeS
18c0: 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28 0a 20 orterIterNext(.
18d0: 20 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 20 sqlite3 *db,
18e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
18f0: 20 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 6e /* Database han
1900: 64 6c 65 20 28 66 6f 72 20 73 71 6c 69 74 65 33 dle (for sqlite3
1910: 44 62 4d 61 6c 6c 6f 63 28 29 20 29 20 2a 2f 0a DbMalloc() ) */.
1920: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 VdbeSorterIter
1930: 20 2a 70 49 74 65 72 20 20 20 20 20 20 20 20 20 *pIter
1940: 20 20 2f 2a 20 49 74 65 72 61 74 6f 72 20 74 6f /* Iterator to
1950: 20 61 64 76 61 6e 63 65 20 2a 2f 0a 29 7b 0a 20 advance */.){.
1960: 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20 int rc;
1970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1980: 20 2f 2a 20 52 65 74 75 72 6e 20 43 6f 64 65 20 /* Return Code
1990: 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 61 64 3b 20 */. int nRead;
19a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
19b0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f /* Number o
19c0: 66 20 62 79 74 65 73 20 72 65 61 64 20 2a 2f 0a f bytes read */.
19d0: 20 20 69 6e 74 20 6e 52 65 63 20 3d 20 30 3b 20 int nRec = 0;
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
19f0: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 72 65 63 /* Size of rec
1a00: 6f 72 64 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a ord in bytes */.
1a10: 20 20 69 6e 74 20 69 4f 66 66 20 3d 20 30 3b 20 int iOff = 0;
1a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1a30: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 73 65 72 /* Size of ser
1a40: 69 61 6c 69 7a 65 64 20 73 69 7a 65 20 76 61 72 ialized size var
1a50: 69 6e 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a int in bytes */.
1a60: 0a 20 20 6e 52 65 61 64 20 3d 20 70 49 74 65 72 . nRead = pIter
1a70: 2d 3e 69 45 6f 66 20 2d 20 70 49 74 65 72 2d 3e ->iEof - pIter->
1a80: 69 52 65 61 64 4f 66 66 3b 0a 20 20 69 66 28 20 iReadOff;. if(
1a90: 6e 52 65 61 64 3e 35 20 29 20 6e 52 65 61 64 20 nRead>5 ) nRead
1aa0: 3d 20 35 3b 0a 20 20 69 66 28 20 6e 52 65 61 64 = 5;. if( nRead
1ab0: 3c 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 54 68 <=0 ){. /* Th
1ac0: 69 73 20 69 73 20 61 6e 20 45 4f 46 20 63 6f 6e is is an EOF con
1ad0: 64 69 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 76 64 dition */. vd
1ae0: 62 65 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f beSorterIterZero
1af0: 28 64 62 2c 20 70 49 74 65 72 29 3b 0a 20 20 20 (db, pIter);.
1b00: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f return SQLITE_O
1b10: 4b 3b 0a 20 20 7d 0a 0a 20 20 72 63 20 3d 20 73 K;. }.. rc = s
1b20: 71 6c 69 74 65 33 4f 73 52 65 61 64 28 70 49 74 qlite3OsRead(pIt
1b30: 65 72 2d 3e 70 46 69 6c 65 2c 20 70 49 74 65 72 er->pFile, pIter
1b40: 2d 3e 61 41 6c 6c 6f 63 2c 20 6e 52 65 61 64 2c ->aAlloc, nRead,
1b50: 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 pIter->iReadOff
1b60: 29 3b 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c );. if( rc==SQL
1b70: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 69 4f ITE_OK ){. iO
1b80: 66 66 20 3d 20 67 65 74 56 61 72 69 6e 74 33 32 ff = getVarint32
1b90: 28 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 2c 20 (pIter->aAlloc,
1ba0: 6e 52 65 63 29 3b 0a 20 20 20 20 69 66 28 20 28 nRec);. if( (
1bb0: 69 4f 66 66 2b 6e 52 65 63 29 3e 6e 52 65 61 64 iOff+nRec)>nRead
1bc0: 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e 52 ){. int nR
1bd0: 65 61 64 32 3b 20 20 20 20 20 20 20 20 20 20 20 ead2;
1be0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 /* Numbe
1bf0: 72 20 6f 66 20 65 78 74 72 61 20 62 79 74 65 73 r of extra bytes
1c00: 20 74 6f 20 72 65 61 64 20 2a 2f 0a 20 20 20 20 to read */.
1c10: 20 20 69 66 28 20 28 69 4f 66 66 2b 6e 52 65 63 if( (iOff+nRec
1c20: 29 3e 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 20 )>pIter->nAlloc
1c30: 29 7b 0a 20 20 20 20 20 20 20 20 69 6e 74 20 6e ){. int n
1c40: 4e 65 77 20 3d 20 70 49 74 65 72 2d 3e 6e 41 6c New = pIter->nAl
1c50: 6c 6f 63 2a 32 3b 0a 20 20 20 20 20 20 20 20 77 loc*2;. w
1c60: 68 69 6c 65 28 20 28 69 4f 66 66 2b 6e 52 65 63 hile( (iOff+nRec
1c70: 29 3e 6e 4e 65 77 20 29 20 6e 4e 65 77 20 3d 20 )>nNew ) nNew =
1c80: 6e 4e 65 77 2a 32 3b 0a 20 20 20 20 20 20 20 20 nNew*2;.
1c90: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 3d 20 pIter->aAlloc =
1ca0: 73 71 6c 69 74 65 33 44 62 52 65 61 6c 6c 6f 63 sqlite3DbRealloc
1cb0: 4f 72 46 72 65 65 28 64 62 2c 20 70 49 74 65 72 OrFree(db, pIter
1cc0: 2d 3e 61 41 6c 6c 6f 63 2c 20 6e 4e 65 77 29 3b ->aAlloc, nNew);
1cd0: 0a 20 20 20 20 20 20 20 20 69 66 28 20 21 70 49 . if( !pI
1ce0: 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 29 20 72 65 ter->aAlloc ) re
1cf0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 turn SQLITE_NOME
1d00: 4d 3b 0a 20 20 20 20 20 20 20 20 70 49 74 65 72 M;. pIter
1d10: 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 4e 65 77 3b ->nAlloc = nNew;
1d20: 0a 20 20 20 20 20 20 7d 0a 20 20 0a 20 20 20 20 . }. .
1d30: 20 20 6e 52 65 61 64 32 20 3d 20 69 4f 66 66 20 nRead2 = iOff
1d40: 2b 20 6e 52 65 63 20 2d 20 6e 52 65 61 64 3b 0a + nRec - nRead;.
1d50: 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74 rc = sqlit
1d60: 65 33 4f 73 52 65 61 64 28 0a 20 20 20 20 20 20 e3OsRead(.
1d70: 20 20 20 20 70 49 74 65 72 2d 3e 70 46 69 6c 65 pIter->pFile
1d80: 2c 20 26 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 , &pIter->aAlloc
1d90: 5b 6e 52 65 61 64 5d 2c 20 6e 52 65 61 64 32 2c [nRead], nRead2,
1da0: 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 pIter->iReadOff
1db0: 2b 6e 52 65 61 64 0a 20 20 20 20 20 20 29 3b 0a +nRead. );.
1dc0: 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 61 73 73 }. }.. ass
1dd0: 65 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f ert( rc!=SQLITE_
1de0: 4f 4b 20 7c 7c 20 6e 52 65 63 3e 30 20 29 3b 0a OK || nRec>0 );.
1df0: 20 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 pIter->iReadOf
1e00: 66 20 2b 3d 20 69 4f 66 66 2b 6e 52 65 63 3b 0a f += iOff+nRec;.
1e10: 20 20 70 49 74 65 72 2d 3e 6e 4b 65 79 20 3d 20 pIter->nKey =
1e20: 6e 52 65 63 3b 0a 20 20 70 49 74 65 72 2d 3e 61 nRec;. pIter->a
1e30: 4b 65 79 20 3d 20 26 70 49 74 65 72 2d 3e 61 41 Key = &pIter->aA
1e40: 6c 6c 6f 63 5b 69 4f 66 66 5d 3b 0a 20 20 72 65 lloc[iOff];. re
1e50: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a turn rc;.}../*.*
1e60: 2a 20 57 72 69 74 65 20 61 20 73 69 6e 67 6c 65 * Write a single
1e70: 20 76 61 72 69 6e 74 2c 20 76 61 6c 75 65 20 69 varint, value i
1e80: 56 61 6c 2c 20 74 6f 20 66 69 6c 65 2d 64 65 73 Val, to file-des
1e90: 63 72 69 70 74 6f 72 20 70 46 69 6c 65 2e 20 52 criptor pFile. R
1ea0: 65 74 75 72 6e 0a 2a 2a 20 53 51 4c 49 54 45 5f eturn.** SQLITE_
1eb0: 4f 4b 20 69 66 20 73 75 63 63 65 73 73 66 75 6c OK if successful
1ec0: 2c 20 6f 72 20 61 6e 20 53 51 4c 69 74 65 20 65 , or an SQLite e
1ed0: 72 72 6f 72 20 63 6f 64 65 20 69 66 20 73 6f 6d rror code if som
1ee0: 65 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2e 0a e error occurs..
1ef0: 2a 2a 0a 2a 2a 20 54 68 65 20 76 61 6c 75 65 20 **.** The value
1f00: 6f 66 20 2a 70 69 4f 66 66 73 65 74 20 77 68 65 of *piOffset whe
1f10: 6e 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 n this function
1f20: 69 73 20 63 61 6c 6c 65 64 20 69 73 20 75 73 65 is called is use
1f30: 64 20 61 73 20 74 68 65 20 62 79 74 65 0a 2a 2a d as the byte.**
1f40: 20 6f 66 66 73 65 74 20 69 6e 20 66 69 6c 65 20 offset in file
1f50: 70 46 69 6c 65 20 74 6f 20 77 72 69 74 65 20 74 pFile to write t
1f60: 6f 2e 20 42 65 66 6f 72 65 20 72 65 74 75 72 6e o. Before return
1f70: 69 6e 67 2c 20 2a 70 69 4f 66 66 73 65 74 20 69 ing, *piOffset i
1f80: 73 20 0a 2a 2a 20 69 6e 63 72 65 6d 65 6e 74 65 s .** incremente
1f90: 64 20 62 79 20 74 68 65 20 6e 75 6d 62 65 72 20 d by the number
1fa0: 6f 66 20 62 79 74 65 73 20 77 72 69 74 74 65 6e of bytes written
1fb0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 ..*/.static int
1fc0: 76 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 56 vdbeSorterWriteV
1fd0: 61 72 69 6e 74 28 0a 20 20 73 71 6c 69 74 65 33 arint(. sqlite3
1fe0: 5f 66 69 6c 65 20 2a 70 46 69 6c 65 2c 20 20 20 _file *pFile,
1ff0: 20 20 20 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 /* File
2000: 20 74 6f 20 77 72 69 74 65 20 74 6f 20 2a 2f 0a to write to */.
2010: 20 20 69 36 34 20 69 56 61 6c 2c 20 20 20 20 20 i64 iVal,
2020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2030: 20 20 2f 2a 20 56 61 6c 75 65 20 74 6f 20 77 72 /* Value to wr
2040: 69 74 65 20 61 73 20 61 20 76 61 72 69 6e 74 20 ite as a varint
2050: 2a 2f 0a 20 20 69 36 34 20 2a 70 69 4f 66 66 73 */. i64 *piOffs
2060: 65 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20 et
2070: 20 20 20 20 20 2f 2a 20 49 4e 2f 4f 55 54 3a 20 /* IN/OUT:
2080: 57 72 69 74 65 20 6f 66 66 73 65 74 20 69 6e 20 Write offset in
2090: 66 69 6c 65 20 70 46 69 6c 65 20 2a 2f 0a 29 7b file pFile */.){
20a0: 0a 20 20 75 38 20 61 56 61 72 69 6e 74 5b 39 5d . u8 aVarint[9]
20b0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
20c0: 20 20 20 2f 2a 20 42 75 66 66 65 72 20 6c 61 72 /* Buffer lar
20d0: 67 65 20 65 6e 6f 75 67 68 20 66 6f 72 20 61 20 ge enough for a
20e0: 76 61 72 69 6e 74 20 2a 2f 0a 20 20 69 6e 74 20 varint */. int
20f0: 6e 56 61 72 69 6e 74 3b 20 20 20 20 20 20 20 20 nVarint;
2100: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e /* N
2110: 75 6d 62 65 72 20 6f 66 20 75 73 65 64 20 62 79 umber of used by
2120: 74 65 73 20 69 6e 20 76 61 72 69 6e 74 20 2a 2f tes in varint */
2130: 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 . int rc;
2140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2150: 20 20 20 2f 2a 20 52 65 73 75 6c 74 20 6f 66 20 /* Result of
2160: 77 72 69 74 65 28 29 20 63 61 6c 6c 20 2a 2f 0a write() call */.
2170: 0a 20 20 6e 56 61 72 69 6e 74 20 3d 20 73 71 6c . nVarint = sql
2180: 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 61 56 ite3PutVarint(aV
2190: 61 72 69 6e 74 2c 20 69 56 61 6c 29 3b 0a 20 20 arint, iVal);.
21a0: 72 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 57 72 rc = sqlite3OsWr
21b0: 69 74 65 28 70 46 69 6c 65 2c 20 61 56 61 72 69 ite(pFile, aVari
21c0: 6e 74 2c 20 6e 56 61 72 69 6e 74 2c 20 2a 70 69 nt, nVarint, *pi
21d0: 4f 66 66 73 65 74 29 3b 0a 20 20 2a 70 69 4f 66 Offset);. *piOf
21e0: 66 73 65 74 20 2b 3d 20 6e 56 61 72 69 6e 74 3b fset += nVarint;
21f0: 0a 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d .. return rc;.}
2200: 0a 0a 2f 2a 0a 2a 2a 20 52 65 61 64 20 61 20 73 ../*.** Read a s
2210: 69 6e 67 6c 65 20 76 61 72 69 6e 74 20 66 72 6f ingle varint fro
2220: 6d 20 66 69 6c 65 2d 64 65 73 63 72 69 70 74 6f m file-descripto
2230: 72 20 70 46 69 6c 65 2e 20 52 65 74 75 72 6e 20 r pFile. Return
2240: 53 51 4c 49 54 45 5f 4f 4b 20 69 66 0a 2a 2a 20 SQLITE_OK if.**
2250: 73 75 63 63 65 73 73 66 75 6c 2c 20 6f 72 20 61 successful, or a
2260: 6e 20 53 51 4c 69 74 65 20 65 72 72 6f 72 20 63 n SQLite error c
2270: 6f 64 65 20 69 66 20 73 6f 6d 65 20 65 72 72 6f ode if some erro
2280: 72 20 6f 63 63 75 72 73 2e 0a 2a 2a 0a 2a 2a 20 r occurs..**.**
2290: 54 68 65 20 76 61 6c 75 65 20 6f 66 20 2a 70 69 The value of *pi
22a0: 4f 66 66 73 65 74 20 77 68 65 6e 20 74 68 69 73 Offset when this
22b0: 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 63 61 6c function is cal
22c0: 6c 65 64 20 69 73 20 75 73 65 64 20 61 73 20 74 led is used as t
22d0: 68 65 0a 2a 2a 20 62 79 74 65 20 6f 66 66 73 65 he.** byte offse
22e0: 74 20 69 6e 20 66 69 6c 65 20 70 46 69 6c 65 20 t in file pFile
22f0: 66 72 6f 6d 20 77 68 65 6e 63 65 20 74 6f 20 72 from whence to r
2300: 65 61 64 20 74 68 65 20 76 61 72 69 6e 74 2e 20 ead the varint.
2310: 49 66 20 73 75 63 63 65 73 73 66 75 6c 0a 2a 2a If successful.**
2320: 20 28 69 2e 65 2e 20 69 66 20 6e 6f 20 49 4f 20 (i.e. if no IO
2330: 65 72 72 6f 72 20 6f 63 63 75 72 73 29 2c 20 74 error occurs), t
2340: 68 65 6e 20 2a 70 69 4f 66 66 73 65 74 20 69 73 hen *piOffset is
2350: 20 73 65 74 20 74 6f 20 74 68 65 20 6f 66 66 73 set to the offs
2360: 65 74 20 6f 66 0a 2a 2a 20 74 68 65 20 66 69 72 et of.** the fir
2370: 73 74 20 62 79 74 65 20 70 61 73 74 20 74 68 65 st byte past the
2380: 20 65 6e 64 20 6f 66 20 74 68 65 20 76 61 72 69 end of the vari
2390: 6e 74 20 62 65 66 6f 72 65 20 72 65 74 75 72 6e nt before return
23a0: 69 6e 67 2e 20 2a 70 69 56 61 6c 20 69 73 0a 2a ing. *piVal is.*
23b0: 2a 20 73 65 74 20 74 6f 20 74 68 65 20 69 6e 74 * set to the int
23c0: 65 67 65 72 20 76 61 6c 75 65 20 72 65 61 64 2e eger value read.
23d0: 20 49 66 20 61 6e 20 65 72 72 6f 72 20 6f 63 63 If an error occ
23e0: 75 72 73 2c 20 74 68 65 20 66 69 6e 61 6c 20 76 urs, the final v
23f0: 61 6c 75 65 73 20 6f 66 0a 2a 2a 20 62 6f 74 68 alues of.** both
2400: 20 2a 70 69 4f 66 66 73 65 74 20 61 6e 64 20 2a *piOffset and *
2410: 70 69 56 61 6c 20 61 72 65 20 75 6e 64 65 66 69 piVal are undefi
2420: 6e 65 64 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 ned..*/.static i
2430: 6e 74 20 76 64 62 65 53 6f 72 74 65 72 52 65 61 nt vdbeSorterRea
2440: 64 56 61 72 69 6e 74 28 0a 20 20 73 71 6c 69 74 dVarint(. sqlit
2450: 65 33 5f 66 69 6c 65 20 2a 70 46 69 6c 65 2c 20 e3_file *pFile,
2460: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 69 /* Fi
2470: 6c 65 20 74 6f 20 72 65 61 64 20 66 72 6f 6d 20 le to read from
2480: 2a 2f 0a 20 20 69 36 34 20 2a 70 69 4f 66 66 73 */. i64 *piOffs
2490: 65 74 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 et,
24a0: 20 20 20 20 20 2f 2a 20 49 4e 2f 4f 55 54 3a 20 /* IN/OUT:
24b0: 52 65 61 64 20 6f 66 66 73 65 74 20 69 6e 20 70 Read offset in p
24c0: 46 69 6c 65 20 2a 2f 0a 20 20 69 36 34 20 2a 70 File */. i64 *p
24d0: 69 56 61 6c 20 20 20 20 20 20 20 20 20 20 20 20 iVal
24e0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 /* OUT
24f0: 3a 20 56 61 6c 75 65 20 72 65 61 64 20 66 72 6f : Value read fro
2500: 6d 20 66 69 6c 65 20 2a 2f 0a 29 7b 0a 20 20 75 m file */.){. u
2510: 38 20 61 56 61 72 69 6e 74 5b 39 5d 3b 20 20 20 8 aVarint[9];
2520: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
2530: 2a 20 42 75 66 66 65 72 20 6c 61 72 67 65 20 65 * Buffer large e
2540: 6e 6f 75 67 68 20 66 6f 72 20 61 20 76 61 72 69 nough for a vari
2550: 6e 74 20 2a 2f 0a 20 20 69 36 34 20 69 4f 66 66 nt */. i64 iOff
2560: 20 3d 20 2a 70 69 4f 66 66 73 65 74 3b 20 20 20 = *piOffset;
2570: 20 20 20 20 20 20 20 20 2f 2a 20 4f 66 66 73 65 /* Offse
2580: 74 20 69 6e 20 66 69 6c 65 20 74 6f 20 72 65 61 t in file to rea
2590: 64 20 66 72 6f 6d 20 2a 2f 0a 20 20 69 6e 74 20 d from */. int
25a0: 72 63 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 rc;
25b0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 /* R
25c0: 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a 0a 20 eturn code */..
25d0: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 52 rc = sqlite3OsR
25e0: 65 61 64 28 70 46 69 6c 65 2c 20 61 56 61 72 69 ead(pFile, aVari
25f0: 6e 74 2c 20 39 2c 20 69 4f 66 66 29 3b 0a 20 20 nt, 9, iOff);.
2600: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f if( rc==SQLITE_O
2610: 4b 20 29 7b 0a 20 20 20 20 2a 70 69 4f 66 66 73 K ){. *piOffs
2620: 65 74 20 2b 3d 20 67 65 74 56 61 72 69 6e 74 28 et += getVarint(
2630: 61 56 61 72 69 6e 74 2c 20 28 75 36 34 20 2a 29 aVarint, (u64 *)
2640: 70 69 56 61 6c 29 3b 0a 20 20 7d 0a 0a 20 20 72 piVal);. }.. r
2650: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a eturn rc;.}../*.
2660: 2a 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 69 74 ** Initialize it
2670: 65 72 61 74 6f 72 20 70 49 74 65 72 20 74 6f 20 erator pIter to
2680: 73 63 61 6e 20 74 68 72 6f 75 67 68 20 74 68 65 scan through the
2690: 20 50 4d 41 20 73 74 6f 72 65 64 20 69 6e 20 66 PMA stored in f
26a0: 69 6c 65 20 70 46 69 6c 65 0a 2a 2a 20 73 74 61 ile pFile.** sta
26b0: 72 74 69 6e 67 20 61 74 20 6f 66 66 73 65 74 20 rting at offset
26c0: 69 53 74 61 72 74 20 61 6e 64 20 65 6e 64 69 6e iStart and endin
26d0: 67 20 61 74 20 6f 66 66 73 65 74 20 69 45 6f 66 g at offset iEof
26e0: 2d 31 2e 20 54 68 69 73 20 66 75 6e 63 74 69 6f -1. This functio
26f0: 6e 20 0a 2a 2a 20 6c 65 61 76 65 73 20 74 68 65 n .** leaves the
2700: 20 69 74 65 72 61 74 6f 72 20 70 6f 69 6e 74 69 iterator pointi
2710: 6e 67 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 ng to the first
2720: 6b 65 79 20 69 6e 20 74 68 65 20 50 4d 41 20 28 key in the PMA (
2730: 6f 72 20 45 4f 46 20 69 66 20 74 68 65 20 0a 2a or EOF if the .*
2740: 2a 20 50 4d 41 20 69 73 20 65 6d 70 74 79 29 2e * PMA is empty).
2750: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 .*/.static int v
2760: 64 62 65 53 6f 72 74 65 72 49 74 65 72 49 6e 69 dbeSorterIterIni
2770: 74 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 t(. sqlite3 *db
2780: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,
2790: 20 20 20 20 20 2f 2a 20 44 61 74 61 62 61 73 65 /* Database
27a0: 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 56 64 62 handle */. Vdb
27b0: 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 eSorter *pSorter
27c0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 , /*
27d0: 53 6f 72 74 65 72 20 6f 62 6a 65 63 74 20 2a 2f Sorter object */
27e0: 0a 20 20 69 36 34 20 69 53 74 61 72 74 2c 20 20 . i64 iStart,
27f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2800: 20 20 20 2f 2a 20 53 74 61 72 74 20 6f 66 66 73 /* Start offs
2810: 65 74 20 69 6e 20 70 46 69 6c 65 20 2a 2f 0a 20 et in pFile */.
2820: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 VdbeSorterIter
2830: 2a 70 49 74 65 72 2c 20 20 20 20 20 20 20 20 20 *pIter,
2840: 20 2f 2a 20 49 74 65 72 61 74 6f 72 20 74 6f 20 /* Iterator to
2850: 70 6f 70 75 6c 61 74 65 20 2a 2f 0a 20 20 69 36 populate */. i6
2860: 34 20 2a 70 6e 42 79 74 65 20 20 20 20 20 20 20 4 *pnByte
2870: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
2880: 20 49 4e 2f 4f 55 54 3a 20 49 6e 63 72 65 6d 65 IN/OUT: Increme
2890: 6e 74 20 74 68 69 73 20 76 61 6c 75 65 20 62 79 nt this value by
28a0: 20 50 4d 41 20 73 69 7a 65 20 2a 2f 0a 29 7b 0a PMA size */.){.
28b0: 20 20 69 6e 74 20 72 63 3b 0a 0a 20 20 61 73 73 int rc;.. ass
28c0: 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 69 57 ert( pSorter->iW
28d0: 72 69 74 65 4f 66 66 3e 69 53 74 61 72 74 20 29 riteOff>iStart )
28e0: 3b 0a 20 20 61 73 73 65 72 74 28 20 70 49 74 65 ;. assert( pIte
28f0: 72 2d 3e 61 41 6c 6c 6f 63 3d 3d 30 20 29 3b 0a r->aAlloc==0 );.
2900: 20 20 70 49 74 65 72 2d 3e 70 46 69 6c 65 20 3d pIter->pFile =
2910: 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 pSorter->pTemp1
2920: 3b 0a 20 20 70 49 74 65 72 2d 3e 69 52 65 61 64 ;. pIter->iRead
2930: 4f 66 66 20 3d 20 69 53 74 61 72 74 3b 0a 20 20 Off = iStart;.
2940: 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 pIter->nAlloc =
2950: 31 32 38 3b 0a 20 20 70 49 74 65 72 2d 3e 61 41 128;. pIter->aA
2960: 6c 6c 6f 63 20 3d 20 28 75 38 20 2a 29 73 71 6c lloc = (u8 *)sql
2970: 69 74 65 33 44 62 4d 61 6c 6c 6f 63 52 61 77 28 ite3DbMallocRaw(
2980: 64 62 2c 20 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f db, pIter->nAllo
2990: 63 29 3b 0a 20 20 69 66 28 20 21 70 49 74 65 72 c);. if( !pIter
29a0: 2d 3e 61 41 6c 6c 6f 63 20 29 7b 0a 20 20 20 20 ->aAlloc ){.
29b0: 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 rc = SQLITE_NOME
29c0: 4d 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 M;. }else{.
29d0: 69 36 34 20 6e 42 79 74 65 3b 20 20 20 20 20 20 i64 nByte;
29e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
29f0: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65 /* Total size
2a00: 20 6f 66 20 50 4d 41 20 69 6e 20 62 79 74 65 73 of PMA in bytes
2a10: 20 2a 2f 0a 20 20 20 20 72 63 20 3d 20 76 64 62 */. rc = vdb
2a20: 65 53 6f 72 74 65 72 52 65 61 64 56 61 72 69 6e eSorterReadVarin
2a30: 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 t(pSorter->pTemp
2a40: 31 2c 20 26 70 49 74 65 72 2d 3e 69 52 65 61 64 1, &pIter->iRead
2a50: 4f 66 66 2c 20 26 6e 42 79 74 65 29 3b 0a 20 20 Off, &nByte);.
2a60: 20 20 2a 70 6e 42 79 74 65 20 2b 3d 20 6e 42 79 *pnByte += nBy
2a70: 74 65 3b 0a 20 20 20 20 70 49 74 65 72 2d 3e 69 te;. pIter->i
2a80: 45 6f 66 20 3d 20 70 49 74 65 72 2d 3e 69 52 65 Eof = pIter->iRe
2a90: 61 64 4f 66 66 20 2b 20 6e 42 79 74 65 3b 0a 20 adOff + nByte;.
2aa0: 20 7d 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c }. if( rc==SQL
2ab0: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 72 63 ITE_OK ){. rc
2ac0: 20 3d 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 = vdbeSorterIte
2ad0: 72 4e 65 78 74 28 64 62 2c 20 70 49 74 65 72 29 rNext(db, pIter)
2ae0: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 ;. }. return r
2af0: 63 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d c;.}.../*.** Com
2b00: 70 61 72 65 20 6b 65 79 31 20 28 62 75 66 66 65 pare key1 (buffe
2b10: 72 20 70 4b 65 79 31 2c 20 73 69 7a 65 20 6e 4b r pKey1, size nK
2b20: 65 79 31 20 62 79 74 65 73 29 20 77 69 74 68 20 ey1 bytes) with
2b30: 6b 65 79 32 20 28 62 75 66 66 65 72 20 70 4b 65 key2 (buffer pKe
2b40: 79 32 2c 20 0a 2a 2a 20 73 69 7a 65 20 6e 4b 65 y2, .** size nKe
2b50: 79 32 20 62 79 74 65 73 29 2e 20 20 41 72 67 75 y2 bytes). Argu
2b60: 6d 65 6e 74 20 70 4b 65 79 49 6e 66 6f 20 73 75 ment pKeyInfo su
2b70: 70 70 6c 69 65 73 20 74 68 65 20 63 6f 6c 6c 61 pplies the colla
2b80: 74 69 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 0a 2a tion functions.*
2b90: 2a 20 75 73 65 64 20 62 79 20 74 68 65 20 63 6f * used by the co
2ba0: 6d 70 61 72 69 73 6f 6e 2e 20 49 66 20 61 6e 20 mparison. If an
2bb0: 65 72 72 6f 72 20 6f 63 63 75 72 73 2c 20 72 65 error occurs, re
2bc0: 74 75 72 6e 20 61 6e 20 53 51 4c 69 74 65 20 65 turn an SQLite e
2bd0: 72 72 6f 72 20 63 6f 64 65 2e 0a 2a 2a 20 4f 74 rror code..** Ot
2be0: 68 65 72 77 69 73 65 2c 20 72 65 74 75 72 6e 20 herwise, return
2bf0: 53 51 4c 49 54 45 5f 4f 4b 20 61 6e 64 20 73 65 SQLITE_OK and se
2c00: 74 20 2a 70 52 65 73 20 74 6f 20 61 20 6e 65 67 t *pRes to a neg
2c10: 61 74 69 76 65 2c 20 7a 65 72 6f 20 6f 72 20 70 ative, zero or p
2c20: 6f 73 69 74 69 76 65 0a 2a 2a 20 76 61 6c 75 65 ositive.** value
2c30: 2c 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 77 , depending on w
2c40: 68 65 74 68 65 72 20 6b 65 79 31 20 69 73 20 73 hether key1 is s
2c50: 6d 61 6c 6c 65 72 2c 20 65 71 75 61 6c 20 74 6f maller, equal to
2c60: 20 6f 72 20 6c 61 72 67 65 72 20 74 68 61 6e 20 or larger than
2c70: 6b 65 79 32 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 key2..**.** If t
2c80: 68 65 20 62 4f 6d 69 74 52 6f 77 69 64 20 61 72 he bOmitRowid ar
2c90: 67 75 6d 65 6e 74 20 69 73 20 6e 6f 6e 2d 7a 65 gument is non-ze
2ca0: 72 6f 2c 20 61 73 73 75 6d 65 20 62 6f 74 68 20 ro, assume both
2cb0: 6b 65 79 73 20 65 6e 64 20 69 6e 20 61 20 72 6f keys end in a ro
2cc0: 77 69 64 0a 2a 2a 20 66 69 65 6c 64 2e 20 46 6f wid.** field. Fo
2cd0: 72 20 74 68 65 20 70 75 72 70 6f 73 65 73 20 6f r the purposes o
2ce0: 66 20 74 68 65 20 63 6f 6d 70 61 72 69 73 6f 6e f the comparison
2cf0: 2c 20 69 67 6e 6f 72 65 20 69 74 2e 20 41 6c 73 , ignore it. Als
2d00: 6f 2c 20 69 66 20 62 4f 6d 69 74 52 6f 77 69 64 o, if bOmitRowid
2d10: 0a 2a 2a 20 69 73 20 74 72 75 65 20 61 6e 64 20 .** is true and
2d20: 6b 65 79 31 20 63 6f 6e 74 61 69 6e 73 20 65 76 key1 contains ev
2d30: 65 6e 20 61 20 73 69 6e 67 6c 65 20 4e 55 4c 4c en a single NULL
2d40: 20 76 61 6c 75 65 2c 20 69 74 20 69 73 20 63 6f value, it is co
2d50: 6e 73 69 64 65 72 65 64 20 74 6f 0a 2a 2a 20 62 nsidered to.** b
2d60: 65 20 6c 65 73 73 20 74 68 61 6e 20 6b 65 79 32 e less than key2
2d70: 2e 20 45 76 65 6e 20 69 66 20 6b 65 79 32 20 61 . Even if key2 a
2d80: 6c 73 6f 20 63 6f 6e 74 61 69 6e 73 20 4e 55 4c lso contains NUL
2d90: 4c 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 L values..**.**
2da0: 49 66 20 70 4b 65 79 32 20 69 73 20 70 61 73 73 If pKey2 is pass
2db0: 65 64 20 61 20 4e 55 4c 4c 20 70 6f 69 6e 74 65 ed a NULL pointe
2dc0: 72 2c 20 74 68 65 6e 20 69 74 20 69 73 20 61 73 r, then it is as
2dd0: 73 75 6d 65 64 20 74 68 61 74 20 74 68 65 20 70 sumed that the p
2de0: 43 73 72 2d 3e 61 53 70 61 63 65 0a 2a 2a 20 68 Csr->aSpace.** h
2df0: 61 73 20 62 65 65 6e 20 61 6c 6c 6f 63 61 74 65 as been allocate
2e00: 64 20 61 6e 64 20 63 6f 6e 74 61 69 6e 73 20 61 d and contains a
2e10: 6e 20 75 6e 70 61 63 6b 65 64 20 72 65 63 6f 72 n unpacked recor
2e20: 64 20 74 68 61 74 20 69 73 20 75 73 65 64 20 61 d that is used a
2e30: 73 20 6b 65 79 32 2e 0a 2a 2f 0a 73 74 61 74 69 s key2..*/.stati
2e40: 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 c int vdbeSorter
2e50: 43 6f 6d 70 61 72 65 28 0a 20 20 56 64 62 65 43 Compare(. VdbeC
2e60: 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 20 20 20 ursor *pCsr,
2e70: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 /* Cu
2e80: 72 73 6f 72 20 6f 62 6a 65 63 74 20 28 66 6f 72 rsor object (for
2e90: 20 70 4b 65 79 49 6e 66 6f 29 20 2a 2f 0a 20 20 pKeyInfo) */.
2ea0: 69 6e 74 20 62 4f 6d 69 74 52 6f 77 69 64 2c 20 int bOmitRowid,
2eb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2ec0: 2f 2a 20 49 67 6e 6f 72 65 20 72 6f 77 69 64 20 /* Ignore rowid
2ed0: 66 69 65 6c 64 20 61 74 20 65 6e 64 20 6f 66 20 field at end of
2ee0: 6b 65 79 73 20 2a 2f 0a 20 20 76 6f 69 64 20 2a keys */. void *
2ef0: 70 4b 65 79 31 2c 20 69 6e 74 20 6e 4b 65 79 31 pKey1, int nKey1
2f00: 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 65 66 , /* Lef
2f10: 74 20 73 69 64 65 20 6f 66 20 63 6f 6d 70 61 72 t side of compar
2f20: 69 73 6f 6e 20 2a 2f 0a 20 20 76 6f 69 64 20 2a ison */. void *
2f30: 70 4b 65 79 32 2c 20 69 6e 74 20 6e 4b 65 79 32 pKey2, int nKey2
2f40: 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 52 69 67 , /* Rig
2f50: 68 74 20 73 69 64 65 20 6f 66 20 63 6f 6d 70 61 ht side of compa
2f60: 72 69 73 6f 6e 20 2a 2f 0a 20 20 69 6e 74 20 2a rison */. int *
2f70: 70 52 65 73 20 20 20 20 20 20 20 20 20 20 20 20 pRes
2f80: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 /* OU
2f90: 54 3a 20 52 65 73 75 6c 74 20 6f 66 20 63 6f 6d T: Result of com
2fa0: 70 61 72 69 73 6f 6e 20 2a 2f 0a 29 7b 0a 20 20 parison */.){.
2fb0: 4b 65 79 49 6e 66 6f 20 2a 70 4b 65 79 49 6e 66 KeyInfo *pKeyInf
2fc0: 6f 20 3d 20 70 43 73 72 2d 3e 70 4b 65 79 49 6e o = pCsr->pKeyIn
2fd0: 66 6f 3b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 fo;. VdbeSorter
2fe0: 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73 72 *pSorter = pCsr
2ff0: 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 55 6e 70 ->pSorter;. Unp
3000: 61 63 6b 65 64 52 65 63 6f 72 64 20 2a 72 32 20 ackedRecord *r2
3010: 3d 20 70 53 6f 72 74 65 72 2d 3e 70 55 6e 70 61 = pSorter->pUnpa
3020: 63 6b 65 64 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a cked;. int i;..
3030: 20 20 69 66 28 20 72 32 3d 3d 30 20 29 7b 0a 20 if( r2==0 ){.
3040: 20 20 20 63 68 61 72 20 2a 70 46 72 65 65 3b 0a char *pFree;.
3050: 20 20 20 20 72 32 20 3d 20 73 71 6c 69 74 65 33 r2 = sqlite3
3060: 56 64 62 65 41 6c 6c 6f 63 55 6e 70 61 63 6b 65 VdbeAllocUnpacke
3070: 64 52 65 63 6f 72 64 28 70 4b 65 79 49 6e 66 6f dRecord(pKeyInfo
3080: 2c 20 30 2c 20 30 2c 20 26 70 46 72 65 65 29 3b , 0, 0, &pFree);
3090: 0a 20 20 20 20 69 66 28 20 72 32 3d 3d 30 20 29 . if( r2==0 )
30a0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e return SQLITE_N
30b0: 4f 4d 45 4d 3b 0a 20 20 20 20 61 73 73 65 72 74 OMEM;. assert
30c0: 28 20 70 46 72 65 65 3d 3d 28 63 68 61 72 20 2a ( pFree==(char *
30d0: 29 72 32 20 29 3b 0a 20 20 20 20 70 53 6f 72 74 )r2 );. pSort
30e0: 65 72 2d 3e 70 55 6e 70 61 63 6b 65 64 20 3d 20 er->pUnpacked =
30f0: 72 32 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 70 r2;. }.. if( p
3100: 4b 65 79 32 20 29 7b 0a 20 20 20 20 73 71 6c 69 Key2 ){. sqli
3110: 74 65 33 56 64 62 65 52 65 63 6f 72 64 55 6e 70 te3VdbeRecordUnp
3120: 61 63 6b 28 70 4b 65 79 49 6e 66 6f 2c 20 6e 4b ack(pKeyInfo, nK
3130: 65 79 32 2c 20 70 4b 65 79 32 2c 20 72 32 29 3b ey2, pKey2, r2);
3140: 0a 20 20 7d 0a 0a 20 20 69 66 28 20 62 4f 6d 69 . }.. if( bOmi
3150: 74 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 66 6f tRowid ){. fo
3160: 72 28 69 3d 30 3b 20 69 3c 72 32 2d 3e 6e 46 69 r(i=0; i<r2->nFi
3170: 65 6c 64 2d 31 3b 20 69 2b 2b 29 7b 0a 20 20 20 eld-1; i++){.
3180: 20 20 20 69 66 28 20 72 32 2d 3e 61 4d 65 6d 5b if( r2->aMem[
3190: 69 5d 2e 66 6c 61 67 73 20 26 20 4d 45 4d 5f 4e i].flags & MEM_N
31a0: 75 6c 6c 20 29 7b 0a 20 20 20 20 20 20 20 20 2a ull ){. *
31b0: 70 52 65 73 20 3d 20 2d 31 3b 0a 20 20 20 20 20 pRes = -1;.
31c0: 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 return SQLITE
31d0: 5f 4f 4b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 _OK;. }.
31e0: 20 7d 0a 20 20 20 20 72 32 2d 3e 66 6c 61 67 73 }. r2->flags
31f0: 20 7c 3d 20 55 4e 50 41 43 4b 45 44 5f 50 52 45 |= UNPACKED_PRE
3200: 46 49 58 5f 4d 41 54 43 48 3b 0a 20 20 20 20 72 FIX_MATCH;. r
3210: 32 2d 3e 6e 46 69 65 6c 64 2d 2d 3b 0a 20 20 20 2->nField--;.
3220: 20 61 73 73 65 72 74 28 20 72 32 2d 3e 6e 46 69 assert( r2->nFi
3230: 65 6c 64 3e 30 20 29 3b 0a 20 20 7d 0a 0a 20 20 eld>0 );. }..
3240: 2a 70 52 65 73 20 3d 20 73 71 6c 69 74 65 33 56 *pRes = sqlite3V
3250: 64 62 65 52 65 63 6f 72 64 43 6f 6d 70 61 72 65 dbeRecordCompare
3260: 28 6e 4b 65 79 31 2c 20 70 4b 65 79 31 2c 20 72 (nKey1, pKey1, r
3270: 32 29 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 2);. return SQL
3280: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a ITE_OK;.}../*.**
3290: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 This function i
32a0: 73 20 63 61 6c 6c 65 64 20 74 6f 20 63 6f 6d 70 s called to comp
32b0: 61 72 65 20 74 77 6f 20 69 74 65 72 61 74 6f 72 are two iterator
32c0: 20 6b 65 79 73 20 77 68 65 6e 20 6d 65 72 67 69 keys when mergi
32d0: 6e 67 20 0a 2a 2a 20 6d 75 6c 74 69 70 6c 65 20 ng .** multiple
32e0: 62 2d 74 72 65 65 20 73 65 67 6d 65 6e 74 73 2e b-tree segments.
32f0: 20 50 61 72 61 6d 65 74 65 72 20 69 4f 75 74 20 Parameter iOut
3300: 69 73 20 74 68 65 20 69 6e 64 65 78 20 6f 66 20 is the index of
3310: 74 68 65 20 61 54 72 65 65 5b 5d 20 0a 2a 2a 20 the aTree[] .**
3320: 76 61 6c 75 65 20 74 6f 20 72 65 63 61 6c 63 75 value to recalcu
3330: 6c 61 74 65 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 late..*/.static
3340: 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 44 6f int vdbeSorterDo
3350: 43 6f 6d 70 61 72 65 28 56 64 62 65 43 75 72 73 Compare(VdbeCurs
3360: 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 69 4f or *pCsr, int iO
3370: 75 74 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65 ut){. VdbeSorte
3380: 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73 r *pSorter = pCs
3390: 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 6e r->pSorter;. in
33a0: 74 20 69 31 3b 0a 20 20 69 6e 74 20 69 32 3b 0a t i1;. int i2;.
33b0: 20 20 69 6e 74 20 69 52 65 73 3b 0a 20 20 56 64 int iRes;. Vd
33c0: 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a 70 31 beSorterIter *p1
33d0: 3b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 ;. VdbeSorterIt
33e0: 65 72 20 2a 70 32 3b 0a 0a 20 20 61 73 73 65 72 er *p2;.. asser
33f0: 74 28 20 69 4f 75 74 3c 70 53 6f 72 74 65 72 2d t( iOut<pSorter-
3400: 3e 6e 54 72 65 65 20 26 26 20 69 4f 75 74 3e 30 >nTree && iOut>0
3410: 20 29 3b 0a 0a 20 20 69 66 28 20 69 4f 75 74 3e );.. if( iOut>
3420: 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65 =(pSorter->nTree
3430: 2f 32 29 20 29 7b 0a 20 20 20 20 69 31 20 3d 20 /2) ){. i1 =
3440: 28 69 4f 75 74 20 2d 20 70 53 6f 72 74 65 72 2d (iOut - pSorter-
3450: 3e 6e 54 72 65 65 2f 32 29 20 2a 20 32 3b 0a 20 >nTree/2) * 2;.
3460: 20 20 20 69 32 20 3d 20 69 31 20 2b 20 31 3b 0a i2 = i1 + 1;.
3470: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 31 20 }else{. i1
3480: 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 = pSorter->aTree
3490: 5b 69 4f 75 74 2a 32 5d 3b 0a 20 20 20 20 69 32 [iOut*2];. i2
34a0: 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 = pSorter->aTre
34b0: 65 5b 69 4f 75 74 2a 32 2b 31 5d 3b 0a 20 20 7d e[iOut*2+1];. }
34c0: 0a 0a 20 20 70 31 20 3d 20 26 70 53 6f 72 74 65 .. p1 = &pSorte
34d0: 72 2d 3e 61 49 74 65 72 5b 69 31 5d 3b 0a 20 20 r->aIter[i1];.
34e0: 70 32 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 p2 = &pSorter->a
34f0: 49 74 65 72 5b 69 32 5d 3b 0a 0a 20 20 69 66 28 Iter[i2];.. if(
3500: 20 70 31 2d 3e 70 46 69 6c 65 3d 3d 30 20 29 7b p1->pFile==0 ){
3510: 0a 20 20 20 20 69 52 65 73 20 3d 20 69 32 3b 0a . iRes = i2;.
3520: 20 20 7d 65 6c 73 65 20 69 66 28 20 70 32 2d 3e }else if( p2->
3530: 70 46 69 6c 65 3d 3d 30 20 29 7b 0a 20 20 20 20 pFile==0 ){.
3540: 69 52 65 73 20 3d 20 69 31 3b 0a 20 20 7d 65 6c iRes = i1;. }el
3550: 73 65 7b 0a 20 20 20 20 69 6e 74 20 72 65 73 3b se{. int res;
3560: 0a 20 20 20 20 69 6e 74 20 72 63 3b 0a 20 20 20 . int rc;.
3570: 20 61 73 73 65 72 74 28 20 70 43 73 72 2d 3e 70 assert( pCsr->p
3580: 53 6f 72 74 65 72 2d 3e 70 55 6e 70 61 63 6b 65 Sorter->pUnpacke
3590: 64 21 3d 30 20 29 3b 20 20 2f 2a 20 61 6c 6c 6f d!=0 ); /* allo
35a0: 63 61 74 65 64 20 69 6e 20 76 64 62 65 53 6f 72 cated in vdbeSor
35b0: 74 65 72 4d 65 72 67 65 28 29 20 2a 2f 0a 20 20 terMerge() */.
35c0: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 rc = vdbeSorte
35d0: 72 43 6f 6d 70 61 72 65 28 0a 20 20 20 20 20 20 rCompare(.
35e0: 20 20 70 43 73 72 2c 20 30 2c 20 70 31 2d 3e 61 pCsr, 0, p1->a
35f0: 4b 65 79 2c 20 70 31 2d 3e 6e 4b 65 79 2c 20 70 Key, p1->nKey, p
3600: 32 2d 3e 61 4b 65 79 2c 20 70 32 2d 3e 6e 4b 65 2->aKey, p2->nKe
3610: 79 2c 20 26 72 65 73 0a 20 20 20 20 29 3b 0a 20 y, &res. );.
3620: 20 20 20 2f 2a 20 54 68 65 20 76 64 62 65 53 6f /* The vdbeSo
3630: 72 74 65 72 43 6f 6d 70 61 72 65 28 29 20 63 61 rterCompare() ca
3640: 6c 6c 20 63 61 6e 6e 6f 74 20 66 61 69 6c 20 73 ll cannot fail s
3650: 69 6e 63 65 20 70 43 73 72 2d 3e 70 53 6f 72 74 ince pCsr->pSort
3660: 65 72 2d 3e 70 55 6e 70 61 63 6b 65 64 0a 20 20 er->pUnpacked.
3670: 20 20 2a 2a 20 68 61 73 20 61 6c 72 65 61 64 79 ** has already
3680: 20 62 65 65 6e 20 61 6c 6c 6f 63 61 74 65 64 2e been allocated.
3690: 20 2a 2f 0a 20 20 20 20 61 73 73 65 72 74 28 20 */. assert(
36a0: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 3b rc==SQLITE_OK );
36b0: 0a 0a 20 20 20 20 69 66 28 20 72 65 73 3c 3d 30 .. if( res<=0
36c0: 20 29 7b 0a 20 20 20 20 20 20 69 52 65 73 20 3d ){. iRes =
36d0: 20 69 31 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a i1;. }else{.
36e0: 20 20 20 20 20 20 69 52 65 73 20 3d 20 69 32 3b iRes = i2;
36f0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 53 . }. }.. pS
3700: 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 69 4f 75 orter->aTree[iOu
3710: 74 5d 20 3d 20 69 52 65 73 3b 0a 20 20 72 65 74 t] = iRes;. ret
3720: 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d urn SQLITE_OK;.}
3730: 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61 6c 69 ../*.** Initiali
3740: 7a 65 20 74 68 65 20 74 65 6d 70 6f 72 61 72 79 ze the temporary
3750: 20 69 6e 64 65 78 20 63 75 72 73 6f 72 20 6a 75 index cursor ju
3760: 73 74 20 6f 70 65 6e 65 64 20 61 73 20 61 20 73 st opened as a s
3770: 6f 72 74 65 72 20 63 75 72 73 6f 72 2e 0a 2a 2f orter cursor..*/
3780: 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65 .int sqlite3Vdbe
3790: 53 6f 72 74 65 72 49 6e 69 74 28 73 71 6c 69 74 SorterInit(sqlit
37a0: 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73 e3 *db, VdbeCurs
37b0: 6f 72 20 2a 70 43 73 72 29 7b 0a 20 20 69 6e 74 or *pCsr){. int
37c0: 20 70 67 73 7a 3b 20 20 20 20 20 20 20 20 20 20 pgsz;
37d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
37e0: 50 61 67 65 20 73 69 7a 65 20 6f 66 20 6d 61 69 Page size of mai
37f0: 6e 20 64 61 74 61 62 61 73 65 20 2a 2f 0a 20 20 n database */.
3800: 69 6e 74 20 6d 78 43 61 63 68 65 3b 20 20 20 20 int mxCache;
3810: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
3820: 2f 2a 20 43 61 63 68 65 20 73 69 7a 65 20 2a 2f /* Cache size */
3830: 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 . VdbeSorter *p
3840: 53 6f 72 74 65 72 3b 20 20 20 20 20 20 20 20 20 Sorter;
3850: 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 73 6f /* The new so
3860: 72 74 65 72 20 2a 2f 0a 0a 20 20 61 73 73 65 72 rter */.. asser
3870: 74 28 20 70 43 73 72 2d 3e 70 4b 65 79 49 6e 66 t( pCsr->pKeyInf
3880: 6f 20 26 26 20 70 43 73 72 2d 3e 70 42 74 3d 3d o && pCsr->pBt==
3890: 30 20 29 3b 0a 20 20 70 43 73 72 2d 3e 70 53 6f 0 );. pCsr->pSo
38a0: 72 74 65 72 20 3d 20 70 53 6f 72 74 65 72 20 3d rter = pSorter =
38b0: 20 73 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 sqlite3DbMalloc
38c0: 5a 65 72 6f 28 64 62 2c 20 73 69 7a 65 6f 66 28 Zero(db, sizeof(
38d0: 56 64 62 65 53 6f 72 74 65 72 29 29 3b 0a 20 20 VdbeSorter));.
38e0: 69 66 28 20 70 53 6f 72 74 65 72 3d 3d 30 20 29 if( pSorter==0 )
38f0: 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c {. return SQL
3900: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 0a 0a ITE_NOMEM;. }..
3910: 20 20 69 66 28 20 21 73 71 6c 69 74 65 33 54 65 if( !sqlite3Te
3920: 6d 70 49 6e 4d 65 6d 6f 72 79 28 64 62 29 20 29 mpInMemory(db) )
3930: 7b 0a 20 20 20 20 70 67 73 7a 20 3d 20 73 71 6c {. pgsz = sql
3940: 69 74 65 33 42 74 72 65 65 47 65 74 50 61 67 65 ite3BtreeGetPage
3950: 53 69 7a 65 28 64 62 2d 3e 61 44 62 5b 30 5d 2e Size(db->aDb[0].
3960: 70 42 74 29 3b 0a 20 20 20 20 70 53 6f 72 74 65 pBt);. pSorte
3970: 72 2d 3e 6d 6e 50 6d 61 53 69 7a 65 20 3d 20 53 r->mnPmaSize = S
3980: 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b 49 4e ORTER_MIN_WORKIN
3990: 47 20 2a 20 70 67 73 7a 3b 0a 20 20 20 20 6d 78 G * pgsz;. mx
39a0: 43 61 63 68 65 20 3d 20 64 62 2d 3e 61 44 62 5b Cache = db->aDb[
39b0: 30 5d 2e 70 53 63 68 65 6d 61 2d 3e 63 61 63 68 0].pSchema->cach
39c0: 65 5f 73 69 7a 65 3b 0a 20 20 20 20 69 66 28 20 e_size;. if(
39d0: 6d 78 43 61 63 68 65 3c 53 4f 52 54 45 52 5f 4d mxCache<SORTER_M
39e0: 49 4e 5f 57 4f 52 4b 49 4e 47 20 29 20 6d 78 43 IN_WORKING ) mxC
39f0: 61 63 68 65 20 3d 20 53 4f 52 54 45 52 5f 4d 49 ache = SORTER_MI
3a00: 4e 5f 57 4f 52 4b 49 4e 47 3b 0a 20 20 20 20 70 N_WORKING;. p
3a10: 53 6f 72 74 65 72 2d 3e 6d 78 50 6d 61 53 69 7a Sorter->mxPmaSiz
3a20: 65 20 3d 20 6d 78 43 61 63 68 65 20 2a 20 70 67 e = mxCache * pg
3a30: 73 7a 3b 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 sz;. }.. retur
3a40: 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a n SQLITE_OK;.}..
3a50: 2f 2a 0a 2a 2a 20 46 72 65 65 20 74 68 65 20 6c /*.** Free the l
3a60: 69 73 74 20 6f 66 20 73 6f 72 74 65 64 20 72 65 ist of sorted re
3a70: 63 6f 72 64 73 20 73 74 61 72 74 69 6e 67 20 61 cords starting a
3a80: 74 20 70 52 65 63 6f 72 64 2e 0a 2a 2f 0a 73 74 t pRecord..*/.st
3a90: 61 74 69 63 20 76 6f 69 64 20 76 64 62 65 53 6f atic void vdbeSo
3aa0: 72 74 65 72 52 65 63 6f 72 64 46 72 65 65 28 73 rterRecordFree(s
3ab0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 53 6f 72 74 qlite3 *db, Sort
3ac0: 65 72 52 65 63 6f 72 64 20 2a 70 52 65 63 6f 72 erRecord *pRecor
3ad0: 64 29 7b 0a 20 20 53 6f 72 74 65 72 52 65 63 6f d){. SorterReco
3ae0: 72 64 20 2a 70 3b 0a 20 20 53 6f 72 74 65 72 52 rd *p;. SorterR
3af0: 65 63 6f 72 64 20 2a 70 4e 65 78 74 3b 0a 20 20 ecord *pNext;.
3b00: 66 6f 72 28 70 3d 70 52 65 63 6f 72 64 3b 20 70 for(p=pRecord; p
3b10: 3b 20 70 3d 70 4e 65 78 74 29 7b 0a 20 20 20 20 ; p=pNext){.
3b20: 70 4e 65 78 74 20 3d 20 70 2d 3e 70 4e 65 78 74 pNext = p->pNext
3b30: 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 ;. sqlite3DbF
3b40: 72 65 65 28 64 62 2c 20 70 29 3b 0a 20 20 7d 0a ree(db, p);. }.
3b50: 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 65 20 61 6e }../*.** Free an
3b60: 79 20 63 75 72 73 6f 72 20 63 6f 6d 70 6f 6e 65 y cursor compone
3b70: 6e 74 73 20 61 6c 6c 6f 63 61 74 65 64 20 62 79 nts allocated by
3b80: 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 sqlite3VdbeSort
3b90: 65 72 58 58 58 20 72 6f 75 74 69 6e 65 73 2e 0a erXXX routines..
3ba0: 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 56 */.void sqlite3V
3bb0: 64 62 65 53 6f 72 74 65 72 43 6c 6f 73 65 28 73 dbeSorterClose(s
3bc0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 qlite3 *db, Vdbe
3bd0: 43 75 72 73 6f 72 20 2a 70 43 73 72 29 7b 0a 20 Cursor *pCsr){.
3be0: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f VdbeSorter *pSo
3bf0: 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f rter = pCsr->pSo
3c00: 72 74 65 72 3b 0a 20 20 69 66 28 20 70 53 6f 72 rter;. if( pSor
3c10: 74 65 72 20 29 7b 0a 20 20 20 20 69 66 28 20 70 ter ){. if( p
3c20: 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 20 29 7b Sorter->aIter ){
3c30: 0a 20 20 20 20 20 20 69 6e 74 20 69 3b 0a 20 20 . int i;.
3c40: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 for(i=0; i<p
3c50: 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65 3b 20 69 Sorter->nTree; i
3c60: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 76 64 62 ++){. vdb
3c70: 65 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 eSorterIterZero(
3c80: 64 62 2c 20 26 70 53 6f 72 74 65 72 2d 3e 61 49 db, &pSorter->aI
3c90: 74 65 72 5b 69 5d 29 3b 0a 20 20 20 20 20 20 7d ter[i]);. }
3ca0: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 44 62 . sqlite3Db
3cb0: 46 72 65 65 28 64 62 2c 20 70 53 6f 72 74 65 72 Free(db, pSorter
3cc0: 2d 3e 61 49 74 65 72 29 3b 0a 20 20 20 20 7d 0a ->aIter);. }.
3cd0: 20 20 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d if( pSorter-
3ce0: 3e 70 54 65 6d 70 31 20 29 7b 0a 20 20 20 20 20 >pTemp1 ){.
3cf0: 20 73 71 6c 69 74 65 33 4f 73 43 6c 6f 73 65 46 sqlite3OsCloseF
3d00: 72 65 65 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 ree(pSorter->pTe
3d10: 6d 70 31 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 mp1);. }.
3d20: 76 64 62 65 53 6f 72 74 65 72 52 65 63 6f 72 64 vdbeSorterRecord
3d30: 46 72 65 65 28 64 62 2c 20 70 53 6f 72 74 65 72 Free(db, pSorter
3d40: 2d 3e 70 52 65 63 6f 72 64 29 3b 0a 20 20 20 20 ->pRecord);.
3d50: 73 71 6c 69 74 65 33 44 62 46 72 65 65 28 64 62 sqlite3DbFree(db
3d60: 2c 20 70 53 6f 72 74 65 72 2d 3e 70 55 6e 70 61 , pSorter->pUnpa
3d70: 63 6b 65 64 29 3b 0a 20 20 20 20 73 71 6c 69 74 cked);. sqlit
3d80: 65 33 44 62 46 72 65 65 28 64 62 2c 20 70 53 6f e3DbFree(db, pSo
3d90: 72 74 65 72 29 3b 0a 20 20 20 20 70 43 73 72 2d rter);. pCsr-
3da0: 3e 70 53 6f 72 74 65 72 20 3d 20 30 3b 0a 20 20 >pSorter = 0;.
3db0: 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 }.}../*.** Alloc
3dc0: 61 74 65 20 73 70 61 63 65 20 66 6f 72 20 61 20 ate space for a
3dd0: 66 69 6c 65 2d 68 61 6e 64 6c 65 20 61 6e 64 20 file-handle and
3de0: 6f 70 65 6e 20 61 20 74 65 6d 70 6f 72 61 72 79 open a temporary
3df0: 20 66 69 6c 65 2e 20 49 66 20 73 75 63 63 65 73 file. If succes
3e00: 73 66 75 6c 2c 0a 2a 2a 20 73 65 74 20 2a 70 70 sful,.** set *pp
3e10: 46 69 6c 65 20 74 6f 20 70 6f 69 6e 74 20 74 6f File to point to
3e20: 20 74 68 65 20 6d 61 6c 6c 6f 63 27 64 20 66 69 the malloc'd fi
3e30: 6c 65 2d 68 61 6e 64 6c 65 20 61 6e 64 20 72 65 le-handle and re
3e40: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 2e 0a turn SQLITE_OK..
3e50: 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 73 65 ** Otherwise, se
3e60: 74 20 2a 70 70 46 69 6c 65 20 74 6f 20 30 20 61 t *ppFile to 0 a
3e70: 6e 64 20 72 65 74 75 72 6e 20 61 6e 20 53 51 4c nd return an SQL
3e80: 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 2e 0a ite error code..
3e90: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 64 */.static int vd
3ea0: 62 65 53 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70 beSorterOpenTemp
3eb0: 46 69 6c 65 28 73 71 6c 69 74 65 33 20 2a 64 62 File(sqlite3 *db
3ec0: 2c 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a , sqlite3_file *
3ed0: 2a 70 70 46 69 6c 65 29 7b 0a 20 20 69 6e 74 20 *ppFile){. int
3ee0: 64 75 6d 6d 79 3b 0a 20 20 72 65 74 75 72 6e 20 dummy;. return
3ef0: 73 71 6c 69 74 65 33 4f 73 4f 70 65 6e 4d 61 6c sqlite3OsOpenMal
3f00: 6c 6f 63 28 64 62 2d 3e 70 56 66 73 2c 20 30 2c loc(db->pVfs, 0,
3f10: 20 70 70 46 69 6c 65 2c 0a 20 20 20 20 20 20 53 ppFile,. S
3f20: 51 4c 49 54 45 5f 4f 50 45 4e 5f 54 45 4d 50 5f QLITE_OPEN_TEMP_
3f30: 4a 4f 55 52 4e 41 4c 20 7c 0a 20 20 20 20 20 20 JOURNAL |.
3f40: 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 52 45 41 44 SQLITE_OPEN_READ
3f50: 57 52 49 54 45 20 20 20 20 7c 20 53 51 4c 49 54 WRITE | SQLIT
3f60: 45 5f 4f 50 45 4e 5f 43 52 45 41 54 45 20 7c 0a E_OPEN_CREATE |.
3f70: 20 20 20 20 20 20 53 51 4c 49 54 45 5f 4f 50 45 SQLITE_OPE
3f80: 4e 5f 45 58 43 4c 55 53 49 56 45 20 20 20 20 7c N_EXCLUSIVE |
3f90: 20 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 44 45 4c SQLITE_OPEN_DEL
3fa0: 45 54 45 4f 4e 43 4c 4f 53 45 2c 20 26 64 75 6d ETEONCLOSE, &dum
3fb0: 6d 79 0a 20 20 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a my. );.}../*.**
3fc0: 20 41 74 74 65 6d 70 20 74 6f 20 6d 65 72 67 65 Attemp to merge
3fd0: 20 74 68 65 20 74 77 6f 20 73 6f 72 74 65 64 20 the two sorted
3fe0: 6c 69 73 74 73 20 70 31 20 61 6e 64 20 70 32 20 lists p1 and p2
3ff0: 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65 20 6c 69 into a single li
4000: 73 74 2e 20 49 66 20 6e 6f 0a 2a 2a 20 65 72 72 st. If no.** err
4010: 6f 72 20 6f 63 63 75 72 73 20 73 65 74 20 2a 70 or occurs set *p
4020: 70 4f 75 74 20 74 6f 20 74 68 65 20 68 65 61 64 pOut to the head
4030: 20 6f 66 20 74 68 65 20 6e 65 77 20 6c 69 73 74 of the new list
4040: 20 61 6e 64 20 72 65 74 75 72 6e 20 53 51 4c 49 and return SQLI
4050: 54 45 5f 4f 4b 2e 0a 2a 2f 0a 73 74 61 74 69 63 TE_OK..*/.static
4060: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 4d int vdbeSorterM
4070: 65 72 67 65 28 0a 20 20 73 71 6c 69 74 65 33 20 erge(. sqlite3
4080: 2a 64 62 2c 20 20 20 20 20 20 20 20 20 20 20 20 *db,
4090: 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62 /* Datab
40a0: 61 73 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 ase handle */.
40b0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 VdbeCursor *pCsr
40c0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,
40d0: 2f 2a 20 46 6f 72 20 70 4b 65 79 49 6e 66 6f 20 /* For pKeyInfo
40e0: 2a 2f 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 */. SorterRecor
40f0: 64 20 2a 70 31 2c 20 20 20 20 20 20 20 20 20 20 d *p1,
4100: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 6c 69 /* First li
4110: 73 74 20 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20 st to merge */.
4120: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70 SorterRecord *p
4130: 32 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2,
4140: 20 2f 2a 20 53 65 63 6f 6e 64 20 6c 69 73 74 20 /* Second list
4150: 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20 20 53 6f to merge */. So
4160: 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 70 70 4f rterRecord **ppO
4170: 75 74 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a ut /*
4180: 20 4f 55 54 3a 20 48 65 61 64 20 6f 66 20 6d 65 OUT: Head of me
4190: 72 67 65 64 20 6c 69 73 74 20 2a 2f 0a 29 7b 0a rged list */.){.
41a0: 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 int rc = SQLIT
41b0: 45 5f 4f 4b 3b 0a 20 20 53 6f 72 74 65 72 52 65 E_OK;. SorterRe
41c0: 63 6f 72 64 20 2a 70 46 69 6e 61 6c 20 3d 20 30 cord *pFinal = 0
41d0: 3b 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 ;. SorterRecord
41e0: 20 2a 2a 70 70 20 3d 20 26 70 46 69 6e 61 6c 3b **pp = &pFinal;
41f0: 0a 20 20 76 6f 69 64 20 2a 70 56 61 6c 32 20 3d . void *pVal2 =
4200: 20 70 32 20 3f 20 70 32 2d 3e 70 56 61 6c 20 3a p2 ? p2->pVal :
4210: 20 30 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70 31 0;.. while( p1
4220: 20 26 26 20 70 32 20 29 7b 0a 20 20 20 20 69 6e && p2 ){. in
4230: 74 20 72 65 73 3b 0a 20 20 20 20 72 63 20 3d 20 t res;. rc =
4240: 76 64 62 65 53 6f 72 74 65 72 43 6f 6d 70 61 72 vdbeSorterCompar
4250: 65 28 70 43 73 72 2c 20 30 2c 20 70 31 2d 3e 70 e(pCsr, 0, p1->p
4260: 56 61 6c 2c 20 70 31 2d 3e 6e 56 61 6c 2c 20 70 Val, p1->nVal, p
4270: 56 61 6c 32 2c 20 70 32 2d 3e 6e 56 61 6c 2c 20 Val2, p2->nVal,
4280: 26 72 65 73 29 3b 0a 20 20 20 20 69 66 28 20 72 &res);. if( r
4290: 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a c!=SQLITE_OK ){.
42a0: 20 20 20 20 20 20 2a 70 70 20 3d 20 30 3b 0a 20 *pp = 0;.
42b0: 20 20 20 20 20 76 64 62 65 53 6f 72 74 65 72 52 vdbeSorterR
42c0: 65 63 6f 72 64 46 72 65 65 28 64 62 2c 20 70 31 ecordFree(db, p1
42d0: 29 3b 0a 20 20 20 20 20 20 76 64 62 65 53 6f 72 );. vdbeSor
42e0: 74 65 72 52 65 63 6f 72 64 46 72 65 65 28 64 62 terRecordFree(db
42f0: 2c 20 70 32 29 3b 0a 20 20 20 20 20 20 76 64 62 , p2);. vdb
4300: 65 53 6f 72 74 65 72 52 65 63 6f 72 64 46 72 65 eSorterRecordFre
4310: 65 28 64 62 2c 20 70 46 69 6e 61 6c 29 3b 0a 20 e(db, pFinal);.
4320: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b *ppOut = 0;
4330: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 72 63 . return rc
4340: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 ;. }. if(
4350: 72 65 73 3c 3d 30 20 29 7b 0a 20 20 20 20 20 20 res<=0 ){.
4360: 2a 70 70 20 3d 20 70 31 3b 0a 20 20 20 20 20 20 *pp = p1;.
4370: 70 70 20 3d 20 26 70 31 2d 3e 70 4e 65 78 74 3b pp = &p1->pNext;
4380: 0a 20 20 20 20 20 20 70 31 20 3d 20 70 31 2d 3e . p1 = p1->
4390: 70 4e 65 78 74 3b 0a 20 20 20 20 20 20 70 56 61 pNext;. pVa
43a0: 6c 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 l2 = 0;. }els
43b0: 65 7b 0a 20 20 20 20 20 20 2a 70 70 20 3d 20 70 e{. *pp = p
43c0: 32 3b 0a 20 20 20 20 20 20 20 70 70 20 3d 20 26 2;. pp = &
43d0: 70 32 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20 p2->pNext;.
43e0: 20 70 32 20 3d 20 70 32 2d 3e 70 4e 65 78 74 3b p2 = p2->pNext;
43f0: 0a 20 20 20 20 20 20 69 66 28 20 70 32 3d 3d 30 . if( p2==0
4400: 20 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 ) break;.
4410: 70 56 61 6c 32 20 3d 20 70 32 2d 3e 70 56 61 6c pVal2 = p2->pVal
4420: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2a 70 ;. }. }. *p
4430: 70 20 3d 20 70 31 20 3f 20 70 31 20 3a 20 70 32 p = p1 ? p1 : p2
4440: 3b 0a 0a 20 20 2a 70 70 4f 75 74 20 3d 20 70 46 ;.. *ppOut = pF
4450: 69 6e 61 6c 3b 0a 20 20 72 65 74 75 72 6e 20 53 inal;. return S
4460: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a QLITE_OK;.}../*.
4470: 2a 2a 20 53 6f 72 74 20 74 68 65 20 6c 69 6e 6b ** Sort the link
4480: 65 64 20 6c 69 73 74 20 6f 66 20 72 65 63 6f 72 ed list of recor
4490: 64 73 20 68 65 61 64 65 64 20 61 74 20 70 43 73 ds headed at pCs
44a0: 72 2d 3e 70 52 65 63 6f 72 64 2e 20 52 65 74 75 r->pRecord. Retu
44b0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 0a 2a 2a 20 rn SQLITE_OK.**
44c0: 69 66 20 73 75 63 63 65 73 73 66 75 6c 2c 20 6f if successful, o
44d0: 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f r an SQLite erro
44e0: 72 20 63 6f 64 65 20 28 69 2e 65 2e 20 53 51 4c r code (i.e. SQL
44f0: 49 54 45 5f 4e 4f 4d 45 4d 29 20 69 66 20 61 6e ITE_NOMEM) if an
4500: 20 65 72 72 6f 72 0a 2a 2a 20 6f 63 63 75 72 73 error.** occurs
4510: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 ..*/.static int
4520: 76 64 62 65 53 6f 72 74 65 72 53 6f 72 74 28 73 vdbeSorterSort(s
4530: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 qlite3 *db, Vdbe
4540: 43 75 72 73 6f 72 20 2a 70 43 73 72 29 7b 0a 20 Cursor *pCsr){.
4550: 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 int rc = SQLITE
4560: 5f 4f 4b 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 _OK;. int i;.
4570: 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 61 SorterRecord **a
4580: 53 6c 6f 74 3b 0a 20 20 53 6f 72 74 65 72 52 65 Slot;. SorterRe
4590: 63 6f 72 64 20 2a 70 3b 0a 20 20 56 64 62 65 53 cord *p;. VdbeS
45a0: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d orter *pSorter =
45b0: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a pCsr->pSorter;.
45c0: 0a 20 20 61 53 6c 6f 74 20 3d 20 28 53 6f 72 74 . aSlot = (Sort
45d0: 65 72 52 65 63 6f 72 64 20 2a 2a 29 73 71 6c 69 erRecord **)sqli
45e0: 74 65 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28 36 34 te3MallocZero(64
45f0: 20 2a 20 73 69 7a 65 6f 66 28 53 6f 72 74 65 72 * sizeof(Sorter
4600: 52 65 63 6f 72 64 20 2a 29 29 3b 0a 20 20 69 66 Record *));. if
4610: 28 20 21 61 53 6c 6f 74 20 29 7b 0a 20 20 20 20 ( !aSlot ){.
4620: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f return SQLITE_NO
4630: 4d 45 4d 3b 0a 20 20 7d 0a 0a 20 20 70 20 3d 20 MEM;. }.. p =
4640: 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 pSorter->pRecord
4650: 3b 0a 20 20 77 68 69 6c 65 28 20 70 20 29 7b 0a ;. while( p ){.
4660: 20 20 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 SorterRecord
4670: 20 2a 70 4e 65 78 74 20 3d 20 70 2d 3e 70 4e 65 *pNext = p->pNe
4680: 78 74 3b 0a 20 20 20 20 70 2d 3e 70 4e 65 78 74 xt;. p->pNext
4690: 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d = 0;. for(i=
46a0: 30 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 0; rc==SQLITE_OK
46b0: 20 26 26 20 61 53 6c 6f 74 5b 69 5d 3b 20 69 2b && aSlot[i]; i+
46c0: 2b 29 7b 0a 20 20 20 20 20 20 72 63 20 3d 20 76 +){. rc = v
46d0: 64 62 65 53 6f 72 74 65 72 4d 65 72 67 65 28 64 dbeSorterMerge(d
46e0: 62 2c 20 70 43 73 72 2c 20 70 2c 20 61 53 6c 6f b, pCsr, p, aSlo
46f0: 74 5b 69 5d 2c 20 26 70 29 3b 0a 20 20 20 20 20 t[i], &p);.
4700: 20 61 53 6c 6f 74 5b 69 5d 20 3d 20 30 3b 0a 20 aSlot[i] = 0;.
4710: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 72 63 21 }. if( rc!
4720: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 =SQLITE_OK ){.
4730: 20 20 20 20 76 64 62 65 53 6f 72 74 65 72 52 65 vdbeSorterRe
4740: 63 6f 72 64 46 72 65 65 28 64 62 2c 20 70 4e 65 cordFree(db, pNe
4750: 78 74 29 3b 0a 20 20 20 20 20 20 62 72 65 61 6b xt);. break
4760: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 61 53 6c 6f ;. }. aSlo
4770: 74 5b 69 5d 20 3d 20 70 3b 0a 20 20 20 20 70 20 t[i] = p;. p
4780: 3d 20 70 4e 65 78 74 3b 0a 20 20 7d 0a 0a 20 20 = pNext;. }..
4790: 70 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 p = 0;. for(i=0
47a0: 3b 20 69 3c 36 34 3b 20 69 2b 2b 29 7b 0a 20 20 ; i<64; i++){.
47b0: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 if( rc==SQLITE
47c0: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 72 63 20 _OK ){. rc
47d0: 3d 20 76 64 62 65 53 6f 72 74 65 72 4d 65 72 67 = vdbeSorterMerg
47e0: 65 28 64 62 2c 20 70 43 73 72 2c 20 70 2c 20 61 e(db, pCsr, p, a
47f0: 53 6c 6f 74 5b 69 5d 2c 20 26 70 29 3b 0a 20 20 Slot[i], &p);.
4800: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 76 }else{. v
4810: 64 62 65 53 6f 72 74 65 72 52 65 63 6f 72 64 46 dbeSorterRecordF
4820: 72 65 65 28 64 62 2c 20 61 53 6c 6f 74 5b 69 5d ree(db, aSlot[i]
4830: 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 70 );. }. }. p
4840: 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 20 Sorter->pRecord
4850: 3d 20 70 3b 0a 0a 20 20 73 71 6c 69 74 65 33 5f = p;.. sqlite3_
4860: 66 72 65 65 28 61 53 6c 6f 74 29 3b 0a 20 20 72 free(aSlot);. r
4870: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 0a 2f 2a eturn rc;.}.../*
4880: 0a 2a 2a 20 57 72 69 74 65 20 74 68 65 20 63 75 .** Write the cu
4890: 72 72 65 6e 74 20 63 6f 6e 74 65 6e 74 73 20 6f rrent contents o
48a0: 66 20 74 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20 f the in-memory
48b0: 6c 69 6e 6b 65 64 2d 6c 69 73 74 20 74 6f 20 61 linked-list to a
48c0: 20 50 4d 41 2e 20 52 65 74 75 72 6e 0a 2a 2a 20 PMA. Return.**
48d0: 53 51 4c 49 54 45 5f 4f 4b 20 69 66 20 73 75 63 SQLITE_OK if suc
48e0: 63 65 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53 cessful, or an S
48f0: 51 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 QLite error code
4900: 20 6f 74 68 65 72 77 69 73 65 2e 0a 2a 2a 0a 2a otherwise..**.*
4910: 2a 20 54 68 65 20 66 6f 72 6d 61 74 20 6f 66 20 * The format of
4920: 61 20 50 4d 41 20 69 73 3a 0a 2a 2a 0a 2a 2a 20 a PMA is:.**.**
4930: 20 20 20 20 2a 20 41 20 76 61 72 69 6e 74 2e 20 * A varint.
4940: 54 68 69 73 20 76 61 72 69 6e 74 20 63 6f 6e 74 This varint cont
4950: 61 69 6e 73 20 74 68 65 20 74 6f 74 61 6c 20 6e ains the total n
4960: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f umber of bytes o
4970: 66 20 63 6f 6e 74 65 6e 74 0a 2a 2a 20 20 20 20 f content.**
4980: 20 20 20 69 6e 20 74 68 65 20 50 4d 41 20 28 6e in the PMA (n
4990: 6f 74 20 69 6e 63 6c 75 64 69 6e 67 20 74 68 65 ot including the
49a0: 20 76 61 72 69 6e 74 20 69 74 73 65 6c 66 29 2e varint itself).
49b0: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 2a 20 4f 6e 65 .**.** * One
49c0: 20 6f 72 20 6d 6f 72 65 20 72 65 63 6f 72 64 73 or more records
49d0: 20 70 61 63 6b 65 64 20 65 6e 64 2d 74 6f 2d 65 packed end-to-e
49e0: 6e 64 20 69 6e 20 6f 72 64 65 72 20 6f 66 20 61 nd in order of a
49f0: 73 63 65 6e 64 69 6e 67 20 6b 65 79 73 2e 20 0a scending keys. .
4a00: 2a 2a 20 20 20 20 20 20 20 45 61 63 68 20 72 65 ** Each re
4a10: 63 6f 72 64 20 63 6f 6e 73 69 73 74 73 20 6f 66 cord consists of
4a20: 20 61 20 76 61 72 69 6e 74 20 66 6f 6c 6c 6f 77 a varint follow
4a30: 65 64 20 62 79 20 61 20 62 6c 6f 62 20 6f 66 20 ed by a blob of
4a40: 64 61 74 61 20 28 74 68 65 20 0a 2a 2a 20 20 20 data (the .**
4a50: 20 20 20 20 6b 65 79 29 2e 20 54 68 65 20 76 61 key). The va
4a60: 72 69 6e 74 20 69 73 20 74 68 65 20 6e 75 6d 62 rint is the numb
4a70: 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 74 er of bytes in t
4a80: 68 65 20 62 6c 6f 62 20 6f 66 20 64 61 74 61 2e he blob of data.
4a90: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 .*/.static int v
4aa0: 64 62 65 53 6f 72 74 65 72 4c 69 73 74 54 6f 50 dbeSorterListToP
4ab0: 4d 41 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 MA(sqlite3 *db,
4ac0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 VdbeCursor *pCsr
4ad0: 29 7b 0a 20 20 69 6e 74 20 72 63 20 3d 20 53 51 ){. int rc = SQ
4ae0: 4c 49 54 45 5f 4f 4b 3b 20 20 20 20 20 20 20 20 LITE_OK;
4af0: 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63 /* Return c
4b00: 6f 64 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 ode */. VdbeSor
4b10: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 ter *pSorter = p
4b20: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 0a 20 Csr->pSorter;..
4b30: 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 49 if( pSorter->nI
4b40: 6e 4d 65 6d 6f 72 79 3d 3d 30 20 29 7b 0a 20 20 nMemory==0 ){.
4b50: 20 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65 assert( pSorte
4b60: 72 2d 3e 70 52 65 63 6f 72 64 3d 3d 30 20 29 3b r->pRecord==0 );
4b70: 0a 20 20 20 20 72 65 74 75 72 6e 20 72 63 3b 0a . return rc;.
4b80: 20 20 7d 0a 0a 20 20 72 63 20 3d 20 76 64 62 65 }.. rc = vdbe
4b90: 53 6f 72 74 65 72 53 6f 72 74 28 64 62 2c 20 70 SorterSort(db, p
4ba0: 43 73 72 29 3b 0a 0a 20 20 2f 2a 20 49 66 20 74 Csr);.. /* If t
4bb0: 68 65 20 66 69 72 73 74 20 74 65 6d 70 6f 72 61 he first tempora
4bc0: 72 79 20 50 4d 41 20 66 69 6c 65 20 68 61 73 20 ry PMA file has
4bd0: 6e 6f 74 20 62 65 65 6e 20 6f 70 65 6e 65 64 2c not been opened,
4be0: 20 6f 70 65 6e 20 69 74 20 6e 6f 77 2e 20 2a 2f open it now. */
4bf0: 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 . if( rc==SQLIT
4c00: 45 5f 4f 4b 20 26 26 20 70 53 6f 72 74 65 72 2d E_OK && pSorter-
4c10: 3e 70 54 65 6d 70 31 3d 3d 30 20 29 7b 0a 20 20 >pTemp1==0 ){.
4c20: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 rc = vdbeSorte
4c30: 72 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 64 62 rOpenTempFile(db
4c40: 2c 20 26 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d , &pSorter->pTem
4c50: 70 31 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 p1);. assert(
4c60: 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c rc!=SQLITE_OK |
4c70: 7c 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 | pSorter->pTemp
4c80: 31 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 1 );. assert(
4c90: 20 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 pSorter->iWrite
4ca0: 4f 66 66 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73 Off==0 );. as
4cb0: 73 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 6e sert( pSorter->n
4cc0: 50 4d 41 3d 3d 30 20 29 3b 0a 20 20 7d 0a 0a 20 PMA==0 );. }..
4cd0: 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f if( rc==SQLITE_
4ce0: 4f 4b 20 29 7b 0a 20 20 20 20 69 36 34 20 69 4f OK ){. i64 iO
4cf0: 66 66 20 3d 20 70 53 6f 72 74 65 72 2d 3e 69 57 ff = pSorter->iW
4d00: 72 69 74 65 4f 66 66 3b 0a 20 20 20 20 53 6f 72 riteOff;. Sor
4d10: 74 65 72 52 65 63 6f 72 64 20 2a 70 3b 0a 20 20 terRecord *p;.
4d20: 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a SorterRecord *
4d30: 70 4e 65 78 74 20 3d 20 30 3b 0a 20 20 20 20 73 pNext = 0;. s
4d40: 74 61 74 69 63 20 63 6f 6e 73 74 20 63 68 61 72 tatic const char
4d50: 20 65 69 67 68 74 5a 65 72 6f 73 5b 38 5d 20 3d eightZeros[8] =
4d60: 20 7b 20 30 2c 20 30 2c 20 30 2c 20 30 2c 20 30 { 0, 0, 0, 0, 0
4d70: 2c 20 30 2c 20 30 2c 20 30 20 7d 3b 0a 0a 20 20 , 0, 0, 0 };..
4d80: 20 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 2b pSorter->nPMA+
4d90: 2b 3b 0a 20 20 20 20 72 63 20 3d 20 76 64 62 65 +;. rc = vdbe
4da0: 53 6f 72 74 65 72 57 72 69 74 65 56 61 72 69 6e SorterWriteVarin
4db0: 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 t(pSorter->pTemp
4dc0: 31 2c 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 1, pSorter->nInM
4dd0: 65 6d 6f 72 79 2c 20 26 69 4f 66 66 29 3b 0a 20 emory, &iOff);.
4de0: 20 20 20 66 6f 72 28 70 3d 70 53 6f 72 74 65 72 for(p=pSorter
4df0: 2d 3e 70 52 65 63 6f 72 64 3b 20 72 63 3d 3d 53 ->pRecord; rc==S
4e00: 51 4c 49 54 45 5f 4f 4b 20 26 26 20 70 3b 20 70 QLITE_OK && p; p
4e10: 3d 70 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 70 =pNext){. p
4e20: 4e 65 78 74 20 3d 20 70 2d 3e 70 4e 65 78 74 3b Next = p->pNext;
4e30: 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64 62 65 . rc = vdbe
4e40: 53 6f 72 74 65 72 57 72 69 74 65 56 61 72 69 6e SorterWriteVarin
4e50: 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 t(pSorter->pTemp
4e60: 31 2c 20 70 2d 3e 6e 56 61 6c 2c 20 26 69 4f 66 1, p->nVal, &iOf
4e70: 66 29 3b 0a 0a 20 20 20 20 20 20 69 66 28 20 72 f);.. if( r
4e80: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a c==SQLITE_OK ){.
4e90: 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c rc = sql
4ea0: 69 74 65 33 4f 73 57 72 69 74 65 28 70 53 6f 72 ite3OsWrite(pSor
4eb0: 74 65 72 2d 3e 70 54 65 6d 70 31 2c 20 70 2d 3e ter->pTemp1, p->
4ec0: 70 56 61 6c 2c 20 70 2d 3e 6e 56 61 6c 2c 20 69 pVal, p->nVal, i
4ed0: 4f 66 66 29 3b 0a 20 20 20 20 20 20 20 20 69 4f Off);. iO
4ee0: 66 66 20 2b 3d 20 70 2d 3e 6e 56 61 6c 3b 0a 20 ff += p->nVal;.
4ef0: 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 73 71 }.. sq
4f00: 6c 69 74 65 33 44 62 46 72 65 65 28 64 62 2c 20 lite3DbFree(db,
4f10: 70 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f p);. }.. /
4f20: 2a 20 54 68 69 73 20 61 73 73 65 72 74 20 76 65 * This assert ve
4f30: 72 69 66 69 65 73 20 74 68 61 74 20 75 6e 6c 65 rifies that unle
4f40: 73 73 20 61 6e 20 65 72 72 6f 72 20 68 61 73 20 ss an error has
4f50: 6f 63 63 75 72 72 65 64 2c 20 74 68 65 20 73 69 occurred, the si
4f60: 7a 65 20 6f 66 20 0a 20 20 20 20 2a 2a 20 74 68 ze of . ** th
4f70: 65 20 50 4d 41 20 6f 6e 20 64 69 73 6b 20 69 73 e PMA on disk is
4f80: 20 74 68 65 20 73 61 6d 65 20 61 73 20 74 68 65 the same as the
4f90: 20 65 78 70 65 63 74 65 64 20 73 69 7a 65 20 73 expected size s
4fa0: 74 6f 72 65 64 20 69 6e 0a 20 20 20 20 2a 2a 20 tored in. **
4fb0: 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f pSorter->nInMemo
4fc0: 72 79 2e 20 2a 2f 20 0a 20 20 20 20 61 73 73 65 ry. */ . asse
4fd0: 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f rt( rc!=SQLITE_O
4fe0: 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 6e 49 K || pSorter->nI
4ff0: 6e 4d 65 6d 6f 72 79 3d 3d 28 0a 20 20 20 20 20 nMemory==(.
5000: 20 20 20 20 20 69 4f 66 66 2d 70 53 6f 72 74 65 iOff-pSorte
5010: 72 2d 3e 69 57 72 69 74 65 4f 66 66 2d 73 71 6c r->iWriteOff-sql
5020: 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28 70 53 ite3VarintLen(pS
5030: 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 orter->nInMemory
5040: 29 0a 20 20 20 20 29 29 3b 0a 0a 20 20 20 20 70 ). ));.. p
5050: 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 Sorter->iWriteOf
5060: 66 20 3d 20 69 4f 66 66 3b 0a 20 20 20 20 69 66 f = iOff;. if
5070: 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 ( rc==SQLITE_OK
5080: 29 7b 0a 20 20 20 20 20 20 2f 2a 20 54 65 72 6d ){. /* Term
5090: 69 6e 61 74 65 20 65 61 63 68 20 66 69 6c 65 20 inate each file
50a0: 77 69 74 68 20 38 20 65 78 74 72 61 20 62 79 74 with 8 extra byt
50b0: 65 73 20 73 6f 20 74 68 61 74 20 66 72 6f 6d 20 es so that from
50c0: 61 6e 79 20 6f 66 66 73 65 74 0a 20 20 20 20 20 any offset.
50d0: 20 2a 2a 20 69 6e 20 74 68 65 20 66 69 6c 65 20 ** in the file
50e0: 77 65 20 63 61 6e 20 61 6c 77 61 79 73 20 72 65 we can always re
50f0: 61 64 20 39 20 62 79 74 65 73 20 77 69 74 68 6f ad 9 bytes witho
5100: 75 74 20 61 20 53 48 4f 52 54 5f 52 45 41 44 20 ut a SHORT_READ
5110: 65 72 72 6f 72 20 2a 2f 0a 20 20 20 20 20 20 72 error */. r
5120: 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 57 72 69 c = sqlite3OsWri
5130: 74 65 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d te(pSorter->pTem
5140: 70 31 2c 20 65 69 67 68 74 5a 65 72 6f 73 2c 20 p1, eightZeros,
5150: 38 2c 20 69 4f 66 66 29 3b 0a 20 20 20 20 7d 0a 8, iOff);. }.
5160: 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 pSorter->pRe
5170: 63 6f 72 64 20 3d 20 70 3b 0a 20 20 7d 0a 0a 20 cord = p;. }..
5180: 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f return rc;.}../
5190: 2a 0a 2a 2a 20 41 64 64 20 61 20 72 65 63 6f 72 *.** Add a recor
51a0: 64 20 74 6f 20 74 68 65 20 73 6f 72 74 65 72 2e d to the sorter.
51b0: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 .*/.int sqlite3V
51c0: 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 28 0a dbeSorterWrite(.
51d0: 20 20 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 sqlite3 *db,
51e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
51f0: 20 20 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 /* Database ha
5200: 6e 64 6c 65 20 2a 2f 0a 20 20 56 64 62 65 43 75 ndle */. VdbeCu
5210: 72 73 6f 72 20 2a 70 43 73 72 2c 20 20 20 20 20 rsor *pCsr,
5220: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 /* Sor
5230: 74 65 72 20 63 75 72 73 6f 72 20 2a 2f 0a 20 20 ter cursor */.
5240: 4d 65 6d 20 2a 70 56 61 6c 20 20 20 20 20 20 20 Mem *pVal
5250: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
5260: 2f 2a 20 4d 65 6d 6f 72 79 20 63 65 6c 6c 20 63 /* Memory cell c
5270: 6f 6e 74 61 69 6e 69 6e 67 20 72 65 63 6f 72 64 ontaining record
5280: 20 2a 2f 0a 29 7b 0a 20 20 56 64 62 65 53 6f 72 */.){. VdbeSor
5290: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 ter *pSorter = p
52a0: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 Csr->pSorter;.
52b0: 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f int rc = SQLITE_
52c0: 4f 4b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 OK;
52d0: 2f 2a 20 52 65 74 75 72 6e 20 43 6f 64 65 20 2a /* Return Code *
52e0: 2f 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 /. SorterRecord
52f0: 20 2a 70 4e 65 77 3b 20 20 20 20 20 20 20 20 20 *pNew;
5300: 20 20 20 20 2f 2a 20 4e 65 77 20 6c 69 73 74 20 /* New list
5310: 65 6c 65 6d 65 6e 74 20 2a 2f 0a 0a 20 20 61 73 element */.. as
5320: 73 65 72 74 28 20 70 53 6f 72 74 65 72 20 29 3b sert( pSorter );
5330: 0a 20 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d . pSorter->nInM
5340: 65 6d 6f 72 79 20 2b 3d 20 73 71 6c 69 74 65 33 emory += sqlite3
5350: 56 61 72 69 6e 74 4c 65 6e 28 70 56 61 6c 2d 3e VarintLen(pVal->
5360: 6e 29 20 2b 20 70 56 61 6c 2d 3e 6e 3b 0a 0a 20 n) + pVal->n;..
5370: 20 70 4e 65 77 20 3d 20 28 53 6f 72 74 65 72 52 pNew = (SorterR
5380: 65 63 6f 72 64 20 2a 29 73 71 6c 69 74 65 33 44 ecord *)sqlite3D
5390: 62 4d 61 6c 6c 6f 63 52 61 77 28 64 62 2c 20 70 bMallocRaw(db, p
53a0: 56 61 6c 2d 3e 6e 20 2b 20 73 69 7a 65 6f 66 28 Val->n + sizeof(
53b0: 53 6f 72 74 65 72 52 65 63 6f 72 64 29 29 3b 0a SorterRecord));.
53c0: 20 20 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 7b if( pNew==0 ){
53d0: 0a 20 20 20 20 72 63 20 3d 20 53 51 4c 49 54 45 . rc = SQLITE
53e0: 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65 6c 73 65 7b _NOMEM;. }else{
53f0: 0a 20 20 20 20 70 4e 65 77 2d 3e 70 56 61 6c 20 . pNew->pVal
5400: 3d 20 28 76 6f 69 64 20 2a 29 26 70 4e 65 77 5b = (void *)&pNew[
5410: 31 5d 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28 70 1];. memcpy(p
5420: 4e 65 77 2d 3e 70 56 61 6c 2c 20 70 56 61 6c 2d New->pVal, pVal-
5430: 3e 7a 2c 20 70 56 61 6c 2d 3e 6e 29 3b 0a 20 20 >z, pVal->n);.
5440: 20 20 70 4e 65 77 2d 3e 6e 56 61 6c 20 3d 20 70 pNew->nVal = p
5450: 56 61 6c 2d 3e 6e 3b 0a 20 20 20 20 70 4e 65 77 Val->n;. pNew
5460: 2d 3e 70 4e 65 78 74 20 3d 20 70 53 6f 72 74 65 ->pNext = pSorte
5470: 72 2d 3e 70 52 65 63 6f 72 64 3b 0a 20 20 20 20 r->pRecord;.
5480: 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 pSorter->pRecord
5490: 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 0a 20 20 = pNew;. }..
54a0: 2f 2a 20 53 65 65 20 69 66 20 74 68 65 20 63 6f /* See if the co
54b0: 6e 74 65 6e 74 73 20 6f 66 20 74 68 65 20 73 6f ntents of the so
54c0: 72 74 65 72 20 73 68 6f 75 6c 64 20 6e 6f 77 20 rter should now
54d0: 62 65 20 77 72 69 74 74 65 6e 20 6f 75 74 2e 20 be written out.
54e0: 54 68 65 79 0a 20 20 2a 2a 20 61 72 65 20 77 72 They. ** are wr
54f0: 69 74 74 65 6e 20 6f 75 74 20 77 68 65 6e 20 65 itten out when e
5500: 69 74 68 65 72 20 6f 66 20 74 68 65 20 66 6f 6c ither of the fol
5510: 6c 6f 77 69 6e 67 20 61 72 65 20 74 72 75 65 3a lowing are true:
5520: 0a 20 20 2a 2a 0a 20 20 2a 2a 20 20 20 2a 20 54 . **. ** * T
5530: 68 65 20 74 6f 74 61 6c 20 6d 65 6d 6f 72 79 20 he total memory
5540: 61 6c 6c 6f 63 61 74 65 64 20 66 6f 72 20 74 68 allocated for th
5550: 65 20 69 6e 2d 6d 65 6d 6f 72 79 20 6c 69 73 74 e in-memory list
5560: 20 69 73 20 67 72 65 61 74 65 72 20 0a 20 20 2a is greater . *
5570: 2a 20 20 20 20 20 74 68 61 6e 20 28 70 61 67 65 * than (page
5580: 2d 73 69 7a 65 20 2a 20 63 61 63 68 65 2d 73 69 -size * cache-si
5590: 7a 65 29 2c 20 6f 72 0a 20 20 2a 2a 0a 20 20 2a ze), or. **. *
55a0: 2a 20 20 20 2a 20 54 68 65 20 74 6f 74 61 6c 20 * * The total
55b0: 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 65 64 memory allocated
55c0: 20 66 6f 72 20 74 68 65 20 69 6e 2d 6d 65 6d 6f for the in-memo
55d0: 72 79 20 6c 69 73 74 20 69 73 20 67 72 65 61 74 ry list is great
55e0: 65 72 20 0a 20 20 2a 2a 20 20 20 20 20 74 68 61 er . ** tha
55f0: 6e 20 28 70 61 67 65 2d 73 69 7a 65 20 2a 20 31 n (page-size * 1
5600: 30 29 20 61 6e 64 20 73 71 6c 69 74 65 33 48 65 0) and sqlite3He
5610: 61 70 4e 65 61 72 6c 79 46 75 6c 6c 28 29 20 72 apNearlyFull() r
5620: 65 74 75 72 6e 73 20 74 72 75 65 2e 0a 20 20 2a eturns true.. *
5630: 2f 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 /. if( rc==SQLI
5640: 54 45 5f 4f 4b 20 26 26 20 70 53 6f 72 74 65 72 TE_OK && pSorter
5650: 2d 3e 6d 78 50 6d 61 53 69 7a 65 3e 30 20 26 26 ->mxPmaSize>0 &&
5660: 20 28 0a 20 20 20 20 20 20 20 20 28 70 53 6f 72 (. (pSor
5670: 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 3e 70 ter->nInMemory>p
5680: 53 6f 72 74 65 72 2d 3e 6d 78 50 6d 61 53 69 7a Sorter->mxPmaSiz
5690: 65 29 0a 20 20 20 20 20 7c 7c 20 28 70 53 6f 72 e). || (pSor
56a0: 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 3e 70 ter->nInMemory>p
56b0: 53 6f 72 74 65 72 2d 3e 6d 6e 50 6d 61 53 69 7a Sorter->mnPmaSiz
56c0: 65 20 26 26 20 73 71 6c 69 74 65 33 48 65 61 70 e && sqlite3Heap
56d0: 4e 65 61 72 6c 79 46 75 6c 6c 28 29 29 0a 20 20 NearlyFull()).
56e0: 29 29 7b 0a 20 20 20 20 72 63 20 3d 20 76 64 62 )){. rc = vdb
56f0: 65 53 6f 72 74 65 72 4c 69 73 74 54 6f 50 4d 41 eSorterListToPMA
5700: 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 20 20 20 (db, pCsr);.
5710: 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f pSorter->nInMemo
5720: 72 79 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20 20 72 ry = 0;. }.. r
5730: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a eturn rc;.}../*.
5740: 2a 2a 20 48 65 6c 70 65 72 20 66 75 6e 63 74 69 ** Helper functi
5750: 6f 6e 20 66 6f 72 20 73 71 6c 69 74 65 33 56 64 on for sqlite3Vd
5760: 62 65 53 6f 72 74 65 72 52 65 77 69 6e 64 28 29 beSorterRewind()
5770: 2e 20 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 . .*/.static int
5780: 20 76 64 62 65 53 6f 72 74 65 72 49 6e 69 74 4d vdbeSorterInitM
5790: 65 72 67 65 28 0a 20 20 73 71 6c 69 74 65 33 20 erge(. sqlite3
57a0: 2a 64 62 2c 20 20 20 20 20 20 20 20 20 20 20 20 *db,
57b0: 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62 /* Datab
57c0: 61 73 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 ase handle */.
57d0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 VdbeCursor *pCsr
57e0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,
57f0: 2f 2a 20 43 75 72 73 6f 72 20 68 61 6e 64 6c 65 /* Cursor handle
5800: 20 66 6f 72 20 74 68 69 73 20 73 6f 72 74 65 72 for this sorter
5810: 20 2a 2f 0a 20 20 69 36 34 20 2a 70 6e 42 79 74 */. i64 *pnByt
5820: 65 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 e
5830: 20 20 20 20 20 20 2f 2a 20 53 75 6d 20 6f 66 20 /* Sum of
5840: 62 79 74 65 73 20 69 6e 20 61 6c 6c 20 6f 70 65 bytes in all ope
5850: 6e 65 64 20 50 4d 41 73 20 2a 2f 0a 29 7b 0a 20 ned PMAs */.){.
5860: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f VdbeSorter *pSo
5870: 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f rter = pCsr->pSo
5880: 72 74 65 72 3b 0a 20 20 69 6e 74 20 72 63 20 3d rter;. int rc =
5890: 20 53 51 4c 49 54 45 5f 4f 4b 3b 20 20 20 20 20 SQLITE_OK;
58a0: 20 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 /* Retur
58b0: 6e 20 63 6f 64 65 20 2a 2f 0a 20 20 69 6e 74 20 n code */. int
58c0: 69 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 i;
58d0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 /* U
58e0: 73 65 64 20 74 6f 20 69 74 65 72 61 74 6f 72 20 sed to iterator
58f0: 74 68 72 6f 75 67 68 20 61 49 74 65 72 5b 5d 20 through aIter[]
5900: 2a 2f 0a 20 20 69 36 34 20 6e 42 79 74 65 20 3d */. i64 nByte =
5910: 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 0;
5920: 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 62 79 /* Total by
5930: 74 65 73 20 69 6e 20 61 6c 6c 20 6f 70 65 6e 65 tes in all opene
5940: 64 20 50 4d 41 73 20 2a 2f 0a 0a 20 20 2f 2a 20 d PMAs */.. /*
5950: 49 6e 69 74 69 61 6c 69 7a 65 20 74 68 65 20 69 Initialize the i
5960: 74 65 72 61 74 6f 72 73 2e 20 2a 2f 0a 20 20 66 terators. */. f
5970: 6f 72 28 69 3d 30 3b 20 69 3c 53 4f 52 54 45 52 or(i=0; i<SORTER
5980: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 _MAX_MERGE_COUNT
5990: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 56 64 62 65 ; i++){. Vdbe
59a0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65 SorterIter *pIte
59b0: 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 49 r = &pSorter->aI
59c0: 74 65 72 5b 69 5d 3b 0a 20 20 20 20 72 63 20 3d ter[i];. rc =
59d0: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 49 vdbeSorterIterI
59e0: 6e 69 74 28 64 62 2c 20 70 53 6f 72 74 65 72 2c nit(db, pSorter,
59f0: 20 70 53 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f pSorter->iReadO
5a00: 66 66 2c 20 70 49 74 65 72 2c 20 26 6e 42 79 74 ff, pIter, &nByt
5a10: 65 29 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d e);. pSorter-
5a20: 3e 69 52 65 61 64 4f 66 66 20 3d 20 70 49 74 65 >iReadOff = pIte
5a30: 72 2d 3e 69 45 6f 66 3b 0a 20 20 20 20 61 73 73 r->iEof;. ass
5a40: 65 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f ert( rc!=SQLITE_
5a50: 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 69 OK || pSorter->i
5a60: 52 65 61 64 4f 66 66 3c 3d 70 53 6f 72 74 65 72 ReadOff<=pSorter
5a70: 2d 3e 69 57 72 69 74 65 4f 66 66 20 29 3b 0a 20 ->iWriteOff );.
5a80: 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49 54 if( rc!=SQLIT
5a90: 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d E_OK || pSorter-
5aa0: 3e 69 52 65 61 64 4f 66 66 3e 3d 70 53 6f 72 74 >iReadOff>=pSort
5ab0: 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 20 29 20 er->iWriteOff )
5ac0: 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 2f 2a break;. }.. /*
5ad0: 20 49 6e 69 74 69 61 6c 69 7a 65 20 74 68 65 20 Initialize the
5ae0: 61 54 72 65 65 5b 5d 20 61 72 72 61 79 2e 20 2a aTree[] array. *
5af0: 2f 0a 20 20 66 6f 72 28 69 3d 70 53 6f 72 74 65 /. for(i=pSorte
5b00: 72 2d 3e 6e 54 72 65 65 2d 31 3b 20 72 63 3d 3d r->nTree-1; rc==
5b10: 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69 3e 30 SQLITE_OK && i>0
5b20: 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 72 63 20 3d ; i--){. rc =
5b30: 20 76 64 62 65 53 6f 72 74 65 72 44 6f 43 6f 6d vdbeSorterDoCom
5b40: 70 61 72 65 28 70 43 73 72 2c 20 69 29 3b 0a 20 pare(pCsr, i);.
5b50: 20 7d 0a 0a 20 20 2a 70 6e 42 79 74 65 20 3d 20 }.. *pnByte =
5b60: 6e 42 79 74 65 3b 0a 20 20 72 65 74 75 72 6e 20 nByte;. return
5b70: 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 4f 6e 63 rc;.}../*.** Onc
5b80: 65 20 74 68 65 20 73 6f 72 74 65 72 20 68 61 73 e the sorter has
5b90: 20 62 65 65 6e 20 70 6f 70 75 6c 61 74 65 64 2c been populated,
5ba0: 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 this function i
5bb0: 73 20 63 61 6c 6c 65 64 20 74 6f 20 70 72 65 70 s called to prep
5bc0: 61 72 65 0a 2a 2a 20 66 6f 72 20 69 74 65 72 61 are.** for itera
5bd0: 74 69 6e 67 20 74 68 72 6f 75 67 68 20 69 74 73 ting through its
5be0: 20 63 6f 6e 74 65 6e 74 73 20 69 6e 20 73 6f 72 contents in sor
5bf0: 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2f 0a 69 6e ted order..*/.in
5c00: 74 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 t sqlite3VdbeSor
5c10: 74 65 72 52 65 77 69 6e 64 28 73 71 6c 69 74 65 terRewind(sqlite
5c20: 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73 6f 3 *db, VdbeCurso
5c30: 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 2a 70 62 r *pCsr, int *pb
5c40: 45 6f 66 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 Eof){. VdbeSort
5c50: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 er *pSorter = pC
5c60: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 sr->pSorter;. i
5c70: 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20 20 20 nt rc;
5c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
5c90: 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f * Return code */
5ca0: 0a 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 . sqlite3_file
5cb0: 2a 70 54 65 6d 70 32 20 3d 20 30 3b 20 20 20 20 *pTemp2 = 0;
5cc0: 20 20 20 2f 2a 20 53 65 63 6f 6e 64 20 74 65 6d /* Second tem
5cd0: 70 20 66 69 6c 65 20 74 6f 20 75 73 65 20 2a 2f p file to use */
5ce0: 0a 20 20 69 36 34 20 69 57 72 69 74 65 32 20 3d . i64 iWrite2 =
5cf0: 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 0;
5d00: 20 20 20 2f 2a 20 57 72 69 74 65 20 6f 66 66 73 /* Write offs
5d10: 65 74 20 66 6f 72 20 70 54 65 6d 70 32 20 2a 2f et for pTemp2 */
5d20: 0a 20 20 69 6e 74 20 6e 49 74 65 72 3b 20 20 20 . int nIter;
5d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
5d40: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 /* Number of
5d50: 69 74 65 72 61 74 6f 72 73 20 75 73 65 64 20 2a iterators used *
5d60: 2f 0a 20 20 69 6e 74 20 6e 42 79 74 65 3b 20 20 /. int nByte;
5d70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
5d80: 20 20 20 20 2f 2a 20 42 79 74 65 73 20 6f 66 20 /* Bytes of
5d90: 73 70 61 63 65 20 72 65 71 75 69 72 65 64 20 66 space required f
5da0: 6f 72 20 61 49 74 65 72 2f 61 54 72 65 65 20 2a or aIter/aTree *
5db0: 2f 0a 20 20 69 6e 74 20 4e 20 3d 20 32 3b 20 20 /. int N = 2;
5dc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
5dd0: 20 20 20 20 2f 2a 20 50 6f 77 65 72 20 6f 66 20 /* Power of
5de0: 32 20 3e 3d 20 6e 49 74 65 72 20 2a 2f 0a 0a 20 2 >= nIter */..
5df0: 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65 72 assert( pSorter
5e00: 20 29 3b 0a 0a 20 20 2f 2a 20 49 66 20 6e 6f 20 );.. /* If no
5e10: 64 61 74 61 20 68 61 73 20 62 65 65 6e 20 77 72 data has been wr
5e20: 69 74 74 65 6e 20 74 6f 20 64 69 73 6b 2c 20 74 itten to disk, t
5e30: 68 65 6e 20 64 6f 20 6e 6f 74 20 64 6f 20 73 6f hen do not do so
5e40: 20 6e 6f 77 2e 20 49 6e 73 74 65 61 64 2c 0a 20 now. Instead,.
5e50: 20 2a 2a 20 73 6f 72 74 20 74 68 65 20 56 64 62 ** sort the Vdb
5e60: 65 53 6f 72 74 65 72 2e 70 52 65 63 6f 72 64 20 eSorter.pRecord
5e70: 6c 69 73 74 2e 20 54 68 65 20 76 64 62 65 20 6c list. The vdbe l
5e80: 61 79 65 72 20 77 69 6c 6c 20 72 65 61 64 20 64 ayer will read d
5e90: 61 74 61 20 64 69 72 65 63 74 6c 79 0a 20 20 2a ata directly. *
5ea0: 2a 20 66 72 6f 6d 20 74 68 65 20 69 6e 2d 6d 65 * from the in-me
5eb0: 6d 6f 72 79 20 6c 69 73 74 2e 20 20 2a 2f 0a 20 mory list. */.
5ec0: 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 50 if( pSorter->nP
5ed0: 4d 41 3d 3d 30 20 29 7b 0a 20 20 20 20 2a 70 62 MA==0 ){. *pb
5ee0: 45 6f 66 20 3d 20 21 70 53 6f 72 74 65 72 2d 3e Eof = !pSorter->
5ef0: 70 52 65 63 6f 72 64 3b 0a 20 20 20 20 61 73 73 pRecord;. ass
5f00: 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 61 54 ert( pSorter->aT
5f10: 72 65 65 3d 3d 30 20 29 3b 0a 20 20 20 20 72 65 ree==0 );. re
5f20: 74 75 72 6e 20 76 64 62 65 53 6f 72 74 65 72 53 turn vdbeSorterS
5f30: 6f 72 74 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 ort(db, pCsr);.
5f40: 20 7d 0a 0a 20 20 2f 2a 20 57 72 69 74 65 20 74 }.. /* Write t
5f50: 68 65 20 63 75 72 72 65 6e 74 20 62 2d 74 72 65 he current b-tre
5f60: 65 20 74 6f 20 61 20 50 4d 41 2e 20 43 6c 6f 73 e to a PMA. Clos
5f70: 65 20 74 68 65 20 62 2d 74 72 65 65 20 63 75 72 e the b-tree cur
5f80: 73 6f 72 2e 20 2a 2f 0a 20 20 72 63 20 3d 20 76 sor. */. rc = v
5f90: 64 62 65 53 6f 72 74 65 72 4c 69 73 74 54 6f 50 dbeSorterListToP
5fa0: 4d 41 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 20 MA(db, pCsr);.
5fb0: 69 66 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f if( rc!=SQLITE_O
5fc0: 4b 20 29 20 72 65 74 75 72 6e 20 72 63 3b 0a 0a K ) return rc;..
5fd0: 20 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 73 70 /* Allocate sp
5fe0: 61 63 65 20 66 6f 72 20 61 49 74 65 72 5b 5d 20 ace for aIter[]
5ff0: 61 6e 64 20 61 54 72 65 65 5b 5d 2e 20 2a 2f 0a and aTree[]. */.
6000: 20 20 6e 49 74 65 72 20 3d 20 70 53 6f 72 74 65 nIter = pSorte
6010: 72 2d 3e 6e 50 4d 41 3b 0a 20 20 69 66 28 20 6e r->nPMA;. if( n
6020: 49 74 65 72 3e 53 4f 52 54 45 52 5f 4d 41 58 5f Iter>SORTER_MAX_
6030: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 29 20 6e 49 MERGE_COUNT ) nI
6040: 74 65 72 20 3d 20 53 4f 52 54 45 52 5f 4d 41 58 ter = SORTER_MAX
6050: 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 3b 0a 20 20 _MERGE_COUNT;.
6060: 61 73 73 65 72 74 28 20 6e 49 74 65 72 3e 30 20 assert( nIter>0
6070: 29 3b 0a 20 20 77 68 69 6c 65 28 20 4e 3c 6e 49 );. while( N<nI
6080: 74 65 72 20 29 20 4e 20 2b 3d 20 4e 3b 0a 20 20 ter ) N += N;.
6090: 6e 42 79 74 65 20 3d 20 4e 20 2a 20 28 73 69 7a nByte = N * (siz
60a0: 65 6f 66 28 69 6e 74 29 20 2b 20 73 69 7a 65 6f eof(int) + sizeo
60b0: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 f(VdbeSorterIter
60c0: 29 29 3b 0a 20 20 70 53 6f 72 74 65 72 2d 3e 61 ));. pSorter->a
60d0: 49 74 65 72 20 3d 20 28 56 64 62 65 53 6f 72 74 Iter = (VdbeSort
60e0: 65 72 49 74 65 72 20 2a 29 73 71 6c 69 74 65 33 erIter *)sqlite3
60f0: 44 62 4d 61 6c 6c 6f 63 5a 65 72 6f 28 64 62 2c DbMallocZero(db,
6100: 20 6e 42 79 74 65 29 3b 0a 20 20 69 66 28 20 21 nByte);. if( !
6110: 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 20 29 pSorter->aIter )
6120: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e return SQLITE_N
6130: 4f 4d 45 4d 3b 0a 20 20 70 53 6f 72 74 65 72 2d OMEM;. pSorter-
6140: 3e 61 54 72 65 65 20 3d 20 28 69 6e 74 20 2a 29 >aTree = (int *)
6150: 26 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b &pSorter->aIter[
6160: 4e 5d 3b 0a 20 20 70 53 6f 72 74 65 72 2d 3e 6e N];. pSorter->n
6170: 54 72 65 65 20 3d 20 4e 3b 0a 0a 20 20 64 6f 20 Tree = N;.. do
6180: 7b 0a 20 20 20 20 69 6e 74 20 69 4e 65 77 3b 20 {. int iNew;
6190: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
61a0: 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 /* Index of
61b0: 6e 65 77 2c 20 6d 65 72 67 65 64 2c 20 50 4d 41 new, merged, PMA
61c0: 20 2a 2f 0a 0a 20 20 20 20 66 6f 72 28 69 4e 65 */.. for(iNe
61d0: 77 3d 30 3b 20 0a 20 20 20 20 20 20 20 20 72 63 w=0; . rc
61e0: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69 ==SQLITE_OK && i
61f0: 4e 65 77 2a 53 4f 52 54 45 52 5f 4d 41 58 5f 4d New*SORTER_MAX_M
6200: 45 52 47 45 5f 43 4f 55 4e 54 3c 70 53 6f 72 74 ERGE_COUNT<pSort
6210: 65 72 2d 3e 6e 50 4d 41 3b 20 0a 20 20 20 20 20 er->nPMA; .
6220: 20 20 20 69 4e 65 77 2b 2b 0a 20 20 20 20 29 7b iNew++. ){
6230: 0a 20 20 20 20 20 20 69 36 34 20 6e 57 72 69 74 . i64 nWrit
6240: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 e;
6250: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 /* Number of
6260: 62 79 74 65 73 20 69 6e 20 6e 65 77 20 50 4d 41 bytes in new PMA
6270: 20 2a 2f 0a 0a 20 20 20 20 20 20 2f 2a 20 49 66 */.. /* If
6280: 20 74 68 65 72 65 20 61 72 65 20 53 4f 52 54 45 there are SORTE
6290: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e R_MAX_MERGE_COUN
62a0: 54 20 6f 72 20 6c 65 73 73 20 50 4d 41 73 20 69 T or less PMAs i
62b0: 6e 20 66 69 6c 65 20 70 54 65 6d 70 31 2c 0a 20 n file pTemp1,.
62c0: 20 20 20 20 20 2a 2a 20 69 6e 69 74 69 61 6c 69 ** initiali
62d0: 7a 65 20 61 6e 20 69 74 65 72 61 74 6f 72 20 66 ze an iterator f
62e0: 6f 72 20 65 61 63 68 20 6f 66 20 74 68 65 6d 20 or each of them
62f0: 61 6e 64 20 62 72 65 61 6b 20 6f 75 74 20 6f 66 and break out of
6300: 20 74 68 65 20 6c 6f 6f 70 2e 0a 20 20 20 20 20 the loop..
6310: 20 2a 2a 20 54 68 65 73 65 20 69 74 65 72 61 74 ** These iterat
6320: 6f 72 73 20 77 69 6c 6c 20 62 65 20 69 6e 63 72 ors will be incr
6330: 65 6d 65 6e 74 61 6c 6c 79 20 6d 65 72 67 65 64 ementally merged
6340: 20 61 73 20 74 68 65 20 56 44 42 45 20 6c 61 79 as the VDBE lay
6350: 65 72 20 63 61 6c 6c 73 0a 20 20 20 20 20 20 2a er calls. *
6360: 2a 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 * sqlite3VdbeSor
6370: 74 65 72 4e 65 78 74 28 29 2e 0a 20 20 20 20 20 terNext()..
6380: 20 2a 2a 0a 20 20 20 20 20 20 2a 2a 20 4f 74 68 **. ** Oth
6390: 65 72 77 69 73 65 2c 20 69 66 20 70 54 65 6d 70 erwise, if pTemp
63a0: 31 20 63 6f 6e 74 61 69 6e 73 20 6d 6f 72 65 20 1 contains more
63b0: 74 68 61 6e 20 53 4f 52 54 45 52 5f 4d 41 58 5f than SORTER_MAX_
63c0: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 50 4d 41 73 MERGE_COUNT PMAs
63d0: 2c 0a 20 20 20 20 20 20 2a 2a 20 69 6e 69 74 69 ,. ** initi
63e0: 61 6c 69 7a 65 20 69 6e 74 65 72 61 74 6f 72 73 alize interators
63f0: 20 66 6f 72 20 53 4f 52 54 45 52 5f 4d 41 58 5f for SORTER_MAX_
6400: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 6f 66 20 74 MERGE_COUNT of t
6410: 68 65 6d 2e 20 54 68 65 73 65 20 50 4d 41 73 0a hem. These PMAs.
6420: 20 20 20 20 20 20 2a 2a 20 61 72 65 20 6d 65 72 ** are mer
6430: 67 65 64 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c ged into a singl
6440: 65 20 50 4d 41 20 74 68 61 74 20 69 73 20 77 72 e PMA that is wr
6450: 69 74 74 65 6e 20 74 6f 20 66 69 6c 65 20 70 54 itten to file pT
6460: 65 6d 70 32 2e 0a 20 20 20 20 20 20 2a 2f 0a 20 emp2.. */.
6470: 20 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f rc = vdbeSo
6480: 72 74 65 72 49 6e 69 74 4d 65 72 67 65 28 64 62 rterInitMerge(db
6490: 2c 20 70 43 73 72 2c 20 26 6e 57 72 69 74 65 29 , pCsr, &nWrite)
64a0: 3b 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20 ;. assert(
64b0: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c rc!=SQLITE_OK ||
64c0: 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b pSorter->aIter[
64d0: 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b pSorter->aTree[
64e0: 31 5d 20 5d 2e 70 46 69 6c 65 20 29 3b 0a 20 20 1] ].pFile );.
64f0: 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49 if( rc!=SQLI
6500: 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 TE_OK || pSorter
6510: 2d 3e 6e 50 4d 41 3c 3d 53 4f 52 54 45 52 5f 4d ->nPMA<=SORTER_M
6520: 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 20 29 AX_MERGE_COUNT )
6530: 7b 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b {. break;
6540: 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 . }..
6550: 2f 2a 20 4f 70 65 6e 20 74 68 65 20 73 65 63 6f /* Open the seco
6560: 6e 64 20 74 65 6d 70 20 66 69 6c 65 2c 20 69 66 nd temp file, if
6570: 20 69 74 20 69 73 20 6e 6f 74 20 61 6c 72 65 61 it is not alrea
6580: 64 79 20 6f 70 65 6e 2e 20 2a 2f 0a 20 20 20 20 dy open. */.
6590: 20 20 69 66 28 20 70 54 65 6d 70 32 3d 3d 30 20 if( pTemp2==0
65a0: 29 7b 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 ){. asser
65b0: 74 28 20 69 57 72 69 74 65 32 3d 3d 30 20 29 3b t( iWrite2==0 );
65c0: 0a 20 20 20 20 20 20 20 20 72 63 20 3d 20 76 64 . rc = vd
65d0: 62 65 53 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70 beSorterOpenTemp
65e0: 46 69 6c 65 28 64 62 2c 20 26 70 54 65 6d 70 32 File(db, &pTemp2
65f0: 29 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 );. }..
6600: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 if( rc==SQLITE
6610: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 72 _OK ){. r
6620: 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 57 72 c = vdbeSorterWr
6630: 69 74 65 56 61 72 69 6e 74 28 70 54 65 6d 70 32 iteVarint(pTemp2
6640: 2c 20 6e 57 72 69 74 65 2c 20 26 69 57 72 69 74 , nWrite, &iWrit
6650: 65 32 29 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20 e2);. }..
6660: 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 if( rc==SQLI
6670: 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20 TE_OK ){.
6680: 20 69 6e 74 20 62 45 6f 66 20 3d 20 30 3b 0a 20 int bEof = 0;.
6690: 20 20 20 20 20 20 20 77 68 69 6c 65 28 20 72 63 while( rc
66a0: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 62 ==SQLITE_OK && b
66b0: 45 6f 66 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 Eof==0 ){.
66c0: 20 20 20 20 69 6e 74 20 6e 54 6f 57 72 69 74 65 int nToWrite
66d0: 3b 0a 20 20 20 20 20 20 20 20 20 20 56 64 62 65 ;. Vdbe
66e0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65 SorterIter *pIte
66f0: 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 49 r = &pSorter->aI
6700: 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61 54 ter[ pSorter->aT
6710: 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 20 20 20 20 ree[1] ];.
6720: 20 20 20 20 61 73 73 65 72 74 28 20 70 49 74 65 assert( pIte
6730: 72 2d 3e 70 46 69 6c 65 20 29 3b 0a 20 20 20 20 r->pFile );.
6740: 20 20 20 20 20 20 6e 54 6f 57 72 69 74 65 20 3d nToWrite =
6750: 20 70 49 74 65 72 2d 3e 6e 4b 65 79 20 2b 20 73 pIter->nKey + s
6760: 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28 qlite3VarintLen(
6770: 70 49 74 65 72 2d 3e 6e 4b 65 79 29 3b 0a 20 20 pIter->nKey);.
6780: 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c rc = sql
6790: 69 74 65 33 4f 73 57 72 69 74 65 28 70 54 65 6d ite3OsWrite(pTem
67a0: 70 32 2c 20 70 49 74 65 72 2d 3e 61 41 6c 6c 6f p2, pIter->aAllo
67b0: 63 2c 20 6e 54 6f 57 72 69 74 65 2c 20 69 57 72 c, nToWrite, iWr
67c0: 69 74 65 32 29 3b 0a 20 20 20 20 20 20 20 20 20 ite2);.
67d0: 20 69 57 72 69 74 65 32 20 2b 3d 20 6e 54 6f 57 iWrite2 += nToW
67e0: 72 69 74 65 3b 0a 20 20 20 20 20 20 20 20 20 20 rite;.
67f0: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f if( rc==SQLITE_O
6800: 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 20 K ){.
6810: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 56 64 62 rc = sqlite3Vdb
6820: 65 53 6f 72 74 65 72 4e 65 78 74 28 64 62 2c 20 eSorterNext(db,
6830: 70 43 73 72 2c 20 26 62 45 6f 66 29 3b 0a 20 20 pCsr, &bEof);.
6840: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
6850: 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 }. }.
6860: 7d 0a 0a 20 20 20 20 69 66 28 20 70 53 6f 72 74 }.. if( pSort
6870: 65 72 2d 3e 6e 50 4d 41 3c 3d 53 4f 52 54 45 52 er->nPMA<=SORTER
6880: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 _MAX_MERGE_COUNT
6890: 20 29 7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b ){. break;
68a0: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 . }else{.
68b0: 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a sqlite3_file *
68c0: 70 54 6d 70 20 3d 20 70 53 6f 72 74 65 72 2d 3e pTmp = pSorter->
68d0: 70 54 65 6d 70 31 3b 0a 20 20 20 20 20 20 70 53 pTemp1;. pS
68e0: 6f 72 74 65 72 2d 3e 6e 50 4d 41 20 3d 20 69 4e orter->nPMA = iN
68f0: 65 77 3b 0a 20 20 20 20 20 20 70 53 6f 72 74 65 ew;. pSorte
6900: 72 2d 3e 70 54 65 6d 70 31 20 3d 20 70 54 65 6d r->pTemp1 = pTem
6910: 70 32 3b 0a 20 20 20 20 20 20 70 54 65 6d 70 32 p2;. pTemp2
6920: 20 3d 20 70 54 6d 70 3b 0a 20 20 20 20 20 20 70 = pTmp;. p
6930: 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 Sorter->iWriteOf
6940: 66 20 3d 20 69 57 72 69 74 65 32 3b 0a 20 20 20 f = iWrite2;.
6950: 20 20 20 70 53 6f 72 74 65 72 2d 3e 69 52 65 61 pSorter->iRea
6960: 64 4f 66 66 20 3d 20 30 3b 0a 20 20 20 20 20 20 dOff = 0;.
6970: 69 57 72 69 74 65 32 20 3d 20 30 3b 0a 20 20 20 iWrite2 = 0;.
6980: 20 7d 0a 20 20 7d 77 68 69 6c 65 28 20 72 63 3d }. }while( rc=
6990: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 3b 0a 0a 20 =SQLITE_OK );..
69a0: 20 69 66 28 20 70 54 65 6d 70 32 20 29 7b 0a 20 if( pTemp2 ){.
69b0: 20 20 20 73 71 6c 69 74 65 33 4f 73 43 6c 6f 73 sqlite3OsClos
69c0: 65 46 72 65 65 28 70 54 65 6d 70 32 29 3b 0a 20 eFree(pTemp2);.
69d0: 20 7d 0a 20 20 2a 70 62 45 6f 66 20 3d 20 28 70 }. *pbEof = (p
69e0: 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b 70 53 Sorter->aIter[pS
69f0: 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31 5d 5d orter->aTree[1]]
6a00: 2e 70 46 69 6c 65 3d 3d 30 29 3b 0a 20 20 72 65 .pFile==0);. re
6a10: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a turn rc;.}../*.*
6a20: 2a 20 41 64 76 61 6e 63 65 20 74 6f 20 74 68 65 * Advance to the
6a30: 20 6e 65 78 74 20 65 6c 65 6d 65 6e 74 20 69 6e next element in
6a40: 20 74 68 65 20 73 6f 72 74 65 72 2e 0a 2a 2f 0a the sorter..*/.
6a50: 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65 53 int sqlite3VdbeS
6a60: 6f 72 74 65 72 4e 65 78 74 28 73 71 6c 69 74 65 orterNext(sqlite
6a70: 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73 6f 3 *db, VdbeCurso
6a80: 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 2a 70 62 r *pCsr, int *pb
6a90: 45 6f 66 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 Eof){. VdbeSort
6aa0: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 er *pSorter = pC
6ab0: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 sr->pSorter;. i
6ac0: 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20 20 20 nt rc;
6ad0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
6ae0: 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f * Return code */
6af0: 0a 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d .. if( pSorter-
6b00: 3e 61 54 72 65 65 20 29 7b 0a 20 20 20 20 69 6e >aTree ){. in
6b10: 74 20 69 50 72 65 76 20 3d 20 70 53 6f 72 74 65 t iPrev = pSorte
6b20: 72 2d 3e 61 54 72 65 65 5b 31 5d 3b 2f 2a 20 49 r->aTree[1];/* I
6b30: 6e 64 65 78 20 6f 66 20 69 74 65 72 61 74 6f 72 ndex of iterator
6b40: 20 74 6f 20 61 64 76 61 6e 63 65 20 2a 2f 0a 20 to advance */.
6b50: 20 20 20 69 6e 74 20 69 3b 20 20 20 20 20 20 20 int i;
6b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
6b70: 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 61 54 72 /* Index of aTr
6b80: 65 65 5b 5d 20 74 6f 20 72 65 63 61 6c 63 75 6c ee[] to recalcul
6b90: 61 74 65 20 2a 2f 0a 0a 20 20 20 20 72 63 20 3d ate */.. rc =
6ba0: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 4e vdbeSorterIterN
6bb0: 65 78 74 28 64 62 2c 20 26 70 53 6f 72 74 65 72 ext(db, &pSorter
6bc0: 2d 3e 61 49 74 65 72 5b 69 50 72 65 76 5d 29 3b ->aIter[iPrev]);
6bd0: 0a 20 20 20 20 66 6f 72 28 69 3d 28 70 53 6f 72 . for(i=(pSor
6be0: 74 65 72 2d 3e 6e 54 72 65 65 2b 69 50 72 65 76 ter->nTree+iPrev
6bf0: 29 2f 32 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f )/2; rc==SQLITE_
6c00: 4f 4b 20 26 26 20 69 3e 30 3b 20 69 3d 69 2f 32 OK && i>0; i=i/2
6c10: 29 7b 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64 ){. rc = vd
6c20: 62 65 53 6f 72 74 65 72 44 6f 43 6f 6d 70 61 72 beSorterDoCompar
6c30: 65 28 70 43 73 72 2c 20 69 29 3b 0a 20 20 20 20 e(pCsr, i);.
6c40: 7d 0a 0a 20 20 20 20 2a 70 62 45 6f 66 20 3d 20 }.. *pbEof =
6c50: 28 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b (pSorter->aIter[
6c60: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31 pSorter->aTree[1
6c70: 5d 5d 2e 70 46 69 6c 65 3d 3d 30 29 3b 0a 20 20 ]].pFile==0);.
6c80: 7d 65 6c 73 65 7b 0a 20 20 20 20 53 6f 72 74 65 }else{. Sorte
6c90: 72 52 65 63 6f 72 64 20 2a 70 46 72 65 65 20 3d rRecord *pFree =
6ca0: 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 pSorter->pRecor
6cb0: 64 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d 3e d;. pSorter->
6cc0: 70 52 65 63 6f 72 64 20 3d 20 70 46 72 65 65 2d pRecord = pFree-
6cd0: 3e 70 4e 65 78 74 3b 0a 20 20 20 20 70 46 72 65 >pNext;. pFre
6ce0: 65 2d 3e 70 4e 65 78 74 20 3d 20 30 3b 0a 20 20 e->pNext = 0;.
6cf0: 20 20 76 64 62 65 53 6f 72 74 65 72 52 65 63 6f vdbeSorterReco
6d00: 72 64 46 72 65 65 28 64 62 2c 20 70 46 72 65 65 rdFree(db, pFree
6d10: 29 3b 0a 20 20 20 20 2a 70 62 45 6f 66 20 3d 20 );. *pbEof =
6d20: 21 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 !pSorter->pRecor
6d30: 64 3b 0a 20 20 20 20 72 63 20 3d 20 53 51 4c 49 d;. rc = SQLI
6d40: 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 20 20 72 65 74 TE_OK;. }. ret
6d50: 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a urn rc;.}../*.**
6d60: 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 Return a pointe
6d70: 72 20 74 6f 20 61 20 62 75 66 66 65 72 20 6f 77 r to a buffer ow
6d80: 6e 65 64 20 62 79 20 74 68 65 20 73 6f 72 74 65 ned by the sorte
6d90: 72 20 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20 r that contains
6da0: 74 68 65 20 0a 2a 2a 20 63 75 72 72 65 6e 74 20 the .** current
6db0: 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 key..*/.static v
6dc0: 6f 69 64 20 2a 76 64 62 65 53 6f 72 74 65 72 52 oid *vdbeSorterR
6dd0: 6f 77 6b 65 79 28 0a 20 20 56 64 62 65 53 6f 72 owkey(. VdbeSor
6de0: 74 65 72 20 2a 70 53 6f 72 74 65 72 2c 20 20 20 ter *pSorter,
6df0: 20 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 /* Sort
6e00: 65 72 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 69 er object */. i
6e10: 6e 74 20 2a 70 6e 4b 65 79 20 20 20 20 20 20 20 nt *pnKey
6e20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f /
6e30: 2a 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66 20 63 * OUT: Size of c
6e40: 75 72 72 65 6e 74 20 6b 65 79 20 69 6e 20 62 79 urrent key in by
6e50: 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 76 6f 69 64 tes */.){. void
6e60: 20 2a 70 4b 65 79 3b 0a 20 20 69 66 28 20 70 53 *pKey;. if( pS
6e70: 6f 72 74 65 72 2d 3e 61 54 72 65 65 20 29 7b 0a orter->aTree ){.
6e80: 20 20 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 VdbeSorterIt
6e90: 65 72 20 2a 70 49 74 65 72 3b 0a 20 20 20 20 70 er *pIter;. p
6ea0: 49 74 65 72 20 3d 20 26 70 53 6f 72 74 65 72 2d Iter = &pSorter-
6eb0: 3e 61 49 74 65 72 5b 20 70 53 6f 72 74 65 72 2d >aIter[ pSorter-
6ec0: 3e 61 54 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 20 >aTree[1] ];.
6ed0: 20 2a 70 6e 4b 65 79 20 3d 20 70 49 74 65 72 2d *pnKey = pIter-
6ee0: 3e 6e 4b 65 79 3b 0a 20 20 20 20 70 4b 65 79 20 >nKey;. pKey
6ef0: 3d 20 70 49 74 65 72 2d 3e 61 4b 65 79 3b 0a 20 = pIter->aKey;.
6f00: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 6e 4b }else{. *pnK
6f10: 65 79 20 3d 20 70 53 6f 72 74 65 72 2d 3e 70 52 ey = pSorter->pR
6f20: 65 63 6f 72 64 2d 3e 6e 56 61 6c 3b 0a 20 20 20 ecord->nVal;.
6f30: 20 70 4b 65 79 20 3d 20 70 53 6f 72 74 65 72 2d pKey = pSorter-
6f40: 3e 70 52 65 63 6f 72 64 2d 3e 70 56 61 6c 3b 0a >pRecord->pVal;.
6f50: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 4b 65 }. return pKe
6f60: 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 70 79 y;.}../*.** Copy
6f70: 20 74 68 65 20 63 75 72 72 65 6e 74 20 73 6f 72 the current sor
6f80: 74 65 72 20 6b 65 79 20 69 6e 74 6f 20 74 68 65 ter key into the
6f90: 20 6d 65 6d 6f 72 79 20 63 65 6c 6c 20 70 4f 75 memory cell pOu
6fa0: 74 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 t..*/.int sqlite
6fb0: 33 56 64 62 65 53 6f 72 74 65 72 52 6f 77 6b 65 3VdbeSorterRowke
6fc0: 79 28 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 y(VdbeCursor *pC
6fd0: 73 72 2c 20 4d 65 6d 20 2a 70 4f 75 74 29 7b 0a sr, Mem *pOut){.
6fe0: 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 VdbeSorter *pS
6ff0: 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 orter = pCsr->pS
7000: 6f 72 74 65 72 3b 0a 20 20 76 6f 69 64 20 2a 70 orter;. void *p
7010: 4b 65 79 3b 20 69 6e 74 20 6e 4b 65 79 3b 20 20 Key; int nKey;
7020: 20 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 /* Sort
7030: 65 72 20 6b 65 79 20 74 6f 20 63 6f 70 79 20 69 er key to copy i
7040: 6e 74 6f 20 70 4f 75 74 20 2a 2f 0a 0a 20 20 70 nto pOut */.. p
7050: 4b 65 79 20 3d 20 76 64 62 65 53 6f 72 74 65 72 Key = vdbeSorter
7060: 52 6f 77 6b 65 79 28 70 53 6f 72 74 65 72 2c 20 Rowkey(pSorter,
7070: 26 6e 4b 65 79 29 3b 0a 20 20 69 66 28 20 73 71 &nKey);. if( sq
7080: 6c 69 74 65 33 56 64 62 65 4d 65 6d 47 72 6f 77 lite3VdbeMemGrow
7090: 28 70 4f 75 74 2c 20 6e 4b 65 79 2c 20 30 29 20 (pOut, nKey, 0)
70a0: 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 53 51 ){. return SQ
70b0: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 0a LITE_NOMEM;. }.
70c0: 20 20 70 4f 75 74 2d 3e 6e 20 3d 20 6e 4b 65 79 pOut->n = nKey
70d0: 3b 0a 20 20 4d 65 6d 53 65 74 54 79 70 65 46 6c ;. MemSetTypeFl
70e0: 61 67 28 70 4f 75 74 2c 20 4d 45 4d 5f 42 6c 6f ag(pOut, MEM_Blo
70f0: 62 29 3b 0a 20 20 6d 65 6d 63 70 79 28 70 4f 75 b);. memcpy(pOu
7100: 74 2d 3e 7a 2c 20 70 4b 65 79 2c 20 6e 4b 65 79 t->z, pKey, nKey
7110: 29 3b 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c );.. return SQL
7120: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a ITE_OK;.}../*.**
7130: 20 43 6f 6d 70 61 72 65 20 74 68 65 20 6b 65 79 Compare the key
7140: 20 69 6e 20 6d 65 6d 6f 72 79 20 63 65 6c 6c 20 in memory cell
7150: 70 56 61 6c 20 77 69 74 68 20 74 68 65 20 6b 65 pVal with the ke
7160: 79 20 74 68 61 74 20 74 68 65 20 73 6f 72 74 65 y that the sorte
7170: 72 20 63 75 72 73 6f 72 0a 2a 2a 20 70 61 73 73 r cursor.** pass
7180: 65 64 20 61 73 20 74 68 65 20 66 69 72 73 74 20 ed as the first
7190: 61 72 67 75 6d 65 6e 74 20 63 75 72 72 65 6e 74 argument current
71a0: 6c 79 20 70 6f 69 6e 74 73 20 74 6f 2e 20 46 6f ly points to. Fo
71b0: 72 20 74 68 65 20 70 75 72 70 6f 73 65 73 20 6f r the purposes o
71c0: 66 0a 2a 2a 20 74 68 65 20 63 6f 6d 70 61 72 69 f.** the compari
71d0: 73 6f 6e 2c 20 69 67 6e 6f 72 65 20 74 68 65 20 son, ignore the
71e0: 72 6f 77 69 64 20 66 69 65 6c 64 20 61 74 20 74 rowid field at t
71f0: 68 65 20 65 6e 64 20 6f 66 20 65 61 63 68 20 72 he end of each r
7200: 65 63 6f 72 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 ecord..**.** If
7210: 61 6e 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2c an error occurs,
7220: 20 72 65 74 75 72 6e 20 61 6e 20 53 51 4c 69 74 return an SQLit
7230: 65 20 65 72 72 6f 72 20 63 6f 64 65 20 28 69 2e e error code (i.
7240: 65 2e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 29 e. SQLITE_NOMEM)
7250: 2e 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 ..** Otherwise,
7260: 73 65 74 20 2a 70 52 65 73 20 74 6f 20 61 20 6e set *pRes to a n
7270: 65 67 61 74 69 76 65 2c 20 7a 65 72 6f 20 6f 72 egative, zero or
7280: 20 70 6f 73 69 74 69 76 65 20 76 61 6c 75 65 20 positive value
7290: 69 66 20 74 68 65 0a 2a 2a 20 6b 65 79 20 69 6e if the.** key in
72a0: 20 70 56 61 6c 20 69 73 20 73 6d 61 6c 6c 65 72 pVal is smaller
72b0: 20 74 68 61 6e 2c 20 65 71 75 61 6c 20 74 6f 20 than, equal to
72c0: 6f 72 20 6c 61 72 67 65 72 20 74 68 61 6e 20 74 or larger than t
72d0: 68 65 20 63 75 72 72 65 6e 74 20 73 6f 72 74 65 he current sorte
72e0: 72 0a 2a 2a 20 6b 65 79 2e 0a 2a 2f 0a 69 6e 74 r.** key..*/.int
72f0: 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 sqlite3VdbeSort
7300: 65 72 43 6f 6d 70 61 72 65 28 0a 20 20 56 64 62 erCompare(. Vdb
7310: 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 20 eCursor *pCsr,
7320: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
7330: 53 6f 72 74 65 72 20 63 75 72 73 6f 72 20 2a 2f Sorter cursor */
7340: 0a 20 20 4d 65 6d 20 2a 70 56 61 6c 2c 20 20 20 . Mem *pVal,
7350: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
7360: 20 20 20 2f 2a 20 56 61 6c 75 65 20 74 6f 20 63 /* Value to c
7370: 6f 6d 70 61 72 65 20 74 6f 20 63 75 72 72 65 6e ompare to curren
7380: 74 20 73 6f 72 74 65 72 20 6b 65 79 20 2a 2f 0a t sorter key */.
7390: 20 20 69 6e 74 20 2a 70 52 65 73 20 20 20 20 20 int *pRes
73a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
73b0: 20 20 2f 2a 20 4f 55 54 3a 20 52 65 73 75 6c 74 /* OUT: Result
73c0: 20 6f 66 20 63 6f 6d 70 61 72 69 73 6f 6e 20 2a of comparison *
73d0: 2f 0a 29 7b 0a 20 20 69 6e 74 20 72 63 3b 0a 20 /.){. int rc;.
73e0: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f VdbeSorter *pSo
73f0: 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f rter = pCsr->pSo
7400: 72 74 65 72 3b 0a 20 20 76 6f 69 64 20 2a 70 4b rter;. void *pK
7410: 65 79 3b 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 ey; int nKey;
7420: 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 65 /* Sorte
7430: 72 20 6b 65 79 20 74 6f 20 63 6f 6d 70 61 72 65 r key to compare
7440: 20 70 56 61 6c 20 77 69 74 68 20 2a 2f 0a 0a 20 pVal with */..
7450: 20 70 4b 65 79 20 3d 20 76 64 62 65 53 6f 72 74 pKey = vdbeSort
7460: 65 72 52 6f 77 6b 65 79 28 70 53 6f 72 74 65 72 erRowkey(pSorter
7470: 2c 20 26 6e 4b 65 79 29 3b 0a 20 20 72 63 20 3d , &nKey);. rc =
7480: 20 76 64 62 65 53 6f 72 74 65 72 43 6f 6d 70 61 vdbeSorterCompa
7490: 72 65 28 70 43 73 72 2c 20 31 2c 20 70 56 61 6c re(pCsr, 1, pVal
74a0: 2d 3e 7a 2c 20 70 56 61 6c 2d 3e 6e 2c 20 70 4b ->z, pVal->n, pK
74b0: 65 79 2c 20 6e 4b 65 79 2c 20 70 52 65 73 29 3b ey, nKey, pRes);
74c0: 0a 20 20 61 73 73 65 72 74 28 20 72 63 21 3d 53 . assert( rc!=S
74d0: 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 70 56 61 6c QLITE_OK || pVal
74e0: 2d 3e 64 62 2d 3e 6d 61 6c 6c 6f 63 46 61 69 6c ->db->mallocFail
74f0: 65 64 20 7c 7c 20 28 2a 70 52 65 73 29 3c 3d 30 ed || (*pRes)<=0
7500: 20 29 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b );. return rc;
7510: 0a 7d 0a 0a 23 65 6e 64 69 66 20 2f 2a 20 23 69 .}..#endif /* #i
7520: 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 fndef SQLITE_OMI
7530: 54 5f 4d 45 52 47 45 5f 53 4f 52 54 20 2a 2f 0a T_MERGE_SORT */.