![[BACK]](/icons/back.gif){kind=icon}
Return to radixsort.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / sort|
Return to radixsort.c CVS log | Up to [local] / src / usr.bin / sort |
1.2 ! millert 1: /* $OpenBSD: radixsort.c,v 1.1 2015/03/17 17:45:13 millert Exp $ */
1.1 millert 2:
3: /*-
4: * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
5: * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
6: * All rights reserved.
7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: *
17: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27: * SUCH DAMAGE.
28: */
29:
30: #include <errno.h>
31: #include <err.h>
32: #include <langinfo.h>
33: #include <math.h>
34: #include <stdlib.h>
35: #include <string.h>
36: #include <wchar.h>
37: #include <wctype.h>
38: #include <unistd.h>
39:
40: #include "coll.h"
41: #include "radixsort.h"
42:
43: #define DEFAULT_SORT_FUNC_RADIXSORT mergesort
44:
45: #define TINY_NODE(sl) ((sl)->tosort_num < 65)
46: #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
47:
48: /* are we sorting in reverse order ? */
49: static bool reverse_sort;
50:
51: /* sort sub-levels array size */
52: static const size_t slsz = 256 * sizeof(struct sort_level *);
53:
54: /* one sort level structure */
55: struct sort_level {
56: struct sort_level **sublevels;
57: struct sort_list_item **leaves;
58: struct sort_list_item **sorted;
59: struct sort_list_item **tosort;
60: size_t leaves_num;
61: size_t leaves_sz;
62: size_t level;
63: size_t real_sln;
64: size_t start_position;
65: size_t sln;
66: size_t tosort_num;
67: size_t tosort_sz;
68: };
69:
70: /* stack of sort levels ready to be sorted */
71: struct level_stack {
72: struct level_stack *next;
73: struct sort_level *sl;
74: };
75:
76: static struct level_stack *g_ls;
77:
78: /*
79: * Push sort level to the stack
80: */
81: static inline void
82: push_ls(struct sort_level* sl)
83: {
84: struct level_stack *new_ls;
85:
86: new_ls = sort_malloc(sizeof(struct level_stack));
87: new_ls->sl = sl;
88:
89: new_ls->next = g_ls;
90: g_ls = new_ls;
91: }
92:
93: /*
94: * Pop sort level from the stack (single-threaded style)
95: */
96: static inline struct sort_level *
97: pop_ls_st(void)
98: {
99: struct sort_level *sl;
100:
101: if (g_ls) {
102: struct level_stack *saved_ls;
103:
104: sl = g_ls->sl;
105: saved_ls = g_ls;
106: g_ls = g_ls->next;
107: sort_free(saved_ls);
108: } else
109: sl = NULL;
110:
111: return sl;
112: }
113:
114: static void
115: add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
116: {
117: struct sort_level *ssl;
118:
119: ssl = sl->sublevels[indx];
120:
121: if (ssl == NULL) {
1.2 ! millert 122: ssl = sort_calloc(1, sizeof(struct sort_level));
1.1 millert 123: ssl->level = sl->level + 1;
124: sl->sublevels[indx] = ssl;
125:
126: ++(sl->real_sln);
127: }
128:
129: if (++(ssl->tosort_num) > ssl->tosort_sz) {
130: ssl->tosort_sz = ssl->tosort_num + 128;
131: ssl->tosort = sort_reallocarray(ssl->tosort, ssl->tosort_sz,
132: sizeof(struct sort_list_item *));
133: }
134:
135: ssl->tosort[ssl->tosort_num - 1] = item;
136: }
137:
138: static inline void
139: add_leaf(struct sort_level *sl, struct sort_list_item *item)
140: {
141:
142: if (++(sl->leaves_num) > sl->leaves_sz) {
143: sl->leaves_sz = sl->leaves_num + 128;
144: sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
145: sizeof(struct sort_list_item *));
146: }
147: sl->leaves[sl->leaves_num - 1] = item;
148: }
149:
150: static inline int
151: get_wc_index(struct sort_list_item *sli, size_t level)
152: {
153: const struct bwstring *bws;
154:
155: bws = sli->ka.key[0].k;
156:
157: if ((BWSLEN(bws) > level))
158: return (unsigned char)BWS_GET(bws, level);
159: return -1;
160: }
161:
162: static void
163: place_item(struct sort_level *sl, size_t item)
164: {
165: struct sort_list_item *sli;
166: int c;
167:
168: sli = sl->tosort[item];
169: c = get_wc_index(sli, sl->level);
170:
171: if (c == -1)
172: add_leaf(sl, sli);
173: else
174: add_to_sublevel(sl, sli, c);
175: }
176:
177: static void
178: free_sort_level(struct sort_level *sl)
179: {
180:
181: if (sl) {
182: if (sl->leaves)
183: sort_free(sl->leaves);
184:
185: if (sl->level > 0)
186: sort_free(sl->tosort);
187:
188: if (sl->sublevels) {
189: struct sort_level *slc;
190: size_t i, sln;
191:
192: sln = sl->sln;
193:
194: for (i = 0; i < sln; ++i) {
195: slc = sl->sublevels[i];
196: if (slc)
197: free_sort_level(slc);
198: }
199:
200: sort_free(sl->sublevels);
201: }
202:
203: sort_free(sl);
204: }
205: }
206:
207: static void
208: run_sort_level_next(struct sort_level *sl)
209: {
210: struct sort_level *slc;
211: size_t i, sln, tosort_num;
212:
213: if (sl->sublevels) {
214: sort_free(sl->sublevels);
215: sl->sublevels = NULL;
216: }
217:
218: switch (sl->tosort_num){
219: case 0:
220: goto end;
221: case 1:
222: sl->sorted[sl->start_position] = sl->tosort[0];
223: goto end;
224: case 2:
225: if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
226: sl->level) > 0) {
227: sl->sorted[sl->start_position++] = sl->tosort[1];
228: sl->sorted[sl->start_position] = sl->tosort[0];
229: } else {
230: sl->sorted[sl->start_position++] = sl->tosort[0];
231: sl->sorted[sl->start_position] = sl->tosort[1];
232: }
233:
234: goto end;
235: default:
236: if (TINY_NODE(sl) || (sl->level > 15)) {
237: listcoll_t func;
238:
239: func = get_list_call_func(sl->level);
240:
241: sl->leaves = sl->tosort;
242: sl->leaves_num = sl->tosort_num;
243: sl->leaves_sz = sl->leaves_num;
244: sl->leaves = sort_reallocarray(sl->leaves,
245: sl->leaves_sz, sizeof(struct sort_list_item *));
246: sl->tosort = NULL;
247: sl->tosort_num = 0;
248: sl->tosort_sz = 0;
249: sl->sln = 0;
250: sl->real_sln = 0;
251: if (sort_opts_vals.sflag) {
252: if (mergesort(sl->leaves, sl->leaves_num,
253: sizeof(struct sort_list_item *),
254: (int(*)(const void *, const void *)) func) == -1)
255: /* NOTREACHED */
256: err(2, "Radix sort error 3");
257: } else
258: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
259: sizeof(struct sort_list_item *),
260: (int(*)(const void *, const void *)) func);
261:
262: memcpy(sl->sorted + sl->start_position,
263: sl->leaves, sl->leaves_num *
264: sizeof(struct sort_list_item *));
265:
266: goto end;
267: } else {
268: sl->tosort_sz = sl->tosort_num;
269: sl->tosort = sort_reallocarray(sl->tosort,
270: sl->tosort_sz, sizeof(struct sort_list_item *));
271: }
272: }
273:
274: sl->sln = 256;
1.2 ! millert 275: sl->sublevels = sort_calloc(1, slsz);
1.1 millert 276: sl->real_sln = 0;
277:
278: tosort_num = sl->tosort_num;
279: for (i = 0; i < tosort_num; ++i)
280: place_item(sl, i);
281:
282: sort_free(sl->tosort);
283: sl->tosort = NULL;
284: sl->tosort_num = 0;
285: sl->tosort_sz = 0;
286:
287: if (sl->leaves_num > 1) {
288: if (keys_num > 1) {
289: if (sort_opts_vals.sflag) {
290: mergesort(sl->leaves, sl->leaves_num,
291: sizeof(struct sort_list_item *), list_coll);
292: } else {
293: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
294: sizeof(struct sort_list_item *), list_coll);
295: }
296: } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
297: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
298: sizeof(struct sort_list_item *), list_coll);
299: }
300: }
301:
302: sl->leaves_sz = sl->leaves_num;
303: sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
304: sizeof(struct sort_list_item *));
305:
306: if (!reverse_sort) {
307: memcpy(sl->sorted + sl->start_position, sl->leaves,
308: sl->leaves_num * sizeof(struct sort_list_item *));
309: sl->start_position += sl->leaves_num;
310:
311: sort_free(sl->leaves);
312: sl->leaves = NULL;
313: sl->leaves_num = 0;
314: sl->leaves_sz = 0;
315:
316: sln = sl->sln;
317:
318: for (i = 0; i < sln; ++i) {
319: slc = sl->sublevels[i];
320:
321: if (slc) {
322: slc->sorted = sl->sorted;
323: slc->start_position = sl->start_position;
324: sl->start_position += slc->tosort_num;
325: if (SMALL_NODE(slc))
326: run_sort_level_next(slc);
327: else
328: push_ls(slc);
329: sl->sublevels[i] = NULL;
330: }
331: }
332:
333: } else {
334: size_t n;
335:
336: sln = sl->sln;
337:
338: for (i = 0; i < sln; ++i) {
339: n = sln - i - 1;
340: slc = sl->sublevels[n];
341:
342: if (slc) {
343: slc->sorted = sl->sorted;
344: slc->start_position = sl->start_position;
345: sl->start_position += slc->tosort_num;
346: if (SMALL_NODE(slc))
347: run_sort_level_next(slc);
348: else
349: push_ls(slc);
350: sl->sublevels[n] = NULL;
351: }
352: }
353:
354: memcpy(sl->sorted + sl->start_position, sl->leaves,
355: sl->leaves_num * sizeof(struct sort_list_item *));
356: }
357:
358: end:
359: free_sort_level(sl);
360: }
361:
362: /*
363: * Single-threaded sort cycle
364: */
365: static void
366: run_sort_cycle_st(void)
367: {
368: struct sort_level *slc;
369:
370: for (;;) {
371: slc = pop_ls_st();
372: if (slc == NULL) {
373: break;
374: }
375: run_sort_level_next(slc);
376: }
377: }
378:
379: static void
380: run_top_sort_level(struct sort_level *sl)
381: {
382: struct sort_level *slc;
383: size_t i;
384:
385: reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
386: default_sort_mods->rflag;
387:
388: sl->start_position = 0;
389: sl->sln = 256;
1.2 ! millert 390: sl->sublevels = sort_calloc(1, slsz);
1.1 millert 391:
392: for (i = 0; i < sl->tosort_num; ++i)
393: place_item(sl, i);
394:
395: if (sl->leaves_num > 1) {
396: if (keys_num > 1) {
397: if (sort_opts_vals.sflag) {
398: mergesort(sl->leaves, sl->leaves_num,
399: sizeof(struct sort_list_item *), list_coll);
400: } else {
401: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
402: sizeof(struct sort_list_item *), list_coll);
403: }
404: } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
405: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
406: sizeof(struct sort_list_item *), list_coll);
407: }
408: }
409:
410: if (!reverse_sort) {
411: size_t i;
412:
413: memcpy(sl->tosort + sl->start_position, sl->leaves,
414: sl->leaves_num * sizeof(struct sort_list_item *));
415: sl->start_position += sl->leaves_num;
416:
417: for (i = 0; i < sl->sln; ++i) {
418: slc = sl->sublevels[i];
419:
420: if (slc) {
421: slc->sorted = sl->tosort;
422: slc->start_position = sl->start_position;
423: sl->start_position += slc->tosort_num;
424: push_ls(slc);
425: sl->sublevels[i] = NULL;
426: }
427: }
428:
429: } else {
430: size_t i, n;
431:
432: for (i = 0; i < sl->sln; ++i) {
433:
434: n = sl->sln - i - 1;
435: slc = sl->sublevels[n];
436:
437: if (slc) {
438: slc->sorted = sl->tosort;
439: slc->start_position = sl->start_position;
440: sl->start_position += slc->tosort_num;
441: push_ls(slc);
442: sl->sublevels[n] = NULL;
443: }
444: }
445:
446: memcpy(sl->tosort + sl->start_position, sl->leaves,
447: sl->leaves_num * sizeof(struct sort_list_item *));
448: }
449: run_sort_cycle_st();
450: }
451:
452: void
453: rxsort(struct sort_list_item **base, size_t nmemb)
454: {
455: struct sort_level *sl;
456:
1.2 ! millert 457: sl = sort_calloc(1, sizeof(struct sort_level));
1.1 millert 458: sl->tosort = base;
459: sl->tosort_num = nmemb;
460: sl->tosort_sz = nmemb;
461:
462: run_top_sort_level(sl);
463:
464: free_sort_level(sl);
465: }