1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
/* SPDX-License-Identifier: LGPL-2.1-only */
/* Copyright (C) 2020-2021 Gediminas Jakutis */
#include <errno.h>
#include <stdlib.h>
#include "defs.h"
#include "stream.h"
#include "mergesort.h"
static int merge(struct stream * const dest, struct stream * const A, struct stream * const B);
/* bottom-up variantas */
int merge_sort(struct stream * const src, struct stream * const dest)
{
int ret = 0;
struct stream tmp[4] = {0}; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */
try(!src || !dest, err, EINVAL, "cannot sort what's not there");
try_s((ret = stream_shallow_copy(src, dest)), err);
if (src->n > 1) {
src->split(src, tmp, tmp + 2); /* split stream in half */
merge_sort(tmp, tmp + 1); /* recurse-sort first half */
merge_sort(tmp + 2, tmp + 3); /* recurse-sort second half */
merge(dest, tmp + 1, tmp + 3); /* merge the two halves back */
dest->rewind(dest);
/* you can't spell -funroll-loops without fun, wee~! */
stream_close(tmp);
stream_close(tmp + 1);
stream_close(tmp + 2);
stream_close(tmp + 3);
} else { /* stream of size one is inherently sorted, simply swap src with dest */
*tmp = *dest;
*dest = *src;
*src = *tmp;
}
err:
return ret;
}
static int merge(struct stream * const dest, struct stream * const A, struct stream * const B)
{
int ret = 0;
struct entry_l *a;
struct entry_l *b;
a = A->get(A);
b = B->get(B);
while (a || b) {
if (a && (!b || a->val <= b->val)) {
dest->put(dest, a);
a = A->get(A);
} else {
dest->put(dest, b);
b = B->get(B);
}
}
return ret;
}
|
