Line data Source code
1 : /**********************************************************************
2 : *
3 : * Name: tif_hash_set.c
4 : * Purpose: Hash set functions.
5 : * Author: Even Rouault, <even dot rouault at spatialys.com>
6 : *
7 : **********************************************************************
8 : * Copyright (c) 2008-2009, Even Rouault <even dot rouault at spatialys.com>
9 : *
10 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 :
29 : #include "tif_config.h"
30 :
31 : #include "tif_hash_set.h"
32 :
33 : #include <assert.h>
34 : #include <stdbool.h>
35 : #include <stdint.h>
36 : #include <stdio.h>
37 : #include <stdlib.h>
38 :
39 : /** List element structure. */
40 : typedef struct _TIFFList TIFFList;
41 :
42 : /** List element structure. */
43 : struct _TIFFList
44 : {
45 : /*! Pointer to the data object. Should be allocated and freed by the
46 : * caller.
47 : * */
48 : void *pData;
49 : /*! Pointer to the next element in list. NULL, if current element is the
50 : * last one.
51 : */
52 : struct _TIFFList *psNext;
53 : };
54 :
55 : struct _TIFFHashSet
56 : {
57 : TIFFHashSetHashFunc fnHashFunc;
58 : TIFFHashSetEqualFunc fnEqualFunc;
59 : TIFFHashSetFreeEltFunc fnFreeEltFunc;
60 : TIFFList **tabList;
61 : int nSize;
62 : int nIndiceAllocatedSize;
63 : int nAllocatedSize;
64 : TIFFList *psRecyclingList;
65 : int nRecyclingListSize;
66 : bool bRehash;
67 : #ifdef HASH_DEBUG
68 : int nCollisions;
69 : #endif
70 : };
71 :
72 : static const int anPrimes[] = {
73 : 53, 97, 193, 389, 769, 1543, 3079,
74 : 6151, 12289, 24593, 49157, 98317, 196613, 393241,
75 : 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
76 : 100663319, 201326611, 402653189, 805306457, 1610612741};
77 :
78 : /************************************************************************/
79 : /* TIFFHashSetHashPointer() */
80 : /************************************************************************/
81 :
82 : /**
83 : * Hash function for an arbitrary pointer
84 : *
85 : * @param elt the arbitrary pointer to hash
86 : *
87 : * @return the hash value of the pointer
88 : */
89 :
90 0 : static unsigned long TIFFHashSetHashPointer(const void *elt)
91 : {
92 0 : return (unsigned long)(uintptr_t)((void *)(elt));
93 : }
94 :
95 : /************************************************************************/
96 : /* TIFFHashSetEqualPointer() */
97 : /************************************************************************/
98 :
99 : /**
100 : * Equality function for arbitrary pointers
101 : *
102 : * @param elt1 the first arbitrary pointer to compare
103 : * @param elt2 the second arbitrary pointer to compare
104 : *
105 : * @return true if the pointers are equal
106 : */
107 :
108 0 : static bool TIFFHashSetEqualPointer(const void *elt1, const void *elt2)
109 : {
110 0 : return elt1 == elt2;
111 : }
112 :
113 : /************************************************************************/
114 : /* TIFFHashSetNew() */
115 : /************************************************************************/
116 :
117 : /**
118 : * Creates a new hash set
119 : *
120 : * The hash function must return a hash value for the elements to insert.
121 : * If fnHashFunc is NULL, TIFFHashSetHashPointer will be used.
122 : *
123 : * The equal function must return if two elements are equal.
124 : * If fnEqualFunc is NULL, TIFFHashSetEqualPointer will be used.
125 : *
126 : * The free function is used to free elements inserted in the hash set,
127 : * when the hash set is destroyed, when elements are removed or replaced.
128 : * If fnFreeEltFunc is NULL, elements inserted into the hash set will not be
129 : * freed.
130 : *
131 : * @param fnHashFunc hash function. May be NULL.
132 : * @param fnEqualFunc equal function. May be NULL.
133 : * @param fnFreeEltFunc element free function. May be NULL.
134 : *
135 : * @return a new hash set
136 : */
137 :
138 141314 : TIFFHashSet *TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,
139 : TIFFHashSetEqualFunc fnEqualFunc,
140 : TIFFHashSetFreeEltFunc fnFreeEltFunc)
141 : {
142 141314 : TIFFHashSet *set = (TIFFHashSet *)malloc(sizeof(TIFFHashSet));
143 141314 : if (set == NULL)
144 0 : return NULL;
145 141314 : set->fnHashFunc = fnHashFunc ? fnHashFunc : TIFFHashSetHashPointer;
146 141314 : set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : TIFFHashSetEqualPointer;
147 141314 : set->fnFreeEltFunc = fnFreeEltFunc;
148 141314 : set->nSize = 0;
149 141314 : set->tabList = (TIFFList **)(calloc(53, sizeof(TIFFList *)));
150 141314 : if (set->tabList == NULL)
151 : {
152 0 : free(set);
153 0 : return NULL;
154 : }
155 141314 : set->nIndiceAllocatedSize = 0;
156 141314 : set->nAllocatedSize = 53;
157 141314 : set->psRecyclingList = NULL;
158 141314 : set->nRecyclingListSize = 0;
159 141314 : set->bRehash = false;
160 : #ifdef HASH_DEBUG
161 : set->nCollisions = 0;
162 : #endif
163 141314 : return set;
164 : }
165 :
166 : /************************************************************************/
167 : /* TIFFHashSetSize() */
168 : /************************************************************************/
169 :
170 : /**
171 : * Returns the number of elements inserted in the hash set
172 : *
173 : * Note: this is not the internal size of the hash set
174 : *
175 : * @param set the hash set
176 : *
177 : * @return the number of elements in the hash set
178 : */
179 :
180 78306 : int TIFFHashSetSize(const TIFFHashSet *set)
181 : {
182 78306 : assert(set != NULL);
183 78306 : return set->nSize;
184 : }
185 :
186 : /************************************************************************/
187 : /* TIFFHashSetGetNewListElt() */
188 : /************************************************************************/
189 :
190 156831 : static TIFFList *TIFFHashSetGetNewListElt(TIFFHashSet *set)
191 : {
192 156831 : if (set->psRecyclingList)
193 : {
194 2974 : TIFFList *psRet = set->psRecyclingList;
195 2974 : psRet->pData = NULL;
196 2974 : set->nRecyclingListSize--;
197 2974 : set->psRecyclingList = psRet->psNext;
198 2974 : return psRet;
199 : }
200 :
201 153857 : return (TIFFList *)malloc(sizeof(TIFFList));
202 : }
203 :
204 : /************************************************************************/
205 : /* TIFFHashSetReturnListElt() */
206 : /************************************************************************/
207 :
208 2996 : static void TIFFHashSetReturnListElt(TIFFHashSet *set, TIFFList *psList)
209 : {
210 2996 : if (set->nRecyclingListSize < 128)
211 : {
212 2996 : psList->psNext = set->psRecyclingList;
213 2996 : set->psRecyclingList = psList;
214 2996 : set->nRecyclingListSize++;
215 : }
216 : else
217 : {
218 0 : free(psList);
219 : }
220 2996 : }
221 :
222 : /************************************************************************/
223 : /* TIFFHashSetClearInternal() */
224 : /************************************************************************/
225 :
226 141449 : static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)
227 : {
228 141449 : assert(set != NULL);
229 7636700 : for (int i = 0; i < set->nAllocatedSize; i++)
230 : {
231 7495240 : TIFFList *cur = set->tabList[i];
232 7649170 : while (cur)
233 : {
234 153920 : if (set->fnFreeEltFunc)
235 76962 : set->fnFreeEltFunc(cur->pData);
236 153924 : TIFFList *psNext = cur->psNext;
237 153924 : if (bFinalize)
238 153924 : free(cur);
239 : else
240 0 : TIFFHashSetReturnListElt(set, cur);
241 153924 : cur = psNext;
242 : }
243 7495250 : set->tabList[i] = NULL;
244 : }
245 141453 : set->bRehash = false;
246 141453 : }
247 :
248 : /************************************************************************/
249 : /* TIFFListDestroy() */
250 : /************************************************************************/
251 :
252 : /**
253 : * Destroy a list. Caller responsible for freeing data objects contained in
254 : * list elements.
255 : *
256 : * @param psList pointer to list head.
257 : *
258 : */
259 :
260 141450 : static void TIFFListDestroy(TIFFList *psList)
261 : {
262 141450 : TIFFList *psCurrent = psList;
263 :
264 141472 : while (psCurrent)
265 : {
266 22 : TIFFList *const psNext = psCurrent->psNext;
267 22 : free(psCurrent);
268 22 : psCurrent = psNext;
269 : }
270 141450 : }
271 :
272 : /************************************************************************/
273 : /* TIFFHashSetDestroy() */
274 : /************************************************************************/
275 :
276 : /**
277 : * Destroys an allocated hash set.
278 : *
279 : * This function also frees the elements if a free function was
280 : * provided at the creation of the hash set.
281 : *
282 : * @param set the hash set
283 : */
284 :
285 141446 : void TIFFHashSetDestroy(TIFFHashSet *set)
286 : {
287 141446 : if (set)
288 : {
289 141448 : TIFFHashSetClearInternal(set, true);
290 141450 : free(set->tabList);
291 141450 : TIFFListDestroy(set->psRecyclingList);
292 141449 : free(set);
293 : }
294 141447 : }
295 :
296 : #ifdef notused
297 : /************************************************************************/
298 : /* TIFFHashSetClear() */
299 : /************************************************************************/
300 :
301 : /**
302 : * Clear all elements from a hash set.
303 : *
304 : * This function also frees the elements if a free function was
305 : * provided at the creation of the hash set.
306 : *
307 : * @param set the hash set
308 : */
309 :
310 : void TIFFHashSetClear(TIFFHashSet *set)
311 : {
312 : TIFFHashSetClearInternal(set, false);
313 : set->nIndiceAllocatedSize = 0;
314 : set->nAllocatedSize = 53;
315 : #ifdef HASH_DEBUG
316 : set->nCollisions = 0;
317 : #endif
318 : set->nSize = 0;
319 : }
320 :
321 : /************************************************************************/
322 : /* TIFFHashSetForeach() */
323 : /************************************************************************/
324 :
325 : /**
326 : * Walk through the hash set and runs the provided function on all the
327 : * elements
328 : *
329 : * This function is provided the user_data argument of TIFFHashSetForeach.
330 : * It must return true to go on the walk through the hash set, or FALSE to
331 : * make it stop.
332 : *
333 : * Note : the structure of the hash set must *NOT* be modified during the
334 : * walk.
335 : *
336 : * @param set the hash set.
337 : * @param fnIterFunc the function called on each element.
338 : * @param user_data the user data provided to the function.
339 : */
340 :
341 : void TIFFHashSetForeach(TIFFHashSet *set, TIFFHashSetIterEltFunc fnIterFunc,
342 : void *user_data)
343 : {
344 : assert(set != NULL);
345 : if (!fnIterFunc)
346 : return;
347 :
348 : for (int i = 0; i < set->nAllocatedSize; i++)
349 : {
350 : TIFFList *cur = set->tabList[i];
351 : while (cur)
352 : {
353 : if (!fnIterFunc(cur->pData, user_data))
354 : return;
355 :
356 : cur = cur->psNext;
357 : }
358 : }
359 : }
360 : #endif
361 :
362 : /************************************************************************/
363 : /* TIFFHashSetRehash() */
364 : /************************************************************************/
365 :
366 0 : static bool TIFFHashSetRehash(TIFFHashSet *set)
367 : {
368 0 : int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
369 : TIFFList **newTabList =
370 0 : (TIFFList **)(calloc((size_t)nNewAllocatedSize, sizeof(TIFFList *)));
371 0 : if (newTabList == NULL)
372 0 : return false;
373 : #ifdef HASH_DEBUG
374 : TIFFDebug("TIFFHASH",
375 : "hashSet=%p, nSize=%d, nCollisions=%d, "
376 : "fCollisionRate=%.02f",
377 : set, set->nSize, set->nCollisions,
378 : set->nCollisions * 100.0 / set->nSize);
379 : set->nCollisions = 0;
380 : #endif
381 0 : for (int i = 0; i < set->nAllocatedSize; i++)
382 : {
383 0 : TIFFList *cur = set->tabList[i];
384 0 : while (cur)
385 : {
386 0 : const unsigned long nNewHashVal =
387 0 : set->fnHashFunc(cur->pData) % (unsigned long)nNewAllocatedSize;
388 : #ifdef HASH_DEBUG
389 : if (newTabList[nNewHashVal])
390 : set->nCollisions++;
391 : #endif
392 0 : TIFFList *psNext = cur->psNext;
393 0 : cur->psNext = newTabList[nNewHashVal];
394 0 : newTabList[nNewHashVal] = cur;
395 0 : cur = psNext;
396 : }
397 : }
398 0 : free(set->tabList);
399 0 : set->tabList = newTabList;
400 0 : set->nAllocatedSize = nNewAllocatedSize;
401 0 : set->bRehash = false;
402 0 : return true;
403 : }
404 :
405 : /************************************************************************/
406 : /* TIFFHashSetFindPtr() */
407 : /************************************************************************/
408 :
409 380584 : static void **TIFFHashSetFindPtr(TIFFHashSet *set, const void *elt)
410 : {
411 380641 : const unsigned long nHashVal =
412 380584 : set->fnHashFunc(elt) % (unsigned long)set->nAllocatedSize;
413 380641 : TIFFList *cur = set->tabList[nHashVal];
414 381330 : while (cur)
415 : {
416 65804 : if (set->fnEqualFunc(cur->pData, elt))
417 65115 : return &cur->pData;
418 689 : cur = cur->psNext;
419 : }
420 315526 : return NULL;
421 : }
422 :
423 : /************************************************************************/
424 : /* TIFFHashSetInsert() */
425 : /************************************************************************/
426 :
427 : /**
428 : * Inserts an element into a hash set.
429 : *
430 : * If the element was already inserted in the hash set, the previous
431 : * element is replaced by the new element. If a free function was provided,
432 : * it is used to free the previously inserted element
433 : *
434 : * @param set the hash set
435 : * @param elt the new element to insert in the hash set
436 : *
437 : * @return true if success. If false is returned, elt has not been inserted,
438 : * but TIFFHashSetInsert() will have run the free function if provided.
439 : */
440 :
441 156869 : bool TIFFHashSetInsert(TIFFHashSet *set, void *elt)
442 : {
443 156869 : assert(set != NULL);
444 156869 : void **pElt = TIFFHashSetFindPtr(set, elt);
445 156888 : if (pElt)
446 : {
447 0 : if (set->fnFreeEltFunc)
448 0 : set->fnFreeEltFunc(*pElt);
449 :
450 0 : *pElt = elt;
451 0 : return true;
452 : }
453 :
454 156888 : if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
455 156873 : (set->bRehash && set->nIndiceAllocatedSize > 0 &&
456 0 : set->nSize <= set->nAllocatedSize / 2))
457 : {
458 15 : set->nIndiceAllocatedSize++;
459 15 : if (!TIFFHashSetRehash(set))
460 : {
461 0 : set->nIndiceAllocatedSize--;
462 0 : if (set->fnFreeEltFunc)
463 0 : set->fnFreeEltFunc(elt);
464 0 : return false;
465 : }
466 : }
467 :
468 156839 : const unsigned long nHashVal =
469 156873 : set->fnHashFunc(elt) % (unsigned long)set->nAllocatedSize;
470 : #ifdef HASH_DEBUG
471 : if (set->tabList[nHashVal])
472 : set->nCollisions++;
473 : #endif
474 :
475 156839 : TIFFList *new_elt = TIFFHashSetGetNewListElt(set);
476 156892 : if (new_elt == NULL)
477 : {
478 0 : if (set->fnFreeEltFunc)
479 0 : set->fnFreeEltFunc(elt);
480 0 : return false;
481 : }
482 156892 : new_elt->pData = elt;
483 156892 : new_elt->psNext = set->tabList[nHashVal];
484 156892 : set->tabList[nHashVal] = new_elt;
485 156892 : set->nSize++;
486 :
487 156892 : return true;
488 : }
489 :
490 : /************************************************************************/
491 : /* TIFFHashSetLookup() */
492 : /************************************************************************/
493 :
494 : /**
495 : * Returns the element found in the hash set corresponding to the element to
496 : * look up The element must not be modified.
497 : *
498 : * @param set the hash set
499 : * @param elt the element to look up in the hash set
500 : *
501 : * @return the element found in the hash set or NULL
502 : */
503 :
504 223729 : void *TIFFHashSetLookup(TIFFHashSet *set, const void *elt)
505 : {
506 223729 : assert(set != NULL);
507 223729 : void **pElt = TIFFHashSetFindPtr(set, elt);
508 223781 : if (pElt)
509 65115 : return *pElt;
510 :
511 158666 : return NULL;
512 : }
513 :
514 : /************************************************************************/
515 : /* TIFFHashSetRemoveInternal() */
516 : /************************************************************************/
517 :
518 2996 : static bool TIFFHashSetRemoveInternal(TIFFHashSet *set, const void *elt,
519 : bool bDeferRehash)
520 : {
521 2996 : assert(set != NULL);
522 2996 : if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
523 : {
524 0 : set->nIndiceAllocatedSize--;
525 0 : if (bDeferRehash)
526 0 : set->bRehash = true;
527 : else
528 : {
529 0 : if (!TIFFHashSetRehash(set))
530 : {
531 0 : set->nIndiceAllocatedSize++;
532 0 : return false;
533 : }
534 : }
535 : }
536 :
537 2996 : int nHashVal =
538 2996 : (int)(set->fnHashFunc(elt) % (unsigned long)set->nAllocatedSize);
539 2996 : TIFFList *cur = set->tabList[nHashVal];
540 2996 : TIFFList *prev = NULL;
541 2996 : while (cur)
542 : {
543 2996 : if (set->fnEqualFunc(cur->pData, elt))
544 : {
545 2996 : if (prev)
546 0 : prev->psNext = cur->psNext;
547 : else
548 2996 : set->tabList[nHashVal] = cur->psNext;
549 :
550 2996 : if (set->fnFreeEltFunc)
551 1498 : set->fnFreeEltFunc(cur->pData);
552 :
553 2996 : TIFFHashSetReturnListElt(set, cur);
554 : #ifdef HASH_DEBUG
555 : if (set->tabList[nHashVal])
556 : set->nCollisions--;
557 : #endif
558 2996 : set->nSize--;
559 2996 : return true;
560 : }
561 0 : prev = cur;
562 0 : cur = cur->psNext;
563 : }
564 0 : return false;
565 : }
566 :
567 : /************************************************************************/
568 : /* TIFFHashSetRemove() */
569 : /************************************************************************/
570 :
571 : /**
572 : * Removes an element from a hash set
573 : *
574 : * @param set the hash set
575 : * @param elt the new element to remove from the hash set
576 : *
577 : * @return true if the element was in the hash set
578 : */
579 :
580 2996 : bool TIFFHashSetRemove(TIFFHashSet *set, const void *elt)
581 : {
582 2996 : return TIFFHashSetRemoveInternal(set, elt, false);
583 : }
584 :
585 : #ifdef notused
586 : /************************************************************************/
587 : /* TIFFHashSetRemoveDeferRehash() */
588 : /************************************************************************/
589 :
590 : /**
591 : * Removes an element from a hash set.
592 : *
593 : * This will defer potential rehashing of the set to later calls to
594 : * TIFFHashSetInsert() or TIFFHashSetRemove().
595 : *
596 : * @param set the hash set
597 : * @param elt the new element to remove from the hash set
598 : *
599 : * @return true if the element was in the hash set
600 : */
601 :
602 : bool TIFFHashSetRemoveDeferRehash(TIFFHashSet *set, const void *elt)
603 : {
604 : return TIFFHashSetRemoveInternal(set, elt, true);
605 : }
606 : #endif
|
