/ Hex Artifact Content
Login

Artifact 4f3265707c3277011fbb0c09d3d8e6461152f639:


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 */.