doc
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  */
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  */
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  */
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  */
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  */
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  */
276 
277 #endif /* _C_LIST_H */
278