Miscellaneous Container Templates

insert somehow not working correctly.

Reported by Lailoken on 2010-04-16
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
MCT
Undecided
Unassigned

Bug Description

The following code gives a problem when an item DOES NOT exist in the map already:

ConfigStore::mapped_type& ConfigStore::Get(const key_type& key, const mapped_type& default_value)
{
 boost::recursive_mutex::scoped_lock lock(map_mutex);
 ConfigMap::iterator i = _configMap.find(key);
 if(i != _configMap.end())
 {
  return i->second;
 }
 else
 {
  ConfigStore::mapped_type& newVal = _configMap.insert(std::make_pair(key, default_value)).first->second;
  newVal.dirtySetter = boost::bind(&ConfigStore::dirty, this, _1);
  dirty(true);
  return newVal;
 }
}

Then externally I call :

ConfigStore::mapped_type& value = store.Get("key", default_val);

What happens is that value is valid after the call, but later becomes invalid. This would suggest that what insert returns is somehow not a reference to the actual stored internal value, but rather of another or copy of the internal value.

I've tried it with:

 typedef std::map<key_type, mapped_type> ConfigMap;
 typedef boost::unordered_map<key_type, mapped_type> ConfigMap;

And it works perfectly, just not with:

 typedef mct::closed_hash_map<key_type, mapped_type> ConfigMap;

mapped_type is a class (not pointer) and key_type is unimportant.

Paul Pogonyshev (doublep) wrote :

If I understand correctly, you keep a reference to an element or part of it. This is expected to break with MCT; from documentation:

    Disadvantages:
        * can move data in memory, i.e. invalidate pointers and references;

References/pointers are invalidated exactly when iterators are invalidated (since the latter are just glorified pointers). In other words, during _any_ insert or rehash operation.

Paul Pogonyshev (doublep) wrote :

I added the following text in 'Conceptual Differences' section:

* Rehashing or insertion, which can indirectly cause it, invalidate pointers and
  references to elements, not only iterators. This is because under closed hashing scheme
  all elements are stored in a single memory block.

Paul Pogonyshev (doublep) wrote :

Please clarify if I understood correctly.

Changed in libmct:
status: New → Incomplete

Ok, I missed that. I assumed it would be similar to boost and std_ext's
hashed maps... in that rehashing only invalidated iterators. I guess if it's
documented it can't be a bug.

My implementation relies heavily on the objects not moving after they were
inserted. Perhaps if I realized this sooner I may have designed differently
but as it is, it is too far along to change now. My initial use of your map
was for a lookup-only use... after the initial set-up of the map I never
modified it again, and thus my reference were stable.

This is my second position I was trying to use your map, and I think I'll
just switch back to boost::unordered_map for this since stability of
references at least are guaranteed and I can get the most performance gain
in my situation by keeping references.

Thanks,
Marius.

On Sat, Apr 17, 2010 at 5:38 AM, Paul Pogonyshev <email address hidden> wrote:

> I added the following text in 'Conceptual Differences' section:
>
> * Rehashing or insertion, which can indirectly cause it, invalidate
> pointers and
> references to elements, not only iterators. This is because under closed
> hashing scheme
> all elements are stored in a single memory block.
>
> --
> insert somehow not working correctly.
> https://bugs.launchpad.net/bugs/565116
> You received this bug notification because you are a direct subscriber
> of the bug.
>
> Status in Miscellaneous Container Templates: New
>
> Bug description:
> The following code gives a problem when an item DOES NOT exist in the map
> already:
>
> ConfigStore::mapped_type& ConfigStore::Get(const key_type& key, const
> mapped_type& default_value)
> {
> boost::recursive_mutex::scoped_lock lock(map_mutex);
> ConfigMap::iterator i = _configMap.find(key);
> if(i != _configMap.end())
> {
> return i->second;
> }
> else
> {
> ConfigStore::mapped_type& newVal =
> _configMap.insert(std::make_pair(key, default_value)).first->second;
> newVal.dirtySetter = boost::bind(&ConfigStore::dirty, this,
> _1);
> dirty(true);
> return newVal;
> }
> }
>
> Then externally I call :
>
> ConfigStore::mapped_type& value = store.Get("key", default_val);
>
> What happens is that value is valid after the call, but later becomes
> invalid. This would suggest that what insert returns is somehow not a
> reference to the actual stored internal value, but rather of another or copy
> of the internal value.
>
> I've tried it with:
>
> typedef std::map<key_type, mapped_type> ConfigMap;
> typedef boost::unordered_map<key_type, mapped_type> ConfigMap;
>
> And it works perfectly, just not with:
>
> typedef mct::closed_hash_map<key_type, mapped_type> ConfigMap;
>
> mapped_type is a class (not pointer) and key_type is unimportant.
>
> To unsubscribe from this bug, go to:
> https://bugs.launchpad.net/libmct/+bug/565116/+subscribe
>

Lailoken (lailoken-gmail) wrote :

Indeed you did, and I'm afraid it is I who did not understand what 'closed
hashing' meant, and now understand why the references are not stable after
some RTFA-ing.

I should have paid more attention when this subject was covered back at
University, although I doubt they delved into this detail...

Marius.

On Sun, Apr 18, 2010 at 6:17 AM, Paul Pogonyshev <email address hidden> wrote:

> Please clarify if I understood correctly.
>
> ** Changed in: libmct
> Status: New => Incomplete
>
> --
> insert somehow not working correctly.
> https://bugs.launchpad.net/bugs/565116
> You received this bug notification because you are a direct subscriber
> of the bug.
>
> Status in Miscellaneous Container Templates: Incomplete
>
> Bug description:
> The following code gives a problem when an item DOES NOT exist in the map
> already:
>
> ConfigStore::mapped_type& ConfigStore::Get(const key_type& key, const
> mapped_type& default_value)
> {
> boost::recursive_mutex::scoped_lock lock(map_mutex);
> ConfigMap::iterator i = _configMap.find(key);
> if(i != _configMap.end())
> {
> return i->second;
> }
> else
> {
> ConfigStore::mapped_type& newVal =
> _configMap.insert(std::make_pair(key, default_value)).first->second;
> newVal.dirtySetter = boost::bind(&ConfigStore::dirty, this,
> _1);
> dirty(true);
> return newVal;
> }
> }
>
> Then externally I call :
>
> ConfigStore::mapped_type& value = store.Get("key", default_val);
>
> What happens is that value is valid after the call, but later becomes
> invalid. This would suggest that what insert returns is somehow not a
> reference to the actual stored internal value, but rather of another or copy
> of the internal value.
>
> I've tried it with:
>
> typedef std::map<key_type, mapped_type> ConfigMap;
> typedef boost::unordered_map<key_type, mapped_type> ConfigMap;
>
> And it works perfectly, just not with:
>
> typedef mct::closed_hash_map<key_type, mapped_type> ConfigMap;
>
> mapped_type is a class (not pointer) and key_type is unimportant.
>
> To unsubscribe from this bug, go to:
> https://bugs.launchpad.net/libmct/+bug/565116/+subscribe
>

Paul Pogonyshev (doublep) wrote :

> I guess if it's documented it can't be a bug.

It's simply unavoidable with closed hashing, in the same way as in std::vector (as opposed to, say, std::list).

> This is my second position I was trying to use your map, and I think I'll just switch back to boost::unordered_map

The only active user :(. But I hope you find another use for these maps later on ;)

I'll close this bug as invalid.

Changed in libmct:
status: Incomplete → Invalid
Lailoken (lailoken-gmail) wrote :

On Sun, Apr 18, 2010 at 10:35 AM, Paul Pogonyshev <email address hidden>wrote:

> > I guess if it's documented it can't be a bug.
>
> It's simply unavoidable with closed hashing, in the same way as in
> std::vector (as opposed to, say, std::list).

Yes, I agree. Now that I understand closed hashing better I know why as
well.

> > This is my second position I was trying to use your map, and I think
> I'll just switch back to boost::unordered_map
>
> The only active user :(. But I hope you find another use for these maps
> later on ;)
>

I won't be using it in this instance, but I am still using it in the most
critical of our maps... one that is perfect for closed hashing (Where I
store simple pointers as my mapped_type)

> I'll close this bug as invalid.
>
>
> ** Changed in: libmct
> Status: Incomplete => Invalid
>
> --
> insert somehow not working correctly.
> https://bugs.launchpad.net/bugs/565116
> You received this bug notification because you are a direct subscriber
> of the bug.
>
> Status in Miscellaneous Container Templates: Invalid
>
> Bug description:
> The following code gives a problem when an item DOES NOT exist in the map
> already:
>
> ConfigStore::mapped_type& ConfigStore::Get(const key_type& key, const
> mapped_type& default_value)
> {
> boost::recursive_mutex::scoped_lock lock(map_mutex);
> ConfigMap::iterator i = _configMap.find(key);
> if(i != _configMap.end())
> {
> return i->second;
> }
> else
> {
> ConfigStore::mapped_type& newVal =
> _configMap.insert(std::make_pair(key, default_value)).first->second;
> newVal.dirtySetter = boost::bind(&ConfigStore::dirty, this,
> _1);
> dirty(true);
> return newVal;
> }
> }
>
> Then externally I call :
>
> ConfigStore::mapped_type& value = store.Get("key", default_val);
>
> What happens is that value is valid after the call, but later becomes
> invalid. This would suggest that what insert returns is somehow not a
> reference to the actual stored internal value, but rather of another or copy
> of the internal value.
>
> I've tried it with:
>
> typedef std::map<key_type, mapped_type> ConfigMap;
> typedef boost::unordered_map<key_type, mapped_type> ConfigMap;
>
> And it works perfectly, just not with:
>
> typedef mct::closed_hash_map<key_type, mapped_type> ConfigMap;
>
> mapped_type is a class (not pointer) and key_type is unimportant.
>
> To unsubscribe from this bug, go to:
> https://bugs.launchpad.net/libmct/+bug/565116/+subscribe
>

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers