EBOOK-TOOLS
linklist.h
Go to the documentation of this file.
1 /* LinkList.H -- ANSI C Linked List Container Type
2  Handles Lists, Queues, Stacks, Splay Trees,
3  and custom list types via one consistant interface.
4 
5  - Written by Jeff Hay, jrhay@lanl.gov
6  - If you find errors in this library, please let me know!
7 
8  What It Does:
9  - Creates, maintains, and destroys any type of linked memory structure
10  (singly/doubly linked lists, queues, stacks, etc) effeciently and
11  without memory leaks.
12  - Any user-specified data may be held within structure nodes.
13  - Allows user-definable memory allocation and deallocation routines
14  to be used in place of standard malloc() and free() calls.
15  - Any number and types of linked memory structures may be created
16  (subject only to memory limitations)
17  - "Should be" portable to any ANSI C compilent platform
18 
19  Stuff To Do Yet:
20  - Add functionallity to be able to interrupt list maintence routines
21  at any point and still maintain list continuity (for multi-processor
22  shared memory environments)
23 
24  The object file compiled from this library is around 5K depending on
25  operating platform.
26 
27 */
28 #ifndef __c_LINKLIST__
29 #define __c_LINKLIST__
30 
31 /*
32  NOTE: All functions assume the list data structures are UNTOUCHED expect
33  by functions in this library. Bad things could happen if you muck
34  with them at all. (unless you know what you are doing.... ;)
35 
36  This library has been through several incarnations, each one adding features
37  while maintaining compatibility with the previous versions. The result is a
38  confusing number of functions. For new programs, the only functions you need
39  are:
40  List Creation - NewListAlloc(), AddNode()
41  List Destruction - FreeList(), DelNode()
42  List Transversal - NextNode(), PrevNode(), IndexNode()
43  List Manipulation - GetNode(), GetNodeData()
44 
45  All other functions are either internal-use functions or obsolete definitions
46  to maintain source compatiblity for programs written to older versions of
47  this library.
48 
49  Note also that if using the library to maintain binary search trees, the
50  List Transversal functions should not normally be used.
51 
52  See the last section of this header file for extended documentation on all
53  functions.
54 */
55 
56 /* Will use the DALLOC library if "dalloc.h" is included on the compiler
57  command line */
58 
59 /* Uncomment the following line to compile an executable from LinkList.C that
60  will demonstrate and test the functions contained in this library. (or
61  define LINKLIST_TEST on the compiler command line ("make linklist") */
62 /* #define LINKLIST_TEST 1 */
63 
64 /* -------
65  Include files used by this library
66 ------- */
67 #include <stdio.h>
68 #include <stdlib.h>
69 
70 /* --------
71  List Flags and Parameters
72 -------- */
73 
74 /* List Parameters */
75 #define LISTADDCURR 0x300 /* Add New Node At Current Record In List */
76 #define LISTADDHEAD 0x100 /* Add New Nodes At Head Of List */
77 #define LISTADDTAIL 0x200 /* Add New Nodes At Tail Of List */
78 #define LISTADDSPLAY 0x400 /* Add New Nodes As A Splay Tree */
79 #define LISTDELCURR 0x030 /* Delete Nodes At Current Record */
80 #define LISTDELHEAD 0x010 /* Delete Nodes At Head Of List */
81 #define LISTDELTAIL 0x020 /* Delete Nodes At Tail Of List */
82 #define LISTDELSPLAY 0x040 /* Delete Nodes As A Splay Tree */
83 #define LISTREADCURR 0x003 /* Read List At Current Node */
84 #define LISTREADHEAD 0x001 /* Read Head Of List */
85 #define LISTREADTAIL 0x002 /* Read Tail Of List */
86 
87 #define LISTDELREAD 0x1000 /* Delete Node On Reading */
88 #define LISTCIRCULAR 0x2000 /* Circular List - Head->Next=Tail, etc */
89 #define LISTBTREE 0x4000 /* List is actually a binary tree */
90 
91 /* Masks of List Parameters */
92 #define LISTADDMASK 0xF00 /* Add New Node Method */
93 #define LISTDELMASK 0x0F0 /* Delete Node Method */
94 #define LISTREADMASK 0x00F /* Read Node Method */
95 #define LISTFLAGMASK 0xF000 /* Operation Flags */
96 
97 /* Common Data Structure Types */
98 #define LIST (LISTADDCURR | LISTREADCURR | LISTDELCURR)
99 #define FIFO (LISTADDTAIL | LISTREADHEAD | LISTDELHEAD)
100 #define LIFO (LISTADDHEAD | LISTREADHEAD | LISTDELHEAD)
101 #define QUEUE (FIFO | LISTDELREAD)
102 #define STACK (LIFO | LISTDELREAD)
103 #define CIRCULAR_QUEUE (QUEUE | LISTCIRCULAR)
104 #define STREE (LISTBTREE | LISTADDSPLAY | LISTDELSPLAY | LISTREADCURR)
105 
106 /* --------
107  Possible return values of functions in this library
108 -------- */
109 #define LLIST_NOERROR 0 /* No problem! */
110 #define LLIST_NULL 1 /* Bad value passed to function */
111 #define LLIST_ERROR -1 /* Misc. program/library error. Serious trouble! */
112 
113 #define LLIST_OK LLIST_NOERROR /* duplicate definitions for compatibility */
114 #define LLIST_BADVALUE LLIST_NULL
115 
116 /* --------
117  List data structures
118 -------- */
119 
120 typedef void (*ListFreeFunc)(void *);
121 /* Function to release memory stored within a list (free() syntax) */
122 
123 typedef void *(* ListAlloc)(size_t size);
124 /* Memory allocation procedure to use for this list (malloc() syntax) */
125 
126 typedef int (* NodeCompareFunc)(void *, void *);
127 /* Function used to compare nodes for list sorting. The two passed pointers
128  are two data elements from nodes of a list. CompareFunc must return:
129  1 iff First Node > Second Node
130  0 iff First Node = Second Node
131  -1 iff First Node < Second Node
132  Results are undefined if one or both pointers are NULL. (note that this
133  definition is compatible with strcmp() and related functions) */
134 
135 typedef int (* ListDumpFunc)(void *);
136 /* Function to dump the data of a node to the screen */
137 
138 typedef struct ListNode* listnodePtr;
139 typedef struct ListNode
140 {
141  void *Data; /* Data stored at this node (user-defined) */
142  listnodePtr Next, /* Next Node in List, Right Child in Binary Tree */
143  Prev; /* Previous Node in List, Left Child in Binary Tree */
145 
146 typedef struct LList* listPtr;
147 typedef struct LList
148 {
149  listnodePtr Current, /* Last Accessed Node */
150  Head, /* Head of List, Root of Binary Tree */
151  Tail; /* Tail of List */
152  int Size, /* Number of nodes in List or Binary Tree */
153  Flags; /* Flags associated with List/Tree */
154  ListAlloc memalloc; /* malloc()-type procedure to use */
155  ListFreeFunc memfree; /* free()-type procedure to use */
156  NodeCompareFunc compare; /* Function to use to compare nodes */
158 
159 /* -------
160  Make sure we have DALLOC (or similarly-named macros)
161 -------- */
162 
163 #ifndef DMALLOC
164 #define DMALLOC malloc
165 #endif
166 #ifndef DFREE
167 #define DFREE dfree
168 #endif
169 #ifndef DCOUNT
170 #define DCOUNT dcount
171 #endif
172 
173 /* --------
174  Function Prototypes
175 -------- */
176 
177 listPtr NewListAlloc(int ListType, ListAlloc Lalloc, ListFreeFunc Lfree,
178  NodeCompareFunc Cfunc);
179 /* Create a brand new list structure. The structrue is defined by
180  ListType, which is a logical OR of the List Parameters defined above.
181  Use the specified allocation and free function to allocate dynamic
182  memory to the list. If "alloc" or "free" are NULL, default to
183  malloc() and free() (respectively) from stdlib. If "Cfunc" is NULL, don't
184  do comparisons.
185 
186  Returns
187  Pointer to a new list
188  NULL on error (Lalloc() procedure failed) */
189 
190 #define NewList(Type) NewListAlloc(Type, NULL, NULL, NULL)
191 /* Macro definition of: listPtr NewList(int ListType);
192  for compatibility with previous versions of library */
193 
194 listnodePtr NewListNode(listPtr List, void *Data);
195 /* Creates a new node for the specified list. Memory is allocated with
196  the list alloc procedure. Data is a pointer to any kind of data or may
197  be NULL. If List is NULL, node is created using malloc().
198  Returns
199  Pointer to the new node
200  NULL on error (alloc failed) */
201 
202 #define NewNode(Data) NewListNode(NULL, Data)
203 /* Macro definition of: listnodePtr NewNode(void *Data);
204  for compatibility with previous versions of library */
205 
206 void *GetNode(listPtr List);
207 /* Reads the next node in the list (as specified at list creation with one of
208  the LISTREAD* properties). If list has unknown LISTREAD* property, returns
209  as LISTREADCURR. If LISTDELREAD is a property of the list, the
210  node is automatically deleted (note that the node DATA is *not* free()'d).
211 
212  Returns
213  Pointer to the node data
214  NULL if List is NULL or empty (or list read property is unknown) */
215 
216 void *FindNode(listPtr List, void *Data);
217 /* Finds a node in the list for which the list compare function specified at
218  list creation returns 0 when compared with "Data". Sets List->Current to
219  the found node, and returns found node's data.
220 
221  Returns
222  Pointer to the node data
223  NULL if list empty
224  if no list compare function
225  if no node matching data was found in list
226 */
227 
228 void *BTFind(listPtr List, void *Data);
229 /* Performs "FindNode" operation when list is a binary tree; called
230  automatically by FindNode() when list has LISTBTREE property set. */
231 
233 /* Returns the data contained in the specified node, or NULL if Node is empty*/
234 
235 int AddNode(listPtr List, listnodePtr Node);
236 /* Adds a node to the list in the location specified at list creation by one of
237  the LISTADD* properties. If the LISTADD property is unknown for any reason
238  (program error), the node is added at the current list position. Node must
239  be created by NewListNode. Current list pointer is set to the newly added
240  node.
241  Returns
242  LLIST_NOERROR on success
243  LLIST_NULL if either List or Node are NULL
244  LLIST_ERROR on undefined program error */
245 
247 int HeadList(listPtr List, listnodePtr Node);
248 int TailList(listPtr List, listnodePtr Node);
250 /* These functions add the specified node to the specified list at the either
251  the current position, the head of the list, the tail of the list, ,or in a
252  splay pattern, respectively. All assume the node has been init'd
253  by NewNode() and all set List->Current to the newly added node.
254 
255  These functions should not normally be called directly by user programs
256  (AddNode() will call the approrpiate function for the list)
257 
258  All return
259  LLIST_NOERROR on success
260  LLIST_NULL if either List or Node are NULL */
261 
262 int DelNode(listPtr List);
263 /* Deletes a node from the list. The node deleted is specified at list creation
264  by one of the LISTDEL* properties. If the LISTDEL property is unknown for
265  any reson, the "current" node is deleted. Current list position is set to
266  the next logical node in the list (or NULL). Note: Note DATA is *not*
267  deleted.
268 
269  Returns
270  LLIST_NOERROR on success
271  LLIST_NULL if List is NULL
272  LLIST_ERROR on undefined program error */
273 
274 int RemoveList(listPtr List);
277 /* These functions delete the node at either the current list position,
278  the head of the list, the tail of the list, or as a splay pattern,
279  respectively. All set List->Current to the next node in the list
280  (Node->Next).
281 
282  These functions should not normally be called directly by user programs
283  (DelNode() will call the approrpiate function for the list)
284 
285  All Return
286  LLIST_NOERROR on success
287  LLIST_NULL if List is NULL */
288 
289 void *NextNode(listPtr List);
290 /* Step to the next logical node in the list. For lists with LISTBTREE set,
291  steps to the right child of the current node.
292 
293  Returns
294  NULL if List or next node is empty
295  Pointer to the next node's data on success */
296 
297 void *PrevNode(listPtr List);
298 /* Step to the previous logical node in the list. For lists with LISTBTREE set,
299  steps to the left child of the current node.
300 
301  Returns
302  NULL if List or next node is empty
303  Pointer to the next node's data on success */
304 
305 void *IndexNode(listPtr List, int Index);
306 /* Step to the logical node numbed "Index" in the List. The head of
307  the list is index "1"; the tail is index "List->Size". If LISTBTREE is set,
308  this function always returns NULL (Indexing makes no sense).
309 
310  Returns
311  NULL if List or indexed node is empty
312  if Index > size of list
313  Pointer to the index node's data on success */
314 
315 int FreeList(listPtr List, ListFreeFunc DataFree);
316 /* Deletes entire list structure and frees all memory. List is undefined
317  after this call. "DataFree" is an optional function used to free the
318  memory allocated for each node's data (ie, if the data is a dynamic
319  structure, etc); it may be NULL. It will *not* be called for empty
320  nodes (node->data == NULL). If this function returns with anything
321  other then LLIST_NOERROR, an error was encountered deleting a node from
322  the list. List is in undefined state. */
323 
324 void SwapList(listPtr List);
325 /* Swaps the current node in the list with the next node in the list. No
326  function if current node is tail of list. */
327 
328 void SortList(listPtr List);
329 /* Preforms a slow sort on the list. Sort is handled in-place. Current node
330  is head of list after sort. Does not attempt to sort lists with LISTBTREE
331  property set.
332 */
333 
334 void *SplayList(listPtr List, void *Data);
335 /* Performs a splay operation on the list. The list is assumed to be a splay
336  tree. Finds the node in the tree that matches "Data" and moves that node
337  (or the closest node less then data) to the root of the tree, preserving the
338  inorder transversal of the tree.
339 
340  Returns
341  Pointer to node data if found
342  NULL if List is NULL
343  if "Data" not found in Tree */
344 
345 int IntCompare(int *First, int* Second);
346 int StringCompare(char *First, char* Second);
347 int DoubleCompare(double *First, double* Second);
348 /* These are suitable NodeCompareFunc functions for three common types of
349  nodes. Provided just to make life a little easier... */
350 
351 int DumpList(listPtr List, ListDumpFunc DataDump);
352 /* Print List data using the DataDump function for Node Data Elements */
353 
354 #ifdef LINKLIST_TEST
355 
356 int PrintList(listPtr List, char *DataFmt);
357 /* Display the contents of a list. Provided mainly as an example
358  of how to transverse list if needed. Written for an old version of
359  this library and never updated. */
360 
361 int PrintTree(listPtr List, char *DataFmt);
362 /* Prints the contents and structure of a Tree using DataFmt as the printf()
363  format for Node Data Elements. Called by PrintList as appropriate. */
364 
365 #endif
366 
367 #endif /* __c_LINKLIST__ */
368 
369 
370 
371 
372 
int Flags
Definition: linklist.h:153
ListAlloc memalloc
Definition: linklist.h:154
listnodePtr Tail
Definition: linklist.h:151
ListFreeFunc memfree
Definition: linklist.h:155
NodeCompareFunc compare
Definition: linklist.h:156
listnodePtr Head
Definition: linklist.h:150
listnodePtr Current
Definition: linklist.h:149
int Size
Definition: linklist.h:152
listnodePtr Prev
Definition: linklist.h:143
listnodePtr Next
Definition: linklist.h:142
void * Data
Definition: linklist.h:141