/ Check-in [9b30ab71]
Login

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

Overview
Comment:Allocate the initial RowHash object using lookaside. (CVS 6530)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9b30ab7199d8b51bdea8ec7f0410281527623673
User & Date: drh 2009-04-21 16:15:15
Context
2009-04-21
17:13
Adjust the rowhash.test module so that it recovers gracefully in the rare event of a rowid collision. (CVS 6531) check-in: 72e16809 user: drh tags: trunk
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
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/rowhash.c.

27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
...
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
...
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
...
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
...
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352

353
354
355
356
357
358
359
...
379
380
381
382
383
384
385
386
387
388
** 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.
*/
................................................................................
};

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

................................................................................
    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.
  */
................................................................................
/*
** 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;
  
  /* If the RowHash structure has not been allocated, allocate it now. */
  if( !p ){
    p = (RowHash*)sqlite3MallocZero(sizeof(RowHash));
    if( !p ){
      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( 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);
  }
}







|







 







|
|
|
|
|
|
|
|
<
<







 







|







 







|







 







|







 







|




|



>







 







|


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146


147
148
149
150
151
152
153
...
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
...
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
...
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
...
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
...
378
379
380
381
382
383
384
385
386
387
** 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.3 2009/04/21 16:15:15 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.
*/
................................................................................
};

/*
** RowHash structure. References to a structure of this type are passed
** around and used as opaque handles by code in other modules.
*/
struct RowHash {
  int nEntry;             /* Number of used entries over all RowHashBlocks */
  int iBatch;             /* The current insert batch number */
  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
................................................................................
** 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;
  }
................................................................................
** 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;

................................................................................
    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.
  */
................................................................................
/*
** 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->pBlock->data.nUsed==ROWHASH_ELEM_PER_BLOCK ){
    RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock));
................................................................................
  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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
**    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.855 2009/04/21 09:02:47 danielk1977 Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
int sqlite3BitvecBuiltinTest(int,int*);

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

int sqlite3RowhashInsert(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*);







|







 







|







7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
....
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
**    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.856 2009/04/21 16:15:15 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_

/*
** Include the configuration header output by 'configure' if we're using the
** autoconf-based build
................................................................................
int sqlite3BitvecBuiltinTest(int,int*);

RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
void sqlite3RowSetClear(RowSet*);
void sqlite3RowSetInsert(RowSet*, 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*);

Changes to src/vdbe.c.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
**
** 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
................................................................................
    rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists);
    if( exists ){
      pc = pOp->p2 - 1;
      break;
    }
  }
  if( iSet>=0 ){
    rc = sqlite3RowhashInsert(&pIn1->u.pRowHash, pIn3->u.i);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER
/* Opcode: ContextPush * * * 







|







 







|







39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
....
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
**
** 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.835 2009/04/21 16:15:15 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
................................................................................
    rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists);
    if( exists ){
      pc = pOp->p2 - 1;
      break;
    }
  }
  if( iSet>=0 ){
    rc = sqlite3RowhashInsert(db, &pIn1->u.pRowHash, pIn3->u.i);
  }
  break;
}


#ifndef SQLITE_OMIT_TRIGGER
/* Opcode: ContextPush * * *