[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

### 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.

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

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