3.1.7 Indirection

In some cases it is necessary to build a tree from the top down rather than from the bottom up, when it is not known in advance what’s on the bottom. Although the list type is a pointer itself, these situations call for a type of pointers to lists, which are declared as the branch type in ‘branches.h’. For example, if b is declared as a branch and l is declared as a list, it would be possible to write b = &l.

Facilities are also provided for maintaining queues of branches, which are declared as the branch_queue type. This type is a pointer to a structure with two fields, above and following, where above is a branch and following is a branch_queue.

These functions are used internally elsewhere in the library and might not be necessary for most client programs to use directly.

Function: void avm_initialize_branches ()

This must be done once before any of the other branch related functions is used, and creates some internal data structures. Results of the other functions are undefined if this one isn’t called first.

Function: void avm_count_branches ()

This function can be used at the end of a run to detect unreclaimed storage used for branches or branch queues. If any storage remains unreclaimed, a message about unreclaimed branches is written to standard error.

Function: void avm_anticipate (branch_queue *front, branch_queue *back, branch operand)

This function provides a simple queueing facility for branches. Similarly to the case with avm_enqueue, front and back should be initialized to NULL before the first call. Each call to this function will enqueue one item to the back, assuming enough memory is available, as the following example shows.

front = NULL; back = NULL; l = avm_join(NULL,NULL); anticipate(&front,&back,&(l->head)); anticipate(&front,&back,&(l->tail));

After the above code is executed, these postconditions will hold.

front->above == &(l->head) front->following->above == &(l->tail) front->following == back back->following == NULL

The name “anticipate” is used because ordinarily the queue contains positions in a tree to be filled in later. As usual, only unshared trees should be modified in place.

Function: void avm_recoverable_anticipate (branch_queue *front, branch_queue *back, branch operand, int *fault)

This function is similar to avm_anticipate, except that it will not exit with an error message in the event of an overflow error, but will simply set *fault to a non-zero value and return to the caller. If an overflow occurs, nothing about the queue is changed.

Function: void avm_enqueue_branch (branch_queue *front, branch_queue *back, int received_bit)

A slightly higher level interface to the avm_anticipate function is provided by this function, which is useful for building a tree from a string of input bits in a format similar to the one described in Concrete Syntax.

This function should be called the first time with front and back having been initialized to represent a queue containing a single branch pointing to a list known to the caller. The list itself need not be allocated or initialized. An easy way of doing so would be the following.

front = NULL; back = NULL; avm_anticipate(&front,&back,&my_list);

On each call to avm_enqueue_branch, the received_bit parameter is examined. If it is zero, nothing will be added to the queue, the list referenced by the front branch will be assigned NULL, and the front branch will be removed from the queue. If received_bit is a non-zero value, the list referenced by the front branch will be assigned to point to a newly created unshared list node, and two more branches will be appended to the queue. The first branch to be appended will point to the head of the newly created list node, and the second branch to be appended will point to the tail.

If the sequence of bits conforms to the required concrete syntax, this function can be called for each of them in turn, and at the end of the sequence, the queue will be empty and the list referenced by the initial branch (i.e., my_list) will be the one specified by the bit string. If the sequence of bits does not conform to the required concrete syntax, the error can be detected insofar as the emptying of the queue will not coincide exactly with the last bit.

The caller should check for the queue becoming prematurely empty due to syntax errors, because no message is reported by avm_enqueue_branch in that event, and subsequent attempts to enqueue anything are ignored. However, in the event of a memory overflow, an error message is reported and the process is terminated.

Function: void avm_recoverable_enqueue_branch (branch_queue *front, branch_queue *back, int received_bit, int *fault)

This function is similar to avm_enqueue_branch but will leave error handling to the caller in the event of insufficient memory to enqueue another branch. Instead of printing an error message and exiting, it will dispose of the queue, set the fault flag to a non-zero value, and return. Although the queue will be reclaimed, the lists referenced by the branches in it will persist. The list nodes themselves can be reclaimed by disposing of the list whose address was stored originally in the front branch.

Function: void avm_dispose_branch_queue (branch_queue front)

This function deallocates a branch queue by chasing the following fields in each one. It does nothing to the lists referenced by the branches in the queue.

Rather than using free directly, client programs should use this function for deallocating branch queues, because it allows better performance by interacting with a local internal cache of free memory, and because it performs necessary bookkeeping for avm_count_branches.

Function: void avm_dispose_branch (branch_queue old)

This disposes of a single branch queue node rather than a whole queue. Otherwise, the same comments as those above apply.

This document was generated on December 10, 2012 using texi2html 1.82.