Embedded Linked List Package

Classes
class	ListItem
	Embedded Doubly-Linked-List Class. More...
class	ListMergeSort
	Merge-sort functor for ListItem lists. More...
class	ListRadixSort
	Radix-sort functor for ListItem lists. More...
class	SListItem
	Embedded Singly-linked list Class. More...
class	SListQueue
	Queue head for SListItem elements supporting FIFO operations. More...
class	SListRadixSort
	Radix-sort functor for SListItem lists. More...
Defines
#define	GetContainer(memberptr, type, member)   static_cast<type*>(__GetContainer(memberptr, &type::member))
	Get a pointer to a structure containing a given ListItem.
#define	ListForEach(listp, head)   for (listp = (head)->next; listp != (head); listp = listp->next)
	Forward list iterator.
#define	ListForEachReverse(listp, head)   for (listp = (head)->prev; listp != (head); listp = listp->prev)
	Reverse list iterator.

---

Detailed Description

The Linked-List package provides two flavors of linked-lists. Both are implemented using embedded data structures, such that all memory required by the list package is implicitly allocated and managed by its clients.

First, the ListItem object, a doubly-linked list, supports unrestricted O(1) insertions and removals. Very simple and versatile.

Second, the SListItem object, a singly-linked list, supports strict LIFO operations, where only succeeding elements can be removed. SListItem is less applicable than ListItem, but requires less memory.

The Linked-List package also provides basic sorting algorithms, including Merge Sort and Radix Sort. These are provided in the ListMergeSort, ListRadixSort, and SListRadixSort functor classes.

If items require infrequent sorting by one of several attributes, consider using ListItem to list items, and MergeSort or RadixSort to perform the infrequent sorting. If items are frequently searched or enumerated in order, and sorted by a single attribute, consider using the BinTree class. For twice the amount of space in each item, and more expensive insertions and removals, it provides incremental sorting and bidirectional enumerability.

To use a List:

1. Embed a ListItem or SListItem object in each application- specific object participating as a list item (call the member ListMember).
2. Create a ListItem in the managing object, e.g. the queue head if handling lists of packets (call it XList). This is used as the head, and will point to the first and last inserted items.
3. To append an item, use XList.AppendItem(ItemPointer->ListMember)
4. To remove an item, use ItemPointer->ListMember.Unlink().

---

Define Documentation

#define GetContainer	(	memberptr,
		type,
		member		)	static_cast<type*>(__GetContainer(memberptr, &type::member))

Get a pointer to a structure containing a given ListItem.

Parameters:

	memberptr	Pointer to the embedded ListItem.
	type	Name of structure type containing the list.
	member	Name of structure member of the ListItem.

For exmaple, if you have a:

        struct some_struct {
                int stuff.
                ...
                ListItem mylist;
                ...
        }

and have a pointer to its mylist member, and need a pointer to the struct some_struct, just use:

        GetContainer(listptr, struct some_struct, mylist)

#define ListForEach	(	listp,
		head		)	for (listp = (head)->next; listp != (head); listp = listp->next)

Forward list iterator.

For-loop iterating over all members of a list in forward order.

Parameters:

	listp	Iterator variable, assigned to the ListItem under consideration for each iteration.
	head	List head. Iteration starts at the beginning of this, and stops when listp == head.

#define ListForEachReverse	(	listp,
		head		)	for (listp = (head)->prev; listp != (head); listp = listp->prev)

Reverse list iterator.

For-loop iterating over all members of a list in forward order.

Parameters:

	listp	Iterator variable, assigned to the ListItem under consideration for each iteration.
	head	List head. Iteration starts at the end of this, and stops when listp == head.

---