A modern Music Player Daemon based on Rockbox open source high quality audio player
tsiry-sandratraina.com
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * Implement arraysort() defined in puzzles.h.
3 *
4 * Strategy: heapsort.
5 */
6
7#include <stddef.h>
8#include <string.h>
9
10#include "puzzles.h"
11
12#define PTR(i) ((char *)array + size * (i))
13#define SWAP(i,j) swap_regions(PTR(i), PTR(j), size)
14#define CMP(i,j) cmp(PTR(i), PTR(j), ctx)
15
16#define LCHILD(i) (2*(i)+1)
17#define RCHILD(i) (2*(i)+2)
18#define PARENT(i) (((i)-1)/2)
19
20static void downheap(void *array, size_t nmemb, size_t size,
21 arraysort_cmpfn_t cmp, void *ctx, size_t i)
22{
23 while (LCHILD(i) < nmemb) {
24 /* Identify the smallest element out of i and its children. */
25 size_t j = i;
26 if (CMP(j, LCHILD(i)) < 0)
27 j = LCHILD(i);
28 if (RCHILD(i) < nmemb &&
29 CMP(j, RCHILD(i)) < 0)
30 j = RCHILD(i);
31
32 if (j == i)
33 return; /* smallest element is already where it should be */
34
35 SWAP(j, i);
36 i = j;
37 }
38}
39
40void arraysort_fn(void *array, size_t nmemb, size_t size,
41 arraysort_cmpfn_t cmp, void *ctx)
42{
43 size_t i;
44
45 if (nmemb < 2)
46 return; /* trivial */
47
48 /*
49 * Stage 1: build the heap.
50 *
51 * Linear-time if we do it by downheaping the elements in
52 * decreasing order of index, instead of the more obvious approach
53 * of upheaping in increasing order. (Also, it means we don't need
54 * the upheap function at all.)
55 *
56 * We don't need to downheap anything in the second half of the
57 * array, because it can't have any children to swap with anyway.
58 */
59 for (i = PARENT(nmemb-1) + 1; i-- > 0 ;)
60 downheap(array, nmemb, size, cmp, ctx, i);
61
62 /*
63 * Stage 2: dismantle the heap by repeatedly swapping the root
64 * element (at index 0) into the last position and then
65 * downheaping the new root.
66 */
67 for (i = nmemb-1; i > 0; i--) {
68 SWAP(0, i);
69 downheap(array, i, size, cmp, ctx, 0);
70 }
71}