Seg fault of STL like skiplist implementation

Tuesday, July 8, 2014

I was implementing STL-style skiplist. The internal node type is like:



template <class N>
struct __skiplist_node
{
typedef __skiplist_node<N>* __skiplist_node_pointer;
N data;
__skiplist_node_pointer prev;
std::list<__skiplist_node_pointer> nexts;
};


There is std::list in internal node. When I want to push_back a __skiplist_node into the list nexts. When the skiplist is constructed at run time. It encounter segment fault. The debug backstrace shows:



#0 0x00007ffff63a6acf in std::__detail::_List_node_base::_M_hook(std::__detail::_List_node_base*) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1 0x000000000045e0f6 in _M_insert (this=<optimized out>, __x=<optimized out>,
__position=...) at /usr/include/c++/4.8/bits/stl_list.h:1554
#2 push_back (__x=<optimized out>, this=<optimized out>)
at /usr/include/c++/4.8/bits/stl_list.h:1016
#3 repo::SkipList<ndn::Name, repo::tests::DatasetBase::DataSetNameCompare>::empty_initialize (this=<optimized out>)
at /home/chenatu/workspace/repo-ng/src/storage/skiplist.hpp:118
#4 0x000000000045ed1b in SkipList (this=0x7fffffffcfd0)
at /home/chenatu/workspace/repo-ng/src/storage/skiplist.hpp:124
#5 repo::tests::SkipList::NdnNameSkipList<repo::tests::BaseTestFixture>::test_method (this=this@entry=0x7fffffffd070) at ../tests/unit/skiplist.cpp:40
#6 0x000000000045efd9 in run<repo::tests::BaseTestFixture> ()
at ../tests/unit/skiplist.cpp:38
#7 operator() (this=<optimized out>)
at /usr/include/boost/test/unit_test_suite_impl.hpp:357
#8 invoke<boost::unit_test::ut_detail::test_case_template_invoker<repo::tests::SkipList::NdnNameSkipList_invoker, repo::tests::BaseTestFixture> > (
this=<optimized out>, f=...)
at /usr/include/boost/test/utils/callback.hpp:56


What I want to know is that how to allocate dynamically for this internal node?


The following it the complete code:



#ifndef REPO_STORAGE_SKIPLIST_HPP
#define REPO_STORAGE_SKIPLIST_HPP

#include "common.hpp"

#include <boost/utility.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>

namespace repo {

static const size_t SKIPLIST_MAX_LAYERS = 32;
static const double SKIPLIST_PROBABILITY = 0.25; // 25% (p = 1/4)

template<typename T, typename Compare = std::less<T> >
class SkipList
{
public:
template <class N>
struct __skiplist_node
{
typedef __skiplist_node<N>* __skiplist_node_pointer;
N data;
__skiplist_node_pointer prev;
std::list<__skiplist_node_pointer> nexts;
};

class iterator : public std::iterator<std::bidirectional_iterator_tag, T>
{
public:
typedef __skiplist_node<T>* link_type;
link_type node;
// constructor
iterator(link_type x) : node(x) {}
iterator() {}
iterator(const iterator& x) : node(x.node) {}
bool operator == (const iterator& x) const { return node == x.node; }
bool operator != (const iterator& x) const { return node != x.node; }

typename std::iterator<std::bidirectional_iterator_tag, T>::reference operator * () const
{ return (*node).data; }
typename std::iterator<std::bidirectional_iterator_tag, T>::pointer operator -> () const
{ return &(operator*()); }
iterator& operator ++ () {
node = (link_type)(*((*node).nexts.begin()));
return *this;
}
iterator& operator -- () {
node = (link_type)((*node).prev);
return *this;
}
};

protected:
typedef __skiplist_node<T> skiplist_node;
public:
typedef skiplist_node* link_type;
protected:
link_type node;
std::allocator<skiplist_node> skiplist_allocator;

link_type
get_node()
{
return skiplist_allocator.allocate(sizeof(skiplist_node));
}

void
put_node(link_type p)
{
skiplist_allocator.deallocate(p);
}

link_type
create_node(const T& x)
{
link_type p = get_node();
construct(&p->data, x);
return p;
}

void
destroy_node(link_type p)
{
destroy(&p->data);
put_node(p);
}

void
empty_initialize()
{
node = get_node();
node->prev = node;
node->nexts.push_back(node);
}
public:
explicit
SkipList()
{
empty_initialize();
}

~SkipList() {}

public:
iterator begin() const { return (link_type)(*(*node).nexts.begin()); }

iterator end() const { return node; }

bool empty() const { return *(node->nexts.begin()) == node; }

size_t size() const
{
size_t result = 0;
result = std::distance(begin(), end());
return result;
}

};
} // namespace repo
#endif // REPO_STORAGE_SKIPLIST_HPP






http://ift.tt/1xKJnbD