/ Check-in [b8cb4f3e]
Login

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

Overview
Comment:New comments and minor refactoring of rowhash.c. (CVS 6529)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:b8cb4f3e2473afaee7c147a6b3f0972f69391a9a
User & Date: drh 2009-04-21 15:05:19
Context
2009-04-21
16:15
Allocate the initial RowHash object using lookaside. (CVS 6530) check-in: 9b30ab71 user: drh tags: trunk
15:05
New comments and minor refactoring of rowhash.c. (CVS 6529) check-in: b8cb4f3e user: drh tags: trunk
12:02
Remove a redundant test from sqlite3_shutdown(). (CVS 6528) check-in: 6f481ceb user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/rowhash.c.

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
...
264
265
266
267
268
269
270
271

272
273
274
275
276
277
278
...
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
**
**    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 "row-hash" data structure.

**


















** $Id: rowhash.c,v 1.1 2009/04/21 09:02:47 danielk1977 Exp $
*/
#include "sqliteInt.h"

typedef struct RowHashElem RowHashElem;
typedef struct RowHashBlock RowHashBlock;

/*
** Size of heap allocations made by this module. This limit is 
** never exceeded.

*/
#define ROWHASH_ALLOCATION 1024




















/*
** 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(void *))

/*
** If there are less than this number of elements in the block-list, do not
** bother building a hash-table. Just do a linear search of the list when
** querying.







*/
#define ROWHASH_LINEAR_SEARCH_LIMIT 10







/*
** Element stored in the hash-table.





*/
struct RowHashElem {
  i64 iVal;

  RowHashElem *pNext;
};

/*
** The following structure is either exactly ROWHASH_ALLOCATION bytes in
** size or just slightly less. It stores up to ROWHASH_ELEM_PER_BLOCK 
** RowHashElem structures.











*/
struct RowHashBlock {
  struct RowHashBlockData {
    int nElem;
    RowHashBlock *pNext;
  } data;
  RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK];
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  /* Variables populated by sqlite3RowhashInsert() */
  int nEntry;               /* Total number of entries in block-list */
  RowHashBlock *pBlock;     /* Linked list of entries */

  /* Variables populated by makeHashTable() */
  int iSet;                 /* Most recent iSet parameter passed to Test() */
  int iMod;                 /* Number of buckets in hash table */
  int nLeaf;                /* Number of leaf pages in hash table */
  int nHeight;              /* Height of tree containing leaf pages */
  void *pHash;              /* Pointer to root of tree */
  int nLinearLimit;         /* Linear search limit (used if pHash==0) */
};


/*
** Allocate a 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 a tree with the 
** maximum possible number of leaves for height nHeight. 
**
** 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 allocTable(void **pp, int nHeight, int *pnLeaf){
  void **ap = (void **)sqlite3MallocZero(ROWHASH_ALLOCATION);
  if( !ap ){
    return SQLITE_NOMEM;
  }
  *pp = (void *)ap;
  if( nHeight==0 ){
    (*pnLeaf)--;
  }else{
    int ii;
    for(ii=0; ii<ROWHASH_POINTER_PER_PAGE && *pnLeaf>0; ii++){
      if( allocTable(&ap[ii], nHeight-1, pnLeaf) ){
        return SQLITE_NOMEM;
      }
    }
  }
  return SQLITE_OK;
}

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

/*
** Delete the hash-table stored in p->pHash. The p->pHash pointer is
** set to zero before returning. This function is the inverse of 
** allocHashTable()
*/
static void deleteHashTable(RowHash *p){
  deleteTable(p->pHash, p->nHeight);
  p->pHash = 0;
}

/*
** Allocate the hash table structure based on the current values of
** p->nLeaf and p->nHeight.
*/
static int allocHashTable(RowHash *p){
  int nLeaf = p->nLeaf;
  assert( p->pHash==0 );
  assert( p->nLeaf>0 );
  return allocTable(&p->pHash, p->nHeight, &nLeaf);
}

/*
** Find the hash-bucket associated with value iVal. Return a pointer to it.



*/
static void **findHashBucket(RowHash *p, i64 iVal){
  int aOffset[16];
  int n = p->nHeight;
  void **ap = p->pHash;

  int h = (((u64)iVal) % p->iMod);


  for(n=0; n<p->nHeight; n++){
    int h1 = h / ROWHASH_POINTER_PER_PAGE;
    aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE);
    h = h1;
  }
  aOffset[n] = h;
  for(n=p->nHeight; n>0; n--){
    ap = (void **)ap[aOffset[n]];
  }
  return &ap[aOffset[0]];
}

/*
** Build a hash table to query with sqlite3RowhashTest() based on the
** set of values stored in the linked list of RowHashBlock structures.







*/
static int makeHashTable(RowHash *p, int iSet){
  RowHashBlock *pBlock;
  int iMod;
  int nLeaf;
  
  /* Delete the old hash table. */
  deleteHashTable(p);
  assert( p->iSet!=iSet );
  p->iSet = iSet;



  if( p->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){
    p->nLinearLimit = p->nEntry;

    return SQLITE_OK;
  }

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

  /* 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;

  while( nLeaf>1 ){
    nLeaf = (nLeaf+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE;
    p->nHeight++;
  }

  /* Allocate the hash-table. */
  if( allocHashTable(p) ){
    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->data.nElem];
    RowHashElem *pIter;
    for(pIter=pBlock->aElem; pIter<pEnd; pIter++){
      RowHashElem **ppElem = (RowHashElem **)findHashBucket(p, pIter->iVal);
      pIter->pNext = *ppElem;
      *ppElem = pIter;
    }
  }

  return SQLITE_OK;
}

/*

** Test if value iVal is in the hash table. If so, set *pExists to 1
** before returning. If iVal is not in the hash table, set *pExists to 0.
**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.









*/
int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists){





  *pExists = 0;
  if( p ){
    assert( p->pBlock );
    if( iSet!=p->iSet && makeHashTable(p, iSet) ){
      return SQLITE_NOMEM;
    }
    if( p->pHash ){
      RowHashElem *pElem = *(RowHashElem **)findHashBucket(p, iVal);
      for(; pElem; pElem=pElem->pNext){
        if( pElem->iVal==iVal ){
          *pExists = 1;
          break;
        }
      }
    }else{
................................................................................
      }
    }
  }
  return SQLITE_OK;
}

/*
** Insert value iVal into the RowHash object.

**
** Return SQLITE_OK if all goes as planned. If a malloc() fails, return
** SQLITE_NOMEM.
*/
int sqlite3RowhashInsert(RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
................................................................................
      return SQLITE_NOMEM;
    }
    *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->pBlock->data.nElem==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.nElem = 0;
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
  }

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->pBlock->data.nElem].iVal = iVal;
  p->pBlock->data.nElem++;
  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);
    for(pBlock=p->pBlock; pBlock; pBlock=pNext){
      pNext = pBlock->data.pNext;
      sqlite3_free(pBlock);
    }
    sqlite3_free(p);
  }
}








|
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|



<
<
<

|
<
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|


|
|
|
>
>
>
>
>
>
>

<
>
>
>
>
>
>


<
>
>
>
>
>


<
>
|



|
|
|
>
>
>
>
>
>
>
>
>
>
>



|
|

|








|
|


|

<
|
|





|
|
|
|







|
|
|


|





|








|

|
|



|


|




<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

>
>
>

|

|
<
>
|
>
>
|





|
|

|



|
|
>
>
>
>
>
>
>

|


|


|
|
<
>

>


>




|
|
<
<








>
|
|




|





|


|









>
|
|

<
|
>
>
>
>
>
>
>
>
>

|
>
>
>
>
>



|



|







 







|
>







 







|




|





|
|










|







<
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
...
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
...
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

**
**    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.2 2009/04/21 15:05:19 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 {
    int nUsed;                /* Num of aElem[] currently used in this block */
    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 {
  /* Variables populated by sqlite3RowhashInsert() */
  int nEntry;               /* Number of used entries over all RowHashBlocks */
  RowHashBlock *pBlock;     /* Linked list of RowHashBlocks */

  /* Variables populated by makeHashTable() */
  int iBatch;               /* The current insert batch number */
  int iMod;                 /* Number of buckets in hash table */

  int nHeight;              /* Height of tree of hash pages */
  RowHashPage *pHash;       /* Pointer to root of hash table tree */
  int nLinearLimit;         /* Linear search limit (used if pHash==0) */
};


/*
** 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->iMod);

  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 iMod;
  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->iMod = iMod = 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->data.nUsed];
    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{
................................................................................
      }
    }
  }
  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(RowHash **pp, i64 iVal){
  RowHash *p = *pp;
  
................................................................................
      return SQLITE_NOMEM;
    }
    *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->pBlock->data.nUsed==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
    if( !pBlock ){
      return SQLITE_NOMEM;
    }
    pBlock->data.nUsed = 0;
    pBlock->data.pNext = p->pBlock;
    p->pBlock = pBlock;
  }

  /* Add iVal to the current RowHashBlock. */
  p->pBlock->aElem[p->pBlock->data.nUsed].iVal = iVal;
  p->pBlock->data.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);
    }
    sqlite3_free(p);
  }
}

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610

4611
4612
4613
4614
4615
4616
4617
**
** 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.833 2009/04/21 09:02:47 danielk1977 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
................................................................................
    sqlite3VdbeMemSetInt64(pOut, val);
  }
  break;
}

/* Opcode: RowHash P1 P2 P3 P4
**
** Register P3 is assumed to hold an 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.

**
** 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







|







 







|


|
>







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
**
** 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.834 2009/04/21 15:05:19 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
................................................................................
    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