"Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)" In CLion
While trying to solve a coding problem today, I got tired of OnlineGDB not being able to support large input files, so I decided to pull out CLion and use that instead. However the result that I get is that the exact same code that had worked for me on OnlineGDB get SIGSEGV error in CLion...
My Code(My apologizes for it being so long):
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 100000000000;
const ll MOD = 1000000007;
const int MAX_N = 1000005;
/*using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef struct trie_node trie_node;
char *decimal_binary(int val) {
char *bin_rep = (char*)(calloc(32, sizeof(char)));
for(int i = 31; i >= 0; --i) {
if(val & (1 << i)) {
bin_rep[i] = '1';
} else {
bin_rep[i] = '0';
}
}
reverse(bin_rep, bin_rep+32);
return bin_rep;
}
int binary_decimal(char *bs) {
int sum = 0;
for(int i = 31, j = 0; i >= 0; --i, ++j) {
sum += ((int)(bs[i]-'0'))*pow(2, j);
}
return sum;
}
struct trie_node {
trie_node *children[2];
bool is_leaf = false;
};
trie_node *make_node() {
trie_node *node = new trie_node;
for(int i = 0; i < 2; ++i) {
node->children[i] = NULL;
}
node->is_leaf = false;
return node;
}
void unload_node(trie_node *node) {
for(int i = 0; i < 2; ++i) {
if(node->children[i] != NULL) {
unload_node(node->children[i]);
} else {
continue;
}
}
free(node);
}
trie_node *insert_node(trie_node *root, char *bs) {
trie_node *temp = root;
for(int i = 0; bs[i] != '\0'; ++i) {
int idx = (int)(bs[i]-'0');
if(temp->children[idx] == NULL) {
temp->children[idx] = make_node();
}
temp = temp->children[idx];
}
temp->is_leaf = true;
return root;
}
bool check_leaf(trie_node *root, char *bs) {
trie_node *temp = root;
for(int i = 0; bs[i]; ++i) {
int idx = (int)bs[i]-'0';
if(temp->children[idx] != NULL) {
temp = temp->children[idx];
}
}
return temp->is_leaf;
}
int earliest_branch(trie_node *root, char *bs) {
trie_node *temp = root;
int n = strlen(bs);
if(n == 0) return 0;
int last_idx = 0;
for(int i = 0; i < n; ++i) {
int idx = bs[i]-'0';
if(temp->children[idx]) {
for(int j = 0; j < 2; ++j) {
if(j != idx && temp->children[j]) {
last_idx = i+1;
break;
}
}
temp = temp->children[idx];
}
}
return last_idx;
}
char *longest_prefix(trie_node *root, char *bs) {
if(!bs || bs[0] == '\0') return NULL;
int n = strlen(bs);
char *lgt_prefix = (char*)(calloc(n+1, sizeof(char)));
for(int i = 0; bs[i] != '\0'; ++i) {
lgt_prefix[i] = bs[i];
}
lgt_prefix[n] = '\0';
int branch_idx = earliest_branch(root, lgt_prefix)-1;
if(branch_idx >= 0) {
lgt_prefix[branch_idx] = '\0';
lgt_prefix = (char*)(realloc(lgt_prefix, (branch_idx+1)*sizeof(char)));
}
return lgt_prefix;
}
trie_node *delete_node(trie_node *root, char *bs) {
if(!root) return NULL;
if(!bs || bs[0] == '\0') return root;
if(!check_leaf(root, bs)) return root;
trie_node *temp = root;
char *lgt_prefix = longest_prefix(root, bs);
if(lgt_prefix[0] == '\0') {
free(lgt_prefix);
return root;
}
int pos;
for(pos = 0; lgt_prefix[pos] != '\0'; ++pos) {
int idx = (int)lgt_prefix[pos]-'0';
if(temp->children[idx] != NULL) {
temp = temp->children[idx];
} else {
free(lgt_prefix);
return root;
}
}
int n = strlen(bs);
for(; pos < n; ++pos) {
int idx = (int)bs[pos]-'0';
if(temp->children[idx]) {
trie_node *extra = temp->children[idx];
temp->children[idx] = NULL;
unload_node(extra);
}
}
free(lgt_prefix);
return root;
}
int search_val(trie_node* root, char* word) {
// Searches for word in the Trie
trie_node* temp = root;
for(int i=0; word[i]!='\0'; i++) {
int position = word[i] - '0';
if(temp->children[position] == NULL) return 0;
temp = temp->children[position];
}
if (temp != NULL && temp->is_leaf == 1) return 1;
return 0;
}
char *search_trie(trie_node *root, char *bs) {
char *res = (char*)(calloc(32, sizeof(char)));
for(int i = 0; i < 32; ++i) {
res[i] = '0';
}
trie_node *temp = root;
for(int i = 0; i < 32; ++i) {
int idx = (((int)(bs[i]-'0'))+1)%2;
if(temp->children[idx] != NULL) {
res[i] = '1';
temp = temp->children[idx];
} else if(temp->children[(idx+1)%2] != NULL){
temp = temp->children[(idx+1)%2];
} else {
break;
}
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
trie_node *root = make_node();
map<int, int> cnt;
char *tmpbs = decimal_binary(0);
root = insert_node(root, tmpbs);
while(t--) {
char type; int val;
cin >> type >> val;
char *bs = decimal_binary(val);
if(type == '+') {
if(cnt[val] == 0) {
root = insert_node(root, bs);
char *tmp = decimal_binary(7);
cout << type << " " << val << " find 7: " << search_val(root, tmp) << "\n";
}
++cnt[val];
} else if(type == '-') {
--cnt[val];
if(cnt[val] == 0) {
root = delete_node(root, bs);
char *tmp = decimal_binary(7);
cout << type << " " << val << " find 7: " << search_val(root, tmp) << "\n";
}
} else {
char *res = search_trie(root, bs);
int ans = binary_decimal(res);
cout << ans << "\n";
char *tmp = decimal_binary(7);
cout << type << " " << val << " find 7: " << search_val(root, tmp) << "\n";
free(res);
}
}
unload_node(root);
return 0;
}
Given Input:
OnlineGDB Result(Works):
CLion Result(SIGSEGV):
I tried going online and searching for what might've caused this error, but nothing showed up looked quite like what I was trying to find. Can someone help me figure out what's wrong please? Thanks!
Solution
Instead of using a function to convert from decimal to a binary string, I changed it to a bitset and then used bitset.to_string(). This meant that I also changed char* to string. Not only that, I saved over 40 lines of code by changing my delete function to be recursive. I ended up with this code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 100000000000;
const ll MOD = 1000000007;
const int MAX_N = 1000005;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef struct trie_node trie_node;
int binary_decimal(string &bs) {
int sum = 0;
for(int i = 31, j = 0; i >= 0; --i, ++j) {
sum += ((int)(bs[i]-'0'))*pow(2, j);
}
return sum;
}
struct trie_node {
trie_node *children[2];
bool is_leaf = false;
};
trie_node *make_node() {
trie_node *node = new trie_node;
for(int i = 0; i < 2; ++i) {
node->children[i] = NULL;
}
node->is_leaf = false;
return node;
}
void unload_node(trie_node *node) {
for(int i = 0; i < 2; ++i) {
if(node->children[i] != NULL) {
unload_node(node->children[i]);
} else {
continue;
}
}
free(node);
}
trie_node *insert_node(trie_node *root, string &bs) {
trie_node *temp = root;
for(int i = 0; bs[i] != '\0'; ++i) {
int idx = (int)(bs[i]-'0');
if(temp->children[idx] == NULL) {
temp->children[idx] = make_node();
}
temp = temp->children[idx];
}
temp->is_leaf = true;
return root;
}
bool check_leaf(trie_node *root) {
for(int i = 0; i < 2; ++i) {
if(root->children[i]) {
return false;
}
}
return true;
}
trie_node *delete_node(trie_node *root, string &bs, int depth = 0) {
if(!root) return NULL;
if(depth == sizeof(bs)) {
if(root->is_leaf) {
root->is_leaf = false;
}
if(check_leaf(root)) {
delete(root);
root = NULL;
}
return root;
}
int idx = (int)bs[depth]-'0';
root->children[idx] = delete_node(root->children[idx], bs, depth+1);
if(check_leaf(root) && root->is_leaf == false) {
delete(root);
root = NULL;
}
return root;
}
string search_trie(trie_node *root, string &bs) {
string res = "00000000000000000000000000000000";
trie_node *temp = root;
for(int i = 0; i < 32; ++i) {
int idx = (((int)(bs[i]-'0'))+1)%2;
if(temp->children[idx] != NULL) {
res[i] = '1';
temp = temp->children[idx];
} else if(temp->children[(idx+1)%2] != NULL){
temp = temp->children[(idx+1)%2];
} else {
break;
}
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
trie_node *root = make_node();
map<int, int> cnt;
string tmpbs = "00000000000000000000000000000000";
root = insert_node(root, tmpbs);
while(t--) {
char type; int val;
cin >> type >> val;
bitset<32> bset(val);
string bs = bset.to_string();
if(type == '+') {
if(cnt[val] == 0) {
root = insert_node(root, bs);
}
++cnt[val];
} else if(type == '-') {
--cnt[val];
if(cnt[val] == 0) {
root = delete_node(root, bs);
}
} else {
string res = search_trie(root, bs);
int ans = binary_decimal(res);
cout << ans << "\n";
}
}
unload_node(root);
return 0;
}
- Segmentation Fault: Zsh: segmentation fault ./a.out
- SDL_Quit segmentation fault
- Segfault in Rust when calling a function returned by a cdylib crate function
- How to resolve "ffmpeg was killed with signal SIGSEGV" in docker container
- Segmentation fault in C BogoSort
- Trying to initialize class objects inside a struct is causing segmentation faults
- Returning const reference from lambda stored as std::function segfaults
- Android Fatal signal 11 (SIGSEGV) at 0x636f7d89 (code=1). How can it be tracked down?
- Segmentation fault with multidimensional arrays whose size is determined at runtime
- Segmentation fault (core dumped) in reading a binary file, memmove-vec-unaligned-erms.S: No such file or directory
- rust code (with no unsafe) keeps segfaulting (musl)
- Integer array seemingly deallocates itself when passed by reference to a function
- fread() is reading the wrong data even though previous chunk were read correctly
- Kivy Application Fatal signal 11 (SIGSEGV), code 1 (SEGV_MAPERR), fault addr 0x40 in tid 10919 (SDLThread) after opening the app in the android device
- Quicksort segmentation fault
- Definitive List of Common Reasons for Segmentation Faults
- Segmentation error in destructor if the array is used
- Huffman code segfaults on random input but not on text input
- Problems with memory allocation and input (C)
- Segmentation core dumped when trying to build a single linklist
- Segmentation fault while implementing a binary tree in c
- C++ accessing vector of vector got segmentation fault
- check if assessing an address will cause a segfault without crashing python
- My c code is giving unknown segmentation fault
- segmentation fault: Malloc problem when i try to create a cv::mat
- select() seems to segfault / kill
- Triple fault when jumping to long mode x86_64
- Crash or 'segmentation fault' when data is copied/scanned/read to an uninitialized pointer
- Segmentation fault with strlen when not ever using strlen?
- strdup giving weird warning and Segmentation fault