SHARE
TWEET

Untitled

a guest Dec 14th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Реализовать набор из следующих функций и показать их работоспособность:
  2. - void* myMalloc(size_t size) – аналог функции malloc;
  3. - void myFree(void* ptr) – аналог функции free;
  4. - void* myRealloc(void* ptr, size_t size) – аналог функции realloc;
  5. - void init() – вспомогательная функция, инициализирующая необходимые структуры данных;
  6. В функции init() происходит выделение большой области динамической памяти штатными средствами.
  7. Выделение памяти в реализуемых функциях должно происходить в этой области.
  8. За пределами функции init() нельзя использовать функции malloc, realloc и free.*/
  9.  
  10. /* менеджер памяти создать
  11. Который пользователю по запросам отдаёт память, потом освобождает
  12. Если надо увеличивает/уменьшает длину */
  13.  
  14. /* идея: есть массив байтов из которого мы будем выделять по нужде байты. # сделано
  15. Есть массив "контроля" в 4 раза меньше # сделано
  16. В нём каждая ячейка отвечает 4 ячейкам исходного массива # сделано
  17. И говорит, сколько блоков справа от этого заняты (включая текущий) # сделано
  18. В функции free будет происходит обнуление блоков и потом проверка не надо ли сдвинуть налево что-нибудь # сделано
  19. В функции realloc будет происходить сдвиг налево если там есть место
  20. И сдвиг всего, что не даёт влезать области, направо
  21. В функции malloc происходит выделение самой левой памяти
  22. При этом во всех случаях считается, что справа уже всё так как и должно быть */
  23.  
  24. /*проблемы
  25. проверить на +/- 1
  26. проверить логику
  27. с указателями разобраться. Правильно ли я ссылаюсь по массивам
  28. ускорить поиск, за счёт того, что у меня хранится в buferstat, вместо +1 делать +buferstat[ptr]
  29. Где вопросы, там я не уверен
  30. Ещё что-нибудь
  31. */
  32.  
  33. //#include "manager.h"
  34. #define _CRT_SECURE_NO_WARNINGS
  35. #include <stdio.h>
  36. #include <stdlib.h>
  37. #define ull unsigned long long
  38. #define uc unsigned char
  39. #define max(x, y) x > y ? x : y
  40. #define min(x, y) x < y ? x : y
  41.  
  42. char* memory_block;
  43. char* buferstat;
  44. ull size_using_memory, memory_size = 16;
  45. ull first_adress, last_adress;
  46. ull control_block_size;
  47.  
  48. ull find_size(ull index_block)
  49. {
  50.     char prev_size = buferstat[index_block];
  51.     ull curr_block = index_block + 1;
  52.     char size = buferstat[curr_block];
  53.     ull i = 0;
  54.     while (size == prev_size && size == 255)
  55.     {
  56.         prev_size = buferstat[curr_block];
  57.         curr_block++;
  58.         size = buferstat[curr_block];
  59.         i++;
  60.     }
  61.     return i + prev_size;
  62. }
  63.  
  64. void my_free(void* ptr)
  65. {
  66.     ull first_byte = (ull)((ull)ptr - first_adress);
  67.     ull curr_block = first_byte / 4;
  68.     ull size_deleted_block = find_size(curr_block);
  69.     ull i = 0;
  70.     for (i; i < size_deleted_block; i++)
  71.         buferstat[curr_block + i] = 0;
  72.     curr_block += i;
  73.     return;
  74. }
  75.  
  76. void* my_malloc(size_t size)
  77. {
  78.     ull right_size = ((ull)size + 3) / 4 * 4;
  79.     ull remaining_blocks = right_size / 4;
  80.     ull first_free_block = 0;
  81.     while (first_free_block != control_block_size)
  82.     {
  83.         if (buferstat[first_free_block] == 0)
  84.         {
  85.             ull available_size = 4;
  86.             ull curr_block = first_free_block + 1;
  87.             while (buferstat[curr_block] == 0 && available_size < right_size && curr_block != control_block_size)
  88.             {
  89.                 available_size += 4;
  90.                 curr_block++;
  91.             }
  92.             if (curr_block == control_block_size && available_size < right_size)
  93.                 return NULL;
  94.             if (available_size < right_size)
  95.             {
  96.                 continue;
  97.                 first_free_block = curr_block;
  98.             }
  99.             curr_block = 0;
  100.             while (remaining_blocks != 0)
  101.             {
  102.                 buferstat[first_free_block + curr_block] = min(remaining_blocks, 255);
  103.                 remaining_blocks--;
  104.                 curr_block++;
  105.             }
  106.             return (void*)&memory_block[first_free_block * 4];
  107.         }
  108.         first_free_block++;
  109.     }
  110. }
  111.  
  112. void* my_realloc(void* ptr, size_t size)
  113. {
  114.     if (size == 0)
  115.     {
  116.         my_free(ptr);
  117.         return;
  118.     }
  119.     if (ptr == NULL)
  120.         return my_malloc(size);
  121.     size_t remaining_size_in_blocks = size / 4;
  122.     ull first_byte = (ull)((ull)ptr - first_adress);
  123.     ull relocate_block = first_byte / 4;
  124.     ull first_free_block = relocate_block - 1;
  125.     while (buferstat[first_free_block] == 0 && first_free_block > -1)
  126.         first_free_block--;
  127.     first_free_block++;
  128.     ull i = 0;
  129.     ull size_relocate_block = find_size(relocate_block);
  130.     ull curr_block = 0;
  131.     while (buferstat[relocate_block + size_relocate_block + curr_block] == 0 && relocate_block + size_relocate_block + curr_block != control_block_size)
  132.         curr_block++;
  133.     ull available_size = size_relocate_block * 4 + (relocate_block - first_free_block) * 4 + curr_block * 4;
  134.     int* pointer;
  135.     if (size <= available_size)
  136.     {
  137.         pointer = &memory_block[first_free_block * 4];
  138.         while (remaining_size_in_blocks != 0)
  139.         {
  140.             buferstat[first_free_block] = min(remaining_size_in_blocks, 255);
  141.             remaining_size_in_blocks--;
  142.             for (char j = 0; j < 4; j++)
  143.                 memory_block[first_free_block * 4 + j] = memory_block[relocate_block * 4 + j];
  144.             buferstat[relocate_block] = 0;
  145.             relocate_block++;
  146.             first_free_block++;
  147.             i++;
  148.         }
  149.         while (i < relocate_block + size_relocate_block)
  150.         {
  151.             buferstat[i] = 0;
  152.             i++;
  153.         }
  154.     }
  155.     else
  156.     {
  157.         curr_block = relocate_block + size_relocate_block; // +- 1?
  158.         ull last_busy = 0;
  159.         ull available_size_after_last_busy = 0;
  160.         while (buferstat[curr_block] != 0)
  161.             curr_block++;
  162.         curr_block--;
  163.         if (curr_block == relocate_block + size_relocate_block - 1)
  164.             curr_block = 0;
  165.         last_busy = curr_block;
  166.         curr_block++;
  167.         while (curr_block != control_block_size)
  168.         {
  169.             available_size_after_last_busy += 4;
  170.             curr_block++;
  171.         }
  172.         if (available_size_after_last_busy < size)
  173.             return NULL;
  174.         curr_block = 0;
  175.         pointer = &memory_block[(last_busy + 1) * 4];
  176.         while (remaining_size_in_blocks != 0)
  177.         {
  178.             for (char j = 0; j < 4; j++)
  179.                 memory_block[(last_busy + curr_block + 1) * 4 + j] = memory_block[(relocate_block + curr_block) * 4 + j];
  180.             buferstat[last_busy + curr_block] = buferstat[relocate_block + curr_block];
  181.             remaining_size_in_blocks--;
  182.             curr_block++;
  183.         }
  184.         my_free((void*)(&memory_block[relocate_block * 4]));
  185.     }
  186.     return (void*)pointer;
  187. }
  188.  
  189. void init()
  190. {
  191.     memory_size = ((memory_size + 3) / 4) * 4;
  192.     memory_block = (char*)malloc(sizeof(char) * memory_size);
  193.     first_adress = memory_block;
  194.     control_block_size = memory_size / 4;
  195.     buferstat = (uc*)calloc(control_block_size, sizeof(uc));
  196.     size_using_memory = memory_size;
  197. }
  198.  
  199. int main()
  200. {
  201.     init();
  202.     int amount = 2;
  203.     int* number;
  204.     printf("%d\n", sizeof(int) * amount);
  205.     number = (int*)my_malloc(sizeof(int) * amount);
  206.     if (number == NULL)
  207.     {
  208.         printf("NULL1");
  209.         return 0;
  210.     }
  211.     number[0] = 1;
  212.     number[1] = 2;
  213.     printf("%d %d\n", number[0], number[1]);
  214.     printf("QQ1\n");
  215.     my_free(number);
  216.     amount--;
  217.     int* number2;
  218.     printf("QQ2\n");
  219.     number = my_realloc(NULL, sizeof(int) * amount);
  220.     printf("QQ3\n");
  221.     number2 = (int*)my_malloc(sizeof(int) * amount);
  222.     printf("QQ4\n");
  223.     if (number == NULL)
  224.     {
  225.         printf("NULL2");
  226.         return 0;
  227.     }
  228.     if (number2 == NULL)
  229.     {
  230.         printf("NULL3");
  231.         return 0;
  232.     }
  233.     number[0] = 1;
  234.     number2[0] = 10;
  235.     printf("%d %d\n", number[0], number2[0]);
  236.     printf("%d %d\n", number, number2);
  237.     amount++;
  238.     number = my_realloc(number, sizeof(int) * amount);
  239.     number[1] = 2;
  240.     printf("%d %d %d\n", number[0], number[1], number2[0]);
  241.     return 0;
  242. }
RAW Paste Data
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
 
Top