allocator.c 3.79 KB
Newer Older
cdf009's avatar
cdf009 committed
1 2 3 4 5 6 7 8 9
#include "allocator.h"
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include "dnode.h"
#include "dlist.h"

//struct dnode *dnode_curr;
cdf009's avatar
cdf009 committed
10 11
struct dlist* free_list;
struct dlist* allocated_list;
cdf009's avatar
cdf009 committed
12
void* data1;
cdf009's avatar
cdf009 committed
13 14 15
void* datafirst;
void* databest;
void* dataworst;
cdf009's avatar
cdf009 committed
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

int allocator_init(int size){
	//void *data;
	//struct dnode *node;

	allocated_list = dlist_create();
	free_list = dlist_create();
	data1 = malloc(size);
	if (data1 == NULL){
		return -1;
	}


	//free_list dlist_create();
	dlist_add_front(free_list, data1, size);

	//allocated_list = dlist_create();

	return 0;
}


int deallocate(void *ptr){
	struct dnode* dealloc;
	dealloc = dlist_find_remove(allocated_list, ptr);

cdf009's avatar
cdf009 committed
42
 // printf("%x deallocating node %x, %d", ptr, dealloc->data, dealloc->size);
cdf009's avatar
cdf009 committed
43 44 45 46 47 48
	dlist_add_back(free_list, dealloc->data, dealloc->size);
	return 0;
}

void allocator_print() {
    // Create iterator to traverse list
cdf009's avatar
cdf009 committed
49
    struct dnode* iter = dlist_iter_begin(free_list);
cdf009's avatar
cdf009 committed
50 51 52 53 54 55 56 57

     printf("\n------------------------\n");
    /* Print free list */
    printf("Free List:             |\n");

    do{
    printf("Pointer: %x, Size: %d  ", iter->data, iter->size);
    iter = dlist_iter_next(free_list);
cdf009's avatar
cdf009 committed
58
printf("count: %d\n", allocated_list->counter);
cdf009's avatar
cdf009 committed
59 60 61 62 63 64 65 66
    }
	while(iter);
		if (dlist_num_elems(allocated_list) > 0) {
		iter = dlist_iter_begin(allocated_list);
   		 /* Print allocated list */
       		printf("\nAllocated List:\n");
		do{
//int* demo = (int*) iter;
cdf009's avatar
cdf009 committed
67
    printf("Pointer: %x, Size: %d\n", iter->data, iter->size);
cdf009's avatar
cdf009 committed
68 69 70 71 72 73 74 75 76 77
		iter = dlist_iter_next(allocated_list);
}
	while(iter);
}
                printf("                       |\n");
                printf("------------------------\n");

                return;
          }

cdf009's avatar
cdf009 committed
78
struct dnode* first_fit(int size){
cdf009's avatar
cdf009 committed
79
	//this is where it will check and see if it fits
cdf009's avatar
cdf009 committed
80
	struct dnode* current  = dlist_iter_begin(free_list);
cdf009's avatar
cdf009 committed
81 82 83

	do{
			if (size <= current->size){
cdf009's avatar
cdf009 committed
84
				datafirst = dlist_add_back(allocated_list, current->data, size);
cdf009's avatar
cdf009 committed
85 86 87 88 89 90 91 92 93
				current->size -= size;
				current->data += size;
				if  (0 == current->size){
					if (dlist_num_elems(free_list) > 1){
						dlist_find_remove(free_list, current);
					}
				}
				break;
			}
cdf009's avatar
cdf009 committed
94 95 96
			if (free_list->back == current){
				printf("No space in list");
			}
cdf009's avatar
cdf009 committed
97 98 99 100 101


			current = dlist_iter_next(free_list);
	}
	while(current);
cdf009's avatar
cdf009 committed
102 103
	return datafirst;

cdf009's avatar
cdf009 committed
104 105 106
	}


cdf009's avatar
cdf009 committed
107 108 109
struct dnode* best_fit(int size){
	struct dnode* iter = dlist_iter_begin(free_list);
	struct dnode* minimum;
cdf009's avatar
cdf009 committed
110 111 112 113 114 115 116 117 118 119 120 121 122
	int min_size = 0;

	do{
			if (size <= iter->size){
				if (iter->size <= min_size || min_size == 0){
					min_size = iter->size;
					minimum = iter;
				}
			}
			iter = dlist_iter_next(free_list);
	}
	while(iter);
			if (min_size == 0){
cdf009's avatar
cdf009 committed
123
				printf("No space in list"); 
cdf009's avatar
cdf009 committed
124
			}
cdf009's avatar
cdf009 committed
125
	databest = dlist_add_back(allocated_list, minimum->data, size);
cdf009's avatar
cdf009 committed
126 127 128 129 130 131 132 133
	minimum->size -= size;
	minimum->data += size;

	if  (0 == minimum->size){
		if (dlist_num_elems(free_list) > 1){
			dlist_find_remove(free_list, minimum);
		}
}
cdf009's avatar
cdf009 committed
134
return databest;
cdf009's avatar
cdf009 committed
135 136
}

cdf009's avatar
cdf009 committed
137 138 139
struct dnode* worst_fit(int size){
	struct dnode* iter = dlist_iter_begin(free_list);
	struct dnode* maximum;
cdf009's avatar
cdf009 committed
140 141 142 143 144 145 146 147 148 149 150 151 152
	int max_size = 0;

	do{
			if (size <= iter->size){
				if (iter->size >= max_size || max_size == 0){
					max_size = iter->size;
					maximum = iter;
				}
			}
			iter = dlist_iter_next(free_list);
	}
	while (iter);
			if (max_size == 0){
cdf009's avatar
cdf009 committed
153
				printf("No space in list!");
cdf009's avatar
cdf009 committed
154
			}
cdf009's avatar
cdf009 committed
155
	dataworst = dlist_add_back(allocated_list, maximum->data, size);
cdf009's avatar
cdf009 committed
156 157 158 159 160 161 162 163
	maximum->size -= size;
	maximum->data += size;

	if  (0 == maximum->size){
		if (dlist_num_elems(free_list) > 1){
			dlist_find_remove(free_list, maximum);
		}
}
cdf009's avatar
cdf009 committed
164 165 166

return dataworst;

cdf009's avatar
cdf009 committed
167 168
}

cdf009's avatar
cdf009 committed
169 170
struct dnode* allocate(int size, int param){
  struct dnode* x = NULL;
cdf009's avatar
cdf009 committed
171 172

	if (param == 0){
cdf009's avatar
cdf009 committed
173 174
		x = first_fit(size);
		return x;
cdf009's avatar
cdf009 committed
175 176
}
	if (param == 1){
cdf009's avatar
cdf009 committed
177 178
		x = best_fit(size);
                return x;
cdf009's avatar
cdf009 committed
179 180
}
	if (param == 2){
cdf009's avatar
cdf009 committed
181 182
		x = worst_fit(size);
		return x;
cdf009's avatar
cdf009 committed
183 184 185
}
return 0;
}