Guest User

Untitled

a guest
Dec 14th, 2019
84
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