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
|
/* SPDX-License-Identifier: LGPL-2.1-only */
/* Copyright (C) 2020 Gediminas Jakutis */
#include <errno.h>
#include <stdlib.h>
#include "defs.h"
#include "io.h"
#include "mergesort.h"
/* bottom-up variantas */
int merge_sort(struct stream * const src, struct stream * const dest)
{
int ret = 0;
struct stream tmp[4]; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */
size_t i;
try(!src || !dest, err, EINVAL, "cannot sort what's not there");
if (src->n > 1) { /* stream of size one is inherently sorted */
src->split(src, tmp, tmp + 2); /* split stream in half */
merge_sort(tmp + 1, tmp); /* recurse-sort first half */
merge_sort(tmp + 3, tmp + 2); /* recurse-sort second half */
merge(dest, tmp, tmp + 2); /* merge the two halves back */
}
for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
stream_close(tmp + i);
}
err:
return ret;
}
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;
try(A->parentid != B->parentid, err, EINVAL, "cannot merge blocks: uncommon parent!");
a = get(A);
b = get(B);
while (a || b) {
if (a && (!b || a->val <= b->val)) {
put(dest, a);
a = get(A);
} else {
put(dest, b);
b = get(B);
}
}
err:
return ret;
}
|
