API tools faq
paste
Guest User

Untitled

a guest
Jan 21st, 2018
114
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.06 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <sys/types.h>
  6. #include <sys/stat.h>
  7. #include <fcntl.h>
  8. #include <unistd.h>
  9. #include <sys/mman.h>
  10. #include <pthread.h>
  11.  
  12. struct param_for_mergesort {
  13.      
  14.      int * array;
  15.      int length;
  16.      
  17. };
  18.  
  19. /* Funkce vracejici pole cisel a ukladajici do promennych pocet cisel a informace o souboru */
  20. int * open_input(char * file, int * count_of_item, struct stat * file_inf);
  21. /* Funkce zapisujici pole cisel do souboru */
  22. void write_to_file(int * array, char * file, int count_of_item, struct stat file_inf);
  23. /* Paralelní mergesort */
  24. int * parallel_merge_sort(int * array, int count_of_threads, int count_of_items);
  25. /* Funkce tridici pole */
  26. int * merge_sort(void * param);
  27. /* Funkce slevajici 2 pole */
  28. int * merge(int * left, int left_len, int * right, int right_len);
  29.  
  30. int main(int argc, char *argv[])
  31. {
  32.      if (argc < 4) {
  33.    
  34.     fprintf(stderr,"Chybny pocet argumentu\n");
  35.     return 1;
  36.    
  37.      }
  38.      
  39.      int * count = (int *) malloc(sizeof(int));
  40.      struct stat * fileinfo = (struct stat *) malloc(sizeof(struct stat)); /* struktura, ze ktere budu zjistovat velikost souboru */
  41.      
  42.      int * my_array = open_input(argv[1], count, fileinfo);    /* Nactu si pole cisel ze souboru */  
  43.          
  44.      int * sorted_array = parallel_merge_sort(my_array, atoi(argv[3]), *count); /* Setridim si pole cisel */
  45.      
  46.      write_to_file(sorted_array,argv[2], *count, *fileinfo); /* Ulozim pole do souboru */
  47.      
  48.      free(my_array);
  49.      free(sorted_array);
  50.      
  51.      return 0;
  52.      
  53. }
  54.  
  55. int * open_input(char * file, int * count_of_item, struct stat * file_inf)
  56. {
  57.  
  58.      /* Otevru si soubor */
  59.      int file_input = open(file, O_RDONLY);
  60.      
  61.      if (file_input == -1) {
  62.    
  63.     fprintf(stderr, "Chyba pri otevirani souboru%s\n", file);
  64.     exit(EXIT_FAILURE);;
  65.    
  66.      }
  67.      
  68.      /* Ulozim do struktury informace o souboru */
  69.      stat(file, file_inf);
  70.      
  71.      
  72.      /* Namapuji si soubor do pameti */
  73.      char * input_map_adress = (char *) mmap(NULL, file_inf->st_size, PROT_READ, MAP_SHARED, file_input, 0);
  74.      
  75.      if (input_map_adress == MAP_FAILED) {
  76.    
  77.     fprintf(stderr, "Selhalo nacteni input souboru do pameti\n");
  78.     close(file_input);
  79.     exit(EXIT_FAILURE);;
  80.    
  81.      }
  82.      
  83.      /* Vytvorim si pole a ukladam hodnoty ze souboru a pocitam pocet polozek */
  84.      int i,j = 0;
  85.      int * my_array = (int *) malloc(10 * sizeof(int));
  86.      char tmp_str[255];
  87.      *count_of_item = 0;
  88.  
  89.      for (i = 0; i < file_inf->st_size; i++) {
  90.  
  91.     /* Pokud narazim na novy radek, prevedu string na cislo a ulozim */
  92.     if (input_map_adress[i] != '\n') {
  93.          
  94.          tmp_str[j++] = input_map_adress[i];
  95.              
  96.     } else {
  97.          
  98.          my_array[(*count_of_item)++] = atoi(tmp_str);
  99.          memset (tmp_str,'\0',255);
  100.          j = 0;
  101.          
  102.     }
  103.    
  104.     /* Realokuju si pole po 10 prvcich */
  105.     if (*count_of_item % 10 == 0) {
  106.          
  107.          int * tmp = (int *) realloc(my_array, (*count_of_item + 10) * sizeof(int));
  108.      
  109.          if (tmp != NULL) {
  110.          
  111.              my_array = tmp;
  112.              
  113.          
  114.          } else {
  115.      
  116.              free(my_array);
  117.              munmap(input_map_adress, file_inf->st_size);
  118.                    close(file_input);
  119.              exit(EXIT_FAILURE);;  
  120.          
  121.          }
  122.          
  123.     }
  124.    
  125.      }
  126.  
  127.      /* Uvolnim mapovanou pamet a zavru file deskriptor */    
  128.      munmap(input_map_adress, file_inf->st_size);
  129.      close(file_input);
  130.  
  131.      
  132.      return my_array;
  133.      
  134. }
  135.  
  136. void write_to_file(int* array, char* file, int count_of_item, struct stat file_inf)
  137. {
  138.      /* Otevru si soubor */
  139.      int file_output = open(file, O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600);
  140.      
  141.      if (file_output == -1) {
  142.    
  143.     fprintf(stderr, "Chyba pri otevirani souboru %s\n", file);
  144.     exit(EXIT_FAILURE);;
  145.    
  146.      }
  147.        
  148.      /* Nastavim velikost souboru na velikost souboru, ze ktereho nacitam */  
  149.      if (lseek(file_output, file_inf.st_size-1, SEEK_SET) == -1) {
  150.  
  151.     close(file_output);
  152.     fprintf(stderr, "Chyba pri zvetsovani souboru na velikost ukladaneho pole\n");
  153.     exit(EXIT_FAILURE);
  154.    
  155.      }
  156.  
  157.      /* Zapisu posledni znak do souboru */
  158.      if (write(file_output, "", 1) != 1) {
  159.  
  160.     close(file_output);
  161.     fprintf(stderr, "Chyba pri zapisovani posledniho znaku do souboru\n");
  162.     exit(EXIT_FAILURE);
  163.      }
  164.      
  165.      /* Namapuju si soubor do pameti */
  166.      char * output_map_adress = (char *) mmap(NULL, file_inf.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, file_output, 0);
  167.      
  168.      if (output_map_adress == MAP_FAILED) {
  169.    
  170.     fprintf(stderr, "Selhalo nacteni output souboru do pameti\n");
  171.     close(file_output);
  172.     exit(EXIT_FAILURE);
  173.    
  174.      }
  175.      
  176.      /* Postupne nacitam cisla z pole do retezcu a kopiruji do mapovane pameti */
  177.      int i;
  178.      char tmp_str[255];
  179.      char * tmp_output_map_adress = output_map_adress;
  180.      
  181.      for (i = 0; i < count_of_item; i++) {
  182.    
  183.     int count = sprintf(tmp_str,"%d\n",array[i]);
  184.     strcpy( output_map_adress , tmp_str );
  185.     output_map_adress += count;
  186.    
  187.      }
  188.      
  189.      /* Uvolnim mapovanou pamet a zavru file deskriptor */
  190.      munmap(tmp_output_map_adress, file_inf.st_size);
  191.      close(file_output);
  192.      
  193. }
  194.  
  195.  
  196. int * parallel_merge_sort(int * array, int count_of_threads, int count_of_items)
  197. {
  198.      
  199.      if (count_of_threads > count_of_items) {
  200.    
  201.     printf("Pocet vlaken je vetsi nez pocet cisel, snizuji pocet vlaken na polovinu poctu cisel\n");
  202.     count_of_threads = count_of_items / 2;
  203.    
  204.      }
  205.  
  206.      /* Alokuji si pole parametru pro vlakna */
  207.      struct param_for_mergesort * parameters = (struct param_for_mergesort *) malloc(count_of_threads * sizeof(struct param_for_mergesort));
  208.      pthread_t * threads = (pthread_t *) malloc(count_of_threads * sizeof(pthread_t));
  209.      pthread_attr_t * attrs = (pthread_attr_t *) malloc (count_of_threads * sizeof(pthread_attr_t));
  210.      /* Alokuji si vysledne pole */
  211.      int * result = (int *) malloc(count_of_items * sizeof(int));
  212.      
  213.      int i, j;    
  214.      int delim = (count_of_items) / count_of_threads; /* Po kolika bude pole rozdeleno */
  215.      int rest = count_of_items - (count_of_threads-1)*delim; /* Kolik prvku bude mit posledni pole */
  216.  
  217.      for (i = 0; i < count_of_threads; i++) {
  218.  
  219.     /* Pokud nebudu poustet vlakno s poslednim polem tak budou prvky po velikost delim */
  220.     if (i < count_of_threads - 1) {
  221.    
  222.          parameters[i].array = (int *) malloc(delim * sizeof(int));
  223.          parameters[i].length = delim;
  224.  
  225.          for (j = 0; j < delim; j++) {
  226.        
  227.         parameters[i].array[j] = array[(i*delim)+j];
  228.        
  229.          }
  230.     /* Jinak pocet prvku bude zbytek */    
  231.     } else {
  232.          
  233.          parameters[i].array = (int *) malloc(rest * sizeof(int));
  234.          parameters[i].length = rest;
  235.          
  236.          for (j = 0; j < rest; j++) {
  237.        
  238.         parameters[i].array[j] = array[count_of_items-rest+j];
  239.  
  240.          }
  241.          
  242.     }
  243.  
  244.           /* Spustim trideni ve vlakne */
  245.     pthread_attr_init(&attrs[i]);
  246.     pthread_create(&threads[i], &attrs[i], (void *)merge_sort, (void *)&parameters[i]);
  247.      }
  248.      
  249.      /* Postupne pockam na jednotliva vlakna a spojuji do vysledneho pole */
  250.      for (i = 0; i < count_of_threads; i++) {
  251.    
  252.     void * tmp;
  253.     pthread_join(threads[i], &tmp);              
  254.    
  255.     if (i < count_of_threads - 1) {
  256.  
  257.          result = merge(result, (i * delim),(int *) tmp, delim);
  258.    
  259.     } else {
  260.        
  261.          result = merge(result, ((i-1) * delim) + rest,(int *)  tmp, rest);  
  262.          
  263.     }
  264.    
  265.    
  266.    
  267.      }    
  268.  
  269.      free(threads);
  270.      free(parameters);
  271.      free(attrs);
  272.  
  273.      return result;
  274. }
  275.  
  276. int * merge_sort(void * param)
  277. {          
  278.      /* Puvodni parametr predany funkci */
  279.      struct param_for_mergesort * parameters;
  280.      parameters = (struct param_for_mergesort *) param;
  281.      
  282.  
  283.      if (parameters->length <= 1) {
  284.    
  285.     return parameters->array;
  286.    
  287.      } else {
  288.    
  289.     int i;
  290.     int middle = parameters->length / 2; /* Spocitam si stred pole */
  291.     int * result;
  292.     /* Vytvorim si pole pro spusteni merge sortu pro levou a pravou cast */
  293.     struct param_for_mergesort * parameters_left = (struct param_for_mergesort *) malloc(sizeof(struct param_for_mergesort));
  294.           struct param_for_mergesort * parameters_right = (struct param_for_mergesort *) malloc(sizeof(struct param_for_mergesort));
  295.           parameters_left->array = (int *) malloc(middle * sizeof(int));
  296.           parameters_right->array = (int *) malloc((parameters->length-middle) * sizeof(int));
  297.    
  298.     /* Presunu prvky prvni poloviny do leveho pole */
  299.     for (i = 0; i < middle; i++) {
  300.      
  301.          parameters_left->array[i] = parameters->array[i];
  302.          
  303.          
  304.     }
  305.     /* Presunu prvky prvni poloviny do praveho pole */
  306.     for (i = 0; i < parameters->length-middle; i++) {
  307.          
  308.          parameters_right->array[i] = parameters->array[i+middle];
  309.          
  310.     }
  311.    
  312.     /* Nastavim delky poli */
  313.     parameters_left->length = middle;
  314.     parameters_right->length = parameters->length-middle;
  315.    
  316.     /* Spustim rekurzivne trideni pro levou a pravou polovinu pole */
  317.     parameters_left->array = merge_sort(parameters_left);
  318.     parameters_right->array = merge_sort(parameters_right);
  319.    
  320.     /* Sloucim pole a ulozim do vysledku */
  321.     result = merge(parameters_left->array,middle, parameters_right->array, parameters->length-middle);
  322.    
  323.     /* Uvolnim alokovane leve a prave poloviny */
  324.     free(parameters_left->array);
  325.     free(parameters_right->array);
  326.     free(parameters_left);
  327.     free(parameters_right);
  328.    
  329.     return result;
  330.    
  331.      }
  332.      
  333.      
  334. }
  335.  
  336. int * merge(int * left, int left_len, int * right, int right_len)
  337. {
  338.  
  339.      /* Nastavim si pocatecni indexy */
  340.      int left_index = 0, right_index = 0, index = 0;
  341.      /* Alokuji si vysledne pole */
  342.      int * result = (int *) malloc((left_len+right_len) * sizeof(int));
  343.      
  344.      /* Postupne prochazim leve a prave pole dokud u jednoho nedojdu na konec */
  345.      while (left_index < left_len && right_index < right_len) {
  346.    
  347.     /* Pokud je prvek v levem poli mensi nez v pravem, ulozim prvek z leveho pole
  348.      * do vysledku, jinak z praveho a posunu indexy */
  349.     if (left[left_index] <= right[right_index]) {
  350.          
  351.          result[index] = left[left_index++];  
  352.          
  353.     } else {
  354.          
  355.          result[index] = right[right_index++];
  356.          
  357.     }
  358.    
  359.     index++;
  360.    
  361.      }
  362.      
  363.      /* Zbytek leveho pole zkopiruji */
  364.      while (left_index < left_len) {
  365.    
  366.     result[index] = left[left_index++];
  367.     index++;
  368.    
  369.      }
  370.      
  371.      /* Zbytek praveho pole zkopiruji */
  372.      while (right_index < right_len) {
  373.    
  374.     result[index] = right[right_index++];
  375.     index++;
  376.    
  377.      }
  378.  
  379.      return result;
  380.      
  381.      
  382. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!