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

/*
 * 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) == (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;
  new_nd->next = NULL;
  new_nd->size = ((header*)(ptr - sizeof(header)))->size;

  if (!(*free_list)) {
    *free_list = new_nd;
    return;
  }

  for (free_nd *nd = *free_list; nd; nd = nd->next) {
    if (nd->next > new_nd) {
      new_nd->next = nd->next;
      nd->next = new_nd;
      return;
    }
  }

  /* if we get here, then the new node must go before the current head */
  new_nd->next = *free_list;
  *free_list = new_nd;
  return;
}