seg fault: Cannot access memory at address

Question

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define ALPHABET_LENGTH    26
#define OPERATION_BUF_SIZE  5
#define NAME_BUF_SIZE      22
#define MAX_BUF_SIZE       27

#ifndef NULL 
#define NULL ((void*)0) 
#endif

/* Basic trie node -- also, keep track of number of nodes below this one. */
typedef struct node {
    int num_children;
    struct node *children[ALPHABET_LENGTH];
} trie_node;

trie_node* init(trie_node* a) {
    a->num_children = 0;
    for (int i = 0; i < ALPHABET_LENGTH; ++i)
    {
        a->children[i] = NULL;
    }
    return a;
}

char* trim(char* a){
    if (a[0] == 'a')
    {
        a += 4;
    }else{
        a += 5;
    }
    return a;
}

void add(char* a, trie_node* node){//need to make sure a is not NULL at beginning
    trie_node* newNode = malloc(sizeof(struct node));
    newNode = init(newNode);
    int i;
    if ((a != NULL && a[0] !='\n') && node->children[a[0] - 97] == NULL)
    {
        node->num_children++;
        //initialize the children array
        for (i = 0; i < ALPHABET_LENGTH; i++)
        {
            if (newNode->children[i] != NULL)
            {
                newNode->children[i] = NULL;
            }
        }
        newNode -> num_children = 0;
        node->children[a[0] - 97] = newNode;
        a++;
        add(a, newNode);
    }
    else if ((a != NULL && a[0] !='\n') && node->children[a[0] - 97] != NULL){
        a++;
        node->num_children++;
        add(a, node->children[a[0] - 97]);
    } else{//a == NULL, which means end of the add procedure
        return;
    }
    free(newNode);
}

int main()
{
    int t,total,remain,temp;
    scanf("%d\n", &t);
    total = t;
    trie_node* contacts = malloc(sizeof(struct node));
    contacts = init(contacts);
    while(t != 0){
        char* s = malloc(MAX_BUF_SIZE); //char array to store the input
        t--;
        remain = total - t;
        fgets(s, MAX_BUF_SIZE, stdin);
        if (s[0] == 'a')
        {
            s = trim(s);
            //do add operation
            if (s != NULL)
            {//make sure there is something to add
                add(s, contacts);
            }

        }
        else{
            printf("No such operation found at line %d. (Only add or find is allowed)\n", remain);
        }
        free(contacts);
        free(s);//memory leak problem
    }

    //if operation is not add or find, will be an error.
    return 0;
}

Every time my program goes into the second case in add function, which is the else if statement, it will segfault saying that node->children[a[0]-97] can not be accessed. For example, I do add abc and then add acd. This will get a segfault. Also, I believe there is some memory leak in my function. I check my code in valgrind. It says invalid free() at free(s)

Sorry, I should mention this at beginning. a assume to be consisted of lower case letters. And all my test input for now, only consider add and find operations.

`s = trim(s);` will do strange things if strlen(a) happens to be <=4. — joop, Apr 03 '17 at 14:29
`if (s != NULL)` should be checked before `fgets(s, MAX_BUF_SIZE, stdin);` — LPs, Apr 03 '17 at 14:29
BTW each time you create a `newNode` and then you'll free at at the end of add function, so second time that memory does not exists..... — LPs, Apr 03 '17 at 14:42
`malloc()` returns void pointer, typecast it to the required type. — Milind Deore, Apr 03 '17 at 14:45
It can not be `free(s);` after `s = trim(s);`. because it differs from `malloc`'s return value. — BLUEPIXY, Apr 03 '17 at 16:45
@BLUEPIXY So in this case, if the value changed, do I still need to free s? If I do, how to free it? — Tom.D, Apr 03 '17 at 18:05
@LPs Thanks for the reply! I tried not free newNode before. The problem is still here. I still cannot access the newNode at second case in the loop — Tom.D, Apr 03 '17 at 18:07
`free` must be applied. For example, you can do as follows. `char* buff = malloc(MAX_BUF_SIZE);while(t != 0){ char* s = buff;... } free(buff);` or `char buff[MAX_BUF_SIZE];` instead of `char* buff = malloc(MAX_BUF_SIZE);` Alos `free(contacts);` move to after while-loop.and Let's free the entire tree. — BLUEPIXY, Apr 03 '17 at 18:15
@MilindDeore [Don't cast malloc](http://stackoverflow.com/q/605845/1848654). — melpomene, Apr 03 '17 at 18:39
when calling any of the heap allocation functions: (malloc, calloc, realloc) always check (!=NULL) the returned value to assure the operation was successful. — user3629249, Apr 04 '17 at 14:20
when calling any of the `scanf()` family of functions, always check the returned value (not the parameter values) to assure the operation was successful. — user3629249, Apr 04 '17 at 14:22
when calling `fgets()`, always check (!=NULL) the returned value to assure the operation was successful. — user3629249, Apr 04 '17 at 14:22
variable names should indicate `usage` or `content` (or better, both). variable names like `t`, `s`, `a` are meaningless, even in the current context. — user3629249, Apr 04 '17 at 14:27
the `init()` function is returned exactly what was passed to it. I.E. a point to an instance of the `struct node`. None of the posted code actually needs the `init()` function to return anything, Suggest this line: `contacts - init( contacts);` be replaced with `init( contacts );` and the `init()` function be modified accordingly. — user3629249, Apr 04 '17 at 14:34
in the `add()` function, the parameter name is `node`, which is the same as the `struct node` definition` This is a poor programming practice. Modern C compilers can handle it as the names are kept in separate name spaces, but it is confusing to the reader. — user3629249, Apr 04 '17 at 14:38
the `add()` function is excessively recursive. Amongst other things the `if else` block is not handling the results of the call to `malloc()`, so that pointer is lost. This is a memory leak — user3629249, Apr 04 '17 at 14:43
in the `trim()` function, the pointer `a` is being incremented by 4 or 5 (not really a 'trim' operation) There is nothing in the code to indicate what that 4 or 5 is actually accomplishing. Infact, there is nothing in the code to indicate the expected format of the data line entered by the user. — user3629249, Apr 04 '17 at 14:53
there are a LOT of calls to `malloc()`, and (per the code) will need a loop to free() all the allocated memory segments, BUT there is no loop that calls `free()` — user3629249, Apr 04 '17 at 14:55
this line: `printf("No such operation found at line %d. (Only add or find is allowed)\n", remain);` indicates a `add` or a `find` operation are allowed, but there is no code for the `find` operation — user3629249, Apr 04 '17 at 14:57
nothing in the posted code is making use of the contents of the `string.h` nor the `math.h` header files. It is a poor programming practice to `#include` header files those contents are not being used. — user3629249, Apr 04 '17 at 15:00
the variable `remain` is actually the current line number, read from the user, and not the `remain`der of anything. Suggest using a meaningful variable name — user3629249, Apr 04 '17 at 15:03
this comment: `//if operation is not add or find, will be an error.` is related to the `else` code block in `main()`, not to the exiting of the program, Please correct this oversight. — user3629249, Apr 04 '17 at 15:05
in `main()`, at the bottom of the `while()` loop, the code passes the pointer `contacts` to `free()` but during the next pass through the loop, uses that pointer as if it were still valid. This is a logic error and can/will lead to a seg fault event. — user3629249, Apr 04 '17 at 15:07
for ease of readability and understanding: 1) follow the axiom: *only one statement per line and (at most) one variable declaration per statement.* 2) separate code blocks (for, if, else, while, do...while, switch, case, default) via a single blank line. 3) separate functions by 2 or 3 blank lines (be consistent) — user3629249, Apr 04 '17 at 15:10
@MilindDeore, a `void*` can be assigned to any other pointer. It only needs to be typecast in C++ and this is NOT C++. Casting the returned value just clutters the code, making it more difficult to understand, debug, etc. — user3629249, Apr 04 '17 at 15:14
this expression: `node->children[a[0] - 97] == NULL)` and this expression: `node->children[a[0] - 97] = newNode;` make the assumption that `a[0]` is a lower case letter, What happens if it is uppercase? What happens if it is a space? What happens if it is punctuation? — user3629249, Apr 04 '17 at 15:18

score 0 · Answer 1 · answered Apr 03 '17 at 19:59

First of all, thanks for all of you who reply my question. The real problem in my function is I modified a before I access the node position using a[0].

Here is how I fix the problem:

void add(char* a, trie_node* node){//need to make sure a is not NULL at beginning
    int i,temp;
    if ((a != NULL && a[0] !='\n') && node->children[a[0] - 97] == NULL)
    {
        node->num_children++;
        //initialize the children array
        trie_node* newNode = malloc(sizeof(struct node));
        newNode = init(newNode);
        node->children[a[0] - 97] = newNode;
        a++;
        add(a, newNode);
    }
    else if ((a != NULL && a[0] !='\n') && node->children[a[0] - 97] != NULL){
        node->num_children++;
        temp = a[0];
        a++;
        add(a, node->children[temp - 97]);//line 56
    } else{//a == NULL, which means end of the add procedure
        return;
    }
}

I add a int temp to store the value of a[0], and then do a++.

Before I do this, if I "add abc" then "add acd", in the second loop, at line 56, add function will get value of a as "cd\n", and value of node->children[a[0]-97] where a[0] is c now instead of a.

Now everything is fixed. Thanks all!

still the problem, what if `a[0]` is not a ascii lower case letter? — user3629249, Apr 04 '17 at 15:23
the char pointer `a` will NEVER be NULL until `a` is incremented until it loops back to 0! I suspect your looking for the NUL string termination byte so you should use: `(*a != '\0')` or `(a[0] != '\0')` or `(*a)`. — user3629249, Apr 04 '17 at 15:28
@user3629249 this is not an real application. So as question mentioned, a must be consisted of lower case letters. Thanks for pointing out that — Tom.D, Apr 05 '17 at 00:35

seg fault: Cannot access memory at address

1 Answers1