1 : /**********************************************************************
2 : * $Id: cpl_hash_set.cpp 16029 2009-01-01 19:32:39Z rouault $
3 : *
4 : * Name: cpl_hash_set.cpp
5 : * Project: CPL - Common Portability Library
6 : * Purpose: Hash set functions.
7 : * Author: Even Rouault, <even dot rouault at mines dash paris dot org>
8 : *
9 : **********************************************************************
10 : * Copyright (c) 2008, Even Rouault, <even dot rouault at mines dash paris dot org>
11 : *
12 : * Permission is hereby granted, free of charge, to any person obtaining a
13 : * copy of this software and associated documentation files (the "Software"),
14 : * to deal in the Software without restriction, including without limitation
15 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 : * and/or sell copies of the Software, and to permit persons to whom the
17 : * Software is furnished to do so, subject to the following conditions:
18 : *
19 : * The above copyright notice and this permission notice shall be included
20 : * in all copies or substantial portions of the Software.
21 : *
22 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
25 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
28 : * DEALINGS IN THE SOFTWARE.
29 : ****************************************************************************/
30 :
31 : #include "cpl_conv.h"
32 : #include "cpl_hash_set.h"
33 : #include "cpl_list.h"
34 :
35 : struct _CPLHashSet
36 : {
37 : CPLHashSetHashFunc fnHashFunc;
38 : CPLHashSetEqualFunc fnEqualFunc;
39 : CPLHashSetFreeEltFunc fnFreeEltFunc;
40 : CPLList** tabList;
41 : int nSize;
42 : int nIndiceAllocatedSize;
43 : int nAllocatedSize;
44 : #ifdef HASH_DEBUG
45 : int nCollisions;
46 : #endif
47 : };
48 :
49 : static const int anPrimes[] =
50 : { 53, 97, 193, 389, 769, 1543, 3079, 6151,
51 : 12289, 24593, 49157, 98317, 196613, 393241,
52 : 786433, 1572869, 3145739, 6291469, 12582917,
53 : 25165843, 50331653, 100663319, 201326611,
54 : 402653189, 805306457, 1610612741 };
55 :
56 : /************************************************************************/
57 : /* CPLHashSetNew() */
58 : /************************************************************************/
59 :
60 : /**
61 : * Creates a new hash set
62 : *
63 : * The hash function must return a hash value for the elements to insert.
64 : * If fnHashFunc is NULL, CPLHashSetHashPointer will be used.
65 : *
66 : * The equal function must return if two elements are equal.
67 : * If fnEqualFunc is NULL, CPLHashSetEqualPointer will be used.
68 : *
69 : * The free function is used to free elements inserted in the hash set,
70 : * when the hash set is destroyed, when elements are removed or replaced.
71 : * If fnFreeEltFunc is NULL, elements inserted into the hash set will not be freed.
72 : *
73 : * @param fnHashFunc hash function. May be NULL.
74 : * @param fnEqualFunc equal function. May be NULL.
75 : * @param fnFreeEltFunc element free function. May be NULL.
76 : *
77 : * @return a new hash set
78 : */
79 :
80 3198 : CPLHashSet* CPLHashSetNew(CPLHashSetHashFunc fnHashFunc,
81 : CPLHashSetEqualFunc fnEqualFunc,
82 : CPLHashSetFreeEltFunc fnFreeEltFunc)
83 : {
84 3198 : CPLHashSet* set = (CPLHashSet*) CPLMalloc(sizeof(CPLHashSet));
85 3198 : set->fnHashFunc = (fnHashFunc) ? fnHashFunc : CPLHashSetHashPointer;
86 3198 : set->fnEqualFunc = (fnEqualFunc) ? fnEqualFunc : CPLHashSetEqualPointer;
87 3198 : set->fnFreeEltFunc = fnFreeEltFunc;
88 3198 : set->nSize = 0;
89 3198 : set->tabList = (CPLList**) CPLCalloc(sizeof(CPLList*), 53);
90 3198 : set->nIndiceAllocatedSize = 0;
91 3198 : set->nAllocatedSize = 53;
92 : #ifdef HASH_DEBUG
93 : set->nCollisions = 0;
94 : #endif
95 3198 : return set;
96 : }
97 :
98 :
99 : /************************************************************************/
100 : /* CPLHashSetSize() */
101 : /************************************************************************/
102 :
103 : /**
104 : * Returns the number of elements inserted in the hash set
105 : *
106 : * Note: this is not the internal size of the hash set
107 : *
108 : * @param set the hash set
109 : *
110 : * @return the number of elements in the hash set
111 : */
112 :
113 11858 : int CPLHashSetSize(const CPLHashSet* set)
114 : {
115 : CPLAssert(set != NULL);
116 11858 : return set->nSize;
117 : }
118 :
119 : /************************************************************************/
120 : /* CPLHashSetDestroy() */
121 : /************************************************************************/
122 :
123 : /**
124 : * Destroys an allocated hash set.
125 : *
126 : * This function also frees the elements if a free function was
127 : * provided at the creation of the hash set.
128 : *
129 : * @param set the hash set
130 : */
131 :
132 3196 : void CPLHashSetDestroy(CPLHashSet* set)
133 : {
134 : CPLAssert(set != NULL);
135 172584 : for(int i=0;i<set->nAllocatedSize;i++)
136 : {
137 169388 : if (set->fnFreeEltFunc)
138 : {
139 169388 : CPLList* cur = set->tabList[i];
140 339417 : while(cur)
141 : {
142 641 : set->fnFreeEltFunc(cur->pData);
143 641 : cur = cur->psNext;
144 : }
145 : }
146 169388 : CPLListDestroy(set->tabList[i]);
147 : }
148 3196 : CPLFree(set->tabList);
149 3196 : CPLFree(set);
150 3196 : }
151 :
152 : /************************************************************************/
153 : /* CPLHashSetForeach() */
154 : /************************************************************************/
155 :
156 :
157 : /**
158 : * Walk through the hash set and runs the provided function on all the
159 : * elements
160 : *
161 : * This function is provided the user_data argument of CPLHashSetForeach.
162 : * It must return TRUE to go on the walk through the hash set, or FALSE to
163 : * make it stop.
164 : *
165 : * Note : the structure of the hash set must *NOT* be modified during the
166 : * walk.
167 : *
168 : * @param set the hash set.
169 : * @param fnIterFunc the function called on each element.
170 : * @param user_data the user data provided to the function.
171 : */
172 :
173 0 : void CPLHashSetForeach(CPLHashSet* set,
174 : CPLHashSetIterEltFunc fnIterFunc,
175 : void* user_data)
176 : {
177 : CPLAssert(set != NULL);
178 0 : if (!fnIterFunc) return;
179 :
180 0 : for(int i=0;i<set->nAllocatedSize;i++)
181 : {
182 0 : CPLList* cur = set->tabList[i];
183 0 : while(cur)
184 : {
185 0 : if (fnIterFunc(cur->pData, user_data) == FALSE)
186 0 : return;
187 :
188 0 : cur = cur->psNext;
189 : }
190 : }
191 : }
192 :
193 : /************************************************************************/
194 : /* CPLHashSetRehash() */
195 : /************************************************************************/
196 :
197 16 : static void CPLHashSetRehash(CPLHashSet* set)
198 : {
199 16 : int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
200 16 : CPLList** newTabList = (CPLList**) CPLCalloc(sizeof(CPLList*), nNewAllocatedSize);
201 : #ifdef HASH_DEBUG
202 : CPLDebug("CPLHASH", "hashSet=%p, nSize=%d, nCollisions=%d, fCollisionRate=%.02f",
203 : set, set->nSize, set->nCollisions, set->nCollisions * 100.0 / set->nSize);
204 : set->nCollisions = 0;
205 : #endif
206 36800 : for(int i=0;i<set->nAllocatedSize;i++)
207 : {
208 36784 : CPLList* cur = set->tabList[i];
209 92853 : while(cur)
210 : {
211 19285 : unsigned long nNewHashVal = set->fnHashFunc(cur->pData) % nNewAllocatedSize;
212 : #ifdef HASH_DEBUG
213 : if (newTabList[nNewHashVal])
214 : set->nCollisions ++;
215 : #endif
216 19285 : newTabList[nNewHashVal] = CPLListInsert(newTabList[nNewHashVal], cur->pData, 0);
217 19285 : cur = cur->psNext;
218 : }
219 36784 : CPLListDestroy(set->tabList[i]);
220 : }
221 16 : CPLFree(set->tabList);
222 16 : set->tabList = newTabList;
223 16 : set->nAllocatedSize = nNewAllocatedSize;
224 16 : }
225 :
226 :
227 : /************************************************************************/
228 : /* CPLHashSetFindPtr() */
229 : /************************************************************************/
230 :
231 31337 : static void** CPLHashSetFindPtr(CPLHashSet* set, const void* elt)
232 : {
233 31337 : unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
234 31337 : CPLList* cur = set->tabList[nHashVal];
235 66455 : while(cur)
236 : {
237 21460 : if (set->fnEqualFunc(cur->pData, elt))
238 17679 : return &cur->pData;
239 3781 : cur = cur->psNext;
240 : }
241 13658 : return NULL;
242 : }
243 :
244 : /************************************************************************/
245 : /* CPLHashSetInsert() */
246 : /************************************************************************/
247 :
248 : /**
249 : * Inserts an element into a hash set.
250 : *
251 : * If the element was already inserted in the hash set, the previous
252 : * element is replaced by the new element. If a free function was provided,
253 : * it is used to free the previously inserted element
254 : *
255 : * @param set the hash set
256 : * @param elt the new element to insert in the hash set
257 : *
258 : * @return TRUE if the element was not already in the hash set
259 : */
260 :
261 12639 : int CPLHashSetInsert(CPLHashSet* set, void* elt)
262 : {
263 : CPLAssert(set != NULL);
264 12639 : void** pElt = CPLHashSetFindPtr(set, elt);
265 12639 : if (pElt)
266 : {
267 0 : if (set->fnFreeEltFunc)
268 0 : set->fnFreeEltFunc(*pElt);
269 :
270 0 : *pElt = elt;
271 0 : return FALSE;
272 : }
273 :
274 12639 : if (set->nSize >= 2 * set->nAllocatedSize / 3)
275 : {
276 8 : set->nIndiceAllocatedSize++;
277 8 : CPLHashSetRehash(set);
278 : }
279 :
280 12639 : unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
281 : #ifdef HASH_DEBUG
282 : if (set->tabList[nHashVal])
283 : set->nCollisions ++;
284 : #endif
285 12639 : set->tabList[nHashVal] = CPLListInsert(set->tabList[nHashVal], (void*) elt, 0);
286 12639 : set->nSize++;
287 :
288 12639 : return TRUE;
289 : }
290 :
291 : /************************************************************************/
292 : /* CPLHashSetLookup() */
293 : /************************************************************************/
294 :
295 : /**
296 : * Returns the element found in the hash set corresponding to the element to look up
297 : * The element must not be modified.
298 : *
299 : * @param set the hash set
300 : * @param elt the element to look up in the hash set
301 : *
302 : * @return the element found in the hash set or NULL
303 : */
304 :
305 18698 : void* CPLHashSetLookup(CPLHashSet* set, const void* elt)
306 : {
307 : CPLAssert(set != NULL);
308 18698 : void** pElt = CPLHashSetFindPtr(set, elt);
309 18698 : if (pElt)
310 17679 : return *pElt;
311 : else
312 1019 : return NULL;
313 : }
314 :
315 : /************************************************************************/
316 : /* CPLHashSetRemove() */
317 : /************************************************************************/
318 :
319 : /**
320 : * Removes an element from a hash set
321 : *
322 : * @param set the hash set
323 : * @param elt the new element to remove from the hash set
324 : *
325 : * @return TRUE if the element was in the hash set
326 : */
327 :
328 11997 : int CPLHashSetRemove(CPLHashSet* set, const void* elt)
329 : {
330 : CPLAssert(set != NULL);
331 11997 : if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
332 : {
333 8 : set->nIndiceAllocatedSize--;
334 8 : CPLHashSetRehash(set);
335 : }
336 :
337 11997 : int nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
338 11997 : CPLList* cur = set->tabList[nHashVal];
339 11997 : CPLList* prev = NULL;
340 25271 : while(cur)
341 : {
342 13274 : if (set->fnEqualFunc(cur->pData, elt))
343 : {
344 11997 : if (prev)
345 1071 : prev->psNext = cur->psNext;
346 : else
347 10926 : set->tabList[nHashVal] = cur->psNext;
348 :
349 11997 : if (set->fnFreeEltFunc)
350 11997 : set->fnFreeEltFunc(cur->pData);
351 :
352 11997 : CPLFree(cur);
353 : #ifdef HASH_DEBUG
354 : if (set->tabList[nHashVal])
355 : set->nCollisions --;
356 : #endif
357 :
358 11997 : set->nSize--;
359 11997 : return TRUE;
360 : }
361 1277 : prev = cur;
362 1277 : cur = cur->psNext;
363 : }
364 0 : return FALSE;
365 : }
366 :
367 :
368 : /************************************************************************/
369 : /* CPLHashSetHashPointer() */
370 : /************************************************************************/
371 :
372 : /**
373 : * Hash function for an arbitrary pointer
374 : *
375 : * @param elt the arbitrary pointer to hash
376 : *
377 : * @return the hash value of the pointer
378 : */
379 :
380 0 : unsigned long CPLHashSetHashPointer(const void* elt)
381 : {
382 0 : return (unsigned long)elt;
383 : }
384 :
385 : /************************************************************************/
386 : /* CPLHashSetEqualPointer() */
387 : /************************************************************************/
388 :
389 : /**
390 : * Equality function for arbitrary pointers
391 : *
392 : * @param elt1 the first arbitrary pointer to compare
393 : * @param elt2 the second arbitrary pointer to compare
394 : *
395 : * @return TRUE if the pointers are equal
396 : */
397 :
398 0 : int CPLHashSetEqualPointer(const void* elt1, const void* elt2)
399 : {
400 0 : return elt1 == elt2;
401 : }
402 :
403 : /************************************************************************/
404 : /* CPLHashSetHashStr() */
405 : /************************************************************************/
406 :
407 : /**
408 : * Hash function for a zero-terminated string
409 : *
410 : * @param elt the string to hash. May be NULL.
411 : *
412 : * @return the hash value of the string
413 : */
414 :
415 8400 : unsigned long CPLHashSetHashStr(const void *elt)
416 : {
417 8400 : unsigned char* pszStr = (unsigned char*)elt;
418 8400 : unsigned long hash = 0;
419 : int c;
420 :
421 8400 : if (pszStr == NULL)
422 0 : return 0;
423 :
424 136182 : while ((c = *pszStr++) != '\0')
425 119382 : hash = c + (hash << 6) + (hash << 16) - hash;
426 :
427 8400 : return hash;
428 : }
429 :
430 : /************************************************************************/
431 : /* CPLHashSetEqualStr() */
432 : /************************************************************************/
433 :
434 : /**
435 : * Equality function for strings
436 : *
437 : * @param elt1 the first string to compare. May be NULL.
438 : * @param elt2 the second string to compare. May be NULL.
439 : *
440 : * @return TRUE if the strings are equal
441 : */
442 :
443 22 : int CPLHashSetEqualStr(const void* elt1, const void* elt2)
444 : {
445 22 : const char* pszStr1 = (const char*)elt1;
446 22 : const char* pszStr2 = (const char*)elt2;
447 22 : if (pszStr1 == NULL && pszStr2 != NULL)
448 0 : return FALSE;
449 22 : else if (pszStr1 != NULL && pszStr2 == NULL)
450 0 : return FALSE;
451 22 : else if (pszStr1 == NULL && pszStr2 == NULL)
452 0 : return TRUE;
453 : else
454 22 : return strcmp(pszStr1, pszStr2) == 0;
455 : }
|
