oogp2p.pastry
Class PastryLocation

java.lang.Object
  oogp2p.pastry.PastryLocation

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

PastryFileLocation

public class PastryLocation

extends java.lang.Object

implements java.io.Serializable

Represents a Pastry identifier for a node, object or key. A single identifier and the bit length for Ids is stored in this class. Ids are stored little endian.

Version:

$Id: PastryLocation.java,v 1.7 2003/11/24 19:42:28 sjg Exp $

Author:

Andrew Ladd (orginal), Peter Druschel (original), OOG's

See Also:

Serialized Form

Nested Class Summary

static class

PastryLocation.Distance A class for representing and manipulating the distance between two Ids on the circle.

Field Summary

static int[]	Half
protected int[]	Id
static int	IdBitLength This is the bit length of the node ids.
private java.lang.String	IPaddr
protected static java.security.MessageDigest	md
static int[]	NegOne
protected static int	nlen
static int[]	Null
static int[]	One

Constructor Summary

PastryLocation()
Constructor.

PastryLocation(byte[] material)
Constructor.

PastryLocation(int[] material)
Constructor.

PastryLocation(java.lang.String str)

PastryLocation(java.lang.String IP, int port)
Creates a new PastryLocation from a given IP and port.

Method Summary

private int[]	absDistance(PastryLocation nid) Returns the absolute numerical distance between a pair of Ids.
PastryLocation	add(PastryLocation.Distance offset) Returns an Id corresponding to this Id plus a given distance
PastryLocation	addToId(PastryLocation.Distance offset) Returns an Id corresponding to this Id plus a given distance
void	blit(byte[] target) Blits the Id into a target array.
boolean	checkBit(int i) Checks if the ith bit is flipped.
boolean	clockwise(PastryLocation nid) Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring.
int	compareTo(java.lang.Object obj) Comparison operator for Ids.
byte[]	copy() Copy the Id into a freshly generated array.
PastryLocation.Distance	distance(PastryLocation nid) Returns the shorter numerical distance on the ring between a pair of Ids.
PastryLocation.Distance	distanceFromId(PastryLocation nid) Returns the shorter numerical distance on the ring between a pair of Ids.
boolean	equals(java.lang.Object obj) Equality operator for Ids.
boolean	equals(PastryLocation nid) Equivalence relation for Ids.
protected void	generateFromBytes(byte[] material) Generates the pastry location information given the hash in byte array form.
PastryLocation	getAlternateId(int num, int b, int i) produces a set of ids (keys) that are evenly distributed around the id ring.
PastryLocation	getCCW() gets the Id just counterclockwise from this
PastryLocation	getCW() gets the Id just clockwise from this
int	getDigit(int i, int b) Gets the ith digit in base 2^b.
PastryLocation	getDomainPrefix(int row, int column, int suffixDigit, int b) produces a Id whose prefix up to row is identical to this, followed by a digit with value column, followed by a suffix of digits with value suffixDigits.
static byte[]	getHash(java.lang.String str) Hashes a string.
int[]	getID()
java.net.InetAddress	getIP()
int	hashCode() Hash codes for Ids.
int	indexOfMSDB(PastryLocation nid) Returns the index of the most significant differing bit (MSDB).
int	indexOfMSDD(PastryLocation nid, int base) Returns the index of the most significant different digit (MSDD) in a given base.
private void	invert(int[] dist) inverts the distance value stored in an integer array (computes 0-value)
boolean	isBetween(PastryLocation ccw, PastryLocation cw) Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle
PastryLocation.Distance	longDistance(PastryLocation nid) Returns the longer numerical distance on the ring between a pair of Ids.
PastryLocation.Distance	longDistanceFromId(PastryLocation nid) Returns the longer numerical distance on the ring between a pair of Ids.
static PastryLocation	makeRandomId(java.util.Random rng) Creates a random Id.
static int	numDigits(int base) return the number of digits in a given base
void	setBit(int i, int v) Sets the ith bit to a given value i = 0 is the least significant bit.
void	setDigit(int i, int v, int b) Sets the ith digit in base 2^b.
byte[]	toByteArray() Returns the byte array representation of this Id
java.lang.String	toString() Returns a string representation of the Id in base 16.
java.lang.String	toStringFull() Returns the complete represntation of this Id, in hex.
void	xor(PastryLocation otherId) Xor operator for Ids.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

IPaddr

private java.lang.String IPaddr

md

protected static java.security.MessageDigest md

Null

public static final int[] Null

One

public static final int[] One

NegOne

public static final int[] NegOne

Half

public static final int[] Half

IdBitLength

public static final int IdBitLength

This is the bit length of the node ids. If it is n, then there are 2^n possible different Ids. We currently assume that it is divisible by 32.

See Also:

Constant Field Values

nlen

protected static final int nlen

See Also:

Constant Field Values

Id

protected int[] Id

Constructor Detail

PastryLocation

public PastryLocation(byte[] material)

Constructor.

Parameters:

material - an array of length at least IdBitLength/8 containing raw Id material.

PastryLocation

public PastryLocation(int[] material)

Constructor.

Parameters:

material - an array of length at least IdBitLength/32 containing raw Id material.

PastryLocation

public PastryLocation(java.lang.String IP,
                      int port)

Creates a new PastryLocation from a given IP and port.

Parameters:

IP - string ip in address (not hostname) form

port -

PastryLocation

public PastryLocation(java.lang.String str)

PastryLocation

public PastryLocation()

Constructor. It constructs a new Id with a value of 0 for all bits.

Method Detail

getHash

public static byte[] getHash(java.lang.String str)

Hashes a string. Uses message digest SHA.

Parameters:

str - -- str to be hashed

Returns:

-- a hash of str ina byte array

generateFromBytes

protected void generateFromBytes(byte[] material)

Generates the pastry location information given the hash in byte array form.

Parameters:

material - -- hash value in byte array

numDigits

public static int numDigits(int base)

return the number of digits in a given base

Parameters:

base - the number of bits in the base

Returns:

the number of digits in that base

makeRandomId

public static PastryLocation makeRandomId(java.util.Random rng)

Creates a random Id. For testing purposed only -- should NOT be used to generate real node or object identifiers (low quality of random material).

Parameters:

rng - random number generator

Returns:

a random Id

getIP

public java.net.InetAddress getIP()

getID

public int[] getID()

getCW

public PastryLocation getCW()

gets the Id just clockwise from this

Returns:

The CW value

getCCW

public PastryLocation getCCW()

gets the Id just counterclockwise from this

Returns:

The CCW value

isBetween

public boolean isBetween(PastryLocation ccw,
                         PastryLocation cw)

Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle

Parameters:

ccw - the counterclockwise id

cw - the clockwise id

Returns:

true if this is between ccw (inclusive) and cw (exclusive), false otherwise

getDigit

public int getDigit(int i,
                    int b)

Gets the ith digit in base 2^b. i = 0 is the least significant digit.

Parameters:

i - which digit to get.

b - which power of 2 is the base to get it in.

Returns:

the ith digit in base 2^b.

getDomainPrefix

public PastryLocation getDomainPrefix(int row,
                                      int column,
                                      int suffixDigit,
                                      int b)

produces a Id whose prefix up to row is identical to this, followed by a digit with value column, followed by a suffix of digits with value suffixDigits.

Parameters:

row - the length of the prefix

column - the value of the following digit

suffixDigit - the value of the suffix digits

b - power of 2 of the base

Returns:

the resulting Id

getAlternateId

public PastryLocation getAlternateId(int num,
                                     int b,
                                     int i)

produces a set of ids (keys) that are evenly distributed around the id ring. One invocation produces the i-th member of a set of size num. The set is evenly distributed around the ring, with an offset given by this Id. The set is useful for constructing, for instance, Scribe trees with disjoint sets of interior nodes.

Parameters:

num - the number of Ids in the set (must be <= 2^b)

b - the routing base (as a power of 2)

i - the index of the requested member of the set (0<=iReturns:

the resulting set member, or null in case of illegal arguments

setBit

public void setBit(int i,
                   int v)

Sets the ith bit to a given value i = 0 is the least significant bit.

Parameters:

i - which bit to set.

v - new value of bit

setDigit

public void setDigit(int i,
                     int v,
                     int b)

Sets the ith digit in base 2^b. i = 0 is the least significant digit.

Parameters:

i - which digit to get.

v - the new value of the digit

b - which power of 2 is the base to get it in.

blit

public void blit(byte[] target)

Blits the Id into a target array.

Parameters:

target - an array of length at least IdBitLength/8 for the Id to be stored in.

copy

public byte[] copy()

Copy the Id into a freshly generated array.

Returns:

a fresh copy of the Id material

equals

public boolean equals(java.lang.Object obj)

Equality operator for Ids.

Parameters:

obj - a Id object

Returns:

true if they are equal, false otherwise.

compareTo

public int compareTo(java.lang.Object obj)

Comparison operator for Ids. The comparison that occurs is a numerical comparison.

Parameters:

obj - the Id to compare with.

Returns:

negative if this < obj, 0 if they are equal and positive if this > obj.

toByteArray

public byte[] toByteArray()

Returns the byte array representation of this Id

Returns:

The byte array representation of this id

hashCode

public int hashCode()

Hash codes for Ids.

Returns:

a hash code.

add

public PastryLocation add(PastryLocation.Distance offset)

Returns an Id corresponding to this Id plus a given distance

Parameters:

offset - the distance to add

Returns:

the new Id

distance

public PastryLocation.Distance distance(PastryLocation nid)

Returns the shorter numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

longDistance

public PastryLocation.Distance longDistance(PastryLocation nid)

Returns the longer numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

xor

public void xor(PastryLocation otherId)

Xor operator for Ids. Sets this Id to the bit-wise XOR of itself and otherId

Parameters:

otherId - a Id object

equals

public boolean equals(PastryLocation nid)

Equivalence relation for Ids.

Parameters:

nid - the other node id.

Returns:

true if they are equal, false otherwise.

clockwise

public boolean clockwise(PastryLocation nid)

Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring. An Id is clockwise if it is within the half circle clockwise from this on the ring. An Id is considered counter-clockwise from itself.

Parameters:

nid - The Id we are comparing to

Returns:

true if clockwise, false otherwise.

checkBit

public boolean checkBit(int i)

Checks if the ith bit is flipped. i = 0 is the least significant bit.

Parameters:

i - which bit to check.

Returns:

true if the bit is set, false otherwise.

indexOfMSDB

public int indexOfMSDB(PastryLocation nid)

Returns the index of the most significant differing bit (MSDB).

Parameters:

nid - another node id to compare with.

Returns:

the index of the msdb (0 is the least significant) / will return negative if they do not differ.

indexOfMSDD

public int indexOfMSDD(PastryLocation nid,
                       int base)

Returns the index of the most significant different digit (MSDD) in a given base.

Parameters:

nid - another node id to compare with.

base - the base (as a power of two) to compare in.

Returns:

the index of the msdd (0 is the least significant) / will return negative if they do not differ.

toString

public java.lang.String toString()

Returns a string representation of the Id in base 16. The string is a byte string from most to least significant.

Returns:

A String representation of this Id, abbreviated

toStringFull

public java.lang.String toStringFull()

Returns the complete represntation of this Id, in hex.

Returns:

The complete representation of this Id, in hexadecimal

addToId

public PastryLocation addToId(PastryLocation.Distance offset)

Returns an Id corresponding to this Id plus a given distance

Parameters:

offset - the distance to add

Returns:

the new Id

distanceFromId

public PastryLocation.Distance distanceFromId(PastryLocation nid)

Returns the shorter numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

longDistanceFromId

public PastryLocation.Distance longDistanceFromId(PastryLocation nid)

Returns the longer numerical distance on the ring between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

absDistance

private int[] absDistance(PastryLocation nid)

Returns the absolute numerical distance between a pair of Ids.

Parameters:

nid - the other node id.

Returns:

an int[] containing the distance between this and nid.

invert

private void invert(int[] dist)

inverts the distance value stored in an integer array (computes 0-value)

Parameters:

dist - the distance value