/ Check-in [45847390]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix for ticket #142: Make sure we get the correct sort order even when the columns being sorted contain NULLs. (CVS 730)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:45847390d007718a4b7a4e9fa445136d013113f8
User & Date: drh 2002-08-26 19:55:08
Context
2002-08-27
14:28
Change the tokenizer to ignore C-style comments /*...*/ in accordance with SQL99. (CVS 731) check-in: f1534489 user: drh tags: trunk
2002-08-26
19:55
Fix for ticket #142: Make sure we get the correct sort order even when the columns being sorted contain NULLs. (CVS 730) check-in: 45847390 user: drh tags: trunk
2002-08-25
20:58
Version 2.7.0 (CVS 729) check-in: 9e341d9c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/util.c.

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
705
706
707
708
709
710
711




712
713
714
715
716
717
718
...
740
741
742
743
744
745
746

747
748

749




750

751
752
753

754

755
756

757
758
759
760
761
762
763
764
...
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.49 2002/08/25 18:29:12 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................

/*
** This routine is used for sorting.  Each key is a list of one or more
** null-terminated elements.  The list is terminated by two nulls in
** a row.  For example, the following text is a key with three elements
**
**            Aone\000Dtwo\000Athree\000\000




**
** Both arguments will have the same number of elements.  This routine
** returns negative, zero, or positive if the first argument is less
** than, equal to, or greater than the first.  (Result is a-b).
**
** Each element begins with one of the characters "+", "-", "A", "D".
** This character determines the sort order and collating sequence:
................................................................................
** of expressions and for indices.  This was not the case for version
** 2.6.3 and earlier.
*/
int sqliteSortCompare(const char *a, const char *b){
  int len;
  int res = 0;
  int isNumA, isNumB;


  while( res==0 && *a && *b ){

    assert( a[0]==b[0] );




    if( a[1]==0 ){

      res = -1;
      break;
    }else if( b[1]==0 ){

      res = +1;

      break;
    }

    if( a[0]=='A' || a[0]=='D' ){
      res = strcmp(&a[1],&b[1]);
      if( res ) break;
    }else{
      isNumA = sqliteIsNumber(&a[1]);
      isNumB = sqliteIsNumber(&b[1]);
      if( isNumA ){
        double rA, rB;
................................................................................
        if( res ) break;
      }
    }
    len = strlen(&a[1]) + 2;
    a += len;
    b += len;
  }
  if( *a=='-' || *a=='D' ) res = -res;
  return res;
}

/*
** Some powers of 64.  These constants are needed in the
** sqliteRealToSortable() routine below.
*/







|







 







>
>
>
>







 







>


>
|
>
>
>
>
|
>
|
<
|
>
|
>


>
|







 







|







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
...
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762

763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
...
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.50 2002/08/26 19:55:08 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................

/*
** This routine is used for sorting.  Each key is a list of one or more
** null-terminated elements.  The list is terminated by two nulls in
** a row.  For example, the following text is a key with three elements
**
**            Aone\000Dtwo\000Athree\000\000
**
** All elements begin with one of the characters "+-AD" and end with "\000"
** with zero or more text elements in between.  Except, NULL elements
** consist of the special two-character sequence "N\000".
**
** Both arguments will have the same number of elements.  This routine
** returns negative, zero, or positive if the first argument is less
** than, equal to, or greater than the first.  (Result is a-b).
**
** Each element begins with one of the characters "+", "-", "A", "D".
** This character determines the sort order and collating sequence:
................................................................................
** of expressions and for indices.  This was not the case for version
** 2.6.3 and earlier.
*/
int sqliteSortCompare(const char *a, const char *b){
  int len;
  int res = 0;
  int isNumA, isNumB;
  int dir;

  while( res==0 && *a && *b ){
    if( a[0]=='N' || b[0]=='N' ){
      if( a[0]==b[0] ){
        a += 2;
        b += 2;
        continue;
      }
      if( a[0]=='N' ){
        dir = b[0];
        res = -1;

      }else{
        dir = a[0];
        res = +1;
      }
      break;
    }
    assert( a[0]==b[0] );
    if( (dir=a[0])=='A' || a[0]=='D' ){
      res = strcmp(&a[1],&b[1]);
      if( res ) break;
    }else{
      isNumA = sqliteIsNumber(&a[1]);
      isNumB = sqliteIsNumber(&b[1]);
      if( isNumA ){
        double rA, rB;
................................................................................
        if( res ) break;
      }
    }
    len = strlen(&a[1]) + 2;
    a += len;
    b += len;
  }
  if( dir=='-' || dir=='D' ) res = -res;
  return res;
}

/*
** Some powers of 64.  These constants are needed in the
** sqliteRealToSortable() routine below.
*/

Changes to src/vdbe.c.

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
....
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399


4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412



4413
4414

4415
4416
4417
4418
4419
4420





4421
4422
4423
4424

4425
4426
4427
4428
4429
4430
4431
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.171 2002/08/25 19:20:40 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test
................................................................................

/* Opcode: SortMakeKey * * P3
**
** Convert the top few entries of the stack into a sort key.  The
** number of stack entries consumed is the number of characters in 
** the string P3.  One character from P3 is prepended to each entry.
** The first character of P3 is prepended to the element lowest in
** the stack and the last character of P3 is appended to the top of
** the stack.  All stack entries are separated by a \000 character
** in the result.  The whole key is terminated by two \000 characters
** in a row.


**
** See also the MakeKey and MakeIdxKey opcodes.
*/
case OP_SortMakeKey: {
  char *zNewKey;
  int nByte;
  int nField;
  int i, j, k;

  nField = strlen(pOp->p3);
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 1;
  for(i=p->tos-nField+1; i<=p->tos; i++){



    if( Stringify(p, i) ) goto no_mem;
    nByte += aStack[i].n+2;

  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  k = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){





    zNewKey[j++] = pOp->p3[k++];
    memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
    j += aStack[i].n-1;
    zNewKey[j++] = 0;

  }
  zNewKey[j] = 0;
  assert( j<nByte );
  PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;







|







 







|



>
>













>
>
>
|
|
>






>
>
>
>
>
|
|
|
|
>







26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
....
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.172 2002/08/26 19:55:08 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_MoveTo or the OP_Next opcode.  The test
................................................................................

/* Opcode: SortMakeKey * * P3
**
** Convert the top few entries of the stack into a sort key.  The
** number of stack entries consumed is the number of characters in 
** the string P3.  One character from P3 is prepended to each entry.
** The first character of P3 is prepended to the element lowest in
** the stack and the last character of P3 is prepended to the top of
** the stack.  All stack entries are separated by a \000 character
** in the result.  The whole key is terminated by two \000 characters
** in a row.
**
** "N" is substituted in place of the P3 character for NULL values.
**
** See also the MakeKey and MakeIdxKey opcodes.
*/
case OP_SortMakeKey: {
  char *zNewKey;
  int nByte;
  int nField;
  int i, j, k;

  nField = strlen(pOp->p3);
  VERIFY( if( p->tos+1<nField ) goto not_enough_stack; )
  nByte = 1;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)!=0 ){
      nByte += 2;
    }else{
      if( Stringify(p, i) ) goto no_mem;
      nByte += aStack[i].n+2;
    }
  }
  zNewKey = sqliteMalloc( nByte );
  if( zNewKey==0 ) goto no_mem;
  j = 0;
  k = 0;
  for(i=p->tos-nField+1; i<=p->tos; i++){
    if( (aStack[i].flags & STK_Null)!=0 ){
      zNewKey[j++] = 'N';
      zNewKey[j++] = 0;
      k++;
    }else{
      zNewKey[j++] = pOp->p3[k++];
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
      zNewKey[j++] = 0;
    }
  }
  zNewKey[j] = 0;
  assert( j<nByte );
  PopStack(p, nField);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;

Changes to test/sort.test.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
213
214
215
216
217
218
219










220




221


































222
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the CREATE TABLE statement.
#
# $Id: sort.test,v 1.6 2002/08/14 12:56:56 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a bunch of data to sort against
#
do_test sort-1.0 {
................................................................................
} {-123 -2.15 -2b -3.141592653 -4.0e9 -4221 0.0013442 01234567890123456789 1.6 11 2.7 5.0e10}
#do_test sort-4.9 {
#  execsql {
#    SELECT substr(v,2,99)+0.0 FROM t1 ORDER BY 1;
#  }
#} {-4000000000 -4221 -123 -3.141592653 -2.15 -2 0.0013442 1.6 2.7 11 50000000000 1.23456789012346e+18}



















































finish_test







|







 







>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the CREATE TABLE statement.
#
# $Id: sort.test,v 1.7 2002/08/26 19:55:11 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a bunch of data to sort against
#
do_test sort-1.0 {
................................................................................
} {-123 -2.15 -2b -3.141592653 -4.0e9 -4221 0.0013442 01234567890123456789 1.6 11 2.7 5.0e10}
#do_test sort-4.9 {
#  execsql {
#    SELECT substr(v,2,99)+0.0 FROM t1 ORDER BY 1;
#  }
#} {-4000000000 -4221 -123 -3.141592653 -2.15 -2 0.0013442 1.6 2.7 11 50000000000 1.23456789012346e+18}

do_test sort-5.1 {
  execsql {
    create table t3(a,b);
    insert into t3 values(5,NULL);
    insert into t3 values(6,NULL);
    insert into t3 values(3,NULL);
    insert into t3 values(4,'cd');
    insert into t3 values(1,'ab');
    insert into t3 values(2,NULL);
    select a from t3 order by b, a;
  }
} {2 3 5 6 1 4}
do_test sort-5.2 {
  execsql {
    select a from t3 order by b, a desc;
  }
} {6 5 3 2 1 4}
do_test sort-5.3 {
  execsql {
    select a from t3 order by b desc, a;
  }
} {4 1 2 3 5 6}
do_test sort-5.4 {
  execsql {
    select a from t3 order by b desc, a desc;
  }
} {4 1 6 5 3 2}

do_test sort-6.1 {
  execsql {
    create index i3 on t3(b,a);
    select a from t3 order by b, a;
  }
} {2 3 5 6 1 4}
do_test sort-6.2 {
  execsql {
    select a from t3 order by b, a desc;
  }
} {6 5 3 2 1 4}
do_test sort-6.3 {
  execsql {
    select a from t3 order by b desc, a;
  }
} {4 1 2 3 5 6}
do_test sort-6.4 {
  execsql {
    select a from t3 order by b desc, a desc;
  }
} {4 1 6 5 3 2}

finish_test