Messages in this thread | | | Date | Sat, 22 Jan 2005 15:28:14 -0800 | From | Matt Mackall <> | Subject | Re: [patch 1/13] Qsort |
| |
On Sat, Jan 22, 2005 at 09:34:01PM +0100, Andreas Gruenbacher wrote: > Add a quicksort from glibc as a kernel library function, and switch > xfs over to using it. The implementations are equivalent. The nfsacl > protocol also requires a sort function, so it makes more sense in > the common code.
Please update this to kernel formatting standards and try to modernize it a bit.
> +/* Byte-wise swap two items of size SIZE. */ > +#define SWAP(a, b, size) \ > + do \ > + { \ > + register size_t __size = (size); \ > + register char *__a = (a), *__b = (b); \ > + do \ > + { \ > + char __tmp = *__a; \ > + *__a++ = *__b; \ > + *__b++ = __tmp; \ > + } while (--__size > 0); \ > + } while (0)
Inline, please? Register keyword?!
> +typedef struct > + { > + char *lo; > + char *hi; > + } stack_node;
void *, please
> + > +/* The next 5 #defines implement a very fast in-line stack abstraction. */ > +/* The stack needs log (total_elements) entries (we could even subtract > + log(MAX_THRESH)). Since total_elements has type size_t, we get as > + upper bound for log (total_elements): > + bits per byte (CHAR_BIT) * sizeof(size_t). */ > +#define CHAR_BIT 8 > +#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
So the stack is going to be either 256 or 1024 bytes. Seems like we ought to kmalloc it.
> +#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) > +#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) > +#define STACK_NOT_EMPTY (stack < top)
There's only one usage of POP, one of STACK_NOT_EMPTY and two of PUSH that can trivially be made one. Please kill these macros.
> + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving > + insertion sort to order the MAX_THRESH items within each partition. > + This is a big win, since insertion sort is faster for small, mostly > + sorted array segments.
This observation may be dated, instruction cache issues may dominate now.
> + char *mid = lo + size * ((hi - lo) / size >> 1);
Get rid of all this char* stuff, please. It makes for lots of ugly and unnecessary casting.
> + if ((*cmp) ((void *) mid, (void *) lo) < 0) > + SWAP (mid, lo, size);
cmp(mid, lo)
> + if ((*cmp) ((void *) hi, (void *) mid) < 0) > + SWAP (mid, hi, size); > + else > + goto jump_over; > + if ((*cmp) ((void *) mid, (void *) lo) < 0) > + SWAP (mid, lo, size); > + jump_over:;
?!
> + /* Once the BASE_PTR array is partially sorted by quicksort the rest > + is completely sorted using insertion sort, since this is efficient > + for partitions below MAX_THRESH size. BASE_PTR points to the beginning > + of the array to sort, and END_PTR points at the very last element in > + the array (*not* one beyond it!). */ > + > + { > + char *end_ptr = &base_ptr[size * (total_elems - 1)]; > + char *tmp_ptr = base_ptr; > + char *thresh = min(end_ptr, base_ptr + max_thresh); > + register char *run_ptr;
Move these vars to the top or better yet, split this into two functions.
-- Mathematics is the supreme nostalgia of our time. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |