www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Dynamically Sized Structs

reply "Jeroen Bollen" <jbinero gmail.com> writes:
Is it possible to have a structure with a dynamic size? The 
structure would contain an array.

I know I can use templates, but the size won't be known at 
compile time. I also know I could just put a dynamic array into 
it, but that way it would just be a pointer.

I know there would be major issues like how to pass the struct to 
a function, as it has an unknown size, but to be quite honest I 
just want pretty code. I'm doing network related operations. I 
was hoping there'd still be a way to do this using templates or 
so? I just don't want to go through the hassle of writing a 
constructor for it to fill in all the fields, and a toByteArray 
method to convert it back to raw data.

struct MyStruct {
         ulong length;
         ubyte[length] data; // obv won't compile
}
Apr 16 2014
next sibling parent Justin Whear <justin economicmodeling.com> writes:
On Wed, 16 Apr 2014 23:15:40 +0000, Jeroen Bollen wrote:


 Is it possible to have a structure with a dynamic size? The structure
 would contain an array.
 
 I know I can use templates, but the size won't be known at compile time.
 I also know I could just put a dynamic array into it, but that way it
 would just be a pointer.
 
 I know there would be major issues like how to pass the struct to a
 function, as it has an unknown size, but to be quite honest I just want
 pretty code. I'm doing network related operations. I was hoping there'd
 still be a way to do this using templates or so? I just don't want to go
 through the hassle of writing a constructor for it to fill in all the
 fields, and a toByteArray method to convert it back to raw data.
 
 struct MyStruct {
          ulong length;
          ubyte[length] data; // obv won't compile
 }


No, you can't make the structs dynamic.  I had a similar situation 
reading shapefiles a while ago and approached it like this:

struct lengthOf
{
   string fieldName;
}

struct Polygon
{
   ulong numParts;
    lengthOf("numParts") Part[] parts;

   ulong numPoints;
    lengthOf("numPoints") Point[] points;
}

T read(T)(...)
    if (/** T is one of your wire-format structs **/)
{
    T ret;
    foreach (I, field; ret.tupleof)
    {
        static if (isDynamicArray!(typeof(field)))
        {
            // use __traits(getAttributes) on the field to get the 
lengthOf attribute
            // mixin a line like this:
            mixin(`field.length = ret.`~lengthOf.fieldName~`;`);
            rawRead(field);

        } else {
            // Assume the field is a primitive and read it
        }
    }
    return ret;
}

Can't find the actual code at the moment, but that's the gist of it.
Apr 16 2014
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jeroen Bollen:


 Is it possible to have a structure with a dynamic size?


See an usage example I have written here:
http://rosettacode.org/wiki/Sokoban#Faster_Version

But that code requires a very updated compiler. Otherwise you 
will need a little different code.

Bye,
bearophile
Apr 16 2014
next sibling parent reply "Dicebot" <public dicebot.lv> writes:
On Wednesday, 16 April 2014 at 23:36:05 UTC, bearophile wrote:

 Jeroen Bollen:


 Is it possible to have a structure with a dynamic size?


 See an usage example I have written here:
 http://rosettacode.org/wiki/Sokoban#Faster_Version

 But that code requires a very updated compiler. Otherwise you 
 will need a little different code.

 Bye,
 bearophile


Just in case, the key line to pay attention to in that example is 
this one:

CellIndex[0] c_;

It is a commonly used C idiom for dynamically sized structures 
that D also supports.
Apr 16 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 17 April 2014 at 00:55:19 UTC, Dicebot wrote:

 Just in case, the key line to pay attention to in that example 
 is this one:

 CellIndex[0] c_;

 It is a commonly used C idiom for dynamically sized structures 
 that D also supports.


Absolutely. However, from a technical point of view, it doesn't 
make the structure "dynamically sized". It is only a hack to 
access data past the end of the struct.

You still have to manually and dynamically allocate the struct:
auto p = cast(State*)malloc(blockSize * stateSize);

And accessing data is done via .ptr, to avoid out of bounds.

     CellIndex get(in size_t i) inout pure nothrow {
         return c_.ptr[i];
     }
Apr 16 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Dicebot:


 Just in case, the key line to pay attention to in that example 
 is this one:

 CellIndex[0] c_;


When you define dynamically sized structs it's also a good idea 
to wrap the items access with some kind of get/set functions, to 
make the code less bug-prone (and sometimes there is also a 
length available somewhere that those functions can use to verify 
the bounds in non-release builds).



 It is a commonly used C idiom for dynamically sized structures 
 that D also supports.


D supports zero length fixed size arrays for this usage too. And 
recently their .ptr was changed from null to their start addreess 
to improve this usage.

Bye,
bearophile
Apr 17 2014
parent reply "Kagamin" <spam here.lot> writes:
Bound checked version of variable size struct: 
http://dpaste.dzfl.pl/fcd91d6912d3
Apr 17 2014
next sibling parent "Kagamin" <spam here.lot> writes:
On Thursday, 17 April 2014 at 17:15:15 UTC, Kagamin wrote:

 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


Well, indexes getter could take cellCount into account...
Apr 17 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Kagamin:


 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


I think you are missing one of the main points of a variable 
sized struct, that is to reduce by 1 the number of indirection 
levels.

Bye,
bearophile
Apr 17 2014
next sibling parent "Dicebot" <public dicebot.lv> writes:
On Thursday, 17 April 2014 at 17:35:17 UTC, bearophile wrote:

 Kagamin:


 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


 I think you are missing one of the main points of a variable 
 sized struct, that is to reduce by 1 the number of indirection 
 levels.

 Bye,
 bearophile


Yeah, otherwise one could have just used dynamic array field.
Apr 17 2014
prev sibling parent reply "Kagamin" <spam here.lot> writes:
On Thursday, 17 April 2014 at 17:35:17 UTC, bearophile wrote:

 Kagamin:


 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


 I think you are missing one of the main points of a variable 
 sized struct, that is to reduce by 1 the number of indirection 
 levels.

 Bye,
 bearophile


As far as I can see, my implementation has only 1 indirection 
level.
Apr 17 2014
parent reply "Dicebot" <public dicebot.lv> writes:
On Thursday, 17 April 2014 at 17:45:22 UTC, Kagamin wrote:

 On Thursday, 17 April 2014 at 17:35:17 UTC, bearophile wrote:

 Kagamin:


 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


 I think you are missing one of the main points of a variable 
 sized struct, that is to reduce by 1 the number of indirection 
 levels.

 Bye,
 bearophile


 As far as I can see, my implementation has only 1 indirection 
 level.


And C-like dynamic structs have 0 indirection.
Apr 17 2014
next sibling parent reply "Kagamin" <spam here.lot> writes:
State* pointer in sokoban example is a perfect 1 indirection.
Apr 17 2014
parent reply "Dicebot" <public dicebot.lv> writes:
On Thursday, 17 April 2014 at 18:17:59 UTC, Kagamin wrote:

 State* pointer in sokoban example is a perfect 1 indirection.


It is not related to actual "dynamic struct" thing, which is why 
I have highlighted the line to look at. Minimal example is this:

struct Dynamic
{
     size_t length;
     int[0] payload;
}

void main()
{
     const length = 42;
     Dynamic* entity = alloca(Dynamic.sizeof + int.sizeof*length);
     entity.length = length;

     // pointer to same stack space so not really an indirection
     entity.payload[5] = 43;
}
Apr 17 2014
parent reply "Kagamin" <spam here.lot> writes:
How is this different from my example?
Apr 17 2014
parent reply "Dicebot" <public dicebot.lv> writes:
On Thursday, 17 April 2014 at 18:29:21 UTC, Kagamin wrote:

 How is this different from my example?


b = new byte[StateImpl.sizeof + CellIndex.sizeof*cellCount];

this line creates heap indirection
Apr 17 2014
parent reply "Kagamin" <spam here.lot> writes:
So you assert that variable length structs can't be allocated on 
heap and sokoban example is a wrong example of variable length 
struct usage?

And how heap indirection is different from stack indirection? 
It's still indirection.
Apr 17 2014
next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 17 April 2014 at 18:40:27 UTC, Kagamin wrote:

 And how heap indirection is different from stack indirection? 
 It's still indirection.


Locality. The stack is (within reason) readily available in cache.
Apr 17 2014
parent "Kagamin" <spam here.lot> writes:
Well, cache locality can be optimized without reducing number of 
indirections, as long as the data is likely to be in cache.
I agree with bearophile that variable size structs reduce number 
of indirections and have no direct relation to cache locality. 
One may have no time or no desire to initialize all the pointers 
or no place to put them.
Apr 17 2014
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 17 Apr 2014 14:40:25 -0400, Kagamin <spam here.lot> wrote:


 So you assert that variable length structs can't be allocated on heap  
 and sokoban example is a wrong example of variable length struct usage?

 And how heap indirection is different from stack indirection? It's still  
 indirection.


I think the biggest issue I would have with your implementation would be  
if I wrapped it in another struct that I wanted to store on the heap.

-Steve
Apr 17 2014
parent reply "Kagamin" <spam here.lot> writes:
Well, it's proof of concept of bound checked variable-size 
struct, I wrote it in a minute. It even compiles and runs.
Apr 17 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 18 Apr 2014 00:05:03 -0400, Kagamin <spam here.lot> wrote:


 Well, it's proof of concept of bound checked variable-size struct, I  
 wrote it in a minute. It even compiles and runs.


Please take no offense :) I just was pointing out a difference between a  
hand-managed and hand-written struct that I might have written and the one  
that you created. Depending on usage, yours might be sufficient.

Note, you could probably, with mixin magic, make a version that could be  
emplaced inside a struct or class without an extra indirection.

-Steve
Apr 18 2014
next sibling parent "Kagamin" <spam here.lot> writes:
I mean, it doesn't cover all scenarios, but can be extended to 
support them. The indexes array does just that: it's emplaced 
without indirection, but still is bound checked.
Apr 18 2014
prev sibling next sibling parent reply "Kagamin" <spam here.lot> writes:
Oh, and I don't believe, that a variable-size struct can be 
emplaced inside fixed-size struct or class. Only as a smart 
pointer from the example.
Apr 18 2014
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 18 Apr 2014 12:59:35 -0400, Kagamin <spam here.lot> wrote:


 Oh, and I don't believe, that a variable-size struct can be emplaced  
 inside fixed-size struct or class. Only as a smart pointer from the  
 example.


It goes at the end. Then you need to allocate the whole thing with that in  
mind.

-Steve
Apr 18 2014
prev sibling parent "Kagamin" <spam here.lot> writes:
On Friday, 18 April 2014 at 13:10:28 UTC, Steven Schveighoffer 
wrote:

 Note, you could probably, with mixin magic, make a version that 
 could be emplaced inside a struct or class without an extra 
 indirection.


Speaking about mixin magic, you probably suggest to do it overly 
generically, though it seems, use cases for variable size structs 
are specialized, specialized code and specialized data 
structures, so I suspect specialized approach will be more 
productive, intuitive, understandable, simple and straightforward 
for such tasks, generic approach is probably inadequate here. But 
if you can do it, you can try.
Apr 18 2014
prev sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 17 April 2014 at 17:50:30 UTC, Dicebot wrote:

 On Thursday, 17 April 2014 at 17:45:22 UTC, Kagamin wrote:

 On Thursday, 17 April 2014 at 17:35:17 UTC, bearophile wrote:

 Kagamin:


 Bound checked version of variable size struct: 
 http://dpaste.dzfl.pl/fcd91d6912d3


 I think you are missing one of the main points of a variable 
 sized struct, that is to reduce by 1 the number of 
 indirection levels.

 Bye,
 bearophile


 As far as I can see, my implementation has only 1 indirection 
 level.


 And C-like dynamic structs have 0 indirection.


Well, technically everything on the stack is accessed through an 
indirection (RBP + offset), but there are more optimisation 
opportunities if the base and/or offset is known statically. 
Performance-wise you're gaining nothing over a static array (or 
any alloca buffer) and potentially losing something compared to 
normal stack variables / struct members.
Apr 17 2014
prev sibling parent "Kagamin" <spam here.lot> writes:
On Wednesday, 16 April 2014 at 23:36:05 UTC, bearophile wrote:

 Jeroen Bollen:


 Is it possible to have a structure with a dynamic size?


 See an usage example I have written here:
 http://rosettacode.org/wiki/Sokoban#Faster_Version


This can illustrate
1. fairly straightforward translation of true C code to better C 
(bound checked D); such translation is important if one doesn't 
want to deeply refactor the debugged algorithm, but still 
reasonably gets bound checked code.
2. how easy is it to write such bound checked code.
3. developer doesn't need to design both safe and unsafe versions 
(as in C and C++, it can give better control of optimization, but 
is counterproductive, when you want to turn off safety globally), 
he writes safe code and gets unsafe one for free - with a 
compiler switch, and sees for himself, how big is performance 
trade-off - effortlessly, no work was spent on unsafe version, 
which can be another advertisement for D.
Apr 17 2014
prev sibling parent "Rene Zwanenburg" <renezwanenburg gmail.com> writes:
On Wednesday, 16 April 2014 at 23:15:43 UTC, Jeroen Bollen wrote:

 Is it possible to have a structure with a dynamic size? The 
 structure would contain an array.

 I know I can use templates, but the size won't be known at 
 compile time. I also know I could just put a dynamic array into 
 it, but that way it would just be a pointer.

 I know there would be major issues like how to pass the struct 
 to a function, as it has an unknown size, but to be quite 
 honest I just want pretty code. I'm doing network related 
 operations. I was hoping there'd still be a way to do this 
 using templates or so? I just don't want to go through the 
 hassle of writing a constructor for it to fill in all the 
 fields, and a toByteArray method to convert it back to raw data.

 struct MyStruct {
         ulong length;
         ubyte[length] data; // obv won't compile
 }


Dynamic structs are impossible with D's static type system. 
However I suspect vibe's BSON module [1] is pretty close to what 
you're looking for; it has a nice API and can easily be sent in 
binary form.

[1] http://vibed.org/api/vibe.data.bson/
Apr 16 2014