-1

I'm confused about how to access an array of structs.

simple case:

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
} node;

node *nodeArray = malloc(sizeof(node));    
nodeArray->number = 5;

So, that all makes sense. but the following doesn't work:

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
} node;

node *nodeArray = malloc(511 * sizeof(node));
for(int i = 0; i < 511; i++)
{
    nodeArray[i]->number = i;
}

However, nodeArray[i].number = i does seem to work can someone explain what's going on and also what's the difference between node *nodeArray = malloc(511 * sizeof(node)); and node (*nodeArray) = malloc(511 * sizeof(node));

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
DCR
  • 14,737
  • 12
  • 52
  • 115

3 Answers3

1

In the first snippet, the following are all equivalent:

nodeArray->number = 5;          // preferred
nodeArray[0].number = 5;
(*nodeArray).number = 5;

In the second snippet, the following are all equivalent:

(nodeArray + i)->number = i;
nodeArray[i].number = i;        // preferred
(*(nodeArray + i)).number = i;

So, as you can see, there is a choice of three different syntaxes that all do the same thing. The arrow syntax (nodeArray->number) is preferred when dealing with a pointer to a single instance of the struct. The array indexing with dot notation (nodeArray[i].number) is preferred when dealing with a pointer to an array of structs. The third syntax (dereferencing the pointer and dot notation) is avoided by sensible programmers.

user3386109
  • 34,287
  • 7
  • 49
  • 68
0

When you allocate an array like this

node* nodeArray = malloc(511*sizeof(node));

nodeArray is a pointer, getting a pointer to an individual struct node you just add an integer:

nodeArray + 1 would give a pointer to the second node

nodeArray + 1 can be written as &nodeArray[1]

so to dereference the pointer

*(nodeArray + 1).number or write nodeArray[1].number

AndersK
  • 35,813
  • 6
  • 60
  • 86
-1

May be the problem is caused by alignment:

Your node structure contains an integer and two pointers, its minimum storage size could be 12 bytes (on most 32-bit architectures) or 24 bytes (64-bit architectures) but the alignment constraints of the architecture may force each node to be aligned using another maximum storage size (with extra padding, which needs to be allocated too.

sizeof(type) just returns a minimum storage size (the extra allocated padding should not be accessible, even if this is not checked at runtime or by the compiler).

Solution: use calloc() which will also take into consideration the alignment constraints for each item in your array!

Replace:

node *nodeArray = malloc(511 * sizeof(node));

by:

node *nodeArray = calloc(511, sizeof(node));

and now your code is normally safe, the actually allocated size will include the necessary additional padding required by the underlying architecture.

Otherwise your code is not portable.

Note that some C/C++ compiler also provide a alignof(type) to get the correct alignment for the datatype (and it should be used for implementing void *calloc(size_t nitems, size_t size) in the C/C++ libraries).

Your sample code above may suffer from buffer overflows because you did not allocate enough space for the array before writing items in the loop.

You don't see the difference when you use simple types (you don't care about their alignment or where they are are isolately allocated, there's possibly extra padding allocated on the stack or in structures using them, which is not accessible, even if no padding is necessary when their storage is allocated inside physical registers; but even with "auto" or "register" allocation, the compiler may still allocate space on the stack for it, as a backing store that could be used to save the register when it is needed for something else or before performing an external function call, or method call in C++ and the function body is not inlined).

See the documentation of alignofand alignas declarators in C++11. There are many resources about them; for example:

https://en.cppreference.com/w/cpp/language/alignas

See as well the documentation of calloc()

(And don't be confused by the simplified 32-bit or 64-bit memory models used in Linux; even Linux uses now more precise memory models, taking into account alignment problems, as well as accessibility and performance problems, sometimes enforced by the underlying platform for good security reasons in order to reduce a surface of attacks that exists in the single/unified "flat" memory model for everything: segmented architectures are coming back in the computing industry, and C/C++ compilers had to adapt: C++11 replies to this problematic that otherwise would require costlier or inefficient solutions in the compiled code, severely limiting some optimizations such as cache management, efficiency of TLB stores, paging and virtualized memory, enforced security scopes for users/process/threads and so on).

Remember that each datatype has its own size and alignment and they are independent. The assumption that there's a single "size" to allocate for a datatype in an array is wrong (as well extra padding at end of the allocated array, after its last item, may not be allocated, and read/write access to padding areas may be restricted/enforced by the compiler or at runtime).

Now consider also the case of bitfields (datatypes declared as members of structures with an extra precision/size parameter): their sizeof() is not the true minimum as they can be packed more tightly (including arrays of booleans: sizeof() returns the minimum size of the datatype once it has been promoted to an integer and so when it has possibly been enlarged with extra padding or extension of the sign bit; usually the compiler enforces theses invalid accesses to padding bits by using bitmasking, shifts or rotations; but a processor may provide more convenient instructions to handle bits inside a word unit in memory or even in a register, so that your bitfields won't overflow and modify other surrounding bitfields or padding bits because of an arithmetic operation on their value).

As well your nodeArray[i] returns a reference to a node object, not a pointer, so nodeArray[i]->anything is invalid: you need to replace the -> by a ..

Philippe Verdy
  • 74
  • 3