$Header: /usr/local/dev/postgres/mastertree/newconf/RCS/simplelists.doc,v 1.5 1989/09/05 17:02:59 mao C_Demo_1 $

			SIMPLELISTS DOCUMENTATION

	lib/C/simplelists.c
	H/simplelists.h

	The simplelists module provides for the handling of doubly linked
lists.  There are two structures involved:


#define NODE_MAGIC  0x41424344
#define LIST_MAGIC  0x45464748

SLNode {
    SLNode  *sn_Next;	/* Next node or &sn_Term	*/
    SLNode  *sn_Prev;	/* Previous node or &sn_Head	*/
    SLList  *sn_List;	/* node's list or NULL		*/ 
    uint32   sn_Magic;	/* NODE_MAGIC			*/
};

SLList {
    SLNode *sl_Head;	/* First node or &sn_Term	*/
    SLNode *sl_Term;	/* Terminator == NULL		*/
    SLNode *sl_Tail;	/* Last node or &sn_Head	*/
    Offset  sl_Offset;	/* structural offset.		*/
    uint32  sl_Magic;	/* LIST_MAGIC			*/
    uint32  sl_Pad0;	/* pad byte for 8 char align.	*/
};

	A SimpleList structure heads every list, which may consist of
an arbitrary number of SimpleNodes.  Both the SimpleList and SimpleNode
structures must be initialized:

	SLNewList(&SimpleList, offsetofnodeinstructure);
	SLNewNode(&SimpleNode);

	The SimpleList is initialized as follows:  sl_Head points to
sl_Term, sl_Term = NULL, sl_Tail points to sl_Head.

	SimpleNodes that are part of a larger structure need not be 
placed at the beginning of the structure to work.  By specifying the
offset of the node from its structure when you call SLNewList(), the
simplelists module will automatically return pointers to the base of
the structure the node is in rather than just to the node itself (in which
case you would have had to subtract its offset to get to the base
yourself).

	SLList List;

	MyStructure {
	    char *poof;
	    SLNode Node;
	};

	MyStructure N1 = { "1" };
	MyStructure N2 = { "2" };
	MyStructure N3 = { "3" };
	MyStructure *n;

	SLNewList(&List, offsetof(MyStructure, Node));
	SLNewNode(&N1.Node);
	SLNewNode(&N2.Node);
	SLNewNode(&N3.Node);

	SLAddTail(&List, &N1.Node);
	SLAddTail(&List, &N2.Node);
	SLAddTail(&List, &N3.Node);

	for (n = (MyStructure *)SLGetHead(&List);
	     n != NULL;
	     n = (MyStructure *)SLGetSucc(&n->Node)
	) {
	    printf("poof is %s\n", n->poof);
	}
	    
			CALL SUMMARY

	(void) SLNewList(&SLList, offsetofnode);
	(void) SLNewNode(&SLNode)

	    Explained above.  The offset specified in SLNewList() is how
	    far into the structure (MyStructure in the above example)
	    the nodes that make up this list will be.

	    This means that all nodes in the list must all be at the same
	    offset in their associated parent structures.

	ArbitraryStructure *SLGetHead(&SimpleList)
	ArbitraryStructure *SLGetTail(&SimpleList)

	    SLGetHead() and SLGetTail() return the first and last
	    nodes in the specified list or NULL if the list is empty.  The
	    sn_Offset field is subtracted from the node address before it
	    is returned so you actually get a pointer to whatever structure
	    you put the node in.

	(void) SLInsertBefore(nodeinlist, newnodetoadd)
	(void) SLInsertAfter(nodeinlist, newnodetoadd)
	SimpleNode *nodeinlist, *newnodetoadd;

	    These functions allow you to insert new nodes before or after
	    other nodes already in a list.  nodeinlist is the node 
	    already in the list, and newnodetoadd is the new node to
	    add before or after nodeinlist.

	ArbitraryStructure *SLGetSucc(&ArbStructure.SimpleNode)
	ArbitraryStructure *SLGetPred(&ArbStructure.SimpleNode)

	    These calls return the next and previous node in the
	    list given a node.  Here you supply the address of a
	    node.  Instead of returning the address of the next or
	    previous node, sn_Offset is subtracted from the next or
	    previous node address and the new address returned, which
	    will point to whatever structure you put the node in.


	(void) SLRemove(&SimpleNode)

	    This function removes a node from its list.  You supply
	    the address of the node to remove.

	    DO NOT REMOVE A NODE THAT IS NOT IN A LIST.


	(void) SLAddHead(&SLList, &SLNode)
	(void) SLAddTail(&SLList, &SLNode)

	    These functions add an initialized node to a given list,
	    either at the beginning or end of the list.

	ArbitraryStructure *SLRemHead(&SLList)
	ArbitraryStructure *SLRemTail(&SLList)

	    These functions remove the first element or last element
	    of a list, subtracting sn_Offset from the node structure
	    to return a pointer to the base of whatever structure the
	    node was placed in.

	    NULL is returned if the list is empty.

--- WORKING EXAMPLE ---



#include "simplelists.h"

typedef struct {
    char *name;
    SLNode Node;
} MyStruct;

SLList List;
MyStruct N1 = { "1" };
MyStruct N2 = { "2" };
MyStruct N3 = { "3" };
MyStruct N4 = { "4" };


main()
{
    SLNewList(&List, offsetof(MyStruct, Node));
    SLNewNode(&N1.Node);
    SLNewNode(&N2.Node);
    SLNewNode(&N3.Node);
    SLNewNode(&N4.Node);

    SLAddHead(&List, &N1.Node);
    SLAddTail(&List, &N4.Node);
    SLInsertAfter(&N1.Node, &N2.Node);
    SLInsertBefore(&N4.Node, &N3.Node);

    ShowList();

    SLRemove(&N1.Node);
    SLRemove(&N4.Node);

    SLInsertBefore(&N2.Node, &N1.Node);
    SLInsertAfter(&N3.Node, &N4.Node);

    ShowList();
}

ShowList()
{
    MyStruct *x;

    for (x = (MyStruct *)SLGetHead(&List);
	 x;
	 x = (MyStruct *)SLGetSucc(&x->Node)
    ) {
	printf("%08lx %s\n", x, x->name);
    }
    puts("");
}