references.java

Chord package into p2psim

/***************************************************************************
 *                                                                         *
 *                              References.java                            *
 *                            -------------------                          *
 *   date                 : 16.08.2004                                     *
 *   copyright            : (C) 2004-2008 Distributed and                  *
 *                              Mobile Systems Group                       *
 *                              Lehrstuhl fuer Praktische Informatik       *
 *                              Universitaet Bamberg                       *
 *                              http://www.uni-bamberg.de/pi/              *
 *   email                : [e-mail]                   *
 *                      [e-mail]                 *
 *                                                                         *
 *                                                                         *
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   A copy of the license can be found in the license.txt file supplied   *
 *   with this software or at: http://www.gnu.org/copyleft/gpl.html        *
 *                                                                         *
 ***************************************************************************/
package de.uniba.wiai.lspi.chord.service.impl;

import static de.uniba.wiai.lspi.util.logging.Logger.LogLevel.DEBUG;
import static de.uniba.wiai.lspi.util.logging.Logger.LogLevel.INFO;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import de.uniba.wiai.lspi.chord.com.CommunicationException;
import de.uniba.wiai.lspi.chord.com.Entry;
import de.uniba.wiai.lspi.chord.com.Node;
import de.uniba.wiai.lspi.chord.com.Proxy;
import de.uniba.wiai.lspi.chord.data.ID;
import de.uniba.wiai.lspi.chord.data.URL;
import de.uniba.wiai.lspi.util.logging.Logger;

/**
 * Stores all remote references of nodes the local node is connected to and
 * provides methods for querying and manipulating these references. Makes use of
 * one finger table, one successor list, and one predecessor reference.
 * 
 * @author Karsten Loesing
 * @version 1.0.5
 */
final class References {

	/**
	 * Object logger.
	 */
	private Logger logger;

	/**
	 * This node's finger table.
	 */
	private FingerTable fingerTable = null;

	/**
	 * This node's successor list
	 */
	private SuccessorList successorList = null;

	/**
	 * This node's predecessor.
	 */
	private Node predecessor = null;

	/**
	 * This node's local ID.
	 */
	private ID localID = null;

	private URL localURL = null;

	private Entries entries;

	/**
	 * Creates an References object which contains no references.
	 * 
	 * @param locID
	 *            ID of local node. Must not be <code>null</code>.
	 * @param numberOfEntriesInSuccessorList
	 *            Length of successor list to be created. Must be greater or
	 *            equal 1!
	 * @param entries
	 *            Reference on this nodes' entries which is passed to creation
	 *            of the successor list. Must not be <code>null</code>.   
	 * @throws IllegalArgumentException
	 *             If any parameters is <code>null</code> or 
	 *             if number of entries in successor list is less than 1.
	 */
	References(ID locID, URL locURL, int numberOfEntriesInSuccessorList, Entries entries) {

		if (locURL == null || locID == null || entries == null) {
			throw new IllegalArgumentException(
					"No parameter of constructor may be null!");
		}

		if (numberOfEntriesInSuccessorList < 1)
			throw new IllegalArgumentException(
					"Number of entries in successor list cannot be less than 1! "
							+ numberOfEntriesInSuccessorList
							+ " is not a valid value!");

		this.logger = Logger.getLogger(References.class.getName() + "."
				+ locID);

		this.logger.debug("Logger initialized.");

		// store node id
		this.localID = locID;
		
		this.localURL = locURL; 

		this.entries = entries;

		// create empty finger table and successor list
		this.fingerTable = new FingerTable(locID, this);
		this.successorList = new SuccessorList(locID,
				numberOfEntriesInSuccessorList, this, entries);
	}

	/**
	 * Determines the closest preceding node for the given ID based on finger
	 * table, successor list, and predecessor, but without testing the node's
	 * liveliness.
	 * 
	 * @param key
	 *            ID to find closest preceding node for.
	 * @throws NullPointerException
	 *             If ID is <code>null</code>.
	 * @return Reference on closest preceding node.
	 */
	final synchronized Node getClosestPrecedingNode(ID key) {

		if (key == null) {
			NullPointerException e = new NullPointerException(
					"ID may not be null!");
			this.logger.error("Null pointer", e);
			throw e;
		}

		Map<ID, Node> foundNodes = new HashMap<ID, Node>();
		// determine closest preceding reference of finger table
		Node closestNodeFT = this.fingerTable.getClosestPrecedingNode(key);
		if (closestNodeFT != null) {
			foundNodes.put(closestNodeFT.getNodeID(), closestNodeFT);
		}

		// determine closest preceding reference of successor list
		Node closestNodeSL = this.successorList.getClosestPrecedingNode(key);
		if (closestNodeSL != null) {
			foundNodes.put(closestNodeSL.getNodeID(), closestNodeSL);
		}

		// predecessor is appropriate only if it precedes the given id
		Node predecessorIfAppropriate = null;
		if (this.predecessor != null
				&& key.isInInterval(this.predecessor.getNodeID(), this.localID)) {
			predecessorIfAppropriate = this.predecessor;
			foundNodes.put(this.predecessor.getNodeID(), predecessor);
		}

		// with three references which may be null, there are eight (8) cases we
		// have to enumerate...
		Node closestNode = null;
		List<ID> orderedIDList = new ArrayList<ID>(foundNodes.keySet());
		orderedIDList.add(key);
		int sizeOfList = orderedIDList.size();
		// size of list must be greater than one to not only contain the key.
		// if (sizeOfList > 1) {

		/*
		 * Sort list in ascending order
		 */
		Collections.sort(orderedIDList);
		/*
		 * The list item with one index lower than that of the key must be the
		 * id of the closest predecessor or the key.
		 */
		int keyIndex = orderedIDList.indexOf(key);
		/*
		 * As all ids are located on a ring if the key is the first item in the
		 * list we have to select the last item as predecessor with help of this
		 * calculation.
		 */
		int index = (sizeOfList + (keyIndex - 1)) % sizeOfList;
		/*
		 * Get the references to the node from the map of collected nodes.
		 */
		ID idOfclosestNode = orderedIDList.get(index);
		closestNode = foundNodes.get(idOfclosestNode);
		if (closestNode == null) {
			throw new NullPointerException("closestNode must not be null!");
		}

		/*
		 * Following code is too complicated.
		 */
		// if (closestNodeFT == null) {
		// if (closestNodeSL == null) {
		// if (predecessorIfAppropriate == null) {
		// // no reference is appropriate
		// closestNode = null;
		// } else {
		// // only predecessor is appropriate (case should not occur,
		// // but anyway...
		// closestNode = predecessorIfAppropriate;
		// }
		// } else {
		// if (predecessorIfAppropriate == null) {
		// // only reference of successor list is appropriate
		// closestNode = closestNodeSL;
		// } else {
		// // either predecessor or reference of successor list is
		// // appropriate; determine one of both
		// if (predecessorIfAppropriate.nodeID.isInInterval(
		// closestNodeSL.nodeID, key)) {
		// closestNode = predecessorIfAppropriate;
		// } else {
		// closestNode = closestNodeSL;
		// }
		// }
		// }
		// } else {
		// if (closestNodeSL == null) {
		// if (predecessorIfAppropriate == null) {
		// // only reference of finger table is appropriate
		// closestNode = closestNodeFT;
		// } else {
		// // either predecessor or reference of finger table is
		// // appropriate; determine one of both
		// if (predecessorIfAppropriate.nodeID.isInInterval(
		// closestNodeFT.nodeID, key)) {
		// closestNode = predecessorIfAppropriate;
		// } else {
		// closestNode = closestNodeFT;
		// }
		// }
		// } else {
		// if (predecessorIfAppropriate == null) {
		// // either reference of successor list or reference of finger
		// // table is appropriate; determine one of both
		// if (closestNodeSL.nodeID.isInInterval(closestNodeFT.nodeID,
		// key)) {
		// closestNode = closestNodeSL;
		// } else {
		// closestNode = closestNodeFT;
		// }
		// } else {
		// // either of the three reference is appropriate; determine
		// // first one of the references of successor list and finger
		// // table is more appropriate and afterwards compare with
		// // predecessor
		// if (closestNodeSL.nodeID.isInInterval(closestNodeFT.nodeID,
		// key)) {
		// if (predecessorIfAppropriate.nodeID.isInInterval(
		// closestNodeSL.nodeID, key)) {
		// closestNode = predecessorIfAppropriate;
		// } else {
		// closestNode = closestNodeSL;
		// }
		// } else {
		// if (predecessorIfAppropriate.nodeID.isInInterval(
		// closestNodeFT.nodeID, key)) {
		// closestNode = predecessorIfAppropriate;
		// } else {
		// closestNode = closestNodeFT;
		// }
		// }
		// }
		// }
		// }
		if (this.logger.isEnabledFor(DEBUG)) {
			this.logger.debug("Closest preceding node of ID "
					+ key
					+ " at node "
					+ this.localID.toString()
					+ " is "
					+ closestNode.getNodeID()
					+ " with closestNodeFT="
					+ (closestNodeFT == null ? "null" : ""
							+ closestNodeFT.getNodeID())
					+ " and closestNodeSL="
					+ (closestNodeSL == null ? "null" : ""
							+ closestNodeSL.getNodeID())
					+ " and predecessor (only if it precedes given ID)="
					+ (predecessorIfAppropriate == null ? "null" : ""
							+ predecessorIfAppropriate.getNodeID()));
		}
		return closestNode;
	}

	/**
	 * Adds the given node reference to the finger table and successor list, if
	 * appropriate. The reference is NOT set as predecessor, even if is closer
	 * to this node. Therefore use {@link #addReferenceAsPredecessor(Node)}.
	 * 
	 * @param newReference
	 *            Reference to be added to the local data structures.
	 * @throws NullPointerException
	 *             If the given reference is null.
	 */
	final synchronized void addReference(Node newReference) {

		if (newReference == null) {
			NullPointerException e = new NullPointerException(
					"Node reference to be added must not be null!");
			this.logger.error("Null pointer", e);
			throw e;
		}

		boolean debug = this.logger.isEnabledFor(DEBUG);
		// June 21, 2006. Moved here by sven to avoid failing of checkIfProxy()
		if (newReference.getNodeID().equals(this.localID)) {
			if (debug) {
				this.logger.debug("Reference on myself was not added");
			}
			return;
		}

		// check parameters
		this.checkIfProxy(newReference);

		this.fingerTable.addReference(newReference);
		this.successorList.addSuccessor(newReference);

		if (debug) {
			this.logger.debug("Attempted to add reference "