(B) Some Implementation Patterns

About Const Casts

Using a cast to remove a const qualifier is a sign for bad design. This is in particular true if you need to cast a const pointer into a non-const pointer. For that reason gcc provides an option -Wcast-qual that produces a warning in such a case. Note that with -Wall this option is not included (so -Wall actually does not turn on all warning flags). Consider for example this example:

session18/const/foo1.c 
1
2
3
4
5
6
7
8
9
#include <stdlib.h>

int
main(void)
{
    const int *p = malloc(sizeof(*p));

    free((int *)p);
}

It with -Wcast-qual you get a warning but it compiles without complains when you just use -Wall:

theon$ gcc -Wcast-qual foo1.c
foo1.c: In function 'main':
foo1.c:8:10: warning: cast discards 'const' qualifier from pointer target type [-Wcast-qual]
    8 |     free((int *)p);
      |          ^
theon$ gcc -Wall foo1.c
theon$ 

Because const casts are really a sign for bad design the option -Wcast-qual should be used. So maybe we should add it in the makefile to CPPFLAGS. And furthermore, we should even use -Werror so that any warning is treated as an error. Because the rule of thumb is that any warning will sooner or later lead to an error.

With that we could never use our class for expression trees in its current form. Because we have such a cast in the destructor. And actually, if we have a design flaw in the class then we anyway should put the code into the trash. However, the design flaw is in this case not in our class, it is in the standard library. The flaw is that free() expects a non-const pointer but it should expect a const pointer. Like kfree() in the Linux kernel and this post by Linus Torvalds on Why is the kfree() argument const basically makes clear why free() has a design flaw.

So that means we should put free() in the trash (or move to C++ and use new and delete where we do not have this flaw). This is not an option. So we have to make an exception. And that means we first have to apply a cast to a non-const pointer that does not raise a warning even if we use Wcast-qual. And this is how you can trick gcc to not do that (or how you state that it is in this case really ok):

session18/const/foo2.c 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#include <stdlib.h>
#include <stdint.h>

int
main(void)
{
    const int *p = malloc(sizeof(*p));

    free((int *)(uintptr_t)p);
}

Type uintptr_t is a unsigned integer type that is guaranteed to be capable to store an address. Converting the pointer first into this type and then into the required non-const pointer is therefore safe and will also bypasses the warning.

Now we get away with the cast even if we turn on more warning flags:

theon$ gcc -Wcast-qual foo2.c
theon$ gcc -Wall foo2.c
theon$ gcc -Wall -Wcast-qual -Wextra -pedantic -Werror foo2.c
theon$ 

By the way even in the last command not all warning flags are turned on. It is kind of a challenge to achieve that for gcc. You will always find another useful option when you read through the man page.

Pointers and Ownerships

When you deal with dynamically allocated memory in C or C++ it has to be clear who “owns” the allocated memory. Because this ownerships goes hand in hand with the responsibility to release the memory. In C++ one can use the class std::unique_ptr for having a pointer type that keeps track of the ownership without introducing any overhead (so no reference counting or, even worse, garbage collection is involved). In C the programmer manually has to keep track on ownership. And this requires conventions.

I just can guess, but the idea for having a non-const pointer as parameter for free() might have been such a conventions. Something like “the owner has a non-const pointer and others only have a const-pointer”. In my opinion this does not work or has would have the consequence that you can not use const-pointers where you want them.

In the C library GTK+ ownership is managed through the documentation not the type system. See for example in the documentation for function gtkactionbar_new() the description of the return value.

Required Changes

We should document that by calling the constructors the caller becomes the owner of the returned pointer:

1
2
3
4
5
// constructors: The caller becomes the owner of the returned expression tree.
struct Expr *newUnsignedLiteralExpr(uint64_t uint);
struct Expr *newUnaryExpr(enum ExprKind kind, const struct Expr *unary);
struct Expr *newBinaryExpr(enum ExprKind kind, const struct Expr *left,
                           const struct Expr *right);

The destructor deleteExpr() should have a const pointer as parameter.

1
2
// destrcutor
void deleteExpr(const struct Expr *expr);

In the implementation we should use a cast as above to remove the const qualifier:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// destrcutor
void
deleteExpr(const struct Expr *expr)
{
    assert(expr);
    assert(expr->kind >= EK_BINARY && expr->kind < EK_PRIMARY_END);

    if (expr->kind >= EK_BINARY && expr->kind < EK_BINARY_END) {
        deleteExpr(expr->binary.left);
        deleteExpr(expr->binary.right);
    } else if (expr->kind >= EK_UNARY && expr->kind < EK_UNARY_END) {
        deleteExpr(expr->unary);
    }
    free((struct Expr *)(uintptr_t)expr);
}

More on Traversing (Binary) Trees

In evalExpr(), printExprTree() and deleteExpr() a so called depth-first algorithm for traversing the expression tree. More precise:

  • In evalExpr() and deleteExpr() we implemented a post-order variant. For each node with child node we first visited all child nodes and then applied to the node some kind of operation (computing the value of the node or releasing its memory).

    In pseudo code the underlying pattern can be describes as follows: 

    1
2
3
4
5
6
7
8
9
    function visit_post(node)
    if (left(node)) then
        visit_post(left(node))
    end if
    if (right(node)) then
        visit_post(right(node))
    end if
    apply(node)
end function.

  • In printExprTree() we implemented a pre-order variant. We first applied the operation to the node (printing its representation) and then visited its child nodes.

    In pseudo code the underlying pattern can be describes as follows: 

    1
2
3
4
5
6
7
8
9
    function visit_pre(node)
    apply(node)
    if (left(node)) then
        visit(left(node))
    end if
    if (right(node)) then
        visit(right(node))
    end if
end function.

Both variants can be generalized for trees where a node can have arbitrary many child nodes. For binary trees there is another special case called inorder traversal where the pseudo code reads as follows:

1
2
3
4
5
6
7
8
9
function visit_pre(node)
    if (left(node)) then
        visit(left(node))
    end if
    apply(node)
    if (right(node)) then
        visit(right(node))
    end if
end function.

This variant will be useful to generate a string representation of an expression tree. So we will come back to this later.

For completeness

In some applications any kind of depth-first traversal might not be the algorithm of your choice. For example, if the tree represents decisions that you can make for finding the shortest way out of a labyrinth. In such a scenario the tree can represent choices that you can make for subsequent moves. And then you want to visit nodes level by level. This would be a so called breadth-First traversal.

Have a look at 4 Types of Tree Traversal Algorithms for a more detailed introduction.

How to Print an Indent

With

1
printf("%*s", 42, "");

you can print an indent with 42 spaces. It is still a good idea to have in expr.c a dedicated function for printing the indent (and static function always can be inlined). But you can simplify printIndent to

1
2
3
4
5
static void
printIndent(size_t indent)
{
    printf("%*s", indent * 4, "");
}

Latex Package for Drawing Trees

There are lots of different packages for drawing graphs and trees. In the video the package forest was used which is based on PGF/TikZ

Such a picture of a tree can be generated for a textual description: every node and its child nodes to be enclosed in brackets. This is very similar to how we already printed tree structures in the last session. We just have to add the brackets at the right places. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 [ +
     [ *
         [ 2]
         [ 3]
     ]
     [ *
         [ 4]
         [ 5]
     ]
 ]

Examples with Complete Latex Code

In these examples the document class standalone is used, i.e. it will just generate the picture and not a complete article.

Minimalistic

This is what you basically get by just placing the brackets around the nodes (and some tiny little bit of Latex ocde before and after): 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
\documentclass[preview, margin=0.2cm]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest}
[ +
    [ *
        [ 2]
        [ 3]
    ]
    [ *
        [ 4]
        [ 5]
    ]
]
\end{forest}
\end{document}

Nodes with Circles

Of course you can use PGF/TikZ to add circles to each node: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
\documentclass[preview, margin=0.2cm]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest} 
for tree={draw,circle}
[ +
    [ *
        [ 2]
        [ 3]
    ]
    [ *
        [ 4]
        [ 5]
    ]
]
\end{forest}
\end{document}

Nodes with Circles and Fixed Angles

Here another example with circles and fixed angles (for small trees this sometimes looks nicer): 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
\documentclass[preview, margin=0.2cm]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest} 
for tree={draw,circle,calign=fixed edge angles}
[ +
    [ *
        [ 2]
        [ 3]
    ]
    [ *
        [ 4]
        [ 5]
    ]
]
\end{forest}
\end{document}