This is usual algorithm, but without back-links on the nodes to allow purely constructive updates if desired. The comparison predicate is passed explicitely to functions which use them. This makes it possible to define both sets and maps in terms of these trees, and it is also a way to allow keys to be stored directly on the slots.
| typedef __see_below__ cucon_rbnode_copier_t |
A node copier closure.
typedef cu_clop(cucon_rbnode_copier_t, cucon_rbnode_t, cucon_rbnode_t)
| cucon_rbnode_t cucon_rbnode_left | ( | cucon_rbnode_t | node | ) |
The left subtree of node.
| void* cucon_rbnode_mem | ( | cucon_rbnode_t | node | ) |
Return a pointer to the slot of node.
| cucon_rbnode_t cucon_rbnode_new_copy | ( | cucon_rbnode_t | src, | |
| size_t | slot_size | |||
| ) |
Create a copy of src, but with an uninitialised value slot of slot_size bytes.
| void* cucon_rbnode_ptr | ( | cucon_rbnode_t | node | ) |
Retrun the slot of node assuming it is a pointer.
| cucon_rbnode_t cucon_rbnode_right | ( | cucon_rbnode_t | node | ) |
The right subtree of node.
| void cucon_rbtree_cct_copy_ctive | ( | cucon_rbtree_t | tree, | |
| cucon_rbtree_t | src | |||
| ) |
Construct a clone of src. Cloned trees must be modified with _ctive functions only, to avoid interference.
| void cucon_rbtree_cct_copy_node | ( | cucon_rbtree_t | dst, | |
| cucon_rbtree_t | src, | |||
| cucon_rbnode_copier_t | node_new_copy | |||
| ) |
Make dst a deep copy of src, where node_new_copy(node) shall return a new copy of node, using cucon_rbnode_new_copy and filling in the slot.
| void cucon_rbtree_cct_copy_ptr | ( | cucon_rbtree_t | dst, | |
| cucon_rbtree_t | src | |||
| ) |
Construct dst as a deep copy of src, assuming the slots are pointers.
| cu_bool_t cucon_rbtree_cinsert1m_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp1, int, void *) | , | |||
| cucon_rbnode_copier_t | node_new_copy, | |||
| size_t | slot_size, | |||
| cu_ptr_ptr_t | slot | |||
| ) |
A contructive version of cucon_rbtree_insert1m_mem.
| void cucon_rbtree_cmerge2p | ( | cucon_rbtree_t | dst, | |
| cucon_rbtree_t | src, | |||
| cu_clop(cmp, int, void *, void *) | ||||
| ) |
Constructively insert all elements of src into dst, assuming slots are pointers.
| cu_bool_t cucon_rbtree_conj_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, cu_bool_t, void *value) | ||||
| ) |
Applies cb on each value of tree in order, exiting immediately with false as soon as cb returns false, otherwise returns true.
| cu_bool_t cucon_rbtree_conj_ptr | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, cu_bool_t, void *value) | ||||
| ) |
Applies cb on each pointer stored in the value slots of tree in order, exiting immediately with false as soon as cb returns false, otherwise returns true.
| void cucon_rbtree_dump_as_graphviz | ( | cucon_rbtree_t | tree, | |
| cu_clop(print_label, void, void *, FILE *) | , | |||
| FILE * | out | |||
| ) |
Debug dump of tree an graphviz format.
| void* cucon_rbtree_erase1m | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp1, int, void *) | ||||
| ) |
Erase from tree the element which compares 0 according to cmp1 and return it's slot, or return NULL if not found.
| cucon_rbnode_t cucon_rbtree_erase2p | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp2, int, void *, void *) | , | |||
| void * | key | |||
| ) |
This function applies when slots of tree start with pointers to their keys. If tree contains a node with a key equal to key according to cmp2, then erase it from tree and return it, else return NULL.
| void* cucon_rbtree_find1m_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp1, int, void *) | ||||
| ) |
Return a pointer to the slot of the node where cmp1 returns 0, or NULL if not found.
| cucon_rbnode_t cucon_rbtree_find2p_node | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp2, int, void *, void *) | , | |||
| void * | key | |||
| ) |
This function applies when slots of tree start with pointers to their keys. Return the node from tree with a key equal to key according to cmp2, or NULL if none.
| void* cucon_rbtree_find2p_ptr | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp2, int, void *, void *) | , | |||
| void * | key | |||
| ) |
Return the slot, assuming it is a pointer, of the node where cmp2 returns 0, or NULL if not found.
| void cucon_rbtree_init | ( | cucon_rbtree_t | tree | ) |
Construct an empty tree.
| cu_bool_t cucon_rbtree_insert1m_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp1, int, void *other_key) | , | |||
| size_t | slot_size, | |||
| cu_ptr_ptr_t | slot | |||
| ) |
Insert into tree an element which compares according to cmp1 where a negative, zero and positive return value means than the key is less than, equal to and greater than other_key, respectively. If cmp1 maps an existing element to 0, then *slot is set to point to its value slot, and false is returned. Otherwise, a new node is created with value of slot_size bytes at an address stored in *slot and true is returned. In the latter case, you should construct an object at *slot for which cmp1 gives 0.
| cu_bool_t cucon_rbtree_insert2p_node | ( | cucon_rbtree_t | tree, | |
| cu_clop(cmp2, int, void *, void *) | , | |||
| void * | key, | |||
| size_t | node_size, | |||
| size_t | node_offset, | |||
| cucon_rbnode_t * | node_out | |||
| ) |
Insert key into tree if not present, assuming the keys are stored in a leading pointer-valued field of the slots. Nodes are allocated with node_size bytes with cucon_rbnode_t at offset node_offset. An allocated or present node with key equal to key is stored at *node_out. If insertion was done, returns true, in which case only the key part of the returned slot is initialised.
| cu_bool_t cucon_rbtree_insert_imem_ctive | ( | cucon_rbtree_t | tree, | |
| size_t | key_size, | |||
| void * | key, | |||
| size_t | slot_size, | |||
| cu_ptr_ptr_t | slot_o | |||
| ) |
If tree has a mapping for key set *slot_o to its mapping and return false, else create a new mapping with key initialised to key, set *slot_o to its slot, and return true.
memcpy, and starts with a key_size bytes key which can be compared with memcmp. (“imem” for “immediate memory”.) | cu_bool_t cucon_rbtree_is_empty | ( | cucon_rbtree_t | tree | ) |
True iff tree is empty.
| void cucon_rbtree_iter_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, void, void *val) | ||||
| ) |
Applies cb to the pointers to slots of tree in order.
| void cucon_rbtree_iter_ptr | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, void, void *val) | ||||
| ) |
Applies cb to pointers stored in the slots of tree in order.
| void cucon_rbtree_merge2p | ( | cucon_rbtree_t | dst, | |
| cucon_rbtree_t | src, | |||
| cu_clop(cmp, int, void *, void *) | ||||
| ) |
Insert all elements of src into dst, assuming slots are pointers.
| cucon_rbtree_t cucon_rbtree_new | ( | void | ) |
Return an empty tree.
| cucon_rbtree_t cucon_rbtree_new_copy_ctive | ( | cucon_rbtree_t | src | ) |
Return a clone of src. Cloned trees must be modified with _ctive functions only, to avoid interference.
| cucon_rbtree_t cucon_rbtree_new_copy_node | ( | cucon_rbtree_t | src, | |
| cucon_rbnode_copier_t | node_new_copy | |||
| ) |
Return a deep copy of src, given that node_new_copy(node) returns a copy of node, using cucon_rbnode_new_copy and filling in the slot.
| cucon_rbtree_t cucon_rbtree_new_copy_ptr | ( | cucon_rbtree_t | src | ) |
Return a deep copy of src, assuming the slots are pointers.
| cu_bool_t cucon_rbtree_rev_conj_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, cu_bool_t, void *value) | ||||
| ) |
Applies cb on each value of tree in reverse order, exiting immediately with false as soon as cb returns false, otherwise returns true.
| cu_bool_t cucon_rbtree_rev_conj_ptr | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, cu_bool_t, void *value) | ||||
| ) |
Applies cb on each pointer stored in the value slots of tree in reverse order, exiting immediately with false as soon as cb returns false, otherwise returns true.
| void cucon_rbtree_rev_iter_mem | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, void, void *) | ||||
| ) |
Applies cb to the pointers to slots of tree in reverse order.
| void cucon_rbtree_rev_iter_ptr | ( | cucon_rbtree_t | tree, | |
| cu_clop(cb, void, void *) | ||||
| ) |
Applies cb to pointers stored in the slots of tree in reverse order.
| cucon_rbnode_t cucon_rbtree_root | ( | cucon_rbtree_t | tree | ) |
The root node of tree.
| size_t cucon_rbtree_size | ( | cucon_rbtree_t | tree | ) |
Return number of elements in the tree.