Segmentation fault (core dumped) but can't figure out

Question

From my understanding a segfault is usually caused by invalid memory access or leak? But I can't figure out where it is. Is there a way like a program that will go through your code and figure out where it is causing this error? Please help.

I am trying to build a ternary trie with functions such as insert find and predict completions.

This is my header file:

#include <vector>
#include <string>
#include <list>
#include <iostream>

using namespace std;

class TNode {
        public:
                TNode* left;
                TNode* right;
                TNode* middle;
                TNode* parent;
                int freq;
                char symbol;
                bool isWord;

                TNode(const char c, bool b, const unsigned int f);
};

class DictionaryTrie {

        public:

        DictionaryTrie();

        bool insert(std::string word, unsigned int freq);

        bool find(std::string word) const;

        std::vector<std::string> predictCompletions(std::string prefix, unsigned int numcompletions);

        ~DictionaryTrie();

        private:


        TNode* root;

        void deleteAll(TNode* root) const;

        void predictHelper(TNode* n, string s, list<pair<string, unsigned int>> &  allWords) const;

};
#endif

and this is my cpp file

#include "DictionaryTrie.hpp"
#include <list>
#include <string>
#include <vector>

using namespace std;

TNode::TNode(const char c, bool b, const unsigned int f) : symbol(c), isWord(b), freq(f), left(0), middle(0), right(0), parent(0) {}

DictionaryTrie::DictionaryTrie():root(0){}

bool DictionaryTrie::insert(string word, unsigned int freq) {
        if (word.empty())
                        return false;

        TNode* curr = root;

        if (curr == nullptr) {
                
                if (word.length() == 1)
                        root = new TNode (word[0], true, freq);
                else
                        root = new TNode(word[0], false, 0);
        }
        
        for (unsigned int i = 0; i < word.length();) {
                
                if (curr->symbol == word[i]) {

                        if (curr->middle != NULL) {
                                if (i == word.length()-1) {
                                        if(curr->isWord == false) {
                                                curr->isWord = true;
                                                curr->freq = freq;
                                                return true;
                                        }
                                        else
                                                return false;
                                }
                                else {
                                        curr = curr->middle;
                                        i++;
                                        continue;
                                }
                        }

                        else if (curr->middle == NULL) {
                                if(i!=word.length() - 1){
                                        curr->middle = new TNode(word[i+1], (i==word.length()-2),(i==word.length()-2)?freq:0);

                                        curr=curr->middle;
                                        i++;
                                        if (i==word.length()-2) return true;
                                }
                                else if (i == word.length() - 1) {
                                        if(curr->isWord == false) {
                                                curr->isWord = true;
                                                curr->freq = freq;
                                                return true;
                                        }
                                }
                                else return false;
                        }
                }
                else if(word[i] > curr->symbol) {
                        if (curr->right != NULL) {
                                curr=curr->right;
                                continue;
                        }
                        else {
                                curr->right = new TNode(word[i], (i==word.length()-1), (i==word.length()-1)?freq:0);
                               curr = curr->right;
                        if (i==word.length()-1)
                                return true;
                        }
                }
                else {
                        if (curr->left != NULL) {
                                curr = curr->left;
                                continue;
                        }
                        else {
                                curr->left = new TNode(word[i], (i==word.length()-1), (i==word.length()-1)?freq:0);
                                curr = curr->left;
                                if (i==word.length()-1)
                                        return true;
                        }
                }
        }
}
bool DictionaryTrie::find(string word) const {

        TNode* curr = root;

        if(word.length() == 0)
                return false;

        for (unsigned int i = 0; i < word.length();) {
                if (curr != NULL) {
                        if(curr->symbol == word[i]) {
                                i++;
                                if(i==word.length()) {
                                        if(curr->isWord == true)
                                                return true;
                                        else
                                                return false;
                                }
                                curr = curr->middle;
                        }
                        else if (word[i] > curr->symbol) {
                                curr = curr->right;
                        }
                        else
                                curr = curr->right;
                }
                else return false;
        }
}
vector<string> DictionaryTrie::predictCompletions(string prefix, unsigned int numCompletions) {
        vector<string> completions;

        list<pair<string, unsigned int>> allWords;

        if (numCompletions == 0 || prefix == "")
                return completions;

        TNode* curr = root;

        for (unsigned int i = 0; i < prefix.length();) {
                if (curr != NULL) {
                        if (curr->symbol == prefix[i]) {
                                i++;
                                if (i==prefix.length())
                                        break;
                                curr = curr->middle;
                        }

                        else if (prefix[i] < curr->symbol)
                                curr=curr->left;
                        else
                                curr=curr->right;
                }
                //prefix is not in trie
                else
                        return completions;
        }

        if (curr->isWord)
                allWords.push_back(make_pair(prefix, curr->freq));

        predictHelper (curr->middle, prefix, allWords);

        allWords.sort([](auto const& a, auto const& b) {

                if (a.second > b.second)
                        return true;
                if (a.second < b.second)
                        return false;
                return a.first < b.first;
                //return tie(b.second, a.first) < tie(a.second, a.first);
        });

        for(auto const& p: allWords) {
                if (completions.size() < numCompletions)
                        completions.push_back(p.first);
                else
                        break;
        }
}

void DictionaryTrie::predictHelper(TNode* n, string s, list<pair<string, unsigned int>> & allWords)const {
        if (n==NULL) return;

        else {
                string temp = s + n->symbol;

                //check if node is a valid word
                if (n->isWord == true)
                        allWords.push_back(make_pair(temp, n->freq));

        predictHelper(n->middle, temp, allWords);
        predictHelper(n->left, temp, allWords);
        predictHelper(n->right, temp, allWords);
        }
}

DictionaryTrie::~DictionaryTrie() {
        deleteAll(root);
}

void DictionaryTrie::deleteAll(TNode* n) const {

        if(!n) return;

        else {
                deleteAll(n->left);
                deleteAll(n->middle);
                deleteAll(n->right);
                delete n;
                return;
        }
}

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) — Jesper Juhl, Feb 03 '20 at 20:05

score 0 · Accepted Answer · answered Feb 03 '20 at 20:20

When you use a debugger, you should see that you get an access violation at if (cur->symbol == word[i]). (Do try this at home.) Why does this happen?

In DictionaryTrie::insert, if curr (== root) is a nullptr, you allocate a node and store it in root, but you do not update curr. You then enter the for loop, and reference curr->symbol. Since curr is a null pointer, you get an access violation.

The simple fix is to assign

curr = root;

after assigning a value to root.

Segmentation fault (core dumped) but can't figure out

1 Answers1