← Back to branch summary

~ubuntu-branches/ubuntu/maverick/sqlite3/maverick-updates

« back to all changes in this revision

Viewing changes to ext/fts3/fts3_hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2008-10-01 20:16:18 UTC
  • mfrom: (3.1.20 intrepid)
  • Revision ID: james.westby@ubuntu.com-20081001201618-yfvqqj1qs29wdtcc
Tags: 3.5.9-5
http://bugs.debian.org/500792
Backport fix for distinct on indexes (closes: #500792).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/fts3/fts3_hash.c
 
1
/*
 
2
** 2001 September 22
 
3
**
 
4
** The author disclaims copyright to this source code.  In place of
 
5
** a legal notice, here is a blessing:
 
6
**
 
7
**    May you do good and not evil.
 
8
**    May you find forgiveness for yourself and forgive others.
 
9
**    May you share freely, never taking more than you give.
 
10
**
 
11
*************************************************************************
 
12
** This is the implementation of generic hash-tables used in SQLite.
 
13
** We've modified it slightly to serve as a standalone hash table
 
14
** implementation for the full-text indexing module.
 
15
*/
 
16
 
 
17
/*
 
18
** The code in this file is only compiled if:
 
19
**
 
20
**     * The FTS3 module is being built as an extension
 
21
**       (in which case SQLITE_CORE is not defined), or
 
22
**
 
23
**     * The FTS3 module is being built into the core of
 
24
**       SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
 
25
*/
 
26
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
 
27
 
 
28
#include <assert.h>
 
29
#include <stdlib.h>
 
30
#include <string.h>
 
31
 
 
32
#include "sqlite3.h"
 
33
#include "fts3_hash.h"
 
34
 
 
35
/*
 
36
** Malloc and Free functions
 
37
*/
 
38
static void *fts3HashMalloc(int n){
 
39
  void *p = sqlite3_malloc(n);
 
40
  if( p ){
 
41
    memset(p, 0, n);
 
42
  }
 
43
  return p;
 
44
}
 
45
static void fts3HashFree(void *p){
 
46
  sqlite3_free(p);
 
47
}
 
48
 
 
49
/* Turn bulk memory into a hash table object by initializing the
 
50
** fields of the Hash structure.
 
51
**
 
52
** "pNew" is a pointer to the hash table that is to be initialized.
 
53
** keyClass is one of the constants 
 
54
** FTS3_HASH_BINARY or FTS3_HASH_STRING.  The value of keyClass 
 
55
** determines what kind of key the hash table will use.  "copyKey" is
 
56
** true if the hash table should make its own private copy of keys and
 
57
** false if it should just use the supplied pointer.
 
58
*/
 
59
void sqlite3Fts3HashInit(fts3Hash *pNew, int keyClass, int copyKey){
 
60
  assert( pNew!=0 );
 
61
  assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_HASH_BINARY );
 
62
  pNew->keyClass = keyClass;
 
63
  pNew->copyKey = copyKey;
 
64
  pNew->first = 0;
 
65
  pNew->count = 0;
 
66
  pNew->htsize = 0;
 
67
  pNew->ht = 0;
 
68
}
 
69
 
 
70
/* Remove all entries from a hash table.  Reclaim all memory.
 
71
** Call this routine to delete a hash table or to reset a hash table
 
72
** to the empty state.
 
73
*/
 
74
void sqlite3Fts3HashClear(fts3Hash *pH){
 
75
  fts3HashElem *elem;         /* For looping over all elements of the table */
 
76
 
 
77
  assert( pH!=0 );
 
78
  elem = pH->first;
 
79
  pH->first = 0;
 
80
  fts3HashFree(pH->ht);
 
81
  pH->ht = 0;
 
82
  pH->htsize = 0;
 
83
  while( elem ){
 
84
    fts3HashElem *next_elem = elem->next;
 
85
    if( pH->copyKey && elem->pKey ){
 
86
      fts3HashFree(elem->pKey);
 
87
    }
 
88
    fts3HashFree(elem);
 
89
    elem = next_elem;
 
90
  }
 
91
  pH->count = 0;
 
92
}
 
93
 
 
94
/*
 
95
** Hash and comparison functions when the mode is FTS3_HASH_STRING
 
96
*/
 
97
static int fts3StrHash(const void *pKey, int nKey){
 
98
  const char *z = (const char *)pKey;
 
99
  int h = 0;
 
100
  if( nKey<=0 ) nKey = (int) strlen(z);
 
101
  while( nKey > 0  ){
 
102
    h = (h<<3) ^ h ^ *z++;
 
103
    nKey--;
 
104
  }
 
105
  return h & 0x7fffffff;
 
106
}
 
107
static int fts3StrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
108
  if( n1!=n2 ) return 1;
 
109
  return strncmp((const char*)pKey1,(const char*)pKey2,n1);
 
110
}
 
111
 
 
112
/*
 
113
** Hash and comparison functions when the mode is FTS3_HASH_BINARY
 
114
*/
 
115
static int fts3BinHash(const void *pKey, int nKey){
 
116
  int h = 0;
 
117
  const char *z = (const char *)pKey;
 
118
  while( nKey-- > 0 ){
 
119
    h = (h<<3) ^ h ^ *(z++);
 
120
  }
 
121
  return h & 0x7fffffff;
 
122
}
 
123
static int fts3BinCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
124
  if( n1!=n2 ) return 1;
 
125
  return memcmp(pKey1,pKey2,n1);
 
126
}
 
127
 
 
128
/*
 
129
** Return a pointer to the appropriate hash function given the key class.
 
130
**
 
131
** The C syntax in this function definition may be unfamilar to some 
 
132
** programmers, so we provide the following additional explanation:
 
133
**
 
134
** The name of the function is "ftsHashFunction".  The function takes a
 
135
** single parameter "keyClass".  The return value of ftsHashFunction()
 
136
** is a pointer to another function.  Specifically, the return value
 
137
** of ftsHashFunction() is a pointer to a function that takes two parameters
 
138
** with types "const void*" and "int" and returns an "int".
 
139
*/
 
140
static int (*ftsHashFunction(int keyClass))(const void*,int){
 
141
  if( keyClass==FTS3_HASH_STRING ){
 
142
    return &fts3StrHash;
 
143
  }else{
 
144
    assert( keyClass==FTS3_HASH_BINARY );
 
145
    return &fts3BinHash;
 
146
  }
 
147
}
 
148
 
 
149
/*
 
150
** Return a pointer to the appropriate hash function given the key class.
 
151
**
 
152
** For help in interpreted the obscure C code in the function definition,
 
153
** see the header comment on the previous function.
 
154
*/
 
155
static int (*ftsCompareFunction(int keyClass))(const void*,int,const void*,int){
 
156
  if( keyClass==FTS3_HASH_STRING ){
 
157
    return &fts3StrCompare;
 
158
  }else{
 
159
    assert( keyClass==FTS3_HASH_BINARY );
 
160
    return &fts3BinCompare;
 
161
  }
 
162
}
 
163
 
 
164
/* Link an element into the hash table
 
165
*/
 
166
static void fts3HashInsertElement(
 
167
  fts3Hash *pH,            /* The complete hash table */
 
168
  struct _fts3ht *pEntry,  /* The entry into which pNew is inserted */
 
169
  fts3HashElem *pNew       /* The element to be inserted */
 
170
){
 
171
  fts3HashElem *pHead;     /* First element already in pEntry */
 
172
  pHead = pEntry->chain;
 
173
  if( pHead ){
 
174
    pNew->next = pHead;
 
175
    pNew->prev = pHead->prev;
 
176
    if( pHead->prev ){ pHead->prev->next = pNew; }
 
177
    else             { pH->first = pNew; }
 
178
    pHead->prev = pNew;
 
179
  }else{
 
180
    pNew->next = pH->first;
 
181
    if( pH->first ){ pH->first->prev = pNew; }
 
182
    pNew->prev = 0;
 
183
    pH->first = pNew;
 
184
  }
 
185
  pEntry->count++;
 
186
  pEntry->chain = pNew;
 
187
}
 
188
 
 
189
 
 
190
/* Resize the hash table so that it cantains "new_size" buckets.
 
191
** "new_size" must be a power of 2.  The hash table might fail 
 
192
** to resize if sqliteMalloc() fails.
 
193
*/
 
194
static void fts3Rehash(fts3Hash *pH, int new_size){
 
195
  struct _fts3ht *new_ht;          /* The new hash table */
 
196
  fts3HashElem *elem, *next_elem;  /* For looping over existing elements */
 
197
  int (*xHash)(const void*,int);   /* The hash function */
 
198
 
 
199
  assert( (new_size & (new_size-1))==0 );
 
200
  new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) );
 
201
  if( new_ht==0 ) return;
 
202
  fts3HashFree(pH->ht);
 
203
  pH->ht = new_ht;
 
204
  pH->htsize = new_size;
 
205
  xHash = ftsHashFunction(pH->keyClass);
 
206
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
 
207
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
 
208
    next_elem = elem->next;
 
209
    fts3HashInsertElement(pH, &new_ht[h], elem);
 
210
  }
 
211
}
 
212
 
 
213
/* This function (for internal use only) locates an element in an
 
214
** hash table that matches the given key.  The hash for this key has
 
215
** already been computed and is passed as the 4th parameter.
 
216
*/
 
217
static fts3HashElem *fts3FindElementByHash(
 
218
  const fts3Hash *pH, /* The pH to be searched */
 
219
  const void *pKey,   /* The key we are searching for */
 
220
  int nKey,
 
221
  int h               /* The hash for this key. */
 
222
){
 
223
  fts3HashElem *elem;            /* Used to loop thru the element list */
 
224
  int count;                     /* Number of elements left to test */
 
225
  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
 
226
 
 
227
  if( pH->ht ){
 
228
    struct _fts3ht *pEntry = &pH->ht[h];
 
229
    elem = pEntry->chain;
 
230
    count = pEntry->count;
 
231
    xCompare = ftsCompareFunction(pH->keyClass);
 
232
    while( count-- && elem ){
 
233
      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
 
234
        return elem;
 
235
      }
 
236
      elem = elem->next;
 
237
    }
 
238
  }
 
239
  return 0;
 
240
}
 
241
 
 
242
/* Remove a single entry from the hash table given a pointer to that
 
243
** element and a hash on the element's key.
 
244
*/
 
245
static void fts3RemoveElementByHash(
 
246
  fts3Hash *pH,         /* The pH containing "elem" */
 
247
  fts3HashElem* elem,   /* The element to be removed from the pH */
 
248
  int h                 /* Hash value for the element */
 
249
){
 
250
  struct _fts3ht *pEntry;
 
251
  if( elem->prev ){
 
252
    elem->prev->next = elem->next; 
 
253
  }else{
 
254
    pH->first = elem->next;
 
255
  }
 
256
  if( elem->next ){
 
257
    elem->next->prev = elem->prev;
 
258
  }
 
259
  pEntry = &pH->ht[h];
 
260
  if( pEntry->chain==elem ){
 
261
    pEntry->chain = elem->next;
 
262
  }
 
263
  pEntry->count--;
 
264
  if( pEntry->count<=0 ){
 
265
    pEntry->chain = 0;
 
266
  }
 
267
  if( pH->copyKey && elem->pKey ){
 
268
    fts3HashFree(elem->pKey);
 
269
  }
 
270
  fts3HashFree( elem );
 
271
  pH->count--;
 
272
  if( pH->count<=0 ){
 
273
    assert( pH->first==0 );
 
274
    assert( pH->count==0 );
 
275
    fts3HashClear(pH);
 
276
  }
 
277
}
 
278
 
 
279
/* Attempt to locate an element of the hash table pH with a key
 
280
** that matches pKey,nKey.  Return the data for this element if it is
 
281
** found, or NULL if there is no match.
 
282
*/
 
283
void *sqlite3Fts3HashFind(const fts3Hash *pH, const void *pKey, int nKey){
 
284
  int h;                 /* A hash on key */
 
285
  fts3HashElem *elem;    /* The element that matches key */
 
286
  int (*xHash)(const void*,int);  /* The hash function */
 
287
 
 
288
  if( pH==0 || pH->ht==0 ) return 0;
 
289
  xHash = ftsHashFunction(pH->keyClass);
 
290
  assert( xHash!=0 );
 
291
  h = (*xHash)(pKey,nKey);
 
292
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
293
  elem = fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1));
 
294
  return elem ? elem->data : 0;
 
295
}
 
296
 
 
297
/* Insert an element into the hash table pH.  The key is pKey,nKey
 
298
** and the data is "data".
 
299
**
 
300
** If no element exists with a matching key, then a new
 
301
** element is created.  A copy of the key is made if the copyKey
 
302
** flag is set.  NULL is returned.
 
303
**
 
304
** If another element already exists with the same key, then the
 
305
** new data replaces the old data and the old data is returned.
 
306
** The key is not copied in this instance.  If a malloc fails, then
 
307
** the new data is returned and the hash table is unchanged.
 
308
**
 
309
** If the "data" parameter to this function is NULL, then the
 
310
** element corresponding to "key" is removed from the hash table.
 
311
*/
 
312
void *sqlite3Fts3HashInsert(
 
313
  fts3Hash *pH,        /* The hash table to insert into */
 
314
  const void *pKey,    /* The key */
 
315
  int nKey,            /* Number of bytes in the key */
 
316
  void *data           /* The data */
 
317
){
 
318
  int hraw;                 /* Raw hash value of the key */
 
319
  int h;                    /* the hash of the key modulo hash table size */
 
320
  fts3HashElem *elem;       /* Used to loop thru the element list */
 
321
  fts3HashElem *new_elem;   /* New element added to the pH */
 
322
  int (*xHash)(const void*,int);  /* The hash function */
 
323
 
 
324
  assert( pH!=0 );
 
325
  xHash = ftsHashFunction(pH->keyClass);
 
326
  assert( xHash!=0 );
 
327
  hraw = (*xHash)(pKey, nKey);
 
328
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
329
  h = hraw & (pH->htsize-1);
 
330
  elem = fts3FindElementByHash(pH,pKey,nKey,h);
 
331
  if( elem ){
 
332
    void *old_data = elem->data;
 
333
    if( data==0 ){
 
334
      fts3RemoveElementByHash(pH,elem,h);
 
335
    }else{
 
336
      elem->data = data;
 
337
    }
 
338
    return old_data;
 
339
  }
 
340
  if( data==0 ) return 0;
 
341
  new_elem = (fts3HashElem*)fts3HashMalloc( sizeof(fts3HashElem) );
 
342
  if( new_elem==0 ) return data;
 
343
  if( pH->copyKey && pKey!=0 ){
 
344
    new_elem->pKey = fts3HashMalloc( nKey );
 
345
    if( new_elem->pKey==0 ){
 
346
      fts3HashFree(new_elem);
 
347
      return data;
 
348
    }
 
349
    memcpy((void*)new_elem->pKey, pKey, nKey);
 
350
  }else{
 
351
    new_elem->pKey = (void*)pKey;
 
352
  }
 
353
  new_elem->nKey = nKey;
 
354
  pH->count++;
 
355
  if( pH->htsize==0 ){
 
356
    fts3Rehash(pH,8);
 
357
    if( pH->htsize==0 ){
 
358
      pH->count = 0;
 
359
      fts3HashFree(new_elem);
 
360
      return data;
 
361
    }
 
362
  }
 
363
  if( pH->count > pH->htsize ){
 
364
    fts3Rehash(pH,pH->htsize*2);
 
365
  }
 
366
  assert( pH->htsize>0 );
 
367
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
368
  h = hraw & (pH->htsize-1);
 
369
  fts3HashInsertElement(pH, &pH->ht[h], new_elem);
 
370
  new_elem->data = data;
 
371
  return 0;
 
372
}
 
373
 
 
374
#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */