lkml.org 
[lkml]   [2005]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
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/
\
 
 \ /
  Last update: 2005-03-22 14:10    [W:0.079 / U:0.428 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site