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     return _le_hashmap_Create(capacity, hashFunc, equalsFunc);
  365 }
  366 #endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
  367 
  368 
  369 
  370 //--------------------------------------------------------------------------------------------------
  371 /**
  372  * Calculate number of buckets for a hashmap of a given size
  373  *
  374  * 0.75 load factor. We have more buckets than expected keys as we want
  375  * to reduce the chance of collisions. 1-1 would assume a perfect hashing
  376  * function which is rather unlikely. Also, ensure that the capacity is
  377  * at least 3 which avoids strange issues in the hashing algorithm
  378  *
  379  * @note Used internally to calculate static hashmap sizes.  Should not be used by users
  380  * of liblegato.  Caps out at 65536 entries
  381  */
  382 //--------------------------------------------------------------------------------------------------
  383 #define LE_HASHMAP_BUCKET_COUNT(capacity)                               \
  384     ((capacity)*4/3<=0x4?0x4:                                           \
  385      ((capacity)*4/3<=0x8?0x8:                                          \
  386       ((capacity)*4/3<=0x10?0x10:                                       \
  387        ((capacity)*4/3<=0x20?0x20:                                      \
  388         ((capacity)*4/3<=0x40?0x40:                                     \
  389          ((capacity)*4/3<=0x80?0x80:                                    \
  390           ((capacity)*4/3<=0x100?0x100:                                 \
  391            ((capacity)*4/3<=0x200?0x200:                                \
  392             ((capacity)*4/3<=0x400?0x400:                               \
  393              ((capacity)*4/3<=0x800?0x800:                              \
  394               ((capacity)*4/3<=0x1000?0x1000:                           \
  395                ((capacity)*4/3<=0x2000?0x2000:                          \
  396                 ((capacity)*4/3<=0x4000?0x4000:                         \
  397                  ((capacity)*4/3<=0x8000?0x8000:                        \
  398                   0x10000))))))))))))))
  399 
  400 //--------------------------------------------------------------------------------------------------
  401 /**
  402  * Statically define a hash-map.
  403  *
  404  * This allocates all the space required for a hash-map at file scope so no dynamic memory
  405  * is needed for the hash map.  This allows a better estimate of memory usage of an app
  406  * to be obtained by examining the linker map, and ensures initializing the static map
  407  * will not fail at run-time.
  408  *
  409  * @note Dynamic hash maps set initial pool to bucket count/2, static hash maps set
  410  * pool size to capacity to avoid overflowing the pool.
  411  */
  412 //--------------------------------------------------------------------------------------------------
  413 #define LE_HASHMAP_DEFINE_STATIC(name, capacity)                                          \
  414     static le_hashmap_Hashmap_t _hashmap_##name##Hashmap;                                 \
  415     LE_MEM_DEFINE_STATIC_POOL(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t));   \
  416     static le_hashmap_Bucket_t _hashmap_##name##Buckets[LE_HASHMAP_BUCKET_COUNT(capacity)]
  417 
  418 
  419 //--------------------------------------------------------------------------------------------------
  420 /**
  421  * Initialize a statically-defined hashmap
  422  *
  423  * If you create a hashmap with a smaller capacity than you actually use, then
  424  * the map will continue to work, but performance will degrade the more you put in the map.
  425  *
  426  *  @param  name        Name used when defining the static hashmap.
  427  *  @param  capacity    Capacity specified when defining the static hashmap.
  428  *  @param  hashFunc    Callback to invoke to hash an entry's key.
  429  *  @param  equalsFunc  Callback to invoke to test key equality.
  430  *
  431  *  @return  Returns a reference to the map.
  432  */
  433 //--------------------------------------------------------------------------------------------------
  434 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  435 #   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
  436         (inline_static_assert(                                                      \
  437             sizeof(_hashmap_##name##Buckets) ==                                     \
  438                 sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
  439             "hashmap init capacity does not match definition"),                     \
  440         _le_hashmap_InitStatic(#name, (capacity), (hashFunc), (equalsFunc),         \
  441                                &_hashmap_##name##Hashmap,                           \
  442                                le_mem_InitStaticPool(_hashmap_##name,               \
  443                                                     (capacity),                     \
  444                                                     sizeof(le_hashmap_Entry_t)),    \
  445                                _hashmap_##name##Buckets))
  446 #else
  447 #   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
  448         (inline_static_assert(                                                      \
  449             sizeof(_hashmap_##name##Buckets) ==                                     \
  450                 sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
  451             "hashmap init capacity does not match definition"),                     \
  452         _le_hashmap_InitStatic((capacity), (hashFunc), (equalsFunc),                \
  453                                &_hashmap_##name##Hashmap,                           \
  454                                le_mem_InitStaticPool(_hashmap_##name,               \
  455                                                     (capacity),                     \
  456                                                     sizeof(le_hashmap_Entry_t)),    \
  457                                _hashmap_##name##Buckets))
  458 #endif
  459 
  460 /// @cond HIDDEN_IN_USER_DOCS
  461 //--------------------------------------------------------------------------------------------------
  462 /**
  463  * Internal function to initialize a statically-defined hashmap
  464  *
  465  * @note use le_hashmap_InitStatic() macro instead
  466  */
  467 //--------------------------------------------------------------------------------------------------
  468 le_hashmap_Ref_t _le_hashmap_InitStatic
  469 (
  470 #if LE_CONFIG_HASHMAP_NAMES_ENABLED
  471     const char              *nameStr,       ///< [in] Name of the HashMap
  472 #endif
  473     size_t                   capacity,      ///< [in] Expected capacity of the map
  474     le_hashmap_HashFunc_t    hashFunc,      ///< [in] The hash function
  475     le_hashmap_EqualsFunc_t  equalsFunc,    ///< [in] The equality function
  476     le_hashmap_Hashmap_t    *mapPtr,        ///< [in] The static hash map to initialize
  477     le_mem_PoolRef_t         entryPoolRef,  ///< [in] The memory pool for map entries
  478     le_hashmap_Bucket_t     *bucketsPtr     ///< [in] The buckets
  479 );
  480 /// @endcond
  481 
  482 
  483 //--------------------------------------------------------------------------------------------------
  484 /**
  485  * Add a key-value pair to a HashMap. If the key already exists in the map, the previous value
  486  * will be replaced with the new value passed into this function.
  487  *
  488  * @return  Returns NULL for a new entry or a pointer to the old value if it is replaced.
  489  *
  490  */
  491 //--------------------------------------------------------------------------------------------------
  492 
  493 void* le_hashmap_Put
  494 (
  495     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  496     const void* keyPtr,        ///< [in] Pointer to the key to be stored.
  497     const void* valuePtr       ///< [in] Pointer to the value to be stored.
  498 );
  499 
  500 //--------------------------------------------------------------------------------------------------
  501 /**
  502  * Retrieve a value from a HashMap.
  503  *
  504  * @return  Returns a pointer to the value or NULL if the key is not found.
  505  *
  506  */
  507 //--------------------------------------------------------------------------------------------------
  508 
  509 void* le_hashmap_Get
  510 (
  511     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  512     const void* keyPtr         ///< [in] Pointer to the key to be retrieved.
  513 );
  514 
  515 //--------------------------------------------------------------------------------------------------
  516 /**
  517  * Retrieve a stored key from a HashMap.
  518  *
  519  * @return  Returns a pointer to the key that was stored in the HashMap by le_hashmap_Put() or
  520  *          NULL if the key is not found.
  521  *
  522  */
  523 //--------------------------------------------------------------------------------------------------
  524 void* le_hashmap_GetStoredKey
  525 (
  526     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map.
  527     const void* keyPtr         ///< [in] Pointer to the key to be retrieved.
  528 );
  529 
  530 //--------------------------------------------------------------------------------------------------
  531 /**
  532  * Remove a value from a HashMap.
  533  *
  534  * @return  Returns a pointer to the value or NULL if the key is not found.
  535  *
  536  */
  537 //--------------------------------------------------------------------------------------------------
  538 
  539 void* le_hashmap_Remove
  540 (
  541    le_hashmap_Ref_t mapRef,       ///< [in] Reference to the map.
  542    const void* keyPtr             ///< [in] Pointer to the key to be removed.
  543 );
  544 
  545 //--------------------------------------------------------------------------------------------------
  546 /**
  547  * Tests if the HashMap is empty (i.e. contains zero keys).
  548  *
  549  * @return  Returns true if empty, false otherwise.
  550  *
  551  */
  552 //--------------------------------------------------------------------------------------------------
  553 
  554 bool le_hashmap_isEmpty
  555 (
  556     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  557 );
  558 
  559 //--------------------------------------------------------------------------------------------------
  560 /**
  561  * Calculates the number of keys in the HashMap.
  562  *
  563  * @return  The number of keys in the HashMap.
  564  *
  565  */
  566 //--------------------------------------------------------------------------------------------------
  567 
  568 size_t le_hashmap_Size
  569 (
  570     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  571 );
  572 
  573 //--------------------------------------------------------------------------------------------------
  574 /**
  575  * Tests if the HashMap contains a particular key.
  576  *
  577  * @return  Returns true if the key is found, false otherwise.
  578  *
  579  */
  580 //--------------------------------------------------------------------------------------------------
  581 
  582 bool le_hashmap_ContainsKey
  583 (
  584     le_hashmap_Ref_t mapRef,  ///< [in] Reference to the map.
  585     const void* keyPtr        ///< [in] Pointer to the key to be searched.
  586 );
  587 
  588 //--------------------------------------------------------------------------------------------------
  589 /**
  590  * Deletes all the entries held in the hashmap. This will not delete the data pointed to by the
  591  * key and value pointers. That cleanup is the responsibility of the caller.
  592  * This allows the map to be re-used. Currently maps can't be deleted.
  593  *
  594  */
  595 //--------------------------------------------------------------------------------------------------
  596 
  597 void le_hashmap_RemoveAll
  598 (
  599     le_hashmap_Ref_t mapRef    ///< [in] Reference to the map.
  600 );
  601 
  602 //--------------------------------------------------------------------------------------------------
  603 /**
  604  * Iterates over the whole map, calling the supplied callback with each key-value pair. If the callback
  605  * returns false for any key then this function will return.
  606  *
  607  * @return  Returns true if all elements were checked; or false if iteration was stopped early
  608  *
  609  */
  610 //--------------------------------------------------------------------------------------------------
  611 bool le_hashmap_ForEach
  612 (
  613     le_hashmap_Ref_t mapRef,                 ///< [in] Reference to the map.
  614     le_hashmap_ForEachHandler_t forEachFn,   ///< [in] Callback function to be called with each pair.
  615     void* contextPtr                         ///< [in] Pointer to a context to be supplied to the callback.
  616 );
  617 
  618 //--------------------------------------------------------------------------------------------------
  619 /**
  620  * Gets an iterator for step-by-step iteration over the map. In this mode,
  621  * the iteration is controlled by the calling function using the le_hashmap_NextNode() function.
  622  * There is one iterator per map, and calling this function resets the
  623  * iterator position to the start of the map.
  624  * The iterator is not ready for data access until le_hashmap_NextNode() has been called
  625  * at least once.
  626  *
  627  * @return  Returns A reference to a hashmap iterator which is ready
  628  *          for le_hashmap_NextNode() to be called on it
  629  *
  630  */
  631 //--------------------------------------------------------------------------------------------------
  632 le_hashmap_It_Ref_t le_hashmap_GetIterator
  633 (
  634     le_hashmap_Ref_t mapRef                 ///< [in] Reference to the map.
  635 );
  636 
  637 //--------------------------------------------------------------------------------------------------
  638 /**
  639  * Moves the iterator to the next key/value pair in the map. Order is dependent
  640  * on the hash algorithm and the order of inserts, and is not sorted at all.
  641  *
  642  * @return  Returns LE_OK unless you go past the end of the map, then returns LE_NOT_FOUND.
  643  *
  644  */
  645 //--------------------------------------------------------------------------------------------------
  646 le_result_t le_hashmap_NextNode
  647 (
  648     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  649 );
  650 
  651 //--------------------------------------------------------------------------------------------------
  652 /**
  653  * Moves the iterator to the previous key/value pair in the map. Order is dependent
  654  * on the hash algorithm and the order of inserts, and is not sorted at all.
  655  *
  656  * @return  Returns LE_OK unless you go past the beginning of the map, then returns LE_NOT_FOUND.
  657  *
  658  */
  659 //--------------------------------------------------------------------------------------------------
  660 le_result_t le_hashmap_PrevNode
  661 (
  662     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator
  663 );
  664 
  665 //--------------------------------------------------------------------------------------------------
  666 /**
  667  * Retrieves a pointer to the key where the iterator is currently pointing.
  668  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
  669  * called, or if the iterator has been invalidated, this will return NULL.
  670  *
  671  * @return  Pointer to the current key, or NULL if the iterator has been invalidated or is not
  672  *          ready.
  673  *
  674  */
  675 //--------------------------------------------------------------------------------------------------
  676 const void* le_hashmap_GetKey
  677 (
  678     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  679 );
  680 
  681 //--------------------------------------------------------------------------------------------------
  682 /**
  683  * Retrieves a pointer to the value where the iterator is currently pointing.
  684  * If the iterator has just been initialized and le_hashmap_NextNode() has not been
  685  * called, or if the iterator has been invalidated, this will return NULL.
  686  *
  687  * @return  Pointer to the current value, or NULL if the iterator has been invalidated or is not
  688  *          ready.
  689  *
  690  */
  691 //--------------------------------------------------------------------------------------------------
  692 void* le_hashmap_GetValue
  693 (
  694     le_hashmap_It_Ref_t iteratorRef        ///< [IN] Reference to the iterator.
  695 );
  696 
  697 //--------------------------------------------------------------------------------------------------
  698 /**
  699  * Retrieves the key and value of the first node stored in the hashmap.
  700  * The hashmap is not sorted so this will simply return the first node stored in the map.
  701  * There is no guarantee that a subsequent call to this function will return the same pair
  702  * if new keys have been added to the map.
  703  * If NULL is passed as the firstValuePointer then only the key will be returned.
  704  *
  705  * @return  LE_OK if the first node is returned or LE_NOT_FOUND if the map is empty.
  706  *          LE_BAD_PARAMETER if the key is NULL.
  707  *
  708  */
  709 //--------------------------------------------------------------------------------------------------
  710 le_result_t le_hashmap_GetFirstNode
  711 (
  712     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map
  713     void **firstKeyPtr,        ///< [out] Pointer to the first key
  714     void **firstValuePtr       ///< [out] Pointer to the first value
  715 );
  716 
  717 //--------------------------------------------------------------------------------------------------
  718 /**
  719  * Retrieves the key and value of the node after the passed in key.
  720  * The hashmap is not sorted so this will simply return the next node stored in the map.
  721  * There is no guarantee that a subsequent call to this function will return the same pair
  722  * if new keys have been added to the map.
  723  * If NULL is passed as the nextValuePtr then only the key will be returned.
  724  *
  725  * @return  LE_OK if the next node is returned. If the keyPtr is not found in the
  726  *          map then LE_BAD_PARAMETER is returned. LE_NOT_FOUND is returned if the passed
  727  *          in key is the last one in the map.
  728  *
  729  */
  730 //--------------------------------------------------------------------------------------------------
  731 le_result_t le_hashmap_GetNodeAfter
  732 (
  733     le_hashmap_Ref_t mapRef,   ///< [in] Reference to the map
  734     const void* keyPtr,        ///< [in] Pointer to the key to be searched for
  735     void **nextKeyPtr,         ///< [out] Pointer to the first key
  736     void **nextValuePtr        ///< [out] Pointer to the first value
  737 );
  738 
  739 
  740 //--------------------------------------------------------------------------------------------------
  741 /**
  742  * Counts the total number of collisions in the map. A collision occurs
  743  * when more than one entry is stored in the map at the same index.
  744  *
  745  * @return  Returns the total collisions in the map.
  746  *
  747  */
  748 //--------------------------------------------------------------------------------------------------
  749 
  750 size_t le_hashmap_CountCollisions
  751 (
  752     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  753 );
  754 
  755 //--------------------------------------------------------------------------------------------------
  756 /**
  757  * String hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  758  * the table is a string.
  759  *
  760  * @return  Returns the hash value of the string pointed to by stringToHash.
  761  *
  762  */
  763 //--------------------------------------------------------------------------------------------------
  764 
  765 size_t le_hashmap_HashString
  766 (
  767     const void* stringToHashPtr    ///< [in] Pointer to the string to be hashed.
  768 );
  769 
  770 //--------------------------------------------------------------------------------------------------
  771 /**
  772  * String equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  773  * the table is a string
  774  *
  775  * @return  Returns true if the strings are identical, false otherwise.
  776  *
  777  */
  778 //--------------------------------------------------------------------------------------------------
  779 
  780 bool le_hashmap_EqualsString
  781 (
  782     const void* firstStringPtr,    ///< [in] Pointer to the first string for comparing.
  783     const void* secondStringPtr    ///< [in] Pointer to the second string for comparing.
  784 );
  785 
  786 //--------------------------------------------------------------------------------------------------
  787 /**
  788  * Integer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  789  * the table is a uint32_t.
  790  *
  791  * @return  Returns the hash value of the uint32_t pointed to by intToHash.
  792  *
  793  */
  794 //--------------------------------------------------------------------------------------------------
  795 
  796 size_t le_hashmap_HashUInt32
  797 (
  798     const void* intToHashPtr    ///< [in] Pointer to the integer to be hashed.
  799 );
  800 
  801 //--------------------------------------------------------------------------------------------------
  802 /**
  803  * Integer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  804  * the table is a uint32_t.
  805  *
  806  * @return  Returns true if the integers are equal, false otherwise.
  807  *
  808  */
  809 //--------------------------------------------------------------------------------------------------
  810 
  811 bool le_hashmap_EqualsUInt32
  812 (
  813     const void* firstIntPtr,    ///< [in] Pointer to the first integer for comparing.
  814     const void* secondIntPtr    ///< [in] Pointer to the second integer for comparing.
  815 );
  816 
  817 //--------------------------------------------------------------------------------------------------
  818 /**
  819  * Long integer hashing function. This can be used as a paramter to le_hashmap_Create if the key to
  820  * the table is a uint64_t
  821  *
  822  * @return  Returns the hash value of the uint64_t pointed to by intToHash
  823  *
  824  */
  825 //--------------------------------------------------------------------------------------------------
  826 
  827 size_t le_hashmap_HashUInt64
  828 (
  829     const void* intToHashPtr    ///< [in] Pointer to the long integer to be hashed
  830 );
  831 
  832 //--------------------------------------------------------------------------------------------------
  833 /**
  834  * Long integer equality function. This can be used as a paramter to le_hashmap_Create if the key to
  835  * the table is a uint64_t
  836  *
  837  * @return  Returns true if the integers are equal, false otherwise
  838  *
  839  */
  840 //--------------------------------------------------------------------------------------------------
  841 
  842 bool le_hashmap_EqualsUInt64
  843 (
  844     const void* firstIntPtr,    ///< [in] Pointer to the first long integer for comparing.
  845     const void* secondIntPtr    ///< [in] Pointer to the second long integer for comparing.
  846 );
  847 
  848 //--------------------------------------------------------------------------------------------------
  849 /**
  850  * Pointer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to
  851  * the table is an pointer or reference. Simply pass in the address as the key.
  852  *
  853  * @return  Returns the hash value of the pointer pointed to by voidToHashPtr
  854  *
  855  */
  856 //--------------------------------------------------------------------------------------------------
  857 
  858 size_t le_hashmap_HashVoidPointer
  859 (
  860     const void* voidToHashPtr    ///< [in] Pointer to be hashed
  861 );
  862 
  863 //--------------------------------------------------------------------------------------------------
  864 /**
  865  * Pointer equality function. Can be used as a parameter to le_hashmap_Create() if the key to
  866  * the table is an pointer or reference.
  867  *
  868  * @return  Returns true if the pointers are equal, false otherwise
  869  *
  870  */
  871 //--------------------------------------------------------------------------------------------------
  872 
  873 bool le_hashmap_EqualsVoidPointer
  874 (
  875     const void* firstVoidPtr,    ///< [in] First pointer for comparing.
  876     const void* secondVoidPtr    ///< [in] Second pointer for comparing.
  877 );
  878 
  879 
  880 //--------------------------------------------------------------------------------------------------
  881 /**
  882  * Generic hash for any plain-old-datatype.
  883  */
  884 //--------------------------------------------------------------------------------------------------
  885 #define LE_HASHMAP_MAKE_HASH(type)                              \
  886     static size_t Hash##type                                    \
  887     (                                                           \
  888         const void* type##Name                                  \
  889     )                                                           \
  890     {                                                           \
  891         size_t byte=0, hash = 0;                                \
  892         unsigned char c;                                        \
  893         const unsigned char* ptr = type##Name;                  \
  894         for (byte = 0; byte < sizeof(type); ++byte)             \
  895         {                                                       \
  896             c = *ptr++;                                         \
  897             hash = c + (hash << 6) + (hash << 16) - hash;       \
  898         }                                                       \
  899         return hash;                                            \
  900     }                                                           \
  901     static bool Equals##type                                    \
  902     (                                                           \
  903         const void* first##type,                                \
  904         const void* second##type                                \
  905     )                                                           \
  906     {                                                           \
  907         return memcmp(first##type, second##type, sizeof(type)) == 0; \
  908     }
  909 
  910 
  911 
  912 //--------------------------------------------------------------------------------------------------
  913 /**
  914  * Makes a particular hashmap traceable without enabling the tracing.  After this is called, when
  915  * the trace keyword for this hashmap (the hashmap's name) is enabled for the "framework" component
  916  * in the process, tracing will start.  If that keyword was enabled before
  917  * this function was called, tracing will start immediately when it is called.
  918  **/
  919 //--------------------------------------------------------------------------------------------------
  920 void le_hashmap_MakeTraceable
  921 (
  922     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  923 );
  924 
  925 
  926 //--------------------------------------------------------------------------------------------------
  927 /**
  928  * Immediately enables tracing on a particular hashmap object.
  929  **/
  930 //--------------------------------------------------------------------------------------------------
  931 void le_hashmap_EnableTrace
  932 (
  933     le_hashmap_Ref_t mapRef     ///< [in] Reference to the map.
  934 );
  935 
  936 
  937 #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_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:274
le_hashmap_GetNodeAfter
le_result_t le_hashmap_GetNodeAfter(le_hashmap_Ref_t mapRef, const void *keyPtr, void **nextKeyPtr, void **nextValuePtr)