Hackerrank: C - Querying the Document

Question

I'm stuck with an unidentified Segmentation Fault.

My erroneous function receives a string text. It should convert it into a document and return it. A document is made of paragraphs(separated by '\n') which is made of sentences(separated by '.') which is made of words(separated by ' '). You may refer the complete problem statement here.

Here is the relevant part of my code:

char**** get_document(char* text) {
    int p = 0, s = 0, w = 0, c = 0;
    char**** document;
    document = malloc(sizeof(char***));
    document[0] = malloc(sizeof(char**));
    document[0][0] = malloc(sizeof(char*));
    document[0][0][0] = malloc(sizeof(char));
    while (*text)
    {
        if (*text == ' ')
        {
            c = 0;
            ++w;
            document[p][s] = realloc(document[p][s], sizeof(char*) * (w + 1));
        }          
        else if (*text == '.')
        {
            c = 0;
            w = 0;
            ++s;
            document[p] = realloc(document[p], sizeof(char**) * (s + 1));
        } 
        else if (*text == '\n')
        {
            c = 0;
            w = 0;
            s = 0;
            ++p;
            document = realloc(document, sizeof(char***) * (p + 1));
        }
        else
        {
            ++c;
            document[p][s][w] = realloc(document[p][s][w], sizeof(char) * (c + 1));
            document[p][s][w][c - 1] = *text;
            document[p][s][w][c] = '\0';
        }
        ++text;
    }
    return document;
}

After debugging, I came to know that the program crashes when

w = 1 at document[p][s][w][c - 1] = *text;

I have no idea why this is happening. I checked the values of p, s, w, and c before the execution of that statement, and if the realloc statements were executing properly.

But in vain!

What might be going wrong in my code?

That's a lot of asterisks. Are you sure the problem requires this degree of pointer indirection? Also, `sizeof(char*)`, `sizeof(char**)` and `sizeof(char***)` should all be the same size. — Robert Harvey, Feb 21 '20 at 15:44
@RobertHarvey The output must be `char****` in order to complete the task — Ardent Coder, Feb 21 '20 at 15:49
Well, you're going to have to fix those mallocs. I'm pretty sure they all return the size of a pointer, not the size of your string. That's most likely the cause of your segmentation faults. — Robert Harvey, Feb 21 '20 at 15:50
@RobertHarvey Those mallocs only deal with the initialization of the pointers. I have allocated the memory for strings in that else block. — Ardent Coder, Feb 21 '20 at 15:52
@RobertHarvey Yeah I know and I had tackled many in the past. To be honest, this is the first time I have asked somebody to help me in debugging my code. — Ardent Coder, Feb 21 '20 at 15:54
If you've never malloc'd a particular location in the array, then why "realloc" it? — Robert Harvey, Feb 21 '20 at 15:55
@RobertHarvey those reallocs are for the upcoming iterations. I think there is no problem in calling realloc before malloc as that would simply mean `realloc(NULL, SIZE)` — Ardent Coder, Feb 21 '20 at 15:56
Well, [this](https://en.cppreference.com/w/c/memory/realloc) says that realloc *"Reallocates the given area of memory. It must be previously allocated by malloc(), calloc() or realloc() and not yet freed with a call to free or realloc. Otherwise, the results are undefined."* — Robert Harvey, Feb 21 '20 at 15:57
@RobertHarvey arghhh I knew something was wrong! I had even checked that when I googled https://stackoverflow.com/questions/4459275/is-a-malloc-needed-before-a-realloc. But I did not see that point! — Ardent Coder, Feb 21 '20 at 15:59
@RobertHarvey Please don't go offline. Let me try and I'll be back soon — Ardent Coder, Feb 21 '20 at 16:00
Well, according to [this](http://www.cplusplus.com/reference/cstdlib/realloc/), your approach is supposed to work. *"In case that ptr is a null pointer, the function behaves like malloc, assigning a new block of size bytes and returning a pointer to its beginning."* — Robert Harvey, Feb 21 '20 at 16:01
You have to troubleshoot it. I think you're going to have to isolate the line of code that is causing the segmentation fault. — Robert Harvey, Feb 21 '20 at 16:03
You're not going to get *any* output unless you fix the segmentation fault. — Robert Harvey, Feb 21 '20 at 16:07
@RobertHarvey lol while debugging, I did get some output until w = 1 :( But I don't know how to proceed after that — Ardent Coder, Feb 21 '20 at 16:08
Try running your code through valgrind. If you're mismanaging memory, it will tell you where. — dbush, Feb 21 '20 at 16:47

score 1 · Accepted Answer · edited Feb 22 '20 at 10:51

You need to allocate memory for the new paragraphs, sentences and words. By reallocation you increased the actual dimension size, but the new element was a null pointer which caused the segfault.

char**** get_document(char* text) {
    int p = 0, s = 0, w = 0, c = 0;
    char**** document;
    document = malloc(sizeof(char***));
    document[0] = malloc(sizeof(char**));
    document[0][0] = malloc(sizeof(char*));
    document[0][0][0] = malloc(sizeof(char));
    while (*text)
    {
        if (*text == ' ')
        {
            c = 0;
            ++w;
            document[p][s] = realloc(document[p][s], sizeof(char**) * (w + 1));
            document[p][s][w] = malloc(sizeof(char*));
        }          
        else if (*text == '.')
        {
            c = 0;
            w = 0;
            ++s;
            document[p] = realloc(document[p], sizeof(char**) * (s + 1));
            document[p][s] = malloc(sizeof(char**));
            document[p][s][w] = malloc(sizeof(char*));
        } 
        else if (*text == '\n')
        {
            c = 0;
            w = 0;
            s = 0;
            ++p;
            document = realloc(document, sizeof(char****) * (p + 1));
            document[p] = malloc(sizeof(char***));
            document[p][s] = malloc(sizeof(char**));
            document[p][s][w] = malloc(sizeof(char*));
        }
        else
        {
            ++c;
            document[p][s][w] = realloc(document[p][s][w], sizeof(char) * (c + 1));
            document[p][s][w][c - 1] = *text;
            document[p][s][w][c] = '\0';
        }
        ++text;
    }
    return document;
}

Moreover, your printing method in the main does not work, because you did not save the spaces (you needn't anyways). So, I fixed it:

int main()
{
    char* text = "New word.No space before a sentence.\nThis is a new paragraph.";
    char**** doc = get_document(text);
    int p = 0, s = 0, w = 0, c = 0;
    char ch;
    while (ch = *text)
    {
        if (ch == ' ')
        {
            putchar(' ');
            c = 0;
            ++w;
        }
        else if (ch == '.')
        {
            putchar('.');
            c = 0;
            w = 0;
            ++s;
        }
        else if (ch == '\n')
        {
            putchar('\n');
            c = 0;
            w = 0;
            s = 0;
            ++p;
        }
        else putchar(doc[p][s][w][c++]);;
        text++;
    }

    return 0;
}

The output seems correct:

New word.No space before a sentence.
This is a new paragraph.

I think you don't have to free the doc because you are returning from the main after it and Hackerrank will handle that if needed. But just note that you should take care of it otherwise.

@ArdentCoder You are welcome. I needed some time to realize this too. And you are right I edit it. — Eraklon, Feb 21 '20 at 17:02
@ArdentCoder Well thanks. I took time for me too figure this out and some debugging. — Eraklon, Feb 21 '20 at 17:17
I still have a question... The error was using realloc before malloc, right? But that is not supposed to have created this problem according to the Standard (link in the Comments of my question). Could you please explain in detail? — Ardent Coder, Feb 22 '20 at 06:24
You could use reallocs instead of mallocs here but it is pointless. The problem is that when the next sentence come so `s = 1` and `p`, `w`, `c` are `0` . You will dereferencing a NULL pointer here `document[p][s][w] = realloc(document[p][s][w], sizeof(char) * (c + 1));` since `document[p][s]` is null at this point. — Eraklon, Feb 22 '20 at 08:27
Oh I see, so the problem is **dereferencing null pointer!** But compilers just know to complain *Segmentation Fault* lol. — Ardent Coder, Feb 22 '20 at 08:41

Hackerrank: C - Querying the Document

1 Answers1