list: Add sort and merge functions

Add functions to efficiently sort lists and to merge sorted lists.

The sort function is a bottom-up mergesort (guaranteed O(n lg n)).

1 files changed, 135 insertions, 0 deletions

diff --git a/list.h b/list.h
index be0880a..f12b000 100644
--- a/list.h
+++ b/list.h
@@ -118,4 +118,139 @@ simpledata_list_foreach (const simpledata_list_t *head,
 	f (el, arg);
 }
 
+static simpleops_inline void
+_simpledata_list_merge (simpledata_list_t *head_a,
+			simpledata_list_t *head_b,
+			int (*cmp) (const simpledata_list_t *a,
+				    const simpledata_list_t *b,
+				    void *arg),
+			void *arg)
+{
+    simpledata_list_t *head, *tmp, *curr_a, *curr_b;
+
+    head = head_a;
+    curr_a = simpledata_list_first(head_a);
+    curr_b = simpledata_list_first(head_b);
+
+    do {
+	while (curr_a != head_a && cmp(curr_a, curr_b, arg) <= 0)
+	    curr_a = curr_a->next;
+
+	curr_b->prev = curr_a->prev;
+	curr_a->prev->next = curr_b;
+	if (curr_a == head_a)
+	    break;
+
+	tmp = head_a;
+	head_a = head_b;
+	head_b = tmp;
+
+	tmp = curr_a;
+	curr_a = curr_b;
+	curr_b = tmp;
+    } while (1);
+
+    head->prev = head_b->prev;
+    head->prev->next = head;
+}
+
+static simpleops_inline void
+simpledata_list_merge (simpledata_list_t *head_a,
+		       simpledata_list_t *head_b,
+		       int (*cmp) (const simpledata_list_t *a,
+				   const simpledata_list_t *b,
+				   void *arg),
+		       void *arg)
+{
+    if (simpledata_list_is_empty(head_b))
+	return;
+
+    if (simpledata_list_is_empty(head_a)) {
+	*head_a = *head_b;
+	head_a->prev->next = head_a;
+	head_a->next->prev = head_a;
+	return;
+    }
+
+    _simpledata_list_merge(head_a, head_b, cmp, arg);
+}
+
+static simpleops_inline void
+_simpledata_list_sort (simpledata_list_t *head,
+		       simpledata_list_t *remaining_head,
+		       size_t level,
+		       int (*cmp) (const simpledata_list_t *a,
+				   const simpledata_list_t *b,
+				   void *arg),
+		       void *arg)
+{
+    simpledata_list_t head_other, *first, *curr;
+    size_t i;
+
+    first = simpledata_list_first(head);
+    curr = first->next;
+
+    /* Single element */
+    if (curr == head)
+	return;
+
+    head_other.next = curr->next;
+    head_other.prev = head->prev;
+
+    if (cmp(first, curr, arg) <= 0) {
+	/* Two elements, already sorted */
+	if (head_other.next == head)
+	    return;
+    } else {
+	/* Two elements, inverted */
+	head->next = curr;
+	curr->next = first;
+	first->next = head;
+
+	head->prev = first;
+	curr->prev = head;
+	first->prev = curr;
+
+	/* Two elements, manually sorted */
+	if (head_other.next == head)
+	    return;
+
+	curr = first;
+    }
+
+    head->prev = curr;
+    curr->next = head;
+
+    for (i = 0; i < level; i++) {
+	head_other.prev->next = &head_other;
+	head_other.next->prev = &head_other;
+	simpledata_list_init_head (remaining_head);
+
+	_simpledata_list_sort (&head_other, remaining_head, i, cmp, arg);
+	_simpledata_list_merge (head, &head_other, cmp, arg);
+
+	if (simpledata_list_is_empty(remaining_head))
+	    return;
+
+	head_other = *remaining_head;
+    }
+
+    *remaining_head = head_other;
+    remaining_head->prev->next = remaining_head;
+    remaining_head->next->prev = remaining_head;
+}
+
+static simpleops_inline void
+simpledata_list_sort (simpledata_list_t *head,
+		      int (*cmp) (const simpledata_list_t *a,
+				  const simpledata_list_t *b,
+				  void *arg),
+		      void *arg)
+{
+    simpledata_list_t tmp;
+
+    if (!simpledata_list_is_empty(head))
+	_simpledata_list_sort(head, &tmp, (size_t)-1, cmp, arg);
+}
+
 #endif