trouble deleting keys/values on STL hash_map when duplicate keys

Question

I am using C++ hash_map to store some C-style string pairs. And all keys should be unique for this case...

My problem is a serious memory leak when stress testing this over mutliple runs.

When none of these keys in the test are not identical, there is no memory leak. But with identical keys its a different story...

The hash_map (this is Google's sparsehash but it implements the SGI functions entirely)

sparse_hash_map<const char*, char *, hash<const char*>, eqstr> values;

I searched and could not find a function to replace a key/val pair that has an identical key.

values[k]=v;

will only add a new pair, even if the key is the same. (a behavior I think should be toggleable) - this is nothing but a hash_map.insert()

So I have a function to check if the key exists, and if it does replace the val, and if not just add a new pair:

char *confFile::replaceOrStoreVal( char *k, char *v ) {
 char *ret = NULL;
 values.set_deleted_key(_DIST_KEY);
 sparse_hash_map<const char*, char *, hash<const char*>, eqstr>::iterator it = 
    values.find(k);
 if(it == values.end())
   values[k] = v;
 else {

 // ret = it->second;  // option 1
 //it->second = v;     // end option 1

 //option 2
 char *t = (char *) it->first;
 ret = it->second;

 values.erase( iter );  <--- seg fault here
 free(t);
 values[k] = v; // end option 2
}

return ret;
}  ... and ret is later free()ed

initally pairs are added like this:

old = replaceOrStoreVal(recordname, value);

It crashes on the first duplicate key.

2 ways I have tried this. Option 1 results in a segfault on erase (something that also puzzles me). Option 2 just doesnt fix the problem, still have a memory leak. Maybe I am just doing this all wrong.

Yes, I know I could use C++ strings, but I dont want to. Trying to keep this real light, for an embedded system. Any help is appreciated...

Answer 1

Seems like something strange is going on. I suspect you are misusing the hash_map, as what you are doing should work. In fact, what you were doing originally should have worked.

ie.

values[k] = v;

Should replace what was already present with key "k" if it existed.

Might I suggest you replace the usage of Google's sparse_hash_map with the standard STL map? That way you can verify that your algorithm works.

Then, if you replace std::map with sparse_hash_map and it breaks, the problem is either with the sparse_hash_map, or the way you're using it.

Answer 2

You can change a value directly inside hash_map through iterator:

    ret = it->second;

    it->second = v; // end option 2
}

It will be faster and safer solution.

You can also try another hash_map method to erase by key, not by iterator:

size_type erase(const key_type& k)

Answer 3

It turns out my code just had a simple error: I was using the wrong iterator to find the key.

However, a couple of points for people who may run into this:
- you are storing pointers, not the strings. So duplicate keys will absolutely not be deleted (the C strings themselves) unless you do not add add key, and just change the ->second, or erase the entire entry (and its strings)
- you must free() all the string memory for the hash, before the hash itself is destroyed.
- using just values[k]=v repeatedly with duplicate keys will cause a leak.

working function:

char *confFile::replaceOrStoreVal( char *k, char *v ) {
 char *ret = NULL;
 values.set_deleted_key(_DIST_KEY);
 sparse_hash_map<const char*, char *, hash<const char*>, eqstr>::iterator it = 
     values.find(k);
 if(it == values.end())
   values[k] = v;
 else {

 ret = it->second;
 it->second = v;
 free(k); // we dont need this - we already have it stored.

 //   char *t = (char *) it->first;
 //ret = it->second;

 //values.erase( it ); // has a typo here
 //free(t);
 //values[k] = v;
 }

return ret;
}

either method does work. thanks all.