gpt4 book ai didi

c++ - 查找 'SEGV on unknown address' 的原因,由 READ 访问引起

转载 作者:行者123 更新时间:2023-12-02 10:38:22 24 4
gpt4 key购买 nike

我正在编写一个 Splay Tree 实现。代码在 VS 中编译得很好,但测试系统因 DEADLYSIGNAL 而失败。
测试的具体输入是:

search 66
min
max
set 1 20
print

这是完整的代码:
#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 调试器没有告诉我导致此错误的原因。 Sanitazier 将其描述为读取错误,但我无法弄清楚它到底发生在哪个函数中。
此外,完整的 sanitizer 输出:
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.

希望有人帮忙。先感谢您。

最佳答案

由于这显示在搜索结果中:
您的某些代码(当您看到完整的 ASan 错误时会发现)正在创建无效地址 0x4 ASan 想看到的内存。
可以说是 int意外转换到指针或故意转换,比如说

 auto p = (int*)4;
查看完整错误和其中的堆栈跟踪。
  • Derived class offset calculation in boost::serialization. Is it valid?
  • 关于c++ - 查找 'SEGV on unknown address' 的原因,由 READ 访问引起,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58596901/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com