Distruzione dei nodi della lista collegata: distruggi anche l'oggetto?

5

Sto scrivendo un elenco collegato in C .

list.h

typedef struct list_struct * List; /* Defined in list.c */

List create_list();
void destroy_list(List list);

void list_add(List list, void * item);
void list_remove(List list, int is_target(void *));

... /* Other handy functions like 'list_size', etc. */

list.c

typedef struct node_struct
{
  void * item;
  struct node_struct * next;
} * Node;

typedef struct list_struct
{
  Node head;
  ... /* Other handy things like size, tail, etc. */
} List;

void list_remove(List list, int is_target(void *))
{
  ... /* Find target node to delete. */
  free(target->item);
  ... /* Update links. */
  free(target);
}

... /* Other functions definitions. */

list_remove : quando rimuovi un Node (è usato dietro le quinte in list.c ), devo ovviamente deallocarlo (usando free ). Tuttavia, prima di liberare Node , dovrei anche liberare l''elemento' che contiene?

My Take

Pro: Il vantaggio di liberare l'elemento è che un client che utilizza questa API non deve tenere traccia degli elementi che archivia in un 'elenco'. Inoltre, non avrebbe dovuto preoccuparsi di liberare l'oggetto da solo.

Contro: se il client desiderava utilizzare l'elemento dopo l'eliminazione del nodo, non può perché è stato distrutto. Ecco perché liberare l'oggetto potrebbe essere una cattiva idea.

Soluzione: modifica la funzione in void * list_remove(List list, int is_target(void *)) (nota che ora restituisce void * ). Restituisce l'oggetto nel nodo (il nodo stesso viene distrutto). Quindi, se il cliente decide che non ha bisogno dell'elemento, può semplicemente chiamare free(list_remove(my_list, homework_that_dog_ate("HW 5"))); . E, se vuole tenerlo, può Homework dog_food = list_remove(my_list, homework_that_dog_ate("HW 5")); .

La mia soluzione è buona? Se no, dov'è il problema? C'è un approccio migliore?

    
posta Fine Man 29.12.2017 - 02:38
fonte

3 risposte

14

In generale (e specialmente quando si scrive codice della libreria) si dovrebbe essere scoraggiati per liberare memoria che qualcun altro ha assegnato. Vale a dire, non si sa quale allocatore hanno usato per allocarlo in primo luogo. (Potrebbe essere in pila, dopo tutto!) Inoltre non sai se hanno bisogno di ulteriori distruzioni prima della deallocazione.

Detto questo, questo non vuol dire che questa regola non possa essere infranta in casi particolari, ma se devi romperla, assicurati di specificarla esplicitamente nella tua documentazione.

    
risposta data 29.12.2017 - 03:23
fonte
0

Un'altra opzione è quella di separare il trovare il nodo e rimuoverlo. Se si dispone di una funzione find_node() , il chiamante prima trova il nodo, quindi chiama semplicemente remove per portare il puntatore al nodo fuori dall'elenco. Se vogliono mantenere la cosa nella lista, tocca a loro farlo prima di chiamare remove. Ovviamente, questo metodo di rimozione è molto più veloce in una lista legata al duale piuttosto che in una lista concatenata.

    
risposta data 29.12.2017 - 03:25
fonte
0

Per le strutture dati generiche in C, ho spesso trovato utile richiedere una dimensione del tipo da passare in costruzione, come ad esempio l'adattamento del tuo esempio:

List create_list(int type_size);

A quel punto quando lo fai:

void list_add(List* list, const void* item);

Puoi allocare memoria per il nodo e l'elemento (che puoi fare separatamente o insieme usando una struttura a lunghezza variabile) usando type_size e memcpy per copiare il contenuto dell'oggetto nel nodo, non un puntatore ad esso.

Quando lo fai, hai allocato la memoria per il nodo / elemento internamente e puoi quindi liberare la memoria durante la rimozione del nodo senza il rischio di causare problemi confusi per il client. E mentre ciò comporta la copia di alcuni bit e dei byte qua e là, è piuttosto veloce a memcpy di dati, specialmente quando stai allocando la memoria per un nodo.

Altrimenti diventa difficile se il client alloca memoria per un elemento, copia superficiale un puntatore ad esso, quindi prova a liberare la memoria per il client anche se non hai allocato la memoria. Come giustamente fa notare user8734617 , questo può essere un comportamento indefinito quando si lavora oltre i limiti del modulo anche se il client ha usato malloc per allocare il suo elemento.

Anche come bonus laterale, se si usano le strutture a lunghezza variabile per allocare il nodo e la memoria degli elementi insieme in un blocco contiguo, l'elenco trasversale può diventare più cache-friendly con un pattern AoS quando si copia il contenuto dell'elemento nell'elenco piuttosto che puntare alla memoria allocata da qualche altra parte (ovunque il client lo abbia allocato).

Inoltre potrebbe aver appena assegnato l'elemento nello stack ea quel punto la memoria dell'elemento potrebbe essere liberata dallo stack prima che il nodo dell'elenco che lo memorizza sia stato rimosso. Questo è un altro motivo per favorire memcpying dei dati dell'elemento nella lista piuttosto che copiarli in modo superficiale. Assegnando e copiando la memoria da soli, è possibile assicurarsi che il puntatore dell'elemento rimanga convalidato all'interno dell'elenco per tutto il tempo in cui l'elemento rimane all'interno dell'elenco.

Modifica: tipi non banali

Per i tipi non POD che richiedono una logica di copia profonda o una distruzione non banale, anche memcpying dei loro contenuti non sarà sufficiente se il contenitore sopravvive alla loro durata. In tal caso, un'interfaccia molto generalizzata potrebbe essere così:

// Function signature to copy one element to another.
// Memory for 'dst' is allocated by the list.
typedef ListCopy(void* dst, const void* src);

// Function signature to destroy an element.
typedef ListDestroy(void* element);

// Creates a list storing types of the specified size.
// If 'copy' is specified, it will be invoked to copy
// elements to the list. Otherwise a 'memcpy' will be used.
// If 'destroy' is specified, it will be invoked prior
// to removing elements and freeing their memory.
List create_list(int type_size, ListCopy* copy, ListDestroy* destroy);

Questo trasformerà la tua lista in un "proprietario di risorse" anche per tipi definiti dall'utente che non possono essere copiati e distrutti banalmente. Il memcpy e l'omissione di un distruttore sono sufficienti per semplici tipi di dati vecchi, e se è tutto ciò che ti serve, puoi fare a meno di questi callback mentre continui a rendere il tuo elenco un "proprietario di risorse".

    
risposta data 18.01.2018 - 07:57
fonte

Leggi altre domande sui tag