SQLite

#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/percentile.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c

# Source code to the library files needed by the test fixture
#
TESTSRC2 = \

#
TESTEXT = \
  $(TOP)\ext\misc\amatch.c \
  $(TOP)\ext\misc\closure.c \
  $(TOP)\ext\misc\fuzzer.c \
  $(TOP)\ext\misc\ieee754.c \
  $(TOP)\ext\misc\nextchar.c \
  $(TOP)\ext\misc\percentile.c \
  $(TOP)\ext\misc\regexp.c \
  $(TOP)\ext\misc\spellfix.c \
  $(TOP)\ext\misc\wholenumber.c


# Source code to the library files needed by the test fixture
#

/*
** 2013-05-28
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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.
**
******************************************************************************
**
** This file contains code to implement the percentile(Y,P) SQL function
** as described below:
**
**   (1)  The percentile(Y,P) function is an aggregate function taking
**        exactly two arguments.
**
**   (2)  If the P argument to percentile(Y,P) is not the same for every
**        row in the aggregate then an error is thrown.  The word "same"
**        in the previous sentence means that the value differ by less
**        than 0.001.
**
**   (3)  If the P argument to percentile(Y,P) evaluates to anything other
**        than a number in the range of 0.0 to 100.0 inclusive then an
**        error is thrown.
**
**   (4)  If any Y argument to percentile(Y,P) evaluates to a value that
**        is not NULL and is not numeric then an error is thrown.
**
**   (5)  If any Y argument to percentile(Y,P) evaluates to plus or minus
**        infinity then an error is thrown.  (SQLite always interprets NaN
**        values as NULL.)
**
**   (6)  Both Y and P in percentile(Y,P) can be arbitrary expressions,
**        including CASE WHEN expressions.
**
**   (7)  The percentile(Y,P) aggregate is able to handle inputs of at least
**        one million (1,000,000) rows.
**
**   (8)  If there are no non-NULL values for Y, then percentile(Y,P)
**        returns NULL.
**
**   (9)  If there is exactly one non-NULL value for Y, the percentile(Y,P)
**        returns the one Y value.
**
**  (10)  If there N non-NULL values of Y where N is two or more and
**        the Y values are ordered from least to greatest and a graph is
**        drawn from 0 to N-1 such that the height of the graph at J is
**        the J-th Y value and such that straight lines are drawn between
**        adjacent Y values, then the percentile(Y,P) function returns
**        the height of the graph at P*(N-1)/100.
**
**  (11)  The percentile(Y,P) function always returns either a floating
**        point number or NULL.
**
**  (12)  The percentile(Y,P) is implemented as a single C99 source-code
**        file that compiles into a shared-library or DLL that can be loaded
**        into SQLite using the sqlite3_load_extension() interface.
*/
#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>
#include <stdlib.h>

/* The following object is the session context for a single percentile()
** function.  We have to remember all input Y values until the very end.
** Those values are accumulated in the Percentile.a[] array.
*/
typedef struct Percentile Percentile;
struct Percentile {
  unsigned nAlloc;     /* Number of slots allocated for a[] */
  unsigned nUsed;      /* Number of slots actually used in a[] */
  double rPct;         /* 1.0 more than the value for P */
  double *a;           /* Array of Y values */
};

/*
** Return TRUE if the input floating-point number is an infinity.
*/
static int isInfinity(double r){
  sqlite3_uint64 u;
  assert( sizeof(u)==sizeof(r) );
  memcpy(&u, &r, sizeof(u));
  return ((u>>52)&0x7ff)==0x7ff;
}

/*
** Return TRUE if two doubles differ by 0.001 or less
*/
static int sameValue(double a, double b){
  a -= b;
  return a>=-0.001 && a<=0.001;
}

/*
** The "step" function for percentile(Y,P) is called once for each
** input row.
*/
static void percentStep(sqlite3_context *pCtx, int argc, sqlite3_value **argv){
  Percentile *p;
  double rPct;
  int eType;
  double y;
  assert( argc==2 );

  /* Requirement 3:  P must be a number between 0 and 100 */
  eType = sqlite3_value_numeric_type(argv[1]);
  rPct = sqlite3_value_double(argv[1]);
  if( (eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT) ||
      ((rPct = sqlite3_value_double(argv[1]))<0.0 || rPct>100.0) ){
    sqlite3_result_error(pCtx, "2nd argument to percentile() is not "
                         "a number between 0.0 and 100.0", -1);
    return;
  }

  /* Allocate the session context. */
  p = (Percentile*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  if( p==0 ) return;

  /* Remember the P value.  Throw an error if the P value is different
  ** from any prior row, per Requirement (2). */
  if( p->rPct==0.0 ){
    p->rPct = rPct+1.0;
  }else if( !sameValue(p->rPct,rPct+1.0) ){
    sqlite3_result_error(pCtx, "2nd argument to percentile() is not the "
                               "same for all input rows", -1);
    return;
  }

  /* Ignore rows for which Y is NULL */
  eType = sqlite3_value_type(argv[0]);
  if( eType==SQLITE_NULL ) return;

  /* If not NULL, then Y must be numeric.  Otherwise throw an error.
  ** Requirement 4 */
  if( eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT ){
    sqlite3_result_error(pCtx, "1st argument to percentile() is not "
                               "numeric", -1);
    return;
  }

  /* Throw an error if the Y value is infinity or NaN */
  y = sqlite3_value_double(argv[0]);
  if( isInfinity(y) ){
    sqlite3_result_error(pCtx, "Inf input to percentile()", -1);
    return;
  }

  /* Allocate and store the Y */
  if( p->nUsed>=p->nAlloc ){
    unsigned n = p->nAlloc*2 + 250;
    double *a = sqlite3_realloc(p->a, sizeof(double)*n);
    if( a==0 ){
      sqlite3_free(p->a);
      memset(p, 0, sizeof(*p));
      sqlite3_result_error_nomem(pCtx);
      return;
    }
    p->nAlloc = n;
    p->a = a;
  }
  p->a[p->nUsed++] = y;
}

/*
** Compare to doubles for sorting using qsort()
*/
static int doubleCmp(const void *pA, const void *pB){
  double a = *(double*)pA;
  double b = *(double*)pB;
  if( a==b ) return 0;
  if( a<b ) return -1;
  return +1;
}

/*
** Called to compute the final output of percentile() and to clean
** up all allocated memory.
*/
static void percentFinal(sqlite3_context *pCtx){
  Percentile *p;
  unsigned i1, i2;
  double v1, v2;
  double ix, vx;
  p = (Percentile*)sqlite3_aggregate_context(pCtx, 0);
  if( p==0 ) return;
  if( p->a==0 ) return;
  if( p->nUsed ){
    qsort(p->a, p->nUsed, sizeof(double), doubleCmp);
    ix = (p->rPct-1.0)*(p->nUsed-1)*0.01;
    i1 = ix;
    i2 = ix==(double)i1 || i1==p->nUsed-1 ? i1 : i1+1;
    v1 = p->a[i1];
    v2 = p->a[i2];
    vx = v1 + (v2-v1)*(ix-i1);
    sqlite3_result_double(pCtx, vx);
  }
  sqlite3_free(p->a);
  memset(p, 0, sizeof(*p));
}


#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_percentile_init(
  sqlite3 *db, 
  char **pzErrMsg, 
  const sqlite3_api_routines *pApi
){
  int rc = SQLITE_OK;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  rc = sqlite3_create_function(db, "percentile", 2, SQLITE_UTF8, 0,
                               0, percentStep, percentFinal);
  return rc;
}

#
TESTSRC += \
  $(TOP)/ext/misc/amatch.c \
  $(TOP)/ext/misc/closure.c \
  $(TOP)/ext/misc/fuzzer.c \
  $(TOP)/ext/misc/ieee754.c \
  $(TOP)/ext/misc/nextchar.c \
  $(TOP)/ext/misc/percentile.c \
  $(TOP)/ext/misc/regexp.c \
  $(TOP)/ext/misc/spellfix.c \
  $(TOP)/ext/misc/wholenumber.c


#TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c
#TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c

  Tcl_Obj *CONST objv[]
){
  extern int sqlite3_amatch_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_closure_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_fuzzer_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_ieee_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_nextchar_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_percentile_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_regexp_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_spellfix_init(sqlite3*,char**,const sqlite3_api_routines*);
  extern int sqlite3_wholenumber_init(sqlite3*,char**,const sqlite3_api_routines*);
  static const struct {
    const char *zExtName;
    int (*pInit)(sqlite3*,char**,const sqlite3_api_routines*);
  } aExtension[] = {
    { "amatch",                sqlite3_amatch_init               },
    { "closure",               sqlite3_closure_init              },
    { "fuzzer",                sqlite3_fuzzer_init               },
    { "ieee754",               sqlite3_ieee_init                 },
    { "nextchar",              sqlite3_nextchar_init             },
    { "percentile",            sqlite3_percentile_init           },
    { "regexp",                sqlite3_regexp_init               },
    { "spellfix",              sqlite3_spellfix_init             },
    { "wholenumber",           sqlite3_wholenumber_init          },
  };
  sqlite3 *db;
  const char *zName;
  int i, j, rc;

# 2013-05-28
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is percentile.c extension
#

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

# Basic test of the percentile() function.
#
do_test percentile-1.0 {
  load_static_extension db percentile
  execsql {
    CREATE TABLE t1(x);
    INSERT INTO t1 VALUES(1),(4),(6),(7),(8),(9),(11),(11),(11);
  }
  execsql {SELECT percentile(x,0) FROM t1}
} {1.0}
foreach {in out} {
  100    11.0
   50     8.0
   12.5   4.0
   15     4.4
   20     5.2
   80    11.0
   89    11.0
} {
  do_test percentile-1.1.$in {
    execsql {SELECT percentile(x,$in) FROM t1}
  } $out
}

# Add some NULL values.
#
do_test percentile-1.2 {
  execsql {INSERT INTO t1 VALUES(NULL),(NULL);}
} {}
foreach {in out} {
  100    11.0
   50     8.0
   12.5   4.0
   15     4.4
   20     5.2
   80    11.0
   89    11.0
} {
  do_test percentile-1.3.$in {
    execsql {SELECT percentile(x,$in) FROM t1}
  } $out
}

# The second argument to percentile can change some, but not much.
#
do_test percentile-1.4 {
  catchsql {SELECT round(percentile(x, 15+0.000001*rowid),1) FROM t1}
} {0 4.4}
do_test percentile-1.5 {
  catchsql {SELECT round(percentile(x, 15+0.1*rowid),1) FROM t1}
} {1 {2nd argument to percentile() is not the same for all input rows}}

# Input values in a random order
#
do_test percentile-1.6 {
  execsql {
    CREATE TABLE t2(x);
    INSERT INTO t2 SELECT x+0.0 FROM t1 ORDER BY random();
  }
} {}
foreach {in out} {
  100    11.0
   50     8.0
   12.5   4.0
   15     4.4
   20     5.2
   80    11.0
   89    11.0
} {
  do_test percentile-1.7.$in {
    execsql {SELECT percentile(x,$in) FROM t2}
  } $out
}

# Wrong number of arguments
#
do_test percentile-1.8 {
  catchsql {SELECT percentile(x,0,1) FROM t1}
} {1 {wrong number of arguments to function percentile()}}
do_test percentile-1.9 {
  catchsql {SELECT percentile(x) FROM t1}
} {1 {wrong number of arguments to function percentile()}}

# Second argument must be numeric
#
do_test percentile-1.10 {
  catchsql {SELECT percentile(x,null) FROM t1}
} {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}}
do_test percentile-1.11 {
  catchsql {SELECT percentile(x,'fifty') FROM t1}
} {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}}
do_test percentile-1.12 {
  catchsql {SELECT percentile(x,x'3530') FROM t1}
} {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}}

# Second argument is out of range
#
do_test percentile-1.13 {
  catchsql {SELECT percentile(x,-0.0000001) FROM t1}
} {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}}
do_test percentile-1.14 {
  catchsql {SELECT percentile(x,100.0000001) FROM t1}
} {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}}

# First argument is not NULL and is not NUMERIC
#
do_test percentile-1.15 {
  catchsql {
    BEGIN;
    UPDATE t1 SET x='50' WHERE x IS NULL;
    SELECT percentile(x, 50) FROM t1;
  }
} {1 {1st argument to percentile() is not numeric}}
do_test percentile-1.16 {
  catchsql {
    ROLLBACK;
    BEGIN;
    UPDATE t1 SET x=x'3530' WHERE x IS NULL;
    SELECT percentile(x, 50) FROM t1;
  }
} {1 {1st argument to percentile() is not numeric}}
do_test percentile-1.17 {
  catchsql {
    ROLLBACK;
    SELECT percentile(x, 50) FROM t1;
  }
} {0 8.0}

# No non-NULL entries.
#
do_test percentile-1.18 {
  execsql {
    UPDATE t1 SET x=NULL;
    SELECT ifnull(percentile(x, 50),'NULL') FROM t1
  } 
} {NULL}

# Exactly one non-NULL entry
#
do_test percentile-1.19 {
  execsql {
    UPDATE t1 SET x=12345 WHERE rowid=5;
    SELECT percentile(x, 0), percentile(x, 50), percentile(x,100) FROM t1
  } 
} {12345.0 12345.0 12345.0}

# Infinity as an input
#
do_test percentile-1.20 {
  catchsql {
    DELETE FROM t1;
    INSERT INTO t1 SELECT x+0.0 FROM t2;
    UPDATE t1 SET x=1.0e300*1.0e300 WHERE rowid=5;
    SELECT percentile(x,50) from t1;
  }
} {1 {Inf input to percentile()}}
do_test percentile-1.21 {
  catchsql {
    UPDATE t1 SET x=-1.0e300*1.0e300 WHERE rowid=5;
    SELECT percentile(x,50) from t1;
  }
} {1 {Inf input to percentile()}}

# Million-row Inputs
#
do_test percentile-2.0 {
  load_static_extension db wholenumber
  execsql {
    CREATE VIRTUAL TABLE nums USING wholenumber;
    CREATE TABLE t3(x);
    INSERT INTO t3 SELECT value-1 FROM nums WHERE value BETWEEN 1 AND 500000;
    INSERT INTO t3 SELECT value*10 FROM nums
                    WHERE value BETWEEN 500000 AND 999999;
    SELECT count(*) FROM t3;
  }
} {1000000}
foreach {in out} {
    0          0.0
  100    9999990.0
   50    2749999.5
   10      99999.9
} {
  do_test percentile-2.1.$in {
    execsql {
      SELECT percentile(x, $in) from t3;
    }
  } $out
}

finish_test