safe way of allocating memory for a list node

Question

In a simple list, ex :

struct Node {  
    Node *next;  
    void *data;  
}

is there any problem if i allocate Node and Data in a single allocation (provided i know the size), like

Node * t = (Node*)malloc(sizeof(Node) + DataSize));

and always assign data at the end of allocated chunk,

t->data = (BYTE*)t+ sizeof(Node); /* BYTE is byte length, can use char in gcc */

Node and data will get deleted in a sinlge go, so there no real problem tighlty coupling them (by design )

I am looking at Portability issues (specifically with Packing) or other unknown issues ?

Is this way of allocation safe and portable ?

Answer 1

You cannot use Node as a type until you create an alias. Use:

typedef struct Node {
   struct Node* n;
   void* data;
}Node;

No need to cast the result of malloc if you are going to stick to a C compiler. I find the following easier to maintain and read:

Node* t = malloc(sizeof *t + DataSize);

BYTE is not a standard type defined by the language and hence unportable. What does the following line try to accomplish?

t->data = (BYTE*)t+ sizeof(Node);

If you want to assign something, the following suffices:

t->data = pointer to some data ...

If you want to get the byte offset use offsetof macro.

Packing is implementation specific. You have to refer the appropriate compiler documentation and see what is available to you.

Additionally, you may want to have a head object that maintains some housekeeping information about the list (length etc).

Answer 2

As dirkgently said, don't case the return of malloc() in C, doing so is useless and can hide errors.

Also, to compute the address following the Node header, I find it cleaner to do it like this:

t->data = t + 1;

This works because t is a typed pointer, so arithmetic on it works fine. Adding one increments it by the size of the pointed-to data, i.e. sizeof (Node) in this case. I find this usage idiomatic for this particular case, of computing the address immediately following something just malloc()ed (when that "something" is a well-defined type with a statically known size, as the Node struct in this case, of course).

This has the following benefits:

• No repetition of the type name.
• No sizeof, so shorter.
• Again, no cast.
• Very simple arithmetic involved, easy to read.

I realized there's an error with your use of the Node type before it's properly declared, too. I don't agree with dirkgently's solution, here's how it should look, in C:

/* This introduces the type name "Node", as an alias for an undefined struct. */
typedef struct Node Node;

struct Node {
  Node *next; /* This is OK, the compiler only needs to know size of pointer. */
  void *data;
};

For completeness, and since I never tire of showing how I consider code like this should be written, here's an example of a function to create a new node to hold n bytes of data:

Node * node_new(size_t n)
{
  Node *node;

  if((node = malloc(sizeof *node + n)) != NULL)
  {
    node->next = NULL;
    node->data = node + 1;
  }
  return node;
}

That's it. Note use of sizeof on the pointer target in the malloc() call, to avoid repeating the type name and making an easy-to-forget dependency if the type should ever change.

Answer 3

Technically, it's could be unsafe if the data has alignment requirements. malloc() returns a pointer suitably aligned for all types, and it's likely that t+1 is also aligned. Likely, but not guaranteed.

Answer 4

I agree with @MSalters. As long as you have a level of indirection (the data pointer), you might as well do the proper thing and allocate a seperate block for it.

Now, an alternative would be using a flexible array member defined in C99:

typedef struct Node {
    struct Node *next;
    char data[];
} Node;

Node *n = malloc(sizeof(*n) + DataSize * sizeof(*data));
//if (n != NULL), access data[0 ~ DataSize-1]

sizeof(struct Node) is supplemented with an appropriate amount of padding (if any) such that the alignment requirements of data are met, and data[] acts as if it was declared as an array of the maximum possible size that would fit the memory block returned by malloc(). This goes for all types of data, not just char (hence the second sizeof).