daily pastebin goal
38%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdint.h>
  5.  
  6. #define dim_gestiune 12
  7. #define la_bloc_anterior 4
  8. #define la_dim_bloc 8
  9.  
  10. uint32_t arena_size, arena_start, block_at_0;
  11. unsigned char* arena;
  12.  
  13. uint32_t min(uint32_t a, uint32_t b)
  14. {
  15.     if(a<b)return a;
  16.     return b;
  17. }
  18. //Returneaza urmatorul numar >= ca x si divizibil cu align
  19. uint32_t next_aligned_index(uint32_t x, uint32_t align)
  20. {
  21.     if(!x) return 0;
  22.     return ((x - 1) / align + 1) * align;
  23. }
  24.  
  25. //Prints an int on the allocator
  26. void uint_to_hex(uint32_t index, uint32_t num)
  27. {
  28.     arena [index + 3] = (num >> 24) & 0xFF;
  29.     arena [index + 2] = (num >> 16) & 0xFF;
  30.     arena [index + 1] = (num >> 8) & 0XFF;
  31.     arena [index] = num & 0xFF;
  32. }
  33.  
  34. //Reads an int from the allocator
  35. uint32_t hex_to_int(uint32_t index)
  36. {
  37.     uint32_t res = 0;
  38.     res = arena[index + 3];
  39.     res = (res << 8) + arena[index + 2];
  40.     res = (res << 8) + arena[index + 1];
  41.     res = (res << 8) + arena[index];
  42.     return res;
  43. }
  44.  
  45. void INITIALIZE(uint32_t size)
  46. {
  47.     //Creeaza o arena noua de dimensiune size,
  48.     //initializeaza dimensiunea si locul primului bloc
  49.     arena_size = size;
  50.     arena_start = 0;
  51.     block_at_0 = 0;
  52.     arena = calloc(size, sizeof(unsigned char));
  53. }
  54.  
  55. void FINALIZE()
  56. {
  57.     //Elibereaza arena si modifica dimensiunea la 0
  58.     if(!arena_size) return;
  59.     free (arena);
  60.     arena_size = 0;
  61. }
  62.  
  63. void DUMP()
  64. {
  65.     uint32_t parse_index;
  66.     for(parse_index = 0; parse_index < arena_size; parse_index++)
  67.     {
  68.         //Printeaza locul din memorie la fiecare bloc de 16 octeti
  69.         if(!(parse_index & 0xF))
  70.             printf("%08X\t",parse_index);
  71.         //Printeaza un spatiu inainte de al 9-lea octet
  72.         else if((parse_index & 0xF) == 8)
  73.             printf(" ");
  74.         printf("%02X ", arena[parse_index]);
  75.         //Trece pe o linie noua dupa al 16-lea octet
  76.         if((parse_index & 0xF) == 0xF)
  77.             printf("\n");
  78.     }
  79.     if(arena_size & 0xF)
  80.             printf("\n");
  81. }
  82.  
  83. //Aloca un bloc de memorie la free_index, de marime size, cu blocul anterior la prev_index
  84. //si blocul urmator la next_index
  85. void alloc_at(uint32_t free_index, uint32_t size, uint32_t prev_index, uint32_t next_index)
  86. {
  87.     //Updateaza blocurile vecine cu noua forma
  88.     if(prev_index || block_at_0)
  89.         uint_to_hex(prev_index, free_index);
  90.     if(next_index)
  91.         uint_to_hex(next_index + la_bloc_anterior, free_index);
  92.     //Initializeaza blocul nou cu datele necesare
  93.     uint_to_hex(free_index, next_index);
  94.     uint_to_hex(free_index + la_bloc_anterior, prev_index);
  95.     uint_to_hex(free_index + la_dim_bloc, size);
  96.     //Marcheaza atunci cand contruieste un bloc incepand la 0
  97.     if(!free_index) block_at_0 = 1;
  98. }
  99.  
  100. uint32_t ALLOCALIGNED(uint32_t size, uint32_t align)
  101. {
  102.     uint32_t loc_align;
  103.     //Calculeaza primul loc aliniat
  104.     loc_align = next_aligned_index(dim_gestiune, align);
  105.     //Verifica daca nu exista niciun bloc de memorie alocat
  106.     if(hex_to_int(arena_start + la_dim_bloc)==0)
  107.     {
  108.         //Daca cererea de memorie este mai mica decat arena se poate aloca
  109.         if(size + loc_align <= arena_size)
  110.         {
  111.             arena_start = loc_align - dim_gestiune;
  112.             alloc_at(arena_start, size, 0, 0);
  113.             return loc_align;
  114.         }
  115.         else return 0;
  116.     }
  117.     //Incearca sa aloce memorie la indexul 0
  118.     if(size + loc_align <= arena_start)
  119.     {
  120.         alloc_at(loc_align - dim_gestiune, size, 0, arena_start);
  121.         arena_start = loc_align - dim_gestiune;
  122.         return loc_align;
  123.     }
  124.     //Cauta primul loc unde poate insera blocul de memorie
  125.     uint32_t parse_index, next_index, curr_bloc_len;
  126.     next_index = arena_start;
  127.     do
  128.     {
  129.         parse_index = next_index;
  130.         next_index = hex_to_int(parse_index);
  131.         curr_bloc_len = hex_to_int(parse_index + la_dim_bloc);
  132.         loc_align = next_aligned_index(parse_index + dim_gestiune * 2 + curr_bloc_len, align);
  133.     }while(next_index && loc_align + size > next_index);
  134.  
  135.     //Trateaza cazul in care se poate aloca memorie intre 2 blocuri existente
  136.     if(next_index)
  137.     {
  138.         alloc_at(loc_align - dim_gestiune, size, parse_index, next_index);
  139.         return loc_align;
  140.     }
  141.     //Trateaza cazul in care aloca memorie la final
  142.     else
  143.     {
  144.         //Daca nu are destul spatiu nu aloca
  145.         if(arena_size< loc_align + size)
  146.             return 0;
  147.         alloc_at(loc_align - dim_gestiune, size, parse_index, 0);
  148.         return loc_align;
  149.     }
  150. }
  151.  
  152. uint32_t ALLOC(uint32_t size)
  153. {
  154.     return ALLOCALIGNED(size, 1);
  155. }
  156.  
  157. void FREE(uint32_t free_index)
  158. {
  159.     //Seteaza free_index la inceputul blocului si citeste urmatorul si anteriorul bloc
  160.     free_index -= dim_gestiune;
  161.     if(free_index == 0) block_at_0 = 0;
  162.     uint32_t next_index = hex_to_int(free_index);
  163.     uint32_t prev_index = hex_to_int(free_index + la_bloc_anterior);
  164.     //Daca free_index e primul bloc trece urmatorul bloc ca friind primul
  165.     if(free_index == arena_start)
  166.         arena_start = next_index;
  167.     //Updateaza blocurile vecine
  168.     if(prev_index >= arena_start)
  169.         uint_to_hex(prev_index,next_index);
  170.     if(next_index)
  171.         uint_to_hex(next_index + la_bloc_anterior, prev_index);
  172.     //Sterge memoria
  173.     memset(arena + free_index, 0, (dim_gestiune + hex_to_int(free_index + la_dim_bloc)) * sizeof(unsigned char));
  174. }
  175.  
  176. void FILL(uint32_t index, uint32_t size, unsigned char value)
  177. {
  178.     index -= dim_gestiune;
  179.     uint32_t block_fill, next_index;
  180.     while(size)
  181.     {
  182.         //Umple blocul curent cu numarul maxim de octeti disponibili
  183.         block_fill = min(size, hex_to_int(index + la_dim_bloc));
  184.         next_index = hex_to_int(index);
  185.         for(uint32_t i = 0; i < block_fill; i++)
  186.             arena[index + dim_gestiune + i] = value;
  187.         //Scade din numarul total de octeti cati a umplut si trece la urmatorul bloc
  188.         size -= block_fill;
  189.         index = next_index;
  190.         //Daca nu mai are loc sa completeze se opreste
  191.         if(!index) return;
  192.     }
  193. }
  194.  
  195. uint32_t REALLOC(uint32_t index, uint32_t size)
  196. {
  197.     //Calculeaza punctul de inceput al blocului si dimensiunea memoriei din el
  198.     index -= dim_gestiune;
  199.     uint32_t dim_mem = min(size, hex_to_int(index + la_dim_bloc));
  200.     //Salveaza intr-un sir de caractere temporal valorile din bloc
  201.     unsigned char* tmp;
  202.     tmp = calloc(dim_mem, sizeof(unsigned char));
  203.     memcpy(tmp, arena + index + dim_gestiune, dim_mem * sizeof(unsigned char));
  204.     //Goleste zona de inlocuit si cauta un loc nou
  205.     FREE(index + dim_gestiune);
  206.     uint32_t free_pos = ALLOC(size);
  207.     //Daca gaseste un loc nou copiaza ce se afla in memoria blocului sters
  208.     if(!free_pos)
  209.     {
  210.         free(tmp);
  211.         return 0;
  212.     }
  213.     memcpy(arena + free_pos, tmp, dim_mem * sizeof(unsigned char));
  214.     free(tmp);
  215.     return free_pos;
  216. }
  217.  
  218. void parse_command(char* cmd)
  219. {
  220.     const char* delims = " \n";
  221.  
  222.     char* cmd_name = strtok(cmd, delims);
  223.     if (!cmd_name) {
  224.         goto invalid_command;
  225.     }
  226.  
  227.     if (strcmp(cmd_name, "INITIALIZE") == 0) {
  228.         char* size_str = strtok(NULL, delims);
  229.         if (!size_str) {
  230.             goto invalid_command;
  231.         }
  232.         uint32_t size = atoi(size_str);
  233.         INITIALIZE (size);
  234.  
  235.     } else if (strcmp(cmd_name, "FINALIZE") == 0) {
  236.         FINALIZE ();
  237.  
  238.     } else if (strcmp(cmd_name, "DUMP") == 0) {
  239.         DUMP ();
  240.  
  241.     } else if (strcmp(cmd_name, "ALLOC") == 0) {
  242.         char* size_str = strtok(NULL, delims);
  243.         if (!size_str) {
  244.             goto invalid_command;
  245.         }
  246.         uint32_t size = atoi(size_str);
  247.         printf("%d\n",ALLOC (size));
  248.  
  249.     } else if (strcmp(cmd_name, "FREE") == 0) {
  250.         char* index_str = strtok(NULL, delims);
  251.         if (!index_str) {
  252.             goto invalid_command;
  253.         }
  254.         uint32_t index = atoi(index_str);
  255.         FREE (index);
  256.  
  257.     } else if (strcmp(cmd_name, "FILL") == 0) {
  258.         char* index_str = strtok(NULL, delims);
  259.         if (!index_str) {
  260.             goto invalid_command;
  261.         }
  262.         uint32_t index = atoi(index_str);
  263.         char* size_str = strtok(NULL, delims);
  264.         if (!size_str) {
  265.             goto invalid_command;
  266.         }
  267.         uint32_t size = atoi(size_str);
  268.         char* value_str = strtok(NULL, delims);
  269.         if (!value_str) {
  270.             goto invalid_command;
  271.         }
  272.         uint32_t value = atoi(value_str);
  273.         FILL(index, size, value);
  274.  
  275.     } else if (strcmp(cmd_name, "ALLOCALIGNED") == 0) {
  276.         char* size_str = strtok(NULL, delims);
  277.         if (!size_str) {
  278.             goto invalid_command;
  279.         }
  280.         uint32_t size = atoi(size_str);
  281.         char* align_str = strtok(NULL, delims);
  282.         if (!align_str) {
  283.             goto invalid_command;
  284.         }
  285.         uint32_t align = atoi(align_str);
  286.         printf("%d\n",ALLOCALIGNED(size, align));
  287.  
  288.     } else if (strcmp(cmd_name, "REALLOC") == 0) {
  289.         char* index_str = strtok(NULL, delims);
  290.         if (!index_str) {
  291.             goto invalid_command;
  292.         }
  293.         uint32_t index = atoi(index_str);
  294.         char* size_str = strtok(NULL, delims);
  295.         if (!size_str) {
  296.             goto invalid_command;
  297.         }
  298.         uint32_t size = atoi(size_str);
  299.         printf("%d\n",REALLOC(index, size));
  300.  
  301.     } else {
  302.         goto invalid_command;
  303.     }
  304.  
  305.     return;
  306.  
  307. invalid_command:
  308.     printf("Invalid command: %s\n", cmd);
  309.     exit(1);
  310. }
  311.  
  312. int main(void)
  313. {
  314.     ssize_t read;
  315.     char* line = NULL;
  316.     size_t len;
  317.  
  318.     /* parse input line by line */
  319.     while ((read = getline(&line, &len, stdin)) != -1) {
  320.         /* print every command to stdout */
  321.         printf("%s", line);
  322.  
  323.         parse_command(line);
  324.     }
  325.  
  326.     free(line);
  327.  
  328.     return 0;
  329. }
RAW Paste Data
Top