diff options
Diffstat (limited to 'lib/list_sort.c')
| -rw-r--r-- | lib/list_sort.c | 23 |
1 files changed, 10 insertions, 13 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c index 712ed1f4eb64..0fb59e92ca2d 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -7,16 +7,13 @@ #include <linux/list_sort.h> #include <linux/list.h> -typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *, - struct list_head const *, struct list_head const *); - /* * 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. */ __attribute__((nonnull(2,3,4))) -static struct list_head *merge(void *priv, cmp_func cmp, +static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b) { struct list_head *head, **tail = &head; @@ -52,7 +49,7 @@ static struct list_head *merge(void *priv, cmp_func cmp, * throughout. */ __attribute__((nonnull(2,3,4,5))) -static void merge_final(void *priv, cmp_func cmp, struct list_head *head, +static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b) { struct list_head *tail = head; @@ -107,7 +104,7 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * @head: the list to sort * @cmp: the elements comparison function * - * The comparison funtion @cmp must return > 0 if @a should sort after + * The comparison function @cmp must return > 0 if @a should sort after * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should * sort before @b *or* their original order should be preserved. It is * always called with the element that came first in the input in @a, @@ -140,7 +137,7 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * * * The merging is controlled by "count", the number of elements in the - * pending lists. This is beautiully simple code, but rather subtle. + * pending lists. This is beautifully simple code, but rather subtle. * * Each time we increment "count", we set one bit (bit k) and clear * bits k-1 .. 0. Each time this happens (except the very first time @@ -157,9 +154,11 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * * The number of pending lists of size 2^k is determined by the * state of bit k of "count" plus two extra pieces of information: + * * - The state of bit k-1 (when k == 0, consider bit -1 always set), and * - Whether the higher-order bits are zero or non-zero (i.e. * is count >= 2^(k+1)). + * * There are six states we distinguish. "x" represents some arbitrary * bits, and "y" represents some arbitrary non-zero bits: * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k @@ -183,9 +182,7 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1). */ __attribute__((nonnull(2,3))) -void list_sort(void *priv, struct list_head *head, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b)) +void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) { struct list_head *list = head->next, *pending = NULL; size_t count = 0; /* Count of pending */ @@ -225,7 +222,7 @@ void list_sort(void *priv, struct list_head *head, if (likely(bits)) { struct list_head *a = *tail, *b = a->prev; - a = merge(priv, (cmp_func)cmp, b, a); + a = merge(priv, cmp, b, a); /* Install the merged result in place of the inputs */ a->prev = b->prev; *tail = a; @@ -247,10 +244,10 @@ void list_sort(void *priv, struct list_head *head, if (!next) break; - list = merge(priv, (cmp_func)cmp, pending, list); + list = merge(priv, cmp, pending, list); pending = next; } /* The final merge, rebuilding prev links */ - merge_final(priv, (cmp_func)cmp, head, pending, list); + merge_final(priv, cmp, head, pending, list); } EXPORT_SYMBOL(list_sort); |