Bulk allocation and partial deallocation for tree data structures.

[Moritz Maxeiner via Digitalmars-d-learn]

On Tuesday, 4 July 2017 at 02:53:00 UTC, Filip Bystricky wrote:
> On Tuesday, 4 July 2017 at 01:56:11 UTC, Moritz Maxeiner wrote:
>> [...]
>
> 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).

Then you must adjust your acceptance parameters, because:
Eventually (down the parent Allocator call chain) you will have 
to get the memory from the operating system, and AFAIK they only 
support deallocating via pointers to the beginning of a 
previously allocated block; let PartiallyDeallocatableAllocator 
(PDA) be our Allocator implementation supporting partial 
deallocations via such a parent Allocator (Parent) that can only 
(de)allocate in whole blocks.
That means even if Parent collects garbage it will not be able to 
allocate memory from within a block previously allocated (by PDA 
calling Parent's allocate) until that (whole) block has been been 
deallocated in Parent, either explicitly (by PDA), or implicitly 
by being collected.
And since PDA will want to track deallocated subblocks and hand 
them out in its own `allocate`, bypassing Parent when feasible 
(otherwise what's the point of supporting partial deallocations 
if you can't reuse the freed memory), it will have to have 
pointers to these subblocks, i.e. even if Parent collects 
garbage, PDA will block the collection, anyway (live pointers 
into the block).

> 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).

I don't see how reallocate helps here, as you can only 
grow/shrink towards the end of a block, not the beginning (so you 
can only do mimick partial deallocations at the end of a block).

> In the meantime I realized that since a child node can only 
> [...]

Good to see that you found an easier solution :)