** This file contains the C functions that implement date and time
** functions for SQLite.  
**
** There is only one exported symbol in this file - the function
** sqliteRegisterDateTimeFunctions() found at the bottom of the file.
** All other code has file scope.
**
** $Id: date.c,v 1.7 2004/01/07 03:29:16 drh Exp $
**
** NOTES:
**
** SQLite processes all times and dates as Julian Day numbers.  The
** dates and times are stored as the number of days since noon
** in Greenwich on November 24, 4714 B.C. according to the Gregorian
** calendar system.
................................................................................

  if( p->validJD ) return;
  if( p->validYMD ){
    Y = p->Y;
    M = p->M;
    D = p->D;
  }else{
    Y = 2000;
    M = 1;
    D = 1;
  }
  if( M<=2 ){
    Y--;
    M += 12;
  }
................................................................................
  p->s -= s;
  p->h = s/3600;
  s -= p->h*3600;
  p->m = s/60;
  p->s += s - p->m*60;
  p->validHMS = 1;
}


















/*
** Compute the difference (in days) between localtime and UTC (a.k.a. GMT)
** for the time value p where p is in UTC.
*/
static double localtimeOffset(DateTime *p){
  DateTime x, y;
  time_t t;
  struct tm *pTm;
  computeYMD(p);
  computeHMS(p);
  x = *p;

  if( x.Y<1971 || x.Y>=2038 ){
    x.Y = 2000;
    x.M = 1;
    x.D = 1;
    x.h = 0;
    x.m = 0;
    x.s = 0.0;
................................................................................
  y.s = pTm->tm_sec;
  sqliteOsLeaveMutex();
  y.validYMD = 1;
  y.validHMS = 1;
  y.validJD = 0;
  y.validTZ = 0;
  computeJD(&y);
  /* printf("x=%d-%02d-%02d %02d:%02d:%02d\n",x.Y,x.M,x.D,x.h,x.m,(int)x.s); */
  /* printf("y=%d-%02d-%02d %02d:%02d:%02d\n",y.Y,y.M,y.D,y.h,y.m,(int)y.s); */
  /* printf("diff=%.17g\n", y.rJD - x.rJD); */
  return y.rJD - x.rJD;
}

/*
** Process a modifier to a date-time stamp.  The modifiers are
** as follows:
**
................................................................................
      **
      ** Assuming the current time value is UTC (a.k.a. GMT), shift it to
      ** show local time.
      */
      if( strcmp(z, "localtime")==0 ){
        computeJD(p);
        p->rJD += localtimeOffset(p);
        p->validYMD = 0;
        p->validHMS = 0;
        p->validTZ = 0;
        rc = 0;
      }
      break;
    }
    case 'u': {
      /*
      **    unixepoch
      **
      ** Treat the current value of p->rJD as the number of
      ** seconds since 1970.  Convert to a real julian day number.
      */
      if( strcmp(z, "unixepoch")==0 && p->validJD ){
        p->rJD = p->rJD/86400.0 + 2440587.5;
        p->validYMD = 0;
        p->validHMS = 0;
        p->validTZ = 0;
        rc = 0;
      }else if( strcmp(z, "utc")==0 ){
        double c1;
        computeJD(p);
        c1 = localtimeOffset(p);
        p->rJD -= c1;
        p->validYMD = 0;
        p->validHMS = 0;
        p->validTZ = 0;
        p->rJD += c1 - localtimeOffset(p);
        p->validYMD = 0;
        p->validHMS = 0;
        p->validTZ = 0;
        rc = 0;
      }
      break;
    }
    case 'w': {
      /*
      **    weekday N
................................................................................
      ** Move the date to the same time on the next occurrance of
      ** weekday N where 0==Sunday, 1==Monday, and so forth.  If the
      ** date is already on the appropriate weekday, this is a no-op.
      */
      if( strncmp(z, "weekday ", 8)==0 && getValue(&z[8],&r)>0
                 && (n=r)==r && n>=0 && r<7 ){
        int Z;
        computeYMD(p);
        computeHMS(p);
        p->validTZ = 0;
        p->validJD = 0;
        computeJD(p);
        Z = p->rJD + 1.5;
        Z %= 7;
        if( Z>n ) Z -= 7;
        p->rJD += n - Z;
        p->validYMD = 0;
        p->validHMS = 0;
        rc = 0;
      }
      break;
    }
    case 's': {
      /*
      **    start of TTTTT
................................................................................
      strcpy(z, zMod);
      if( z[n-1]=='s' ){ z[n-1] = 0; n--; }
      computeJD(p);
      rc = 0;
      if( n==3 && strcmp(z,"day")==0 ){
        p->rJD += r;
      }else if( n==4 && strcmp(z,"hour")==0 ){
        computeJD(p);
        p->rJD += r/24.0;
      }else if( n==6 && strcmp(z,"minute")==0 ){
        computeJD(p);
        p->rJD += r/(24.0*60.0);
      }else if( n==6 && strcmp(z,"second")==0 ){
        computeJD(p);
        p->rJD += r/(24.0*60.0*60.0);
      }else if( n==5 && strcmp(z,"month")==0 ){
        int x, y;
        computeYMD(p);
        computeHMS(p);
        p->M += r;
        x = p->M>0 ? (p->M-1)/12 : (p->M-12)/12;
        p->Y += x;
        p->M -= x*12;
        p->validJD = 0;
        computeJD(p);
        y = r;
        if( y!=r ){
          p->rJD += (r - y)*30.0;
        }
      }else if( n==4 && strcmp(z,"year")==0 ){
        computeYMD(p);
        computeHMS(p);
        p->Y += r;
        p->validJD = 0;
        computeJD(p);
      }else{
        rc = 1;
      }
      p->validYMD = 0;
      p->validHMS = 0;
      p->validTZ = 0;
      break;
    }
    default: {
      break;
    }
  }
  return rc;
................................................................................
**
** Return YYYY-MM-DD HH:MM:SS
*/
static void datetimeFunc(sqlite_func *context, int argc, const char **argv){
  DateTime x;
  if( isDate(argc, argv, &x)==0 ){
    char zBuf[100];
    computeYMD(&x);
    computeHMS(&x);
    sprintf(zBuf, "%04d-%02d-%02d %02d:%02d:%02d",x.Y, x.M, x.D, x.h, x.m,
           (int)(x.s));
    sqlite_set_result_string(context, zBuf, -1);
  }
}

/*
................................................................................
  if( n<sizeof(zBuf) ){
    z = zBuf;
  }else{
    z = sqliteMalloc( n );
    if( z==0 ) return;
  }
  computeJD(&x);
  computeYMD(&x);
  computeHMS(&x);
  for(i=j=0; zFmt[i]; i++){
    if( zFmt[i]!='%' ){
      z[j++] = zFmt[i];
    }else{
      i++;
      switch( zFmt[i] ){
        case 'd':  sprintf(&z[j],"%02d",x.D); j+=2; break;

** This file contains the C functions that implement date and time
** functions for SQLite.  
**
** There is only one exported symbol in this file - the function
** sqliteRegisterDateTimeFunctions() found at the bottom of the file.
** All other code has file scope.
**
** $Id: date.c,v 1.8 2004/01/08 02:17:32 drh Exp $
**
** NOTES:
**
** SQLite processes all times and dates as Julian Day numbers.  The
** dates and times are stored as the number of days since noon
** in Greenwich on November 24, 4714 B.C. according to the Gregorian
** calendar system.
................................................................................

  if( p->validJD ) return;
  if( p->validYMD ){
    Y = p->Y;
    M = p->M;
    D = p->D;
  }else{
    Y = 2000;  /* If no YMD specified, assume 2000-Jan-01 */
    M = 1;
    D = 1;
  }
  if( M<=2 ){
    Y--;
    M += 12;
  }
................................................................................
  p->s -= s;
  p->h = s/3600;
  s -= p->h*3600;
  p->m = s/60;
  p->s += s - p->m*60;
  p->validHMS = 1;
}

/*
** Compute both YMD and HMS
*/
static void computeYMD_HMS(DateTime *p){
  computeYMD(p);
  computeHMS(p);
}

/*
** Clear the YMD and HMS and the TZ
*/
static void clearYMD_HMS_TZ(DateTime *p){
  p->validYMD = 0;
  p->validHMS = 0;
  p->validTZ = 0;
}

/*
** Compute the difference (in days) between localtime and UTC (a.k.a. GMT)
** for the time value p where p is in UTC.
*/
static double localtimeOffset(DateTime *p){
  DateTime x, y;
  time_t t;
  struct tm *pTm;


  x = *p;
  computeYMD_HMS(&x);
  if( x.Y<1971 || x.Y>=2038 ){
    x.Y = 2000;
    x.M = 1;
    x.D = 1;
    x.h = 0;
    x.m = 0;
    x.s = 0.0;
................................................................................
  y.s = pTm->tm_sec;
  sqliteOsLeaveMutex();
  y.validYMD = 1;
  y.validHMS = 1;
  y.validJD = 0;
  y.validTZ = 0;
  computeJD(&y);



  return y.rJD - x.rJD;
}

/*
** Process a modifier to a date-time stamp.  The modifiers are
** as follows:
**
................................................................................
      **
      ** Assuming the current time value is UTC (a.k.a. GMT), shift it to
      ** show local time.
      */
      if( strcmp(z, "localtime")==0 ){
        computeJD(p);
        p->rJD += localtimeOffset(p);
        clearYMD_HMS_TZ(p);


        rc = 0;
      }
      break;
    }
    case 'u': {
      /*
      **    unixepoch
      **
      ** Treat the current value of p->rJD as the number of
      ** seconds since 1970.  Convert to a real julian day number.
      */
      if( strcmp(z, "unixepoch")==0 && p->validJD ){
        p->rJD = p->rJD/86400.0 + 2440587.5;
        clearYMD_HMS_TZ(p);


        rc = 0;
      }else if( strcmp(z, "utc")==0 ){
        double c1;
        computeJD(p);
        c1 = localtimeOffset(p);
        p->rJD -= c1;
        clearYMD_HMS_TZ(p);


        p->rJD += c1 - localtimeOffset(p);



        rc = 0;
      }
      break;
    }
    case 'w': {
      /*
      **    weekday N
................................................................................
      ** Move the date to the same time on the next occurrance of
      ** weekday N where 0==Sunday, 1==Monday, and so forth.  If the
      ** date is already on the appropriate weekday, this is a no-op.
      */
      if( strncmp(z, "weekday ", 8)==0 && getValue(&z[8],&r)>0
                 && (n=r)==r && n>=0 && r<7 ){
        int Z;
        computeYMD_HMS(p);

        p->validTZ = 0;
        p->validJD = 0;
        computeJD(p);
        Z = p->rJD + 1.5;
        Z %= 7;
        if( Z>n ) Z -= 7;
        p->rJD += n - Z;
        clearYMD_HMS_TZ(p);

        rc = 0;
      }
      break;
    }
    case 's': {
      /*
      **    start of TTTTT
................................................................................
      strcpy(z, zMod);
      if( z[n-1]=='s' ){ z[n-1] = 0; n--; }
      computeJD(p);
      rc = 0;
      if( n==3 && strcmp(z,"day")==0 ){
        p->rJD += r;
      }else if( n==4 && strcmp(z,"hour")==0 ){

        p->rJD += r/24.0;
      }else if( n==6 && strcmp(z,"minute")==0 ){

        p->rJD += r/(24.0*60.0);
      }else if( n==6 && strcmp(z,"second")==0 ){

        p->rJD += r/(24.0*60.0*60.0);
      }else if( n==5 && strcmp(z,"month")==0 ){
        int x, y;
        computeYMD_HMS(p);

        p->M += r;
        x = p->M>0 ? (p->M-1)/12 : (p->M-12)/12;
        p->Y += x;
        p->M -= x*12;
        p->validJD = 0;
        computeJD(p);
        y = r;
        if( y!=r ){
          p->rJD += (r - y)*30.0;
        }
      }else if( n==4 && strcmp(z,"year")==0 ){
        computeYMD_HMS(p);

        p->Y += r;
        p->validJD = 0;
        computeJD(p);
      }else{
        rc = 1;
      }
      clearYMD_HMS_TZ(p);


      break;
    }
    default: {
      break;
    }
  }
  return rc;
................................................................................
**
** Return YYYY-MM-DD HH:MM:SS
*/
static void datetimeFunc(sqlite_func *context, int argc, const char **argv){
  DateTime x;
  if( isDate(argc, argv, &x)==0 ){
    char zBuf[100];
    computeYMD_HMS(&x);

    sprintf(zBuf, "%04d-%02d-%02d %02d:%02d:%02d",x.Y, x.M, x.D, x.h, x.m,
           (int)(x.s));
    sqlite_set_result_string(context, zBuf, -1);
  }
}

/*
................................................................................
  if( n<sizeof(zBuf) ){
    z = zBuf;
  }else{
    z = sqliteMalloc( n );
    if( z==0 ) return;
  }
  computeJD(&x);
  computeYMD_HMS(&x);

  for(i=j=0; zFmt[i]; i++){
    if( zFmt[i]!='%' ){
      z[j++] = zFmt[i];
    }else{
      i++;
      switch( zFmt[i] ){
        case 'd':  sprintf(&z[j],"%02d",x.D); j+=2; break;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the implementation of generic hash-tables
** used in SQLite.
**
** $Id: hash.c,v 1.10 2003/05/12 23:06:53 drh Exp $
*/
#include "sqliteInt.h"
#include <assert.h>

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**
................................................................................
static int intHash(const void *pKey, int nKey){
  return nKey ^ (nKey<<8) ^ (nKey>>8);
}
static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  return n2 - n1;
}


/*
** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
*/
static int ptrHash(const void *pKey, int nKey){
  uptr x = Addr(pKey);
  return x ^ (x<<8) ^ (x>>8);
}
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( pKey1==pKey2 ) return 0;
  if( pKey1<pKey2 ) return -1;
  return 1;
}


/*
** Hash and comparison functions when the mode is SQLITE_HASH_STRING
*/
static int strHash(const void *pKey, int nKey){
  return sqliteHashNoCase((const char*)pKey, nKey); 
}
................................................................................
** is a pointer to another function.  Specifically, the return value
** of hashFunction() is a pointer to a function that takes two parameters
** with types "const void*" and "int" and returns an "int".
*/
static int (*hashFunction(int keyClass))(const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intHash;
    case SQLITE_HASH_POINTER: return &ptrHash;
    case SQLITE_HASH_STRING:  return &strHash;
    case SQLITE_HASH_BINARY:  return &binHash;;
    default: break;
  }
  return 0;
}

................................................................................
**
** For help in interpreted the obscure C code in the function definition,
** see the header comment on the previous function.
*/
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intCompare;
    case SQLITE_HASH_POINTER: return &ptrCompare;
    case SQLITE_HASH_STRING:  return &strCompare;
    case SQLITE_HASH_BINARY:  return &binCompare;
    default: break;
  }
  return 0;
}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the implementation of generic hash-tables
** used in SQLite.
**
** $Id: hash.c,v 1.11 2004/01/08 02:17:33 drh Exp $
*/
#include "sqliteInt.h"
#include <assert.h>

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**
................................................................................
static int intHash(const void *pKey, int nKey){
  return nKey ^ (nKey<<8) ^ (nKey>>8);
}
static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  return n2 - n1;
}

#if 0 /* NOT USED */
/*
** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
*/
static int ptrHash(const void *pKey, int nKey){
  uptr x = Addr(pKey);
  return x ^ (x<<8) ^ (x>>8);
}
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  if( pKey1==pKey2 ) return 0;
  if( pKey1<pKey2 ) return -1;
  return 1;
}
#endif

/*
** Hash and comparison functions when the mode is SQLITE_HASH_STRING
*/
static int strHash(const void *pKey, int nKey){
  return sqliteHashNoCase((const char*)pKey, nKey); 
}
................................................................................
** is a pointer to another function.  Specifically, the return value
** of hashFunction() is a pointer to a function that takes two parameters
** with types "const void*" and "int" and returns an "int".
*/
static int (*hashFunction(int keyClass))(const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intHash;
    /* case SQLITE_HASH_POINTER: return &ptrHash; // NOT USED */
    case SQLITE_HASH_STRING:  return &strHash;
    case SQLITE_HASH_BINARY:  return &binHash;;
    default: break;
  }
  return 0;
}

................................................................................
**
** For help in interpreted the obscure C code in the function definition,
** see the header comment on the previous function.
*/
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intCompare;
    /* case SQLITE_HASH_POINTER: return &ptrCompare; // NOT USED */
    case SQLITE_HASH_STRING:  return &strCompare;
    case SQLITE_HASH_BINARY:  return &binCompare;
    default: break;
  }
  return 0;
}

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.5 2002/06/08 23:25:09 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;
................................................................................
**   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
**                           memcmp() is used to compare keys.
**
** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
** if the copyKey parameter to HashInit is 1.  
*/
#define SQLITE_HASH_INT       1
#define SQLITE_HASH_POINTER   2
#define SQLITE_HASH_STRING    3
#define SQLITE_HASH_BINARY    4

/*
** Access routines.  To delete, insert a NULL pointer.
*/
void sqliteHashInit(Hash*, int keytype, int copyKey);

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This is the header file for the generic hash-table implemenation
** used in SQLite.
**
** $Id: hash.h,v 1.6 2004/01/08 02:17:33 drh Exp $
*/
#ifndef _SQLITE_HASH_H_
#define _SQLITE_HASH_H_

/* Forward declarations of structures. */
typedef struct Hash Hash;
typedef struct HashElem HashElem;
................................................................................
**   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
**                           memcmp() is used to compare keys.
**
** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
** if the copyKey parameter to HashInit is 1.  
*/
#define SQLITE_HASH_INT       1
/* #define SQLITE_HASH_POINTER   2 // NOT USED */
#define SQLITE_HASH_STRING    3
#define SQLITE_HASH_BINARY    4

/*
** Access routines.  To delete, insert a NULL pointer.
*/
void sqliteHashInit(Hash*, int keytype, int copyKey);

*************************************************************************
** An tokenizer for SQL
**
** This file contains C code that splits an SQL input string up into
** individual tokens and sends those tokens one-by-one over to the
** parser for analysis.
**
** $Id: tokenize.c,v 1.66 2003/12/23 02:17:35 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include <stdlib.h>

/*
** All the keywords of the SQL language are stored as in a hash
** table composed of instances of the following structure.
*/
typedef struct Keyword Keyword;
struct Keyword {
  char *zName;             /* The keyword name */
  u16 len;                 /* Number of characters in the keyword */
  u16 tokenType;           /* The token value for this keyword */
  Keyword *pNext;          /* Next keyword with the same hash */
};

/*
** These are the keywords
*/
static Keyword aKeywordTable[] = {
  { "ABORT",             0, TK_ABORT,            0 },
  { "AFTER",             0, TK_AFTER,            0 },
  { "ALL",               0, TK_ALL,              0 },
  { "AND",               0, TK_AND,              0 },
  { "AS",                0, TK_AS,               0 },
  { "ASC",               0, TK_ASC,              0 },
  { "ATTACH",            0, TK_ATTACH,           0 },
  { "BEFORE",            0, TK_BEFORE,           0 },
  { "BEGIN",             0, TK_BEGIN,            0 },
  { "BETWEEN",           0, TK_BETWEEN,          0 },
  { "BY",                0, TK_BY,               0 },
  { "CASCADE",           0, TK_CASCADE,          0 },
  { "CASE",              0, TK_CASE,             0 },
  { "CHECK",             0, TK_CHECK,            0 },
  { "CLUSTER",           0, TK_CLUSTER,          0 },
  { "COLLATE",           0, TK_COLLATE,          0 },
  { "COMMIT",            0, TK_COMMIT,           0 },
  { "CONFLICT",          0, TK_CONFLICT,         0 },
  { "CONSTRAINT",        0, TK_CONSTRAINT,       0 },
  { "COPY",              0, TK_COPY,             0 },
  { "CREATE",            0, TK_CREATE,           0 },
  { "CROSS",             0, TK_JOIN_KW,          0 },
  { "DATABASE",          0, TK_DATABASE,         0 },
  { "DEFAULT",           0, TK_DEFAULT,          0 },
  { "DEFERRED",          0, TK_DEFERRED,         0 },
  { "DEFERRABLE",        0, TK_DEFERRABLE,       0 },
  { "DELETE",            0, TK_DELETE,           0 },
  { "DELIMITERS",        0, TK_DELIMITERS,       0 },
  { "DESC",              0, TK_DESC,             0 },
  { "DETACH",            0, TK_DETACH,           0 },
  { "DISTINCT",          0, TK_DISTINCT,         0 },
  { "DROP",              0, TK_DROP,             0 },
  { "END",               0, TK_END,              0 },
  { "EACH",              0, TK_EACH,             0 },
  { "ELSE",              0, TK_ELSE,             0 },
  { "EXCEPT",            0, TK_EXCEPT,           0 },
  { "EXPLAIN",           0, TK_EXPLAIN,          0 },
  { "FAIL",              0, TK_FAIL,             0 },
  { "FOR",               0, TK_FOR,              0 },
  { "FOREIGN",           0, TK_FOREIGN,          0 },
  { "FROM",              0, TK_FROM,             0 },
  { "FULL",              0, TK_JOIN_KW,          0 },
  { "GLOB",              0, TK_GLOB,             0 },
  { "GROUP",             0, TK_GROUP,            0 },
  { "HAVING",            0, TK_HAVING,           0 },
  { "IGNORE",            0, TK_IGNORE,           0 },
  { "IMMEDIATE",         0, TK_IMMEDIATE,        0 },
  { "IN",                0, TK_IN,               0 },
  { "INDEX",             0, TK_INDEX,            0 },
  { "INITIALLY",         0, TK_INITIALLY,        0 },
  { "INNER",             0, TK_JOIN_KW,          0 },
  { "INSERT",            0, TK_INSERT,           0 },
  { "INSTEAD",           0, TK_INSTEAD,          0 },
  { "INTERSECT",         0, TK_INTERSECT,        0 },
  { "INTO",              0, TK_INTO,             0 },
  { "IS",                0, TK_IS,               0 },
  { "ISNULL",            0, TK_ISNULL,           0 },
  { "JOIN",              0, TK_JOIN,             0 },
  { "KEY",               0, TK_KEY,              0 },
  { "LEFT",              0, TK_JOIN_KW,          0 },
  { "LIKE",              0, TK_LIKE,             0 },
  { "LIMIT",             0, TK_LIMIT,            0 },
  { "MATCH",             0, TK_MATCH,            0 },
  { "NATURAL",           0, TK_JOIN_KW,          0 },
  { "NOT",               0, TK_NOT,              0 },
  { "NOTNULL",           0, TK_NOTNULL,          0 },
  { "NULL",              0, TK_NULL,             0 },
  { "OF",                0, TK_OF,               0 },
  { "OFFSET",            0, TK_OFFSET,           0 },
  { "ON",                0, TK_ON,               0 },
  { "OR",                0, TK_OR,               0 },
  { "ORDER",             0, TK_ORDER,            0 },
  { "OUTER",             0, TK_JOIN_KW,          0 },
  { "PRAGMA",            0, TK_PRAGMA,           0 },
  { "PRIMARY",           0, TK_PRIMARY,          0 },
  { "RAISE",             0, TK_RAISE,            0 },
  { "REFERENCES",        0, TK_REFERENCES,       0 },
  { "REPLACE",           0, TK_REPLACE,          0 },
  { "RESTRICT",          0, TK_RESTRICT,         0 },
  { "RIGHT",             0, TK_JOIN_KW,          0 },
  { "ROLLBACK",          0, TK_ROLLBACK,         0 },
  { "ROW",               0, TK_ROW,              0 },
  { "SELECT",            0, TK_SELECT,           0 },
  { "SET",               0, TK_SET,              0 },
  { "STATEMENT",         0, TK_STATEMENT,        0 },
  { "TABLE",             0, TK_TABLE,            0 },
  { "TEMP",              0, TK_TEMP,             0 },
  { "TEMPORARY",         0, TK_TEMP,             0 },
  { "THEN",              0, TK_THEN,             0 },
  { "TRANSACTION",       0, TK_TRANSACTION,      0 },
  { "TRIGGER",           0, TK_TRIGGER,          0 },
  { "UNION",             0, TK_UNION,            0 },
  { "UNIQUE",            0, TK_UNIQUE,           0 },
  { "UPDATE",            0, TK_UPDATE,           0 },
  { "USING",             0, TK_USING,            0 },
  { "VACUUM",            0, TK_VACUUM,           0 },
  { "VALUES",            0, TK_VALUES,           0 },
  { "VIEW",              0, TK_VIEW,             0 },
  { "WHEN",              0, TK_WHEN,             0 },
  { "WHERE",             0, TK_WHERE,            0 },
};

/*
** This is the hash table
*/
#define KEY_HASH_SIZE 71
static Keyword *apHashTable[KEY_HASH_SIZE];


/*
** This function looks up an identifier to determine if it is a
** keyword.  If it is a keyword, the token code of that keyword is 
** returned.  If the input is not a keyword, TK_ID is returned.
*/
int sqliteKeywordCode(const char *z, int n){
  int h;
  Keyword *p;
  static char needInit = 1;
  if( needInit ){
    /* Initialize the keyword hash table */
    sqliteOsEnterMutex();
    if( needInit ){
      int i;
      int n;
      n = sizeof(aKeywordTable)/sizeof(aKeywordTable[0]);
      for(i=0; i<n; i++){
        aKeywordTable[i].len = strlen(aKeywordTable[i].zName);
        h = sqliteHashNoCase(aKeywordTable[i].zName, aKeywordTable[i].len);
        h %= KEY_HASH_SIZE;
        aKeywordTable[i].pNext = apHashTable[h];
        apHashTable[h] = &aKeywordTable[i];
      }
      needInit = 0;
    }
    sqliteOsLeaveMutex();
  }
  h = sqliteHashNoCase(z, n) % KEY_HASH_SIZE;
  for(p=apHashTable[h]; p; p=p->pNext){

    if( p->len==n && sqliteStrNICmp(p->zName, z, n)==0 ){
      return p->tokenType;
    }
  }
  return TK_ID;
}


/*
** If X is a character that can be used in an identifier then
** isIdChar[X] will be 1.  Otherwise isIdChar[X] will be 0.




**
** In this implementation, an identifier can be a string of
** alphabetic characters, digits, and "_" plus any character
** with the high-order bit set.  The latter rule means that
** any sequence of UTF-8 characters or characters taken from
** an extended ISO8859 character set can form an identifier.
*/
................................................................................
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* 1x */
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* 2x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 8x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 9x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Ax */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Bx */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Cx */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Dx */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Ex */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* Fx */
};


/*
** Return the length of the token that begins at z[0]. 
** Store the token type in *tokenType before returning.
*/
................................................................................
      return i;
    }
    case '?': {
      *tokenType = TK_VARIABLE;
      return 1;
    }
    default: {
      if( !isIdChar[*z] ){
        break;
      }
      for(i=1; isIdChar[z[i]]; i++){}
      *tokenType = sqliteKeywordCode((char*)z, i);
      return i;
    }
  }
  *tokenType = TK_ILLEGAL;
  return 1;
}

*************************************************************************
** An tokenizer for SQL
**
** This file contains C code that splits an SQL input string up into
** individual tokens and sends those tokens one-by-one over to the
** parser for analysis.
**
** $Id: tokenize.c,v 1.67 2004/01/08 02:17:33 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include <stdlib.h>

/*
** All the keywords of the SQL language are stored as in a hash
** table composed of instances of the following structure.
*/
typedef struct Keyword Keyword;
struct Keyword {
  char *zName;             /* The keyword name */
  u8 tokenType;            /* Token value for this keyword */
  u8 len;                  /* Length of this keyword */
  u8 iNext;                /* Index in aKeywordTable[] of next with same hash */
};

/*
** These are the keywords
*/
static Keyword aKeywordTable[] = {
  { "ABORT",             TK_ABORT,        },
  { "AFTER",             TK_AFTER,        },
  { "ALL",               TK_ALL,          },
  { "AND",               TK_AND,          },
  { "AS",                TK_AS,           },
  { "ASC",               TK_ASC,          },
  { "ATTACH",            TK_ATTACH,       },
  { "BEFORE",            TK_BEFORE,       },
  { "BEGIN",             TK_BEGIN,        },
  { "BETWEEN",           TK_BETWEEN,      },
  { "BY",                TK_BY,           },
  { "CASCADE",           TK_CASCADE,      },
  { "CASE",              TK_CASE,         },
  { "CHECK",             TK_CHECK,        },
  { "CLUSTER",           TK_CLUSTER,      },
  { "COLLATE",           TK_COLLATE,      },
  { "COMMIT",            TK_COMMIT,       },
  { "CONFLICT",          TK_CONFLICT,     },
  { "CONSTRAINT",        TK_CONSTRAINT,   },
  { "COPY",              TK_COPY,         },
  { "CREATE",            TK_CREATE,       },
  { "CROSS",             TK_JOIN_KW,      },
  { "DATABASE",          TK_DATABASE,     },
  { "DEFAULT",           TK_DEFAULT,      },
  { "DEFERRED",          TK_DEFERRED,     },
  { "DEFERRABLE",        TK_DEFERRABLE,   },
  { "DELETE",            TK_DELETE,       },
  { "DELIMITERS",        TK_DELIMITERS,   },
  { "DESC",              TK_DESC,         },
  { "DETACH",            TK_DETACH,       },
  { "DISTINCT",          TK_DISTINCT,     },
  { "DROP",              TK_DROP,         },
  { "END",               TK_END,          },
  { "EACH",              TK_EACH,         },
  { "ELSE",              TK_ELSE,         },
  { "EXCEPT",            TK_EXCEPT,       },
  { "EXPLAIN",           TK_EXPLAIN,      },
  { "FAIL",              TK_FAIL,         },
  { "FOR",               TK_FOR,          },
  { "FOREIGN",           TK_FOREIGN,      },
  { "FROM",              TK_FROM,         },
  { "FULL",              TK_JOIN_KW,      },
  { "GLOB",              TK_GLOB,         },
  { "GROUP",             TK_GROUP,        },
  { "HAVING",            TK_HAVING,       },
  { "IGNORE",            TK_IGNORE,       },
  { "IMMEDIATE",         TK_IMMEDIATE,    },
  { "IN",                TK_IN,           },
  { "INDEX",             TK_INDEX,        },
  { "INITIALLY",         TK_INITIALLY,    },
  { "INNER",             TK_JOIN_KW,      },
  { "INSERT",            TK_INSERT,       },
  { "INSTEAD",           TK_INSTEAD,      },
  { "INTERSECT",         TK_INTERSECT,    },
  { "INTO",              TK_INTO,         },
  { "IS",                TK_IS,           },
  { "ISNULL",            TK_ISNULL,       },
  { "JOIN",              TK_JOIN,         },
  { "KEY",               TK_KEY,          },
  { "LEFT",              TK_JOIN_KW,      },
  { "LIKE",              TK_LIKE,         },
  { "LIMIT",             TK_LIMIT,        },
  { "MATCH",             TK_MATCH,        },
  { "NATURAL",           TK_JOIN_KW,      },
  { "NOT",               TK_NOT,          },
  { "NOTNULL",           TK_NOTNULL,      },
  { "NULL",              TK_NULL,         },
  { "OF",                TK_OF,           },
  { "OFFSET",            TK_OFFSET,       },
  { "ON",                TK_ON,           },
  { "OR",                TK_OR,           },
  { "ORDER",             TK_ORDER,        },
  { "OUTER",             TK_JOIN_KW,      },
  { "PRAGMA",            TK_PRAGMA,       },
  { "PRIMARY",           TK_PRIMARY,      },
  { "RAISE",             TK_RAISE,        },
  { "REFERENCES",        TK_REFERENCES,   },
  { "REPLACE",           TK_REPLACE,      },
  { "RESTRICT",          TK_RESTRICT,     },
  { "RIGHT",             TK_JOIN_KW,      },
  { "ROLLBACK",          TK_ROLLBACK,     },
  { "ROW",               TK_ROW,          },
  { "SELECT",            TK_SELECT,       },
  { "SET",               TK_SET,          },
  { "STATEMENT",         TK_STATEMENT,    },
  { "TABLE",             TK_TABLE,        },
  { "TEMP",              TK_TEMP,         },
  { "TEMPORARY",         TK_TEMP,         },
  { "THEN",              TK_THEN,         },
  { "TRANSACTION",       TK_TRANSACTION,  },
  { "TRIGGER",           TK_TRIGGER,      },
  { "UNION",             TK_UNION,        },
  { "UNIQUE",            TK_UNIQUE,       },
  { "UPDATE",            TK_UPDATE,       },
  { "USING",             TK_USING,        },
  { "VACUUM",            TK_VACUUM,       },
  { "VALUES",            TK_VALUES,       },
  { "VIEW",              TK_VIEW,         },
  { "WHEN",              TK_WHEN,         },
  { "WHERE",             TK_WHERE,        },
};

/*
** This is the hash table
*/
#define KEY_HASH_SIZE 101
static u8 aiHashTable[KEY_HASH_SIZE];


/*
** This function looks up an identifier to determine if it is a
** keyword.  If it is a keyword, the token code of that keyword is 
** returned.  If the input is not a keyword, TK_ID is returned.
*/
int sqliteKeywordCode(const char *z, int n){
  int h, i;
  Keyword *p;
  static char needInit = 1;
  if( needInit ){
    /* Initialize the keyword hash table */
    sqliteOsEnterMutex();
    if( needInit ){

      int nk;
      nk = sizeof(aKeywordTable)/sizeof(aKeywordTable[0]);
      for(i=0; i<nk; i++){
        aKeywordTable[i].len = strlen(aKeywordTable[i].zName);
        h = sqliteHashNoCase(aKeywordTable[i].zName, aKeywordTable[i].len);
        h %= KEY_HASH_SIZE;
        aKeywordTable[i].iNext = aiHashTable[h];
        aiHashTable[h] = i+1;
      }
      needInit = 0;
    }
    sqliteOsLeaveMutex();
  }
  h = sqliteHashNoCase(z, n) % KEY_HASH_SIZE;
  for(i=aiHashTable[h]; i; i=p->iNext){
    p = &aKeywordTable[i-1];
    if( p->len==n && sqliteStrNICmp(p->zName, z, n)==0 ){
      return p->tokenType;
    }
  }
  return TK_ID;
}


/*
** If X is a character that can be used in an identifier and
** X&0x80==0 then isIdChar[X] will be 1.  If X&0x80==0x80 then
** X is always an identifier character.  (Hence all UTF-8
** characters can be part of an identifier).  isIdChar[X] will
** be 0 for every character in the lower 128 ASCII characters
** that cannot be used as part of an identifier.
**
** In this implementation, an identifier can be a string of
** alphabetic characters, digits, and "_" plus any character
** with the high-order bit set.  The latter rule means that
** any sequence of UTF-8 characters or characters taken from
** an extended ISO8859 character set can form an identifier.
*/
................................................................................
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* 1x */
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /* 2x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */
    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */








};


/*
** Return the length of the token that begins at z[0]. 
** Store the token type in *tokenType before returning.
*/
................................................................................
      return i;
    }
    case '?': {
      *tokenType = TK_VARIABLE;
      return 1;
    }
    default: {
      if( (*z&0x80)==0 && !isIdChar[*z] ){
        break;
      }
      for(i=1; (z[i]&0x80)!=0 || isIdChar[z[i]]; i++){}
      *tokenType = sqliteKeywordCode((char*)z, i);
      return i;
    }
  }
  *tokenType = TK_ILLEGAL;
  return 1;
}