[webkit-dev] We need OwnPtrHashMap

[Maciej Stachowiak]

On Aug 25, 2010, at 1:46 PM, Geoffrey Garen wrote:

>> Sorry for the late-night webkit-dev spam, but in deploying adoptPtr,
>> I've noticed a number of places where have a HashMap that owns its
>> values as OwnPtrs.  Unfortunately, this very clumsy currently.  Each
>> instance of this pattern has its own way of hacking around the
>> problem, which might or might not result in memory errors.  We really
>> should have an OwnPtrHashMap (to complement RefPtrHashMap) that
>> understands how to handle this case correctly.
> 
> To clarify:
> 
> Optimization aside, HashMap<RefPtr<T>, U> and HashMap<T, RefPtr<U> > work just fine. RefPtrHashMap was an optimization. The feature it needed, which HashMap did not provide, was the ability to look up a value by a non-key type (raw pointer), without first converting to key type (RefPtr), since converting to RefPtr would cause refcount churn. We couldn't find a way to do this using HashTraits without using casts that violated strict aliasing rules.
> 
> In contrast, HashMap<OwnPtr<T>, U> and HashMap<T, OwnPtr<U> > don't work at all. They don't compile, since OwnPtr is not copyable. If you made OwnPtr copyable, they would accidentally delete items during get() and resize() operations.

I think it is possible to make a specialization of HashMap that secretly uses a HashMap of raw pointers under the covers. That would fix the copies internal to HashTable. However, you'd have to decide on the correct semantics for get/set operations and possibly tweak their return types. In particular, for an OwnPtr value (likely the common case), you'd want get() to return a raw pointer, set() to take a PassOwnPtr, and take() to return a PassOwnPtr. You probably would not want to use OwnPtr anywhere in the API.

This doesn't quite entirely match the HashMap contract, but it's close enough to be useful.

(Note: I'm probably one of the people with enough template-fu to code this, but I probably won't have time in the very near future.)

> 
> A HashMap that owns its values wants to do something special when an item is overwritten, removed, or implicitly removed by HashMap destruction, but it doesn't want to do anything special when an item is copied or extracted.
> 
> I think the best way to achieve this with HashMap might be a hash trait, rather than literally putting an OwnPtr in the map. Specifically, the trait would be one willRemove callback, which took an iterator to an item, and one willRemoveAll callback, which took a begin iterator. These callbacks would default to empty inline functions.
> 
> But maybe there's a way to use special hash traits and translators to eliminate all or nearly all the C++ copying operations.

I don't think HashTraits is the right solution. It doesn't give as good type safety as a HashMap variant that takes PassOwnPtr for all set/add/whatever type functions. Also, HashTraits are about a type, but whether the HashMap takes single ownership is not intrinsic to the type, it is a question for the individual HashMap. You could validly have one HashMap that owns all its values (of type Foo*) and another HashMap with the same value space that does not. The only error would be multiple HashMaps trying to own the same object. Using PassOwnPtr as the way to transfer ownership to the HashMap would prevent this.

Regards,
Maciej