home *** CD-ROM | disk | FTP | other *** search
/ Hall of Fame / HallofFameCDROM.cdr / proglc / maxsort.lzh / MAXSORT.C
Encoding:
C/C++ Source or Header  |  1987-12-30  |  9.2 KB  |  373 lines
  1. /*--------------------------------------------------------------------------
  2.    MAXSORT -- Program that will sort (using a classic shell sort) any file
  3.    regardless of size.  Buffer_size and/or max_num_lines determines when
  4.    to split a file.  If a file is split it will be merged.
  5.  
  6.    Usage:   maxsort [arg1] [arg2]
  7.  
  8.             arg1 = file to be sorted
  9.             arg2 = output of sorted file
  10.  
  11.             By not supplying arg2 the output sorted file will go to
  12.             stdout.
  13.  
  14.             If no arguments are given the program opens for input from
  15.             stdin, and will output to the stdout.
  16.  
  17. ---------------------------------------------------------------------------*/
  18. #include <stdio.h>
  19. #include <malloc.h>
  20.  
  21. /* definitions */
  22. #define min(a, b)       ((a < b) ? a : b)
  23. #define BOOL            int
  24. #define BUFFER_SIZE     50000
  25. #define CTRL_Z          26
  26. #define EOS             '\0'
  27. #define FILE_NAME_LEN   20
  28. #define MAX_STR_LEN     255
  29. #define MAX_NUM_LINES   1000
  30. #define MERGE_ORDER     3
  31. #define TEMP_FILE_END   ".TMP"
  32. #define TEMP_FILE_START "S"
  33.  
  34. /* Globals */
  35. FILE  *infile;
  36. int   lines[MAX_NUM_LINES];
  37. FILE  *merge_files[MERGE_ORDER];
  38. int   next_buf_avail = 0;
  39. int   next_line = 0;
  40. int   next_merge_file = 0;
  41. int   sort_number = 0;
  42.  
  43. /* Forward declarations */
  44. int   compare_strings();
  45. void  copy_to_destination();
  46. BOOL  get_sort_buffer();
  47. void  make_file_name();
  48. void  merge();
  49. void  open_merge_input();
  50. FILE  * open_out_file();
  51. void  resort_merge_buffer();
  52. void  remove_files();
  53. void  sort_buffer();
  54. void  write_lines();
  55.  
  56. main(argc, argv)
  57. int   argc;
  58. char  *argv[];
  59. {
  60.    char  *buffer;
  61.    BOOL  continue_reading;
  62.    int   limit;
  63.    int   merge_index;
  64.    FILE  *outfile;
  65.    char  output_file_name[FILE_NAME_LEN];
  66.  
  67.    infile = stdin;
  68.    output_file_name[0] = EOS;
  69.  
  70.    if ((argc > 1) && ((infile = fopen(argv[1], "r")) == (FILE *) NULL)) {
  71.       fprintf(stderr, "Unable to open %s for input.", argv[1]);
  72.       exit(1);
  73.    }
  74.  
  75.    if (argc > 2)
  76.       strcpy(output_file_name, argv[2]);
  77.  
  78.    buffer = malloc(BUFFER_SIZE);
  79.  
  80.    do {
  81.       continue_reading = get_sort_buffer(buffer);
  82.       outfile = open_out_file(next_merge_file++);
  83.       sort_buffer(buffer, lines, next_line);
  84.       write_lines(outfile, buffer);
  85.       if (fclose(outfile) != NULL) {
  86.          fprintf(stderr, "Unable to close merge file.");
  87.          exit(1);
  88.       }
  89.       fprintf(stderr, "Sort run completed. \n");
  90.    } while (continue_reading);
  91.  
  92.    if (fclose(infile) != NULL) {
  93.       fprintf(stderr, "Unable to close input file.");
  94.       exit(1);
  95.    }
  96.  
  97.    free(buffer);
  98.  
  99.    for (merge_index = 0; (merge_index < (next_merge_file -1));
  100.                                        (merge_index += MERGE_ORDER)) {
  101.       limit = min(merge_index + MERGE_ORDER, next_merge_file);
  102.       open_merge_input(merge_index, limit);
  103.       outfile = open_out_file(next_merge_file++);
  104.       merge(merge_files, outfile, limit - merge_index);
  105.       if (fclose(outfile) != NULL) {
  106.          fprintf(stderr, "Unable to close merge file.");
  107.          exit(1);
  108.       }
  109.       remove_files(merge_files, merge_index, limit);
  110.       fprintf(stderr, "Merge run completed.\n");
  111.    }
  112.  
  113.    if (output_file_name[0] != EOS ) {
  114.       char  tmp_file_name[FILE_NAME_LEN];
  115.  
  116.       make_file_name(--next_merge_file, tmp_file_name);
  117.        unlink(output_file_name);
  118.       if (rename(tmp_file_name, output_file_name) != NULL) {
  119.          fprintf(stderr, "Unable to use output file.");
  120.          exit(1);
  121.       }
  122.    }
  123.    else
  124.       copy_to_destination(--next_merge_file);
  125.          
  126. }
  127.  
  128. /*  COMPARE_STRINGS */
  129.  
  130. int compare_strings(string1, string2)
  131. char  *string1;
  132. char  *string2;
  133. {
  134.    return(strcmp(string1, string2));
  135. }
  136.  
  137.  
  138. /* COPY_TO_DESTINATION */
  139.  
  140. void copy_to_destination(filenum)
  141. int   filenum;
  142. {
  143.    FILE  *fileptr;
  144.    char  filename[FILE_NAME_LEN];
  145.    char  line[MAX_STR_LEN];
  146.    int   value;
  147.  
  148.    make_file_name(filenum, filename);
  149.    if ((fileptr = fopen(filename, "r")) == (FILE *) NULL) {
  150.       fprintf(stderr, "Error in reopening final merge file.");
  151.       exit(1);
  152.    }
  153.  
  154.    while (fgets(line, MAX_STR_LEN, fileptr) != (char *) NULL)
  155.       fputs(line, stdout);
  156.    if (fclose(stdout) != NULL) {
  157.       fprintf(stderr, "Unable to close output file.");
  158.       exit(1);
  159.    }
  160.  
  161.    if (fclose(fileptr) != NULL) {
  162.       fprintf(stderr, "Unable to close merge file.");
  163.       exit(1);
  164.    }
  165.    unlink(filename);
  166. }
  167.  
  168.  
  169. /*  GET_SORT_BUFFER */
  170.  
  171. BOOL get_sort_buffer(buffer)
  172. char  *buffer;
  173. {
  174.    int   curchar;
  175.    
  176.    next_buf_avail = 0;       /* initialize globals */
  177.    next_line = 0;
  178.    lines[0] = 0;
  179.  
  180.    while (((curchar = getc(infile)) != EOF) && (curchar != CTRL_Z)) {
  181.       buffer[next_buf_avail++] = curchar;
  182.  
  183.       if (curchar == '\n') {
  184.          buffer[next_buf_avail -1] = EOS;
  185.          lines[++next_line] = next_buf_avail;
  186.  
  187.          if ((next_line >= MAX_NUM_LINES) ||
  188.                         (next_buf_avail > (BUFFER_SIZE - MAX_STR_LEN)))
  189.             break;
  190.       }
  191.    }
  192.  
  193.    buffer[next_buf_avail -1] = EOS;
  194.  
  195.    return(curchar != EOF);
  196. }
  197.  
  198. /*  MAKE_FILE_NAME */
  199.  
  200. void make_file_name(filenum, destination)
  201. int   filenum;
  202. char  destination[];
  203. {
  204.    char  numbuffer[10];
  205.  
  206.    destination[0] = EOS;
  207.    strcat(destination, TEMP_FILE_START);
  208.    sprintf(numbuffer, "%d", filenum);
  209.    if (strlen(numbuffer) > (8 - strlen(TEMP_FILE_START))) {
  210.       fprintf(stderr, "Too many merge files. ");
  211.       exit(1);
  212.    }
  213.    strcat(destination, numbuffer);
  214.    strcat(destination, TEMP_FILE_END);
  215. }
  216.  
  217.  
  218. /*   MERGE */
  219.  
  220. void merge(merge_files, outfile, numfiles)
  221. FILE  *merge_files[], *outfile;
  222. int   numfiles;
  223. {
  224.    char  merge_buf[MERGE_ORDER * MAX_STR_LEN];
  225.    int   merge_lines[MERGE_ORDER], i, j;
  226.  
  227.    for (i = 0, j = 0; (i < numfiles); i++, j += MAX_STR_LEN) {
  228.       merge_lines[i] = j;
  229.       fgets(&merge_buf[j], MAX_STR_LEN, merge_files[i]);
  230.    }
  231.  
  232.    sort_buffer(merge_buf, merge_lines, numfiles);
  233.  
  234.    while (numfiles > 0) {
  235.       fputs(&merge_buf[merge_lines[0]], outfile);
  236.  
  237.       if (fgets(&merge_buf[merge_lines[0]], MAX_STR_LEN,
  238.                            merge_files[merge_lines[0] / MAX_STR_LEN])
  239.                               == (char *) NULL) {
  240.          merge_lines[0] = merge_lines[--numfiles];
  241.       }
  242.       resort_merge_buffer(merge_buf, merge_lines, numfiles);
  243.    }
  244. }
  245.    
  246. /* OPEN_MERGE_INPUT */
  247.  
  248. void open_merge_input(start, stop)
  249. int   start, stop;
  250. {
  251.    int   i;
  252.    int   range = stop - start;
  253.    char  file_name[FILE_NAME_LEN];
  254.  
  255.    if (range > MERGE_ORDER) {
  256.       fprintf(stderr, "Internal error.");
  257.       exit(1);
  258.    }
  259.    for (i = 0; (i < range); i++) {
  260.       make_file_name(start + i, file_name);
  261.       if ((merge_files[i] = fopen(file_name, "r")) == (FILE *) NULL) {
  262.          fprintf(stderr, "Error in reopening merge file.");
  263.          exit(1);
  264.       }
  265.    }
  266. }
  267.  
  268.  
  269. /*  OPEN_OUT_FILE */
  270.  
  271. FILE *open_out_file(filenum)
  272. int   filenum;
  273. {
  274.    FILE  *fileptr;
  275.    char  file_name[FILE_NAME_LEN];
  276.  
  277.    make_file_name(filenum, file_name);
  278.    if ((fileptr = fopen(file_name, "w")) == (FILE *) NULL) {
  279.       fprintf(stderr, "Error in opening merge file.");
  280.       exit(1);
  281.    }
  282.    return(fileptr);
  283. }
  284.  
  285. /* RESORT_MERGE_BUFFER */
  286.  
  287. void  resort_merge_buffer(merge_buf, merge_lines, numfiles)
  288. char  merge_buf[];
  289. int   merge_lines[];
  290. int   numfiles;
  291. {
  292.    register int   i = 0;
  293.    register int   j = 1;
  294.    int            temp;
  295.  
  296.    while (j < numfiles) {
  297.       if (j < (numfiles - 1))
  298.          if (compare_strings(&merge_buf[merge_lines[j]],
  299.                               &merge_buf[merge_lines[j + 1]]) > 0)
  300.             j++;
  301.          if (compare_strings(&merge_buf[merge_lines[i]],
  302.                               &merge_buf[merge_lines[j]]) <= 0)
  303.             break;
  304.          temp = merge_lines[j];
  305.          merge_lines[j] = merge_lines[i];
  306.          merge_lines[i] = temp;
  307.          i = j;
  308.          j = i + i;
  309.    }
  310. }
  311.  
  312. /* REMOVE_FILES */
  313.  
  314. void remove_files(merge_files, start, stop)
  315. FILE  *merge_files[];
  316. int   start, stop;
  317. {
  318.    register int   i;
  319.    register int   range = stop - start;
  320.    char           file_name[FILE_NAME_LEN];
  321.  
  322.    if (range > MERGE_ORDER) {
  323.       fprintf(stderr, "internal error.");
  324.       exit(1);
  325.    }
  326.    for (i = 0; (i < range); i++) {
  327.       make_file_name(start + i, file_name);
  328.       if (fclose(merge_files[i]) != NULL) {
  329.          fprintf(stderr, "Unable to close merge file.");
  330.          exit(1);
  331.       }
  332.       unlink(file_name);
  333.    }
  334. }
  335.  
  336.  
  337. /*   SORT_BUFFER */
  338.  
  339. void sort_buffer(buffer, lineptr, last_in_buf)
  340. char  buffer[];
  341. int   last_in_buf;
  342. int   lineptr[];
  343. {
  344.    int            gap, i, temp;
  345.    register int   j, jg;
  346.  
  347.    for (gap = last_in_buf / 2; (gap > 0); gap /= 2)
  348.       for (i = gap; (i < last_in_buf); i++)
  349.          for (j = i - gap; (j >= 0); j -= gap) {
  350.             jg = j + gap;
  351.             if (compare_strings(&buffer[lineptr[j]],
  352.                                &buffer[lineptr[jg]]) <= 0)
  353.                break;
  354.             temp = lineptr[jg];
  355.             lineptr[jg] = lineptr[j];
  356.             lineptr[j] = temp;
  357.          }
  358. }
  359.  
  360. /*  WRITE_LINES */
  361.  
  362. void write_lines(outfile, buffer)
  363. FILE  *outfile;
  364. char  buffer[];
  365. {
  366.    int   i;
  367.  
  368.    for (i = 0; (i < next_line); i++) {
  369.       fputs(&buffer[lines[i]], outfile);
  370.       putc('\n', outfile);
  371.    }
  372. }
  373.