#8803 closed patch
COMMON: Managed List
| Reported by: | lordhoto | Owned by: | lordhoto |
|---|---|---|---|
| Priority: | normal | Component: | --Other-- |
| Version: | Keywords: | ||
| Cc: | Game: |
Description
I got to know that some people are asking for a 'managed' List implementation in a common place. Currently lure and parallaction implement their own ManagedList, so we got some code duplication.
This patch adds support to auto free entries of Common::List, when specified. To achieve this it specializes Common::List for pointers and adds a _autoFree flag for it which can be set via the constructor.
The patch also has some downsides and left to be done things:
FIXME: - find a nice solution for copying lists via "operator =" or the copy constructor, currently copied lists always use "_autoFree = false" to prevent double frees.
DOWNSIDES: - currently "operator delete" is used and thus the implementation can not be used for allocated arrays as entries. (maybe it could be added that the user can specify a deletion operator via a template parameter and a function pointer passed via constructor)
There are of course other ways to make Common::List (and also other containers) auto free objects, for example we could implement something like boost::shared_ptr which takes care of freeing the object when no more references are to it exist. This patch is just modelled after the way lure and parallaction are handling it though.
Ticket imported from: #1895703. Ticket imported from: patches/908.
Attachments (4)
Change History (24)
by , 17 years ago
| Attachment: | list.patch added |
|---|
by , 17 years ago
| Attachment: | shared_ptr.patch added |
|---|
comment:1 by , 17 years ago
comment:2 by , 17 years ago
| Owner: | set to |
|---|
comment:3 by , 17 years ago
I would personally support making ManagedList available from the Common namespace, since it is the lighter approach in this case. Anyway, I recognize SharedPtr has broader applications and would be more useful in the medium/long term.
I have some notes/questions about the SharedPtr implementation in the attachment #266964: - it would crash when assigning an uninitialized SharedPtr to another uninitialized SharedPtr (trying to increment an unallocated reference count); - users must be well aware that initializing multiple SharedPtr's with the same pointer will yield multiple reference counts (and that it will be BAD when one of them reaches zero); - why do we need both a templated and non-templated copy constructor and assignment operator? (sorry, I am a template noob)
comment:4 by , 17 years ago
Thread safety: None of our container classes are thread safe, so don't worry about that.
List template specialization: I am a bit vary of doing such a thing, esp. when it introduced subtle semantic difference -- as in this case, were it introduces a constructor parameter which is not normally there, and potentially different behavior, *and* a full duplicate of the List class implementation. Which also means that any fix/improvement made to class List has to be applied to two places. Which in the past often was forgotten in similar scenarios, so I am a bit afraid of extra bit rot creeping in... Code duplication simply is nasty.
But *if* we do it, I say we should just forbid copying of these Lists. I.e. instead of disabling _autofree in the copy constructor, make it non-copyable (e.g. subclass Common::NonCopyable).
All in all I think I would prefer simply moving ManagedList to Common and not try to be "clever" by using template specialization -- IMO it will cause us more problems than it helps.
As for SharedPtr: Well, "smart pointers" can be very powerful and might tools, but they carry their own danger. A minimal *must* for any such class in ScummVM would be a thorough documentation of its semantics. So that would have to be added. Still, this is probably a better solution than the above template specialization.
Note that the operator= in the pointer class seems to have a common bug -- it decs the refcount first before assigning. Hence SharedPtr<Foo> bar = ...; bar = bar; // use bar... will cause a crash. Correct is to first increment r._useCount, then call dec(), as our String class nicely demonstrates. BTW, I'd also suggest aligning name with that (e.g.. decRef instead of dec, _refCount instead of _useCount)
Another bug: the default constructor sets _useCount to 0, but the copy constructor(s) do(es) ++(*_useCount) without any safe guards. Boom.
operator != does actually the same as operator ==
I don't think we should provide the other comparision operators -- at least I can imagine any valid (and portable) reason why one would use "<" on two pointers returned by malloc() / new. Better not to suggest such a thing in the first place.
Why is it useful / beneficial to expose the refcount to client code via a query method?
comment:5 by , 17 years ago
The reason why I choose specialization instead of sub classing is just that I did not like the idea, that, at least with the way lure and parallaction are implementing it, it would just cause compile errors with non pointer types, of course that could be prevented by just specifying the type and then using T* in all the code :-).
The sub classing approach is implemented in ScummVM anyway currently, so I did not attach a patch for it.
Yeah that bug in the operator = and copy constructor code is known, I'll fix it, I thought maybe of adding a special class for reference counting, which could also be used in Common::String and could be made thread safe if there are any needs for it (maybe in audio related client code or backend code).
The templated operator = and copy constructors are for usual casts, so one can do: Common::shared_ptr<A> foo; Common::shared_ptr<B> bar(new B()); foo = bar; if B is derived from A.
The only reason to let the client code query the ref count is debugging actually. Apart from it there is no real reason to have that implemented.
by , 17 years ago
| Attachment: | shared_ptr_v2.patch added |
|---|
comment:6 by , 17 years ago
Appended updated shared_ptr patch. Documentation is still missing. File Added: shared_ptr_v2.patch
by , 17 years ago
| Attachment: | shared_ptr_v3.patch added |
|---|
comment:7 by , 17 years ago
Oops apparently I forgot to update the constructors, done that now... File Added: shared_ptr_v3.patch
comment:8 by , 17 years ago
Argh, now I see why you weren't responding to my "last update" -- apparently, it never got through here. Dammit, I was sure I wrote a reply days ago :/
To recap: * I like SharedPtr a lot, much better than the yucky ManagedList hack * It needs to get a proper Doxygen comment explaining its semantics and how to use it properly * The FilesystemNode class in common/fs.cpp could make use excellent use of SharedPtr to replace its custom ref counting code.
* Common::String uses quite optimized code for memory allocation, else low end systems with slow malloc would slow down to a crawl. Hence it's unlikely that it could share the refcounting code with it. Don't bother with this, it would likely end up as a pointless extra layer of abstraction
* Don't worry about thread safety either. It's not even safe to access an "int" member of a class unless you make it volatile, and even then you should use a mutex to be on the safe side on certain systems. We absolutely require code to use a mutex before it access object members, and Lists etc. are no exception. So again, no need to waste energy on this -- esp. when no gains are apparent in any way.
* What is the idea behind the "unique()" method? Can we ditch it?
comment:9 by , 17 years ago
Yeah I didn't write any Doxygen documentation yet, I'll do that then, since the chances are high to have it accepted.
So we don't even want a subclassed ManagedList like lure and parallaction got?
Yes we could, unique and refCount were just added for debugging and since boost::shared_ptr also contains them (for the same reason IIRC).
Ok that about refcounting and thread safety is fine with me.
comment:10 by , 17 years ago
Re Doxygen: good
ManagedList: My stance on it is this: First off, if we have SharedPtr, and hence can use List<SharedPtr<FOO> > -- is there any reason for having a ManagedList class at all?
ManagedList can be implemented in two ways: Via subclassing, which has drawbacks (like we have to turn some methods into virtual ones, else subtle and hard to track down bugs easily creep in; and we need to duplicate some code). Or using specialization on the List template. Which I think is even more dangerous -- people will simply fail to notice that there are two implementations, one for pointers and one for "normal" stuff. Also, if we have to do two implementations, and hence duplicate the code -- then we could just as well use two different names for the two copies of the code.
So, is there any compelling reason to have a ManagedList "class", once we have SharedPtr?
comment:11 by , 17 years ago
Well ManagedList could be implemented via encapsulating a Common::List as implementation, this would also prevent it from being copied into a Common::List. That's why I asked, also using List<SharedPtr<FOO> > is a bit 'harder' for users not used to SharedPtr or the like.
comment:12 by , 17 years ago
Sure, we could always have a template <class T> class ManagedList : public List<SharedPtr<T> > { }; as a simple "alias".
comment:13 by , 17 years ago
Somehow, I never saw peres comment before, so let me answer to this question a bit delayed :) "- why do we need both a templated and non-templated copy constructor and assignment operator? (sorry, I am a template noob)"
LordHoto already explained why we need the templated operator = and copy constructors. Now, you might wonder why we then need the non-templated ones -- the answer being that the compiler will not recognize these as assignment operator/copy constructor, and hence will provide automatically generated ones, which of course then would break the refcounting.
It's still true that once a pointer has been assigned to a SharedPtr, then it should ideally *never* be used bare-bone again. Both assigning it to a second SharedPtr as well as using it after the last SharedPtr is gone, could cause problems. Hence the doxygen comments are vital.
comment:14 by , 17 years ago
OK, currently we have two different approaches to managed containers: one created by LordHoto, using shared pointers, and one by next_ghost, which subclasses the current classes: Patch #1906528 - "Managed containers" and Patch #1895703 - "COMMON: Managed List"
We can't go forward with both ideas, one of them should be ultimately be chosen. Personally, I like the idea of shared pointers more... what's your opinion? (posting this in both tracker items)
comment:16 by , 17 years ago
So, besides missing Doxygen comments, I think this is good for checkin. I think LordHoto still wants to add some features, but I wonder whether we really need them *now*, or whether those could be added after this is in SVN... ?
comment:17 by , 17 years ago
No the features I plan to add are not needed right now if I see it correctly.
comment:18 by , 17 years ago
| Owner: | changed from to |
|---|---|
| Status: | new → closed |
comment:19 by , 17 years ago
Ok I added documentation for it and committed it now. I will close the track item then, since everyone should now be able to take advanged of 'managed' lists with using Common::SharedPtr.
comment:20 by , 6 years ago
| Component: | → --Other-- |
|---|
I now added a patch which implements a boost::shared_ptr like object, it lacks thread safety, because of the reference counting, but I guess that doesn't matter for ScummVM. The patch also contains a very minimalistic test and a example change in the Kyrandia engine on how to use it.
I'm assigning this tracker entry to Max now since he is usually in charge of our common code. File Added: shared_ptr.patch