Bulk allocation and partial deallocation for tree data structures.

[Filip Bystricky via Digitalmars-d-learn]

On Tuesday, 4 July 2017 at 01:56:11 UTC, Moritz Maxeiner wrote:
> On Monday, 3 July 2017 at 17:06:10 UTC, Ali Çehreli wrote:
>> On 07/02/2017 07:56 PM, Stefan Koch wrote:
>>> On Monday, 3 July 2017 at 02:51:49 UTC, Filip Bystricky wrote:
>>>> Anyone?
>>>
>>> The answer is no.
>>>
>>> Partial deallocation in an arbitrary fashion is not advisable.
>>>
>>> And there are no standard library mechanisms for it.
>>
>> Would it be possible to write a custom 
>> std.experimental.allocator that does this?
>
> Since the `deallocate` function an Allocator has to implement 
> takes a `void[]` (-> known size), it's possible:
> At deallocation the Allocator will have to check if the given 
> memory subblock lies within any of the previously allocated 
> memory blocks; if it does, it will have to "tear" the 
> to-be-deallocated memory subblock from within it, storing the 
> resulting prefix and suffix memory subblocks (both remain 
> allocated) and removing the original block. It will still have 
> to track those two subblocks as belonging together, though, 
> since it can only deallocate the original memory block back to 
> the parent allocator (another Allocator, or something else) 
> once both of these subblocks are no longer allocated. Obviously 
> this applies to further partial deallocations of subblocks 
> within subblocks.
> I tend to agree with Stefan that this is likely not sensible, 
> but if in doubt, benchmark for the specific use case.

Thanks for the responses!

Moritz, that is a good suggestion. However, in many cases it is 
unacceptable to have to prevent the whole block from being freed 
(especially if the memory is managed by a compacting gc). I think 
the feature would work better as an additional allocator 
primitive, which should be easy to implement for most allocators 
that support reallocate (e.g. bitmapped-block and free-list 
allocators).

In the meantime I realized that since a child node can only be 
freed after its parent is freed, I can allocate all 6 nodes in a 
single allocation, but in reverse order, (putting the leaf at the 
front and the root at the tail). That way, to free an ancestor, 
we just realloc the corresponding leaf's memory.