summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--libdimension/dimension/list.h15
-rw-r--r--libdimension/list.c19
2 files changed, 25 insertions, 9 deletions
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);