How to achieve encapsulation in C

Question

I'm not sure what I'm trying to do is called encapsulation, but this is the concept of OOP. I implement a binary tree and in particular the insert function:

typedef struct __node* tree; typedef struct __node { void* data; tree l,r; } node; typedef struct {int (*cmp)(void* a,void* b); tree root;} avl_tree; .... void tree_insert(tree node, tree* root, int (*cmp)(void* a,void* b)) { if (*root==NULL) { *root=node; return; } int c1 = cmp(node->data, (*root)->data); if (c1==-1) tree_insert(node, &((*root)->l), cmp); } tree tree_new_node(void*data){ tree a = malloc(...); ... return a; } void avl_insert(void* data, avl_tree* a) { tree_insert(tree_new_node(data), &(a->root), a->cmp); .... } 

The module should be used through the avl_insert function, which is pointed to the corresponding balanced avl_tree tree, which contains a pointer to an unprocessed tree, as well as a pointer to a comparator. Now it should obviously call tree insert , and tree_insert should have access to the comparator, as well as to the node that I am inserting now. The function works on a binary tree, so it is naturally recursive. However, if I give it a comparator and the current node as parameters, they will be passed with every recursive call that is not needed, since they will always be the same.

I would not want to do this. I could not come up with a clean and pleasant solution. Here are the options I could think of:

• Use the C ++ class and use the tree_insert function as a method of the avl_tree class. Then it will have access to the comparator using the this pointer. The problem with this solution is that I want to use C not C ++. In addition, it will not eliminate the passing of the current node parameter.

• Use static members inside a function (or global data). I am not sure that I can initialize them each time avl_insert called. In addition, this solution is not thread safe.

Now that I think about it, it is very simple to implement in a functional programming language. Interestingly, this is a fundamental problem with C, or I just don't know how to do this. What will be the cleanest way to achieve this?

Thanks!

---

After I thought about Victor Sorokin, I read about the this pointer, and it turns out that this is an implicit parameter in every call to the member function. Now when I think about it, this is the only logical solution. Each call to the tree_insert function must know the address of the structure in which it works. Even in a functional language, you could not escape this extra pointer ...

A possible solution would be to keep a pointer to the main tree structure in each node ..

So this is a fundamental "problem."

Answer 1

One interesting approach that can be used to achieve encapsulation is to look at the assembly code emitted by the C ++ compiler, and then translate it into the appropriate C code.

Another, more traditional, would be to use some library of C objects, such as GLib.

I think these two methods will give similar results :)

By the way, the first option that you mentioned is just as vulnerable to threading issues as the second. In C ++, there is no implicit thread safety.

The "OOP" C code that I saw in the Linux kernel (file system level) mainly refers to polymorphism, not encapsulation. Polymorphism is achieved by introducing a structure that lists possible operations (as pointers to functions). Then various "subclasses" are created, each of which initializes this structure with its own set of implementation methods.

Answer 2

You should be able to convert this tail recursion to iteration and generally avoid function calls. Sort of

 void tree_insert(tree node,tree*root,int (*cmp)(void*a,void*b)) { tree* current = root; while (*current != NULL) { int c1=cmp(node->data,(*current)->data); if(c1==-1)current = &((*current)->l); else current = &((*current)->r); } *current=node; } 

Answer 3

There is already a question covering my answer: What does “static” mean in program C?

---

You can roughly take the source C file as a class. The static keyword makes a variable or function only an internal relationship, which is similar to the private one in classical OOP.

foo.h

 #ifndef FOO_H #define FOO_H double publicStuff; double getter (void); void setter (double); int publicFunction (void); #endif 

foo.c

 #include "foo.h" static double privateStuff; static int privateFunction (void) { return privateStuff; } int publicFunction (void) { return privateFunction(); } double getter (void) { return privateStuff; } void setter (double foo) { privateStuff = foo; } 

main.c

 #include "foo.h" #include <stdio.h> static double privateStuff = 42; static int privateFunction (void) { return privateStuff; } int main (void) { publicStuff = 3.14; setter(publicStuff); printf("%g %d %d\n", getter(), publicFunction(), privateFunction()); return 0; }