C segmentation fault in linked list class member function-CodePudding

I have created a nested class (LinkedList and Node) to implement a linked list class in C , but I am having segmentation fault errors with a few of my class member functions. I have spent multiple hours trying to figure out what the errors are because I have been using Microsoft Virtual Studio to compile my code and it doesn't catch any segmentation fault errors for any of my test cases, but different compilers do catch the errors.

Here is an example of the error message: Error message

For instance, my GetNode() function (which is supposed to return a pointer to the node at a given index and then throw an exception of type out_of_range if the index is out of range) is as follows:

    const Node* GetNode(unsigned int index) const {
        if ((int)index < count && (int)index >= 0 && head != nullptr) {
            Node* test = head;
            for (unsigned int i = 0; i < index;   i) {
                test = test->next;
            }
            return test;
        }
        else {
            throw out_of_range("Error: out of range");
        }
    }

I type casted index to integer because count is an integer and I wasn't sure if the different data types would cause an issue. Head is the first node of the linked list. Next is the pointer to the next node. The first index of the linked list should be 0 and then the last one should be count - 1. I would really appreciate any help here. I can post the code of other functions that are giving me the segmentation fault error if requested.

CodePudding user response：

If you know for certain that count is the actual length of the list then the only possible way for your code to cause a seg fault is if index exceeds the largest possible 32-bit integer (and count), and casting that value into an int causes it to wrap around to a value between 0 and count, making the initial if statement pass. Then the for loop iterates using that large number, causing test to reach the end of the list and dereferencing that null pointer would cause a segmentation fault.

Here is code that doesn't have that flaw:

const Node* GetNode(unsigned int index) const {
  while (index--) {
    if (!test)
      break;
    test = test->next;
  }
  return !test ? throw out_of_range("Error: out of range") : test;
}

The problem might still be elsewhere, but in your code the only two issues are the one I just explained, and if count isn't the actual length of the list.

CodePudding user response：

Your version of function exhibits Undefined Behaviour in case if index is incorrectly big (larger than MAX_INT) or if head is nullptr. Generally speaking do not allow any case where a function that return value may not return. Some compilers have a quirk to generate an incorrect code in that case, intentionally to avoid masquerade of missed edge cases. It should look at least like:

const Node* GetNode(unsigned int index) const {
    if ((int)index < count && (int)index >= 0 && head != nullptr) {
        Node* test = head;
        for (unsigned int i = 0; i < index;   i) {
            test = test->next;
        }
        return test;
    }
  
    throw out_of_range("Error: out of range");
}

(int)index on a unsigned and in general such cast style are not recommended. The function also assumes that there is enough elements in list

You have to also assume that head maybe non-null but index is zero and vice versa.

If index is zero-based then while index=N-1, N-th element can be nullptr, we're returning one before it. I.e. if index=0, then we are returning head if it's not nullptr. At index=1 we are returning head->next if it's not nullptr, and so on.

Possible solution (it assumes index is zero based):

const Node* GetNode(unsigned index) const {
    Node* cour = head;
    
    // we can't return nullptr, we must throw
    while(test) {
       // if index is zero, return courser pointer
       if(!index) return cour;
       test = test->next; 
       --index;
    } 
    throw out_of_range("Error: out of range");
}

So far, you appear to "know" some invariant count which may allow a short circuit check. But what type it is? Your cast suggest it being an int.

In real life an unsigned int parameter for index may be a design flaw unless you can ensure its correct usage at all times. Especially if actually stored parameter is an int. A negative value would get converted to very large positive, which may result in lock-up of program if your algorithm is built like one provided in question.

If you're casting unsigned to signed, you're already in gray area. If you're comparing unsigned to signed, you're allowing a similar error because its wrongdoing is the the implicit cast. You just made compiler to trust that you actually want such check.

If parameter is signed, passing a too large unsigned value as an argument of function results in a negative value of parameter:

const Node* GetNode(int index) const {
    Node* cour = head;

    // we can't return nullptr, we must throw
    if(index > 0 && index < count)
       while(test) {
         // if index is zero, return courser pointer
         if(!index) return cour;
         test = test->next; 
         --index;
       } 
    throw out_of_range("Error: out of range");
}

That seems a little paranoid, we assume here that count may be bad. You may add explicit check for head being nullptr and do a while-loop with index decrement, if you can trust the invariance of count.

In real life invariants can't be trusted 100% of time and should be checked in debug builds, the issue there isn't only a logic error but accidental data race, stale pointer dereference or an out-of-bound write somewhere in program. In that case diagnostics may be different, e.g. signaling a logic error instead of out-of-bound.