Еще одна реализация функции malloc() в C


Мне очень интересно знать чужое мнение об их реализации. В частности, я хотел бы знать, как вы бы это реализовали. Вот список вопросов, которые я нашел в этой примитивной реализации:

  1. Оно медленно. Вам предстоит пройти весь список, чтобы найти свободный блок памяти.
  2. Злоупотребление sbrk().
  3. Очень высока вероятность внутренней фрагментации.

мэм.ч

#ifndef __MEM__
#define __MEM__
#include<stdio.h>
#include<stdlib.h>

typedef enum { false, true } bool;

typedef struct page
{
  size_t size;
  bool free;
  struct page* next;
  struct page* prev;
} page_t;

extern void* memalloc(size_t size);
extern void  memfree(void* pointer);

#endif

мэм.с

#include "include/mem.h"
#include <assert.h>
#include <sys/types.h>
#include <unistd.h>

#define SBRK_ERROR (void*)(-1)
#define UNDEFINED 0

page_t* global;
page_t* last;

page_t* allocate(size_t size)
{
  page_t* node = sbrk(0);
  void* pointer = sbrk(size + sizeof(page_t));
  if(pointer == SBRK_ERROR)
    return NULL;
  if(last != NULL)
    last-> next = node;
  last = node;
  last-> size = size;
  last-> free = false;
  last-> next = NULL;
  return last;
}

void* search(size_t size)
{
  page_t* node = global;
  while(node != NULL){
    if(node-> size >= size || node-> size == UNDEFINED){
      if(node-> free)
        return node;
    }
    node = node-> next;
  }
  return NULL;
}

void* memalloc(size_t size)
{
  page_t* result = NULL;
  if(size >= 0){
    if(global != NULL){
      result = search(size);
      if(result == NULL)
        result = allocate(size);
    }else {
      global = allocate(size);
      result = global;
    }
  }
  return result != NULL ? (result + 1) : NULL;
}

page_t* to_page(void* pointer){
  return pointer - sizeof(page_t);
}

void memfree(void* pointer)
{
  if(pointer != NULL) {
    page_t* page = to_page(pointer);
    page-> size = UNDEFINED;
    page-> free = true;
  }
}

int main(int argc, char** argv)
{
  char* pointer = memalloc(5);
  memfree(pointer);
  return 1;
}

Каковы наиболее распространенные методы (реализаций) для решения вопросов выше? Только приблизительные представления о нем.



Комментарии