rice.pastry
Class Id

java.lang.Object
  rice.pastry.Id

All Implemented Interfaces:

java.io.Serializable, java.lang.Comparable<Id>, Id, RawSerializable

public class Id
extends java.lang.Object
implements Id, RawSerializable

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. NOTE: Ids are immutable, and are coalesced for memory efficiency. New Ids are to be constructed from the build() methods, which ensure that only one copy of each Id is in memory at a time.

Version:

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

Author:

Andrew Ladd, Peter Druschel, Alan Mislove

See Also:

Serialized Form

Nested Class Summary

static class

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

Field Summary

static int[]	Half
static int	IdBitLength This is the bit length of the node ids.
static int[]	NegOne
static int	nlen
static int[]	Null Distance constants
static int[]	One
static java.lang.String[]	tran The static translation array
static short	TYPE

Constructor Summary

protected

Id(int[] material) Constructor.

Method Summary

Id	add(Id.Distance offset) Returns an Id corresponding to this Id plus a given distance
Id	addToId(Id.Distance offset) Returns an Id corresponding to this Id plus a given distance
void	blit(byte[] target) Blits the Id into a target array.
void	blit(byte[] target, int offset) Blits the distance into a target array, starting at the given offset.
static Id	build() Constructor.
static Id	build(byte[] material) Constructor.
static Id	build(char[] chars, int offset, int length) Constructor, which takes the output of a toStringFull() and converts it back into an Id.
static Id	build(InputBuffer buf) Id (Version 0) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 160 Bit + + + + + + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
static Id	build(int[] material) Constructor.
static Id	build(java.lang.String hex) Constructor, which takes the output of a toStringFull() and converts it back into an Id.
boolean	checkBit(int i) Checks if the ith bit is flipped.
boolean	clockwise(Id nid) Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring.
boolean	clockwise(Id nid) Checks to see if the Id nid is clockwise or counterclockwise from this, on the ring.
int	compareTo(Id obj) Comparison operator for Ids.
byte[]	copy() Copy the Id into a freshly generated array.
Id.Distance	distance(Id nid) Returns the shorter numerical distance on the ring between a pair of Ids.
Id.Distance	distance(Id nid, Id.Distance d)
Id.Distance	distanceFromId(Id nid) Returns the shorter numerical distance on the ring between a pair of Ids.
boolean	equals(Id nid) Equivalence relation for Ids.
boolean	equals(java.lang.Object obj) Equality operator for Ids.
Id	getAlternateId(int num, int b, int i) produces a set of ids (keys) that are evenly distributed around the id ring.
int	getByteArrayLength() Returns the length of the byte[] representing this Id
Id	getCCW() gets the Id just counterclockwise from this
Id	getCW() gets the Id just clockwise from this
int	getDigit(int i, int b) Gets the ith digit in base 2^b.
Id	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.
short	getType()
int	hashCode() Hash codes for Ids.
int	indexOfMSDB(Id nid) Returns the index of the most significant differing bit (MSDB).
int	indexOfMSDD(Id nid, int base) Returns the index of the most significant different digit (MSDD) in a given base.
boolean	isBetween(Id ccw, Id cw) Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle
boolean	isBetween(Id ccw, Id cw) Checks if this Id is between two given ids ccw (inclusive) and cw (exclusive) on the circle
Id.Distance	longDistance(Id nid) Returns the longer numerical distance on the ring between a pair of Ids.
Id.Distance	longDistanceFromId(Id nid) Returns the longer numerical distance on the ring between a pair of Ids.
static void	main(java.lang.String[] args)
static Id	makeRandomId(java.util.Random rng) Creates a random Id.
static Id	makeRandomId(RandomSource rng)
static int	numDigits(int base) return the number of digits in a given base
protected static Id	resolve(java.util.WeakHashMap map, Id id) Method which performs the coalescing and interaction with the weak hash map
void	serialize(OutputBuffer buf) Serialize
byte[]	toByteArray() Returns the byte array representation of this Id
void	toByteArray(byte[] array, int offset) Stores the byte[] value of this Id in the provided byte array
java.lang.String	toString() Returns a string representation of the Id in base 16.
java.lang.String	toStringBare() Similar to toString(), but not wrapped by <0x ..>
java.lang.String	toStringFull() Returns the complete represntation of this Id, in hex.
protected static int[]	trans(byte[] material) Internal method for mapping byte[] -> int[]
protected static byte	trans(char c) Internal method for mapping digit -> num
protected static int[]	trans(java.lang.String hex) Static method for converting the hex representation into an array of ints.

Methods inherited from class java.lang.Object

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

Field Detail

TYPE

public static final short TYPE

See Also:

Constant Field Values

tran

public static final java.lang.String[] tran

The static translation array

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

public static final int nlen

See Also:

Constant Field Values

Null

public static final int[] Null

Distance constants

One

public static final int[] One

NegOne

public static final int[] NegOne

Half

public static final int[] Half

Constructor Detail

Id

protected Id(int[] material)

Constructor.

Parameters:

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

Method Detail

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 Id 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

makeRandomId

public static Id makeRandomId(RandomSource rng)

build

public static Id build(int[] material)

Constructor.

Parameters:

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

build

public static Id build(InputBuffer buf)
                throws java.io.IOException

Id (Version 0) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 160 Bit + + + + + + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Parameters:

buf -

Throws:

java.io.IOException

serialize

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

Description copied from interface: Id

Serialize

Specified by:

serialize in interface Id

Specified by:

serialize in interface RawSerializable

Throws:

java.io.IOException

build

public static Id build(java.lang.String hex)

Constructor, which takes the output of a toStringFull() and converts it back into an Id. Should not normally be used.

Parameters:

hex - The hexadecimal representation from the toStringFull()

build

public static Id build(char[] chars,
                       int offset,
                       int length)

Constructor, which takes the output of a toStringFull() and converts it back into an Id. Should not normally be used.

Parameters:

hex - The hexadecimal representation from the toStringFull()

trans

protected static byte trans(char c)

Internal method for mapping digit -> num

Parameters:

digit - The printed char

num - The byte number

build

public static Id build(byte[] material)

Constructor.

Parameters:

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

trans

protected static int[] trans(byte[] material)

Internal method for mapping byte[] -> int[]

Parameters:

material - The input byte[]

Returns:

THe int[]

build

public static Id build()

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

trans

protected static int[] trans(java.lang.String hex)

Static method for converting the hex representation into an array of ints.

Parameters:

hex - The hexadecimal representation

Returns:

The corresponding int array

resolve

protected static Id resolve(java.util.WeakHashMap map,
                            Id id)

Method which performs the coalescing and interaction with the weak hash map

Parameters:

id - The Id to coalesce

Returns:

The Id to use

getCW

public Id getCW()

gets the Id just clockwise from this

Returns:

The CW value

getCCW

public Id getCCW()

gets the Id just counterclockwise from this

Returns:

The CCW value

isBetween

public boolean isBetween(Id ccw,
                         Id 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 Id 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 Id 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

isBetween

public boolean isBetween(Id ccw,
                         Id cw)

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

Specified by:

isBetween in interface Id

Parameters:

ccw - the counterclockwise id

cw - the clockwise id

Returns:

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

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.

blit

public void blit(byte[] target,
                 int offset)

Blits the distance into a target array, starting at the given offset.

Parameters:

offset - The offset to start at

target - an array of length at least IdBitLength/8 for the distance 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.

Overrides:

equals in class java.lang.Object

Parameters:

obj - a Id object

Returns:

true if they are equal, false otherwise.

compareTo

public int compareTo(Id obj)

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

Specified by:

compareTo in interface java.lang.Comparable<Id>

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

Specified by:

toByteArray in interface Id

Returns:

The byte array representation of this id

toByteArray

public void toByteArray(byte[] array,
                        int offset)

Stores the byte[] value of this Id in the provided byte array

Specified by:

toByteArray in interface Id

getByteArrayLength

public int getByteArrayLength()

Returns the length of the byte[] representing this Id

Specified by:

getByteArrayLength in interface Id

Returns:

The length of the byte[] representing this Id

hashCode

public int hashCode()

Hash codes for Ids.

Overrides:

hashCode in class java.lang.Object

Returns:

a hash code.

add

public Id add(Id.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 Id.Distance distance(Id 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.

distance

public Id.Distance distance(Id nid,
                            Id.Distance d)

longDistance

public Id.Distance longDistance(Id 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.

equals

public boolean equals(Id nid)

Equivalence relation for Ids.

Parameters:

nid - the other node id.

Returns:

true if they are equal, false otherwise.

clockwise

public boolean clockwise(Id 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(Id 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(Id 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. This was updated by Jeff because it was becomming a performance bottleneck.

Overrides:

toString in class java.lang.Object

Returns:

A String representation of this Id, abbreviated

toStringBare

public java.lang.String toStringBare()

Similar to toString(), but not wrapped by <0x ..>

Returns:

toStringFull

public java.lang.String toStringFull()

Returns the complete represntation of this Id, in hex.

Specified by:

toStringFull in interface Id

Returns:

The complete representation of this Id, in hexadecimal

clockwise

public boolean clockwise(Id 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.

Specified by:

clockwise in interface Id

Parameters:

nid - DESCRIBE THE PARAMETER

Returns:

true if clockwise, false otherwise.

addToId

public Id addToId(Id.Distance offset)

Returns an Id corresponding to this Id plus a given distance

Specified by:

addToId in interface Id

Parameters:

offset - the distance to add

Returns:

the new Id

distanceFromId

public Id.Distance distanceFromId(Id nid)

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

Specified by:

distanceFromId in interface Id

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

longDistanceFromId

public Id.Distance longDistanceFromId(Id nid)

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

Specified by:

longDistanceFromId in interface Id

Parameters:

nid - the other node id.

Returns:

the distance between this and nid.

getType

public short getType()

Specified by:

getType in interface Id

main

public static void main(java.lang.String[] args)