Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 :
17 : #define RADIX 8 /* one char at a time */
18 : #define NBUCKETS (1 << RADIX)
19 :
20 : gdk_return
21 20143 : GDKrsort(void *restrict h, void *restrict t, size_t n, size_t hs, size_t ts, bool reverse, bool isuuid)
22 : {
23 20143 : size_t (*counts)[NBUCKETS] = GDKmalloc(hs * sizeof(counts[0]));
24 20143 : size_t pos[NBUCKETS];
25 20143 : uint8_t *h1 = h;
26 20143 : uint8_t *h2;
27 20143 : uint8_t *t1 = NULL;
28 20143 : uint8_t *t2 = NULL;
29 20143 : Heap tmph, tmpt;
30 :
31 20143 : if (counts == NULL)
32 : return GDK_FAIL;
33 :
34 20143 : tmph = tmpt = (Heap) {
35 : .farmid = 1,
36 : };
37 :
38 40286 : snprintf(tmph.filename, sizeof(tmph.filename), "%s%crsort%zuh",
39 20143 : TEMPDIR_NAME, DIR_SEP, (size_t) MT_getpid());
40 20143 : if (HEAPalloc(&tmph, n, hs) != GDK_SUCCEED) {
41 0 : GDKfree(counts);
42 0 : return GDK_FAIL;
43 : }
44 20143 : h2 = (uint8_t *) tmph.base;
45 :
46 20143 : if (t) {
47 39916 : snprintf(tmpt.filename, sizeof(tmpt.filename), "%s%crsort%zut",
48 19958 : TEMPDIR_NAME, DIR_SEP, (size_t) MT_getpid());
49 19958 : if (HEAPalloc(&tmpt, n, ts) != GDK_SUCCEED) {
50 0 : GDKfree(counts);
51 0 : HEAPfree(&tmph, true);
52 0 : return GDK_FAIL;
53 : }
54 19958 : t1 = t;
55 19958 : t2 = (uint8_t *) tmpt.base;
56 : } else {
57 : ts = 0;
58 : }
59 :
60 20143 : memset(counts, 0, hs * sizeof(counts[0]));
61 : #ifndef WORDS_BIGENDIAN
62 20143 : if (isuuid /* UUID, treat like big-endian */) {
63 : #endif
64 5 : for (size_t i = 0, o = 0; i < n; i++, o += hs) {
65 68 : for (size_t j = 0, k = hs - 1; j < hs; j++, k--) {
66 64 : uint8_t v = h1[o + k];
67 64 : counts[j][v]++;
68 : }
69 : }
70 : #ifndef WORDS_BIGENDIAN
71 : } else {
72 45465960 : for (size_t i = 0, o = 0; i < n; i++, o += hs) {
73 243051117 : for (size_t j = 0; j < hs; j++) {
74 197605299 : uint8_t v = h1[o + j];
75 197605299 : counts[j][v]++;
76 : }
77 : }
78 : }
79 : #endif
80 : /* When sorting in ascending order, the negative numbers occupy
81 : * the second half of the buckets in the last iteration; when
82 : * sorting in descending order, the negative numbers occupy the
83 : * first half. In either case, at the end we need to put the
84 : * second half first and the first half after. */
85 20143 : size_t negpos = 0;
86 101427 : for (size_t j = 0, k = hs - 1; j < hs; j++, k--) {
87 81284 : size_t nb = counts[j][0] > 0;
88 81284 : if (reverse) {
89 430 : pos[NBUCKETS - 1] = 0;
90 110080 : for (size_t i = NBUCKETS - 1; i > 0; i--) {
91 109650 : pos[i - 1] = pos[i] + counts[j][i];
92 109650 : nb += counts[j][i] > 0;
93 : }
94 : } else {
95 80854 : pos[0] = 0;
96 20698624 : for (size_t i = 1; i < NBUCKETS; i++) {
97 20617770 : pos[i] = pos[i - 1] + counts[j][i - 1];
98 20617770 : nb += counts[j][i] > 0;
99 : }
100 : }
101 : /* we're only interested in the position in the last
102 : * iteration */
103 81284 : negpos = pos[NBUCKETS / 2 - reverse];
104 81284 : if (nb == 1) {
105 : /* no need to reshuffle data for this iteration:
106 : * everything is in the same bucket */
107 21901 : continue;
108 : }
109 : /* note, this loop changes the pos array */
110 : #ifndef WORDS_BIGENDIAN
111 59383 : if (isuuid /* UUID, treat like big-endian */)
112 : #endif
113 80 : for (size_t i = 0, ho = 0, to = 0; i < n; i++, ho += hs, to += ts) {
114 64 : uint8_t v = h1[ho + k];
115 64 : if (t)
116 64 : memcpy(t2 + ts * pos[v], t1 + to, ts);
117 64 : memcpy(h2 + hs * pos[v]++, h1 + ho, hs);
118 : }
119 : #ifndef WORDS_BIGENDIAN
120 : else
121 86876127 : for (size_t i = 0, ho = 0, to = 0; i < n; i++, ho += hs, to += ts) {
122 86816760 : uint8_t v = h1[ho + j];
123 86816760 : if (t)
124 83439152 : memcpy(t2 + ts * pos[v], t1 + to, ts);
125 86816760 : memcpy(h2 + hs * pos[v]++, h1 + ho, hs);
126 : }
127 : #endif
128 : uint8_t *t = h1;
129 : h1 = h2;
130 : h2 = t;
131 : t = t1;
132 : t1 = t2;
133 : t2 = t;
134 : }
135 20143 : GDKfree(counts);
136 :
137 20143 : if (h1 != (uint8_t *) h) {
138 : /* we need to copy the data back to the correct heap */
139 19141 : if (isuuid) {
140 : /* no negative values in uuid, so no shuffling */
141 0 : memcpy(h2, h1, n * hs);
142 0 : if (t)
143 0 : memcpy(t2, t1, n * ts);
144 : } else {
145 : /* copy the negative integers to the start, copy positive after */
146 19141 : if (negpos < n) {
147 47 : memcpy(h2, h1 + hs * negpos, (n - negpos) * hs);
148 47 : if (t)
149 44 : memcpy(t2, t1 + ts * negpos, (n - negpos) * ts);
150 : }
151 19141 : if (negpos > 0) {
152 19108 : memcpy(h2 + hs * (n - negpos), h1, negpos * hs);
153 19108 : if (t)
154 18960 : memcpy(t2 + ts * (n - negpos), t1, negpos * ts);
155 : }
156 : }
157 1002 : } else if (negpos > 0 && negpos < n && !isuuid) {
158 : /* copy the negative integers to the start, copy positive after */
159 28 : memcpy(h2, h1 + hs * negpos, (n - negpos) * hs);
160 28 : memcpy(h2 + hs * (n - negpos), h1, negpos * hs);
161 28 : memcpy(h, h2, n * hs);
162 28 : if (t) {
163 26 : memcpy(t2, t1 + ts * negpos, (n - negpos) * ts);
164 26 : memcpy(t2 + ts * (n - negpos), t1, negpos * ts);
165 26 : memcpy(t, t2, n * ts);
166 : }
167 : } /* else, everything is already in the correct place */
168 20143 : HEAPfree(&tmph, true);
169 20143 : if (t)
170 19958 : HEAPfree(&tmpt, true);
171 : return GDK_SUCCEED;
172 : }
|
