Creating index to a file in C

Question

My task was to index a file in C.

I'm getting one argument: file name. The index should contain all the words and a line list which appears in.

A few notes:

1. Big and small letters are the same.
2. A word is max sequence of chars which are only from english alphabet and or digits every other char is splitting between the words.
3. I should print an error message to stderr if I got too much args or if the input isn't matching (file doesn't exist).

The output will be written to a file with the same name and the ending ".index": if the file reading from is "input.txt" the output will be at "input.txt.index".

The word in the file should appear in lexicographic order.

For example:

input.txt:

Hello world

My, name is

WoooW././.L

Bye

So the file "input.txt.index" is created and should contain:

The word: "bye" appears in line: 4

The word: "hello" appears in line: 1

The word: "is" appears in line: 2

The word: "l" appears in line: 3

The word: "my" appears in line: 2

The word: "name" appears in line: 2

The word: "wooow" appears in line: 3

The word: "world" appears in line: 1

My code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#include "index.h"

/* Text functions area */

FILE *getFile (int argc, char const *argv[]) { /* A function to get the file inclouding a input check */
    FILE *theinput;

    if (argc < 2) { /* no argument */
        fprintf(stderr, "Must pass an argument!\n");
        exit(1);
    }

    theinput = fopen(argv[1], "r");

    if (!theinput) { /* Argument is non-existing file */
        fprintf(stderr, "Can't read %s\n", argv[1]);
        exit(1);
    }

    return theinput;
}

char *getText (FILE *file) { /* Gets the text from file, Return a string with the file content */
    char *text, *q;
    char token;
    int i = 0;
    text = malloc(sizeof(char));
    while ((token = getc(file)) != EOF) {
        text[i] = token;
        i++;
        q = realloc(text, (i + 2) * sizeof(char));
        if (!q) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        text = q;
    }
    text[i] = '\0';
    return text;
}

bool isLegalChar (char a) { /* Checks if a char is A - Z or a - z or 0 - 9 using ascii */
    if (a <= 90 && a >= 65) { /* A = 65, Z = 90 */
        return true;
    }
    else if (a <= 122 && a >= 97) { /* a = 97, z = 122 */
        return true;
    }
    else if (isdigit(a)) {
        return true;
    }
    else {
        return false;
    }
}

char *getWord (char *text, int start, bool *isEnterFound) { /* returns a single word from text starts searching from start */
    char *word,*q; /* q = a helper string to make sure mallocing well */
    char token; /* token is the right now input char */
    int i = 0;
    int j = start;
    word = malloc(sizeof(char));
    while (isLegalChar(token = text[j++]) || token == '\n') { 
        if (token == '\n')
        {
            (*isEnterFound) = true;
            break;
        }
        word[i++] = token;
        q = realloc(word, (strlen(word) + 2) * sizeof(char));
        if (!q) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        word = q;
    }
    word[i] = '\0';
    return word;
}

void tolowerString (char *input) { /* Changes a string so all the letters in it will by lower */
    int i;
    for (i = 0; i < strlen(input); ++i)
    {
        input[i] = tolower(input[i]);
    }
}

char* stradd(const char* a, const char* b) { /* Return a string which is the two given strings combined */
    size_t len = strlen(a) + strlen(b);
    char *ret = (char*)malloc(len * sizeof(char) + 1);
    *ret = '\0';
    return strcat(strcat(ret, a) ,b);
}

/* Tree functions area */ 

Node* newNode(char* word, int line) { /* Return a new node with the vars given to the funcion */
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->word = word;
    p->lines = malloc(sizeof(int));
    p->lines[0] = line;
    p->linesLength = 1;
    p->ls = p->rs = NULL; 
    return p; 
}

void insert(Node **root, char *word, int line) { /* Insert node to tree using recursion */
    int *q;
    int i;
    if(!*root) {
        *root = newNode(word, line); 
        return; 
    }
    if(strcmp(word, (*root)->word) < 0)  /* In case word is smaller than the nodes word */
    { 
        insert(&((*root)->ls),word,line); 
    }
    else if (strcmp(word, (*root)->word) == 0) /* In case word already exist */
    {
        for (i = 0; i < (*root)->linesLength; ++i)
        {
            if ((*root)->lines[i] == line)
            {
                return;
            }
        }
        q = realloc((*root)->lines, (*root)->linesLength + 2);
        if (!q)
        {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }
        (*root)->lines = q;
        (*root)->lines[(*root)->linesLength] = line;
        (*root)->linesLength++;
        return;
    }
    else /* In case word is bigger than the nodes word */
    {
        insert(&((*root)->rs),word,line); 
    }
}

void printTreeRec(Node *root, FILE *outputFile) { /* A recursive function which prints the tree by given root */
    int i;

    if(!root) {
        return; 
    }
    printTreeRec(root->ls, outputFile);

    fprintf(outputFile, "The word: \"%s\" ",root->word); 
    if (strlen(root->word) < 15) {
        for (i = 0; i < 15 - strlen(root->word); ++i) {
            fprintf(outputFile, " ");
        }
    }   
    fprintf(outputFile, "appears in ");
    if (root->linesLength == 1) {
        fprintf(outputFile, "line: ");
    }
    else {
        fprintf(outputFile, "lines: ");
    }
    for (i = 0;i < root->linesLength - 1; i++) {
        fprintf(outputFile, "%d, ", root->lines[i]);
    }
    fprintf(outputFile, "%d", root->lines[i]);
    fprintf(outputFile, "\n");

    printTreeRec(root->rs,outputFile);
}

void freeTree(Node *root) { /* A function to free the tree recursively */
    if(!root)
        return; 
    freeTree(root->ls);
    freeTree(root->rs); 
    free(root->lines);
    free(root); 
}

/* Main */

int main(int argc, char const *argv[]) {
    FILE *inputFile = getFile(argc,argv); /* Opening input file */
    char *ouputAddress = stradd(argv[1],".index"); /* Creating output file address */
    FILE *outputFile = fopen(ouputAddress,"w"); /* Creating output file */
    char *text = getText(inputFile);
    char *word;
    int line = 1; /* Line counter */
    bool foundEnter = false;
    bool *isEnterFound = &foundEnter;
    Node *root = NULL; /* First node of the tree */
    int start = 0; /* Pointer to what was the last thing readed in text string */

    while (start < strlen(text)) {
        word = getWord(text, start, isEnterFound); /* If getWord detected enter foundEnter will become true */
        tolowerString(word);
        start += strlen(word) + 1;

        if (strcmp(word, "") != 0) /* If word is not NULL */
        {
            insert(&root,word,line);
        }

        if (foundEnter)
        {
            foundEnter = false;
            line++;
        }
    }

    /* Ptinting the tree */
    printTreeRec(root, outputFile);

    /* Freeing the tree */
    freeTree(root);
    fclose(inputFile);
    fclose(outputFile);
    free(ouputAddress);
    free(text);
    free(word);

    return 0;
}

It's working great, but I'm afraid of memory problems because of all the struct vars.

By the way, the code is running at time complexity of \$O(log(n))\$, which is for adding a word to a binary search tree.

Answer 1

Magic Numbers

Don't write things like

if (a <= 90 && a >= 65) { /* A = 65, Z = 90 */

if you can just write

if (a <= 'Z' && a >= 'A') {

which is much clearer.

Declaring Variables

Assuming that you are using a reasonably modern version of c (e.g. C99, C11, ...), you do not need to declare all your variables up front. Instead, declare them when you actually use them the first time. This will add readability to your code, because the reader doesn't have to juggle all those variables in his head that are not going to be used until tenths of lines later.

Check The Return Value Of malloc

Every time you call realloc, you make sure that the call actually succeeded, which is the right thing to do. However, you do not do the same with calls to malloc, which can also fail if, for example, no more memory is available.

getFile

Why do you pass the arguments to main straight on to getFile? In my opinion, it would be better to only have getFile do what the name suggests (which is getting/opening a file) and leave handling argc and argv to main or another helper function (something like validateInput).

Also, you state that you have to check whether the program is called with too many arguments, but currently you only check for too few.

Finally. the comment

* Argument is non-existing file */

is misleading because fopen can also fail if, for example, the file exists but you have no reading permissions for it.

isLegalChar

This method is completely redundant because c offers the method isalnum which does exactly the same.

getText

getText is highly suboptimal. First of all, it actually contains a bug: token is of type char, but getc returns an int, because EOF may not fit into a char. Depending on whether char is signed or unsigned on your system, you might get an infinite loop or an early termination. Fixing this is easy: Just change the type of token to int.

Secondly, i is of type int, but since it is an index variable which can never go below zero, you should use an unsigned type at least. Also, if your file is very long, you might run into problems because of overflow. To counter these issues, C offers just the right type: size_t. You should use it every time you deal with the size of an array, a struct etc. (just as the name size_t suggests).

From a performance point of view, this function is terrible. You start off allocating a single byte for text, and then call realloc for every single character read (also, the reason why you allocate i + 2 bytes instead of i + 1 eludes me). As you hopefully know, calls to malloc are not cheap, and calls to realloc even less so (especially if realloc has to copy data).

Now you say: "Sure enough, but how do I do this efficiently if I do not know the file size?" Worry not, for the c standard library has just the right tools for you! They are called fseek and ftell. Most commonly, they are used as following:

• Go to the last position in the file using fseek(yourfile, 0, SEEK_END)
• Get the offset from the start of the file (= the file length) by means of ftell(yourfile)
• Go back to the beginning of the file by using fseek(yourfile, 0, SEEK_SET)

A better version of getText might thus look something like this:

char *getText(FILE *file) {
  fseek(file, 0, SEEK_END);
  long length = ftell(file);
  fseek(file, 0, SEEK_SET);

  char *text = malloc(length + 1);
  if (!text) {
    fprintf(stderr, "Malloc failed.\n");
    exit(1);
  }
  text[length] = '\0';

  size_t bytes_read;
  if ((bytes_read = fread(text, 1, length, file)) != length) {
    fprintf(stderr, "Failed to read file completely!");
    free(text);
    exit(1);
  }

  return text;
}

Notice also the use of fread for reading the file in one batch.

getWord

The same problem I mentioned at getText also occurs here: You have a lot of unncessary allocations. Again, the approach to solving the problem is similar:

1. Find the next word boundary
2. Allocate memory according to the distance between start and the word boundary found in 1.
3. Copy the word into the newly allocated memory

An improved implementation might look something like this:

char* getWord(const char* text, bool* isEnterFound) {
    size_t index = 0;
    while (isLegalChar(text[index]) || text[index] == '\n') {
        if (text[index] == '\n') {
            *isEnterFound = true;
            break;
        }

        index++;
    }

    char* word = malloc(index + 1);
    word[index] = '\0';
    if (!word) {
        fprintf(stderr, "Malloc failed.\n");
        exit(1);
    }

    memcpy(word, text, index);

    return word;
}

Notice that, instead of passing start separately, text now points to the beginning of the next word.

Don't Cast malloc

It is unnecessary and even discouraged because it clutters your code with casts and adds no further information.

Omit sizeof(char)

The standard specifies that sizeof(char) is always 1. Although some people advocate for it because it adds some information to your code, the knowledge that the size of char is one is so widespread that I wouldn't recommend writing it.

Memory Leaks

In main, you are getting new words by using getWord repeatedly in a while-loop whilst not freeing the current word after each iteration, instead only freeing the very last word at the end of the program. You should add a free(word) at the end of said loop.

Iterating Over A String

Writing

for (i = 0; i < strlen(input); ++i)

is suboptimal because it calls strlen for each iteration of your loop. Write something like

size_t length = strlen(input);
for (i = 0; i < length; ++i)

instead.

About Time Complexity

You state that your code is \$O(\log n)\$, which is obviously incorrect. The reason for this is that you need to iterate over every char in your input file, which is an \$O(n)\$ operation. Although you are right that inserting into a BST is an \$O(\log n)\$ operation, this term considers the size of the BST for \$n\$, which is separate from the length of your input.

About Memory Problems

You say that you are afraid of memory problems, but you really do not have to be. Apart from the missing free in your while-loop in main (see Memory Leaks), I did not spot any problems with forgotten frees or the like. The functions getText and getWord are a bit of a performance issue because they do so many allocations, but if you stick to the tips I gave you then that should be fine.

If you are worried about running out of memory, don't be. There is hardly anything you can do against it, and exiting gracefully if a call to malloc or realloc fails is really the best you can do. One could argue that you might run into memory fragmentation problems because of the tree data structure you employ, but this is very difficult to work around.

If you are really concerned about memory usage, e.g. because you process gigabyte-sized files, there is one optimization that you could apply: Instead of making separate copies of each word you find, just store offsets to where the word begins and ends in your memory buffer. In the best case, this could roughly cut memory usage in half (although maybe a 20% improvement is more realistic, but I am just guessing anyway). As I said before, you could also try replacing you BST with a normal array, although this will, of course, increase the cost of inserting elements quite drastically.

---

I did not review the Node related functions since the definition of Node was not given.

Answer 2

Memory Leaks

This program has a memory leaks. There should be a free() for every memory allocation, the variable word gets gets freed once at the end of the program, this is the wrong place to call free on word. Word should be freed whenever a Node is freed as root->lines is freed.

Use the Library Functions

The function isLegalChar() isn't really necessary, the function can be replaced by isalnum(), especially since isLegalChar() already calls isdigit().

Program Return Values

The program already includes stdlib.h probably for malloc(), realloc() and free(). Since stdlib.h is already included it might be better to use EXIT_SUCCESS and EXIT_FAILURE rather than return 0; in main() and exit(1); in other functions.

The Use of exit()

There are two functions that use exit(1) after memory allocation errors. This causes the program to exit without closing the input and output files. It would be better to have some way to return an error code from getText() and getWord() and then closing the input file and output file before the program quits, even better if freeTree() was called before the program exited.

Not as Fast as You Think

While the binary tree does allow a fast implementation, all the reallocation of memory can slow the program down. Every time malloc(), realloc() and calloc() are used the program is swapped out for a system call.