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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
/* This file is part of GNU Dico
Copyright (C) 2018-2024 Sergey Poznyakoff
GNU Dico is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GNU Dico is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Dico. If not, see <http://www.gnu.org/licenses/>. */
#include <config.h>
#include "dico.h"
#include <string.h>
static void *dico_mergesort(void *a, void *b, size_t nmemb, size_t size,
int (*comp)(const void *, const void *, void *),
void *closure);
static void merge(void *source, void *work, size_t size,
size_t left, size_t right, size_t end,
int (*comp)(const void *, const void *, void *),
void *closure);
int
dico_sort(void *base, size_t nmemb, size_t size,
int (*comp)(const void *, const void *, void *),
void *closure)
{
void *tmp, *res;
tmp = calloc(nmemb, size);
if (!tmp)
return -1;
res = dico_mergesort(base, tmp, nmemb, size, comp, closure);
if (res != base)
memcpy(base, res, nmemb * size);
free(tmp);
return 0;
}
static inline size_t
min(size_t a, size_t b)
{
return a < b ? a : b;
}
static void *
dico_mergesort(void *a, void *b, size_t nmemb, size_t size,
int (*comp)(const void *, const void *, void *),
void *closure)
{
size_t width;
for (width = 1; width < nmemb; width <<= 1) {
size_t i;
void *t;
for (i = 0; i < nmemb; i += 2 * width) {
merge(a, b, size,
i, min(i + width, nmemb), min(i + 2 * width, nmemb),
comp, closure);
}
t = a;
a = b;
b = t;
}
return a;
}
static void
merge(void *source, void *work, size_t size,
size_t left, size_t right, size_t end,
int (*comp)(const void *, const void *, void *),
void *closure)
{
size_t i = left;
size_t j = right;
size_t k;
#define MEMB(b,n) ((char*)(b) + (n) * size)
#define COPY(dp,dn,sp,sn) (memcpy(MEMB(dp,dn), MEMB(sp,sn), size))
for (k = left; k < end; k++) {
if (i < right
&& (j >= end || comp(MEMB(source, i),
MEMB(source, j),
closure) <= 0)) {
COPY(work, k, source, i);
i++;
} else {
COPY(work, k, source, j);
j++;
}
}
}
|
