list_sort() [LWN.net]

By Jonathan Corbet
January 6, 2010

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

list_sort()

Posted Jan 7, 2010 9:52 UTC (Thu) by jond (subscriber, #37669) [Link] (1 responses)

I always enjoy seeing this variety of work going on. It strikes me as the
kind of work that someone new to the kernel could do to familiarise
themselves. It often seems to be experienced people that get around to it,
though: Robert Love did strdup in 2005 and Andrew Morton did boolean
definitions in 2006.

list_sort()

Posted Jan 8, 2010 21:43 UTC (Fri) by magnus (subscriber, #34778) [Link]

It often seems to be experienced people that get around to it, though: Robert Love did strdup in 2005 and Andrew Morton did boolean definitions in 2006.

Most people probably don't have the stones to post their custom strchr() implementation on lkml :)

I'm surprised the article didn't mention which sorting algorithm it was, Apparently it's merge sort judging by the code comments...