This header implements a simple hash map data structure. More...

#include <stdint.h>
#include <datatypes/array.h>

Include dependency graph for hash_map.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	_inner_hash_map_t

struct	_inner_hash_map_t::_hash_map_node_t

Macros
#define	MAX_LOAD_FACTOR 0.85

#define	MIN_LOAD_FACTOR 0.05

#define	HMAP_INVALID_I UINT_MAX

#define	rootsim_hash_map(type)

#define	hash_map_init(hashmap)

#define	hash_map_count(hashmap)

#define	hash_map_fini(hashmap)

#define	hash_map_reserve_elem(hashmap, key)

#define	hash_map_lookup(hashmap, key)

#define	hash_map_delete_elem(hashmap, elem)

#define	hash_map_items(hashmap)

#define	hash_map_dump_size(hashmap)

#define	hash_map_dump(hashmap, destination)

#define	hash_map_load(hashmap, source)

Typedefs
typedef uint32_t	map_size_t

typedef map_size_t	hash_t

typedef unsigned long long	key_type_t

Functions
void	_hash_map_init (struct _inner_hash_map_t *_i_hmap)

void	_hash_map_fini (struct _inner_hash_map_t *_i_hmap)

void	_hash_map_add (struct _inner_hash_map_t *_i_hmap, unsigned long long key, map_size_t cur_count)

unsigned	_hash_map_lookup (struct _inner_hash_map_t *_i_hmap, unsigned long long key)

void	_hash_map_remove (struct _inner_hash_map_t *_i_hmap, unsigned long long key, map_size_t cur_count)

void	_hash_map_update_i (struct _inner_hash_map_t *_i_hmap, unsigned long long key, map_size_t new_i)

size_t	_hash_map_dump_size (struct _inner_hash_map_t *_i_hmap)

unsigned char *	_hash_map_dump (struct _inner_hash_map_t _i_hmap, unsigned char _destination)

unsigned char *	_hash_map_load (struct _inner_hash_map_t _i_hmap, unsigned char _source)

Detailed Description

This header implements a simple hash map data structure.

This file is part of ROOT-Sim (ROme OpTimistic Simulator).

ROOT-Sim is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; only version 3 of the License applies.

ROOT-Sim is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with ROOT-Sim; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

Date: 9 Nov 2018

Author: Andrea Piccione

This a simple hash map implementation, currently used in the abm layer. It's based on a open addressing design: it handles collisions through linear probing, entries are reordered through robin hood hashing. TODO by default __wrap_malloc and __wrap_free are used, instead the choice of the allocation facilities should change on demand

Definition in file hash_map.h.

Macro Definition Documentation

#define hash_map_count ( hashmap )

Value:

({ \
        array_count((hashmap).elems);\
    })

Definition at line 69 of file hash_map.h.

#define hash_map_delete_elem	(	hashmap,
		elem
	)

Value:

({ \
        assert(array_count((hashmap).elems)); \
        key_type_t __l_key = array_peek((hashmap).elems).key; \
        unsigned __rem_i = elem - array_items((hashmap).elems); \
        _hash_map_remove(&((hashmap)._i_hmap), elem->key, array_count((hashmap).elems)); \
        _hash_map_update_i(&((hashmap)._i_hmap), __l_key, __rem_i); \
        array_lazy_remove_at((hashmap).elems, __rem_i); \
    })

Definition at line 90 of file hash_map.h.

#define hash_map_dump	(	hashmap,
		destination
	)

Value:

({ \
        array_dump((hashmap).elems, destination); \
        destination = _hash_map_dump(&((hashmap)._i_hmap), destination); \
    })

Definition at line 111 of file hash_map.h.

#define hash_map_dump_size ( hashmap )

Value:

({ \
        size_t __ret = array_dump_size((hashmap).elems); \
        __ret += _hash_map_dump_size(&((hashmap)._i_hmap)); \
        __ret; \
    })

Definition at line 105 of file hash_map.h.

#define hash_map_fini ( hashmap )

Value:

({ \
        _hash_map_fini(&((hashmap)._i_hmap)); \
        array_fini((hashmap).elems); \
    })

Definition at line 73 of file hash_map.h.

#define hash_map_init ( hashmap )

Value:

({ \
        _hash_map_init(&((hashmap)._i_hmap)); \
        array_init((hashmap).elems); \
    })

Definition at line 64 of file hash_map.h.

#define hash_map_items ( hashmap )

Value:

({ \
        assert(array_count((hashmap).elems)); \
        __typeof__(array_items((hashmap).elems)) __ret = array_items((hashmap).elems); \
        __ret; \
    })

Definition at line 99 of file hash_map.h.

#define hash_map_load	(	hashmap,
		source
	)

Value:

({ \
        array_load((hashmap).elems, source); \
        source = _hash_map_load(&((hashmap)._i_hmap), source); \
    })

Definition at line 116 of file hash_map.h.

#define hash_map_lookup	(	hashmap,
		key
	)

Value:

({ \
        map_size_t __lkp_i =  _hash_map_lookup(&((hashmap)._i_hmap), key); \
        __lkp_i != UINT_MAX ? &(array_get_at((hashmap).elems, __lkp_i)) : NULL; \
    })

Definition at line 85 of file hash_map.h.

#define hash_map_reserve_elem	(	hashmap,
		key
	)

Value:

({ \
        _hash_map_add(&((hashmap)._i_hmap), key, array_count((hashmap).elems)); \
        __typeof__(array_items((hashmap).elems)) __ret = array_reserve((hashmap).elems, 1); \
        assert(__ret); \
        __ret; \
    })

Definition at line 78 of file hash_map.h.

#define rootsim_hash_map ( type )

Value:

struct { \
        rootsim_array(type) elems; \
        struct _inner_hash_map_t _i_hmap; \
        }

Definition at line 58 of file hash_map.h.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation