doc
Main Page
Related Pages
Modules
Data Structures
Files
File List
Globals
src
std
c_list.h
Go to the documentation of this file.
1
/*
2
* c_list -- a doubly-linked list
3
*
4
* This code is based on glist.{h,c} from glib
5
* ftp://ftp.gtk.org/pub/gtk/
6
* Copyright (c) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
7
* Copyright (c) 2006-2008 Andreas Schneider <mail@csyncapses.org>
8
*
9
* This program is free software; you can redistribute it and/or
10
* modify it under the terms of the GNU General Public License
11
* as published by the Free Software Foundation; either version 2
12
* of the License, or (at your option) any later version.
13
*
14
* This program is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU General Public License for more details.
18
*
19
* You should have received a copy of the GNU General Public License
20
* along with this program; if not, write to the Free Software Foundation,
21
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22
*
23
* vim: ts=2 sw=2 et cindent
24
*/
25
26
#ifndef _C_LIST_H
27
#define _C_LIST_H
28
29
/**
30
* c_list -- a doubly-linked list.
31
*
32
* The c_list_t structure and its associated functions provide a standard
33
* doubly-linked list data structure. Each node has two links: one points to
34
* the previous node, or points to a null value or empty list if it is the
35
* first node; and one points to the next, or points to a null value or empty
36
* list if it is the final node.
37
*
38
* The data contained in each element can be simply pointers to any type of
39
* data. You are the owner of the data, this means you have to free the memory
40
* you have allocated for the data.
41
*
42
* @file c_list.h
43
*/
44
45
46
/**
47
* @typedef c_list_t
48
* Creates a type name for c_list_s
49
*/
50
typedef
struct
c_list_s
c_list_t
;
51
/**
52
* @struct c_list_s
53
*
54
* Used for each element in a doubly-linked list. The list can hold
55
* any kind of data.
56
*/
57
struct
c_list_s
{
58
/** Link to the next element in the list */
59
struct
c_list_s
*
next
;
60
/** Link to the previous element in the list */
61
struct
c_list_s
*
prev
;
62
63
/**
64
* Holds the element's data, which can be a pointer to any kind of
65
* data.
66
*/
67
void
*
data
;
68
};
69
70
/**
71
* Specifies the type of a comparison function used to compare two values. The
72
* value which should be returned depends on the context in which the
73
* c_list_compare_fn is used.
74
*
75
* @param a First parameter to compare with.
76
*
77
* @param b Second parameter to compare with.
78
*
79
* @return The function should return a number > 0 if the first
80
* parameter comes after the second parameter in the sort
81
* order.
82
*/
83
typedef
int (*
c_list_compare_fn
) (
const
void
*a,
const
void
*b);
84
85
/**
86
* Adds a new element on to the end of the list.
87
*
88
* @param list A pointer to c_list.
89
*
90
* @param data The data for the new element.
91
*
92
* @return New start of the list, which may have changed, so make
93
* sure you store the new value.
94
*/
95
c_list_t
*
c_list_append
(
c_list_t
*list,
void
*
data
);
96
97
/**
98
* Adds a new element on at the beginning of the list.
99
*
100
* @param list A pointer to c_list.
101
*
102
* @param data The data for the new element.
103
*
104
* @return New start of the list, which may have changed, so make
105
* sure you store the new value.
106
*/
107
c_list_t
*
c_list_prepend
(
c_list_t
*list,
void
*
data
);
108
109
/**
110
* Inserts a new element into the list at the given position. If the position
111
* is lesser than 0, the new element gets appended to the list, if the position
112
* is 0, we prepend the element and if the given position is greater than the
113
* length of the list, the element gets appended too.
114
*
115
* @param list A pointer to c_list.
116
*
117
* @param data The data for the new element.
118
*
119
* @param position The position to insert the element.
120
*
121
* @return New start of the list, which may have changed, so make
122
* sure you store the new value.
123
*/
124
c_list_t
*
c_list_insert
(
c_list_t
*list,
void
*
data
,
long
position);
125
126
/**
127
* Inserts a new element into the list, using the given comparison function to
128
* determine its position.
129
*
130
* @param list A pointer to c_list.
131
*
132
* @param data The data for the new element.
133
*
134
* @param fn The function to compare elements in the list. It
135
* should return a number > 0 if the first parameter comes
136
* after the second parameter in the sort order.
137
*
138
* @return New start of the list, which may have changed, so make
139
* sure you store the new value.
140
*/
141
c_list_t
*
c_list_insert_sorted
(
c_list_t
*list,
void
*
data
,
142
c_list_compare_fn
fn);
143
144
/**
145
* Allocates space for one c_list_t element.
146
*
147
* @return A pointer to the newly-allocated element.
148
*/
149
c_list_t
*
c_list_alloc
(
void
);
150
151
/**
152
* Removes an element from a c_list. If two elements contain the same data,
153
* only the first is removed.
154
*
155
* @param list A pointer to c_list.
156
*
157
* @param data The data of the element to remove.
158
*
159
* @return The first element of the list, NULL on error.
160
*/
161
c_list_t
*
c_list_remove
(
c_list_t
*list,
void
*
data
);
162
163
/**
164
* Frees all elements from a c_list.
165
*
166
* @param list A pointer to c_list.
167
*/
168
void
c_list_free
(
c_list_t
*list);
169
170
/**
171
* Gets the next element in a c_list.
172
*
173
* @param An element in a c_list.
174
*
175
* @return The next element, or NULL if there are no more
176
* elements.
177
*/
178
c_list_t
*
c_list_next
(
c_list_t
*list);
179
180
/**
181
* Gets the previous element in a c_list.
182
*
183
* @param An element in a c_list.
184
*
185
* @return The previous element, or NULL if there are no more
186
* elements.
187
*/
188
c_list_t
*
c_list_prev
(
c_list_t
*list);
189
190
/**
191
* Gets the number of elements in a c_list
192
*
193
* @param list A pointer to c_list.
194
*
195
* @return The number of elements
196
*/
197
unsigned
long
c_list_length
(
c_list_t
*list);
198
199
/**
200
* Gets the first element in a c_list
201
*
202
* @param list A pointer to c_list.
203
*
204
* @return New start of the list, which may have changed, so make
205
* sure you store the new value.
206
*/
207
c_list_t
*
c_list_first
(
c_list_t
*list);
208
209
/**
210
* Gets the last element in a c_list
211
*
212
* @param list A pointer to c_list.
213
*
214
* @return New start of the list, which may have changed, so make
215
* sure you store the new value.
216
*/
217
c_list_t
*
c_list_last
(
c_list_t
*list);
218
219
/**
220
* Gets the element at the given positon in a c_list.
221
*
222
* @param list A pointer to c_list.
223
*
224
* @param position The position of the element, counting from 0.
225
*
226
* @return New start of the list, which may have changed, so make
227
* sure you store the new value.
228
*/
229
c_list_t
*
c_list_position
(
c_list_t
*list,
long
position);
230
231
/**
232
* Finds the element in a c_list_t which contains the given data.
233
*
234
* @param list A pointer to c_list.
235
*
236
* @param data The data of the element to remove.
237
*
238
* @return The found element or NULL if it is not found.
239
*/
240
c_list_t
*
c_list_find
(
c_list_t
*list,
const
void
*
data
);
241
242
/**
243
* Finds an element, using a supplied function to find the desired
244
* element.
245
*
246
* @param list A pointer to c_list.
247
*
248
* @param data The data of the element to remove.
249
*
250
* @param func The function to call for each element. It should
251
* return 0 when the desired element is found.
252
*
253
* @return The found element or NULL if it is not found.
254
*/
255
c_list_t
*
c_list_find_custom
(
c_list_t
*list,
const
void
*
data
,
256
c_list_compare_fn
fn);
257
258
/**
259
* Sorts the elements of a c_list.
260
* The algorithm used is Mergesort, because that works really well
261
* on linked lists, without requiring the O(N) extra space it needs
262
* when you do it on arrays.
263
*
264
* @param list A pointer to c_list.
265
*
266
* @param func The comparison function used to sort the c_list. This
267
* function is passed 2 elements of the GList and should
268
* return 0 if they are equal, a negative value if the
269
* first element comes before the second, or a positive
270
* value if the first element comes after the second.
271
*
272
* @return New start of the list, which may have changed, so make
273
* sure you store the new value.
274
*/
275
c_list_t
*
c_list_sort
(
c_list_t
*list,
c_list_compare_fn
func);
276
277
#endif
/* _C_LIST_H */
278
Generated by
1.8.1