Pointer to an array of structs and getting memory - C

Question

A link is a pointer to a node

typedef struct node * link;

In main(), I have the following code (config->m is just some integer):

// array of pointers to structs
link heads[config->m]; 

// make memory for head nodes
for(i = 0; i < config->m; i++)
  heads[i] = malloc(sizeof(struct node));

The code works (which is great). But is there a way I can allocate config->m pieces of memory without the loop? I tried

link heads[config->m];
heads = malloc(sizeof(struct node) * config->m);

but my friendly neighborhood compiler tells me incompatible types in assignment

I know I could use

struct node heads[config->m];

But I want to do this stuff with pointers.

And as always, someone will ask me if this is part of homework, and the answer is yes (sort of). But this particular chunk of code doesn't have anything to do with the actual assignment; it's for my own enlightenment. But thanks for asking :|

Answer 1

link heads[config->m]; 
link buffer = malloc(sizeof(struct node) * config->m);

for(i = 0; i < config->m; i++)
  heads[i] = &buffer[i];

....
free(buffer);

On edit: Actually, you don't need heads. First, let's get rid of link, as (see comments in Cannonade's answer) it just confuses the issue.

Let's pretend that a struct node is a node in an intrusive linked list, and looks like this:

      struct node {
        int val;
        int filler[10]; // this is pure filler, to make node big
        struct node* next;
      };

Now we add our includes, and config->m:

  #include <stdio.h>
  #include <stdlib.h>
  // your config->m
  const int m = 10 ;

And in main() we print the sizeof a node:

  int main() {

     printf( "sizeof( struct node ) = %i\n", sizeof( struct node) );

Now we declare a pointer to node:

     // na is a node pointer
     struct node* na;

And malloc up m nodes. malloc returns the address of the array, whichis also the address of the first node in the array. We set na to the address malloc returned:

      na = malloc(sizeof(struct node) * m);

Now we will use na, a pointer, as if it were an array. This works because C defines array[offset] as *(array + offset * sizeof(element))

     int i;
     // we give the first node a val of zero
     na[0].val = 0;
     // and a null next pointer
     na[0].next = 0 ;

Now we'll walk up the rest of the array and set each node's next to the PREVIOUS node in the array:

     for(i = 1; i < m; i++) {
        na[i].val = i ;
        // na[ offset ] is *(na + offset)
        // we don't want to dereference, 
        // we want the address, so we use the 
        // address-of operator ("&")
        na[i].next = &na[ i - 1 ];
     }

Our head is the LAST node in the array na[ m - 1]. Each next in the list is the preceding node in the array. Again, we use the address-of operator if we want the pointer, instead of what's pointed to:

     struct node* current = &na[ m - 1 ];

We'll print the address of each node. It should be the address of its next node pointer + sizeof( struct node), because each node is the node after (in the array) its next in the list ( the list is the array "reversed").

We cast it to char* to get a result in bytes. If we don't cast, we get the result in units of truct node* (which should always be 1).

     while( current ) {
        printf( "val %i, address of current %p, ", current->val, current) ;
        printf( " address of current->next %p, ", current->next ) ;
        if( current->next ) {
           printf( " distance from next: ");
           printf( "in bytes %i, ", 
              ( (char*) current)  - (char*) current->next ) ;
           printf( " in struct nodes %i", current  - current->next ) ;
        }
        printf( "\n" );
        current = current->next;   
     }

     return 0;
  }

On my system, that gives this output:

  sizeof( struct node ) = 48
  val 9, address of current 0x804a1b8,  address of current->next 0x804a188,  distance from next: in bytes 48,  in struct nodes 1
  val 8, address of current 0x804a188,  address of current->next 0x804a158,  distance from next: in bytes 48,  in struct nodes 1
  val 7, address of current 0x804a158,  address of current->next 0x804a128,  distance from next: in bytes 48,  in struct nodes 1
  val 6, address of current 0x804a128,  address of current->next 0x804a0f8,  distance from next: in bytes 48,  in struct nodes 1
  val 5, address of current 0x804a0f8,  address of current->next 0x804a0c8,  distance from next: in bytes 48,  in struct nodes 1
  val 4, address of current 0x804a0c8,  address of current->next 0x804a098,  distance from next: in bytes 48,  in struct nodes 1
  val 3, address of current 0x804a098,  address of current->next 0x804a068,  distance from next: in bytes 48,  in struct nodes 1
  val 2, address of current 0x804a068,  address of current->next 0x804a038,  distance from next: in bytes 48,  in struct nodes 1
  val 1, address of current 0x804a038,  address of current->next 0x804a008,  distance from next: in bytes 48,  in struct nodes 1
  val 0, address of current 0x804a008,  address of current->next (nil),

Answer 2

Nope, you need the loop. Your heads array is essentially a two dimensional array. You need at least two allocations. The first is the array of pointers:

link * heads = (link*)malloc (config->m * sizeof (link));

The second is the memory that each member of the heads array points to:

link buf = (link)malloc(sizeof(struct node) * config->m);
for(i = 0; i < config->m; i++)
    heads[i] = &buf[i];

And then to de-allocate:

free(heads);
free(buf);