id.java

pastry的java实现的2.0b版

/*************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate 

Copyright 2002, Rice University. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither  the name  of Rice  University (RICE) nor  the names  of its
contributors may be  used to endorse or promote  products derived from
this software without specific prior written permission.

This software is provided by RICE and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall RICE or contributors be liable
for any direct, indirect, incidental, special, exemplary, or
consequential damages (including, but not limited to, procurement of
substitute goods or services; loss of use, data, or profits; or
business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even
if advised of the possibility of such damage.

********************************************************************************/

package rice.pastry;

import java.io.*;
import java.lang.Comparable;
import java.lang.ref.*;
import java.util.*;

import antlr.InputBuffer;

import rice.environment.random.RandomSource;

/**
 * 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 3274 2006-05-15 16:17:47Z jeffh $
 * @author Andrew Ladd
 * @author Peter Druschel
 * @author Alan Mislove
 */
public class Id implements rice.p2p.commonapi.Id {

  /**
   * The actual contents of this Id
   */
  private int Id[];

  /**
   * DESCRIBE THE FIELD
   */
  public final static short TYPE = 1;

  /**
   * Support for coalesced Ids - ensures only one copy of each Id is in memory
   */
  private static WeakHashMap ID_MAP = new WeakHashMap();

  /**
   * The static translation array
   */
  private static String tran[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};

  /**
   * 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.
   */
  public final static int IdBitLength = 160;
  /**
   * DESCRIBE THE FIELD
   */
  public final static int nlen = IdBitLength / 32;

  /**
   * serialver for backwards compatibility
   */
  final static long serialVersionUID = 2166868464271508935L;

  /**
   * Distance constants
   */
  public final static int[] Null = {0, 0, 0, 0, 0};
  /**
   * DESCRIBE THE FIELD
   */
  public final static int[] One = {1, 0, 0, 0, 0};
  /**
   * DESCRIBE THE FIELD
   */
  public final static int[] NegOne = {-1, -1, -1, -1, -1};
  /**
   * DESCRIBE THE FIELD
   */
  public final static int[] Half = {0x80, 0, 0, 0, 0};

  /**
   * Constructor.
   *
   * @param material an array of length at least IdBitLength/32 containing raw
   *      Id material.
   */
  protected Id(int material[]) {
    Id = new int[nlen];
    for (int i = 0; (i < nlen) && (i < material.length); i++) {
      Id[i] = material[i];
    }
  }


  // ----- NORMAL ID METHODS -----

  /**
   * gets the Id just clockwise from this
   *
   * @return The CW value
   */
  public Id getCW() {
    Distance one = new Distance(One);
    return add(one);
  }

  /**
   * gets the Id just counterclockwise from this
   *
   * @return The CCW value
   */
  public Id getCCW() {
    Distance negone = new Distance(NegOne);
    return add(negone);
  }

  /**
   * Checks if this Id is between two given ids ccw (inclusive) and cw
   * (exclusive) on the circle
   *
   * @param ccw the counterclockwise id
   * @param cw the clockwise id
   * @return true if this is between ccw (inclusive) and cw (exclusive), false
   *      otherwise
   */
  public boolean isBetween(Id ccw, Id cw) {
    if (ccw.equals(cw)) {
      return false;
    }

    if (ccw.clockwise(cw)) {
      return this.clockwise(cw) && !this.clockwise(ccw);
    } else {
      return !this.clockwise(ccw) || this.clockwise(cw);
    }
  }

  /**
   * Gets the ith digit in base 2^b. i = 0 is the least significant digit.
   *
   * @param i which digit to get.
   * @param b which power of 2 is the base to get it in.
   * @return the ith digit in base 2^b.
   */
  public int getDigit(int i, int b) {
    int bitIndex = b * i + (IdBitLength % b);
    int index = bitIndex / 32;
    int shift = bitIndex % 32;

    long val = Id[index];
    if (shift + b > 32) {
      val = (val & 0xffffffffL) | (((long) Id[index + 1]) << 32);
    }

    return ((int) (val >> shift)) & ((1 << b) - 1);
  }

  /**
   * 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.
   *
   * @param row the length of the prefix
   * @param column the value of the following digit
   * @param suffixDigit the value of the suffix digits
   * @param b power of 2 of the base
   * @return the resulting Id
   */
  public Id getDomainPrefix(int row, int column, int suffixDigit, int b) {
    Id res = new Id(Id);

    res.setDigit(row, column, b);
    for (int i = 0; i < row; i++) {
      res.setDigit(i, suffixDigit, b);
    }

    return build(res.Id);
  }


  /**
   * 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.
   *
   * @param num the number of Ids in the set (must be <= 2^b)
   * @param b the routing base (as a power of 2)
   * @param i the index of the requested member of the set (0<=i<num; the 0-th
   *      member is this)
   * @return the resulting set member, or null in case of illegal arguments
   */
  public Id getAlternateId(int num, int b, int i) {
    if (num > (1 << b) || i < 0 || i >= num) {
      return null;
    }

    Id res = new Id(Id);

    int digit = res.getDigit(numDigits(b) - 1, b) + ((1 << b) / num) * i;
    res.setDigit(numDigits(b) - 1, digit, b);

    return build(res.Id);
  }

  // ----- COMMON API SUPPORT -----

  /**
   * Checks if this Id is between two given ids ccw (inclusive) and cw
   * (exclusive) on the circle
   *
   * @param ccw the counterclockwise id
   * @param cw the clockwise id
   * @return true if this is between ccw (inclusive) and cw (exclusive), false
   *      otherwise
   */
  public boolean isBetween(rice.p2p.commonapi.Id ccw, rice.p2p.commonapi.Id cw) {
    return isBetween((Id) ccw, (Id) cw);
  }

  /**
   * Returns the length of the byte[] representing this Id
   *
   * @return The length of the byte[] representing this Id
   */
  public int getByteArrayLength() {
    return (int) IdBitLength / 8;
  }

  /**
   * Gets the Type attribute of the Id object
   *
   * @return The Type value
   */
  public short getType() {
    return TYPE;
  }


  /**
   * Sets the ith bit to a given value i = 0 is the least significant bit.
   *
   * @param i which bit to set.
   * @param v new value of bit
   */
  private void setBit(int i, int v) {
    int index = i / 32;
    int shift = i % 32;
    int val = Id[index];
    int mask = (1 << shift);

    if (v == 1) {
      Id[index] = val | mask;
    } else {
      Id[index] = val & ~mask;
    }
  }


  /**
   * Sets the ith digit in base 2^b. i = 0 is the least significant digit.
   *
   * @param i which digit to get.
   * @param v the new value of the digit
   * @param b which power of 2 is the base to get it in.
   */
  private void setDigit(int i, int v, int b) {
    int bitIndex = b * i + (IdBitLength % b);
    int index = bitIndex / 32;
    int shift = bitIndex % 32;
    int mask = (1 << b) - 1;

    if (shift + b > 32) {
      // digit overlaps a word boundary

      long newd = ((long) (v & mask)) << shift;
      long vmask = ~(((long) mask) << shift);
      long val = Id[index];
      val = (val & 0xffffffffL) | (((long) Id[index + 1]) << 32);

      val = (val & vmask) | newd;

      Id[index] = (int) val;
      Id[index + 1] = (int) (val >> 32);
    } else {
      int newd = (v & mask) << shift;
      int vmask = ~(mask << shift);
      Id[index] = (Id[index] & vmask) | newd;
    }
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param buf DESCRIBE THE PARAMETER
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public void serialize(rice.p2p.commonapi.rawserialization.OutputBuffer buf) throws IOException {
    for (int i = 0; i < Id.length; i++) {
      buf.writeInt(Id[i]);
    }
  }

  /**
   * Define readResolve, which will replace the deserialized object with the
   * canootical one (if one exists) to ensure Id coalescing.
   *
   * @return The real Id
   * @exception ObjectStreamException DESCRIBE THE EXCEPTION
   */
  private Object readResolve() throws ObjectStreamException {
    return resolve(ID_MAP, this);
  }

  /**
   * Blits the Id into a target array.
   *
   * @param target an array of length at least IdBitLength/8 for the Id to be
   *      stored in.
   */
  public void blit(byte target[]) {
    blit(target, 0);
  }

  /**
   * Blits the distance into a target array, starting at the given offset.
   *
   * @param offset The offset to start at
   * @param target an array of length at least IdBitLength/8 for the distance to
   *      be stored in.
   */
  public void blit(byte target[], int offset) {
    for (int j = 0; j < IdBitLength / 8; j++) {
      int k = Id[j / 4] >> ((j % 4) * 8);
      target[offset + j] = (byte) (k & 0xff);
    }
  }

  /**
   * Copy the Id into a freshly generated array.
   *
   * @return a fresh copy of the Id material
   */
  public byte[] copy() {
    byte target[] = new byte[IdBitLength / 8];
    blit(target);
    return target;
  }


  /**
   * Equality operator for Ids.
   *
   * @param obj a Id object
   * @return true if they are equal, false otherwise.
   */
  public boolean equals(Object obj) {
    if ((obj == null) || (!(obj instanceof Id))) {
      return false;
    }

    Id nid = (Id) obj;

    for (int i = 0; i < nlen; i++) {
      if (Id[i] != nid.Id[i]) {
        return false;
      }
    }

    return true;
  }

  /**
   * Comparison operator for Ids. The comparison that occurs is a numerical
   * comparison.
   *
   * @param obj the Id to compare with.
   * @return negative if this < obj, 0 if they are equal and positive if this >
   *      obj.
   */
  public int compareTo(Object obj) {
    Id oth = (Id) obj;

    for (int i = nlen - 1; i >= 0; i--) {
      if (Id[i] != oth.Id[i]) {
        long t = Id[i] & 0x0ffffffffL;
        long o = oth.Id[i] & 0x0ffffffffL;
        if (t < o) {
          return -1;
        } else {
          return 1;
        }
      }
    }

    return 0;
  }

  /**
   * Returns the byte array representation of this Id
   *
   * @return The byte array representation of this id
   */
  public byte[] toByteArray() {
    return copy();
  }