[Bug libstdc++/25896] New: hash_map::erase, unordered_map::erase fail if key is inside the table

[Bug libstdc++/25896] New: hash_map::erase, unordered_map::erase fail if key is inside the table

[mec at google dot com]

This happens with both hash_map and unordered_map and their related classes.  I
know that hash_map is not standard, and unordered_map is in TR1 so not
considered standard yet.

Here is a kernel of the problem:

  hash_map<string,int> c;
  c.insert(...);
  hash_map<string,int>::iterator it = c.find("...");
  c.erase(it->first);

This is deleting by key value, not by iterator.

it->first is a key value which belongs to the collection object.
hash_map::erase(const key&) takes the key by reference.  It delegates to its
rep object, which is a hashtable.  hashtable::ref looks like this in gcc 4.0.2:

  if (__first)
    {
      ...
      while (__next)
        {
          if (_M_equals(_M_get_key(__next->_M_val), __key))
            {
              ...
              _M_delete_node(__next);
              ...
            }
          ...
        }
     ...
    }

The actual key object is in a node of the hash table.  After deleting that
node, the while() loop keeps using the deleted __key value with every other
node in the same bucket.

The following gcc versions have this problem with the following classes:

  gcc 3.4.5
    hash_map, hash_multimap, hash_set, hash_multiset

  gcc 4.0.2
  gcc 4.1-20060106
  gcc 4.2-20060114
    hash_map, hash_multimap, hash_set, hash_multiset
    unordered_map, unordered_multimap, unordered_set, unordered_multiset

You could punt on hash_map and friends because they are non-standard, but it is
nasty to have a case where code compiles and links and runs and then a library
function reads a destroyed object.  unordered_map and friends will eventually
(probably) be standardized so they are more serious.


-- 
           Summary: hash_map::erase, unordered_map::erase fail if key is
                    inside the table
           Product: gcc
           Version: 4.0.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: mec at google dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] hash_map::erase, unordered_map::erase fail if key is inside the table

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-01-21 06:47 -------
I should note that TR1 is a written document.  I am wondering what it says
about this case.  If it says libstdc++ is right, then maybe you should try to
get it fixed (hard because I hear it is close to approval but I could be
wrong).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] hash_map::erase, unordered_map::erase fail if key is inside the table

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-01-21 06:59 -------
I should note that TR1 says erase does take the key by reference.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] hash_map::erase, unordered_map::erase fail if key is inside the table

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2006-01-21 07:21 -------
"Erases all elements with key equivalent to k. Returns the number of elements
erased."
and then:
size_type erase(const key_type& k); 


So from that it might not be a bug in libstdc++ as far as I can see.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] hash_map::erase, unordered_map::erase fail if key is inside the table

[pcarlini at suse dot de]

------- Comment #4 from pcarlini at suse dot de  2006-01-21 10:10 -------
This is a general issue in the standard described in DR 526

  http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html

and prompted by libstdc++/17012 too. I guess the best we can do, is SUSPENDING
both the PRs and making sure DR 526 is discussed as soon as possible by the
LWG.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-01-21 10:10:38
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] hash_map::erase, unordered_map::erase fail if key is inside the table

[pcarlini at suse dot de]

-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |SUSPENDED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] [DR 526] hash_map::erase, unordered_map::erase fail if key is inside the table

[pcarlini at suse dot de]

------- Comment #5 from pcarlini at suse dot de  2007-02-22 19:29 -------
Now that we have a resolution for DR 526:

http://home.twcny.rr.com/hinnant/cpp_extensions/issues_preview/lwg-active.html#526

we can fix this problem too, similarly to like libstdc++/17012.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|SUSPENDED                   |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] [DR 526] hash_map::erase, unordered_map::erase fail if key is inside the table

[paolo at gcc dot gnu dot org]

------- Comment #6 from paolo at gcc dot gnu dot org  2007-02-23 23:34 -------
Subject: Bug 25896

Author: paolo
Date: Fri Feb 23 23:34:18 2007
New Revision: 122276

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122276
Log:
2007-02-23  Paolo Carlini  <pcarlini@suse.de>

        PR libstdc++/25896
        * include/tr1/hashtable (_Hashtable<>::erase(const key_type&)):
        Take care of &_M_extract((*__slot)->_M_v) == &__k.

        * testsuite/tr1/6_containers/unordered_map/erase/1.cc: New.
        * testsuite/tr1/6_containers/unordered_multimap/erase/1.cc: Likewise.
        * testsuite/tr1/6_containers/unordered_multiset/erase/1.cc: Likewise.
        * testsuite/tr1/6_containers/unordered_set/erase/1.cc: Likewise.

Added:
    trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered_map/erase/1.cc
    trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered_multimap/erase/1.cc
    trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered_multiset/erase/1.cc
    trunk/libstdc++-v3/testsuite/tr1/6_containers/unordered_set/erase/1.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/tr1/hashtable


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896

[Bug libstdc++/25896] [DR 526] hash_map::erase, unordered_map::erase fail if key is inside the table

[pcarlini at suse dot de]

------- Comment #7 from pcarlini at suse dot de  2007-02-23 23:35 -------
Fixed.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25896