**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.25 2001/09/16 00:13:27 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................

/*
** This function computes a hash on the name of a keyword.
** Case is not significant.
*/
int sqliteHashNoCase(const char *z, int n){
  int h = 0;
  int c;
  if( n<=0 ) n = strlen(z);
  while( n-- > 0 && (c = *z++)!=0 ){

    h = (h<<3) ^ h ^ UpperToLower[c];

  }
  if( h<0 ) h = -h;
  return h;
}

/*
** Some systems have stricmp().  Others have strcasecmp().  Because

**
*************************************************************************
** Utility functions used throughout sqlite.
**
** This file contains functions for allocating memory, comparing
** strings, and stuff like that.
**
** $Id: util.c,v 1.26 2001/09/18 22:17:44 drh Exp $
*/
#include "sqliteInt.h"
#include <stdarg.h>
#include <ctype.h>

/*
** If malloc() ever fails, this global variable gets set to 1.
................................................................................

/*
** This function computes a hash on the name of a keyword.
** Case is not significant.
*/
int sqliteHashNoCase(const char *z, int n){
  int h = 0;

  if( n<=0 ) n = strlen(z);

  while( n > 0  ){
    h = (h<<3) ^ h ^ UpperToLower[*z++];
    n--;
  }
  if( h<0 ) h = -h;
  return h;
}

/*
** Some systems have stricmp().  Others have strcasecmp().  Because

** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.71 2001/09/18 02:02:23 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
  int nElem;             /* The number of AggElems */
  int nHash;             /* Number of slots in apHash[] */
  AggElem **apHash;      /* A hash array for looking up AggElems by zKey */
  AggElem *pFirst;       /* A list of all AggElems */
};
struct AggElem {
  char *zKey;            /* The key to this AggElem */

  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
................................................................................
  memset(p, 0, sizeof(*p));
}

/*
** Add the given AggElem to the hash array
*/
static void AggEnhash(Agg *p, AggElem *pElem){
  int h = sqliteHashNoCase(pElem->zKey, 0) % p->nHash;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Change the size of the hash array to the amount given.
*/
................................................................................
}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey){
  AggElem *pElem;
  int i;
  if( p->nHash <= p->nElem*2 ){
    AggRehash(p, p->nElem*2 + 19);
  }
  if( p->nHash==0 ) return 1;
  pElem = sqliteMalloc( sizeof(AggElem) + strlen(zKey) + 1 +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  strcpy(pElem->zKey, zKey);

  AggEnhash(p, pElem);
  pElem->pNext = p->pFirst;
  p->pFirst = pElem;
  p->nElem++;
  p->pCurrent = pElem;
  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
................................................................................
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  AggElem *pFocus = p->pFirst;
  if( pFocus ){
    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"");
    pFocus = p->pCurrent = p->pFirst;
  }
  return pFocus;
}

/*
** Erase all information from a Set
................................................................................
*/
case OP_NewRecno: {
  int i = pOp->p1;
  int v = 0;
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
















    int res, rx, cnt;
    static int x = 0;
    union {
       char zBuf[sizeof(int)];
       int i;
    } ux;
    cnt = 0;
    do{
      if( x==0 || cnt>5 ){
        x = sqliteRandomInteger();
      }else{
        x += sqliteRandomByte() + 1;
      }
      if( x==0 ) continue;
      ux.zBuf[3] = x&0xff;
      ux.zBuf[2] = (x>>8)&0xff;
      ux.zBuf[1] = (x>>16)&0xff;
      ux.zBuf[0] = (x>>24)&0xff;
      v = ux.i;
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, &v, sizeof(v), &res);
      cnt++;
    }while( cnt<200 && rx==SQLITE_OK && res==0 );
    if( rx==SQLITE_OK && res==0 ){
      rc = SQLITE_FULL;
      goto abort_due_to_error;
    }
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
................................................................................
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  zKey = zStack[tos]; 
  nKey = aStack[tos].n;
  if( p->agg.nHash<=0 ){
    pElem = 0;
  }else{
    int h = sqliteHashNoCase(zKey, nKey-1) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( strcmp(pElem->zKey, zKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
  POPSTACK;
  break; 
}

/* Opcode: AggIncr P1 P2 *

** type to the other occurs as necessary.
** 
** Most of the code in this file is taken up by the sqliteVdbeExec()
** function which does the work of interpreting a VDBE program.
** But other routines are also provided to help in building up
** a program instruction by instruction.
**
** $Id: vdbe.c,v 1.72 2001/09/18 22:17:44 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
#include <unistd.h>

/*
** SQL is translated into a sequence of instructions to be
................................................................................
  int nElem;             /* The number of AggElems */
  int nHash;             /* Number of slots in apHash[] */
  AggElem **apHash;      /* A hash array for looking up AggElems by zKey */
  AggElem *pFirst;       /* A list of all AggElems */
};
struct AggElem {
  char *zKey;            /* The key to this AggElem */
  int nKey;              /* Number of bytes in the key, including '\0' at end */
  AggElem *pHash;        /* Next AggElem with the same hash on zKey */
  AggElem *pNext;        /* Next AggElem in a list of them all */
  Mem aMem[1];           /* The values for this AggElem */
};

/*
** A Set structure is used for quick testing to see if a value
................................................................................
  memset(p, 0, sizeof(*p));
}

/*
** Add the given AggElem to the hash array
*/
static void AggEnhash(Agg *p, AggElem *pElem){
  int h = sqliteHashNoCase(pElem->zKey, pElem->nKey) % p->nHash;
  pElem->pHash = p->apHash[h];
  p->apHash[h] = pElem;
}

/*
** Change the size of the hash array to the amount given.
*/
................................................................................
}

/*
** Insert a new element and make it the current element.  
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey, int nKey){
  AggElem *pElem;
  int i;
  if( p->nHash <= p->nElem*2 ){
    AggRehash(p, p->nElem*2 + 19);
  }
  if( p->nHash==0 ) return 1;
  pElem = sqliteMalloc( sizeof(AggElem) + nKey +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return 1;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  memcpy(pElem->zKey, zKey, nKey);
  pElem->nKey = nKey;
  AggEnhash(p, pElem);
  pElem->pNext = p->pFirst;
  p->pFirst = pElem;
  p->nElem++;
  p->pCurrent = pElem;
  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].s.flags = STK_Null;
................................................................................
*/
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  AggElem *pFocus = p->pFirst;
  if( pFocus ){
    p->pCurrent = pFocus;
  }else{
    AggInsert(p,"",1);
    pFocus = p->pCurrent = p->pFirst;
  }
  return pFocus;
}

/*
** Erase all information from a Set
................................................................................
*/
case OP_NewRecno: {
  int i = pOp->p1;
  int v = 0;
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    /* A probablistic algorithm is used to locate an unused rowid.
    ** We select a rowid at random and see if it exists in the table.
    ** If it does not exist, we have succeeded.  If the random rowid
    ** does exist, we select a new one and try again, up to 1000 times.
    **
    ** For a table with less than 2 billion entries, the probability
    ** of not finding a unused rowid is about 1.0e-300.  This is a 
    ** non-zero probability, but it is still vanishingly small and should
    ** never cause a problem.  You are much, much more likely to have a
    ** hardware failure than for this algorithm to fail.
    **
    ** To promote locality of reference for repetitive inserts, the
    ** first few attempts at chosing a rowid pick values just a little
    ** larger than the previous rowid.  This has been shown experimentally
    ** to double the speed of the COPY operation.
    */
    int res, rx, cnt;
    static int x = 0;
    union {
       char zBuf[sizeof(int)];
       int i;
    } ux;
    cnt = 0;
    do{
      if( cnt>5 ){
        x = sqliteRandomInteger();
      }else{
        x += sqliteRandomByte() + 1;
      }
      if( x==0 ) continue;
      ux.zBuf[3] = x&0xff;
      ux.zBuf[2] = (x>>8)&0xff;
      ux.zBuf[1] = (x>>16)&0xff;
      ux.zBuf[0] = (x>>24)&0xff;
      v = ux.i;
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, &v, sizeof(v), &res);
      cnt++;
    }while( cnt<1000 && rx==SQLITE_OK && res==0 );
    if( rx==SQLITE_OK && res==0 ){
      rc = SQLITE_FULL;
      goto abort_due_to_error;
    }
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
................................................................................
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( Stringify(p, tos) ) goto no_mem;
  zKey = zStack[tos]; 
  nKey = aStack[tos].n;
  if( p->agg.nHash<=0 ){
    pElem = 0;
  }else{
    int h = sqliteHashNoCase(zKey, nKey) % p->agg.nHash;
    for(pElem=p->agg.apHash[h]; pElem; pElem=pElem->pHash){
      if( pElem->nKey==nKey && memcmp(pElem->zKey, zKey, nKey)==0 ) break;
    }
  }
  if( pElem ){
    p->agg.pCurrent = pElem;
    pc = pOp->p2 - 1;
  }else{
    AggInsert(&p->agg, zKey, nKey);
    if( sqlite_malloc_failed ) goto no_mem;
  }
  POPSTACK;
  break; 
}

/* Opcode: AggIncr P1 P2 *

# 2001 September 15
#
# 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.
#
# This file implements tests for miscellanous features that were
# left out of other test files.
#
# $Id: misc1.test,v 1.1 2001/09/18 22:17:45 drh Exp $

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

# Test the creation and use of tables that have a large number
# of columns.
#
do_test misc1-1.1 {
  set cmd "CREATE TABLE manycol(x0 text"
  for {set i 1} {$i<=99} {incr i} {
    append cmd ",x$i text"
  }
  append cmd ")";
  execsql $cmd
  set cmd "INSERT INTO manycol VALUES(0"
  for {set i 1} {$i<=99} {incr i} {
    append cmd ",$i"
  }
  append cmd ")";
  execsql $cmd
  execsql "SELECT x99 FROM manycol"
} 99
do_test misc1-1.2 {
  execsql {SELECT x0, x10, x25, x50, x75 FROM manycol}
} {0 10 25 50 75}
do_test misc1-1.3 {
  for {set j 100} {$j<=1000} {incr j 100} {
    set cmd "INSERT INTO manycol VALUES($j"
    for {set i 1} {$i<=99} {incr i} {
      append cmd ",[expr {$i+$j}]"
    }
    append cmd ")"
    execsql $cmd
  }
  execsql {SELECT x50 FROM manycol ORDER BY x80}
} {50 150 250 350 450 550 650 750 850 950 1050}
do_test misc1-1.4 {
  execsql {SELECT x75 FROM manycol WHERE x50=350}
} 375
do_test misc1-1.5 {
  execsql {SELECT x50 FROM manycol WHERE x99=599}
} 550
do_test misc1-1.6 {
  execsql {CREATE INDEX manycol_idx1 ON manycol(x99)}
  execsql {SELECT x50 FROM manycol WHERE x99=899}
} 850
do_test misc1-1.7 {
  execsql {SELECT count(*) FROM manycol}
} 11
do_test misc1-1.8 {
  execsql {DELETE FROM manycol WHERE x98=1234}
  execsql {SELECT count(*) FROM manycol}
} 11
do_test misc1-1.9 {
  execsql {DELETE FROM manycol WHERE x98=998}
  execsql {SELECT count(*) FROM manycol}
} 10
do_test misc1-1.10 {
  execsql {DELETE FROM manycol WHERE x99=500}
  execsql {SELECT count(*) FROM manycol}
} 10
do_test misc1-1.11 {
  execsql {DELETE FROM manycol WHERE x99=599}
  execsql {SELECT count(*) FROM manycol}
} 9

# Check GROUP BY expressions that name two or more columns.
#
do_test misc1-2.1 {
  execsql {
    BEGIN TRANSACTION;
    CREATE TABLE agger(one text, two text, three text, four text);
    INSERT INTO agger VALUES(1, 'one', 'hello', 'yes');
    INSERT INTO agger VALUES(2, 'two', 'howdy', 'no');
    INSERT INTO agger VALUES(3, 'thr', 'howareya', 'yes');
    INSERT INTO agger VALUES(4, 'two', 'lothere', 'yes');
    INSERT INTO agger VALUES(5, 'one', 'atcha', 'yes');
    INSERT INTO agger VALUES(6, 'two', 'hello', 'no');
    COMMIT
  }
  execsql {SELECT count(*) FROM agger}
} 6
do_test misc1-2.2 {
  execsql {SELECT sum(one), two, four FROM agger
           GROUP BY two, four ORDER BY sum(one) desc}
} {8 two no 6 one yes 4 two yes 3 thr yes}

finish_test