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 123976 : TIFFHashSet *TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,
139 : TIFFHashSetEqualFunc fnEqualFunc,
140 : TIFFHashSetFreeEltFunc fnFreeEltFunc)
141 : {
142 123976 : TIFFHashSet *set = (TIFFHashSet *)malloc(sizeof(TIFFHashSet));
143 123976 : if (set == NULL)
144 0 : return NULL;
145 123976 : set->fnHashFunc = fnHashFunc ? fnHashFunc : TIFFHashSetHashPointer;
146 123976 : set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : TIFFHashSetEqualPointer;
147 123976 : set->fnFreeEltFunc = fnFreeEltFunc;
148 123976 : set->nSize = 0;
149 123976 : set->tabList = (TIFFList **)(calloc(53, sizeof(TIFFList *)));
150 123976 : if (set->tabList == NULL)
151 : {
152 0 : free(set);
153 0 : return NULL;
154 : }
155 123976 : set->nIndiceAllocatedSize = 0;
156 123976 : set->nAllocatedSize = 53;
157 123976 : set->psRecyclingList = NULL;
158 123976 : set->nRecyclingListSize = 0;
159 123976 : set->bRehash = false;
160 : #ifdef HASH_DEBUG
161 : set->nCollisions = 0;
162 : #endif
163 123976 : 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 68820 : int TIFFHashSetSize(const TIFFHashSet *set)
181 : {
182 68820 : assert(set != NULL);
183 68820 : return set->nSize;
184 : }
185 :
186 : /************************************************************************/
187 : /* TIFFHashSetGetNewListElt() */
188 : /************************************************************************/
189 :
190 137688 : static TIFFList *TIFFHashSetGetNewListElt(TIFFHashSet *set)
191 : {
192 137688 : if (set->psRecyclingList)
193 : {
194 2682 : TIFFList *psRet = set->psRecyclingList;
195 2682 : psRet->pData = NULL;
196 2682 : set->nRecyclingListSize--;
197 2682 : set->psRecyclingList = psRet->psNext;
198 2682 : return psRet;
199 : }
200 :
201 135006 : return (TIFFList *)malloc(sizeof(TIFFList));
202 : }
203 :
204 : /************************************************************************/
205 : /* TIFFHashSetReturnListElt() */
206 : /************************************************************************/
207 :
208 2702 : static void TIFFHashSetReturnListElt(TIFFHashSet *set, TIFFList *psList)
209 : {
210 2702 : if (set->nRecyclingListSize < 128)
211 : {
212 2702 : psList->psNext = set->psRecyclingList;
213 2702 : set->psRecyclingList = psList;
214 2702 : set->nRecyclingListSize++;
215 : }
216 : else
217 : {
218 0 : free(psList);
219 : }
220 2702 : }
221 :
222 : /************************************************************************/
223 : /* TIFFHashSetClearInternal() */
224 : /************************************************************************/
225 :
226 124069 : static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)
227 : {
228 124069 : assert(set != NULL);
229 6697550 : for (int i = 0; i < set->nAllocatedSize; i++)
230 : {
231 6573480 : TIFFList *cur = set->tabList[i];
232 6708560 : while (cur)
233 : {
234 135079 : if (set->fnFreeEltFunc)
235 67539 : set->fnFreeEltFunc(cur->pData);
236 135081 : TIFFList *psNext = cur->psNext;
237 135081 : if (bFinalize)
238 135081 : free(cur);
239 : else
240 0 : TIFFHashSetReturnListElt(set, cur);
241 135083 : cur = psNext;
242 : }
243 6573480 : set->tabList[i] = NULL;
244 : }
245 124073 : set->bRehash = false;
246 124073 : }
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 124073 : static void TIFFListDestroy(TIFFList *psList)
261 : {
262 124073 : TIFFList *psCurrent = psList;
263 :
264 124093 : while (psCurrent)
265 : {
266 20 : TIFFList *const psNext = psCurrent->psNext;
267 20 : free(psCurrent);
268 20 : psCurrent = psNext;
269 : }
270 124073 : }
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 124070 : void TIFFHashSetDestroy(TIFFHashSet *set)
286 : {
287 124070 : if (set)
288 : {
289 124069 : TIFFHashSetClearInternal(set, true);
290 124075 : free(set->tabList);
291 124075 : TIFFListDestroy(set->psRecyclingList);
292 124074 : free(set);
293 : }
294 124075 : }
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(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) % 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 327585 : static void **TIFFHashSetFindPtr(TIFFHashSet *set, const void *elt)
410 : {
411 327585 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
412 327535 : TIFFList *cur = set->tabList[nHashVal];
413 328163 : while (cur)
414 : {
415 51253 : if (set->fnEqualFunc(cur->pData, elt))
416 50625 : return &cur->pData;
417 628 : cur = cur->psNext;
418 : }
419 276910 : return NULL;
420 : }
421 :
422 : /************************************************************************/
423 : /* TIFFHashSetInsert() */
424 : /************************************************************************/
425 :
426 : /**
427 : * Inserts an element into a hash set.
428 : *
429 : * If the element was already inserted in the hash set, the previous
430 : * element is replaced by the new element. If a free function was provided,
431 : * it is used to free the previously inserted element
432 : *
433 : * @param set the hash set
434 : * @param elt the new element to insert in the hash set
435 : *
436 : * @return true if success. If false is returned, elt has not been inserted,
437 : * but TIFFHashSetInsert() will have run the free function if provided.
438 : */
439 :
440 137643 : bool TIFFHashSetInsert(TIFFHashSet *set, void *elt)
441 : {
442 137643 : assert(set != NULL);
443 137643 : void **pElt = TIFFHashSetFindPtr(set, elt);
444 137653 : if (pElt)
445 : {
446 0 : if (set->fnFreeEltFunc)
447 0 : set->fnFreeEltFunc(*pElt);
448 :
449 0 : *pElt = elt;
450 0 : return true;
451 : }
452 :
453 137653 : if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
454 137696 : (set->bRehash && set->nIndiceAllocatedSize > 0 &&
455 0 : set->nSize <= set->nAllocatedSize / 2))
456 : {
457 0 : set->nIndiceAllocatedSize++;
458 0 : if (!TIFFHashSetRehash(set))
459 : {
460 0 : set->nIndiceAllocatedSize--;
461 0 : if (set->fnFreeEltFunc)
462 0 : set->fnFreeEltFunc(elt);
463 0 : return false;
464 : }
465 : }
466 :
467 137696 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
468 : #ifdef HASH_DEBUG
469 : if (set->tabList[nHashVal])
470 : set->nCollisions++;
471 : #endif
472 :
473 137715 : TIFFList *new_elt = TIFFHashSetGetNewListElt(set);
474 137638 : if (new_elt == NULL)
475 : {
476 0 : if (set->fnFreeEltFunc)
477 0 : set->fnFreeEltFunc(elt);
478 0 : return false;
479 : }
480 137638 : new_elt->pData = elt;
481 137638 : new_elt->psNext = set->tabList[nHashVal];
482 137638 : set->tabList[nHashVal] = new_elt;
483 137638 : set->nSize++;
484 :
485 137638 : return true;
486 : }
487 :
488 : /************************************************************************/
489 : /* TIFFHashSetLookup() */
490 : /************************************************************************/
491 :
492 : /**
493 : * Returns the element found in the hash set corresponding to the element to
494 : * look up The element must not be modified.
495 : *
496 : * @param set the hash set
497 : * @param elt the element to look up in the hash set
498 : *
499 : * @return the element found in the hash set or NULL
500 : */
501 :
502 189914 : void *TIFFHashSetLookup(TIFFHashSet *set, const void *elt)
503 : {
504 189914 : assert(set != NULL);
505 189914 : void **pElt = TIFFHashSetFindPtr(set, elt);
506 189871 : if (pElt)
507 50625 : return *pElt;
508 :
509 139246 : return NULL;
510 : }
511 :
512 : /************************************************************************/
513 : /* TIFFHashSetRemoveInternal() */
514 : /************************************************************************/
515 :
516 2702 : static bool TIFFHashSetRemoveInternal(TIFFHashSet *set, const void *elt,
517 : bool bDeferRehash)
518 : {
519 2702 : assert(set != NULL);
520 2702 : if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
521 : {
522 0 : set->nIndiceAllocatedSize--;
523 0 : if (bDeferRehash)
524 0 : set->bRehash = true;
525 : else
526 : {
527 0 : if (!TIFFHashSetRehash(set))
528 : {
529 0 : set->nIndiceAllocatedSize++;
530 0 : return false;
531 : }
532 : }
533 : }
534 :
535 2702 : int nHashVal = (int)(set->fnHashFunc(elt) % set->nAllocatedSize);
536 2702 : TIFFList *cur = set->tabList[nHashVal];
537 2702 : TIFFList *prev = NULL;
538 2702 : while (cur)
539 : {
540 2702 : if (set->fnEqualFunc(cur->pData, elt))
541 : {
542 2702 : if (prev)
543 0 : prev->psNext = cur->psNext;
544 : else
545 2702 : set->tabList[nHashVal] = cur->psNext;
546 :
547 2702 : if (set->fnFreeEltFunc)
548 1351 : set->fnFreeEltFunc(cur->pData);
549 :
550 2702 : TIFFHashSetReturnListElt(set, cur);
551 : #ifdef HASH_DEBUG
552 : if (set->tabList[nHashVal])
553 : set->nCollisions--;
554 : #endif
555 2702 : set->nSize--;
556 2702 : return true;
557 : }
558 0 : prev = cur;
559 0 : cur = cur->psNext;
560 : }
561 0 : return false;
562 : }
563 :
564 : /************************************************************************/
565 : /* TIFFHashSetRemove() */
566 : /************************************************************************/
567 :
568 : /**
569 : * Removes an element from a hash set
570 : *
571 : * @param set the hash set
572 : * @param elt the new element to remove from the hash set
573 : *
574 : * @return true if the element was in the hash set
575 : */
576 :
577 2702 : bool TIFFHashSetRemove(TIFFHashSet *set, const void *elt)
578 : {
579 2702 : return TIFFHashSetRemoveInternal(set, elt, false);
580 : }
581 :
582 : #ifdef notused
583 : /************************************************************************/
584 : /* TIFFHashSetRemoveDeferRehash() */
585 : /************************************************************************/
586 :
587 : /**
588 : * Removes an element from a hash set.
589 : *
590 : * This will defer potential rehashing of the set to later calls to
591 : * TIFFHashSetInsert() or TIFFHashSetRemove().
592 : *
593 : * @param set the hash set
594 : * @param elt the new element to remove from the hash set
595 : *
596 : * @return true if the element was in the hash set
597 : */
598 :
599 : bool TIFFHashSetRemoveDeferRehash(TIFFHashSet *set, const void *elt)
600 : {
601 : return TIFFHashSetRemoveInternal(set, elt, true);
602 : }
603 : #endif
|
