Mercurial > hg > CbC > CbC_gcc

comparison gcc/sort.cc @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Platform-independent deterministic sort function. 1 /* Platform-independent deterministic sort function.
2 Copyright (C) 2018 Free Software Foundation, Inc. 2 Copyright (C) 2018-2020 Free Software Foundation, Inc.
3 Contributed by Alexander Monakov. 3 Contributed by Alexander Monakov.
4 4
5 This file is part of GCC. 5 This file is part of GCC.
6 6
7 GCC is free software; you can redistribute it and/or modify it 7 GCC is free software; you can redistribute it and/or modify it
56 size_t n; // number of elements 56 size_t n; // number of elements
57 size_t size; // element size 57 size_t size; // element size
58 size_t nlim; // limit for network sort 58 size_t nlim; // limit for network sort
59 }; 59 };
60 60
61 /* Like sort_ctx, but for use with qsort_r-style comparators. Several
62 functions in this file are templates that work with either context type. */
63 struct sort_r_ctx
64 {
65 void *data;
66 sort_r_cmp_fn *cmp_;
67 char *out;
68 size_t n;
69 size_t size;
70 size_t nlim;
71 int cmp (const void *a, const void *b)
72 {
73 return cmp_ (a, b, data);
74 }
75 };
76
61 /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements, 77 /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
62 placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */ 78 placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */
79 template<typename sort_ctx>
63 static void 80 static void
64 reorder23 (sort_ctx *c, char *e0, char *e1, char *e2) 81 reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
65 { 82 {
66 #define REORDER_23(TYPE, STRIDE, OFFSET) \ 83 #define REORDER_23(TYPE, STRIDE, OFFSET) \
67 do { \ 84 do { \
88 REORDER_23 (char, c->size, offset); 105 REORDER_23 (char, c->size, offset);
89 } 106 }
90 } 107 }
91 108
92 /* Like reorder23, but permute 4 or 5 elements. */ 109 /* Like reorder23, but permute 4 or 5 elements. */
110 template<typename sort_ctx>
93 static void 111 static void
94 reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4) 112 reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
95 { 113 {
96 #define REORDER_45(TYPE, STRIDE, OFFSET) \ 114 #define REORDER_45(TYPE, STRIDE, OFFSET) \
97 do { \ 115 do { \
125 143
126 /* Helper for netsort. Invoke comparator CMP on E0 and E1. 144 /* Helper for netsort. Invoke comparator CMP on E0 and E1.
127 Return E0^E1 if E0 compares less than E1, zero otherwise. 145 Return E0^E1 if E0 compares less than E1, zero otherwise.
128 This is noinline to avoid code growth and confine invocation 146 This is noinline to avoid code growth and confine invocation
129 to a single call site, assisting indirect branch prediction. */ 147 to a single call site, assisting indirect branch prediction. */
148 template<typename sort_ctx>
130 noinline static intptr_t 149 noinline static intptr_t
131 cmp1 (char *e0, char *e1, cmp_fn *cmp) 150 cmp1 (char *e0, char *e1, sort_ctx *c)
132 { 151 {
133 intptr_t x = (intptr_t)e0 ^ (intptr_t)e1; 152 intptr_t x = (intptr_t)e0 ^ (intptr_t)e1;
134 return x & (cmp (e0, e1) >> 31); 153 return x & (c->cmp (e0, e1) >> 31);
135 } 154 }
136 155
137 /* Execute network sort on 2 to 5 elements from IN, placing them into C->OUT. 156 /* Execute network sort on 2 to 5 elements from IN, placing them into C->OUT.
138 IN may be equal to C->OUT, in which case elements are sorted in place. */ 157 IN may be equal to C->OUT, in which case elements are sorted in place. */
158 template<typename sort_ctx>
139 static void 159 static void
140 netsort (char *in, sort_ctx *c) 160 netsort (char *in, sort_ctx *c)
141 { 161 {
142 #define CMP(e0, e1) \ 162 #define CMP(e0, e1) \
143 do { \ 163 do { \
144 intptr_t x = cmp1 (e1, e0, c->cmp); \ 164 intptr_t x = cmp1 (e1, e0, c); \
145 e0 = (char *)((intptr_t)e0 ^ x); \ 165 e0 = (char *)((intptr_t)e0 ^ x); \
146 e1 = (char *)((intptr_t)e1 ^ x); \ 166 e1 = (char *)((intptr_t)e1 ^ x); \
147 } while (0) 167 } while (0)
148 168
149 char *e0 = in, *e1 = e0 + c->size, *e2 = e1 + c->size; 169 char *e0 = in, *e1 = e0 + c->size, *e2 = e1 + c->size;
174 } 194 }
175 195
176 /* Execute merge sort on N elements from IN, placing them into OUT, 196 /* Execute merge sort on N elements from IN, placing them into OUT,
177 using TMP as temporary storage if IN is equal to OUT. 197 using TMP as temporary storage if IN is equal to OUT.
178 This is a stable sort if netsort is used only for 2 or 3 elements. */ 198 This is a stable sort if netsort is used only for 2 or 3 elements. */
199 template<typename sort_ctx>
179 static void 200 static void
180 mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp) 201 mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp)
181 { 202 {
182 if (likely (n <= c->nlim)) 203 if (likely (n <= c->nlim))
183 { 204 {
215 MERGE_ELTSIZE (c->size); 236 MERGE_ELTSIZE (c->size);
216 } 237 }
217 memcpy (out, l, r - out); 238 memcpy (out, l, r - out);
218 } 239 }
219 240
241 #if CHECKING_P
242 /* Adapter for using two-argument comparators in functions expecting the
243 three-argument sort_r_cmp_fn type. */
244 static int
245 cmp2to3 (const void *a, const void *b, void *c)
246 {
247 return ((cmp_fn *)c) (a, b);
248 }
249 #endif
250
251 /* Replacement for C qsort. */
220 void 252 void
221 gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp) 253 gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
222 { 254 {
223 if (n < 2) 255 if (n < 2)
224 return; 256 return;
233 void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz); 265 void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz);
234 mergesort (base, &c, n, base, (char *)buf); 266 mergesort (base, &c, n, base, (char *)buf);
235 if (buf != scratch) 267 if (buf != scratch)
236 free (buf); 268 free (buf);
237 #if CHECKING_P 269 #if CHECKING_P
238 qsort_chk (vbase, n, size, cmp); 270 qsort_chk (vbase, n, size, cmp2to3, (void*)cmp);
239 #endif 271 #endif
240 } 272 }
241 273
274 /* Substitute for Glibc qsort_r. */
275 void
276 gcc_sort_r (void *vbase, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
277 {
278 if (n < 2)
279 return;
280 char *base = (char *)vbase;
281 sort_r_ctx c = {data, cmp, base, n, size, 5};
282 long long scratch[32];
283 size_t bufsz = (n / 2) * size;
284 void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz);
285 mergesort (base, &c, n, base, (char *)buf);
286 if (buf != scratch)
287 free (buf);
288 #if CHECKING_P
289 qsort_chk (vbase, n, size, cmp, data);
290 #endif
291 }
292
293 /* Stable sort, signature-compatible to C qsort. */
242 void 294 void
243 gcc_stablesort (void *vbase, size_t n, size_t size, cmp_fn *cmp) 295 gcc_stablesort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
244 { 296 {
245 gcc_qsort (vbase, n, ~size, cmp); 297 gcc_qsort (vbase, n, ~size, cmp);
246 } 298 }