forked from dale48/levawc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdlist.h
342 lines (315 loc) · 11.5 KB
/
dlist.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
/*
* _____
* ANSI / ___/
* / /__
* \___/
*
* Filename: dlist.h
* Author : Kyle Loudon/Dan Levin
* Date : Fri Mar 22 12:40:45 GMT 2013
* Version : 0.40
* ---
* Description: A doubly-linked list - implemented as a pure, generic ADT.
*
* Revision history - coming up below:
*
* Date Revision message
* 2012-12-03 Created this file
* 2013-02-05 Created a new function 'int DLISTfind_remove(Dlist list, void **data)'
* 2013-02-19 Made some revision to the Doxygen documentation. Enhanced the description of
* in/out parameters - i.e. double-pointers.
*
*/
/**
* @file dlist.h
**/
#ifndef _DLIST_H_
#define _DLIST_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>
#ifdef __cplusplus
extern "C" {
#endif
/**
* Macro for forward traversal of the list
*
**/
#define DLIST_FWD 1
/**
* Macro for backward traversal of the list
*
**/
#define DLIST_BWD -1
/**
* Use a @b typedef - to hide the interior of @b DList_ - in the
* implementation file. This is how @a data @a hiding can be done in C.
*
**/
typedef struct DList_ *Dlist;
/**
* Another @b typedef - for hiding the interior of @b DListElmt_ -
* in the implementation file.
*
**/
typedef struct DListElmt_ *DlistNode;
/* FUNCTION DECLARATIONS */
/**
*
* Initiate the list.
*
* @param[in] destroy - A reference to a user-made function, reponsible
* for freeing node data, when the list is deleted. If @a destroy is
* NULL - then node data will be left untouched when the list is
* destroyed.
* @return A reference - to a new, empty list - if dynamic memory
* allocation for the ADT was successful - or NULL otherwise.
* Take really good care of this return value, since it will be needed
* as a parameter in subsequent calls - to the majority of other list
* handling functions in the this function interface - i.e. a sort of
* "handle" to the list.
* @see DLISTdestroy()
**/
Dlist DLISTinit(void (*destroy)(void *data));
/**
* Destroy the list.
*
* The list is destroyed - that is, all the memory occupied by the nodes
* is deallocated. The user-defined callback function @a destroy, given
* as an argument to @b DLISTinit(), is responsible for freeing
* dynamically allocated node data, when this function is called. When
* all nodes and data have been deallocated - the list header is
* deallocated, too.
*
* @param[in] list - a reference to current list.
* @return Nothing.
* @see DLISTinit()
**/
void DLISTdestroy(Dlist list);
/**
* Insert a new node - @b after parameter @a node.
*
* This function inserts an new node, with a reference to node data
* given by parameter @a data - @b after the node referenced by
* parameter @a node - into @a list. If list is empty - the
* function should be called with @a node set to NULL - to avoid
* confusion.
*
* @param[in] list - reference to current list
* @param[in] node - the node after which the new node is to be
* inserted. Should be set to @b NULL - if the list is empty.
* @param[in] data - reference to data to be stored in the new node,
* that is inserted into the list.
*
* @return Value 0 - if everything went OK - or value -1 otherwise.
**/
int DLISTinsnext(Dlist list, DlistNode node, const void *data);
/**
* Insert a new node - @b before parameter @a node.
*
* This function inserts an new node, with a reference to node data
* given by parameter @a data - @b before the node referenced by
* parameter @a node - into @a list. If list is empty - the
* function should be called with @a node set to NULL - to avoid
* confusion.
*
* @param[in] list - reference to current list
* @param[in] node - the node before which the new node is to be
* inserted. Should be set to @b NULL - if the list is empty.
* @param[in] data - reference to data to be stored in the new node,
* that is inserted into the list.
*
* @return Value 0 - if everything went OK - or value -1 otherwise.
**/
int DLISTinsprev(Dlist list, DlistNode node, const void *data);
/**
* Remove the node referenced by parameter @a node.
*
* After the call - an (external) pointer referenced by parameter
* @a data, has been redirected to point to data of the removed
* node - if the call was succesful. The caller is responsible
* for the future of this memory - deallocating it, if needed,
* for example.
*
* @param[in] list - reference to current list.
* @param[in] node - the node to be removed.
* @param[out] data - reference to a pointer, that will point to data
* of the removed node - after the call, if successful.
*
* @return Value 0 - if the call was OK - or value -1
* otherwise.
**/
int DLISTremove(Dlist list, DlistNode node, void **data);
/**
* Get the list size.
*
* @param[in] list - a reference to the current list.
*
* @return The size, that is, the number of nodes in the list.
**/
int DLISTsize(Dlist list);
/**
* Get a reference to the head node of the list.
*
* @param[in] list - a reference to the current list.
* @return A reference to the @b first node in the list.
**/
DlistNode DLISThead(Dlist list);
/**
* Get a reference to the tail node of the list.
*
* @param[in] list - a reference to the current list.
* @return A reference to the @b last node in the list.
**/
DlistNode DLISTtail(Dlist list);
/**
* Determine if a certain node is the head node of
* the list - or not.
*
* @param[in] list - a reference to the current list.
* @param[in] node - a reference to the node to be tested.
* @return Value 1 - if @a node indeed is the first node
* of the list - or 0 otherwise.
**/
int DLISTishead(Dlist list, DlistNode node);
/**
* Determine if a certain node is the tail node
* of the list - or not.
*
* @param[in] list - a reference to the current list.
* @param[in] node - a reference to the node to be tested.
* @return Value 1 - if @a node indeed is the last node
* of the list - or 0 otherwise.
**/
int DLISTistail(Dlist list, DlistNode node);
/**
* Get a reference to data stored in a node.
*
* @param[in] node - a reference to the current node.
* @return Generic reference to data - stored in parameter @a node.
**/
void *DLISTdata(DlistNode node);
/**
* Get a reference to the next node in the list.
*
* @param[in] node - a reference to @b current node.
* @return A reference to the @b next node - following
* parameter @a node - in the list.
**/
DlistNode DLISTnext(DlistNode node);
/**
* Get a reference to the previous node in the list.
*
* @param[in] node - a reference to @b current node.
* @return A reference to the @b previous node - directly
* prior to parameter @a node - in the list.
**/
DlistNode DLISTprev(DlistNode node);
/**
* Find the first node - with node data matching data referenced by
* parameter @a data.
*
* Search the list sequentially for a node, whose data matches the data
* referenced by parameter @a data. A reference to the node with the
* @b first match will be returned - NULL otherwise. A @b user-defined
* @b callback @b function, responsible for doing the @b matching
* of node data - with data referenced by parameter @a data - @b must
* exist for this function to work - otherwise NULL will be returned -
* always. This user-supplied @b match-callback is set into the list
* with another function - DLISTsetmatch().
*
* @param[in] list - reference to the current list.
* @param[in] data - reference to the search key data.
*
* @return Reference to the first node with a match to data referenced
* by parameter @a data - if found - NULL otherwise
* @see DLISTsetmatch()
**/
DlistNode DLISTfindnode(Dlist list, const void *data);
/**
* Set a valid match callback function for sequentially searching
* the list
*
* @param[in] list - reference to current list.
* @param[in] match - a reference to a user-defined function that
* receives references to node data - and search key data - via its
* parameters @a key1 and @a key2 - and thereby can make
* the actual matching. This match-callback shall return 1 -
* in case of a hit - or 0 otherwise.
*
* @return Nothing.
**/
void DLISTsetmatch(Dlist list, int (*match)(const void *key1,
const void *key2));
/**
* Search - and remove a node - by using an in/out parameter.
*
* When called, the 2nd parameter of this function, @a data, should
* reference a pointer, that points to the search key data. Moreover,
* a @b user-defined @b callback @b function responsible for doing the
* @b matching of node data - and data referenced by parameter
* @a data - must exist for this function to work - otherwise -2 will
* be returned - always.
* This user-supplied @b match-callback is set into the list with a
* call to another function, DLISTsetmatch().
*
* After the call - an (external) pointer referenced by parameter
* @a data, has been redirected to point to data of the removed
* node - if the call was succesful. The caller is responsible
* for the future of this memory - deallocating it, if needed,
* for example.
*
* @param[in] list - reference to current list.
* @param[in,out] data - reference to an external pointer, that
* initially shall point to the search key data - when this
* function is called. After the call, this referenced (external)
* pointer, has been redirected - to point to node data of the
* removed node - if the call was successful. The caller is
* responsible for the future of this memory - deallocating it,
* for example.
*
* @return Value 0 -- if the call was OK - that is, node found and removed.\n
* Value 1 -- node not found.\n
* Value -2 -- if match-callback is not set.\n
* Value -1 -- otherwise (implies fatal error).
*
* @see DLISTsetmatch()
**/
int DLISTfind_remove(Dlist list, void **data);
/**
* Sort a list according to the Selection Sort Algorithm -
* with complexity Θ(n<sup>2</sup>)).
*
* @param[in] list - reference to current list.
* @param[in] cmp - reference to a user-defined callback function
* responsible for comparing node data.
* This callback function should return a value of -1
* if data referenced by @a key1 is less than data referenced by
* @a key2 - or 0 if they are equal - or 1 otherwise. This will
* produce an ascending sort order. If a descending order is what
* you want - just swap the return values -1 and 1 for the
* comparisons made above.
*
* @return Nothing.
**/
void DLISTsort(Dlist list, int (*cmp)(const void *key1, const void *key2));
/**
* Traverse the list from the beginning or the end - and have
* a user-defined function called - for each node in the list.
*
* @param[in] list - reference to current list.
* @param[in] callback - reference to user-defined callback function,
* that gets @b read @b access to node data via its parameter
* @a data - to do whatever is relevant. Print data, for example.
* @param[in] direction - @a direction of @a traversal. Set to DLIST_FWD
* for forward traversal - and DLIST_BWD for traversing backwards.
*
* @return Nothing.
**/
void DLISTtraverse(Dlist list, void (*callback)(const void *data), int direction);
#ifdef __cplusplus
}
#endif
#endif /* _DLIST_H_ */