Can a data structure contain multiple type of elements?

Question

This program is a different approach over the same old singly linked list. Instead of creating a single structure and keeping the pointer of the next node of the same type as a member of the structure, I here used three different structures, and a plain long nextaddress member in each to point the address of the next node, because pointers also do the same.

Each node also has a int flag member as the first item of the structure, and the data part resides at the end of the structure because of its variable length.

The three structures are basic extension of the built-in types, long, double and char. While accessing the structures, I first casted the address of the node as an int *, which gives me access to the flag without fully typecasting the address to a definite structure from the three.

Then analyzing the flag, various operations are done.

So here's my question. Can it be called a valid linked list? And moreover, is it even a valid data structure?

Answer 1

It is fine to do this as long as you have a means to tell which type each node contains, like the flag variable.

It seems reasonable that you can assume that flag and nextaddress will be on the same struct offsets no matter which struct type you use. Although strictly speaking the C language does not guarantee this, I believe it will work in practice on any system out there.

However, you cannot assume that data is located at (uint8_t*)&my_struct + sizeof(int) + sizeof(long). This offset may vary between structues because of different alignment requirements.

A more serious concern is pointer aliasing. You cannot take a pointer struct* x and convert that to another pointer type struct* y. It will compile, but this is a violation of the type rules in C and invokes undefined behavior (unless both structs have exactly the same members). Standard-compliant compilers that use aggressive optimizations (like GCC) will not compile such code as expected. (What is the strict aliasing rule?)

To be on the safe side and to get better program design overall, I would recommend that you instead do this:

typedef struct node
{
  long   nextaddress;
  type_t type; // some enum
  void*  data;
} node_t;

Where data is allocated separately from a node. You get a chained linked list of sorts.

Answer 2

Your code has many problems, but only referring to your specific questions about structs

Standard C grants that you solution works

6.7.2.1 Structure and union specifiers

Sub chapter 15

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

^{Emphasis mine}

You should use gen_struct inside the other struct:this grants to respect the rule of "initial member".

struct gen_type {
    int flag;
    void *nextaddress;
};

struct node_type_int {
    struct gen_type header;
    long data;
};

struct node_type_real {
    struct gen_type header;
    double data;
};

struct node_type_char {
    struct gen_type header;
    char data;
};

As you can see I also changed type of nextaddress: is meant to be a pointer, so use a pointer.

Side note: do-i-cast-the-result-of-malloc

Answer 3

Nice. Out of the box, I liked different way of doing it! but ...

Considering memory alignments differences across don't you feel there could be issue with below code:

dataaddress = ((long)(&generic->nextaddress)) + sizeof(long);

Here you are assuming the data is stored continuously and hence calculating address of data by adding sizeof long to the address of next address. But this need not be the case always right?

Instead, I feel its better to typecast to the appropriate structure type after reading the flag value, and then read data.

Considering such challenges, though you are saving on some memory but adding some more processing. So though it looks like a valid linked list, implementation can be decided upon choice of memory vs processing.

Answer 4

Your code has at least two weak points:

1.) conversion between long and pointer and back. The C standard allows this only if the integer type can hold the necessary range, which may not be the case on architectures with 32-bit long integers and 64-bit pointers.

I am adding quotation from C11 standard, section 6.3.2.3 Pointers:

An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.67)

Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

67) The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment

2.) implementation supposes that fields in two different structures (where types of preceding fields match) are stored at the same place (offset) within the structure. Although this is true for most implementations, the standard guarantee this only if those two structures are part of a union.

Section 6.5.2.3 Structure and union members:

One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible. Tw o structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members.