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

Using javascript map with a function that has two arguments

javascript

I know that I can use map with a function of one variable in the following manner:

Memory issues using ASIHTTPRequest or Image Resizing

iphone file-upload asihttprequest

I can't tell where but I'm having memory issues uploading images to my server. After about 10 or so successful uploads i get memory warnings of level 1 then the next time it quits due DateFormatter...

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.