* [PATCH] lib/sort: adjust types
@ 2020-12-22 16:49 Jan Beulich
2020-12-22 17:05 ` Andrew Cooper
0 siblings, 1 reply; 3+ messages in thread
From: Jan Beulich @ 2020-12-22 16:49 UTC (permalink / raw)
To: xen-devel
Cc: Andrew Cooper, George Dunlap, Ian Jackson, Julien Grall,
Stefano Stabellini, Wei Liu, Roger Pau Monné
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.
Signed-off-by: Jan Beulich <jbeulich@suse.com>
--- a/xen/arch/x86/extable.c
+++ b/xen/arch/x86/extable.c
@@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(cons
return 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)
--- a/xen/include/xen/sort.h
+++ b/xen/include/xen/sort.h
@@ -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__ */
--- a/xen/lib/sort.c
+++ b/xen/lib/sort.c
@@ -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 )
{
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] lib/sort: adjust types
2020-12-22 16:49 [PATCH] lib/sort: adjust types Jan Beulich
@ 2020-12-22 17:05 ` Andrew Cooper
2020-12-23 10:19 ` Jan Beulich
0 siblings, 1 reply; 3+ messages in thread
From: Andrew Cooper @ 2020-12-22 17:05 UTC (permalink / raw)
To: Jan Beulich, xen-devel
Cc: George Dunlap, Ian Jackson, Julien Grall, Stefano Stabellini,
Wei Liu, Roger Pau Monné
On 22/12/2020 16:49, Jan Beulich wrote:
> 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.
>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>
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.
>
> --- a/xen/arch/x86/extable.c
> +++ b/xen/arch/x86/extable.c
> @@ -37,8 +37,7 @@ static int init_or_livepatch cmp_ex(cons
> return 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)
> --- a/xen/include/xen/sort.h
> +++ b/xen/include/xen/sort.h
> @@ -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__ */
> --- a/xen/lib/sort.c
> +++ b/xen/lib/sort.c
> @@ -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 )
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
> {
> 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 )
> {
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] lib/sort: adjust types
2020-12-22 17:05 ` Andrew Cooper
@ 2020-12-23 10:19 ` Jan Beulich
0 siblings, 0 replies; 3+ messages in thread
From: Jan Beulich @ 2020-12-23 10:19 UTC (permalink / raw)
To: Andrew Cooper
Cc: George Dunlap, Ian Jackson, Julien Grall, Stefano Stabellini,
Wei Liu, Roger Pau Monné,
xen-devel
On 22.12.2020 18:05, Andrew Cooper wrote:
> On 22/12/2020 16:49, Jan Beulich wrote:
>> 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.
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>
> Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>
Thanks.
>> --- a/xen/lib/sort.c
>> +++ b/xen/lib/sort.c
>> @@ -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 )
>
> 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;".
> Also as you're editing the line, the "r = c" part should lose one space.
Oh, indeed.
Jan
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-12-23 10:20 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-12-22 16:49 [PATCH] lib/sort: adjust types Jan Beulich
2020-12-22 17:05 ` Andrew Cooper
2020-12-23 10:19 ` Jan Beulich
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.