1 files changed, 128 insertions, 4 deletions
diff --git a/src/lists.h b/src/lists.h
index ae8929e..bd371a4 100644
--- a/src/lists.h
+++ b/src/lists.h
@@ -1,10 +1,10 @@
 /*
- * lists.h	Simple doubly linked list implementation,
- *		based on <linux/list.h> and <linux/prefetch.h>.
+ * lists.h	Simple doubly linked list implementation, based on
+ *		<linux/list.h>, <linux/prefetch.h>, and lib/list_sort.c
  *
- * Version:	0.1 01-Feb-2011 Fink
+ * Version:	0.2 11-Dec-2012 Fink
  *
- * Copyright 2011 Werner Fink, 2005 SUSE LINUX Products GmbH, Germany.
+ * Copyright 2011,2012 Werner Fink, 2005,2012 SUSE LINUX Products GmbH, Germany.
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -246,4 +246,128 @@ static inline void move_tail(list_t *restrict entry, list_t *restrict head)
 #define np_list_for_each_prev(pos, head)	\
 	for (pos = (head)->prev; pos != (head); pos = pos->prev)
 
+#define MAX_LIST_LENGTH_BITS 20
+
+/*
+ * Returns a list organized in an intermediate format suited
+ * to chaining of merge() calls: null-terminated, no reserved or
+ * sentinel head node, "prev" links not maintained.
+ */
+static inline list_t *merge(int (*cmp)(list_t *a, list_t *b), list_t *a, list_t *b)
+{
+    list_t head, *tail = &head;
+    while (a && b) {
+	/* if equal, take 'a' -- important for sort stability */
+	if ((*cmp)(a, b) <= 0) {
+	    tail->next = a;
+	    a = a->next;
+	} else {
+	    tail->next = b;
+	    b = b->next;
+	}
+	tail = tail->next;
+    }
+    tail->next = a ? a : b;
+    return head.next;
+}
+
+/*
+ * Combine final list merge with restoration of standard doubly-linked
+ * list structure.  This approach duplicates code from merge(), but
+ * runs faster than the tidier alternatives of either a separate final
+ * prev-link restoration pass, or maintaining the prev links
+ * throughout.
+ */
+static inline void merge_and_restore_back_links(int (*cmp)(list_t *a, list_t *b), list_t *head, list_t *a, list_t *b)
+{
+    list_t *tail = head;
+
+    while (a && b) {
+	/* if equal, take 'a' -- important for sort stability */
+	if ((*cmp)(a, b) <= 0) {
+	    tail->next = a;
+	    a->prev = tail;
+	    a = a->next;
+	} else {
+	    tail->next = b;
+	    b->prev = tail;
+	    b = b->next;
+	}
+	tail = tail->next;
+    }
+    tail->next = a ? a : b;
+
+    do {
+	/*
+	 * In worst cases this loop may run many iterations.
+	 * Continue callbacks to the client even though no
+	 * element comparison is needed, so the client's cmp()
+	 * routine can invoke cond_resched() periodically.
+	 */
+	(*cmp)(tail->next, tail->next);
+
+	tail->next->prev = tail;
+	tail = tail->next;
+    } while (tail->next);
+
+    tail->next = head;
+    head->prev = tail;
+}
+
+
+/**
+ * list_sort - sort a list
+ * @head: the list to sort
+ * @cmp: the elements comparison function
+ *
+ * This function implements "merge sort", which has O(nlog(n))
+ * complexity.
+ *
+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp must return 0.
+ */
+static inline void list_sort(list_t *head, int (*cmp)(list_t *a, list_t *b))
+{
+    list_t *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
+						-- last slot is a sentinel */
+    size_t lev;  /* index into part[] */
+    size_t max_lev = 0;
+    list_t *list;
+
+    if (list_empty(head))
+	return;
+
+    memset(part, 0, sizeof(part));
+
+    head->prev->next = NULL;
+    list = head->next;
+
+    while (list) {
+	list_t *cur = list;
+	list = list->next;
+	cur->next = NULL;
+
+	for (lev = 0; part[lev]; lev++) {
+	    cur = merge(cmp, part[lev], cur);
+	    part[lev] = NULL;
+	}
+	if (lev > max_lev) {
+	    /* list passed to list_sort() too long for efficiency */
+	    if (lev >= MAX_LIST_LENGTH_BITS)
+		lev--;
+	    max_lev = lev;
+	}
+	part[lev] = cur;
+    }
+
+    for (lev = 0; lev < max_lev; lev++) {
+	if (part[lev])
+	    list = merge(cmp, part[lev], list);
+    }
+
+    merge_and_restore_back_links(cmp, head, part[max_lev], list);
+}
+
 #endif /* _LISTS_H */