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;
}
}
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.