SQLite

Check-in [e963bed0fe]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Remove the rowhash object from the code. Rowset now fills its role. (CVS 6535)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e963bed0fe3ce5fa32f04b930e5ed0956dc2aa47
User & Date: drh 2009-04-22 02:15:48.000
Context
2009-04-22
15:32
Change the OP_Rowid opcode so that a deferred OP_Seek is pending, it simply pulls the rowid from the deferred seek target and does not actually move the cursor or do a seek. Other where.c cleanups. (CVS 6536) (check-in: 1c508a9982 user: drh tags: trunk)
02:15
Remove the rowhash object from the code. Rowset now fills its role. (CVS 6535) (check-in: e963bed0fe user: drh tags: trunk)
00:47
Extend the Rowset object to contain all the capabilities of Rowhash in addition to its legacy capabilities. Use Rowset to replace Rowhash. In addition to requiring less code, This removes the 2^32 result row limitation, uses less memory, and gives better bounds on worst-case performance. The Rowhash implementation has yet to be removed. (CVS 6534) (check-in: b101cf70b7 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to Makefile.in.
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowhash.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#







|







168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
        delete.lo expr.lo fault.lo func.lo global.lo \
        hash.lo journal.lo insert.lo legacy.lo loadext.lo \
        main.lo malloc.lo mem0.lo mem1.lo mem2.lo mem3.lo mem5.lo \
        memjournal.lo \
        mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \
        notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
        pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \
        random.lo resolve.lo rowset.lo select.lo status.lo \
        table.lo tokenize.lo trigger.lo update.lo \
        util.lo vacuum.lo \
        vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \
        walker.lo where.lo utf.lo vtab.lo

# Object files for the amalgamation.
#
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \







<







245
246
247
248
249
250
251

252
253
254
255
256
257
258
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \

  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c

rowhash.lo:	$(TOP)/src/rowhash.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowhash.c

rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)







<
<
<







667
668
669
670
671
672
673



674
675
676
677
678
679
680

random.lo:	$(TOP)/src/random.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/random.c

resolve.lo:	$(TOP)/src/resolve.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c




rowset.lo:	$(TOP)/src/rowset.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c

select.lo:	$(TOP)/src/select.c $(HDR)
	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/select.c

status.lo:	$(TOP)/src/status.c $(HDR)
Changes to main.mk.
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowhash.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o










|







57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
         func.o global.o hash.o \
         icu.o insert.o journal.o legacy.o loadext.o \
         main.o malloc.o mem0.o mem1.o mem2.o mem3.o mem5.o \
         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \
         walker.o where.o utf.o vtab.o



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \
  $(TOP)/src/rowhash.c \
  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \







<







126
127
128
129
130
131
132

133
134
135
136
137
138
139
  $(TOP)/src/pcache.h \
  $(TOP)/src/pcache1.c \
  $(TOP)/src/pragma.c \
  $(TOP)/src/prepare.c \
  $(TOP)/src/printf.c \
  $(TOP)/src/random.c \
  $(TOP)/src/resolve.c \

  $(TOP)/src/rowset.c \
  $(TOP)/src/select.c \
  $(TOP)/src/status.c \
  $(TOP)/src/shell.c \
  $(TOP)/src/sqlite.h.in \
  $(TOP)/src/sqlite3ext.h \
  $(TOP)/src/sqliteInt.h \
Deleted src/rowhash.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
/*
** 2009 April 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
** This file contains the implementation of the RowHash data structure.
** A RowHash has the following properties:
**
**   *  A RowHash stores an unordered "bag" of 64-bit integer rowids.
**      There is no other content.
**
**   *  Primative operations are CREATE, INSERT, TEST, and DESTROY.
**      There is no way to remove individual elements from the RowHash
**      once they are inserted.
**
**   *  INSERT operations are batched.  TEST operation will ignore
**      elements in the current INSERT batch.  Only elements inserted
**      in prior batches will be seen by a TEST.
**
** The insert batch number is a parameter to the TEST primitive.  The
** hash table is rebuilt whenever the batch number increases.  TEST
** operations only look for INSERTs that occurred in prior batches.
**
** The caller is responsible for insuring that there are no duplicate
** INSERTs.
**
** $Id: rowhash.c,v 1.5 2009/04/22 00:47:01 drh Exp $
*/
#include "sqliteInt.h"

/*
** An upper bound on the size of heap allocations made by this module.
** Limiting the size of allocations helps to avoid memory fragmentation.
*/
#define ROWHASH_ALLOCATION 1024

/*
** If there are less than this number of elements in the RowHash, do not
** bother building a hash-table. Just do a linear search.
*/
#define ROWHASH_LINEAR_SEARCH_LIMIT 10

/*
** This value is what we want the average length of the collision hash
** chain to be.
*/
#define ROWHASH_COLLISION_LENGTH 3


/* Forward references to data structures. */
typedef struct RowHashElem RowHashElem;
typedef struct RowHashBlock RowHashBlock;
typedef union RowHashPtr RowHashPtr;
typedef struct RowHashPage RowHashPage;

/*
** Number of elements in the RowHashBlock.aElem[] array. This array is
** sized to make RowHashBlock very close to (without exceeding)
** ROWHASH_ALLOCATION bytes in size.
*/
#define ROWHASH_ELEM_PER_BLOCK (                                            \
    (ROWHASH_ALLOCATION - ROUND8(sizeof(struct RowHashBlockData))) /        \
    sizeof(RowHashElem)                                                     \
)

/*
** Number of pointers that fit into a single allocation of 
** ROWHASH_ALLOCATION bytes.
*/
#define ROWHASH_POINTER_PER_PAGE (ROWHASH_ALLOCATION/sizeof(RowHashPtr))

/*
** A page of pointers used to construct a hash table.
**
** The hash table is actually a tree composed of instances of this
** object.  Leaves of the tree use the a[].pElem pointer to point
** to RowHashElem entries.  Interior nodes of the tree use the
** a[].pPage element to point to subpages.
**
** The hash table is split into a tree in order to avoid having
** to make large memory allocations, since large allocations can
** result in unwanted memory fragmentation.
*/
struct RowHashPage {
  union RowHashPtr {
    RowHashPage *pPage;   /* Used by interior nodes.  Pointer to subtree. */
    RowHashElem *pElem;   /* Used by leaves.  Pointer to hash entry. */
  } a[ROWHASH_POINTER_PER_PAGE];
};

/*
** Each 64-bit integer in a RowHash is stored as an instance of
** this object.  
**
** Instances of this object are not allocated separately.  They are
** allocated in large blocks using the RowHashBlock object as a container.
*/
struct RowHashElem {
  i64 iVal;              /* The value being stored.  A rowid. */
  RowHashElem *pNext;    /* Next element with the same hash */
};

/*
** In order to avoid many small allocations of RowHashElem objects,
** multiple RowHashElem objects are allocated at once, as an instance
** of this object, and then used as needed.
**
** A single RowHash object will allocate one or more of these RowHashBlock
** objects.  As many are allocated as are needed to store all of the
** content.  All RowHashBlocks are kept on a linked list formed using
** RowHashBlock.data.pNext so that they can be freed when the RowHash
** is destroyed.
**
** The linked list of RowHashBlock objects also provides a way to sequentially
** scan all elements in the RowHash.  This sequential scan is used when
** rebuilding the hash table.  The hash table is rebuilt after every 
** batch of inserts.
*/
struct RowHashBlock {
  struct RowHashBlockData {
    RowHashBlock *pNext;      /* Next RowHashBlock object in list of them all */
  } data;
  RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK]; /* Available RowHashElem objects */
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  unsigned int nEntry;    /* Number of used entries over all RowHashBlocks */
  int iBatch;             /* The current insert batch number */
  u16 nUsed;              /* Number of used entries in first RowHashBlock */
  u8 nHeight;             /* Height of tree of hash pages */
  u8 nLinearLimit;        /* Linear search limit (used if pHash==0) */
  int nBucket;            /* Number of buckets in hash table */
  RowHashPage *pHash;     /* Pointer to root of hash table tree */
  RowHashBlock *pBlock;   /* Linked list of RowHashBlocks */
  sqlite3 *db;            /* Associated database connection */
};


/*
** Allocate a hash table tree of height nHeight with *pnLeaf leaf pages. 
** Set *pp to point to the root of the tree.  If the maximum number of leaf 
** pages in a tree of height nHeight is less than *pnLeaf, allocate only
** that part of the tree that is necessary to account for all leaves.
**
** Before returning, subtract the number of leaves in the tree allocated
** from *pnLeaf.
**
** This routine returns SQLITE_NOMEM if a malloc() fails, or SQLITE_OK
** otherwise.
*/
static int allocHashTable(RowHashPage **pp, int nHeight, int *pnLeaf){
  RowHashPage *p = (RowHashPage *)sqlite3MallocZero(sizeof(*p));
  if( !p ){
    return SQLITE_NOMEM;
  }
  *pp = p;
  if( nHeight==0 ){
    (*pnLeaf)--;
  }else{
    int ii;
    for(ii=0; ii<ROWHASH_POINTER_PER_PAGE && *pnLeaf>0; ii++){
      if( allocHashTable(&p->a[ii].pPage, nHeight-1, pnLeaf) ){
        return SQLITE_NOMEM;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Delete the hash table tree of height nHeight passed as the first argument.
*/
static void deleteHashTable(RowHashPage *p, int nHeight){
  if( p ){
    if( nHeight>0 ){
      int ii;
      for(ii=0; ii<ROWHASH_POINTER_PER_PAGE; ii++){
        deleteHashTable(p->a[ii].pPage, nHeight-1);
      }
    }
    sqlite3_free(p);
  }
}

/*
** Find the hash-bucket associated with value iVal. Return a pointer to it.
**
** By "hash-bucket", we mean the RowHashPage.a[].pElem pointer that
** corresponds to a particular hash entry.
*/
static RowHashElem **findHashBucket(RowHash *pRowHash, i64 iVal){
  int aOffset[16];
  int n;
  RowHashPage *pPage = pRowHash->pHash;
  int h = (((u64)iVal) % pRowHash->nBucket);

  assert( pRowHash->nHeight < sizeof(aOffset)/sizeof(aOffset[0]) );
  for(n=0; n<pRowHash->nHeight; n++){
    int h1 = h / ROWHASH_POINTER_PER_PAGE;
    aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE);
    h = h1;
  }
  aOffset[n] = h;
  for(n=pRowHash->nHeight; n>0; n--){
    pPage = pPage->a[aOffset[n]].pPage;
  }
  return &pPage->a[aOffset[0]].pElem;
}

/*
** Build a new hash table tree in p->pHash.  The new hash table should
** contain all p->nEntry entries in the p->pBlock list.  If there
** existed a prior tree, delete the old tree first before constructing
** the new one.
**
** If the number of entries (p->nEntry) is less than
** ROWHASH_LINEAR_SEARCH_LIMIT, then we are guessing that a linear
** search is going to be faster than a lookup, so do not bother
** building the hash table.
*/
static int makeHashTable(RowHash *p, int iBatch){
  RowHashBlock *pBlock;
  int nBucket;
  int nLeaf, n;
  
  /* Delete the old hash table. */
  deleteHashTable(p->pHash, p->nHeight);
  assert( p->iBatch!=iBatch );
  p->iBatch = iBatch;

  /* Skip building the hash table if the number of elements is small */
  if( p->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){
    p->nLinearLimit = p->nEntry;
    p->pHash = 0;
    return SQLITE_OK;
  }

  /* Determine how many leaves the hash-table will comprise. */
  nLeaf = 1 + (p->nEntry / (ROWHASH_POINTER_PER_PAGE*ROWHASH_COLLISION_LENGTH));
  p->nBucket = nBucket = nLeaf*ROWHASH_POINTER_PER_PAGE;

  /* Set nHeight to the height of the tree that contains the leaf pages. If
  ** RowHash.nHeight is zero, then the whole hash-table fits on a single
  ** leaf. If RowHash.nHeight is 1, then RowHash.pHash points to an array
  ** of pointers to leaf pages. If 2, pHash points to an array of pointers
  ** to arrays of pointers to leaf pages. And so on.
  */
  p->nHeight = 0;
  n = nLeaf;
  while( n>1 ){
    n = (n+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE;
    p->nHeight++;
  }

  /* Allocate the hash-table. */
  if( allocHashTable(&p->pHash, p->nHeight, &nLeaf) ){
    return SQLITE_NOMEM;
  }

  /* Insert all values into the hash-table. */
  for(pBlock=p->pBlock; pBlock; pBlock=pBlock->data.pNext){
    RowHashElem * const pEnd = &pBlock->aElem[
      pBlock==p->pBlock?p->nUsed:ROWHASH_ELEM_PER_BLOCK
    ];
    RowHashElem *pIter;
    for(pIter=pBlock->aElem; pIter<pEnd; pIter++){
      RowHashElem **ppElem = findHashBucket(p, pIter->iVal);
      pIter->pNext = *ppElem;
      *ppElem = pIter;
    }
  }

  return SQLITE_OK;
}

/*
** Check to see if iVal has been inserted into the hash table "p"
** in some batch prior to iBatch.  If so, set *pExists to 1.
** If not, set *pExists to 0.
**
** The hash table is rebuilt whenever iBatch changes.  A hash table
** rebuild might encounter an out-of-memory condition.  If that happens,
** return SQLITE_NOMEM.  If there are no problems, return SQLITE_OK.
**
** The initial "batch" is 0.  So, if there were prior calls to
** sqlite3RowhashInsert() and then this routine is invoked with iBatch==0,
** because all prior inserts where in the same batch, none of the prior
** inserts will be visible and this routine will indicate not found.
** Hence, the first invocation of this routine should probably use
** a batch number of 1.
*/
int sqlite3RowhashTest(
  RowHash *p,     /* The RowHash to search in */
  int iBatch,     /* Look for values inserted in batches prior to this batch */
  i64 iVal,       /* The rowid value we are looking for */
  int *pExists    /* Store 0 or 1 hear to indicate not-found or found */
){
  *pExists = 0;
  if( p ){
    assert( p->pBlock );
    if( iBatch!=p->iBatch && makeHashTable(p, iBatch) ){
      return SQLITE_NOMEM;
    }
    if( p->pHash ){
      RowHashElem *pElem = *findHashBucket(p, iVal);
      for(; pElem; pElem=pElem->pNext){
        if( pElem->iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }else{
      int ii;
      RowHashElem *aElem = p->pBlock->aElem;
      for(ii=0; ii<p->nLinearLimit; ii++){
        if( aElem[ii].iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }
  }
  return SQLITE_OK;
}

/*
** Insert value iVal into the RowHash object.  Allocate a new RowHash
** object if necessary.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashInsert(sqlite3 *db, RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
  /* If the RowHash structure has not been allocated, allocate it now. */
  if( !p ){
    p = (RowHash*)sqlite3DbMallocZero(db, sizeof(RowHash));
    if( !p ){
      return SQLITE_NOMEM;
    }
    p->db = db;
    *pp = p;
  }

  /* If the current RowHashBlock is full, or if the first RowHashBlock has
  ** not yet been allocated, allocate one now. */ 
  if( !p->pBlock || p->nUsed==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
    p->nUsed = 0;
  }
  assert( p->nUsed==(p->nEntry % ROWHASH_ELEM_PER_BLOCK) );

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->nUsed].iVal = iVal;
  p->nUsed++;
  p->nEntry++;
  return SQLITE_OK;
}

/*
** Destroy the RowHash object passed as the first argument.
*/
void sqlite3RowhashDestroy(RowHash *p){
  if( p ){
    RowHashBlock *pBlock, *pNext;
    deleteHashTable(p->pHash, p->nHeight);
    for(pBlock=p->pBlock; pBlock; pBlock=pNext){
      pNext = pBlock->data.pNext;
      sqlite3_free(pBlock);
    }
    sqlite3DbFree(p->db, p);
  }
}
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<












































































































































































































































































































































































































































































































































































































































































































































































































Changes to src/sqliteInt.h.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.857 2009/04/22 00:47:01 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
** @(#) $Id: sqliteInt.h,v 1.858 2009/04/22 02:15:48 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;
typedef struct RowHash RowHash;
typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;







<







553
554
555
556
557
558
559

560
561
562
563
564
565
566

/*
** Forward references to structures
*/
typedef struct AggInfo AggInfo;
typedef struct AuthContext AuthContext;
typedef struct Bitvec Bitvec;

typedef struct RowSet RowSet;
typedef struct CollSeq CollSeq;
typedef struct Column Column;
typedef struct Db Db;
typedef struct Schema Schema;
typedef struct Expr Expr;
typedef struct ExprList ExprList;
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
#define WHERE_FILL_ROWHASH     0x0040  /* Save results in a RowHash object */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset/rowhash */
  int iRowidHandler;             /* Address of OP_RowSet or OP_RowHash */
  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */







|












|
|







1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
#define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
#define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
#define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
#define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
#define WHERE_FILL_ROWSET      0x0008  /* Save results in a RowSet object */
#define WHERE_OMIT_OPEN        0x0010  /* Table cursor are already open */
#define WHERE_OMIT_CLOSE       0x0020  /* Omit close of table & index cursors */
#define WHERE_FILL_ROWTEST     0x0040  /* Save results using OP_RowSetTest */

/*
** The WHERE clause processing routine has two halves.  The
** first part does the start of the WHERE loop and the second
** half does the tail of the WHERE loop.  An instance of
** this structure is returned by the first half and passed
** into the second half to give some continuity.
*/
struct WhereInfo {
  Parse *pParse;       /* Parsing and code generating context */
  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  int regRowSet;                 /* Store rowids in this rowset */
  int iRowidHandler;             /* Address of OP_RowSet or OP_RowSetTest */
  SrcList *pTabList;             /* List of tables in the join */
  int iTop;                      /* The very beginning of the WHERE loop */
  int iContinue;                 /* Jump here to continue with next record */
  int iBreak;                    /* Jump here to break out of the loop */
  int nLevel;                    /* Number of nested loop */
  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  WhereLevel a[1];               /* Information about each nest loop in WHERE */
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetTest(RowSet*, u8 iBatch, i64);
int sqlite3RowSetNext(RowSet*, i64*);

int sqlite3RowhashInsert(sqlite3*, RowHash **pp, i64 iVal);
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists);
void sqlite3RowhashDestroy(RowHash *p);

void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0
#endif







<
<
<
<







2398
2399
2400
2401
2402
2403
2404




2405
2406
2407
2408
2409
2410
2411

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, i64);
int sqlite3RowSetTest(RowSet*, u8 iBatch, i64);
int sqlite3RowSetNext(RowSet*, i64*);





void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

#if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE)
  int sqlite3ViewGetColumnNames(Parse*,Table*);
#else
# define sqlite3ViewGetColumnNames(A,B) 0
#endif
Changes to src/vdbe.c.
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.836 2009/04/22 00:47:01 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test







|







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.837 2009/04/22 02:15:48 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The following global variable is incremented every time a cursor
** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618


4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641

4642
4643
4644
4645
4646
4647
4648
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowHash P1 P2 P3 P4
**
** Register P3 is assumed to hold a 64-bit integer value. If register P1
** contains a rowid-hash object and the rowid-hash object contains
** the value held in P3, jump to register P2. Otherwise, insert the
** integer in P3 into the rowid-hash container and continue on to the
** next opcode.
**
** The rowid-hash is optimized for the case where successive sets
** of integers, where each set contains no duplicates. Each set
** of values is identified by a unique P4 value. The first set
** must have P4==0, the final set P4=-1.


**
** This allows optimizations: (a) when P4==0 there is no need to test
** the row-hash object for P3, as it is guaranteed not to contain it,
** (b) when P4==-1 there is no need to insert the value, as it will
** never be tested for, and (c) when a value that is part of set X is
** inserted, there is no need to search to see if the same value was
** previously inserted as part of set X (only if it was previously
** inserted as part of some other set).
*/
case OP_RowHash: {                     /* jump, in1, in3 */
  int iSet = pOp->p4.i;
  assert( pIn3->flags&MEM_Int );

  /* If there is anything other than a row-hash object in memory cell P1,
  ** delete it now and initialize P1 with an empty row-hash (a null pointer
  ** is an acceptable representation of an empty row-hash).
  */
  if( (pIn1->flags & MEM_RowSet)==0 ){
    sqlite3VdbeMemSetRowSet(pIn1);
    if( (pIn1->flags & MEM_RowSet)==0 ) goto no_mem;
  }

  assert( pOp->p4type==P4_INT32 );

  if( iSet ){
    int exists;
    exists = sqlite3RowSetTest(pIn1->u.pRowSet, iSet>=0 ? iSet & 0xf : 0xff,
                               pIn3->u.i);
    if( exists ){
      pc = pOp->p2 - 1;
      break;







|


|

|


|


|
>
>


|






|



|
|
<







>







4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635

4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
    /* A value was pulled from the index */
    assert( pOp->p3>0 && pOp->p3<=p->nMem );
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowSetTest P1 P2 P3 P4
**
** Register P3 is assumed to hold a 64-bit integer value. If register P1
** contains a RowSet object and that RowSet object contains
** the value held in P3, jump to register P2. Otherwise, insert the
** integer in P3 into the RowSet and continue on to the
** next opcode.
**
** The RowSet object is optimized for the case where successive sets
** of integers, where each set contains no duplicates. Each set
** of values is identified by a unique P4 value. The first set
** must have P4==0, the final set P4=-1.  P4 must be either -1 or
** non-negative.  For non-negative values of P4 only the lower 4
** bits are significant.
**
** This allows optimizations: (a) when P4==0 there is no need to test
** the rowset object for P3, as it is guaranteed not to contain it,
** (b) when P4==-1 there is no need to insert the value, as it will
** never be tested for, and (c) when a value that is part of set X is
** inserted, there is no need to search to see if the same value was
** previously inserted as part of set X (only if it was previously
** inserted as part of some other set).
*/
case OP_RowSetTest: {                     /* jump, in1, in3 */
  int iSet = pOp->p4.i;
  assert( pIn3->flags&MEM_Int );

  /* If there is anything other than a rowset object in memory cell P1,
  ** delete it now and initialize P1 with an empty rowset

  */
  if( (pIn1->flags & MEM_RowSet)==0 ){
    sqlite3VdbeMemSetRowSet(pIn1);
    if( (pIn1->flags & MEM_RowSet)==0 ) goto no_mem;
  }

  assert( pOp->p4type==P4_INT32 );
  assert( iSet==-1 || iSet>=0 );
  if( iSet ){
    int exists;
    exists = sqlite3RowSetTest(pIn1->u.pRowSet, iSet>=0 ? iSet & 0xf : 0xff,
                               pIn3->u.i);
    if( exists ){
      pc = pOp->p2 - 1;
      break;
Changes to src/vdbeInt.h.
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.168 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.







|







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
*************************************************************************
** This is the header file for information that is private to the
** VDBE.  This information used to all be at the top of the single
** source code file "vdbe.c".  When that file became too big (over
** 6000 lines long) it was split up into several smaller files and
** this header information was factored out.
**
** $Id: vdbeInt.h,v 1.169 2009/04/22 02:15:48 drh Exp $
*/
#ifndef _VDBEINT_H_
#define _VDBEINT_H_

/*
** intToKey() and keyToInt() used to transform the rowid.  But with
** the latest versions of the design they are no-ops.
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */
    RowHash *pRowHash;  /* Used only when flags==MEM_RowHash */
  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */







<







111
112
113
114
115
116
117

118
119
120
121
122
123
124
*/
struct Mem {
  union {
    i64 i;              /* Integer value. */
    int nZero;          /* Used when bit MEM_Zero is set in flags */
    FuncDef *pDef;      /* Used only when flags==MEM_Agg */
    RowSet *pRowSet;    /* Used only when flags==MEM_RowSet */

  } u;
  double r;           /* Real value */
  sqlite3 *db;        /* The associated database connection */
  char *z;            /* String or BLOB value */
  int n;              /* Number of characters in string value, excluding '\0' */
  u16 flags;          /* Some combination of MEM_Null, MEM_Str, MEM_Dyn, etc. */
  u8  type;           /* One of SQLITE_NULL, SQLITE_TEXT, SQLITE_INTEGER, etc */
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */
#define MEM_RowHash   0x0040   /* Value is a RowHash object */
#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/







<







144
145
146
147
148
149
150

151
152
153
154
155
156
157
*/
#define MEM_Null      0x0001   /* Value is NULL */
#define MEM_Str       0x0002   /* Value is a string */
#define MEM_Int       0x0004   /* Value is an integer */
#define MEM_Real      0x0008   /* Value is a real number */
#define MEM_Blob      0x0010   /* Value is a BLOB */
#define MEM_RowSet    0x0020   /* Value is a RowSet object */

#define MEM_TypeMask  0x00ff   /* Mask of type bits */

/* Whenever Mem contains a valid string or blob representation, one of
** the following flags must be set to determine the memory management
** policy for Mem.z.  The MEM_Term flag tells us whether or not the
** string is \000 or \u0000 terminated
*/
Changes to src/vdbeaux.c.
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.452 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*







|







10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
**
*************************************************************************
** This file contains code used for creating, destroying, and populating
** a VDBE (or an "sqlite3_stmt" as it is known to the outside world.)  Prior
** to version 2.8.7, all this code was combined into the vdbe.c source file.
** But that file was getting too big so this subroutines were split out.
**
** $Id: vdbeaux.c,v 1.453 2009/04/22 02:15:48 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"



/*
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }
    if( pMem->flags & MEM_RowHash ){
      sqlite3RowhashDestroy(pMem->u.pRowHash);
    }
    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;







<
<
<







1220
1221
1222
1223
1224
1225
1226



1227
1228
1229
1230
1231
1232
1233
  sqlite3 *db = p->db;
  Mem *pMem;
  closeAllCursorsExceptActiveVtabs(p);
  for(pMem=&p->aMem[1], i=1; i<=p->nMem; i++, pMem++){
    if( pMem->flags & MEM_RowSet ){
      sqlite3RowSetClear(pMem->u.pRowSet);
    }



    MemSetTypeFlag(pMem, MEM_Null);
  }
  releaseMemArray(&p->aMem[1], p->nMem);
  if( p->contextStack ){
    sqlite3DbFree(db, p->contextStack);
  }
  p->contextStack = 0;
Changes to src/vdbemem.c.
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.141 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.







|







11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
*************************************************************************
**
** This file contains code use to manipulate "Mem" structure.  A "Mem"
** stores a single value in the VDBE.  Mem is an opaque structure visible
** only within the VDBE.  Interface routines refer to a Mem using the
** name sqlite_value
**
** $Id: vdbemem.c,v 1.142 2009/04/22 02:15:49 drh Exp $
*/
#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** Call sqlite3VdbeMemExpandBlob() on the supplied value (type Mem*)
** P if required.
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
/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );
  if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_RowHash) ){
    if( p->flags&MEM_Agg ){
      sqlite3VdbeMemFinalize(p, p->u.pDef);
      assert( (p->flags & MEM_Agg)==0 );
      sqlite3VdbeMemRelease(p);
    }else if( p->flags&MEM_Dyn && p->xDel ){
      assert( (p->flags&MEM_RowSet)==0 );
      p->xDel((void *)p->z);
      p->xDel = 0;
    }else if( p->flags&MEM_RowSet ){
      sqlite3RowSetClear(p->u.pRowSet);
    }else if( p->flags&MEM_RowHash ){
      sqlite3RowhashDestroy(p->u.pRowHash);
      p->u.pRowHash = 0;
    }
  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and







|










<
<
<







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
/*
** If the memory cell contains a string value that must be freed by
** invoking an external callback, free it now. Calling this function
** does not free any Mem.zMalloc buffer.
*/
void sqlite3VdbeMemReleaseExternal(Mem *p){
  assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) );
  if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet) ){
    if( p->flags&MEM_Agg ){
      sqlite3VdbeMemFinalize(p, p->u.pDef);
      assert( (p->flags & MEM_Agg)==0 );
      sqlite3VdbeMemRelease(p);
    }else if( p->flags&MEM_Dyn && p->xDel ){
      assert( (p->flags&MEM_RowSet)==0 );
      p->xDel((void *)p->z);
      p->xDel = 0;
    }else if( p->flags&MEM_RowSet ){
      sqlite3RowSetClear(p->u.pRowSet);



    }
  }
}

/*
** Release any memory held by the Mem. This may leave the Mem in an
** inconsistent state, for example with (Mem.z==0) and
Changes to src/where.c.
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.384 2009/04/21 17:23:05 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)







|







12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
** This module contains C code that generates VDBE code used to process
** the WHERE clause of SQL statements.  This module is responsible for
** generating the code that loops through a table looking for applicable
** rows.  Indices are selected and used to speed the search when doing
** so is applicable.  Because this module is responsible for selecting
** indices, you might also think of this module as the "query optimizer".
**
** $Id: where.c,v 1.385 2009/04/22 02:15:49 drh Exp $
*/
#include "sqliteInt.h"

/*
** Trace output macros
*/
#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447

  /* Sometimes, this function is required to generate code to do 
  ** something with the rowid of each row scanned. Specifically:
  **
  **   1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted
  **      into the RowSet object stored in register pWInfo->regRowSet.
  **
  **   2) If pWInfo->regRowHash is non-zero, then the rowid must be inserted
  **      into the RowHash object stored in register pWInfo->regRowHash.
  **
  ** Extracting a rowid value from a VDBE cursor is not always a cheap
  ** operation, especially if the rowid is being extracted from an index
  ** cursor. If the rowid value is available as a by-product of the code
  ** generated to create the top of the scan loop, then it can be reused
  ** for either of the two purposes enumerated above without extracting
  ** it from a cursor. The following two variables are used to communicate
  ** the availability of the rowid value to the C-code at the end of this
  ** function that generates the rowid-handling VDBE code.
  */
  int iRowidReg = 0;              /* Rowid is stored in this register */
  int iReleaseReg = 0;            /* Temp register to free before returning */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FILL_ROWHASH)==0;
  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.







<
<
<




|















|







2410
2411
2412
2413
2414
2415
2416



2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444

  /* Sometimes, this function is required to generate code to do 
  ** something with the rowid of each row scanned. Specifically:
  **
  **   1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted
  **      into the RowSet object stored in register pWInfo->regRowSet.
  **



  ** Extracting a rowid value from a VDBE cursor is not always a cheap
  ** operation, especially if the rowid is being extracted from an index
  ** cursor. If the rowid value is available as a by-product of the code
  ** generated to create the top of the scan loop, then it can be reused
  ** without extracting
  ** it from a cursor. The following two variables are used to communicate
  ** the availability of the rowid value to the C-code at the end of this
  ** function that generates the rowid-handling VDBE code.
  */
  int iRowidReg = 0;              /* Rowid is stored in this register */
  int iReleaseReg = 0;            /* Temp register to free before returning */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = pWInfo->pWC;
  pLevel = &pWInfo->a[iLevel];
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
           && (wctrlFlags & WHERE_FILL_ROWTEST)==0;
  regRowSet = pWInfo->regRowSet;
  codeRowSetEarly = 0;

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop looks like this:
    **
    **          Null       1                # Zero the row-hash in reg 1
    **
    ** Then, for each indexed term, the following. The arguments to
    ** RowHash are such that the rowid of the current row is inserted
    ** into the row-hash. If it is already present, control skips the
    ** Gosub opcode and jumps straight to the code generated by WhereEnd().
    **
    **        sqlite3WhereBegin(<term>)
    **          RowHash                     # Insert rowid into rowhash
    **          Gosub      2 A
    **        sqlite3WhereEnd()
    **
    ** Following the above, code to terminate the loop. Label A, the target
    ** of the Gosub above, jumps to the instruction right after the Goto.
    **
    **          Null       1                # Zero the row-hash in reg 1
    **          Goto       B                # The loop is finished.
    **
    **       A: <loop body>                 # Return data, whatever.
    **
    **          Return     2                # Jump back to the Gosub
    **
    **       B: <after the loop>
    **
    */
    const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWHASH;

    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pFinal;     /* Final subterm within the OR-clause. */
    SrcList oneTab;        /* Shortened table list */

    int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
    int regRowhash = ++pParse->nMem;          /* Register for RowHash object */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int ii;
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pFinal = &pOrWc->a[pOrWc->nTerm-1];

    /* Set up a SrcList containing just the table being scanned by this loop. */
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;

    /* Initialize the row-hash register to contain NULL. An SQL NULL is 
    ** equivalent to an empty row-hash. 
    **
    ** Also initialize regReturn to contain the address of the instruction 
    ** immediately following the OP_Return at the bottom of the loop. This
    ** is required in a few obscure LEFT JOIN cases where control jumps
    ** over the top of the loop into the body of it. In this case the 
    ** correct response for the end-of-loop code (the OP_Return) is to 
    ** fall through to the next instruction, just as an OP_Next does if
    ** called on an uninitialized cursor.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

    /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */
    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */

        /* Loop through table entries that match term pOrTerm. */
        pSubWInfo = sqlite3WhereBegin(
            pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowhash);
        if( pSubWInfo ){
          int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
          /* The call to sqlite3WhereBegin has coded an OP_RowHash 
          ** at instruction iRowHash. Set P2 (the jump target) of this
          ** instruction to jump past the OP_Gosub coded below. This way,
          ** if the rowid is already in the hash-table, the body of the
          ** loop is not executed.
          */
          int iRowHash = pSubWInfo->iRowidHandler;
          sqlite3VdbeChangeP2(v, iRowHash, sqlite3VdbeCurrentAddr(v) + 1);
          sqlite3VdbeChangeP4(v, iRowHash, (char *)iSet, P4_INT32);
          sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
        }
      }
    }
    sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
    sqlite3VdbeResolveLabel(v, iLoopBody);

    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;
    disableTerm(pLevel, pTerm);
  }else







|


|
|



|






|









|






|
















|
|









|










|


|
|




|
|
|








|







2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
    **   CREATE INDEX i3 ON t1(c);
    **
    **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
    **
    ** In the example, there are three indexed terms connected by OR.
    ** The top of the loop looks like this:
    **
    **          Null       1                # Zero the rowset in reg 1
    **
    ** Then, for each indexed term, the following. The arguments to
    ** RowSetTest are such that the rowid of the current row is inserted
    ** into the RowSet. If it is already present, control skips the
    ** Gosub opcode and jumps straight to the code generated by WhereEnd().
    **
    **        sqlite3WhereBegin(<term>)
    **          RowSetTest                  # Insert rowid into rowset
    **          Gosub      2 A
    **        sqlite3WhereEnd()
    **
    ** Following the above, code to terminate the loop. Label A, the target
    ** of the Gosub above, jumps to the instruction right after the Goto.
    **
    **          Null       1                # Zero the rowset in reg 1
    **          Goto       B                # The loop is finished.
    **
    **       A: <loop body>                 # Return data, whatever.
    **
    **          Return     2                # Jump back to the Gosub
    **
    **       B: <after the loop>
    **
    */
    const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWTEST;

    WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
    WhereTerm *pFinal;     /* Final subterm within the OR-clause. */
    SrcList oneTab;        /* Shortened table list */

    int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
    int regRowset = ++pParse->nMem;           /* Register for RowSet object */
    int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
    int iRetInit;                             /* Address of regReturn init */
    int ii;
   
    pTerm = pLevel->plan.u.pTerm;
    assert( pTerm!=0 );
    assert( pTerm->eOperator==WO_OR );
    assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
    pOrWc = &pTerm->u.pOrInfo->wc;
    pFinal = &pOrWc->a[pOrWc->nTerm-1];

    /* Set up a SrcList containing just the table being scanned by this loop. */
    oneTab.nSrc = 1;
    oneTab.nAlloc = 1;
    oneTab.a[0] = *pTabItem;

    /* Initialize the rowset register to contain NULL. An SQL NULL is 
    ** equivalent to an empty rowset.
    **
    ** Also initialize regReturn to contain the address of the instruction 
    ** immediately following the OP_Return at the bottom of the loop. This
    ** is required in a few obscure LEFT JOIN cases where control jumps
    ** over the top of the loop into the body of it. In this case the 
    ** correct response for the end-of-loop code (the OP_Return) is to 
    ** fall through to the next instruction, just as an OP_Next does if
    ** called on an uninitialized cursor.
    */
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
    iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);

    /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */
    for(ii=0; ii<pOrWc->nTerm; ii++){
      WhereTerm *pOrTerm = &pOrWc->a[ii];
      if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
        WhereInfo *pSubWInfo;          /* Info for single OR-term scan */

        /* Loop through table entries that match term pOrTerm. */
        pSubWInfo = sqlite3WhereBegin(
            pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowset);
        if( pSubWInfo ){
          int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
          /* The call to sqlite3WhereBegin has coded an OP_RowSetTest
          ** at instruction iRowSet. Set P2 (the jump target) of this
          ** instruction to jump past the OP_Gosub coded below. This way,
          ** if the rowid is already in the hash-table, the body of the
          ** loop is not executed.
          */
          int iRowSet = pSubWInfo->iRowidHandler;
          sqlite3VdbeChangeP2(v, iRowSet, sqlite3VdbeCurrentAddr(v) + 1);
          sqlite3VdbeChangeP4(v, iRowSet, (char *)iSet, P4_INT32);
          sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
        }
      }
    }
    sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
    sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
    sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
    sqlite3VdbeResolveLabel(v, iLoopBody);

    pLevel->op = OP_Return;
    pLevel->p1 = regReturn;
    disableTerm(pLevel, pTerm);
  }else
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
      }
    }
    
    pWInfo->iRowidHandler = sqlite3VdbeCurrentAddr(v);
    if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg);
    }else{
      assert( pWInfo->wctrlFlags&WHERE_FILL_ROWHASH );
      sqlite3VdbeAddOp3(v, OP_RowHash, regRowSet, 0, iRowidReg);
    }
  }
  sqlite3ReleaseTempReg(pParse, iReleaseReg);

  return notReady;
}








|
|







2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
      }
    }
    
    pWInfo->iRowidHandler = sqlite3VdbeCurrentAddr(v);
    if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){
      sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg);
    }else{
      assert( pWInfo->wctrlFlags&WHERE_FILL_ROWTEST );
      sqlite3VdbeAddOp3(v, OP_RowSetTest, regRowSet, 0, iRowidReg);
    }
  }
  sqlite3ReleaseTempReg(pParse, iReleaseReg);

  return notReady;
}

3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = regRowSet;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];
  assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWHASH)) );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);







|







3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
  pWInfo->pParse = pParse;
  pWInfo->pTabList = pTabList;
  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  pWInfo->regRowSet = regRowSet;
  pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  pWInfo->wctrlFlags = wctrlFlags;
  pMaskSet = (WhereMaskSet*)&pWC[1];
  assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWTEST)) );

  /* Split the WHERE clause into separate subexpressions where each
  ** subexpression is separated by an AND operator.
  */
  initMaskSet(pMaskSet);
  whereClauseInit(pWC, pParse, pMaskSet);
  sqlite3ExprCodeConstants(pParse, pWhere);
Changes to tool/mksqlite3c.tcl.
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c

   rowhash.c
   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c







<







235
236
237
238
239
240
241

242
243
244
245
246
247
248
   hash.c
   opcodes.c

   os_os2.c
   os_unix.c
   os_win.c


   bitvec.c
   pcache.c
   pcache1.c
   rowset.c
   pager.c

   btmutex.c