[fpc-pascal] about dynamic array -- PS

[Matthias K.]

2010/5/6 spir ☣ <denis.spir at gmail.com>:
> Hello,
>
> It seems the actual issue with static array is that the size is part the type. So that one cannot even use a pointer to refer to an array which size is supposed to change (since the pointer's type itself would be constrained by the size). Is this correct?
> If yes, how is it possible to build a "flexible" array type (in which on can add/remove elements) on top of static array?

It is possible but not as clean as using Dynamic Arrays (actually its
nearly the same but you need to do the work, the compiler would do for
you with dynamic arrays). The following Example uses a Static Array
such that the Compiler knows the Field Type.

---- Example:

type
  TMyTypedArray = array[ 0 .. High( Integer ) ] of SomeType;
  PMyTypedArray = ^TMyTypedArray;

  TMyDynArray = record
    len: Integer;
    data: Pointer;
  end;
  PMyDynArray = ^TMyDynArray;

..

procedure Init( var pda: PMyDynArray; len: Integer );
begin
  pda := New( PMyDynArray );
  pda^.len := len;
  GetMem( pda^.data, SizeOf( SomeType )*len ); // allocate array buffer
end;

function getElement( pda: PMyDynArray; index: Integer ): SomeType;
begin
  Assert( ( pda <> nil ) and ( index >= 0 ) and ( index < pda^.len ) );
  Result := PMyTypedArray( pda^.data )^[ index ];
end;

----

As you can see, this uses casting. Reallocation/Allocation/Deallocation
can be made with ReAllocMem/GetMem/FreeMem. It is possible to build a
Dynamic Array for a given Type (or a given Element size and more
casting) using own implementations for SetLength, index access (, and
boundary checks). Since (possibly relocated) array data is in the
pointer TMyDynArray.data, pointers to TMyDynArray can be used as Array
references.

The same thing is Possible using own address calculations on Pointers
without the static array type. Problem is, the deeper you go (or the
more low level using pointers and casts), the less readable/secure this
stuff gets.

But it is possible and nearly the same thing as using Dynamic Arrays.

>
> Also, a side-question: is resizing a flexible array more efficient than reallocating and copying a static one (provided the above issue is solved)?
> (I intend to do tests, but fpc's site seems to be down? I need info about timing funcs.)
Depends.. in general it is not as efficient. Reallocation sometimes
can be done more efficient by the OS or a Memory Manager. Worst case
needs a full copy, best case doesnt change anything (maybe because
theres free memory behind the array). Afaik DynArrays use ReAllocMem
too.

Matthias

PS: And never try to declare Variables as TMyTypedArray.. this will
simply crash your prog while trying to allocate (0 ..
High( Integer ))*SizeOf(SomeType) memory on the Stack. Its simply for
Compiler Information, such that Compiler can calcuate "pda^.data +
SizeOf(SomeType)*index" for "PMyTypedArray( pda^.data )^[ index ]"..