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 "tiffconf.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
TIFFHashSetHashPointer(const void * elt)90 static unsigned long TIFFHashSetHashPointer(const void *elt)
91 {
92 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
TIFFHashSetEqualPointer(const void * elt1,const void * elt2)108 static bool TIFFHashSetEqualPointer(const void *elt1, const void *elt2)
109 {
110 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
TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,TIFFHashSetEqualFunc fnEqualFunc,TIFFHashSetFreeEltFunc fnFreeEltFunc)138 TIFFHashSet *TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,
139 TIFFHashSetEqualFunc fnEqualFunc,
140 TIFFHashSetFreeEltFunc fnFreeEltFunc)
141 {
142 TIFFHashSet *set = (TIFFHashSet *)malloc(sizeof(TIFFHashSet));
143 if (set == NULL)
144 return NULL;
145 set->fnHashFunc = fnHashFunc ? fnHashFunc : TIFFHashSetHashPointer;
146 set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : TIFFHashSetEqualPointer;
147 set->fnFreeEltFunc = fnFreeEltFunc;
148 set->nSize = 0;
149 set->tabList = (TIFFList **)(calloc(sizeof(TIFFList *), 53));
150 if (set->tabList == NULL)
151 {
152 free(set);
153 return NULL;
154 }
155 set->nIndiceAllocatedSize = 0;
156 set->nAllocatedSize = 53;
157 set->psRecyclingList = NULL;
158 set->nRecyclingListSize = 0;
159 set->bRehash = false;
160 #ifdef HASH_DEBUG
161 set->nCollisions = 0;
162 #endif
163 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
TIFFHashSetSize(const TIFFHashSet * set)180 int TIFFHashSetSize(const TIFFHashSet *set)
181 {
182 assert(set != NULL);
183 return set->nSize;
184 }
185
186 /************************************************************************/
187 /* TIFFHashSetGetNewListElt() */
188 /************************************************************************/
189
TIFFHashSetGetNewListElt(TIFFHashSet * set)190 static TIFFList *TIFFHashSetGetNewListElt(TIFFHashSet *set)
191 {
192 if (set->psRecyclingList)
193 {
194 TIFFList *psRet = set->psRecyclingList;
195 psRet->pData = NULL;
196 set->nRecyclingListSize--;
197 set->psRecyclingList = psRet->psNext;
198 return psRet;
199 }
200
201 return (TIFFList *)malloc(sizeof(TIFFList));
202 }
203
204 /************************************************************************/
205 /* TIFFHashSetReturnListElt() */
206 /************************************************************************/
207
TIFFHashSetReturnListElt(TIFFHashSet * set,TIFFList * psList)208 static void TIFFHashSetReturnListElt(TIFFHashSet *set, TIFFList *psList)
209 {
210 if (set->nRecyclingListSize < 128)
211 {
212 psList->psNext = set->psRecyclingList;
213 set->psRecyclingList = psList;
214 set->nRecyclingListSize++;
215 }
216 else
217 {
218 free(psList);
219 }
220 }
221
222 /************************************************************************/
223 /* TIFFHashSetClearInternal() */
224 /************************************************************************/
225
TIFFHashSetClearInternal(TIFFHashSet * set,bool bFinalize)226 static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)
227 {
228 assert(set != NULL);
229 for (int i = 0; i < set->nAllocatedSize; i++)
230 {
231 TIFFList *cur = set->tabList[i];
232 while (cur)
233 {
234 if (set->fnFreeEltFunc)
235 set->fnFreeEltFunc(cur->pData);
236 TIFFList *psNext = cur->psNext;
237 if (bFinalize)
238 free(cur);
239 else
240 TIFFHashSetReturnListElt(set, cur);
241 cur = psNext;
242 }
243 set->tabList[i] = NULL;
244 }
245 set->bRehash = false;
246 }
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
TIFFListDestroy(TIFFList * psList)260 static void TIFFListDestroy(TIFFList *psList)
261 {
262 TIFFList *psCurrent = psList;
263
264 while (psCurrent)
265 {
266 TIFFList *const psNext = psCurrent->psNext;
267 free(psCurrent);
268 psCurrent = psNext;
269 }
270 }
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
TIFFHashSetDestroy(TIFFHashSet * set)285 void TIFFHashSetDestroy(TIFFHashSet *set)
286 {
287 if (set)
288 {
289 TIFFHashSetClearInternal(set, true);
290 free(set->tabList);
291 TIFFListDestroy(set->psRecyclingList);
292 free(set);
293 }
294 }
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
TIFFHashSetClear(TIFFHashSet * set)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
TIFFHashSetForeach(TIFFHashSet * set,TIFFHashSetIterEltFunc fnIterFunc,void * user_data)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
TIFFHashSetRehash(TIFFHashSet * set)366 static bool TIFFHashSetRehash(TIFFHashSet *set)
367 {
368 int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
369 TIFFList **newTabList =
370 (TIFFList **)(calloc(sizeof(TIFFList *), nNewAllocatedSize));
371 if (newTabList == NULL)
372 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 for (int i = 0; i < set->nAllocatedSize; i++)
382 {
383 TIFFList *cur = set->tabList[i];
384 while (cur)
385 {
386 const unsigned long nNewHashVal =
387 set->fnHashFunc(cur->pData) % nNewAllocatedSize;
388 #ifdef HASH_DEBUG
389 if (newTabList[nNewHashVal])
390 set->nCollisions++;
391 #endif
392 TIFFList *psNext = cur->psNext;
393 cur->psNext = newTabList[nNewHashVal];
394 newTabList[nNewHashVal] = cur;
395 cur = psNext;
396 }
397 }
398 free(set->tabList);
399 set->tabList = newTabList;
400 set->nAllocatedSize = nNewAllocatedSize;
401 set->bRehash = false;
402 return true;
403 }
404
405 /************************************************************************/
406 /* TIFFHashSetFindPtr() */
407 /************************************************************************/
408
TIFFHashSetFindPtr(TIFFHashSet * set,const void * elt)409 static void **TIFFHashSetFindPtr(TIFFHashSet *set, const void *elt)
410 {
411 const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
412 TIFFList *cur = set->tabList[nHashVal];
413 while (cur)
414 {
415 if (set->fnEqualFunc(cur->pData, elt))
416 return &cur->pData;
417 cur = cur->psNext;
418 }
419 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
TIFFHashSetInsert(TIFFHashSet * set,void * elt)440 bool TIFFHashSetInsert(TIFFHashSet *set, void *elt)
441 {
442 assert(set != NULL);
443 void **pElt = TIFFHashSetFindPtr(set, elt);
444 if (pElt)
445 {
446 if (set->fnFreeEltFunc)
447 set->fnFreeEltFunc(*pElt);
448
449 *pElt = elt;
450 return true;
451 }
452
453 if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
454 (set->bRehash && set->nIndiceAllocatedSize > 0 &&
455 set->nSize <= set->nAllocatedSize / 2))
456 {
457 set->nIndiceAllocatedSize++;
458 if (!TIFFHashSetRehash(set))
459 {
460 set->nIndiceAllocatedSize--;
461 if (set->fnFreeEltFunc)
462 set->fnFreeEltFunc(elt);
463 return false;
464 }
465 }
466
467 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 TIFFList *new_elt = TIFFHashSetGetNewListElt(set);
474 if (new_elt == NULL)
475 {
476 if (set->fnFreeEltFunc)
477 set->fnFreeEltFunc(elt);
478 return false;
479 }
480 new_elt->pData = elt;
481 new_elt->psNext = set->tabList[nHashVal];
482 set->tabList[nHashVal] = new_elt;
483 set->nSize++;
484
485 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
TIFFHashSetLookup(TIFFHashSet * set,const void * elt)502 void *TIFFHashSetLookup(TIFFHashSet *set, const void *elt)
503 {
504 assert(set != NULL);
505 void **pElt = TIFFHashSetFindPtr(set, elt);
506 if (pElt)
507 return *pElt;
508
509 return NULL;
510 }
511
512 /************************************************************************/
513 /* TIFFHashSetRemoveInternal() */
514 /************************************************************************/
515
TIFFHashSetRemoveInternal(TIFFHashSet * set,const void * elt,bool bDeferRehash)516 static bool TIFFHashSetRemoveInternal(TIFFHashSet *set, const void *elt,
517 bool bDeferRehash)
518 {
519 assert(set != NULL);
520 if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
521 {
522 set->nIndiceAllocatedSize--;
523 if (bDeferRehash)
524 set->bRehash = true;
525 else
526 {
527 if (!TIFFHashSetRehash(set))
528 {
529 set->nIndiceAllocatedSize++;
530 return false;
531 }
532 }
533 }
534
535 int nHashVal = (int)(set->fnHashFunc(elt) % set->nAllocatedSize);
536 TIFFList *cur = set->tabList[nHashVal];
537 TIFFList *prev = NULL;
538 while (cur)
539 {
540 if (set->fnEqualFunc(cur->pData, elt))
541 {
542 if (prev)
543 prev->psNext = cur->psNext;
544 else
545 set->tabList[nHashVal] = cur->psNext;
546
547 if (set->fnFreeEltFunc)
548 set->fnFreeEltFunc(cur->pData);
549
550 TIFFHashSetReturnListElt(set, cur);
551 #ifdef HASH_DEBUG
552 if (set->tabList[nHashVal])
553 set->nCollisions--;
554 #endif
555 set->nSize--;
556 return true;
557 }
558 prev = cur;
559 cur = cur->psNext;
560 }
561 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
TIFFHashSetRemove(TIFFHashSet * set,const void * elt)577 bool TIFFHashSetRemove(TIFFHashSet *set, const void *elt)
578 {
579 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
TIFFHashSetRemoveDeferRehash(TIFFHashSet * set,const void * elt)599 bool TIFFHashSetRemoveDeferRehash(TIFFHashSet *set, const void *elt)
600 {
601 return TIFFHashSetRemoveInternal(set, elt, true);
602 }
603 #endif
604