linux_programming/linux_programming_interface/solutions/chapter_7/exercise_7_2.c

/*
(Advanced) Implement malloc() and free()
 */

// TODO: puts use malloc why?
// TODO: more tests more implementations

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>
#include <assert.h>

#ifndef CHUNK_SIZE
#define CHUNK_SIZE 100
#endif

struct free_list_node
{
  size_t length;
  struct free_list_node* prev_free;
  struct free_list_node* next_free;
};

struct free_list_node *head;

static void
debug_brk(void)
{
  char buffer[200];
  snprintf(buffer, 200, "current program break: %p\n", sbrk(0));
  write(STDOUT_FILENO, buffer, strlen(buffer));
}

static void
debug_pointer(void *ptr)
{
  char buffer[200];
  snprintf(buffer, 200, "%p\n", ptr);
  write(STDOUT_FILENO, buffer, strlen(buffer));
}

static void
debug_print_free_list()
{
  char buffer[200];
  write(STDOUT_FILENO, "free_list:\n", 11);
  for (struct free_list_node *node = head;
       node; node = node->next_free)
    {
      snprintf(buffer, 200, "\t node: %p, %zu\n", head, head->length);
      write(STDOUT_FILENO, buffer, strlen(buffer));
    }

  write(STDOUT_FILENO, "\n", 1);
}

static struct free_list_node*
find_space_to_allocate(size_t size)
{
  struct free_list_node *result = NULL;
  for (struct free_list_node *node = head; node; node = node->next_free)
    if (node->length >= size)
      result = node;

  return result;
}

void*
malloc(size_t size)
{
  size_t real_size = size + sizeof(size_t);
  void* malloced_memory = NULL;
  char buffer[200];
  write(STDOUT_FILENO, "inside malloc\n", 14);
  if (!head)
    {
      write(STDOUT_FILENO, "brand new malloc\n", 17);
      debug_brk();
      void* program_break = sbrk(CHUNK_SIZE);
      debug_brk();
      head = program_break;
      head->length = CHUNK_SIZE;
      head->prev_free = NULL;
      head->next_free = NULL;
    }
  debug_print_free_list();
  struct free_list_node *node_to_allocate;
  if ((node_to_allocate = find_space_to_allocate(real_size)) != NULL)
    {
      void *new_node_ptr = (char *)head + real_size;
      memmove(new_node_ptr, head, sizeof *head);
      *(size_t*)head = size;
      malloced_memory = head;
      *(size_t *) malloced_memory = size;
      malloced_memory = (size_t *)malloced_memory + 1;
      head = new_node_ptr;
      head->length -= real_size;
    }
  debug_print_free_list();

  return malloced_memory;
}

static struct free_list_node*
find_nearest_free_space(void* ptr)
{
  struct free_list_node *result = head;
  for (struct free_list_node *node = head; node; node = node->next_free)
    {
      ptrdiff_t best_result = abs(ptr - (void*)result);
      ptrdiff_t current_result = abs(ptr - (void*)node);
      if (best_result < current_result)
        result = node;
    }

  return result;
}


void
free(void* ptr)
{
  typedef struct free_list_node free_list_node;
  write(STDOUT_FILENO, "inside free\n", 12);
  size_t* malloced_size = (size_t*)ptr - 1;
  struct free_list_node* closest_node = find_nearest_free_space(malloced_size);
  if ((void*)malloced_size < (void*)closest_node)
    {
      closest_node->length += *malloced_size + sizeof(size_t);
      memmove(malloced_size, closest_node, sizeof *closest_node);
      if (closest_node == head) head = (free_list_node *)malloced_size;
      closest_node = (free_list_node *)malloced_size;
      if (closest_node->next_free)
        closest_node->next_free->prev_free = closest_node;
      if (closest_node->prev_free)
        closest_node->prev_free->next_free = closest_node;
    }
  else
    {
      closest_node->length += *malloced_size + sizeof(size_t);
    }
  debug_print_free_list();
}

/*
 * tst
 */
static void
tst_simple_malloc(void)
{
  unsigned char *arr = malloc(10);
  assert(*((size_t *)arr - 1) == 10);
  debug_pointer(arr);
  free(arr);
}

int
main(int argc, char *argv[])
{
  tst_simple_malloc();
  return EXIT_SUCCESS;
}