1 /*
2 * gslist.c: Singly-linked list implementation
3 *
4 * Authors:
5 * Duncan Mak (duncan@novell.com)
6 * Raja R Harinath (rharinath@novell.com)
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining
9 * a copy of this software and associated documentation files (the
10 * "Software"), to deal in the Software without restriction, including
11 * without limitation the rights to use, copy, modify, merge, publish,
12 * distribute, sublicense, and/or sell copies of the Software, and to
13 * permit persons to whom the Software is furnished to do so, subject to
14 * the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
23 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
24 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
25 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 *
27 * (C) 2006 Novell, Inc.
28 */
29
30 #include <stdio.h>
31 #include <glib.h>
32
33 GSList*
g_slist_alloc(void)34 g_slist_alloc (void)
35 {
36 return g_new0 (GSList, 1);
37 }
38
39 void
g_slist_free_1(GSList * list)40 g_slist_free_1 (GSList *list)
41 {
42 g_free (list);
43 }
44
45 GSList*
g_slist_append(GSList * list,gpointer data)46 g_slist_append (GSList *list, gpointer data)
47 {
48 return g_slist_concat (list, g_slist_prepend (NULL, data));
49 }
50
51 /* This is also a list node constructor. */
52 GSList*
g_slist_prepend(GSList * list,gpointer data)53 g_slist_prepend (GSList *list, gpointer data)
54 {
55 GSList *head = g_slist_alloc ();
56 head->data = data;
57 head->next = list;
58
59 return head;
60 }
61
62 /*
63 * Insert the given data in a new node after the current node.
64 * Return new node.
65 */
66 static inline GSList *
insert_after(GSList * list,gpointer data)67 insert_after (GSList *list, gpointer data)
68 {
69 list->next = g_slist_prepend (list->next, data);
70 return list->next;
71 }
72
73 /*
74 * Return the node prior to the node containing 'data'.
75 * If the list is empty, or the first node contains 'data', return NULL.
76 * If no node contains 'data', return the last node.
77 */
78 static inline GSList*
find_prev(GSList * list,gconstpointer data)79 find_prev (GSList *list, gconstpointer data)
80 {
81 GSList *prev = NULL;
82 while (list) {
83 if (list->data == data)
84 break;
85 prev = list;
86 list = list->next;
87 }
88 return prev;
89 }
90
91 /* like 'find_prev', but searches for node 'link' */
92 static inline GSList*
find_prev_link(GSList * list,GSList * link)93 find_prev_link (GSList *list, GSList *link)
94 {
95 GSList *prev = NULL;
96 while (list) {
97 if (list == link)
98 break;
99 prev = list;
100 list = list->next;
101 }
102 return prev;
103 }
104
105 GSList*
g_slist_insert_before(GSList * list,GSList * sibling,gpointer data)106 g_slist_insert_before (GSList *list, GSList *sibling, gpointer data)
107 {
108 GSList *prev = find_prev_link (list, sibling);
109
110 if (!prev)
111 return g_slist_prepend (list, data);
112
113 insert_after (prev, data);
114 return list;
115 }
116
117 void
g_slist_free(GSList * list)118 g_slist_free (GSList *list)
119 {
120 while (list) {
121 GSList *next = list->next;
122 g_slist_free_1 (list);
123 list = next;
124 }
125 }
126
127 GSList*
g_slist_copy(GSList * list)128 g_slist_copy (GSList *list)
129 {
130 GSList *copy, *tmp;
131
132 if (!list)
133 return NULL;
134
135 copy = g_slist_prepend (NULL, list->data);
136 tmp = copy;
137
138 for (list = list->next; list; list = list->next)
139 tmp = insert_after (tmp, list->data);
140
141 return copy;
142 }
143
144 GSList*
g_slist_concat(GSList * list1,GSList * list2)145 g_slist_concat (GSList *list1, GSList *list2)
146 {
147 if (!list1)
148 return list2;
149
150 g_slist_last (list1)->next = list2;
151 return list1;
152 }
153
154 void
g_slist_foreach(GSList * list,GFunc func,gpointer user_data)155 g_slist_foreach (GSList *list, GFunc func, gpointer user_data)
156 {
157 while (list) {
158 (*func) (list->data, user_data);
159 list = list->next;
160 }
161 }
162
163 GSList*
g_slist_last(GSList * list)164 g_slist_last (GSList *list)
165 {
166 if (!list)
167 return NULL;
168
169 while (list->next)
170 list = list->next;
171
172 return list;
173 }
174
175 GSList*
g_slist_find(GSList * list,gconstpointer data)176 g_slist_find (GSList *list, gconstpointer data)
177 {
178 for (; list; list = list->next)
179 if (list->data == data)
180 break;
181 return list;
182 }
183
184 GSList *
g_slist_find_custom(GSList * list,gconstpointer data,GCompareFunc func)185 g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func)
186 {
187 if (!func)
188 return NULL;
189
190 while (list) {
191 if (func (list->data, data) == 0)
192 return list;
193
194 list = list->next;
195 }
196
197 return NULL;
198 }
199
200 guint
g_slist_length(GSList * list)201 g_slist_length (GSList *list)
202 {
203 guint length = 0;
204
205 while (list) {
206 length ++;
207 list = list->next;
208 }
209
210 return length;
211 }
212
213 GSList*
g_slist_remove(GSList * list,gconstpointer data)214 g_slist_remove (GSList *list, gconstpointer data)
215 {
216 GSList *prev = find_prev (list, data);
217 GSList *current = prev ? prev->next : list;
218
219 if (current) {
220 if (prev)
221 prev->next = current->next;
222 else
223 list = current->next;
224 g_slist_free_1 (current);
225 }
226
227 return list;
228 }
229
230 GSList*
g_slist_remove_all(GSList * list,gconstpointer data)231 g_slist_remove_all (GSList *list, gconstpointer data)
232 {
233 GSList *next = list;
234 GSList *prev = NULL;
235 GSList *current;
236
237 while (next) {
238 GSList *tmp_prev = find_prev (next, data);
239 if (tmp_prev)
240 prev = tmp_prev;
241 current = prev ? prev->next : list;
242
243 if (!current)
244 break;
245
246 next = current->next;
247
248 if (prev)
249 prev->next = next;
250 else
251 list = next;
252 g_slist_free_1 (current);
253 }
254
255 return list;
256 }
257
258 GSList*
g_slist_remove_link(GSList * list,GSList * link)259 g_slist_remove_link (GSList *list, GSList *link)
260 {
261 GSList *prev = find_prev_link (list, link);
262 GSList *current = prev ? prev->next : list;
263
264 if (current) {
265 if (prev)
266 prev->next = current->next;
267 else
268 list = current->next;
269 current->next = NULL;
270 }
271
272 return list;
273 }
274
275 GSList*
g_slist_delete_link(GSList * list,GSList * link)276 g_slist_delete_link (GSList *list, GSList *link)
277 {
278 list = g_slist_remove_link (list, link);
279 g_slist_free_1 (link);
280
281 return list;
282 }
283
284 GSList*
g_slist_reverse(GSList * list)285 g_slist_reverse (GSList *list)
286 {
287 GSList *prev = NULL;
288 while (list){
289 GSList *next = list->next;
290 list->next = prev;
291 prev = list;
292 list = next;
293 }
294
295 return prev;
296 }
297
298 GSList*
g_slist_insert_sorted(GSList * list,gpointer data,GCompareFunc func)299 g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
300 {
301 GSList *prev = NULL;
302
303 if (!func)
304 return list;
305
306 if (!list || func (list->data, data) > 0)
307 return g_slist_prepend (list, data);
308
309 /* Invariant: func (prev->data, data) <= 0) */
310 for (prev = list; prev->next; prev = prev->next)
311 if (func (prev->next->data, data) > 0)
312 break;
313
314 /* ... && (prev->next == 0 || func (prev->next->data, data) > 0)) */
315 insert_after (prev, data);
316 return list;
317 }
318
319 gint
g_slist_index(GSList * list,gconstpointer data)320 g_slist_index (GSList *list, gconstpointer data)
321 {
322 gint index = 0;
323
324 while (list) {
325 if (list->data == data)
326 return index;
327
328 index++;
329 list = list->next;
330 }
331
332 return -1;
333 }
334
335 GSList*
g_slist_nth(GSList * list,guint n)336 g_slist_nth (GSList *list, guint n)
337 {
338 for (; list; list = list->next) {
339 if (n == 0)
340 break;
341 n--;
342 }
343 return list;
344 }
345
346 gpointer
g_slist_nth_data(GSList * list,guint n)347 g_slist_nth_data (GSList *list, guint n)
348 {
349 GSList *node = g_slist_nth (list, n);
350 return node ? node->data : NULL;
351 }
352
353 typedef GSList list_node;
354 #include "sort.frag.h"
355
356 GSList*
g_slist_sort(GSList * list,GCompareFunc func)357 g_slist_sort (GSList *list, GCompareFunc func)
358 {
359 if (!list || !list->next)
360 return list;
361 return do_sort (list, func);
362 }
363