[C] Manipolazione liste generiche

[Frank Lioty]

Salve a tutti ragazzi, è la prima volta che scrivo nel forum (non c'è una sezione di presentazione?). Devo realizzare un progetto per l'uni. Al momento mi sto cimentando nelle varie esercitazioni prima di lanciarmi sul progetto vero e proprio.

Una di queste chiede di realizzare funzioni che manipolino liste con due campi generici: una chiave (key) ed un'informazione (payload). Il codice di partenza è il seguente:

----------------------------------------------------------------------

#ifndef __GENLIST__H
#define __GENLIST__H

typedef struct elem {
void * key;
void * payload;
struct elem * next;
} elem_t; 

typedef struct {
elem_t * head;
int (* compare) (void *, void *); //confronta due chiavi, ritorna 0 se uguali
void * (* copyk) (void *); //copia una chiave
void * (* copyp) (void *); //copia un payload
} list_t;

list_t * new_List(int (* compare) (void *, void *),void* (* copyk) (void *),void* (*copyp) (void*));

void free_List (list_t ** pt);

int add_ListElement(list_t * t,void * key, void* payload);

int remove_ListElement(list_t * t,void * key);

elem_t * find_ListElement(list_t * t,void * key);

#endif

-----------------------------------------------------------------------

Partiamo dalla più semplice (cioè l'add_ListElement). Nel caso si trattasse di liste di int (sia la key che il payload), dovrebbe essere qualcosa di questo tipo:

inserisce una nuova coppia (key, payload) in testa alla lista, sia key che payload devono essere copiate nel nuovo elemento della lista. Nella lista non sono permesse chiavi replicate

//Return values:
-1 se si sono verificati errori (errno settato opportunamente)
0 se l'inserimento è andato a buon fine

int add_ListElement (list_t* head, int k, int p) {
elem_t* tmp;
tmp = malloc(sizeof(elem_t));
if ( tmp == NULL ) return -1;
tmp -> next = head;
tmp -> key = k;
tmp -> payload = p;
return 0;
}

Proviamo ora con liste generiche:

int add_ListElement (list_t* head, void* k, void* p, void * (* copyk) (void *), void * (* copyp) (void *)) {
elem_t* tmp;
tmp = malloc(sizeof(elem_t));
if ( tmp == NULL ) return -1;
tmp -> next = head;
tmp -> key = copyk(k);
tmp -> payload = copyp(p);
return 0;
}

questo perché non possiamo dereferenziare i puntatori di tipo void (non sto tentando di spiegare...semplicemente vi spiego il mio "pensiero" così da permettervi di correggermi là dove sbagliassi).

Bisogna quindi implementare la copyk e la copyp. La domanda è: come? prendono come argomento la sola chiave/informazione d'aggiungere, possibile che sia una cosa del tipo:

void *copyk (void* k) {

return k;

}

???

[shodan]

Dovresti chiarire se questa lista generica è pensata per essere specializzata con un tipo specifico di dato (es. tutti int, tutti char, tutti quel che è), oppure ogni singolo nodo può essere specializzato per un tipo di dato diverso.

Nel primo caso la cosa è banale.
La copyk (e le altre) sono puntatori a funzione (come si vede dalla dichiarazione) a cui devi fornire una specializzazione valida.
Ad esempio per una lista di int:

void* copy_key(void* p) {
    int *pi = (int*) p;
    int *new_value = malloc(sizeof(int));
    *new_value = *pi;
    return (void*) new_value;
}

int compare_element(void *a, void *b) {
    int* pa = (int*) a;
    int* pb = (int*) b;
    if ((*pa) == (*pb)) return 0;
    return -1;
}

void* copy_paylod(void *b) {
...
}

list_t * new_List(compare_element,copy_key,copy_paylod);

[Frank Lioty]

La prima che hai detto. Solo non capisco una cosa: dovrei creare una funzione per ogni tipo possibile (char, int, float etc)? E come faccio a capire con che tipo sto lavorando?

EDIT: Se può essere d'aiuto qui c'è il link all'esercizio con la possibilità di scaricare il codice con commenti in doxygen

link

[shodan]

Originariamente inviato da Frank Lioty
dovrei creare una funzione per ogni tipo possibile (char, int, float etc)?

Si.

E come faccio a capire con che tipo sto lavorando?

Devi saperlo tu. Il compilatore non ti da nessun aiuto in caso di void*

[Frank Lioty]

Ah perfetto! Una cosa:

void* copy_key(void* p) {
    int *pi = (int*) p;
    int *new_value = malloc(sizeof(int));
    *new_value = *pi;
    return (void*) new_value;
}

perché ci si appoggia ad un nuovo puntatore (pi) e non si fa invece:

int *new_value = malloc(sizeof(int));
*new_value = (int*) p;

???

[shodan]

Il motivo è prettamente pratico e serve per evidenziare i vari passaggi da fare. Un pò come identare il codice: serve agli uomini, non al compilatore.

Comunque il passaggio che fai è sbagliato.
Con:

*new_value = (int*) p;

a sinistra dell'uguale hai un intero (il puntatore dereferenziato), a destra hai un puntatore a int (ottenuto tramite cast).
Devi usare un paio di parentesi in più.

*new_value = *( (int*) p );

[Frank Lioty]

sì, hai ragione, non avevo notato.

Ho provato ad implementare le altre funzioni:

int remove_ListElement(list_t * t,void * key) {

elem_t *key_element_prec;
elem_t *key_element;

key_element_prec = key_element = t->head;

/*primo elemento*/

  if (t->head->key == key) {

  t->head = t->head->next;
  /*dealloco memoria*/ 
  free(key_element);  
  return 0;

  }

/*altri elementi*/

while (key_element != NULL) {

key_element = key_element->next;

  if (key_element->key == key) {
  key_element_prec->next = key_element->next;
  free(key_element);
  return 0;
  }

key_element_prec = key_element;

}
return -1;
}

la free in questa maniera dealloca tutto correttamente? Inoltre leggevo da qualche parte che è consigliato settare a NULL quando si dealloca (facendo cioè un key_element = NULL dopo la chiamata alla free?), anche se non ho ben capito il motivo.

elem_t *find_ListElement(list_t *t, void* key) {

elem_t *current = t->head;

  while (current != NULL) {
 
  if (t->compare(current->key, key) == 0) return current;
  current = current->next;
  }

return NULL;
}

qui avrei un dubbio: non esiste un modo per creare una versione ricorsiva della find? Il mio problema è che tale funzione prende in ingresso la lista e non un elemento della lista, quindi non mi sarebbe stato possibile fare una cosa del tipo:

elem_t *find_ListElement(list_t *t, void* key) {

if (t->head == NULL ) return NULL;
if (compare(t->head ->key, key)==0) return t->head;
return find_ListElement(t->head->next , key);
}

proprio perché nel passo ricorsivo come primo parametro vuole un tipo list_t* piuttosto che un elem_t* . Devo necessariamente arrangiarmi con la versione iterativa? :master:

Mi resta da implementare la free e la new_list, con questi prototipi:

list_t * new_List(int (* compare) (void *, void *),void* (* copyk) (void *),void* (*copyp) (void*));

void free_List (list_t ** pt);

Avrei un paio di dubbi, giusto uno per ciascuna funzione :

1) perché la new_list prende come argomenti le funzioni compare, copyk e copyp? Nel momento in cui creo la lista di tipo list_t non dovrei comunque poter avere accesso alle 3 funzioni in quanto all'interno della struct di definizione?

2) perché la free prende in ingresso un puntatore ad un puntatore alla lista? Mi si ripresenta lo stesso problema della find. Avesse preso in ingresso un parametro elem_t*, potevo facilmente implementare questa versione ricorsiva (ammettendo pt il primo elemento della lista):

void free_List (elem_t* pt) {

if (pt == NULL) return;

elem_t* node = pt->next;
free(pt);
free_List(node);
}

Grazie mille per la pazienza

[Ippo343]

la free in questa maniera dealloca tutto correttamente? Inoltre leggevo da qualche parte che è consigliato settare a NULL quando si dealloca (facendo cioè un key_element = NULL dopo la chiamata alla free?), anche se non ho ben capito il motivo.
[/CODE]

Ad un'occhiata molto veloce mi sembra che deallochi tutto nel modo corretto.
Bisogna settare il puntatore a NULL per poterci richiamare free(): free(NULL) non va niente, free(ptr) va in crash se ptr punta ad un'area di memoria che è già stata deallocata.

[QUOTE
qui avrei un dubbio: non esiste un modo per creare una versione ricorsiva della find?
proprio perché nel passo ricorsivo come primo parametro vuole un tipo list_t* piuttosto che un elem_t* . Devo necessariamente arrangiarmi con la versione iterativa? :master:

Non serve, fai due funzioni:

elem_t* find_element(elem_t* ls, void* key, int (*cmp)(void*, void*));

list_t* find_ListElement(list_t* ls, void* key)
{
    return find_element(ls->head, key, compare);
}

In cui la seconda sulla lista ti fa da wrapper sulla prima.

1) perché la new_list prende come argomenti le funzioni compare, copyk e copyp? Nel momento in cui creo la lista di tipo list_t non dovrei comunque poter avere accesso alle 3 funzioni in quanto all'interno della struct di definizione?

Nella definizione della struct ci sono dei puntatori a funzione: quei puntatori però devi inizializzarli ad una vera funzione. Altrimenti, che codice potrebbero mai eseguire?
E' un po' come quando dichiari un puntatore ad un intero... poi dovrai pur inizializzarlo a qualche intero. Qui è la stessa cosa: dei puntatori a funzione vanno inizializzati per puntare ad una funzione.

2) perché la free prende in ingresso un puntatore ad un puntatore alla lista? Mi si ripresenta lo stesso problema della find. Avesse preso in ingresso un parametro elem_t*, potevo facilmente implementare questa versione ricorsiva (ammettendo pt il primo elemento della lista):

Il doppio puntatore serve per essere sicuri che venga inizializzato a NULL in modo da essere più sicuro:

void free_List(list_t** ls)
{
    procedura_che_elimina_la_lista( *ls ); //(*ls) è un list_t*
    (*ls) = NULL;    //ora il puntatore è a NULL e il programma non esplode se rifai una free
}

[Frank Lioty]

Originariamente inviato da Ippo343
Non serve, fai due funzioni:

elem_t* find_element(elem_t* ls, void* key, int (*cmp)(void*, void*));

list_t* find_ListElement(list_t* ls, void* key)
{
    return find_element(ls->head, key, compare);
}

In cui la seconda sulla lista ti fa da wrapper sulla prima.

Ah perfetto, me l'ero immaginata anch'io in questo modo. Pensavo ad una cosa però: in termini di costi computazionali, non risulta essere più efficiente la versione iterativa?

P.S: Che vuol dire che "fa da wrapper sulla prima"?

Nella definizione della struct ci sono dei puntatori a funzione: quei puntatori però devi inizializzarli ad una vera funzione. Altrimenti, che codice potrebbero mai eseguire?
E' un po' come quando dichiari un puntatore ad un intero... poi dovrai pur inizializzarlo a qualche intero. Qui è la stessa cosa: dei puntatori a funzione vanno inizializzati per puntare ad una funzione.

Che stupido che sono...per un qualche oscuro motivo pensavo che si inizializzassero "da sole" nel momento in cui dichiaravo le reali funzioni

Il doppio puntatore serve per essere sicuri che venga inizializzato a NULL in modo da essere più sicuro:

void free_List(list_t** ls)
{
    procedura_che_elimina_la_lista( *ls ); //(*ls) è un list_t*
    (*ls) = NULL;    //ora il puntatore è a NULL e il programma non esplode se rifai una free
}

Continuo a non capire, ma va beh, ti prendo sulla parola

P.S: Riguardo il metodo corretto per deallocare mi basta richiamare la free sul puntatore alla struct o devo deallocare anche singolarmente la key, il payload? Per le funzioni non c'è nulla da deallocare credo...

[Ippo343]

P.S: Che vuol dire che "fa da wrapper sulla prima"?

In effetti non sono proprio certo che sia un termine corretto in questo caso (al limite arriverà oregon e mi martellerà i ditini), comunque "wrapper" significa "involucro": in pratica questa funzione ti nasconde la presenza dell'altra, e ti da un modo di utilizzarla senza incorrere in errori.

Continuo a non capire, ma va beh, ti prendo sulla parola

Prova con un esperimento:

int x = 0;
int* ptr = &x;

free(ptr);
//ptr = NULL;
free(ptr);

Prova ad eseguirlo con e senza la riga commentata e vedrai cosa succede

P.S: Riguardo il metodo corretto per deallocare mi basta richiamare la free sul puntatore alla struct o devo deallocare anche singolarmente la key, il payload? Per le funzioni non c'è nulla da deallocare credo...

Hai ragione scusa, essendo dei puntatori devi deallocare anche key e payload: infatti tu liberi la memoria dedicata al puntatore, ma non la memoria puntata da questo puntatore.

Sinceramente non ho mai provato a deallocare una funzione... chissà cosa succede? Ora ci provo