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

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

Answer 2

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

Answer 3

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 4

You can do this is the data is const by using a void * to the specific array. Then you just cast the void * to what you need it to be depending on the attributes in the structure.

It becomes more complicated when you need the structures in runtime. Especially on embedded targets.

typedef struct {
    short size;
    void *array;
} doc_t;

Where array points to a memory block allocated by the memory manager.

You now have to decide whether to use C standard malloc or use some pooled memory system based on the largest block size. An example would be ChibiOS Memory pools. If you are allocating and freeing variable sized memory blocks at random you risk memory fragmentation.

If you allocate incrementally you don't have to worry about much about memory. Just create one large block and keep track of where you are. A bit like a stack.

Answer 5

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 6

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 7

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