In questa sezione si andrà a vedere un esempio di modulo C. Questo modulo offre l'opportunità di creare una lista generica e di effettuarne delle operazioni base. Il modulo è diviso in header con tutte le dichiarazioni del caso e codice sorgente, contenente tutte le definizioni.

Il primo passo è capire come è una lista unidirezionale in memoria. L'idea è che la lista è composta da vari elementi, ognuno dei quali contiene un singolo elemento ed un puntatore all'elemento successivo. La nostra lista può in generale contenere qualunque elemento, quindi ci serve che ci sia un puntatore di tipo void* che rappresenti il nostro generico elemento. Per quanto riguarda next invece, se l'elemento è l'ultimo nella lista, il puntatore sarà NULL. Per velocizzare l'operazione di count, l'inizio della lista avrà dei metadati in più (come il numero di elementi). In memoria avremo una cosa di questo tipo:

Ok, quindi le strutture saranno:

typedef struct list_cell {
    void* data;
    struct list_cell* next;
} list_cell;

typedef struct {
    list_cell* head;
    list_cell* tail;
    int size;
} list;

Ok, abbiamo le nostre strutture dati. Però ora vogliamo effettuare alcune operazioni. Le primisse operazioni che vorremo saranno la creazione e la distruzione delle strutture dati principali:

list* initList() {
	list* retVal = malloc(sizeof(list));
	if (retVal == NULL) {
		exit(1);
	}

	retVal->head = NULL;
	retVal->size = 0;
	retVal->tail = NULL;

	return retVal;
}

void destroyList(list* lst) {
	list_cell* tmp = lst->head;
	list_cell* tmp2;

	while (tmp != NULL) {
		tmp2 = tmp->next;
		free(tmp);
		tmp = tmp2;
	}
	free(lst);
}

Nella nostra lista potremo aggiungere elementi o in testa o in coda:

void addHeadInList(list* l, void* el) {
	list_cell* new_cell = malloc(sizeof(list_cell));
	if (new_cell == NULL) {
		exit(1);
	}

	new_cell->payload = el;
	new_cell->next = l->head;

	l->size++;
	l->head = new_cell;
	if (l->tail == NULL) {
		l->tail = new_cell;
	}
}

void addTailInList(list* l, void* el) {
	list_cell* new_cell = malloc(sizeof(list_cell));
	if (new_cell == NULL) {
		exit(1);
	}

	new_cell->payload = el;
	new_cell->next = NULL;
	if (l->tail != NULL) {
		l->tail->next = new_cell;
	}

	l->size++;
	if (l->head == NULL) {
		l->head = new_cell;
	}
	l->tail = new_cell;

}

Mettiamo alcune funzioni di contorno:

int getSizeOfList(const list* l) {
	return l->size;
}

bool isEmptyList(const list* l) {
	return l->size == 0;
}

void* popFromList(list* l) {
	if (isEmptyList(l)) {
		return NULL;
	}

	list_cell* cell = l->head;
	void* retVal = cell->payload;
	l->head = l->head->next;
	l->size--;
	if (isEmptyList(l)) {
		l->tail = NULL;
	}

	free(cell);
	return retVal;
}

void* getHeadOfList(const list* l) {
	if (isEmptyList(l)) {
		return NULL;
	}
	return l->head->payload;
}

void* getTailOfList(const list* l) {
	if (l->tail == NULL) {
		return NULL;
	}
	return l->tail->payload;
}

In questo step aggiungiamo delle funzioni che sfruttano i prototipi di funzioni per ottenere un modulo lista abbastanza generale.

bool removeElementInList(list* l, bool (*f)(void*)) {
	list_cell* previous = NULL;
	list_cell* tmp = l->head;
	list_cell* tmp2;
	while (tmp != NULL) {
		tmp2 = tmp->next;
		if (f(tmp->payload)) {
			if (previous == NULL) {
				//head removal
				l->head = tmp->next;
			} else {
				previous->next = tmp->next;
			}
			l->size--;

			free(tmp);
			return true;
		}
		previous = tmp;
		tmp = tmp2;
	}
	return false;
}

bool removeAndDestroyElementInList(list* l, bool (*f)(void*), void (*d)(void*)) {
	list_cell* previous = NULL;
	list_cell* tmp = l->head;
	list_cell* tmp2;
	while (tmp != NULL) {
		tmp2 = tmp->next;
		if (f(tmp->payload)) {
			if (previous == NULL) {
				//head removal
				l->head = tmp->next;
			} else {
				previous->next = tmp->next;
			}
			l->size--;

			d(tmp->payload);
			free(tmp);
			return true;
		}
		previous = tmp;
		tmp = tmp2;
	}
	return false;
}

Abbiamo appena fatto una carrellata del codice sorgente che implementa le funzioni. Ma dove lo mettiamo? Ogni modulo è formato da 2 componenti: l'header file in cui possiamo mettere tutte le dichiarazioni delle funzioni e delle variabili che vogliamo esporre al pubblico (opportunamente con le guardie MACRO); il codice sorgente dove mettiamo le definizioni delle funzioni e delle variabili che abbiamo dichiarato nell'header file. Puoi vedere l'esempio finale qui.

Ok, ora come facciamo ad usare il nostro modulo di esempio? Semplice, nel nostro programma principale includiamo l'header list.h e poi sfruttiamo tutte le funzioni dichiarate nel modulo stesso, come in questo modo:

#include "list.h"
#include <stdio.h>

int main() {
    list* l = initList();
    int* a = malloc(sizeof(int)); *a = 5;
    int* b = malloc(sizeof(int)); *b = 6;
    int* c = malloc(sizeof(int)); *c = 7;
    addTailInList(l, a);
    addTailInList(l, b);
    addHeadInList(l, c);

    list_cell* tmp = getHeadOfList(l);
    while (tmp != NULL) {
        printf("element is %d\n", *((int*)(tmp->payload)));
        tmp = tmp->next;
    }

    destroyListWithElements(l, free);
}

Prova ad estendere il modulo con nuove funzionalità:

1. Una funzione che ti permette di ottenere l'n-esimo elemento;
2. Una funzione che clona la lista (ma lascia i riferimenti degli oggetti);
3. Una funzione che clone la lista (e clona anche gli oggetti contenuti nella lista);
4. Una funzione che, dato un buffer di caratteri, stampi il contenuto della stringa in esso;

Questa implementazione di lista va bene, ma a volte è un pò sprecona per quanto riguarda l'heap. Come nell'esempio fatto prima, se noi abbiamo semplici interi o strutture molto piccole, sarebbe forse raccomandabile inserire i dati non esterni alle list_cell, ma direttamente al loro interno.

Un'altra cosa: se andate nell'header di list.h nella repository vi accorgerete che la definizione del typedef struct list non è presente! E' solo presente la linea:

typedef struct list list;

Questo è fatto perché gli sviluppatori terzi non devono sapere come è fatta esattamente la struttura list, ma la devono semplicemente usare tramite le API che voi avete fornito nell'header. Questo approccio permette di creare codice più flessibile: supponete che un giorno dobbiate modificare la struttura di list (per esempio togliendo il campo size per qualche motivo); se avete definito la struttura list nell'header potenzialmente tutti potrebbero aver usato il campo size. Con questo metodo invece è assicurato che solo list.c lo stia utilizzando. Questo approccia ha anche dei difetti: potrete infatti usare solo list*, ma non potrete mai definire una variabile di tipo list (giust'appunto perché al di fuori di list.c, nessuno sa quale sia l'esatto numero di byte occupato da list).

• Un video che spiega le liste: https://www.youtube.com/watch?v=_jQhALI4ujg;
• Alcune riflessioni di Bjarne Stroustrup circa le liste: https://www.youtube.com/watch?v=YQs6IC-vgmo