le_hashmap.h

Go to the documentation of this file.
1 /**
2  * @page c_hashmap HashMap API
3  *
4  * @subpage le_hashmap.h "API Reference"
5  *
6  * <HR>
7  *
8  * This API provides a straightforward HashMap implementation.
9  *
10  * @section c_hashmap_create Creating a HashMap
11  *
12  * There are two methods to create a hashmap. Either use @c le_hashmap_Create() to create
13  * a hashmap on the heap, or use LE_HASHMAP_DEFINE_STATIC to define space for a hashmap,
14  * then use @c le_hashmap_InitStatic() to initialize the hashmap. It's the responsibility of
15  * the caller to maintain type integrity using this function's parameters.
16  * It's important to supply hash and equality functions that operate on the
17  * type of key that you intend to store. It's unwise to mix types in a single table because
18  * implementation of the table has no way to detect this behaviour.
19  *
20  * Choose the initial size should carefully as the index size remains fixed. The best
21  * choice for the initial size is a prime number slightly larger than the
22  * maximum expected capacity. If a too small size is chosen, there will be an
23  * increase in collisions that degrade performance over time.
24  *
25  * All hashmaps have names for diagnostic purposes.
26  *
27  * @section c_hashmap_insert Adding key-value pairs
28  *
29  * Key-value pairs are added using le_hashmap_Put(). For example:
30  *
31  * @code
32  * static void StoreStuff(const char* keyStr, const char* valueStr)
33  * {
34  * myTable = le_hashmap_Create(
35  * "My Table",
36  * 31,
37  * le_hashmap_HashString,
38  * le_hashmap_EqualsString
39  * );
40  *
41  * le_hashmap_Put(myTable, keyStr, valueStr);
42  * ....
43  * }
44  * @endcode
45  *
46  * The table does not take control of the keys or values. The map only stores the pointers
47  * to these values, not the values themselves. It's the responsibility of the caller to manage
48  * the actual data storage.
49  *
50  * @subsection c_hashmap_tips Tip
51  *
52  * The code sample shows some pre-defined functions for certain
53  * key types. The key types supported are uint32_t, uint64_t and strings. The strings must be
54  * NULL terminated.
55  *
56  * Tables can also have their own hash and equality functions,
57  * but ensure the functions work on the type of key you're
58  * storing. The hash function should provide a good distribution of values. It
59  * is not required that they be unique.
60  *
61  * @section c_hashmap_iterating Iterating over a map
62  *
63  * This API allows the user of the map to iterate over the entire
64  * map, acting on each key-value pair. You supply a callback function conforming
65  * to the prototype:
66  * @code
67  * bool (*callback)(void* key, void* value, void* context)
68  * @endcode
69  *
70  * This can then be used to process every value in the map. The return value from the
71  * callback function determines if iteration should continue or stop. If the function
72  * returns false then iteration will cease. For example:
73  *
74  * @code
75  * bool ProcessTableData
76  * (
77  * void* keyPtr, // Pointer to the map entry's key
78  * void* valuePtr, // Pointer to the map entry's value
79  * void* contextPtr // Pointer to an abritrary context for the callback function
80  * )
81  * {
82  * int keyCheck = *((int*)context);
83  * int currentKey = *((int*)key);
84  *
85  * if (keyCheck == currentKey) return false;
86  *
87  * // Do some stuff, maybe print out data or do a calculation
88  * return true;
89  * }
90  *
91  * {
92  * // ... somewhere else in the code ...
93  * int lastKey = 10;
94  * le_hashmap_ForEach (myTable, processTableData, &lastKey);
95  * }
96  * @endcode
97  *
98  * This code sample shows the callback function must also be aware of the
99  * types stored in the table.
100  *
101  * However, keep in mind that it is unsafe and undefined to modify the map during
102  * this style of iteration.
103  *
104  * Alternatively, the calling function can control the iteration by first
105  * calling @c le_hashmap_GetIterator(). This returns an iterator that is ready
106  * to return each key/value pair in the map in the order in which they are
107  * stored. The iterator is controlled by calling @c le_hashmap_NextNode(), and must
108  * be called before accessing any elements. You can then retrieve pointers to
109  * the key and value by using le_hashmap_GetKey() and le_hashmap_GetValue().
110  *
111  * @note There is only one iterator per hashtable. Calling le_hashmap_GetIterator()
112  * will simply re-initialize the current iterator
113  *
114  * It is possible to add and remove items during this style of iteration. When
115  * adding items during an iteration it is not guaranteed that the newly added item
116  * will be iterated over. It's very possible that the newly added item is added in
117  * an earlier location than the iterator is curently pointed at.
118  *
119  * When removing items during an iteration you also have to keep in mind that the
120  * iterator's current item may be the one removed. If this is the case,
121  * le_hashmap_GetKey, and le_hashmap_GetValue will return NULL until either,
122  * le_hashmap_NextNode, or le_hashmap_PrevNode are called.
123  *
124  * For example (assuming a table of string/string):
125  *
126  * @code
127  * void ProcessTable(le_hashmap_Ref_t myTable)
128  * {
129  * char* nextKey;
130  * char* nextVal;
131  *
132  * le_hashmap_It_Ref_t myIter = le_hashmap_GetIterator(myTable);
133  *
134  * while (LE_OK == le_hashmap_NextNode(myIter))
135  * {
136  * // Do something with the strings
137  * nextKey = le_hashmap_GetKey(myIter);
138  * nextVal = le_hashmap_GetValue(myIter);
139  * }
140  * }
141  * @endcode
142  *
143  * If you need to control access to the hashmap, then a mutex can be used.
144  *
145  * @section c_hashmap_tracing Tracing a map
146  *
147  * Hashmaps can be traced using the logging system.
148  *
149  * If @c le_hashmap_MakeTraceable() is called for a specified hashmap object, the name of that
150  * hashmap (the name passed into le_hashmap_Create() ) becomes a trace keyword
151  * to enable and disable tracing of that particular hashmap.
152  *
153  * If @c le_hashmap_EnableTrace() is called for a hashmap object, tracing is
154  * immediately activated for that hashmap.
155  *
156  * See @ref c_log_controlling for more information on how to enable and disable tracing using
157  * configuration and/or the log control tool.
158  *
159  * <HR>
160  *
161  * Copyright (C) Sierra Wireless Inc.
162  */
163 
164 //--------------------------------------------------------------------------------------------------
165 /**
166  * @file le_hashmap.h
167  *
168  * Legato @ref c_hashmap include file.
169  *
170  * Copyright (C) Sierra Wireless Inc.
171  */
172 //--------------------------------------------------------------------------------------------------
173 
174 #ifndef LEGATO_HASHMAP_INCLUDE_GUARD
175 #define LEGATO_HASHMAP_INCLUDE_GUARD
176 
177 #include "le_mem.h"
178 
179 #include "le_singlyLinkedList.h"
180 #include "le_doublyLinkedList.h"
181 
182 #if LE_CONFIG_REDUCE_FOOTPRINT
185 #else /* if not LE_CONFIG_REDUCE_FOOTPRINT */
188 #endif /* end LE_CONFIG_REDUCE_FOOTPRINT */
189 
190 //--------------------------------------------------------------------------------------------------
191 /**
192  * Reference to a HashMap.
193  */
194 //--------------------------------------------------------------------------------------------------
195 typedef struct le_hashmap* le_hashmap_Ref_t;
196 
197 //--------------------------------------------------------------------------------------------------
198 /**
199  * Reference to a HashMap Iterator.
200  */
201 //--------------------------------------------------------------------------------------------------
202 typedef struct le_hashmap_It* le_hashmap_It_Ref_t;
203 
204 //--------------------------------------------------------------------------------------------------
205 /**
206  * Prototype for hash functions. The hash function must generate a good spread of hashes without
207  * consuming lots of processing power.
208  *
209  * @param keyToHashPtr Pointer to the key which will be hashed
210  * @return The calculated hash value
211  */
212 //--------------------------------------------------------------------------------------------------
213 typedef size_t (*le_hashmap_HashFunc_t)
214 (
215  const void* keyToHashPtr
216 );
217 
218 //--------------------------------------------------------------------------------------------------
219 /**
220  * Prototype for equality functions. The equality function returns true if the the keys point to
221  * values are equivalent. The HashMap doesn't know in advance which types are to be stored so
222  * this function must be supplied by the caller.
223  *
224  * @param firstKeyPtr Pointer to the first key for comparing.
225  * @param secondKeyPtr Pointer to the second key for comparing.
226  * @return Returns true if the values are the same, false otherwise
227  */
228 //--------------------------------------------------------------------------------------------------
229 typedef bool (*le_hashmap_EqualsFunc_t)
230 (
231  const void* firstKeyPtr,
232  const void* secondKeyPtr
233 );
234 
235 
236 //--------------------------------------------------------------------------------------------------
237 /**
238  * Prototype for callback functions for the iterator function le_hashmap_ForEach(). This function should
239  * return true in order to continue iterating, or false to stop.
240  *
241  * @param keyPtr Pointer to the key at the current position in the map
242  * @param valuePtr Pointer to the value associated to this key
243  * @param contextPtr Pointer to the context supplied to le_hashmap_ForEach()
244  * @return Returns true to continue, false to stop
245  */
246 //--------------------------------------------------------------------------------------------------
247 typedef bool (*le_hashmap_ForEachHandler_t)
248 (
249  const void* keyPtr,
250  const void* valuePtr,
251  void* contextPtr
252 );
253 
254 
255 /**
256  * A struct to hold the data in the table
257  *
258  * @note This is an internal structure which should not be instantiated directly
259  */
260 typedef struct le_hashmap_Entry
261 {
262  le_hashmap_Link_t entryListLink; ///< Next entry in bucket.
263  const void *keyPtr; ///< Pointer to key data.
264  const void *valuePtr; ///< Pointer to value data.
265 }
267 
268 /**
269  * A hashmap iterator
270  *
271  * @note This is an internal structure which should not be instantiated directly
272  */
273 typedef struct le_hashmap_It
274 {
275  size_t currentIndex; ///< Current bucket index.
276  le_hashmap_Link_t *currentLinkPtr; ///< Current bucket list item pointer.
277 }
279 
280 /**
281  * The hashmap itself
282  *
283  * @note This is an internal structure which should not be instantiated directly
284  */
285 typedef struct le_hashmap
286 {
287  le_hashmap_HashmapIt_t iterator; ///< Iterator instance.
288 
289  le_hashmap_EqualsFunc_t equalsFuncPtr; ///< Equality operator.
290  le_hashmap_HashFunc_t hashFuncPtr; ///< Hash operator.
291 
292  le_hashmap_Bucket_t *bucketsPtr; ///< Pointer to the array of hash map buckets.
293  le_mem_PoolRef_t entryPoolRef; ///< Memory pool to expand into for expanding buckets.
294  size_t bucketCount; ///< Number of buckets.
295  size_t size; ///< Number of inserted entries.
296 
297 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
298  const char *nameStr; ///< Name of the hashmap for diagnostic purposes.
299  le_log_TraceRef_t traceRef; ///< Log trace reference for debugging the hashmap.
300 #endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
301 }
303 
304 
305 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
306 //--------------------------------------------------------------------------------------------------
307 /**
308  * Create a HashMap.
309  *
310  * If you create a hashmap with a smaller capacity than you actually use, then
311  * the map will continue to work, but performance will degrade the more you put in the map.
312  *
313  * @param[in] nameStr Name of the HashMap. This must be a static string as it is not copied.
314  * @param[in] capacity Size of the hashmap
315  * @param[in] hashFunc Hash function
316  * @param[in] equalsFunc Equality function
317  *
318  * @return Returns a reference to the map.
319  *
320  * @note Terminates the process on failure, so no need to check the return value for errors.
321  */
322 //--------------------------------------------------------------------------------------------------
324 (
325  const char *nameStr,
326  size_t capacity,
327  le_hashmap_HashFunc_t hashFunc,
328  le_hashmap_EqualsFunc_t equalsFunc
329 );
330 #else /* if not LE_CONFIG_HASHMAP_NAMES_ENABLED */
331 /// @cond HIDDEN_IN_USER_DOCS
332 //--------------------------------------------------------------------------------------------------
333 /**
334  * Internal function used to implement le_hashmap_Create().
335  */
336 //--------------------------------------------------------------------------------------------------
337 le_hashmap_Ref_t _le_hashmap_Create
338 (
339  size_t capacity,
340  le_hashmap_HashFunc_t hashFunc,
341  le_hashmap_EqualsFunc_t equalsFunc
342 );
343 /// @endcond
344 //--------------------------------------------------------------------------------------------------
345 /**
346  * Create a HashMap.
347  *
348  * If you create a hashmap with a smaller capacity than you actually use, then
349  * the map will continue to work, but performance will degrade the more you put in the map.
350  *
351  * @param[in] nameStr Name of the HashMap. This must be a static string as it is not copied.
352  * @param[in] capacity Size of the hashmap
353  * @param[in] hashFunc Hash function
354  * @param[in] equalsFunc Equality function
355  *
356  * @return Returns a reference to the map.
357  *
358  * @note Terminates the process on failure, so no need to check the return value for errors.
359  */
360 //--------------------------------------------------------------------------------------------------
362 (
363  const char *nameStr,
364  size_t capacity,
365  le_hashmap_HashFunc_t hashFunc,
366  le_hashmap_EqualsFunc_t equalsFunc
367 )
368 {
369  LE_UNUSED(nameStr);
370  return _le_hashmap_Create(capacity, hashFunc, equalsFunc);
371 }
372 #endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
373 
374 
375 
376 //--------------------------------------------------------------------------------------------------
377 /**
378  * Calculate number of buckets for a hashmap of a given size
379  *
380  * 0.75 load factor. We have more buckets than expected keys as we want
381  * to reduce the chance of collisions. 1-1 would assume a perfect hashing
382  * function which is rather unlikely. Also, ensure that the capacity is
383  * at least 3 which avoids strange issues in the hashing algorithm
384  *
385  * @note Used internally to calculate static hashmap sizes. Should not be used by users
386  * of liblegato. Caps out at 65536 entries
387  */
388 //--------------------------------------------------------------------------------------------------
389 #define LE_HASHMAP_BUCKET_COUNT(capacity) \
390  ((capacity)*4/3<=0x4?0x4: \
391  ((capacity)*4/3<=0x8?0x8: \
392  ((capacity)*4/3<=0x10?0x10: \
393  ((capacity)*4/3<=0x20?0x20: \
394  ((capacity)*4/3<=0x40?0x40: \
395  ((capacity)*4/3<=0x80?0x80: \
396  ((capacity)*4/3<=0x100?0x100: \
397  ((capacity)*4/3<=0x200?0x200: \
398  ((capacity)*4/3<=0x400?0x400: \
399  ((capacity)*4/3<=0x800?0x800: \
400  ((capacity)*4/3<=0x1000?0x1000: \
401  ((capacity)*4/3<=0x2000?0x2000: \
402  ((capacity)*4/3<=0x4000?0x4000: \
403  ((capacity)*4/3<=0x8000?0x8000: \
404  0x10000))))))))))))))
405 
406 //--------------------------------------------------------------------------------------------------
407 /**
408  * Statically define a hash-map.
409  *
410  * This allocates all the space required for a hash-map at file scope so no dynamic memory
411  * is needed for the hash map. This allows a better estimate of memory usage of an app
412  * to be obtained by examining the linker map, and ensures initializing the static map
413  * will not fail at run-time.
414  *
415  * @note Dynamic hash maps set initial pool to bucket count/2, static hash maps set
416  * pool size to capacity to avoid overflowing the pool.
417  */
418 //--------------------------------------------------------------------------------------------------
419 #define LE_HASHMAP_DEFINE_STATIC(name, capacity) \
420  static le_hashmap_Hashmap_t _hashmap_##name##Hashmap; \
421  LE_MEM_DEFINE_STATIC_POOL(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t)); \
422  static le_hashmap_Bucket_t _hashmap_##name##Buckets[LE_HASHMAP_BUCKET_COUNT(capacity)]
423 
424 //--------------------------------------------------------------------------------------------------
425 /**
426  * Statically define a hash-map in a specific memory section
427  *
428  * By default static memory will the assigned to the bss or data section of the final object.
429  * This macro tells the linker to assign to variable to a specific section, sectionName.
430  * Essentially a "__attribute__((section("sectionName")))" will be added after the variable
431  * declaration.
432  *
433  * @note Dynamic hash maps set initial pool to bucket count/2, static hash maps set
434  * pool size to capacity to avoid overflowing the pool.
435  */
436 //--------------------------------------------------------------------------------------------------
437 #define LE_HASHMAP_DEFINE_STATIC_IN_SECTION(name, capacity, sectionName) \
438  static le_hashmap_Hashmap_t _hashmap_##name##Hashmap __attribute__((section(sectionName))); \
439  LE_MEM_DEFINE_STATIC_POOL_IN_SECTION(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t), \
440  sectionName); \
441  static le_hashmap_Bucket_t _hashmap_##name##Buckets[ \
442  LE_HASHMAP_BUCKET_COUNT(capacity)] __attribute__((section(sectionName)))
443 
444 //--------------------------------------------------------------------------------------------------
445 /**
446  * Initialize a statically-defined hashmap
447  *
448  * If you create a hashmap with a smaller capacity than you actually use, then
449  * the map will continue to work, but performance will degrade the more you put in the map.
450  *
451  * @param name Name used when defining the static hashmap.
452  * @param capacity Capacity specified when defining the static hashmap.
453  * @param hashFunc Callback to invoke to hash an entry's key.
454  * @param equalsFunc Callback to invoke to test key equality.
455  *
456  * @return Returns a reference to the map.
457  */
458 //--------------------------------------------------------------------------------------------------
459 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
460 # define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc) \
461  (inline_static_assert( \
462  sizeof(_hashmap_##name##Buckets) == \
463  sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]), \
464  "hashmap init capacity does not match definition"), \
465  _le_hashmap_InitStatic(#name, (capacity), (hashFunc), (equalsFunc), \
466  &_hashmap_##name##Hashmap, \
467  le_mem_InitStaticPool(_hashmap_##name, \
468  (capacity), \
469  sizeof(le_hashmap_Entry_t)), \
470  _hashmap_##name##Buckets))
471 #else
472 # define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc) \
473  (inline_static_assert( \
474  sizeof(_hashmap_##name##Buckets) == \
475  sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]), \
476  "hashmap init capacity does not match definition"), \
477  _le_hashmap_InitStatic((capacity), (hashFunc), (equalsFunc), \
478  &_hashmap_##name##Hashmap, \
479  le_mem_InitStaticPool(_hashmap_##name, \
480  (capacity), \
481  sizeof(le_hashmap_Entry_t)), \
482  _hashmap_##name##Buckets))
483 #endif
484 
485 /// @cond HIDDEN_IN_USER_DOCS
486 //--------------------------------------------------------------------------------------------------
487 /**
488  * Internal function to initialize a statically-defined hashmap
489  *
490  * @note use le_hashmap_InitStatic() macro instead
491  */
492 //--------------------------------------------------------------------------------------------------
493 le_hashmap_Ref_t _le_hashmap_InitStatic
494 (
495 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
496  const char *nameStr, ///< [in] Name of the HashMap
497 #endif
498  size_t capacity, ///< [in] Expected capacity of the map
499  le_hashmap_HashFunc_t hashFunc, ///< [in] The hash function
500  le_hashmap_EqualsFunc_t equalsFunc, ///< [in] The equality function
501  le_hashmap_Hashmap_t *mapPtr, ///< [in] The static hash map to initialize
502  le_mem_PoolRef_t entryPoolRef, ///< [in] The memory pool for map entries
503  le_hashmap_Bucket_t *bucketsPtr ///< [in] The buckets
504 );
505 /// @endcond
506 
507 
508 //--------------------------------------------------------------------------------------------------
509 /**
510  * Add a key-value pair to a HashMap. If the key already exists in the map, the previous value
511  * will be replaced with the new value passed into this function.
512  *
513  * @return Returns NULL for a new entry or a pointer to the old value if it is replaced.
514  *
515  */
516 //--------------------------------------------------------------------------------------------------
517 
518 void* le_hashmap_Put
519 (
520  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
521  const void* keyPtr, ///< [in] Pointer to the key to be stored.
522  const void* valuePtr ///< [in] Pointer to the value to be stored.
523 );
524 
525 //--------------------------------------------------------------------------------------------------
526 /**
527  * Retrieve a value from a HashMap.
528  *
529  * @return Returns a pointer to the value or NULL if the key is not found.
530  *
531  */
532 //--------------------------------------------------------------------------------------------------
533 
534 void* le_hashmap_Get
535 (
536  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
537  const void* keyPtr ///< [in] Pointer to the key to be retrieved.
538 );
539 
540 //--------------------------------------------------------------------------------------------------
541 /**
542  * Retrieve a stored key from a HashMap.
543  *
544  * @return Returns a pointer to the key that was stored in the HashMap by le_hashmap_Put() or
545  * NULL if the key is not found.
546  *
547  */
548 //--------------------------------------------------------------------------------------------------
550 (
551  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
552  const void* keyPtr ///< [in] Pointer to the key to be retrieved.
553 );
554 
555 //--------------------------------------------------------------------------------------------------
556 /**
557  * Remove a value from a HashMap.
558  *
559  * @return Returns a pointer to the value or NULL if the key is not found.
560  *
561  */
562 //--------------------------------------------------------------------------------------------------
563 
564 void* le_hashmap_Remove
565 (
566  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
567  const void* keyPtr ///< [in] Pointer to the key to be removed.
568 );
569 
570 //--------------------------------------------------------------------------------------------------
571 /**
572  * Tests if the HashMap is empty (i.e. contains zero keys).
573  *
574  * @return Returns true if empty, false otherwise.
575  *
576  */
577 //--------------------------------------------------------------------------------------------------
578 
580 (
581  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
582 );
583 
584 //--------------------------------------------------------------------------------------------------
585 /**
586  * Calculates the number of keys in the HashMap.
587  *
588  * @return The number of keys in the HashMap.
589  *
590  */
591 //--------------------------------------------------------------------------------------------------
592 
593 size_t le_hashmap_Size
594 (
595  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
596 );
597 
598 //--------------------------------------------------------------------------------------------------
599 /**
600  * Tests if the HashMap contains a particular key.
601  *
602  * @return Returns true if the key is found, false otherwise.
603  *
604  */
605 //--------------------------------------------------------------------------------------------------
606 
608 (
609  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
610  const void* keyPtr ///< [in] Pointer to the key to be searched.
611 );
612 
613 //--------------------------------------------------------------------------------------------------
614 /**
615  * Deletes all the entries held in the hashmap. This will not delete the data pointed to by the
616  * key and value pointers. That cleanup is the responsibility of the caller.
617  * This allows the map to be re-used. Currently maps can't be deleted.
618  *
619  */
620 //--------------------------------------------------------------------------------------------------
621 
623 (
624  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
625 );
626 
627 //--------------------------------------------------------------------------------------------------
628 /**
629  * Iterates over the whole map, calling the supplied callback with each key-value pair. If the callback
630  * returns false for any key then this function will return.
631  *
632  * @return Returns true if all elements were checked; or false if iteration was stopped early
633  *
634  */
635 //--------------------------------------------------------------------------------------------------
637 (
638  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map.
639  le_hashmap_ForEachHandler_t forEachFn, ///< [in] Callback function to be called with each pair.
640  void* contextPtr ///< [in] Pointer to a context to be supplied to the callback.
641 );
642 
643 //--------------------------------------------------------------------------------------------------
644 /**
645  * Gets an iterator for step-by-step iteration over the map. In this mode,
646  * the iteration is controlled by the calling function using the le_hashmap_NextNode() function.
647  * There is one iterator per map, and calling this function resets the
648  * iterator position to the start of the map.
649  * The iterator is not ready for data access until le_hashmap_NextNode() has been called
650  * at least once.
651  *
652  * @return Returns A reference to a hashmap iterator which is ready
653  * for le_hashmap_NextNode() to be called on it
654  *
655  */
656 //--------------------------------------------------------------------------------------------------
658 (
659  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
660 );
661 
662 //--------------------------------------------------------------------------------------------------
663 /**
664  * Moves the iterator to the next key/value pair in the map. Order is dependent
665  * on the hash algorithm and the order of inserts, and is not sorted at all.
666  *
667  * @return Returns LE_OK unless you go past the end of the map, then returns LE_NOT_FOUND.
668  *
669  */
670 //--------------------------------------------------------------------------------------------------
672 (
673  le_hashmap_It_Ref_t iteratorRef ///< [IN] Reference to the iterator.
674 );
675 
676 //--------------------------------------------------------------------------------------------------
677 /**
678  * Moves the iterator to the previous key/value pair in the map. Order is dependent
679  * on the hash algorithm and the order of inserts, and is not sorted at all.
680  *
681  * @return Returns LE_OK unless you go past the beginning of the map, then returns LE_NOT_FOUND.
682  *
683  */
684 //--------------------------------------------------------------------------------------------------
686 (
687  le_hashmap_It_Ref_t iteratorRef ///< [IN] Reference to the iterator
688 );
689 
690 //--------------------------------------------------------------------------------------------------
691 /**
692  * Retrieves a pointer to the key where the iterator is currently pointing.
693  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
694  * called, or if the iterator has been invalidated, this will return NULL.
695  *
696  * @return Pointer to the current key, or NULL if the iterator has been invalidated or is not
697  * ready.
698  *
699  */
700 //--------------------------------------------------------------------------------------------------
701 const void* le_hashmap_GetKey
702 (
703  le_hashmap_It_Ref_t iteratorRef ///< [IN] Reference to the iterator.
704 );
705 
706 //--------------------------------------------------------------------------------------------------
707 /**
708  * Retrieves a pointer to the value where the iterator is currently pointing.
709  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
710  * called, or if the iterator has been invalidated, this will return NULL.
711  *
712  * @return Pointer to the current value, or NULL if the iterator has been invalidated or is not
713  * ready.
714  *
715  */
716 //--------------------------------------------------------------------------------------------------
718 (
719  le_hashmap_It_Ref_t iteratorRef ///< [IN] Reference to the iterator.
720 );
721 
722 //--------------------------------------------------------------------------------------------------
723 /**
724  * Retrieves the key and value of the first node stored in the hashmap.
725  * The hashmap is not sorted so this will simply return the first node stored in the map.
726  * There is no guarantee that a subsequent call to this function will return the same pair
727  * if new keys have been added to the map.
728  * If NULL is passed as the firstValuePointer then only the key will be returned.
729  *
730  * @return LE_OK if the first node is returned or LE_NOT_FOUND if the map is empty.
731  * LE_BAD_PARAMETER if the key is NULL.
732  *
733  */
734 //--------------------------------------------------------------------------------------------------
736 (
737  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map
738  void **firstKeyPtr, ///< [out] Pointer to the first key
739  void **firstValuePtr ///< [out] Pointer to the first value
740 );
741 
742 //--------------------------------------------------------------------------------------------------
743 /**
744  * Retrieves the key and value of the node after the passed in key.
745  * The hashmap is not sorted so this will simply return the next node stored in the map.
746  * There is no guarantee that a subsequent call to this function will return the same pair
747  * if new keys have been added to the map.
748  * If NULL is passed as the nextValuePtr then only the key will be returned.
749  *
750  * @return LE_OK if the next node is returned. If the keyPtr is not found in the
751  * map then LE_BAD_PARAMETER is returned. LE_NOT_FOUND is returned if the passed
752  * in key is the last one in the map.
753  *
754  */
755 //--------------------------------------------------------------------------------------------------
757 (
758  le_hashmap_Ref_t mapRef, ///< [in] Reference to the map
759  const void* keyPtr, ///< [in] Pointer to the key to be searched for
760  void **nextKeyPtr, ///< [out] Pointer to the first key
761  void **nextValuePtr ///< [out] Pointer to the first value
762 );
763 
764 
765 //--------------------------------------------------------------------------------------------------
766 /**
767  * Counts the total number of collisions in the map. A collision occurs
768  * when more than one entry is stored in the map at the same index.
769  *
770  * @return Returns the total collisions in the map.
771  *
772  */
773 //--------------------------------------------------------------------------------------------------
774 
776 (
777  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
778 );
779 
780 //--------------------------------------------------------------------------------------------------
781 /**
782  * String hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
783  * the table is a string.
784  *
785  * @return Returns the hash value of the string pointed to by stringToHash.
786  *
787  */
788 //--------------------------------------------------------------------------------------------------
789 
791 (
792  const void* stringToHashPtr ///< [in] Pointer to the string to be hashed.
793 );
794 
795 //--------------------------------------------------------------------------------------------------
796 /**
797  * String equality function. Can be used as a parameter to le_hashmap_Create() if the key to
798  * the table is a string
799  *
800  * @return Returns true if the strings are identical, false otherwise.
801  *
802  */
803 //--------------------------------------------------------------------------------------------------
804 
806 (
807  const void* firstStringPtr, ///< [in] Pointer to the first string for comparing.
808  const void* secondStringPtr ///< [in] Pointer to the second string for comparing.
809 );
810 
811 //--------------------------------------------------------------------------------------------------
812 /**
813  * Integer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
814  * the table is a uint32_t.
815  *
816  * @return Returns the hash value of the uint32_t pointed to by intToHash.
817  *
818  */
819 //--------------------------------------------------------------------------------------------------
820 
822 (
823  const void* intToHashPtr ///< [in] Pointer to the integer to be hashed.
824 );
825 
826 //--------------------------------------------------------------------------------------------------
827 /**
828  * Integer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
829  * the table is a uint32_t.
830  *
831  * @return Returns true if the integers are equal, false otherwise.
832  *
833  */
834 //--------------------------------------------------------------------------------------------------
835 
837 (
838  const void* firstIntPtr, ///< [in] Pointer to the first integer for comparing.
839  const void* secondIntPtr ///< [in] Pointer to the second integer for comparing.
840 );
841 
842 //--------------------------------------------------------------------------------------------------
843 /**
844  * Long integer hashing function. This can be used as a paramter to le_hashmap_Create if the key to
845  * the table is a uint64_t
846  *
847  * @return Returns the hash value of the uint64_t pointed to by intToHash
848  *
849  */
850 //--------------------------------------------------------------------------------------------------
851 
853 (
854  const void* intToHashPtr ///< [in] Pointer to the long integer to be hashed
855 );
856 
857 //--------------------------------------------------------------------------------------------------
858 /**
859  * Long integer equality function. This can be used as a paramter to le_hashmap_Create if the key to
860  * the table is a uint64_t
861  *
862  * @return Returns true if the integers are equal, false otherwise
863  *
864  */
865 //--------------------------------------------------------------------------------------------------
866 
868 (
869  const void* firstIntPtr, ///< [in] Pointer to the first long integer for comparing.
870  const void* secondIntPtr ///< [in] Pointer to the second long integer for comparing.
871 );
872 
873 //--------------------------------------------------------------------------------------------------
874 /**
875  * Pointer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
876  * the table is an pointer or reference. Simply pass in the address as the key.
877  *
878  * @return Returns the hash value of the pointer pointed to by voidToHashPtr
879  *
880  */
881 //--------------------------------------------------------------------------------------------------
882 
884 (
885  const void* voidToHashPtr ///< [in] Pointer to be hashed
886 );
887 
888 //--------------------------------------------------------------------------------------------------
889 /**
890  * Pointer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
891  * the table is an pointer or reference.
892  *
893  * @return Returns true if the pointers are equal, false otherwise
894  *
895  */
896 //--------------------------------------------------------------------------------------------------
897 
899 (
900  const void* firstVoidPtr, ///< [in] First pointer for comparing.
901  const void* secondVoidPtr ///< [in] Second pointer for comparing.
902 );
903 
904 
905 //--------------------------------------------------------------------------------------------------
906 /**
907  * Generic hash for any plain-old-datatype.
908  */
909 //--------------------------------------------------------------------------------------------------
910 #define LE_HASHMAP_MAKE_HASH(type) \
911  static size_t Hash##type \
912  ( \
913  const void* type##Name \
914  ) \
915  { \
916  size_t byte=0, hash = 0; \
917  unsigned char c; \
918  const unsigned char* ptr = type##Name; \
919  for (byte = 0; byte < sizeof(type); ++byte) \
920  { \
921  c = *ptr++; \
922  hash = c + (hash << 6) + (hash << 16) - hash; \
923  } \
924  return hash; \
925  } \
926  static bool Equals##type \
927  ( \
928  const void* first##type, \
929  const void* second##type \
930  ) \
931  { \
932  return memcmp(first##type, second##type, sizeof(type)) == 0; \
933  }
934 
935 
936 
937 //--------------------------------------------------------------------------------------------------
938 /**
939  * Makes a particular hashmap traceable without enabling the tracing. After this is called, when
940  * the trace keyword for this hashmap (the hashmap's name) is enabled for the "framework" component
941  * in the process, tracing will start. If that keyword was enabled before
942  * this function was called, tracing will start immediately when it is called.
943  **/
944 //--------------------------------------------------------------------------------------------------
946 (
947  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
948 );
949 
950 
951 //--------------------------------------------------------------------------------------------------
952 /**
953  * Immediately enables tracing on a particular hashmap object.
954  **/
955 //--------------------------------------------------------------------------------------------------
957 (
958  le_hashmap_Ref_t mapRef ///< [in] Reference to the map.
959 );
960 
961 
962 #endif /* LEGATO_HASHMAP_INCLUDE_GUARD */
const void * le_hashmap_GetKey(le_hashmap_It_Ref_t iteratorRef)
Definition: le_hashmap.h:285
Definition: le_hashmap.h:273
void le_hashmap_EnableTrace(le_hashmap_Ref_t mapRef)
bool le_hashmap_ForEach(le_hashmap_Ref_t mapRef, le_hashmap_ForEachHandler_t forEachFn, void *contextPtr)
void * le_hashmap_GetStoredKey(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_log_TraceRef_t traceRef
Log trace reference for debugging the hashmap.
Definition: le_hashmap.h:299
le_result_t
Definition: le_basics.h:46
le_hashmap_It_Ref_t le_hashmap_GetIterator(le_hashmap_Ref_t mapRef)
struct le_hashmap_It * le_hashmap_It_Ref_t
Definition: le_hashmap.h:202
#define LE_UNUSED(v)
Definition: le_basics.h:369
le_hashmap_Bucket_t * bucketsPtr
Pointer to the array of hash map buckets.
Definition: le_hashmap.h:292
size_t(* le_hashmap_HashFunc_t)(const void *keyToHashPtr)
Definition: le_hashmap.h:214
le_hashmap_HashFunc_t hashFuncPtr
Hash operator.
Definition: le_hashmap.h:290
struct le_hashmap * le_hashmap_Ref_t
Definition: le_hashmap.h:195
le_hashmap_HashmapIt_t iterator
Iterator instance.
Definition: le_hashmap.h:287
size_t le_hashmap_Size(le_hashmap_Ref_t mapRef)
bool le_hashmap_EqualsString(const void *firstStringPtr, const void *secondStringPtr)
Definition: le_hashmap.h:260
size_t le_hashmap_HashUInt32(const void *intToHashPtr)
size_t le_hashmap_HashString(const void *stringToHashPtr)
le_hashmap_Link_t * currentLinkPtr
Current bucket list item pointer.
Definition: le_hashmap.h:276
le_hashmap_Ref_t le_hashmap_Create(const char *nameStr, size_t capacity, le_hashmap_HashFunc_t hashFunc, le_hashmap_EqualsFunc_t equalsFunc)
*/
Definition: le_hashmap.h:362
bool le_hashmap_isEmpty(le_hashmap_Ref_t mapRef)
bool le_hashmap_EqualsVoidPointer(const void *firstVoidPtr, const void *secondVoidPtr)
size_t size
Number of inserted entries.
Definition: le_hashmap.h:295
void * le_hashmap_Put(le_hashmap_Ref_t mapRef, const void *keyPtr, const void *valuePtr)
*/
le_mem_PoolRef_t entryPoolRef
Memory pool to expand into for expanding buckets.
Definition: le_hashmap.h:293
void * le_hashmap_GetValue(le_hashmap_It_Ref_t iteratorRef)
struct le_mem_Pool * le_mem_PoolRef_t
Definition: le_mem.h:545
bool(* le_hashmap_EqualsFunc_t)(const void *firstKeyPtr, const void *secondKeyPtr)
Definition: le_hashmap.h:230
le_hashmap_Link_t entryListLink
Next entry in bucket.
Definition: le_hashmap.h:262
bool(* le_hashmap_ForEachHandler_t)(const void *keyPtr, const void *valuePtr, void *contextPtr)
Definition: le_hashmap.h:248
size_t le_hashmap_CountCollisions(le_hashmap_Ref_t mapRef)
le_result_t le_hashmap_GetFirstNode(le_hashmap_Ref_t mapRef, void **firstKeyPtr, void **firstValuePtr)
size_t le_hashmap_HashVoidPointer(const void *voidToHashPtr)
void le_hashmap_MakeTraceable(le_hashmap_Ref_t mapRef)
const void * valuePtr
Pointer to value data.
Definition: le_hashmap.h:264
void * le_hashmap_Remove(le_hashmap_Ref_t mapRef, const void *keyPtr)
const void * keyPtr
Pointer to key data.
Definition: le_hashmap.h:263
le_hashmap_EqualsFunc_t equalsFuncPtr
Equality operator.
Definition: le_hashmap.h:289
bool le_hashmap_ContainsKey(le_hashmap_Ref_t mapRef, const void *keyPtr)
Definition: le_singlyLinkedList.h:201
void le_hashmap_RemoveAll(le_hashmap_Ref_t mapRef)
bool le_hashmap_EqualsUInt64(const void *firstIntPtr, const void *secondIntPtr)
const char * nameStr
Name of the hashmap for diagnostic purposes.
Definition: le_hashmap.h:298
void * le_hashmap_Get(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_result_t le_hashmap_NextNode(le_hashmap_It_Ref_t iteratorRef)
size_t bucketCount
Number of buckets.
Definition: le_hashmap.h:294
Definition: le_doublyLinkedList.h:216
bool le_hashmap_EqualsUInt32(const void *firstIntPtr, const void *secondIntPtr)
size_t le_hashmap_HashUInt64(const void *intToHashPtr)
size_t currentIndex
Current bucket index.
Definition: le_hashmap.h:275
le_result_t le_hashmap_PrevNode(le_hashmap_It_Ref_t iteratorRef)
#define LE_DECLARE_INLINE
Definition: le_basics.h:320
le_result_t le_hashmap_GetNodeAfter(le_hashmap_Ref_t mapRef, const void *keyPtr, void **nextKeyPtr, void **nextValuePtr)