doubly_ll_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/basic_ops.h"
#include "headers/simply_ll_ops.h"

/*
 * Functie care gaseste al n-lea nod dintr-o lista dublu inlantuita
 * @return pointer catre nod
 */
dll_node_t *get_nth_node(dll_node_t *head, U_INT n)
{
	U_INT i = 0;
	dll_node_t *prev;
	while (head && i != n) {
		prev = head;
		head = head->next;
		i++;
	}

	return (head) ? head : prev;
}

/*
 * Functie care calculeaza numarul de elemente
 * dintr-o lista dublu/simplu inlantuita !liniara.
 * @return numarul de elemente
 */
U_INT get_size_dll(dll_node_t *head)
{
	U_INT size = 0;
	while (head)
		head = head->next, size++;

	return size;
}

/*
 * Functie care aloca memorie pentru o noua lista si
 * face toate initializarile aferente
 *
 * @return pointer catre lista creata
 */
doubly_ll_t *create_dll(U_INT data_size)
{
	doubly_ll_t *list = malloc(sizeof(doubly_ll_t));
	DIE(!list, "Malloc failed\n");

	list->head = NULL;
	list->data_size = data_size;
	list->size = 0;

	return list;
}

/*
 * Functie care creeaza un block la sfarsitul
 * unei liste dublu inlantuite
 *
 * @return dll_node_t* catre noul nod
 */
dll_node_t *create_last(dll_node_t **head, U_INT data_size, U_INT addr)
{
	dll_node_t *new = calloc(1, sizeof(dll_node_t));
	DIE(!new, "Calloc failed\n");

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

	_info->data = calloc(1, data_size);
	DIE(!_info->data, "Calloc failed\n");
	_info->frag_ids = create_sll(sizeof(U_INT));
	_info->size = data_size;
	_info->addr = addr;

	new->data = _info;
	new->next = NULL;

	if (!(*head)) {
		*head = new;
		new->prev = NULL;
		return new;
	}

	dll_node_t *curr = *head;
	while (curr->next)
		curr = curr->next;

	curr->next = new;
	new->prev = curr;

	return new;
}

/*
 * Functie care insereaza un block deja existent
 * ca head al unei liste dublu inlantuite liniare.
 */
void insert_as_head(dll_node_t **head, dll_node_t **block)
{
	(*block)->next = *head;

	(*block)->prev = NULL;
	if (*head)
		(*head)->prev = *block;

	*head = *block;
}

/*
 * Functie care insereaza un block deja existent
 * ca ultim element al unei liste dublu inlantuite liniare.
 */
void insert_as_last(dll_node_t **head, dll_node_t **block)
{
	(*block)->next = NULL;

	if (!(*head)) {
		*head = *block;
		(*block)->prev = NULL;
		return;
	}

	dll_node_t *curr = *head;
	while (curr->next)
		curr = curr->next;

	curr->next = *block;
	(*block)->prev = curr;
}

/*
 * Functie care insereaza un block deja existent
 * la pozitia n dintr-o lista dublu inlantuita liniara.
 */
void insert_to_nth_pos(dll_node_t **head, U_INT n, dll_node_t **block)
{
	U_INT size = get_size_dll(*head);

	if (!n) {
		insert_as_head(head, block);
	} else if (n >= size) {
		insert_as_last(head, block);
	} else {
		dll_node_t *curr = *head;

		(*block)->next = NULL;
		while (--n)
			curr = curr->next;

		dll_node_t *tmp = curr->next;
		(*block)->next = curr->next;
		(*block)->prev = curr;
		curr->next = (*block);
		tmp->prev = (*block);
	}
}

/*
 * Functie care scoate un block dat ca parametru
 * dintr-o lista dublu inlantuita liniara.
 *
 * @return block-ul dupa ce a fost scos din lista
 */
dll_node_t *delete_block(dll_node_t **head, dll_node_t *block)
{
	if (!(*head) || !block)
		return NULL;

	// Daca stergem head
	if (*head == block)
		*head = block->next;

	// Daca nu e ultimul nod, refacem legaturile
	if (block->next)
		block->next->prev = block->prev;

	// Daca nu e primul nod, refacem legaturile
	if (block->prev)
		block->prev->next = block->next;

	return block;
}

/*
 * Functie care elibereaza toata memoria
 * alocata unei liste dublu inlantuite,
 */
void dll_free(doubly_ll_t **list_ptr)
{
	dll_node_t *curr;

	if (!list_ptr || !*list_ptr)
		return;

	U_INT size = get_size_dll((*list_ptr)->head);
	while (size > 0) {
		curr = delete_block(&(*list_ptr)->head, (*list_ptr)->head);
		free_block(curr);
		size--;
	}

	free(*list_ptr);
	*list_ptr = NULL;
}