Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm doing a small FastCGI application in C and I've created this template system to keep the design away from the code.

There's a binary tree containing all possible first characters, each node points to another binary tree containing all characters that can appear after it. Some nodes have the replacement, when they are reached it means that a match was found.

The template system will read the characters from the file and parse the tree at the same time, always favoring the longest match.

I would like to know how to improve efficiency and reduce complexity.

word_tree.h

#ifndef WORD_TREE_H
#define WORD_TREE_H

typedef enum {
    WT_SUCCESS, WT_ERROR, WT_DUPLICATE, WT_DONE //WT_DONE is for internal use only
} WT_Return;

typedef struct Word_Tree{
    struct Word_Tree *sequence;
    struct Word_Tree *smaller;
    struct Word_Tree *greater;
    const char *replacement;
    int c;
} Word_Tree;

void word_tree_init(Word_Tree **root);
void word_tree_delete(Word_Tree *root);

WT_Return word_tree_insert(Word_Tree **root, const char *word, const char *replacement);

const Word_Tree *word_tree_find(const Word_Tree *wt, int c);

#endif

word_tree.c

#include "word_tree.h"
#include <stdlib.h>

void word_tree_init(Word_Tree **root)
{
    *root = NULL;
}

static Word_Tree *word_tree_new(void)
{
    Word_Tree *wt = malloc(sizeof(Word_Tree));
    if(wt == NULL)
        return NULL;

    wt->sequence = NULL;
    wt->smaller = NULL;
    wt->greater = NULL;
    wt->replacement = NULL;
    wt->c = '\0';

    return wt;
}

void word_tree_delete(Word_Tree *root)
{
    if(root->sequence)
        word_tree_delete(root->sequence);

    if(root->smaller)
        word_tree_delete(root->smaller);

    if(root->greater)
        word_tree_delete(root->greater);

    free(root);
}

WT_Return word_tree_insert(Word_Tree **root, const char *word, const char *replacement)
{
    int comparison;

    //Signal that the replacement should be inserted
    if(*word == '\0')
        return WT_DONE;

    //If we are inserting, it's impossible to be a duplicate
    if(*root == NULL){
        if((*root = word_tree_new()) == NULL)
            return WT_ERROR;

        (*root)->c = *word;

        switch(word_tree_insert(&(*root)->sequence, word + 1, replacement)){
            case WT_DONE:
                (*root)->replacement = replacement;
                return WT_SUCCESS;

            case WT_ERROR:
                free(*root);
                *root = NULL;
                return WT_ERROR;
        }

        return WT_SUCCESS;
    }

    comparison = *word - (*root)->c;

    //Try to find the character
    if(comparison > 0){
        switch(word_tree_insert(&(*root)->greater, word, replacement)){
            case WT_DUPLICATE:
                return WT_DUPLICATE;

            case WT_ERROR:
                return WT_ERROR;

            case WT_SUCCESS:
                return WT_SUCCESS;

            case WT_DONE:
                if((*root)->replacement != NULL)
                    return WT_DUPLICATE;

                (*root)->replacement = replacement;
                return WT_SUCCESS;
        }
    }

    //Try to find the character
    if(comparison < 0){
        switch(word_tree_insert(&(*root)->smaller, word, replacement)){
            case WT_DUPLICATE:
                return WT_DUPLICATE;

            case WT_ERROR:
                return WT_ERROR;

            case WT_SUCCESS:
                return WT_SUCCESS;

            case WT_DONE:
                if((*root)->replacement != NULL)
                    return WT_DUPLICATE;

                (*root)->replacement = replacement;
                return WT_SUCCESS;
        }
    }

    //We found the character
    switch(word_tree_insert(&(*root)->sequence, word + 1, replacement)){
        case WT_DUPLICATE:
            return WT_DUPLICATE;

        case WT_ERROR:
            return WT_ERROR;

        case WT_SUCCESS:
            return WT_SUCCESS;

        case WT_DONE:
            if((*root)->replacement != NULL)
                return WT_DUPLICATE;

            (*root)->replacement = replacement;
            return WT_SUCCESS;
    }
}

const Word_Tree *word_tree_find(const Word_Tree *wt, int c)
{
    int comparison;

    while(wt){
        comparison = c - wt->c;

        if(comparison > 0)
            wt = wt->greater;

        else
        if(comparison < 0)
            wt = wt->smaller;

        else
            return wt;
    }

    return NULL;
}

template.h

#ifndef TEMPLATE_H
#define TEMPLATE_H

#include "return_codes.h"

#define MAX_VARIABLE_NAME_LENGTH 255

int template_show(const char *file_name, const char **variables, const char **contents);

#endif

template.c

#include "template.h"
#include "word_tree.h"
#include "fcgi_stdio.h"

int template_show(const char *file_name, const char **variables, const char **contents)
{
    char buffer[MAX_VARIABLE_NAME_LENGTH];
    int c, i = 0, last_replacement_position = 0;
    FILE *file;
    Word_Tree *tree;
    const Word_Tree *node, *last_replacement = NULL;

    //open file
    if((file = fopen(file_name, "rb")) == NULL)
        return ERROR;

    //create a word tree with all variables
    word_tree_init(&tree);
    while(*variables != NULL){
        if(word_tree_insert(&tree, *variables, *contents) == WT_ERROR){
            word_tree_delete(tree);
            fclose(file);
            return ERROR;
        }

        ++variables;
        ++contents;
    }

    //read characters and go through the word tree
    node = tree;
    while((c = fgetc(file)) != EOF){
        if((node = word_tree_find(node, c)) != NULL){
            buffer[i++] = c;
            if(node->replacement){
                last_replacement_position = i;
                last_replacement = node;
            }

            node = node->sequence;
        }

        else {
            buffer[i] = '\0';

            if(last_replacement)
                printf("%s%s",
                        last_replacement->replacement, 
                        buffer + last_replacement_position  );

            else
                printf("%s", buffer);

            putchar(c);

            i = 0;
            last_replacement = NULL;
            node = tree;
        }
    }

    if(last_replacement)
        printf("%s%s",
                last_replacement->replacement, 
                buffer + last_replacement_position  );

    else
        printf("%s", buffer);

    //clean up
    word_tree_delete(tree);
    fclose(file);

    return SUCCESS;
}
share|improve this question

1 Answer 1

up vote 6 down vote accepted

A couple notes:

  • This looks fishy to me:

    //Try to find the character
    if(comparison > 0){
        switch(word_tree_insert(&(*root)->greater, word, replacement)){
            case WT_DUPLICATE:
                return WT_DUPLICATE;
    
            case WT_ERROR:
                return WT_ERROR;
    
            case WT_SUCCESS:
                return WT_SUCCESS;
    
            case WT_DONE:
                if((*root)->replacement != NULL)
                    return WT_DUPLICATE;
    
                (*root)->replacement = replacement;
                return WT_SUCCESS;
        }
    }
    

    It seems like a very complex system when you mostly just return the case values (except for one specific value). Here is what I would do to clean it up (untested):

    //Try to find the character
    if(comparison > 0)
    {
        WT_Return val = word_tree_insert(&(*root)->greater, word, replacement);
        if(val != WT_DONE) return val;
        else
        {
            if((*root)->replacement) return WT_DUPLICATE;
            (*root)->replacement = replacement;
            return WT_SUCCESS;
        }
    }
    
  • You have a comment here:

    //If we are inserting, it's impossible to be a duplicate
    

    I think that you should be using assert() in this one situation to verify that, since it is used to check for situations that "can't happen" or are "impossible".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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