The kernel has long had a set of standard functions for the manipulation of
linked lists. What it has lacked, though, is a function for sorting those
lists. Actually, that's not quite true: it has two of them: one in the
direct rendering code, and one in the UBIFS filesystem. When Dave Chinner
found himself needing the same functionality for XFS, he decided that
adding a third implementation was probably not the best idea.
So, instead, Dave grabbed the UBIFS version and reworked it into a generic list_sort()
patch. The result is this function:
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a, struct list_head *b));
This function behaves like many generic sort utilities - the cmp()
function will be called with pairs of list elements (and the given
priv pointer); it should return an integer value indicating
whether the first item should sort ahead of or behind the second.
The existing users of this functionality have acknowledged the change, so
it will almost certainly make an appearance in 2.6.34.
to post comments)