225 for (;;) {
226 size_t b, c, d;
227
228 if (a) /* Building heap: sift down a */
229 a -= size << shift;
230 else if (n > 3 * size) { /* Sorting: Extract two largest elements */
231 n -= size;
232 do_swap(base, base + n, size, swap_func, priv);
233 shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0;
234 a = size << shift;
235 n -= size;
236 do_swap(base + a, base + n, size, swap_func, priv);
237 } else { /* Sort complete */
238 break;
239 }
240
241 /*
242 * Sift element at "a" down into heap. This is the
243 * "bottom-up" variant, which significantly reduces
244 * calls to cmp_func(): we find the sift-down path all
245 * the way to the leaves (one compare per level), then
246 * backtrack to find where to insert the target element.
247 *
248 * Because elements tend to sift down close to the leaves,
249 * this uses fewer compares than doing two per level
250 * on the way down. (A bit more than half as many on
251 * average, 3/4 worst-case.)
252 */
253 for (b = a; c = 2*b + size, (d = c + size) < n;)
254 b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d;
255 if (d == n) /* Special case last leaf with no sibling */
256 b = c;
257
258 /* Now backtrack from "b" to the correct location for "a" */
259 while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0)
260 b = parent(b, lsbit, size);