lib/sort: adjust types
PATCH 1/1 lib/sort: adjust types
First and foremost do away with the use of plain int for sizes or size- derived values. Use size_t, despite this requiring some adjustment to the logic. Also replace u32 by uint32_t.
While not directly related also drop a leftover #ifdef from x86's swap_ex - this was needed only back when 32-bit Xen was still a thing.
xen/arch/x86/extable.c +1 -3
@@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(consreturn 0 ; } -#ifndef swap_ex -static void init_or_livepatch swap_ex(void *a, void *b, int size) +static void init_or_livepatch swap_ex(void *a, void *b, size_t size) {struct exception_table_entry *l = a, *r = b, tmp;long delta = b - a;
@@ -49,7 +48,6 @@ static void init_or_livepatch swap_ex(vo r->addr = tmp.addr - delta; r->cont = tmp.cont - delta; } -#endif void init_or_livepatch sort_exception_table(struct exception_table_entry *start,const struct exception_table_entry *stop)
xen/include/xen/sort.h +1 -1
@@ -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 /* __XEN_SORT_H__ */
xen/lib/sort.c +12 -10
@@ -6,14 +6,15 @@#include <xen/types.h> -static void u32_swap (void *a,void *b,int size) +static void u32_swap (void *a,void *b,size_t size) { -u32 t = *(u32 *)a; - *(u32 *)a = *(u32 *)b; - *(u32 *)b = t; +uint32_t t = *(uint32_t *)a; + + *(uint32_t *)a = *(uint32_t *)b; + *(uint32_t *)b = t; } -static void generic_swap (void *a,void *b,int size) +static void generic_swap (void *a,void *b,size_t size) {char t;
@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *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 -1 ) * size, n = num * size, c, r; +size_t i = (num /2 ) * size, n = num * size, c, r;if ( !swap ) swap = (size ==4 ? u32_swap : generic_swap);/* heapify */ -for ( ; i >=0 ; i -= size ) +while ( i >0 ) { -for ( r = i; r *2 + size < n; r = c ) +for ( r = i -= size; r *2 + size < n; r = c ) { c = r *2 + size;if ( (c < n - size) && (cmp (base + c, base + c + size) <0 ) )
@@ -66,8 +67,9 @@ void sort(void *base, size_t num, size_t }/* 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 + size < i; r = c ) {
Quoted 8 lines · Jan Beulich
First and foremost do away with the use of plain int for sizes or size- derived values. Use
size_t, despite this requiring some adjustment to the logic. Also replace u32 byuint32_t.While not directly related also drop a leftover #ifdef from x86's
swap_ex- this was needed only back when 32-bit Xen was still a thing.Signed-off-by Jan Beulich <[email protected]>
Its a shame that we've got exactly two users of sort() (ought to be named heapsort), one in arm/io.c which ought to be replaced with a generalised version of my sorted-array logic for VMCS load/save lists, and the other in x86's sort_exception_table() which ought to become build-time logic.
Quoted 64 lines
xen/arch/x86/extable.c +1
-3@@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(consreturn 0 ; } -#ifndef swap_ex -static void init_or_livepatch swap_ex(void *a, void *b, int size) +static void init_or_livepatch swap_ex(void *a, void *b, size_t size) {struct exception_table_entry *l = a, *r = b, tmp;long delta = b - a;@@ -49,7 +48,6 @@ static void init_or_livepatch swap_ex(vo r->addr = tmp.addr - delta; r->cont = tmp.cont - delta; } -#endif void init_or_livepatch sort_exception_table(struct exception_table_entry *start,const struct exception_table_entry *stop)xen/include/xen/sort.h +1
-1@@ -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 /* __XEN_SORT_H__ */ xen/lib/sort.c +8
-7@@ -6,14 +6,15 @@#include <xen/types.h> -static void u32_swap (void *a,void *b,int size) +static void u32_swap (void *a,void *b,size_t size) { -u32 t = *(u32 *)a; - *(u32 *)a = *(u32 *)b; - *(u32 *)b = t; +uint32_t t = *(uint32_t *)a; + + *(uint32_t *)a = *(uint32_t *)b; + *(uint32_t *)b = t; } -static void generic_swap (void *a,void *b,int size) +static void generic_swap (void *a,void *b,size_t size) {char t;@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *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 -1 ) * size, n = num * size, c, r; +size_t i = (num /2 ) * size, n = num * size, c, r;
xen/lib/sort.c static void generic_swap(void *a, void * · line 58
Quoted 10 lines
xen/lib/sort.c +2
-2if ( !swap ) swap = (size ==4 ? u32_swap : generic_swap);/* heapify */ -for ( ; i >=0 ; i -= size ) +while ( i >0 ) { -for ( r = i; r *2 + size < n; r = c ) +for ( r = i -= size; r *2 + size < n; r = c )
Aren't some compilers going to complain at the lack of brackets for this setup of r?
Also as you're editing the line, the "r = c" part should lose one space.
~Andrew
Quoted 14 lines
xen/lib/sort.c +2
-1{ c = r *2 + size;if ( (c < n - size) && (cmp (base + c, base + c + size) <0 ) )@@ -66,8 +67,9 @@ void sort(void *base, size_t num, size_t }/* 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 + size < i; r = c ) {
Quoted 11 lines · Andrew Cooper
Quoted 8 lines · Jan Beulich
First and foremost do away with the use of plain int for sizes or size- derived values. Use
size_t, despite this requiring some adjustment to the logic. Also replace u32 byuint32_t.While not directly related also drop a leftover #ifdef from x86's
swap_ex- this was needed only back when 32-bit Xen was still a thing.Signed-off-by Jan Beulich <[email protected]>Acked-by Andrew Cooper <[email protected]>
Thanks.
Quoted 37 lines
Quoted 37 lines
xen/lib/sort.c +8
-7@@ -6,14 +6,15 @@#include <xen/types.h> -static void u32_swap (void *a,void *b,int size) +static void u32_swap (void *a,void *b,size_t size) { -u32 t = *(u32 *)a; - *(u32 *)a = *(u32 *)b; - *(u32 *)b = t; +uint32_t t = *(uint32_t *)a; + + *(uint32_t *)a = *(uint32_t *)b; + *(uint32_t *)b = t; } -static void generic_swap (void *a,void *b,int size) +static void generic_swap (void *a,void *b,size_t size) {char t;@@ -43,18 +44,18 @@ static void generic_swap(void *a, void *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 -1 ) * size, n = num * size, c, r; +size_t i = (num /2 ) * size, n = num * size, c, r;if ( !swap ) swap = (size ==4 ? u32_swap : generic_swap);
Quoted 9 lines
xen/lib/sort.c static void generic_swap(void *a, void * · line 58
Quoted 6 lines
xen/lib/sort.c +2
-2/* heapify */ -for ( ; i >=0 ; i -= size ) +while ( i >0 ) { -for ( r = i; r *2 + size < n; r = c ) +for ( r = i -= size; r *2 + size < n; r = c )Aren't some compilers going to complain at the lack of brackets for this setup of r?
I've never seen any warning on this type of construct. It's no different from "a = b = c;".
Quoted 1 line
Also as you're editing the line, the "r = c" part should lose one space.
Oh, indeed.
Jan