Skip to content

Instantly share code, notes, and snippets.

@victoroliveirab

victoroliveirab/contiguous.c

Last active October 14, 2019 02:03
Show Gist options
  • Save victoroliveirab/53c71804cedbf8c52f881dc4db256f5d to your computer and use it in GitHub Desktop.
Save victoroliveirab/53c71804cedbf8c52f881dc4db256f5d to your computer and use it in GitHub Desktop.
Download ZIP
Contiguous - Worst code ever written :D
Raw
contiguous.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFFER_LENGTH 20
int parse_process(char* token);
void request_worst(short (*array)[], long num_of_bytes, int pid);
void request_best(short (*array)[], long num_of_bytes, int pid);
void request_first(short (*array)[], long num_of_bytes, int pid);
void traverse_array(short (*array)[]);
void release(short(*array)[],long tam[],int pid_re);
void compact (short (*array)[]);
int find_hole_start(short (*array)[], int start_index);
int find_hole_end (short (*array)[], int start_index);
void show_status(short (*array)[]);
int take_index_final(short(*array)[],int pid_re);
int take_index_start(short(*array)[],int pid_re);
long total_memory;
int main(int argc, char const *argv[])
{
long number_of_process[4];
long tam[4];
// ./allocator 1048576
const char blank[2] = " ";
if (argc < 2) {
printf("Too few arguments... Exit\n");
exit(1);
}
total_memory = atol(argv[1]);
short array[total_memory];
short (*ptr)[];
ptr = &array;
memset(array, 0, sizeof array);
printf("Allocated %ld bytes on the memory\n", total_memory);
char line[BUFFER_LENGTH];
while (1) {
traverse_array(ptr);
printf("allocator>");
char *command = fgets(line, BUFFER_LENGTH, stdin);
if (command != NULL) printf("command typed = %s", command);
char *token = strtok(command, blank);
if (strncmp(token, "RQ", 2) == 0) {
token = strtok(NULL, blank);
if (strncmp(token, "P", 1)) {
continue;
}
int pid = parse_process(token);
token = strtok(NULL, blank);
if (token == NULL) continue;
long num_of_bytes = atol(token);
tam[pid] = num_of_bytes;
if (token == NULL) continue;
token = strtok(NULL, blank);
if (token == NULL) continue;
char method = *token;
switch (method) {
case 'W':
request_worst(ptr, num_of_bytes, pid);
break;
case 'B':
request_best(ptr, num_of_bytes, pid);
break;
case 'F':
request_first(ptr, num_of_bytes, pid);
break;
default:
printf("%c method is undefined...\n", method);
}
} else if (strncmp(token, "RL", 2) == 0) {
token = strtok(NULL, blank);
if (strncmp(token, "P", 1)) {
continue;
}
int pid_re = parse_process(token);
release(ptr,tam,pid_re);
} else if (strncmp(token, "C", 1) == 0) {
compact(ptr);
} else if (strncmp(token, "STAT",4) == 0) {
show_status(ptr);
} else if (strncmp(token, "X", 1) == 0) {
printf("Exiting...\n");
break;
} else {
printf("Command not found...\n");
}
}
printf("Program normally terminated...\n");
return 0;
}
int take_index_final(short(*array)[],int index){
int finale = 0;
while((*array)[finale] && finale < total_memory){
++finale;
if((*array)[finale] == index + 2 || (*array)[finale] < index){
break;
}
}
return finale;
}
int take_index_start(short(*array)[],int index){
int start = 0;
int compare = index + 1;
while((*array)[start] != compare){
++start;
if((*array)[start] == compare){
break;
}
}
if(start == 1){
start = 0;
}
return start;
}
void release(short(*array)[],long tam[],int pid_re){
int begin = take_index_start(array,pid_re);
printf("START AT:%d\n",begin);
long final = tam[pid_re] + begin;
printf("FINISH AT:%ld\n",final);
if (final - begin == tam[pid_re]) {
printf("process %d released with sucess\n",pid_re);
for (int i = begin; i < final; ++i) {
(*array)[i] = (*array)[i] -(pid_re + 1);
}
}
else {
printf("Unable to release\n");
}
}
void request_first(short (*array)[], long num_of_bytes, int pid)
{
int address = 0;
int begin = 0;
while (address < total_memory && address - begin <= num_of_bytes) {
if ((*array)[address]) {
begin = address + 1;
}
++address;
}
--address;
if (address - begin == num_of_bytes) {
printf("Able to allocate\n");
for (int i = begin; i < address; ++i) {
(*array)[i] = pid + 1;
}
}
else {
printf("Unable to allocate\n");
}
}
void request_worst(short (*array)[], long num_of_bytes, int pid)
{
int address = 0;
int begin = 0;
int begin_of_worst_fit = 0;
int end_of_worst_fit = 0;
int size = 0;
while (address < total_memory) {
if ((*array)[address]) {
begin = address;
}
else {
if (address - 1 - begin >= num_of_bytes) {
if (address - 1 - begin > size) {
size = address - 1 - begin;
begin_of_worst_fit = begin;
end_of_worst_fit = address - 1;
}
}
}
++address;
}
if (size >= num_of_bytes) {
printf("Able to allocate\n");
if (begin_of_worst_fit) ++begin_of_worst_fit;
if (begin_of_worst_fit == 0 && (*array)[begin_of_worst_fit]) ++begin_of_worst_fit;
for (int i = begin_of_worst_fit; i < begin_of_worst_fit + num_of_bytes; ++i) {
(*array)[i] = pid + 1;
}
}
else {
printf("Unable to allocate\n");
}
}
void request_best(short (*array)[], long num_of_bytes, int pid)
{
int address = 0;
int begin = 0;
int begin_of_best_fit = 0;
int end_of_best_fit = 0;
int b = 0, e = 0;
int size = 0;
while (address < total_memory) {
if ((*array)[address]) {
if (e != b && e - 1 - b >= num_of_bytes) {
begin_of_best_fit = b;
end_of_best_fit = e - 1;
size = end_of_best_fit - begin_of_best_fit;
}
b = address + 1;
e = address + 1;
begin = address;
}
else {
++e;
}
++address;
}
if ((e - b - 1 < end_of_best_fit - begin_of_best_fit && (e - b == 1)) || (begin_of_best_fit == 0 && end_of_best_fit == 0 && (*array)[b] == 0)) {
begin_of_best_fit = b;
end_of_best_fit = e - 1;
size = end_of_best_fit - begin_of_best_fit;
if (size == 0) ++size;
}
if (size >= num_of_bytes) {
printf("Able to allocate\n");
if (begin_of_best_fit == 0 && (*array)[begin_of_best_fit]) ++begin_of_best_fit;
for (int i = begin_of_best_fit; i < begin_of_best_fit + num_of_bytes; ++i) {
(*array)[i] = pid + 1;
}
}
else {
printf("Unable to allocate\n");
}
}
void compact (short (*array)[])
{
int destination_hole_end;
int index = 0;
int destination_hole_start = find_hole_start(array, index);
index = destination_hole_start;
while(index < total_memory) {
destination_hole_end = find_hole_end(array, index);
index = destination_hole_end;
if (index == total_memory) break;
int pid = (*array)[index];
while ((*array)[index] == pid) {
(*array)[destination_hole_start] = (*array)[index];
(*array)[index] = 0;
destination_hole_start++;
index++;
}
}
}
int find_hole_start (short (*array)[], int start_index)
{
int hole_start = start_index;
while ((*array)[hole_start] && hole_start < total_memory) hole_start++;
return hole_start;
}
int find_hole_end (short (*array)[], int start_index)
{
int hole_end = start_index;
while((*array)[hole_end] == 0 && hole_end < total_memory) hole_end++;
return hole_end;
}
void show_status(short (*array)[])
{
int index = 0;
int process_start;
int hole_end;
while (index < total_memory) {
printf("Addresses ");
if ((*array)[index] == 0) {
hole_end = find_hole_end(array, index);
printf("[%d:%d] Unused\n", index, hole_end-1);
index = hole_end;
} else {
process_start = index;
while((*array)[index] == (*array)[process_start]) index++;
printf("[%d:%d] Process P%d\n", process_start, index-1, (*array)[process_start] - 1);
}
}
}
int parse_process(char* token)
{
char p[4];
char p1[4];
int i = 1;
while (*(token + i) >= 48 && *(token + i) <= 57) p[i++-1] = *(token + i);
//printf("Process passed is %s\n", p);
return atoi(p);
}
void traverse_array(short (*array)[])
{
printf("--------------------------------------------------MEMORY--------------------------------------------------\n");
printf(">>> [");
int i = 0;
for (; i < total_memory - 1; ++i) {
printf("%d, ", (*array)[i]);
}
printf("%d]\n", (*array)[i]);
printf("----------------------------------------------------------------------------------------------------------\n");
}
@victoroliveirab
Copy link
Author

Reproduce error:

Execute ./contiguous 30
And then the following commands:

RQ P0 20 W
RQ P1 5 F
RL P0
RQ P3 3 W
RQ P0 13 W
RQ P7 2 W
RQ P5 2 W
RQ P8 1 W
C
RL P0 << This command doesn't free the spots

@victoroliveirab
Copy link
Author

Ok now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment