SquareLists

SqList_makeHead, SqList_insertNode, SqList_deleteNode, SqList_findNode, SqList_freeList, SqList_printList, SqList_getMin, SqList_getMax, SqList_getNext SqList_getNext_r − work with Square List Data Structures

#include <squarelists.h>

SquareList *SqList_makeHead(int (*cmp)());
int SqList_insertNode(SquareList **head, void *data);
void *SqList_deleteNode(SquareList **head, void *data);
void *SqList_findNode(SquareList **head, void *data);
void SqList_freeList(SquareList **head, void (*freeData)());
void SqList_printList(SquareList **head, FILE *fp, void (*printData)());
void *SqList_getMin(SquareList **head);
void *SqList_getMax(SquareList **head);
void *SqList_getNext(SquareList **head);
void *SqList_getNext_r(SquareList **head, SquareList **where);

SqList_makeHead() allocates memory for the head of a Square List Data Structure. The cmp routine will be passed two data elements which it must compare and return a -1, 0, or 1 return code, signifying that the first is larger, they are equal, or the second is larger, respectively.

SqList_insertNode() inserts data element into the SquareList structure head points to.

SqList_deleteNode() removes the node from the SquareList head points to which matches the key in the data structure passed. The data structure from the deleted node is returned. NULL is returned if no matching node is found to delete.

SqList_findNode() searches the SquareList head points to for a node that matches the key in the data structure passed. The data structure found is returned. NULL is returned if no matching node is found. You must not modify the key in the returned node or you will destroy the integrity of the SquareList Data Structure.

SqList_freeList() frees the memory associated with the SquareList Data Structure head points to. The freedata() routine is called with the pointer to the data structure from each node to free the associated memory. For a simple structure, you can pass the free() library routine.

SqList_printList() prints the data from the SquareList Data Structure head points to using the printData() routine you provide. The printData() routine will be passed the FILE *fp parameter you passed and the data structure from the node being examined for printing.

SqList_getMin() returns the data structure with the minimum key value from the SquareList Data Structure pointed to by head.

SqList_getMax() returns the data structure with the maximum key value from the SquareList Data Structure pointed to by head.

SqList_getNext() returns the data structure from the next node in the SquareList Data Structure pointed to by head. NULL will be returned when the end of the SquareList Data Structure is reached. If SqList_deleteNode() is used between calls to SqList_getNext() the results are undefined. SqList_getNext() is not thread-safe, it uses static memory to track the path through the SquareList Data Structure.

SqList_getNext_r() is the thread-safe version of SqList_getNext(). The parameter where should be set to (SquareList *)NULL before the first call to SqList_getNext_r() and must not be modified between calls. If where is modified, the resulting disaster is your own fault.

For SqList_makeHead(), the value returned is a pointer to the head node of the SquareList Data Structure, or NULL if the request fails.

SqList_insertNode() returns 0 if the insert succeeds and -1 if it fails.

SqList_deleteNode() and SqList_findNode(), return a pointer to the data structure from the deleted or found node, or NULL if the request fails.

SqList_freeList() and SqList_printList(), do not return anything.

SqList_getMin() returns the data structure from the head node (which is the minimum key value), or NULL if there are no nodes.

SqList_getMax() returns the data structure from the node with the maximum key value, or NULL if there are no nodes.

SqList_getNext() and SqList_getNext_r() return the data structure from the next node in the SquareList Data Structure, or NULL if there are no nodes or you have walked to the end of the structure. Usage of Sqlist_deleteNode() between calls to SqList_getNext() or SqList_getNext_r() must be avoided as such behavior is likely to cause disaster.

This is based on the article on the Square List Data Structure in the May 2003 issue of Dr. Dobb’s Journal by Mark Sams.

WARNING: You will destroy the SquareList structure if you change the value of the key(s) used by your cmp routine in the data structure returned by SqList_findNode. If you want to change the key(s), you MUST use the SqList_deleteNode to find it, modify it, and then use SqList_insertNode to put it back into the SquareList data structure.

If you use SqList_deleteNode() between calls to SqList_getNext() or SqList_getNext_r() the results are undefined.

None known.