2 * gslist.c: Singly-linked list implementation
5 * Duncan Mak (duncan@novell.com)
6 * Raja R Harinath (rharinath@novell.com)
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:
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
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.
27 * (C) 2006 Novell, Inc.
36 return g_new0 (GSList, 1);
40 g_slist_free_1 (GSList *list)
46 g_slist_append (GSList *list, gpointer data)
48 return g_slist_concat (list, g_slist_prepend (NULL, data));
51 /* This is also a list node constructor. */
53 g_slist_prepend (GSList *list, gpointer data)
55 GSList *head = g_slist_alloc ();
63 * Insert the given data in a new node after the current node.
66 static inline GSList *
67 insert_after (GSList *list, gpointer data)
69 list->next = g_slist_prepend (list->next, data);
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.
79 find_prev (GSList *list, gconstpointer data)
83 if (list->data == data)
91 /* like 'find_prev', but searches for node 'link' */
93 find_prev_link (GSList *list, GSList *link)
106 g_slist_insert_before (GSList *list, GSList *sibling, gpointer data)
108 GSList *prev = find_prev_link (list, sibling);
111 return g_slist_prepend (list, data);
113 insert_after (prev, data);
118 g_slist_free (GSList *list)
121 GSList *next = list->next;
122 g_slist_free_1 (list);
128 g_slist_copy (GSList *list)
135 copy = g_slist_prepend (NULL, list->data);
138 for (list = list->next; list; list = list->next)
139 tmp = insert_after (tmp, list->data);
145 g_slist_concat (GSList *list1, GSList *list2)
150 g_slist_last (list1)->next = list2;
155 g_slist_foreach (GSList *list, GFunc func, gpointer user_data)
158 (*func) (list->data, user_data);
164 g_slist_last (GSList *list)
176 g_slist_find (GSList *list, gconstpointer data)
178 for (; list; list = list->next)
179 if (list->data == data)
185 g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func)
191 if (func (list->data, data) == 0)
201 g_slist_length (GSList *list)
214 g_slist_remove (GSList *list, gconstpointer data)
216 GSList *prev = find_prev (list, data);
217 GSList *current = prev ? prev->next : list;
221 prev->next = current->next;
223 list = current->next;
224 g_slist_free_1 (current);
231 g_slist_remove_all (GSList *list, gconstpointer data)
238 GSList *tmp_prev = find_prev (next, data);
241 current = prev ? prev->next : list;
246 next = current->next;
252 g_slist_free_1 (current);
259 g_slist_remove_link (GSList *list, GSList *link)
261 GSList *prev = find_prev_link (list, link);
262 GSList *current = prev ? prev->next : list;
266 prev->next = current->next;
268 list = current->next;
269 current->next = NULL;
276 g_slist_delete_link (GSList *list, GSList *link)
278 list = g_slist_remove_link (list, link);
279 g_slist_free_1 (link);
285 g_slist_reverse (GSList *list)
289 GSList *next = list->next;
299 g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
306 if (!list || func (list->data, data) > 0)
307 return g_slist_prepend (list, data);
309 /* Invariant: func (prev->data, data) <= 0) */
310 for (prev = list; prev->next; prev = prev->next)
311 if (func (prev->next->data, data) > 0)
314 /* ... && (prev->next == 0 || func (prev->next->data, data) > 0)) */
315 insert_after (prev, data);
320 g_slist_index (GSList *list, gconstpointer data)
325 if (list->data == data)
336 g_slist_nth (GSList *list, guint n)
338 for (; list; list = list->next) {
347 g_slist_nth_data (GSList *list, guint n)
349 GSList *node = g_slist_nth (list, n);
350 return node ? node->data : NULL;
353 typedef GSList list_node;
354 #include "sort.frag.h"
357 g_slist_sort (GSList *list, GCompareFunc func)
359 if (!list || !list->next)
361 return do_sort (list, func);