fingertable.java

Chord package into p2psim

/***************************************************************************
 *                                                                         *
 *                             FingerTable.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.HashSet;
import java.util.List;
import java.util.Set;

import de.uniba.wiai.lspi.chord.com.Node;
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 references on the nodes in the finger table and provides methods for
 * querying and manipulating this table.
 * 
 * @author Karsten Loesing
 * @version 1.0.5
 */
final class FingerTable {

	/**
	 * ID of local node.
	 */
	private final ID localID;

	/**
	 * Finger table data.
	 */
	private final Node[] remoteNodes;

	/**
	 * Reference on parent object.
	 */
	private final References references;

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

	/**
	 * Creates an initially empty finger table. The table size is determined by
	 * the given ID's length. A reference on the parent object of type
	 * References is stored for being able to determine and disconnect unused
	 * references after removing them from the table.
	 * 
	 * @param localID
	 *            ID of local node.
	 * @param references
	 *            Reference on parent object.
	 * @throws NullPointerException
	 *             If either of the parameters is <code>null</code>.
	 */
	FingerTable(ID localID, References references) {

		if (localID == null || references == null) {
			throw new NullPointerException(
					"Neither parameter of the constructor may contain a null "
							+ "value!");
		}

		this.logger = Logger.getLogger(FingerTable.class + "." + localID);
		this.logger.debug("Logger initialized.");

		this.references = references;
		this.localID = localID;
		this.remoteNodes = new Node[localID.getLength()];
	}

	/**
	 * Sets one table entry to the given reference.
	 * 
	 * @param index
	 *            Index of table entry.
	 * @param proxy
	 *            Reference to store.
	 * @throws ArrayIndexOutOfBoundsException
	 *             If given index is not contained in the finger table.
	 * @throws NullPointerException
	 *             If given reference is <code>null</code>.
	 */
	private final void setEntry(int index, Node proxy) {

		if (index < 0 || index >= this.remoteNodes.length) {
			ArrayIndexOutOfBoundsException e = new ArrayIndexOutOfBoundsException(
					"setEntry was invoked with an index out of array "
							+ "bounds; index=" + index + ", length of array="
							+ this.remoteNodes.length);
			this.logger.error("Out of bounds!", e);
			throw e;
		}

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

		this.remoteNodes[index] = proxy;

		if (this.logger.isEnabledFor(DEBUG)) {
			this.logger.debug("Entry " + index + " set to " + proxy.toString());
		}
	}

	/**
	 * Returns the reference stored at the given index.
	 * 
	 * @param index
	 *            Index of entry to be returned.
	 * @throws ArrayIndexOutOfBoundsException
	 *             If given index is not contained in the finger table.
	 * @return Reference stored at the given index.
	 */
	private final Node getEntry(int index) {

		if (index < 0 || index >= this.remoteNodes.length) {
			ArrayIndexOutOfBoundsException e = new ArrayIndexOutOfBoundsException(
					"getEntry was invoked with an index out of array "
							+ "bounds; index=" + index + ", length of array="
							+ this.remoteNodes.length);
			this.logger.error("Out of bounds!", e);
			throw e;
		}

		return this.remoteNodes[index];
	}

	/**
	 * Sets the reference at the given index to <code>null</code> and triggers
	 * to disconnect that node, if no other reference to it is kept any more.
	 * 
	 * @param index
	 *            Index of entry to be set to <code>null</code>.
	 * @throws ArrayIndexOutOfBoundsException
	 *             If given index is not contained in the finger table.
	 */
	private final void unsetEntry(int index) {
		if (index < 0 || index >= this.remoteNodes.length) {
			ArrayIndexOutOfBoundsException e = new ArrayIndexOutOfBoundsException(
					"unsetEntry was invoked with an index out of array "
							+ "bounds; index=" + index + ", length of array="
							+ this.remoteNodes.length);
			this.logger.error("Out of bounds!", e);
			throw e;
		}

		// remember overwritten reference
		Node overwrittenNode = this.getEntry(index);

		// set reference to null
		this.remoteNodes[index] = null;

		if (overwrittenNode == null) {
			this.logger.debug("unsetEntry did not change anything, because "
					+ "entry was null before.");
		} else {
			// check if overwritten reference does not exist any more
			this.references.disconnectIfUnreferenced(overwrittenNode);
			if (this.logger.isEnabledFor(DEBUG)) {
				this.logger.debug("Entry set to null: index=" + index
						+ ", overwritten node=" + overwrittenNode.toString());
			}
		}
	}

	/**
	 * Adds the given reference to all finger table entries of which the start
	 * index is in the interval (local node ID, new node ID) and of which the
	 * current entry is <code>null</code> or further away from the local node
	 * ID than the new node ID (ie. the new node ID is in the interval (local
	 * node ID, currently stored node ID) ).
	 * 
	 * @param proxy
	 *            Reference to be added to the finger table.
	 * @throws NullPointerException
	 *             If given reference is <code>null</code>.
	 */
	final void addReference(Node proxy) {

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

		// for logging
		int lowestWrittenIndex = -1;
		int highestWrittenIndex = -1;

		for (int i = 0; i < this.remoteNodes.length; i++) {

			ID startOfInterval = this.localID.addPowerOfTwo(i);
			if (!startOfInterval.isInInterval(this.localID, proxy.getNodeID())) {
				break;
			}

			// for logging
			if (lowestWrittenIndex == -1) {
				lowestWrittenIndex = i;
			}
			highestWrittenIndex = i;

			if (getEntry(i) == null) {
				setEntry(i, proxy);
			} else if (proxy.getNodeID().isInInterval(this.localID,
					getEntry(i).getNodeID())) {
				Node oldEntry = getEntry(i);
				setEntry(i, proxy);
				this.references.disconnectIfUnreferenced(oldEntry);
			}
		}

		// logging
		if (this.logger.isEnabledFor(DEBUG)) {
			if (highestWrittenIndex == -1) {

				this.logger
						.debug("addReference did not add the given reference, "
								+ "because it did not fit anywhere!");

			}
		}
		if (this.logger.isEnabledFor(INFO)) {
			if (highestWrittenIndex == lowestWrittenIndex) {

				this.logger.info("Added reference to finger table entry "
						+ highestWrittenIndex);