Hash maps

Constants

HASH_MAP_DUPLICATE, HASH_MAP_NOT_FOUND, HASH_MAP_OK

hm_ functions return codes

VALUES

• HASH_MAP_OK - everything went fine
  
• HASH_MAP_DUPLICATE - element with such key exists
  
• HASH_MAP_NOT_FOUND - such element not found
  

#define HASH_MAP_OK 0
#define HASH_MAP_DUPLICATE  -1
#define HASH_MAP_NOT_FOUND  -2

HM_WALKER_CONTINUE, HM_WALKER_REMOVE, HM_WALKER_STOP

Walker flags for hash_map_walk. Returned by walker func.

VALUES

• HM_WALKER_CONTINUE - continue walking
  
• HM_WALKER_STOP - stop walking here and return current object (useful for "find")
  
• HM_WALKER_REMOVE - remove current element
  

#define HM_WALKER_CONTINUE  0
#define HM_WALKER_STOP  0x01
#define HM_WALKER_REMOVE    0x02

Functions

hm_item_ptr

public

STATIC_INLINE void* hm_item_ptr(hm_item_t* obj, ptrdiff_t off) 
STATIC_INLINE void* hm_item_ptr(hm_item_t* obj, ptrdiff_t off) 

hm_get_key

public

STATIC_INLINE hm_key_t* hm_get_key(hashmap_t* hm, hm_item_t* obj) 

hash_map_init

public

Initialize static hash map.

Because hash map usually a global object, it doesn't
support formatted names

ARGUMENTS

• hm - hash map to initialize
  
• name - identifier for hash map
  

LIBEXPORT void hash_map_init(hashmap_t* hm, const char* name)

hash_map_create

public

Create dynamic hashmap

ARGUMENTS

• base - static hashmap, that contains compare/hash functions, size and offsets
  
• namefmt - name format
  

LIBEXPORT hashmap_t* hash_map_create(hashmap_t* base, const char* namefmt, ...)

hash_map_destroy

public

Destroy hash map

It shouldn't contain objects (or assertion will rise)

LIBEXPORT void hash_map_destroy(hashmap_t* hm)

hash_map_insert

public

Insert element into hash map

ARGUMENTS

• hm - hash map
  
• object - object to be inserted
  

RETURN VALUES
HASH_MAP_OK if object was successfully inserted or HASH_MAP_DUPLICATE if object with same key (not hash!) already exists in hash map

LIBEXPORT int  hash_map_insert(hashmap_t* hm, hm_item_t* object)

hash_map_remove

public

Remove element from hash map

ARGUMENTS

• hm - hash map
  
• object - object to be removed
  

RETURN VALUES
HASH_MAP_OK if object was successfully remove or HASH_MAP_NOT_FOUND if object is not

LIBEXPORT int  hash_map_remove(hashmap_t* hm, hm_item_t* object)

hash_map_find_nolock

public

Find object in hash map by key without locking hashmap
call it only from walker context!

LIBEXPORT void* hash_map_find_nolock(hashmap_t* hm, const hm_key_t* key)

hash_map_find

public

Find object in hash map by key

LIBEXPORT void* hash_map_find(hashmap_t* hm, const hm_key_t* key)

hash_map_walk

public

Walk over objects in hash map and execute func for each object.

Func proto: int (func)(void object, void* arg)
Function func may return HM_WALKER_CONTINUE or HM_WALKER_STOP.

For HM_WALKER_STOP, hash_map_walk will stop walking over hash map and return
current object

ARGUMENTS

• hm - hash map
  
• func - function that will be called for each object
  
• arg - argument that will be passed as second argument for func
  

RETURN VALUES
NULL or object where func returned STOP

NOTES
because of nature of hash maps, walking order is undefined

LIBEXPORT void* hash_map_walk(hashmap_t* hm, hm_walker_func func, void* arg)

hm_string_hash

public

Calculate hash for strings

LIBEXPORT unsigned hm_string_hash(const hm_key_t* str, unsigned mask)

DECLARE_HASH_MAP

Declare hash map

ARGUMENTS

• name - name of hash map var (all corresponding objects will be named hm_(object)(name))
  
• is_indirect - if set to B_TRUE, key_field is considered a pointer to a key, not a key itself
  
• type - type of elements
  
• size - size of hash map (not of type)
  
• key_field - field of element that contains key
  
• next_field - field of element that contains pointer to next object
  
• hm_hash_body - function body {} that hashes key and returns hash (params: const void* key)
  
• hm_compare_body - function body {} that compares to keys (params: const void* key1, const void* key2)
  

#define DECLARE_HASH_MAP(name, is_indirect, type, size, key_field, next_field, hm_hash_body, hm_compare_body)

DECLARE_HASH_MAP_STRKEY

Same as DECLARE_HASH_MAP, but assumes that key field is string declared as char* (AAS)

#define DECLARE_HASH_MAP_STRKEY(name, type, size, key_field, next_field, mask)

Types

typedef void hm_item_t;

typedef void hm_key_t;

hashmap_t

typedef struct {
    size_t            hm_size;
    hm_item_t**     hm_heads;

    boolean_t        hm_indirect;
    int             hm_type;

    thread_mutex_t hm_mutex;

    ptrdiff_t hm_off_key;
    ptrdiff_t hm_off_next;

    char* hm_name;

    unsigned (*hm_hash_key)(const hm_key_t* key);
    boolean_t (*hm_compare)(const hm_key_t* key1, const hm_key_t* key2);
} hashmap_t;