I'm writing a Splay Tree implementation. Code compiles just fine in VS, but the testing system fails with DEADLYSIGNAL. The specific input for testing is:
search 66
min
max
set 1 20
print
Here is the full code:
#include <iostream>
#include <sstream>
#include <stack>
#include <queue>
#include <cmath>
struct Node
{
int64_t key;
std::string value;
Node* left, * right, * parent;
Node(const int64_t& k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
Node(const int64_t& k, const std::string& v, Node* p) : key(k), value(v),
left(nullptr), right(nullptr), parent(p) {}
};
class SplayTree
{
Node* root;
size_t size;
bool isRight(Node* node)
{
if (node && node->parent)
if (node->parent->right == node)
return true;
else
return false;
}
std::pair<int, Node*> Find(const int64_t& key)
{
Node* node = root;
while (node)
{
if (node->key == key)
return { 2, node };
else if (node->key > key)
if (node->left)
node = node->left;
else
return { 0, node };
else if (node->key < key)
if (node->right)
node = node->right;
else
return { 1, node };
}
}
void Merge(Node* left, Node* right)
{
if (!left && !right)
root = nullptr;
else if (!left)
{
root = right;
right->parent = nullptr;
}
else if (!right)
{
root = left;
left->parent = nullptr;
}
else
{
left = Max(left);
left->parent = nullptr;
left->right = right;
right->parent = left;
}
}
void rotateL(Node* node)
{
Node* p = node->parent;
Node* r = node->right;
if (p != nullptr)
if (p->left == node)
p->left = r;
else
p->right = r;
Node* temp = r->left;
r->left = node;
node->right = temp;
node->parent = r;
r->parent = p;
if (temp != nullptr)
temp->parent = node;
}
void rotateR(Node* node)
{
Node* p = node->parent;
Node* l = node->left;
if (p != nullptr)
if (p->left == node)
p->left = l;
else
p->right = l;
Node* temp = l->right;
l->right = node;
node->left = temp;
node->parent = l;
l->parent = p;
if (temp != nullptr)
temp->parent = node;
}
void Zig(Node* node)
{
!isRight(node) ?
rotateR(node->parent) : rotateL(node->parent);
}
void ZigZig(Node* node, bool side)
{
if (side)
{
rotateL(node->parent->parent);
rotateL(node->parent);
}
else
{
rotateR(node->parent->parent);
rotateR(node->parent);
}
}
void ZigZag(Node* node, bool side)
{
if (side)
{
rotateL(node->parent);
rotateR(node->parent);
}
else
{
rotateR(node->parent);
rotateL(node->parent);
}
}
void Splay(Node* node)
{
while (node->parent != nullptr)
{
if (node->parent == root)
Zig(node);
else if (!isRight(node) && !isRight(node->parent))
ZigZig(node, 0);
else if (isRight(node) && isRight(node->parent))
ZigZig(node, 1);
else if (!isRight(node) && isRight(node->parent))
ZigZag(node, 0);
else
ZigZag(node, 1);
}
root = node;
}
std::string printNode(Node* node)
{
std::string result;
result += '[' + std::to_string(node->key) + ' ' + node->value;
if (node->parent)
result += ' ' + std::to_string(node->parent->key);
result += ']';
return result;
}
Node* Max(Node* node)
{
Node* temp = node;
if (temp)
{
while (temp->right)
temp = temp->right;
Splay(temp);
return temp;
}
else
return nullptr;
}
Node* Min(Node* node)
{
Node* temp = node;
if (temp)
{
while (temp->left)
temp = temp->left;
Splay(temp);
return temp;
}
else
return nullptr;
}
public:
Node* getRoot() { return root; }
SplayTree() : root(nullptr), size(0) { }
SplayTree(uint64_t key)
{
root = new Node(key);
size = 1;
}
~SplayTree()
{
if (root)
{
std::stack<Node*> toDelete;
toDelete.push(root);
while (!toDelete.empty())
{
Node* node = toDelete.top();
if (node->left)
{
toDelete.push(node->left);
node->left = nullptr;
}
else if (node->right)
{
toDelete.push(node->right);
node->right = nullptr;
}
else
{
toDelete.pop();
delete node;
}
}
}
}
bool Add(const int64_t& key, const std::string& value)
{
if (!root)
{
root = new Node(key, value, nullptr);
size++;
return true;
}
else
{
std::pair<int, Node*> result = Find(key);
if (result.first == 2)
return false;
else if (result.first == 0)
{
result.second->left = new Node(key, value, result.second);
Splay(result.second->left);
size++;
return true;
}
else
{
result.second->right = new Node(key, value, result.second);
Splay(result.second->right);
size++;
return true;
}
}
}
std::string Search(const int64_t& key)
{
if (root)
{
std::pair<int, Node*> result = Find(key);
if (result.first == 2)
{
Splay(result.second);
return "1 " + result.second->value;
}
Splay(result.second);
}
return "0";
}
Node* Min() { return Min(root); }
Node* Max() { return Max(root); }
bool Set(const int64_t& key, const std::string& value)
{
std::pair<int, Node*> result = Find(key);
if (result.first == 2)
{
result.second->value = value;
Splay(result.second);
return true;
}
else
return false;
}
bool Delete(const int64_t& key)
{
if (!root)
return false;
std::pair<int, Node*> result = Find(key);
if (result.first == 2)
{
Splay(result.second);
Node* subL = result.second->left;
Node* subR = result.second->right;
Merge(subL, subR);
delete result.second;
size--;
return true;
}
return false;
}
std::string Print()
{
std::string result;
std::queue<Node*> toPrint;
toPrint.push(root);
size_t counter = size;
size_t space = 0;
size_t i = 0;
while (!toPrint.empty())
{
Node* node = toPrint.front();
toPrint.pop();
space++;
if (node)
{
result += printNode(node);
toPrint.push(node->left);
toPrint.push(node->right);
counter--;
}
else
{
result += "_";
toPrint.push(nullptr);
toPrint.push(nullptr);
}
if (space == pow(2, i))
{
result += "\n";
if (counter != 0)
{
i++;
space = 0;
}
}
else
result += " ";
if (counter == 0 && space == pow(2, i))
break;
}
return result;
}
};
int main()
{
std::string data;
std::getline(std::cin, data, '\0');
data += '\n';
std::istringstream is(data);
std::ostringstream os;
SplayTree tree;
int64_t key;
std::string command, value;
bool empty = false;
while (is >> command)
{
if (command.empty())
{
empty = true;
}
if (command == "add" && is.peek() != '\n'
&& is >> key && is.peek() != '\n' && is >> value && is.peek() == '\n')
{
if (!tree.Add(key, value))
os << "error" << std::endl;
}
else if (command == "set" && is.peek() != '\n'
&& is >> key && is.peek() != '\n' && is >> value && is.peek() == '\n')
{
if (!tree.Set(key, value))
os << "error" << std::endl;
}
else if (command == "delete" && is.peek() != '\n'
&& is >> key && is.peek() == '\n')
{
if (!tree.Delete(key))
os << "error" << std::endl;
}
else if (command == "search" && is.peek() != '\n'
&& is >> key && is.peek() == '\n')
{
os << tree.Search(key) << std::endl;
}
else if (command == "min" && is.peek() == '\n')
{
Node* temp = tree.Min();
if (temp)
{
os << temp->key << " "
<< temp->value << std::endl;
}
else
os << "error" << std::endl;
}
else if (command == "max" && is.peek() == '\n')
{
Node* temp = tree.Max();
if (temp)
{
os << temp->key << " "
<< temp->value << std::endl;
}
else
os << "error" << std::endl;
}
else if (command == "print" && is.peek() == '\n')
{
os << tree.Print();
}
else
{
if (!empty)
os << "error" << std::endl;
}
}
std::cout << os.str();
return 0;
}
VS debugger tells me nothing on what causes this error. Sanitazier describes it as read fault, but I can't figure out in which function exactly it happens. Also, full Sanitizer output:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==26100==ERROR: AddressSanitizer: SEGV on unknown address 0x00000004 (pc 0x08164c7a bp 0xbff0f8d8 sp 0xbff0f420 T0)
==26100==The signal is caused by a READ memory access.
==26100==Hint: address points to the zero page.
Hope someone helps. Thank you in advance.
Since this shows up in search results:
Some part of you code (which you'll find out when you see the full ASan error) is creating an invalid address 0x4 which ASan wants to see the memory of.
It could be say an int accidentally cast to a pointer or an intentional cast like say
auto p = (int*)4;
See full error and the stack trace in it.