2 * glist.c: Doubly-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.
35 return g_new0 (GList, 1);
39 new_node (GList *prev, gpointer data, GList *next)
41 GList *node = g_list_alloc ();
53 disconnect_node (GList *node)
56 node->next->prev = node->prev;
58 node->prev->next = node->next;
63 g_list_prepend (GList *list, gpointer data)
65 return new_node (list ? list->prev : NULL, data, list);
69 g_list_free_1 (GList *list)
75 g_list_free (GList *list)
78 GList *next = list->next;
85 g_list_append (GList *list, gpointer data)
87 GList *node = new_node (g_list_last (list), data, NULL);
88 return list ? list : node;
92 g_list_concat (GList *list1, GList *list2)
95 list2->prev = g_list_last (list1);
96 list2->prev->next = list2;
98 return list1 ? list1 : list2;
102 g_list_length (GList *list)
115 g_list_remove (GList *list, gconstpointer data)
117 GList *current = g_list_find (list, data);
123 g_list_free_1 (disconnect_node (current));
129 g_list_remove_link (GList *list, GList *link)
134 disconnect_node (link);
142 g_list_delete_link (GList *list, GList *link)
144 list = g_list_remove_link (list, link);
145 g_list_free_1 (link);
151 g_list_find (GList *list, gconstpointer data)
154 if (list->data == data)
164 g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func)
170 if (func (list->data, data) == 0)
180 g_list_reverse (GList *list)
182 GList *reverse = NULL;
186 list = reverse->next;
188 reverse->next = reverse->prev;
189 reverse->prev = list;
196 g_list_first (GList *list)
208 g_list_last (GList *list)
220 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
229 /* Invariant: !prev || func (prev->data, data) <= 0) */
230 for (current = list; current; current = current->next) {
231 if (func (current->data, data) > 0)
236 node = new_node (prev, data, current);
237 return list == current ? node : list;
241 g_list_insert_before (GList *list, GList *sibling, gpointer data)
244 GList *node = new_node (sibling->prev, data, sibling);
245 return list == sibling ? node : list;
247 return g_list_append (list, data);
251 g_list_foreach (GList *list, GFunc func, gpointer user_data)
254 (*func) (list->data, user_data);
260 g_list_index (GList *list, gconstpointer data)
265 if (list->data == data)
276 g_list_nth (GList *list, guint n)
278 for (; list; list = list->next) {
287 g_list_nth_data (GList *list, guint n)
289 GList *node = g_list_nth (list, n);
290 return node ? node->data : NULL;
294 g_list_copy (GList *list)
299 GList *tmp = new_node (NULL, list->data, NULL);
302 for (list = list->next; list; list = list->next)
303 tmp = new_node (tmp, list->data, NULL);
309 typedef GList list_node;
310 #include "sort.frag.h"
313 g_list_sort (GList *list, GCompareFunc func)
316 if (!list || !list->next)
318 list = do_sort (list, func);
320 /* Fixup: do_sort doesn't update 'prev' pointers */
322 for (current = list; current->next; current = current->next)
323 current->next->prev = current;