7
\$\begingroup\$

For the past few weeks, I've been using the wonderful cJSON to add content to my game. But recently, I got tired of JSON's verbosity so I decided to roll my own format called SON (Simple Object Notation). I plan on using this format in all of my future game projects.

rogue
    anim
        timer 0
    brain
        type player
    image
        visibility visible
        texture rogue
        imagebox 0 0 24 40
        imageoff 0 -20
    player
    pos
        loc -30 85
        dir south
        solidity solid
kobold
    anim
        timer 0
    brain
        type monster
    image
        visibility visible
        texture kobold
        imagebox 0 0 24 40
        imageoff 0 -20
    pos
        loc 12 45
        dir south
        solidity solid

My parser is closely modeled after cJSON. I still have work to do (search by key, file writing, etc) but I'd like to get feedback on what I have so far. The three things I'm concerned about are:

  1. How is my coding style? I've only been using C for a few weeks and I'm still trying to find what works for me. I used to write C++ capitalization in Allman but I've recently switched to C-style capitalization and 1TBS.
  2. Is my file parsing efficient? This is my first time reading files in C and I struggled for several days figuring out the recursion part.
  3. How would approach writing my SON tree back to a file? What algorithms do I need to learn? I want my output to look like the input character-for-character.

sonparse.h

#pragma once

/* A node in a son file with accompanying value and relatives */
typedef struct son son;

struct son {
    char* key;
    son* child;
    son* next;

    enum { SON_NONE, SON_INTEGER, SON_STRING, SON_ARRAY } type;
    union {
        int integer;
        char* string;
        struct {
            int* data;
            int size;
        } array;
    };
};

/* Create a new node and set pointers to NULL. */
son* son_new(void);
/* Recursively free a node and all of its relatives. */
void son_del(son* node);
/* Parse a son tree from the given file path. */
son* son_parse(const char* filepath);
/* Print the node to console for debugging. */
void son_print(son* node);

sonparse.c

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

/* The file being parsed */
static FILE* file;
/* The character at the current file position. */
static char c;
/* Temporary node being returned to a higher recursion level. */
static son* temp_node;
/* The depth of the temporary node. */
static int temp_tab;

/* Read key at current file position into the node. */
static void read_key(son* node);
/* Read value at current file position into node. */
static void read_value(son* node);
/* Read array at current file position into node. */
static void read_array(son* node);
/* Read string at current file position into node. */
static void read_string(son* node);
/* Build a tree off of a node, setting pointers. */
static void build_tree(int this_tab, son* this_node);

son* son_new(void) {
    son* node = malloc(sizeof(son));
    node->child = NULL;
    node->next = NULL;
    return node;
}

void son_del(son* node) {
    if (node->type == SON_STRING) {
        free(node->string);
    } else if (node->type == SON_ARRAY) {
        free(node->array.data);
    }

    if (node->child) {
        son_del(node->child);
    }
    if (node->next) {
        son_del(node->next);
    }

    free(node->key);
    free(node);
}

son* son_parse(const char* filepath) {
    /*
        Example usage:
        son* tree = son_parse("entity.son");
        son_print(tree->next->child->next->next->child->next->next);
        son_del(tree);

        Output:
        imagebox : 0 0 24 40
        next: imageoff child: (null)
    */

    file = fopen(filepath, "r");
    son* root = son_new();
    read_key(root);
    read_value(root);
    build_tree(0, root);
    return root;
}

void son_print(son* node) {
    printf("%s", node->key);

    /* Print node value, or (null) if none. */
    char* valuestr = NULL;
    switch (node->type) {
    case SON_INTEGER:
        printf(" : %d\n", node->integer);
        break;
    case SON_ARRAY:
        printf(" :");
        for(int i = 0; i < node->array.size; ++i) {
            printf(" %d", node->array.data[i]);
        }
        putchar('\n');
        break;
    case SON_STRING:
        valuestr = node->string;
    case SON_NONE:
    default:
        printf(" : %s\n", valuestr);
        break;
    }

    /* Print node siblings, or (null) if none. */
    char* nextstr = NULL;
    char* childstr = NULL;
    if (node->next) {
        nextstr = node->next->key;
    }
    if (node->child) {
        childstr = node->child->key;
    }
    printf("next: %s child: %s\n", nextstr, childstr);
}

void read_key(son* node) {
    /* Read until a space or newline to get key length. */
    int key_start = ftell(file);
    int key_size = 0;
    c = getc(file);
    while(c && c != ' ' && c != '\n') {
        ++key_size;
        c = getc(file);
    }
    fseek(file, key_start, SEEK_SET);

    /* Allocate space for node key and null-terminator. */
    ++key_size;
    node->key = malloc(sizeof(char) * key_size);
    fread(node->key, sizeof(char), key_size, file);
    node->key[--key_size] = '\0';
}

void read_value(son* node) {
    /* Return if there is no value after key. */
    if (c != ' ') {
        node->type = SON_NONE;
        return;
    }

    c = getc(file);
    if (c == '-' || (c >= '0' && c <= '9')) {
        read_array(node);
    } else {
        read_string(node);
    }
}

void read_array(son* node) {
    int array_start = ftell(file) - 1;
    int array_size = 1;
    while (c && c != '\n') {
        if (c == ' ') {
            ++array_size;
        }
        c = getc(file);
    }
    fseek(file, array_start, SEEK_SET);

    if (array_size == 1) {
        node->type = SON_INTEGER;
        node->integer = 0;
        int sign = 1;
        c = getc(file);
        while (c && c != '\n') {
            if (c == '-') {
                sign = -1;
            } else {
                /* Add digit to integer */
                node->integer *= 10;
                node->integer += (c - '0') * sign;
            }
            c = getc(file);
        }
    } else {
        node->type = SON_ARRAY;
        node->array.size = array_size;
        node->array.data = malloc(sizeof(int) * array_size);
        node->array.data[0] = 0;
        int sign = 1;
        int i = 0;
        c = getc(file);
        while (c && c != '\n') {
            if (c == '-') {
                sign = -1;
            } else if (c == ' ') {
                ++i;
                sign = 1;
                node->array.data[i] = 0;
            } else {
                /* Add digit to current index. */
                node->array.data[i] *= 10;
                node->array.data[i] += (c - '0') * sign;
            }
            c = getc(file);
        }
    }
}

void read_string(son* node) {
    node->type = SON_STRING;
    int str_start = ftell(file) - 1;
    int str_size = 0;

    while(c != EOF && c != '\n') {
        ++str_size;
        c = getc(file);
    }
    fseek(file, str_start, SEEK_SET);

    /* Allocate space for node string and null-terminator. */
    ++str_size;
    node->string = malloc(sizeof(char) * str_size);
    fread(node->string, sizeof(char), str_size, file);
    node->string[--str_size] = '\0';
}

void build_tree(int this_tab, son* this_node) {
    /* Reached end of file, finish parsing. */
    if (c == EOF) {
        return;
    }

    /* Determine depth of node on next line. */
    int next_tab = 0;
    c = getc(file);
    while (c == '\t') {
        ++next_tab;
        c = getc(file);
    }
    ungetc(c, file);

    /* Create next node, determine if child or adjacent. */
    son* next_node = son_new();
    read_key(next_node);
    read_value(next_node);
    if (next_tab > this_tab) {
        this_node->child = next_node;
        build_tree(next_tab, next_node);

        /* Check if a node was returned to this depth. */
        if (temp_node && temp_tab == this_tab) {
            this_node->next = temp_node;
            temp_node = NULL;
            build_tree(temp_tab, this_node->next);
        }
    } else if (next_tab == this_tab) {
        this_node->next = next_node;
        build_tree(next_tab, next_node);
    } else {
        /* Return next node to previous depth. */
        temp_node = next_node;
        temp_tab = next_tab;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Interesting. The format seems fairly straight forward. I bet I could write a parser for this in javascript in a couple of hours. :D \$\endgroup\$ – Nolo Dec 10 '16 at 7:57
  • \$\begingroup\$ Consider using yaml instead of inventing yet another format. \$\endgroup\$ – 200_success Apr 7 '17 at 3:57
  • \$\begingroup\$ Tried yaml, couldn't find a good C parser. I'm aware of the potential issues with what I've done but I don't intend to share this format outside personal projects. \$\endgroup\$ – DragonDePlatino Apr 7 '17 at 6:47
5
\$\begingroup\$

Welcome to Code Review, nice first question. If you had more points I would suggest putting a bounty on the question to get more answers.

Possible Bugs

The first possible bug is in son_new(), key is not initialized to NULL. A good practice is to initialize all fields in an allocated structure, the previous value of the memory location is unknown.

The next possible bug is in son_parse(), the variable file is not checked to see if a it contains a valid file pointer. If fopen() fails the value of file will be NULL, and any use of the file pointer will result in a program crash. The Global Variable errno will provide an indication of why the call failed. The fread() and fwrite() functions can both fail.

Consider using intatoi(const char* string) rather than using the following code in read_array():

        c = getc(file);
        while (c && c != '\n') {
            if (c == '-') {
                sign = -1;
            } else if (c == ' ') {
                ++i;
                sign = 1;
                node->array.data[i] = 0;
            } else {
                /* Add digit to current index. */
                node->array.data[i] *= 10;
                node->array.data[i] += (c - '0') * sign;
            }
            c = getc(file);
        }

One possible bug in the preceding code is that it may try to convert non-numeric characters, there should at least be a check using isdigit(char c).

A Second possible bug in the preceding code is that the numeric value of the converted string may be larger than the word size on the computer running the program.

Coding Style

This question is somewhat subjective, you will usually get some comments or answers here on Code Review if the style is bad or can be improved. As long as you pick a coding convention such as camelCase or Capitalization and stick with it throughout the code you're doing good. Your indentation is already fine. Some people may have avoided answering the question because of the subjectivity of the question. If you are coding professionally the company or the department may have coding standards that you must use (it makes it easier for other developers to fix the code when you are on vacation or have gotten a better job).

Naming Conventions for Types, Functions and Variables

If the functions were more descriptively named, the need for comments would be greatly reduced. Comments are generally used to describe what the the algorithm is or why the specific algorithm was used. Using underscores in a name does differentiate the word in the name but can take up a lot more space. The Example Usage comment in son_parse is a good example of what a comment should be. The comment /* Check if a node was returned to this depth */ is also a good comment.

Examples:

  • The struct son might be better named son_node, or SonNode.
  • The son_new function might be better named son_new_node or SonNewNode.
  • The file variable in son_parse.c might be better named SonInputFile().

Typedef's

The code in son_parse.h could be made more readable in this manner:

typedef enum { SON_NONE, SON_INTEGER, SON_STRING, SON_ARRAY } SonType;

typedef struct son_node {
    char* key;
    son* child;
    son* next;

    SonType type;
    union {
        int integer;
        char* string;
        struct {
            int* data;
            int size;
        } array;
    };
} SonNode;

For more object oriented pointers to functions in the struct can be added. Some pointers to functions that might be added are:

  • AddChild()
  • DeleteChild()
  • AddNextNode()
  • DeleteNextNode()
  • WriteNodeToOutputFile()
  • PrintNode()

This would remove the necessity for the declarations of son_new(), son_del() and son_print() in son_parse.h

Debug Code

Embed the debug code in #ifdef DEBUG

Example

in son_parse.h:

#ifdef DEBUG
    void son_print();
#endif

in son_parse.c

#ifdef DEBUG
void son_print(son* node) {
    printf("%s", node->key);

    /* Print node value, or (null) if none. */
    char* valuestr = NULL;
    switch (node->type) {
    case SON_INTEGER:
        printf(" : %d\n", node->integer);
        break;
    case SON_ARRAY:
        printf(" :");
        for(int i = 0; i < node->array.size; ++i) {
            printf(" %d", node->array.data[i]);
        }
        putchar('\n');
        break;
    case SON_STRING:
        valuestr = node->string;
    case SON_NONE:
    default:
        printf(" : %s\n", valuestr);
        break;
    }

    /* Print node siblings, or (null) if none. */
    char* nextstr = NULL;
    char* childstr = NULL;
    if (node->next) {
        nextstr = node->next->key;
    }
    if (node->child) {
        childstr = node->child->key;
    }
    printf("next: %s child: %s\n", nextstr, childstr);
}
#endif

You can define DEBUG in the CC or gcc command line, have a DEBUG target in a make file, or your IDE may provide a DEBUG mode that defines the DEBUG macro for you.

Global Variables

While the variables c, file, temp_node and temp_tab are localized to son_parse.c by the static definition, they are still global to the file.

Global variables should be avoided because it's much harder to write robust code using them and it's much harder to debug. A programmer has to search an entire file to find where the variable is being changed. It is much better to pass the variables as arguments to the function. This also allows the programmer to prevent change to the variable depending on how it is passed into the function, pass by reference allows the variable to be changed when the function returns, pass by value allows a function to change the variable internally but not globally (in C a copy of the variable is passed in for pass by value, a pointer is passed in for pass by reference).

Guardbanding vs #pragma once

This stackoverflow.com question discusses using

#pragma once

versus guardbanding such as

#ifndef SON_PARSE_H_
#define SON_PARSE_H

... code ...

#endif

The two provide similar functions, but #pragma once is not part of the C standard and may not be implemented in all compilers. The file son_parse.h may not portable to all systems.

Efficient File Input

There are multiple possibilities to make the reading of the input file more efficient. - Read large blocks of text into a large character buffer and then process the text using a pointer to character. - Use fgets() to get a line at a time and then parse the line of text using character manipulation, fgets() returns a null terminated string that does not contain a new line character.

It would be more efficient input an entire node and then parse the input string rather than use fseek(). Every time code calls fseek() or fread() it is making a system call, this means the code in the program is swapped out while the file system does it's thing (context switch). On a time sharing system or server this can really affect performance, on personal computer it doesn't matter as much but it is still a performance hit.

The code also uses ungetc(), if the entire node was read into a string / character buffer, backing up is easier by using pointers.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the pointers. I've implemented some of these suggestions since posting my question, but I learned a lot from your other points. The reading efficiency seems to be a big problem so I'll convert everything over to string-parsing. \$\endgroup\$ – DragonDePlatino Apr 7 '17 at 3:13
  • 1
    \$\begingroup\$ Using atoi for parsing numbers is bad. \$\endgroup\$ – Roland Illig Apr 9 '17 at 17:13

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.