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

Data Structures
struct	cucon_umap
struct	cucon_umap_node
struct	cucon_umap_it_t
Defines
#define	CUCON_UMAP_NODE_INIT(key)   { key }
#define	cucon_umap_node_alloc(slot_size)   cu_galloc(CU_ALIGNED_SIZEOF(struct cucon_umap_node) + slot_size)
#define	cucon_umap_node_get_mem(node)   CU_ALIGNED_MARG_END(cucon_umap_node_t, node)
#define	cucon_umap_it_eq(it0, it1)   ((it0.node) == (it1.node))
#define	cucon_umap_it_key(it)   ((it).node->key)
#define	cucon_umap_it_value_mem(it)   ((void*)CU_ALIGNED_PTR_END((it).node))
#define	cucon_umap_it_value_ptr(it)   (*(void**)CU_ALIGNED_PTR_END((it).node))
#define	cucon_umap_cct   cucon_umap_init
#define	cucon_umap_cct_copy_void   cucon_umap_init_copy_void
#define	cucon_umap_cct_copy_mem   cucon_umap_init_copy_mem
#define	cucon_umap_cct_copy_mem_ctor   cucon_umap_init_copy_mem_ctor
#define	cucon_umap_cct_copy_node   cucon_umap_init_copy_node
Typedefs
typedef struct cucon_umap_node *	cucon_umap_node_t
Functions
cu_uintptr_t	cucon_umap_node_key (cucon_umap_node_t node)
void	cucon_umap_init (cucon_umap_t map)
cucon_umap_t	cucon_umap_new (void)
void	cucon_umap_init_copy_void (cucon_umap_t dst, cucon_umap_t src)
cucon_umap_t	cucon_umap_new_copy_void (cucon_umap_t src)
void	cucon_umap_init_copy_mem (cucon_umap_t dst, cucon_umap_t src, size_t slot_size)
cucon_umap_t	cucon_umap_new_copy_mem (cucon_umap_t src, size_t slot_size)
void	cucon_umap_init_copy_mem_ctor (cucon_umap_t dst, cucon_umap_t src, size_t slot_size, cu_clop(value_init_copy, void, void *dst_slot, void *src_slot, uintptr_t key))
void	cucon_umap_init_copy_node (cucon_umap_t dst, cucon_umap_t src, cu_clop(node_alloc_copy, cucon_umap_node_t, void *src_slot, uintptr_t key))
void	cucon_umap_swap (cucon_umap_t map0, cucon_umap_t map1)
cu_bool_t	cucon_umap_insert_init_node (cucon_umap_t map, cucon_umap_node_t node)
cu_bool_t	cucon_umap_insert_new_node (cucon_umap_t map, uintptr_t key, size_t node_size, cu_ptr_ptr_t node_out)
cu_bool_t	cucon_umap_insert_mem (cucon_umap_t map, uintptr_t key, size_t slot_size, cu_ptr_ptr_t slot)
cu_bool_t	cucon_umap_insert_void (cucon_umap_t map, uintptr_t key)
cu_bool_t	cucon_umap_insert_ptr (cucon_umap_t map, uintptr_t key, void *ptr)
cu_bool_t	cucon_umap_insert_int (cucon_umap_t map, uintptr_t key, int val)
cu_bool_t	cucon_umap_insert_general (cucon_umap_t map, uintptr_t key, cu_clop0(alloc_node, cucon_umap_node_t), cucon_umap_node_t *node_out)
void *	cucon_umap_replace_ptr (cucon_umap_t map, uintptr_t key, void *ptr)
int	cucon_umap_replace_int (cucon_umap_t map, uintptr_t key, int val)
cu_bool_t	cucon_umap_erase (cucon_umap_t map, uintptr_t key)
void *	cucon_umap_erase_ptr (cucon_umap_t map, uintptr_t key)
int	cucon_umap_erase_int (cucon_umap_t map, uintptr_t key)
cu_bool_t	cucon_umap_erase_keep_cap (cucon_umap_t map, uintptr_t key)
cucon_umap_node_t	cucon_umap_pop_any_node (cucon_umap_t map)
uintptr_t	cucon_umap_pop_any_key (cucon_umap_t map)
void	cucon_umap_update_cap (cucon_umap_t map)
cucon_umap_node_t	cucon_umap_find_node (cucon_umap_t map, uintptr_t key)
void *	cucon_umap_find_mem (cucon_umap_t map, uintptr_t key)
void *	cucon_umap_find_ptr (cucon_umap_t map, uintptr_t key)
int	cucon_umap_find_int (cucon_umap_t map, uintptr_t key)
cu_bool_t	cucon_umap_find_void (cucon_umap_t map, uintptr_t key)
void	cucon_umap_iter_mem (cucon_umap_t map, cu_clop(cb, void, uintptr_t key, void *value))
cu_bool_t	cucon_umap_conj_general (cucon_umap_t map, size_t node_offset, cu_clop(cb, cu_bool_t, uintptr_t, void *))
cu_bool_t	cucon_umap_conj_mem (cucon_umap_t map, cu_clop(cb, cu_bool_t, uintptr_t, void *))
void	cucon_umap_iter_keys (cucon_umap_t map, cu_clop(cb, void, uintptr_t))
void	cucon_umap_iter_increasing_keys (cucon_umap_t map, cu_clop(cb, void, uintptr_t))
cu_bool_t	cucon_umap_conj_keys (cucon_umap_t map, cu_clop(cb, cu_bool_t, uintptr_t))
cu_bool_t	cucon_umap_conj_node (cucon_umap_t map, cu_clop(cb, cu_bool_t, cucon_umap_node_t node))
void	cucon_umap_assign_isecn_union (cucon_umap_t map0, cucon_umap_t map1)
void	cucon_umap_move_isecn (cucon_umap_t dst, cucon_umap_t src0, cucon_umap_t src1)
void	cucon_umap_assign_isecn (cucon_umap_t dst, cucon_umap_t src)
void	cucon_umap_assign_union_void (cucon_umap_t dst, cucon_umap_t src)
void	cucon_umap_dump_stats (cucon_umap_t map, FILE *out)
size_t	cucon_umap_size (cucon_umap_t map)
cu_bool_t	cucon_umap_is_empty (cucon_umap_t map)
cu_bool_t	cucon_umap_eq_keys (cucon_umap_t map0, cucon_umap_t map1)
cu_bool_t	cucon_umap_eq_mem (cucon_umap_t map0, cucon_umap_t map1, size_t slot_size)
cu_bool_t	cucon_umap_eq_ptr (cucon_umap_t map0, cucon_umap_t map1)
cu_hash_t	cucon_umap_hash_keys (cucon_umap_t map)
cu_hash_t	cucon_umap_hash_mem (cucon_umap_t map, size_t slot_size)
cu_hash_t	cucon_umap_hash_ptr (cucon_umap_t map)
void	cucon_umap_print_keys (cucon_umap_t map, FILE *out)
cucon_umap_it_t	cucon_umap_begin (cucon_umap_t map)
cucon_umap_it_t	cucon_umap_end (cucon_umap_t map)
cu_bool_t	cucon_umap_end_eq (cucon_umap_t map, cucon_umap_it_t it)
cucon_umap_it_t	cucon_umap_it_next (cucon_umap_it_t it)

---

Detailed Description

This header implements hash maps with uintptr_t keys and arbitrary value slots. The slots are stored on the nodes for maximum efficiency. You can still store and access arbitrary values using the *_mem functions, whereas some specialised functions are provided for pointers and integers.

See also:

cucon/uset.h: Integer-Keyed (Sparse) Sets

cucon/pmap.h: Pointer-Keyed Hash Map

---

Define Documentation

#define cucon_umap_cct   cucon_umap_init

Deprecated:

Use cucon_umap_init.

#define cucon_umap_cct_copy_mem   cucon_umap_init_copy_mem

Deprecated:

Use cucon_umap_init_copy_mem.

#define cucon_umap_cct_copy_mem_ctor   cucon_umap_init_copy_mem_ctor

Deprecated:

Use cucon_umap_init_copy_mem_ctor.

#define cucon_umap_cct_copy_node   cucon_umap_init_copy_node

Deprecated:

Use cucon_umap_init_copy_node.

#define cucon_umap_cct_copy_void   cucon_umap_init_copy_void

Deprecated:

Use cucon_umap_init_copy_void.

---

Function Documentation

void cucon_umap_assign_isecn	(	cucon_umap_t	dst,
		cucon_umap_t	src
	)

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

void cucon_umap_assign_isecn_union	(	cucon_umap_t	map0,
		cucon_umap_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_umap_assign_union_void	(	cucon_umap_t	dst,
		cucon_umap_t	src
	)

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

cu_bool_t cucon_umap_conj_keys	(	cucon_umap_t	map,
		cu_clop(cb, cu_bool_t, uintptr_t)
	)

Perform a sequantial conjunction of cb over keys in map.

cu_bool_t cucon_umap_conj_mem	(	cucon_umap_t	map,
		cu_clop(cb, cu_bool_t, uintptr_t, void *)
	)

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

cu_bool_t cucon_umap_conj_node	(	cucon_umap_t	map,
		cu_clop(cb, cu_bool_t, cucon_umap_node_t node)
	)

Sequential conjunction of cb over nodes in map.

void cucon_umap_dump_stats	(	cucon_umap_t	map,
		FILE *	out
	)

For profiling use.

cu_bool_t cucon_umap_eq_keys	(	cucon_umap_t	map0,
		cucon_umap_t	map1
	)

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

cu_bool_t cucon_umap_eq_mem	(	cucon_umap_t	map0,
		cucon_umap_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_umap_eq_ptr	(	cucon_umap_t	map0,
		cucon_umap_t	map1
	)

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

cu_bool_t cucon_umap_erase	(	cucon_umap_t	map,
		uintptr_t	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_umap_erase_int	(	cucon_umap_t	map,
		uintptr_t	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_umap_erase_keep_cap	(	cucon_umap_t	map,
		uintptr_t	key
	)

Same as cucon_umap_erase, except the capacity of map is kept.

void* cucon_umap_erase_ptr	(	cucon_umap_t	map,
		uintptr_t	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_umap_find_int	(	cucon_umap_t	map,
		uintptr_t	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_umap_find_mem	(	cucon_umap_t	map,
		uintptr_t	key
	)

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

cucon_umap_node_t cucon_umap_find_node	(	cucon_umap_t	map,
		uintptr_t	key
	)

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

void* cucon_umap_find_ptr	(	cucon_umap_t	map,
		uintptr_t	key
	)

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

cu_bool_t cucon_umap_find_void	(	cucon_umap_t	map,
		uintptr_t	key
	)

True iff map contains key, ignoring the slot.

cu_hash_t cucon_umap_hash_keys

(

cucon_umap_t

map

)

Returns a hash of the keys in map.

cu_hash_t cucon_umap_hash_mem	(	cucon_umap_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_umap_hash_ptr

(

cucon_umap_t

map

)

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

void cucon_umap_init

(

cucon_umap_t

map

)

Construct map as an empty property map.

void cucon_umap_init_copy_mem	(	cucon_umap_t	dst,
		cucon_umap_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_umap_init_copy_mem_ctor	(	cucon_umap_t	dst,
		cucon_umap_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_umap_init_copy_node	(	cucon_umap_t	dst,
		cucon_umap_t	src,
		cu_clop(node_alloc_copy, cucon_umap_node_t, void *src_slot, uintptr_t key)
	)

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_umap_init_copy_void	(	cucon_umap_t	dst,
		cucon_umap_t	src
	)

Return an empty property map with void * keys. Construct dst as a copy of src but dropping all value slots.

cu_bool_t cucon_umap_insert_general	(	cucon_umap_t	map,
		uintptr_t	key,
		cu_clop0(alloc_node, cucon_umap_node_t)	,
		cucon_umap_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_umap_insert_init_node	(	cucon_umap_t	map,
		cucon_umap_node_t	node
	)

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

cu_bool_t cucon_umap_insert_int	(	cucon_umap_t	map,
		uintptr_t	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_umap_insert_mem	(	cucon_umap_t	map,
		uintptr_t	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_umap_insert_new_node	(	cucon_umap_t	map,
		uintptr_t	key,
		size_t	node_size,
		cu_ptr_ptr_t	node_out
	)

If key is not in map, allocates a node of size node_size, initialises it the key key, inserts it, assigns it to *node_out, and return true. Otherwise, returns false. This works if the full node inherits cucon_umap_node at the top of the struct.

cu_bool_t cucon_umap_insert_ptr	(	cucon_umap_t	map,
		uintptr_t	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_umap_insert_void	(	cucon_umap_t	map,
		uintptr_t	key
	)

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

cu_bool_t cucon_umap_is_empty

(

cucon_umap_t

map

)

True iff map is empty.

void cucon_umap_iter_increasing_keys	(	cucon_umap_t	map,
		cu_clop(cb, void, uintptr_t)
	)

Call cb on each key of map in increasing order.

void cucon_umap_iter_keys	(	cucon_umap_t	map,
		cu_clop(cb, void, uintptr_t)
	)

Call cb on each key in map.

void cucon_umap_iter_mem	(	cucon_umap_t	map,
		cu_clop(cb, void, uintptr_t key, void *value)
	)

Call cb on each key-value pair in map.

void cucon_umap_move_isecn	(	cucon_umap_t	dst,
		cucon_umap_t	src0,
		cucon_umap_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_umap_t cucon_umap_new

(

void

)

Return an empty property map.

cucon_umap_t cucon_umap_new_copy_mem	(	cucon_umap_t	src,
		size_t	slot_size
	)

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

cucon_umap_t cucon_umap_new_copy_void

(

cucon_umap_t

src

)

Return a copy of src after dropping all value slots.

uintptr_t cucon_umap_pop_any_key

(

cucon_umap_t

map

)

As cucon_umap_pop_any_node, but return key instead of node.

cucon_umap_node_t cucon_umap_pop_any_node

(

cucon_umap_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.

void cucon_umap_print_keys	(	cucon_umap_t	map,
		FILE *	out
	)

Prints the keys of map to out in set notation.

int cucon_umap_replace_int	(	cucon_umap_t	map,
		uintptr_t	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_umap_replace_ptr	(	cucon_umap_t	map,
		uintptr_t	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_umap_size

(

cucon_umap_t

map

)

Return the number of elements in map.

void cucon_umap_swap	(	cucon_umap_t	map0,
		cucon_umap_t	map1
	)

Swap the contents of map0 with map1.

void cucon_umap_update_cap

(

cucon_umap_t

map

)

Update capacity after _keep_cap calls.