Powiązana lista zawierająca inne powiązane listy i bezpłatne

Question

Mam ogólną implementację listy powiązanej ze strukturą węzła zawierającą void * do danych i strukturę listy zawierającą odniesienie do head. Teraz tutaj jest mój problem, węzeł na połączonej liście może zawierać odwołanie do innej połączonej listy poprzez jego pustkę *. Powoduje to wycieki pamięci, gdy uwalniam większą listę zawierającą mniejsze listy. Zastanawiam się, czy istnieje sposób sprawdzenia, czy void * wskazuje na inną listę, więc podążam za nią i uwalniam to samo lub do danych.

Czy mogę dodać klucz do początku mojej struktury magiczną liczbą, którą mogę sprawdzić, usuwając pustkę * i stwierdzając, że jest to lista?

EDYCJA: Dzwoniący nie wstawiają mniejszych list, które są wstawiane przez moje funkcje Nie chcę, aby wywołujący zajmował się zwalnianiem wielu list tylko tych, na których trzymają wskaźnik.

Answer 1

To pytanie naprawdę zależy od tego, czyim zadaniem jest uporządkowanie wpisów na liście. Jeśli twoja struktura jest odpowiedzialna za wyczyszczenie pamięci, do której odnoszą się pola void *, masz tutaj znacznie większy problem, mianowicie, że biorąc pod uwagę void * odwołanie do jakiegoś dowolnego bloku pamięci, nigdy nie wiesz, jaki jest właściwy sposób jego zwolnienia. . Na przykład, jeśli masz implementację dynamicznej tablicy wzdłuż linii C++ std::vector, to twoja void * może wskazywać na strukturę, która sama zawiera wskaźnik, a twoja lista będzie musiała wiedzieć, że musi zejść do tej struktury, aby rekurencyjnie uwalnia swój dynamicznie przydzielony blok. Opisywany przypadek, w którym przenikniesz listę zagnieżdżoną, jest tylko szczególnym przypadkiem tego bardziej ogólnego problemu.

Jeśli z drugiej strony lista nie jest odpowiedzialna za wyczyszczenie pamięci, do której odnosi się void *, która jest przechowywana, nie powinieneś w ogóle martwić się tym problemem.

Jeśli twoja lista ma semantykę własności i jest wymagana do wyczyszczenia pamięci dla elementów w niej przechowywanych, zdecydowanie odradzam ci używanie magicznej liczby do określenia, czy masz listę zagnieżdżoną. Raczej prawdopodobnie powinieneś dać klientowi wskaźnik funkcji zawierający procedurę deallokacji do uruchomienia na elementach wstawionych na listę. W ten sposób twój kod może wykorzystywać dostarczony przez użytkownika kod czyszczenia, aby upewnić się, że wszystkie elementy zapisane na liście zostały wyczyszczone.

Answer 2

Nie tylko Twój void* może wskazywać na listę. Może wskazywać na dowolną pamięć przydzielaną dynamicznie.

Sposób, w jaki GLib rozwiązuje ten problem, polega na tym, że osoba dzwoniąca jest odpowiedzialna za to, aby wszystko, co wskazywało na liście void *data, zostało zwolnione. Zobacz http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free.

Alternatywą (którą GLib zapewnia również) jest utworzenie funkcji, która przyjmuje wskaźnik funkcji i wywołuje ją na każdym void *data podczas jej przeglądania. Wyszukaj numer g_list_free_full.

Answer 3

Moja rada byłaby w miarę możliwości nieco uproszająca i wystarczy upewnić się, że jedna połączona lista zawiera tylko jeden typ obiektu.

Jeśli nie możesz tego zrobić, prawdopodobnie każdy z węzłów na liście będzie posiadał nie tylko niektóre dane, ale także wskaźnik do funkcji, która wie, jak prawidłowo zwolnić elementy tego typu. Nieuchronnie, dwa tygodnie po napisaniu specjalnego kodu dla połączonej listy, zdecydujesz, że potrzebujesz także innej magicznej liczby, aby móc trzymać dynamiczną tablicę itp.

Answer 4

Aby odpowiedzieć na pytanie, jaka jest mądrość "Jeśli dodaję kluczowi do początku mojej struktury magiczną liczbę, którą mogę sprawdzić, usuwając pustkę * i stwierdzam, że jest to lista?"

Tak, możesz może zrobić to, ale niewielu by to polecić. Po prostu być naprawdę na pewno, że "magia" wartość nie może ewentualnie wystąpić inaczej. To bardzo duże pytanie. Chcesz rozważyć, na co jeszcze możesz wskazywać i jakie wartości może on przyjąć, gdy jest reprezentowany jako niepodpisana liczba całkowita. Pamiętaj, że jeśli zdecydujesz, że jest to lista, zamierzasz ją uwolnić, a tym samym najprawdopodobniej nastąpi awaria i spalenie, jeśli się mylisz.

Najprostszym rozwiązaniem jest to, że jeśli trzeba węzła wiedzieć, że to wskazuje na liście dostarczyć flagę w węźle mówiąc tak.

Jeśli naprawdę chcesz lista posiadać odpowiedzialność za uwolnienie całej jego zawartości, trzeba więcej niż flagą, trzeba wiedzieć, jak to zrobić każdy wolny. To może być identyfikator lub coś w rodzaju wskaźnika do funkcji, która uwalnia jego zawartość.