This file implements a strict parital order (E, ≺), that is a relation ≺ (precedes) over elements of E where
E contains at least two elements, the bottom ⊥ and top ⊤ such that ∀(x ∈ E) ⊥ ≺ x ≺ ⊤. This implementation allows growing the partial order by inserting elements with variable sized value stots, and forcing constraints of the form x ≺ y.
Using pointer equality = over elements, we can define the relation ≼ (precedes or equal to) by ∀(x, y ∈ E) x ≼ y ⇔ x ≺ y ∨ x = y, which satisfies
This gives the parital order (E, ≼). However, constraints of the form x ≼ y can produce equality constraints due to the antisymmetry rule, so forcing such constraints is not possible in an implementation with trivial equality.
| cucon_po_t cucon_po_new | ( | void | ) | cucon_po_new_mem(0, 0) |
Return a partial order with only bottom and top elements.
| enum cucon_pocmp_t |
| cucon_poelt_t cucon_po_bot | ( | cucon_po_t | po | ) |
Return the bottom element of po.
| void cucon_po_cct | ( | cucon_po_t | po | ) |
Construct po as a partial order with only bottom and top elements.
| void cucon_po_cct_2elt_cct | ( | cucon_po_t | po, | |
| cucon_poelt_t | bot, | |||
| cucon_poelt_t | top | |||
| ) |
Construct po, bot and top such that po is a partial order with bottom element bot and top element top.
| void cucon_po_cct_mem | ( | cucon_po_t | po, | |
| size_t | size_bot, | |||
| size_t | size_top | |||
| ) |
Construct po as a partial order with only a bottom element with slot size size_bot and a top element with slot size size_top.
| void cucon_po_cct_ptr | ( | cucon_po_t | po, | |
| void * | bot, | |||
| void * | top | |||
| ) |
Construct po as a partial order with only a bottom element with its slot equal to bot and a top element with its slot equal to top.
| cu_bool_t cucon_po_conj_lspan | ( | cucon_po_t | po, | |
| cucon_pmap_t | S, | |||
| cu_clop(cb, cu_bool_t, cucon_poelt_t elt) | ||||
| ) |
Sequentially conjunct cb over the lower span of S given the ordering po.
| void cucon_po_connected_prune_to_max | ( | cucon_pmap_t | S, | |
| cucon_poelt_t | start | |||
| ) |
Remove from S the successors of start which are not maxima of S.
| void cucon_po_connected_prune_to_min | ( | cucon_pmap_t | S, | |
| cucon_poelt_t | start | |||
| ) |
Remove from S the predecessors of start which are not minima of S.
| cu_bool_t cucon_po_constrain_prec | ( | cucon_po_t | po, | |
| cucon_poelt_t | e0, | |||
| cucon_poelt_t | e1 | |||
| ) |
If e1 ≼ e0, return false, else force the constraint e0 ≺ e1 and return true.
| unsigned int cucon_po_depth | ( | cucon_po_t | po | ) |
Return the number of elements in the longest chain from cucon_po_bot(po) to cucon_po_top(po).
| cucon_pmap_t cucon_po_inf_of_list | ( | cucon_list_t | L | ) |
Return the set of infimums of the elements in L.
| void cucon_po_insert_cct | ( | cucon_po_t | po, | |
| cucon_poelt_t | elt | |||
| ) |
Construct elt, insert it into po such that it is only constrained with respect to the bottom and top elements.
| cucon_poelt_t cucon_po_insert_mem | ( | cucon_po_t | po, | |
| size_t | size | |||
| ) |
Return an element with size bytes slot, which is newly constructed and inserted into po, and constrained with respect to the bottom and top elements only.
| cucon_poelt_t cucon_po_insert_ptr | ( | cucon_po_t | po, | |
| void * | ptr | |||
| ) |
Return an element which is newly constructed with slot equal to ptr, inserted into po such that it is only constrained with respect to the bottom and top elements.
| cucon_po_ipred_it_t cucon_po_ipred_begin | ( | cucon_poelt_t | e | ) |
Return an iterator to the first element of the range of predecessors of e.
| cucon_po_ipred_it_t cucon_po_ipred_end | ( | cucon_poelt_t | e | ) |
Return an iterator past the last element of the range of predecessors if e.
| cucon_poelt_t cucon_po_ipred_it_get | ( | cucon_po_ipred_it_t | it | ) |
Return the element referred by it in a range of predecessors.
| cucon_po_ipred_it_t cucon_po_ipred_it_next | ( | cucon_po_ipred_it_t | it | ) |
Return the iterator next after it in a range of predecessors.
| cucon_po_isucc_it_t cucon_po_isucc_begin | ( | cucon_poelt_t | e | ) |
Return an iterator to the first element of the range of successors of e.
| cucon_po_isucc_it_t cucon_po_isucc_end | ( | cucon_poelt_t | e | ) |
Return an iterator past the last element of the range of successors of e.
| cucon_poelt_t cucon_po_isucc_it_get | ( | cucon_po_isucc_it_t | it | ) |
Return the element referred by it in a range of successors.
| cucon_po_isucc_it_t cucon_po_isucc_it_next | ( | cucon_po_isucc_it_t | it | ) |
Return the iterator next after it in a range of successors.
| void cucon_po_iter_closed_range | ( | cucon_poelt_t | min, | |
| cucon_poelt_t | max, | |||
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(e) for each e such that min ≼ e ≼ max.
| void cucon_po_iter_ipreds | ( | cucon_poelt_t | e, | |
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(x) for each immediate predecessor x of e.
| void cucon_po_iter_isuccs | ( | cucon_poelt_t | e, | |
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(x) for each immediate successor x of e.
| void cucon_po_iter_left_range | ( | cucon_poelt_t | min, | |
| cucon_poelt_t | above, | |||
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(e) for each e such that min ≼ e ≺ above.
| void cucon_po_iter_open_range | ( | cucon_poelt_t | below, | |
| cucon_poelt_t | above, | |||
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(e) for each e such that below ≺ e ≺ above.
| void cucon_po_iter_right_range | ( | cucon_poelt_t | below, | |
| cucon_poelt_t | max, | |||
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(e) for each e such that below ≺ e ≼ max'.
| cucon_pmap_t cucon_po_lspan | ( | cucon_poelt_t | max | ) |
Return the set of predecessors of max.
| void cucon_po_lspan_accum | ( | cucon_poelt_t | max, | |
| cucon_pmap_t | accum | |||
| ) |
Accumulate the lower span of max into accum.
| cucon_pmap_t cucon_po_lspan_isecn | ( | cucon_poelt_t | max, | |
| cucon_pmap_t | S | |||
| ) |
Return the set of x ∈ S such that x ≼ max.
| cucon_po_t cucon_po_new_mem | ( | size_t | size_bot, | |
| size_t | size_top | |||
| ) |
Return a partial order with only a bottom element with slot size size_bot and a top element with slot size size_top.
| cucon_po_t cucon_po_new_ptr | ( | void * | bot, | |
| void * | top | |||
| ) |
Return a partial order with only a bottom element with its slot equal to bot and a top element with its slot equal to top.
| cucon_pmap_t cucon_po_open_range | ( | cucon_poelt_t | min, | |
| cucon_poelt_t | max | |||
| ) |
Return the range (below, above).
| cu_bool_t cucon_po_open_range_accum | ( | cucon_poelt_t | below, | |
| cucon_poelt_t | above, | |||
| cucon_pmap_t | S | |||
| ) |
Accumulate range (below, above) into S and return true iff below ≺ above.
| cu_bool_t cucon_po_prec | ( | cucon_poelt_t | e0, | |
| cucon_poelt_t | e1 | |||
| ) |
True iff e0 ≺ e1.
| cu_bool_t cucon_po_preceq | ( | cucon_poelt_t | e0, | |
| cucon_poelt_t | e1 | |||
| ) |
True iff e0 ≼ e1.
| void cucon_po_print_gviz | ( | cucon_po_t | po, | |
| cu_clop(label, cu_str_t, cucon_poelt_t) | , | |||
| FILE * | out | |||
| ) |
Print po to out in graphviz format, with labels according to label.
| void cucon_po_range_and_bounds_of_fn | ( | cucon_poelt_t | bot, | |
| cucon_poelt_t | top, | |||
| cu_clop(cmp, cucon_pocmp_t, cucon_poelt_t) | , | |||
| cucon_pmap_t | range, | |||
| cucon_pmap_t | ipreds, | |||
| cucon_pmap_t | isuccs | |||
| ) |
Given search limits bot and top, and the predicate cmp which classifies elements by cucon_pocmp_eq, cucon_pocmp_prec, cucon_pocmp_succ, and cucon_pocmp_unord, in a way consistent with the ordering as if describing a virtual subrange of [bot, top], this function inserts the range into range, the immediate predecessors into ipreds and the immediate successors into isuccs. By consistent with the ordering it is meant that if e is classified as cucon_pocmp_eq, then all its successors must be classified as either cucon_pocmp_eq or cucon_pocmp_succ, etc. Note that need not return cucon_pocmp_eq on any existing element, but it must return cucon_pocmp_succ or cucon_pocmp_eq for bot and cocon_pocmp_prec or cucon_pocmp_eq for top.
| cucon_pmap_t cucon_po_sup_of_list | ( | cucon_list_t | L | ) |
Return the set of supremums of the elements in L.
| cucon_poelt_t cucon_po_top | ( | cucon_po_t | po | ) |
Return the top element of po.
| void cucon_po_topological_succs | ( | cucon_poelt_t | e, | |
| cu_clop(f, void, cucon_poelt_t) | ||||
| ) |
Call f(x) for x = e and each successor of e such when f(x) is called before f(y) iff x ≺ y.
| cucon_pmap_t cucon_po_uspan | ( | cucon_poelt_t | min | ) |
Return the set of successors of min.
| void cucon_po_uspan_accum | ( | cucon_poelt_t | min, | |
| cucon_pmap_t | accum | |||
| ) |
Accumulate the upper span of min into accum.
| cucon_pmap_t cucon_po_uspan_isecn | ( | cucon_poelt_t | min, | |
| cucon_pmap_t | S | |||
| ) |
Return the set of x ∈ S such that min ≼ x.
| void* cucon_poelt_get_mem | ( | cucon_poelt_t | elt | ) |
Return a pointer to the slot of elt.
| void* cucon_poelt_get_ptr | ( | cucon_poelt_t | elt | ) |
Assuming elt has a pointer slot, return the pointer.
| cu_bool_t cucon_poelt_has_single_ipred | ( | cucon_poelt_t | e | ) |
True iff e has a single predecessor.
| cu_bool_t cucon_poelt_has_single_isucc | ( | cucon_poelt_t | e | ) |
True iff e has a single successor.
| unsigned int cucon_poelt_level | ( | cucon_poelt_t | elt | ) |
Return the topological level of elt.
| cucon_poelt_t cucon_poelt_of_data | ( | void * | slot | ) |
Return the element with slot at slot.