Eric Lee / smarc-fsl-linux-kernel | Embedian Git Server

043b3f7b6 lib/list_sort: simplify and remove MAX_LIST_LENGTH_BITS ... Browse Code »

Rather than a fixed-size array of pending sorted runs, use the ->prev
links to keep track of things. This reduces stack usage, eliminates
some ugly overflow handling, and reduces the code size.

Also:
* merge() no longer needs to handle NULL inputs, so simplify.
* The same applies to merge_and_restore_back_links(), which is renamed
to the less ponderous merge_final(). (It's a static helper function,
so we don't need a super-descriptive name; comments will do.)
* Document the actual return value requirements on the (*cmp)()
function; some callers are already using this feature.

x86-64 code size 1086 -> 739 bytes (-347)

(Yes, I see checkpatch complaining about no space after comma in
"__attribute__((nonnull(2,3,4,5)))". Checkpatch is wrong.)

Feedback from Rasmus Villemoes, Andy Shevchenko and Geert Uytterhoeven.

[akpm@linux-foundation.org: remove __pure usage due to mysterious warning]
Link: http://lkml.kernel.org/r/f63c410e0ff76009c9b58e01027e751ff7fdb749.1552704200.git.lkml@sdf.org
Signed-off-by: George Spelvin
Acked-by: Andrey Abramov
Acked-by: Rasmus Villemoes
Reviewed-by: Andy Shevchenko
Cc: Geert Uytterhoeven
Cc: Daniel Wagner
Cc: Dave Chinner
Cc: Don Mullis
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds

George Spelvin
2019-05-15 10:52:49 +0800

list_sort.h 307 Bytes

edit raw blame history

1 2 3 4 5 6 7 8 9 10 11 12 13

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H

#include <linux/types.h>

struct list_head;

__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));
#endif