`On 21/02/2019 09.21, George Spelvin wrote:> > +/**> + * parent - given the offset of the child, find the offset of the parent.> + * @i: the offset of the heap element whose parent is sought.  Non-zero.> + * @lsbit: a precomputed 1-bit mask, equal to "size & -size"> + * @size: size of each element> + *> + * In terms of array indexes, the parent of element j = i/size is simply> + * (j-1)/2.  But when working in byte offsets, we can't use implicit> + * truncation of integer divides.> + *> + * Fortunately, we only need one bit of the quotient, not the full divide.> + * size has a least significant bit.  That bit will be clear if i is> + * an even multiple of size, and set if it's an odd multiple.> + *> + * Logically, we're doing "if (i & lsbit) i -= size;", but since the> + * branch is unpredictable, it's done with a bit of clever branch-free> + * code instead.> + */> +__attribute_const__ __always_inline> +static size_t parent(size_t i, unsigned int lsbit, size_t size)> +{> +	i -= size;> +	i -= size & -(i & lsbit);> +	return i / 2;> +}> +Really nice :) I had to work through this by hand, but it's solid.>  /**>   * sort - sort an array of elements>   * @base: pointer to data to sort> @@ -125,21 +151,26 @@ static void generic_swap(void *a, void *b, int size)>   * @cmp_func: pointer to comparison function>   * @swap_func: pointer to swap function or NULL>   *> - * This function does a heapsort on the given array. You may provide a> - * swap_func function optimized to your element type.> + * This function does a heapsort on the given array.  You may provide a> + * swap_func function if you need to do something more than a memory copy> + * (e.g. fix up pointers or auxiliary data), but the built-in swap isn't> + * usually a bottleneck.>   *>   * Sorting time is O(n log n) both on average and worst-case. While>   * qsort is about 20% faster on average, it suffers from exploitable>   * O(n*n) worst-case behavior and extra memory requirements that make>   * it less suitable for kernel use.>   */> ->  void sort(void *base, size_t num, size_t size,>  	  int (*cmp_func)(const void *, const void *),>  	  void (*swap_func)(void *, void *, int size))>  {>  	/* pre-scale counters for performance */> -	int i = (num/2 - 1) * size, n = num * size, c, r;> +	size_t n = num * size, a = (num/2) * size;> +	unsigned const lsbit = size & -size;	/* Used to find parent */> +Nit: qualifier before type, "const unsigned". And this sets ZF, so aparanoid check for zero size (cf. the other mail) by doing "if (!lsbit)return;" is practically free. Though it's probably a bit obscure doingit that way...> +	if (!n)> +		return;I'd make that n <= 1. Shouldn't be much more costly.> -		}> -	}> +	/*> +	 * Loop invariants:> +	 * 1. elements [a,n) satisfy the heap property (compare greater than> +	 *    all of their children),> +	 * 2. elements [n,num*size) are sorted, and> +	 * 3. a <= b <= c <= d <= n (whenever they are valid).> +	 */> +	for (;;) {> +		size_t b, c, d;>  > +		if (a)			/* Building heap: sift down --a */> +			a -= size;> +		else if (n -= size)	/* Sorting: Extract root to --n */> +			swap_func(base, base + n, size);> +		else			/* Sort complete */> +			break;> +> +		/*> +		 * Sift element at "a" down into heap.  This is the> +		 * "bottom-up" variant, which significantly reduces> +		 * calls to cmp_func(): we find the sift-down path all> +		 * the way to the leaves (one compare per level), then> +		 * backtrack to find where to insert the target element.> +		 *> +		 * Because elements tend to sift down close to the leaves,> +		 * this uses fewer compares than doing two per level> +		 * on the way down.  (A bit more than half as many on> +		 * average, 3/4 worst-case.)> +		 */> +		for (b = a; c = 2*b + size, (d = c + size) < n;)> +			b = cmp_func(base + c, base + d) >= 0 ? c : d;> +		if (d == n)	/* Special case last leaf with no sibling */> +			b = c;> +> +		/* Now backtrack from "b" to the correct location for "a" */> +		while (b != a && cmp_func(base + a, base + b) >= 0)> +			b = parent(b, lsbit, size);> +		c = b;			/* Where "a" belongs */> +		while (b != a) {	/* Shift it into place */> +			b = parent(b, lsbit, size);> +			swap_func(base + b, base + c, size);>  		}>  	}>  }> Nice!Rasmus`