← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/sqlite/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/3rdparty/sqlite/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
 
13
** used in SQLite.
 
14
**
 
15
** $Id: hash.c,v 1.16 2005/01/31 12:56:44 danielk1977 Exp $
 
16
*/
 
17
#include "sqliteInt.h"
 
18
#include <assert.h>
 
19
 
 
20
/* Turn bulk memory into a hash table object by initializing the
 
21
** fields of the Hash structure.
 
22
**
 
23
** "pNew" is a pointer to the hash table that is to be initialized.
 
24
** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
 
25
** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING.  The value of keyClass 
 
26
** determines what kind of key the hash table will use.  "copyKey" is
 
27
** true if the hash table should make its own private copy of keys and
 
28
** false if it should just use the supplied pointer.  CopyKey only makes
 
29
** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
 
30
** for other key classes.
 
31
*/
 
32
void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
 
33
  assert( pNew!=0 );
 
34
  assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
 
35
  pNew->keyClass = keyClass;
 
36
#if 0
 
37
  if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
 
38
#endif
 
39
  pNew->copyKey = copyKey;
 
40
  pNew->first = 0;
 
41
  pNew->count = 0;
 
42
  pNew->htsize = 0;
 
43
  pNew->ht = 0;
 
44
}
 
45
 
 
46
/* Remove all entries from a hash table.  Reclaim all memory.
 
47
** Call this routine to delete a hash table or to reset a hash table
 
48
** to the empty state.
 
49
*/
 
50
void sqlite3HashClear(Hash *pH){
 
51
  HashElem *elem;         /* For looping over all elements of the table */
 
52
 
 
53
  assert( pH!=0 );
 
54
  elem = pH->first;
 
55
  pH->first = 0;
 
56
  if( pH->ht ) sqliteFree(pH->ht);
 
57
  pH->ht = 0;
 
58
  pH->htsize = 0;
 
59
  while( elem ){
 
60
    HashElem *next_elem = elem->next;
 
61
    if( pH->copyKey && elem->pKey ){
 
62
      sqliteFree(elem->pKey);
 
63
    }
 
64
    sqliteFree(elem);
 
65
    elem = next_elem;
 
66
  }
 
67
  pH->count = 0;
 
68
}
 
69
 
 
70
#if 0 /* NOT USED */
 
71
/*
 
72
** Hash and comparison functions when the mode is SQLITE_HASH_INT
 
73
*/
 
74
static int intHash(const void *pKey, int nKey){
 
75
  return nKey ^ (nKey<<8) ^ (nKey>>8);
 
76
}
 
77
static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
78
  return n2 - n1;
 
79
}
 
80
#endif
 
81
 
 
82
#if 0 /* NOT USED */
 
83
/*
 
84
** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
 
85
*/
 
86
static int ptrHash(const void *pKey, int nKey){
 
87
  uptr x = Addr(pKey);
 
88
  return x ^ (x<<8) ^ (x>>8);
 
89
}
 
90
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
91
  if( pKey1==pKey2 ) return 0;
 
92
  if( pKey1<pKey2 ) return -1;
 
93
  return 1;
 
94
}
 
95
#endif
 
96
 
 
97
/*
 
98
** Hash and comparison functions when the mode is SQLITE_HASH_STRING
 
99
*/
 
100
static int strHash(const void *pKey, int nKey){
 
101
  const char *z = (const char *)pKey;
 
102
  int h = 0;
 
103
  if( nKey<=0 ) nKey = strlen(z);
 
104
  while( nKey > 0  ){
 
105
    h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
 
106
    nKey--;
 
107
  }
 
108
  return h & 0x7fffffff;
 
109
}
 
110
static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
111
  if( n1!=n2 ) return 1;
 
112
  return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
 
113
}
 
114
 
 
115
/*
 
116
** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
 
117
*/
 
118
static int binHash(const void *pKey, int nKey){
 
119
  int h = 0;
 
120
  const char *z = (const char *)pKey;
 
121
  while( nKey-- > 0 ){
 
122
    h = (h<<3) ^ h ^ *(z++);
 
123
  }
 
124
  return h & 0x7fffffff;
 
125
}
 
126
static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 
127
  if( n1!=n2 ) return 1;
 
128
  return memcmp(pKey1,pKey2,n1);
 
129
}
 
130
 
 
131
/*
 
132
** Return a pointer to the appropriate hash function given the key class.
 
133
**
 
134
** The C syntax in this function definition may be unfamilar to some 
 
135
** programmers, so we provide the following additional explanation:
 
136
**
 
137
** The name of the function is "hashFunction".  The function takes a
 
138
** single parameter "keyClass".  The return value of hashFunction()
 
139
** is a pointer to another function.  Specifically, the return value
 
140
** of hashFunction() is a pointer to a function that takes two parameters
 
141
** with types "const void*" and "int" and returns an "int".
 
142
*/
 
143
static int (*hashFunction(int keyClass))(const void*,int){
 
144
#if 0  /* HASH_INT and HASH_POINTER are never used */
 
145
  switch( keyClass ){
 
146
    case SQLITE_HASH_INT:     return &intHash;
 
147
    case SQLITE_HASH_POINTER: return &ptrHash;
 
148
    case SQLITE_HASH_STRING:  return &strHash;
 
149
    case SQLITE_HASH_BINARY:  return &binHash;;
 
150
    default: break;
 
151
  }
 
152
  return 0;
 
153
#else
 
154
  if( keyClass==SQLITE_HASH_STRING ){
 
155
    return &strHash;
 
156
  }else{
 
157
    assert( keyClass==SQLITE_HASH_BINARY );
 
158
    return &binHash;
 
159
  }
 
160
#endif
 
161
}
 
162
 
 
163
/*
 
164
** Return a pointer to the appropriate hash function given the key class.
 
165
**
 
166
** For help in interpreted the obscure C code in the function definition,
 
167
** see the header comment on the previous function.
 
168
*/
 
169
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
 
170
#if 0 /* HASH_INT and HASH_POINTER are never used */
 
171
  switch( keyClass ){
 
172
    case SQLITE_HASH_INT:     return &intCompare;
 
173
    case SQLITE_HASH_POINTER: return &ptrCompare;
 
174
    case SQLITE_HASH_STRING:  return &strCompare;
 
175
    case SQLITE_HASH_BINARY:  return &binCompare;
 
176
    default: break;
 
177
  }
 
178
  return 0;
 
179
#else
 
180
  if( keyClass==SQLITE_HASH_STRING ){
 
181
    return &strCompare;
 
182
  }else{
 
183
    assert( keyClass==SQLITE_HASH_BINARY );
 
184
    return &binCompare;
 
185
  }
 
186
#endif
 
187
}
 
188
 
 
189
/* Link an element into the hash table
 
190
*/
 
191
static void insertElement(
 
192
  Hash *pH,              /* The complete hash table */
 
193
  struct _ht *pEntry,    /* The entry into which pNew is inserted */
 
194
  HashElem *pNew         /* The element to be inserted */
 
195
){
 
196
  HashElem *pHead;       /* First element already in pEntry */
 
197
  pHead = pEntry->chain;
 
198
  if( pHead ){
 
199
    pNew->next = pHead;
 
200
    pNew->prev = pHead->prev;
 
201
    if( pHead->prev ){ pHead->prev->next = pNew; }
 
202
    else             { pH->first = pNew; }
 
203
    pHead->prev = pNew;
 
204
  }else{
 
205
    pNew->next = pH->first;
 
206
    if( pH->first ){ pH->first->prev = pNew; }
 
207
    pNew->prev = 0;
 
208
    pH->first = pNew;
 
209
  }
 
210
  pEntry->count++;
 
211
  pEntry->chain = pNew;
 
212
}
 
213
 
 
214
 
 
215
/* Resize the hash table so that it cantains "new_size" buckets.
 
216
** "new_size" must be a power of 2.  The hash table might fail 
 
217
** to resize if sqliteMalloc() fails.
 
218
*/
 
219
static void rehash(Hash *pH, int new_size){
 
220
  struct _ht *new_ht;            /* The new hash table */
 
221
  HashElem *elem, *next_elem;    /* For looping over existing elements */
 
222
  int (*xHash)(const void*,int); /* The hash function */
 
223
 
 
224
  assert( (new_size & (new_size-1))==0 );
 
225
  new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
 
226
  if( new_ht==0 ) return;
 
227
  if( pH->ht ) sqliteFree(pH->ht);
 
228
  pH->ht = new_ht;
 
229
  pH->htsize = new_size;
 
230
  xHash = hashFunction(pH->keyClass);
 
231
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
 
232
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
 
233
    next_elem = elem->next;
 
234
    insertElement(pH, &new_ht[h], elem);
 
235
  }
 
236
}
 
237
 
 
238
/* This function (for internal use only) locates an element in an
 
239
** hash table that matches the given key.  The hash for this key has
 
240
** already been computed and is passed as the 4th parameter.
 
241
*/
 
242
static HashElem *findElementGivenHash(
 
243
  const Hash *pH,     /* The pH to be searched */
 
244
  const void *pKey,   /* The key we are searching for */
 
245
  int nKey,
 
246
  int h               /* The hash for this key. */
 
247
){
 
248
  HashElem *elem;                /* Used to loop thru the element list */
 
249
  int count;                     /* Number of elements left to test */
 
250
  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
 
251
 
 
252
  if( pH->ht ){
 
253
    struct _ht *pEntry = &pH->ht[h];
 
254
    elem = pEntry->chain;
 
255
    count = pEntry->count;
 
256
    xCompare = compareFunction(pH->keyClass);
 
257
    while( count-- && elem ){
 
258
      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
 
259
        return elem;
 
260
      }
 
261
      elem = elem->next;
 
262
    }
 
263
  }
 
264
  return 0;
 
265
}
 
266
 
 
267
/* Remove a single entry from the hash table given a pointer to that
 
268
** element and a hash on the element's key.
 
269
*/
 
270
static void removeElementGivenHash(
 
271
  Hash *pH,         /* The pH containing "elem" */
 
272
  HashElem* elem,   /* The element to be removed from the pH */
 
273
  int h             /* Hash value for the element */
 
274
){
 
275
  struct _ht *pEntry;
 
276
  if( elem->prev ){
 
277
    elem->prev->next = elem->next; 
 
278
  }else{
 
279
    pH->first = elem->next;
 
280
  }
 
281
  if( elem->next ){
 
282
    elem->next->prev = elem->prev;
 
283
  }
 
284
  pEntry = &pH->ht[h];
 
285
  if( pEntry->chain==elem ){
 
286
    pEntry->chain = elem->next;
 
287
  }
 
288
  pEntry->count--;
 
289
  if( pEntry->count<=0 ){
 
290
    pEntry->chain = 0;
 
291
  }
 
292
  if( pH->copyKey && elem->pKey ){
 
293
    sqliteFree(elem->pKey);
 
294
  }
 
295
  sqliteFree( elem );
 
296
  pH->count--;
 
297
}
 
298
 
 
299
/* Attempt to locate an element of the hash table pH with a key
 
300
** that matches pKey,nKey.  Return the data for this element if it is
 
301
** found, or NULL if there is no match.
 
302
*/
 
303
void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
 
304
  int h;             /* A hash on key */
 
305
  HashElem *elem;    /* The element that matches key */
 
306
  int (*xHash)(const void*,int);  /* The hash function */
 
307
 
 
308
  if( pH==0 || pH->ht==0 ) return 0;
 
309
  xHash = hashFunction(pH->keyClass);
 
310
  assert( xHash!=0 );
 
311
  h = (*xHash)(pKey,nKey);
 
312
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
313
  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
 
314
  return elem ? elem->data : 0;
 
315
}
 
316
 
 
317
/* Insert an element into the hash table pH.  The key is pKey,nKey
 
318
** and the data is "data".
 
319
**
 
320
** If no element exists with a matching key, then a new
 
321
** element is created.  A copy of the key is made if the copyKey
 
322
** flag is set.  NULL is returned.
 
323
**
 
324
** If another element already exists with the same key, then the
 
325
** new data replaces the old data and the old data is returned.
 
326
** The key is not copied in this instance.  If a malloc fails, then
 
327
** the new data is returned and the hash table is unchanged.
 
328
**
 
329
** If the "data" parameter to this function is NULL, then the
 
330
** element corresponding to "key" is removed from the hash table.
 
331
*/
 
332
void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
 
333
  int hraw;             /* Raw hash value of the key */
 
334
  int h;                /* the hash of the key modulo hash table size */
 
335
  HashElem *elem;       /* Used to loop thru the element list */
 
336
  HashElem *new_elem;   /* New element added to the pH */
 
337
  int (*xHash)(const void*,int);  /* The hash function */
 
338
 
 
339
  assert( pH!=0 );
 
340
  xHash = hashFunction(pH->keyClass);
 
341
  assert( xHash!=0 );
 
342
  hraw = (*xHash)(pKey, nKey);
 
343
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
344
  h = hraw & (pH->htsize-1);
 
345
  elem = findElementGivenHash(pH,pKey,nKey,h);
 
346
  if( elem ){
 
347
    void *old_data = elem->data;
 
348
    if( data==0 ){
 
349
      removeElementGivenHash(pH,elem,h);
 
350
    }else{
 
351
      elem->data = data;
 
352
    }
 
353
    return old_data;
 
354
  }
 
355
  if( data==0 ) return 0;
 
356
  new_elem = (HashElem*)sqliteMalloc( sizeof(HashElem) );
 
357
  if( new_elem==0 ) return data;
 
358
  if( pH->copyKey && pKey!=0 ){
 
359
    new_elem->pKey = sqliteMallocRaw( nKey );
 
360
    if( new_elem->pKey==0 ){
 
361
      sqliteFree(new_elem);
 
362
      return data;
 
363
    }
 
364
    memcpy((void*)new_elem->pKey, pKey, nKey);
 
365
  }else{
 
366
    new_elem->pKey = (void*)pKey;
 
367
  }
 
368
  new_elem->nKey = nKey;
 
369
  pH->count++;
 
370
  if( pH->htsize==0 ){
 
371
    rehash(pH,8);
 
372
    if( pH->htsize==0 ){
 
373
      pH->count = 0;
 
374
      sqliteFree(new_elem);
 
375
      return data;
 
376
    }
 
377
  }
 
378
  if( pH->count > pH->htsize ){
 
379
    rehash(pH,pH->htsize*2);
 
380
  }
 
381
  assert( pH->htsize>0 );
 
382
  assert( (pH->htsize & (pH->htsize-1))==0 );
 
383
  h = hraw & (pH->htsize-1);
 
384
  insertElement(pH, &pH->ht[h], new_elem);
 
385
  new_elem->data = data;
 
386
  return 0;
 
387
}