| |||||||||||||
Zeuthen: Writing a C library, part 1Zeuthen: Writing a C library, part 1Posted Jul 3, 2011 8:14 UTC (Sun) by vlovich (guest, #63271)In reply to: Zeuthen: Writing a C library, part 1 by njs Parent article: Zeuthen: Writing a C library, part 1 I'm not understanding the claims that it takes anything other than O(n) in the worst case for a tree de-allocation.
function destroy_tree(tree) {
foreach child in tree
delete_tree(child)
free(tree)
}
(Log in to post comments)
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 11:35 UTC (Sun) by cladisch (✭ supporter ✭, #50193) [Link]
If a generic deletion function is used, it might rebalance the tree after each step.
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 18:35 UTC (Sun) by nix (subscriber, #2304) [Link]
When you're writing a tree deallocator, I'd expect it to have privileged access to the interior of the tree. There's no reason not to use a specialized high-speed node deletor in that case: rebalancing the tree between every deletion is silly, because it will never be accessed again. (Even a multithread-safe tree should probably block and warn on accesses once tree deallocation begins: any such accesses are racy and could easily access rubbish if they happened just an instant later.)
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 19:39 UTC (Sun) by vlovich (guest, #63271) [Link]
Rebalancing the tree would be enormously redundant - the extra 4-6 lines of really simple code is worth it (hell, if you're lazy, provide a boolean to the internal delete function that says whether or not to rebalance).
Thread-safety is irrelevant here - if you can access the tree after the destructor is already called, you've failed at thread safety (actually you've failed at maintaining the lifetime of the object properly).
Zeuthen: Writing a C library, part 1 Posted Jul 3, 2011 22:04 UTC (Sun) by nix (subscriber, #2304) [Link]
I think we are in violent agreement.
Zeuthen: Writing a C library, part 1 Posted Jul 6, 2011 15:56 UTC (Wed) by jwakely (subscriber, #60262) [Link]
I'm glad someone sensible agrees with the point I made way back in http://lwn.net/Articles/449645/ ... I was starting to think I was going mad and everyone else knew something about RB trees that I didn't
Zeuthen: Writing a C library, part 1 Posted Jul 6, 2011 16:56 UTC (Wed) by vlovich (guest, #63271) [Link]
Same here. I mean it's been a while since I took data structures. Maybe things have changed ;).
|
|||||||||||||