rice.pastry.leafset
Class LeafSet

java.lang.Object
  java.util.Observable
      rice.pastry.leafset.LeafSet

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<NodeHandle>

public class LeafSet
extends java.util.Observable
implements java.io.Serializable, java.lang.Iterable<NodeHandle>

A class for representing and manipulating the leaf set. The leafset is not strictly a set: when the ring is small, a node may appear in both the cw and the ccw half of the "set".

Version:

$Id: LeafSet.java 4654 2009-01-08 16:33:07Z jeffh $

Author:

Andrew Ladd, Peter Druschel

See Also:

Serialized Form

Constructor Summary

LeafSet(NodeHandle localNode, int size, boolean observe)

LeafSet(NodeHandle localNode, int size, boolean observe, NodeHandle[] cwTable, NodeHandle[] ccwTable)

LeafSet(NodeHandle localNode, int size, RoutingTable rt)
Constructor.

Method Summary

void	addNodeSetListener(NodeSetListener listener) Add observer method.
void	addObserver(java.util.Observer o) Deprecated. use addNodeSetListener
java.util.List<NodeHandle>	asList() If overlaps() a NodeHandle may show up twice.
static LeafSet	build(InputBuffer buf, NodeHandleFactory nhf) So that small LeafSets (who have overlapping nodes) don't waste bandwidth, leafset first defines the NodeHandles to be loaded into an array, then specifies their locations.
int	ccwSize() Gets the current counterclockwise size.
boolean	contains(NodeHandle nh)
LeafSet	copy()
int	cwSize() Gets the current clockwise size.
void	deleteNodeSetListener(NodeSetListener listener) Delete observer method.
void	deleteObserver(java.util.Observer o) Deprecated. use deleteNodeSetListener
void	destroy()
boolean	directTest(NodeHandle handle)
NodeHandle	get(int index) Finds the NodeHandle at a given index.
int	getIndex(NodeHandle nh) There are 2 possible indexes (if the ring is small), the cw index and the ccw, this returns the nearest index, and if they are the same, the cw index.
int	getUniqueCount() Returns the number of unique nodes in the leafset
java.util.Collection<NodeHandle>	getUniqueSet() Set of nodes in the leafset, not the local node, each node only once.
boolean	isComplete()
protected boolean	isProperlyRemoved(NodeHandle handle)
java.util.Iterator<NodeHandle>	iterator() Unordered iterator, does not contain local node.
int	maxSize() Gets the maximal size of the leaf set.
boolean	member(Id nid) Verifies if the set contains this particular id.
boolean	member(NodeHandle nid) Verifies if the set contains this particular handle.
boolean	merge(LeafSet remotels, NodeHandle from, RoutingTable routeTable, boolean testOnly, java.util.Set<NodeHandle> insertedHandles) Merge a remote leafset into this
int	mostSimilar(Id nid) Numerically closests node to a given a node in the leaf set.
NodeSet	neighborSet(int max) compute an ordered set of nodes that are neighbors of this local node, in order of numerical closeness to the local node
boolean	overlaps() Test if the leafset overlaps
boolean	put(NodeHandle handle) Puts a NodeHandle into the set.
boolean	put(NodeHandle handle, boolean suppressNotification)
IdRange	range(NodeHandle n, int r) range computes the range of keys for which node n is a i-root, 0<=i<=r a node is the r-root for a key of the node becomes the numerically closest node to the key when i-roots for the key fail, O<=i
IdRange	range(NodeHandle n, int r, boolean cw) range computes the ranges of keys for which node n is a r-root a node is the r-root for a key of the node becomes the numerically closest node to the key when i-roots for the key fail, O<=i
void	remove(NodeHandle nh) Removes a node id and its handle from the set.
NodeSet	replicaSet(Id key, int max) compute an ordered set of nodes, in order of numerical closeness to a given key
void	serialize(OutputBuffer buf) So that small LeafSets (who have overlapping nodes) don't waste bandwidth, leafset first defines the NodeHandles to be loaded into an array, then specifies their locations.
int	size() Gets the current size of the leaf set.
boolean	test(NodeHandle handle) Test if a put of the given NodeHandle would succeed.
protected boolean	testOtherSet(SimilarSet set, NodeHandle handle)
java.lang.String	toString() Returns a string representation of the leaf set

Methods inherited from class java.util.Observable

clearChanged, countObservers, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LeafSet

public LeafSet(NodeHandle localNode,
               int size,
               RoutingTable rt)

Constructor.

Parameters:

localHandle - the local node

size - the size of the leaf set.

rt - (to fall back on for more entries on delete operations)

LeafSet

public LeafSet(NodeHandle localNode,
               int size,
               boolean observe)

LeafSet

public LeafSet(NodeHandle localNode,
               int size,
               boolean observe,
               NodeHandle[] cwTable,
               NodeHandle[] ccwTable)

Method Detail

put

public boolean put(NodeHandle handle)

Puts a NodeHandle into the set.

Parameters:

handle - the handle to put.

Returns:

true if successful, false otherwise.

put

public boolean put(NodeHandle handle,
                   boolean suppressNotification)

test

public boolean test(NodeHandle handle)

Test if a put of the given NodeHandle would succeed.

Parameters:

handle - the handle to test.

Returns:

true if a put would succeed, false otherwise.

overlaps

public boolean overlaps()

Test if the leafset overlaps

Returns:

true if the most distant cw member appears in the ccw set or vice versa, false otherwise

isComplete

public boolean isComplete()

getIndex

public int getIndex(NodeHandle nh)
             throws java.util.NoSuchElementException

There are 2 possible indexes (if the ring is small), the cw index and the ccw, this returns the nearest index, and if they are the same, the cw index. Note: previous to FP2.1a3, this always returned the cw index if it existed.

Parameters:

nh -

Returns:

Throws:

java.util.NoSuchElementException

get

public NodeHandle get(int index)

Finds the NodeHandle at a given index.

Parameters:

index - an index.

Returns:

the handle associated with that index.

member

public boolean member(NodeHandle nid)

Verifies if the set contains this particular handle.

Parameters:

nid - a NodeHandle.

Returns:

true if that NodeHandle is in the set, false otherwise.

contains

public boolean contains(NodeHandle nh)

member

public boolean member(Id nid)

Verifies if the set contains this particular id.

Parameters:

nid - a node id.

Returns:

true if that node id is in the set, false otherwise.

remove

public void remove(NodeHandle nh)

Removes a node id and its handle from the set.

Parameters:

nid - the node to remove.

maxSize

public int maxSize()

Gets the maximal size of the leaf set.

Returns:

the size.

size

public int size()

Gets the current size of the leaf set. Note that if the leafset overlaps, there will be duplicates. If you want the unique nodes, use getUniqueCount().

Returns:

the size.

cwSize

public int cwSize()

Gets the current clockwise size.

Returns:

the size.

ccwSize

public int ccwSize()

Gets the current counterclockwise size.

Returns:

the size.

mostSimilar

public int mostSimilar(Id nid)

Numerically closests node to a given a node in the leaf set.

Parameters:

nid - a node id.

Returns:

the index of the numerically closest node (0 if baseId is the closest).

neighborSet

public NodeSet neighborSet(int max)

compute an ordered set of nodes that are neighbors of this local node, in order of numerical closeness to the local node

Parameters:

max - the maximal size of the set requested

Returns:

the ordered set of nodehandles

replicaSet

public NodeSet replicaSet(Id key,
                          int max)

compute an ordered set of nodes, in order of numerical closeness to a given key

Parameters:

key - the key

max - the maximal size of the set requested

Returns:

the ordered set of nodehandles

getUniqueCount

public int getUniqueCount()

Returns the number of unique nodes in the leafset

Returns:

the number of unique nodes in the leafset

iterator

public java.util.Iterator<NodeHandle> iterator()

Unordered iterator, does not contain local node. Contains each element only once. TODO: Make this in order from nearest neighbor to farthest neighbor, not by replica, but take cw[0], cc2[0], cw[1], ccw[1] etc...

Specified by:

iterator in interface java.lang.Iterable<NodeHandle>

Returns:

getUniqueSet

public java.util.Collection<NodeHandle> getUniqueSet()

Set of nodes in the leafset, not the local node, each node only once.

Returns:

range

public IdRange range(NodeHandle n,
                     int r)

range computes the range of keys for which node n is a i-root, 0<=i<=r a node is the r-root for a key of the node becomes the numerically closest node to the key when i-roots for the key fail, O<=i

Parameters:

n - the nodehandle

r -

Returns:

the range of keys, or null if n is not a member of the leafset, or if the range cannot be computed

range

public IdRange range(NodeHandle n,
                     int r,
                     boolean cw)

range computes the ranges of keys for which node n is a r-root a node is the r-root for a key of the node becomes the numerically closest node to the key when i-roots for the key fail, O<=i

Parameters:

n - the nodehandle

r -

cw - if true returns the clockwise range, else the counterclockwise range

Returns:

the range of keys, or null if n is not a member of the leafset, or if the range cannot be computed

merge

public boolean merge(LeafSet remotels,
                     NodeHandle from,
                     RoutingTable routeTable,
                     boolean testOnly,
                     java.util.Set<NodeHandle> insertedHandles)

Merge a remote leafset into this

Parameters:

remotels - the remote leafset

from - the node from which we received the leafset

routeTable - the routing table

security - the security manager

testOnly - if true, do not change the leafset

insertedHandles - if not null, a Set that contains, upon return of this method, the nodeHandles that would be inserted into this LeafSet if testOnly is true

Returns:

true if the local leafset changed

addObserver

public void addObserver(java.util.Observer o)

Deprecated. use addNodeSetListener

Add observer method.

Overrides:

addObserver in class java.util.Observable

Parameters:

o - the observer to add.

deleteObserver

public void deleteObserver(java.util.Observer o)

Deprecated. use deleteNodeSetListener

Delete observer method.

Overrides:

deleteObserver in class java.util.Observable

Parameters:

o - the observer to delete.

addNodeSetListener

public void addNodeSetListener(NodeSetListener listener)

Add observer method.

Parameters:

o - the observer to add.

deleteNodeSetListener

public void deleteNodeSetListener(NodeSetListener listener)

Delete observer method.

Parameters:

o - the observer to delete.

toString

public java.lang.String toString()

Returns a string representation of the leaf set

Overrides:

toString in class java.lang.Object

isProperlyRemoved

protected boolean isProperlyRemoved(NodeHandle handle)

testOtherSet

protected boolean testOtherSet(SimilarSet set,
                               NodeHandle handle)

directTest

public boolean directTest(NodeHandle handle)

copy

public LeafSet copy()

build

public static LeafSet build(InputBuffer buf,
                            NodeHandleFactory nhf)
                     throws java.io.IOException

So that small LeafSets (who have overlapping nodes) don't waste bandwidth, leafset first defines the NodeHandles to be loaded into an array, then specifies their locations. We do this because a NodeHandle takes up a lot more space than the index in the leafset, and it may be in the leafset 1 or 2 times. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte theSize +numUniqueHandls+ byte cwSize + byte ccwSize + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle baseHandle + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle 1st + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle numUniqueHandls-th + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte cw 1st + cw 2nd + ... + ccw 1st + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + ccw 2nd + ... + ... + ccw Nth + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Throws:

java.io.IOException

serialize

public void serialize(OutputBuffer buf)
               throws java.io.IOException

So that small LeafSets (who have overlapping nodes) don't waste bandwidth, leafset first defines the NodeHandles to be loaded into an array, then specifies their locations. We do this because a NodeHandle takes up a lot more space than the index in the leafset, and it may be in the leafset 1 or 2 times. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte theSize +numUniqueHandls+ byte cwSize + byte ccwSize + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle baseHandle + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle 1st + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + NodeHandle numUniqueHandls-th + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte cw 1st + cw 2nd + ... + ccw 1st + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + ccw 2nd + ... + ... + ccw Nth + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ TODO 2.23.2006 the synchronization of LeafSet is nonexistent and it's difficult to add because the listeneer interface should not be called while holding a lock, but the lock should be acquired once while making the change

Throws:

java.io.IOException

asList

public java.util.List<NodeHandle> asList()

If overlaps() a NodeHandle may show up twice. Does not return self.

Returns:

list of NodeHandle

destroy

public void destroy()