le_hashmap.h File Reference

Go to the source code of this file.

Data Structures

struct  le_hashmap_Entry_t
 
struct  le_hashmap_HashmapIt_t
 
struct  le_hashmap_Hashmap_t
 

Macros

#define LE_HASHMAP_BUCKET_COUNT(capacity)
 
#define LE_HASHMAP_DEFINE_STATIC(name, capacity)
 
#define LE_HASHMAP_DEFINE_STATIC_IN_SECTION(name, capacity, sectionName)
 
#define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)
 
#define LE_HASHMAP_MAKE_HASH(type)
 

Typedefs

typedef le_dls_List_t le_hashmap_Bucket_t
 
typedef le_dls_Link_t le_hashmap_Link_t
 
typedef struct le_hashmap * le_hashmap_Ref_t
 
typedef struct le_hashmap_It * le_hashmap_It_Ref_t
 
typedef size_t(* le_hashmap_HashFunc_t) (const void *keyToHashPtr)
 
typedef bool(* le_hashmap_EqualsFunc_t) (const void *firstKeyPtr, const void *secondKeyPtr)
 
typedef bool(* le_hashmap_ForEachHandler_t) (const void *keyPtr, const void *valuePtr, void *contextPtr)
 

Functions

le_hashmap_Ref_t le_hashmap_Create (const char *nameStr, size_t capacity, le_hashmap_HashFunc_t hashFunc, le_hashmap_EqualsFunc_t equalsFunc)
 
void * le_hashmap_Put (le_hashmap_Ref_t mapRef, const void *keyPtr, const void *valuePtr)
 
void * le_hashmap_Get (le_hashmap_Ref_t mapRef, const void *keyPtr)
 
void * le_hashmap_GetStoredKey (le_hashmap_Ref_t mapRef, const void *keyPtr)
 
void * le_hashmap_Remove (le_hashmap_Ref_t mapRef, const void *keyPtr)
 
bool le_hashmap_isEmpty (le_hashmap_Ref_t mapRef)
 
size_t le_hashmap_Size (le_hashmap_Ref_t mapRef)
 
bool le_hashmap_ContainsKey (le_hashmap_Ref_t mapRef, const void *keyPtr)
 
void le_hashmap_RemoveAll (le_hashmap_Ref_t mapRef)
 
bool le_hashmap_ForEach (le_hashmap_Ref_t mapRef, le_hashmap_ForEachHandler_t forEachFn, void *contextPtr)
 
le_hashmap_It_Ref_t le_hashmap_GetIterator (le_hashmap_Ref_t mapRef)
 
le_result_t le_hashmap_NextNode (le_hashmap_It_Ref_t iteratorRef)
 
le_result_t le_hashmap_PrevNode (le_hashmap_It_Ref_t iteratorRef)
 
const void * le_hashmap_GetKey (le_hashmap_It_Ref_t iteratorRef)
 
void * le_hashmap_GetValue (le_hashmap_It_Ref_t iteratorRef)
 
le_result_t le_hashmap_GetFirstNode (le_hashmap_Ref_t mapRef, void **firstKeyPtr, void **firstValuePtr)
 
le_result_t le_hashmap_GetNodeAfter (le_hashmap_Ref_t mapRef, const void *keyPtr, void **nextKeyPtr, void **nextValuePtr)
 
size_t le_hashmap_CountCollisions (le_hashmap_Ref_t mapRef)
 
size_t le_hashmap_HashString (const void *stringToHashPtr)
 
bool le_hashmap_EqualsString (const void *firstStringPtr, const void *secondStringPtr)
 
size_t le_hashmap_HashUInt32 (const void *intToHashPtr)
 
bool le_hashmap_EqualsUInt32 (const void *firstIntPtr, const void *secondIntPtr)
 
size_t le_hashmap_HashUInt64 (const void *intToHashPtr)
 
bool le_hashmap_EqualsUInt64 (const void *firstIntPtr, const void *secondIntPtr)
 
size_t le_hashmap_HashVoidPointer (const void *voidToHashPtr)
 
bool le_hashmap_EqualsVoidPointer (const void *firstVoidPtr, const void *secondVoidPtr)
 
void le_hashmap_MakeTraceable (le_hashmap_Ref_t mapRef)
 
void le_hashmap_EnableTrace (le_hashmap_Ref_t mapRef)
 

Detailed Description

Legato HashMap API include file.

Macro Definition Documentation

◆ LE_HASHMAP_BUCKET_COUNT

#define LE_HASHMAP_BUCKET_COUNT (   capacity)
Value:
((capacity)*4/3<=0x4?0x4: \
((capacity)*4/3<=0x8?0x8: \
((capacity)*4/3<=0x10?0x10: \
((capacity)*4/3<=0x20?0x20: \
((capacity)*4/3<=0x40?0x40: \
((capacity)*4/3<=0x80?0x80: \
((capacity)*4/3<=0x100?0x100: \
((capacity)*4/3<=0x200?0x200: \
((capacity)*4/3<=0x400?0x400: \
((capacity)*4/3<=0x800?0x800: \
((capacity)*4/3<=0x1000?0x1000: \
((capacity)*4/3<=0x2000?0x2000: \
((capacity)*4/3<=0x4000?0x4000: \
((capacity)*4/3<=0x8000?0x8000: \
0x10000))))))))))))))

Calculate number of buckets for a hashmap of a given size

0.75 load factor. We have more buckets than expected keys as we want to reduce the chance of collisions. 1-1 would assume a perfect hashing function which is rather unlikely. Also, ensure that the capacity is at least 3 which avoids strange issues in the hashing algorithm

Note
Used internally to calculate static hashmap sizes. Should not be used by users of liblegato. Caps out at 65536 entries

◆ LE_HASHMAP_DEFINE_STATIC

#define LE_HASHMAP_DEFINE_STATIC (   name,
  capacity 
)
Value:
static le_hashmap_Hashmap_t _hashmap_##name##Hashmap; \
LE_MEM_DEFINE_STATIC_POOL(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t)); \
static le_hashmap_Bucket_t _hashmap_##name##Buckets[LE_HASHMAP_BUCKET_COUNT(capacity)]
Definition: le_hashmap.h:280
Definition: le_hashmap.h:255
#define LE_HASHMAP_BUCKET_COUNT(capacity)
Definition: le_hashmap.h:384
Definition: le_doublyLinkedList.h:216

Statically define a hash-map.

This allocates all the space required for a hash-map at file scope so no dynamic memory is needed for the hash map. This allows a better estimate of memory usage of an app to be obtained by examining the linker map, and ensures initializing the static map will not fail at run-time.

Note
Dynamic hash maps set initial pool to bucket count/2, static hash maps set pool size to capacity to avoid overflowing the pool.

◆ LE_HASHMAP_DEFINE_STATIC_IN_SECTION

#define LE_HASHMAP_DEFINE_STATIC_IN_SECTION (   name,
  capacity,
  sectionName 
)
Value:
static le_hashmap_Hashmap_t _hashmap_##name##Hashmap __attribute__((section(sectionName))); \
LE_MEM_DEFINE_STATIC_POOL_IN_SECTION(_hashmap_##name, (capacity), sizeof(le_hashmap_Entry_t), \
sectionName); \
static le_hashmap_Bucket_t _hashmap_##name##Buckets[ \
LE_HASHMAP_BUCKET_COUNT(capacity)] __attribute__((section(sectionName)))
Definition: le_hashmap.h:280
Definition: le_hashmap.h:255
Definition: le_doublyLinkedList.h:216

Statically define a hash-map in a specific memory section

By default static memory will the assigned to the bss or data section of the final object. This macro tells the linker to assign to variable to a specific section, sectionName. Essentially a "__attribute__((section("sectionName")))" will be added after the variable declaration.

Note
Dynamic hash maps set initial pool to bucket count/2, static hash maps set pool size to capacity to avoid overflowing the pool.

◆ le_hashmap_InitStatic

#define le_hashmap_InitStatic (   name,
  capacity,
  hashFunc,
  equalsFunc 
)
Value:
(inline_static_assert( \
sizeof(_hashmap_##name##Buckets) == \
"hashmap init capacity does not match definition"), \
_le_hashmap_InitStatic(#name, (capacity), (hashFunc), (equalsFunc), \
&_hashmap_##name##Hashmap, \
le_mem_InitStaticPool(_hashmap_##name, \
(capacity), \
sizeof(le_hashmap_Entry_t)), \
_hashmap_##name##Buckets))
Definition: le_hashmap.h:255
#define LE_HASHMAP_BUCKET_COUNT(capacity)
Definition: le_hashmap.h:384

Initialize a statically-defined hashmap

If you create a hashmap with a smaller capacity than you actually use, then the map will continue to work, but performance will degrade the more you put in the map.

Parameters
nameName used when defining the static hashmap.
capacityCapacity specified when defining the static hashmap.
hashFuncCallback to invoke to hash an entry's key.
equalsFuncCallback to invoke to test key equality.
Returns
Returns a reference to the map.

◆ LE_HASHMAP_MAKE_HASH

#define LE_HASHMAP_MAKE_HASH (   type)
Value:
static size_t Hash##type \
( \
const void* type##Name \
) \
{ \
size_t byte=0, hash = 0; \
unsigned char c; \
const unsigned char* ptr = type##Name; \
for (byte = 0; byte < sizeof(type); ++byte) \
{ \
c = *ptr++; \
hash = c + (hash << 6) + (hash << 16) - hash; \
} \
return hash; \
} \
static bool Equals##type \
( \
const void* first##type, \
const void* second##type \
) \
{ \
return memcmp(first##type, second##type, sizeof(type)) == 0; \
}

Generic hash for any plain-old-datatype.

Typedef Documentation

◆ le_hashmap_EqualsFunc_t

typedef bool(* le_hashmap_EqualsFunc_t) (const void *firstKeyPtr, const void *secondKeyPtr)

Prototype for equality functions. The equality function returns true if the the keys point to values are equivalent. The HashMap doesn't know in advance which types are to be stored so this function must be supplied by the caller.

Parameters
firstKeyPtrPointer to the first key for comparing.
secondKeyPtrPointer to the second key for comparing.
Returns
Returns true if the values are the same, false otherwise

◆ le_hashmap_ForEachHandler_t

typedef bool(* le_hashmap_ForEachHandler_t) (const void *keyPtr, const void *valuePtr, void *contextPtr)

Prototype for callback functions for the iterator function le_hashmap_ForEach(). This function should return true in order to continue iterating, or false to stop.

Parameters
keyPtrPointer to the key at the current position in the map
valuePtrPointer to the value associated to this key
contextPtrPointer to the context supplied to le_hashmap_ForEach()
Returns
Returns true to continue, false to stop

◆ le_hashmap_HashFunc_t

typedef size_t(* le_hashmap_HashFunc_t) (const void *keyToHashPtr)

Prototype for hash functions. The hash function must generate a good spread of hashes without consuming lots of processing power.

Parameters
keyToHashPtrPointer to the key which will be hashed
Returns
The calculated hash value

◆ le_hashmap_It_Ref_t

typedef struct le_hashmap_It* le_hashmap_It_Ref_t

Reference to a HashMap Iterator.

◆ le_hashmap_Ref_t

typedef struct le_hashmap* le_hashmap_Ref_t

Reference to a HashMap.

Function Documentation

◆ le_hashmap_ContainsKey()

bool le_hashmap_ContainsKey ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr 
)

Tests if the HashMap contains a particular key.

Returns
Returns true if the key is found, false otherwise.
Parameters
[in]mapRefReference to the map.
[in]keyPtrPointer to the key to be searched.

◆ le_hashmap_CountCollisions()

size_t le_hashmap_CountCollisions ( le_hashmap_Ref_t  mapRef)

Counts the total number of collisions in the map. A collision occurs when more than one entry is stored in the map at the same index.

Returns
Returns the total collisions in the map.
Parameters
[in]mapRefReference to the map.

◆ 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 
)

Create a HashMap.

If you create a hashmap with a smaller capacity than you actually use, then the map will continue to work, but performance will degrade the more you put in the map.

Parameters
[in]nameStrName of the HashMap. This must be a static string as it is not copied.
[in]capacitySize of the hashmap
[in]hashFuncHash function
[in]equalsFuncEquality function
Returns
Returns a reference to the map.
Note
Terminates the process on failure, so no need to check the return value for errors.

◆ le_hashmap_EnableTrace()

void le_hashmap_EnableTrace ( le_hashmap_Ref_t  mapRef)

Immediately enables tracing on a particular hashmap object.

Parameters
[in]mapRefReference to the map.

◆ le_hashmap_EqualsString()

bool le_hashmap_EqualsString ( const void *  firstStringPtr,
const void *  secondStringPtr 
)

String equality function. Can be used as a parameter to le_hashmap_Create() if the key to the table is a string

Returns
Returns true if the strings are identical, false otherwise.
Parameters
[in]firstStringPtrPointer to the first string for comparing.
[in]secondStringPtrPointer to the second string for comparing.

◆ le_hashmap_EqualsUInt32()

bool le_hashmap_EqualsUInt32 ( const void *  firstIntPtr,
const void *  secondIntPtr 
)

Integer equality function. Can be used as a parameter to le_hashmap_Create() if the key to the table is a uint32_t.

Returns
Returns true if the integers are equal, false otherwise.
Parameters
[in]firstIntPtrPointer to the first integer for comparing.
[in]secondIntPtrPointer to the second integer for comparing.

◆ le_hashmap_EqualsUInt64()

bool le_hashmap_EqualsUInt64 ( const void *  firstIntPtr,
const void *  secondIntPtr 
)

Long integer equality function. This can be used as a paramter to le_hashmap_Create if the key to the table is a uint64_t

Returns
Returns true if the integers are equal, false otherwise
Parameters
[in]firstIntPtrPointer to the first long integer for comparing.
[in]secondIntPtrPointer to the second long integer for comparing.

◆ le_hashmap_EqualsVoidPointer()

bool le_hashmap_EqualsVoidPointer ( const void *  firstVoidPtr,
const void *  secondVoidPtr 
)

Pointer equality function. Can be used as a parameter to le_hashmap_Create() if the key to the table is an pointer or reference.

Returns
Returns true if the pointers are equal, false otherwise
Parameters
[in]firstVoidPtrFirst pointer for comparing.
[in]secondVoidPtrSecond pointer for comparing.

◆ le_hashmap_ForEach()

bool le_hashmap_ForEach ( le_hashmap_Ref_t  mapRef,
le_hashmap_ForEachHandler_t  forEachFn,
void *  contextPtr 
)

Iterates over the whole map, calling the supplied callback with each key-value pair. If the callback returns false for any key then this function will return.

Returns
Returns true if all elements were checked; or false if iteration was stopped early
Parameters
[in]mapRefReference to the map.
[in]forEachFnCallback function to be called with each pair.
[in]contextPtrPointer to a context to be supplied to the callback.

◆ le_hashmap_Get()

void* le_hashmap_Get ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr 
)

Retrieve a value from a HashMap.

Returns
Returns a pointer to the value or NULL if the key is not found.
Parameters
[in]mapRefReference to the map.
[in]keyPtrPointer to the key to be retrieved.

◆ le_hashmap_GetFirstNode()

le_result_t le_hashmap_GetFirstNode ( le_hashmap_Ref_t  mapRef,
void **  firstKeyPtr,
void **  firstValuePtr 
)

Retrieves the key and value of the first node stored in the hashmap. The hashmap is not sorted so this will simply return the first node stored in the map. There is no guarantee that a subsequent call to this function will return the same pair if new keys have been added to the map. If NULL is passed as the firstValuePointer then only the key will be returned.

Returns
LE_OK if the first node is returned or LE_NOT_FOUND if the map is empty. LE_BAD_PARAMETER if the key is NULL.
Parameters
[in]mapRefReference to the map
[out]firstKeyPtrPointer to the first key
[out]firstValuePtrPointer to the first value

◆ le_hashmap_GetIterator()

le_hashmap_It_Ref_t le_hashmap_GetIterator ( le_hashmap_Ref_t  mapRef)

Gets an iterator for step-by-step iteration over the map. In this mode, the iteration is controlled by the calling function using the le_hashmap_NextNode() function. There is one iterator per map, and calling this function resets the iterator position to the start of the map. The iterator is not ready for data access until le_hashmap_NextNode() has been called at least once.

Returns
Returns A reference to a hashmap iterator which is ready for le_hashmap_NextNode() to be called on it
Parameters
[in]mapRefReference to the map.

◆ le_hashmap_GetKey()

const void* le_hashmap_GetKey ( le_hashmap_It_Ref_t  iteratorRef)

Retrieves a pointer to the key where the iterator is currently pointing. If the iterator has just been initialized and le_hashmap_NextNode() has not been called, or if the iterator has been invalidated, this will return NULL.

Returns
Pointer to the current key, or NULL if the iterator has been invalidated or is not ready.
Parameters
[in]iteratorRefReference to the iterator.

◆ le_hashmap_GetNodeAfter()

le_result_t le_hashmap_GetNodeAfter ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr,
void **  nextKeyPtr,
void **  nextValuePtr 
)

Retrieves the key and value of the node after the passed in key. The hashmap is not sorted so this will simply return the next node stored in the map. There is no guarantee that a subsequent call to this function will return the same pair if new keys have been added to the map. If NULL is passed as the nextValuePtr then only the key will be returned.

Returns
LE_OK if the next node is returned. If the keyPtr is not found in the map then LE_BAD_PARAMETER is returned. LE_NOT_FOUND is returned if the passed in key is the last one in the map.
Parameters
[in]mapRefReference to the map
[in]keyPtrPointer to the key to be searched for
[out]nextKeyPtrPointer to the first key
[out]nextValuePtrPointer to the first value

◆ le_hashmap_GetStoredKey()

void* le_hashmap_GetStoredKey ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr 
)

Retrieve a stored key from a HashMap.

Returns
Returns a pointer to the key that was stored in the HashMap by le_hashmap_Put() or NULL if the key is not found.
Parameters
[in]mapRefReference to the map.
[in]keyPtrPointer to the key to be retrieved.

◆ le_hashmap_GetValue()

void* le_hashmap_GetValue ( le_hashmap_It_Ref_t  iteratorRef)

Retrieves a pointer to the value where the iterator is currently pointing. If the iterator has just been initialized and le_hashmap_NextNode() has not been called, or if the iterator has been invalidated, this will return NULL.

Returns
Pointer to the current value, or NULL if the iterator has been invalidated or is not ready.
Parameters
[in]iteratorRefReference to the iterator.

◆ le_hashmap_HashString()

size_t le_hashmap_HashString ( const void *  stringToHashPtr)

String hashing function. Can be used as a parameter to le_hashmap_Create() if the key to the table is a string.

Returns
Returns the hash value of the string pointed to by stringToHash.
Parameters
[in]stringToHashPtrPointer to the string to be hashed.

◆ le_hashmap_HashUInt32()

size_t le_hashmap_HashUInt32 ( const void *  intToHashPtr)

Integer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to the table is a uint32_t.

Returns
Returns the hash value of the uint32_t pointed to by intToHash.
Parameters
[in]intToHashPtrPointer to the integer to be hashed.

◆ le_hashmap_HashUInt64()

size_t le_hashmap_HashUInt64 ( const void *  intToHashPtr)

Long integer hashing function. This can be used as a paramter to le_hashmap_Create if the key to the table is a uint64_t

Returns
Returns the hash value of the uint64_t pointed to by intToHash
Parameters
[in]intToHashPtrPointer to the long integer to be hashed

◆ le_hashmap_HashVoidPointer()

size_t le_hashmap_HashVoidPointer ( const void *  voidToHashPtr)

Pointer hashing function. Can be used as a parameter to le_hashmap_Create() if the key to the table is an pointer or reference. Simply pass in the address as the key.

Returns
Returns the hash value of the pointer pointed to by voidToHashPtr
Parameters
[in]voidToHashPtrPointer to be hashed

◆ le_hashmap_isEmpty()

bool le_hashmap_isEmpty ( le_hashmap_Ref_t  mapRef)

Tests if the HashMap is empty (i.e. contains zero keys).

Returns
Returns true if empty, false otherwise.
Parameters
[in]mapRefReference to the map.

◆ le_hashmap_MakeTraceable()

void le_hashmap_MakeTraceable ( le_hashmap_Ref_t  mapRef)

Makes a particular hashmap traceable without enabling the tracing. After this is called, when the trace keyword for this hashmap (the hashmap's name) is enabled for the "framework" component in the process, tracing will start. If that keyword was enabled before this function was called, tracing will start immediately when it is called.

Parameters
[in]mapRefReference to the map.

◆ le_hashmap_NextNode()

le_result_t le_hashmap_NextNode ( le_hashmap_It_Ref_t  iteratorRef)

Moves the iterator to the next key/value pair in the map. Order is dependent on the hash algorithm and the order of inserts, and is not sorted at all.

Returns
Returns LE_OK unless you go past the end of the map, then returns LE_NOT_FOUND.
Parameters
[in]iteratorRefReference to the iterator.

◆ le_hashmap_PrevNode()

le_result_t le_hashmap_PrevNode ( le_hashmap_It_Ref_t  iteratorRef)

Moves the iterator to the previous key/value pair in the map. Order is dependent on the hash algorithm and the order of inserts, and is not sorted at all.

Returns
Returns LE_OK unless you go past the beginning of the map, then returns LE_NOT_FOUND.
Parameters
[in]iteratorRefReference to the iterator

◆ le_hashmap_Put()

void* le_hashmap_Put ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr,
const void *  valuePtr 
)

Add a key-value pair to a HashMap. If the key already exists in the map, the previous value will be replaced with the new value passed into this function.

Returns
Returns NULL for a new entry or a pointer to the old value if it is replaced.
Parameters
[in]mapRefReference to the map.
[in]keyPtrPointer to the key to be stored.
[in]valuePtrPointer to the value to be stored.

◆ le_hashmap_Remove()

void* le_hashmap_Remove ( le_hashmap_Ref_t  mapRef,
const void *  keyPtr 
)

Remove a value from a HashMap.

Returns
Returns a pointer to the value or NULL if the key is not found.
Parameters
[in]mapRefReference to the map.
[in]keyPtrPointer to the key to be removed.

◆ le_hashmap_RemoveAll()

void le_hashmap_RemoveAll ( le_hashmap_Ref_t  mapRef)

Deletes all the entries held in the hashmap. This will not delete the data pointed to by the key and value pointers. That cleanup is the responsibility of the caller. This allows the map to be re-used. Currently maps can't be deleted.

Parameters
[in]mapRefReference to the map.

◆ le_hashmap_Size()

size_t le_hashmap_Size ( le_hashmap_Ref_t  mapRef)

Calculates the number of keys in the HashMap.

Returns
The number of keys in the HashMap.
Parameters
[in]mapRefReference to the map.