cucon/ucmap.h: Constructive Maps from Unsigned Integers to Pointers
[Associative Containers (trees, maps, sets)]

Data Structures
struct	cucon_ucmap
Defines
#define	cucon_ucmap_int_none   INT_MIN
Functions
cucon_ucmap_t	cucon_ucmap_empty ()
cu_bool_t	cucon_ucmap_is_empty (cucon_ucmap_t map)
cucon_ucmap_t	cucon_ucmap_singleton (uintptr_t key, uintptr_t val)
cucon_ucmap_t	cucon_ucmap_singleton_ptr (uintptr_t key, void *val)
cu_bool_t	cucon_ucmap_is_singleton (cucon_ucmap_t map)
cucon_ucmap_t	cucon_ucmap_insert (cucon_ucmap_t, uintptr_t, uintptr_t)
cucon_ucmap_t	cucon_ucmap_insert_ptr (cucon_ucmap_t map, uintptr_t key, void *val)
cucon_ucmap_t	cucon_ucmap_insert_int (cucon_ucmap_t map, uintptr_t key, int val)
cucon_ucmap_t	cucon_ucmap_erase (cucon_ucmap_t map, uintptr_t key)
cu_bool_t	cucon_ucmap_contains (cucon_ucmap_t map, uintptr_t key)
cu_bool_t	cucon_ucmap_find (cucon_ucmap_t map, uintptr_t key, uintptr_t *v_out)
void *	cucon_ucmap_find_ptr (cucon_ucmap_t map, uintptr_t key)
int	cucon_ucmap_find_int (cucon_ucmap_t map, uintptr_t key)
size_t	cucon_ucmap_card (cucon_ucmap_t map)
cu_bool_t	cucon_ucmap_iterA (cu_clop(f, cu_bool_t, uintptr_t, uintptr_t), cucon_ucmap_t M)
cu_bool_t	cucon_ucmap_iterA_clipped (cu_clop(f, cu_bool_t, uintptr_t, uintptr_t), cucon_ucmap_t M, uintptr_t k_min, uintptr_t k_max)
void	cucon_ucmap_iter_ptr (cucon_ucmap_t M, cu_clop(f, void, uintptr_t, void *))
void	cucon_ucmap_iter_int (cucon_ucmap_t M, cu_clop(f, void, uintptr_t, int))
cu_bool_t	cucon_ucmap_conj_ptr (cucon_ucmap_t map, cu_clop(f, cu_bool_t, uintptr_t, void *))
cu_bool_t	cucon_ucmap_conj_int (cucon_ucmap_t map, cu_clop(cb, cu_bool_t, uintptr_t, int))
cucon_ucmap_t	cucon_ucmap_left_union (cucon_ucmap_t M0, cucon_ucmap_t M1)
uintptr_t	cucon_ucmap_min_ukey (cucon_ucmap_t map)
uintptr_t	cucon_ucmap_max_ukey (cucon_ucmap_t map)
cucon_ucmap_t	cucon_ucmap_uclip (cucon_ucmap_t map, uintptr_t k_min, uintptr_t k_max)
cucon_ucmap_t	cucon_ucmap_clip (cucon_ucmap_t map, uintptr_t k_min, uintptr_t k_max)
cu_bool_t	cucon_ucmap_eq (cucon_ucmap_t map0, cucon_ucmap_t map1)
cu_bool_t	cucon_ucmap_eq_ptr (cu_clop(f, cu_bool_t, void const *, void const *), cucon_ucmap_t map0, cucon_ucmap_t map1)
int	cucon_ucmap_cmp (cucon_ucmap_t map0, cucon_ucmap_t map1)
int	cucon_ucmap_cmp_ptr (cu_clop(f, int, void const *, void const *), cucon_ucmap_t map0, cucon_ucmap_t map1)
void	cucon_ucmap_dump (cucon_ucmap_t map, FILE *out)

---

Detailed Description

The following implements maps from integers to pointers, represented as binary trees with a structure based on the bit-pattern of the integer keys. The implementation is more compact than a trie due to the omission of single-choice branches. Some key features are

• O(1) copy since modifications are non-destructive.
• O(1) equality and arbitrary ordering due to hash-consing.
• Search and insert complexity ranges from O(log n) on average for containers of n random numbers, to O(n) for some pathological cases of containers with n powers of two. The pathological cases are limited by the range of integers, e.g. n ≤ 32 for 32 bit integers.

See also:

cucon/ucset.h: A wrapper specialising to set.

cucon/pcmap.h: A wrapper specialising to pointer keys.

cucon/umap.h: Hash maps which are more efficient for uses which do not require constructive updates.

---

Function Documentation

size_t cucon_ucmap_card

(

cucon_ucmap_t

map

)

Returns the number of elements in map.

int cucon_ucmap_cmp	(	cucon_ucmap_t	map0,
		cucon_ucmap_t	map1
	)

Return -1, 0, or 1 when map0 is less, equal, or greater than map1, where the value slots are compared as integers or by pointer equality.

int cucon_ucmap_cmp_ptr	(	cu_clop(f, int, void const *, void const *)	,
		cucon_ucmap_t	map0,
		cucon_ucmap_t	map1
	)

Return -1, 0, or 1 when map0 is less, equal, or greater than map1, where the value solts are compared according to f.

Precondition:

f must return 0 on equal pointers.

cu_bool_t cucon_ucmap_conj_int	(	cucon_ucmap_t	map,
		cu_clop(cb, cu_bool_t, uintptr_t, int)
	)

Sequential conjunction over mappings in order of increasing keys.

cu_bool_t cucon_ucmap_conj_ptr	(	cucon_ucmap_t	map,
		cu_clop(f, cu_bool_t, uintptr_t, void *)
	)

Sequential conjunction over mappings in order of increasing keys.

cu_bool_t cucon_ucmap_contains	(	cucon_ucmap_t	map,
		uintptr_t	key
	)

True iff map has a mapping from key.

void cucon_ucmap_dump	(	cucon_ucmap_t	map,
		FILE *	out
	)

Debug dump of map.

cucon_ucmap_t cucon_ucmap_empty

(

)

The empty map.

cu_bool_t cucon_ucmap_eq	(	cucon_ucmap_t	map0,
		cucon_ucmap_t	map1
	)

True iff map0 and map1 are equal, where values are compared as integers or by pointer comparison.

cu_bool_t cucon_ucmap_eq_ptr	(	cu_clop(f, cu_bool_t, void const *, void const *)	,
		cucon_ucmap_t	map0,
		cucon_ucmap_t	map1
	)

True iff map0 and map1 are equal, where f compares the values.

Precondition:

f must return true on equal pointers.

cucon_ucmap_t cucon_ucmap_erase	(	cucon_ucmap_t	map,
		uintptr_t	key
	)

If map has a mapping from key, returns the result of erasing it, otherwise returns map.

cu_bool_t cucon_ucmap_find	(	cucon_ucmap_t	map,
		uintptr_t	key,
		uintptr_t *	v_out
	)

If key is found in map, assign its value to v_out and return true, else return false.

int cucon_ucmap_find_int	(	cucon_ucmap_t	map,
		uintptr_t	key
	)

The mapping for key in map, or cucon_ucmap_int_none if not found.

void* cucon_ucmap_find_ptr	(	cucon_ucmap_t	map,
		uintptr_t	key
	)

The mapping for key in map or NULL if none.

cucon_ucmap_t cucon_ucmap_insert	(	cucon_ucmap_t	,
		uintptr_t	,
		uintptr_t
	)

Return a map which agrees with map everywhere, except that key maps to val.

cucon_ucmap_t cucon_ucmap_insert_int	(	cucon_ucmap_t	map,
		uintptr_t	key,
		int	val
	)

Return a map which agrees with map everywhere, except that key maps to val.

cucon_ucmap_t cucon_ucmap_insert_ptr	(	cucon_ucmap_t	map,
		uintptr_t	key,
		void *	val
	)

Return a map which agrees with map everywhere, except that key maps to val.

cu_bool_t cucon_ucmap_is_empty

(

cucon_ucmap_t

map

)

True iff map is the empty map.

cu_bool_t cucon_ucmap_is_singleton

(

cucon_ucmap_t

map

)

True iff the domain of map is a singleton.

void cucon_ucmap_iter_int	(	cucon_ucmap_t	M,
		cu_clop(f, void, uintptr_t, int)
	)

Call f for each key and value pair in M, assuming values are integers.

void cucon_ucmap_iter_ptr	(	cucon_ucmap_t	M,
		cu_clop(f, void, uintptr_t, void *)
	)

Call f for each key and value pair in M, assuming values are pointers.

cu_bool_t cucon_ucmap_iterA	(	cu_clop(f, cu_bool_t, uintptr_t, uintptr_t)	,
		cucon_ucmap_t	M
	)

Call f for each key and value pair in M.

cucon_ucmap_t cucon_ucmap_left_union	(	cucon_ucmap_t	M0,
		cucon_ucmap_t	M1
	)

Return a map with co-range equal to the union of the co-ranges of M0 and M1, and the mappings agree with M0 on its co-range and with M1 elsewhere.

uintptr_t cucon_ucmap_max_ukey

(

cucon_ucmap_t

map

)

The maximum key in map when keys are interpreted as unsigned.

uintptr_t cucon_ucmap_min_ukey

(

cucon_ucmap_t

map

)

The minimum key in map when keys are interpreted as unsigned.

cucon_ucmap_t cucon_ucmap_singleton	(	uintptr_t	key,
		uintptr_t	val
	)

Return the map {key ↦ val}.

cucon_ucmap_t cucon_ucmap_singleton_ptr	(	uintptr_t	key,
		void *	val
	)

Return the map {key ↦ val}.