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