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
);