5
\$\begingroup\$

Good morning, everyone.

I have developed a C library whose goal is to store strings in an easily searchable tree structure (which I have dubbed tree-dictionary). I come from a math background and I have been coding in Python for a few months, but I am a still a complete beginner to C and this is my first non-trivial project in the language. My goal was to learn the basics of C syntax, non-OOP programming, and hands-on memory management.

Here comes the code:

/**
 * @file treedict.h
 * @author
 * @brief Define a tree dictionary that stores words using a tree data structure.
 * 
 * The dictionary will only have three basic functionalities: it will be able to store a word, to check
 * if a word is in it, and, finally, to delete a word.
 * 
 * The dictionary is defined in three steps: first, define the nodes of the tree and the related functions.
 * Then, define the functions that work with the whole tree.
 * Finally, define the functions that use the tree as a dictionary.
 * 
 * Internally, each word is represented as a sequence of consecutive nodes originating at the root of the
 * tree. Each node contains a letter and the last letter is marked as an end-of-word node. 
 * A single node of the tree may contain a letter belonging to more than one word. The words are added
 * in such a way that the number of nodes is minimized.
 * 
 * Example: a dictionary that contains the words "ant", "antilope", "animal" and "animalistic" 
 * can be represented as follows:
 * 
 * a n
 *     i m a l E
 *             i s t i c E
 *     t E
 *       i l o p e E   
 * 
 * The root of a tree dictionary is supposed to be a node containing the null character '\0'.
 */

#ifndef TREEDICT_H
#define TREEDICT_H

#include <stdio.h>
#include <stdlib.h>
#include "bool.h"

/*********************************** NODE DEFINITION ****************************/

/**
 * @struct Node
 * @brief Datatype for the nodes of the tree.
 */
struct Node
{
    struct Node **children; /*< Array of pointers to the children of the node. */
    int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
    int number_of_children; /*< Number of children of the node. */

    char letter; /*< Letter represented by the node. */
    bool is_end_of_word; /*< Bool marking whether this is an end-of-word node or not. */
};
typedef struct Node Node;

/*********************************** NODE FUNCTIONS ****************************/

/**
 * @brief Initialize a new node instance.
 * 
 * @param letter 
 * Letter of the created node.
 * @return Node* 
 * Pointer to the created node.
 */
Node *create_node(char letter);

/**
 * @brief Free a node and its children array from memory. 
 * 
 * @param node
 */
void delete_node(Node *node);

/**
 * @brief Add child node to parent node.
 * 
 * @param child 
 * @param parent
 */
void add_child(Node *parent, Node *child);

/**
 * @brief Check if a node has children or not.
 * 
 * @param node 
 * @return true 
 * @return false 
 */
bool is_leaf(Node *node);

/**
 * @brief Reallocate children array of the given node to the be as long as the number of children.
 * 
 * @param node 
 */
void resize_children_array(Node *node);

/*********************************** TREE FUNCTIONS ****************************/

/**
 * @brief Free a whole tree from memory by freeing each node recursively, starting from the leaves.
 * 
 * @param root 
 * Pointer to the root of the tree.
 */
void delete_tree(Node *root);

/**
 * @brief Print a text representation of a tree to screen.
 * 
 * @param root 
 * Pointer to the root of the tree.
 */
void print_tree(Node *root);

/**
 * @brief Remove a whole branch recursively from its parent and free it from memory.
 * 
 * @param parent 
 * Pointer to the parent.
 * @param index_of_child 
 * parent->children[index_of_child] is supposed to point to the root of the branch that is to be deleted.
 */
void delete_branch(Node *parent, int index_of_child);

/*********************************** TREE DICTIONARY FUNCTIONS ****************************/

/**
 * @brief Add a word to a tree dictionary.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 */
void add_word(Node *dict, const char *word);

/**
 * @brief Check if a tree dictionary contains a word.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 * @return true 
 * @return false 
 */
bool contains_word(Node *dict, const char *word);

/**
 * @brief Delete a word from a tree dictionary.
 * 
 * @param dict 
 * Pointer to the root of the dictionary.
 * @param word 
 * Pointer to string representing the word.
 */
void delete_word(Node *dict, const char *word);

#endif

/**
 * @file treedict.c
 * @author
 * @brief Code for treedict.h.
 * 
 * 
 * 
 */
#include "treedict.h"

/*********************************** NODE DEFINITION ****************************/

/**
 * @brief Default length the the node.children array in a newly created node.
 */
static const int DEFAULT_LENGTH_OF_CHILDREN_ARRAY = 32;

/*********************************** NODE FUNCTIONS ****************************/

/* 
    Allocate memory for a new node instance and initialize its attributes before returning a pointer
    to the user. 
*/
Node *create_node(char letter) {
    Node *node = (Node *)calloc(1,sizeof(Node));

    node->children = (Node **)malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY*sizeof(Node*));
    node->length_of_children_array = DEFAULT_LENGTH_OF_CHILDREN_ARRAY;
    node->letter = letter;

    return node;
}

/*
    Free the children array of the given node from memory and then free the node itself.
*/
void delete_node(Node *node) {
    free(node->children);
    free(node);
}

/*
    Add a child node to a parent node. If the children array is full, reallocate it with twice its length. 
*/
void add_child(Node *parent, Node *child) {
    if (parent->number_of_children == parent->length_of_children_array) {
        parent->children = (Node **)realloc(parent->children, 2*parent->length_of_children_array*sizeof(Node *));
        parent->length_of_children_array *= 2;
    }

    parent->children[parent->number_of_children] = child;
    ++parent->number_of_children;
}

/*
    Check if a child is a leaf.
*/
bool is_leaf(Node *node) {
    return node->number_of_children == 0;
}

void resize_children_array(Node *node) {
    node->children = (Node **)realloc(node->children, node->number_of_children*sizeof(Node *));
    node->length_of_children_array = node->number_of_children;
}


/*********************************** TREE FUNCTIONS ****************************/

/*
    Recursively delete a whole tree.
*/
void delete_tree(Node *root) {
    int i;

    for (i = 0; i < root->number_of_children; i++)
        delete_tree(root->children[i]);

    delete_node(root);
}

/*
    If the child has any children, the branch of the tree starting with the child is
    recursively deleted and its memory is freed.
*/
void delete_branch(Node *parent, int index_of_child){
    int i;
    delete_tree(parent->children[index_of_child]);

    for(i = index_of_child; i < parent->number_of_children-1; i++)
        parent->children[i] = parent->children[i+1];

    parent->number_of_children--;
}

/* 
    Helper function that actually does the recursion for the print_tree function below.

    branch is a pointer that keeps track of the node of the tree we are at.
    depth tells us how deep we are in the tree.

    Represent the depth by printing an equal number of dots. Then, print the current letter. If
    we are at an end-of-word node, print E. Print a new-line.
    Finally, call print_branch at all the children of the current node with an incremented depth.
*/
void print_branch(Node* branch, int depth) {
    int i,j;

    for (j = 0; j < depth; j++)
        printf(".");

    if (branch->is_end_of_word)
        printf("%c E\n", branch->letter);
    else
        printf("%c\n", branch->letter);

    for (i = 0; i < branch->number_of_children; i++)
        print_branch(branch->children[i], depth+1);
}

void print_tree(Node *root) {
    print_branch(root, 0);
}


/*********************************** TREE DICTIONARY FUNCTIONS ****************************/

void add_word(Node *dict, const char *word) {
    /* i = string index, j = children index */
    int i = 0, j;
    bool matching_child_found;
    Node *current_node = dict;
    
    /* Travel along the branches of the dictionary to find the end of the longest
    prefix of word contained in the dictionary. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                current_node = current_node->children[j];
                matching_child_found = true;
                i++;
                break;
            }
        
        if (!matching_child_found) break;
        if (word[i] == '\0') break;
    }

    /* If we have found a child that matches the last character of the word, it suffices to
    mark it as an end-of-word character. Otherwise, if the last found character is not the last
    character of the word, add one node for each of the following characters and mark the last
    as an end-of-word character. */
    if (matching_child_found)
        current_node->is_end_of_word = true;
    else {
        Node *new_node;
        for (; word[i] != '\0'; i++) {
            new_node = create_node(word[i]);
            add_child(current_node, new_node);
            current_node = new_node;
        }
        current_node->is_end_of_word = true;
    }
}

/* 
    Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. If no matching child is found, return false. If a matching child
    is found for the last letter of word, check whether it is an end-of-word node.
    If it is, return true. If it isn't, return false.
*/
bool contains_word(Node *dict, const char *word){
    /* i = string index, j = children index */
    int i = 0, j;
    bool matching_child_found;
    Node *current_node = dict;
    
    /* Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                current_node = current_node->children[j];
                matching_child_found = true;
                i++;
                break;
            }
        
        /* If no mathing child is found word is no in the dictionary. */
        if (!matching_child_found) return false;
        /* If a node matching the last character of word is found, the word is in the dictionary
        if and only if the node is an end-of-word node. */
        if (word[i] == '\0') return current_node->is_end_of_word;
    }
}

/* 
     If no matching child is found, the word is not in the dictionary
    and thus we can return.
    
    If we find the node containing the last letter of word, if such node is marked as an end-of-word 
    node, and if such node has no children, we will deleted the entire branch with root node 
    "parent_of_branch_to_delete->children[index_of_branch_to_delte]", 
    as these nodes would become redundant.
    On the other hand, we find the node containing the last letter of word but the node has children,
    no node needs to be deleted and it suffices to set current_node->is_end_of_word = false.
*/
void delete_word(Node *dict, const char *word) {
    /* i = string index, j = children index */
    int i = 0, j, index_of_branch_to_delete;
    Node *current_node = dict, *parent_of_branch_to_delete = NULL;
    bool matching_child_found;

    /* Travel along the branches of the dictionary comparing the letter of each child of 
    current node to word[i]. */
    while (true) {
        matching_child_found = false;

        for (j = 0; j < current_node->number_of_children; j++)
            if ((current_node->children[j])->letter == word[i]) {
                /* Keep track of the last node encountered with more than 1 child and keep track of the index
                that the subsequent branch we travel along has in its children array (parent_of_branch_to_delete 
                and index_of_branch_to_delete) respectively. */
                if (current_node->number_of_children > 1) { 
                    parent_of_branch_to_delete = current_node;
                    index_of_branch_to_delete = j;
                }

                matching_child_found = true;
                current_node = current_node->children[j];
                i++;
                break;
            }

        /* If no matching child is found, we can return because the word is not 
        in the dictionary in the first place. */
        if (!matching_child_found) return;

        /* If a node containing the last character of the string is found, but it is not marked as
        an end_of_word node, the word is not in the dictionary and we can thus return. */
        if (word[i] == '\0' && !current_node->is_end_of_word) return;

        /* If a node containing the last character of the string is found and such node is marked as
        an end-of-word node, the word is in the dictionary and we can procced 
        break out of the loop and remove it. */
        if (word[i] == '\0' && current_node->is_end_of_word) break;
    }

    /* If current_node has children, it suffices to unmark it as an end-of-word node but no node
    needs to be deleted as every node we have iterated along is part of other words and is not redundant.
    If current_node has no children, the entire branch is sits on needs 
    to be remove at its last bifurcation. 
    */
    if (current_node->number_of_children > 0)
        current_node->is_end_of_word = false;
    else
        delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);
}

I have done some simple unit testing with words loaded from a .txt file and everything seems to be working fairly well, but I would appreciate it very much if someone more experienced than me could take a look at my code and confirm that I'm on the right path. My main concerns are:

  1. Although C is not geared towards OOP programming, I find it very hard not to think in terms of objects, methods and attributes. I know that OOP is not a language paradigm but a programming paradigm... still, I'm not sure whether this is the best approach to C programming. Does my code look like native C to you, or does it look like I am translating from Python to C in my head?
  2. Is my code memory safe? Am I leaking memory somewhere? I have written deleter functions both for trees and nodes and I have tried to have them handle garbage collection. Is this recommended? Have I used
  3. I have used a Doxygen extension for vscode to generate docstrings. Is this appropriate? Is my code readable? Is it good practice to put API documentation in .h files and implementation documentation in .c files?
  4. Does the way I have divided the code between treedict.h and treedict.c make sense? Am I putting header files and the preprocessor to good use?

I'm following the C89 standard. I know that C99 is a bit nicer (one-line comments and all...), but my school still uses C89 and I will be required to write assignments in C89 in the next few months, so I've decided to practice C89.

Thank you very munch in advance, and have a good day.

PS: bool.h just defines bool as an enum.

/**
 * @file bool.h
 * @author
 * @brief Custom definition for Boolean datatype.
 * 
 */
#ifndef BOOL_H
#define BOOL_H

typedef enum { false, true } bool;

#endif
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Can you include the test program and bool.h as well? How well did the test program fare under valgrind? \$\endgroup\$
    – Harith
    Feb 12 at 14:00
  • 3
    \$\begingroup\$ Re: I know that C99 is a bit nicer..." --> Note that we are currently on C17, and C23 is soon to be released. See: What is C23 and why should I care? \$\endgroup\$
    – Harith
    Feb 12 at 14:51
  • \$\begingroup\$ Thank you for letting me know @Harith. I had no idea that those standards existed. I will check the new features out as soon as I can. \$\endgroup\$ Feb 12 at 15:01
  • \$\begingroup\$ I heard about valgrind but I haven't been able to install it because I am on windows. I will look into getting a linux VM for it and post the results here (and the possible fixes, if necessary). \$\endgroup\$ Feb 12 at 15:06
  • 2
    \$\begingroup\$ Change your dictionary, if it contains antilope in place of antelope! ;) \$\endgroup\$ Feb 13 at 8:28

2 Answers 2

10
\$\begingroup\$

Hide the implementation:

Node should be an opaque data type defined in the source file. The header file would then only contain the forward declaration, and the prototypes for the APIs:

#ifndef TREEDICT_H
#define TREEDICT_H

#include <stdio.h>
#include <stdlib.h>
#include "bool.h"

/*********************************** NODE DEFINITION ****************************/

struct Node;

/*********************************** NODE FUNCTIONS ****************************/
...
Node *create_node(char letter);
...

and in the source file:

struct Node {
    struct Node **children; /*< Array of pointers to the children of the node. */
    int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
    int number_of_children; /*< Number of children of the node. */

    char letter; /*< Letter represented by the node. */
    bool is_end_of_word; /*< Bool marking whether this is an end-of-word node or not. */
};

See: What defines an opaque type in C, and when are they necessary and/or useful?

Do not cast the return of malloc() and family:

Starting with C89, malloc() and family returns a generic void * (as compared to the char * it originally used to) that is implicitly converted to any other pointer type (the cast is redundant, no need to clutter the codebase).

#if 0
Node *node = (Node *)calloc(1,sizeof(Node));
#else
// Take the size from the variable rather than its type to reduce the chance of a mismatch.
Node *const node = calloc(1, sizeof *node);
#endif

Side-note: Is there any specific reason you used calloc() for node but malloc() for node->children?

Check the return value of library functions:

If a function be advertised to return an error code in the event of difficulties, thou shalt check for that code, yea, even though the checks triple the size of thy code and produce aches in thy typing fingers, for if thou thinkest ''it cannot happen to me'', the gods shall surely punish thee for thy arrogance. - The Ten Commandments for C Programmers

According to the C17 standard:

The malloc function returns either a null pointer or a pointer to the allocated space.

Failing to check for it risks invoking undefined behavior by a subsequent null pointer dereference.

#if 0
    Node * node = (Node *)calloc(1,sizeof(Node));

    node->children = (Node **)malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY*sizeof(Node*));
#else
    Node *const node = calloc(1, sizeof *node);

    if (!node) {
        return NULL;
    }

    node->children = malloc(DEFAULT_LENGTH_OF_CHILDREN_ARRAY * sizeof node->children[0]);
    
    if (!node->children) {
        free(node);
        return NULL;
    }
    ...
}
#endif

Use braces around if/while/for statement et cetera:

I suggest always using:

if (current_node->number_of_children > 0) {
    current_node->is_end_of_word = false;
} else {
    delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);
}

to

if (current_node->number_of_children > 0)
    current_node->is_end_of_word = false;
else
    delete_branch(parent_of_branch_to_delete, index_of_branch_to_delete);

The problem with the second version is that if you go back and add a second statement to the if or else clause without adding the curly braces, your code will break. See: Apple's SSL/TLS bug.

Use size_t for sizes, cardinalities, and ordinal numbers:

int length_of_children_array; /*< Length of allocated children array 
                                    (NB: this is not the number of children, just the memory allocated for
                                    their pointers.) 
                                */
int number_of_children; /*< Number of children of the node. */

The length_of_children_array and number_of_children can not be negative. Consider using size_t or some other unsigned type.

Minor:

/*
    Free the children array of the given node from memory and then free the node itself.
*/
void delete_node(Node *node) {
    free(node->children);
    free(node);
}

I don't think this comment adds any value to the code. It is perfectly clear what delete_node() does. Consider removing it.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you very much for your priceless advice. I will fix the code tomorrow and post a link to the updated repository. \$\endgroup\$ Feb 12 at 15:09
  • 2
    \$\begingroup\$ You're welcome. Consider un-accepting the answer and waiting at least 2-3 days before accepting it again. You may get more and better reviews that way, and then you can cherry-pick which one you liked best from them. \$\endgroup\$
    – Harith
    Feb 12 at 15:17
  • \$\begingroup\$ Last minor point, I would say it's worth being explicit about whether children are handled or not, so the comment does actually add something. \$\endgroup\$
    – BurnsBA
    Feb 13 at 18:43
2
\$\begingroup\$

While the answer by Harith addresses very valid points, I feel that there is some repetition in this code that deserves to be eliminated. In particular, you see the following pattern arise a lot:

while (true) {
    matching_child_found = false;

    for (j = 0; j < current_node->number_of_children; j++)
        if ((current_node->children[j])->letter == word[i]) {
            current_node = current_node->children[j];
            matching_child_found = true;
            i++;
            break;
        }
    
    if (!matching_child_found) break;
    if (word[i] == '\0') break;
}

This could be simplified by extracting the common functionality of finding a child (inner loop), and following a path through the tree (outer loop). One way to achieve this could be for instance the following two helper functions (untested):

// Finds the child with letter `letter`
static Node* find_child(Node* node, char letter) {
    for (size_t i = 0; i < node->number_of_children; i++) {
        if (node->children[i]->letter == letter)
            return node->children[i];
    }
    return NULL;
}

// Traverses the tree from `node` using the path determined by `prefix`.
// Stops when the node has no child or when the end of the prefix has been found.
static void find_longest_prefix(Node** node, const char** prefix) {
    while (**prefix) {
        Node* child = find_child(*node, **prefix);
        if (!child)
            return;
        *node = child;
        *prefix = (*prefix) + 1;
    }
}

These can be static and remain private, if you want to keep these a detail of the implementation. Now, with those two functions, you can implement contains_word and add_word like this:

bool contains_word(Node* node, const char* word) {
    find_longest_prefix(&node, &word);
    return *word == 0 && node->is_end_of_word;
}

bool add_word(Node* node, const char* word) {
    find_longest_prefix(&node, &word);
    while (*word) {
        Node* child = create_child(*word);
        add_child(node, child);
        node = child;
        word++;
    }
    bool already_exists = node->is_end_of_word;
    node->is_end_of_word = true;
    return !already_exists;
}

I will leave rewriting the rest of the implementation using those helpers as an exercise.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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