src/free_list.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/*
 * src/free_list.c
 *
 * Implementation of free list management for liballoc
 * CISC 301 -- Operating Systems, Project 3
 *
 * Copyright (C) 2025  Douglas B. Rumbaugh <dbrumbaugh@harrisburgu.edu>
 *
 * Distributed under the Modified BSD License
 *
 */
#include "free_list.h"

free_nd *fl_find_first_fit(free_nd *free_list, size_t size) {
  for (free_nd *nd = free_list; nd; nd = nd->next) {
    if (nd->size >= size) {
      return nd;
    }
  }

  return NULL;
}

void *fl_split_node(free_nd **free_list, free_nd *split_nd, size_t size) {

  ssize_t extra_space = split_nd->size - size - sizeof(header);
  if (extra_space >= SPLIT_THRESHOLD) {
    free_nd *new_nd = (free_nd *)((char *)(split_nd) + size + sizeof(header));
    new_nd->next = split_nd->next;
    split_nd->next = new_nd;

    new_nd->size = extra_space - sizeof(header);

    header *new_hdr = (header *)((char *)new_nd - sizeof(header));
    new_hdr->magic_number = MAGIC_NUMBER;
    new_hdr->size = extra_space - sizeof(header);

    header *old_hdr = (header *)((char *)split_nd - sizeof(header));
    old_hdr->size = size;
  }

  if (*free_list == split_nd) {
    *free_list = (*free_list)->next;
  }

  for (free_nd *nd = *free_list; nd; nd = nd->next) {
    if (nd->next == split_nd) {
      /*
       * split_nd is not null, so we know that nd->next is
       * also not null here
       */
      nd->next = nd->next->next;
    }
  }

  return split_nd;
}

void fl_coalesce_nodes(free_nd *free_list) {
  for (free_nd *nd = free_list; nd; nd = nd->next) {
    if ((size_t)nd + sizeof(header) + nd->size == (size_t)nd->next) {
      nd->size += sizeof(header) + nd->next->size;
      ((header *)((void *)nd - sizeof(header)))->size += sizeof(header) + nd->next->size;
      nd->next = nd->next->next;
    }
  }
}

void fl_add_node(free_nd **free_list, void *ptr) {
  free_nd *new_nd = (free_nd *)ptr;

  free_nd **insert_point = free_list;
  for (free_nd *nd = *free_list; nd; nd = nd->next) {
    if (nd < new_nd) {
      insert_point = &nd->next;
    } else {
      break;
    }
  }

  new_nd->next = *insert_point;
  new_nd->size = ((header *)(ptr - sizeof(header)))->size;

  *insert_point = new_nd;
}