Seg fault of STL like skiplist implementation

Question

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

Answer 1

The mistake is here:

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

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

allocate just allocates memory, it does not initializes it. You have to call construct to initialize it, but only do it for data and not for the other parts of your node.

Thus, you never built the std::list, just allocated memory for it, and so hit undefined behavior when attempting to use this uninitialized memory.