hashmap.h File Reference

#include <stddef.h>
#include <assert.h>
#include <stdbool.h>

Go to the source code of this file.

Macros
#define	K   void*
	Defines a generic, non-resizing hashmap data type.
#define	V   void*
#define	HASH_OF(key)   (size_t) key
#define	HASHMAP(token)   hashmap##_##token

Functions
struct	HASHMAP (entry_t) *HASHMAP(get_actual_address)(HASHMAP(t) *hashmap = hashmap->entries + hashmap->capacity
	Return the actual address of the hashmap entry corresponding to key, or the address of the closest empty entry if no such entry exists.
struct	HASHMAP (t) *HASHMAP(new)(size_t capacity = (HASHMAP(t)*)malloc(sizeof(HASHMAP(t)))
	Construct a new hashmap object.
void HASHMAP	free (HASHMAP(t) *hashmap)
	Free all memory used by the given hashmap.
void HASHMAP	put (HASHMAP(t) *hashmap, K key, V value)
	Associate a value with the given key.
V HASHMAP	get (HASHMAP(t) *hashmap, K key)
	Get the value associated with the given key. Precondition: The key must be present in the map.
	assert (address >=hashmap->entries)
	assert (address< hashmap->entries+hashmap->capacity)
	while ((address->key !=hashmap->nothing) &(address->key !=key)) address++
	if (address==upper_limit)
	assert (address->key==key||address->key==hashmap->nothing)
	if (!entries) exit(1)
	for (size_t i=0;i< capacity+1;i++)

Variables
K	nothing
static K	key
return	address
ret	entries = entries
ret	capacity = capacity
ret	num_entries = 0
return	ret

Macro Definition Documentation

HASH_OF

#define HASH_OF

(

key

)

(size_t) key

HASHMAP

#define HASHMAP

(

token

)

hashmap##_##token

K

#define K   void*

Defines a generic, non-resizing hashmap data type.

Author

Peter Donovan (peter.nosp@m.dono.nosp@m.van@b.nosp@m.erke.nosp@m.ley.e.nosp@m.du)

Hashmaps are defined by redefining K, V, HASH_OF, and HASHMAP, and including this file. A default hashmap type is defined here. See pointer_hashmap.h for an example of a hashmap declaration.

• K and V must be the types of keys and values of the hashmap, respectively.
• HASH_OF must be the hash of a key.
• HASHMAP must be a function-like macro that prefixes tokens with the name of the hashmap. For example, the name of the hashmap data type is given by evaluation of the macro HASHMAP(t) so that it is "t" prefixed with the name of the hashmap. The function names associated with the data type are similar.

V

#define V   void*

Function Documentation

assert() [1/3]

assert

(

address >=hashmap->

entries

)

assert() [2/3]

assert

(

address->

key = =key||address->key==hashmap->nothing

)

assert() [3/3]

assert

(

address< hashmap->entries+hashmap->

capacity

)

for()

for

(

)

free()

void HASHMAP free

(

HASHMAP(t) *

hashmap

)

Free all memory used by the given hashmap.

get()

V HASHMAP get	(	HASHMAP(t) *	hashmap,
		K	key )

Get the value associated with the given key. Precondition: The key must be present in the map.

HASHMAP() [1/2]

HASHMAP

(

entry_t

)

= hashmap->entries + hashmap->capacity

Return the actual address of the hashmap entry corresponding to key, or the address of the closest empty entry if no such entry exists.

Parameters

key	The key from which to begin a search.
desired	The key that the desired returnable entry should have.

HASHMAP() [2/2]

HASHMAP ( t ) = (HASHMAP(t)*)malloc(sizeof(HASHMAP(t)))

new

Construct a new hashmap object.

Parameters

capacity	A number that is much larger than the maximum number of items that this hashmap will contain. Insufficient surplus capacity will cause poor performance.
nothing	A key that is guaranteed never to be used.

if() [1/2]

if

(

!

entries

)

if() [2/2]

if

(

address

= = upper_limit

)

put()

void HASHMAP put	(	HASHMAP(t) *	hashmap,
		K	key,
		V	value )

Associate a value with the given key.

while()

while

(

(address->key !=hashmap->nothing) &(address->key !=key)

)

Variable Documentation

address

return address

capacity

ret capacity = capacity

entries

ret entries = entries

key

static K key

Initial value:

{
  HASHMAP(entry_t)* address = hashmap->entries + (HASH_OF(key) % hashmap->capacity)

nothing

ret nothing

Initial value:

{
  HASHMAP(entry_t)* entries = (HASHMAP(entry_t)*)malloc((capacity + 1) * sizeof(HASHMAP(entry_t)))

num_entries

ret num_entries = 0

ret

return ret