NAME

cru_order - comparison structure for the cru library

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_order_s
{
   cru_hash hash;
   cru_bpred equal;
} *cru_order;

DESCRIPTION

Applications communicate a concept of comparison between edges, vertices, or properties in a graph to cru library functions through this structure initialized accordingly to be used any time a library function needs to compare two user-defined entities. The predicate applies to two similarly typed operands, and the hash function takes an operand of the same type.

• The predicate is expected to return a non-zero value if and only if its operands are equal or equivalent according to a user-defined relationship, not necessarily pointer equality.
• The hash function is required to be consistent with the predicate in that any two equivalent operands have the same hash. Hash collisions are allowed and theoretically unavoidable but hash functions that rarefy them benefit performance.

ERRORS

The predicate is taken to model a relation that is algebraically reflexive, transitive, and symmetric, or in other words, an equivalence relation. Failure on the part of the application to satisfy these algebraic properties is an error and will lead to anomalous results. There is no way for cru to detect this error.

If a hash function is omitted and no default can be inferred as noted below, then an error of CRU_UNDHSH is reported by whatever API function is passed this structure. Similarly, if a required predicate is omitted, an error of CRU_UNDEQU is reported.

NOTES

The cru_order structure may be built into a cru_classifier structure, a cru_filter structure, or either of two fields in a cru_order_pair structure used for building a graph. The context determines the type of operands.

• In a cru_classifier, the order pertains to a pair of user-defined properties computed about vertices in a graph in the course of classification according to the cl_prop field of the same classifier.
• In a cru_filter, the order pertains to a pair of edge labels in the graph being filtered.
• In a cru_order_pair, the order pertains to either a pair of vertices or a pair of edge labels in the graph to be built depending on whether the cru_order structure is in the v_order or the e_order field, respectively.

Optimizing the hash function is more important than optimizing the predicate because the predicate is evaluated only in the ideally rare case of a hash collision.

Normally where it is possible for cru to infer by their lack of a destructor that the operands are scalar values, applications can omit either or both of the predicate and the hash function by making them NULL. Then cru infers a pointer equality relation and a built in hash function.

FILES

/usr/local/include/cru/function_types.h

/usr/local/include/cru/error_codes.h

/usr/local/include/cru/data_types.h

SEE ALSO

cru, cru_bop, cru_bpred, cru_builder, cru_built, cru_cbop, cru_classifier, cru_class_of, cru_class_size, cru_composed, cru_composer, cru_connect, cru_connector, cru_cqop, cru_crossed, cru_crosser, cru_ctop, cru_ctop_pair, cru_ctop_quad, cru_data_types, cru_deduplicated, cru_destructor, cru_destructor_pair, cru_edge_count, cru_fabricated, cru_fabricator, cru_filter, cru_filtered, cru_fold, cru_free_kill_switch, cru_free_later, cru_free_now, cru_free_partition, cru_function_types, cru_get, cru_hash, cru_induced, cru_inducer, cru_kernel, cru_kill, cru_killed, cru_mapreduced, cru_mapreducer, cru_merged, cru_merger, cru_mutated, cru_mutator, cru_new_kill_switch, cru_nop, cru_order_pair, cru_partition_of, cru_plan, cru_postponed, cru_postponer, cru_prop, cru_prop_pair, cru_pruner, cru_qop, cru_qpred, cru_set, cru_sig, cru_singleton, cru_split, cru_splitter, cru_spread, cru_strerror, cru_stretch, cru_stretched, cru_stretcher, cru_subconnector, cru_terminus_count, cru_top, cru_tpred, cru_united, cru_uop, cru_vertex_count, cru_zone

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru