Master

src/main.c

+#include "test.h"
+
+int main() {
+    test1_standart_memory_allocate();
+    test2_memory_free_one_block();
+    test3_memory_free_two_blocks();
+    test4_new_region_from_old();
+    test5_new_region_from_new();
+    fprintf(stdout, " All tests passed\n");
+    return 0;
+}
+
+

src/mem.c

 #define _DEFAULT_SOURCE
 
+#define ZERO_SIZE 0
+
+
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 
 /*  аллоцировать регион памяти и инициализировать его блоком */
 static struct region alloc_region  ( void const * addr, size_t query ) {
-  /*  ??? */
+    size_t regionActualSize = region_actual_size(size_from_capacity((block_capacity) { query }).bytes);
+    void *newAddrReg = map_pages(addr, regionActualSize, MAP_FIXED_NOREPLACE);
+    bool flag = true;
+    if (newAddrReg == MAP_FAILED){
+        newAddrReg = map_pages(addr, regionActualSize, ZERO_SIZE);
+        if (newAddrReg == MAP_FAILED){
+            return REGION_INVALID;
+        }
+        if (newAddrReg != addr){
+            flag = false;
+        }
+    }
+
+    struct region region = {.addr = newAddrReg, .size = regionActualSize, .extends = flag};
+    block_init(newAddrReg, (block_size) {regionActualSize}, NULL );
+
+    return region;
+
+
 }
 
 static void* block_after( struct block_header const* block )         ;
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
+  if (!block_splittable(block, query)) {
+        return false;
+    }
+    block_size free_block_size = (block_size) {block->capacity.bytes - query};
+    block->capacity = (block_capacity) {query};
+    void *sub_block = block_after(block);
+    block_init(sub_block, free_block_size, block->next);
+    block->next = sub_block;
+    return true;
 }
 
 
 }
 
 static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
+  struct block_header *next = block->next;
+    if (next != NULL && mergeable(block, next)){
+        block->capacity.bytes += size_from_capacity(next->capacity).bytes;
+        block->next = next->next;
+        return true;
+    }
+    return false;
 }
 
 
 
 
 static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+      struct block_header* block_behind = NULL;
+
+    while (block) {
+        while (try_merge_with_next(block));
+        if ((block_is_big_enough(sz, block)) && block->is_free) {
+            return (struct block_search_result) {
+                    .type = BSR_FOUND_GOOD_BLOCK,
+                    .block = block
+            };
+        }
+
+        block_behind = block;
+        block = block->next;
+    }
+
+    return (struct block_search_result) {
+            .type = BSR_REACHED_END_NOT_FOUND,
+            .block = block_behind
+    };
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
 static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
-  
+  struct block_search_result blockSearchResult = find_good_or_last(block, query);
+    if (!blockSearchResult.type) {
+        split_if_too_big(blockSearchResult.block, query);
+        blockSearchResult.block->is_free = false;
+    }
+    return blockSearchResult;
 }
 
 
 
 static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+      if (query < BLOCK_MIN_CAPACITY) {
+        query = BLOCK_MIN_CAPACITY;
+    }
+    struct region grew_region = alloc_region(block_after(last), query);
+    last->next = grew_region.addr;
+    if (try_merge_with_next(last)) {
+        return last;
+    }
+    return last->next;
 }
 
 /*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
 static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
 
-  /*  ??? */
+      if (query < BLOCK_MIN_CAPACITY) {
+        query = BLOCK_MIN_CAPACITY;
+    }
+    struct block_search_result blockSearchResult = try_memalloc_existing(query, heap_start);
+    if (blockSearchResult.type == BSR_REACHED_END_NOT_FOUND) {
+        struct block_header* new = grow_heap(blockSearchResult.block, query);
+        if (!new) return NULL;
+        blockSearchResult = try_memalloc_existing(query, new);
+    }
+    if (blockSearchResult.type != BSR_FOUND_GOOD_BLOCK) return NULL;
+    return blockSearchResult.block;
 
 }
 
   if (!mem) return ;
   struct block_header* header = block_get_header( mem );
   header->is_free = true;
-  /*  ??? */
+  while (try_merge_with_next(header));
 }

src/test.c

+#include "test.h"
+
+#define MEMORY_SIZE 100
+#define SECOND_SIZE 2000
+
+static struct block_header *block_get_header(void *contents) {
+    return (struct block_header *) (((uint8_t *) contents) - offsetof(struct block_header, contents));
+}
+
+
+//Обычное успешное выделение памяти.
+void test1_standart_memory_allocate(){
+    fprintf(stdout, "Starting test №1! \n");
+    void* data = _malloc(MEMORY_SIZE);
+    if (data == NULL){
+        err("Test №1 failed (memory not allocated)");
+    }
+    _free(data);
+    fprintf(stdout, " №1 passed\n");
+    
+}
+//Освобождение одного блока из нескольких выделенных.
+void test2_memory_free_one_block(){
+    fprintf(stdout, "Starting test №2! \n");
+    void *heap = heap_init(HEAP_SIZE);
+    if (heap == NULL) {
+        err("Test №2 failed (heap initialization failed!)\n");
+
+    }
+    void *data1 = _malloc(MEMORY_SIZE);
+    void *data2 = _malloc(MEMORY_SIZE);
+
+    if (data1 == NULL || data2 == NULL){
+        err("Test №2 failed (memory not allocated!)");
+    }
+
+    struct block_header *data1_block = block_get_header(data1);
+    struct block_header *data2_block = block_get_header(data2);
+
+    _free(data1);
+    if (!data1_block->is_free || data2_block->is_free){
+        err("Test №2 failed (wrong order!)");
+    }
+
+    _free(data2);
+    fprintf(stdout,"Test №2 passed\n");
+}
+//Освобождение двух блоков из нескольких выделенных.
+void test3_memory_free_two_blocks(){
+    fprintf(stdout, "Starting test №3! \n");
+    void *heap = heap_init(HEAP_SIZE);
+    if (heap == NULL) {
+        err("Test №3 failed (heap initialization failed!)\n");
+    }
+    void* data1 = _malloc(MEMORY_SIZE);
+    void* data2 = _malloc(MEMORY_SIZE);
+    void* data3 = _malloc(MEMORY_SIZE);
+    if (data1 == NULL || data2 == NULL || data3 == NULL){
+        err("Test №3 failed (memory not allocated!)");
+    }
+    _free(data2);
+    _free(data1);
+    debug_heap(stdout, heap);
+    struct block_header* data1_block = block_get_header(data1);
+    struct block_header* data3_block = block_get_header(data3);
+    if (data1_block -> is_free || !data3_block -> is_free){
+        err("Test №3 failed (wrong order!)");
+    }
+    if (data1_block->capacity.bytes != SECOND_SIZE + offsetof(struct block_header, contents))
+        err("Test №3 failed (incorrect size!)");
+    _free(data3);
+    fprintf(stdout,"Test №3 passed\n");
+
+}
+//Память закончилась, новый регион памяти расширяет старый.
+void test4_new_region_from_old(){
+    fprintf(stdout, "Starting test №4! \n");
+    void* heap = heap_init(HEAP_SIZE);
+    if (heap == NULL){
+        err("Test №4 failed (heap initialization failed!)");
+    }
+    void* data1 = _malloc(MEMORY_SIZE);
+    void* data2 = _malloc(MEMORY_SIZE);
+    void* data3 = _malloc(MEMORY_SIZE);
+    if (data1 == NULL || data2 == NULL || data3 == NULL){
+        err("Test №4 failed (memory not allocated!)");
+    }
+    struct block_header* data1_block = block_get_header(data1);
+    struct block_header* data2_block = block_get_header(data2);
+    struct block_header* data3_block = block_get_header(data3);
+    if (data1_block->next != data2_block || data2_block->next != data3_block){
+        err("Test №4 failed (incorrect blocks ordering!)");
+    }
+    void* data4 = _malloc(MEMORY_SIZE);
+    if (data4 == NULL){
+        err("Test №4 failed (memory not extended!)");
+    }
+    struct block_header* data4_block = block_get_header(data4);
+    if (data3_block->next != data4_block){
+        err("Test №4 failed (incorrect blocks ordering!)");
+    }
+    fprintf(stdout,"Test №4 passed\n");     
+}
+//Память закончилась, старый регион памяти не расширить из-за другого выделенного диапазона адресов,
+// новый регион выделяется в другом месте.
+
+void test5_new_region_from_new(){
+
+  fprintf(stdout, "Starting test №5! \n");
+
+    void* heap = heap_init(HEAP_SIZE);
+    if (heap == NULL) {
+        err("Test №5 failed (heap initialization failed!)\n");
+    }
+
+    void* data1 = _malloc(MEMORY_SIZE*5);
+    void* data2 = _malloc(MEMORY_SIZE*5);
+    if (data1 == NULL || data2 == NULL) {
+        err("Test №5 failed (memory not allocated!)");
+    }
+
+    void* data3 = _malloc(MEMORY_SIZE*5);
+    if (data3 == NULL) {
+        err("Test №5 failed (memory not allocated!)");
+    }
+    if (data3 == heap) {
+        err("Test №5 failed (new region not allocated in different place!)");
+    }
+
+}

src/test.h

+#define HEAP_SIZE 4096
+
+#include "mem.h"
+#include "mem_internals.h"
+#include "util.h"
+#include <stdlib.h>
+
+void test1_standart_memory_allocate();
+
+void test2_memory_free_one_block();
+
+void test3_memory_free_two_blocks();
+
+void test4_new_region_from_old();
+
+void test5_new_region_from_new();