Re: [PATCH] lib/sort: adjust types

[Andrew Cooper <andrew.cooper3@xxxxxxxxxx>]

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@xxxxxxxx>

Acked-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>

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 )
>          {