From 4b61b9a2d67e8f011840c95d20deef096c2e51a3 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Sat, 1 May 2010 15:55:00 -0600
Subject: Fix list sorting.

---
 libdimension/dimension/list.h | 15 ++++++++-------
 libdimension/list.c           | 19 +++++++++++++++++--
 2 files changed, 25 insertions(+), 9 deletions(-)

(limited to 'libdimension')

diff --git a/libdimension/dimension/list.h b/libdimension/dimension/list.h
index 8143e8b..0b68e91 100644
--- a/libdimension/dimension/list.h
+++ b/libdimension/dimension/list.h
@@ -133,9 +133,9 @@ dmnsn_list_set(dmnsn_list_iterator *i, const void *obj)
 DMNSN_INLINE void
 dmnsn_list_swap(dmnsn_list_iterator *a, dmnsn_list_iterator *b)
 {
-  dmnsn_list_iterator temp = *a;
-  *a = *b;
-  *b = temp;
+  void *temp = a->ptr;
+  a->ptr = b->ptr;
+  b->ptr = temp;
 }
 
 /* Insert `j' before `i' */
@@ -150,13 +150,12 @@ dmnsn_list_iterator_insert(dmnsn_list *list,
     j->prev = i->prev;
     i->prev = j;
   } else {
-    if (list->last) {
-      j->prev = list->last;
-      j->prev->next = j;
-    }
+    j->prev = list->last;
     list->last = j;
   }
 
+  if (j->prev)
+    j->prev->next = j;
   j->next = i;
   ++list->length;
 }
@@ -183,6 +182,8 @@ dmnsn_list_iterator_remove(dmnsn_list *list, dmnsn_list_iterator *i)
     i->prev->next = i->next;
   if (i->next)
     i->next->prev = i->prev;
+  i->prev = NULL;
+  i->next = NULL;
   --list->length;
 }
 
diff --git a/libdimension/list.c b/libdimension/list.c
index f6a1f5d..4851e94 100644
--- a/libdimension/list.c
+++ b/libdimension/list.c
@@ -66,7 +66,6 @@ dmnsn_list_split(dmnsn_list *list)
 
   list->length -= max;
   half->length = max;
-
   return half;
 }
 
@@ -84,10 +83,26 @@ dmnsn_list_sort(dmnsn_list *list, dmnsn_comparator_fn *comparator)
     dmnsn_list *half = dmnsn_list_split(list);
     dmnsn_list_sort(list, comparator);
     dmnsn_list_sort(half, comparator);
+    dmnsn_list_iterator *ii;
 
     dmnsn_list_iterator *i = list->first, *j = half->first;
     while (i || j) {
-      if (!i || (*comparator)(j, i)) {
+      if (!i) {
+        dmnsn_list_iterator *temp = dmnsn_list_next(j);
+        dmnsn_list_iterator_remove(half, j);
+        dmnsn_list_iterator_insert(list, i, j);
+        j = temp;
+        continue;
+
+        j->prev = list->last;
+        list->last = j;
+        list->length += half->length;
+        half->first = half->last = NULL;
+        half->length = 0;
+        break;
+      } else if (!j) {
+        break;
+      } else if ((*comparator)(j, i)) {
         dmnsn_list_iterator *temp = dmnsn_list_next(j);
         dmnsn_list_iterator_remove(half, j);
         dmnsn_list_iterator_insert(list, i, j);
-- 
cgit v1.2.3