/ Check-in [a0a1e701]
Login
Overview
Comment:The BTree changes are now integrated and the whole thing compiles and links. I have not yet tried to run it, though. (CVS 239)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:a0a1e701abc52a164d9b09a5426eb12af1fe6a4c
User & Date: drh 2001-09-13 14:46:10
Context
2001-09-13
15:21
The new Btree code runs, but it does not yet work. (CVS 240) check-in: 991ce811 user: drh tags: trunk
14:46
The BTree changes are now integrated and the whole thing compiles and links. I have not yet tried to run it, though. (CVS 239) check-in: a0a1e701 user: drh tags: trunk
13:46
The code is in place to replace GDBM with BTree. But I have not yet attempted to compile it. I am sure the code contains bugs. (CVS 238) check-in: 6ecc8b20 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to Makefile.in.

43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

68
69
70
71
72
73
74
...
117
118
119
120
121
122
123

124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

# The library that programs using readline() must link against.
#
LIBREADLINE = @TARGET_READLINE_LIBS@

# Object files for the SQLite library.
#
LIBOBJ = btree.o build.o dbbe.o dbbegdbm.o dbbemem.o delete.o expr.o insert.o \
         main.o pager.o parse.o printf.o random.o select.o table.o \
         tokenize.o update.o util.o vdbe.o where.o tclsqlite.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/build.c \
  $(TOP)/src/dbbe.c \
  $(TOP)/src/dbbe.h \
  $(TOP)/src/dbbegdbm.c \
  $(TOP)/src/dbbemem.c \
  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/pager.c \

  $(TOP)/src/parse.y \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/select.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqliteInt.h \
................................................................................
	$(BCC) -o lemon $(TOP)/tool/lemon.c
	cp $(TOP)/tool/lempar.c .

# Header files used by all library source files.
#
HDR = \
   sqlite.h  \

   $(TOP)/src/sqliteInt.h  \
   $(TOP)/src/dbbe.h  \
   $(TOP)/src/vdbe.h  \
   parse.h

btree.o:	$(TOP)/src/btree.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/btree.c

build.o:	$(TOP)/src/build.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/build.c

dbbe.o:	$(TOP)/src/dbbe.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/dbbe.c

dbbegdbm.o:	$(TOP)/src/dbbegdbm.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/dbbegdbm.c

dbbemem.o:	$(TOP)/src/dbbemem.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/dbbemem.c

main.o:	$(TOP)/src/main.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/main.c

pager.o:	$(TOP)/src/pager.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/pager.c

parse.o:	parse.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c parse.c

parse.h:	parse.c








|







|
|
<
<
<





>







 







>

<



|





<
<
<
<
<
<
<
<
<



|







43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59



60
61
62
63
64
65
66
67
68
69
70
71
72
...
115
116
117
118
119
120
121
122
123

124
125
126
127
128
129
130
131
132









133
134
135
136
137
138
139
140
141
142
143

# The library that programs using readline() must link against.
#
LIBREADLINE = @TARGET_READLINE_LIBS@

# Object files for the SQLite library.
#
LIBOBJ = btree.o build.o delete.o expr.o insert.o \
         main.o pager.o parse.o printf.o random.o select.o table.o \
         tokenize.o update.o util.o vdbe.o where.o tclsqlite.o

# All of the source code files.
#
SRC = \
  $(TOP)/src/btree.c \
  $(TOP)/src/btree.h \
  $(TOP)/src/build.c \



  $(TOP)/src/delete.c \
  $(TOP)/src/expr.c \
  $(TOP)/src/insert.c \
  $(TOP)/src/main.c \
  $(TOP)/src/pager.c \
  $(TOP)/src/pager.h \
  $(TOP)/src/parse.y \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/select.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqliteInt.h \
................................................................................
	$(BCC) -o lemon $(TOP)/tool/lemon.c
	cp $(TOP)/tool/lempar.c .

# Header files used by all library source files.
#
HDR = \
   sqlite.h  \
   $(TOP)/src/btree.h \
   $(TOP)/src/sqliteInt.h  \

   $(TOP)/src/vdbe.h  \
   parse.h

btree.o:	$(TOP)/src/btree.c $(HDR) $(TOP)/src/pager.h
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/btree.c

build.o:	$(TOP)/src/build.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/build.c










main.o:	$(TOP)/src/main.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/main.c

pager.o:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
	$(TCC) $(GDBM_FLAGS) -c $(TOP)/src/pager.c

parse.o:	parse.c $(HDR)
	$(TCC) $(GDBM_FLAGS) -c parse.c

parse.h:	parse.c

Changes to src/btree.c.

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
....
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.22 2001/09/13 13:46:56 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  if( !sqlitepager_isreadonly(pBt) ){
    rc = sqlitepager_write(pBt->page1);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    rc = newDatabase(pBt);
  }
  pBt->inTrans = 1;
................................................................................
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what database the record should be inserted into.  The cursor
** is left pointing at the new record.
*/
int sqliteBtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey,  int nKey,   /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;







|







 







|







 







|







17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
....
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.23 2001/09/13 14:46:10 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
  if( pBt->inTrans ) return SQLITE_ERROR;
  if( pBt->page1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }
  if( !sqlitepager_isreadonly(pBt->pPager) ){
    rc = sqlitepager_write(pBt->page1);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    rc = newDatabase(pBt);
  }
  pBt->inTrans = 1;
................................................................................
** Insert a new record into the BTree.  The key is given by (pKey,nKey)
** and the data is given by (pData,nData).  The cursor is used only to
** define what database the record should be inserted into.  The cursor
** is left pointing at the new record.
*/
int sqliteBtreeInsert(
  BtCursor *pCur,                /* Insert data into the table of this cursor */
  const void *pKey, int nKey,    /* The key of the new record */
  const void *pData, int nData   /* The data of the new record */
){
  Cell newCell;
  int rc;
  int loc;
  int szNew;
  MemPage *pPage;

Changes to src/btree.h.

20
21
22
23
24
25
26
27
28


29
30
31
32
33
34
35
..
58
59
60
61
62
63
64
65
66
67


**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.11 2001/09/13 13:46:56 drh Exp $
*/



typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree);
int sqliteBtreeClose(Btree*);

................................................................................
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
Pager *sqliteBtreePager(Btree*);
char *sqliteBtreeSanityCheck(Btree*, int*, int);
#endif









|

>
>







 







|


>
>
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
..
60
61
62
63
64
65
66
67
68
69
70
71
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This header file defines the interface that the sqlite B-Tree file
** subsystem.
**
** @(#) $Id: btree.h,v 1.12 2001/09/13 14:46:10 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_

typedef struct Btree Btree;
typedef struct BtCursor BtCursor;

int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree);
int sqliteBtreeClose(Btree*);

................................................................................
int sqliteBtreeGetMeta(Btree*, int*);
int sqliteBtreeUpdateMeta(Btree*, int*);


#ifdef SQLITE_TEST
int sqliteBtreePageDump(Btree*, int, int);
int sqliteBtreeCursorDump(BtCursor*, int*);
struct Pager *sqliteBtreePager(Btree*);
char *sqliteBtreeSanityCheck(Btree*, int*, int);
#endif

#endif /* _BTREE_H_ */

Changes to src/build.c.

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
45
46
47
48
49
50
51

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
...
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
...
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
...
339
340
341
342
343
344
345

346
347
348
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
...
438
439
440
441
442
443
444

445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
...
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
...
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
...
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
...
591
592
593
594
595
596
597

598
599
600
601
602
603
604
...
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
...
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
...
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
...
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
...
769
770
771
772
773
774
775

776
777
778
779
780
781
782
783
784
785
786
787
...
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
...
948
949
950
951
952
953
954

955
956
957
958
959
960
961
962
963
964
965
...
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
....
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
....
1023
1024
1025
1026
1027
1028
1029

1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
....
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
....
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
**     DROP TABLE
**     CREATE INDEX
**     DROP INDEX
**     creating expressions and ID lists
**     COPY
**     VACUUM
**
** $Id: build.c,v 1.29 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
** that statement.  Prior action routines should have already
................................................................................
** This routine just has to execute the VDBE code.
**
** Note that if an error occurred, it might be the case that
** no VDBE code was generated.
*/
void sqliteExec(Parse *pParse){
  int rc = SQLITE_OK;

  if( sqlite_malloc_failed ) return;
  if( pParse->pVdbe ){
    if( pParse->explain ){
      rc = sqliteVdbeList(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg);
    }else{
      FILE *trace = (pParse->db->flags & SQLITE_VdbeTrace)!=0 ? stderr : 0;
      sqliteVdbeTrace(pParse->pVdbe, trace);
      rc = sqliteVdbeExec(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg, pParse->db->pBusyArg,
                          pParse->db->xBusyCallback);
    }
    sqliteVdbeDelete(pParse->pVdbe);
    pParse->pVdbe = 0;
    pParse->colNamesSet = 0;
    pParse->rc = rc;
  }
}
................................................................................
** See also: sqliteRollbackInternalChanges()
*/
void sqliteCommitInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( pTable->isDelete ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isCommit==0 ){
        pTable->isCommit = 1;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( pIndex->isDelete ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isCommit==0 ){
        pIndex->isCommit = 1;
      }
    }
................................................................................
** See also: sqliteCommitInternalChanges()
*/
void sqliteRollbackInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( !pTable->isCommit ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isDelete ){
        pTable->isDelete = 0;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( !pIndex->isCommit ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isDelete ){
        pIndex->isDelete = 0;
      }
    }
................................................................................
** The new table is constructed in files of the pParse structure.  As
** more of the CREATE TABLE statement is parsed, additional action
** routines are called to build up more of the table.
*/
void sqliteStartTable(Parse *pParse, Token *pStart, Token *pName){
  Table *pTable;
  char *zName;


  pParse->sFirstToken = *pStart;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pTable = sqliteFindTable(pParse->db, zName);
  if( pTable!=0 ){
    sqliteSetNString(&pParse->zErrMsg, "table ", 0, pName->z, pName->n,
        " already exists", 0, 0);
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  if( sqliteFindIndex(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already an index named ", 
       zName, 0);
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  pTable = sqliteMalloc( sizeof(Table) );
  if( pTable==0 ) return;
  pTable->zName = zName;
  pTable->pHash = 0;
  pTable->nCol = 0;
  pTable->aCol = 0;
  pTable->pIndex = 0;
  if( pParse->pNewTable ) sqliteDeleteTable(pParse->db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (pParse->db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
  }
}

................................................................................
** the master table because we just connected to the database, so 
** the entry for this table already exists in the master table.
** We do not want to create it again.
*/
void sqliteEndTable(Parse *pParse, Token *pEnd){
  Table *p;
  int h;


  if( pEnd==0 || pParse->nErr || sqlite_malloc_failed ) return;
  p = pParse->pNewTable;
  if( p==0 ) return;

  /* Add the table to the in-memory representation of the database
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(p->zName, 0) % N_HASH;
    p->pHash = pParse->db->apTblHash[h];
    pParse->db->apTblHash[h] = p;
    pParse->pNewTable = 0;
    pParse->db->nTable++;
    db->flags |= SQLITE_InternChanges;
  }

  /* If not initializing, then create the table on disk.
  */
  if( !pParse->initFlag ){
    static VdbeOp addTable[] = {
................................................................................
    n = (int)pEnd->z - (int)pParse->sFirstToken.z + 1;
    base = sqliteVdbeAddOpList(v, ArraySize(addTable), addTable);
    sqliteVdbeChangeP3(v, base+3, p->zName, 0);
    sqliteVdbeTableRootAddr(v, &p->tnum);
    sqliteVdbeChangeP3(v, base+5, p->zName, 0);
    sqliteVdbeChangeP3(v, base+6, pParse->sFirstToken.z, n);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
}

/*
** Given a token, look up a table with that name.  If not found, leave
................................................................................

/*
** This routine is called to do the work of a DROP TABLE statement.
** pName is the name of the table to be dropped.
*/
void sqliteDropTable(Parse *pParse, Token *pName){
  Table *pTable;
  int h;
  Vdbe *v;
  int base;

  if( pParse->nErr || sqlite_malloc_failed ) return;
  pTable = sqliteTableFromToken(pParse, pName);
  if( pTable==0 ) return;
  if( pTable->readOnly ){
................................................................................
  ** deletion occurs inside of sqliteCommitInternalChanges().
  **
  ** Exception: if the SQL statement began with the EXPLAIN keyword,
  ** then no changes should be made.
  */
  if( !pParse->explain ){
    pTable->isDelete = 1;
    db->flags |= SQLITE_InternChanges;
  }
}

/*
** Create a new index for an SQL table.  pIndex is the name of the index 
** and pTable is the name of the table that is to be indexed.  Both will 
** be NULL for a primary key.  In that case, use pParse->pNewTable as the 
................................................................................
  Token *pEnd      /* The ")" that closes the CREATE INDEX statement */
){
  Table *pTab;     /* Table to be indexed */
  Index *pIndex;   /* The index to be created */
  char *zName = 0;
  int i, j, h;
  Token nullId;    /* Fake token for an empty ID list */


  if( pParse->nErr || sqlite_malloc_failed ) goto exit_create_index;

  /*
  ** Find the table that is to be indexed.  Return early if not found.
  */
  if( pTable!=0 ){
................................................................................
  if( pName ){
    zName = sqliteTableNameFromToken(pName);
  }else{
    zName = 0;
    sqliteSetString(&zName, pTab->zName, "__primary_key", 0);
  }
  if( zName==0 ) goto exit_create_index;
  if( sqliteFindIndex(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "index ", zName, 
       " already exists", 0);
    pParse->nErr++;
    goto exit_create_index;
  }
  if( sqliteFindTable(pParse->db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already a table named ",
       zName, 0);
    pParse->nErr++;
    goto exit_create_index;
  }

  /* If pList==0, it means this routine was called to make a primary
................................................................................
  }

  /* Link the new Index structure to its table and to the other
  ** in-memory database structures.
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
    pIndex->pHash = pParse->db->apIdxHash[h];
    pParse->db->apIdxHash[h] = pIndex;
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 0 then create the index on disk.  This
  ** involves writing the index into the master table and filling in the
................................................................................
    int n;
    Vdbe *v = pParse->pVdbe;
    int lbl1, lbl2;
    int i;

    v = sqliteGetVdbe(pParse);
    if( v==0 ) goto exit_create_index;
    if( pTable!=0 && (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    sqliteVdbeAddOp(v, OP_Open, 1, pIndex->tnum, pIndex->zName, 0);
    if( pStart && pEnd ){
      int base;
      n = (int)pEnd->z - (int)pStart->z + 1;
................................................................................
      sqliteVdbeIndexRootAddr(v, &pIndex->tnum);
      sqliteVdbeChangeP3(v, base+5, pTab->zName, 0);
      sqliteVdbeChangeP3(v, base+6, pStart->z, n);
    }
    lbl1 = sqliteVdbeMakeLabel(v);
    lbl2 = sqliteVdbeMakeLabel(v);
    sqliteVdbeAddOp(v, OP_Next, 0, lbl2, 0, lbl1);
    sqliteVdbeAddOp(v, OP_GetRecno, 0, 0, 0, 0);
    for(i=0; i<pIndex->nColumn; i++){
      sqliteVdbeAddOp(v, OP_Column, 0, pIndex->aiColumn[i], 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIndex->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, lbl1, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, lbl2);
    sqliteVdbeAddOp(v, OP_Close, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( pTable!=0 && (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Reclaim memory on an EXPLAIN call.
  */
  if( pParse->explain ){
................................................................................
/*
** This routine will drop an existing named index.
*/
void sqliteDropIndex(Parse *pParse, Token *pName){
  Index *pIndex;
  char *zName;
  Vdbe *v;


  if( pParse->nErr || sqlite_malloc_failed ) return;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pIndex = sqliteFindIndex(pParse->db, zName);
  sqliteFree(zName);
  if( pIndex==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such index: ", 0, 
        pName->z, pName->n, 0);
    pParse->nErr++;
    return;
  }
................................................................................
    static VdbeOp dropIndex[] = {
      { OP_Open,       0, 2,       0},
      { OP_String,     0, 0,       0}, /* 1 */
      { OP_Next,       0, ADDR(8), 0}, /* 2 */
      { OP_Dup,        0, 0,       0},
      { OP_Column,     0, 1,       0},
      { OP_Ne,         0, ADDR(2), 0},
      { OP_Key,        0, 0,       0},
      { OP_Delete,     0, 0,       0},
      { OP_Destroy,    0, 0,       0}, /* 8 */
      { OP_Close,      0, 0,       0},
    };
    int base;

    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    base = sqliteVdbeAddOpList(v, ArraySize(dropIndex), dropIndex);
    sqliteVdbeChangeP1(v, base+8, pIndex->tnum);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Mark the internal Index structure for deletion by the
  ** sqliteCommitInternalChanges routine.
  */
................................................................................
){
  Table *pTab;
  char *zTab;
  int i, j;
  Vdbe *v;
  int addr, end;
  Index *pIdx;


  zTab = sqliteTableNameFromToken(pTableName);
  if( sqlite_malloc_failed || zTab==0 ) goto copy_cleanup;
  pTab = sqliteFindTable(pParse->db, zTab);
  sqliteFree(zTab);
  if( pTab==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such table: ", 0, 
        pTableName->z, pTableName->n, 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
................................................................................
    sqliteSetString(&pParse->zErrMsg, "table ", pTab->zName,
        " may not be modified", 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v ){
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    addr = sqliteVdbeAddOp(v, OP_FileOpen, 0, 0, 0, 0);
    sqliteVdbeChangeP3(v, addr, pFilename->z, pFilename->n);
    sqliteVdbeDequoteP3(v, addr);
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, i++){
................................................................................
        sqliteVdbeAddOp(v, OP_FileColumn, pIdx->aiColumn[j], 0, 0, 0);
      }
      sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_PutIdx, i, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, end);
    if( (pParse->db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
  
copy_cleanup:
  return;
}
................................................................................
** The non-standard VACUUM command is used to clean up the database,
** collapse free space, etc.  It is modelled after the VACUUM command
** in PostgreSQL.
*/
void sqliteVacuum(Parse *pParse, Token *pTableName){
  char *zName;
  Vdbe *v;


  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( pTableName ){
    zName = sqliteTableNameFromToken(pTableName);
  }else{
    zName = 0;
  }
  if( zName && sqliteFindIndex(pParse->db, zName)==0
    && sqliteFindTable(pParse->db, zName)==0 ){
    sqliteSetString(&pParse->zErrMsg, "no such table or index: ", zName, 0);
    pParse->nErr++;
    goto vacuum_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto vacuum_cleanup;
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }
  if( zName ){
    sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, zName, 0);
  }else{
    int h;
    Table *pTab;
    Index *pIdx;
    for(h=0; h<N_HASH; h++){
      for(pTab=pParse->db->apTblHash[h]; pTab; pTab=pTab->pHash){
        sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pTab->zName, 0);
        for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pIdx->zName, 0);
        }
      }
    }
  }
  if( (pParse->db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

vacuum_cleanup:
  sqliteFree(zName);
  return;
}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( db->flags & SQLITE_InTrans ) return;
  v = sqliteGetVdbe(pParse);
................................................................................
  db->flags |= SQLITE_InTrans;
}

/*
** Commit a transaction
*/
void sqliteCommitTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
................................................................................
  db->flags &= ~SQLITE_InTrans;
}

/*
** Rollback a transaction
*/
void sqliteRollbackTransaction(Parse *pParse){
  int rc;
  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
  if( v ){
    sqliteVdbeAddOp(v, OP_Rollback, 0, 0, 0, 0);
  }
  db->flags &= ~SQLITE_InTrans;
}







|







 







>






|


|
|







 







|










|







 







|










|







 







>




|







|













|

|







 







>









|
|

|







 







|







 







<







 







|







 







>







 







|





|







 







|
|







 







|







 







|









|







 







>




|







 







|






|




|







 







>



|







 







|







 







|







 







>







|
|






|









|







|












<







 







<







 







<












29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
...
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
...
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
...
340
341
342
343
344
345
346
347
348
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
382
383
...
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
...
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
...
514
515
516
517
518
519
520

521
522
523
524
525
526
527
...
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
...
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
...
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
...
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
...
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
...
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
...
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
...
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
...
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
...
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
....
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
....
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081

1082
1083
1084
1085
1086
1087
1088
....
1092
1093
1094
1095
1096
1097
1098

1099
1100
1101
1102
1103
1104
1105
....
1109
1110
1111
1112
1113
1114
1115

1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
**     DROP TABLE
**     CREATE INDEX
**     DROP INDEX
**     creating expressions and ID lists
**     COPY
**     VACUUM
**
** $Id: build.c,v 1.30 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is called after a single SQL statement has been
** parsed and we want to execute the VDBE code to implement 
** that statement.  Prior action routines should have already
................................................................................
** This routine just has to execute the VDBE code.
**
** Note that if an error occurred, it might be the case that
** no VDBE code was generated.
*/
void sqliteExec(Parse *pParse){
  int rc = SQLITE_OK;
  sqlite *db = pParse->db;
  if( sqlite_malloc_failed ) return;
  if( pParse->pVdbe ){
    if( pParse->explain ){
      rc = sqliteVdbeList(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg);
    }else{
      FILE *trace = (db->flags & SQLITE_VdbeTrace)!=0 ? stderr : 0;
      sqliteVdbeTrace(pParse->pVdbe, trace);
      rc = sqliteVdbeExec(pParse->pVdbe, pParse->xCallback, pParse->pArg, 
                          &pParse->zErrMsg, db->pBusyArg,
                          db->xBusyCallback);
    }
    sqliteVdbeDelete(pParse->pVdbe);
    pParse->pVdbe = 0;
    pParse->colNamesSet = 0;
    pParse->rc = rc;
  }
}
................................................................................
** See also: sqliteRollbackInternalChanges()
*/
void sqliteCommitInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = db->apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( pTable->isDelete ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isCommit==0 ){
        pTable->isCommit = 1;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = db->apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( pIndex->isDelete ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isCommit==0 ){
        pIndex->isCommit = 1;
      }
    }
................................................................................
** See also: sqliteCommitInternalChanges()
*/
void sqliteRollbackInternalChanges(sqlite *db){
  int i;
  if( (db->flags & SQLITE_InternChanges)==0 ) return;
  for(i=0; i<N_HASH; i++){
    Table *pTable, *pNext;
    for(pTable = db->apTblHash[i]; pTable; pTable=pNext){
      pNext = pTable->pHash;
      if( !pTable->isCommit ){
        sqliteDeleteTable(db, pTable);
      }else if( pTable->isDelete ){
        pTable->isDelete = 0;
      }
    }
  }
  for(i=0; i<N_HASH; i++){
    Index *pIndex, *pNext;
    for(pIndex = db->apIdxHash[i]; pIndex; pIndex=pNext){
      pNext = pIndex->pHash;
      if( !pIndex->isCommit ){
        sqliteUnlinkAndDeleteIndex(db, pIndex);
      }else if( pIndex->isDelete ){
        pIndex->isDelete = 0;
      }
    }
................................................................................
** The new table is constructed in files of the pParse structure.  As
** more of the CREATE TABLE statement is parsed, additional action
** routines are called to build up more of the table.
*/
void sqliteStartTable(Parse *pParse, Token *pStart, Token *pName){
  Table *pTable;
  char *zName;
  sqlite *db = pParse->db;

  pParse->sFirstToken = *pStart;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pTable = sqliteFindTable(db, zName);
  if( pTable!=0 ){
    sqliteSetNString(&pParse->zErrMsg, "table ", 0, pName->z, pName->n,
        " already exists", 0, 0);
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  if( sqliteFindIndex(db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already an index named ", 
       zName, 0);
    sqliteFree(zName);
    pParse->nErr++;
    return;
  }
  pTable = sqliteMalloc( sizeof(Table) );
  if( pTable==0 ) return;
  pTable->zName = zName;
  pTable->pHash = 0;
  pTable->nCol = 0;
  pTable->aCol = 0;
  pTable->pIndex = 0;
  if( pParse->pNewTable ) sqliteDeleteTable(db, pParse->pNewTable);
  pParse->pNewTable = pTable;
  if( !pParse->initFlag && (db->flags & SQLITE_InTrans)==0 ){
    Vdbe *v = sqliteGetVdbe(pParse);
    if( v ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
  }
}

................................................................................
** the master table because we just connected to the database, so 
** the entry for this table already exists in the master table.
** We do not want to create it again.
*/
void sqliteEndTable(Parse *pParse, Token *pEnd){
  Table *p;
  int h;
  sqlite *db = pParse->db;

  if( pEnd==0 || pParse->nErr || sqlite_malloc_failed ) return;
  p = pParse->pNewTable;
  if( p==0 ) return;

  /* Add the table to the in-memory representation of the database
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(p->zName, 0) % N_HASH;
    p->pHash = db->apTblHash[h];
    db->apTblHash[h] = p;
    pParse->pNewTable = 0;
    db->nTable++;
    db->flags |= SQLITE_InternChanges;
  }

  /* If not initializing, then create the table on disk.
  */
  if( !pParse->initFlag ){
    static VdbeOp addTable[] = {
................................................................................
    n = (int)pEnd->z - (int)pParse->sFirstToken.z + 1;
    base = sqliteVdbeAddOpList(v, ArraySize(addTable), addTable);
    sqliteVdbeChangeP3(v, base+3, p->zName, 0);
    sqliteVdbeTableRootAddr(v, &p->tnum);
    sqliteVdbeChangeP3(v, base+5, p->zName, 0);
    sqliteVdbeChangeP3(v, base+6, pParse->sFirstToken.z, n);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
}

/*
** Given a token, look up a table with that name.  If not found, leave
................................................................................

/*
** This routine is called to do the work of a DROP TABLE statement.
** pName is the name of the table to be dropped.
*/
void sqliteDropTable(Parse *pParse, Token *pName){
  Table *pTable;

  Vdbe *v;
  int base;

  if( pParse->nErr || sqlite_malloc_failed ) return;
  pTable = sqliteTableFromToken(pParse, pName);
  if( pTable==0 ) return;
  if( pTable->readOnly ){
................................................................................
  ** deletion occurs inside of sqliteCommitInternalChanges().
  **
  ** Exception: if the SQL statement began with the EXPLAIN keyword,
  ** then no changes should be made.
  */
  if( !pParse->explain ){
    pTable->isDelete = 1;
    pParse->db->flags |= SQLITE_InternChanges;
  }
}

/*
** Create a new index for an SQL table.  pIndex is the name of the index 
** and pTable is the name of the table that is to be indexed.  Both will 
** be NULL for a primary key.  In that case, use pParse->pNewTable as the 
................................................................................
  Token *pEnd      /* The ")" that closes the CREATE INDEX statement */
){
  Table *pTab;     /* Table to be indexed */
  Index *pIndex;   /* The index to be created */
  char *zName = 0;
  int i, j, h;
  Token nullId;    /* Fake token for an empty ID list */
  sqlite *db = pParse->db;

  if( pParse->nErr || sqlite_malloc_failed ) goto exit_create_index;

  /*
  ** Find the table that is to be indexed.  Return early if not found.
  */
  if( pTable!=0 ){
................................................................................
  if( pName ){
    zName = sqliteTableNameFromToken(pName);
  }else{
    zName = 0;
    sqliteSetString(&zName, pTab->zName, "__primary_key", 0);
  }
  if( zName==0 ) goto exit_create_index;
  if( sqliteFindIndex(db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "index ", zName, 
       " already exists", 0);
    pParse->nErr++;
    goto exit_create_index;
  }
  if( sqliteFindTable(db, zName) ){
    sqliteSetString(&pParse->zErrMsg, "there is already a table named ",
       zName, 0);
    pParse->nErr++;
    goto exit_create_index;
  }

  /* If pList==0, it means this routine was called to make a primary
................................................................................
  }

  /* Link the new Index structure to its table and to the other
  ** in-memory database structures.
  */
  if( pParse->explain==0 ){
    h = sqliteHashNoCase(pIndex->zName, 0) % N_HASH;
    pIndex->pHash = db->apIdxHash[h];
    db->apIdxHash[h] = pIndex;
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    db->flags |= SQLITE_InternChanges;
  }

  /* If the initFlag is 0 then create the index on disk.  This
  ** involves writing the index into the master table and filling in the
................................................................................
    int n;
    Vdbe *v = pParse->pVdbe;
    int lbl1, lbl2;
    int i;

    v = sqliteGetVdbe(pParse);
    if( v==0 ) goto exit_create_index;
    if( pTable!=0 && (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    sqliteVdbeAddOp(v, OP_Open, 1, pIndex->tnum, pIndex->zName, 0);
    if( pStart && pEnd ){
      int base;
      n = (int)pEnd->z - (int)pStart->z + 1;
................................................................................
      sqliteVdbeIndexRootAddr(v, &pIndex->tnum);
      sqliteVdbeChangeP3(v, base+5, pTab->zName, 0);
      sqliteVdbeChangeP3(v, base+6, pStart->z, n);
    }
    lbl1 = sqliteVdbeMakeLabel(v);
    lbl2 = sqliteVdbeMakeLabel(v);
    sqliteVdbeAddOp(v, OP_Next, 0, lbl2, 0, lbl1);
    sqliteVdbeAddOp(v, OP_Recno, 0, 0, 0, 0);
    for(i=0; i<pIndex->nColumn; i++){
      sqliteVdbeAddOp(v, OP_Column, 0, pIndex->aiColumn[i], 0, 0);
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIndex->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, lbl1, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, lbl2);
    sqliteVdbeAddOp(v, OP_Close, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Close, 0, 0, 0, 0);
    if( pTable!=0 && (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Reclaim memory on an EXPLAIN call.
  */
  if( pParse->explain ){
................................................................................
/*
** This routine will drop an existing named index.
*/
void sqliteDropIndex(Parse *pParse, Token *pName){
  Index *pIndex;
  char *zName;
  Vdbe *v;
  sqlite *db = pParse->db;

  if( pParse->nErr || sqlite_malloc_failed ) return;
  zName = sqliteTableNameFromToken(pName);
  if( zName==0 ) return;
  pIndex = sqliteFindIndex(db, zName);
  sqliteFree(zName);
  if( pIndex==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such index: ", 0, 
        pName->z, pName->n, 0);
    pParse->nErr++;
    return;
  }
................................................................................
    static VdbeOp dropIndex[] = {
      { OP_Open,       0, 2,       0},
      { OP_String,     0, 0,       0}, /* 1 */
      { OP_Next,       0, ADDR(8), 0}, /* 2 */
      { OP_Dup,        0, 0,       0},
      { OP_Column,     0, 1,       0},
      { OP_Ne,         0, ADDR(2), 0},
      { OP_Recno,      0, 0,       0},
      { OP_Delete,     0, 0,       0},
      { OP_Destroy,    0, 0,       0}, /* 8 */
      { OP_Close,      0, 0,       0},
    };
    int base;

    if( (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    base = sqliteVdbeAddOpList(v, ArraySize(dropIndex), dropIndex);
    sqliteVdbeChangeP1(v, base+8, pIndex->tnum);
    if( (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }

  /* Mark the internal Index structure for deletion by the
  ** sqliteCommitInternalChanges routine.
  */
................................................................................
){
  Table *pTab;
  char *zTab;
  int i, j;
  Vdbe *v;
  int addr, end;
  Index *pIdx;
  sqlite *db = pParse->db;

  zTab = sqliteTableNameFromToken(pTableName);
  if( sqlite_malloc_failed || zTab==0 ) goto copy_cleanup;
  pTab = sqliteFindTable(db, zTab);
  sqliteFree(zTab);
  if( pTab==0 ){
    sqliteSetNString(&pParse->zErrMsg, "no such table: ", 0, 
        pTableName->z, pTableName->n, 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
................................................................................
    sqliteSetString(&pParse->zErrMsg, "table ", pTab->zName,
        " may not be modified", 0);
    pParse->nErr++;
    goto copy_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v ){
    if( (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
    }
    addr = sqliteVdbeAddOp(v, OP_FileOpen, 0, 0, 0, 0);
    sqliteVdbeChangeP3(v, addr, pFilename->z, pFilename->n);
    sqliteVdbeDequoteP3(v, addr);
    sqliteVdbeAddOp(v, OP_Open, 0, pTab->tnum, pTab->zName, 0);
    for(i=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, i++){
................................................................................
        sqliteVdbeAddOp(v, OP_FileColumn, pIdx->aiColumn[j], 0, 0, 0);
      }
      sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_PutIdx, i, 0, 0, 0);
    }
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);
    sqliteVdbeAddOp(v, OP_Noop, 0, 0, 0, end);
    if( (db->flags & SQLITE_InTrans)==0 ){
      sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
    }
  }
  
copy_cleanup:
  return;
}
................................................................................
** The non-standard VACUUM command is used to clean up the database,
** collapse free space, etc.  It is modelled after the VACUUM command
** in PostgreSQL.
*/
void sqliteVacuum(Parse *pParse, Token *pTableName){
  char *zName;
  Vdbe *v;
  sqlite *db = pParse->db;

  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( pTableName ){
    zName = sqliteTableNameFromToken(pTableName);
  }else{
    zName = 0;
  }
  if( zName && sqliteFindIndex(db, zName)==0
    && sqliteFindTable(db, zName)==0 ){
    sqliteSetString(&pParse->zErrMsg, "no such table or index: ", zName, 0);
    pParse->nErr++;
    goto vacuum_cleanup;
  }
  v = sqliteGetVdbe(pParse);
  if( v==0 ) goto vacuum_cleanup;
  if( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Transaction, 0, 0, 0, 0);
  }
  if( zName ){
    sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, zName, 0);
  }else{
    int h;
    Table *pTab;
    Index *pIdx;
    for(h=0; h<N_HASH; h++){
      for(pTab=db->apTblHash[h]; pTab; pTab=pTab->pHash){
        sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pTab->zName, 0);
        for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          sqliteVdbeAddOp(v, OP_Reorganize, 0, 0, pIdx->zName, 0);
        }
      }
    }
  }
  if( (db->flags & SQLITE_InTrans)==0 ){
    sqliteVdbeAddOp(v, OP_Commit, 0, 0, 0, 0);
  }

vacuum_cleanup:
  sqliteFree(zName);
  return;
}

/*
** Begin a transaction
*/
void sqliteBeginTransaction(Parse *pParse){

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( db->flags & SQLITE_InTrans ) return;
  v = sqliteGetVdbe(pParse);
................................................................................
  db->flags |= SQLITE_InTrans;
}

/*
** Commit a transaction
*/
void sqliteCommitTransaction(Parse *pParse){

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
................................................................................
  db->flags &= ~SQLITE_InTrans;
}

/*
** Rollback a transaction
*/
void sqliteRollbackTransaction(Parse *pParse){

  sqlite *db;
  Vdbe *v;

  if( pParse==0 || (db=pParse->db)==0 || db->pBe==0 ) return;
  if( pParse->nErr || sqlite_malloc_failed ) return;
  if( (db->flags & SQLITE_InTrans)==0 ) return;
  v = sqliteGetVdbe(pParse);
  if( v ){
    sqliteVdbeAddOp(v, OP_Rollback, 0, 0, 0, 0);
  }
  db->flags &= ~SQLITE_InTrans;
}

Deleted src/dbbe.c.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/*
** Copyright (c) 1999, 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses GDBM as the database backend.  It should be
** relatively simple to convert to a different database such
** as NDBM, SDBM, or BerkeleyDB.
**
** $Id: dbbe.c,v 1.28 2001/04/28 16:52:41 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** This routine opens a new database.  It looks at the first
** few characters of the database name to try to determine what
** kind of database to open.  If the first characters are "gdbm:",
** then it uses the GDBM driver.  If the first few characters are
** "memory:" then it uses the in-memory driver.  If there is no
** match, the default to the GDBM driver.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteDbbeOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  extern Dbbe *sqliteMemOpen(const char*,int,int,char**);
#ifndef DISABLE_GDBM
  extern Dbbe *sqliteGdbmOpen(const char*,int,int,char**);
  if( strncmp(zName, "gdbm:", 5)==0 ){
    return sqliteGdbmOpen(&zName[5], writeFlag, createFlag, pzErrMsg);
  }
#endif
  if( strncmp(zName, "memory:", 7)==0 ){
    return sqliteMemOpen(&zName[7], writeFlag, createFlag, pzErrMsg);
  }
#ifndef DISABLE_GDBM
  return sqliteGdbmOpen(zName, writeFlag, createFlag, pzErrMsg);
#else
  return sqliteMemOpen(zName, writeFlag, createFlag, pzErrMsg);
#endif
}

#if 0  /* NOT USED */
/*
** Translate the name of an SQL table (or index) into the name 
** of a file that holds the key/data pairs for that table or
** index.  Space to hold the filename is obtained from
** sqliteMalloc() and must be freed by the calling function.
**
** zDir is the name of the directory in which the file should
** be located.  zSuffix is the filename extension to use for
** the file.
*/
char *sqliteDbbeNameToFile(
  const char *zDir,      /* Directory containing the file */
  const char *zTable,    /* Name of the SQL table that the file contains */
  const char *zSuffix    /* Suffix for the file.  Includes the "." */
){
  char *zFile = 0;
  int i, k, c;
  int nChar = 0;

  for(i=0; (c = zTable[i])!=0; i++){
    if( !isalnum(c) && c!='_' ){
      nChar += 3;
    }else{
      nChar ++;
    }
  }
  nChar += strlen(zDir) + strlen(zSuffix) + 2;
  zFile = sqliteMalloc( nChar );
  if( zFile==0 ) return 0;
  for(i=0; (c = zDir[i])!=0; i++){
    zFile[i] = c;
  }
  zFile[i++] = '/';
  for(k=0; (c = zTable[k])!=0; k++){
    if( isupper(c) ){
      zFile[i++] = tolower(c);
    }else if( isalnum(c) || c=='_' ){
      zFile[i++] = c;
    }else{
      zFile[i++] = '~';
      zFile[i++] = "0123456789abcdef"[c & 0xf];
      zFile[i++] = "0123456789abcdef"[(c>>8)&0xf];
    }
  }
  for(k=0; (c = zSuffix[k])!=0; k++){
    zFile[i++] = c;
  }
  zFile[i] = 0;
  return zFile;
}
#endif /* NOT USED */
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
























































































































































































































































Deleted src/dbbe.h.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
/*
** Copyright (c) 1999, 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file defines the interface to the database backend (Dbbe).
**
** The database backend is designed to be as general as possible
** so that it can easily be replaced by a different backend.
** This library was originally designed to support the following
** backends: GDBM, NDBM, SDBM, Berkeley DB.
**
** $Id: dbbe.h,v 1.14 2001/08/19 18:19:46 drh Exp $
*/
#ifndef _SQLITE_DBBE_H_
#define _SQLITE_DBBE_H_
#include <stdio.h>

/*
** The database backend supports two opaque structures.  A Dbbe is
** a context for the entire set of tables forming a complete
** database.  A DbbeCursor is a pointer into a single single table.
**
** Note that at this level, the term "table" can mean either an
** SQL table or an SQL index.  In this module, a table stores a
** single arbitrary-length key and corresponding arbitrary-length
** data.  The differences between tables and indices, and the
** segregation of data into various fields or columns is handled
** by software at higher layers.
**
** The DbbeCursor structure holds some state information, such as
** the key and data from the last retrieval.  For this reason, 
** the backend must allow the creation of multiple independent
** DbbeCursor structures for each table in the database.
*/
typedef struct Dbbe Dbbe;
typedef struct DbbeCursor DbbeCursor;
typedef struct DbbeMethods DbbeMethods;

/*
** Open a complete database.
**
** If the database name begins with "gdbm:" the GDBM driver is used.
** If the name begins with "memory:" the in-memory driver is used.
** The default driver is GDBM.
*/
Dbbe *sqliteDbbeOpen(const char *zName, int write, int create, char **pzErr);

/*
** Each of the various SQLite backends defines a set of methods for
** accessing the database.  Pointers to the methods are contained in
** an instance of the following structure.  A pointer to a static instance
** of this structure is assigned to the Dbbe structure that sqlileDbbeOpen
** returns.
*/
struct DbbeMethods {
  /* Close the whole database. */
  void (*Close)(Dbbe*);

  /* Open a cursor into a particular table of a previously opened database.
  ** Create the table if it doesn't already exist and writeable!=0.  zName
  ** is the base name of the table to be opened.  If the database is 
  ** implement as one file per table, then this routine will add an
  ** appropriate path and extension to the table name to locate the 
  ** actual file.
  **
  ** The intKeyOnly parameter is TRUE if this table will only be accessed
  ** using integer keys.  This parameter allows the database backend to
  ** use a faster algorithm for the special case of integer keys, if it
  ** wants to.
  **
  ** If zName is 0 or "", then a temporary table is created that
  ** will be deleted when closed.
  */
  int (*OpenCursor)(Dbbe*, const char *zName, int writeable, 
                    int intKeyOnly, DbbeCursor**);

  /* Delete a table from the database */
  void (*DropTable)(Dbbe*, const char *zTableName);

  /* Reorganize a table to speed access or reduce its disk usage */
  int (*ReorganizeTable)(Dbbe*, const char *zTableName);

  /* Close a cursor */
  void (*CloseCursor)(DbbeCursor*);

  /* Fetch an entry from a table with the given key.  Return 1 if
  ** successful and 0 if no such entry exists.
  */
  int (*Fetch)(DbbeCursor*, int nKey, char *pKey);

  /* Return 1 if the given key is already in the table.  Return 0
  ** if it is not.
  */
  int (*Test)(DbbeCursor*, int nKey, char *pKey);

  /* Retrieve the key or data used for the last fetch.  Only size
  ** bytes are read beginning with the offset-th byte.  The return
  ** value is the actual number of bytes read.
  */
  int (*CopyKey)(DbbeCursor*, int offset, int size, char *zBuf);
  int (*CopyData)(DbbeCursor*, int offset, int size, char *zBuf);

  /* Retrieve the key or data.  The result is ephemeral.  In other words,
  ** the result is stored in a buffer that might be overwritten on the next
  ** call to any DBBE routine.  If the results are needed for longer than
  ** that, you must make a copy.
  */
  char *(*ReadKey)(DbbeCursor*, int offset);
  char *(*ReadData)(DbbeCursor*, int offset);

  /* Return the length of the most recently fetched key or data. */
  int (*KeyLength)(DbbeCursor*);
  int (*DataLength)(DbbeCursor*);

  /* Retrieve the next entry in the table.  The first key is retrieved
  ** the first time this routine is called, or after a call to
  ** Dbbe.Rewind().  The return value is 1 if there is another
  ** entry, or 0 if there are no more entries. */
  int (*NextKey)(DbbeCursor*);

  /* Make it so that the next call to Dbbe.NextKey() returns
  ** the first entry of the table. */
  int (*Rewind)(DbbeCursor*);

  /* Get a new integer key for this table. */
  int (*New)(DbbeCursor*);

  /* Write an entry into a table.  If another entry already exists with
  ** the same key, the old entry is discarded first.
  */
  int (*Put)(DbbeCursor*, int nKey, char *pKey, int nData, char *pData);

  /* Remove an entry from the table */
  int (*Delete)(DbbeCursor*, int nKey, char *pKey);

  /* Begin a transaction. */
  int (*BeginTransaction)(Dbbe*);

  /* Commit a transaction. */
  int (*Commit)(Dbbe*);

  /* Rollback a transaction. */
  int (*Rollback)(Dbbe*);

  /* Begin searching an index where the key is given. */
  int (*BeginIndex)(DbbeCursor*, int nKey, char *pKey);

  /* Return the integer key for the next index entry, or return 0 if
  ** there are no more index entries. */
  int (*NextIndex)(DbbeCursor*);

  /* Add a new index entry to the file.  The key and record number are
  ** given. */
  int (*PutIndex)(DbbeCursor*, int nKey, char *pKey, int recno);

  /* Delete an index entry from the file.  The key and record number are
  ** given. */
  int (*DeleteIndex)(DbbeCursor*, int nKey, char *pKey, int recno);
};

/*
** This is the structure returned by sqliteDbbeOpen().  It contains
** information common to all the different backend drivers.
**
** The information in this structure (with the exception the method
** pointers in the Dbbe.x field) is intended to be visible to
** the backend drivers only.  Users should not access or modify
** this structure in any way other than the read the method pointers
** in Dbbe.x.
*/
struct Dbbe {
  struct DbbeMethods *x; /* Backend-specific methods for database access */
  /* There used to be other information here, but it has since
  ** been removed.  We'll keep the same design, though, in case we
  ** ever want to add some new fields in the future. */
};

#endif /* defined(_SQLITE_DBBE_H_) */
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<










































































































































































































































































































































































































Deleted src/dbbebtree.c.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
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
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
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
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
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
/*
** Copyright (c) 2001 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses a custom B-Tree implementation as the database backend.
**
** $Id: dbbebtree.c,v 1.1 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"
#include "btree.h"

/*
** The following structure contains all information used by B-Tree
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  int write;         /* True for write permission */
  int inTrans;       /* Currently in a transaction */
  char *zFile;       /* File containing the database */
  Btree *pBt;        /* Pointer to the open database */
  BtCursor *pCur;    /* Cursor for the main database table */
  DbbeCursor *pDCur; /* List of all Dbbe cursors */
};

/*
** An cursor into a database table is an instance of the following
** structure.
*/
struct DbbeCursor {
  DbbeCursor *pNext; /* Next on list of all cursors */
  DbbeCursor *pPrev; /* Previous on list of all cursors */
  Dbbex *pBe;        /* The database of which this record is a part */
  BtCursor *pCur;    /* The cursor */
  char *zTempFile;   /* Name of file if referring to a temporary table */
  Btree *pTempBt;    /* Database handle, if this is a temporary table */
  char *zKey;        /* Most recent key.  Memory obtained from sqliteMalloc() */
  int nKey;          /* Size of the key */
  char *zKeyBuf;     /* Space used during NextIndex() processing */
  char *zData;       /* Most recent data.  Memory from sqliteMalloc() */
  int needRewind;    /* Next call to Next() returns first entry in table */
  int skipNext;      /* Do not advance cursor for next NextIndex() call */
};

/*
** Forward declaration
*/
static void sqliteBtbeCloseCursor(DbbeCursor *pCursr);

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteBtbeClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  assert( pBe->pDCur==0 );
  if( pBe->pCur ){
    sqliteBtreeCloseCursor(pBe->pCur);
  }
  sqliteBtreeClose(pBe->pBt);
  sqliteFree(pBe->zFile);
  sqliteFree(pBe);
}

/*
** Translate a database table name into the table number for the database.
** The pBe->pCur cursor points to table number 2 of the database and that
** table maps all other database names into database number.  Return the
** database number of the table, or return 0 if not found.
*/
static int mapTableNameToNumber(Dbbex *pBe, char *zName){
  int nName = strlen(zName);
  int rc;
  int res;
  if( pBe->pCur==0 ){
    rc = sqliteBtreeCursor(pBe, 2, &pBe->pCur);
    if( rc!=SQLITE_OK ) return 0;
  }
  rc = sqliteBtreeMoveto(pBe->pCur, zName, nName, &res);
  if( rc!=SQLITE_OK || res!=0 ) return 0;
  rc = sqliteBtreeData(pBe->pCur, 0, sizeof(res), &res);
  if( rc!=SQLITE_OK ) return 0;
  return res;
}

/*
** Locate a directory where we can potentially create a temporary
** file.
*/
static const char *findTempDir(void){
  static const char *azDirs[] = {
     "/var/tmp",
     "/usr/tmp",
     "/tmp",
     "/temp",
     ".",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && S_IWUSR(buf.st_mode) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*
** Open a new table cursor.  Write a pointer to the corresponding
** DbbeCursor structure into *ppCursr.  Return an integer success
** code:
**
**    SQLITE_OK          It worked!
**
**    SQLITE_NOMEM       sqliteMalloc() failed
**
**    SQLITE_PERM        Attempt to access a file for which file
**                       access permission is denied
**
**    SQLITE_BUSY        Another thread or process is already using
**                       the corresponding file and has that file locked.
**
**    SQLITE_READONLY    The current thread already has this file open
**                       readonly but you are trying to open for writing.
**                       (This can happen if a SELECT callback tries to
**                       do an UPDATE or DELETE.)
**
** If the table does not previously exist and writeable is TRUE then
** a new table is created.  If zTable is 0 or "", then a temporary 
** database table is created and a cursor to that temporary file is
** opened.  The temporary file will be deleted when it is closed.
*/
static int sqliteBtbeOpenCursor(
  Dbbe *pDbbe,            /* The database the table belongs to */
  const char *zTable,     /* The SQL name of the file to be opened */
  int writeable,          /* True to open for writing */
  int intKeyOnly,         /* True if only integer keys are used */
  DbbeCursor **ppCursr    /* Write the resulting table pointer here */
){
  char *zFile;            /* Name of the table file */
  DbbeCursor *pCursr;     /* The new table cursor */
  int rc = SQLITE_OK;     /* Return value */
  int rw_mask;            /* Permissions mask for opening a table */
  int mode;               /* Mode for opening a table */
  Dbbex *pBe = (Dbbex*)pDbbe;

  *ppCursr = 0;
  if( pBe->pCur==0 ){
    rc = sqliteBtreeCursor(pBe->pBt, 2, &pBe->pCur);
    if( rc!=SQLITE_OK ) return rc;
  }
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    char *zTab;
    int tabId, i;

    if( writeable && pBe->inTrans==0 ){
      rc = sqliteBeginTrans(pBe->pBt);
      if( rc!=SQLITE_OK ){
        sqliteFree(pCursr);
        return rc;
      }
      pBe->inTrans = 1;
    }
    zTab = sqliteStrDup(zTable);
    for(i=0; zTab[i]; i++){
       if( isupper(zTab[i]) ) zTab[i] = tolower(zTab[i]);
    }
    tabId = mapTableNameToNumber(pBe, zTab);
    if( tabId==0 ){
      if( writeable==0 ){
        pCursr->pCur = 0;
      }else{
        rc = sqliteBtreeCreateTable(pBe->pBt, &tabId);
        if( rc!=SQLITE_OK ){
          sqliteFree(pCursr);
          sqliteFree(zTab);
          return rc;
        }
        sqliteBtreeInsert(pBe->pCur, zTab, strlen(zTab), tabId, sizeof(tabId));
      }
    }
    sqliteFree(zTab);
    rc = sqliteBtreeCursor(pBe->pBt, tabId, &pCursr->pCur);
    if( rc!=SQLITE_OK ){
      sqliteFree(pCursr);
      return rc;
    }
    pCursr->zTempFile = 0;
    pCursr->pTempBt = 0;
  }else{
    int nTry = 5;
    char zFileName[200];
    while( nTry>0 ){
      nTry--;
      sprintf(zFileName,"%s/_sqlite_temp_file_%d",
           findTempDir(), sqliteRandomInteger());
      rc = sqliteBtreeOpen(zFileName, 0, 100, &pCursr->pTempBt);
      if( rc!=SQLITE_OK ) continue;
      rc = sqliteBtreeCursor(pCursr->pTempBt, 2, &pCursr->pCur*****
    pFile = 0;
    zFile = 0;
  }
  pCursr->pNext = pBe->pDCur;
  if( pBe->pDCur ){
    pBe->pDCur->pPrev = pCursr;
  }
  pCursr->pPrev = 0;
  pCursr->pBe = pBe;
  pCursr->skipNext = 0;
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Drop a table from the database. 
*/
static void sqliteBtbeDropTable(Dbbe *pDbbe, const char *zTable){
  int iTable;
  Dbbex *pBe = (Dbbex*)pDbbe;

  iTable = mapTableNameToNumber(zTable);
  if( iTable>0 ){
    sqliteBtreeDelete(pBe->pCur);
    sqliteBtreeDropTable(pBe->pBt, iTable);
  }
}

/*
** Clear the remembered key and data from the cursor.
*/
static void clearCursorCache(DbbeCursor *pCursr){
  if( pCursr->zKey ){
    sqliteFree(pCursr->zKey);
    pCursr->zKey = 0;
    pCursr->nKey = 0;
    pCursr->zKeyBuf = 0;
  }
  if( pCursr->zData ){
    sqliteFree(pCursr->zData);
    pCursr->zData = 0;
  }
}

/*
** Close a cursor previously opened by sqliteBtbeOpenCursor().
*/
static void sqliteBtbeCloseCursor(DbbeCursor *pCursr){
  Dbbex *pBe;
  if( pCursr==0 ) return;
  if( pCursr->pCur ){
    sqliteBtreeCloseCursor(pCursr->pCur);
  }
  if( pCursr->pTemp ){
    sqliteBtreeClose(pCursr->pTemp);
  }
  if( pCursr->zTempFile ){
    unlink(pCursr->zTempFile);
    sqliteFree(pCursr->zTempFile);
  }
  clearCursorCache(pCursr);
  pBe = pCursr->pBe;
  if( pCursr->pPrev ){
    pCursr->pPrev->pNext = pCursr->pNext;
  }else{
    pBe->pDCur = pCur->pNext;
  }
  if( pCursr->pNext ){
    pCursr->pNext->pPrev = pCursr->pPrev;
  }
  if( pBe->pDCur==0 && pBe->inTrans==0 && pBe->pCur!=0 ){
    sqliteBtreeCloseCursor(pBe->pCur);
    pBe->pCur = 0;
  }
  memset(pCursr, 0, sizeof(*pCursr));
  sqliteFree(pCursr);
}

/*
** Reorganize a table to reduce search times and disk usage.
*/
static int sqliteBtbeReorganizeTable(Dbbe *pBe, const char *zTable){
  return SQLITE_OK;
}

/*
** Move the cursor so that it points to the entry with a key that
** matches the argument.  Return 1 on success and 0 if no keys match
** the argument.
*/
static int sqliteBtbeFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc, res;
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  rc = sqliteBtreeMoveto(pCursr->pCur, pKey, nKey, &res);
  return rc==SQLITE_OK && res==0;
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteBtbeCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  if( pCursr->pCur==0 ) return 0;
  int rc = sqliteBtreeKey(pCursr->pCur, offset, amt, zBuf);
  if( rc!=SQLITE_OK ) amt = 0;
  return amt;
}
static
int sqliteBtbeCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  if( pCursr->pCur==0 ) return 0;
  int rc = sqliteBtreeData(pCursr->pCur, offset, amt, zBuf);
  if( rc!=SQLITE_OK ) amt = 0;
  return amt;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteBtbeReadKey(DbbeCursor *pCursr, int offset){
  if( pCursr->zKey==0 && pCursr->pCur!=0 ){
    sqliteBtreeKeySize(pCursr->pCur, &pCursr->nKey);
    pCursr->zKey = sqliteMalloc( pCursr->nKey + 1 );
    if( pCursr->zKey==0 ) return 0;
    sqliteBtreeKey(pCursr->pCur, 0, pCursr->nKey, pCursr->zKey);
    pCursr->zKey[pCursor->nKey] = 0;
  }
  return pCursr->zKey;
}
static char *sqliteBtbeReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->zData==0 && pCursr->pCur!=0 ){
    int nData;
    sqliteBtreeDataSize(pCursr->pCur, &nData);
    pCursr->zData = sqliteMalloc( nData + 1 );
    if( pCursr->zData==0 ) return 0;
    sqliteBtreeData(pCursr->pCur, 0, nData, pCursr->zData);
    pCursr->zData[nData] = 0;
  }
  return pCursr->zData;
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteBtbeKeyLength(DbbeCursor *pCursr){
  int n;
  if( pCursr->pCur==0 ) return 0;
  sqliteBtreeKeySize(pCursr->pCur, &n);
  return n;
}
static int sqliteBtbeDataLength(DbbeCursor *pCursr){
  int n;
  if( pCursr->pCur==0 ) return 0;
  sqliteBtreeDataSize(pCursr->pCur, &n);
  return n;
}

/*
** Make is so that the next call to sqliteNextKey() finds the first
** key of the table.
*/
static int sqliteBtbeRewind(DbbeCursor *pCursr){
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Move the cursor so that it points to the next key in the table.
** Return 1 on success.  Return 0 if there are no more keys in this
** table.
**
** If the pCursr->needRewind flag is set, then move the cursor so
** that it points to the first key of the table.
*/
static int sqliteBtbeNextKey(DbbeCursor *pCursr){
  int rc, res;
  static char zNullKey[1] = { '\000' };
  assert( pCursr!=0 );
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  if( pCursr->needRewind ){
    rc = sqliteBtreeFirst(pCursr->pCur, &res);
    return rc==SQLITE_OK && res==0;
  }
  rc = sqliteBtreeNext(pCursr->pCur);
  return rc==SQLITE_OK && res==0;
}

/*
** Get a new integer key.
*/
static int sqliteBtbeNew(DbbeCursor *pCursr){
  int rc;
  int res = 0;

  assert( pCursr->pCur!=0 );
  while( res==0 ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    rc = sqliteBtreeMoveto(pCursr->pCur, &iKey, sizeof(iKey), &res);
    assert( rc==SQLITE_OK );
  }
  clearCursorCache(pCursr);
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteBtbePut(
  DbbeCursor *pCursr,  /* Write to the database associated with this cursor */
  int nKey,            /* Number of bytes in the key */
  char *pKey,          /* The data for the key */
  int nData,           /* Number of bytes of data */
  char *pData          /* The data */
){
  clearCursorCache(pCursr);
  assert( pCursr->pCur!=0 );
  return sqliteBtreeInsert(pCursr->pCur, pKey, nKey, pData, nData);
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteBtbeDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc;
  int res;
  clearCursorCache(pCursr);
  assert( pCursr->pCur!=0 );
  rc = sqliteBtreeMoveto(pCursr->pCur, pKey, nKey, &res);
  if( rc==SQLITE_OK && res==0 ){
    rc = sqliteBtreeDelete(pCursr->pCur);
  }
  return rc;
}

/*
** Begin a transaction.
*/
static int sqliteBtbeBeginTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( pBe->inTrans ) return SQLITE_OK;
  sqliteBtreeBeginTrans(pBe->pBt);
  pBe->inTrans = 1;
  return SQLITE_OK;  
}

/*
** Commit a transaction.
*/
static int sqliteBtbeCommit(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( !pBe->inTrans ) return SQLITE_OK;
  pBe->inTrans = 0;
  return sqliteBtreeCommit(pBe->pBt);
}

/*
** Rollback a transaction.
*/
static int sqliteBtbeRollback(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  if( !pBe->inTrans ) return SQLITE_OK;
  if( pBt->pDCur!=0 ) return SQLITE_INTERNAL;
  pBe->inTrans = 0;
  if( pBe->pCur ){
    sqliteBtreeCloseCursor(pBe->pCur);
    pBe->pCur = 0;
  }
  return sqliteBtreeRollback(pBe->pBt);
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.  (Vdbe ignores the return value.)
*/
static int sqliteBtbeBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  int rc;
  int res;
  clearCursorCache(pCursr);
  if( pCursr->pCur==0 ) return 0;
  pCursr->nKey = nKey;
  pCursr->zKey = sqliteMalloc( 2*(nKey + 1) );
  if( pCursr->zKey==0 ) return 0;
  pCursr->zKeyBuf = &pCursr->zKey[nKey+1];
  memcpy(pCursr->zKey, zKey, nKey);
  pCursr->zKey[nKey] = 0;
  rc = sqliteBtreeMoveTo(pCursr->pCur, pKey, nKey, res);
  pCursr->skipNext = res<0;
  return rc==SQLITE_OK;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteBtbeNextIndex(DbbeCursor *pCursr){
  int rc, res;
  int iRecno;
  BtCursor *pCur = pCursr->pCur;
  if( pCur==0 ) return 0;
  if( pCursr->zKey==0 || pCursr->zKeyBuf==0 ) return 0;
  if( !pCursr->skipNext ){
    rc = sqliteBtreeNext(pCur, &res);
    pCursr->skipNext = 0;
    if( res ) return 0;
  }
  if( sqliteBtreeKeySize(pCur)!=pCursr->nKey+4 ){
    return 0;
  }
  rc = sqliteBtreeKey(pCur, 0, pCursr->nKey, pCursr->zKeyBuf);
  if( rc!=SQLITE_OK || memcmp(pCursr->zKey, pCursr->zKeyBuf, pCursr->nKey)!=0 ){
    return 0;
  }
  sqliteBtreeKey(pCur, pCursr->nKey, 4, &iRecno);
  return iRecno;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteBtbePutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  char *zBuf;
  int rc;
  char zStaticSpace[200];

  assert( pCursr->pCur!=0 );
  if( nKey+4>sizeof(zStaticSpace){
    zBuf = sqliteMalloc( nKey + 4 );
    if( zBuf==0 ) return SQLITE_NOMEM;
  }else{
    zBuf = zStaticSpace;
  }
  memcpy(zBuf, pKey, nKey);
  memcpy(&zBuf[nKey], N, 4);
  rc = sqliteBtreeInsert(pCursr->pCur, zBuf, nKey+4, "", 0);
  if( zBuf!=zStaticSpace ){
    sqliteFree(zBuf);
  }
}

/*
** Delete an index entry.  Return a status code.
*/
static 
int sqliteBtbeDeleteIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  char *zBuf;
  int rc;
  char zStaticSpace[200];

  assert( pCursr->pCur!=0 );
  if( nKey+4>sizeof(zStaticSpace){
    zBuf = sqliteMalloc( nKey + 4 );
    if( zBuf==0 ) return SQLITE_NOMEM;
  }else{
    zBuf = zStaticSpace;
  }
  memcpy(zBuf, pKey, nKey);
  memcpy(&zBuf[nKey], N, 4);
  rc = sqliteBtreeMoveto(pCursr->pCur, zBuf, nKey+4, &res);
  if( rc==SQLITE_OK && res==0 ){
    sqliteBtreeDelete(pCursr->pCur);
  }
  if( zBuf!=zStaticSpace ){
    sqliteFree(zBuf);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the GDBM backend.
*/
static struct DbbeMethods btbeMethods = {
  /*           Close */   sqliteBtbeClose,
  /*      OpenCursor */   sqliteBtbeOpenCursor,
  /*       DropTable */   sqliteBtbeDropTable,
  /* ReorganizeTable */   sqliteBtbeReorganizeTable,
  /*     CloseCursor */   sqliteBtbeCloseCursor,
  /*           Fetch */   sqliteBtbeFetch,
  /*            Test */   sqliteBtbeFetch,
  /*         CopyKey */   sqliteBtbeCopyKey,
  /*        CopyData */   sqliteBtbeCopyData,
  /*         ReadKey */   sqliteBtbeReadKey,
  /*        ReadData */   sqliteBtbeReadData,
  /*       KeyLength */   sqliteBtbeKeyLength,
  /*      DataLength */   sqliteBtbeDataLength,
  /*         NextKey */   sqliteBtbeNextKey,
  /*          Rewind */   sqliteBtbeRewind,
  /*             New */   sqliteBtbeNew,
  /*             Put */   sqliteBtbePut,
  /*          Delete */   sqliteBtbeDelete,
  /*      BeginTrans */   sqliteBtbeBeginTrans,
  /*          Commit */   sqliteBtbeCommit,
  /*        Rollback */   sqliteBtbeRollback,
  /*      BeginIndex */   sqliteBtbeBeginIndex,
  /*       NextIndex */   sqliteBtbeNextIndex,
  /*        PutIndex */   sqliteBtbePutIndex,
  /*     DeleteIndex */   sqliteBtbeDeleteIndex,
};


/*
** This routine opens a new database.  For the BTree driver
** implemented here, the database name is the name of a single
** file that contains all tables of the database.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteBtbeOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;
  char *zTemp;
  Btree *pBt;
  int rc;

  rc = sqliteBtreeOpen(zName, 0, 100, &pBt);
  if( rc!=SQLITE_OK ){
    sqliteSetString(pzErrMsg, "unable to open database file \"", zName, "\"",0);
    return 0;
  }
  pNew = sqliteMalloc(sizeof(Dbbex) + strlen(zName) + 1);
  if( pNew==0 ){
    sqliteBtreeCloseCursor(pCur);
    sqliteBtreeClose(pBt);
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  pNew->dbbe.x = &btbeMethods;
  pNew->write = writeFlag;
  pNew->inTrans = 0;
  pNew->zFile = (char*)&pNew[1];
  strcpy(pNew->zFile, zName);
  pNew->pBt = pBt;
  pNew->pCur = 0;
  return &pNew->dbbe;
}
#endif /* DISABLE_GDBM */
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<








































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Deleted src/dbbegdbm.c.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
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
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
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
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
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
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
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
/*
** Copyright (c) 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses GDBM as the database backend.  It should be
** relatively simple to convert to a different database such
** as NDBM, SDBM, or BerkeleyDB.
**
** $Id: dbbegdbm.c,v 1.9 2001/08/19 18:19:46 drh Exp $
*/
#ifndef DISABLE_GDBM
#include "sqliteInt.h"
#include <gdbm.h>
#include <sys/stat.h>
#include <unistd.h>
#include <ctype.h>
#include <time.h>

/*
** Information about each open disk file is an instance of this 
** structure.  There will only be one such structure for each
** disk file.  If the VDBE opens the same file twice (as will happen
** for a self-join, for example) then two DbbeCursor structures are
** created but there is only a single BeFile structure with an
** nRef of 2.
**
** This backend uses a separate disk file for each database table
** and index.
*/
typedef struct BeFile BeFile;
struct BeFile {
  char *zName;            /* Name of the file */
  GDBM_FILE dbf;          /* The file itself */
  int nRef;               /* Number of references */
  int delOnClose;         /* Delete when closing */
  int writeable;          /* Opened for writing */
  BeFile *pNext, *pPrev;  /* Next and previous on list of open files */
};

/*
** The following structure contains all information used by GDBM
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  int write;         /* True for write permission */
  int inTrans;       /* Currently in a transaction */
  BeFile *pOpen;     /* List of open files */
  char *zDir;        /* Directory hold the database */
};

/*
** An cursor into a database file is an instance of the following structure.
** There can only be a single BeFile structure for each disk file, but
** there can be multiple DbbeCursor structures.  Each DbbeCursor represents
** a cursor pointing to a particular part of the open BeFile.  The
** BeFile.nRef field hold a count of the number of DbbeCursor structures
** associated with the same disk file.
*/
struct DbbeCursor {
  Dbbex *pBe;        /* The database of which this record is a part */
  BeFile *pFile;     /* The database file for this table */
  datum key;         /* Most recently used key */
  datum data;        /* Most recent data */
  int nextIndex;     /* Next index entry to search */
  int needRewind;    /* Next key should be the first */
  int readPending;   /* The fetch hasn't actually been done yet */
};

/*
** The "mkdir()" function only takes one argument under Windows.
*/
#if OS_WIN
# define mkdir(A,B) mkdir(A)
#endif

/*
** Forward declaration
*/
static void sqliteGdbmCloseCursor(DbbeCursor *pCursr);

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteGdbmClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile, *pNext;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    gdbm_close(pFile->dbf);
    memset(pFile, 0, sizeof(*pFile));   
    sqliteFree(pFile);
  }
  memset(pBe, 0, sizeof(*pBe));
  sqliteFree(pBe);
}

/*
** Translate the name of an SQL table (or index) into the name 
** of a file that holds the key/data pairs for that table or
** index.  Space to hold the filename is obtained from
** sqliteMalloc() and must be freed by the calling function.
*/
static char *sqliteFileOfTable(Dbbex *pBe, const char *zTable){
  char *zFile = 0;
  int i;
  sqliteSetString(&zFile, pBe->zDir, "/", zTable, ".tbl", 0);
  if( zFile==0 ) return 0;
  for(i=strlen(pBe->zDir)+1; zFile[i]; i++){
    int c = zFile[i];
    if( isupper(c) ){
      zFile[i] = tolower(c);
    }else if( !isalnum(c) && c!='-' && c!='_' && c!='.' ){
      zFile[i] = '+';
    }
  }
  return zFile;
}

/*
** Open a new table cursor.  Write a pointer to the corresponding
** DbbeCursor structure into *ppCursr.  Return an integer success
** code:
**
**    SQLITE_OK          It worked!
**
**    SQLITE_NOMEM       sqliteMalloc() failed
**
**    SQLITE_PERM        Attempt to access a file for which file
**                       access permission is denied
**
**    SQLITE_BUSY        Another thread or process is already using
**                       the corresponding file and has that file locked.
**
**    SQLITE_READONLY    The current thread already has this file open
**                       readonly but you are trying to open for writing.
**                       (This can happen if a SELECT callback tries to
**                       do an UPDATE or DELETE.)
**
** If zTable is 0 or "", then a temporary database file is created and
** a cursor to that temporary file is opened.  The temporary file
** will be deleted from the disk when it is closed.
*/
static int sqliteGdbmOpenCursor(
  Dbbe *pDbbe,            /* The database the table belongs to */
  const char *zTable,     /* The SQL name of the file to be opened */
  int writeable,          /* True to open for writing */
  int intKeyOnly,         /* True if only integer keys are used */
  DbbeCursor **ppCursr    /* Write the resulting table pointer here */
){
  char *zFile;            /* Name of the table file */
  DbbeCursor *pCursr;     /* The new table cursor */
  BeFile *pFile;          /* The underlying data file for this table */
  int rc = SQLITE_OK;     /* Return value */
  int rw_mask;            /* Permissions mask for opening a table */
  int mode;               /* Mode for opening a table */
  Dbbex *pBe = (Dbbex*)pDbbe;

  if( pBe->inTrans ) writeable = 1;
  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    zFile = sqliteFileOfTable(pBe, zTable);
    if( zFile==0 ) return SQLITE_NOMEM;
    for(pFile=pBe->pOpen; pFile; pFile=pFile->pNext){
      if( strcmp(pFile->zName,zFile)==0 ) break;
    }
  }else{
    pFile = 0;
    zFile = 0;
  }
  if( pFile==0 ){
    if( writeable ){
      rw_mask = GDBM_WRCREAT | GDBM_FAST;
      mode = 0640;
    }else{
      rw_mask = GDBM_READER;
      mode = 0640;
    }
    pFile = sqliteMalloc( sizeof(*pFile) );
    if( pFile==0 ){
      sqliteFree(zFile);
      return SQLITE_NOMEM;
    }
    if( zFile ){
      if( !writeable || pBe->write ){
        pFile->dbf = gdbm_open(zFile, 0, rw_mask, mode, 0);
      }else{
        pFile->dbf = 0;
      }
    }else{
      int limit;
      char zRandom[50];
      zFile = 0;
      limit = 5;
      do {
        sqliteRandomName(zRandom, "_temp_table_");
        sqliteFree(zFile);
        zFile = sqliteFileOfTable(pBe, zRandom);
        pFile->dbf = gdbm_open(zFile, 0, rw_mask, mode, 0);
      }while( pFile->dbf==0 && limit-- >= 0);
      pFile->delOnClose = 1;
    }
    pFile->writeable = writeable;
    pFile->zName = zFile;
    pFile->nRef = 1 + pBe->inTrans;
    pFile->pPrev = 0;
    if( pBe->pOpen ){
      pBe->pOpen->pPrev = pFile;
    }
    pFile->pNext = pBe->pOpen;
    pBe->pOpen = pFile;
    if( pFile->dbf==0 ){
      if( !writeable && access(zFile,0) ){
        /* Trying to read a non-existant file.  This is OK.  All the
        ** reads will return empty, which is what we want. */
        rc = SQLITE_OK;   
      }else if( pBe->write==0 ){
        rc = SQLITE_READONLY;
      }else if( access(zFile,W_OK|R_OK) ){
        rc = SQLITE_PERM;
      }else{
        rc = SQLITE_BUSY;
      }
    }
  }else{
    sqliteFree(zFile);
    pFile->nRef++;
    if( writeable && !pFile->writeable ){
      rc = SQLITE_READONLY;
    }
  }
  pCursr->pBe = pBe;
  pCursr->pFile = pFile;
  pCursr->readPending = 0;
  pCursr->needRewind = 1;
  if( rc!=SQLITE_OK ){
    sqliteGdbmCloseCursor(pCursr);
    *ppCursr = 0;
  }else{
    *ppCursr = pCursr;
  }
  return rc;
}

/*
** Drop a table from the database.  The file on the disk that corresponds
** to this table is deleted.
*/
static void sqliteGdbmDropTable(Dbbe *pBe, const char *zTable){
  char *zFile;            /* Name of the table file */

  zFile = sqliteFileOfTable((Dbbex*)pBe, zTable);
  unlink(zFile);
  sqliteFree(zFile);
}

/*
** Unlink a file pointer
*/
static void sqliteUnlinkFile(Dbbex *pBe, BeFile *pFile){
  if( pFile->dbf!=NULL ){
    gdbm_close(pFile->dbf);
  }
  if( pFile->pPrev ){
    pFile->pPrev->pNext = pFile->pNext;
  }else{
    pBe->pOpen = pFile->pNext;
  }
  if( pFile->pNext ){
    pFile->pNext->pPrev = pFile->pPrev;
  }
  if( pFile->delOnClose ){
    unlink(pFile->zName);
  }
  sqliteFree(pFile->zName);
  memset(pFile, 0, sizeof(*pFile));
  sqliteFree(pFile);
}

/*
** Close a cursor previously opened by sqliteGdbmOpenCursor().
**
** There can be multiple cursors pointing to the same open file.
** The underlying file is not closed until all cursors have been
** closed.  This routine decrements the BeFile.nref field of the
** underlying file and closes the file when nref reaches 0.
*/
static void sqliteGdbmCloseCursor(DbbeCursor *pCursr){
  BeFile *pFile;
  Dbbex *pBe;
  if( pCursr==0 ) return;
  pFile = pCursr->pFile;
  pBe = pCursr->pBe;
  pFile->nRef--;
  if( pFile->dbf!=NULL ){
    gdbm_sync(pFile->dbf);
  }
  if( pFile->nRef<=0 ){
    sqliteUnlinkFile(pBe, pFile);
  }
  if( pCursr->key.dptr ) free(pCursr->key.dptr);
  if( pCursr->data.dptr ) free(pCursr->data.dptr);
  memset(pCursr, 0, sizeof(*pCursr));
  sqliteFree(pCursr);
}

/*
** Reorganize a table to reduce search times and disk usage.
*/
static int sqliteGdbmReorganizeTable(Dbbe *pBe, const char *zTable){
  DbbeCursor *pCursr;
  int rc;

  rc = sqliteGdbmOpenCursor(pBe, zTable, 1, 0, &pCursr);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( pCursr && pCursr->pFile && pCursr->pFile->dbf ){
    gdbm_reorganize(pCursr->pFile->dbf);
  }
  if( pCursr ){
    sqliteGdbmCloseCursor(pCursr);
  }
  return SQLITE_OK;
}

/*
** Clear the given datum
*/
static void datumClear(datum *p){
  if( p->dptr ) free(p->dptr);
  p->dptr = 0;
  p->dsize = 0;
}

/*
** Fetch a single record from an open cursor.  Return 1 on success
** and 0 on failure.
*/
static int sqliteGdbmFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  key.dsize = nKey;
  key.dptr = pKey;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  if( pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, key);
  }
  return pCursr->data.dptr!=0;
}

/*
** Return 1 if the given key is already in the table.  Return 0
** if it is not.
*/
static int sqliteGdbmTest(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  int result = 0;
  key.dsize = nKey;
  key.dptr = pKey;
  if( pCursr->pFile && pCursr->pFile->dbf ){
    result = gdbm_exists(pCursr->pFile->dbf, key);
  }
  return result;
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteGdbmCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( offset>=pCursr->key.dsize ) return 0;
  if( offset+size>pCursr->key.dsize ){
    n = pCursr->key.dsize - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &pCursr->key.dptr[offset], n);
  return n;
}
static
int sqliteGdbmCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  if( offset>=pCursr->data.dsize ) return 0;
  if( offset+size>pCursr->data.dsize ){
    n = pCursr->data.dsize - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &pCursr->data.dptr[offset], n);
  return n;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteGdbmReadKey(DbbeCursor *pCursr, int offset){
  if( offset<0 || offset>=pCursr->key.dsize ) return "";
  return &pCursr->key.dptr[offset];
}
static char *sqliteGdbmReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  if( offset<0 || offset>=pCursr->data.dsize ) return "";
  return &pCursr->data.dptr[offset];
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteGdbmKeyLength(DbbeCursor *pCursr){
  return pCursr->key.dsize;
}
static int sqliteGdbmDataLength(DbbeCursor *pCursr){
  if( pCursr->readPending && pCursr->pFile && pCursr->pFile->dbf ){
    pCursr->data = gdbm_fetch(pCursr->pFile->dbf, pCursr->key);
    pCursr->readPending = 0;
  }
  return pCursr->data.dsize;
}

/*
** Make is so that the next call to sqliteNextKey() finds the first
** key of the table.
*/
static int sqliteGdbmRewind(DbbeCursor *pCursr){
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Read the next key from the table.  Return 1 on success.  Return
** 0 if there are no more keys.
*/
static int sqliteGdbmNextKey(DbbeCursor *pCursr){
  datum nextkey;
  int rc;
  if( pCursr==0 || pCursr->pFile==0 || pCursr->pFile->dbf==0 ){
    pCursr->readPending = 0;
    return 0;
  }
  if( pCursr->needRewind ){
    nextkey = gdbm_firstkey(pCursr->pFile->dbf);
    pCursr->needRewind = 0;
  }else{
    nextkey = gdbm_nextkey(pCursr->pFile->dbf, pCursr->key);
  }
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  pCursr->key = nextkey;
  if( pCursr->key.dptr ){
    pCursr->readPending = 1;
    rc = 1;
  }else{
    pCursr->needRewind = 1;
    pCursr->readPending = 0;
    rc = 0;
  }
  return rc;
}

/*
** Get a new integer key.
*/
static int sqliteGdbmNew(DbbeCursor *pCursr){
  int iKey;
  datum key;
  int go = 1;

  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return 1;
  while( go ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    key.dptr = (char*)&iKey;
    key.dsize = 4;
    go = gdbm_exists(pCursr->pFile->dbf, key);
  }
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteGdbmPut(
  DbbeCursor *pCursr,  /* Write to the database associated with this cursor */
  int nKey,            /* Number of bytes in the key */
  char *pKey,          /* The data for the key */
  int nData,           /* Number of bytes of data */
  char *pData          /* The data */
){
  datum data, key;
  int rc;
  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return SQLITE_ERROR;
  data.dsize = nData;
  data.dptr = pData;
  key.dsize = nKey;
  key.dptr = pKey;
  rc = gdbm_store(pCursr->pFile->dbf, key, data, GDBM_REPLACE);
  if( rc ) rc = SQLITE_ERROR;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  return rc;
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteGdbmDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  datum key;
  int rc;
  datumClear(&pCursr->key);
  datumClear(&pCursr->data);
  if( pCursr->pFile==0 || pCursr->pFile->dbf==0 ) return SQLITE_ERROR;
  key.dsize = nKey;
  key.dptr = pKey;
  rc = gdbm_delete(pCursr->pFile->dbf, key);
  if( rc ) rc = SQLITE_ERROR;
  return rc;
}

/*
** Begin a transaction.
*/
static int sqliteGdbmBeginTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile;
  if( pBe->inTrans ) return SQLITE_OK;
  for(pFile=pBe->pOpen; pFile; pFile=pFile->pNext){
    pFile->nRef++;
  }
  pBe->inTrans = 1;
  return SQLITE_OK;  
}

/*
** End a transaction.
*/
static int sqliteGdbmEndTrans(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  BeFile *pFile, *pNext;
  if( !pBe->inTrans ) return SQLITE_OK;
  for(pFile=pBe->pOpen; pFile; pFile=pNext){
    pNext = pFile->pNext;
    pFile->nRef--;
    if( pFile->nRef<=0 ){
      sqliteUnlinkFile(pBe, pFile);
    }
  }
  pBe->inTrans = 0;
  return SQLITE_OK;  
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.
*/
static int sqliteGdbmBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  if( !sqliteGdbmFetch(pCursr, nKey, pKey) ) return 0;
  pCursr->nextIndex = 0;
  return 1;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteGdbmNextIndex(DbbeCursor *pCursr){
  int *aIdx;
  int nIdx;
  int k;
  nIdx = pCursr->data.dsize/sizeof(int);
  aIdx = (int*)pCursr->data.dptr;
  if( nIdx>1 ){
    k = *(aIdx++);
    if( k>nIdx-1 ) k = nIdx-1;
  }else{
    k = nIdx;
  }
  while( pCursr->nextIndex < k ){
    int recno = aIdx[pCursr->nextIndex++];
    if( recno!=0 ) return recno;
  }
  pCursr->nextIndex = 0;
  return 0;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteGdbmPutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int r = sqliteGdbmFetch(pCursr, nKey, pKey);
  if( r==0 ){
    /* Create a new record for this index */
    sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int), (char*)&N);
  }else{
    /* Extend the existing record */
    int nIdx;
    int *aIdx;
    int k;
            
    nIdx = pCursr->data.dsize/sizeof(int);
    if( nIdx==1 ){
      aIdx = sqliteMalloc( sizeof(int)*4 );
      if( aIdx==0 ) return SQLITE_NOMEM;
      aIdx[0] = 2;
      sqliteGdbmCopyData(pCursr, 0, sizeof(int), (char*)&aIdx[1]);
      aIdx[2] = N;
      sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*4, (char*)aIdx);
      sqliteFree(aIdx);
    }else{
      aIdx = (int*)sqliteGdbmReadData(pCursr, 0);
      k = aIdx[0];
      if( k<nIdx-1 ){
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
      }else{
        nIdx *= 2;
        aIdx = sqliteMalloc( sizeof(int)*nIdx );
        if( aIdx==0 ) return SQLITE_NOMEM;
        sqliteGdbmCopyData(pCursr, 0, sizeof(int)*(k+1), (char*)aIdx);
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
        sqliteFree(aIdx);
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete an index entry.  Return a status code.
*/
static 
int sqliteGdbmDeleteIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int *aIdx;
  int nIdx;
  int j, k;
  int rc;
  rc = sqliteGdbmFetch(pCursr, nKey, pKey);
  if( !rc ) return SQLITE_OK;
  nIdx = pCursr->data.dsize/sizeof(int);
  aIdx = (int*)sqliteGdbmReadData(pCursr, 0);
  if( (nIdx==1 && aIdx[0]==N) || (aIdx[0]==1 && aIdx[1]==N) ){
    sqliteGdbmDelete(pCursr, nKey, pKey);
  }else{
    k = aIdx[0];
    for(j=1; j<=k && aIdx[j]!=N; j++){}
    if( j>k ) return SQLITE_OK;
    aIdx[j] = aIdx[k];
    aIdx[k] = 0;
    aIdx[0]--;
    if( aIdx[0]*3 + 1 < nIdx ){
      nIdx /= 2;
    }
    sqliteGdbmPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the GDBM backend.
*/
static struct DbbeMethods gdbmMethods = {
  /*           Close */   sqliteGdbmClose,
  /*      OpenCursor */   sqliteGdbmOpenCursor,
  /*       DropTable */   sqliteGdbmDropTable,
  /* ReorganizeTable */   sqliteGdbmReorganizeTable,
  /*     CloseCursor */   sqliteGdbmCloseCursor,
  /*           Fetch */   sqliteGdbmFetch,
  /*            Test */   sqliteGdbmTest,
  /*         CopyKey */   sqliteGdbmCopyKey,
  /*        CopyData */   sqliteGdbmCopyData,
  /*         ReadKey */   sqliteGdbmReadKey,
  /*        ReadData */   sqliteGdbmReadData,
  /*       KeyLength */   sqliteGdbmKeyLength,
  /*      DataLength */   sqliteGdbmDataLength,
  /*         NextKey */   sqliteGdbmNextKey,
  /*          Rewind */   sqliteGdbmRewind,
  /*             New */   sqliteGdbmNew,
  /*             Put */   sqliteGdbmPut,
  /*          Delete */   sqliteGdbmDelete,
  /*      BeginTrans */   sqliteGdbmBeginTrans,
  /*          Commit */   sqliteGdbmEndTrans,
  /*        Rollback */   sqliteGdbmEndTrans,
  /*      BeginIndex */   sqliteGdbmBeginIndex,
  /*       NextIndex */   sqliteGdbmNextIndex,
  /*        PutIndex */   sqliteGdbmPutIndex,
  /*     DeleteIndex */   sqliteGdbmDeleteIndex,
};


/*
** This routine opens a new database.  For the GDBM driver
** implemented here, the database name is the name of the directory
** containing all the files of the database.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteGdbmOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;
  struct stat statbuf;
  char *zMaster;

  if( !writeFlag ) createFlag = 0;
  if( stat(zName, &statbuf)!=0 ){
    if( createFlag ) mkdir(zName, 0750);
    if( stat(zName, &statbuf)!=0 ){
      sqliteSetString(pzErrMsg, createFlag ? 
         "can't find or create directory \"" : "can't find directory \"",
         zName, "\"", 0);
      return 0;
    }
  }
  if( !S_ISDIR(statbuf.st_mode) ){
    sqliteSetString(pzErrMsg, "not a directory: \"", zName, "\"", 0);
    return 0;
  }
  if( access(zName, writeFlag ? (X_OK|W_OK|R_OK) : (X_OK|R_OK)) ){
    sqliteSetString(pzErrMsg, "access permission denied", 0);
    return 0;
  }
  zMaster = 0;
  sqliteSetString(&zMaster, zName, "/" MASTER_NAME ".tbl", 0);
  if( stat(zMaster, &statbuf)==0
   && access(zMaster, writeFlag ? (W_OK|R_OK) : R_OK)!=0 ){
    sqliteSetString(pzErrMsg, "access permission denied for ", zMaster, 0);
    sqliteFree(zMaster);
    return 0;
  }
  sqliteFree(zMaster);
  pNew = sqliteMalloc(sizeof(Dbbex) + strlen(zName) + 1);
  if( pNew==0 ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  pNew->dbbe.x = &gdbmMethods;
  pNew->zDir = (char*)&pNew[1];
  strcpy(pNew->zDir, zName);
  pNew->write = writeFlag;
  pNew->pOpen = 0;
  return &pNew->dbbe;
}
#endif /* DISABLE_GDBM */
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
















































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Deleted src/dbbemem.c.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
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
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
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
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
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
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
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
/*
** Copyright (c) 2000 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains code to implement the database backend (DBBE)
** for sqlite.  The database backend is the interface between
** sqlite and the code that does the actually reading and writing
** of information to the disk.
**
** This file uses an in-memory hash table as the database backend. 
** Nothing is ever written to disk using this backend.  All information
** is forgotten when the program exits.
**
** $Id: dbbemem.c,v 1.17 2001/08/20 00:33:58 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>


typedef struct Array Array;
typedef struct ArrayElem ArrayElem;
typedef struct Datum Datum;

/* A complete associative array is an instance of the following structure.
** The internals of this structure are intended to be opaque -- client
** code should not attempt to access or modify the fields of this structure
** directly.  Change this structure only by using the routines below.
** However, many of the "procedures" and "functions" for modifying and
** accessing this structure are really macros, so we can't really make
** this structure opaque.
*/
struct Array {
  int count;               /* Number of entries in the array */
  ArrayElem *first;        /* The first element of the array */
  int htsize;              /* Number of buckets in the hash table */
  struct _Array_ht {         /* the hash table */
    int count;               /* Number of entries with this hash */
    ArrayElem *chain;        /* Pointer to first entry with this hash */
  } *ht;
};

/*
** An instance of the following structure stores a single key or
** data element.
*/
struct Datum {
  int n;
  void *p;
};

/* Each element in the associative array is an instance of the following 
** structure.  All elements are stored on a single doubly-linked list.
**
** Again, this structure is intended to be opaque, but it can't really
** be opaque because it is used by macros.
*/
struct ArrayElem {
  ArrayElem *next, *prev;  /* Next and previous elements in the array */
  Datum key, data;         /* Key and data for this element */
};

/* Some routines are so simple that they can be implemented as macros
** These are given first. */

/* Return the number of entries in the array */
#define ArrayCount(X)    ((X)->count)

/* Return a pointer to the first element of the array */
#define ArrayFirst(X)    ((X)->first)

/* Return a pointer to the next (or previous) element of the array */
#define ArrayNext(X)     ((X)->next)
#define ArrayPrev(X)     ((X)->prev)

/* Return TRUE if the element given is the last element in the array */
#define ArrayIsLast(X)   ((X)->next==0)
#define ArrayIsFirst(X)  ((X)->prev==0)

/* Return the data or key for an element of the array */
#define ArrayData(X)     ((X)->data.p)
#define ArrayDataSize(X) ((X)->data.n)
#define ArrayKey(X)      ((X)->key.p)
#define ArrayKeySize(X)  ((X)->key.n)

/* Turn bulk memory into an associative array object by initializing the
** fields of the Array structure.
*/
static void ArrayInit(Array *new){
  new->first = 0;
  new->count = 0;
  new->htsize = 0;
  new->ht = 0;
}

/* Remove all entries from an associative array.  Reclaim all memory.
** This is the opposite of ArrayInit().
*/
static void ArrayClear(Array *array){
  ArrayElem *elem;         /* For looping over all elements of the array */

  elem = array->first;
  array->first = 0;
  array->count = 0;
  if( array->ht ) sqliteFree(array->ht);
  array->ht = 0;
  array->htsize = 0;
  while( elem ){
    ArrayElem *next_elem = elem->next;
    sqliteFree(elem);
    elem = next_elem;
  }
}

/*
** Generate a hash from an N-byte key
*/
static int ArrayHash(Datum d){
  int h = 0;
  while( d.n-- > 0 ){
    /* The funky case "*(char**)&d.p" is to work around a bug the
    ** c89 compiler of HPUX. */
    h = (h<<9) ^ (h<<3) ^ h ^ *((*(char**)&d.p)++);
  }
  if( h<0 ) h = -h; 
  return h;
}

/* Resize the hash table for a Array array
*/
static void ArrayRehash(Array *array, int new_size){
  struct _Array_ht *new_ht;       /* The new hash table */
  ArrayElem *elem, *next_elem;    /* For looping over existing elements */
  int i;                          /* Loop counter */
  ArrayElem *x;                   /* Element being copied to new hash table */

  new_ht = sqliteMalloc( new_size*sizeof(struct _Array_ht) );
  if( new_ht==0 ){ ArrayClear(array); return; }
  if( array->ht ) sqliteFree(array->ht);
  array->ht = new_ht;
  array->htsize = new_size;
  for(i=new_size-1; i>=0; i--){ 
    new_ht[i].count = 0;
    new_ht[i].chain = 0;
  }
  for(elem=array->first, array->first=0; elem; elem = next_elem){
    int h = ArrayHash(elem->key) & (new_size-1);
    next_elem = elem->next;
    x = new_ht[h].chain;
    if( x ){
      elem->next = x;
      elem->prev = x->prev;
      if( x->prev ) x->prev->next = elem;
      else          array->first = elem;
      x->prev = elem;
    }else{
      elem->next = array->first;
      if( array->first ) array->first->prev = elem;
      elem->prev = 0;
      array->first = elem;
    }
    new_ht[h].chain = elem;
    new_ht[h].count++;
  }
}

/* This function (for internal use only) locates an element in an
** array that matches the given key.  The hash for this key has
** already been computed and is passed as the 3rd parameter.
*/
static ArrayElem *ArrayFindElementGivenHash(
  const Array *array,    /* The array to be searched */
  const Datum key,       /* The key we are searching for */
  int h                  /* The hash for this key. */
){
  ArrayElem *elem;                /* Used to loop thru the element list */
  int count;                      /* Number of elements left to test */

  if( array->count ){
    elem = array->ht[h].chain;
    count = array->ht[h].count;
    while( count-- && elem ){
      if( elem->key.n==key.n && memcmp(elem->key.p,key.p,key.n)==0 ){ 
        return elem;
      }
      elem = elem->next;
    }
  }
  return 0;
}


/* Attempt to locate an element of the associative array with a key
** that matches "key".  Return the ArrayElement if found and NULL if
** if no match.
*/
static ArrayElem *ArrayFindElement(const Array *array, Datum key){
  int h;             /* A hash on key */
  if( array->count==0 ) return 0;
  h = ArrayHash(key);
  return ArrayFindElementGivenHash(array, key, h & (array->htsize-1));
}

/* Remove a single entry from the array given a pointer to that
** element and a hash on the element's key.
*/
static void ArrayRemoveElementGivenHash(
  Array *array,        /* The array containing "elem" */
  ArrayElem* elem,     /* The element to be removed from the array */
  int h                /* Hash value for the element */
){
  if( elem->prev ){
    elem->prev->next = elem->next; 
  }else{
    array->first = elem->next;
  }
  if( elem->next ){
    elem->next->prev = elem->prev;
  }
  if( array->ht[h].chain==elem ){
    array->ht[h].chain = elem->next;
  }
  array->ht[h].count--;
  if( array->ht[h].count<=0 ){
    array->ht[h].chain = 0;
  }
  sqliteFree( elem );
  array->count--;
}

/* Attempt to locate an element of the associative array with a key
** that matches "key".  Return the data for this element if it is
** found, or NULL if no match is found.
*/
static Datum ArrayFind(const Array *array, Datum key){
  int h;             /* A hash on key */
  ArrayElem *elem;   /* The element that matches key */
  static Datum nil = {0, 0};

  if( array->count==0 ) return nil;
  h = ArrayHash(key);
  elem = ArrayFindElementGivenHash(array, key, h & (array->htsize-1));
  return elem ? elem->data : nil;
}

/* Insert an element into the array.  The key will be "key" and
** the data will be "data".
**
** If no array element exists with a matching key, then a new
** array element is created.  The key is copied into the new element.
** But only a pointer to the data is stored.  NULL is returned.
**
** If another element already exists with the same key, then the
** new data replaces the old data and the old data is returned.
** The key is not copied in this instance.
**
** If the "data" parameter to this function is NULL, then the
** element corresponding to "key" is removed from the array.
*/
static Datum ArrayInsert(Array *array, Datum key, Datum data){
  int hraw;              /* Raw hash value of the key */
  int h;                 /* the hash of the key modulo hash table size */
  ArrayElem *elem;       /* Used to loop thru the element list */
  ArrayElem *new_elem;   /* New element added to the array */
  Datum rv;              /* Return value */
  static Datum nil = {0, 0};

  hraw = ArrayHash(key);
  h = hraw & (array->htsize-1);
  elem = ArrayFindElementGivenHash(array,key,h);
  if( elem ){
    Datum old_data = elem->data;
    if( data.p==0 ){
      ArrayRemoveElementGivenHash(array,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data.p==0 ) return nil;
  new_elem = (ArrayElem*)sqliteMalloc( sizeof(ArrayElem) + key.n );
  if( new_elem==0 ) return nil;
  new_elem->key.n = key.n;
  new_elem->key.p = (void*)&new_elem[1];
  memcpy(new_elem->key.p, key.p, key.n);
  array->count++;
  if( array->htsize==0 ) ArrayRehash(array,4);
  if( array->htsize==0 ) return nil;
  if( array->count > array->htsize ){
    ArrayRehash(array,array->htsize*2);
    if( array->htsize==0 ){
      sqliteFree(new_elem);
      return nil;
    }
  }
  h = hraw & (array->htsize-1);
  elem = array->ht[h].chain;
  if( elem ){
    new_elem->next = elem;
    new_elem->prev = elem->prev;
    if( elem->prev ){ elem->prev->next = new_elem; }
    else            { array->first = new_elem; }
    elem->prev = new_elem;
  }else{
    new_elem->next = array->first;
    new_elem->prev = 0;
    if( array->first ){ array->first->prev = new_elem; }
    array->first = new_elem;
  }
  array->ht[h].count++;
  array->ht[h].chain = new_elem;
  new_elem->data = data;
  rv.p = 0;
  rv.n = 0;
  return rv;
}

/*
** Information about each open database table is an instance of this 
** structure.  There will only be one such structure for each
** table.  If the VDBE opens the same table twice (as will happen
** for a self-join, for example) then two DbbeCursor structures are
** created but there is only a single MTable structure.
*/
typedef struct MTable MTable;
struct MTable {
  char *zName;            /* Name of the table */
  int delOnClose;         /* Delete when closing */
  int intKeyOnly;         /* Use only integer keys on this table */
  Array data;             /* The data in this stable */
};

/*
** The following structure contains all information used by GDBM
** database driver.  This is a subclass of the Dbbe structure.
*/
typedef struct Dbbex Dbbex;
struct Dbbex {
  Dbbe dbbe;         /* The base class */
  Array tables;      /* All tables of the database */
};

/*
** An cursor into a database file is an instance of the following structure.
** There can only be a single MTable structure for each disk file, but
** there can be multiple DbbeCursor structures.  Each DbbeCursor represents
** a cursor pointing to a particular part of the open MTable.  The
** MTable.nRef field hold a count of the number of DbbeCursor structures
** associated with the same disk file.
*/
struct DbbeCursor {
  Dbbex *pBe;        /* The database of which this record is a part */
  MTable *pTble;     /* The database file for this table */
  ArrayElem *elem;   /* Most recently accessed record */
  int needRewind;    /* Next key should be the first */
  int nextIndex;     /* Next recno in an index entry */
};

/*
** Forward declaration
*/
static void sqliteMemCloseCursor(DbbeCursor *pCursr);

/*
** Erase all the memory of an MTable
*/
static void deleteMTable(MTable *p){
  ArrayElem *i;
  for(i=ArrayFirst(&p->data); i; i=ArrayNext(i)){
    void *data = ArrayData(i);
    sqliteFree(data);
  }
  ArrayClear(&p->data);
  sqliteFree(p->zName);
  sqliteFree(p);
}

/*
** Completely shutdown the given database.  Close all files.  Free all memory.
*/
static void sqliteMemClose(Dbbe *pDbbe){
  Dbbex *pBe = (Dbbex*)pDbbe;
  MTable *pTble;
  ArrayElem *j;
  for(j=ArrayFirst(&pBe->tables); j; j=ArrayNext(j)){
    pTble = ArrayData(j);
    deleteMTable(pTble);
  }
  ArrayClear(&pBe->tables);
  memset(pBe, 0, sizeof(*pBe));
  sqliteFree(pBe);
}

/*
** Translate the name of an SQL table (or index) into its
** canonical name.
** 
** Space to hold the canonical name is obtained from
** sqliteMalloc() and must be freed by the calling function.
*/
static char *sqliteNameOfTable(const char *zTable){
  char *zNew = 0;
  int i, c;
  sqliteSetString(&zNew, zTable, 0);
  if( zNew==0 ) return 0;
  for(i=0; (c = zNew[i])!=0; i++){
    if( isupper(c) ){
      zNew[i] = tolower(c);
    }
  }
  return zNew;
}

/*
** Open a new table cursor.  Write a pointer to the corresponding
** DbbeCursor structure into *ppCursr.  Return an integer success
** code:
**
**    SQLITE_OK          It worked!
**
**    SQLITE_NOMEM       sqliteMalloc() failed
**
**    SQLITE_PERM        Attempt to access a file for which file
**                       access permission is denied
**
**    SQLITE_BUSY        Another thread or process is already using
**                       the corresponding file and has that file locked.
**
**    SQLITE_READONLY    The current thread already has this file open
**                       readonly but you are trying to open for writing.
**                       (This can happen if a SELECT callback tries to
**                       do an UPDATE or DELETE.)
**
** If zTable is 0 or "", then a temporary database file is created and
** a cursor to that temporary file is opened.  The temporary file
** will be deleted from the disk when it is closed.
*/
static int sqliteMemOpenCursor(
  Dbbe *pDbbe,            /* The database the table belongs to */
  const char *zTable,     /* The SQL name of the file to be opened */
  int writeable,          /* True to open for writing */
  int intKeyOnly,         /* True if only integer keys are used */
  DbbeCursor **ppCursr    /* Write the resulting table pointer here */
){
  DbbeCursor *pCursr;     /* The new table cursor */
  char *zName;            /* Canonical table name */
  MTable *pTble;          /* The underlying data file for this table */
  int rc = SQLITE_OK;     /* Return value */
  Dbbex *pBe = (Dbbex*)pDbbe;

  *ppCursr = 0;
  pCursr = sqliteMalloc( sizeof(*pCursr) );
  if( pCursr==0 ) return SQLITE_NOMEM;
  if( zTable ){
    Datum key;
    zName = sqliteNameOfTable(zTable);
    if( zName==0 ) return SQLITE_NOMEM;
    key.p = zName;
    key.n = strlen(zName);
    pTble = ArrayFind(&pBe->tables, key).p;
  }else{
    zName = 0;
    pTble = 0;
  }
  if( pTble==0 ){
    pTble = sqliteMalloc( sizeof(*pTble) );
    if( pTble==0 ){
      sqliteFree(zName);
      return SQLITE_NOMEM;
    }
    if( zName ){
      Datum ins_key, ins_data;
      pTble->zName = zName;
      pTble->delOnClose = 0;
      ins_data.p = pTble;
      ins_data.n = sizeof( *pTble );
      ins_key.p = zName;
      ins_key.n = strlen(zName);
      ArrayInsert(&pBe->tables, ins_key, ins_data);
    }else{
      pTble->zName = 0;
      pTble->delOnClose = 1;
    }
    pTble->intKeyOnly = intKeyOnly;
    ArrayInit(&pTble->data);
  }else{
    assert( pTble->intKeyOnly==intKeyOnly );
    sqliteFree(zName);
  }
  pCursr->pBe = pBe;
  pCursr->pTble = pTble;
  pCursr->needRewind = 1;
  *ppCursr = pCursr;
  return rc;
}

/*
** Drop a table from the database.  The file on the disk that corresponds
** to this table is deleted.
*/
static void sqliteMemDropTable(Dbbe *pDbbe, const char *zTable){
  char *zName;            /* Name of the table file */
  Datum key, data;
  MTable *pTble;
  Dbbex *pBe = (Dbbex*)pDbbe;

  zName = sqliteNameOfTable(zTable);
  key.p = zName;
  key.n = strlen(zName);
  pTble = ArrayFind(&pBe->tables, key).p;
  if( pTble ){
    data.p = 0;
    data.n = 0;
    ArrayInsert(&pBe->tables, key, data);
    deleteMTable(pTble);
  }
  sqliteFree(zName);
}

/*
** Close a cursor previously opened by sqliteMemOpenCursor().
**
** There can be multiple cursors pointing to the same open file.
** The underlying file is not closed until all cursors have been
** closed.  This routine decrements the MTable.nref field of the
** underlying file and closes the file when nref reaches 0.
*/
static void sqliteMemCloseCursor(DbbeCursor *pCursr){
  MTable *pTble;
  Dbbex *pBe;
  if( pCursr==0 ) return;
  pTble = pCursr->pTble;
  pBe = pCursr->pBe;
  if( pTble->delOnClose ){
    deleteMTable(pTble);
  }
  sqliteFree(pCursr);
}

/*
** Reorganize a table to reduce search times and disk usage.
*/
static int sqliteMemReorganizeTable(Dbbe *pBe, const char *zTable){
  /* Do nothing */
  return SQLITE_OK;
}

/*
** Fetch a single record from an open cursor.  Return 1 on success
** and 0 on failure.
*/
static int sqliteMemFetch(DbbeCursor *pCursr, int nKey, char *pKey){
  Datum key;
  key.n = nKey;
  key.p = pKey;
  assert( nKey==4 || pCursr->pTble->intKeyOnly==0 );
  pCursr->elem = ArrayFindElement(&pCursr->pTble->data, key);
  return pCursr->elem!=0;
}

/*
** Return 1 if the given key is already in the table.  Return 0
** if it is not.
*/
static int sqliteMemTest(DbbeCursor *pCursr, int nKey, char *pKey){
  return sqliteMemFetch(pCursr, nKey, pKey);
}

/*
** Copy bytes from the current key or data into a buffer supplied by
** the calling function.  Return the number of bytes copied.
*/
static
int sqliteMemCopyKey(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->elem==0 ) return 0;
  if( offset>=ArrayKeySize(pCursr->elem) ) return 0;
  if( offset+size>ArrayKeySize(pCursr->elem) ){
    n = ArrayKeySize(pCursr->elem) - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &((char*)ArrayKey(pCursr->elem))[offset], n);
  return n;
}
static
int sqliteMemCopyData(DbbeCursor *pCursr, int offset, int size, char *zBuf){
  int n;
  if( pCursr->elem==0 ) return 0;
  if( offset>=ArrayDataSize(pCursr->elem) ) return 0;
  if( offset+size>ArrayDataSize(pCursr->elem) ){
    n = ArrayDataSize(pCursr->elem) - offset;
  }else{
    n = size;
  }
  memcpy(zBuf, &((char*)ArrayData(pCursr->elem))[offset], n);
  return n;
}

/*
** Return a pointer to bytes from the key or data.  The data returned
** is ephemeral.
*/
static char *sqliteMemReadKey(DbbeCursor *pCursr, int offset){
  if( pCursr->elem==0 || offset<0 || offset>=ArrayKeySize(pCursr->elem) ){
    return "";
  }
  return &((char*)ArrayKey(pCursr->elem))[offset];
}
static char *sqliteMemReadData(DbbeCursor *pCursr, int offset){
  if( pCursr->elem==0 || offset<0 || offset>=ArrayDataSize(pCursr->elem) ){
    return "";
  }
  return &((char*)ArrayData(pCursr->elem))[offset];
}

/*
** Return the total number of bytes in either data or key.
*/
static int sqliteMemKeyLength(DbbeCursor *pCursr){
  return pCursr->elem ? ArrayKeySize(pCursr->elem) : 0;
}
static int sqliteMemDataLength(DbbeCursor *pCursr){
  return pCursr->elem ? ArrayDataSize(pCursr->elem) : 0;
}

/*
** Make is so that the next call to sqliteNextKey() finds the first
** key of the table.
*/
static int sqliteMemRewind(DbbeCursor *pCursr){
  pCursr->needRewind = 1;
  return SQLITE_OK;
}

/*
** Read the next key from the table.  Return 1 on success.  Return
** 0 if there are no more keys.
*/
static int sqliteMemNextKey(DbbeCursor *pCursr){
  if( pCursr->needRewind || pCursr->elem==0 ){
    pCursr->elem = ArrayFirst(&pCursr->pTble->data);
    pCursr->needRewind = 0;
  }else{
    pCursr->elem = ArrayNext(pCursr->elem);
  }
  return pCursr->elem!=0;
}

/*
** Get a new integer key.
*/
static int sqliteMemNew(DbbeCursor *pCursr){
  int iKey;
  Datum key;
  int go = 1;

  while( go ){
    iKey = sqliteRandomInteger() & 0x7fffffff;
    if( iKey==0 ) continue;
    key.p = (char*)&iKey;
    key.n = 4;
    go = ArrayFindElement(&pCursr->pTble->data, key)!=0;
  }
  return iKey;
}   

/*
** Write an entry into the table.  Overwrite any prior entry with the
** same key.
*/
static int sqliteMemPut(
  DbbeCursor *pCursr,       /* Write new entry into this database table */
  int nKey, char *pKey,     /* The key of the new entry */
  int nData, char *pData    /* The data of the new entry */
){
  Datum data, key;
  data.n = nData;
  data.p = sqliteMalloc( data.n );
  if( data.p==0 ) return SQLITE_NOMEM;
  memcpy(data.p, pData, data.n);
  key.n = nKey;
  key.p = pKey;
  assert( nKey==4 || pCursr->pTble->intKeyOnly==0 );
  data = ArrayInsert(&pCursr->pTble->data, key, data);
  if( data.p ){
    sqliteFree(data.p);
  }
  return SQLITE_OK;
}

/*
** Remove an entry from a table, if the entry exists.
*/
static int sqliteMemDelete(DbbeCursor *pCursr, int nKey, char *pKey){
  Datum key, data;
  key.n = nKey;
  key.p = pKey;
  data.p = 0;
  data.n = 0;
  data = ArrayInsert(&pCursr->pTble->data, key, data);
  if( data.p ){
    sqliteFree(data.p);
  }
  return SQLITE_OK;
}

/*
** Begin scanning an index for the given key.  Return 1 on success and
** 0 on failure.
*/
static int sqliteMemBeginIndex(DbbeCursor *pCursr, int nKey, char *pKey){
  if( !sqliteMemFetch(pCursr, nKey, pKey) ) return 0;
  pCursr->nextIndex = 0;
  return 1;
}

/*
** Return an integer key which is the next record number in the index search
** that was started by a prior call to BeginIndex.  Return 0 if all records
** have already been searched.
*/
static int sqliteMemNextIndex(DbbeCursor *pCursr){
  int *aIdx;
  int nIdx;
  int k;
  nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
  aIdx = (int*)sqliteMemReadData(pCursr, 0);
  if( nIdx>1 ){
    k = *(aIdx++);
    if( k>nIdx-1 ) k = nIdx-1;
  }else{
    k = nIdx;
  }
  while( pCursr->nextIndex < k ){
    int recno = aIdx[pCursr->nextIndex++];
    if( recno!=0 ) return recno;
  }
  pCursr->nextIndex = 0;
  return 0;
}

/*
** Write a new record number and key into an index table.  Return a status
** code.
*/
static int sqliteMemPutIndex(DbbeCursor *pCursr, int nKey, char *pKey, int N){
  int r = sqliteMemFetch(pCursr, nKey, pKey);
  if( r==0 ){
    /* Create a new record for this index */
    sqliteMemPut(pCursr, nKey, pKey, sizeof(int), (char*)&N);
  }else{
    /* Extend the existing record */
    int nIdx;
    int *aIdx;
    int k;
            
    nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
    if( nIdx==1 ){
      aIdx = sqliteMalloc( sizeof(int)*4 );
      if( aIdx==0 ) return SQLITE_NOMEM;
      aIdx[0] = 2;
      sqliteMemCopyData(pCursr, 0, sizeof(int), (char*)&aIdx[1]);
      aIdx[2] = N;
      sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*4, (char*)aIdx);
      sqliteFree(aIdx);
    }else{
      aIdx = (int*)sqliteMemReadData(pCursr, 0);
      k = aIdx[0];
      if( k<nIdx-1 ){
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
      }else{
        nIdx *= 2;
        aIdx = sqliteMalloc( sizeof(int)*nIdx );
        if( aIdx==0 ) return SQLITE_NOMEM;
        sqliteMemCopyData(pCursr, 0, sizeof(int)*(k+1), (char*)aIdx);
        aIdx[k+1] = N;
        aIdx[0]++;
        sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
        sqliteFree(aIdx);
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete an index entry.  Return a status code.
*/
static int sqliteMemDeleteIndex(DbbeCursor *pCursr,int nKey,char *pKey, int N){
  int *aIdx;
  int nIdx;
  int j, k;
  int rc;
  rc = sqliteMemFetch(pCursr, nKey, pKey);
  if( !rc ) return SQLITE_OK;
  nIdx = sqliteMemDataLength(pCursr)/sizeof(int);
  if( nIdx==0 ) return SQLITE_OK;
  aIdx = (int*)sqliteMemReadData(pCursr, 0);
  if( (nIdx==1 && aIdx[0]==N) || (aIdx[0]==1 && aIdx[1]==N) ){
    sqliteMemDelete(pCursr, nKey, pKey);
  }else{
    k = aIdx[0];
    for(j=1; j<=k && aIdx[j]!=N; j++){}
    if( j>k ) return SQLITE_OK;
    aIdx[j] = aIdx[k];
    aIdx[k] = 0;
    aIdx[0]--;
    if( aIdx[0]*3 + 1 < nIdx ){
      nIdx /= 2;
    }
    sqliteMemPut(pCursr, nKey, pKey, sizeof(int)*nIdx, (char*)aIdx);
  }
  return SQLITE_OK;
}

/*
** This variable contains pointers to all of the access methods
** used to implement the MEMORY backend.
*/
static struct DbbeMethods memoryMethods = {
  /*           Close */   sqliteMemClose,
  /*      OpenCursor */   sqliteMemOpenCursor,
  /*       DropTable */   sqliteMemDropTable,
  /* ReorganizeTable */   sqliteMemReorganizeTable,
  /*     CloseCursor */   sqliteMemCloseCursor,
  /*           Fetch */   sqliteMemFetch,
  /*            Test */   sqliteMemTest,
  /*         CopyKey */   sqliteMemCopyKey,
  /*        CopyData */   sqliteMemCopyData,
  /*         ReadKey */   sqliteMemReadKey,
  /*        ReadData */   sqliteMemReadData,
  /*       KeyLength */   sqliteMemKeyLength,
  /*      DataLength */   sqliteMemDataLength,
  /*         NextKey */   sqliteMemNextKey,
  /*          Rewind */   sqliteMemRewind,
  /*             New */   sqliteMemNew,
  /*             Put */   sqliteMemPut,
  /*          Delete */   sqliteMemDelete,
  /*      BeginTrans */   0,
  /*          Commit */   0,
  /*        Rollback */   0,
  /*      BeginIndex */   sqliteMemBeginIndex,
  /*       NextIndex */   sqliteMemNextIndex,
  /*        PutIndex */   sqliteMemPutIndex,
  /*     DeleteIndex */   sqliteMemDeleteIndex,
};

/*
** This routine opens a new database.  For the MEMORY driver
** implemented here, the database name is ignored.  Every MEMORY database
** is unique and is erased when the database is closed.
**
** If successful, a pointer to the Dbbe structure is returned.
** If there are errors, an appropriate error message is left
** in *pzErrMsg and NULL is returned.
*/
Dbbe *sqliteMemOpen(
  const char *zName,     /* The name of the database */
  int writeFlag,         /* True if we will be writing to the database */
  int createFlag,        /* True to create database if it doesn't exist */
  char **pzErrMsg        /* Write error messages (if any) here */
){
  Dbbex *pNew;

  pNew = sqliteMalloc( sizeof(*pNew) );
  if( pNew==0 ){
    sqliteSetString(pzErrMsg, "out of memory", 0);
    return 0;
  }
  ArrayInit(&pNew->tables);
  pNew->dbbe.x = &memoryMethods;
  return &pNew->dbbe;
}
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<




























































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Changes to src/delete.c.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.10 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process a DELETE FROM statement.
*/
void sqliteDeleteFrom(
................................................................................
    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Open, base+i, pIdx->tnum, 0, 0);
    }
    end = sqliteVdbeMakeLabel(v);
    addr = sqliteVdbeAddOp(v, OP_ListRead, 0, end, 0, 0);
    if( pTab->pIndex ){
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_Fetch, base, 0, 0, 0);
      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        int j;
        sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
        for(j=0; j<pIdx->nColumn; j++){
          sqliteVdbeAddOp(v, OP_Field, base, pIdx->aiColumn[j], 0, 0);
        }
        sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
        sqliteVdbeAddOp(v, OP_DeleteIdx, base+i, 0, 0, 0);
      }
    }
    sqliteVdbeAddOp(v, OP_Delete, base, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);







|







 







|




|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle DELETE FROM statements.
**
** $Id: delete.c,v 1.11 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** Process a DELETE FROM statement.
*/
void sqliteDeleteFrom(
................................................................................
    for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
      sqliteVdbeAddOp(v, OP_Open, base+i, pIdx->tnum, 0, 0);
    }
    end = sqliteVdbeMakeLabel(v);
    addr = sqliteVdbeAddOp(v, OP_ListRead, 0, end, 0, 0);
    if( pTab->pIndex ){
      sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_MoveTo, base, 0, 0, 0);
      for(i=1, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){
        int j;
        sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
        for(j=0; j<pIdx->nColumn; j++){
          sqliteVdbeAddOp(v, OP_Column, base, pIdx->aiColumn[j], 0, 0);
        }
        sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
        sqliteVdbeAddOp(v, OP_DeleteIdx, base+i, 0, 0, 0);
      }
    }
    sqliteVdbeAddOp(v, OP_Delete, base, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Goto, 0, addr, 0, 0);

Changes to src/expr.c.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
...
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions.
**
** $Id: expr.c,v 1.25 2001/07/23 14:33:04 drh Exp $
*/
#include "sqliteInt.h"

/*
** Walk an expression tree.  Return 1 if the expression is constant
** and 0 if it involves variables.
*/
................................................................................
      if( pExpr->pSelect ){
        /* Case 1:     expr IN (SELECT ...)
        **
        ** Generate code to write the results of the select into a temporary
        ** table.  The cursor number of the temporary table has already
        ** been put in iTable by sqliteExprResolveInSelect().
        */
        sqliteVdbeAddOp(v, OP_OpenIdx, pExpr->iTable, 1, 0, 0);
        if( sqliteSelect(pParse, pExpr->pSelect, SRT_Set, pExpr->iTable) );
      }else if( pExpr->pList ){
        /* Case 2:     expr IN (exprlist)
        **
        ** Create a set to put the exprlist values in.  The Set id is stored
        ** in iTable.
        */
................................................................................
    default: break;
  }
  switch( pExpr->op ){
    case TK_COLUMN: {
      if( pParse->useAgg ){
        sqliteVdbeAddOp(v, OP_AggGet, 0, pExpr->iAgg, 0, 0);
      }else if( pExpr->iColumn>=0 ){
        sqliteVdbeAddOp(v, OP_Field, pExpr->iTable, pExpr->iColumn, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_Key, pExpr->iTable, 0, 0, 0);
      }
      break;
    }
    case TK_INTEGER: {
      int i = atoi(pExpr->token.z);
      sqliteVdbeAddOp(v, OP_Integer, i, 0, 0, 0);
      break;







|







 







|







 







|

|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
...
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains routines used for analyzing expressions and
** for generating VDBE code that evaluates expressions.
**
** $Id: expr.c,v 1.26 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** Walk an expression tree.  Return 1 if the expression is constant
** and 0 if it involves variables.
*/
................................................................................
      if( pExpr->pSelect ){
        /* Case 1:     expr IN (SELECT ...)
        **
        ** Generate code to write the results of the select into a temporary
        ** table.  The cursor number of the temporary table has already
        ** been put in iTable by sqliteExprResolveInSelect().
        */
        sqliteVdbeAddOp(v, OP_OpenTemp, pExpr->iTable, 0, 0, 0);
        if( sqliteSelect(pParse, pExpr->pSelect, SRT_Set, pExpr->iTable) );
      }else if( pExpr->pList ){
        /* Case 2:     expr IN (exprlist)
        **
        ** Create a set to put the exprlist values in.  The Set id is stored
        ** in iTable.
        */
................................................................................
    default: break;
  }
  switch( pExpr->op ){
    case TK_COLUMN: {
      if( pParse->useAgg ){
        sqliteVdbeAddOp(v, OP_AggGet, 0, pExpr->iAgg, 0, 0);
      }else if( pExpr->iColumn>=0 ){
        sqliteVdbeAddOp(v, OP_Column, pExpr->iTable, pExpr->iColumn, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_FullKey, pExpr->iTable, 0, 0, 0);
      }
      break;
    }
    case TK_INTEGER: {
      int i = atoi(pExpr->token.z);
      sqliteVdbeAddOp(v, OP_Integer, i, 0, 0, 0);
      break;

Changes to src/insert.c.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
..
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
...
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
...
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle INSERT statements.
**
** $Id: insert.c,v 1.14 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is call to handle SQL of the following forms:
**
**    insert into TABLE (IDLIST) values(EXPRLIST)
................................................................................
  ** all the code to implement the SELECT statement and leave the data
  ** in a temporary table.  If data is coming from an expression list,
  ** then we just have to count the number of expressions.
  */
  if( pSelect ){
    int rc;
    srcTab = pParse->nTab++;
    sqliteVdbeAddOp(v, OP_OpenTbl, srcTab, 1, 0, 0);
    rc = sqliteSelect(pParse, pSelect, SRT_Table, srcTab);
    if( rc || pParse->nErr || sqlite_malloc_failed ) goto insert_cleanup;
    assert( pSelect->pEList );
    nColumn = pSelect->pEList->nExpr;
  }else{
    assert( pList!=0 );
    srcTab = -1;
................................................................................
    }
  }

  /* Open cursors into the table that is received the new data and
  ** all indices of that table.
  */
  base = pParse->nTab;
  sqliteVdbeAddOp(v, OP_OpenTbl, base, 1, pTab->zName, 0);
  for(idx=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, idx++){
    sqliteVdbeAddOp(v, OP_OpenIdx, idx+base, 1, pIdx->zName, 0);
  }

  /* If the data source is a SELECT statement, then we have to create
  ** a loop because there might be multiple rows of data.  If the data
  ** source is an expression list, then exactly one row will be inserted
  ** and the loop is not used.
  */
................................................................................
    sqliteVdbeAddOp(v, OP_Rewind, srcTab, 0, 0, 0);
    iBreak = sqliteVdbeMakeLabel(v);
    iCont = sqliteVdbeAddOp(v, OP_Next, srcTab, iBreak, 0, 0);
  }

  /* Create a new entry in the table and fill it with data.
  */
  sqliteVdbeAddOp(v, OP_New, 0, 0, 0, 0);
  if( pTab->pIndex ){
    sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
  }
  for(i=0; i<pTab->nCol; i++){
    if( pColumn==0 ){
      j = i;
    }else{
................................................................................
      char *zDflt = pTab->aCol[i].zDflt;
      if( zDflt==0 ){
        sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_String, 0, 0, zDflt, 0);
      }
    }else if( srcTab>=0 ){
      sqliteVdbeAddOp(v, OP_Field, srcTab, i, 0, 0); 
    }else{
      sqliteExprCode(pParse, pList->a[j].pExpr);
    }
  }
  sqliteVdbeAddOp(v, OP_MakeRecord, pTab->nCol, 0, 0, 0);
  sqliteVdbeAddOp(v, OP_Put, base, 0, 0, 0);

................................................................................
        char *zDflt = pTab->aCol[idx].zDflt;
        if( zDflt==0 ){
          sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
        }else{
          sqliteVdbeAddOp(v, OP_String, 0, 0, zDflt, 0);
        }
      }else if( srcTab>=0 ){
        sqliteVdbeAddOp(v, OP_Field, srcTab, idx, 0, 0); 
      }else{
        sqliteExprCode(pParse, pList->a[j].pExpr);
      }
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, idx+base, 0, 0, 0);
  }







|







 







|







 







|

|







 







|







 







|







 







|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
..
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
...
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
...
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle INSERT statements.
**
** $Id: insert.c,v 1.15 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** This routine is call to handle SQL of the following forms:
**
**    insert into TABLE (IDLIST) values(EXPRLIST)
................................................................................
  ** all the code to implement the SELECT statement and leave the data
  ** in a temporary table.  If data is coming from an expression list,
  ** then we just have to count the number of expressions.
  */
  if( pSelect ){
    int rc;
    srcTab = pParse->nTab++;
    sqliteVdbeAddOp(v, OP_OpenTemp, srcTab, 0, 0, 0);
    rc = sqliteSelect(pParse, pSelect, SRT_Table, srcTab);
    if( rc || pParse->nErr || sqlite_malloc_failed ) goto insert_cleanup;
    assert( pSelect->pEList );
    nColumn = pSelect->pEList->nExpr;
  }else{
    assert( pList!=0 );
    srcTab = -1;
................................................................................
    }
  }

  /* Open cursors into the table that is received the new data and
  ** all indices of that table.
  */
  base = pParse->nTab;
  sqliteVdbeAddOp(v, OP_Open, base, pTab->tnum, pTab->zName, 0);
  for(idx=1, pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext, idx++){
    sqliteVdbeAddOp(v, OP_Open, idx+base, pIdx->tnum, pIdx->zName, 0);
  }

  /* If the data source is a SELECT statement, then we have to create
  ** a loop because there might be multiple rows of data.  If the data
  ** source is an expression list, then exactly one row will be inserted
  ** and the loop is not used.
  */
................................................................................
    sqliteVdbeAddOp(v, OP_Rewind, srcTab, 0, 0, 0);
    iBreak = sqliteVdbeMakeLabel(v);
    iCont = sqliteVdbeAddOp(v, OP_Next, srcTab, iBreak, 0, 0);
  }

  /* Create a new entry in the table and fill it with data.
  */
  sqliteVdbeAddOp(v, OP_NewRecno, 0, 0, 0, 0);
  if( pTab->pIndex ){
    sqliteVdbeAddOp(v, OP_Dup, 0, 0, 0, 0);
  }
  for(i=0; i<pTab->nCol; i++){
    if( pColumn==0 ){
      j = i;
    }else{
................................................................................
      char *zDflt = pTab->aCol[i].zDflt;
      if( zDflt==0 ){
        sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
      }else{
        sqliteVdbeAddOp(v, OP_String, 0, 0, zDflt, 0);
      }
    }else if( srcTab>=0 ){
      sqliteVdbeAddOp(v, OP_Column, srcTab, i, 0, 0); 
    }else{
      sqliteExprCode(pParse, pList->a[j].pExpr);
    }
  }
  sqliteVdbeAddOp(v, OP_MakeRecord, pTab->nCol, 0, 0, 0);
  sqliteVdbeAddOp(v, OP_Put, base, 0, 0, 0);

................................................................................
        char *zDflt = pTab->aCol[idx].zDflt;
        if( zDflt==0 ){
          sqliteVdbeAddOp(v, OP_Null, 0, 0, 0, 0);
        }else{
          sqliteVdbeAddOp(v, OP_String, 0, 0, zDflt, 0);
        }
      }else if( srcTab>=0 ){
        sqliteVdbeAddOp(v, OP_Column, srcTab, idx, 0, 0); 
      }else{
        sqliteExprCode(pParse, pList->a[j].pExpr);
      }
    }
    sqliteVdbeAddOp(v, OP_MakeIdxKey, pIdx->nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_PutIdx, idx+base, 0, 0, 0);
  }

Changes to src/main.c.

22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.30 2001/09/13 13:46:56 drh Exp $
*/
#include "sqliteInt.h"
#if defined(HAVE_USLEEP) && HAVE_USLEEP
#include <unistd.h>
#endif

/*
................................................................................
      default: {
        if( pzErrMsg ){
          sqliteSetString(pzErrMsg, "unable to open database: ", zFilename, 0);
        }
      }
    }
    sqliteFree(db);
    return rc;
  }

  /* Assume file format 1 unless the database says otherwise */
  db->file_format = 1;

  /* Attempt to read the schema */
  rc = sqliteInit(db, pzErrMsg);







|







 







|







22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
**
*************************************************************************
** Main file for the SQLite library.  The routines in this file
** implement the programmer interface to the library.  Routines in
** other files are for internal use by SQLite and should not be
** accessed by users of the library.
**
** $Id: main.c,v 1.31 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"
#if defined(HAVE_USLEEP) && HAVE_USLEEP
#include <unistd.h>
#endif

/*
................................................................................
      default: {
        if( pzErrMsg ){
          sqliteSetString(pzErrMsg, "unable to open database: ", zFilename, 0);
        }
      }
    }
    sqliteFree(db);
    return 0;
  }

  /* Assume file format 1 unless the database says otherwise */
  db->file_format = 1;

  /* Attempt to read the schema */
  rc = sqliteInit(db, pzErrMsg);

Changes to src/pager.c.

23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
...
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
....
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or to one writer.
**
** @(#) $Id: pager.c,v 1.14 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>
................................................................................
     "/temp",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && S_IWUSR(buf.st_mode) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*
................................................................................
    if( fd<0 ){
      fd = open(zFilename, O_RDONLY, 0);
      readOnly = 1;
    }
    tempFile = 0;
  }else{
    int cnt = 8;
    char *zDir = findTempDir();
    if( zDir==0 ) return SQLITE_CANTOPEN;
    do{
      cnt--;
      sprintf(zTemp,"%s/_sqlite_%u",(unsigned)sqliteRandomInteger());
      fd = open(zTemp, O_RDWR|O_CREAT|O_EXCL, 0600);
    }while( cnt>0 && fd<0 );
    zFilename = zTemp;
    tempFile = 1;
  }
  if( fd<0 ){
    return SQLITE_CANTOPEN;
................................................................................
};

/*
** Return TRUE if the database file is opened read-only.  Return FALSE
** if the database is (in theory) writable.
*/
int sqlitepager_isreadonly(Pager *pPager){
  return pPager->readonly;
}

/*
** This routine is used for testing and analysis only.
*/
int *sqlitepager_stats(Pager *pPager){
  static int a[9];







|







 







|







 







|



|







 







|







23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
...
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
....
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
*************************************************************************
** This is the implementation of the page cache subsystem.
** 
** The page cache is used to access a database file.  The pager journals
** all writes in order to support rollback.  Locking is used to limit
** access to one or more reader or to one writer.
**
** @(#) $Id: pager.c,v 1.15 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include <fcntl.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>
................................................................................
     "/temp",
     "./temp",
  };
  int i;
  struct stat buf;
  for(i=0; i<sizeof(azDirs)/sizeof(azDirs[0]); i++){
    if( stat(azDirs[i], &buf)==0 && S_ISDIR(buf.st_mode)
         && access(azDirs[i], W_OK) ){
       return azDirs[i];
    }
  }
  return 0;
}

/*
................................................................................
    if( fd<0 ){
      fd = open(zFilename, O_RDONLY, 0);
      readOnly = 1;
    }
    tempFile = 0;
  }else{
    int cnt = 8;
    const char *zDir = findTempDir();
    if( zDir==0 ) return SQLITE_CANTOPEN;
    do{
      cnt--;
      sprintf(zTemp,"%s/_sqlite_%u", zDir, (unsigned)sqliteRandomInteger());
      fd = open(zTemp, O_RDWR|O_CREAT|O_EXCL, 0600);
    }while( cnt>0 && fd<0 );
    zFilename = zTemp;
    tempFile = 1;
  }
  if( fd<0 ){
    return SQLITE_CANTOPEN;
................................................................................
};

/*
** Return TRUE if the database file is opened read-only.  Return FALSE
** if the database is (in theory) writable.
*/
int sqlitepager_isreadonly(Pager *pPager){
  return pPager->readOnly;
}

/*
** This routine is used for testing and analysis only.
*/
int *sqlitepager_stats(Pager *pPager){
  static int a[9];

Changes to src/select.c.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
...
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements.
**
** $Id: select.c,v 1.32 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
  if( pEList ){
    for(i=0; i<pEList->nExpr; i++){
      sqliteExprCode(pParse, pEList->a[i].pExpr);
    }
    nColumn = pEList->nExpr;
  }else{
    for(i=0; i<nColumn; i++){
      sqliteVdbeAddOp(v, OP_Field, srcTab, i, 0, 0);
    }
  }

  /* If the DISTINCT keyword was present on the SELECT statement
  ** and this row has been seen before, then do not make this row
  ** part of the result.
  */
................................................................................
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Store the result as data using a unique key.
  */
  if( eDest==SRT_Table ){
    sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_New, iParm, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Pull, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Construct a record from the query result, but instead of
  ** saving that record, use it as a key to delete elements from
  ** the temporary table iParm.







|







 







|







 







|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
...
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
...
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements.
**
** $Id: select.c,v 1.33 2001/09/13 14:46:10 drh Exp $
*/
#include "sqliteInt.h"

/*
** Allocate a new Select structure and return a pointer to that
** structure.
*/
................................................................................
  if( pEList ){
    for(i=0; i<pEList->nExpr; i++){
      sqliteExprCode(pParse, pEList->a[i].pExpr);
    }
    nColumn = pEList->nExpr;
  }else{
    for(i=0; i<nColumn; i++){
      sqliteVdbeAddOp(v, OP_Column, srcTab, i, 0, 0);
    }
  }

  /* If the DISTINCT keyword was present on the SELECT statement
  ** and this row has been seen before, then do not make this row
  ** part of the result.
  */
................................................................................
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Store the result as data using a unique key.
  */
  if( eDest==SRT_Table ){
    sqliteVdbeAddOp(v, OP_MakeRecord, nColumn, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_NewRecno, iParm, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Pull, 1, 0, 0, 0);
    sqliteVdbeAddOp(v, OP_Put, iParm, 0, 0, 0);
  }else 

  /* Construct a record from the query result, but instead of
  ** saving that record, use it as a key to delete elements from
  ** the temporary table iParm.

Changes to src/sqliteInt.h.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
...
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
...
206
207
208
209
210
211
212

213
214
215
216
217
218
219
...
441
442
443
444
445
446
447
448
449
450
451
452
453
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.43 2001/09/13 13:46:57 drh Exp $
*/
#include "sqlite.h"
#include "vdbe.h"
#include "parse.h"
#ifndef DISABLE_GDBM
#include <gdbm.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
** The paging system deals with 32-bit integers.
................................................................................
  Table *pHash;    /* Next table with same hash on zName */
  int nCol;        /* Number of columns in this table */
  Column *aCol;    /* Information about each column */
  Index *pIndex;   /* List of SQL indexes on this table. */
  int tnum;        /* Page containing root for this table */
  int readOnly;    /* True if this table should not be written by the user */
  int isCommit;    /* True if creation of this table has been committed */
  int isDelete;    /* True if deletion of this table has not been comitted */    
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described
................................................................................
*/
struct Index {
  char *zName;     /* Name of this index */
  Index *pHash;    /* Next index with the same hash on zName */
  int nColumn;     /* Number of columns in the table used by this index */
  int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  Table *pTable;   /* The SQL table being indexed */

  int isUnique;    /* True if keys must all be unique */
  int isCommit;    /* True if creation of this index has been committed */
  int isDelete;    /* True if deletion of this index has not been comitted */
  Index *pNext;    /* The next index associated with the same table */
};

/*
................................................................................
void sqliteExprResolveInSelect(Parse*, Expr*);
int sqliteExprAnalyzeAggregates(Parse*, Expr*);
void sqliteParseInfoReset(Parse*);
Vdbe *sqliteGetVdbe(Parse*);
int sqliteRandomByte(void);
int sqliteRandomInteger(void);
void sqliteRandomName(char*,char*);
char *sqliteDbbeNameToFile(const char*,const char*,const char*);
void sqliteBeginTransaction(Parse*);
void sqliteCommitTransaction(Parse*);
void sqliteRollbackTransaction(Parse*);
char *sqlite_mprintf(const char *, ...);
const char *sqliteErrStr(int);







|




<
|
<







 







|







 







>







 







<





19
20
21
22
23
24
25
26
27
28
29
30

31

32
33
34
35
36
37
38
...
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
...
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
...
440
441
442
443
444
445
446

447
448
449
450
451
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.44 2001/09/13 14:46:10 drh Exp $
*/
#include "sqlite.h"
#include "vdbe.h"
#include "parse.h"

#include "btree.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*
** The paging system deals with 32-bit integers.
................................................................................
  Table *pHash;    /* Next table with same hash on zName */
  int nCol;        /* Number of columns in this table */
  Column *aCol;    /* Information about each column */
  Index *pIndex;   /* List of SQL indexes on this table. */
  int tnum;        /* Page containing root for this table */
  int readOnly;    /* True if this table should not be written by the user */
  int isCommit;    /* True if creation of this table has been committed */
  int isDelete;    /* True if this table is being deleted */
};

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described
................................................................................
*/
struct Index {
  char *zName;     /* Name of this index */
  Index *pHash;    /* Next index with the same hash on zName */
  int nColumn;     /* Number of columns in the table used by this index */
  int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  Table *pTable;   /* The SQL table being indexed */
  int tnum;        /* Page containing root of this index in database file */
  int isUnique;    /* True if keys must all be unique */
  int isCommit;    /* True if creation of this index has been committed */
  int isDelete;    /* True if deletion of this index has not been comitted */
  Index *pNext;    /* The next index associated with the same table */
};

/*
................................................................................
void sqliteExprResolveInSelect(Parse*, Expr*);
int sqliteExprAnalyzeAggregates(Parse*, Expr*);
void sqliteParseInfoReset(Parse*);
Vdbe *sqliteGetVdbe(Parse*);
int sqliteRandomByte(void);
int sqliteRandomInteger(void);
void sqliteRandomName(char*,char*);

void sqliteBeginTransaction(Parse*);
void sqliteCommitTransaction(Parse*);
void sqliteRollbackTransaction(Parse*);
char *sqlite_mprintf(const char *, ...);
const char *sqliteErrStr(int);

Changes to src/vdbe.c.

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
...
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
...
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
....
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
....
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
....
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
....
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
....
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
....
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
....
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
....
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
....
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
....
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
....
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
....
2246
2247
2248
2249
2250
2251
2252

2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
....
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
....
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
....
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
....
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
....
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
....
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
....
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
....
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
....
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
....
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
....
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
** inplicit conversion from one 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.60 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** SQL is translated into a sequence of instructions to be
** executed by a virtual machine.  Each instruction is an instance
................................................................................
};

/*
** An instance of the virtual machine
*/
struct Vdbe {
  sqlite *db;         /* The whole database */
  Dbbe *pBe;          /* Opaque context structure used by DB backend */
  FILE *trace;        /* Write an execution trace here, if not NULL */
  int nOp;            /* Number of instructions in the program */
  int nOpAlloc;       /* Number of slots allocated for aOp[] */
  Op *aOp;            /* Space to hold the virtual machine's program */
  int nLabel;         /* Number of labels used */
  int nLabelAlloc;    /* Number of slots allocated in aLabel[] */
  int *aLabel;        /* Space to hold the labels */
................................................................................
/*
** Create a new virtual database engine.
*/
Vdbe *sqliteVdbeCreate(sqlite *db){
  Vdbe *p;
  p = sqliteMalloc( sizeof(Vdbe) );
  if( p==0 ) return 0;
  p->pBe = db->pBe;
  p->db = db;
  return p;
}

/*
** Turn tracing on or off
*/
................................................................................
  "Recno",             "FullKey",           "Rewind",            "Next",
  "Destroy",           "CreateIndex",       "CreateTable",       "Reorganize",
  "BeginIdx",          "NextIdx",           "PutIdx",            "DeleteIdx",
  "MemLoad",           "MemStore",          "ListOpen",          "ListWrite",
  "ListRewind",        "ListRead",          "ListClose",         "SortOpen",
  "SortPut",           "SortMakeRec",       "SortMakeKey",       "Sort",
  "SortNext",          "SortKey",           "SortCallback",      "SortClose",
  "FileOpen",          "FileRead",          "FileField",         "FileClose",
  "AggReset",          "AggFocus",          "AggIncr",           "AggNext",
  "AggSet",            "AggGet",            "SetInsert",         "SetFound",
  "SetNotFound",       "SetClear",          "MakeRecord",        "MakeKey",
  "Goto",              "If",                "Halt",              "ColumnCount",
  "ColumnName",        "Callback",          "Integer",           "String",
  "Null",              "Pop",               "Dup",               "Pull",
  "Add",               "AddImm",            "Subtract",          "Multiply",
  "Divide",            "Min",               "Max",               "Like",
  "Glob",              "Eq",                "Ne",                "Lt",
  "Le",                "Gt",                "Ge",                "IsNull",
  "NotNull",           "Negative",          "And",               "Or",
  "Not",               "Concat",            "Noop",              "Strlen",
  "Substr",          
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.
................................................................................
  char **pzErrMsg,           /* Error msg written here */
  void *pBusyArg,            /* 1st argument to the busy callback */
  int (*xBusy)(void*,const char*,int)  /* Called when a file is busy */
){
  int pc;                    /* The program counter */
  Op *pOp;                   /* Current operation */
  int rc;                    /* Value to return */
  Dbbe *pBe = p->pBe;        /* The backend driver */
  sqlite *db = p->db;        /* The database */
  int rollbackOnError = 0;   /* If TRUE, rollback if the script fails.
  char **zStack;             /* Text stack */
  Stack *aStack;             /* Additional stack information */
  char zBuf[100];            /* Space to sprintf() an integer */


  /* No instruction ever pushes more than a single element onto the
  ** stack.  And the stack never grows on successive executions of the
................................................................................
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j++] = 0;
  Integerify(p, p->tos-nField);
  memcpy(&zNewKey[j], aStack[p->tos-nField].i, sizeof(int));
  PopStack(p, nField+1);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
................................................................................
** opcode is encountered or whenever there is an execution error that causes
** a script to abort.  
**
** A transaction must be started before any changes can be made to the
** database.
*/
case OP_Transaction: {
  rc = sqliteBtreeBeginTrans(pBe);
  break;
}

/* Opcode: Commit * * *
**
** Cause all modifications to the database that have been made since the
** last Transaction to actually take effect.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Commit: {
  rc = sqliteBtreeCommit(pBe);
  if( rc==SQLITE_OK ){
    sqliteCommitInternalChanges(db);
  }else{
    sqliteRollbackInternalChanges(db);
  }
  break;
}
................................................................................
**
** Cause all modifications to the database that have been made since the
** last Transaction to be undone. The database is restored to its state
** before the Transaction opcode was executed.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Rollback: {
  rc = sqliteBtreeRollback(pBe);
  sqliteRollbackInternalChanges(db);
  break;
}

/* Opcode: Open P1 P2 P3
**
** Open a new cursor for the database table whose root page is
................................................................................
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  memset(&p->aCsr[i], 0, sizeof(Cursor));
  do {
    rc = sqliteBtreeOpenCursor(pBe, pOp->p2, &p->aCsr[i].pCursor);
    switch( rc ){
      case SQLITE_BUSY: {
        if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
          sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
          busy = 0;
        }
        break;
................................................................................
**
** Open a new cursor that points to a table in a temporary database
** file.  The temporary file is opened read/write event if the main
** database is read-only.  The temporary file is deleted when the
** cursor is closed.
*/
case OP_OpenTemp: {
  int busy = 0;
  int i = pOp->p1;
  Cursor *pCx;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nCursor ){
    int j;
    p->aCsr = sqliteRealloc( p->aCsr, (i+1)*sizeof(Cursor) );
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
................................................................................
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  pCx = &p->aCsr[i];
  memset(pCx, 0, sizeof(*pCx));
  rc = sqliteBtreeOpen(0, 0, 100, &pCx->pBt);
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeOpenCursor(pCx->pBt, 2, &pCx->pCursor);
  }
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeBeginTrans(pCx->pBt);
  }
  break;
}

................................................................................
case OP_MoveTo: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
    int res;
    if( aStack[tos].flags & STK_Int ){
      sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                     (char*)&aStack[tos].i, &res);
      p->aCsr[i].lastRecno = aStack[tos].i;
      p->aCsr[i].recnoIsValid = 1;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      pBex->Fetch(p->aCsr[i].pCursor, aStack[tos].n, 
                     zStack[tos], &res);
      p->aCsr[i].recnoIsValid = 0;
    }
    p->nFetch++;
  }
  POPSTACK;
  break;
}
................................................................................
  int i = pOp->p1;
  int tos = p->tos;
  int alreadyExists = 0;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor ){
    int res, rx;
    if( aStack[tos].flags & STK_Int ){
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(int), 
                                    (char*)&aStack[tos].i, &res);
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor,aStack[tos].n, 
                                     zStack[tos], &res);
    }
    alreadyExists = rx==SQLITE_OK && res==0;
  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;
................................................................................
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    int res, rx, cnt;
    cnt = 0;
    do{
      v = sqliteRandomInteger();
      rx = sqliteBtreeMoveTo(p->aCsr[i].pCursor, sizeof(v), &v, &res);
      cnt++;
    }while( cnt<10 && rx==SQLITE_OK && res==0 );
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].i = v;
  aStack[p->tos].flags = STK_Int;
................................................................................
      if( Stringify(p, nos) ) goto no_mem;
      nKey = aStack[nos].n;
      zKey = zStack[nos];
    }else{
      nKey = sizeof(int);
      zKey = (char*)&aStack[nos].i;
    }
    rc = sqliteBtreeInsert(p->aCsr[i].pCursor, nKey, zKey,
                        aStack[tos].n, zStack[tos]);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  POPSTACK;
  break;
}

/* Opcode: Delete P1 * *
................................................................................
**
** The top of the stack is a key.  Remove this key and its data
** from database file P1.  Then pop the stack to discard the key.
*/
case OP_Delete: {
  int tos = p->tos;
  int i = pOp->p1;

  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    char *zKey;
    int nKey;
    if( aStack[tos].flags & STK_Int ){
      nKey = sizeof(int);
      zKey = (char*)&aStack[tos].i;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      nKey = aStack[tos].n;
      zKey = zStack[tos];
    }
    rc = sqliteBtreeDelete(p->aCsr[i].pCursor, nKey, zKey);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  POPSTACK;
  break;
}

/* Opcode: KeyAsData P1 P2 *
**
................................................................................
** "Concat 1 0 0") if it needs to persist longer than that.
**
** If the KeyAsData opcode has previously executed on this cursor,
** then the field might be extracted from the key rather than the
** data.
*/
case OP_Column: {
  int *pAddr;
  int amt, offset, nCol, payloadSize;
  int aHdr[10];
  const int mxHdr = sizeof(aHdr)/sizeof(aHdr[0]);
  int i = pOp->p1;
  int p2 = pOp->p2;
  int tos = ++p->tos;
  BtCursor *pCrsr;
  char *z;

  VERIFY( if( NeedStack(p, tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int (*xSize)(BtCursor*, int*);
    int (*xRead)(BtCursor*, int, int, void*);

    /* Use different access functions depending on whether the information
    ** is coming from the key or the data of the record.
    */
    if( p->aCsr[i].keyAsData ){
      xSize = sqliteBtreeKeySize;
      xRead = sqliteBtreeKey;
................................................................................
    */
    (*xSize)(pCrsr, &payloadSize);
    if( payloadSize < sizeof(int)*(p2+1) ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    if( p2+1<mxHdr ){
      (*xRead)(pCrsr, 0, sizeof(aHdr[0])*(p2+2), aHdr);
      nCol = aHdr[0];
      offset = aHdr[p2];
      if( p2 == nCol-1 ){
        amt = payloadSize - offset;
      }else{
        amt = aHdr[p2+1] - offset;
      }
    }else{
      sqliteBtreeData(pCrsr, 0, sizeof(int), &nCol);
      nCol /= sizeof(int);
      if( p2 == nCol-1 ){
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int), &offset);
        amt = payloadSize - offset;
      }else{
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int)*2, aHdr);
        offset = aHdr[0];
        amt = aHdr[1] - offset;
      }
    }
    if( payloadSize < nCol || amt<0 || offset<0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
................................................................................

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int v;
    if( p->aCsr[i].recnoIsValid ){
      v = p->aCsr[i].lastRecno;
    }else{
      sqliteBtreeKey(pCrsr, 0, sizeof(int), &v);
    }
    aStack[tos].i = v;
    aStack[tos].flags = STK_Int;
  }
  break;
}

................................................................................
    if( Stringify(p, tos) ) goto no_mem;
    pCrsr->nKey = aStack[tos].n;
    pCrsr->zKey = sqliteMalloc( 2*(pCrsr->nKey + 1) );
    if( pCrsr->zKey==0 ) goto no_mem;
    pCrsr->zBuf = &pCrsr->zKey[pCrsr->nKey+1];
    strncpy(pCrsr->zKey, zStack[tos], aStack[tos].n);
    pCrsr->zKey[aStack[tos].n] = 0;
    rx = sqliteBtreeMoveTo(pCrsr->pCursor, aStack[tos].n, zStack[tos], &res);
    pCrsr->atFirst = rx==SQLITE_OK && res>0;
    pCrsr->recnoIsValid = 0;
  }
  POPSTACK;
  break;
}

................................................................................
** record numbers for the given key, this opcode pushes nothing onto the
** stack but instead jumps to instruction P2.
*/
case OP_NextIdx: {
  int i = pOp->p1;
  int tos = ++p->tos;
  Cursor *pCrsr;
  BtCursr *pCur;
  int rx, res, size;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[tos] = 0;
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = &p->aCsr[i])->pCursor)!=0 ){
    pCur = pCrsr->pCursor;
    rx = sqliteBtreeNext(pCur, &res);
    if( rx!=SQLITE_OK ) goto abort_due_to_error;
    sqliteBtreeKeySzie(pCur, &size);
    if( res>0 || size!=pCrsr->nKey+sizeof(int) ||
      sqliteBtreeKey(pCur, 0, pCrsr->nKey, pCrsr->zBuf)!=pCrsr->nKey ||
      strncmp(pCrsr->zKey, pCrsr->zBuf, pCrsr->nKey)!=0
    ){
      pc = pOp->p2 - 1;
      POPSTACK;
    }else{
      int recno;
      sqliteBtreeKey(pCur, pCrsr->nKey, sizeof(int), &recno);
      p->aCsr[i].lastRecno = aStack[tos].i = recno;
      p->aCsr[i].recnoIsValid = 1;
      aStack[tos].flags = STK_Int;
    }
  }
  break;
}
................................................................................
*/
case OP_PutIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    sqliteBtreePut(pCrsr, aStack[tos].n, zStack[tos], 0, "");
  }
  POPSTACK;
  break;
}

/* Opcode: DeleteIdx P1 * *
**
................................................................................
case OP_DeleteIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int rx, res;
    rx = sqliteBtreeMoveTo(pCrsr, aStack[tos].n, zStack[tos], &res);
    if( rx==SQLITE_OK && res==0 ){
      sqliteBtreeDelete(pCrsr);
    }
  }
  POPSTACK;
  break;
}
................................................................................

/* Opcode: Destroy P1 * *
**
** Delete an entire database table or index whose root page in the database
** file is given by P1.
*/
case OP_Destroy: {
  sqliteBtreeDropTable(pBe, pOp->p1);
  break;
}

/* Opcode: Reorganize P1 * *
**
** Compress, optimize, and tidy up table or index whose root page in the
** database file is P1.
................................................................................
  /* If we reach end-of-file, or if anything goes wrong, jump here.
  ** This code will cause a jump to P2 */
fileread_jump:
  pc = pOp->p2 - 1;
  break;
}

/* Opcode: FileField P1 * *
**
** Push onto the stack the P1-th field of the most recently read line
** from the input file.
*/
case OP_FileField: {
  int i = pOp->p1;
  char *z;
  VERIFY( if( NeedStack(p, p->tos+1) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nField && ) p->azField ){
    z = p->azField[i];
  }else{
    z = 0;
................................................................................
    }
#endif
  }

cleanup:
  Cleanup(p);
  if( rc!=SQLITE_OK && (db->flags & SQLITE_InTrans)!=0 ){
    sqliteBtreeRollback(pBe);
    sqliteRollbackInternalChanges(db);
    db->flags &= ~SQLITE_InTrans;
  }
  return rc;

  /* Jump to here if a malloc() fails.  It's hard to get a malloc()
  ** to fail on a modern VM computer, so this code is untested.
................................................................................
  sqliteSetString(pzErrMsg, "out or memory", 0);
  rc = SQLITE_NOMEM;
  goto cleanup;

  /* Jump to here for any other kind of fatal error.  The "rc" variable
  ** should hold the error number.
  */
abort_due_to_err:
  sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
  goto cleanup;

  /* Jump to here if a operator is encountered that requires more stack
  ** operands than are currently available on the stack.
  */
not_enough_stack:







|







 







|







 







|







 







|



|
|
|
|
|
|
|
|
|
|







 







|

<







 







|







 







|










|







 







|







 







|
|







 







<







 







|







 







|
|




|
<







 







|
|


|
|







 







|







 







|
|
<







 







>












|
|







 







<












|







 







|








|


|


|







 







|







 







|







 







|




|



|








|







 







|







 







|







 







|







 







|




|







 







|







 







|







37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
...
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
...
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
....
1034
1035
1036
1037
1038
1039
1040
1041
1042

1043
1044
1045
1046
1047
1048
1049
....
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
....
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
....
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
....
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
....
2024
2025
2026
2027
2028
2029
2030

2031
2032
2033
2034
2035
2036
2037
....
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
....
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098

2099
2100
2101
2102
2103
2104
2105
....
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
....
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
....
2226
2227
2228
2229
2230
2231
2232
2233
2234

2235
2236
2237
2238
2239
2240
2241
....
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
....
2294
2295
2296
2297
2298
2299
2300

2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
....
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
....
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
....
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
....
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
....
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
....
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
....
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
....
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
....
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
....
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
** inplicit conversion from one 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.61 2001/09/13 14:46:11 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>

/*
** SQL is translated into a sequence of instructions to be
** executed by a virtual machine.  Each instruction is an instance
................................................................................
};

/*
** An instance of the virtual machine
*/
struct Vdbe {
  sqlite *db;         /* The whole database */
  Btree *pBt;         /* Opaque context structure used by DB backend */
  FILE *trace;        /* Write an execution trace here, if not NULL */
  int nOp;            /* Number of instructions in the program */
  int nOpAlloc;       /* Number of slots allocated for aOp[] */
  Op *aOp;            /* Space to hold the virtual machine's program */
  int nLabel;         /* Number of labels used */
  int nLabelAlloc;    /* Number of slots allocated in aLabel[] */
  int *aLabel;        /* Space to hold the labels */
................................................................................
/*
** Create a new virtual database engine.
*/
Vdbe *sqliteVdbeCreate(sqlite *db){
  Vdbe *p;
  p = sqliteMalloc( sizeof(Vdbe) );
  if( p==0 ) return 0;
  p->pBt = db->pBe;
  p->db = db;
  return p;
}

/*
** Turn tracing on or off
*/
................................................................................
  "Recno",             "FullKey",           "Rewind",            "Next",
  "Destroy",           "CreateIndex",       "CreateTable",       "Reorganize",
  "BeginIdx",          "NextIdx",           "PutIdx",            "DeleteIdx",
  "MemLoad",           "MemStore",          "ListOpen",          "ListWrite",
  "ListRewind",        "ListRead",          "ListClose",         "SortOpen",
  "SortPut",           "SortMakeRec",       "SortMakeKey",       "Sort",
  "SortNext",          "SortKey",           "SortCallback",      "SortClose",
  "FileOpen",          "FileRead",          "FileColumn",        "FileClose",
  "AggReset",          "AggFocus",          "AggIncr",           "AggNext",
  "AggSet",            "AggGet",            "SetInsert",         "SetFound",
  "SetNotFound",       "SetClear",          "MakeRecord",        "MakeKey",
  "MakeIdxKey",        "Goto",              "If",                "Halt",
  "ColumnCount",       "ColumnName",        "Callback",          "Integer",
  "String",            "Null",              "Pop",               "Dup",
  "Pull",              "Add",               "AddImm",            "Subtract",
  "Multiply",          "Divide",            "Min",               "Max",
  "Like",              "Glob",              "Eq",                "Ne",
  "Lt",                "Le",                "Gt",                "Ge",
  "IsNull",            "NotNull",           "Negative",          "And",
  "Or",                "Not",               "Concat",            "Noop",
  "Strlen",            "Substr",          
};

/*
** Given the name of an opcode, return its number.  Return 0 if
** there is no match.
**
** This routine is used for testing and debugging.
................................................................................
  char **pzErrMsg,           /* Error msg written here */
  void *pBusyArg,            /* 1st argument to the busy callback */
  int (*xBusy)(void*,const char*,int)  /* Called when a file is busy */
){
  int pc;                    /* The program counter */
  Op *pOp;                   /* Current operation */
  int rc;                    /* Value to return */
  Btree *pBt = p->pBt;       /* The backend driver */
  sqlite *db = p->db;        /* The database */

  char **zStack;             /* Text stack */
  Stack *aStack;             /* Additional stack information */
  char zBuf[100];            /* Space to sprintf() an integer */


  /* No instruction ever pushes more than a single element onto the
  ** stack.  And the stack never grows on successive executions of the
................................................................................
      memcpy(&zNewKey[j], zStack[i], aStack[i].n-1);
      j += aStack[i].n-1;
    }
    if( i<p->tos ) zNewKey[j++] = '\t';
  }
  zNewKey[j++] = 0;
  Integerify(p, p->tos-nField);
  memcpy(&zNewKey[j], &aStack[p->tos-nField].i, sizeof(int));
  PopStack(p, nField+1);
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].n = nByte;
  aStack[p->tos].flags = STK_Str|STK_Dyn;
  zStack[p->tos] = zNewKey;
  break;
................................................................................
** opcode is encountered or whenever there is an execution error that causes
** a script to abort.  
**
** A transaction must be started before any changes can be made to the
** database.
*/
case OP_Transaction: {
  rc = sqliteBtreeBeginTrans(pBt);
  break;
}

/* Opcode: Commit * * *
**
** Cause all modifications to the database that have been made since the
** last Transaction to actually take effect.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Commit: {
  rc = sqliteBtreeCommit(pBt);
  if( rc==SQLITE_OK ){
    sqliteCommitInternalChanges(db);
  }else{
    sqliteRollbackInternalChanges(db);
  }
  break;
}
................................................................................
**
** Cause all modifications to the database that have been made since the
** last Transaction to be undone. The database is restored to its state
** before the Transaction opcode was executed.  No additional modifications
** are allowed until another transaction is started.
*/
case OP_Rollback: {
  rc = sqliteBtreeRollback(pBt);
  sqliteRollbackInternalChanges(db);
  break;
}

/* Opcode: Open P1 P2 P3
**
** Open a new cursor for the database table whose root page is
................................................................................
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
    for(j=p->nCursor; j<=i; j++) p->aCsr[j].pCursor = 0;
    p->nCursor = i+1;
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  memset(&p->aCsr[i], 0, sizeof(Cursor));
  do{
    rc = sqliteBtreeCursor(pBt, pOp->p2, &p->aCsr[i].pCursor);
    switch( rc ){
      case SQLITE_BUSY: {
        if( xBusy==0 || (*xBusy)(pBusyArg, pOp->p3, ++busy)==0 ){
          sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
          busy = 0;
        }
        break;
................................................................................
**
** Open a new cursor that points to a table in a temporary database
** file.  The temporary file is opened read/write event if the main
** database is read-only.  The temporary file is deleted when the
** cursor is closed.
*/
case OP_OpenTemp: {

  int i = pOp->p1;
  Cursor *pCx;
  VERIFY( if( i<0 ) goto bad_instruction; )
  if( i>=p->nCursor ){
    int j;
    p->aCsr = sqliteRealloc( p->aCsr, (i+1)*sizeof(Cursor) );
    if( p->aCsr==0 ){ p->nCursor = 0; goto no_mem; }
................................................................................
  }else if( p->aCsr[i].pCursor ){
    sqliteBtreeCloseCursor(p->aCsr[i].pCursor);
  }
  pCx = &p->aCsr[i];
  memset(pCx, 0, sizeof(*pCx));
  rc = sqliteBtreeOpen(0, 0, 100, &pCx->pBt);
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeCursor(pCx->pBt, 2, &pCx->pCursor);
  }
  if( rc==SQLITE_OK ){
    rc = sqliteBtreeBeginTrans(pCx->pBt);
  }
  break;
}

................................................................................
case OP_MoveTo: {
  int i = pOp->p1;
  int tos = p->tos;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( i>=0 && i<p->nCursor && p->aCsr[i].pCursor ){
    int res;
    if( aStack[tos].flags & STK_Int ){
      sqliteBtreeMoveto(p->aCsr[i].pCursor, 
          (char*)&aStack[tos].i, sizeof(int), &res);
      p->aCsr[i].lastRecno = aStack[tos].i;
      p->aCsr[i].recnoIsValid = 1;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      sqliteBtreeMoveto(p->aCsr[i].pCursor, zStack[tos], aStack[tos].n, &res);

      p->aCsr[i].recnoIsValid = 0;
    }
    p->nFetch++;
  }
  POPSTACK;
  break;
}
................................................................................
  int i = pOp->p1;
  int tos = p->tos;
  int alreadyExists = 0;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor ){
    int res, rx;
    if( aStack[tos].flags & STK_Int ){
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, 
           (char*)&aStack[tos].i, sizeof(int), &res);
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor,
         zStack[tos], aStack[tos].n, &res);
    }
    alreadyExists = rx==SQLITE_OK && res==0;
  }
  if( pOp->opcode==OP_Found ){
    if( alreadyExists ) pc = pOp->p2 - 1;
  }else{
    if( !alreadyExists ) pc = pOp->p2 - 1;
................................................................................
  if( VERIFY( i<0 || i>=p->nCursor || ) p->aCsr[i].pCursor==0 ){
    v = 0;
  }else{
    int res, rx, cnt;
    cnt = 0;
    do{
      v = sqliteRandomInteger();
      rx = sqliteBtreeMoveto(p->aCsr[i].pCursor, &v, sizeof(v), &res);
      cnt++;
    }while( cnt<10 && rx==SQLITE_OK && res==0 );
  }
  VERIFY( NeedStack(p, p->tos+1); )
  p->tos++;
  aStack[p->tos].i = v;
  aStack[p->tos].flags = STK_Int;
................................................................................
      if( Stringify(p, nos) ) goto no_mem;
      nKey = aStack[nos].n;
      zKey = zStack[nos];
    }else{
      nKey = sizeof(int);
      zKey = (char*)&aStack[nos].i;
    }
    rc = sqliteBtreeInsert(p->aCsr[i].pCursor, zKey, nKey,
                        zStack[tos], aStack[tos].n);

  }
  POPSTACK;
  POPSTACK;
  break;
}

/* Opcode: Delete P1 * *
................................................................................
**
** The top of the stack is a key.  Remove this key and its data
** from database file P1.  Then pop the stack to discard the key.
*/
case OP_Delete: {
  int tos = p->tos;
  int i = pOp->p1;
  int res;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) p->aCsr[i].pCursor!=0 ){
    char *zKey;
    int nKey;
    if( aStack[tos].flags & STK_Int ){
      nKey = sizeof(int);
      zKey = (char*)&aStack[tos].i;
    }else{
      if( Stringify(p, tos) ) goto no_mem;
      nKey = aStack[tos].n;
      zKey = zStack[tos];
    }
    rc = sqliteBtreeMoveto(p->aCsr[i].pCursor, zKey, nKey, &res);
    rc = sqliteBtreeDelete(p->aCsr[i].pCursor);
  }
  POPSTACK;
  break;
}

/* Opcode: KeyAsData P1 P2 *
**
................................................................................
** "Concat 1 0 0") if it needs to persist longer than that.
**
** If the KeyAsData opcode has previously executed on this cursor,
** then the field might be extracted from the key rather than the
** data.
*/
case OP_Column: {

  int amt, offset, nCol, payloadSize;
  int aHdr[10];
  const int mxHdr = sizeof(aHdr)/sizeof(aHdr[0]);
  int i = pOp->p1;
  int p2 = pOp->p2;
  int tos = ++p->tos;
  BtCursor *pCrsr;
  char *z;

  VERIFY( if( NeedStack(p, tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int (*xSize)(BtCursor*, int*);
    int (*xRead)(BtCursor*, int, int, char*);

    /* Use different access functions depending on whether the information
    ** is coming from the key or the data of the record.
    */
    if( p->aCsr[i].keyAsData ){
      xSize = sqliteBtreeKeySize;
      xRead = sqliteBtreeKey;
................................................................................
    */
    (*xSize)(pCrsr, &payloadSize);
    if( payloadSize < sizeof(int)*(p2+1) ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
    }
    if( p2+1<mxHdr ){
      (*xRead)(pCrsr, 0, sizeof(aHdr[0])*(p2+2), (char*)aHdr);
      nCol = aHdr[0];
      offset = aHdr[p2];
      if( p2 == nCol-1 ){
        amt = payloadSize - offset;
      }else{
        amt = aHdr[p2+1] - offset;
      }
    }else{
      sqliteBtreeData(pCrsr, 0, sizeof(int), (char*)&nCol);
      nCol /= sizeof(int);
      if( p2 == nCol-1 ){
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int), (char*)&offset);
        amt = payloadSize - offset;
      }else{
        (*xRead)(pCrsr, sizeof(int)*p2, sizeof(int)*2, (char*)aHdr);
        offset = aHdr[0];
        amt = aHdr[1] - offset;
      }
    }
    if( payloadSize < nCol || amt<0 || offset<0 ){
      rc = SQLITE_CORRUPT;
      goto abort_due_to_error;
................................................................................

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int v;
    if( p->aCsr[i].recnoIsValid ){
      v = p->aCsr[i].lastRecno;
    }else{
      sqliteBtreeKey(pCrsr, 0, sizeof(int), (char*)&v);
    }
    aStack[tos].i = v;
    aStack[tos].flags = STK_Int;
  }
  break;
}

................................................................................
    if( Stringify(p, tos) ) goto no_mem;
    pCrsr->nKey = aStack[tos].n;
    pCrsr->zKey = sqliteMalloc( 2*(pCrsr->nKey + 1) );
    if( pCrsr->zKey==0 ) goto no_mem;
    pCrsr->zBuf = &pCrsr->zKey[pCrsr->nKey+1];
    strncpy(pCrsr->zKey, zStack[tos], aStack[tos].n);
    pCrsr->zKey[aStack[tos].n] = 0;
    rx = sqliteBtreeMoveto(pCrsr->pCursor, zStack[tos], aStack[tos].n, &res);
    pCrsr->atFirst = rx==SQLITE_OK && res>0;
    pCrsr->recnoIsValid = 0;
  }
  POPSTACK;
  break;
}

................................................................................
** record numbers for the given key, this opcode pushes nothing onto the
** stack but instead jumps to instruction P2.
*/
case OP_NextIdx: {
  int i = pOp->p1;
  int tos = ++p->tos;
  Cursor *pCrsr;
  BtCursor *pCur;
  int rx, res, size;

  VERIFY( if( NeedStack(p, p->tos) ) goto no_mem; )
  zStack[tos] = 0;
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = &p->aCsr[i])->pCursor!=0 ){
    pCur = pCrsr->pCursor;
    rx = sqliteBtreeNext(pCur, &res);
    if( rx!=SQLITE_OK ) goto abort_due_to_error;
    sqliteBtreeKeySize(pCur, &size);
    if( res>0 || size!=pCrsr->nKey+sizeof(int) ||
      sqliteBtreeKey(pCur, 0, pCrsr->nKey, pCrsr->zBuf)!=pCrsr->nKey ||
      strncmp(pCrsr->zKey, pCrsr->zBuf, pCrsr->nKey)!=0
    ){
      pc = pOp->p2 - 1;
      POPSTACK;
    }else{
      int recno;
      sqliteBtreeKey(pCur, pCrsr->nKey, sizeof(int), (char*)&recno);
      p->aCsr[i].lastRecno = aStack[tos].i = recno;
      p->aCsr[i].recnoIsValid = 1;
      aStack[tos].flags = STK_Int;
    }
  }
  break;
}
................................................................................
*/
case OP_PutIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    sqliteBtreeInsert(pCrsr, zStack[tos], aStack[tos].n, "", 0);
  }
  POPSTACK;
  break;
}

/* Opcode: DeleteIdx P1 * *
**
................................................................................
case OP_DeleteIdx: {
  int i = pOp->p1;
  int tos = p->tos;
  BtCursor *pCrsr;
  VERIFY( if( tos<0 ) goto not_enough_stack; )
  if( VERIFY( i>=0 && i<p->nCursor && ) (pCrsr = p->aCsr[i].pCursor)!=0 ){
    int rx, res;
    rx = sqliteBtreeMoveto(pCrsr, zStack[tos], aStack[tos].n, &res);
    if( rx==SQLITE_OK && res==0 ){
      sqliteBtreeDelete(pCrsr);
    }
  }
  POPSTACK;
  break;
}
................................................................................

/* Opcode: Destroy P1 * *
**
** Delete an entire database table or index whose root page in the database
** file is given by P1.
*/
case OP_Destroy: {
  sqliteBtreeDropTable(pBt, pOp->p1);
  break;
}

/* Opcode: Reorganize P1 * *
**
** Compress, optimize, and tidy up table or index whose root page in the
** database file is P1.
................................................................................
  /* If we reach end-of-file, or if anything goes wrong, jump here.
  ** This code will cause a jump to P2 */
fileread_jump:
  pc = pOp->p2 - 1;
  break;
}

/* Opcode: FileColumn P1 * *
**
** Push onto the stack the P1-th field of the most recently read line
** from the input file.
*/
case OP_FileColumn: {
  int i = pOp->p1;
  char *z;
  VERIFY( if( NeedStack(p, p->tos+1) ) goto no_mem; )
  if( VERIFY( i>=0 && i<p->nField && ) p->azField ){
    z = p->azField[i];
  }else{
    z = 0;
................................................................................
    }
#endif
  }

cleanup:
  Cleanup(p);
  if( rc!=SQLITE_OK && (db->flags & SQLITE_InTrans)!=0 ){
    sqliteBtreeRollback(pBt);
    sqliteRollbackInternalChanges(db);
    db->flags &= ~SQLITE_InTrans;
  }
  return rc;

  /* Jump to here if a malloc() fails.  It's hard to get a malloc()
  ** to fail on a modern VM computer, so this code is untested.
................................................................................
  sqliteSetString(pzErrMsg, "out or memory", 0);
  rc = SQLITE_NOMEM;
  goto cleanup;

  /* Jump to here for any other kind of fatal error.  The "rc" variable
  ** should hold the error number.
  */
abort_due_to_error:
  sqliteSetString(pzErrMsg, sqliteErrStr(rc), 0);
  goto cleanup;

  /* Jump to here if a operator is encountered that requires more stack
  ** operands than are currently available on the stack.
  */
not_enough_stack:

Changes to src/vdbe.h.

23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.19 2001/09/13 13:46:57 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
#define OP_SortNext           41
#define OP_SortKey            42
#define OP_SortCallback       43
#define OP_SortClose          44

#define OP_FileOpen           45
#define OP_FileRead           46
#define OP_FileField          47
#define OP_FileClose          48

#define OP_AggReset           49
#define OP_AggFocus           50
#define OP_AggIncr            51
#define OP_AggNext            52
#define OP_AggSet             53







|







 







|







23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
*************************************************************************
** Header file for the Virtual DataBase Engine (VDBE)
**
** This header defines the interface to the virtual database engine
** or VDBE.  The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
** $Id: vdbe.h,v 1.20 2001/09/13 14:46:11 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
#include <stdio.h>

/*
** A single VDBE is an opaque structure named "Vdbe".  Only routines
................................................................................
#define OP_SortNext           41
#define OP_SortKey            42
#define OP_SortCallback       43
#define OP_SortClose          44

#define OP_FileOpen           45
#define OP_FileRead           46
#define OP_FileColumn         47
#define OP_FileClose          48

#define OP_AggReset           49
#define OP_AggFocus           50
#define OP_AggIncr            51
#define OP_AggNext            52
#define OP_AggSet             53

Changes to src/where.c.

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
...
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
...
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
...
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.16 2001/09/13 13:46:57 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................

  /* Open all tables in the pTabList and all indices in aIdx[].
  */
  for(i=0; i<pTabList->nId; i++){
    sqliteVdbeAddOp(v, OP_Open, base+i, pTabList->a[i].pTab->tnum,
         pTabList->a[i].pTab->zName, 0);
    if( i<ARRAYSIZE(aIdx) && aIdx[i]!=0 ){
      sqliteVdbeAddOp(v, OP_Open, base+pTabList->nId+i, aIdx[i]->tnum
          aIdx[i]->zName, 0);
    }
  }
  memcpy(pWInfo->aIdx, aIdx, sizeof(aIdx));

  /* Generate the code to do the search
  */
................................................................................
          break;
        }
      }
      sqliteVdbeAddOp(v, OP_AddImm, 0, 0, 0, 0);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }else if( pIdx==0 ){
      /* Case 2:  There was no usable index.  We must do a complete
      ** scan of the table.
      */
      cont = sqliteVdbeMakeLabel(v);
................................................................................
      }
      sqliteVdbeAddOp(v, OP_MakeKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_BeginIdx, base+pTabList->nId+i, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_NextIdx, base+pTabList->nId+i, brk, 0, cont);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }
    loopMask |= 1<<idx;

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
................................................................................
    */
    for(j=0; j<nExpr; j++){
      if( aExpr[j].p==0 ) continue;
      if( (aExpr[j].prereqRight & loopMask)!=aExpr[j].prereqRight ) continue;
      if( (aExpr[j].prereqLeft & loopMask)!=aExpr[j].prereqLeft ) continue;
      if( haveKey ){
        haveKey = 0;
        sqliteVdbeAddOp(v, OP_Fetch, base+idx, 0, 0, 0);
      }
      sqliteExprIfFalse(pParse, aExpr[j].p, cont);
      aExpr[j].p = 0;
    }
    brk = cont;
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveKey ){
    sqliteVdbeAddOp(v, OP_Key, base, 0, 0, 0);
  }
  sqliteFree(aOrder);
  return pWInfo;
}

/*
** Generate the end of the WHERE loop.







|







 







|







 







|







 







|







 







|








|







21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
...
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
...
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
...
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
...
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
**   http://www.hwaci.com/drh/
**
*************************************************************************
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  Also found here are subroutines
** to generate VDBE code to evaluate expressions.
**
** $Id: where.c,v 1.17 2001/09/13 14:46:11 drh Exp $
*/
#include "sqliteInt.h"

/*
** The query generator uses an array of instances of this structure to
** help it analyze the subexpressions of the WHERE clause.  Each WHERE
** clause subexpression is separated from the others by an AND operator.
................................................................................

  /* Open all tables in the pTabList and all indices in aIdx[].
  */
  for(i=0; i<pTabList->nId; i++){
    sqliteVdbeAddOp(v, OP_Open, base+i, pTabList->a[i].pTab->tnum,
         pTabList->a[i].pTab->zName, 0);
    if( i<ARRAYSIZE(aIdx) && aIdx[i]!=0 ){
      sqliteVdbeAddOp(v, OP_Open, base+pTabList->nId+i, aIdx[i]->tnum,
          aIdx[i]->zName, 0);
    }
  }
  memcpy(pWInfo->aIdx, aIdx, sizeof(aIdx));

  /* Generate the code to do the search
  */
................................................................................
          break;
        }
      }
      sqliteVdbeAddOp(v, OP_AddImm, 0, 0, 0, 0);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }else if( pIdx==0 ){
      /* Case 2:  There was no usable index.  We must do a complete
      ** scan of the table.
      */
      cont = sqliteVdbeMakeLabel(v);
................................................................................
      }
      sqliteVdbeAddOp(v, OP_MakeKey, pIdx->nColumn, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_BeginIdx, base+pTabList->nId+i, 0, 0, 0);
      sqliteVdbeAddOp(v, OP_NextIdx, base+pTabList->nId+i, brk, 0, cont);
      if( i==pTabList->nId-1 && pushKey ){
        haveKey = 1;
      }else{
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0, 0, 0);
        haveKey = 0;
      }
    }
    loopMask |= 1<<idx;

    /* Insert code to test every subexpression that can be completely
    ** computed using the current set of tables.
................................................................................
    */
    for(j=0; j<nExpr; j++){
      if( aExpr[j].p==0 ) continue;
      if( (aExpr[j].prereqRight & loopMask)!=aExpr[j].prereqRight ) continue;
      if( (aExpr[j].prereqLeft & loopMask)!=aExpr[j].prereqLeft ) continue;
      if( haveKey ){
        haveKey = 0;
        sqliteVdbeAddOp(v, OP_MoveTo, base+idx, 0, 0, 0);
      }
      sqliteExprIfFalse(pParse, aExpr[j].p, cont);
      aExpr[j].p = 0;
    }
    brk = cont;
  }
  pWInfo->iContinue = cont;
  if( pushKey && !haveKey ){
    sqliteVdbeAddOp(v, OP_Recno, base, 0, 0, 0);
  }
  sqliteFree(aOrder);
  return pWInfo;
}

/*
** Generate the end of the WHERE loop.

Changes to test/btree2.test.

19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
284
285
286
287
288
289
290

291
292
293
294
295
296
297
298
299
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree2.test,v 1.4 2001/08/20 00:33:58 drh Exp $


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

if {[info commands btree_open]!=""} {

................................................................................
# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2
  200 3

} {
#  2000 5
  puts "**** N=$N L=$L ****"
  set hash [md5file test2.bt]
  do_test btree2-$testno.1 [subst -nocommands {
    set ::c2 [btree_cursor $::b 2]
    set ::c3 [btree_cursor $::b 3]
    set ::c4 [btree_cursor $::b 4]
    set ::c5 [btree_cursor $::b 5]







|







 







>

<







19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
...
284
285
286
287
288
289
290
291
292

293
294
295
296
297
298
299
#   drh@hwaci.com
#   http://www.hwaci.com/drh/
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree2.test,v 1.5 2001/09/13 14:46:11 drh Exp $


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

if {[info commands btree_open]!=""} {

................................................................................
# Repeat this test sequence on database of various sizes
#
set testno 2
foreach {N L} {
  10 2
  50 2
  200 3
  2000 5
} {

  puts "**** N=$N L=$L ****"
  set hash [md5file test2.bt]
  do_test btree2-$testno.1 [subst -nocommands {
    set ::c2 [btree_cursor $::b 2]
    set ::c3 [btree_cursor $::b 3]
    set ::c4 [btree_cursor $::b 4]
    set ::c5 [btree_cursor $::b 5]