Detailed Description

Special hashmap for DP-border Steiner tree algorithm.

Author: Daniel Rehfeldt

modified version of https://github.com/sheredom/hashmap.h

#include <stdlib.h>
#include <string.h>
#include "scip/scip.h"

Data Structures
struct	hashmap_element_s

struct	hashmap_s

Macros
#define	HASHMAP_USED

#define	HASHMAP_MAX_CHAIN_LENGTH (8)

#define	HASHMAP_CAST(type, x) ((type)x)

#define	HASHMAP_PTR_CAST(type, x) ((type)x)

#define	HASHMAP_NULL 0

Typedefs
typedef struct hashmap_s	DPBHASHMAP

Functions
static SCIP_RETCODE	hashmap_create (const unsigned initial_size, const char keyarr, struct hashmap_s const out_hashmap) HASHMAP_USED
	Create a hashmap. More...

static void	hashmap_updateKeyarr (const char keyarr, struct hashmap_s out_hashmap) HASHMAP_USED

static int	hashmap_putcheck (struct hashmap_s *const hashmap, int key_position, const unsigned len, int value) HASHMAP_USED
	Put an element into the hashmap. More...

static void	hashmap_put (struct hashmap_s *const hashmap, int position, const unsigned len, int value) HASHMAP_USED

static int	hashmap_get (const struct hashmap_s *const hashmap, int position, const unsigned len) HASHMAP_USED
	Get an element from the hashmap. More...

static int	hashmap_remove (struct hashmap_s *const hashmap, int position, const unsigned len) HASHMAP_USED
	Remove an element from the hashmap. More...

static int	hashmap_iterate_pairs (struct hashmap_s const hashmap, struct hashmap_s const hashmap_new) HASHMAP_USED
	Iterate over all the elements in a hashmap. More...

static unsigned	hashmap_num_entries (const struct hashmap_s *const hashmap) HASHMAP_USED
	Get the size of the hashmap. More...

static SCIP_Bool	hashmap_isEmpty (const struct hashmap_s *const hashmap) HASHMAP_USED

static void	hashmap_destroy (struct hashmap_s *const hashmap) HASHMAP_USED
	Destroy the hashmap. More...

static unsigned	hashmap_crc32_helper (const char *const s, const unsigned len) HASHMAP_USED

static unsigned	hashmap_hash_helper_int_helper (const struct hashmap_s const m, const char const keystring, const unsigned len) HASHMAP_USED

static int	hashmap_hash_helper (const struct hashmap_s const m, int position, const unsigned len, unsigned const out_index) HASHMAP_USED

static int	hashmap_rehash_iterator (struct hashmap_s const m_new, struct hashmap_element_s const e) HASHMAP_USED

static int	hashmap_rehash_helper (struct hashmap_s *const m) HASHMAP_USED

static int	hashmap_match_helper (const struct hashmap_element_s const element, const char const key, const char *const keyarr, const unsigned len)

Macro Definition Documentation

◆ HASHMAP_USED

#define HASHMAP_USED

Definition at line 73 of file dpborder_hashmap.h.

◆ HASHMAP_MAX_CHAIN_LENGTH

#define HASHMAP_MAX_CHAIN_LENGTH (8)

Definition at line 93 of file dpborder_hashmap.h.

Referenced by hashmap_get(), hashmap_hash_helper(), and hashmap_remove().

◆ HASHMAP_CAST

#define HASHMAP_CAST	(	type,
		x
	)	((type)x)

Definition at line 189 of file dpborder_hashmap.h.

Referenced by hashmap_crc32_helper(), and hashmap_create().

◆ HASHMAP_PTR_CAST

#define HASHMAP_PTR_CAST	(	type,
		x
	)	((type)x)

Definition at line 190 of file dpborder_hashmap.h.

◆ HASHMAP_NULL

#define HASHMAP_NULL 0

Definition at line 191 of file dpborder_hashmap.h.

Typedef Documentation

◆ DPBHASHMAP

typedef struct hashmap_s DPBHASHMAP

Function Documentation

◆ hashmap_create()

SCIP_RETCODE hashmap_create	(	const unsigned	initial_size,
		const char *	keyarr,
		struct hashmap_s *const	out_hashmap
	)

static

Create a hashmap.

Parameters

initial_size	The initial size of the hashmap. Must be a power of two.
out_hashmap	The storage for the created hashmap.
keyarr	Array with keys

Returns: On success 0 is returned.

Note that the initial size of the hashmap must be a power of two, and creation of the hashmap will fail if this is not the case.

Definition at line 201 of file dpborder_hashmap.h.

References hashmap_s::elements, HASHMAP_CAST, hashmap_s::keyarray, SCIP_ERROR, SCIP_OKAY, hashmap_s::size, and hashmap_s::table_size.

Referenced by dpborder_solve(), and hashmap_rehash_helper().

◆ hashmap_updateKeyarr()

void hashmap_updateKeyarr	(	const char *	keyarr,
		struct hashmap_s *	out_hashmap
	)

static

Definition at line 223 of file dpborder_hashmap.h.

References hashmap_s::keyarray.

Referenced by initSolve(), and partitionTryRealloc().

◆ hashmap_putcheck()

int hashmap_putcheck	(	struct hashmap_s *const	hashmap,
		int	key_position,
		const unsigned	len,
		int	value
	)

static

Put an element into the hashmap.

Parameters

hashmap	The hashmap to insert into.
key_position	The string key position to use.
len	The length of the string key.
value	The value to insert.

Returns: On success 0 is returned.

The key string slice is not copied when creating the hashmap entry, and thus must remain a valid pointer until the hashmap entry is removed or the hashmap is destroyed.

Definition at line 232 of file dpborder_hashmap.h.

References hashmap_s::elements, hashmap_hash_helper(), hashmap_rehash_helper(), hashmap_element_s::in_use, hashmap_element_s::key_len, hashmap_element_s::key_position, hashmap_s::size, and hashmap_element_s::value.

Referenced by hashmap_rehash_iterator().