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 #if LE_CONFIG_REDUCE_FOOTPRINT
  178 typedef le_sls_List_t le_hashmap_Bucket_t;
  179 typedef le_sls_Link_t le_hashmap_Link_t;
  180 #else /* if not LE_CONFIG_REDUCE_FOOTPRINT */
  181 typedef le_dls_List_t le_hashmap_Bucket_t;
  182 typedef le_dls_Link_t le_hashmap_Link_t;
  183 #endif /* end LE_CONFIG_REDUCE_FOOTPRINT */
  184 
  185 //--------------------------------------------------------------------------------------------------
  186 /**
  187  * Reference to a HashMap.
  188  */
  189 //--------------------------------------------------------------------------------------------------
  190 typedef struct le_hashmap* le_hashmap_Ref_t;
  191 
  192 //--------------------------------------------------------------------------------------------------
  193 /**
  194  * Reference to a HashMap Iterator.
  195  */
  196 //--------------------------------------------------------------------------------------------------
  197 typedef struct le_hashmap_It* le_hashmap_It_Ref_t;
  198 
  199 //--------------------------------------------------------------------------------------------------
  200 /**
  201  * Prototype for hash functions.  The hash function must generate a good spread of hashes without
  202  * consuming lots of processing power.
  203  *
  204  * @param keyToHashPtr Pointer to the key which will be hashed
  205  * @return The calculated hash value
  206  */
  207 //--------------------------------------------------------------------------------------------------
  208 typedef size_t (*le_hashmap_HashFunc_t)
  209 (
  210     const void* keyToHashPtr
  211 );
  212 
  213 //--------------------------------------------------------------------------------------------------
  214 /**
  215  * Prototype for equality functions.  The equality function returns true if the the keys point to
  216  * values are equivalent. The HashMap doesn't know in advance which types are to be stored so
  217  * this function must be supplied by the caller.
  218  *
  219  * @param firstKeyPtr Pointer to the first key for comparing.
  220  * @param secondKeyPtr Pointer to the second key for comparing.
  221  * @return Returns true if the values are the same, false otherwise
  222  */
  223 //--------------------------------------------------------------------------------------------------
  224 typedef bool (*le_hashmap_EqualsFunc_t)
  225 (
  226     const void* firstKeyPtr,
  227     const void* secondKeyPtr
  228 );
  229 
  230 
  231 //--------------------------------------------------------------------------------------------------
  232 /**
  233  * Prototype for callback functions for the iterator function le_hashmap_ForEach().  This function should
  234  * return true in order to continue iterating, or false to stop.
  235  *
  236  * @param keyPtr Pointer to the key at the current position in the map
  237  * @param valuePtr Pointer to the value associated to this key
  238  * @param contextPtr Pointer to the context supplied to le_hashmap_ForEach()
  239  * @return Returns true to continue, false to stop
  240  */
  241 //--------------------------------------------------------------------------------------------------
  242 typedef bool (*le_hashmap_ForEachHandler_t)
  243 (
  244     const void* keyPtr,
  245     const void* valuePtr,
  246     void* contextPtr
  247 );
  248 
  249 
  250 /**
  251  * A struct to hold the data in the table
  252  *
  253  * @note This is an internal structure which should not be instantiated directly
  254  */
  255 typedef struct le_hashmap_Entry
  256 {
  257     le_hashmap_Link_t    entryListLink; ///< Next entry in bucket.
  258     const void          *keyPtr;        ///< Pointer to key data.
  259     const void          *valuePtr;      ///< Pointer to value data.
  260 }
  261 le_hashmap_Entry_t;
  262 
  263 /**
  264  * A hashmap iterator
  265  *
  266  * @note This is an internal structure which should not be instantiated directly
  267  */
  268 typedef struct le_hashmap_It
  269 {
  270     size_t               currentIndex;      ///< Current bucket index.
  271     le_hashmap_Link_t   *currentLinkPtr;    ///< Current bucket list item pointer.
  272 }
  273 le_hashmap_HashmapIt_t;
  274 
  275 /**
  276  *  The hashmap itself
  277  *
  278  * @note This is an internal structure which should not be instantiated directly
  279  */
  280 typedef struct le_hashmap
  281 {
  282     le_hashmap_HashmapIt_t   iterator;      ///< Iterator instance.
  283 
  284     le_hashmap_EqualsFunc_t  equalsFuncPtr; ///< Equality operator.
  285     le_hashmap_HashFunc_t    hashFuncPtr;   ///< Hash operator.
  286 
  287     le_hashmap_Bucket_t     *bucketsPtr;    ///< Pointer to the array of hash map buckets.
  288     le_mem_PoolRef_t         entryPoolRef;  ///< Memory pool to expand into for expanding buckets.
  289     size_t                   bucketCount;   ///< Number of buckets.
  290     size_t                   size;          ///< Number of inserted entries.
  291 
  292 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  293     const char               *nameStr;        ///< Name of the hashmap for diagnostic purposes.
  294     le_log_TraceRef_t         traceRef;       ///< Log trace reference for debugging the hashmap.
  295 #endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
  296 }
  297 le_hashmap_Hashmap_t;
  298 
  299 
  300 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  301 //--------------------------------------------------------------------------------------------------
  302 /**
  303  * Create a HashMap.
  304  *
  305  * If you create a hashmap with a smaller capacity than you actually use, then
  306  * the map will continue to work, but performance will degrade the more you put in the map.
  307  *
  308  *  @param[in]  nameStr     Name of the HashMap.  This must be a static string as it is not copied.
  309  *  @param[in]  capacity    Size of the hashmap
  310  *  @param[in]  hashFunc    Hash function
  311  *  @param[in]  equalsFunc  Equality function
  312  *
  313  *  @return  Returns a reference to the map.
  314  *
  315  *  @note Terminates the process on failure, so no need to check the return value for errors.
  316  */
  317 //--------------------------------------------------------------------------------------------------
  318 le_hashmap_Ref_t le_hashmap_Create
  319 (
  320     const char                *nameStr,
  321     size_t                     capacity,
  322     le_hashmap_HashFunc_t      hashFunc,
  323     le_hashmap_EqualsFunc_t    equalsFunc
  324 );
  325 #else /* if not LE_CONFIG_HASHMAP_NAMES_ENABLED */
  326 /// @cond HIDDEN_IN_USER_DOCS
  327 //--------------------------------------------------------------------------------------------------
  328 /**
  329  * Internal function used to implement le_hashmap_Create().
  330  */
  331 //--------------------------------------------------------------------------------------------------
  332 le_hashmap_Ref_t _le_hashmap_Create
  333 (
  334     size_t                     capacity,
  335     le_hashmap_HashFunc_t      hashFunc,
  336     le_hashmap_EqualsFunc_t    equalsFunc
  337 );
  338 /// @endcond
  339 //--------------------------------------------------------------------------------------------------
  340 /**
  341  * Create a HashMap.
  342  *
  343  * If you create a hashmap with a smaller capacity than you actually use, then
  344  * the map will continue to work, but performance will degrade the more you put in the map.
  345  *
  346  *  @param[in]  nameStr     Name of the HashMap.  This must be a static string as it is not copied.
  347  *  @param[in]  capacity    Size of the hashmap
  348  *  @param[in]  hashFunc    Hash function
  349  *  @param[in]  equalsFunc  Equality function
  350  *
  351  *  @return  Returns a reference to the map.
  352  *
  353  *  @note Terminates the process on failure, so no need to check the return value for errors.
  354  */
  355 //--------------------------------------------------------------------------------------------------
  356 LE_DECLARE_INLINE le_hashmap_Ref_t le_hashmap_Create
  357 (
  358     const char                *nameStr,
  359     size_t                     capacity,
  360     le_hashmap_HashFunc_t      hashFunc,
  361     le_hashmap_EqualsFunc_t    equalsFunc
  362 )
  363 {
  364     LE_UNUSED(nameStr);
  365     return _le_hashmap_Create(capacity, hashFunc, equalsFunc);
  366 }
  367 #endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
  368 
  369 
  370 
  371 //--------------------------------------------------------------------------------------------------
  372 /**
  373  * Calculate number of buckets for a hashmap of a given size
  374  *
  375  * 0.75 load factor. We have more buckets than expected keys as we want
  376  * to reduce the chance of collisions. 1-1 would assume a perfect hashing
  377  * function which is rather unlikely. Also, ensure that the capacity is
  378  * at least 3 which avoids strange issues in the hashing algorithm
  379  *
  380  * @note Used internally to calculate static hashmap sizes.  Should not be used by users
  381  * of liblegato.  Caps out at 65536 entries
  382  */
  383 //--------------------------------------------------------------------------------------------------
  384 #define LE_HASHMAP_BUCKET_COUNT(capacity)                               \
  385     ((capacity)*4/3<=0x4?0x4:                                           \
  386      ((capacity)*4/3<=0x8?0x8:                                          \
  387       ((capacity)*4/3<=0x10?0x10:                                       \
  388        ((capacity)*4/3<=0x20?0x20:                                      \
  389         ((capacity)*4/3<=0x40?0x40:                                     \
  390          ((capacity)*4/3<=0x80?0x80:                                    \
  391           ((capacity)*4/3<=0x100?0x100:                                 \
  392            ((capacity)*4/3<=0x200?0x200:                                \
  393             ((capacity)*4/3<=0x400?0x400:                               \
  394              ((capacity)*4/3<=0x800?0x800:                              \
  395               ((capacity)*4/3<=0x1000?0x1000:                           \
  396                ((capacity)*4/3<=0x2000?0x2000:                          \
  397                 ((capacity)*4/3<=0x4000?0x4000:                         \
  398                  ((capacity)*4/3<=0x8000?0x8000:                        \
  399                   0x10000))))))))))))))
  400 
  401 //--------------------------------------------------------------------------------------------------
  402 /**
  403  * Statically define a hash-map.
  404  *
  405  * This allocates all the space required for a hash-map at file scope so no dynamic memory
  406  * is needed for the hash map.  This allows a better estimate of memory usage of an app
  407  * to be obtained by examining the linker map, and ensures initializing the static map
  408  * will not fail at run-time.
  409  *
  410  * @note Dynamic hash maps set initial pool to bucket count/2, static hash maps set
  411  * pool size to capacity to avoid overflowing the pool.
  412  */
  413 //--------------------------------------------------------------------------------------------------
  414 #define LE_HASHMAP_DEFINE_STATIC(name, capacity)                                          \
  415     static le_hashmap_Hashmap_t _hashmap_##name##Hashmap;                                 \
  416     LE_MEM_DEFINE_STATIC_POOL(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t));   \
  417     static le_hashmap_Bucket_t _hashmap_##name##Buckets[LE_HASHMAP_BUCKET_COUNT(capacity)]
  418 
  419 
  420 //--------------------------------------------------------------------------------------------------
  421 /**
  422  * Initialize a statically-defined hashmap
  423  *
  424  * If you create a hashmap with a smaller capacity than you actually use, then
  425  * the map will continue to work, but performance will degrade the more you put in the map.
  426  *
  427  *  @param  name        Name used when defining the static hashmap.
  428  *  @param  capacity    Capacity specified when defining the static hashmap.
  429  *  @param  hashFunc    Callback to invoke to hash an entry's key.
  430  *  @param  equalsFunc  Callback to invoke to test key equality.
  431  *
  432  *  @return  Returns a reference to the map.
  433  */
  434 //--------------------------------------------------------------------------------------------------
  435 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  436 #   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
  437         (inline_static_assert(                                                      \
  438             sizeof(_hashmap_##name##Buckets) ==                                     \
  439                 sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
  440             "hashmap init capacity does not match definition"),                     \
  441         _le_hashmap_InitStatic(#name, (capacity), (hashFunc), (equalsFunc),         \
  442                                &_hashmap_##name##Hashmap,                           \
  443                                le_mem_InitStaticPool(_hashmap_##name,               \
  444                                                     (capacity),                     \
  445                                                     sizeof(le_hashmap_Entry_t)),    \
  446                                _hashmap_##name##Buckets))
  447 #else
  448 #   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
  449         (inline_static_assert(                                                      \
  450             sizeof(_hashmap_##name##Buckets) ==                                     \
  451                 sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
  452             "hashmap init capacity does not match definition"),                     \
  453         _le_hashmap_InitStatic((capacity), (hashFunc), (equalsFunc),                \
  454                                &_hashmap_##name##Hashmap,                           \
  455                                le_mem_InitStaticPool(_hashmap_##name,               \
  456                                                     (capacity),                     \
  457                                                     sizeof(le_hashmap_Entry_t)),    \
  458                                _hashmap_##name##Buckets))
  459 #endif
  460 
  461 /// @cond HIDDEN_IN_USER_DOCS
  462 //--------------------------------------------------------------------------------------------------
  463 /**
  464  * Internal function to initialize a statically-defined hashmap
  465  *
  466  * @note use le_hashmap_InitStatic() macro instead
  467  */
  468 //--------------------------------------------------------------------------------------------------
  469 le_hashmap_Ref_t _le_hashmap_InitStatic
  470 (
  471 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  472     const char              *nameStr,       ///< [in] Name of the HashMap
  473 #endif
  474     size_t                   capacity,      ///< [in] Expected capacity of the map
  475     le_hashmap_HashFunc_t    hashFunc,      ///< [in] The hash function
  476     le_hashmap_EqualsFunc_t  equalsFunc,    ///< [in] The equality function
  477     le_hashmap_Hashmap_t    *mapPtr,        ///< [in] The static hash map to initialize
  478     le_mem_PoolRef_t         entryPoolRef,  ///< [in] The memory pool for map entries
  479     le_hashmap_Bucket_t     *bucketsPtr     ///< [in] The buckets
  480 );
  481 /// @endcond
  482 
  483 
  484 //--------------------------------------------------------------------------------------------------
  485 /**
  486  * Add a key-value pair to a HashMap. If the key already exists in the map, the previous value
  487  * will be replaced with the new value passed into this function.
  488  *
  489  * @return  Returns NULL for a new entry or a pointer to the old value if it is replaced.
  490  *
  491  */
  492 //--------------------------------------------------------------------------------------------------
  493 
  494 void* le_hashmap_Put
  495 (
  496     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  497     const void* keyPtr,        ///< [in] Pointer to the key to be stored.
  498     const void* valuePtr       ///< [in] Pointer to the value to be stored.
  499 );
  500 
  501 //--------------------------------------------------------------------------------------------------
  502 /**
  503  * Retrieve a value from a HashMap.
  504  *
  505  * @return  Returns a pointer to the value or NULL if the key is not found.
  506  *
  507  */
  508 //--------------------------------------------------------------------------------------------------
  509 
  510 void* le_hashmap_Get
  511 (
  512     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  513     const void* keyPtr         ///< [in] Pointer to the key to be retrieved.
  514 );
  515 
  516 //--------------------------------------------------------------------------------------------------
  517 /**
  518  * Retrieve a stored key from a HashMap.
  519  *
  520  * @return  Returns a pointer to the key that was stored in the HashMap by le_hashmap_Put() or
  521  *          NULL if the key is not found.
  522  *
  523  */
  524 //--------------------------------------------------------------------------------------------------
  525 void* le_hashmap_GetStoredKey
  526 (
  527     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  528     const void* keyPtr         ///< [in] Pointer to the key to be retrieved.
  529 );
  530 
  531 //--------------------------------------------------------------------------------------------------
  532 /**
  533  * Remove a value from a HashMap.
  534  *
  535  * @return  Returns a pointer to the value or NULL if the key is not found.
  536  *
  537  */
  538 //--------------------------------------------------------------------------------------------------
  539 
  540 void* le_hashmap_Remove
  541 (
  542    le_hashmap_Ref_t mapRef,       ///< [in] Reference to the map.
  543    const void* keyPtr             ///< [in] Pointer to the key to be removed.
  544 );
  545 
  546 //--------------------------------------------------------------------------------------------------
  547 /**
  548  * Tests if the HashMap is empty (i.e. contains zero keys).
  549  *
  550  * @return  Returns true if empty, false otherwise.
  551  *
  552  */
  553 //--------------------------------------------------------------------------------------------------
  554 
  555 bool le_hashmap_isEmpty
  556 (
  557     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  558 );
  559 
  560 //--------------------------------------------------------------------------------------------------
  561 /**
  562  * Calculates the number of keys in the HashMap.
  563  *
  564  * @return  The number of keys in the HashMap.
  565  *
  566  */
  567 //--------------------------------------------------------------------------------------------------
  568 
  569 size_t le_hashmap_Size
  570 (
  571     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  572 );
  573 
  574 //--------------------------------------------------------------------------------------------------
  575 /**
  576  * Tests if the HashMap contains a particular key.
  577  *
  578  * @return  Returns true if the key is found, false otherwise.
  579  *
  580  */
  581 //--------------------------------------------------------------------------------------------------
  582 
  583 bool le_hashmap_ContainsKey
  584 (
  585     le_hashmap_Ref_t mapRef,  ///< [in] Reference to the map.
  586     const void* keyPtr        ///< [in] Pointer to the key to be searched.
  587 );
  588 
  589 //--------------------------------------------------------------------------------------------------
  590 /**
  591  * Deletes all the entries held in the hashmap. This will not delete the data pointed to by the
  592  * key and value pointers. That cleanup is the responsibility of the caller.
  593  * This allows the map to be re-used. Currently maps can't be deleted.
  594  *
  595  */
  596 //--------------------------------------------------------------------------------------------------
  597 
  598 void le_hashmap_RemoveAll
  599 (
  600     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  601 );
  602 
  603 //--------------------------------------------------------------------------------------------------
  604 /**
  605  * Iterates over the whole map, calling the supplied callback with each key-value pair. If the callback
  606  * returns false for any key then this function will return.
  607  *
  608  * @return  Returns true if all elements were checked; or false if iteration was stopped early
  609  *
  610  */
  611 //--------------------------------------------------------------------------------------------------
  612 bool le_hashmap_ForEach
  613 (
  614     le_hashmap_Ref_t mapRef,                 ///< [in] Reference to the map.
  615     le_hashmap_ForEachHandler_t forEachFn,   ///< [in] Callback function to be called with each pair.
  616     void* contextPtr                         ///< [in] Pointer to a context to be supplied to the callback.
  617 );
  618 
  619 //--------------------------------------------------------------------------------------------------
  620 /**
  621  * Gets an iterator for step-by-step iteration over the map. In this mode,
  622  * the iteration is controlled by the calling function using the le_hashmap_NextNode() function.
  623  * There is one iterator per map, and calling this function resets the
  624  * iterator position to the start of the map.
  625  * The iterator is not ready for data access until le_hashmap_NextNode() has been called
  626  * at least once.
  627  *
  628  * @return  Returns A reference to a hashmap iterator which is ready
  629  *          for le_hashmap_NextNode() to be called on it
  630  *
  631  */
  632 //--------------------------------------------------------------------------------------------------
  633 le_hashmap_It_Ref_t le_hashmap_GetIterator
  634 (
  635     le_hashmap_Ref_t mapRef                 ///< [in] Reference to the map.
  636 );
  637 
  638 //--------------------------------------------------------------------------------------------------
  639 /**
  640  * Moves the iterator to the next key/value pair in the map. Order is dependent
  641  * on the hash algorithm and the order of inserts, and is not sorted at all.
  642  *
  643  * @return  Returns LE_OK unless you go past the end of the map, then returns LE_NOT_FOUND.
  644  *
  645  */
  646 //--------------------------------------------------------------------------------------------------
  647 le_result_t le_hashmap_NextNode
  648 (
  649     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  650 );
  651 
  652 //--------------------------------------------------------------------------------------------------
  653 /**
  654  * Moves the iterator to the previous key/value pair in the map. Order is dependent
  655  * on the hash algorithm and the order of inserts, and is not sorted at all.
  656  *
  657  * @return  Returns LE_OK unless you go past the beginning of the map, then returns LE_NOT_FOUND.
  658  *
  659  */
  660 //--------------------------------------------------------------------------------------------------
  661 le_result_t le_hashmap_PrevNode
  662 (
  663     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator
  664 );
  665 
  666 //--------------------------------------------------------------------------------------------------
  667 /**
  668  * Retrieves a pointer to the key where the iterator is currently pointing.
  669  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
  670  * called, or if the iterator has been invalidated, this will return NULL.
  671  *
  672  * @return  Pointer to the current key, or NULL if the iterator has been invalidated or is not
  673  *          ready.
  674  *
  675  */
  676 //--------------------------------------------------------------------------------------------------
  677 const void* le_hashmap_GetKey
  678 (
  679     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  680 );
  681 
  682 //--------------------------------------------------------------------------------------------------
  683 /**
  684  * Retrieves a pointer to the value where the iterator is currently pointing.
  685  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
  686  * called, or if the iterator has been invalidated, this will return NULL.
  687  *
  688  * @return  Pointer to the current value, or NULL if the iterator has been invalidated or is not
  689  *          ready.
  690  *
  691  */
  692 //--------------------------------------------------------------------------------------------------
  693 void* le_hashmap_GetValue
  694 (
  695     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  696 );
  697 
  698 //--------------------------------------------------------------------------------------------------
  699 /**
  700  * Retrieves the key and value of the first node stored in the hashmap.
  701  * The hashmap is not sorted so this will simply return the first node stored in the map.
  702  * There is no guarantee that a subsequent call to this function will return the same pair
  703  * if new keys have been added to the map.
  704  * If NULL is passed as the firstValuePointer then only the key will be returned.
  705  *
  706  * @return  LE_OK if the first node is returned or LE_NOT_FOUND if the map is empty.
  707  *          LE_BAD_PARAMETER if the key is NULL.
  708  *
  709  */
  710 //--------------------------------------------------------------------------------------------------
  711 le_result_t le_hashmap_GetFirstNode
  712 (
  713     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map
  714     void **firstKeyPtr,        ///< [out] Pointer to the first key
  715     void **firstValuePtr       ///< [out] Pointer to the first value
  716 );
  717 
  718 //--------------------------------------------------------------------------------------------------
  719 /**
  720  * Retrieves the key and value of the node after the passed in key.
  721  * The hashmap is not sorted so this will simply return the next node stored in the map.
  722  * There is no guarantee that a subsequent call to this function will return the same pair
  723  * if new keys have been added to the map.
  724  * If NULL is passed as the nextValuePtr then only the key will be returned.
  725  *
  726  * @return  LE_OK if the next node is returned. If the keyPtr is not found in the
  727  *          map then LE_BAD_PARAMETER is returned. LE_NOT_FOUND is returned if the passed
  728  *          in key is the last one in the map.
  729  *
  730  */
  731 //--------------------------------------------------------------------------------------------------
  732 le_result_t le_hashmap_GetNodeAfter
  733 (
  734     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map
  735     const void* keyPtr,        ///< [in] Pointer to the key to be searched for
  736     void **nextKeyPtr,         ///< [out] Pointer to the first key
  737     void **nextValuePtr        ///< [out] Pointer to the first value
  738 );
  739 
  740 
  741 //--------------------------------------------------------------------------------------------------
  742 /**
  743  * Counts the total number of collisions in the map. A collision occurs
  744  * when more than one entry is stored in the map at the same index.
  745  *
  746  * @return  Returns the total collisions in the map.
  747  *
  748  */
  749 //--------------------------------------------------------------------------------------------------
  750 
  751 size_t le_hashmap_CountCollisions
  752 (
  753     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  754 );
  755 
  756 //--------------------------------------------------------------------------------------------------
  757 /**
  758  * String hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  759  * the table is a string.
  760  *
  761  * @return  Returns the hash value of the string pointed to by stringToHash.
  762  *
  763  */
  764 //--------------------------------------------------------------------------------------------------
  765 
  766 size_t le_hashmap_HashString
  767 (
  768     const void* stringToHashPtr    ///< [in] Pointer to the string to be hashed.
  769 );
  770 
  771 //--------------------------------------------------------------------------------------------------
  772 /**
  773  * String equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  774  * the table is a string
  775  *
  776  * @return  Returns true if the strings are identical, false otherwise.
  777  *
  778  */
  779 //--------------------------------------------------------------------------------------------------
  780 
  781 bool le_hashmap_EqualsString
  782 (
  783     const void* firstStringPtr,    ///< [in] Pointer to the first string for comparing.
  784     const void* secondStringPtr    ///< [in] Pointer to the second string for comparing.
  785 );
  786 
  787 //--------------------------------------------------------------------------------------------------
  788 /**
  789  * Integer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  790  * the table is a uint32_t.
  791  *
  792  * @return  Returns the hash value of the uint32_t pointed to by intToHash.
  793  *
  794  */
  795 //--------------------------------------------------------------------------------------------------
  796 
  797 size_t le_hashmap_HashUInt32
  798 (
  799     const void* intToHashPtr    ///< [in] Pointer to the integer to be hashed.
  800 );
  801 
  802 //--------------------------------------------------------------------------------------------------
  803 /**
  804  * Integer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  805  * the table is a uint32_t.
  806  *
  807  * @return  Returns true if the integers are equal, false otherwise.
  808  *
  809  */
  810 //--------------------------------------------------------------------------------------------------
  811 
  812 bool le_hashmap_EqualsUInt32
  813 (
  814     const void* firstIntPtr,    ///< [in] Pointer to the first integer for comparing.
  815     const void* secondIntPtr    ///< [in] Pointer to the second integer for comparing.
  816 );
  817 
  818 //--------------------------------------------------------------------------------------------------
  819 /**
  820  * Long integer hashing function. This can be used as a paramter to le_hashmap_Create if the key to
  821  * the table is a uint64_t
  822  *
  823  * @return  Returns the hash value of the uint64_t pointed to by intToHash
  824  *
  825  */
  826 //--------------------------------------------------------------------------------------------------
  827 
  828 size_t le_hashmap_HashUInt64
  829 (
  830     const void* intToHashPtr    ///< [in] Pointer to the long integer to be hashed
  831 );
  832 
  833 //--------------------------------------------------------------------------------------------------
  834 /**
  835  * Long integer equality function. This can be used as a paramter to le_hashmap_Create if the key to
  836  * the table is a uint64_t
  837  *
  838  * @return  Returns true if the integers are equal, false otherwise
  839  *
  840  */
  841 //--------------------------------------------------------------------------------------------------
  842 
  843 bool le_hashmap_EqualsUInt64
  844 (
  845     const void* firstIntPtr,    ///< [in] Pointer to the first long integer for comparing.
  846     const void* secondIntPtr    ///< [in] Pointer to the second long integer for comparing.
  847 );
  848 
  849 //--------------------------------------------------------------------------------------------------
  850 /**
  851  * Pointer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  852  * the table is an pointer or reference. Simply pass in the address as the key.
  853  *
  854  * @return  Returns the hash value of the pointer pointed to by voidToHashPtr
  855  *
  856  */
  857 //--------------------------------------------------------------------------------------------------
  858 
  859 size_t le_hashmap_HashVoidPointer
  860 (
  861     const void* voidToHashPtr    ///< [in] Pointer to be hashed
  862 );
  863 
  864 //--------------------------------------------------------------------------------------------------
  865 /**
  866  * Pointer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  867  * the table is an pointer or reference.
  868  *
  869  * @return  Returns true if the pointers are equal, false otherwise
  870  *
  871  */
  872 //--------------------------------------------------------------------------------------------------
  873 
  874 bool le_hashmap_EqualsVoidPointer
  875 (
  876     const void* firstVoidPtr,    ///< [in] First pointer for comparing.
  877     const void* secondVoidPtr    ///< [in] Second pointer for comparing.
  878 );
  879 
  880 
  881 //--------------------------------------------------------------------------------------------------
  882 /**
  883  * Generic hash for any plain-old-datatype.
  884  */
  885 //--------------------------------------------------------------------------------------------------
  886 #define LE_HASHMAP_MAKE_HASH(type)                              \
  887     static size_t Hash##type                                    \
  888     (                                                           \
  889         const void* type##Name                                  \
  890     )                                                           \
  891     {                                                           \
  892         size_t byte=0, hash = 0;                                \
  893         unsigned char c;                                        \
  894         const unsigned char* ptr = type##Name;                  \
  895         for (byte = 0; byte < sizeof(type); ++byte)             \
  896         {                                                       \
  897             c = *ptr++;                                         \
  898             hash = c + (hash << 6) + (hash << 16) - hash;       \
  899         }                                                       \
  900         return hash;                                            \
  901     }                                                           \
  902     static bool Equals##type                                    \
  903     (                                                           \
  904         const void* first##type,                                \
  905         const void* second##type                                \
  906     )                                                           \
  907     {                                                           \
  908         return memcmp(first##type, second##type, sizeof(type)) == 0; \
  909     }
  910 
  911 
  912 
  913 //--------------------------------------------------------------------------------------------------
  914 /**
  915  * Makes a particular hashmap traceable without enabling the tracing.  After this is called, when
  916  * the trace keyword for this hashmap (the hashmap's name) is enabled for the "framework" component
  917  * in the process, tracing will start.  If that keyword was enabled before
  918  * this function was called, tracing will start immediately when it is called.
  919  **/
  920 //--------------------------------------------------------------------------------------------------
  921 void le_hashmap_MakeTraceable
  922 (
  923     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  924 );
  925 
  926 
  927 //--------------------------------------------------------------------------------------------------
  928 /**
  929  * Immediately enables tracing on a particular hashmap object.
  930  **/
  931 //--------------------------------------------------------------------------------------------------
  932 void le_hashmap_EnableTrace
  933 (
  934     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  935 );
  936 
  937 
  938 #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:280
le_hashmap_HashmapIt_t
Definition: le_hashmap.h:268
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:294
le_result_t
le_result_t
Definition: le_basics.h:35
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:197
LE_UNUSED
#define LE_UNUSED(v)
Definition: le_basics.h:355
le_hashmap_Hashmap_t::bucketsPtr
le_hashmap_Bucket_t * bucketsPtr
Pointer to the array of hash map buckets. 
Definition: le_hashmap.h:287
le_hashmap_HashFunc_t
size_t(* le_hashmap_HashFunc_t)(const void *keyToHashPtr)
Definition: le_hashmap.h:209
le_hashmap_Hashmap_t::hashFuncPtr
le_hashmap_HashFunc_t hashFuncPtr
Hash operator. 
Definition: le_hashmap.h:285
le_hashmap_Ref_t
struct le_hashmap * le_hashmap_Ref_t
Definition: le_hashmap.h:190
le_hashmap_Hashmap_t::iterator
le_hashmap_HashmapIt_t iterator
Iterator instance. 
Definition: le_hashmap.h:282
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:255
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:271
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:290
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:288
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:540
le_hashmap_EqualsFunc_t
bool(* le_hashmap_EqualsFunc_t)(const void *firstKeyPtr, const void *secondKeyPtr)
Definition: le_hashmap.h:225
le_hashmap_Entry_t::entryListLink
le_hashmap_Link_t entryListLink
Next entry in bucket. 
Definition: le_hashmap.h:257
le_hashmap_ForEachHandler_t
bool(* le_hashmap_ForEachHandler_t)(const void *keyPtr, const void *valuePtr, void *contextPtr)
Definition: le_hashmap.h:243
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:259
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:258
le_hashmap_Hashmap_t::equalsFuncPtr
le_hashmap_EqualsFunc_t equalsFuncPtr
Equality operator. 
Definition: le_hashmap.h:284
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_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)
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:293
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_hashmap_Hashmap_t::bucketCount
size_t bucketCount
Number of buckets. 
Definition: le_hashmap.h:289
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:270
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:306
le_hashmap_GetNodeAfter
le_result_t le_hashmap_GetNodeAfter(le_hashmap_Ref_t mapRef, const void *keyPtr, void **nextKeyPtr, void **nextValuePtr)