Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Christophe Saout <christophe@saout.de>]

[-- Attachment #1: Type: text/plain, Size: 3473 bytes --]

Am Sonntag, den 27.02.2005, 13:25 -0800 schrieb Matt Mackall:

> Which kernel? There was an off-by-one for odd array sizes in the
> original posted version that was quickly spotted:
> 
> http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc4/2.6.11-rc4-mm1/broken-out/sort-fix.patch
> 
> I've since tested all sizes 1 - 1000 with 100 random arrays each, so
> I'm fairly confident it's now fixed.

-	int i = (num/2 - 1) * size, n = num * size, c, r;
+	int i = (num/2) * size, n = num * size, c, r;

What's probably meant is: ((num - 1)/2) * size

`i' must cover half of the array or a little bit more (not less, in case
of odd numbers). `i' (before my patch) is the highest address to start
with, so that's why it should be ((num + 1)/2 - 1) * size or simpler:
((num - 1)/2) * size

Anyway, I was wondering, is there a specific reason you are not using
size_t for the offset variables? size is a size_t and the only purpose
of the variables i, n, c and r is to be compared or added to the start
pointer (also I think it's just ugly to cast size_t down to an int).

On system where int is 32 bit but pointers are 64 bit the compiler might
need to extend to adjust the size of the operands for the address
calculation. Right?

Since size_t is unsigned I also had to modify the two loops since I
can't check for any of the variables becoming negative. Tested with all
kinds of array sizes.

Signed-off-by: Christophe Saout <christophe@saout.de>

diff -Nur linux-2.6.11-rc4-mm1.orig/include/linux/sort.h linux-2.6.11-rc4-mm1/include/linux/sort.h
--- linux-2.6.11-rc4-mm1.orig/include/linux/sort.h	2005-03-01 19:45:11.000000000 +0100
+++ linux-2.6.11-rc4-mm1/include/linux/sort.h	2005-03-01 19:47:13.456097896 +0100
@@ -5,6 +5,6 @@
 
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
-	  void (*swap)(void *, void *, int));
+	  void (*swap)(void *, void *, size_t));
 
 #endif
diff -Nur linux-2.6.11-rc4-mm1.orig/lib/sort.c linux-2.6.11-rc4-mm1/lib/sort.c
--- linux-2.6.11-rc4-mm1.orig/lib/sort.c	2005-03-01 19:46:05.000000000 +0100
+++ linux-2.6.11-rc4-mm1/lib/sort.c	2005-03-01 19:47:55.688677568 +0100
@@ -7,14 +7,14 @@
 #include <linux/kernel.h>
 #include <linux/module.h>
 
-void u32_swap(void *a, void *b, int size)
+void u32_swap(void *a, void *b, size_t size)
 {
 	u32 t = *(u32 *)a;
 	*(u32 *)a = *(u32 *)b;
 	*(u32 *)b = t;
 }
 
-void generic_swap(void *a, void *b, int size)
+void generic_swap(void *a, void *b, size_t size)
 {
 	char t;
 
@@ -44,17 +44,19 @@
 
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
-	  void (*swap)(void *, void *, int size))
+	  void (*swap)(void *, void *, size_t size))
 {
 	/* pre-scale counters for performance */
-	int i = (num/2) * size, n = num * size, c, r;
+	size_t i = ((num + 1)/2) * size, n = num * size, c, r;
 
 	if (!swap)
 		swap = (size == 4 ? u32_swap : generic_swap);
 
 	/* heapify */
-	for ( ; i >= 0; i -= size) {
-		for (r = i; r * 2 < n; r  = c) {
+	while(i > 0) {
+		i -= size;
+
+		for (r = i; r * 2 < n; r = c) {
 			c = r * 2;
 			if (c < n - size && cmp(base + c, base + c + size) < 0)
 				c += size;
@@ -65,7 +67,9 @@
 	}
 
 	/* sort */
-	for (i = n - size; i >= 0; i -= size) {
+	for (i = n; i > 0;) {
+		i -= size;
+
 		swap(base, base + i, size);
 		for (r = 0; r * 2 < i; r = c) {
 			c = r * 2;


[-- Attachment #2: Dies ist ein digital signierter Nachrichtenteil --]
[-- Type: application/pgp-signature, Size: 189 bytes --]