/ Check-in [0736b7e8]
Login

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

Overview
Comment:Sorting bug fixes. Now only 17 tests fail. (CVS 1422)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 0736b7e8401f587f8b412602d029ef9bd69425f6
User & Date: drh 2004-05-21 01:29:06
Context
2004-05-21
01:47
Add new sqlite3_open() and sqlite3_open16() APIs. (CVS 1423) check-in: 307b5500 user: danielk1977 tags: trunk
01:29
Sorting bug fixes. Now only 17 tests fail. (CVS 1422) check-in: 0736b7e8 user: drh tags: trunk
2004-05-20
23:37
Fix a bug that prevented sorting by index. Down to 162 failed tests. (CVS 1421) check-in: b032b646 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/build.c.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.190 2004/05/20 22:16:29 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Check to see if the schema for the database needs
................................................................................
  pColl = sqlite3HashFind(&db->aCollSeq, zName, nName);
  if( pColl==0 ){
    pColl = sqliteMallocRaw( sizeof(*pColl) + nName + 1 );
    if( pColl==0 ){
      return 0;
    }
    pColl->zName = (char*)&pColl[1];
    pColl->reverseOrder = 0;
    memcpy(pColl->zName, zName, nName+1);
    sqlite3HashInsert(&db->aCollSeq, pColl->zName, nName, pColl);
  }
  pColl->pUser = pUser;
  pColl->xCmp = xCmp;
  return pColl;
}







|







 







<







19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
785
786
787
788
789
790
791

792
793
794
795
796
797
798
**     DROP INDEX
**     creating ID lists
**     BEGIN TRANSACTION
**     COMMIT
**     ROLLBACK
**     PRAGMA
**
** $Id: build.c,v 1.191 2004/05/21 01:29:06 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine is called when a new SQL statement is beginning to
** be parsed.  Check to see if the schema for the database needs
................................................................................
  pColl = sqlite3HashFind(&db->aCollSeq, zName, nName);
  if( pColl==0 ){
    pColl = sqliteMallocRaw( sizeof(*pColl) + nName + 1 );
    if( pColl==0 ){
      return 0;
    }
    pColl->zName = (char*)&pColl[1];

    memcpy(pColl->zName, zName, nName+1);
    sqlite3HashInsert(&db->aCollSeq, pColl->zName, nName, pColl);
  }
  pColl->pUser = pUser;
  pColl->xCmp = xCmp;
  return pColl;
}

Changes to src/select.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
314
315
316
317
318
319
320
321
322


323
324

325

326
327
328
329
330
331
332
333

334
335

336
337


338
339
340
341
342
343
344
...
537
538
539
540
541
542
543

544
545
546
547
548
549
550
551
552





553
554











555
556
557
558
559
560
561
....
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
....
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
....
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
....
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.171 2004/05/20 22:16:29 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
** FIX ME:  Change this so that it uses the OP_MakeKey opcode
** instead of OP_SortMakeKey.  Delete the OP_SortMakeKey opcode.
** All columns should have affinity NONE.  Handle ASC versus
** DESC sort order by defining a list of comparison functions to
** be used by the OP_Sort opcode.
*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){
  char *zSortOrder;
  int i;


  zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
  if( zSortOrder==0 ) return;

  for(i=0; i<pOrderBy->nExpr; i++){

    int order = pOrderBy->a[i].sortOrder;
    int c;
    if( order==SQLITE_SO_ASC ){
      c = 'A';
    }else{
      c = 'D';
    }
    zSortOrder[i] = c;

    sqlite3ExprCode(pParse, pOrderBy->a[i].pExpr);
  }

  zSortOrder[pOrderBy->nExpr] = 0;
  sqlite3VdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);


  sqlite3VdbeAddOp(v, OP_SortPut, 0, 0);
}

/*
** This routine generates the code for the inside of the inner loop
** of a SELECT.
**
................................................................................
/*
** If the inner loop was generated using a non-null pOrderBy argument,
** then the results were placed in a sorter.  After the loop is terminated
** we need to run the sorter and output the results.  The following
** routine generates the code needed to do that.
*/
static void generateSortTail(

  Select *p,       /* The SELECT statement */
  Vdbe *v,         /* Generate code into this VDBE */
  int nColumn,     /* Number of columns of data */
  int eDest,       /* Write the sorted results here */
  int iParm        /* Optional parameter associated with eDest */
){
  int end1 = sqlite3VdbeMakeLabel(v);
  int end2 = sqlite3VdbeMakeLabel(v);
  int addr;





  if( eDest==SRT_Sorter ) return;
  sqlite3VdbeAddOp(v, OP_Sort, 0, 0);











  addr = sqlite3VdbeAddOp(v, OP_SortNext, 0, end1);
  if( p->iOffset>=0 ){
    sqlite3VdbeAddOp(v, OP_MemIncr, p->iOffset, addr+4);
    sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
    sqlite3VdbeAddOp(v, OP_Goto, 0, addr);
  }
  if( p->iLimit>=0 ){
................................................................................

  pKeyInfo = sqliteMalloc( sizeof(*pKeyInfo)+nColumn*sizeof(CollSeq*) );
  if( pKeyInfo==0 ) return;
  pKeyInfo->nField = nColumn;
  for(i=0; i<nColumn; i++){
    pKeyInfo->aColl[i] = db->pDfltColl;
  }
  sqlite3VdbeOp3(v, OP_OpenTemp, iTab, 0, (char*)pKeyInfo, P3_KEYINFO);
  sqliteFree(pKeyInfo);
  if( keyAsData ){
    sqlite3VdbeAddOp(v, OP_KeyAsData, iTab, 1);
  }
}

/*
** This routine is called to process a query that is really the union
................................................................................
          goto multi_select_end;
        }
        sqlite3VdbeResolveLabel(v, iCont);
        sqlite3VdbeAddOp(v, OP_Next, unionTab, iStart);
        sqlite3VdbeResolveLabel(v, iBreak);
        sqlite3VdbeAddOp(v, OP_Close, unionTab, 0);
        if( p->pOrderBy ){
          generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
        }
      }
      break;
    }
    case TK_INTERSECT: {
      int tab1, tab2;
      int iCont, iBreak, iStart;
................................................................................
      }
      sqlite3VdbeResolveLabel(v, iCont);
      sqlite3VdbeAddOp(v, OP_Next, tab1, iStart);
      sqlite3VdbeResolveLabel(v, iBreak);
      sqlite3VdbeAddOp(v, OP_Close, tab2, 0);
      sqlite3VdbeAddOp(v, OP_Close, tab1, 0);
      if( p->pOrderBy ){
        generateSortTail(p, v, p->pEList->nExpr, eDest, iParm);
      }
      break;
    }
  }
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
    sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
................................................................................
    pParse->useAgg = 0;
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( pOrderBy ){
    generateSortTail(p, v, pEList->nExpr, eDest, iParm);
  }

  /* If this was a subquery, we have now converted the subquery into a
  ** temporary table.  So delete the subquery structure from the parent
  ** to prevent this subquery from being evaluated again and to force the
  ** the use of the temporary table.
  */







|







 







<

>
>


>

>








>


>


>
>







 







>









>
>
>
>
>

<
>
>
>
>
>
>
>
>
>
>
>







 







|
<







 







|







 







|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
314
315
316
317
318
319
320

321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
...
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566

567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
....
1233
1234
1235
1236
1237
1238
1239
1240

1241
1242
1243
1244
1245
1246
1247
....
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
....
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
....
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.172 2004/05/21 01:29:06 drh Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.
................................................................................
** FIX ME:  Change this so that it uses the OP_MakeKey opcode
** instead of OP_SortMakeKey.  Delete the OP_SortMakeKey opcode.
** All columns should have affinity NONE.  Handle ASC versus
** DESC sort order by defining a list of comparison functions to
** be used by the OP_Sort opcode.
*/
static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){

  int i;
#if 0
  char *zSortOrder;
  zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );
  if( zSortOrder==0 ) return;
#endif
  for(i=0; i<pOrderBy->nExpr; i++){
#if 0
    int order = pOrderBy->a[i].sortOrder;
    int c;
    if( order==SQLITE_SO_ASC ){
      c = 'A';
    }else{
      c = 'D';
    }
    zSortOrder[i] = c;
#endif
    sqlite3ExprCode(pParse, pOrderBy->a[i].pExpr);
  }
#if 0
  zSortOrder[pOrderBy->nExpr] = 0;
  sqlite3VdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);
#endif
  sqlite3VdbeAddOp(v, OP_MakeKey, pOrderBy->nExpr, 0);
  sqlite3VdbeAddOp(v, OP_SortPut, 0, 0);
}

/*
** This routine generates the code for the inside of the inner loop
** of a SELECT.
**
................................................................................
/*
** If the inner loop was generated using a non-null pOrderBy argument,
** then the results were placed in a sorter.  After the loop is terminated
** we need to run the sorter and output the results.  The following
** routine generates the code needed to do that.
*/
static void generateSortTail(
  Parse *pParse,   /* The parsing context */
  Select *p,       /* The SELECT statement */
  Vdbe *v,         /* Generate code into this VDBE */
  int nColumn,     /* Number of columns of data */
  int eDest,       /* Write the sorted results here */
  int iParm        /* Optional parameter associated with eDest */
){
  int end1 = sqlite3VdbeMakeLabel(v);
  int end2 = sqlite3VdbeMakeLabel(v);
  int addr;
  KeyInfo *pInfo;
  ExprList *pOrderBy;
  int nCol, i;
  sqlite *db = pParse->db;

  if( eDest==SRT_Sorter ) return;

  pOrderBy = p->pOrderBy;
  nCol = pOrderBy->nExpr;
  pInfo = sqliteMalloc( sizeof(*pInfo) + nCol*(sizeof(CollSeq*)+1) );
  if( pInfo==0 ) return;
  pInfo->aSortOrder = (char*)&pInfo->aColl[nCol];
  pInfo->nField = nCol;
  for(i=0; i<nCol; i++){
    pInfo->aColl[i] = db->pDfltColl;
    pInfo->aSortOrder[i] = pOrderBy->a[i].sortOrder;
  }
  sqlite3VdbeOp3(v, OP_Sort, 0, 0, (char*)pInfo, P3_KEYINFO_HANDOFF);
  addr = sqlite3VdbeAddOp(v, OP_SortNext, 0, end1);
  if( p->iOffset>=0 ){
    sqlite3VdbeAddOp(v, OP_MemIncr, p->iOffset, addr+4);
    sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
    sqlite3VdbeAddOp(v, OP_Goto, 0, addr);
  }
  if( p->iLimit>=0 ){
................................................................................

  pKeyInfo = sqliteMalloc( sizeof(*pKeyInfo)+nColumn*sizeof(CollSeq*) );
  if( pKeyInfo==0 ) return;
  pKeyInfo->nField = nColumn;
  for(i=0; i<nColumn; i++){
    pKeyInfo->aColl[i] = db->pDfltColl;
  }
  sqlite3VdbeOp3(v, OP_OpenTemp, iTab, 0, (char*)pKeyInfo, P3_KEYINFO_HANDOFF);

  if( keyAsData ){
    sqlite3VdbeAddOp(v, OP_KeyAsData, iTab, 1);
  }
}

/*
** This routine is called to process a query that is really the union
................................................................................
          goto multi_select_end;
        }
        sqlite3VdbeResolveLabel(v, iCont);
        sqlite3VdbeAddOp(v, OP_Next, unionTab, iStart);
        sqlite3VdbeResolveLabel(v, iBreak);
        sqlite3VdbeAddOp(v, OP_Close, unionTab, 0);
        if( p->pOrderBy ){
          generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm);
        }
      }
      break;
    }
    case TK_INTERSECT: {
      int tab1, tab2;
      int iCont, iBreak, iStart;
................................................................................
      }
      sqlite3VdbeResolveLabel(v, iCont);
      sqlite3VdbeAddOp(v, OP_Next, tab1, iStart);
      sqlite3VdbeResolveLabel(v, iBreak);
      sqlite3VdbeAddOp(v, OP_Close, tab2, 0);
      sqlite3VdbeAddOp(v, OP_Close, tab1, 0);
      if( p->pOrderBy ){
        generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm);
      }
      break;
    }
  }
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
    sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
................................................................................
    pParse->useAgg = 0;
  }

  /* If there is an ORDER BY clause, then we need to sort the results
  ** and send them to the callback one by one.
  */
  if( pOrderBy ){
    generateSortTail(pParse, p, v, pEList->nExpr, eDest, iParm);
  }

  /* If this was a subquery, we have now converted the subquery into a
  ** temporary table.  So delete the subquery structure from the parent
  ** to prevent this subquery from being evaluated again and to force the
  ** the use of the temporary table.
  */

Changes to src/sqliteInt.h.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
...
643
644
645
646
647
648
649

650
651
652
653
654
655
656
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.241 2004/05/20 22:16:30 drh Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "parse.h"
#include <stdio.h>
#include <stdlib.h>
................................................................................
**
** If CollSeq.xCmp is NULL, it means that the collating sequence is
** undefined.  Indices built on an undefined collating sequence may
** not be read or written.
*/
struct CollSeq {
  char *zName;         /* Name of the collating sequence */
  u8 reverseOrder;     /* Compare in reverse order.  Used by OP_Sort only */
  void *pUser;         /* First argument to xCmp() */
  int (*xCmp)(void*,int,const void*,int,const void*); /* Comparison function */
};

/*
** A sort order can be either ASC or DESC.
*/
................................................................................
**
** If the KeyInfo.incrKey value is true and the comparison would
** otherwise be equal, then return a result as if the second key larger.
*/
struct KeyInfo {
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */
  int nField;         /* Number of entries in aColl[] */

  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**







|







 







<







 







>







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
...
483
484
485
486
487
488
489

490
491
492
493
494
495
496
...
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.242 2004/05/21 01:29:06 drh Exp $
*/
#include "config.h"
#include "sqlite.h"
#include "hash.h"
#include "parse.h"
#include <stdio.h>
#include <stdlib.h>
................................................................................
**
** If CollSeq.xCmp is NULL, it means that the collating sequence is
** undefined.  Indices built on an undefined collating sequence may
** not be read or written.
*/
struct CollSeq {
  char *zName;         /* Name of the collating sequence */

  void *pUser;         /* First argument to xCmp() */
  int (*xCmp)(void*,int,const void*,int,const void*); /* Comparison function */
};

/*
** A sort order can be either ASC or DESC.
*/
................................................................................
**
** If the KeyInfo.incrKey value is true and the comparison would
** otherwise be equal, then return a result as if the second key larger.
*/
struct KeyInfo {
  u8 incrKey;         /* Increase 2nd key by epsilon before comparison */
  int nField;         /* Number of entries in aColl[] */
  u8 *aSortOrder;     /* If defined an aSortOrder[i] is true, sort DESC */
  CollSeq *aColl[1];  /* Collating sequence for each term of the key */
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
...
364
365
366
367
368
369
370
371
372
373
374
375
376


377
378
379
380
381
382
383
384
....
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300

4301
4302
4303

4304
4305
4306
4307
4308
4309
4310
....
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
....
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075


5076
5077
5078
5079
5080
5081
5082
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.309 2004/05/20 22:16:30 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
** The parameters are pointers to the head of two sorted lists
** of Sorter structures.  Merge these two lists together and return
** a single sorted list.  This routine forms the core of the merge-sort
** algorithm.
**
** In the case of a tie, left sorts in front of right.
*/
static Sorter *Merge(Sorter *pLeft, Sorter *pRight){
  Sorter sHead;
  Sorter *pTail;
  pTail = &sHead;
  pTail->pNext = 0;
  while( pLeft && pRight ){


    int c = sqlite3SortCompare(pLeft->zKey, pRight->zKey);
    if( c<=0 ){
      pTail->pNext = pLeft;
      pLeft = pLeft->pNext;
    }else{
      pTail->pNext = pRight;
      pRight = pRight->pNext;
    }
................................................................................
  pTos++;
  pTos->n = nByte;
  pTos->flags = MEM_Str|MEM_Dyn;
  pTos->z = zNewKey;
  break;
}

/* Opcode: Sort * * *
**
** Sort all elements on the sorter.  The algorithm is a
** mergesort.

*/
case OP_Sort: {
  int i;

  Sorter *pElem;
  Sorter *apSorter[NSORT];
  for(i=0; i<NSORT; i++){
    apSorter[i] = 0;
  }
  while( p->pSort ){
    pElem = p->pSort;
................................................................................
    p->pSort = pElem->pNext;
    pElem->pNext = 0;
    for(i=0; i<NSORT-1; i++){
    if( apSorter[i]==0 ){
        apSorter[i] = pElem;
        break;
      }else{
        pElem = Merge(apSorter[i], pElem);
        apSorter[i] = 0;
      }
    }
    if( i>=NSORT-1 ){
      apSorter[NSORT-1] = Merge(apSorter[NSORT-1],pElem);
    }
  }
  pElem = 0;
  for(i=0; i<NSORT; i++){
    pElem = Merge(apSorter[i], pElem);
  }
  p->pSort = pElem;
  break;
}

/* Opcode: SortNext * P2 *
**
................................................................................
            zBuf[1] = 'e';
            assert( (pTos[i].flags & (MEM_Static|MEM_Dyn))==0 );
          }else{
            zBuf[1] = 's';
          }
          zBuf[2] = '[';
          k = 3;
          for(j=0; j<20 && j<pTos[i].n; j++){
            int c = pTos[i].z[j];
            if( c==0 && j==pTos[i].n-1 ) break;


            if( c>=0x20 && c<0x7f ){
              zBuf[k++] = c;
            }else{
              zBuf[k++] = '.';
            }
          }
          zBuf[k++] = ']';







|







 







|





>
>
|







 







|


|
>



>







 







|




|




|







 







|
|

>
>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
...
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
....
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
....
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
....
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.310 2004/05/21 01:29:06 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
** The parameters are pointers to the head of two sorted lists
** of Sorter structures.  Merge these two lists together and return
** a single sorted list.  This routine forms the core of the merge-sort
** algorithm.
**
** In the case of a tie, left sorts in front of right.
*/
static Sorter *Merge(Sorter *pLeft, Sorter *pRight, KeyInfo *pKeyInfo){
  Sorter sHead;
  Sorter *pTail;
  pTail = &sHead;
  pTail->pNext = 0;
  while( pLeft && pRight ){
    int c = sqlite3VdbeKeyCompare(pKeyInfo, pLeft->nKey, pLeft->zKey,
                                  pRight->nKey, pRight->zKey);
    /* int c = sqlite3SortCompare(pLeft->zKey, pRight->zKey); */
    if( c<=0 ){
      pTail->pNext = pLeft;
      pLeft = pLeft->pNext;
    }else{
      pTail->pNext = pRight;
      pRight = pRight->pNext;
    }
................................................................................
  pTos++;
  pTos->n = nByte;
  pTos->flags = MEM_Str|MEM_Dyn;
  pTos->z = zNewKey;
  break;
}

/* Opcode: Sort * * P3
**
** Sort all elements on the sorter.  The algorithm is a
** mergesort.  The P3 argument is a pointer to a KeyInfo structure
** that describes the keys to be sorted.
*/
case OP_Sort: {
  int i;
  KeyInfo *pKeyInfo = (KeyInfo*)pOp->p3;
  Sorter *pElem;
  Sorter *apSorter[NSORT];
  for(i=0; i<NSORT; i++){
    apSorter[i] = 0;
  }
  while( p->pSort ){
    pElem = p->pSort;
................................................................................
    p->pSort = pElem->pNext;
    pElem->pNext = 0;
    for(i=0; i<NSORT-1; i++){
    if( apSorter[i]==0 ){
        apSorter[i] = pElem;
        break;
      }else{
        pElem = Merge(apSorter[i], pElem, pKeyInfo);
        apSorter[i] = 0;
      }
    }
    if( i>=NSORT-1 ){
      apSorter[NSORT-1] = Merge(apSorter[NSORT-1],pElem, pKeyInfo);
    }
  }
  pElem = 0;
  for(i=0; i<NSORT; i++){
    pElem = Merge(apSorter[i], pElem, pKeyInfo);
  }
  p->pSort = pElem;
  break;
}

/* Opcode: SortNext * P2 *
**
................................................................................
            zBuf[1] = 'e';
            assert( (pTos[i].flags & (MEM_Static|MEM_Dyn))==0 );
          }else{
            zBuf[1] = 's';
          }
          zBuf[2] = '[';
          k = 3;
          for(j=0; j<15 && j<pTos[i].n; j++){
            u8 c = pTos[i].z[j];
            if( c==0 && j==pTos[i].n-1 ) break;
            zBuf[k++] = "0123456789ABCDEF"[c>>4];
            zBuf[k++] = "0123456789ABCDEF"[c&0xf];
            if( c>=0x20 && c<0x7f ){
              zBuf[k++] = c;
            }else{
              zBuf[k++] = '.';
            }
          }
          zBuf[k++] = ']';

Changes to src/vdbe.h.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
66
67
68
69
70
71
72









73
74
75
76
77
78
79
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.79 2004/05/20 22:16:30 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
*/
#define P3_NOTUSED    0   /* The P3 parameter is not used */
#define P3_DYNAMIC  (-1)  /* Pointer to a string obtained from sqliteMalloc() */
#define P3_STATIC   (-2)  /* Pointer to a static string */
#define P3_POINTER  (-3)  /* P3 is a pointer to some structure or object */
#define P3_COLLSEQ  (-4)  /* P3 is a pointer to a CollSeq structure */
#define P3_KEYINFO  (-5)  /* P3 is a pointer to a KeyInfo structure */










/*
** The following macro converts a relative address in the p2 field
** of a VdbeOp structure into a negative number so that 
** sqlite3VdbeAddOpList() knows that the address is relative.  Calling
** the macro again restores the address.
*/







|







 







>
>
>
>
>
>
>
>
>







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
..
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.80 2004/05/21 01:29:06 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
*/
#define P3_NOTUSED    0   /* The P3 parameter is not used */
#define P3_DYNAMIC  (-1)  /* Pointer to a string obtained from sqliteMalloc() */
#define P3_STATIC   (-2)  /* Pointer to a static string */
#define P3_POINTER  (-3)  /* P3 is a pointer to some structure or object */
#define P3_COLLSEQ  (-4)  /* P3 is a pointer to a CollSeq structure */
#define P3_KEYINFO  (-5)  /* P3 is a pointer to a KeyInfo structure */

/* When adding a P3 argument using P3_KEYINFO, a copy of the KeyInfo structure
** is made.  That copy is freed when the Vdbe is finalized.  But if the
** argument is P3_KEYINFO_HANDOFF, the passed in pointer is used.  It still
** gets freed when the Vdbe is finalized so it still should be obtained
** from a single sqliteMalloc().  But no copy is made and the calling
** function should *not* try to free the KeyInfo.
*/
#define P3_KEYINFO_HANDOFF (-6)

/*
** The following macro converts a relative address in the p2 field
** of a VdbeOp structure into a negative number so that 
** sqlite3VdbeAddOpList() knows that the address is relative.  Calling
** the macro again restores the address.
*/

Changes to src/vdbeaux.c.

308
309
310
311
312
313
314



315
316
317
318
319
320
321
...
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
...
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
....
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
....
1628
1629
1630
1631
1632
1633
1634

1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
....
1652
1653
1654
1655
1656
1657
1658
1659







1660
1661
1662
1663
1664
1665
1666
....
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688

1689
1690
1691




1692
1693
1694
1695
1696
1697
1698


1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
    pOp->p3 = (char*)pKeyInfo;
    if( pKeyInfo ){
      memcpy(pKeyInfo, zP3, nByte);
      pOp->p3type = P3_KEYINFO;
    }else{
      pOp->p3type = P3_NOTUSED;
    }



  }else if( n<0 ){
    pOp->p3 = (char*)zP3;
    pOp->p3type = n;
  }else{
    sqlite3SetNString(&pOp->p3, zP3, n, 0);
    pOp->p3type = P3_DYNAMIC;
  }
................................................................................
        if( pColl ){
          int n = strlen(pColl->zName);
          if( i+n>nTemp-6 ){
            strcpy(&zTemp[i],",...");
            break;
          }
          zTemp[i++] = ',';
          if( pColl->reverseOrder ){
            zTemp[i++] = '-';
          }
          strcpy(&zTemp[i], pColl->zName);
          i += n;
        }else if( i+4<nTemp-6 ){
          strcpy(&zTemp[i],",nil");
          i += 4;
................................................................................
      zTemp[i] = 0;
      assert( i<nTemp );
      zP3 = zTemp;
      break;
    }
    case P3_COLLSEQ: {
      CollSeq *pColl = (CollSeq*)pOp->p3;
      sprintf(zTemp, "collseq(%s%.20s)", 
         pColl->reverseOrder ? "-" : "", pColl->zName);
      zP3 = zTemp;
      break;
    }
    default: {
      zP3 = pOp->p3;
      if( zP3==0 ){
        zP3 = "";
................................................................................
  int rc;
  int f1, f2;
  int combined_flags;

  /* Interchange pMem1 and pMem2 if the collating sequence specifies
  ** DESC order.
  */
  if( pColl && pColl->reverseOrder ){
    const Mem *pTemp = pMem1;
    pMem1 = pMem2;
    pMem2 = pTemp;
  }
  f1 = pMem1->flags;
  f2 = pMem2->flags;
  combined_flags = f1|f2;
 
  /* If one value is NULL, it is less than the other. If both values
  ** are NULL, return 0.
  */
................................................................................
  int nKey1, const void *pKey1, 
  int nKey2, const void *pKey2
){
  KeyInfo *pKeyInfo = (KeyInfo*)userData;
  int offset1 = 0;
  int offset2 = 0;
  int i = 0;

  const unsigned char *aKey1 = (const unsigned char *)pKey1;
  const unsigned char *aKey2 = (const unsigned char *)pKey2;
  
  assert( pKeyInfo!=0 );
  while( offset1<nKey1 && offset2<nKey2 ){
    Mem mem1;
    Mem mem2;
    u64 serial_type1;
    u64 serial_type2;
    int rc;

    /* Read the serial types for the next element in each key. */
    offset1 += sqlite3GetVarint(&aKey1[offset1], &serial_type1);
    offset2 += sqlite3GetVarint(&aKey2[offset2], &serial_type2);

    /* If either of the varints just read in are 0 (not a type), then
    ** this is the end of the keys. The remaining data in each key is
................................................................................
    ** the varint rowid. Compare these as signed integers and return
    ** the result.
    */
    if( !serial_type1 || !serial_type2 ){
      assert( !serial_type1 && !serial_type2 );
      sqlite3GetVarint(&aKey1[offset1], &serial_type1);
      sqlite3GetVarint(&aKey2[offset2], &serial_type2);
      return ( (i64)serial_type1 - (i64)serial_type2 );







    }

    assert( i<pKeyInfo->nField );

    /* Assert that there is enough space left in each key for the blob of
    ** data to go with the serial type just read. This assert may fail if
    ** the file is corrupted.  Then read the value from each key into mem1
................................................................................
    if( mem1.flags&MEM_Dyn ){
      sqliteFree(mem1.z);
    }
    if( mem2.flags&MEM_Dyn ){
      sqliteFree(mem2.z);
    }
    if( rc!=0 ){
      return rc;
    }
    i++;
  }

  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */

  if( pKeyInfo->incrKey ){
    assert( offset2==nKey2 );
    return -1;




  }

  if( offset1<nKey1 ){
    return 1;
  }
  if( offset2<nKey2 ){
    return -1;


  }

  return 0;
}

/*
** This function compares the two table row records specified by 
** {nKey1, pKey1} and {nKey2, pKey2}, returning a negative, zero
** or positive integer if {nKey1, pKey1} is less than, equal to or 
** greater than {nKey2, pKey2}.







>
>
>







 







|







 







|
<







 







<
<
<
<
<







 







>









<







 







|
>
>
>
>
>
>
>







 







|








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


|







308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
...
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
...
581
582
583
584
585
586
587
588

589
590
591
592
593
594
595
....
1529
1530
1531
1532
1533
1534
1535





1536
1537
1538
1539
1540
1541
1542
....
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641

1642
1643
1644
1645
1646
1647
1648
....
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
....
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702


1703


1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
    pOp->p3 = (char*)pKeyInfo;
    if( pKeyInfo ){
      memcpy(pKeyInfo, zP3, nByte);
      pOp->p3type = P3_KEYINFO;
    }else{
      pOp->p3type = P3_NOTUSED;
    }
  }else if( n==P3_KEYINFO_HANDOFF ){
    pOp->p3 = (char*)zP3;
    pOp->p3type = P3_KEYINFO;
  }else if( n<0 ){
    pOp->p3 = (char*)zP3;
    pOp->p3type = n;
  }else{
    sqlite3SetNString(&pOp->p3, zP3, n, 0);
    pOp->p3type = P3_DYNAMIC;
  }
................................................................................
        if( pColl ){
          int n = strlen(pColl->zName);
          if( i+n>nTemp-6 ){
            strcpy(&zTemp[i],",...");
            break;
          }
          zTemp[i++] = ',';
          if( pKeyInfo->aSortOrder && pKeyInfo->aSortOrder[j] ){
            zTemp[i++] = '-';
          }
          strcpy(&zTemp[i], pColl->zName);
          i += n;
        }else if( i+4<nTemp-6 ){
          strcpy(&zTemp[i],",nil");
          i += 4;
................................................................................
      zTemp[i] = 0;
      assert( i<nTemp );
      zP3 = zTemp;
      break;
    }
    case P3_COLLSEQ: {
      CollSeq *pColl = (CollSeq*)pOp->p3;
      sprintf(zTemp, "collseq(%.20s)", pColl->zName);

      zP3 = zTemp;
      break;
    }
    default: {
      zP3 = pOp->p3;
      if( zP3==0 ){
        zP3 = "";
................................................................................
  int rc;
  int f1, f2;
  int combined_flags;

  /* Interchange pMem1 and pMem2 if the collating sequence specifies
  ** DESC order.
  */





  f1 = pMem1->flags;
  f2 = pMem2->flags;
  combined_flags = f1|f2;
 
  /* If one value is NULL, it is less than the other. If both values
  ** are NULL, return 0.
  */
................................................................................
  int nKey1, const void *pKey1, 
  int nKey2, const void *pKey2
){
  KeyInfo *pKeyInfo = (KeyInfo*)userData;
  int offset1 = 0;
  int offset2 = 0;
  int i = 0;
  int rc = 0;
  const unsigned char *aKey1 = (const unsigned char *)pKey1;
  const unsigned char *aKey2 = (const unsigned char *)pKey2;
  
  assert( pKeyInfo!=0 );
  while( offset1<nKey1 && offset2<nKey2 ){
    Mem mem1;
    Mem mem2;
    u64 serial_type1;
    u64 serial_type2;


    /* Read the serial types for the next element in each key. */
    offset1 += sqlite3GetVarint(&aKey1[offset1], &serial_type1);
    offset2 += sqlite3GetVarint(&aKey2[offset2], &serial_type2);

    /* If either of the varints just read in are 0 (not a type), then
    ** this is the end of the keys. The remaining data in each key is
................................................................................
    ** the varint rowid. Compare these as signed integers and return
    ** the result.
    */
    if( !serial_type1 || !serial_type2 ){
      assert( !serial_type1 && !serial_type2 );
      sqlite3GetVarint(&aKey1[offset1], &serial_type1);
      sqlite3GetVarint(&aKey2[offset2], &serial_type2);
      if( serial_type1 < serial_type2 ){
        rc = -1;
      }else if( serial_type1 > serial_type2 ){
        rc = +1;
      }else{
        rc = 0;
      }
      return rc;
    }

    assert( i<pKeyInfo->nField );

    /* Assert that there is enough space left in each key for the blob of
    ** data to go with the serial type just read. This assert may fail if
    ** the file is corrupted.  Then read the value from each key into mem1
................................................................................
    if( mem1.flags&MEM_Dyn ){
      sqliteFree(mem1.z);
    }
    if( mem2.flags&MEM_Dyn ){
      sqliteFree(mem2.z);
    }
    if( rc!=0 ){
      break;
    }
    i++;
  }

  /* One of the keys ran out of fields, but all the fields up to that point
  ** were equal. If the incrKey flag is true, then the second key is
  ** treated as larger.
  */
  if( rc==0 ){
    if( pKeyInfo->incrKey ){
      assert( offset2==nKey2 );
      rc = -1;
    }else if( offset1<nKey1 ){
      rc = 1;
    }else if( offset2<nKey2 ){
      rc = -1;
    }
  }





  if( pKeyInfo->aSortOrder && i<pKeyInfo->nField && pKeyInfo->aSortOrder[i] ){
    rc = -rc;
  }

  return rc;
}

/*
** This function compares the two table row records specified by 
** {nKey1, pKey1} and {nKey2, pKey2}, returning a negative, zero
** or positive integer if {nKey1, pKey1} is less than, equal to or 
** greater than {nKey2, pKey2}.