Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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)

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2005 - Rice Pastry.