#c #debugging
#c #отладка
Вопрос:
Я пытаюсь реализовать базовый список пропусков, но я не могу понять, в чем проблема, потому что, когда я запускаю его, он выдает ошибку Segmentaion.
Я использовал Valgrind для проверки утечек памяти, и это выдает мне некоторые ОПРЕДЕЛЕННО потерянные блоки ошибок.
Я запускаю Valgrind следующим образом :
valgrind --leak-check=full --show-leak-kinds=all -v ./myProgram
Я попытался удалить то, что можно удалить, но это дает мне тот же результат плюс некоторые другие ошибки.
==20782== HEAP SUMMARY:
==20782== in use at exit: 96 bytes in 2 blocks
==20782== total heap usage: 14 allocs, 12 frees, 81,976 bytes allocated
==20782==
==20782== Searching for pointers to 2 not-freed blocks
==20782== Checked 111,288 bytes
==20782==
==20782== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==20782== at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==20782== by 0x1096AA: SkipList<int>::insertID(int, int) (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782== by 0x109395: main (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782==
==20782== 48 bytes in 1 blocks are definitely lost in loss record 2 of 2
==20782== at 0x4C3017F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==20782== by 0x1096CD: SkipList<int>::insertID(int, int) (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782== by 0x109395: main (in /home/matei/Desktop/Anul 1/S.D./Tema1/checker_tema1_2019/tema1)
==20782==
==20782== LEAK SUMMARY:
==20782== definitely lost: 96 bytes in 2 blocks
==20782== indirectly lost: 0 bytes in 0 blocks
==20782== possibly lost: 0 bytes in 0 blocks
==20782== still reachable: 0 bytes in 0 blocks
==20782== suppressed: 0 bytes in 0 blocks
==20782==
==20782== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
==20782== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
SkipList.h
using namespace std;
#define MIN_ID 0
#define MAX_ID 999999
#define NULL_SCORE 0
template < class T >
class Node {
public:
T level;
T ID;
T score;
Node<T>* next;
Node<T>* prev;
Node<T>* below;
Node<T>* above;
Node() {
next = NULL;
prev = NULL;
below = NULL;
above = NULL;
}
Node(T ID, T score) {
this->level = 1;
this->ID = ID;
this->score = score;
next = NULL;
prev = NULL;
below = NULL;
above = NULL;
}
Node(const Nodeamp; node) : level(node->level), ID(node->ID), score(node->score) {
}
Nodeamp; operator=(const Nodeamp; node) {
level = node->level;
ID = node->ID;
score = node->score;
return *this;
}
~Node() {}
T getScore() {
return this->score;
}
T getID() {
return this->ID;
}
T getLeve() {
return this->level;
}
T setScore(T score) {
T old_score;
old_score = this->score;
this->score = score;
return old_score;
}
};
template < class T >
class SkipList {
public:
Node<T>* head;
Node<T>* tail;
Node<T>* p1;
Node<T>* p2;
T height;
T no_entries;
SkipList() {
p1 = new Node<T>(MIN_ID, NULL_SCORE);
p2 = new Node<T>(MAX_ID, NULL_SCORE);
head = p1;
tail = p2;
p1->next = p2;
p2->prev = p1;
height = 1;
no_entries = 0;
}
~SkipList() {
delete p1;
delete p2;
}
SkipList(const SkipListamp; SkipList) : height(SkipList->height), no_entries(SkipList->no_entries) {
}
SkipListamp; operator=(const SkipListamp; SkipList) {
height = SkipList->height;
no_entries = SkipList->no_entries;
return *this;
}
T getSize() {
return this->no_entries;
}
T getHeight() {
return this->height;
}
bool isEmpty() {
if (no_entries == 0) {
return true;
}else {
return false;
}
}
T getScore(T ID) {
Node<T>* p;
p = searchID(ID);
if (p.getID() == ID ) {
return p->score;
}else {
return NULL;
}
}
string coinFlip() {
string s;
string str1 = "Heads";
string str2 = "Tails";
int r;
srand(time(0));
for (int i = 1; i < 2; i ) {
r = 1 (rand() %2);
}
if (r == 1) {
s.assign(str1);
}else if (r == 2) {
s.assign(str2);
}
return s;
}
Node<T>* insertAbove(Node<T>* p, Node<T>* e, T ID, T score) {
e = new Node<T>(ID, score);
p->above = e;
e->below = p;
e->below->prev->above->next = e;
e->prev = e->below->prev->above;
e->below->next->above->prev = e;
e->next = e->below->next->above;
delete e;
return e;
}
Node<T>* searchID(T ID) {
Node<T>* p;
p = head;
while (p->below != NULL) {
p = p->below;
while (ID >= p->next->ID) {
p = p->next;
}
}
return p;
}
Node<T>* insertID(T ID, T score) {
Node<T>* aux1;
Node<T>* new_node1 = new Node<T>(ID, score);
aux1 = searchID(ID);
aux1->next = new_node1;
new_node1->prev = aux1;
new_node1->next = tail;
while (coinFlip() == "Heads"); {
if (new_node1->level >= height) {
height ;
Node<T>* new_node2 = new Node<T>(ID, score);
//Create a new empty layer
Node<T>* p1 = new Node<T>(MIN_ID, NULL_SCORE);
Node<T>* p2 = new Node<T>(MAX_ID, NULL_SCORE);
//Making the connections
head->above = p1;
tail->above = p2;
p1->below = head;
p2->below = tail;
p1 = head;
p2 = tail;
while (aux1->above == NULL) {
aux1 = aux1->prev;
}
aux1 = aux1->above;
insertAbove(new_node1, new_node2, ID, score);
new_node1->level ;
delete new_node2;
}
}
no_entries ;
delete new_node1;
return new_node1;
}
bool deleteID(T ID) {
Node<T>* current = head;
bool found = false;
if (current->next == NULL amp;amp; current->next->ID == ID) {
found = true;
current->next = current->next->next;
no_entries--;
}
delete current;
return found;
}
};
main.cpp
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include "SkipList.h"
using namespace std;
int main() {
SkipList<int>* my_SkipList = new SkipList<int>();
for (int i = 0; i < 5; i ) {
my_SkipList->insertID(i, i);
}
return 0;
}
Комментарии:
1. Используйте интеллектуальные указатели.
2. @Quentin Я не могу этого сделать, поскольку это часть моей домашней работы, и мне не разрешено использовать функции из STL, и я могу использовать только несколько библиотек для C / C
3. «ВСЕ ЕЩЕ ДОСТУПНЫЕ БЛОКИ не настолько вредны» — Это может быть правдой, но это показывает, что в вашем коде происходит что-то, чего вы не понимаете. Это что-то, при других обстоятельствах, может быть вредным.
4. @BennyK Итак, что я могу сделать, чтобы решить мою проблему? Например, я дважды использую ключевое слово new в своем конструкторе и удаляю эти объекты в Destructor, пока не получу тот же результат, но если я удаляю те же объекты в Constructor, ошибки / предупреждения от Valgrind увеличиваются с 9 до 4. Итак, что мне нужно понять из этого?
5. Исправьте ошибку сегментации, прежде чем беспокоиться о любых утечках памяти. Если код, который должен был бы корректно устранить сбои, скорее всего, у него просто не было возможности что-то удалить. Не обязательно проблема, но оба ваших класса нарушают правило трех / пяти. Хотя на первый взгляд я не вижу, чтобы что-то их копировало, поэтому вы могли бы просто определить конструкторы копирования и присваивание как удаленные, а не внедрять их.
Ответ №1:
(Я предполагаю, что вы добавили delete my_SkipList
в конце main
.)
Если вы компилируете с отладочной информацией, лучше всего без оптимизации (параметры часто зависят от компилятора -g -O0
), valgrind
показывает номера строк обнаруженных проблем, например
==23956== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==23956== at 0x4C266E7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23956== by 0x400E94: SkipList<int>::insertID(int, int) (SkipList.h:194)
==23956== by 0x400C40: main (main.cpp:13)
==23956==
==23956== 48 bytes in 1 blocks are definitely lost in loss record 2 of 2
==23956== at 0x4C266E7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==23956== by 0x400EB7: SkipList<int>::insertID(int, int) (SkipList.h:195)
==23956== by 0x400C40: main (main.cpp:13)
Из этого мы можем легко видеть, что непревзойденные распределения являются
//Create a new empty layer
Node<T>* p1 = new Node<T>(MIN_ID, NULL_SCORE);
Node<T>* p2 = new Node<T>(MAX_ID, NULL_SCORE);
Отсюда мы можем определить, с чем связаны ошибки.
-
Вы не должны
delete
удалять узлы, которые являются частью существующихSkipList
, т.е.delete e
frominsertAbove()
иdelete new_node1
frominsertID()
. -
В
insertID()
коде для вставкиnew_node1
aux1->next = new_node1; new_node1->prev = aux1; new_node1->next = tail;
неверно предполагать, что следующий узел всегда был
tail
; лучше:new_node1->next = aux1->next; // next isn't necessarily tail aux1->next = new_node1; new_node1->prev = aux1;
-
Прежде всего, деструктора,
~SkipList()
освобождающего только два узла, выделенных в конструкторе, недостаточно — скорее, также должны быть освобождены все узлы, выделенные позже дляSkipList
, например.:~SkipList() { for (Node<T> *p, *c; p = head; ) { head = head->above; do c = p, p = p->next, delete c; while (p); } }
Обратите внимание, что эти пункты устраняют только ошибки выделения в коде, а не любую другую логическую ошибку.