From: ÒÝÁØ Ñî (yyl_20050115_at_[hidden])
Date: 2020-08-03 18:36:08
Let me try to explain how it works (in case you don¡¯t want to read the code or think, 150+ lines of code can do nothing).
Objects get linked together into a network.
Most of time, no need to be so complicated. However, language related or knowledge related projects
Are exceptions, which most of time I worked on them.
Circular-Reference is a tough problem even in Java or C# although they have GC, And GC has bad performance as we known.
Reference Counting is the most close to the final solution.
It¡¯s good enough to free trees, and near good to free graphs.
When we solve circular reference in graphs, we use DFS or BFS.
DFS requires implicit stack and BFS requires explicit stack.
Moving these concepts to C++¡¯s deleting objects, we can only use DFS.
Because the compiler did the work to free objects inside of objects in cascade.
But this is not enough. You can not delete your object in it¡¯s detor again if one object has its link
Back to itself. Or if in the case of shared_ptr, the shared_ptr object itself is in the content
Of the object it referenced. Therefore if you free the memory of the shared_ptr¡¯s containing
Object, the shared_ptr will be gone(so unable to decrease 1), if you free the shared_ptr¡¯s memory (so the shared_ptr¡¯s content is gone)
and the containing object will not be freed (refence count has 1 to be decreased).
So in either case, you can not decrease 1. And therefore one object referencing itself with shared_ptr can not be deleted
At correct time or even to the end(Same thing happens when other longer circular reference with objects¡¯ graph).
But if you let shared_ptr call it¡¯s referenced object¡¯s detor(can be dispose method) and the detor calls back to the shared_ptr¡¯s detor (or dispose)
The detor of shared_ptr can understand and just decrease count then return to the caller which is the referenced object¡¯s
detor(or dispose). And if we don¡¯t free memory instantly here, we get the count decreased correctly and content of either object or the reference intact.
And when every related object within this object as fields get reference decreased and if any decreased to zero,
They (objects) can be all put into the _wild (to be free) list which we can free them all together after this round.
This is the simplest situation that one object use shared_ptr to reference itself.
Things can go much complicated. However, you just don¡¯t free memory, and call every detor or dispose of the referenced objects
And according detors or dispose methods of shared_ptrs on one stage and free the object which has a reference count decreased to 0
on next stage, you just fix the conflict and solve the problem.
1. DFS (compiler generated code enforces this method) works in circle results in stack overflow can be solved by the control provided by detor or dispose method of shared_ptrs.
2. Detor calling stage and freeing stage are separated can make memory intact and the detors can be called multiple times to decrease count correctly.
With the correct decreased count, one object can be freed at the very right time, no need to do manual work, or use GC method to build object linkage
graph on the fly or try invalid pointers like GO¡¯s runtime does.
Yes, this method violates C++ specification if calling detors of shared_ptr pointed objects. But this is optional. You can still use common method
To call, maybe named dispose or disposing. Because the algorithm is not based on C++ undefined behavior. One defect is that you have to
Call the field¡¯s shared_ptr¡¯s dispose method manually inside of the dispose method of the container object which means, write more code.
This is why I don¡¯t like this solution. However if you insist in C++ specification, and don¡¯t want to add any syntax, this is the final solution
I can provide. The other defect is that something like std::string can not be put as field directly in some container wrapped with rcgc_shared_ptr,
Because they can not ensure correct freeing or destroying when detor¡¯s called for the second time. The solution for this is that we always
Use rcgc_shared_ptr on fields in side of the classes which would be wrapped by rcgc_shared_ptrs, or use simple pointers and protect
The pointer will be NULL checked. Either shared_ptr<A> or A*, just not A as field member of a class B (which will be wrapped with rcgc_shared_ptr<B>).
What I¡¯m talking about here is, reference counting aided method of automatic memory management is practical and the code of 150+ lines
already made it true. And the above is how it works ¨C I tried my best, but still feel limited in the vocabulary of English.
So, is this OK?
Again, thanks for pointing out the detor¡¯s abusing problem. As Andrey suggested, if put in a library, has to be the disposing way.
I accept the kindly suggestion.
And please see the point.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk