le_hashmap.h

    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
  183 typedef le_sls_List_t le_hashmap_Bucket_t;
  184 typedef le_sls_Link_t le_hashmap_Link_t;
  185 #else /* if not LE_CONFIG_REDUCE_FOOTPRINT */
  186 typedef le_dls_List_t le_hashmap_Bucket_t;
  187 typedef le_dls_Link_t le_hashmap_Link_t;
  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 }
  266 le_hashmap_Entry_t;
  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 }
  278 le_hashmap_HashmapIt_t;
  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 }
  302 le_hashmap_Hashmap_t;
  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 //--------------------------------------------------------------------------------------------------
  323 le_hashmap_Ref_t le_hashmap_Create
  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 //--------------------------------------------------------------------------------------------------
  361 LE_DECLARE_INLINE le_hashmap_Ref_t le_hashmap_Create
  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 //--------------------------------------------------------------------------------------------------
  549 void* le_hashmap_GetStoredKey
  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 
  579 bool le_hashmap_isEmpty
  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 
  607 bool le_hashmap_ContainsKey
  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 
  622 void le_hashmap_RemoveAll
  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 //--------------------------------------------------------------------------------------------------
  636 bool le_hashmap_ForEach
  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 //--------------------------------------------------------------------------------------------------
  657 le_hashmap_It_Ref_t le_hashmap_GetIterator
  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 //--------------------------------------------------------------------------------------------------
  671 le_result_t le_hashmap_NextNode
  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 //--------------------------------------------------------------------------------------------------
  685 le_result_t le_hashmap_PrevNode
  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 //--------------------------------------------------------------------------------------------------
  717 void* le_hashmap_GetValue
  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 //--------------------------------------------------------------------------------------------------
  735 le_result_t le_hashmap_GetFirstNode
  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 //--------------------------------------------------------------------------------------------------
  756 le_result_t le_hashmap_GetNodeAfter
  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 
  775 size_t le_hashmap_CountCollisions
  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 
  790 size_t le_hashmap_HashString
  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 
  805 bool le_hashmap_EqualsString
  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 
  821 size_t le_hashmap_HashUInt32
  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 
  836 bool le_hashmap_EqualsUInt32
  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 
  852 size_t le_hashmap_HashUInt64
  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 
  867 bool le_hashmap_EqualsUInt64
  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 
  883 size_t le_hashmap_HashVoidPointer
  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 
  898 bool le_hashmap_EqualsVoidPointer
  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 //--------------------------------------------------------------------------------------------------
  945 void le_hashmap_MakeTraceable
  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 //--------------------------------------------------------------------------------------------------
  956 void le_hashmap_EnableTrace
  957 (
  958     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  959 );
  960 
  961 
  962 #endif /* LEGATO_HASHMAP_INCLUDE_GUARD */
le_hashmap_GetKey
const void * le_hashmap_GetKey(le_hashmap_It_Ref_t iteratorRef)
le_hashmap_Hashmap_t
Definition: le_hashmap.h:285
le_hashmap_HashmapIt_t
Definition: le_hashmap.h:273
le_hashmap_EnableTrace
void le_hashmap_EnableTrace(le_hashmap_Ref_t mapRef)
le_sls_Link_t
Definition: le_singlyLinkedList.h:186
le_hashmap_ForEach
bool le_hashmap_ForEach(le_hashmap_Ref_t mapRef, le_hashmap_ForEachHandler_t forEachFn, void *contextPtr)
le_hashmap_GetStoredKey
void * le_hashmap_GetStoredKey(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_hashmap_Hashmap_t::traceRef
le_log_TraceRef_t traceRef
Log trace reference for debugging the hashmap. 
Definition: le_hashmap.h:299
le_result_t
le_result_t
Definition: le_basics.h:45
le_hashmap_GetIterator
le_hashmap_It_Ref_t le_hashmap_GetIterator(le_hashmap_Ref_t mapRef)
le_hashmap_It_Ref_t
struct le_hashmap_It * le_hashmap_It_Ref_t
Definition: le_hashmap.h:202
LE_UNUSED
#define LE_UNUSED(v)
Definition: le_basics.h:366
le_hashmap_Hashmap_t::bucketsPtr
le_hashmap_Bucket_t * bucketsPtr
Pointer to the array of hash map buckets. 
Definition: le_hashmap.h:292
le_hashmap_HashFunc_t
size_t(* le_hashmap_HashFunc_t)(const void *keyToHashPtr)
Definition: le_hashmap.h:214
le_hashmap_Hashmap_t::hashFuncPtr
le_hashmap_HashFunc_t hashFuncPtr
Hash operator. 
Definition: le_hashmap.h:290
le_hashmap_Ref_t
struct le_hashmap * le_hashmap_Ref_t
Definition: le_hashmap.h:195
le_hashmap_Hashmap_t::iterator
le_hashmap_HashmapIt_t iterator
Iterator instance. 
Definition: le_hashmap.h:287
le_hashmap_Size
size_t le_hashmap_Size(le_hashmap_Ref_t mapRef)
le_hashmap_EqualsString
bool le_hashmap_EqualsString(const void *firstStringPtr, const void *secondStringPtr)
le_hashmap_Entry_t
Definition: le_hashmap.h:260
le_hashmap_HashUInt32
size_t le_hashmap_HashUInt32(const void *intToHashPtr)
le_hashmap_HashString
size_t le_hashmap_HashString(const void *stringToHashPtr)
le_hashmap_HashmapIt_t::currentLinkPtr
le_hashmap_Link_t * currentLinkPtr
Current bucket list item pointer. 
Definition: le_hashmap.h:276
le_doublyLinkedList.h
le_hashmap_Create
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
le_hashmap_isEmpty
bool le_hashmap_isEmpty(le_hashmap_Ref_t mapRef)
le_hashmap_EqualsVoidPointer
bool le_hashmap_EqualsVoidPointer(const void *firstVoidPtr, const void *secondVoidPtr)
le_hashmap_Hashmap_t::size
size_t size
Number of inserted entries. 
Definition: le_hashmap.h:295
le_hashmap_Put
void * le_hashmap_Put(le_hashmap_Ref_t mapRef, const void *keyPtr, const void *valuePtr)
*/ 
le_hashmap_Hashmap_t::entryPoolRef
le_mem_PoolRef_t entryPoolRef
Memory pool to expand into for expanding buckets. 
Definition: le_hashmap.h:293
le_hashmap_GetValue
void * le_hashmap_GetValue(le_hashmap_It_Ref_t iteratorRef)
le_mem_PoolRef_t
struct le_mem_Pool * le_mem_PoolRef_t
Definition: le_mem.h:542
le_hashmap_EqualsFunc_t
bool(* le_hashmap_EqualsFunc_t)(const void *firstKeyPtr, const void *secondKeyPtr)
Definition: le_hashmap.h:230
le_hashmap_Entry_t::entryListLink
le_hashmap_Link_t entryListLink
Next entry in bucket. 
Definition: le_hashmap.h:262
le_hashmap_ForEachHandler_t
bool(* le_hashmap_ForEachHandler_t)(const void *keyPtr, const void *valuePtr, void *contextPtr)
Definition: le_hashmap.h:248
le_hashmap_CountCollisions
size_t le_hashmap_CountCollisions(le_hashmap_Ref_t mapRef)
le_hashmap_GetFirstNode
le_result_t le_hashmap_GetFirstNode(le_hashmap_Ref_t mapRef, void **firstKeyPtr, void **firstValuePtr)
le_hashmap_HashVoidPointer
size_t le_hashmap_HashVoidPointer(const void *voidToHashPtr)
le_hashmap_MakeTraceable
void le_hashmap_MakeTraceable(le_hashmap_Ref_t mapRef)
le_hashmap_Entry_t::valuePtr
const void * valuePtr
Pointer to value data. 
Definition: le_hashmap.h:264
le_hashmap_Remove
void * le_hashmap_Remove(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_hashmap_Entry_t::keyPtr
const void * keyPtr
Pointer to key data. 
Definition: le_hashmap.h:263
le_hashmap_Hashmap_t::equalsFuncPtr
le_hashmap_EqualsFunc_t equalsFuncPtr
Equality operator. 
Definition: le_hashmap.h:289
le_hashmap_ContainsKey
bool le_hashmap_ContainsKey(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_sls_List_t
Definition: le_singlyLinkedList.h:201
le_singlyLinkedList.h
le_hashmap_RemoveAll
void le_hashmap_RemoveAll(le_hashmap_Ref_t mapRef)
le_hashmap_EqualsUInt64
bool le_hashmap_EqualsUInt64(const void *firstIntPtr, const void *secondIntPtr)
le_hashmap_Hashmap_t::nameStr
const char * nameStr
Name of the hashmap for diagnostic purposes. 
Definition: le_hashmap.h:298
le_hashmap_Get
void * le_hashmap_Get(le_hashmap_Ref_t mapRef, const void *keyPtr)
le_dls_Link_t
Definition: le_doublyLinkedList.h:200
le_hashmap_NextNode
le_result_t le_hashmap_NextNode(le_hashmap_It_Ref_t iteratorRef)
le_mem.h
le_hashmap_Hashmap_t::bucketCount
size_t bucketCount
Number of buckets. 
Definition: le_hashmap.h:294
le_dls_List_t
Definition: le_doublyLinkedList.h:216
le_hashmap_EqualsUInt32
bool le_hashmap_EqualsUInt32(const void *firstIntPtr, const void *secondIntPtr)
le_hashmap_HashUInt64
size_t le_hashmap_HashUInt64(const void *intToHashPtr)
le_hashmap_HashmapIt_t::currentIndex
size_t currentIndex
Current bucket index. 
Definition: le_hashmap.h:275
le_hashmap_PrevNode
le_result_t le_hashmap_PrevNode(le_hashmap_It_Ref_t iteratorRef)
LE_DECLARE_INLINE
#define LE_DECLARE_INLINE
Definition: le_basics.h:317
le_hashmap_GetNodeAfter
le_result_t le_hashmap_GetNodeAfter(le_hashmap_Ref_t mapRef, const void *keyPtr, void **nextKeyPtr, void **nextValuePtr)