Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 22nd, 2012  |  syntax: None  |  size: 6.00 KB  |  hits: 10  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2. * Machine Problem #3
  3. * CS 241, Spring 2011
  4. *
  5. * Implements parallel file-based mergesort
  6. *    Uses qsort library for per file sort
  7. */
  8.  
  9. #include <stdio.h>              /* Standard buffered input/output        */
  10. #include <stdlib.h>             /* Standard library functions            */
  11. #include <string.h>             /* String operations                     */
  12. #include <pthread.h>                    /* Thread related functions                              */
  13.  
  14. //passed into threads
  15. typedef struct _input_args{
  16.         char *file;
  17.         FILE *output;
  18. } input_args_t;
  19.  
  20. typedef struct _input_files{
  21.         FILE *file1;
  22.         FILE *file2;
  23.         FILE *t_file;
  24. } input_files_t;
  25.  
  26. //int compare for qsort
  27. int int_compare(const void *a, const void *b){
  28.         return *(int*) a - *(int*) b;
  29. }
  30.  
  31. //counts numbers in file
  32. int num_count(FILE *input){
  33.         int i=0;
  34.         char c;
  35.         rewind(input);
  36.         c = fgetc(input);
  37.         while(c != EOF){
  38.                 if(c == '\n')
  39.                         i++;
  40.                 c = fgetc(input);
  41.         }
  42.         rewind(input);
  43.         return i;
  44. }
  45.  
  46. //sorts files and writes new "input.sorted" files as output
  47. void *file_sort(void* args){
  48.         int i=0, count=0;
  49.         char input_read[12];
  50.         char i_name[100], o_name[100];
  51.  
  52.         //assign file names to i_name and o_name
  53.         strcpy(i_name, ((input_args_t*)args)->file);
  54.         *o_name = '\0';
  55.         strcat(o_name,((input_args_t*)args)->file);
  56.         strcat(o_name,".sorted");
  57.  
  58.         //create file descriptors
  59.         FILE *input = fopen(i_name,"r");
  60.         FILE *output = ((input_args_t*)args)->output;
  61.  
  62.         //count the numbers in the file and create an array of that size
  63.         count = num_count(input);
  64.         int input_num[count];
  65.  
  66.         //get strings and read into the integer array
  67.         while(fgets(input_read,11,input) != NULL){
  68.                 input_num[i] = atoi(input_read);
  69.                 i++;
  70.         }
  71.  
  72.         //sort and print array into ".sorted" file
  73.         qsort(input_num,count,sizeof(int),int_compare);
  74.         for(i=0;i<count;i++)
  75.                 fprintf(output, "%d\n", input_num[i]);
  76.  
  77.         printf("This worker thread writes %d lines to \"%s\".\n", count, o_name);
  78.        
  79.         fclose(input);
  80.         return NULL;
  81. }
  82.  
  83. //merge two files into a temp file
  84. void *file_merge(void *files){
  85.         int i=0,j=0,k=0,x=0,count1 = 0,count2 = 0,count3 = 0;
  86.         char input_read[12];
  87.  
  88.         //create file descriptors
  89.         FILE *input1 = ((input_files_t*)files)->file1;
  90.         FILE *input2 = ((input_files_t*)files)->file2;
  91.         FILE *output = ((input_files_t*)files)->t_file;
  92.        
  93.         //count the numbers in the file and create arrays of corresponding size
  94.         count1 = num_count(input1);
  95.         count2 = num_count(input2);
  96.         count3 = count1 + count2;
  97.         int input_num1[count1];
  98.         int input_num2[count2];
  99.         int output_num[count3];
  100.        
  101.         //get strings and read into the integer array
  102.         while(fgets(input_read,11,input1) != NULL){
  103.                 input_num1[i] = atoi(input_read);
  104.                 i++;
  105.         }
  106.         while(fgets(input_read,11,input2) != NULL){
  107.                 input_num2[j] = atoi(input_read);
  108.                 j++;
  109.         }
  110.  
  111.         //merge input_num1 and input_num2 into output_num
  112.         i=0;
  113.         j=0;
  114.         while(i < count1 && j < count2){
  115.                 if(input_num1[i] == input_num2[j]){
  116.                         j++;
  117.                         count3--;
  118.                 }
  119.                 else if(input_num1[i] < input_num2[j]){
  120.                         output_num[k] = input_num1[i];
  121.                         i++;
  122.                         k++;
  123.                 }
  124.                 else{
  125.                         output_num[k] = input_num2[j];
  126.                         j++;
  127.                         k++;
  128.                 }
  129.         }
  130.  
  131.         if(i < count1){
  132.                 for(x=i; x < count1; x++){
  133.                         output_num[k] = input_num1[x];
  134.                         k++;
  135.                 }
  136.         }
  137.         else{
  138.                 for(x=j; x < count2; x++){
  139.                         output_num[k] = input_num2[x];
  140.                         k++;
  141.                 }
  142.         }
  143.  
  144.         //print output_num to output (t_file)
  145.         for(i=0;i<count3;i++){
  146.                 printf("%d\n", output_num[i]);
  147.                 fprintf(output, "%d\n", output_num[i]);
  148.         }
  149.  
  150.         printf("Merged %d lines and %d lines into %d lines.\n", count1, count2, count3);
  151.        
  152.         return NULL;
  153. }
  154.  
  155. /* MAIN PROCEDURE SECTION */
  156. int main(int argc, char **argv){
  157.         int i=0, num_files = argc - 1;
  158.         char o_name[100];
  159.         pthread_t *thread = malloc(num_files*sizeof(pthread_t));
  160.         input_args_t *args = malloc(num_files*sizeof(input_args_t));
  161.         input_files_t *files1= malloc((num_files/2+1)*sizeof(input_files_t));
  162.         input_files_t *files2= malloc((num_files/2+1)*sizeof(input_files_t));
  163.  
  164.         //create individual sorted output files and call file_sort()
  165.         for(i=0;i < num_files; i++){
  166.                 args[i].file = argv[i+1];
  167.                 *o_name = '\0';
  168.                 strcat(o_name, args[i].file);
  169.                 strcat(o_name,".sorted");
  170.                 args[i].output = fopen(o_name, "w+");
  171.                
  172.                 pthread_create(&thread[i],NULL,file_sort,&args[i]);
  173.         }
  174.  
  175.         for(i=0;i < num_files; i++)
  176.                 pthread_join (thread[i],NULL);
  177.  
  178.         //put output in args structs into files structs
  179.         for(i=0;i < num_files/2;i++){
  180.                 printf("struct switch is run and i is %d\n", i);
  181.                 rewind(args[i*2].output);
  182.                 files1[i].file1 = args[i*2].output;
  183.                 rewind(args[i*2+1].output);
  184.                 files1[i].file2 = args[i*2+1].output;
  185.                 files1[i].t_file = tmpfile();
  186.         }
  187.         if(num_files % 2 == 1){
  188.                 i++;
  189.                 rewind(args[i*2].output);
  190.                 files1[i].t_file = args[i*2].output;
  191.         }
  192.        
  193.         //merge the temp files
  194.         int num_threads = i;
  195.         printf("num_threads: %d\n", num_threads);
  196.         for(i=0;i < num_threads;i++)
  197.                 pthread_create(&thread[i],NULL,file_merge,&files1[i]);
  198.         for(i=0;i < num_files; i++)
  199.                 pthread_join(thread[i],NULL);
  200.  
  201.         //continue merging temp files until 1 temp file is left
  202.         while(num_threads > 1){
  203.                 for(i=0;i < num_threads/2;i++){
  204.                         rewind(files1[i*2].t_file);
  205.                         files2[i].file1 = files1[i*2].t_file;
  206.                         rewind(files1[i*2+1].t_file);
  207.                         files2[i].file2 = files1[i*2+1].t_file;
  208.                         files2[i].t_file = tmpfile();
  209.                 }
  210.                 if(num_threads % 2 == 1){
  211.                         i++;
  212.                         rewind(args[i*2].output);
  213.                         files2[i].t_file = args[i*2].output;
  214.                 }
  215.                
  216.                 num_threads = i;
  217.                 for(i=0;i < num_threads;i++){
  218.                         pthread_create(&thread[i],NULL,file_merge,&files2[i]);
  219.                 }
  220.                 for(i=0;i < num_files; i++)
  221.                         pthread_join(thread[i],NULL);
  222.                 for(i=0;i < num_threads;i++)
  223.                         files1[i].t_file = files2[i].t_file;
  224.         }
  225.        
  226.         //when there is 1 temp file, write it to sorted.txt
  227.         FILE *final_file = fopen("sorted.txt", "w");
  228.         int num=0;
  229.         while(fscanf(files1[0].t_file, "%d", &num) != EOF)
  230.                 fprintf(final_file, "%d\n", num);
  231.        
  232.        
  233.         /*
  234.         //close individually sorted files
  235.         for(i=0;i < num_files; i++){
  236.                 fclose(args[i].output);
  237.         }*/
  238.  
  239.         //free all memory
  240.         free(thread);
  241.         free(args);
  242.         free(files1);
  243.         free(files2);
  244.         pthread_exit(NULL);
  245.        
  246.         return 0;
  247. } /* end main() */
create a new version of this paste RAW Paste Data