0

Suppose we have the following C snippet, implementing a tree data structure:

typedef struct node {
    char* data;
    struct node** children;
    unsigned int num_children;
} node;

Then we could create a leaf constructor that looks like the below,

node* make_leaf(char* data) {
    node* res = malloc(sizeof(*res));
    res->data = malloc(sizeof(*(res->data)) * strlen(data) + 1);
    strcpy(res->data, data); 

    res->children = NULL;
    res->num_children = 0;
}

Now suppose you have a few leaves, and you want to build them into a larger tree. You could do something like the following:

node *make_tree_1(char *data, unsigned int num_children, node *children) {
  node *res = malloc(sizeof(*res));
  res->data = malloc(sizeof(*(res->data)) * strlen(data) + 1);
  strcpy(res->data, data);

  res->num_children = num_children;
  res->children = malloc(sizeof(*(res->children)) * res->num_children);
  for (int i = 0; i < num_children; ++i) {
    *(res->children + i) = children + i;
  }
  return res;
}

void shallow_cleanup(node *nd) {
  free(nd->children);
  nd->children = NULL;
  free(nd->data);
  nd->data = NULL;
  free(nd);
  nd = NULL;
}

So users can create trees with make_tree_1 and for every such tree created with this function, there needs to be a corresponding call to shallow_cleanup. This feels natural, but has the property that editing a subtree will change the larger tree. Intuitively, this feels like a big onus to put on the user, to remember not to touch certain trees once they have been included in a larger tree. Conversely, this may be what the user wants. Of course, they could just clone the subtrees before passing them to make_tree_1, but this potentially just adds more line noise to your code. Additionally, if a user is building a large tree, then there will be a lot of corresponding calls to shallow_cleanup at the end of the function.

So another alternative is to clone the subtrees for the user, and do something like the following:

node *clone(node *nd) {
  node *res = malloc(sizeof(*res));
  res->data = malloc(sizeof(*(res->data)) * strlen(nd->data) + 1);
  strcpy(res->data, nd->data);

  res->num_children = nd->num_children;
  res->children = malloc(sizeof(*(res->children)) * res->num_children);
  res->children = NULL;
  for (unsigned int i = 0; i < nd->num_children; ++i) {
    *(res->children + i) = clone(nd->children + i);
  }

  return res;
}

node *make_tree_2(char *data, unsigned int num_children, node *children) {
  node *res = malloc(sizeof(*res));
  res->data = malloc(sizeof(*(res->data)) * strlen(data) + 1);
  strcpy(res->data, data);

  res->num_children = num_children;
  res->children = malloc(sizeof(*(res->children)) * res->num_children);
  for (unsigned int i = 0; i < num_children; ++i) {
    *(res->children + i) = clone(children + i);
  }
  return res;
}

void deep_cleanup(node *nd) {
  if (nd->num_children > 0) {
    for (int i = 0; i < nd->num_children; ++i) {
      deep_cleanup(*(nd->children + i));
    }
  }
  free(nd->children);
  nd->children = NULL;
  free(nd->data);
  nd->data = NULL;
  free(nd);
  nd = NULL;
}

To me, this seems even more natural - you can now chain calls without worrying about memory leaks, and you will probably need fewer cleanup calls at the end. But this could potentially invoke a massive memory overhead, as we are repeatedly copying everything.

Questions:

  1. Are either of these two ways outlined above idiomatic C? If not, why not? Is there a third way of doing things? What is most commonly found 'in the wild', when managing memory on custom data structures?

  2. In the second case, is the memory overhead 'worth it'?

  3. Is the idiomatic way of handling this language dependent? Would you copy in some languages and clone in others?

  4. What is the most friendly/natural of the above two options for end users?

I asked a philosophically similar question here, but I feel this (new) question is more oriented around design principles rather than details of C. I also appreciate that the above question may not be entirely well-formed, but I feel I'm in a position where I don't know what I don't know. Any help would be very much appreciated - thank you in advance.

1
  • A typical solution to this is to use reference counting (compare with C++'s std::unique_pr or std::shared_ptr, Rust's RC<T>, GObject's g_object_ref/g_object_unref). It has a secondary benefit, which is that you can implement Copy-on-Write. Since you know when a tree is uniquely referenced or shared, you can implement mutating operations to either work in place (when it's safe to do so), or to first clone and work on the clone. This allows you to share common subtrees safely
    – Alexander
    Feb 5 '21 at 1:30
0
  1. Are either of these two ways outlined above idiomatic C? If not, why not? Is there a third way of doing things? What is most commonly found 'in the wild', when managing memory on custom data structures?

I think it is pretty opinionated what "idiomatic C" means, so this is actually hard to answer. Some people would call code "idiomatic C" when it does all memory allocation manually, creates occasions for side effects and uses lots of unsafe pointers. You may check if this "definition" fits to the shown code, but I guess that is not what you had in mind. And I am sure, such code is often found "in the wild".

However, both shown approaches are valid and (probably) working code, and they are not overly complicated, so there is nothing "wrong" with them "per se". And yes, there are other approaches, see #3 below.

  1. In the second case, is the memory overhead 'worth it'?

This depends. Without any real problem to solve with such a tree, no context at all, this is not really answerable. There are problems where it is "worth", and others, where is it a waste of memory.

  1. Is the idiomatic way of handling this language dependent? Would you copy in some languages and clone in others?

In a programming language like Python, C# or Java where it is very easy to implement immutable data structures, or almost mandatory (like Haskell), one would neither copy nor clone the data of a partial tree, but simply set references - immutability will prevent side effects, either. These languages also take the burden from you to manage all the memory manually, the garbage collector will do the bookkeeping for you and know which memory has to released when it is not required any more.

I am sure such behaviour can be implemented in C as well. It would only be more effort. One would need to encapsulate the accessors to the structs in some module, to make them "read-only" after construction. Additionally, one needs to implement a more sophisticated memory management (for example by using reference counting).

  1. What is the most friendly/natural of the above two options for end users?

From the users side, both solutions provide the same API, so this is no criterion. Solution #1 uses less memory and may be faster, for the price of allowing more potential side effects. For several applications, the risk for side effects may be a showstopper, but there are also cases where one can live with this risk, and higher performance or less memory usage may be more important.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.