C same structure different size

Question

My question is related to this one : c define arrays in struct with different sizes

However, I do NOT want to use dynamic allocation (embedded target).

• Problem recap :

In C, I want to have two versions of the same structure, each one with a different size for its static arrays. Both the structures will be used by the same functions through pointer parameter.

    typedef struct {
        short isLarge;         //set 0 at initialization
        short array[SIZE_A];
        //more arrays
    } doc_t;

    typedef struct {
        short isLarge;         //set 1 at initialization
        short array[SIZE_B];
        //more arrays
    } doc_large_t;

    void function( doc_t* document ) {
        if ( document->isLarge ) {
             //change document into doc_large_t* [1]
        } 
        //common code for both doc_t and doc_large_t
    }

• Questions :

(1) The above description needs a way to dynamically cast the pointer doc_t* pointer to doc_large_t* document [1]. Is that possible ? How ?

(2) An other solution i came with is to have a common header data part for both structure, including not only the isLarge flag, but also the pointers to the following static arrays. How ugly is that ?

(3) Also, do you have a good trick or workarround I could use ?

EDIT :

• More context :

My application is a path finding on an embedded MCU.

I have geometrical objects, like polygons. Polygons can describe simple rectangular obstacles, as well as more complex shapes (such as the accessible area).

Complex polygons can have a huge amount of vertices, but are in small quantity. Simple polygons are very common.

Both will use the same algorithms. I know in advance which polygon will need more vertices.

What I am trying to do is to optimize working memory to make it fit into the MCU. (i.e. small shapes get small arrays; complex ones get large arrays)

Answer 1

Create the arrays globally and use a pointer pointig to the big or small array.

Answer 2

It's easy with malloc() or similar dynamic allocation methods. Just use a flexible array member:

typedef struct {
    short isLarge;         //set 0 at initialization
     .
     .
     .
    short array[SIZE_A];
    short largeArray[];
} doc_t;

To allocate a "small structure":

doc_t *small = malloc( sizeof( *small ) );
small->isLarge = 0;

To allocate a "large structure":

doc_t *large = malloc( sizeof( *large ) + ( SIZE_B - SIZE_A ) * sizeof( large->largeArray[ 0 ] );
large->isLarge = 1;

Note that you must keep the largeArray element last, which means that the array element must be next-to-last for this to work.

Depending on how you do your own allocation, this may or may not be applicable.

(It's also a bit of a hack, since it depends on being able to access data in largeArray by using an index of SIZE_A or greater on array. That's accessing an object outside its bounds...)

Answer 3

After the edit, I think the best thing you can do is to profile your needs defining max simple and complex polygons your target can manage and then declare a pool of simplex and common polygons, like:

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

#define MAX_COMPLEX 16
#define MAX_SIMPLE  16

uint16_t g_Simple_Poly_set[MAX_COMPLEX][SIZE_A];
uint16_t g_Complex_Poly_set[MAX_COMPLEX][SIZE_B];

uint16_t g_Simple_Poly_used = 0;
uint16_t g_Complex_Poly_used = 0;

struct poly
{
    bool     isLarge;
    uint16_t *vetexes;
};


bool create_poly_simple (struct poly *p)
{
    bool retVal = false; // default: not more space for poly

    if (g_Simple_Poly_used < MAX_SIMPLE)
    {
        p->isLarge = false;
        p->vetexes = &g_Simple_Poly_set[g_Simple_Poly_used][0];

        g_Simple_Poly_used++;

        retVal = true;
    }

    return retVal;
}

bool create_poly_compleX (struct poly *p)
{
    bool retVal = false; // default: not more space for poly

    if (g_Complex_Poly_used < MAX_COMPLEX)
    {
        p->isLarge = true;
        p->vetexes = &g_Complex_Poly_set[g_Complex_Poly_used][0];

        g_Complex_Poly_used++;

        retVal = true;
    }

    return retVal;
}

void your_stuff_with_poly ( struct poly *p)
{
    uint32_t poly_size = (p->isLarge == false) ? SIZE_A : SIZE_B;

    // your stuff with the correct size
}

This is a simple implementation designed for a static "instantiation" of structs. You can also enhance the code with a create/destroy function that trace which array into pool is free to be used.

Answer 4

Your number 2 solution is the right idea. It's unclear to me why you think that is ugly. Maybe this beautiful implementation will change your mind.

You can implement single inheritance is C by placing the base structure as the first member of the inheriting structure. Then inheriting objects can be referenced with a pointer to the base type.

typedef struct {
    short doc_type;
    short *array_ptr;
    // more array pointers
} doc_base_t;

typedef struct {
    doc_base_t base;         // base.doc_type set 0 at initialization
    short array[SIZE_A];     // base.array_ptr initialized to point here
    //more arrays
} doc_small_t;

typedef struct {
    doc_base_t base;         // base.doc_type set 1 at initialization
    short array[SIZE_B];     // base.array_ptr initialized to point here
    //more arrays
} doc_large_t;

void function( doc_base_t* document ) {
    if ( document->doc_type == 1) {
         // array size is large
    } else {
         // array size is small
    }

    //common code referencing arrays through doc_base_t->array_ptr
}

The array_ptr member in doc_base_t isn't necessary for the inheritance mechanism. But I added that specifically for the "common code" portion of your function. If doc_base_t didn't include the array_ptr then you could cast the generic document to either adoc_small_t or doc_large_t type based upon the base_type value. But then you might need a different implementation for each inherited type. By adding the array_ptr member to doc_base_t I suspect you could write a common implementation for all inherited types.

So you will statically declare all your instances of doc_small_t and doc_large_t. And you'll initialize both the base.doc_type and base.array_ptr members when initializing each object. Then you will cast both types of objects to doc_base_t before calling function. (Or pass the address of the base member, which results in the same pointer value.)

Updated example:

static doc_small_t doc_small_instances[NUM_SMALL_INSTANCES];
static doc_large_t doc_large_instances[NUM_LARGE_INSTANCES];

// DocInit must be called once at startup to initialize all the instances.
void DocInit()
{
    int index;

    for (index = 0; index < NUM_SMALL_INSTANCES; index++)
    {
        doc_small_instances[index].base.doc_type = SMALL;
        doc_small_instances[index].base.array_ptr = doc_small_instances[index].array;
    }

    for (index = 0; index < NUM_LARGE_INSTANCES; index++)
    {
        doc_large_instances[index].base.doc_type = LARGE;
        doc_large_instances[index].base.array_ptr = doc_large_instances[index].array;
    }
}

// DocProcess processes one doc, large or small.
void DocProcess(doc_base_t *document)
{
    int index;
    short *array_member_ptr = document->array_ptr;

    int array_size = SMALL;
    if (document->doc_type == LARGE)
    {
        array_size = LARGE;
    }

    for (index = 0; index < array_size; index++)
    {
        // Application specific processing of *array_member_ptr goes here.

        array_member_ptr++;
    }
}

// ProcessAllDocs processes all large and small docs.
void ProcessAllDocs(void)
{
    int index;

    for (index = 0; index < NUM_SMALL_INSTANCES; index++)
    {
        DocProcess(&doc_small_instances[index].base);
    }

    for (index = 0; index < NUM_LARGE_INSTANCES; index++)
    {
        DocProcess(&doc_large_instances[index].base);
    }
}    

Answer 5

You should try to keep a single structure and for the different array sizes put them in an union. I don't know whether the following structure would make sense to your case.

    typedef struct {
        short isLarge;         //manually set to 0 or 1 after creating structure 
                               //and accordingly initialize the arrays in below union
        union my_varying_arrays {
            short array_A[SIZE_A];
            short array_B[SIZE_B];
        };
        //more arrays
    } doc_t;

If isLarge is 0, set the value for array_A array and if 1 set the value for array array_B.

Answer 6

Idea similar to what you mentioned in your question already (pointers to arrays), but with only one single pointer:

typedef struct
{
     short array[SIZE_B - SIZE_A];
     // more arrays alike...
} Extension;
typedef struct
{
    short array[SIZE_A];
    //more arrays (all the small ones!)
    Extension* extraData;
} doc_t;

If extraData is NULL, you have a small polygone, otherwise, you find the additional data in the struct referenced. Admitted, iterating over all values for large polygons gets a little nasty...

If you can use global arrays of predefined size for each object type (as Dominic Gibson proposed - a good proposition, by the way), you could spare the isLarge flag by replacing it with a function:

int isLarge(void* ptr)
{
    return
        (uintptr_t)globalLargeArray <= (uintptr_t)ptr
        &&
        (uintptr_t)ptr < (uintptr_t)globalLargeArray + sizeof(globalLargeArray);
}

Of course, all polygons (in above case: the large ones at least) would have to live in this array to make it work. If you create at least one dynamically or otherwise elsewhere (stack, another global variable) - we are out...