.[ ČeskéHry.cz ].
Zajištění platnosti ukazatele (v konkrétním návrhu)

 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
Solid.Sn



Založen: 08. 08. 2009
Příspěvky: 55

PříspěvekZaslal: 17. červenec 2012, 01:53:05    Předmět: Zajištění platnosti ukazatele (v konkrétním návrhu) Odpovědět s citátem

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
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
josh



Založen: 30. 07. 2007
Příspěvky: 74

PříspěvekZaslal: 17. červenec 2012, 06:51:48    Předmět: Odpovědět s citátem

<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 Smile

</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?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 535

PříspěvekZaslal: 17. červenec 2012, 08:48:50    Předmět: Odpovědět s citátem

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.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Tringi



Založen: 28. 07. 2007
Příspěvky: 283

PříspěvekZaslal: 17. červenec 2012, 09:09:35    Předmět: Odpovědět s citátem

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.
_________________
systems programmer
CV | WWW | FB | TW
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 535

PříspěvekZaslal: 17. červenec 2012, 09:19:28    Předmět: Odpovědět s citátem

Tringi napsal:
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.

To je fajn nápad, nicméně to neřeší nulování pointerů Wink
Leda mít seznam všech pointerů, ty si na konci framu projít a vynulovat je pro marked objekty. Samozřejmě by se musely projít všechny pointery, takže pokud budu mít 10 milionů pointerů (v praxi asi nereálné), tak se na konci každého framu lehce zapotím.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
OndraSej



Založen: 28. 07. 2007
Příspěvky: 757
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 17. červenec 2012, 10:31:47    Předmět: Odpovědět s citátem

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
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++ Časy uváděny v GMT + 1 hodina
Strana 1 z 1

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna