Line data Source code
1 : /**********************************************************************
2 : *
3 : * Name: cpl_hash_set.cpp
4 : * Project: CPL - Common Portability Library
5 : * Purpose: Hash set functions.
6 : * Author: Even Rouault, <even dot rouault at spatialys.com>
7 : *
8 : **********************************************************************
9 : * Copyright (c) 2008-2009, Even Rouault <even dot rouault at spatialys.com>
10 : *
11 : * SPDX-License-Identifier: MIT
12 : ****************************************************************************/
13 :
14 : #include "cpl_hash_set.h"
15 :
16 : #include <cstring>
17 :
18 : #include "cpl_conv.h"
19 : #include "cpl_error.h"
20 : #include "cpl_list.h"
21 :
22 : struct _CPLHashSet
23 : {
24 : CPLHashSetHashFunc fnHashFunc;
25 : CPLHashSetEqualFunc fnEqualFunc;
26 : CPLHashSetFreeEltFunc fnFreeEltFunc;
27 : CPLList **tabList;
28 : int nSize;
29 : int nIndiceAllocatedSize;
30 : int nAllocatedSize;
31 : CPLList *psRecyclingList;
32 : int nRecyclingListSize;
33 : bool bRehash;
34 : #ifdef HASH_DEBUG
35 : int nCollisions;
36 : #endif
37 : };
38 :
39 : constexpr int anPrimes[] = {
40 : 53, 97, 193, 389, 769, 1543, 3079,
41 : 6151, 12289, 24593, 49157, 98317, 196613, 393241,
42 : 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
43 : 100663319, 201326611, 402653189, 805306457, 1610612741};
44 :
45 : /************************************************************************/
46 : /* CPLHashSetNew() */
47 : /************************************************************************/
48 :
49 : /**
50 : * Creates a new hash set
51 : *
52 : * The hash function must return a hash value for the elements to insert.
53 : * If fnHashFunc is NULL, CPLHashSetHashPointer will be used.
54 : *
55 : * The equal function must return if two elements are equal.
56 : * If fnEqualFunc is NULL, CPLHashSetEqualPointer will be used.
57 : *
58 : * The free function is used to free elements inserted in the hash set,
59 : * when the hash set is destroyed, when elements are removed or replaced.
60 : * If fnFreeEltFunc is NULL, elements inserted into the hash set will not be
61 : * freed.
62 : *
63 : * @param fnHashFunc hash function. May be NULL.
64 : * @param fnEqualFunc equal function. May be NULL.
65 : * @param fnFreeEltFunc element free function. May be NULL.
66 : *
67 : * @return a new hash set
68 : */
69 :
70 5227 : CPLHashSet *CPLHashSetNew(CPLHashSetHashFunc fnHashFunc,
71 : CPLHashSetEqualFunc fnEqualFunc,
72 : CPLHashSetFreeEltFunc fnFreeEltFunc)
73 : {
74 5227 : CPLHashSet *set = static_cast<CPLHashSet *>(CPLMalloc(sizeof(CPLHashSet)));
75 5227 : set->fnHashFunc = fnHashFunc ? fnHashFunc : CPLHashSetHashPointer;
76 5227 : set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : CPLHashSetEqualPointer;
77 5227 : set->fnFreeEltFunc = fnFreeEltFunc;
78 5227 : set->nSize = 0;
79 5227 : set->tabList = static_cast<CPLList **>(CPLCalloc(sizeof(CPLList *), 53));
80 5227 : set->nIndiceAllocatedSize = 0;
81 5227 : set->nAllocatedSize = 53;
82 5227 : set->psRecyclingList = nullptr;
83 5227 : set->nRecyclingListSize = 0;
84 5227 : set->bRehash = false;
85 : #ifdef HASH_DEBUG
86 : set->nCollisions = 0;
87 : #endif
88 5227 : return set;
89 : }
90 :
91 : /************************************************************************/
92 : /* CPLHashSetSize() */
93 : /************************************************************************/
94 :
95 : /**
96 : * Returns the number of elements inserted in the hash set
97 : *
98 : * Note: this is not the internal size of the hash set
99 : *
100 : * @param set the hash set
101 : *
102 : * @return the number of elements in the hash set
103 : */
104 :
105 7 : int CPLHashSetSize(const CPLHashSet *set)
106 : {
107 7 : CPLAssert(set != nullptr);
108 7 : return set->nSize;
109 : }
110 :
111 : /************************************************************************/
112 : /* CPLHashSetGetNewListElt() */
113 : /************************************************************************/
114 :
115 19053 : static CPLList *CPLHashSetGetNewListElt(CPLHashSet *set)
116 : {
117 19053 : if (set->psRecyclingList)
118 : {
119 24 : CPLList *psRet = set->psRecyclingList;
120 24 : psRet->pData = nullptr;
121 24 : set->nRecyclingListSize--;
122 24 : set->psRecyclingList = psRet->psNext;
123 24 : return psRet;
124 : }
125 :
126 19029 : return static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
127 : }
128 :
129 : /************************************************************************/
130 : /* CPLHashSetReturnListElt() */
131 : /************************************************************************/
132 :
133 1390 : static void CPLHashSetReturnListElt(CPLHashSet *set, CPLList *psList)
134 : {
135 1390 : if (set->nRecyclingListSize < 128)
136 : {
137 518 : psList->psNext = set->psRecyclingList;
138 518 : set->psRecyclingList = psList;
139 518 : set->nRecyclingListSize++;
140 : }
141 : else
142 : {
143 872 : CPLFree(psList);
144 : }
145 1390 : }
146 :
147 : /************************************************************************/
148 : /* CPLHashSetClearInternal() */
149 : /************************************************************************/
150 :
151 5226 : static void CPLHashSetClearInternal(CPLHashSet *set, bool bFinalize)
152 : {
153 5226 : CPLAssert(set != nullptr);
154 286844 : for (int i = 0; i < set->nAllocatedSize; i++)
155 : {
156 281618 : CPLList *cur = set->tabList[i];
157 299280 : while (cur)
158 : {
159 17662 : if (set->fnFreeEltFunc)
160 1159 : set->fnFreeEltFunc(cur->pData);
161 17662 : CPLList *psNext = cur->psNext;
162 17662 : if (bFinalize)
163 17662 : CPLFree(cur);
164 : else
165 0 : CPLHashSetReturnListElt(set, cur);
166 17662 : cur = psNext;
167 : }
168 281618 : set->tabList[i] = nullptr;
169 : }
170 5226 : set->bRehash = false;
171 5226 : }
172 :
173 : /************************************************************************/
174 : /* CPLHashSetDestroy() */
175 : /************************************************************************/
176 :
177 : /**
178 : * Destroys an allocated hash set.
179 : *
180 : * This function also frees the elements if a free function was
181 : * provided at the creation of the hash set.
182 : *
183 : * @param set the hash set
184 : */
185 :
186 5226 : void CPLHashSetDestroy(CPLHashSet *set)
187 : {
188 5226 : CPLHashSetClearInternal(set, true);
189 5226 : CPLFree(set->tabList);
190 5226 : CPLListDestroy(set->psRecyclingList);
191 5226 : CPLFree(set);
192 5226 : }
193 :
194 : /************************************************************************/
195 : /* CPLHashSetClear() */
196 : /************************************************************************/
197 :
198 : /**
199 : * Clear all elements from a hash set.
200 : *
201 : * This function also frees the elements if a free function was
202 : * provided at the creation of the hash set.
203 : *
204 : * @param set the hash set
205 : * @since GDAL 2.1
206 : */
207 :
208 0 : void CPLHashSetClear(CPLHashSet *set)
209 : {
210 0 : CPLHashSetClearInternal(set, false);
211 0 : set->tabList = static_cast<CPLList **>(
212 0 : CPLRealloc(set->tabList, sizeof(CPLList *) * 53));
213 0 : set->nIndiceAllocatedSize = 0;
214 0 : set->nAllocatedSize = 53;
215 : #ifdef HASH_DEBUG
216 : set->nCollisions = 0;
217 : #endif
218 0 : set->nSize = 0;
219 0 : }
220 :
221 : /************************************************************************/
222 : /* CPLHashSetForeach() */
223 : /************************************************************************/
224 :
225 : /**
226 : * Walk through the hash set and runs the provided function on all the
227 : * elements
228 : *
229 : * This function is provided the user_data argument of CPLHashSetForeach.
230 : * It must return TRUE to go on the walk through the hash set, or FALSE to
231 : * make it stop.
232 : *
233 : * Note : the structure of the hash set must *NOT* be modified during the
234 : * walk.
235 : *
236 : * @param set the hash set.
237 : * @param fnIterFunc the function called on each element.
238 : * @param user_data the user data provided to the function.
239 : */
240 :
241 1 : void CPLHashSetForeach(CPLHashSet *set, CPLHashSetIterEltFunc fnIterFunc,
242 : void *user_data)
243 : {
244 1 : CPLAssert(set != nullptr);
245 1 : if (!fnIterFunc)
246 0 : return;
247 :
248 1544 : for (int i = 0; i < set->nAllocatedSize; i++)
249 : {
250 1543 : CPLList *cur = set->tabList[i];
251 2543 : while (cur)
252 : {
253 1000 : if (!fnIterFunc(cur->pData, user_data))
254 0 : return;
255 :
256 1000 : cur = cur->psNext;
257 : }
258 : }
259 : }
260 :
261 : /************************************************************************/
262 : /* CPLHashSetRehash() */
263 : /************************************************************************/
264 :
265 80 : static void CPLHashSetRehash(CPLHashSet *set)
266 : {
267 80 : int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
268 : CPLList **newTabList = static_cast<CPLList **>(
269 80 : CPLCalloc(sizeof(CPLList *), nNewAllocatedSize));
270 : #ifdef HASH_DEBUG
271 : CPLDebug("CPLHASH",
272 : "hashSet=%p, nSize=%d, nCollisions=%d, "
273 : "fCollisionRate=%.02f",
274 : set, set->nSize, set->nCollisions,
275 : set->nCollisions * 100.0 / set->nSize);
276 : set->nCollisions = 0;
277 : #endif
278 9602 : for (int i = 0; i < set->nAllocatedSize; i++)
279 : {
280 9522 : CPLList *cur = set->tabList[i];
281 15333 : while (cur)
282 : {
283 : const unsigned long nNewHashVal =
284 5811 : set->fnHashFunc(cur->pData) % nNewAllocatedSize;
285 : #ifdef HASH_DEBUG
286 : if (newTabList[nNewHashVal])
287 : set->nCollisions++;
288 : #endif
289 5811 : CPLList *psNext = cur->psNext;
290 5811 : cur->psNext = newTabList[nNewHashVal];
291 5811 : newTabList[nNewHashVal] = cur;
292 5811 : cur = psNext;
293 : }
294 : }
295 80 : CPLFree(set->tabList);
296 80 : set->tabList = newTabList;
297 80 : set->nAllocatedSize = nNewAllocatedSize;
298 80 : set->bRehash = false;
299 80 : }
300 :
301 : /************************************************************************/
302 : /* CPLHashSetFindPtr() */
303 : /************************************************************************/
304 :
305 49672 : static void **CPLHashSetFindPtr(CPLHashSet *set, const void *elt)
306 : {
307 49672 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
308 49672 : CPLList *cur = set->tabList[nHashVal];
309 53539 : while (cur)
310 : {
311 30609 : if (set->fnEqualFunc(cur->pData, elt))
312 26742 : return &cur->pData;
313 3867 : cur = cur->psNext;
314 : }
315 22930 : return nullptr;
316 : }
317 :
318 : /************************************************************************/
319 : /* CPLHashSetInsert() */
320 : /************************************************************************/
321 :
322 : /**
323 : * Inserts an element into a hash set.
324 : *
325 : * If the element was already inserted in the hash set, the previous
326 : * element is replaced by the new element. If a free function was provided,
327 : * it is used to free the previously inserted element
328 : *
329 : * @param set the hash set
330 : * @param elt the new element to insert in the hash set
331 : *
332 : * @return TRUE if the element was not already in the hash set
333 : */
334 :
335 21479 : int CPLHashSetInsert(CPLHashSet *set, void *elt)
336 : {
337 21479 : CPLAssert(set != nullptr);
338 21479 : void **pElt = CPLHashSetFindPtr(set, elt);
339 21479 : if (pElt)
340 : {
341 2426 : if (set->fnFreeEltFunc)
342 25 : set->fnFreeEltFunc(*pElt);
343 :
344 2426 : *pElt = elt;
345 2426 : return FALSE;
346 : }
347 :
348 19053 : if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
349 18978 : (set->bRehash && set->nIndiceAllocatedSize > 0 &&
350 0 : set->nSize <= set->nAllocatedSize / 2))
351 : {
352 75 : set->nIndiceAllocatedSize++;
353 75 : CPLHashSetRehash(set);
354 : }
355 :
356 19053 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
357 : #ifdef HASH_DEBUG
358 : if (set->tabList[nHashVal])
359 : set->nCollisions++;
360 : #endif
361 :
362 19053 : CPLList *new_elt = CPLHashSetGetNewListElt(set);
363 19053 : new_elt->pData = elt;
364 19053 : new_elt->psNext = set->tabList[nHashVal];
365 19053 : set->tabList[nHashVal] = new_elt;
366 19053 : set->nSize++;
367 :
368 19053 : return TRUE;
369 : }
370 :
371 : /************************************************************************/
372 : /* CPLHashSetLookup() */
373 : /************************************************************************/
374 :
375 : /**
376 : * Returns the element found in the hash set corresponding to the element to
377 : * look up The element must not be modified.
378 : *
379 : * @param set the hash set
380 : * @param elt the element to look up in the hash set
381 : *
382 : * @return the element found in the hash set or NULL
383 : */
384 :
385 28193 : void *CPLHashSetLookup(CPLHashSet *set, const void *elt)
386 : {
387 28193 : CPLAssert(set != nullptr);
388 28193 : void **pElt = CPLHashSetFindPtr(set, elt);
389 28193 : if (pElt)
390 24316 : return *pElt;
391 :
392 3877 : return nullptr;
393 : }
394 :
395 : /************************************************************************/
396 : /* CPLHashSetRemoveInternal() */
397 : /************************************************************************/
398 :
399 1391 : static bool CPLHashSetRemoveInternal(CPLHashSet *set, const void *elt,
400 : bool bDeferRehash)
401 : {
402 1391 : CPLAssert(set != nullptr);
403 1391 : if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
404 : {
405 5 : set->nIndiceAllocatedSize--;
406 5 : if (bDeferRehash)
407 0 : set->bRehash = true;
408 : else
409 5 : CPLHashSetRehash(set);
410 : }
411 :
412 1391 : int nHashVal = static_cast<int>(set->fnHashFunc(elt) % set->nAllocatedSize);
413 1391 : CPLList *cur = set->tabList[nHashVal];
414 1391 : CPLList *prev = nullptr;
415 1399 : while (cur)
416 : {
417 1398 : if (set->fnEqualFunc(cur->pData, elt))
418 : {
419 1390 : if (prev)
420 7 : prev->psNext = cur->psNext;
421 : else
422 1383 : set->tabList[nHashVal] = cur->psNext;
423 :
424 1390 : if (set->fnFreeEltFunc)
425 390 : set->fnFreeEltFunc(cur->pData);
426 :
427 1390 : CPLHashSetReturnListElt(set, cur);
428 : #ifdef HASH_DEBUG
429 : if (set->tabList[nHashVal])
430 : set->nCollisions--;
431 : #endif
432 1390 : set->nSize--;
433 1390 : return true;
434 : }
435 8 : prev = cur;
436 8 : cur = cur->psNext;
437 : }
438 1 : return false;
439 : }
440 :
441 : /************************************************************************/
442 : /* CPLHashSetRemove() */
443 : /************************************************************************/
444 :
445 : /**
446 : * Removes an element from a hash set
447 : *
448 : * @param set the hash set
449 : * @param elt the new element to remove from the hash set
450 : *
451 : * @return TRUE if the element was in the hash set
452 : */
453 :
454 1391 : int CPLHashSetRemove(CPLHashSet *set, const void *elt)
455 : {
456 1391 : return CPLHashSetRemoveInternal(set, elt, false);
457 : }
458 :
459 : /************************************************************************/
460 : /* CPLHashSetRemoveDeferRehash() */
461 : /************************************************************************/
462 :
463 : /**
464 : * Removes an element from a hash set.
465 : *
466 : * This will defer potential rehashing of the set to later calls to
467 : * CPLHashSetInsert() or CPLHashSetRemove().
468 : *
469 : * @param set the hash set
470 : * @param elt the new element to remove from the hash set
471 : *
472 : * @return TRUE if the element was in the hash set
473 : * @since GDAL 2.1
474 : */
475 :
476 0 : int CPLHashSetRemoveDeferRehash(CPLHashSet *set, const void *elt)
477 : {
478 0 : return CPLHashSetRemoveInternal(set, elt, true);
479 : }
480 :
481 : /************************************************************************/
482 : /* CPLHashSetHashPointer() */
483 : /************************************************************************/
484 :
485 : /**
486 : * Hash function for an arbitrary pointer
487 : *
488 : * @param elt the arbitrary pointer to hash
489 : *
490 : * @return the hash value of the pointer
491 : */
492 :
493 62695 : unsigned long CPLHashSetHashPointer(const void *elt)
494 : {
495 : return static_cast<unsigned long>(
496 62695 : reinterpret_cast<GUIntptr_t>(const_cast<void *>(elt)));
497 : }
498 :
499 : /************************************************************************/
500 : /* CPLHashSetEqualPointer() */
501 : /************************************************************************/
502 :
503 : /**
504 : * Equality function for arbitrary pointers
505 : *
506 : * @param elt1 the first arbitrary pointer to compare
507 : * @param elt2 the second arbitrary pointer to compare
508 : *
509 : * @return TRUE if the pointers are equal
510 : */
511 :
512 24612 : int CPLHashSetEqualPointer(const void *elt1, const void *elt2)
513 : {
514 24612 : return elt1 == elt2;
515 : }
516 :
517 : /************************************************************************/
518 : /* CPLHashSetHashStr() */
519 : /************************************************************************/
520 :
521 : /**
522 : * Hash function for a zero-terminated string
523 : *
524 : * @param elt the string to hash. May be NULL.
525 : *
526 : * @return the hash value of the string
527 : */
528 :
529 : CPL_NOSANITIZE_UNSIGNED_INT_OVERFLOW
530 49307 : unsigned long CPLHashSetHashStr(const void *elt)
531 : {
532 49307 : if (elt == nullptr)
533 10 : return 0;
534 :
535 49297 : const unsigned char *pszStr = static_cast<const unsigned char *>(elt);
536 49297 : unsigned long hash = 0;
537 :
538 49297 : int c = 0;
539 1044020 : while ((c = *pszStr++) != '\0')
540 994718 : hash = c + (hash << 6) + (hash << 16) - hash;
541 :
542 49297 : return hash;
543 : }
544 :
545 : /************************************************************************/
546 : /* CPLHashSetEqualStr() */
547 : /************************************************************************/
548 :
549 : /**
550 : * Equality function for strings
551 : *
552 : * @param elt1 the first string to compare. May be NULL.
553 : * @param elt2 the second string to compare. May be NULL.
554 : *
555 : * @return TRUE if the strings are equal
556 : */
557 :
558 98 : int CPLHashSetEqualStr(const void *elt1, const void *elt2)
559 : {
560 98 : const char *pszStr1 = static_cast<const char *>(elt1);
561 98 : const char *pszStr2 = static_cast<const char *>(elt2);
562 :
563 98 : if (pszStr1 == nullptr && pszStr2 != nullptr)
564 0 : return FALSE;
565 :
566 98 : if (pszStr1 != nullptr && pszStr2 == nullptr)
567 0 : return FALSE;
568 :
569 98 : if (pszStr1 == nullptr && pszStr2 == nullptr)
570 2 : return TRUE;
571 :
572 96 : return strcmp(pszStr1, pszStr2) == 0;
573 : }
|
