NAME

List − overview of circular linked list routines. 

SYNOPSIS

#include <list.h>
List_Init(headerPtr)
List_InitElement(itemPtr)
List_Insert(itemPtr, destPtr)
List_ListInsert(headerPtr, destPtr)
List_Remove(itemPtr)
List_Move(itemPtr, destPtr)
LIST_AFTER(itemPtr)
LIST_BEFORE(itemPtr)
LIST_ATFRONT(headerPtr)
LIST_ATREAR(headerPtr)
LIST_FORALL(headerPtr, itemPtr)
List_IsEmpty(headerPtr)
List_IsAtEnd(headerPtr, itemPtr)
List_First(headerPtr)
List_Last(headerPtr)
List_Prev(itemPtr)
List_Next(itemPtr)

ARGUMENTS

List_Links ∗headerPtr   (in) Pointer to the header of a list. 

List_Links ∗itemPtr   (in) Pointer to a member of a list (possibly the header). 

List_Links ∗destPtr   (in) Pointer to the member after which to insert or move another member. 
 

INTRODUCTION

The List_ routines define the “list” abstraction, which enables one to link together arbitrary data structures.  Lists are doubly-linked and circular.  A list contains a header followed by its real members, if any.  (An empty list therefore consists of a single element, the header,  whose nextPtr and prevPtr fields point to itself).  To refer to a list as a whole, the user keeps a pointer to the header; that header is initialized by a call to List_Init(), which creates an empty list given a pointer to a List_Links structure (described below). 

The links are contained in a two-element structure called List_Links.  A list joins List_Links records (that is, each List_Links structure points to other List_Links structures), but if the List_Links is the first field within a larger structure, then the larger structures are effectively linked together as shown in Figure 1. 
 
  Figure 1: Structure of a list.
...
struct
rest of
List_Links
first elt.
...
struct
rest of
...
...
...
...
List_Links
last elt.
header
List_Links

A typical structure might be something like:
 

     typedef struct {
                 List_Links links;
                 char ch;
                 int flags;
     } EditChar;

It is possible to link structures through List_Links fields that are not at the beginning of the larger structure, but it is then necessary to perform an additional pointer indirection to find the beginning of the larger structure, given a pointer to some point within it.  The easiest way to do this is to define a structure that contains a List_Links field and a pointer to the larger structure, such as:

     typedef struct {
                 List_Links links;
                 LargeStruct ∗structPtr;
     } LargeStructLink;

By including a “LargeStructLink” within a “LargeStruct” and setting the structPtr field of the LargeStructLink to point to the LargeStruct itself, LargeStruct structures may be linked together in a list that is contained in the middle of the structure rather than the beginning. 
 

USAGE

After a list has been initialized by calling List_Init, elements may be inserted, deleted, or moved within the list.  Before an element is inserted in a list for the first time it must be initialized by calling the routine List_InitElement.  To insert a List_Links element into a list, List_Insert is called with two arguments.  The first argument is a pointer to the structure to be inserted into a list, and the second argument is a pointer to the list member after which it is to be inserted.  Typically, the following macros are used to select the insertion point or the destination of a List_Move:

• LIST_BEFORE(itemPtr)Insert the element before ∗itemPtr. 

• LIST_AFTER(itemPtr)Insert the element after ∗itemPtr. 

• LIST_ATFRONT(headerPtr)
Insert the element at the front of the list.

• LIST_ATREAR(headerPtr)Insert the element at the end of the list. 

To insert a list into another list, call List_ListInsert with the header of the list to be inserted and a pointer to the member of the second list after which the first list is to be inserted.  After calling List_ListInsert, the header of the first list is no longer valid and may be destroyed. 

To remove a structure from a list, call List_Remove with a pointer to the structure to be removed.  To move a structure, call List_Move with two arguments: a pointer to the structure to be moved, and a pointer to the structure after which it is to be placed.  List_Move(itemPtr, destPtr) is therefore equivalent to List_Remove(itemPtr) followed by List_Insert(itemPtr, destPtr). 
 

ADDITIONAL UTILITIES

Several other macros are available for the manipulation of List_Links.  LIST_FORALL(headerPtr, itemPtr) is used to step through each element in the list pointed to by headerPtr, setting itemPtr to point to each element in turn.  LIST_FORALL is used typically by casting itemPtr as a pointer to the entire structure, as in:

List_Links ∗headerPtr;/∗ pointer to head of existing list ∗/
List_Links ∗itemPtr;/∗ place-holder during loop ∗/
EditChar   ∗charPtr;/∗ pointer to entire EditChar structure ∗/
 LIST_FORALL(headerPtr, itemPtr) {
charPtr = (EditChar ∗) itemPtr;
/∗ operations using charPtr ∗/
}

The following macros may be useful to those who use List_Links at a “lower” level than looping through an entire list:

• List_IsEmpty(headerPtr)returns TRUE if headerPtr points to an empty list. 

• List_IsAtEnd(headerPtr, itemPtr)
returns TRUE if itemPtr is past the end of the list; i.e., it points to the header. 

• List_First(headerPtr)

• List_Last(headerPtr)List_First returns the first member in a list, and List_Last returns the last member.  If the list is empty, the header is considered to be the first and last member. 

• List_Prev(itemPtr)returns a pointer to the member preceding the given member in its list.  Note:  if the given member is the first element of the list, List_Prev will return the list header. 

• List_Next(itemPtr)returns the next member of the list.  Note:  if the given member is the last element of the list, List_Next will return the list header. 

KEYWORDS

list, linked, circular, List_Links, data structures

Sprite version 1.0  —  December 14, 1989