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