Dynamic Arrays as Stack and/or Queue

[Jonathan M Davis]

On Tuesday, October 8, 2019 2:42:22 PM MDT mipri via Digitalmars-d-learn 
wrote:
> On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis
>
> wrote:
> > The result of this is that code like
> >
> > stack.popBack();
> > stack ~= foo;
> > stack ~= bar;
> > stack.popBack();
> > stack ~= baz;
> >
> > will end up allocating all over the place. Every time you
> > append to the array after shrinking it, you're going to end up
> > with the GC allocating a new block of memory instead of
> > appending in place.
>
> Thanks as well! I thought the code I posted would only allocate
> when
> the array ran out of capacity. And I see how, even if that's
> worked
> around with assumeSafeAppend, it becomes a bad idea to define the
> stack functions against `ref T[]` as this makes it too easy for
> other
> code to slice the array and cause the bugs that assumeSafeAppend
> allows.

Technically, it only does allocate when it runs out of capacity. However, if
you do something like

arr = arr[0 .. $ - 1];

then arr.capacity will either be the length of the array or 0 (I don't
remember which off the top of my head), because the capacity is calculated
based on how much space is available after the end of the dynamic array. How
much space is available at the end of the memory block is irrelevant unless
the dynamic array includes the last element that any dynamic array has ever
had within that memory block. If it's at the end, and the capacity is
greater than the length of the array, then the array can expand in place (up
to the difference between the length and the capacity). But if there is no
extra room on the end, or if the current dynamic array is not at the end,
then the capacity will reflect that. The same goes if the dynamic array is
actually a slice of memory that wasn't allocated by the GC for dynamic
arrays. IIRC, a dynamic array which is a slice of malloc-ed memory will
always give a capacity of 0, but regardless of whether it's actually 0, it's
never more than the length of the dynamic array, because there is no extra
capacity to grow into, since the memory was not allocated by the GC for use
by a dynamic array.

All of the various dynamic array functions work the same regardless of what
kind of memory is backing the dynamic array. It's just that if the memory
wasn't allocated by the GC for dynamic arrays, then when you call the
dynamic array function or property, then the GC treats it the same as it
would treat a dynamic array that referred to the end of the block of memory
(and thus wouldn't have any extra capacity).

You should always be able to call capacity on a dynamic array and see
whether appending to would then result in a reallocation or not.

Either way, because assumeSafeAppend resets the metadata so that the dynamic
array it's given is considered to be the farthest dynamic array within the
block of memory, after calling assumeSafeAppend, capacity will reflect that.

- Jonathan M Davis