Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S261955AbVAaHlE (ORCPT ); Mon, 31 Jan 2005 02:41:04 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S261959AbVAaHjy (ORCPT ); Mon, 31 Jan 2005 02:39:54 -0500 Received: from waste.org ([216.27.176.166]:60396 "EHLO waste.org") by vger.kernel.org with ESMTP id S261955AbVAaHfC (ORCPT ); Mon, 31 Jan 2005 02:35:02 -0500 Date: Mon, 31 Jan 2005 01:35:00 -0600 From: Matt Mackall To: Andrew Morton X-PatchBomber: http://selenic.com/scripts/mailpatches Cc: linux-kernel@vger.kernel.org In-Reply-To: <5.416337461@selenic.com> Message-Id: <6.416337461@selenic.com> Subject: [PATCH 5/8] lib/sort: Replace open-coded O(pids**2) bubblesort in cpusets Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1587 Lines: 55 Eep. cpuset uses bubble sort on a data set that's potentially O(# processes). Switch to lib/sort. Signed-off-by: Matt Mackall 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 #include #include +#include #include #include @@ -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/