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
120typedef void (*ListFreeFunc)(void *);
121/* Function to release memory stored within a list (free() syntax) */
122
123typedef void *(* ListAlloc)(size_t size);
124/* Memory allocation procedure to use for this list (malloc() syntax) */
125
126typedef 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
135typedef int (* ListDumpFunc)(void *);
136/* Function to dump the data of a node to the screen */
137
138typedef struct ListNode* listnodePtr;
139typedef 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
146typedef struct LList* listPtr;
147typedef 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
177listPtr 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
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
206void *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
216void *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
228void *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
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
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
262int 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
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
289void *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
297void *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
305void *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
315int 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
324void 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
328void 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
334void *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
345int IntCompare(int *First, int* Second);
346int StringCompare(char *First, char* Second);
347int 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
351int DumpList(listPtr List, ListDumpFunc DataDump);
352/* Print List data using the DataDump function for Node Data Elements */
353
354#ifdef LINKLIST_TEST
355
356int 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
361int 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