/ Check-in [e31d2f87]
Login

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

Overview
Comment:Cleanup the hash functions in FTS2. Backports (4440) from fts3. (CVS 5452)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e31d2f875c13ee41742c9aaee6291662cdbbf863
User & Date: shess 2008-07-22 22:15:48
Context
2008-07-22
22:20
fts2.c buildTerms() passes -1 for nInput. Backports (4511) from fts3. (CVS 5453) check-in: d562515e user: shess tags: trunk
22:15
Cleanup the hash functions in FTS2. Backports (4440) from fts3. (CVS 5452) check-in: e31d2f87 user: shess tags: trunk
18:45
Documentation updates. No changes to code. (CVS 5451) check-in: e58b4977 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts2/fts2_hash.c.

27
28
29
30
31
32
33



34
35
36
37
38
39



40
41
42
43
44
45
46
..
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
...
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
...
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
...
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

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

#include "fts2_hash.h"




static void *malloc_and_zero(int n){
  void *p = malloc(n);
  if( p ){
    memset(p, 0, n);
  }
  return p;



}

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**
** "pNew" is a pointer to the hash table that is to be initialized.
** keyClass is one of the constants 
................................................................................
  assert( keyClass>=FTS2_HASH_STRING && keyClass<=FTS2_HASH_BINARY );
  pNew->keyClass = keyClass;
  pNew->copyKey = copyKey;
  pNew->first = 0;
  pNew->count = 0;
  pNew->htsize = 0;
  pNew->ht = 0;
  pNew->xMalloc = malloc_and_zero;
  pNew->xFree = free;
}

/* Remove all entries from a hash table.  Reclaim all memory.
** Call this routine to delete a hash table or to reset a hash table
** to the empty state.
*/
void sqlite3Fts2HashClear(fts2Hash *pH){
  fts2HashElem *elem;         /* For looping over all elements of the table */

  assert( pH!=0 );
  elem = pH->first;
  pH->first = 0;
  if( pH->ht ) pH->xFree(pH->ht);
  pH->ht = 0;
  pH->htsize = 0;
  while( elem ){
    fts2HashElem *next_elem = elem->next;
    if( pH->copyKey && elem->pKey ){
      pH->xFree(elem->pKey);
    }
    pH->xFree(elem);
    elem = next_elem;
  }
  pH->count = 0;
}

/*
** Hash and comparison functions when the mode is FTS2_HASH_STRING
................................................................................
*/
static void rehash(fts2Hash *pH, int new_size){
  struct _fts2ht *new_ht;          /* The new hash table */
  fts2HashElem *elem, *next_elem;  /* For looping over existing elements */
  int (*xHash)(const void*,int);   /* The hash function */

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _fts2ht *)pH->xMalloc( new_size*sizeof(struct _fts2ht) );
  if( new_ht==0 ) return;
  if( pH->ht ) pH->xFree(pH->ht);
  pH->ht = new_ht;
  pH->htsize = new_size;
  xHash = hashFunction(pH->keyClass);
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
    next_elem = elem->next;
    insertElement(pH, &new_ht[h], elem);
................................................................................
    pEntry->chain = elem->next;
  }
  pEntry->count--;
  if( pEntry->count<=0 ){
    pEntry->chain = 0;
  }
  if( pH->copyKey && elem->pKey ){
    pH->xFree(elem->pKey);
  }
  pH->xFree( elem );
  pH->count--;
  if( pH->count<=0 ){
    assert( pH->first==0 );
    assert( pH->count==0 );
    fts2HashClear(pH);
  }
}
................................................................................
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data==0 ) return 0;
  new_elem = (fts2HashElem*)pH->xMalloc( sizeof(fts2HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = pH->xMalloc( nKey );
    if( new_elem->pKey==0 ){
      pH->xFree(new_elem);
      return data;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = (void*)pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ){
    rehash(pH,8);
    if( pH->htsize==0 ){
      pH->count = 0;
      pH->xFree(new_elem);
      return data;
    }
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( pH->htsize>0 );







>
>
>
|
|




>
>
>







 







<
<












|





|

|







 







|

|







 







|

|







 







|


|

|












|







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
..
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
...
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
...
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
...
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

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

#include "fts2_hash.h"

/*
** Malloc and Free functions
*/
static void *fts2HashMalloc(int n){
  void *p = sqlite3_malloc(n);
  if( p ){
    memset(p, 0, n);
  }
  return p;
}
static void fts2HashFree(void *p){
  sqlite3_free(p);
}

/* Turn bulk memory into a hash table object by initializing the
** fields of the Hash structure.
**
** "pNew" is a pointer to the hash table that is to be initialized.
** keyClass is one of the constants 
................................................................................
  assert( keyClass>=FTS2_HASH_STRING && keyClass<=FTS2_HASH_BINARY );
  pNew->keyClass = keyClass;
  pNew->copyKey = copyKey;
  pNew->first = 0;
  pNew->count = 0;
  pNew->htsize = 0;
  pNew->ht = 0;


}

/* Remove all entries from a hash table.  Reclaim all memory.
** Call this routine to delete a hash table or to reset a hash table
** to the empty state.
*/
void sqlite3Fts2HashClear(fts2Hash *pH){
  fts2HashElem *elem;         /* For looping over all elements of the table */

  assert( pH!=0 );
  elem = pH->first;
  pH->first = 0;
  fts2HashFree(pH->ht);
  pH->ht = 0;
  pH->htsize = 0;
  while( elem ){
    fts2HashElem *next_elem = elem->next;
    if( pH->copyKey && elem->pKey ){
      fts2HashFree(elem->pKey);
    }
    fts2HashFree(elem);
    elem = next_elem;
  }
  pH->count = 0;
}

/*
** Hash and comparison functions when the mode is FTS2_HASH_STRING
................................................................................
*/
static void rehash(fts2Hash *pH, int new_size){
  struct _fts2ht *new_ht;          /* The new hash table */
  fts2HashElem *elem, *next_elem;  /* For looping over existing elements */
  int (*xHash)(const void*,int);   /* The hash function */

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _fts2ht *)fts2HashMalloc( new_size*sizeof(struct _fts2ht) );
  if( new_ht==0 ) return;
  fts2HashFree(pH->ht);
  pH->ht = new_ht;
  pH->htsize = new_size;
  xHash = hashFunction(pH->keyClass);
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
    next_elem = elem->next;
    insertElement(pH, &new_ht[h], elem);
................................................................................
    pEntry->chain = elem->next;
  }
  pEntry->count--;
  if( pEntry->count<=0 ){
    pEntry->chain = 0;
  }
  if( pH->copyKey && elem->pKey ){
    fts2HashFree(elem->pKey);
  }
  fts2HashFree( elem );
  pH->count--;
  if( pH->count<=0 ){
    assert( pH->first==0 );
    assert( pH->count==0 );
    fts2HashClear(pH);
  }
}
................................................................................
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data==0 ) return 0;
  new_elem = (fts2HashElem*)fts2HashMalloc( sizeof(fts2HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = fts2HashMalloc( nKey );
    if( new_elem->pKey==0 ){
      fts2HashFree(new_elem);
      return data;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = (void*)pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ){
    rehash(pH,8);
    if( pH->htsize==0 ){
      pH->count = 0;
      fts2HashFree(new_elem);
      return data;
    }
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( pH->htsize>0 );

Changes to ext/fts2/fts2_hash.h.

30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
** this structure opaque.
*/
struct fts2Hash {
  char keyClass;          /* HASH_INT, _POINTER, _STRING, _BINARY */
  char copyKey;           /* True if copy of key made on insert */
  int count;              /* Number of entries in this table */
  fts2HashElem *first;    /* The first element of the array */
  void *(*xMalloc)(int);  /* malloc() function to use */
  void (*xFree)(void *);  /* free() function to use */
  int htsize;             /* Number of buckets in the hash table */
  struct _fts2ht {        /* the hash table */
    int count;               /* Number of entries with this hash */
    fts2HashElem *chain;     /* Pointer to first entry with this hash */
  } *ht;
};








<
<







30
31
32
33
34
35
36


37
38
39
40
41
42
43
** this structure opaque.
*/
struct fts2Hash {
  char keyClass;          /* HASH_INT, _POINTER, _STRING, _BINARY */
  char copyKey;           /* True if copy of key made on insert */
  int count;              /* Number of entries in this table */
  fts2HashElem *first;    /* The first element of the array */


  int htsize;             /* Number of buckets in the hash table */
  struct _fts2ht {        /* the hash table */
    int count;               /* Number of entries with this hash */
    fts2HashElem *chain;     /* Pointer to first entry with this hash */
  } *ht;
};