Messages in this thread Patch in this message | | | Date | Mon, 31 Jan 2005 01:35:00 -0600 | From | Matt Mackall <> | Subject | [PATCH 5/8] lib/sort: Replace open-coded O(pids**2) bubblesort in cpusets |
| |
Eep. cpuset uses bubble sort on a data set that's potentially O(# processes). Switch to lib/sort.
Signed-off-by: Matt Mackall <mpm@selenic.com>
Index: tq/kernel/cpuset.c =================================================================== --- tq.orig/kernel/cpuset.c 2005-01-29 16:13:53.000000000 -0800 +++ tq/kernel/cpuset.c 2005-01-30 13:26:48.000000000 -0800 @@ -47,6 +47,7 @@ #include <linux/string.h> #include <linux/time.h> #include <linux/backing-dev.h> +#include <linux/sort.h> #include <asm/uaccess.h> #include <asm/atomic.h> @@ -1055,21 +1056,9 @@ return n; } -/* - * In place bubble sort pidarray of npids pid_t's. - */ -static inline void pid_array_sort(pid_t *pidarray, int npids) +static int cmppid(const void *a, const void *b) { - int i, j; - - for (i = 0; i < npids - 1; i++) { - for (j = 0; j < npids - 1 - i; j++) - if (pidarray[j + 1] < pidarray[j]) { - pid_t tmp = pidarray[j]; - pidarray[j] = pidarray[j + 1]; - pidarray[j + 1] = tmp; - } - } + return *(pid_t *)a - *(pid_t *)b; } /* @@ -1114,7 +1103,7 @@ goto err1; npids = pid_array_load(pidarray, npids, cs); - pid_array_sort(pidarray, npids); + sort(pidarray, npids, sizeof(pid_t), cmppid, 0); /* Call pid_array_to_buf() twice, first just to get bufsz */ ctr->bufsz = pid_array_to_buf(&c, sizeof(c), pidarray, npids) + 1; - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |