3.1.1 Simple Operations

These functions are declared in the header file lists.h, which should be included in any C source file that uses them with a directive such as #include <avm/lists.h>. All of these functions except the first three have the potential cause a memory overflow. In that event, a brief message is written to standard error and the process is killed rather than returning to the caller. It is possible for client programs requiring more robust behavior to do their own error handling by using the alternative versions of these operations described in the next section.

Function: void avm_initialize_lists ()

The function avm_initialize_lists should be called before any of the other ones in this section is called, because it sets up some internal data structures. Otherwise, the behavior of the other functions is undefined.

Function: void avm_dispose (list front)

This function deallocates the memory associated with a given list, either by consigning it to a cache maintained internally by the library, or by the standard free function if the cache is full. Shared lists are taken into account and handled properly according to a reference counting scheme. Lists should be freed only by this function, not by using free directly.

Function: void avm_count_lists ()

If a client program aims to do its own storage reclamation, this function can be called optionally at the end of a run when it is believed that all lists have been freed. If any allocated lists remain at large, a warning will be printed to standard error. This function therefore provides a useful check for memory leaks. Overhead is small enough that it is not infeasible to leave this check in the production code.

Function: list avm_copied (list operand)

A copy of the argument list is returned by this function. The copy remains intact after the original is reclaimed. A typical use might be for retaining part of a list after the rest of it is no longer needed. In this example, a list x is traversed by a hypothetical visit function to each item, which is then immediately reclaimed.

while(x){ visit(x->head); old_x = x; x = avm_copied(x->tail); /* the right way */ avm_dispose(old_x); }

This example allows each item in the list to be visited even as previously visited items are reclaimed, because x is copied at each iteration. This example contrasts with the next one, which will probably cause a segmentation fault.

while(x){ visit(x->head); old_x = x; x = x->tail; /* the wrong way */ avm_dispose(old_x); }

In the second example, a reference is made to a part of a list which no longer exists because it has been deallocated.

In fact, the avm_copied function does nothing but increment a reference count, so it is a fast, constant time operation that requires no additional memory allocation. Semantically this action is equivalent to creating a fresh copy of the list, because all list operations in the library deal with reference counts properly.

Function: list avm_join (list left, list right)

This function takes a pair of lists to a list in which the left is the head and the right is the tail. It may need to use malloc to allocate additional memory. If there is insufficient memory, an error message is written to standard error and the program exits. When the list returned by avm_join is eventually deallocated, the lists from which it was built are taken with it and must not be referenced again. For example, the following code is an error.

z = avm_join(x,y); … avm_dispose(z); avm_print_list(x); /* error here */

To accomplish something similar to this without an error, a copy of x should be made, as in the next example.

z = avm_join(avm_copied(x),y); … avm_dispose(z); avm_print_list(x); /* original x still intact */

Function: void avm_enqueue (list *front, list *back, list operand)

A fast simple way of building a list head first is provided by the enqueue function. The front is a pointer to the beginning of the list being built, and the back is a pointer to the last item. The recommended way to use it would be something like this.

front = back = NULL; avm_enqueue(&front,&back,item); avm_enqueue(&front,&back,next_item); avm_enqueue(&front,&back,another_item); …

It might be more typical for the calls to avm_enqueue to appear within a loop. In any case, after the above code is executed, the following postconditions will hold.

front->head == item front->tail->head == next_item front->tail->tail->head == another_item back->head == another_item back->tail == NULL

The avm_enqueue function must never be used on a shared list, because it modifies its arguments in place. The only practical way to guarantee that a list is not shared is to initialize the front and back to NULL as shown before the first call to avm_enqueue, and to make no copies of front or back until after the last call to avm_enqueue.

Because a list built with avm_enqueue is not shared, it is one of the few instances of a list that can have something harmlessly appended to it in place. For example, if the next line of code were

back->tail = rest_of_list;

that would be acceptable assuming rest_of_list is not shared and does not conceal a dangling or cyclic reference, and if nothing further were enqueued.

The items that are enqueued into a list are not copied and will be deallocated when the list is deallocated, so they must not be referenced thereafter. A non-obvious violation of this convention is implicit in the following code.

… avm_enqueue(&front,&back,x->head); … avm_dispose(front); avm_print_list(x); /* error here */

This code might cause a segmentation fault because of the reference to x after its head has been deallocated. The following code is subject to the same problem,

… avm_enqueue(&front,&back,x->head); … avm_dispose(x); avm_print_list(front); /* error here */

as is the following.

… avm_enqueue(&front,&back,x->head); … avm_dispose(x); /* front is now impossible to reclaim */ avm_dispose(front);

The problem with the last example is that it is not valid even to dispose of the same list more than once, albeit indirectly.

If part of a list is intended to be enqueued temporarily or independently of its parent, the list should be copied explicitly, as the following code demonstrates.

… avm_enqueue(&front,&back,avm_copied(x->head)); /* correct */ … avm_dispose(front); avm_print_list(x);

Function: counter avm_length (list operand)

A counter is meant to be the longest unsigned integer available on the host machine, and is defined in common.h, which is automatically included whenever lists.h is included. The avm_length function returns the number of items in a list. If a list is NULL, a value of zero is returned. There is a possibility of a counter overflow error from this function (Overflow Errors), but only on a platform where the counter type is shorter than the address length.

Function: counter avm_area (list operand)

This function is similar to avm_length, but it treats its argument as a list of lists and returns the summation of their lengths.

Function: list avm_natural (counter number)

This function takes a counter to its representation as a list, as described in Representation of Numeric and Textual Data. That is, the number is represented as a list of bits, least significant bit first, with each zero bit represented by NULL and each one bit represented by a list whose head and tail are NULL.

Function: void avm_print_list (list operand)

The avm_print_list function is not used in any production code but retained in the library for debugging purposes. It prints a list to standard output using an expression involving only commas and parentheses, as per the silly syntax (A Simple Lisp Like Language). The results quickly become unintelligible for lists of any significant size. The function is recursively defined and will crash in the event of a stack overflow, which will occur in the case of very large or cyclic lists.

Function: list avm_position (list key, list table, int *fault)

This function searches for a key in a short table where each item is a possible key.

If it’s not found, a NULL value is returned. If it’s found, a list representing a character encoding according to Character Table is returned.

The ascii code of the character corresponding to the returned list is the position of the key in the table, assuming position numbers start with 1.

The table should have a length of 255 or less. If it’s longer and the key is found beyond that range, the higher order bits of the position number are ignored.

The integer referenced by fault is set to a non-zero value in the event of a memory overflow, which could happen in the course of the list comparisons necessary for the search.

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