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  */
47 typedef 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  */
54 struct 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  */
80 typedef 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  */
92 c_list_t *c_list_append(c_list_t *list, void *data);
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  */
104 c_list_t *c_list_prepend(c_list_t *list, void *data);
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  */
121 c_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  */
139  c_list_compare_fn fn);
140 
141 /**
142  * Allocates space for one c_list_t element.
143  *
144  * @return A pointer to the newly-allocated element.
145  */
146 c_list_t *c_list_alloc(void);
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  */
158 c_list_t *c_list_remove(c_list_t *list, void *data);
159 
160 /**
161  * Frees all elements from a c_list.
162  *
163  * @param list A pointer to c_list.
164  */
165 void c_list_free(c_list_t *list);
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  */
194 unsigned 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  */
226 c_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  */
237 c_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  */
252 c_list_t *c_list_find_custom(c_list_t *list, const void *data,
253  c_list_compare_fn fn);
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 
void * data
Holds the element&#39;s data, which can be a pointer to any kind of data.
Definition: c_list.h:64
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.
Used for each element in a doubly-linked list.
Definition: c_list.h:54
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.
void c_list_free(c_list_t *list)
Frees all elements 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_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_alloc(void)
Allocates space for one c_list_t element.
struct c_list_s * prev
Link to the previous element in the list.
Definition: c_list.h:58
c_list_t * c_list_append(c_list_t *list, void *data)
Adds a new element on to the end of the list.
c_list_t * c_list_last(c_list_t *list)
Gets the last element in a c_list.
c_list_t * c_list_sort(c_list_t *list, c_list_compare_fn func)
Sorts the elements of 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_next(c_list_t *list)
Gets the next element in a c_list.
c_list_t * c_list_prev(c_list_t *list)
Gets the previous element in 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_prepend(c_list_t *list, void *data)
Adds a new element on at the beginning of the list.
unsigned long c_list_length(c_list_t *list)
Gets the number of elements in a c_list.
c_list_t * c_list_position(c_list_t *list, long position)
Gets the element at the given positon in a c_list.
struct c_list_s * next
Link to the next element in the list.
Definition: c_list.h:56
c_list_t * c_list_first(c_list_t *list)
Gets the first element in a c_list.