**
** 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.349 2004/05/30 20:46:09 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  assert( pTos>=p->aStack );
  assert( pTos->flags & MEM_Blob );
  z = pTos->z;
  n = pTos->n;
  k = sqlite3GetVarint32(z, &serial_type);
  for(; k<n && i>0; i--){
    k += sqlite3GetVarint32(&z[k], &serial_type);
    if( serial_type==6 ){   /* Serial type 6 is a NULL */
      pc = pOp->p2-1;
      break;
    }
  }
  Release(pTos);
  pTos--;
  break;

**
** 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.350 2004/05/30 21:14:59 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
................................................................................
  assert( pTos>=p->aStack );
  assert( pTos->flags & MEM_Blob );
  z = pTos->z;
  n = pTos->n;
  k = sqlite3GetVarint32(z, &serial_type);
  for(; k<n && i>0; i--){
    k += sqlite3GetVarint32(&z[k], &serial_type);
    if( serial_type==0 ){   /* Serial type 0 is a NULL */
      pc = pOp->p2-1;
      break;
    }
  }
  Release(pTos);
  pTos--;
  break;

** the end. Hence these functions allow the caller to handle the
** serial-type and data blob seperately.
**
** The following table describes the various storage classes for data:
**
**   serial type        bytes of data      type
**   --------------     ---------------    ---------------
**      0                     -            Not a type.
**      1                     1            signed integer
**      2                     2            signed integer
**      3                     4            signed integer
**      4                     8            signed integer
**      5                     8            IEEE float
**      6                     0            NULL

**     7..11                               reserved for expansion
**    N>=12 and even       (N-12)/2        BLOB
**    N>=13 and odd        (N-13)/2        text
**
*/

/*
** Return the serial-type for the value stored in pMem.
*/
u32 sqlite3VdbeSerialType(Mem *pMem){
  int flags = pMem->flags;

  if( flags&MEM_Null ){
    return 6;
  }
  if( flags&MEM_Int ){
    /* Figure out whether to use 1, 2, 4 or 8 bytes. */
    i64 i = pMem->i;
    if( i>=-127 && i<=127 ) return 1;
    if( i>=-32767 && i<=32767 ) return 2;

    if( i>=-2147483647 && i<=2147483647 ) return 3;

    return 4;
  }
  if( flags&MEM_Real ){
    return 5;
  }
  if( flags&MEM_Str ){
    int n = pMem->n;
    assert( n>=0 );
    return ((n*2) + 13);
  }
  if( flags&MEM_Blob ){
................................................................................
  return 0;
}

/*
** Return the length of the data corresponding to the supplied serial-type.
*/
int sqlite3VdbeSerialTypeLen(u32 serial_type){
  assert( serial_type!=0 );
  if( serial_type>6 ){
    return (serial_type-12)/2;
  }else{
    static u8 aSize[] = { 0, 1, 2, 4, 8, 8, 0, };
    return aSize[serial_type];
  }
}

/*
** Write the serialized data blob for the value stored in pMem into 
** buf. It is assumed that the caller has allocated sufficient space.
** Return the number of bytes written.
*/ 
int sqlite3VdbeSerialPut(unsigned char *buf, Mem *pMem){
  u32 serial_type = sqlite3VdbeSerialType(pMem);
  int len;

  assert( serial_type!=0 );
 
  /* NULL */
  if( serial_type==6 ){
    return 0;
  }
 
  /* Integer and Real */
  if( serial_type<=5 ){
    u64 v;
    int i;
    if( serial_type==5 ){
      v = *(u64*)&pMem->r;
    }else{
      v = *(u64*)&pMem->i;
    }
    len = i = sqlite3VdbeSerialTypeLen(serial_type);
    while( i-- ){
      buf[i] = (v&0xFF);
................................................................................
int sqlite3VdbeSerialGet(
  const unsigned char *buf,     /* Buffer to deserialize from */
  u32 serial_type,              /* Serial type to deserialize */
  Mem *pMem                     /* Memory cell to write value into */
){
  int len;






  len = sqlite3VdbeSerialTypeLen(serial_type);
  assert( serial_type!=0 );
  if( serial_type<=5 ){
    /* Integer and Real */
    if( serial_type<=3 ){
      /* 32-bit integer type.  This is handled by a special case for
      ** performance reasons. */
      int v = buf[0];
      int n;
      if( v&0x80 ){
        v |= -256;
      }
................................................................................

      if( buf[0]&0x80 ){
        v = -1;
      }
      for(n=0; n<len; n++){
        v = (v<<8) | buf[n];
      }
      if( serial_type==5 ){
        pMem->flags = MEM_Real;
        pMem->r = *(double*)&v;
      }else{
        pMem->flags = MEM_Int;
        pMem->i = *(i64*)&v;
      }
    }
  }else if( serial_type>=12 ){
    /* String or blob */

    pMem->z = (char *)buf;
    pMem->n = len;
    if( serial_type&0x01 ){
      pMem->flags = MEM_Str | MEM_Ephem;
    }else{
      pMem->flags = MEM_Blob | MEM_Ephem;
    }
  }else{
    /* NULL */
    assert( serial_type==6 );
    assert( len==0 );
    pMem->flags = MEM_Null;
  }
  return len;
}

/*
** The following is the comparison function for (non-integer)
** keys in the btrees.  This function returns negative, zero, or

** the end. Hence these functions allow the caller to handle the
** serial-type and data blob seperately.
**
** The following table describes the various storage classes for data:
**
**   serial type        bytes of data      type
**   --------------     ---------------    ---------------
**      0                     0            NULL
**      1                     1            signed integer
**      2                     2            signed integer
**      3                     3            signed integer
**      4                     4            signed integer
**      5                     6            signed integer
**      6                     8            signed integer
**      7                     8            IEEE float
**     8-11                                reserved for expansion
**    N>=12 and even       (N-12)/2        BLOB
**    N>=13 and odd        (N-13)/2        text
**
*/

/*
** Return the serial-type for the value stored in pMem.
*/
u32 sqlite3VdbeSerialType(Mem *pMem){
  int flags = pMem->flags;

  if( flags&MEM_Null ){
    return 0;
  }
  if( flags&MEM_Int ){
    /* Figure out whether to use 1, 2, 4 or 8 bytes. */
    i64 i = pMem->i;
    if( i>=-127 && i<=127 ) return 1;
    if( i>=-32767 && i<=32767 ) return 2;
    if( i>=-8388607 && i<=8388607 ) return 3;
    if( i>=-2147483647 && i<=2147483647 ) return 4;
    if( i>=-140737488355328L && i<=140737488355328L ) return 5;
    return 6;
  }
  if( flags&MEM_Real ){
    return 7;
  }
  if( flags&MEM_Str ){
    int n = pMem->n;
    assert( n>=0 );
    return ((n*2) + 13);
  }
  if( flags&MEM_Blob ){
................................................................................
  return 0;
}

/*
** Return the length of the data corresponding to the supplied serial-type.
*/
int sqlite3VdbeSerialTypeLen(u32 serial_type){

  if( serial_type>=12 ){
    return (serial_type-12)/2;
  }else{
    static u8 aSize[] = { 0, 1, 2, 3, 4, 6, 8, 8, 0, 0, 0, 0 };
    return aSize[serial_type];
  }
}

/*
** Write the serialized data blob for the value stored in pMem into 
** buf. It is assumed that the caller has allocated sufficient space.
** Return the number of bytes written.
*/ 
int sqlite3VdbeSerialPut(unsigned char *buf, Mem *pMem){
  u32 serial_type = sqlite3VdbeSerialType(pMem);
  int len;



  /* NULL */
  if( serial_type==0 ){
    return 0;
  }
 
  /* Integer and Real */
  if( serial_type<=7 ){
    u64 v;
    int i;
    if( serial_type==7 ){
      v = *(u64*)&pMem->r;
    }else{
      v = *(u64*)&pMem->i;
    }
    len = i = sqlite3VdbeSerialTypeLen(serial_type);
    while( i-- ){
      buf[i] = (v&0xFF);
................................................................................
int sqlite3VdbeSerialGet(
  const unsigned char *buf,     /* Buffer to deserialize from */
  u32 serial_type,              /* Serial type to deserialize */
  Mem *pMem                     /* Memory cell to write value into */
){
  int len;

  if( serial_type==0 ){
    /* NULL */
    pMem->flags = MEM_Null;
    return 0;
  }
  len = sqlite3VdbeSerialTypeLen(serial_type);

  if( serial_type<=7 ){
    /* Integer and Real */
    if( serial_type<=4 ){
      /* 32-bit integer type.  This is handled by a special case for
      ** performance reasons. */
      int v = buf[0];
      int n;
      if( v&0x80 ){
        v |= -256;
      }
................................................................................

      if( buf[0]&0x80 ){
        v = -1;
      }
      for(n=0; n<len; n++){
        v = (v<<8) | buf[n];
      }
      if( serial_type==7 ){
        pMem->flags = MEM_Real;
        pMem->r = *(double*)&v;
      }else{
        pMem->flags = MEM_Int;
        pMem->i = *(i64*)&v;
      }
    }
  }else{
    /* String or blob */
    assert( serial_type>=12 );
    pMem->z = (char *)buf;
    pMem->n = len;
    if( serial_type&0x01 ){
      pMem->flags = MEM_Str | MEM_Ephem;
    }else{
      pMem->flags = MEM_Blob | MEM_Ephem;
    }





  }
  return len;
}

/*
** The following is the comparison function for (non-integer)
** keys in the btrees.  This function returns negative, zero, or

#    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 script is btree database backend
#
# $Id: btree.test,v 1.25 2004/05/18 15:57:42 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
#   2.  Delete every other entry of table 1.
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}

catch {unset key}
catch {unset data}
do_test btree-7.2 {
  # Each record will be 10 bytes in size.
  #   + 100 bytes of database header
  #   + 6 bytes of table header
  #   + 91*10=910 bytes of cells
  # Totals 1016 bytes.  8 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_info $::c1] 4 5
} {8 1}

do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i
    btree_delete $::c1
  }
  # Freed 45 blocks.  Total freespace is 458
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_info $::c1] 4 5
} {458 46}
#btree_tree_dump $::b1 1
do_test btree-7.4 {
  # The largest free block is 10 bytes long.  So if we insert
  # a record bigger than 10 bytes it should force a defrag
  # The record is 20 bytes long.






  btree_insert $::c1 2000 {123456789_12345}
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_info $::c1] 4 5
} {438 1}
#btree_tree_dump $::b1 1

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
................................................................................
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_info $::c1] 4 5
} {458 3}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 2
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_info $::c1] 4 5
} {448 2}   ;# Filled in the first hole
#btree_page_dump $::b1 2

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {458 2}  ;# Coalesce with the whole before


do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
................................................................................
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}


# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
................................................................................
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=999} {incr i} {
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]
................................................................................
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-11.3 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_page_dump $::b1 2

# Delete the dividers on the root page
#

do_test btree-11.4 {
  btree_move_to $::c1 551
  btree_delete $::c1
  btree_move_to $::c1 551
  set k [btree_key $::c1]
  if {$k==550} {
    set k [btree_next $::c1]
  }
  btree_key $::c1
} {552}


# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}

#    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 script is btree database backend
#
# $Id: btree.test,v 1.26 2004/05/30 21:14:59 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
#   2.  Delete every other entry of table 1.
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
if 0 {
catch {unset key}
catch {unset data}
do_test btree-7.2 {
  # Each record will be 10 bytes in size.
  #   + 100 bytes of database header
  #   + 8 bytes of table header
  #   + 91*10=910 bytes of cells
  # Totals 1018 bytes.  6 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_info $::c1] 4 5
} {6 0}
#btree_tree_dump $::b1 1
do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i
    btree_delete $::c1
  }
  # Freed 45 blocks.  Total freespace is 456
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_info $::c1] 4 5
} {456 45}
#btree_tree_dump $::b1 1
do_test btree-7.4 {
  # The largest free block is 8 bytes long.  But there is also a
  # huge hole between the cell pointer array and the cellcontent.
  # But if we insert a large enough record, it should force a defrag.
  set data 123456789_
  append data $data
  append data $data
  append data $data
  append data $data
  append data $data
  btree_insert $::c1 2000 $data
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_info $::c1] 4 5
} {343 0}
#btree_tree_dump $::b1 1

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
................................................................................
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_info $::c1] 4 5
} {363 2}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 1
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_info $::c1] 4 5
} {353 1}   ;# Filled in the first hole
btree_page_dump $::b1 1

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {363 2}  ;# Coalesce with the hole before
btree_page_dump $::b1 1
exit
do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
................................................................................
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}
} ;# endif

# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
................................................................................
  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=2000} {incr i} {
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]
................................................................................
  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-11.3 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}


# Delete the dividers on the root page
#
#btree_page_dump $::b1 2
do_test btree-11.4 {
  btree_move_to $::c1 1667
  btree_delete $::c1
  btree_move_to $::c1 1667
  set k [btree_key $::c1]
  if {$k==1666} {
    set k [btree_next $::c1]
  }
  btree_key $::c1
} {1668}
#btree_page_dump $::b1 2

# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}