w7 ex 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MEMORY_SIZE 10000000

unsigned int memory[MEMORY_SIZE];

void initialize_memory() {
    memset(memory, 0, sizeof(memory));
}

int allocate_first_fit(unsigned int adrs, int size) {
    for (int i = 0; i < MEMORY_SIZE; i++) {
        int contiguous = 0;
        while (i < MEMORY_SIZE && memory[i] == 0) {
            contiguous++;
            if (contiguous == size) {
                for (int j = i - size + 1; j <= i; j++) {
                    memory[j] = adrs;
                }
                return i - size + 1;
            }
            i++;
        }
    }
    return -1;
}


int allocate_best_fit(unsigned int adrs, int size) {
    int best_fit_start = -1;
    int best_fit_size = MEMORY_SIZE + 1;

    int current_start = -1;
    int current_size = 0;

    for (int i = 0; i < MEMORY_SIZE; i++) {
        if (memory[i] == 0) {
            if (current_start == -1) {
                current_start = i;
            }
            current_size++;
        } else {
            if (current_size >= size && current_size < best_fit_size) {
                best_fit_start = current_start;
                best_fit_size = current_size;
            }
            current_start = -1;
            current_size = 0;
        }
    }

    if (current_size >= size && current_size < best_fit_size) {
        best_fit_start = current_start;
    }

    if (best_fit_start != -1) {
        for (int i = best_fit_start; i < best_fit_start + size; i++) {
            memory[i] = adrs;
        }
        return best_fit_start;
    }

    return -1;
}


int allocate_worst_fit(unsigned int adrs, int size) {
    int worst_fit_start = -1;
    int worst_fit_size = -1;

    int current_start = -1;
    int current_size = 0;

    for (int i = 0; i < MEMORY_SIZE; i++) {
        if (memory[i] == 0) {
            if (current_start == -1) {
                current_start = i;
            }
            current_size++;
        } else {
            if (current_size > worst_fit_size) {
                worst_fit_start = current_start;
                worst_fit_size = current_size;
            }
            current_start = -1;
            current_size = 0;
        }
    }

    if (current_size > worst_fit_size) {
        worst_fit_start = current_start;
    }

    if (worst_fit_start != -1) {
        for (int i = worst_fit_start; i < worst_fit_start + size; i++) {
            memory[i] = adrs;
        }
        return worst_fit_start;
    }

    return -1;
}


void clear(unsigned int adrs) {
    for (int i = 0; i < MEMORY_SIZE; i++) {
        if (memory[i] == adrs) {
            memory[i] = 0;
        }
    }
}

int main() {
    initialize_memory();

    FILE* file = fopen("queries.txt", "r");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    clock_t start_time = clock();

    char line[100];
    while (fgets(line, sizeof(line), file)) {
        if (strcmp(line, "end\n") == 0) {
            break;
        }

        unsigned int adrs;
        int size;

        if (sscanf(line, "allocate %u %d", &adrs, &size) == 2) {
            int result = allocate_first_fit(adrs, size);
            if (result != -1) {
                printf("Allocated %d cells starting at address %u\n", size, result);
            } else {
                printf("Allocation failed for %d cells\n", size);
            }
        } else if (sscanf(line, "clear %u", &adrs) == 1) {
            clear(adrs);
        }
    }

    clock_t end_time = clock();


    double total_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;
    int total_queries = 0;

    rewind(file);
    while (fgets(line, sizeof(line), file)) {
        if (strcmp(line, "end\n") == 0) {
            break;
        }
        total_queries++;
    }

    double throughput = total_queries / total_time;

    printf("Throughput: %lf\n", throughput);

    fclose(file);

    return 0;
}