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 5337 : CPLHashSet *CPLHashSetNew(CPLHashSetHashFunc fnHashFunc,
71 : CPLHashSetEqualFunc fnEqualFunc,
72 : CPLHashSetFreeEltFunc fnFreeEltFunc)
73 : {
74 5337 : CPLHashSet *set = static_cast<CPLHashSet *>(CPLMalloc(sizeof(CPLHashSet)));
75 5337 : set->fnHashFunc = fnHashFunc ? fnHashFunc : CPLHashSetHashPointer;
76 5337 : set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : CPLHashSetEqualPointer;
77 5337 : set->fnFreeEltFunc = fnFreeEltFunc;
78 5337 : set->nSize = 0;
79 5337 : set->tabList = static_cast<CPLList **>(CPLCalloc(sizeof(CPLList *), 53));
80 5337 : set->nIndiceAllocatedSize = 0;
81 5337 : set->nAllocatedSize = 53;
82 5337 : set->psRecyclingList = nullptr;
83 5337 : set->nRecyclingListSize = 0;
84 5337 : set->bRehash = false;
85 : #ifdef HASH_DEBUG
86 : set->nCollisions = 0;
87 : #endif
88 5337 : 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 19142 : static CPLList *CPLHashSetGetNewListElt(CPLHashSet *set)
116 : {
117 19142 : if (set->psRecyclingList)
118 : {
119 28 : CPLList *psRet = set->psRecyclingList;
120 28 : psRet->pData = nullptr;
121 28 : set->nRecyclingListSize--;
122 28 : set->psRecyclingList = psRet->psNext;
123 28 : return psRet;
124 : }
125 :
126 19114 : return static_cast<CPLList *>(CPLMalloc(sizeof(CPLList)));
127 : }
128 :
129 : /************************************************************************/
130 : /* CPLHashSetReturnListElt() */
131 : /************************************************************************/
132 :
133 1411 : static void CPLHashSetReturnListElt(CPLHashSet *set, CPLList *psList)
134 : {
135 1411 : if (set->nRecyclingListSize < 128)
136 : {
137 539 : psList->psNext = set->psRecyclingList;
138 539 : set->psRecyclingList = psList;
139 539 : set->nRecyclingListSize++;
140 : }
141 : else
142 : {
143 872 : CPLFree(psList);
144 : }
145 1411 : }
146 :
147 : /************************************************************************/
148 : /* CPLHashSetClearInternal() */
149 : /************************************************************************/
150 :
151 5336 : static void CPLHashSetClearInternal(CPLHashSet *set, bool bFinalize)
152 : {
153 5336 : CPLAssert(set != nullptr);
154 292784 : for (int i = 0; i < set->nAllocatedSize; i++)
155 : {
156 287448 : CPLList *cur = set->tabList[i];
157 305178 : while (cur)
158 : {
159 17730 : if (set->fnFreeEltFunc)
160 1161 : set->fnFreeEltFunc(cur->pData);
161 17730 : CPLList *psNext = cur->psNext;
162 17730 : if (bFinalize)
163 17730 : CPLFree(cur);
164 : else
165 0 : CPLHashSetReturnListElt(set, cur);
166 17730 : cur = psNext;
167 : }
168 287448 : set->tabList[i] = nullptr;
169 : }
170 5336 : set->bRehash = false;
171 5336 : }
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 5336 : void CPLHashSetDestroy(CPLHashSet *set)
187 : {
188 5336 : CPLHashSetClearInternal(set, true);
189 5336 : CPLFree(set->tabList);
190 5336 : CPLListDestroy(set->psRecyclingList);
191 5336 : CPLFree(set);
192 5336 : }
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 : */
206 :
207 0 : void CPLHashSetClear(CPLHashSet *set)
208 : {
209 0 : CPLHashSetClearInternal(set, false);
210 0 : set->tabList = static_cast<CPLList **>(
211 0 : CPLRealloc(set->tabList, sizeof(CPLList *) * 53));
212 0 : set->nIndiceAllocatedSize = 0;
213 0 : set->nAllocatedSize = 53;
214 : #ifdef HASH_DEBUG
215 : set->nCollisions = 0;
216 : #endif
217 0 : set->nSize = 0;
218 0 : }
219 :
220 : /************************************************************************/
221 : /* CPLHashSetForeach() */
222 : /************************************************************************/
223 :
224 : /**
225 : * Walk through the hash set and runs the provided function on all the
226 : * elements
227 : *
228 : * This function is provided the user_data argument of CPLHashSetForeach.
229 : * It must return TRUE to go on the walk through the hash set, or FALSE to
230 : * make it stop.
231 : *
232 : * Note : the structure of the hash set must *NOT* be modified during the
233 : * walk.
234 : *
235 : * @param set the hash set.
236 : * @param fnIterFunc the function called on each element.
237 : * @param user_data the user data provided to the function.
238 : */
239 :
240 1 : void CPLHashSetForeach(CPLHashSet *set, CPLHashSetIterEltFunc fnIterFunc,
241 : void *user_data)
242 : {
243 1 : CPLAssert(set != nullptr);
244 1 : if (!fnIterFunc)
245 0 : return;
246 :
247 1544 : for (int i = 0; i < set->nAllocatedSize; i++)
248 : {
249 1543 : CPLList *cur = set->tabList[i];
250 2543 : while (cur)
251 : {
252 1000 : if (!fnIterFunc(cur->pData, user_data))
253 0 : return;
254 :
255 1000 : cur = cur->psNext;
256 : }
257 : }
258 : }
259 :
260 : /************************************************************************/
261 : /* CPLHashSetRehash() */
262 : /************************************************************************/
263 :
264 80 : static void CPLHashSetRehash(CPLHashSet *set)
265 : {
266 80 : int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
267 : CPLList **newTabList = static_cast<CPLList **>(
268 80 : CPLCalloc(sizeof(CPLList *), nNewAllocatedSize));
269 : #ifdef HASH_DEBUG
270 : CPLDebug("CPLHASH",
271 : "hashSet=%p, nSize=%d, nCollisions=%d, "
272 : "fCollisionRate=%.02f",
273 : set, set->nSize, set->nCollisions,
274 : set->nCollisions * 100.0 / set->nSize);
275 : set->nCollisions = 0;
276 : #endif
277 9602 : for (int i = 0; i < set->nAllocatedSize; i++)
278 : {
279 9522 : CPLList *cur = set->tabList[i];
280 15333 : while (cur)
281 : {
282 : const unsigned long nNewHashVal =
283 5811 : set->fnHashFunc(cur->pData) % nNewAllocatedSize;
284 : #ifdef HASH_DEBUG
285 : if (newTabList[nNewHashVal])
286 : set->nCollisions++;
287 : #endif
288 5811 : CPLList *psNext = cur->psNext;
289 5811 : cur->psNext = newTabList[nNewHashVal];
290 5811 : newTabList[nNewHashVal] = cur;
291 5811 : cur = psNext;
292 : }
293 : }
294 80 : CPLFree(set->tabList);
295 80 : set->tabList = newTabList;
296 80 : set->nAllocatedSize = nNewAllocatedSize;
297 80 : set->bRehash = false;
298 80 : }
299 :
300 : /************************************************************************/
301 : /* CPLHashSetFindPtr() */
302 : /************************************************************************/
303 :
304 49515 : static void **CPLHashSetFindPtr(CPLHashSet *set, const void *elt)
305 : {
306 49515 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
307 49515 : CPLList *cur = set->tabList[nHashVal];
308 52861 : while (cur)
309 : {
310 30191 : if (set->fnEqualFunc(cur->pData, elt))
311 26845 : return &cur->pData;
312 3346 : cur = cur->psNext;
313 : }
314 22670 : return nullptr;
315 : }
316 :
317 : /************************************************************************/
318 : /* CPLHashSetInsert() */
319 : /************************************************************************/
320 :
321 : /**
322 : * Inserts an element into a hash set.
323 : *
324 : * If the element was already inserted in the hash set, the previous
325 : * element is replaced by the new element. If a free function was provided,
326 : * it is used to free the previously inserted element
327 : *
328 : * @param set the hash set
329 : * @param elt the new element to insert in the hash set
330 : *
331 : * @return TRUE if the element was not already in the hash set
332 : */
333 :
334 21579 : int CPLHashSetInsert(CPLHashSet *set, void *elt)
335 : {
336 21579 : CPLAssert(set != nullptr);
337 21579 : void **pElt = CPLHashSetFindPtr(set, elt);
338 21579 : if (pElt)
339 : {
340 2437 : if (set->fnFreeEltFunc)
341 25 : set->fnFreeEltFunc(*pElt);
342 :
343 2437 : *pElt = elt;
344 2437 : return FALSE;
345 : }
346 :
347 19142 : if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
348 19067 : (set->bRehash && set->nIndiceAllocatedSize > 0 &&
349 0 : set->nSize <= set->nAllocatedSize / 2))
350 : {
351 75 : set->nIndiceAllocatedSize++;
352 75 : CPLHashSetRehash(set);
353 : }
354 :
355 19142 : const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
356 : #ifdef HASH_DEBUG
357 : if (set->tabList[nHashVal])
358 : set->nCollisions++;
359 : #endif
360 :
361 19142 : CPLList *new_elt = CPLHashSetGetNewListElt(set);
362 19142 : new_elt->pData = elt;
363 19142 : new_elt->psNext = set->tabList[nHashVal];
364 19142 : set->tabList[nHashVal] = new_elt;
365 19142 : set->nSize++;
366 :
367 19142 : return TRUE;
368 : }
369 :
370 : /************************************************************************/
371 : /* CPLHashSetLookup() */
372 : /************************************************************************/
373 :
374 : /**
375 : * Returns the element found in the hash set corresponding to the element to
376 : * look up The element must not be modified.
377 : *
378 : * @param set the hash set
379 : * @param elt the element to look up in the hash set
380 : *
381 : * @return the element found in the hash set or NULL
382 : */
383 :
384 27936 : void *CPLHashSetLookup(CPLHashSet *set, const void *elt)
385 : {
386 27936 : CPLAssert(set != nullptr);
387 27936 : void **pElt = CPLHashSetFindPtr(set, elt);
388 27936 : if (pElt)
389 24408 : return *pElt;
390 :
391 3528 : return nullptr;
392 : }
393 :
394 : /************************************************************************/
395 : /* CPLHashSetRemoveInternal() */
396 : /************************************************************************/
397 :
398 1412 : static bool CPLHashSetRemoveInternal(CPLHashSet *set, const void *elt,
399 : bool bDeferRehash)
400 : {
401 1412 : CPLAssert(set != nullptr);
402 1412 : if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
403 : {
404 5 : set->nIndiceAllocatedSize--;
405 5 : if (bDeferRehash)
406 0 : set->bRehash = true;
407 : else
408 5 : CPLHashSetRehash(set);
409 : }
410 :
411 1412 : int nHashVal = static_cast<int>(set->fnHashFunc(elt) % set->nAllocatedSize);
412 1412 : CPLList *cur = set->tabList[nHashVal];
413 1412 : CPLList *prev = nullptr;
414 1421 : while (cur)
415 : {
416 1420 : if (set->fnEqualFunc(cur->pData, elt))
417 : {
418 1411 : if (prev)
419 8 : prev->psNext = cur->psNext;
420 : else
421 1403 : set->tabList[nHashVal] = cur->psNext;
422 :
423 1411 : if (set->fnFreeEltFunc)
424 411 : set->fnFreeEltFunc(cur->pData);
425 :
426 1411 : CPLHashSetReturnListElt(set, cur);
427 : #ifdef HASH_DEBUG
428 : if (set->tabList[nHashVal])
429 : set->nCollisions--;
430 : #endif
431 1411 : set->nSize--;
432 1411 : return true;
433 : }
434 9 : prev = cur;
435 9 : cur = cur->psNext;
436 : }
437 1 : return false;
438 : }
439 :
440 : /************************************************************************/
441 : /* CPLHashSetRemove() */
442 : /************************************************************************/
443 :
444 : /**
445 : * Removes an element from a hash set
446 : *
447 : * @param set the hash set
448 : * @param elt the new element to remove from the hash set
449 : *
450 : * @return TRUE if the element was in the hash set
451 : */
452 :
453 1412 : int CPLHashSetRemove(CPLHashSet *set, const void *elt)
454 : {
455 1412 : return CPLHashSetRemoveInternal(set, elt, false);
456 : }
457 :
458 : /************************************************************************/
459 : /* CPLHashSetRemoveDeferRehash() */
460 : /************************************************************************/
461 :
462 : /**
463 : * Removes an element from a hash set.
464 : *
465 : * This will defer potential rehashing of the set to later calls to
466 : * CPLHashSetInsert() or CPLHashSetRemove().
467 : *
468 : * @param set the hash set
469 : * @param elt the new element to remove from the hash set
470 : *
471 : * @return TRUE if the element was in the hash set
472 : */
473 :
474 0 : int CPLHashSetRemoveDeferRehash(CPLHashSet *set, const void *elt)
475 : {
476 0 : return CPLHashSetRemoveInternal(set, elt, true);
477 : }
478 :
479 : /************************************************************************/
480 : /* CPLHashSetHashPointer() */
481 : /************************************************************************/
482 :
483 : /**
484 : * Hash function for an arbitrary pointer
485 : *
486 : * @param elt the arbitrary pointer to hash
487 : *
488 : * @return the hash value of the pointer
489 : */
490 :
491 62911 : unsigned long CPLHashSetHashPointer(const void *elt)
492 : {
493 : return static_cast<unsigned long>(
494 62911 : reinterpret_cast<GUIntptr_t>(const_cast<void *>(elt)));
495 : }
496 :
497 : /************************************************************************/
498 : /* CPLHashSetEqualPointer() */
499 : /************************************************************************/
500 :
501 : /**
502 : * Equality function for arbitrary pointers
503 : *
504 : * @param elt1 the first arbitrary pointer to compare
505 : * @param elt2 the second arbitrary pointer to compare
506 : *
507 : * @return TRUE if the pointers are equal
508 : */
509 :
510 24155 : int CPLHashSetEqualPointer(const void *elt1, const void *elt2)
511 : {
512 24155 : return elt1 == elt2;
513 : }
514 :
515 : /************************************************************************/
516 : /* CPLHashSetHashStr() */
517 : /************************************************************************/
518 :
519 : /**
520 : * Hash function for a zero-terminated string
521 : *
522 : * @param elt the string to hash. May be NULL.
523 : *
524 : * @return the hash value of the string
525 : */
526 :
527 : CPL_NOSANITIZE_UNSIGNED_INT_OVERFLOW
528 55105 : unsigned long CPLHashSetHashStr(const void *elt)
529 : {
530 55105 : if (elt == nullptr)
531 10 : return 0;
532 :
533 55095 : const unsigned char *pszStr = static_cast<const unsigned char *>(elt);
534 55095 : unsigned long hash = 0;
535 :
536 55095 : int c = 0;
537 1104240 : while ((c = *pszStr++) != '\0')
538 1049140 : hash = c + (hash << 6) + (hash << 16) - hash;
539 :
540 55095 : return hash;
541 : }
542 :
543 : /************************************************************************/
544 : /* CPLHashSetEqualStr() */
545 : /************************************************************************/
546 :
547 : /**
548 : * Equality function for strings
549 : *
550 : * @param elt1 the first string to compare. May be NULL.
551 : * @param elt2 the second string to compare. May be NULL.
552 : *
553 : * @return TRUE if the strings are equal
554 : */
555 :
556 98 : int CPLHashSetEqualStr(const void *elt1, const void *elt2)
557 : {
558 98 : const char *pszStr1 = static_cast<const char *>(elt1);
559 98 : const char *pszStr2 = static_cast<const char *>(elt2);
560 :
561 98 : if (pszStr1 == nullptr && pszStr2 != nullptr)
562 0 : return FALSE;
563 :
564 98 : if (pszStr1 != nullptr && pszStr2 == nullptr)
565 0 : return FALSE;
566 :
567 98 : if (pszStr1 == nullptr && pszStr2 == nullptr)
568 2 : return TRUE;
569 :
570 96 : return strcmp(pszStr1, pszStr2) == 0;
571 : }
|
