le_hashmap.h

Go to the documentation of this file.

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------

#ifndef LEGATO_HASHMAP_INCLUDE_GUARD
#define LEGATO_HASHMAP_INCLUDE_GUARD

#include "le_mem.h"

#include "le_singlyLinkedList.h"
#include "le_doublyLinkedList.h"

#if LE_CONFIG_REDUCE_FOOTPRINT
typedef le_sls_List_t le_hashmap_Bucket_t;
typedef le_sls_Link_t le_hashmap_Link_t;
#else /* if not LE_CONFIG_REDUCE_FOOTPRINT */
typedef le_dls_List_t le_hashmap_Bucket_t;
typedef le_dls_Link_t le_hashmap_Link_t;
#endif /* end LE_CONFIG_REDUCE_FOOTPRINT */

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
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
);


typedef struct le_hashmap_Entry
{
    le_hashmap_Link_t    entryListLink; 
    const void          *keyPtr;        
    const void          *valuePtr;      
}
le_hashmap_Entry_t;

typedef struct le_hashmap_It
{
    size_t               currentIndex;      
    le_hashmap_Link_t   *currentLinkPtr;    
}
le_hashmap_HashmapIt_t;

typedef struct le_hashmap
{
    le_hashmap_HashmapIt_t   iterator;      

    le_hashmap_EqualsFunc_t  equalsFuncPtr; 
    le_hashmap_HashFunc_t    hashFuncPtr;   

    le_hashmap_Bucket_t     *bucketsPtr;    
    le_mem_PoolRef_t         entryPoolRef;  
    size_t                   bucketCount;   
    size_t                   size;          

#if LE_CONFIG_HASHMAP_NAMES_ENABLED
    const char               *nameStr;        
    le_log_TraceRef_t         traceRef;       
#endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */
}
le_hashmap_Hashmap_t;


#if LE_CONFIG_HASHMAP_NAMES_ENABLED
//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_hashmap_Ref_t le_hashmap_Create
(
    const char                *nameStr,
    size_t                     capacity,
    le_hashmap_HashFunc_t      hashFunc,
    le_hashmap_EqualsFunc_t    equalsFunc
);
#else /* if not LE_CONFIG_HASHMAP_NAMES_ENABLED */
//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_hashmap_Ref_t _le_hashmap_Create
(
    size_t                     capacity,
    le_hashmap_HashFunc_t      hashFunc,
    le_hashmap_EqualsFunc_t    equalsFunc
);
//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
LE_DECLARE_INLINE le_hashmap_Ref_t le_hashmap_Create
(
    const char                *nameStr,
    size_t                     capacity,
    le_hashmap_HashFunc_t      hashFunc,
    le_hashmap_EqualsFunc_t    equalsFunc
)
{
    LE_UNUSED(nameStr);
    return _le_hashmap_Create(capacity, hashFunc, equalsFunc);
}
#endif /* end LE_CONFIG_HASHMAP_NAMES_ENABLED */



//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
#define LE_HASHMAP_BUCKET_COUNT(capacity)                               \
    ((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))))))))))))))

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
#define LE_HASHMAP_DEFINE_STATIC(name, capacity)                                          \
    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)]

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
#define LE_HASHMAP_DEFINE_STATIC_IN_SECTION(name, capacity, sectionName)                          \
    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)))

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
#if LE_CONFIG_HASHMAP_NAMES_ENABLED
#   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
        (inline_static_assert(                                                      \
            sizeof(_hashmap_##name##Buckets) ==                                     \
                sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
            "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))
#else
#   define le_hashmap_InitStatic(name, capacity, hashFunc, equalsFunc)              \
        (inline_static_assert(                                                      \
            sizeof(_hashmap_##name##Buckets) ==                                     \
                sizeof(le_hashmap_Entry_t *[LE_HASHMAP_BUCKET_COUNT(capacity)]),    \
            "hashmap init capacity does not match definition"),                     \
        _le_hashmap_InitStatic((capacity), (hashFunc), (equalsFunc),                \
                               &_hashmap_##name##Hashmap,                           \
                               le_mem_InitStaticPool(_hashmap_##name,               \
                                                    (capacity),                     \
                                                    sizeof(le_hashmap_Entry_t)),    \
                               _hashmap_##name##Buckets))
#endif

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_hashmap_Ref_t _le_hashmap_InitStatic
(
#if LE_CONFIG_HASHMAP_NAMES_ENABLED
    const char              *nameStr,       
#endif
    size_t                   capacity,      
    le_hashmap_HashFunc_t    hashFunc,      
    le_hashmap_EqualsFunc_t  equalsFunc,    
    le_hashmap_Hashmap_t    *mapPtr,        
    le_mem_PoolRef_t         entryPoolRef,  
    le_hashmap_Bucket_t     *bucketsPtr     
);


//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------

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


//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
#define LE_HASHMAP_MAKE_HASH(type)                              \
    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; \
    }



//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
void le_hashmap_MakeTraceable
(
    le_hashmap_Ref_t mapRef     
);


//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
void le_hashmap_EnableTrace
(
    le_hashmap_Ref_t mapRef     
);


#endif /* LEGATO_HASHMAP_INCLUDE_GUARD */