cucon/pmap.h: Pointer-Keyed Hash Map
[Associative Containers (trees, maps, sets)]

Data Structures
struct	cucon_pmap
struct	cucon_pmap_node
Defines
#define	cucon_pmap_it_eq(it0, it1)   ((it0.node) == (it1.node))
#define	cucon_pmap_it_key(it)   ((void*)(it).node->key)
#define	cucon_pmap_it_value_mem(it)   ((void*)CU_ALIGNED_PTR_END((it).node))
#define	cucon_pmap_it_value_ptr(it)   (*(void**)CU_ALIGNED_PTR_END((it).node))
#define	cucon_pmap_cct   cucon_pmap_init
#define	cucon_pmap_cct_copy_void   cucon_pmap_init_copy_void
#define	cucon_pmap_cct_copy_mem   cucon_pmap_init_copy_mem
#define	cucon_pmap_cct_copy_mem_ctor   cucon_pmap_init_copy_mem_ctor
#define	cucon_pmap_cct_copy_node   cucon_pmap_init_copy_node
Typedefs
typedef struct cucon_pmap_node *	cucon_pmap_node_t
typedef cucon_umap_it_t	cucon_pmap_it_t
Functions
void *	cucon_pmap_node_key (cucon_pmap_node_t node)
void	cucon_pmap_init (cucon_pmap_t map)
cucon_pmap_t	cucon_pmap_new (void)
void	cucon_pmap_init_copy_void (cucon_pmap_t dst, cucon_pmap_t src)
cucon_pmap_t	cucon_pmap_new_copy_void (cucon_pmap_t src)
void	cucon_pmap_init_copy_mem (cucon_pmap_t dst, cucon_pmap_t src, size_t slot_size)
cucon_pmap_t	cucon_pmap_new_copy_mem (cucon_pmap_t src, size_t slot_size)
void	cucon_pmap_init_copy_mem_ctor (cucon_pmap_t dst, cucon_pmap_t src, size_t slot_size, cu_clop(value_init_copy, void, void *dst_slot, void *src_slot, uintptr_t key))
void	cucon_pmap_init_copy_node (cucon_pmap_t dst, cucon_pmap_t src, cu_clop(node_alloc_copy, cucon_pmap_node_t, void *, uintptr_t))
cucon_pmap_node_t	cucon_pmap_node_alloc (size_t slot_size)
void *	cucon_pmap_node_get_mem (cucon_pmap_node_t node)
void	cucon_pmap_swap (cucon_pmap_t map0, cucon_pmap_t map1)
cu_bool_t	cucon_pmap_insert_init_node (cucon_pmap_t map, cucon_pmap_node_t node)
cu_bool_t	cucon_pmap_insert_new_node (cucon_pmap_t map, void const *key, size_t node_size, cu_ptr_ptr_t node_out)
cu_bool_t	cucon_pmap_insert_mem (cucon_pmap_t map, void const *key, size_t slot_size, cu_ptr_ptr_t slot)
cu_bool_t	cucon_pmap_insert_void (cucon_pmap_t map, void const *key)
cu_bool_t	cucon_pmap_insert_ptr (cucon_pmap_t map, void const *key, void *ptr)
cu_bool_t	cucon_pmap_insert_int (cucon_pmap_t map, void const *key, int val)
cu_bool_t	cucon_pmap_insert_general (cucon_pmap_t map, void const *key, cu_clop0(alloc_node, cucon_pmap_node_t), cucon_pmap_node_t *node_out)
void *	cucon_pmap_replace_ptr (cucon_pmap_t map, void const *key, void *ptr)
int	cucon_pmap_replace_int (cucon_pmap_t map, void const *key, int val)
cu_bool_t	cucon_pmap_erase (cucon_pmap_t map, void const *key)
void *	cucon_pmap_erase_ptr (cucon_pmap_t map, void const *key)
int	cucon_pmap_erase_int (cucon_pmap_t map, void const *key)
cu_bool_t	cucon_pmap_erase_keep_cap (cucon_pmap_t map, void const *key)
cucon_pmap_node_t	cucon_pmap_pop_any_node (cucon_pmap_t map)
void const *	cucon_pmap_pop_any_key (cucon_pmap_t map)
void	cucon_pmap_update_cap (cucon_pmap_t map)
cucon_pmap_node_t	cucon_pmap_find_node (cucon_pmap_t map, void const *key)
void *	cucon_pmap_find_mem (cucon_pmap_t map, void const *key)
void *	cucon_pmap_find_ptr (cucon_pmap_t map, void const *key)
int	cucon_pmap_find_int (cucon_pmap_t map, void const *key)
cu_bool_t	cucon_pmap_find_void (cucon_pmap_t map, void const *key)
void	cucon_pmap_iter_mem (cucon_pmap_t map, cu_clop(cb, void, void const *key, void *value))
void	cucon_pmap_iter_ptr (cucon_pmap_t map, cu_clop(cb, void, void const *key, void *value))
cu_bool_t	cucon_pmap_conj_general (cucon_pmap_t map, size_t node_offset, cu_clop(cb, cu_bool_t, void const *, void *))
cu_bool_t	cucon_pmap_conj_mem (cucon_pmap_t map, cu_clop(cb, cu_bool_t, void const *, void *))
cu_bool_t	cucon_pmap_conj_ptr (cucon_pmap_t map, cu_clop(cb, cu_bool_t, void const *, void *))
void	cucon_pmap_iter_keys (cucon_pmap_t map, cu_clop(cb, void, void const *))
cu_bool_t	cucon_pmap_conj_keys (cucon_pmap_t map, cu_clop(cb, cu_bool_t, void const *))
cu_bool_t	cucon_pmap_conj_node (cucon_pmap_t map, cu_clop(cb, cu_bool_t, cucon_pmap_node_t node))
void	cucon_pmap_assign_isecn_union (cucon_pmap_t map0, cucon_pmap_t map1)
void	cucon_pmap_move_isecn (cucon_pmap_t dst, cucon_pmap_t src0, cucon_pmap_t src1)
void	cucon_pmap_assign_isecn (cucon_pmap_t dst, cucon_pmap_t src)
void	cucon_pmap_assign_union_void (cucon_pmap_t dst, cucon_pmap_t src)
void	cucon_pmap_dump_stats (cucon_pmap_t map, FILE *out)
size_t	cucon_pmap_size (cucon_pmap_t map)
cu_bool_t	cucon_pmap_is_empty (cucon_pmap_t map)
cu_bool_t	cucon_pmap_eq_keys (cucon_pmap_t map0, cucon_pmap_t map1)
cu_bool_t	cucon_pmap_eq_mem (cucon_pmap_t map0, cucon_pmap_t map1, size_t slot_size)
cu_bool_t	cucon_pmap_eq_ptr (cucon_pmap_t map0, cucon_pmap_t map1)
cu_hash_t	cucon_pmap_hash_keys (cucon_pmap_t map)
cu_hash_t	cucon_pmap_hash_mem (cucon_pmap_t map, size_t slot_size)
cu_hash_t	cucon_pmap_hash_ptr (cucon_pmap_t map)
cucon_pmap_it_t	cucon_pmap_begin (cucon_pmap_t map)
cucon_pmap_it_t	cucon_pmap_end (cucon_pmap_t map)
cu_bool_t	cucon_pmap_end_eq (cucon_pmap_t map, cucon_pmap_it_t it)
cucon_pmap_it_t	cucon_pmap_it_next (cucon_pmap_it_t it)
void	cucon_pmap_dump_idr_ptr (cucon_pmap_t map, FILE *out)

---

Detailed Description

This header implements hash maps keyed on pointers, and with arbitrary value slots. The slots are arbitrary sized memory which is stored on the nodes for best efficiency. The slots are accessed directly using the *_mem functions, whereas some specialised functions are provided for pointers and integers.

See also:

cucon/pset.h: Poiter-Keyed Sets

cucon/umap.h: Integer-Keyed Hash Map

---

Define Documentation

#define cucon_pmap_cct   cucon_pmap_init

Deprecated:

Use cucon_pmap_init.

#define cucon_pmap_cct_copy_mem   cucon_pmap_init_copy_mem

Deprecated:

Use cucon_pmap_init_copy_mem.

#define cucon_pmap_cct_copy_mem_ctor   cucon_pmap_init_copy_mem_ctor

Deprecated:

Use cucon_pmap_init_copy_mem_ctor.

#define cucon_pmap_cct_copy_node   cucon_pmap_init_copy_node

Deprecated:

Use cucon_pmap_init_copy_node.

#define cucon_pmap_cct_copy_void   cucon_pmap_init_copy_void

Deprecated:

Use cucon_pmap_init_copy_void.

---

Function Documentation

void cucon_pmap_assign_isecn	(	cucon_pmap_t	dst,
		cucon_pmap_t	src
	)

Assign to dst the intersection dst ∩ src, keeping the slots.

void cucon_pmap_assign_isecn_union	(	cucon_pmap_t	map0,
		cucon_pmap_t	map1
	)

Move all pairs of map0 with keys not in map1 to map1. This effectively assigns map0 ∩ map1 to map0 and map0 ∪ map1 to map1, where only keys are considered for the set operation tests.

void cucon_pmap_assign_union_void	(	cucon_pmap_t	dst,
		cucon_pmap_t	src
	)

Assign to dst the union of dst and src, with void slots for duplicated nodes.

cu_bool_t cucon_pmap_conj_keys	(	cucon_pmap_t	map,
		cu_clop(cb, cu_bool_t, void const *)
	)

Perform a sequential conjunction of cb over keys in map.

cu_bool_t cucon_pmap_conj_mem	(	cucon_pmap_t	map,
		cu_clop(cb, cu_bool_t, void const *, void *)
	)

Sequentially conjunct cb over (key, value) pairs in map.

cu_bool_t cucon_pmap_conj_node	(	cucon_pmap_t	map,
		cu_clop(cb, cu_bool_t, cucon_pmap_node_t node)
	)

Sequential conjunction of cb over nodes in map.

void cucon_pmap_dump_idr_ptr	(	cucon_pmap_t	map,
		FILE *	out
	)

Dump map to out assuming keys are cu_idr_t and slots are pointers.

void cucon_pmap_dump_stats	(	cucon_pmap_t	map,
		FILE *	out
	)

For profiling use.

cu_bool_t cucon_pmap_eq_keys	(	cucon_pmap_t	map0,
		cucon_pmap_t	map1
	)

True iff map0 and map1 contains the same sets of keys.

cu_bool_t cucon_pmap_eq_mem	(	cucon_pmap_t	map0,
		cucon_pmap_t	map1,
		size_t	slot_size
	)

True iff map0 and map1 are equal, assuming slot size is slot_size bytes and trivially comparable.

cu_bool_t cucon_pmap_eq_ptr	(	cucon_pmap_t	map0,
		cucon_pmap_t	map1
	)

True iff map0 and map1 are equal, assuming slots are pointers with pointer equality.

cu_bool_t cucon_pmap_erase	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, erase it and return true, else return false. To optimise for many deletions, use _keep_cap variants and call cucon_umap_update_cap once afterwards.

int cucon_pmap_erase_int	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, erase it and return the int value stored in the slot, else return * INT_MIN.

Precondition:

The slot of key, if present, must hold an int.

cu_bool_t cucon_pmap_erase_keep_cap	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, erase it and return true, else return false. To optimise for many deletions, use _keep_cap variants and call cucon_umap_update_cap once afterwards.

void* cucon_pmap_erase_ptr	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, erase it and return the pointer value stored in the slot, else return NULL.

Precondition:

The slot of key, if present, must hold a pointer.

int cucon_pmap_find_int	(	cucon_pmap_t	map,
		void const *	key
	)

If key is in map, return its mapping, else return INT_MIN.

Precondition:

The slot of key, if present, must hold an integer.

void* cucon_pmap_find_mem	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, return a pointer to the slot, else return NULL.

cucon_pmap_node_t cucon_pmap_find_node	(	cucon_pmap_t	map,
		void const *	key
	)

Returns the internal node of key, or NULL if none.

void* cucon_pmap_find_ptr	(	cucon_pmap_t	map,
		void const *	key
	)

If key has a mapping in map, interpret the slot as a pointer and return it, else return NULL.

cu_bool_t cucon_pmap_find_void	(	cucon_pmap_t	map,
		void const *	key
	)

True iff map contains key, ignoring the slot.

cu_hash_t cucon_pmap_hash_keys

(

cucon_pmap_t

map

)

Returns a hash of the keys in map.

cu_hash_t cucon_pmap_hash_mem	(	cucon_pmap_t	map,
		size_t	slot_size
	)

Returns a hash of the keys and slots of map, assuming slots are slot_size bytes long.

cu_hash_t cucon_pmap_hash_ptr

(

cucon_pmap_t

map

)

Returns a hash of the keys and slots of map, assuming the slots are pointers.

void cucon_pmap_init

(

cucon_pmap_t

map

)

Construct map as an empty property map.

void cucon_pmap_init_copy_mem	(	cucon_pmap_t	dst,
		cucon_pmap_t	src,
		size_t	slot_size
	)

Construct dst as a copy of src assuming slots are slot_size bytes which can be copied with memcpy.

void cucon_pmap_init_copy_mem_ctor	(	cucon_pmap_t	dst,
		cucon_pmap_t	src,
		size_t	slot_size,
		cu_clop(value_init_copy, void, void *dst_slot, void *src_slot,uintptr_t key)
	)

Copy src to dst, assuming all slots have the same size, where value_init_copy copies the value at src_slot to dst_slot.

void cucon_pmap_init_copy_node	(	cucon_pmap_t	dst,
		cucon_pmap_t	src,
		cu_clop(node_alloc_copy, cucon_pmap_node_t, void *, uintptr_t)
	)

Copy src to dst where src may have variable slot size. node_alloc_copy shall call cucon_umap_alloc to allocate some node, and construct a copy of src_slot at the location given by cucon_umap_node_get_mem(node).

void cucon_pmap_init_copy_void	(	cucon_pmap_t	dst,
		cucon_pmap_t	src
	)

Construct dst as a copy of src but dropping all value slots.

cu_bool_t cucon_pmap_insert_general	(	cucon_pmap_t	map,
		void const *	key,
		cu_clop0(alloc_node, cucon_pmap_node_t)	,
		cucon_pmap_node_t *	node_out
	)

If key is not in map, insert a node allocated with alloc_node mapped from key and return true, else return false. In any case *node_out is set to the node of key. This function lets you embed a node in your own data structures. alloc_node must use garbage collection.

cu_bool_t cucon_pmap_insert_init_node	(	cucon_pmap_t	map,
		cucon_pmap_node_t	node
	)

Insert node, which must be prepared with a key, into map.

cu_bool_t cucon_pmap_insert_int	(	cucon_pmap_t	map,
		void const *	key,
		int	val
	)

If key is not in map, map it to val and return true, else return false. If cucon_umap_find_int is used, then val should not be INT_MIN for the obvious reason. This is a shortcut equivalent to calling cucon_umap_insert_mem and initialising the slot with val.

cu_bool_t cucon_pmap_insert_mem	(	cucon_pmap_t	map,
		void const *	key,
		size_t	slot_size,
		cu_ptr_ptr_t	slot
	)

If key has a mapping in map, set *slot to a pointer to the value and return false, else create a new mapping to slot_size bytes of assigned to *slot and return true. This the generic insert which supports arbitrary value types.

cu_bool_t cucon_pmap_insert_new_node	(	cucon_pmap_t	map,
		void const *	key,
		size_t	node_size,
		cu_ptr_ptr_t	node_out
	)

If key is not in map, this call allocates a node of size node_size, initialises a cucon_pmap_node from offset 0 with the key key, inserts the node into map, assigns it to *node_out, and returns true. Otherwise, returns false.

cu_bool_t cucon_pmap_insert_ptr	(	cucon_pmap_t	map,
		void const *	key,
		void *	ptr
	)

Insert (key, ptr) into map if it does not exist. Returns true iff the insertion was done. This is a shortcut equivalent to calling cucon_umap_insert_mem and initialising the slot with ptr.

cu_bool_t cucon_pmap_insert_void	(	cucon_pmap_t	map,
		void const *	key
	)

Insert key into map unless it exists. Returns true iff the insertion was done.

cu_bool_t cucon_pmap_is_empty

(

cucon_pmap_t

map

)

True iff map is empty.

void cucon_pmap_iter_keys	(	cucon_pmap_t	map,
		cu_clop(cb, void, void const *)
	)

Call cb on each key in map.

void cucon_pmap_iter_mem	(	cucon_pmap_t	map,
		cu_clop(cb, void, void const *key, void *value)
	)

Call cb on each key-value pair in map.

void cucon_pmap_iter_ptr	(	cucon_pmap_t	map,
		cu_clop(cb, void, void const *key, void *value)
	)

Call cb on each key-value pair in map.

void cucon_pmap_move_isecn	(	cucon_pmap_t	dst,
		cucon_pmap_t	src0,
		cucon_pmap_t	src1
	)

For each element in src0 ∩ src1, move one pair to dst and delete the other. It is unspecified which of the values from the sources are moved. If dst already contains the key, the elemets of both sources are simply discarded.

cucon_pmap_t cucon_pmap_new

(

void

)

Return an empty property map.

cucon_pmap_t cucon_pmap_new_copy_mem	(	cucon_pmap_t	src,
		size_t	slot_size
	)

Return a copy of src assuming slots are slot_size bytes which can be copied with memcpy.

cucon_pmap_t cucon_pmap_new_copy_void

(

cucon_pmap_t

src

)

Return a copy of src after dropping all value slots.

void const* cucon_pmap_pop_any_key

(

cucon_pmap_t

map

)

As cucon_umap_pop_any_node, but return key instead of node.

cucon_pmap_node_t cucon_pmap_pop_any_node

(

cucon_pmap_t

map

)

Erase any element of map and return the erased node. This uses a random number generator to prevent compromising the average case structure of map.

int cucon_pmap_replace_int	(	cucon_pmap_t	map,
		void const *	key,
		int	val
	)

If key has a mapping in map, replace it with val and return the old mapping, else insert val and return INT_MIN. As a special case, if val is INT_MIN, erase the mapping of key and return the old value or INT_MIN of none.

Precondition:

The solt of key, if present, must hold an int.

void* cucon_pmap_replace_ptr	(	cucon_pmap_t	map,
		void const *	key,
		void *	ptr
	)

If key is bound in map, assume it is bound to a pointer, replace the poiter with ptr and return the old pointer, else bind key to ptr and return NULL.

Precondition:

The slot of key, if present, must hold a pointer.

size_t cucon_pmap_size

(

cucon_pmap_t

map

)

Return the number of elements in map.

void cucon_pmap_swap	(	cucon_pmap_t	map0,
		cucon_pmap_t	map1
	)

Swap the contents of map0 with map1.

void cucon_pmap_update_cap

(

cucon_pmap_t

map

)

Update capacity after _keep_cap calls.