![[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.1 ! millert 1: /* $OpenBSD$ */
! 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) {
! 122: ssl = sort_malloc(sizeof(struct sort_level));
! 123: memset(ssl, 0, sizeof(struct sort_level));
! 124:
! 125: ssl->level = sl->level + 1;
! 126: sl->sublevels[indx] = ssl;
! 127:
! 128: ++(sl->real_sln);
! 129: }
! 130:
! 131: if (++(ssl->tosort_num) > ssl->tosort_sz) {
! 132: ssl->tosort_sz = ssl->tosort_num + 128;
! 133: ssl->tosort = sort_reallocarray(ssl->tosort, ssl->tosort_sz,
! 134: sizeof(struct sort_list_item *));
! 135: }
! 136:
! 137: ssl->tosort[ssl->tosort_num - 1] = item;
! 138: }
! 139:
! 140: static inline void
! 141: add_leaf(struct sort_level *sl, struct sort_list_item *item)
! 142: {
! 143:
! 144: if (++(sl->leaves_num) > sl->leaves_sz) {
! 145: sl->leaves_sz = sl->leaves_num + 128;
! 146: sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
! 147: sizeof(struct sort_list_item *));
! 148: }
! 149: sl->leaves[sl->leaves_num - 1] = item;
! 150: }
! 151:
! 152: static inline int
! 153: get_wc_index(struct sort_list_item *sli, size_t level)
! 154: {
! 155: const struct bwstring *bws;
! 156:
! 157: bws = sli->ka.key[0].k;
! 158:
! 159: if ((BWSLEN(bws) > level))
! 160: return (unsigned char)BWS_GET(bws, level);
! 161: return -1;
! 162: }
! 163:
! 164: static void
! 165: place_item(struct sort_level *sl, size_t item)
! 166: {
! 167: struct sort_list_item *sli;
! 168: int c;
! 169:
! 170: sli = sl->tosort[item];
! 171: c = get_wc_index(sli, sl->level);
! 172:
! 173: if (c == -1)
! 174: add_leaf(sl, sli);
! 175: else
! 176: add_to_sublevel(sl, sli, c);
! 177: }
! 178:
! 179: static void
! 180: free_sort_level(struct sort_level *sl)
! 181: {
! 182:
! 183: if (sl) {
! 184: if (sl->leaves)
! 185: sort_free(sl->leaves);
! 186:
! 187: if (sl->level > 0)
! 188: sort_free(sl->tosort);
! 189:
! 190: if (sl->sublevels) {
! 191: struct sort_level *slc;
! 192: size_t i, sln;
! 193:
! 194: sln = sl->sln;
! 195:
! 196: for (i = 0; i < sln; ++i) {
! 197: slc = sl->sublevels[i];
! 198: if (slc)
! 199: free_sort_level(slc);
! 200: }
! 201:
! 202: sort_free(sl->sublevels);
! 203: }
! 204:
! 205: sort_free(sl);
! 206: }
! 207: }
! 208:
! 209: static void
! 210: run_sort_level_next(struct sort_level *sl)
! 211: {
! 212: struct sort_level *slc;
! 213: size_t i, sln, tosort_num;
! 214:
! 215: if (sl->sublevels) {
! 216: sort_free(sl->sublevels);
! 217: sl->sublevels = NULL;
! 218: }
! 219:
! 220: switch (sl->tosort_num){
! 221: case 0:
! 222: goto end;
! 223: case 1:
! 224: sl->sorted[sl->start_position] = sl->tosort[0];
! 225: goto end;
! 226: case 2:
! 227: if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
! 228: sl->level) > 0) {
! 229: sl->sorted[sl->start_position++] = sl->tosort[1];
! 230: sl->sorted[sl->start_position] = sl->tosort[0];
! 231: } else {
! 232: sl->sorted[sl->start_position++] = sl->tosort[0];
! 233: sl->sorted[sl->start_position] = sl->tosort[1];
! 234: }
! 235:
! 236: goto end;
! 237: default:
! 238: if (TINY_NODE(sl) || (sl->level > 15)) {
! 239: listcoll_t func;
! 240:
! 241: func = get_list_call_func(sl->level);
! 242:
! 243: sl->leaves = sl->tosort;
! 244: sl->leaves_num = sl->tosort_num;
! 245: sl->leaves_sz = sl->leaves_num;
! 246: sl->leaves = sort_reallocarray(sl->leaves,
! 247: sl->leaves_sz, sizeof(struct sort_list_item *));
! 248: sl->tosort = NULL;
! 249: sl->tosort_num = 0;
! 250: sl->tosort_sz = 0;
! 251: sl->sln = 0;
! 252: sl->real_sln = 0;
! 253: if (sort_opts_vals.sflag) {
! 254: if (mergesort(sl->leaves, sl->leaves_num,
! 255: sizeof(struct sort_list_item *),
! 256: (int(*)(const void *, const void *)) func) == -1)
! 257: /* NOTREACHED */
! 258: err(2, "Radix sort error 3");
! 259: } else
! 260: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
! 261: sizeof(struct sort_list_item *),
! 262: (int(*)(const void *, const void *)) func);
! 263:
! 264: memcpy(sl->sorted + sl->start_position,
! 265: sl->leaves, sl->leaves_num *
! 266: sizeof(struct sort_list_item *));
! 267:
! 268: goto end;
! 269: } else {
! 270: sl->tosort_sz = sl->tosort_num;
! 271: sl->tosort = sort_reallocarray(sl->tosort,
! 272: sl->tosort_sz, sizeof(struct sort_list_item *));
! 273: }
! 274: }
! 275:
! 276: sl->sln = 256;
! 277: sl->sublevels = sort_malloc(slsz);
! 278: memset(sl->sublevels, 0, slsz);
! 279:
! 280: sl->real_sln = 0;
! 281:
! 282: tosort_num = sl->tosort_num;
! 283: for (i = 0; i < tosort_num; ++i)
! 284: place_item(sl, i);
! 285:
! 286: sort_free(sl->tosort);
! 287: sl->tosort = NULL;
! 288: sl->tosort_num = 0;
! 289: sl->tosort_sz = 0;
! 290:
! 291: if (sl->leaves_num > 1) {
! 292: if (keys_num > 1) {
! 293: if (sort_opts_vals.sflag) {
! 294: mergesort(sl->leaves, sl->leaves_num,
! 295: sizeof(struct sort_list_item *), list_coll);
! 296: } else {
! 297: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
! 298: sizeof(struct sort_list_item *), list_coll);
! 299: }
! 300: } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
! 301: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
! 302: sizeof(struct sort_list_item *), list_coll);
! 303: }
! 304: }
! 305:
! 306: sl->leaves_sz = sl->leaves_num;
! 307: sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
! 308: sizeof(struct sort_list_item *));
! 309:
! 310: if (!reverse_sort) {
! 311: memcpy(sl->sorted + sl->start_position, sl->leaves,
! 312: sl->leaves_num * sizeof(struct sort_list_item *));
! 313: sl->start_position += sl->leaves_num;
! 314:
! 315: sort_free(sl->leaves);
! 316: sl->leaves = NULL;
! 317: sl->leaves_num = 0;
! 318: sl->leaves_sz = 0;
! 319:
! 320: sln = sl->sln;
! 321:
! 322: for (i = 0; i < sln; ++i) {
! 323: slc = sl->sublevels[i];
! 324:
! 325: if (slc) {
! 326: slc->sorted = sl->sorted;
! 327: slc->start_position = sl->start_position;
! 328: sl->start_position += slc->tosort_num;
! 329: if (SMALL_NODE(slc))
! 330: run_sort_level_next(slc);
! 331: else
! 332: push_ls(slc);
! 333: sl->sublevels[i] = NULL;
! 334: }
! 335: }
! 336:
! 337: } else {
! 338: size_t n;
! 339:
! 340: sln = sl->sln;
! 341:
! 342: for (i = 0; i < sln; ++i) {
! 343: n = sln - i - 1;
! 344: slc = sl->sublevels[n];
! 345:
! 346: if (slc) {
! 347: slc->sorted = sl->sorted;
! 348: slc->start_position = sl->start_position;
! 349: sl->start_position += slc->tosort_num;
! 350: if (SMALL_NODE(slc))
! 351: run_sort_level_next(slc);
! 352: else
! 353: push_ls(slc);
! 354: sl->sublevels[n] = NULL;
! 355: }
! 356: }
! 357:
! 358: memcpy(sl->sorted + sl->start_position, sl->leaves,
! 359: sl->leaves_num * sizeof(struct sort_list_item *));
! 360: }
! 361:
! 362: end:
! 363: free_sort_level(sl);
! 364: }
! 365:
! 366: /*
! 367: * Single-threaded sort cycle
! 368: */
! 369: static void
! 370: run_sort_cycle_st(void)
! 371: {
! 372: struct sort_level *slc;
! 373:
! 374: for (;;) {
! 375: slc = pop_ls_st();
! 376: if (slc == NULL) {
! 377: break;
! 378: }
! 379: run_sort_level_next(slc);
! 380: }
! 381: }
! 382:
! 383: static void
! 384: run_top_sort_level(struct sort_level *sl)
! 385: {
! 386: struct sort_level *slc;
! 387: size_t i;
! 388:
! 389: reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
! 390: default_sort_mods->rflag;
! 391:
! 392: sl->start_position = 0;
! 393: sl->sln = 256;
! 394: sl->sublevels = sort_malloc(slsz);
! 395: memset(sl->sublevels, 0, slsz);
! 396:
! 397: for (i = 0; i < sl->tosort_num; ++i)
! 398: place_item(sl, i);
! 399:
! 400: if (sl->leaves_num > 1) {
! 401: if (keys_num > 1) {
! 402: if (sort_opts_vals.sflag) {
! 403: mergesort(sl->leaves, sl->leaves_num,
! 404: sizeof(struct sort_list_item *), list_coll);
! 405: } else {
! 406: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
! 407: sizeof(struct sort_list_item *), list_coll);
! 408: }
! 409: } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
! 410: DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
! 411: sizeof(struct sort_list_item *), list_coll);
! 412: }
! 413: }
! 414:
! 415: if (!reverse_sort) {
! 416: size_t i;
! 417:
! 418: memcpy(sl->tosort + sl->start_position, sl->leaves,
! 419: sl->leaves_num * sizeof(struct sort_list_item *));
! 420: sl->start_position += sl->leaves_num;
! 421:
! 422: for (i = 0; i < sl->sln; ++i) {
! 423: slc = sl->sublevels[i];
! 424:
! 425: if (slc) {
! 426: slc->sorted = sl->tosort;
! 427: slc->start_position = sl->start_position;
! 428: sl->start_position += slc->tosort_num;
! 429: push_ls(slc);
! 430: sl->sublevels[i] = NULL;
! 431: }
! 432: }
! 433:
! 434: } else {
! 435: size_t i, n;
! 436:
! 437: for (i = 0; i < sl->sln; ++i) {
! 438:
! 439: n = sl->sln - i - 1;
! 440: slc = sl->sublevels[n];
! 441:
! 442: if (slc) {
! 443: slc->sorted = sl->tosort;
! 444: slc->start_position = sl->start_position;
! 445: sl->start_position += slc->tosort_num;
! 446: push_ls(slc);
! 447: sl->sublevels[n] = NULL;
! 448: }
! 449: }
! 450:
! 451: memcpy(sl->tosort + sl->start_position, sl->leaves,
! 452: sl->leaves_num * sizeof(struct sort_list_item *));
! 453: }
! 454: run_sort_cycle_st();
! 455: }
! 456:
! 457: void
! 458: rxsort(struct sort_list_item **base, size_t nmemb)
! 459: {
! 460: struct sort_level *sl;
! 461:
! 462: sl = sort_malloc(sizeof(struct sort_level));
! 463: memset(sl, 0, sizeof(struct sort_level));
! 464:
! 465: sl->tosort = base;
! 466: sl->tosort_num = nmemb;
! 467: sl->tosort_sz = nmemb;
! 468:
! 469: run_top_sort_level(sl);
! 470:
! 471: free_sort_level(sl);
! 472: }