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.
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.
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.
This function provides a simple queueing facility for branches. Similarly to the case with
avm_enqueue
,front
andback
should be initialized toNULL
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 == NULLThe 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.
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.
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
andback
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 assignedNULL
, 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.
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.
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 foravm_count_branches
.