Is there a way to fix the segmentation fault ? I can't seem to figure it out

Question

I'm not sure why I'm getting a segmentation fault in my code?

 class Node {
    public:
        int data;
        Node *next;
};

void push_back(Node** head_ref, int new_data) {  
    Node* new_node = new Node(); 
  
    Node *last = *head_ref;
    new_node->data = new_data;  
    new_node->next = NULL;  

    if (*head_ref == NULL) {  
        *head_ref = new_node;  
        return;  
    }  
  
    while (last->next != NULL)  
        last = last->next;  
  
    last->next = new_node;
    
    return;  
}  

int getHash(string initials) {
    string digits;
    
    for (int i = 0; i < 3; i++) {
        switch(initials[i]) {
            case 'A':
            case 'B':
            case 'C':
                digits += "2";
                break;
            case 'D':
            case 'E':
            case 'F':
                digits += "3";
                break;
            case 'G':
            case 'H':
            case 'I':
                digits += "4";
                break;
            case 'J':
            case 'K':
            case 'L':
                digits += "5";
                break;
            case 'M':
            case 'N':
            case 'O':
                digits += "6";
                break;
            case 'P':
            case 'Q':
            case 'R':
            case 'S':
                digits += "7";
                break;
            case 'T':
            case 'U':
            case 'V':
                digits += "8";
                break;
            case 'W':
            case 'X':
            case 'Y':
            case 'Z':
                digits += "9";
                break;
        }
    }
    
    return stoi(digits);
}

int getSize (Node* head) {
    int size = 0;
    bool not_null = true;
    Node *current = head;
    
    while (not_null) {
        if (current->next == NULL) {
            not_null = false;
            return size;
        } else {
            size++;
            current = current->next;
        }
    }
}

int main() {
    int count = 512;
    string initials;
    map<int, int> stats;
    Node* bitvec[count];
    for ( int i = 0; i < count; i++ ) {
        Node *data_node = new Node;
        data_node->data = 1;
        bitvec[i] = data_node;
    }

    for ( int i = 0; i < count; i++ ) {
        for (int j = 0; j < 3; j++) 
            initials.push_back((char)(rand() % 26 + 65));
        
        int hash = getHash(initials);
        
        cout << initials << " - " << hash << " - " << hash % count << endl;
        //cout <<"-"<< count<< endl;
        push_back(&(bitvec[hash % count]), 0);
        
        initials = "";
    }

    cout << "collision array" << endl;

    for ( int i = 0; i < count; i++ ) {
            if ( stats.count( getSize(bitvec[i]) ) <= 0 ) {
                    stats[ getSize(bitvec[i]) ] = 1;
            } else {
                    stats[ getSize(bitvec[i]) ]++;
            }
            cout << setw( 2 ) << getSize(bitvec[i]) << " ";
            if ( ( i + 1 ) % 25 == 0 ) {
                    cout << endl;
            }
    }

    int total = 0;
    cout << endl;
    for ( map<int, int>::iterator it = stats.begin( ); it != stats.end( ); it++ ) {
            if ( it->first != 0 ) {
                    total += it->second;
            }
            cout << it->first << " collisions occurred #" << it->second << endl;
    }

    cout << "Max number of collisions is: " << ( --stats.end( ) )->first << endl;
    cout << "Total collisions: " << total << endl;
    float avg = (float) count / total;
    cout << "average search: " << avg << endl;
  
    return 0;
}

You have a small hole in `getSize`. Enter it with an null `head` and it'll go boom. — user4581301, Dec 20 '20 at 05:10
Repeat of the above, sort of. `while (last->next != NULL)` is a tough sucker to get right. You're usually better off rewriting for `while (last != NULL)` so you don't have to worry about trying to `last->next` when `last` is null. Five bucks says that one'll be your error. — user4581301, Dec 20 '20 at 05:14
Side note: There's a neat trick you can do with a pointer to a pointer to make [inserts](https://stackoverflow.com/a/59779376/4581301) and [removal](https://stackoverflow.com/a/22122095/4581301) from a singly linked list dead easy. — user4581301, Dec 20 '20 at 05:17
Bypassing the limit on the amount of code you can post without explanatory text by just repeating your text is not the way to use this site. The reason the limit is there is to encourage you to provide a detailed explanation of your problem. Have you tried using a debugger? What's your code supposed to do? Where does it crash? Please provide a [mre] — Alan Birtles, Dec 20 '20 at 05:30
Side note: If you don't have to make your own linked list, don't. [C++ has all sorts of suitable containers](https://en.cppreference.com/w/cpp/container) that'll do all if the work for you with no fuss and no muss. — user4581301, Dec 20 '20 at 05:36

score 0 · Answer 1 · answered Dec 20 '20 at 05:31

In main

for ( int i = 0; i < count; i++ ) {
    Node *data_node = new Node;
    data_node->data = 1;
    // whoops! Didn't set data_node->next = NULL.
    bitvec[i] = data_node;
}

This mistake means the while (last->next != NULL) and similar tests later in the code fail. This means my comment under the question nailed the location of the bug, but got the cause wrong. Such is life. Should have taken me up on the bet.

This can be simplified to

for ( int i = 0; i < count; i++ ) {
    bitvec[i] = new Node{1, NULL};
}

Which uses Aggregate Initialization to make sure everything is initialized.

This prevents the program from crashing. I have not checked to see if the output is correct.

Is there a way to fix the segmentation fault ? I can't seem to figure it out

1 Answers1