Re: Locking of nodes in tree for concurrent access



Hello,

below the code of my TupleSpaceNode class. The class won't compile
since referenced classes are not included. But the basic ideas can be
seen from the code. The problem with removing a node that after a take
becomes empty is not yet dealt with in the code snippet below. I
appreciate any input about alternative approaches or possible logical
errors.

Regards, Oliver


public class TupleSpaceNode
{
protected static int LastId = 0;

protected int internalId = -1;

// Use CopyOnWriteArrayList for takeListeners and writeListeners
since rarely objects are added or removed from
// the listeners lists, but they are often being iterated over
during take or write. This way we get around defining locks
// for iterating over these lists iterations.
protected List<TakeListener> takeListeners = new
CopyOnWriteArrayList<TakeListener>();
protected List<WriteListener> writeListeners = new
CopyOnWriteArrayList<WriteListener>();

protected ConcurrentLinkedQueue<Entry> entries = new
ConcurrentLinkedQueue<Entry>();

protected ConcurrentSkipListMap<Comparable<?>, TupleSpaceNode>
children = new ConcurrentSkipListMap<Comparable<?>, TupleSpaceNode>();

public TupleSpaceNode()
{
internalId = ++LastId;
}

public Entry read(Entry template, MatchKeyIterator
matchKeyIterator)
{
TupleSpaceNode node = this;

while (matchKeyIterator.hasNext() && node != null)
node = node.children.get(matchKeyIterator.next());

if (node == null)
return null;

return node.entries.peek();
}

public Entry take(Entry template, MatchKeyIterator
matchKeyIterator)
{
TupleSpaceNode node = this;

while (matchKeyIterator.hasNext() && node != null)
node = node.children.get(matchKeyIterator.next());

if (node == null)
return null;

Entry entry = node.entries.poll();

if (entry != null)
{
invokeTakeListeners(entry);
return entry;
}

return null;
}

public Lease writeSingleton(Entry entry, MatchKeyIterator
matchKeyIterator) throws EntryAlreadyExistsException
{
if (!matchKeyIterator.hasNext())
{
// since writeSingleton can be expected to be used rarely
(inserting flags to deal with concurrency, etc.)
// synchronization using synchronized is considered a good
performance / concurrency trade-off
synchronized (entries)
{
if (entries.isEmpty())
{
entries.add(entry);
invokeWriteListeners(entry);
}
else
throw new EntryAlreadyExistsException(entry);
}
return new DummyLease();
}

TupleSpaceNode child = new TupleSpaceNode();
TupleSpaceNode previousChild =
children.putIfAbsent(matchKeyIterator.next(), child);
if (previousChild != null)
child = previousChild;

return child.writeSingleton(entry, matchKeyIterator);
}

protected void invokeTakeListeners(Entry entry)
{
Iterator<TakeListener> cowIterator = takeListeners.iterator();
while (cowIterator.hasNext())
cowIterator.next().takeFromSpace(entry);
}

protected void invokeWriteListeners(Entry entry)
{
Iterator<WriteListener> cowIterator =
writeListeners.iterator();
while (cowIterator.hasNext())
cowIterator.next().writtenToSpace(entry);
}

public int getInternalId()
{
return internalId;
}

public Lease write(Entry entry, MatchKeyIterator matchKeyIterator)
{
if (!matchKeyIterator.hasNext())
{
entries.add(entry);
invokeWriteListeners(entry);
return new DummyLease();
}

TupleSpaceNode child = new TupleSpaceNode();
TupleSpaceNode previousChild =
children.putIfAbsent(matchKeyIterator.next(), child);
if (previousChild != null)
child = previousChild;

return child.write(entry, matchKeyIterator);
}
}


.