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

[Andreas Gruenbacher <agruen@suse.de>]

On Mon, 2005-01-31 at 18:30, Paulo Marques wrote:
> Andreas Gruenbacher wrote:
> > [...]
> > 
> > static inline void swap(void *a, void *b, int size)
> > {
> >         if (size % sizeof(long)) {
> >                 char t;
> >                 do {
> >                         t = *(char *)a;
> >                         *(char *)a++ = *(char *)b;
> >                         *(char *)b++ = t;
> >                 } while (--size > 0);
> >         } else {
> >                 long t;
> >                 do {
> >                         t = *(long *)a;
> >                         *(long *)a = *(long *)b;
> >                         *(long *)b = t;
> >                         size -= sizeof(long);
> >                 } while (size > sizeof(long));
> 
> You forgot to increment a and b, and this should be "while (size);", no?

Correct, yes.

> Or better yet,
> 
> static inline void swap(void *a, void *b, int size)
> {
> 	long tl;
>          char t;
> 
> 	while (size >= sizeof(long)) {
>                  tl = *(long *)a;
>                  *(long *)a = *(long *)b;
>                  *(long *)b = tl;
> 		a += sizeof(long);
> 		b += sizeof(long);
>                  size -= sizeof(long);
> 	}
> 	while (size) {
>                  t = *(char *)a;
>                  *(char *)a++ = *(char *)b;
>                  *(char *)b++ = t;
> 		size--;
>          }
> }
> 
> This works better if the size is not a multiple of sizeof(long), but is 
> bigger than a long.

In case size is not a multiple of sizeof(long) here, you'll have
unaligned memory accesses most of the time anyway, so it probably
doesn't really matter.

Thanks,
-- 
Andreas Gruenbacher <agruen@suse.de>
SUSE Labs, SUSE LINUX GMBH