YetAnotherCoupler 3.1.1
Loading...
Searching...
No Matches
mergesort.c
Go to the documentation of this file.
1// Copyright (c) 2024 The YAC Authors
2//
3// SPDX-License-Identifier: BSD-3-Clause
4
5#include <stdlib.h>
6#include <string.h>
7
8#include "ensure_array_size.h"
9#include "utils_core.h"
10
11struct run {
12
13 size_t count;
15};
16
17static void determine_runs(char * base, size_t num, size_t size,
18 int (*compar)(const void *,const void *),
19 struct run ** runs, size_t * num_runs) {
20
21 size_t runs_array_size = 0;
22 *runs = NULL;
23 *num_runs = 1;
24
25 ENSURE_ARRAY_SIZE(*runs, runs_array_size, *num_runs);
26 (*runs)->count = 1;
27 (*runs)->ordering = -1;
28
29 char * curr_element = base + size;
30 int curr_order = -1;
31 size_t * curr_count = &((*runs)->count);
32
33 for (size_t i = 1; i < num; ++i) {
34
35 int order = compar(curr_element - size, curr_element);
36
37 if ((order == 0) || !((order < 0) ^ (curr_order < 0))) {
38
39 ++*curr_count;
40
41 } else {
42
43 ENSURE_ARRAY_SIZE(*runs, runs_array_size, *num_runs + 1);
44
45 curr_order = order;
46 curr_count = &((*runs)[*num_runs].count);
47 (*runs)[*num_runs].count = 1;
48 (*runs)[*num_runs].ordering = order;
49 ++*num_runs;
50 }
51
52 curr_element += size;
53 }
54}
55
56static void merge(char * base_a, size_t num_a, int a_ascending,
57 char * base_b, size_t num_b, int b_ascending,
58 size_t size,
59 int (*compar)(const void *,const void *),
60 char * target) {
61
62 char * curr_a = base_a + ((a_ascending)?0:((num_a - 1) * size));
63 char * curr_b = base_b + ((b_ascending)?0:((num_b - 1) * size));
64 int inc_a = (a_ascending)?(size):(-size);
65 int inc_b = (b_ascending)?(size):(-size);
66 char * end_a = curr_a + inc_a * num_a;
67 char * end_b = curr_b + inc_b * num_b;
68
69 while (curr_a != end_a && curr_b != end_b) {
70
71 char * from;
72
73 if (compar(curr_a, curr_b) <= 0) {
74 from = curr_a;
75 curr_a += inc_a;
76 } else {
77 from = curr_b;
78 curr_b += inc_b;
79 }
80
81 memcpy(target, from, size);
82 target += size;
83 }
84
85 size_t diff = (size_t)(end_a - curr_a);
86 if (diff) {
87 memcpy(target, curr_a, diff);
88 target += diff;
89 }
90
91 diff = (size_t)(end_b - curr_b);
92 if (diff) {
93 memcpy(target, curr_b, diff);
94 target += diff;
95 }
96}
97
98static void merge_runs(
99 char * base, size_t size, int (*compar)(const void *,const void *),
100 struct run ** runs, size_t * num_runs, char * buffer) {
101
102 size_t num_merges = *num_runs >> 1;
103
104 struct run * curr_runs = *runs;
105
106 for (size_t i = 0; i < num_merges; ++i) {
107
108 merge(base, curr_runs[0].count, curr_runs[0].ordering < 0,
109 base + curr_runs[0].count * size, curr_runs[1].count,
110 curr_runs[1].ordering < 0, size, compar, buffer);
111
112 base += (curr_runs[0].count + curr_runs[1].count) * size;
113 buffer += (curr_runs[0].count + curr_runs[1].count) * size;
114
115 (*runs)[i].count = curr_runs[0].count + curr_runs[1].count;
116 (*runs)[i].ordering = -1;
117
118 curr_runs += 2;
119 }
120
121 if ((*num_runs) & 1) {
122
123 (*runs)[num_merges] = (*runs)[*num_runs-1];
124 memcpy(buffer, base, (*runs)[num_merges].count * size);
125 }
126
127 *num_runs = num_merges + ((*num_runs) & 1);
128}
129
134void yac_mergesort(void * base, size_t num, size_t size,
135 int (*compar)(const void *,const void *)) {
136
137 if (size == 0 || num == 0) return;
138
139 struct run * runs;
140 size_t num_runs;
141
142 char * buffer = xmalloc(num * size);
143
144 determine_runs((char*)base, num, size, compar, &runs, &num_runs);
145
146 while (num_runs > 1) {
147 merge_runs((char*)base, size, compar, &runs, &num_runs, buffer);
148 merge_runs(buffer, size, compar, &runs, &num_runs, (char*)base);
149 };
150
151 free(runs);
152 free(buffer);
153}
154
#define ENSURE_ARRAY_SIZE(arrayp, curr_array_size, req_size)
void yac_mergesort(void *base, size_t num, size_t size, int(*compar)(const void *, const void *))
Definition mergesort.c:134
static void determine_runs(char *base, size_t num, size_t size, int(*compar)(const void *, const void *), struct run **runs, size_t *num_runs)
Definition mergesort.c:17
static void merge(char *base_a, size_t num_a, int a_ascending, char *base_b, size_t num_b, int b_ascending, size_t size, int(*compar)(const void *, const void *), char *target)
Definition mergesort.c:56
static void merge_runs(char *base, size_t size, int(*compar)(const void *, const void *), struct run **runs, size_t *num_runs, char *buffer)
Definition mergesort.c:98
#define xmalloc(size)
Definition ppm_xfuncs.h:66
size_t count
Definition mergesort.c:13
int ordering
Definition mergesort.c:14