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