/*
* gslist.c: Singly-linked list implementation
*
- * Author:
- * Duncan Mak (duncan@a-chinaman.com)
+ * Authors:
+ * Duncan Mak (duncan@novell.com)
+ * Raja R Harinath (rharinath@novell.com)
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
* (C) 2006 Novell, Inc.
*/
return head;
}
+/*
+ * Insert the given data in a new node after the current node.
+ * Return new node.
+ */
+static inline GSList *
+insert_after (GSList *list, gpointer data)
+{
+ list->next = g_slist_prepend (list->next, data);
+ return list->next;
+}
+
+/*
+ * Return the node prior to the node containing 'data'.
+ * If the list is empty, or the first node contains 'data', return NULL.
+ * If no node contains 'data', return the last node.
+ */
+static inline GSList*
+find_prev (GSList *list, gconstpointer data)
+{
+ GSList *prev = NULL;
+ while (list) {
+ if (list->data == data)
+ break;
+ prev = list;
+ list = list->next;
+ }
+ return prev;
+}
+
+/* like 'find_prev', but searches for node 'link' */
+static inline GSList*
+find_prev_link (GSList *list, GSList *link)
+{
+ GSList *prev = NULL;
+ while (list) {
+ if (list == link)
+ break;
+ prev = list;
+ list = list->next;
+ }
+ return prev;
+}
+
+GSList*
+g_slist_insert_before (GSList *list, GSList *sibling, gpointer data)
+{
+ GSList *prev = find_prev_link (list, sibling);
+
+ if (!prev)
+ return g_slist_prepend (list, data);
+
+ insert_after (prev, data);
+ return list;
+}
+
void
g_slist_free (GSList *list)
{
- GSList *next;
while (list) {
- next = list->next;
+ GSList *next = list->next;
g_slist_free_1 (list);
list = next;
}
copy = g_slist_prepend (NULL, list->data);
tmp = copy;
- while (list->next) {
- tmp->next = g_slist_prepend (NULL, list->next->data);
-
- tmp = tmp->next;
- list = list->next;
- }
+ for (list = list->next; list; list = list->next)
+ tmp = insert_after (tmp, list->data);
return copy;
}
GSList*
g_slist_concat (GSList *list1, GSList *list2)
{
- if (list1)
- g_slist_last (list1)->next = list2;
- else
- list1 = list2;
+ if (!list1)
+ return list2;
+ g_slist_last (list1)->next = list2;
return list1;
}
return list;
}
+
+GSList*
+g_slist_find (GSList *list, gconstpointer data)
+{
+ for (; list; list = list->next)
+ if (list->data == data)
+ break;
+ return list;
+}
+
+GSList *
+g_slist_find_custom (GSList *list, gconstpointer data, GCompareFunc func)
+{
+ if (!func)
+ return NULL;
+
+ while (list) {
+ if (func (list->data, data) == 0)
+ return list;
+
+ list = list->next;
+ }
+
+ return NULL;
+}
+
+guint
+g_slist_length (GSList *list)
+{
+ guint length = 0;
+
+ while (list) {
+ length ++;
+ list = list->next;
+ }
+
+ return length;
+}
+
+GSList*
+g_slist_remove (GSList *list, gconstpointer data)
+{
+ GSList *prev = find_prev (list, data);
+ GSList *current = prev ? prev->next : list;
+
+ if (current) {
+ if (prev)
+ prev->next = current->next;
+ else
+ list = current->next;
+ g_slist_free_1 (current);
+ }
+
+ return list;
+}
+
+GSList*
+g_slist_remove_all (GSList *list, gconstpointer data)
+{
+ GSList *next = list;
+ GSList *prev = NULL;
+ GSList *current;
+
+ while (next) {
+ GSList *tmp_prev = find_prev (next, data);
+ if (tmp_prev)
+ prev = tmp_prev;
+ current = prev ? prev->next : list;
+
+ if (!current)
+ break;
+
+ next = current->next;
+
+ if (prev)
+ prev->next = next;
+ else
+ list = next;
+ g_slist_free_1 (current);
+ }
+
+ return list;
+}
+
+GSList*
+g_slist_remove_link (GSList *list, GSList *link)
+{
+ GSList *prev = find_prev_link (list, link);
+ GSList *current = prev ? prev->next : list;
+
+ if (current) {
+ if (prev)
+ prev->next = current->next;
+ else
+ list = current->next;
+ current->next = NULL;
+ }
+
+ return list;
+}
+
+GSList*
+g_slist_delete_link (GSList *list, GSList *link)
+{
+ list = g_slist_remove_link (list, link);
+ g_slist_free_1 (link);
+
+ return list;
+}
+
+GSList*
+g_slist_reverse (GSList *list)
+{
+ GSList *prev = NULL;
+ while (list){
+ GSList *next = list->next;
+ list->next = prev;
+ prev = list;
+ list = next;
+ }
+
+ return prev;
+}
+
+GSList*
+g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)
+{
+ GSList *prev = NULL;
+
+ if (!func)
+ return list;
+
+ if (!list || func (list->data, data) > 0)
+ return g_slist_prepend (list, data);
+
+ /* Invariant: func (prev->data, data) <= 0) */
+ for (prev = list; prev->next; prev = prev->next)
+ if (func (prev->next->data, data) > 0)
+ break;
+
+ /* ... && (prev->next == 0 || func (prev->next->data, data) > 0)) */
+ insert_after (prev, data);
+ return list;
+}
+
+gint
+g_slist_index (GSList *list, gconstpointer data)
+{
+ gint index = 0;
+
+ while (list) {
+ if (list->data == data)
+ return index;
+
+ index++;
+ list = list->next;
+ }
+
+ return -1;
+}
+
+GSList*
+g_slist_nth (GSList *list, guint n)
+{
+ for (; list; list = list->next) {
+ if (n == 0)
+ break;
+ n--;
+ }
+ return list;
+}
+
+gpointer
+g_slist_nth_data (GSList *list, guint n)
+{
+ GSList *node = g_slist_nth (list, n);
+ return node ? node->data : NULL;
+}
+
+typedef GSList list_node;
+#include "sort.frag.h"
+
+GSList*
+g_slist_sort (GSList *list, GCompareFunc func)
+{
+ if (!list || !list->next)
+ return list;
+ return do_sort (list, func);
+}
projects / mono.git / blobdiff