single malloc for creating 2 structs

Question

I have a node with this structure:

struct node
{
    unsigned long key;
    unsigned long value;
    struct node* lChild;    
    struct node* rChild;   
};

I have a dummy node which has default values:

struct node* newSpecialNode()
{
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->key = 0;
    node->value = 0;
    node->lChild = NULL;
    node->rChild = NULL;
    return(node);
}

All nodes in my data structure will call this method to create a node.

struct node* newInternalNode(unsigned long key, unsigned long value)
{
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->key = key;
    node->value = value;
    node->lChild = newSpecialNode();
    node->rChild = newSpecialNode();
    return(node);
}

I call the function newSpecialNode() for left and right child. So there are two malloc calls. But whenever I create a node, I always create two dummy nodes. So I wanted to do a single malloc which allocates memory for both lChild and rChild. Possibly allocate a double word and reference its parts. But I do not know how to do it.

I tried this approach. But again I need to do two mallocs.

struct node** ptrToTwoNodes = (struct node**) malloc(2*sizeof(struct node*));
ptrToTwoNodes[0] = (struct node*) malloc(sizeof(struct node));
ptrToTwoNodes[1] = (struct node*) malloc(sizeof(struct node));

`struct node* ptrToTwoNodes = (struct node*) malloc(2*sizeof(struct node));`, `(ptrToTwoNodes)`, `(ptrToTwoNodes+1)` — BLUEPIXY, Mar 14 '14 at 09:41
One important thing to consider is that if you allocate multiple nodes in a single `malloc()` call, you'll need to free those nodes as a block. This might mean that you will have to keep track of which pointer is the one to be freed and only free the block when *all* of the pointers to it are no longer in use. If you need to be able to independently free `lChild` or `rChild` (or otherwise transfer ownership to other things that might hold pointers to a `node` probably), you should stick with separate `malloc()` calls. — Michael Burr, Mar 14 '14 at 09:55
Related: http://stackoverflow.com/questions/21475414/allocating-several-arrays-of-the-same-type. — michaelmeyer, Mar 14 '14 at 10:39

score 4 · Answer 1 · answered Mar 14 '14 at 09:51

4

While you technically can allocate all three nodes with a single malloc(), you really shouldn't because it breaks the recursive "symmetry" of the tree structure.

When calling malloc() three times, you get a tree where each node is independent of each other. That means you can change the tree later (adding and removing nodes) without having to worry how the child node was allocated.

The root of the problem is that you can't free() part of a memory segment returned my malloc(). You always have to call free() exactly once for each pointer returned by malloc() - no more and no less.

If malloc is too expensive for you, then an alternative is to create a set of helper functions that keep a pool of node structures (so they allocate N at once and then return one after the other until the pool runs out). See object pool pattern.

answered Mar 14 '14 at 09:51

Aaron Digulla

321,842
108
597
820

Great explanation!!thanks.. 3 Reasons why I'm trying to do a single malloc. 1.I'm not doing any GC. 2. I'm using it in a concurrent setting and havn't figured out a GC algorithm. 3.These special nodes will never change values and they will will get replaced only by another internal node – arunmoezhi Mar 14 '14 at 10:04
Re 3: If "replace" means for you "change the l/rChild pointer", then keep in mind that this will create (small) memory leaks. My current feeling is that you have an idea how to solve a problem but that idea is bad. Maybe if you told us what problem you're trying to solve, we could offer you better alternatives. – Aaron Digulla Mar 14 '14 at 12:23
Let us say, I create two mallocs (one for each child). When I "replace" a node (Yes I'm changing l/r child pointer), I still cannot release the memory of this replaced node. Reason being some other thread can still hold reference to it in a concurrent setting. So till I figure out a GC for my algorithm, I planned to go with this approach. – arunmoezhi Mar 14 '14 at 20:02

score 1 · Accepted Answer · answered Mar 14 '14 at 09:42

1

If you want to allocate a single block of memory for the two nodes, try

struct node* ptrToTwoNodes = (struct node*) malloc(2*sizeof(struct node));

then &ptrToTwoNodes[0] and &ptrToTwoNodes[1] will be pointers to your two nodes. BTW I guess you should remove C++ tag.

answered Mar 14 '14 at 09:42

Wojtek Surowka

20,535
4
44
51

Thanks. It worked. The idea is simple and it did not strike me :) Someone removed the `C++` tag for me – arunmoezhi Mar 14 '14 at 10:07

score 1 · Answer 3 · answered Mar 14 '14 at 09:43

1

You can allocate memory for 2 nodes, and assign the pointer to a variable:

struct node* ptrToTwoNodes = (struct node*) malloc(2*sizeof(struct node));
ptrToTwoNodes[0].value = ...;
ptrToTwoNodes[1].value = ...;

answered Mar 14 '14 at 09:43

MByD

135,866
28
264
277

score 1 · Answer 4 · answered Mar 14 '14 at 09:45

I am not sure what is your end result, but you can do it like:

struct node
{
    unsigned long key;
    unsigned long value;
    struct node* Child;    //allocate two 2 node sized blocks for it & access left-Child[0], right-Child[1]
};

And Initialize as:

struct node* newSpecialNode()
{
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->key = 0;
    node->value = 0;
    node->Child = NULL;
    return(node);
}

And then allocate like:

struct node* newInternalNode(unsigned long key, unsigned long value)
{
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->key = key;
    node->value = value;
    node->Child = malloc(sizeof(sruct node)*2); //Child[0] & Child[1] 
    return(node);
}

score 1 · Answer 5 · edited May 23 '17 at 12:13

1

Modify the code like follows:

struct node * newSpecialNode(void)
{
  struct node * node = malloc(2 * sizeof(*node));
  node->key = 0;
  node->value = 0;
  node->lChild = NULL;
  node->rChild = NULL;
  ++node;

  node->key = 0;
  node->value = 0;
  node->lChild = NULL;
  node->rChild = NULL;
  --node;

  return node;
}

struct node * newInternalNode(unsigned long key, unsigned long value)
{
  struct node * node = malloc(sizeof(*node));
  node->key = key;
  node->value = value;
  node->lChild = newSpecialNode();
  node->rChild = node->lChild + 1; 

  return node;
}

Take care on how to free() things.

Also add error checking to all those malloc()s.

Also^2: In C there is no need to cast the result of malloc(), nor is it recommended.

edited May 23 '17 at 12:13

Community

1
1

answered Mar 14 '14 at 09:50

alk

69,737
10
105
255

Do you mean I can safely replace `struct node * node = (struct node*) malloc(2 * sizeof(*node));` with `struct node * node = malloc(2 * sizeof(*node));` ? – arunmoezhi Mar 14 '14 at 10:06
@arunmoezhi: In C you should, yes. – alk Mar 14 '14 at 10:07
will removing the typecasting improve performance? Practically I wont see any considerable change. But theoretically will it reduce the # of assembly instructions? – arunmoezhi Mar 14 '14 at 10:09
1

It will make your code safer, as the cast may easily hide bugs ... that's all. – alk Mar 14 '14 at 10:09

single malloc for creating 2 structs

5 Answers5