#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <inttypes.h>
#include "hashmap_tx.h"

Include dependency graph for hashmap_tx.c:

Macros
#define	HASH_FUNC_COEFF_P 32212254719ULL

#define	INIT_BUCKETS_NUM 10

#define	MIN_HASHSET_THRESHOLD 5

#define	MAX_HASHSET_THRESHOLD 10

Functions
static void	create_hashmap (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, uint32_t seed)
	Hashmap initializer. More...

static uint64_t	hash (const TOID(struct hashmap_tx) hashmap, const TOID(struct buckets) buckets, uint64_t value)
	The hash function. More...

static void	hm_tx_rebuild (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, size_t new_len)
	Rebuilds the hashmap when the hashmap size threshold is reached. More...

int	hm_tx_insert (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, uint64_t key, MEMoid value)
	Inserts the specified `value` into the `hashmap`. More...

MEMoid	hm_tx_remove (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, uint64_t key)
	Removes specified `value` from the `hashmap`. More...

int	hm_tx_foreach (PMEMobjpool pop, TOID(struct hashmap_tx) hashmap, int(cb)(uint64_t key, MEMoid value, void arg), void arg)
	Calls a given `callback` for every element in the `hashmap`. More...

void	hm_tx_debug (PMEMobjpool pop, TOID(struct hashmap_tx) hashmap, FILE out)
	Prints complete hashmap state. More...

MEMoid	hm_tx_get (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, uint64_t key)
	Checks whether specified `key` is in the `hashmap` and retries the `value` associated with it. More...

int	hm_tx_lookup (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, uint64_t key)
	Checks whether specified `key` exists in the `hashmap`. More...

size_t	hm_tx_count (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap)
	Returns number of elements in the `hashmap`. More...

int	hm_tx_init (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap)
	Recovers `hashmap` state. More...

int	hm_tx_create (PMEMobjpool pop, TOID(struct hashmap_tx) map, void *arg)
	Allocates a new `hashmap`. More...

int	hm_tx_check (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap)
	Checks if specified `persistent` object is an instance of `hashmap`. More...

int	hm_tx_cmd (PMEMobjpool *pop, TOID(struct hashmap_tx) hashmap, unsigned cmd, uint64_t arg)
	Executes a command for `hashmap`. More...

Detailed Description

The implemantation of a Persistent Hashmap using only transaction APIs of libpmemobj

Definition in file hashmap_tx.c.

Macro Definition Documentation

◆ HASH_FUNC_COEFF_P

#define HASH_FUNC_COEFF_P 32212254719ULL

Definition at line 15 of file hashmap_tx.c.

◆ INIT_BUCKETS_NUM

#define INIT_BUCKETS_NUM 10

Definition at line 18 of file hashmap_tx.c.

◆ MAX_HASHSET_THRESHOLD

#define MAX_HASHSET_THRESHOLD 10

Definition at line 24 of file hashmap_tx.c.

◆ MIN_HASHSET_THRESHOLD

#define MIN_HASHSET_THRESHOLD 5

Definition at line 21 of file hashmap_tx.c.

Function Documentation

◆ create_hashmap()

static void create_hashmap	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		uint32_t	seed
	)

static

Hashmap initializer.

This is the function called by hm_tx_create() for creation of the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` would be stored.
hashmap	the typed hashmap which needs to be initialised.
seed	the seed for initialising hashing varaibles.

Returns: nothing

Note: This is an internal function. Not exposed to other files.

See also: hm_tx_create()

Definition at line 38 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hash()

static uint64_t hash	(	const TOID(struct hashmap_tx) *	hashmap,
		const TOID(struct buckets) *	buckets,
		uint64_t	value
	)

static

The hash function.

Its the simplest hashing function.

This function is used to get the hash for a key in the hashmap.

Parameters

hashmap	the hashmap which is being accessed
buckets	the pointer to the buckets in the `hashmap`
value	the `value` that needs to be hashed. *

Note: This is an internal function. Not exposed to other files.

See also: For more info on the hash function; hm_tx_insert() hm_tx_remove() hm_tx_get() hm_tx_lookup()

Definition at line 76 of file hashmap_tx.c.

◆ hm_tx_check()

int hm_tx_check	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap
	)

Checks if specified persistent object is an instance of hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.

Returns: 0: if it is a hashmap; 1: otherwise

Definition at line 463 of file hashmap_tx.c.

◆ hm_tx_cmd()

int hm_tx_cmd	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		unsigned	cmd,
		uint64_t	arg
	)

Executes a command for hashmap.

Available commands are: HASHMAP_CMD_REBUILD and HASHMAP_CMD_DEBUG

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
cmd	the command to be executed.
arg	the arguments for the command.

Returns: 0: on successful execution; -EINVAL: otherwise

Definition at line 480 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_count()

size_t hm_tx_count	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap
	)

Returns number of elements in the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.

Returns: Number of elements in the hashmap.

Definition at line 401 of file hashmap_tx.c.

◆ hm_tx_create()

int hm_tx_create	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx) *	map,
		void *	arg
	)

Allocates a new hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` would be stored.
hashmap	the typed hashmap which needs to be initialised.
arg	additional arguments if necessary

Returns: 0: on successful creation; -1: on failure.

See also: create_hashmap()

Definition at line 433 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_debug()

void hm_tx_debug	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		FILE *	out
	)

Prints complete hashmap state.

This function is used for debugging purposes.

Parameters

PMEMobjpool	the `pool` where the `hashmap` would be stored.
hashmap	the typed hashmap which needs to be initialised.
out	the `file desciptor` for where the output needs to be recorded.

Returns: Nothing

Note: The out paramater can be stdout and stderr too.

Definition at line 314 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_foreach()

int hm_tx_foreach	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		int()(uint64_t key, MEMoid value, void arg)	cb,
		void *	arg
	)

Calls a given callback for every element in the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
cb	the `calback` function.
arg	additional arguments for the `callback` function

Returns: The return value of the callback function.

Definition at line 281 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_get()

MEMoid hm_tx_get	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		uint64_t	key
	)

Checks whether specified key is in the hashmap and retries the value associated with it.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
key	the `key` for the `value` being inserted. It will be used to calculate the `hash`.

Returns: the value associated with the key.; MEMOID_NULL upon failure or if not such key existed

Definition at line 349 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_init()

int hm_tx_init	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap
	)

Recovers hashmap state.

Called after pmemobj_open().

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.

See also: init_types_table()

Definition at line 415 of file hashmap_tx.c.

◆ hm_tx_insert()

int hm_tx_insert	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		uint64_t	key,
		MEMoid	value
	)

Inserts the specified value into the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
key	the `key` for the `value` being inserted. It will be used to calculate the `hash`.
value	the `value` that is supposed to be inserted.

Returns: 0: if successful; 1: if value already existed; -1: if the insertion failed

Warning: If the key already exists in the hashmap, then the value provided is not inserted.

Definition at line 164 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_lookup()

int hm_tx_lookup	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		uint64_t	key
	)

Checks whether specified key exists in the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
key	the `key` for the `value` being inserted. It will be used to calculate the `hash`.

Returns: 1: if the key exists; 0: otherwise

See also: hm_tx_get()

Definition at line 377 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_rebuild()

static void hm_tx_rebuild	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		size_t	new_len
	)

static

Rebuilds the hashmap when the hashmap size threshold is reached.

The hashmap is rebuilt, i.e its size is increased/decreased, when its size exceeds the MAX_HASHSET_THRESHOLD or when the number of elements in the hashmap are less than the number of buckets in the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
new_len	the length of the resulting `hashmap` after resizing.

Returns: nothing

Note: This is an internal function. Not exposed to other files.

See also: hm_tx_insert() hm_tx_remove()

Definition at line 102 of file hashmap_tx.c.

Here is the call graph for this function:

◆ hm_tx_remove()

MEMoid hm_tx_remove	(	PMEMobjpool *	pop,
		TOID(struct hashmap_tx)	hashmap,
		uint64_t	key
	)

Removes specified value from the hashmap.

Parameters

PMEMobjpool	the `pool` where the `hashmap` is stored.
hashmap	the typed hashmap which needs to be initialised.
key	the `key` for the `value` being inserted. It will be used to calculate the `hash`.

Returns: the value associated with the key deleted upon success; MEMOID_NULL upon failure or if not such key existed

Note: This function does call hm_tx_rebuild() if the the number of elements in the hashmap are less that number of buckets.

Definition at line 224 of file hashmap_tx.c.

Here is the call graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ HASH_FUNC_COEFF_P

◆ INIT_BUCKETS_NUM

◆ MAX_HASHSET_THRESHOLD

◆ MIN_HASHSET_THRESHOLD

Function Documentation

◆ create_hashmap()

◆ hash()

◆ hm_tx_check()

◆ hm_tx_cmd()

◆ hm_tx_count()

◆ hm_tx_create()

◆ hm_tx_debug()

◆ hm_tx_foreach()

◆ hm_tx_get()

◆ hm_tx_init()

◆ hm_tx_insert()

◆ hm_tx_lookup()

◆ hm_tx_rebuild()

◆ hm_tx_remove()