Re: hash_set core dump on memory free

[James Kanze]

Rupert Kittinger wrote:
> { Note: this article is cross-posted to comp.lang.c++,
> microsoft.public.vc.stl, gnu.g++.help and comp.lang.c++.moderated. -mod }

Which is curious in itself: why microsoft.public.vc.stl, when
the compiler being used is manifestly g++?

> Rakesh schrieb:

> >   What is wrong this implementation? I get a core dump at the free()
> > statement? Thanks

> > #include <ext/hash_map>
> > #include <iostream.h>
> > #include <ext/hash_set>

> > using namespace std;
> > using namespace __gnu_cxx;

> > struct eqstr
> > {
> >   bool operator()(char* s1, char* s2) const
> >   {Variou
> >     return strcmp(s1, s2) == 0;
> >   }
> > };

> > int main()
> > {
> >   char *s, *s1, *temp;
> >   hash_set<char *, hash<char *>, eqstr> AddedPhrases;
> >   hash_set<char*, hash<char*>, eqstr> ::iterator Iter1;

> >   s = (char *)malloc(sizeof(char)*100);
> >   strcpy(s, "apple");
> >   AddedPhrases.insert(s);

> >   s1 = (char *)malloc(sizeof(char)*100);
> >   strcpy(s1, "absent");
> >   AddedPhrases.insert(s1);
> >   for (Iter1 = AddedPhrases.begin(); Iter1 != AddedPhrases.end();
> > Iter1++)
> >   {
> >          temp = *Iter1;
> >          //printf("\nDeleting:%s:%d", temp, strlen(temp));
> >          free(temp);
> >   }
> > }

     [...]
> the problem is that you are freeing an object that is still inside the
> container, but the iterator still tries to access the object during to
> call to operator++().

The problem is that the specifications of hash_set have not been
respected.  There is a requirement that the key value of any
element in the set not be modified.  Although it's not essential
that any particular operation access the key, it's also not
forbidden.

> The reason is that the iterator does not store the
> bucket number, so when the end of the bucket is reached, the hash
> function is called to compute the bucket number.

Which is a legal implementation, given the specifications, even
if it is somewhat surprising.  (Typically, there should only be
one or two elements in each bucket, and recalculating the hash
value each time you change buckets can make incrementation an
expensive operation.)

Of course, even if ++ didn't access the key value, other
functions might (including the destructor).

The important point is that he has a contract with the
container, and he has violated it.

> At this point, hash<char*>() is called with a pointer that no
> longer points to valid memory, so you encounter undefined
> behaviour.

> So you have to erase() the string from the container before calling
> free(), but after calling

> AddedPhrases.erase(Iter1);

> Iter1 is no longer a valid iterator. So the whole loop must be rewritten:

> for (Iter1 = AddedPhrases.begin();
>        Iter1 != AddedPhrases.end();
>        /* do nothing */) { // increment is now performed inside the loop

>            temp = *Iter1++; // increment iterator, then dereference
>                                                 // original value value
>            free(temp);
> }

The "standard" solution when removing objects in a loop is to
update the iterator with the return value of the erase()
function.  This works for multiset and unordered_multiset, as
well as for set and unordered_set.  (The g++ hash_set is a
preliminary version of unordered_set.)

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orientée objet/
                    Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]