Rice Pastry API

rice.pastry
Class Id

java.lang.Object
  extended by 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)

Rice Pastry API

Copyright © 2001-2005 - Rice Pastry.


Imprint-Dataprotection