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_all (GList *list, gconstpointer data)
131 GList *current = g_list_find (list, data);
139 g_list_free_1 (disconnect_node (current));
141 current = g_list_find (list, data);
148 g_list_remove_link (GList *list, GList *link)
153 disconnect_node (link);
161 g_list_delete_link (GList *list, GList *link)
163 list = g_list_remove_link (list, link);
164 g_list_free_1 (link);
170 g_list_find (GList *list, gconstpointer data)
173 if (list->data == data)
183 g_list_find_custom (GList *list, gconstpointer data, GCompareFunc func)
189 if (func (list->data, data) == 0)
199 g_list_reverse (GList *list)
201 GList *reverse = NULL;
205 list = reverse->next;
207 reverse->next = reverse->prev;
208 reverse->prev = list;
215 g_list_first (GList *list)
227 g_list_last (GList *list)
239 g_list_insert_sorted (GList *list, gpointer data, GCompareFunc func)
248 /* Invariant: !prev || func (prev->data, data) <= 0) */
249 for (current = list; current; current = current->next) {
250 if (func (current->data, data) > 0)
255 node = new_node (prev, data, current);
256 return list == current ? node : list;
260 g_list_insert_before (GList *list, GList *sibling, gpointer data)
263 GList *node = new_node (sibling->prev, data, sibling);
264 return list == sibling ? node : list;
266 return g_list_append (list, data);
270 g_list_foreach (GList *list, GFunc func, gpointer user_data)
273 (*func) (list->data, user_data);
279 g_list_index (GList *list, gconstpointer data)
284 if (list->data == data)
295 g_list_nth (GList *list, guint n)
297 for (; list; list = list->next) {
306 g_list_nth_data (GList *list, guint n)
308 GList *node = g_list_nth (list, n);
309 return node ? node->data : NULL;
313 g_list_copy (GList *list)
318 GList *tmp = new_node (NULL, list->data, NULL);
321 for (list = list->next; list; list = list->next)
322 tmp = new_node (tmp, list->data, NULL);
328 typedef GList list_node;
329 #include "sort.frag.h"
332 g_list_sort (GList *list, GCompareFunc func)
335 if (!list || !list->next)
337 list = do_sort (list, func);
339 /* Fixup: do_sort doesn't update 'prev' pointers */
341 for (current = list; current->next; current = current->next)
342 current->next->prev = current;