← Back to branch summary

~ubuntu-branches/ubuntu/feisty/digikam/feisty

« back to all changes in this revision

Viewing changes to digikam/sqlite/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Achim Bohnet
  • Date: 2005-03-10 02:39:02 UTC
  • mfrom: (1.2.1 upstream) (2.1.1 hoary)
  • Revision ID: james.westby@ubuntu.com-20050310023902-023nymfst5mg696c
Tags: 0.7.2-2
* debian/TODO: clean
* digikam manpage: better --detect-camera description

Show diffs side-by-side

added added

removed removed

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