milkway: steal the glist from glib

3 files changed, 1163 insertions, 0 deletions

diff --git a/milkway/Makefile.am b/milkway/Makefile.am
index cb053c9..df428cf 100644
--- a/milkway/Makefile.am
+++ b/milkway/Makefile.am
@@ -20,6 +20,7 @@ milkway_headers = \
 	mw-thread.h \
 	mw-object.h \
 	mw-connection-mgr.h \
+	mw-list.h \
 	mw-source.h
 
 libmilkway_la_LDFLAGS = -version-info  $(LT_VERSION_INFO) -no-undefined
@@ -48,6 +49,7 @@ libmilkway_la_SOURCES = \
 	mw-thread-private.c \
 	mw-object.c \
 	mw-connection-mgr.c \
+	mw-list.c \
 	mw-source.c
 
 milkwayincludedir = $(includedir)/milkway/milkway
diff --git a/milkway/mw-list.c b/milkway/mw-list.c
new file mode 100644
index 0000000..947bef5
--- /dev/null
+++ b/milkway/mw-list.c
@@ -0,0 +1,999 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
+
+/*
+ * MT safe
+ */
+
+#include "milkwayint.h"
+#include "milkway/mw-list.h"
+
+#include <stdlib.h>
+
+#define _mw_list_alloc()         malloc (sizeof(mw_list_t))
+#define _mw_list_alloc0()        calloc (1, sizeof(mw_list_t))
+#define _mw_list_free1(list)     free (list)
+
+mw_list_t*
+mw_list_alloc (void)
+{
+  return _mw_list_alloc0 ();
+}
+
+/**
+ * mw_list_free:
+ * @list: a #mw_list_t*
+ *
+ * Frees all of the memory used by a #mw_list_t*.
+ * The freed elements are returned to the slice allocator.
+ *
+ * <note><para>
+ * If list elements contain dynamically-allocated memory,
+ * they should be freed first.
+ * </para></note>
+ */
+void
+mw_list_free (mw_list_t *list)
+{
+  mw_list_t *last = list;
+  mw_list_t *next;
+
+  if (!list)
+    return;
+
+  for (;last; last = next) {
+      next = last->next;
+      _mw_list_free1 (last);
+  }
+}
+
+/**
+ * mw_list_free_1:
+ * @list: a #mw_list_t* element
+ *
+ * Frees one #mw_list_t* element.
+ * It is usually used after mw_list_remove_link().
+ */
+void
+mw_list_free_1 (mw_list_t *list)
+{
+  _mw_list_free1 (list);
+}
+
+/**
+ * mw_list_append:
+ * @list: a pointer to a #mw_list_t
+ * @data: the data for the new element
+ *
+ * Adds a new element on to the end of the list.
+ *
+ * <note><para>
+ * The return value is the new start of the list, which
+ * may have changed, so make sure you store the new value.
+ * </para></note>
+ *
+ * <note><para>
+ * Note that mw_list_append() has to traverse the entire list
+ * to find the end, which is inefficient when adding multiple
+ * elements. A common idiom to avoid the inefficiency is to prepend
+ * the elements and reverse the list when all elements have been added.
+ * </para></note>
+ *
+ * |[
+ * /&ast; Notice that these are initialized to the empty list. &ast;/
+ * mw_list_t *list = NULL, *number_list = NULL;
+ *
+ * /&ast; This is a list of strings. &ast;/
+ * list = mw_list_append (list, "first");
+ * list = mw_list_append (list, "second");
+ *
+ * /&ast; This is a list of integers. &ast;/
+ * number_list = mw_list_append (number_list, GINT_TO_POINTER (27));
+ * number_list = mw_list_append (number_list, GINT_TO_POINTER (14));
+ * ]|
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_append (mw_list_t	*list,
+		mw_pointer_t	 data)
+{
+  mw_list_t *new_list;
+  mw_list_t *last;
+
+  new_list = _mw_list_alloc ();
+  new_list->data = data;
+  new_list->next = NULL;
+
+  if (list)
+    {
+      last = mw_list_last (list);
+      /* mw_assert (last != NULL); */
+      last->next = new_list;
+      new_list->prev = last;
+
+      return list;
+    }
+  else
+    {
+      new_list->prev = NULL;
+      return new_list;
+    }
+}
+
+/**
+ * mw_list_prepend:
+ * @list: a pointer to a #mw_list_t
+ * @data: the data for the new element
+ *
+ * Adds a new element on to the start of the list.
+ *
+ * <note><para>
+ * The return value is the new start of the list, which
+ * may have changed, so make sure you store the new value.
+ * </para></note>
+ *
+ * |[
+ * /&ast; Notice that it is initialized to the empty list. &ast;/
+ * mw_list_t *list = NULL;
+ * list = mw_list_prepend (list, "last");
+ * list = mw_list_prepend (list, "first");
+ * ]|
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_prepend (mw_list_t	 *list,
+		mw_pointer_t  data)
+{
+  mw_list_t *new_list;
+
+  new_list = _mw_list_alloc ();
+  new_list->data = data;
+  new_list->next = list;
+
+  if (list)
+    {
+      new_list->prev = list->prev;
+      if (list->prev)
+	list->prev->next = new_list;
+      list->prev = new_list;
+    }
+  else
+    new_list->prev = NULL;
+
+  return new_list;
+}
+
+/**
+ * mw_list_insert:
+ * @list: a pointer to a #mw_list_t
+ * @data: the data for the new element
+ * @position: the position to insert the element. If this is
+ *     negative, or is larger than the number of elements in the
+ *     list, the new element is added on to the end of the list.
+ *
+ * Inserts a new element into the list at the given position.
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_insert (mw_list_t	*list,
+	       mw_pointer_t	 data,
+	       int	 position)
+{
+  mw_list_t *new_list;
+  mw_list_t *tmp_list;
+
+  if (position < 0)
+    return mw_list_append (list, data);
+  else if (position == 0)
+    return mw_list_prepend (list, data);
+
+  tmp_list = mw_list_nth (list, position);
+  if (!tmp_list)
+    return mw_list_append (list, data);
+
+  new_list = _mw_list_alloc ();
+  new_list->data = data;
+  new_list->prev = tmp_list->prev;
+  if (tmp_list->prev)
+    tmp_list->prev->next = new_list;
+  new_list->next = tmp_list;
+  tmp_list->prev = new_list;
+
+  if (tmp_list == list)
+    return new_list;
+  else
+    return list;
+}
+
+/**
+ * mw_list_insert_before:
+ * @list: a pointer to a #mw_list_t
+ * @sibling: the list element before which the new element
+ *     is inserted or %NULL to insert at the end of the list
+ * @data: the data for the new element
+ *
+ * Inserts a new element into the list before the given position.
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_insert_before (mw_list_t   *list,
+		      mw_list_t   *sibling,
+		      mw_pointer_t data)
+{
+  if (!list)
+    {
+      list = mw_list_alloc ();
+      list->data = data;
+      return list;
+    }
+  else if (sibling)
+    {
+      mw_list_t *node;
+
+      node = _mw_list_alloc ();
+      node->data = data;
+      node->prev = sibling->prev;
+      node->next = sibling;
+      sibling->prev = node;
+      if (node->prev)
+	{
+	  node->prev->next = node;
+	  return list;
+	}
+      else
+	{
+	  return node;
+	}
+    }
+  else
+    {
+      mw_list_t *last;
+
+      last = list;
+      while (last->next)
+	last = last->next;
+
+      last->next = _mw_list_alloc ();
+      last->next->data = data;
+      last->next->prev = last;
+      last->next->next = NULL;
+
+      return list;
+    }
+}
+
+/**
+ * mw_list_concat:
+ * @list1: a #mw_list_t
+ * @list2: the #mw_list_t to add to the end of the first #mw_list_t
+ *
+ * Adds the second #mw_list_t onto the end of the first #mw_list_t.
+ * Note that the elements of the second #mw_list_t are not copied.
+ * They are used directly.
+ *
+ * Returns: the start of the new #mw_list_t
+ */
+mw_list_t *
+mw_list_concat (mw_list_t *list1, mw_list_t *list2)
+{
+  mw_list_t *tmp_list;
+
+  if (list2)
+    {
+      tmp_list = mw_list_last (list1);
+      if (tmp_list)
+	tmp_list->next = list2;
+      else
+	list1 = list2;
+      list2->prev = tmp_list;
+    }
+
+  return list1;
+}
+
+/**
+ * mw_list_remove:
+ * @list: a #mw_list_t
+ * @data: the data of the element to remove
+ *
+ * Removes an element from a #mw_list_t.
+ * If two elements contain the same data, only the first is removed.
+ * If none of the elements contain the data, the #mw_list_t is unchanged.
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_remove (mw_list_t	     *list,
+	       const mw_pointer_t  data)
+{
+  mw_list_t *tmp;
+
+  tmp = list;
+  while (tmp)
+    {
+      if (tmp->data != data)
+	tmp = tmp->next;
+      else
+	{
+	  if (tmp->prev)
+	    tmp->prev->next = tmp->next;
+	  if (tmp->next)
+	    tmp->next->prev = tmp->prev;
+
+	  if (list == tmp)
+	    list = list->next;
+
+	  _mw_list_free1 (tmp);
+
+	  break;
+	}
+    }
+  return list;
+}
+
+/**
+ * mw_list_remove_all:
+ * @list: a #mw_list_t
+ * @data: data to remove
+ *
+ * Removes all list nodes with data equal to @data.
+ * Returns the new head of the list. Contrast with
+ * mw_list_remove() which removes only the first node
+ * matching the given data.
+ *
+ * Returns: new head of @list
+ */
+mw_list_t*
+mw_list_remove_all (mw_list_t	*list,
+		   const mw_pointer_t data)
+{
+  mw_list_t *tmp = list;
+
+  while (tmp)
+    {
+      if (tmp->data != data)
+	tmp = tmp->next;
+      else
+	{
+	  mw_list_t *next = tmp->next;
+
+	  if (tmp->prev)
+	    tmp->prev->next = next;
+	  else
+	    list = next;
+	  if (next)
+	    next->prev = tmp->prev;
+
+	  _mw_list_free1 (tmp);
+	  tmp = next;
+	}
+    }
+  return list;
+}
+
+static inline mw_list_t*
+_mw_list_remove_link (mw_list_t *list,
+		     mw_list_t *link)
+{
+  if (link)
+    {
+      if (link->prev)
+	link->prev->next = link->next;
+      if (link->next)
+	link->next->prev = link->prev;
+
+      if (link == list)
+	list = list->next;
+
+      link->next = NULL;
+      link->prev = NULL;
+    }
+
+  return list;
+}
+
+/**
+ * mw_list_remove_link:
+ * @list: a #mw_list_t
+ * @llink: an element in the #mw_list_t
+ *
+ * Removes an element from a #mw_list_t, without freeing the element.
+ * The removed element's prev and next links are set to %NULL, so
+ * that it becomes a self-contained list with one element.
+ *
+ * Returns: the new start of the #mw_list_t, without the element
+ */
+mw_list_t*
+mw_list_remove_link (mw_list_t *list,
+		    mw_list_t *llink)
+{
+  return _mw_list_remove_link (list, llink);
+}
+
+/**
+ * mw_list_delete_link:
+ * @list: a #mw_list_t
+ * @link_: node to delete from @list
+ *
+ * Removes the node link_ from the list and frees it.
+ * Compare this to mw_list_remove_link() which removes the node
+ * without freeing it.
+ *
+ * Returns: the new head of @list
+ */
+mw_list_t*
+mw_list_delete_link (mw_list_t *list,
+		    mw_list_t *link_)
+{
+  list = _mw_list_remove_link (list, link_);
+  _mw_list_free1 (link_);
+
+  return list;
+}
+
+/**
+ * mw_list_copy:
+ * @list: a #mw_list_t
+ *
+ * Copies a #mw_list_t.
+ *
+ * <note><para>
+ * Note that this is a "shallow" copy. If the list elements
+ * consist of pointers to data, the pointers are copied but
+ * the actual data is not.
+ * </para></note>
+ *
+ * Returns: a copy of @list
+ */
+mw_list_t*
+mw_list_copy (mw_list_t *list)
+{
+  mw_list_t *new_list = NULL;
+
+  if (list)
+    {
+      mw_list_t *last;
+
+      new_list = _mw_list_alloc ();
+      new_list->data = list->data;
+      new_list->prev = NULL;
+      last = new_list;
+      list = list->next;
+      while (list)
+	{
+	  last->next = _mw_list_alloc ();
+	  last->next->prev = last;
+	  last = last->next;
+	  last->data = list->data;
+	  list = list->next;
+	}
+      last->next = NULL;
+    }
+
+  return new_list;
+}
+
+/**
+ * mw_list_reverse:
+ * @list: a #mw_list_t
+ *
+ * Reverses a #mw_list_t.
+ * It simply switches the next and prev pointers of each element.
+ *
+ * Returns: the start of the reversed #mw_list_t
+ */
+mw_list_t*
+mw_list_reverse (mw_list_t *list)
+{
+  mw_list_t *last;
+
+  last = NULL;
+  while (list)
+    {
+      last = list;
+      list = last->next;
+      last->next = last->prev;
+      last->prev = list;
+    }
+
+  return last;
+}
+
+/**
+ * mw_list_nth:
+ * @list: a #mw_list_t
+ * @n: the position of the element, counting from 0
+ *
+ * Gets the element at the given position in a #mw_list_t.
+ *
+ * Returns: the element, or %NULL if the position is off
+ *     the end of the #mw_list_t
+ */
+mw_list_t*
+mw_list_nth (mw_list_t *list,
+	    mw_uint_t  n)
+{
+  while ((n-- > 0) && list)
+    list = list->next;
+
+  return list;
+}
+
+/**
+ * mw_list_nth_prev:
+ * @list: a #mw_list_t
+ * @n: the position of the element, counting from 0
+ *
+ * Gets the element @n places before @list.
+ *
+ * Returns: the element, or %NULL if the position is
+ *     off the end of the #mw_list_t
+ */
+mw_list_t*
+mw_list_nth_prev (mw_list_t *list,
+		 mw_uint_t  n)
+{
+  while ((n-- > 0) && list)
+    list = list->prev;
+
+  return list;
+}
+
+/**
+ * mw_list_nth_data:
+ * @list: a #mw_list_t
+ * @n: the position of the element
+ *
+ * Gets the data of the element at the given position.
+ *
+ * Returns: the element's data, or %NULL if the position
+ *     is off the end of the #mw_list_t
+ */
+mw_pointer_t
+mw_list_nth_data (mw_list_t     *list,
+		 mw_uint_t      n)
+{
+  while ((n-- > 0) && list)
+    list = list->next;
+
+  return list ? list->data : NULL;
+}
+
+/**
+ * mw_list_find:
+ * @list: a #mw_list_t
+ * @data: the element data to find
+ *
+ * Finds the element in a #mw_list_t which
+ * contains the given data.
+ *
+ * Returns: the found #mw_list_t element,
+ *     or %NULL if it is not found
+ */
+mw_list_t*
+mw_list_find (mw_list_t         *list,
+	     const mw_pointer_t  data)
+{
+  while (list)
+    {
+      if (list->data == data)
+	break;
+      list = list->next;
+    }
+
+  return list;
+}
+
+/**
+ * mw_list_find_custom:
+ * @list: a #mw_list_t
+ * @data: user data passed to the function
+ * @func: the function to call for each element.
+ *     It should return 0 when the desired element is found
+ *
+ * Finds an element in a #mw_list_t, using a supplied function to
+ * find the desired element. It iterates over the list, calling
+ * the given function which should return 0 when the desired
+ * element is found. The function takes two #const mw_pointer_t arguments,
+ * the #mw_list_t element's data as the first argument and the
+ * given user data.
+ *
+ * Returns: the found #mw_list_t element, or %NULL if it is not found
+ */
+mw_list_t*
+mw_list_find_custom (mw_list_t         *list,
+		    const mw_pointer_t  data,
+		    mw_compare_func_t   func)
+{
+  mw_assert (func != NULL);
+
+  while (list)
+    {
+      if (! func (list->data, data))
+	return list;
+      list = list->next;
+    }
+
+  return NULL;
+}
+
+
+/**
+ * mw_list_position:
+ * @list: a #mw_list_t
+ * @llink: an element in the #mw_list_t
+ *
+ * Gets the position of the given element
+ * in the #mw_list_t (starting from 0).
+ *
+ * Returns: the position of the element in the #mw_list_t,
+ *     or -1 if the element is not found
+ */
+int
+mw_list_position (mw_list_t *list,
+		 mw_list_t *llink)
+{
+  int i;
+
+  i = 0;
+  while (list)
+    {
+      if (list == llink)
+	return i;
+      i++;
+      list = list->next;
+    }
+
+  return -1;
+}
+
+/**
+ * mw_list_index:
+ * @list: a #mw_list_t
+ * @data: the data to find
+ *
+ * Gets the position of the element containing
+ * the given data (starting from 0).
+ *
+ * Returns: the index of the element containing the data,
+ *     or -1 if the data is not found
+ */
+int
+mw_list_index (mw_list_t         *list,
+	      const mw_pointer_t  data)
+{
+  int i;
+
+  i = 0;
+  while (list)
+    {
+      if (list->data == data)
+	return i;
+      i++;
+      list = list->next;
+    }
+
+  return -1;
+}
+
+/**
+ * mw_list_last:
+ * @list: a #mw_list_t
+ *
+ * Gets the last element in a #mw_list_t.
+ *
+ * Returns: the last element in the #mw_list_t,
+ *     or %NULL if the #mw_list_t has no elements
+ */
+mw_list_t*
+mw_list_last (mw_list_t *list)
+{
+  if (list)
+    {
+      while (list->next)
+	list = list->next;
+    }
+
+  return list;
+}
+
+/**
+ * mw_list_first:
+ * @list: a #mw_list_t
+ *
+ * Gets the first element in a #mw_list_t.
+ *
+ * Returns: the first element in the #mw_list_t,
+ *     or %NULL if the #mw_list_t has no elements
+ */
+mw_list_t*
+mw_list_first (mw_list_t *list)
+{
+  if (list)
+    {
+      while (list->prev)
+	list = list->prev;
+    }
+
+  return list;
+}
+
+/**
+ * mw_list_length:
+ * @list: a #mw_list_t
+ *
+ * Gets the number of elements in a #mw_list_t.
+ *
+ * <note><para>
+ * This function iterates over the whole list to
+ * count its elements.
+ * </para></note>
+ *
+ * Returns: the number of elements in the #mw_list_t
+ */
+mw_uint_t
+mw_list_length (mw_list_t *list)
+{
+  mw_uint_t length;
+
+  length = 0;
+  while (list)
+    {
+      length++;
+      list = list->next;
+    }
+
+  return length;
+}
+
+/**
+ * mw_list_foreach:
+ * @list: a #mw_list_t
+ * @func: the function to call with each element's data
+ * @user_data: user data to pass to the function
+ *
+ * Calls a function for each element of a #mw_list_t.
+ */
+void
+mw_list_foreach (mw_list_t	 *list,
+		mw_func_t	  func,
+		mw_pointer_t  user_data)
+{
+  while (list)
+    {
+      mw_list_t *next = list->next;
+      (*func) (list->data, user_data);
+      list = next;
+    }
+}
+
+static mw_list_t*
+mw_list_insert_sorted_real (mw_list_t    *list,
+			   mw_pointer_t  data,
+			   mw_func_t     func,
+			   mw_pointer_t  user_data)
+{
+  mw_list_t *tmp_list = list;
+  mw_list_t *new_list;
+  int cmp;
+
+  mw_assert (func != NULL);
+
+  if (!list)
+    {
+      new_list = _mw_list_alloc0 ();
+      new_list->data = data;
+      return new_list;
+    }
+
+  cmp = ((mw_compare_data_func_t) func) (data, tmp_list->data, user_data);
+
+  while ((tmp_list->next) && (cmp > 0))
+    {
+      tmp_list = tmp_list->next;
+
+      cmp = ((mw_compare_data_func_t) func) (data, tmp_list->data, user_data);
+    }
+
+  new_list = _mw_list_alloc0 ();
+  new_list->data = data;
+
+  if ((!tmp_list->next) && (cmp > 0))
+    {
+      tmp_list->next = new_list;
+      new_list->prev = tmp_list;
+      return list;
+    }
+
+  if (tmp_list->prev)
+    {
+      tmp_list->prev->next = new_list;
+      new_list->prev = tmp_list->prev;
+    }
+  new_list->next = tmp_list;
+  tmp_list->prev = new_list;
+
+  if (tmp_list == list)
+    return new_list;
+  else
+    return list;
+}
+
+/**
+ * mw_list_insert_sorted:
+ * @list: a pointer to a #mw_list_t
+ * @data: the data for the new element
+ * @func: the function to compare elements in the list. It should
+ *     return a number > 0 if the first parameter comes after the
+ *     second parameter in the sort order.
+ *
+ * Inserts a new element into the list, using the given comparison
+ * function to determine its position.
+ *
+ * Returns: the new start of the #mw_list_t
+ */
+mw_list_t*
+mw_list_insert_sorted (mw_list_t        *list,
+		      mw_pointer_t      data,
+		      mw_compare_func_t  func)
+{
+  return mw_list_insert_sorted_real (list, data, (mw_func_t) func, NULL);
+}
+
+/**
+ * mw_list_insert_sorted_with_data:
+ * @list: a pointer to a #mw_list_t
+ * @data: the data for the new element
+ * @func: the function to compare elements in the list.
+ *     It should return a number > 0 if the first parameter
+ *     comes after the second parameter in the sort order.
+ * @user_data: user data to pass to comparison function.
+ *
+ * Inserts a new element into the list, using the given comparison
+ * function to determine its position.
+ *
+ * Returns: the new start of the #mw_list_t
+ *
+ * Since: 2.10
+ */
+mw_list_t*
+mw_list_insert_sorted_with_data (mw_list_t            *list,
+				mw_pointer_t          data,
+				mw_compare_data_func_t  func,
+				mw_pointer_t          user_data)
+{
+  return mw_list_insert_sorted_real (list, data, (mw_func_t) func, user_data);
+}
+
+static mw_list_t *
+mw_list_sort_merge (mw_list_t     *l1,
+		   mw_list_t     *l2,
+		   mw_func_t     compare_func,
+		   mw_pointer_t  user_data)
+{
+  mw_list_t list, *l, *lprev;
+  int cmp;
+
+  l = &list;
+  lprev = NULL;
+
+  while (l1 && l2)
+    {
+      cmp = ((mw_compare_data_func_t) compare_func) (l1->data, l2->data, user_data);
+
+      if (cmp <= 0)
+        {
+	  l->next = l1;
+	  l1 = l1->next;
+        }
+      else
+	{
+	  l->next = l2;
+	  l2 = l2->next;
+        }
+      l = l->next;
+      l->prev = lprev;
+      lprev = l;
+    }
+  l->next = l1 ? l1 : l2;
+  l->next->prev = l;
+
+  return list.next;
+}
+
+static mw_list_t*
+mw_list_sort_real (mw_list_t    *list,
+		  mw_func_t     compare_func,
+		  mw_pointer_t  user_data)
+{
+  mw_list_t *l1, *l2;
+
+  if (!list)
+    return NULL;
+  if (!list->next)
+    return list;
+
+  l1 = list;
+  l2 = list->next;
+
+  while ((l2 = l2->next) != NULL)
+    {
+      if ((l2 = l2->next) == NULL)
+	break;
+      l1 = l1->next;
+    }
+  l2 = l1->next;
+  l1->next = NULL;
+
+  return mw_list_sort_merge (mw_list_sort_real (list, compare_func, user_data),
+			    mw_list_sort_real (l2, compare_func, user_data),
+			    compare_func,
+			    user_data);
+}
+
+/**
+ * mw_list_sort:
+ * @list: a #mw_list_t
+ * @compare_func: the comparison function used to sort the #mw_list_t.
+ *     This function is passed the data from 2 elements of the #mw_list_t
+ *     and should return 0 if they are equal, a negative value if the
+ *     first element comes before the second, or a positive value if
+ *     the first element comes after the second.
+ *
+ * Sorts a #mw_list_t using the given comparison function.
+ *
+ * Returns: the start of the sorted #mw_list_t
+ */
+mw_list_t*
+mw_list_sort (mw_list_t        *list,
+	     mw_compare_func_t  compare_func)
+{
+  return mw_list_sort_real (list, (mw_func_t) compare_func, NULL);
+
+}
+
+/**
+ * mw_list_sort_with_data:
+ * @list: a #mw_list_t
+ * @compare_func: comparison function
+ * @user_data: user data to pass to comparison function
+ *
+ * Like mw_list_sort(), but the comparison function accepts
+ * a user data argument.
+ *
+ * Returns: the new head of @list
+ */
+mw_list_t*
+mw_list_sort_with_data (mw_list_t             *list,
+		       mw_compare_data_func_t  compare_func,
+		       mw_pointer_t            user_data)
+{
+  return mw_list_sort_real (list, (mw_func_t) compare_func, user_data);
+}
diff --git a/milkway/mw-list.h b/milkway/mw-list.h
new file mode 100644
index 0000000..20cdf63
--- /dev/null
+++ b/milkway/mw-list.h
@@ -0,0 +1,162 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
+
+#ifndef __MW_LIST_H__
+#define __MW_LIST_H__
+
+MW_BEGIN_DECLS
+
+typedef struct _mw_list mw_list_t;
+struct _mw_list
+{
+    void *data;
+    mw_list_t *next;
+    mw_list_t *prev;
+};
+
+/* Doubly linked lists
+ */
+mw_public mw_list_t*
+mw_list_alloc(void);
+
+mw_public void
+mw_list_free                    (mw_list_t            *list);
+
+mw_public void
+mw_list_free_1                  (mw_list_t            *list);
+
+mw_public mw_list_t*
+mw_list_append                  (mw_list_t          *list,
+				 mw_pointer_t        data);
+
+mw_public mw_list_t*
+mw_list_prepend                 (mw_list_t          *list,
+				 mw_pointer_t          data);
+mw_public mw_list_t*
+mw_list_insert                  (mw_list_t           *list,
+				 mw_pointer_t        data,
+				 mw_int_t            position);
+mw_public mw_list_t*
+mw_list_insert_sorted           (mw_list_t          *list,
+				 mw_pointer_t        data,
+				 mw_compare_func_t   func);
+
+mw_public mw_list_t*
+mw_list_insert_sorted_with_data (mw_list_t             *list,
+				 mw_pointer_t           data,
+				 mw_compare_data_func_t func,
+				 mw_pointer_t           user_data);
+
+mw_public mw_list_t*
+mw_list_insert_before           (mw_list_t            *list,
+				 mw_list_t            *sibling,
+				 mw_pointer_t          data);
+
+mw_public mw_list_t*
+mw_list_concat                  (mw_list_t            *list1,
+				 mw_list_t            *list2);
+
+mw_public mw_list_t*
+mw_list_remove                  (mw_list_t            *list,
+				 const mw_pointer_t  data);
+
+mw_public mw_list_t*
+mw_list_remove_all              (mw_list_t            *list,
+				 const mw_pointer_t  data);
+
+mw_public mw_list_t*
+mw_list_remove_link             (mw_list_t            *list,
+				 mw_list_t            *llink);
+
+mw_public mw_list_t*
+mw_list_delete_link             (mw_list_t            *list,
+				 mw_list_t            *link_);
+
+mw_public mw_list_t*
+mw_list_reverse                 (mw_list_t            *list);
+
+mw_public mw_list_t*
+mw_list_copy                    (mw_list_t            *list);
+
+mw_public mw_list_t*
+mw_list_nth                     (mw_list_t         *list,
+				 mw_uint_t          n);
+
+mw_public mw_list_t*
+mw_list_nth_prev                (mw_list_t          *list,
+				 mw_uint_t          n);
+
+mw_public mw_list_t*
+mw_list_find                    (mw_list_t          *list,
+				 const mw_pointer_t  data);
+
+mw_public mw_list_t*
+mw_list_find_custom             (mw_list_t          *list,
+				 const mw_pointer_t  data,
+				 mw_compare_func_t   func);
+
+mw_public int
+mw_list_position                (mw_list_t            *list,
+				 mw_list_t            *llink);
+
+mw_public int
+mw_list_index                   (mw_list_t            *list,
+				 const mw_pointer_t  data);
+
+mw_public mw_list_t*
+mw_list_last                    (mw_list_t            *list);
+
+mw_public mw_list_t*
+mw_list_first                   (mw_list_t            *list);
+
+mw_public mw_uint_t
+mw_list_length                  (mw_list_t            *list);
+
+mw_public void
+mw_list_foreach                 (mw_list_t            *list,
+				 mw_func_t           func,
+				 mw_pointer_t         user_data);
+
+mw_public mw_list_t*
+mw_list_sort                    (mw_list_t            *list,
+				 mw_compare_func_t   compare_func);
+
+mw_public mw_list_t*
+mw_list_sort_with_data          (mw_list_t                *list,
+				 mw_compare_data_func_t  compare_func,
+				 mw_pointer_t            user_data);
+
+mw_public mw_pointer_t
+mw_list_nth_data                (mw_list_t            *list,
+				 mw_uint_t           n);
+
+
+#define mw_list_previous(list)	        ((list) ? (((mw_list *)(list))->prev) : NULL)
+#define mw_list_next(list)	        ((list) ? (((mw_list *)(list))->next) : NULL)
+
+MW_END_DECLS
+
+#endif /* __MW_LIST_H__ */