SEGV in gcc's std::unordered_map

I have encountered a SEGV in gcc 4.7.2's unordered_map

in find() it calls _M_find_node, which in turn calls _M_find_before_node, passing in the bucket number, the key we're searching for, and the hash code.

In _M_find_before_node, it looks up the first node in the bucket in question:

_BaseNode* __prev_p = _M_buckets[__n];

and then gets the node following this:

_Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);

The problem is that __prev_p->_M_nxt is null; and _M_equals tries to dereference it and causes the seg fault.

I'm not 100% clued up on the inner workings of unordered_map - is it a requirement that the first node in a bucket's _M_nxt be non-null, or is this a bug?

The code in question is here:

  // Find the node whose key compares equal to k in the bucket n. Return nullptr
  // if no node is found.
  template<typename _Key, typename _Value,
       typename _Allocator, typename _ExtractKey, typename _Equal,
       typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
       bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
            _Equal, _H1, _H2, _Hash, _RehashPolicy,
            __chc, __cit, __uk>::_BaseNode*
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
           _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_find_before_node(size_type __n, const key_type& __k,
            typename _Hashtable::_Hash_code_type __code) const
    {
      _BaseNode* __prev_p = _M_buckets[__n];
      if (!__prev_p)
    return nullptr;
      _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); // __p is null here!!
      for (;; __p = __p->_M_next())
    {
      if (this->_M_equals(__k, __code, __p))
        return __prev_p;
      if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
        break;
      __prev_p = __p;
    }
      return nullptr;
    }

Answers


I'm not 100% clued up on the inner workings of unordered_map - is it a requirement that the first node in a bucket's _M_nxt be non-null, or is this a bug?

The question is obviously specific to GCC's implementation, but I'm pretty sure that if _M_buckets[__n] is non-null then _M_buckets[__n]->_M_nxt should be non-null too.

i.e. if the bucket is empty then _M_buckets[__n]==nullptr, if the bucket is non-empty then _M_buckets[__n]->_M_nxt is the first node in the bucket.

Try building with -D_GLIBCXX_DEBUG and see if it identifies a problem with your code, it's possible there's a bug but it's more likely you've corrupted the container somehow or are using it wrong.


Need Your Help

ActiveRecord::Relation hits the Array method instead of my class method

ruby-on-rails scopes

In a Rails 3.2 model, was hoping to create a "to_csv" class method to generate CSV output from an ActiveRecord scope, like this:

Show an Image resource in a WPF window defined in a class library

wpf resources

I have seen this thread: WPF image resources and applied the information there. But my situation seems a bit more tricky:

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.