Жданок Прокопий P32102

src/CMakeLists.txt

 add_library(memalloc STATIC ${sources})
 target_include_directories(memalloc PUBLIC .)
 
-if(EXISTS main.c)
-    add_executable(memalloc_exe main.c)
-    target_link_libraries(memalloc_exe PRIVATE memalloc)
-    set_target_properties(memalloc_exe PROPERTIES OUTPUT_NAME memalloc)
-endif()
+add_executable(memalloc_exe main.c)
+target_link_libraries(memalloc_exe PRIVATE memalloc)
+set_target_properties(memalloc_exe PROPERTIES OUTPUT_NAME memalloc)

src/main.c

+#include "tests.h"
+
+extern inline void run_tests();
+
+int main() {
+    run_tests();
+    return 0;
+}
\ No newline at end of file

src/mem.c

 #define _DEFAULT_SOURCE
 
-#include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
 
 extern inline block_size size_from_capacity( block_capacity cap );
 extern inline block_capacity capacity_from_size( block_size sz );
+extern inline struct block_header* block_get_header(void* contents);
 
-static bool            block_is_big_enough( size_t query, struct block_header* block ) { return block->capacity.bytes >= query; }
-static size_t          pages_count   ( size_t mem )                      { return mem / getpagesize() + ((mem % getpagesize()) > 0); }
-static size_t          round_pages   ( size_t mem )                      { return getpagesize() * pages_count( mem ) ; }
+static bool block_is_big_enough( size_t query, struct block_header* block ) { return block->capacity.bytes >= query; }
+static size_t pages_count( size_t mem ) { return mem / getpagesize() + ((mem % getpagesize()) > 0); }
+static size_t round_pages( size_t mem ) { return getpagesize() * pages_count( mem ) ; }
 
 static void block_init( void* restrict addr, block_size block_sz, void* restrict next ) {
   *((struct block_header*)addr) = (struct block_header) {
 extern inline bool region_is_invalid( const struct region* r );
 
 
-
 static void* map_pages(void const* addr, size_t length, int additional_flags) {
   return mmap( (void*) addr, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | additional_flags , -1, 0 );
 }
 
 /*  аллоцировать регион памяти и инициализировать его блоком */
-static struct region alloc_region  ( void const * addr, size_t query ) {
-  /*  ??? */
+static struct region alloc_region( void* addr, size_t query ) {
+  size_t length = region_actual_size(size_from_capacity((block_capacity) {query}).bytes);
+
+  void* res = map_pages(addr, length, MAP_FIXED_NOREPLACE);
+  
+  if(res == MAP_FAILED) res = map_pages(addr, length, 0);
+  if(res == MAP_FAILED) return REGION_INVALID;
+  
+  block_init(res, (block_size){length}, NULL);
+  return (struct region) {res, length, res == addr};
 }
 
-static void* block_after( struct block_header const* block )         ;
+static void* block_after( struct block_header const* block );
 
 void* heap_init( size_t initial ) {
   const struct region region = alloc_region( HEAP_START, initial );
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
+  if(!block || !block_splittable(block, query)) return false;
+  
+  struct block_header* next = block->next;
+
+  block_size full_size = size_from_capacity(block->capacity);
+  block_size l_size = size_from_capacity((block_capacity) {query});
+  
+  block_init(block->contents + query, (block_size) {full_size.bytes - l_size.bytes}, next);
+  block_init(block, l_size, block->contents + query);
+  
+  return true;
 }
 
 
 }
 
 static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
+  if(!block || !block->next) return false;
+  if(!mergeable(block, block->next)) return false;
+
+  block_init(block, 
+            (block_size){
+              size_from_capacity(block->capacity).bytes + 
+              size_from_capacity(block->next->capacity).bytes
+            },
+            block->next->next);
+  
+  return true;
 }
 
 
   struct block_header* block;
 };
 
+bool is_block_good(struct block_header* restrict block, size_t query) {
+  return block && block->is_free && block->capacity.bytes >= query;
+}
+
+static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t query){
+  if(!block) return (struct block_search_result) {.type=BSR_CORRUPTED};
+
+  while(try_merge_with_next(block));
 
-static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+  while(block->next && !is_block_good(block, query)){
+    block = block->next;
+    while(try_merge_with_next(block));
+  }
+
+  if(block->next == NULL && !is_block_good(block, query)) return (struct block_search_result){BSR_REACHED_END_NOT_FOUND, block};
+  return (struct block_search_result){.type=BSR_FOUND_GOOD_BLOCK, .block=block};
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
 static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
-  
-}
+  struct block_search_result res = find_good_or_last(block, query);
 
+  if(res.type == BSR_FOUND_GOOD_BLOCK) {
+    split_if_too_big(res.block, query);
+    res.block->is_free = false;
+  }
 
+  return res;
+}
 
 static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+  struct region reg = alloc_region(block_after(last), query);
+  if(reg.addr == block_after(last)) reg.extends = true;
+
+  if(region_is_invalid(&reg)) return NULL;
+
+  if(reg.extends && last->is_free) {
+    block_init(last, (block_size) {size_from_capacity(last->capacity).bytes + reg.size}, NULL);
+    return last;
+  }
+
+  block_init(reg.addr, (block_size) {reg.size}, NULL);
+  last->next = reg.addr;
+  
+  return last->next;
 }
 
 /*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
 static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
+  query = size_max(query, BLOCK_MIN_CAPACITY);
+
+  struct block_search_result res = try_memalloc_existing(query, heap_start);
 
-  /*  ??? */
+  if(res.type == BSR_FOUND_GOOD_BLOCK) return res.block;
+  else if(res.type == BSR_CORRUPTED) return NULL;
 
+  struct block_header* last = grow_heap(res.block, query);
+  if(!last) return NULL;
+  
+  struct block_search_result res_last = try_memalloc_existing(query, last);
+  
+  if(res_last.type != BSR_FOUND_GOOD_BLOCK) return NULL;
+  return res_last.block;
 }
 
 void* _malloc( size_t query ) {
   else return NULL;
 }
 
-static struct block_header* block_get_header(void* contents) {
-  return (struct block_header*) (((uint8_t*)contents)-offsetof(struct block_header, contents));
-}
 
 void _free( void* mem ) {
-  if (!mem) return ;
+  if (!mem) return;
   struct block_header* header = block_get_header( mem );
   header->is_free = true;
-  /*  ??? */
+  while(try_merge_with_next(header));
 }

src/mem_debug.c

 #include <stdarg.h>
 #include <stdio.h>
 
-#include "mem_internals.h"
 #include "mem.h"
+#include "mem_internals.h"
 
 void debug_struct_info( FILE* f,
                                  void const* addr ) {

src/mem_internals.h

 typedef struct { size_t bytes; } block_size;
 
 struct block_header {
-  struct block_header*    next;
+  struct block_header* next;
   block_capacity capacity;
-  bool           is_free;
-  uint8_t        contents[];
+  bool is_free;
+  uint8_t contents[];
 };
 
 inline block_size size_from_capacity( block_capacity cap ) { return (block_size) {cap.bytes + offsetof( struct block_header, contents ) }; }
 inline block_capacity capacity_from_size( block_size sz ) { return (block_capacity) {sz.bytes - offsetof( struct block_header, contents ) }; }
-
+inline struct block_header* block_get_header(void* contents) { return (struct block_header*) (((uint8_t*)contents)-offsetof(struct block_header, contents)); }
 #endif

[Prokopiy Zhdanok]

@andrew done

[Andrey Zhdanov]

Ок