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

Overview
Comment:Additional comments on the key encoder. Remove an unused variable.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fdaed18ddfae0cd18f10103916582f65034b2d0c
User & Date: drh 2012-04-21 19:59:02.390
Context
2012-04-23
09:40
Fix for compound EXCEPT queries. check-in: 2dc7b22339 user: dan tags: trunk
2012-04-21
19:59
Additional comments on the key encoder. Remove an unused variable. check-in: fdaed18ddf user: drh tags: trunk
19:19
Fix an off-by-one problem with encoding real values into index keys. Add a test for sorting numeric values. check-in: 7017d07fea user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbecodec.c.
349
350
351
352
353
354
355
356
357
358
359
360

361





362






363
364
365
366
367
368
369
  }
  return SQLITE_OK;
}

/*
** Encode the positive integer m using the key encoding.
**
** The key encoding for a positive integer consists of a varint which
** is the number of digits in the integer, followed by the digits of
** the integer from most significant to least significant, packed to
** digits to a byte.  Each digit is represented by a number between 1
** and 10 with 1 representing 0 and 10 representing 9.  A zero value 

** marks the end of the significand.  An extra zero is added to fill out





** the final byte, if necessary.






*/
static int encodeIntKey(sqlite4_uint64 m, KeyEncoder *p){
  int i = 0;
  int e;
  unsigned char aDigits[20];
  assert( m>0 );
  do{







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







349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
  }
  return SQLITE_OK;
}

/*
** Encode the positive integer m using the key encoding.
**
** To encode an integer, the integer value is represented as centimal
** (base-100) with E digits.  Each centimal digit is stored in one byte
** with the most significant digits coming first.  For each centimal
** digit X (with X>=0 and X<=99) the byte value will be 2*X+1 except
** for the last digit for which the value is 2*X.  Trailing 0 digits are
** omitted, so that the encoding of the mantissa will never contain
** a zero byte.
**
** The key encoding consists of the E value (the number of
** centimal digits in the original number, before trailing zero digits
** are removed), followed by the mantissa encoding M.  This routine
** only writes the mantissa.  The E values will be embedded in the
** initial byte of the encoding by the calling function.  This
** routine returns the value of E.  E will always be at least 1 and
** no more than 10.
**
** Note that values encoded by this routine have exactly the same
** byte representation as the equivalent floating-point values encoded
** by the encodeLargeFloatKey() routine below.
*/
static int encodeIntKey(sqlite4_uint64 m, KeyEncoder *p){
  int i = 0;
  int e;
  unsigned char aDigits[20];
  assert( m>0 );
  do{
400
401
402
403
404
405
406












407
408
409
410
411
412
413
  return s.nOut;
}

/*
** Encode the small positive floating point number r using the key
** encoding.  The caller guarantees that r will be less than 1.0 and
** greater than 0.0.












*/
static void encodeSmallFloatKey(double r, KeyEncoder *p){
  int e = 0;
  int i, n;
  assert( r>0.0 && r<1.0 );
  while( r<1e-10 ){ r *= 1e8; e+=4; }
  while( r<0.01 ){ r *= 100.0; e++; }







>
>
>
>
>
>
>
>
>
>
>
>







412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
  return s.nOut;
}

/*
** Encode the small positive floating point number r using the key
** encoding.  The caller guarantees that r will be less than 1.0 and
** greater than 0.0.
**
** A floating point value is encoded as an integer exponent E and a 
** mantissa M.  The original value is equal to (M * 100^E). E is set
** to the smallest value possible without making M greater than or equal 
** to 1.0.
**
** For this routine, E will always be zero or negative, since the original
** value is less than one.  The encoding written by this routine is the
** ones-complement of the varint of the negative of E followed by the
** mantissa:
**
**   Encoding:   ~-E  M
*/
static void encodeSmallFloatKey(double r, KeyEncoder *p){
  int e = 0;
  int i, n;
  assert( r>0.0 && r<1.0 );
  while( r<1e-10 ){ r *= 1e8; e+=4; }
  while( r<0.01 ){ r *= 100.0; e++; }
437
438
439
440
441
442
443
444
445
446


447



448
449
450
451
452
453
454
455
** of the centimal digit is X (hence X>=0 and X<=99) then the byte value 
** will be 2*X+1 for every byte of the mantissa, except for the last byte 
** which will be 2*X+0. The mantissa must be the minimum number of bytes 
** necessary to represent the value; trailing X==0 digits are omitted. 
** This means that the mantissa will never contain a byte with the 
** value 0x00.
**
** If E is greater than 10, the encoded value consists of E as a varint
** followed by the mantissa as described above. Otherwise, it consists
** of the mantissa only.


**



** The value returned by this function is E.
*/
static int encodeLargeFloatKey(double r, KeyEncoder *p){
  int e = 0;
  int i, n;
  assert( r>=1.0 );
  while( r>=1e32 && e<=350 ){ r *= 1e-32; e+=16; }
  while( r>=1e8 && e<=350 ){ r *= 1e-8; e+=4; }







|
|
|
>
>

>
>
>
|







461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
** of the centimal digit is X (hence X>=0 and X<=99) then the byte value 
** will be 2*X+1 for every byte of the mantissa, except for the last byte 
** which will be 2*X+0. The mantissa must be the minimum number of bytes 
** necessary to represent the value; trailing X==0 digits are omitted. 
** This means that the mantissa will never contain a byte with the 
** value 0x00.
**
** If E is greater than 10, then this routine writes of E as a varint
** followed by the mantissa as described above. Otherwise, if E is 10 or
** less, this routine only writes the mantissa and leaves the E value
** to be encoded as part of the opening byte of the field by the
** calling function.
**
**   Encoding:  M       (if E<=10)
**              E M     (if E>10)
**
** This routine returns the value of E.
*/
static int encodeLargeFloatKey(double r, KeyEncoder *p){
  int e = 0;
  int i, n;
  assert( r>=1.0 );
  while( r>=1e32 && e<=350 ){ r *= 1e-32; e+=16; }
  while( r>=1e8 && e<=350 ){ r *= 1e-8; e+=4; }
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
  int *pnOut,                  /* Number of bytes in the key */
  int nExtra                   /* See above */
){
  int i;
  int rc = SQLITE_OK;
  KeyEncoder x;
  u8 *so;
  int iShort;
  CollSeq **aColl;
  CollSeq *xColl;
  static const CollSeq defaultColl;

  assert( pKeyInfo );
  assert( nIn<=pKeyInfo->nField );

  x.db = db;
  x.aOut = 0;
  x.nOut = 0;
  x.nAlloc = 0;
  *paOut = 0;
  *pnOut = 0;

  if( enlargeEncoderAllocation(&x, (nIn+1)*10) ) return SQLITE_NOMEM;
  x.nOut = sqlite4PutVarint64(x.aOut, iTabno);
  iShort = pKeyInfo->nField - pKeyInfo->nPK;
  aColl = pKeyInfo->aColl;
  so = pKeyInfo->aSortOrder;
  for(i=0; i<nIn && rc==SQLITE_OK; i++){
    rc = encodeOneKeyValue(&x, aIn+i, so ? so[i] : SQLITE_SO_ASC, aColl[i]);
  }

  if( rc==SQLITE_OK && nExtra ){ rc = enlargeEncoderAllocation(&x, nExtra); }







<
















<







678
679
680
681
682
683
684

685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700

701
702
703
704
705
706
707
  int *pnOut,                  /* Number of bytes in the key */
  int nExtra                   /* See above */
){
  int i;
  int rc = SQLITE_OK;
  KeyEncoder x;
  u8 *so;

  CollSeq **aColl;
  CollSeq *xColl;
  static const CollSeq defaultColl;

  assert( pKeyInfo );
  assert( nIn<=pKeyInfo->nField );

  x.db = db;
  x.aOut = 0;
  x.nOut = 0;
  x.nAlloc = 0;
  *paOut = 0;
  *pnOut = 0;

  if( enlargeEncoderAllocation(&x, (nIn+1)*10) ) return SQLITE_NOMEM;
  x.nOut = sqlite4PutVarint64(x.aOut, iTabno);

  aColl = pKeyInfo->aColl;
  so = pKeyInfo->aSortOrder;
  for(i=0; i<nIn && rc==SQLITE_OK; i++){
    rc = encodeOneKeyValue(&x, aIn+i, so ? so[i] : SQLITE_SO_ASC, aColl[i]);
  }

  if( rc==SQLITE_OK && nExtra ){ rc = enlargeEncoderAllocation(&x, nExtra); }