Synchronized Linked List Traversal

[Steven Schveighoffer]

On Wed, 20 Jan 2010 19:25:27 -0500, Jonathan Crapuchettes  
<jcrapuchettes at gmail.com> wrote:

> I'm working on a project that requires multi-threading and I am trying  
> to grasp the best way to work with setting up a linked-list where  
> multiple threads might try to be setting the next element in the list at  
> the same time.
>
> What I really need to know is if this will work:
>
> Node!(T) child = parent.firstChild;
> synchronized (child)
> {
>      while (child.sibling !is null)
>          child = child.sibling;
>
>      child.sibling = node;
> }
>
> What I am worried about is that the mutex will not follow the traversal.  
> Any help would be great.

It will not follow the traversal.  Unfortunately, you cannot use the  
synchronized keyword since you cannot do interleaving locks, you must  
manually lock in this pattern:

lock(child)
while(child.sibling !is null)
{
    auto tmp = child;
    child = child.sibling;
    lock(child);
    unlock(tmp);
}
child.sibling = node;
unlock(child);

To do this, you need a manual mutex, look in tango.core.sync.Mutex I think.

But it might also be a better thing to have parent save a pointer to the  
end of the list so you don't traverse the list for every addition...

-Steve