/* SPDX-License-Identifier: LGPL-2.1-only */ /* Copyright (C) 2020-2021 Gediminas Jakutis */ #include #include #include "defs.h" #include "stream.h" #include "mergesort.h" #include "util.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) { 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 */ stream_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; struct entry_l a_store; struct entry_l b_store; a = A->get(A, &a_store); b = B->get(B, &b_store); while (a || b) { if (a && (!b || a_store.val <= b_store.val)) { dest->put(dest, a); a = A->get(A, &a_store); } else { dest->put(dest, b); b = B->get(B, &b_store); } } return ret; }