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

/*
 * 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) {
  /* for now, we'll just remove the node from the free list */

  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;
      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;
 }