3.1.5 Comparison

The file ‘compare.h’ contains a few function declarations pertaining to the computation of the comparison predicate described in Compare. Some of the work is done by static functions in ‘compare.c’ that are not recommended entry points to the library.

Function: void avm_initialize_compare ()

This function should be called once before the first call to avm_comparison, as it initializes some necessary internal data structures.

Function: void avm_count_compare ()

This function can be used to check for memory leaks, by detecting unreclaimed storage at the end of a run. The data structures relevant to comparison that could be reported as unreclaimed are known as “decision” nodes, but these should always be handled properly by the library without intervention. If avm_count_lists is also being used, the call to this function must precede it.

Function: list avm_comparison (list operand, int *fault)

This function takes a list operand representing a pair of trees and returns a list representing the logical value of their equality. If the operand is NULL, a message of invalid comparison is returned and the *fault is set to a non-zero value. If the head of the operand is unequal to the tail, a NULL value is returned. If they are equal, a list is returned whose head and tail are both NULL. The equality in question is structural rather than pointer equality.

The list operand to this function may be modified by this function, but not in a way that should make any difference to a client program. If two lists are found to be equal, or if even two sublists are found to be equal in the course of the comparison, one of them is deallocated and made to point to the other. This action saves memory and may make subsequent comparisons faster. However, it could disrupt client programs that happen to be holding stale list pointers.

As of avram version 0.6.0, a logical field called discontiguous has been added to the node record type declared in lists.h, which is checked by the comparison function. If a list node has its discontiguous field set to a non-zero value, and if it also has a non-null value field, then it won’t be deallocated in the course of comparison even if it is found to be equal to something else. This feature can be used by client modules to create lists in which value fields refer to data structures that are meant to exist independently of them. See ‘mpfr.c’ for an example.

This function is likely to have better performance and memory usage than a naive implementation of comparison, for the above reasons and also because of optimizations pertaining to comparison of lists representing characters. Moreover, it is not subject to stack overflow exceptions because it is not written in a recursive style.

Function: list avm_binary_comparison (list left_operand, list right_operand, int *fault);

This function is the same as avm_comparison except that it allows the left and right operands to be passed as separate lists rather than taking them from the head and the tail of a single list.

This document was generated on November 8, 2012 using texi2html 1.82.