How to avoid using two mallocs for both the node and the data(a string) of the node?

Question

struct treeNode {
    char *word;
    struct treeNode *left;
    struct treeNode *right;
    struct treeNode *father;

};
struct treeNode* new_node;
    new_node = (struct treeNode *) malloc(
            sizeof(struct treeNode));
    new_node->word= malloc(sizeof(char)*(k+1));

This is how i implement but i noticed that malloc is quite slow... Is there a way to use only one malloc to allocate space for both the node and the string?

Perhaps a [flexible array member](https://en.wikipedia.org/wiki/Flexible_array_member)? — Some programmer dude, Aug 23 '22 at 12:38
On another note, in C you [should not cast the result of `malloc`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858). — Some programmer dude, Aug 23 '22 at 12:39
How did you “notice” that `malloc` is slow? Is that really an issue in your program or just something you read somewhere? If it is just something you read somewhere, then ignore that for now. At this point in your studies, learn the basics of data structures, algorithms, and memory management. When the time comes that you need to make performance optimizations on the level of consolidating `malloc` calls, you will know how to do it. — Eric Postpischil, Aug 23 '22 at 12:42
If you are working on some online coding challenge, the cause of exceeding the time limit is more likely an inefficient algorithm rather than use of `malloc`. — Eric Postpischil, Aug 23 '22 at 12:58
Are you using a self-balancing tree structure (such as AVL tree or Red-Black tree) to deal with special cases such as being provided with already sorted input (which would effectively turn your tree into a linear list if it is not self-balancing)? — Ian Abbott, Aug 23 '22 at 17:00

chux - Reinstate Monica · Answer 1 · 2022-08-23T17:03:59.347

The usual alternative is a flexible array member FAM.

struct treeNode {
  struct treeNode *left;
  struct treeNode *right;
  struct treeNode *father;
  char word[];  // FAM
};

size_t k = strlen(word);
struct treeNode* new_node = malloc(sizeof new_node[0] +
    sizeof new_node->word[0] * (k+1));
if (new_node) {
  strcpy(new_node->word, word);
  ...

sizeof new_node[0] includes any padding that may exist just before the FAM member. Size does not include the FAM member itself.

I suspect this will only marginally improve speed performance, The real performance issue lies elsewhere.

How to avoid using two mallocs for both the node and the data(a string) of the node?

1 Answers1