Re: Manual reference counting and doubly-linked lists
Re: Manual reference counting and doubly-linked lists
- Subject: Re: Manual reference counting and doubly-linked lists
- From: Uli Kusterer <email@hidden>
- Date: Thu, 15 Nov 2012 13:10:36 +0100
On Nov 15, 2012, at 4:59 AM, William Squires <email@hidden> wrote:
> @interface Thing : NSObject
>
> @property (nonatomic, ???) Thing *nextThing;
> @property (nonatomic, ???) Thing *prevThing;
>
> @end
>
> and somewhere I keep a reference to the 'head' of this doubly-linked list. What should ??? be, "retain", or "assign" in order to work properly? If I was using ARC instead, would they be "strong" or "weak"? Assuming the list doesn't contain circular references (i.e. a<->b<->c<->a) will releasing my 'head' reference properly clean up if I have:
I think you should make one of the two retain (strong), the other assign (weak). E.g. nextThing is strong. That means when you release head, it releases thing1, which then releases its nextThing (thing2) etc., tearing the whole list down like dominoes and not leaking.
However, you can still walk backwards using prevThing. You just have to make sure that when you sever the connection between an object and its nextThing, you also clear their prevThing, or you have a dangling pointer.
You also need to be a bit careful when re-arranging objects. Before you disconnect some object's nextThing, retain the nextThing until you re-insert it, so it doesn't go away.
While theoretically you could have a separate array for the retains and have thing unretained, that would be kind of pointless: You create linked lists for performance reasons, because look-up of the next object is fast. You're kind of defeating that benefit (at least for insertions and removals) if you still use an array to retain them.
Also, NSArray is not a classic C-style linear array. If you look at the performance guarantees Apple gives, they're a little looser. What NSArray actually does internally is switch algorithms depending on how many items you put in it. So you might get a red/black tree (or whatever), or a straight C array, or a linked list already just by using NSArray. Also, look at for( object in collection ) and the fast enumeration stuff, which lets the NSArray be smart about iterating over your list of objects based on its own knowledge of what algorithm it is using.
PS - Objective C is actually not that young ... it's from 1983.
Cheers,
-- Uli Kusterer
"The Witnesses of TeachText are everywhere..."
http://www.zathras.de
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden