Elenco collegato contenente altri elenchi concatenati e gratuito

Question

Ho un'implementazione di elenchi concatenati generici con una struttura di nodo contenente un void * ai dati e una struttura di elenchi che contiene un riferimento a capo. Ora ecco il mio problema: un nodo nell'elenco collegato può contenere un riferimento a un altro elenco collegato tramite il suo vuoto *. Ciò causa perdite di memoria quando liberare la lista più grande contenente elenchi più piccoli. Quindi mi chiedo se c'è un modo per verificare se il vuoto * sta puntando su un'altra lista, quindi seguo e libero anche questo o solo dati.

Se aggiungo una chiave all'inizio della mia struct un numero magico che posso controllare dereferenziando il vuoto * e capirlo è una lista?

MODIFICA: i chiamanti non inseriscono gli elenchi più piccoli inseriti dalle mie funzioni. Non voglio che i chiamanti si occupino di rifasare più elenchi solo quello a cui tengono un puntatore.

Answer 1

Questa domanda dipende molto dalla responsabilità di pulire le voci nell'elenco. Se la tua struttura è responsabile della pulizia della memoria a cui fanno riferimento i campi void *, allora hai un problema molto più grande qui, ovvero che dato un void * riferimento a qualche blocco arbitrario di memoria non puoi mai sapere quale sia il modo giusto per deallocarlo . Ad esempio, se hai un'implementazione di un array dinamico lungo le linee del C++ std::vector, allora il tuo void * potrebbe puntare a una struttura che contiene esso stesso un puntatore, e il tuo elenco dovrà sapere che deve scendere in quella struttura per liberare in modo ricorsivo il blocco assegnato in modo dinamico. Il caso che stai descrivendo, dove stai perdendo una lista annidata - è solo un caso speciale di questo problema più generale.

Se, d'altra parte, l'elenco non è responsabile della pulizia della memoria a cui fa riferimento lo void * s memorizza, quindi non dovresti preoccuparti di questo problema.

Se la tua lista ha semantica della proprietà ed è necessario per ripulire la memoria per gli elementi memorizzati in essa, ti sconsiglio vivamente di usare un numero magico per determinare se hai un elenco annidato. Piuttosto, dovresti probabilmente avere il client che ti fornisce un puntatore a funzione contenente una routine di deallocation da eseguire sugli elementi inseriti nell'elenco. In questo modo, il codice può utilizzare il codice di pulizia fornito dall'utente per garantire che tutti gli elementi memorizzati nell'elenco vengano ripuliti.

Answer 2

Non è solo che il tuo void* potrebbe puntare a un elenco. Potrebbe puntare a qualsiasi memoria allocata dinamicamente.

Il modo in cui GLib gestisce questo problema consiste nel dire che è responsabilità del chiamante assicurarsi che venga liberato qualsiasi elemento indicato dallo void *data di un elenco. Vedi http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free.

L'alternativa (che GLIB fornisce anche) è quella di creare una funzione che accetta un puntatore a funzione e lo chiama su ogni void *data mentre attraversa l'elenco. Cercare g_list_free_full.

Answer 3

Il mio consiglio sarebbe se possibile semplificare un po 'le cose, e semplicemente assicurare che una lista collegata detenga solo un tipo di oggetto.

Se non riesci a farlo, probabilmente ogni nodo nell'elenco contiene non solo alcuni dati, ma anche un puntatore a una funzione che sa come liberare correttamente gli elementi di quel tipo. Inevitabilmente, due settimane dopo aver scritto il tuo codice speciale per un elenco collegato, decidi che hai bisogno di un altro numero magico per poter tenere un array dinamico, ecc.

Answer 4

Per rispondere alla domanda su quale sia la saggezza di "Se aggiungo una chiave all'inizio della mia struttura un numero magico che posso verificare dereferenziando il vuoto * e capirlo è una lista?"

Sì, è possibile fare questo, ma pochi lo consiglierei. Basta essere davvero sicuro che il valore "magico" non possa eventualmente accadere diversamente. Questa è una domanda piuttosto grande. Si desidera considerare su quale altro si potrebbe puntare e quali valori potrebbe assumere quando rappresentato come qualcosa di simile a un numero intero senza segno. Ricorda che se decidi che si tratta di un elenco, lo libererai e quindi si bloccherà e brucerai se ti sbagli.

La soluzione più semplice ed efficace è che se si ha bisogno di un nodo per sapere che punta a un elenco, fornire un flag nel nodo che lo dice.

Se si desidera veramente che la lista abbia la responsabilità di liberare tutti i suoi contenuti, è necessario più di una bandiera, è necessario sapere come liberarli. Potrebbe essere un id o qualcosa come un puntatore alla funzione che libera il suo contenuto.