/ Check-in [3047a25f]
Login

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

Overview
Comment:Merge the latest changes from trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 3047a25f1c41e83f0b4772f7c36fbfec0f12dc7e
User & Date: drh 2014-03-28 18:35:39
Context
2014-03-28
19:47
Fix a compiler warning and an after-OOM memory leak. check-in: 58f7ca29 user: drh tags: orderby-planning
19:18
Merge latest changes from orderby-planning branch. check-in: 4c7fb542 user: dan tags: threads
18:35
Merge the latest changes from trunk. check-in: 3047a25f user: drh tags: orderby-planning
14:41
Disable the wal64k.test script for non-unix systems since it depends on unix-only features. check-in: 27deb6e4 user: drh tags: trunk
2014-03-27
19:25
Instead of allocating a single large buffer at the beginning of each sort operation, start with a small buffer and extend it using realloc() as required. check-in: 81987c8c user: dan tags: orderby-planning
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to src/btree.c.

  4584   4584         *pRes = -1;
  4585   4585         return SQLITE_OK;
  4586   4586       }
  4587   4587     }
  4588   4588   
  4589   4589     if( pIdxKey ){
  4590   4590       xRecordCompare = sqlite3VdbeFindCompare(pIdxKey);
         4591  +    pIdxKey->isCorrupt = 0;
  4591   4592       assert( pIdxKey->default_rc==1 
  4592   4593            || pIdxKey->default_rc==0 
  4593   4594            || pIdxKey->default_rc==-1
  4594   4595       );
  4595   4596     }else{
  4596   4597       xRecordCompare = 0; /* All keys are integers */
  4597   4598     }
................................................................................
  4707   4708             if( rc ){
  4708   4709               sqlite3_free(pCellKey);
  4709   4710               goto moveto_finish;
  4710   4711             }
  4711   4712             c = xRecordCompare(nCell, pCellKey, pIdxKey, 0);
  4712   4713             sqlite3_free(pCellKey);
  4713   4714           }
         4715  +        assert( pIdxKey->isCorrupt==0 || c==0 );
  4714   4716           if( c<0 ){
  4715   4717             lwr = idx+1;
  4716   4718           }else if( c>0 ){
  4717   4719             upr = idx-1;
  4718   4720           }else{
  4719   4721             assert( c==0 );
  4720   4722             *pRes = 0;
  4721   4723             rc = SQLITE_OK;
  4722   4724             pCur->aiIdx[pCur->iPage] = (u16)idx;
         4725  +          if( pIdxKey->isCorrupt ) rc = SQLITE_CORRUPT;
  4723   4726             goto moveto_finish;
  4724   4727           }
  4725   4728           if( lwr>upr ) break;
  4726   4729           assert( lwr+upr>=0 );
  4727   4730           idx = (lwr+upr)>>1;  /* idx = (lwr+upr)/2 */
  4728   4731         }
  4729   4732       }

Changes to src/sqliteInt.h.

  1623   1623   ** The r1 and r2 member variables are only used by the optimized comparison
  1624   1624   ** functions vdbeRecordCompareInt() and vdbeRecordCompareString().
  1625   1625   */
  1626   1626   struct UnpackedRecord {
  1627   1627     KeyInfo *pKeyInfo;  /* Collation and sort-order information */
  1628   1628     u16 nField;         /* Number of entries in apMem[] */
  1629   1629     i8 default_rc;      /* Comparison result if keys are equal */
         1630  +  u8 isCorrupt;       /* Corruption detected by xRecordCompare() */
  1630   1631     Mem *aMem;          /* Values */
  1631   1632     int r1;             /* Value to return if (lhs > rhs) */
  1632   1633     int r2;             /* Value to return if (rhs < lhs) */
  1633   1634   };
  1634   1635   
  1635   1636   
  1636   1637   /*

Changes to src/vdbe.h.

   207    207   sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8);
   208    208   void sqlite3VdbeSetVarmask(Vdbe*, int);
   209    209   #ifndef SQLITE_OMIT_TRACE
   210    210     char *sqlite3VdbeExpandSql(Vdbe*, const char*);
   211    211   #endif
   212    212   
   213    213   void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*);
   214         -int sqlite3VdbeRecordCompare(int,const void*,const UnpackedRecord*,int);
          214  +int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*,int);
   215    215   UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **);
   216    216   
   217         -typedef int (*RecordCompare)(int,const void*,const UnpackedRecord*,int);
          217  +typedef int (*RecordCompare)(int,const void*,UnpackedRecord*,int);
   218    218   RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*);
   219    219   
   220    220   #ifndef SQLITE_OMIT_TRIGGER
   221    221   void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *);
   222    222   #endif
   223    223   
   224    224   /* Use SQLITE_ENABLE_COMMENTS to enable generation of extra comments on

Changes to src/vdbeInt.h.

   388    388   u32 sqlite3VdbeSerialTypeLen(u32);
   389    389   u32 sqlite3VdbeSerialType(Mem*, int);
   390    390   u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32);
   391    391   u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*);
   392    392   void sqlite3VdbeDeleteAuxData(Vdbe*, int, int);
   393    393   
   394    394   int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *);
   395         -int sqlite3VdbeIdxKeyCompare(VdbeCursor*,const UnpackedRecord*,int*);
          395  +int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*);
   396    396   int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *);
   397    397   int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*);
   398    398   int sqlite3VdbeExec(Vdbe*);
   399    399   int sqlite3VdbeList(Vdbe*);
   400    400   int sqlite3VdbeHalt(Vdbe*);
   401    401   int sqlite3VdbeChangeEncoding(Mem *, int);
   402    402   int sqlite3VdbeMemTooBig(Mem*);

Changes to src/vdbeaux.c.

  3401   3401   **
  3402   3402   ** If argument bSkip is non-zero, it is assumed that the caller has already
  3403   3403   ** determined that the first fields of the keys are equal.
  3404   3404   **
  3405   3405   ** Key1 and Key2 do not have to contain the same number of fields. If all 
  3406   3406   ** fields that appear in both keys are equal, then pPKey2->default_rc is 
  3407   3407   ** returned.
         3408  +**
         3409  +** If database corruption is discovered, set pPKey2->isCorrupt to non-zero
         3410  +** and return 0.
  3408   3411   */
  3409   3412   int sqlite3VdbeRecordCompare(
  3410   3413     int nKey1, const void *pKey1,   /* Left key */
  3411         -  const UnpackedRecord *pPKey2,   /* Right key */
         3414  +  UnpackedRecord *pPKey2,         /* Right key */
  3412   3415     int bSkip                       /* If true, skip the first field */
  3413   3416   ){
  3414   3417     u32 d1;                         /* Offset into aKey[] of next data element */
  3415   3418     int i;                          /* Index of next field to compare */
  3416   3419     u32 szHdr1;                     /* Size of record header in bytes */
  3417   3420     u32 idx1;                       /* Offset of first type in header */
  3418   3421     int rc = 0;                     /* Return value */
................................................................................
  3430   3433       szHdr1 = aKey1[0];
  3431   3434       d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1);
  3432   3435       i = 1;
  3433   3436       pRhs++;
  3434   3437     }else{
  3435   3438       idx1 = getVarint32(aKey1, szHdr1);
  3436   3439       d1 = szHdr1;
  3437         -    if( d1>(unsigned)nKey1 ) return 1;  /* Corruption */
         3440  +    if( d1>(unsigned)nKey1 ){ 
         3441  +      pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
         3442  +      return 0;  /* Corruption */
         3443  +    }
  3438   3444       i = 0;
  3439   3445     }
  3440   3446   
  3441   3447     VVA_ONLY( mem1.zMalloc = 0; ) /* Only needed by assert() statements */
  3442   3448     assert( pPKey2->pKeyInfo->nField+pPKey2->pKeyInfo->nXField>=pPKey2->nField 
  3443   3449          || CORRUPT_DB );
  3444   3450     assert( pPKey2->pKeyInfo->aSortOrder!=0 );
................................................................................
  3507   3513         }else if( !(serial_type & 0x01) ){
  3508   3514           rc = +1;
  3509   3515         }else{
  3510   3516           mem1.n = (serial_type - 12) / 2;
  3511   3517           testcase( (d1+mem1.n)==(unsigned)nKey1 );
  3512   3518           testcase( (d1+mem1.n+1)==(unsigned)nKey1 );
  3513   3519           if( (d1+mem1.n) > (unsigned)nKey1 ){
  3514         -          rc = 1;                /* Corruption */
         3520  +          pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
         3521  +          return 0;                /* Corruption */
  3515   3522           }else if( pKeyInfo->aColl[i] ){
  3516   3523             mem1.enc = pKeyInfo->enc;
  3517   3524             mem1.db = pKeyInfo->db;
  3518   3525             mem1.flags = MEM_Str;
  3519   3526             mem1.z = (char*)&aKey1[d1];
  3520   3527             rc = vdbeCompareMemString(&mem1, pRhs, pKeyInfo->aColl[i]);
  3521   3528           }else{
................................................................................
  3533   3540         if( serial_type<12 || (serial_type & 0x01) ){
  3534   3541           rc = -1;
  3535   3542         }else{
  3536   3543           int nStr = (serial_type - 12) / 2;
  3537   3544           testcase( (d1+nStr)==(unsigned)nKey1 );
  3538   3545           testcase( (d1+nStr+1)==(unsigned)nKey1 );
  3539   3546           if( (d1+nStr) > (unsigned)nKey1 ){
  3540         -          rc = 1;                /* Corruption */
         3547  +          pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
         3548  +          return 0;                /* Corruption */
  3541   3549           }else{
  3542   3550             int nCmp = MIN(nStr, pRhs->n);
  3543   3551             rc = memcmp(&aKey1[d1], pRhs->z, nCmp);
  3544   3552             if( rc==0 ) rc = nStr - pRhs->n;
  3545   3553           }
  3546   3554         }
  3547   3555       }
................................................................................
  3592   3600   ** byte (i.e. is less than 128).
  3593   3601   **
  3594   3602   ** To avoid concerns about buffer overreads, this routine is only used
  3595   3603   ** on schemas where the maximum valid header size is 63 bytes or less.
  3596   3604   */
  3597   3605   static int vdbeRecordCompareInt(
  3598   3606     int nKey1, const void *pKey1, /* Left key */
  3599         -  const UnpackedRecord *pPKey2, /* Right key */
         3607  +  UnpackedRecord *pPKey2,       /* Right key */
  3600   3608     int bSkip                     /* Ignored */
  3601   3609   ){
  3602   3610     const u8 *aKey = &((const u8*)pKey1)[*(const u8*)pKey1 & 0x3F];
  3603   3611     int serial_type = ((const u8*)pKey1)[1];
  3604   3612     int res;
  3605   3613     u32 y;
  3606   3614     u64 x;
................................................................................
  3690   3698   ** This function is an optimized version of sqlite3VdbeRecordCompare() 
  3691   3699   ** that (a) the first field of pPKey2 is a string, that (b) the first field
  3692   3700   ** uses the collation sequence BINARY and (c) that the size-of-header varint 
  3693   3701   ** at the start of (pKey1/nKey1) fits in a single byte.
  3694   3702   */
  3695   3703   static int vdbeRecordCompareString(
  3696   3704     int nKey1, const void *pKey1, /* Left key */
  3697         -  const UnpackedRecord *pPKey2, /* Right key */
         3705  +  UnpackedRecord *pPKey2,       /* Right key */
  3698   3706     int bSkip
  3699   3707   ){
  3700   3708     const u8 *aKey1 = (const u8*)pKey1;
  3701   3709     int serial_type;
  3702   3710     int res;
  3703   3711     UNUSED_PARAMETER(bSkip);
  3704   3712   
................................................................................
  3711   3719       res = pPKey2->r2;      /* (pKey1/nKey1) is a blob */
  3712   3720     }else{
  3713   3721       int nCmp;
  3714   3722       int nStr;
  3715   3723       int szHdr = aKey1[0];
  3716   3724   
  3717   3725       nStr = (serial_type-12) / 2;
  3718         -    if( (szHdr + nStr) > nKey1 ) return 0;    /* Corruption */
         3726  +    if( (szHdr + nStr) > nKey1 ){
         3727  +      pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT;
         3728  +      return 0;    /* Corruption */
         3729  +    }
  3719   3730       nCmp = MIN( pPKey2->aMem[0].n, nStr );
  3720   3731       res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp);
  3721   3732   
  3722   3733       if( res==0 ){
  3723   3734         res = nStr - pPKey2->aMem[0].n;
  3724   3735         if( res==0 ){
  3725   3736           if( pPKey2->nField>1 ){
................................................................................
  3876   3887   ** pUnpacked is either created without a rowid or is truncated so that it
  3877   3888   ** omits the rowid at the end.  The rowid at the end of the index entry
  3878   3889   ** is ignored as well.  Hence, this routine only compares the prefixes 
  3879   3890   ** of the keys prior to the final rowid, not the entire key.
  3880   3891   */
  3881   3892   int sqlite3VdbeIdxKeyCompare(
  3882   3893     VdbeCursor *pC,                  /* The cursor to compare against */
  3883         -  const UnpackedRecord *pUnpacked, /* Unpacked version of key */
         3894  +  UnpackedRecord *pUnpacked,       /* Unpacked version of key */
  3884   3895     int *res                         /* Write the comparison result here */
  3885   3896   ){
  3886   3897     i64 nCellKey = 0;
  3887   3898     int rc;
  3888   3899     BtCursor *pCur = pC->pCursor;
  3889   3900     Mem m;
  3890   3901   

Changes to src/where.c.

  4324   4324            && (pProbe->szIdxRow<pTab->szTabRow)
  4325   4325            && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  4326   4326            && sqlite3GlobalConfig.bUseCis
  4327   4327            && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
  4328   4328             )
  4329   4329         ){
  4330   4330           pNew->iSortIdx = b ? iSortIdx : 0;
         4331  +        /* TUNING:  The base cost of an index scan is N + log2(N).
         4332  +        ** The log2(N) is for the initial seek to the beginning and the N
         4333  +        ** is for the scan itself. */
         4334  +        pNew->rRun = sqlite3LogEstAdd(rSize, rLogSize);
  4331   4335           if( m==0 ){
  4332   4336             /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
  4333   4337             **  +  The extra factor K of between 1.1 and 3.0 that depends
  4334   4338             **     on the relative sizes of the table and the index.  K
  4335   4339             **     is smaller for smaller indices, thus favoring them.
         4340  +          **     The upper bound on K (3.0) matches the penalty factor
         4341  +          **     on a full table scan that tries to encourage the use of
         4342  +          **     indexed lookups over full scans.
  4336   4343             */
  4337         -          pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 +
  4338         -                        (15*pProbe->szIdxRow)/pTab->szTabRow;
         4344  +          pNew->rRun +=  1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
  4339   4345           }else{
  4340         -          /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
  4341         -          ** which we will simplify to just N*log2(N) */
  4342         -          pNew->rRun = rSize + rLogSize;
         4346  +          /* TUNING: The cost of scanning a non-covering index is multiplied
         4347  +          ** by log2(N) to account for the binary search of the main table
         4348  +          ** that must happen for each row of the index.
         4349  +          ** TODO: Should there be a multiplier here, analogous to the 3x
         4350  +          ** multiplier for a fulltable scan or covering index scan, to
         4351  +          ** further discourage the use of an index scan?  Or is the log2(N)
         4352  +          ** term sufficient discouragement?
         4353  +          ** TODO: What if some or all of the WHERE clause terms can be
         4354  +          ** computed without reference to the original table.  Then the
         4355  +          ** penality should reduce to logK where K is the number of output
         4356  +          ** rows.
         4357  +          */
         4358  +          pNew->rRun += rLogSize;
  4343   4359           }
  4344   4360           whereLoopOutputAdjust(pWC, pNew);
  4345   4361           rc = whereLoopInsert(pBuilder, pNew);
  4346   4362           pNew->nOut = rSize;
  4347   4363           if( rc ) break;
  4348   4364         }
  4349   4365       }
................................................................................
  4916   4932           if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue;
  4917   4933           if( (mTerm&~orderDistinctMask)==0 ){
  4918   4934             obSat |= MASKBIT(i);
  4919   4935           }
  4920   4936         }
  4921   4937       }
  4922   4938     } /* End the loop over all WhereLoops from outer-most down to inner-most */
  4923         -  if( obSat==obDone ) return nOrderBy;
         4939  +  if( obSat==obDone ) return (i8)nOrderBy;
  4924   4940     if( !isOrderDistinct ){
  4925   4941       for(i=nOrderBy-1; i>0; i--){
  4926   4942         Bitmask m = MASKBIT(i) - 1;
  4927   4943         if( (obSat&m)==m ) return i;
  4928   4944       }
  4929   4945       return 0;
  4930   4946     }
................................................................................
  5037   5053           nOut = pFrom->nRow + pWLoop->nOut;
  5038   5054           maskNew = pFrom->maskLoop | pWLoop->maskSelf;
  5039   5055           if( isOrdered<0 ){
  5040   5056             isOrdered = wherePathSatisfiesOrderBy(pWInfo,
  5041   5057                          pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
  5042   5058                          iLoop, pWLoop, &revMask);
  5043   5059             if( isOrdered>=0 && isOrdered<nOrderBy ){
  5044         -            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).
  5045         -            ** If some but not all of the columns are in sorted order, then
  5046         -            ** scale down the log(N) term. */
  5047         -            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
  5048         -            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;
         5060  +            /* TUNING: Estimated cost of sorting is N*log(N).
         5061  +            ** If the order-by clause has X terms but only the last Y terms
         5062  +            ** are out of order, then block-sorting will reduce the sorting
         5063  +            ** cost to N*log(N)*log(Y/X).  The log(Y/X) term is computed
         5064  +            ** by rScale.
         5065  +            ** TODO: Should the sorting cost get a small multiplier to help
         5066  +            ** discourage the use of sorting and encourage the use of index
         5067  +            ** scans instead?
         5068  +            */
         5069  +            LogEst rScale, rSortCost;
         5070  +            assert( nOrderBy>0 );
         5071  +            rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66;
         5072  +            rSortCost = nRowEst + estLog(nRowEst) + rScale;
  5049   5073               /* TUNING: The cost of implementing DISTINCT using a B-TREE is
  5050   5074               ** also N*log(N) but it has a larger constant of proportionality.
  5051   5075               ** Multiply by 3.0. */
  5052   5076               if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
  5053   5077                 rSortCost += 16;
  5054   5078               }
  5055   5079               WHERETRACE(0x002,

Changes to test/corruptG.test.

    43     43   sqlite3 db test.db
    44     44   
    45     45   # Try to use the file.
    46     46   do_test 1.2 {
    47     47     catchsql {
    48     48       SELECT c FROM t1 WHERE a>'abc';
    49     49     }
    50         -} {0 {}}
           50  +} {1 {database disk image is malformed}}
    51     51   do_test 1.3 {
    52     52     catchsql {
    53     53        PRAGMA integrity_check
    54     54     }
    55         -} {0 ok}
           55  +} {1 {database disk image is malformed}}
    56     56   do_test 1.4 {
    57     57     catchsql {
    58     58       SELECT c FROM t1 ORDER BY a;
    59     59     }
    60     60   } {1 {database disk image is malformed}}
    61     61   
    62     62   # Corrupt the same file in a slightly different way.  Make the record header
................................................................................
    67     67   hexio_write test.db [expr {$idxroot*512-15}] 0513ff7f01
    68     68   sqlite3 db test.db
    69     69   
    70     70   do_test 2.1 {
    71     71     catchsql {
    72     72       SELECT rowid FROM t1 WHERE a='abc' and b='xyz123456789XYZ';
    73     73     }
    74         -  # The following test result is brittle.  The point above is to try to
    75         -  # force a buffer overread by a corrupt database file.  If we get an
    76         -  # incorrect answer from a corrupt database file, that is OK.  If the
    77         -  # result below changes, that just means that "undefined behavior" has
    78         -  # changed.
    79         -} {/0 .*/}
           74  +} {1 {database disk image is malformed}}
    80     75   
    81     76   finish_test

Changes to test/corruptI.test.

    47     47   do_test 1.3 {
    48     48     db close
    49     49     set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]]
    50     50     set off [expr 2*1024 + $offset + 1]
    51     51     hexio_write test.db $off FFFF7f02
    52     52     sqlite3 db test.db
    53     53     catchsql { SELECT * FROM t1 WHERE a = 10 }
    54         -} {0 {}}
           54  +} {1 {database disk image is malformed}}
    55     55   
    56     56   do_test 2.0 {
    57     57     execsql {
    58     58       CREATE TABLE r(x);
    59     59       INSERT INTO r VALUES('ABCDEFGHIJK');
    60     60       CREATE INDEX r1 ON r(x);
    61     61     }

Changes to test/wal64k.test.

    14     14   #
    15     15   
    16     16   set testdir [file dirname $argv0]
    17     17   source $testdir/tester.tcl
    18     18   set testprefix wal64k
    19     19   
    20     20   ifcapable !wal {finish_test ; return }
           21  +
           22  +if {$tcl_platform(platform) != "unix"} {
           23  +  finish_test
           24  +  return
           25  +}
    21     26   
    22     27   db close
    23     28   test_syscall pagesize 65536
    24     29   sqlite3 db test.db
    25     30   
    26     31   do_execsql_test 1.0 { 
    27     32     PRAGMA journal_mode = WAL;
................................................................................
    40     45   } {131072}
    41     46   
    42     47   integrity_check 1.3
    43     48   
    44     49   db close
    45     50   test_syscall pagesize -1
    46     51   finish_test
    47         -

Changes to tool/logest.c.

    13     13   ** integers and LogEst values and back again and for doing simple
    14     14   ** arithmetic operations (multiple and add) on LogEst values.
    15     15   **
    16     16   ** Usage:
    17     17   **
    18     18   **      ./LogEst ARGS
    19     19   **
    20         -** Arguments:
    21         -**
    22         -**    'x'    Multiple the top two elements of the stack
    23         -**    '+'    Add the top two elements of the stack
    24         -**    NUM    Convert NUM from integer to LogEst and push onto the stack
    25         -**   ^NUM    Interpret NUM as a LogEst and push onto stack.
    26         -**
           20  +** See the showHelp() routine for a description of valid arguments.
    27     21   ** Examples:
    28     22   **
    29     23   ** To convert 123 from LogEst to integer:
    30     24   ** 
    31     25   **         ./LogEst ^123
    32     26   **
    33     27   ** To convert 123456 from integer to LogEst:
................................................................................
    92     86     if( x<1.0 ) return -logEstFromDouble(1/x);
    93     87     if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100;
    94     88     if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x);
    95     89     memcpy(&a, &x, 8);
    96     90     e = (a>>52) - 1022;
    97     91     return e*10;
    98     92   }
           93  +
           94  +int isInteger(const char *z){
           95  +  while( z[0]>='0' && z[0]<='9' ) z++;
           96  +  return z[0]==0;
           97  +}
    99     98   
   100     99   int isFloat(const char *z){
   101         -  while( z[0] ){
   102         -    if( z[0]=='.' || z[0]=='E' || z[0]=='e' ) return 1;
   103         -    z++;
          100  +  char c;
          101  +  while( ((c=z[0])>='0' && c<='9') || c=='.' || c=='E' || c=='e'
          102  +          || c=='+' || c=='-'  ) z++;
          103  +  return z[0]==0;
   104    104     }
   105         -  return 0;
          105  +
          106  +static void showHelp(const char *zArgv0){
          107  +  printf("Usage: %s ARGS...\n", zArgv0);
          108  +  printf("Arguments:\n"
          109  +    "  NUM    Convert NUM from integer to LogEst and push onto the stack\n"
          110  +    " ^NUM    Interpret NUM as a LogEst and push onto stack\n"
          111  +    "  x      Multiple the top two elements of the stack\n"
          112  +    "  +      Add the top two elements of the stack\n"
          113  +    "  dup    Dupliate the top element on the stack\n"
          114  +    "  inv    Take the reciprocal of the top of stack.  N = 1/N.\n"
          115  +    "  log    Find the LogEst of the number on top of stack\n"
          116  +    "  nlogn  Compute NlogN where N is the top of stack\n"
          117  +  );
          118  +  exit(1);
   106    119   }
   107    120   
   108    121   int main(int argc, char **argv){
   109    122     int i;
   110    123     int n = 0;
   111    124     LogEst a[100];
   112    125     for(i=1; i<argc; i++){
   113    126       const char *z = argv[i];
   114         -    if( z[0]=='+' ){
          127  +    if( strcmp(z,"+")==0 ){
   115    128         if( n>=2 ){
   116    129           a[n-2] = logEstAdd(a[n-2],a[n-1]);
   117    130           n--;
   118    131         }
   119         -    }else if( z[0]=='x' ){
          132  +    }else if( strcmp(z,"x")==0 ){
   120    133         if( n>=2 ){
   121    134           a[n-2] = logEstMultiply(a[n-2],a[n-1]);
   122    135           n--;
   123    136         }
          137  +    }else if( strcmp(z,"dup")==0 ){
          138  +      if( n>0 ){
          139  +        a[n] = a[n-1];
          140  +        n++;
          141  +      }
          142  +    }else if( strcmp(z,"log")==0 ){
          143  +      if( n>0 ) a[n-1] = logEstFromInteger(a[n-1]) - 33;
          144  +    }else if( strcmp(z,"nlogn")==0 ){
          145  +      if( n>0 ) a[n-1] += logEstFromInteger(a[n-1]) - 33;
          146  +    }else if( strcmp(z,"inv")==0 ){
          147  +      if( n>0 ) a[n-1] = -a[n-1];
   124    148       }else if( z[0]=='^' ){
   125    149         a[n++] = atoi(z+1);
   126         -    }else if( isFloat(z) ){
          150  +    }else if( isInteger(z) ){
          151  +      a[n++] = logEstFromInteger(atoi(z));
          152  +    }else if( isFloat(z) && z[0]!='-' ){
   127    153         a[n++] = logEstFromDouble(atof(z));
   128    154       }else{
   129         -      a[n++] = logEstFromInteger(atoi(z));
          155  +      showHelp(argv[0]);
   130    156       }
   131    157     }
   132    158     for(i=n-1; i>=0; i--){
   133    159       if( a[i]<0 ){
   134         -      printf("%d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
          160  +      printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
   135    161       }else{
   136    162         sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024;
   137         -      printf("%d (%lld.%02lld)\n", a[i], x/100, x%100);
          163  +      printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100);
   138    164       }
   139    165     }
   140    166     return 0;
   141    167   }