Zajištění platnosti ukazatele (v konkrétním návrhu)

[Solid.Sn]

Ahoj,

řeším vcelku jednoduchý problém:

- Mám acyklický graf - strom objektů. V tomto stromu lze přidávat/rušit objekty.
- Dále existují různé třídy, které objekty v uvedeném stromu používají různými způsoby (řekněme, že jde o moduly).
- Všechny tyto moduly mají společného předka.
- Moduly pracují tak, že se postupně cysklicky prochází a volá se jejich metoda pro zpracování, která nějak používá objekty ve stromu z prvního bodu.
- Mezi voláním metod zpracování jednotlivých modulů může dojít ke změně struktury stromu - třeba odstranění objektů (a zde nastává problém)


Problém nastává právě v situaci, když odeberu ze stromu některý z prvků (případně celou větev) a moduly nějakým způsobem onen odebíraný prvek používají (například ho mají nastaven pro svou práci jako aktivní prvek).

Destruktory objektů ve stromu mám napsané tak, aby vše uvolňovaly v rámci stromu, tedy pokud uvolním nejaký uzel, vše za ním se uvolní jak má.

Ještě bych ale potřeboval, aby moduly byly schopné identifikovat, že daný objekt, na který mají uložený ukazatel už prostě není platný.

Napadly mě tedy dva způsoby řešení:

1) Jelikož mají moduly společného předka, pak této třídě dopíšu statické metody a přidám "statický" seznam referencí na ukazatele na objekty ve stromu. Moduly, si následně budou "registrovat" použávané objekty pomocí těchto metod a v destruktoru objektů ve stromu se bude volat ještě nějaký kód, který projde veškeré používané objekty (v rámci těch registrovaných) a pokud bude ukazatel roven this, pak se ukazatel v tom seznamu vynuluje. Následně si pak modul může zkontrolovat, jestli je ten jeho ukazatel na zpracovávaný objekt stále platný (nenulový) a v případě že ne, bude dělat něco dalšího...

2) Způsob defakto stejný jako v předchozím případě, jen by se seznam neudržoval pro všechny moduly jeden (tedy i pro všechny objekty ze stromu jeden), ale byl by v rámci každého objektu zvlášť a "registrace" platných ukazatelů by se prováděla přímo k objektu, kterého se to týká. Tento objekt by v případě volání destruktoru jen prošel svůj seznam, ten by vynuloval a došlo by se ke stejnému řešení jako v předchozím bodu.

Zajímalo by mě, co si o těchto způsobech myslíte, případně pokud myslíte, že je to špatně pak jak by vypadalo Vaše řešení?

Děkuji

[josh]

<vtipdne>

drzel bych se v tomto pripade pravidla
O(n) jde zle fakturovat
O(logn) jde spatne fakturovat
O(1) se uz da vyborne fakturovat

</vtipdne>

Nerozumim na 100 % tvemu popisu reseni.

Pokud si nejaky objekt bude chtit zapamatovat ukazatel na uzel stromu, muze se zaregistrovat u toho uzlu, ze chce byt notifikovan u pri jeho uvolneni.
Tj. kazdy uzel ma seznam objektu, ktere na nej ukazuji.
Pri uvolneni uzlu (v destruktoru), informuju vsechny objekty ktere na nej ukazuji ze se uvolnuji a oni si nastavi pointer na uzel na NULL.

Jestli je to ta tvoje 2ka tak ok ne?
_________________
Tak Karle, kolik?

[mar]

No já už dlouho používám to, co popisuješ, tj. že objekt má množinu pointerů, co na něj ukazují (def. ve společném předkovi) a při zničení objektu se vynulují. Při změně pointeru se sám odebere ze seznamu a pak přidá do nového (pokud není null).

OT: Výhoda taky je, že takový pointer (template) může využít RTTI (C++ nebo vlastní) a např. nastavit se na null, pokud do něj přiřazuji objekt, co není odvozen od typu v template parametru.

Funguje to relativně dobře na heavyweight objekty a pokud se často pointery nemění. (často = n*1000 na frame).
Nevýhoda je samozřejmě výkon + paměť, navíc na pointer je potřeba speciální objekt/template.
Taky je potřeba si dát pozor, aby to překladač neoptimalizoval a při použití pointeru to znovu nahrál (že by si schoval pointer třeba do registru, pak by tam bylo volání, které smaže objekt a dál by se pracovalo s tím pointerem).
Výhoda je možnost mazat objekty přímo přes delete a změna se projeví hned. Navíc tenhle způsob řeší cross-reference narozdíl od reference countingu.

Pak taky můžeš zkusit reference counting, ale v tomhle případě to asi nebude ono.
Výhoda reference countingu je, že pointery můžou zůstat native, reference counting je rychlejší - O(1).
Nevýhoda je, že není možné přímo smazat nějaký objekt, snižím referenci (release), jenže ostatní pointery na ten objekt jsou pořád platné (tj. delete nelze). A poslední nevýhoda je, že cross reference znamenají automaticky leak.

[Tringi]

Co třeba něco alá mark&sweep?
Existuje-li v programu nějaký stabilní bod (např. konec snímku), pak není nic snazšího než přidat do uzlů bool příznak "to be deleted", nechat jednotlivé moduly místo samotného mazání jen nastavit tento příznak, a ve zmíněném stabilním bodě označené (kde si jsem jistý, že žádný modul není uprostřed stromu) uzly smazat.
_________________
WWW | GitHub | TW

[mar]

[OndraSej]

Solid.SN> bylo by lepší, kdybys popsal i co za problem se snažíš vyresit, ne jen jak ho resis.

Asi bych použil bud variantu 2, nebo nějakou kombinaci shared_ptr a označování, ze dany objekt je neaktivní.
_________________
http://trionteam.net