I am currently implementing skiplist with my own vector implementation and I am getting an heap corruption not detected error
testing skiplist
entered Skiplist constructor
Skiplist: success creating pSentinel
Skiplist: success creating pHeader
Skiplist: pHeader()->levels() == 4
Skiplist: success constructing
***success: testing skiplist
testing node creation
try creating Skiplist<int> testNodeCreation
entered Skiplist constructor
Test_Skiplist(70815,0x7ff8457d7100) malloc: Heap corruption detected, free list is damaged at 0x6000005f01a0
*** Incorrect guard value: 105553167581712
Test_Skiplist(70815,0x7ff8457d7100) malloc: *** set a breakpoint in malloc_error_break to debug
zsh: abort ./bin/src/test/Test_Skiplist
when running
int main() {
std::cout<<std::endl<<std::endl<<"testing skiplist"<<std::endl;
Skiplist<int> sk1;
std::cout<<"***success: testing skiplist"<<std::endl;
std::cout<<std::endl<<"testing node creation"<<std::endl;
std::cout<<"try creating Skiplist<int> testNodeCreation"<<std::endl;
Skiplist<int> testNodeCreation;
std::cout<<"created Skiplist<int>"<<std::endl;
}
My understanding is that heat corruption error is thrown when I try to access out of bounds of heap allocated memory.
However, it seems like the error occurs right after second iteration of operator new + Skiplist<T>::Node::Node() constructor call:
template<typename T>
Skiplist<T>::Skiplist() {
std::cout<<"entered Skiplist constructor"<<std::endl;
using Node = typename Skiplist<T>::Node;
this->pSentinel = new Node(*this, 4);
/*(typename Skiplist<T>::Node *) this->pSentinel = new Node(*this, 4);*/ /* Skiplist<T>::Node* sentinel */
std::cout<<"Skiplist: success creating pSentinel"<<std::endl;
this->pHeader = new Node(*this, 4);
/*(typename Skiplist<T>::Node *) this->pHeader = new Node(*this, 4);*/ /* Skiplist<T>::Node* header */
std::cout<<"Skiplist: success creating pHeader"<<std::endl;
std::cout<<"Skiplist: pHeader()->levels() == "<<pHeader->levels()<<std::endl;
int inx = this->pHeader->levels() - 1;
for(; inx>=0; --inx) {
(*pHeader)[inx] = pSentinel; /* typeof Node * */
}
std::srand(std::time(0)); /* seeding std::rand() */
std::cout<<"Skiplist: success constructing"<<std::endl;
}
Looking at the first round of Skiplist<T>::Skiplist constructor call stdout value, it seemes like
pHeader()->levels()
is providing the proper output 4 and therefore the for loop in the Skiplist<T>::Skiplist constructor should be within the proper index range, and that is probably why the first iteration of Skiplist<T>::Skiplist constructor call does not fail, successfully connecting the header node to the sentinel node of the skiplist.
Node constructor
template<typename T>
Skiplist<T>::Node::Node(Skiplist<T>& sk, size_t __levels) : skiplist(sk) {
this->listToNext = Vector<Skiplist<T>::Node*>(__levels, nullptr);
/* no val initialized */
if(skiplist.allowedMaxLevel <= __levels){
skiplist.allowedMaxLevel = __levels + 1;
}
}
constructs a statically allocated Skiplist<T>::Node which contains the reference to the skiplist containing itself, a personally implemented vector, and a value.
The unary operator[] for Skiplist<T>::Node is implemented as
template<typename T>
Skiplist<T>::Node * & Skiplist<T>::Node::operator[](const size_t i) {
return listToNext.at(i); /* listToNext : Vector<Node*> */
}
which therefore is intended to return the Skiplist<T>::Node* pointer value.
The vector
template<typename T>
Vector<T>::Vector(size_t size, const T& val) {
this->vsize = size;
set_appropriate_capacity();
this->container = (T *)std::malloc((this->vcapacity) * sizeof(T));
for(size_t i = 0; i < size; ++i) {
container[i] = val;
}
}
itself is static, which includes a dynamically allocated container in it.
The .at() member function of Vector<T> which is used to implement Skiplist<T>::Node::operator[] is implemented as
template<typename T>
T& Vector<T>::operator[](size_t i) {
return this->container[i];
}
template<typename T>
T& Vector<T>::at(size_t i) {
if(i>=this->vsize)
throw("Vector::at() index out of bounds");
return this->container[i];
}
with rest of the functions used in the vector constructor being
template<typename T>
Vector<T>& Vector<T>::operator=(Vector<T> && vec) {
vsize = vec.vsize;
vcapacity = vec.vcapacity;
container = vec.container;
return *this;
}
template<typename T>
Vector<T>::~Vector() {
this->vsize = 0;
std::free(this->container);
this->vcapacity = 0;
}
template<typename T>
void Vector<T>::set_appropriate_capacity() {
size_t capacity_candidate = 25;
/*
prevent overflow
REQUIRES: this->vsize is of type size_t (ensured by def)
(probably also works when max_size is odd)
*/
const size_t max_size = -1; /*signed -1 is unsigned max*/
if((max_size/2 - 10 < this->vsize)
&& (this->vsize <= max_size)){
this->vcapacity = max_size;
}
while((capacity_candidate - 10) < this->vsize) {
capacity_candidate *= 2;
}
this->vcapacity = capacity_candidate;
}
When I have tested the Vector<T> implementation, there has been no problem with the heap regardless of how many vectors I have created. Therefore I suppose that the problem is not about the Vector<T> implementation.
I have tried using lldb and it seems like the error is from malloc which doesn’t seem to make sense considering it’s a Heap corruption detected error
(lldb) s
Process 75063 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = step in
frame #0: 0x0000000100002a35 Test_Skiplist`Vector<Skiplist<int>::Node*>::Vector(this=0x0000600003a08060) at vector.tpp:11:47
8 this->vsize = 0;
9 set_appropriate_capacity();
10
-> 11 this->container = (T *)std::malloc((this->vcapacity) * sizeof(T));
12 }
13
14 template<typename T>
(lldb) s
Test_Skiplist(75063,0x7ff8457d7100) malloc: Heap corruption detected, free list is damaged at 0x600000f001a0
*** Incorrect guard value: 105553177116672
Test_Skiplist(75063,0x7ff8457d7100) malloc: *** set a breakpoint in malloc_error_break to debug
Process 75063 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
frame #0: 0x00007ff80226d14a libsystem_kernel.dylib`__pthread_kill + 10
libsystem_kernel.dylib`__pthread_kill:
-> 0x7ff80226d14a <+10>: jae 0x7ff80226d154 ; <+20>
0x7ff80226d14c <+12>: movq %rax, %rdi
0x7ff80226d14f <+15>: jmp 0x7ff802266b20 ; cerror_nocancel
0x7ff80226d154 <+20>: retq
Are there some other potential reasons why an Heap corruption detected error might occur? Is my use of operator new wrong in any way? Thank you in advance.
#ifndef Skiplist_Included
#define Skiplist_Included
#include "vector.hpp"
#include <cstddef> /* size_t */
#include <cstdlib> /* rand() */
template<typename T>
class Skiplist {
private:
size_t allowedMaxLevel; /* Inner class is a friend of the class it is defined within */
/* Outer::Inner class can access the (private) member variable of Outer */
bool flipcoin();
public:
class Node {
private:
Vector<Node *> listToNext;
Skiplist& skiplist;
public:
Node(Skiplist& sk);
Node(Skiplist& sk, size_t __levels);
Node(Skiplist& sk, size_t __levels, T __key);
/*
Node(Node& n);
Node& operator=(Node& n);
*/
Node(Node&& n); /* want to use default move constructor */
/*
Node& operator=(Node&& n);
*/
T key;
/* void updateMaxNumOfLevels(); */
const size_t levels();
Node* & operator[](const size_t i);
void addLevel(const size_t i);
};
private:
Node* pHeader;
Node* pSentinel;
void insertBetween(Node* pFrontNode, Node* pBackNode, Node* pNodeToInsert);
void insertImpl(Node* pCurrNode, Node* pNodeToInsert, size_t topLevel);
public:
Skiplist();
/* ~Skiplist(); */
/* bool isNextNodeSentinel(Node* pCurrNode); */
void insert(T __key);
};
/*--------------------------------------------*/
/*--------------------------------------------*/
#include "skiplist.tpp"
#endif
#ifndef Vector_Included
#define Vector_Included
#include<cstdlib> /* for size_t, memory alloc */
#include<iterator> /* for std::random_access_iterator_tag */
#include<cstddef> /* for ptrdiff_t */
template<typename T>
class Vector {
T * container;
size_t vsize, vcapacity;
/* size_t iter; */
void set_appropriate_capacity();
public:
/* Constructors */
Vector();
Vector(size_t size);
Vector(size_t size, const T& val);
template<size_t N>
Vector(const T(&arr)[N]);
Vector& operator=(Vector& vec);
Vector(Vector<T>&& vec);
Vector& operator=(Vector&& vec);
/* Destructor */
~Vector();
T& operator[](size_t i);
T& operator[](size_t i) const;
T& at(size_t i);
/* const T& at(size_t i) const; */
T& front();
T& back();
void sort(size_t lo, size_t hi);
const size_t& capacity();
const size_t& size();
void print_container();
struct Iterator {
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
Iterator(); /* default construct */
Iterator(const Vector<T>* other_vp); /* construct */
Iterator(const Vector<T>* other_vp, size_t other_inx); /* construct */
Iterator(const Iterator & other_iter); /* copy construct */
Iterator operator=(const Iterator & other_iter); /* copy assign */
/* destruct - use default : declaring default destructor causes error */
reference operator*(); /* dereference operator: *Iter */
reference operator*() const;
pointer operator&(); /* address_of operator: &Iter */
/* const pointer operator&() const; */
reference operator[](difference_type n); /* dereference n index away from current */
/* const reference operator[](difference_type n) const; */
/* change inx value of *this iterator, return some iterator */
Iterator& operator++(); /* prefix ++ on Iterator, return ++'d one */
Iterator operator++(int); /* postfix ++ on Iterator, return non++'d one */
Iterator& operator--(); /* prefix -- on Iterator, return --'d one */
Iterator operator--(int); /* postfix -- on Iterator, return non--'d one*/
Iterator& operator+=(const difference_type& n); /* shift *this iter, return *this */
Iterator& operator-=(const difference_type& n); /* shift *this iter, return *this */
Iterator operator+(const difference_type& n); /* return new shifted iter, *this no change */
Iterator operator-(const difference_type& n); /* return new shifted iter, *this no change */
/*---------------*/
difference_type operator-(const Iterator& j); /* return difference between *this.inx and I2.inx */
/* compare inx values between Iterators */
bool operator==(const Iterator& j); /* *this.inx == j.inx */
bool operator!=(const Iterator& j); /* *this.inx != j.inx */
bool operator<(const Iterator& j); /* *this.inx < j.inx */
bool operator>(const Iterator& j); /* *this.inx > j.inx */
bool operator<=(const Iterator& j); /* *this.inx <= j.inx */
bool operator>=(const Iterator& j); /* *this.inx >= j.inx */
void turn_invalid();
bool is_invalid();
private:
const Vector<T>* vp;
size_t inx;
bool is_valid;
void try_throw_invalid_iter_error();
};
Iterator begin() const;
Iterator end() const;
Iterator insert(const Iterator & position_iter, size_t n, const T val);
void pop_back();
void push_back(const T& val);
};
template<typename T>
void swap(Vector<T>& v, const size_t i, const size_t j);
template<typename T>
size_t partition(Vector<T>& v, const size_t lo, const size_t pi, const size_t hi);
template<typename T>
void quicksort(Vector<T>& v, const size_t lo, const size_t hi);
/*---------------------------------------------------*/
#include"vector.tpp"
#endif