basic_ops.c

/**
 * Copyright GOIDESCU Rares-Stefan 312CAb 2023-2024
 */

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

#include "headers/macros.h"
#include "headers/structs.h"
#include "headers/sfl_ops.h"
#include "headers/doubly_ll_ops.h"
#include "headers/simply_ll_ops.h"

/*
 * @return pointer la informatiile unui block
 */
block_info_t *get_block_info(void *data)
{
	return (block_info_t *)data;
}

/*
 * Functie care elibereaza memoria unui block
 */
void free_block(dll_node_t *node)
{
	block_info_t *node_info = get_block_info(node->data);
	free_sll(&node_info->frag_ids);
	free(node_info->data);
	free(node_info);
	free(node);
}

/*
 * Functie care intoarce inversul unei stive si
 * elibereaza memoria stivei originale
 *
 * @return pointer catre stiva inversata
 */
s_ll_t *reverse_stack(s_ll_t *src)
{
	s_ll_t *tmp = create_sll(sizeof(U_INT));

	while (get_size_sll(src) > 0) {
		s_ll_node_t *popd = pop_sll(&src->head);

		push_sll(&tmp->head, popd->data, sizeof(U_INT));

		free(popd->data);
		free(popd);
	}

	return tmp;
}

/*
 * Functie care copiaza stiva in care mentin ID-urile fragmentarilor
 * si elibereaza memoria stivei originale
 */
void copy_frag_ids(block_info_t *dest1, block_info_t *dest2, block_info_t *src)
{
	s_ll_t *tmp = reverse_stack(src->frag_ids);

	while (get_size_sll(tmp) > 0) {
		s_ll_node_t *popd = pop_sll(&tmp->head);

		push_sll(&dest1->frag_ids->head, popd->data, sizeof(U_INT));
		push_sll(&dest2->frag_ids->head, popd->data, sizeof(U_INT));

		free(popd->data);
		free(popd);
	}

	free_sll(&tmp);
}

/*
 * Functie care imparte un block in 2 fragmente
 *
 * prin "referinta" trimite block-ul care ramane liber
 * @return pointer la block-ul de alocat
 */
dll_node_t *fragment_block(dll_node_t **block_to_fragment_ref,
						   U_INT fragment_size,
						   U_INT *last_frag_id_ref)
{
	dll_node_t *block_to_fragment = *block_to_fragment_ref;

	block_info_t *block_to_fragment_info =
		get_block_info(block_to_fragment->data);

	U_INT left_shard_size = fragment_size; // Aflam datele noilor block-uri
	U_INT right_shard_size = block_to_fragment_info->size - fragment_size;
	U_INT last_frag_id = *last_frag_id_ref;

	block_info_t *left_shard_info = malloc(sizeof(block_info_t));
	DIE(!left_shard_info, "Malloc failed\n");

	block_info_t *right_shard_info = malloc(sizeof(block_info_t));
	DIE(!right_shard_info, "Malloc failed\n");

	left_shard_info->frag_ids = create_sll(sizeof(int)); // Continui lista de ID
	right_shard_info->frag_ids = create_sll(sizeof(int)); // ale fragmentarilor

	copy_frag_ids(left_shard_info, right_shard_info, block_to_fragment_info);

	// Adaugam ultimul ID de fragmentare in listele celor 2 block-uri
	push_sll(&left_shard_info->frag_ids->head, &last_frag_id, sizeof(U_INT));
	push_sll(&right_shard_info->frag_ids->head, &last_frag_id, sizeof(U_INT));

	dll_node_t *left_shard = malloc(sizeof(dll_node_t));
	DIE(!left_shard, "Malloc failed\n");

	dll_node_t *right_shard = malloc(sizeof(dll_node_t));
	DIE(!right_shard, "Malloc failed\n");

	// Initializam block-urile noi
	left_shard_info->size = left_shard_size;
	left_shard_info->addr = block_to_fragment_info->addr;
	left_shard_info->data = calloc(1, left_shard_size);
	DIE(!left_shard_info->data, "Calloc failed\n");
	left_shard->data = left_shard_info;
	left_shard->next = NULL;
	left_shard->prev = NULL;

	right_shard_info->size = right_shard_size;
	right_shard_info->addr = left_shard_info->addr + fragment_size;
	right_shard_info->data = calloc(1, right_shard_size);
	DIE(!left_shard_info->data, "Calloc failed\n");
	right_shard->data = right_shard_info;
	right_shard->prev = NULL;
	right_shard->next = NULL;

	free_block(block_to_fragment);

	// Trimitem prin "referinta" unul dintre fragmente
	block_to_fragment = right_shard;

	*block_to_fragment_ref = block_to_fragment;

	last_frag_id += 1;
	*last_frag_id_ref = last_frag_id;

	// returnam pointer catre block-ul de alocat
	return left_shard;
}

/*
 * Functie care muta un block primit la locatia perfecta in lista care
 * tine minte block-urile alocate
 */
void move_block_from_sfl_to_allocd(allocd_t **dest_ref,
								   dll_node_t **fragment_ref)
{
	block_info_t *frag_info = get_block_info((*fragment_ref)->data);
	dll_node_t *curr = (*dest_ref)->blocks->head;
	U_INT i = 0;
	for (; i < (*dest_ref)->blocks->size && curr; ++i, curr = curr->next) {
		block_info_t *curr_info = get_block_info(curr->data);
		if (curr_info->addr > frag_info->addr)
			break;
	}

	insert_to_nth_pos(&((*dest_ref)->blocks->head), i, &(*fragment_ref));
}

/*
 * Functie care uneste doua block-uri
 *
 * @return dll_node_t* catre noul block
 */
dll_node_t *reconstruct_block(dll_node_t *block1, dll_node_t *block2)
{
	dll_node_t *new_block = malloc(sizeof(dll_node_t));
	DIE(!new_block, "Malloc failed\n");

	block_info_t *new_block_info = malloc(sizeof(block_info_t));
	DIE(!new_block_info, "Malloc failed\n");

	block_info_t *block1_info = get_block_info(block1->data);
	block_info_t *block2_info = get_block_info(block2->data);

	new_block_info->size = block1_info->size + block2_info->size;
	new_block_info->data = calloc(1, new_block_info->size);
	DIE(!new_block_info, "Calloc failed\n");

	if (block1_info->addr < block2_info->addr)
		new_block_info->addr = block1_info->addr;
	else
		new_block_info->addr = block2_info->addr;

	// Copiem ID-urile fragmentarilor la care au luat parte block-urile
	new_block_info->frag_ids = create_sll(sizeof(U_INT));

	// Intoarcem stiva pentru a pastra ordinea
	s_ll_t *tmp = reverse_stack(block1_info->frag_ids);
	while (get_size_sll(tmp) > 0) {
		s_ll_node_t *popd = pop_sll(&tmp->head);

		push_sll(&new_block_info->frag_ids->head, popd->data, sizeof(U_INT));

		free(popd->data);
		free(popd);
	}
	free_sll(&tmp);

	// Eliberam memoria ocupata de cele 2 block-uri
	free_block(block1);
	free_block(block2);

	new_block->data = new_block_info;

	return new_block;
}

/*
 * Insereaza un block pe pozitia perfecta :) in vectorul de liste
 */
void insert_block_in_arr(seg_free_list_t *sfl, dll_node_t *block)
{
	block_info_t *block_info = get_block_info(block->data);
	// Cautam un bucket care sa contina block-uri de dimensiunea necesara
	U_CHAR bucket_exists = FALSE;
	U_INT idx = sfl->curr_size;
	for (U_INT i = 0; i < sfl->curr_size; ++i) {
		if (sfl->blocks[i]->data_size == block_info->size) {
			bucket_exists = TRUE;
			idx = i;
			break;
		}
	}

	if (bucket_exists) {
		// Daca exista un bucket, inseram block-ul acolo,
		// avand grija sa mentinem adresele sortatea
		dll_node_t *_head = sfl->blocks[idx]->head;

		if (!_head) {
			insert_as_head(&sfl->blocks[idx]->head, &block);
			sfl->blocks[idx]->size++;
			return;
		}

		block_info_t *_head_info = get_block_info(_head->data);
		if (_head_info->addr > block_info->addr) {
			insert_as_head(&sfl->blocks[idx]->head, &block);
			sfl->blocks[idx]->size++;
			return;
		}

		U_INT i = 1;
		while (_head && _head->next) {
			_head_info = get_block_info(_head->data);
			block_info_t *_next_info = get_block_info(_head->next->data);
			if (_head_info->addr < block_info->addr &&
				_next_info->addr > block_info->addr) {
				insert_to_nth_pos(&sfl->blocks[idx]->head, i, &block);

				sfl->blocks[idx]->size++;
				return;
			}
			i++;
			_head = _head->next;
		}

		insert_as_last(&sfl->blocks[idx]->head, &block);
		sfl->blocks[idx]->size++;
	} else {
		// Daca nu exista vreun bucket cu block-uri de dimensiunea cautata
		// cream un nou bucket, la finalul vectorului de liste, pe care
		// il vom muta pana cand se va afla pe pozitia corespunzatoare
		// in vector, criteriul de sortare fiind dimensiunea block-urilor
		sfl->curr_size++;
		check_resize_sfl(&sfl); // verificam daca avem destul loc in vector
								// in caz contrar, marim vectorul

		sfl->blocks[idx] = create_dll(block_info->size);
		insert_as_head(&sfl->blocks[idx]->head, &block);
		sfl->blocks[idx]->size = 1;
		sfl->blocks[idx]->data_size = block_info->size;

		U_INT i = 0;
		for (; i < sfl->curr_size; i++)
			if (sfl->blocks[i]->data_size > block_info->size)
				break;

		for (U_INT j = sfl->curr_size - 1; j > i; --j) {
			void *aux = sfl->blocks[j];
			sfl->blocks[j] = sfl->blocks[j - 1];
			sfl->blocks[j - 1] = aux;
		}
	}
}