fingertable.java

High performance DB query

/*
 * @(#)$Id: FingerTable.java,v 1.7 2004/08/20 20:53:15 huebsch Exp $
 *
 * Copyright (c) 2001-2004 Regents of the University of California.
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached BERKELEY-LICENSE
 * file. If you do not find these files, copies can be found by writing to:
 * Computer Science Division, Database Group, Universite of California,
 * 617 Soda Hall #1776, Berkeley, CA 94720-1776. Attention: Berkeley License
 *
 * Copyright (c) 2003-2004 Intel Corporation. All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE file.
 * If you do not find these files, copies can be found by writing to:
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300,
 * Berkeley, CA, 94704.  Attention:  Intel License Inquiry.
 */


package overlay.location.chord;

import java.net.InetSocketAddress;
import java.util.ArrayList;
import services.LocalNode;
import util.BitID;

/** A class representing a chord FingerTable and all the operations that can be performed on it.  All operations are with respect to the Chord class that creates this table */
public class FingerTable {

    private BitID id;
    private InetSocketAddress address;
    private Finger selfFinger;
    private int maxFingers;
    private double lifetime;
    private double latencyWeight;
    private ArrayList fingers;

    /**
     * Constructor FingerTable
     *
     * @param id
     * @param address
     * @param maxFingers
     * @param lifetime
     * @param latencyWeight
     */
    public FingerTable(BitID id, InetSocketAddress address, int maxFingers,
                       double lifetime, double latencyWeight) {
        this.id = id;
        this.address = address;
        this.maxFingers = maxFingers;
        this.lifetime = lifetime;
        this.latencyWeight = latencyWeight;
        fingers = new ArrayList();
        selfFinger = new Finger(address, id, 0, 0, 0);
    }

    /**
     * Method getSelfFinger
     * @return
     */
    public Finger getSelfFinger() {
        return selfFinger;
    }

    /**
     * Method getSuccessor
     * @return
     */
    public Finger getSuccessor() {
        if (fingers.size() > 0) {
            return (Finger) fingers.get(0);
        }

        return selfFinger;
    }

    /**
     * Method getPredecessor
     * @return
     */
    public Finger getPredecessor() {
        if (fingers.size() > 0) {
            return (Finger) fingers.get(fingers.size() - 1);
        }

        return selfFinger;
    }

    /**
     * Method insertFinger
     *
     * @param newFingerID
     * @param newFingerAddr
     * @param latency
     */
    public void insertFinger(BitID newFingerID,
                             InetSocketAddress newFingerAddr, double latency) {
        Finger theFinger = getFinger(newFingerID);

        if (theFinger != null) {
            update(theFinger, latency);
        } else {
            double curTime = LocalNode.myTimer.getCurrentTime();

            theFinger = new Finger(newFingerAddr, newFingerID, curTime,
                                   curTime + lifetime, latency);

            insertFinger(theFinger);
        }
    }

    private void insertFinger(Finger newFinger) {

        // Cleanup old fingers
        clean();

        // Do not insert a self finger
        if (newFinger.getID().equals(id)) {
            return;
        }

        // If table is full, make room for a new finger
        if (fingers.size() > maxFingers) {
            evict();
        }

        // If table is empty, simply add to front
        if (fingers.size() == 0) {
            fingers.add(newFinger);

            return;
        }

        // Check if this my successor
        if (newFinger.getID().inRange(id, ((Finger) (fingers.get(0))).getID(),
                                      false, false)) {
            fingers.add(0, newFinger);

            return;
        }

        // Place in correct spot (ascending clockwise upward)
        Finger prev = (Finger) fingers.get(0);

        for (int i = 1; i < fingers.size(); i++) {
            Finger cur = (Finger) fingers.get(i);

            if (newFinger.getID().inRange(prev.getID(), cur.getID(), false,
                                          false)) {
                fingers.add(i, newFinger);

                return;
            }

            prev = cur;
        }

        // Append to end
        fingers.add(newFinger);
    }

    /* Remove any expired fingers */
    private void clean() {
        double curtime = LocalNode.myTimer.getCurrentTime();
        Finger f;
        int size = fingers.size() - 2;    // Do not remove predecessor

        for (int i = 1; i < size; i++) {
            f = (Finger) (fingers.get(i));

            if (f.getExpiration() < curtime) {
                remove(f);

                i--;
                size--;
            }
        }
    }

    /** Remove finger f from the list */
    private void remove(Finger theFinger) {
        int index = fingers.indexOf(theFinger);

        if (index >= 0) {
            fingers.remove(index);
        }
    }

    /** Remove the least-recently-updated finger */
    private void evict() {
        double time = Double.MAX_VALUE;
        Finger oldest = null;
        Finger curFinger;
        int size = fingers.size() - 2;    // Do not remove the predecessor

        for (int i = 1; i < size; i++) {    // Do not remove successor
            curFinger = (Finger) (fingers.get(i));

            if (curFinger.getLastUpdate() < time) {
                oldest = curFinger;
                time = curFinger.getLastUpdate();
            }
        }

        remove(oldest);
    }

    /**
     * Get the finger with id id
     *
     * @param id
     * @return
     */
    public Finger getFinger(BitID id) {
        for (int i = 0; i < fingers.size(); i++) {
            if (((Finger) (fingers.get(i))).getID().equals(id)) {
                return (Finger) fingers.get(i);
            }
        }

        return null;
    }

    /**
     * Reset the expiry time on a finger
     *
     * @param theFinger
     * @param latency
     */
    public void update(Finger theFinger, double latency) {
        double curtime = LocalNode.myTimer.getCurrentTime();

        theFinger.setLastUpdate(curtime);
        theFinger.setExpiration(curtime + lifetime);
        theFinger.setLatency(latency);
        clean();
    }

    /**
     * Return a copy of this finger table.
     * @return
     */
    public Finger[] copy() {
        Finger[] clonedTable = new Finger[fingers.size()];

        for (int i = fingers.size(); i >= 0; i--) {
            clonedTable[i] = (Finger) (((Finger) fingers.get(i)).clone());
        }

        return clonedTable;
    }

    /**
     * Method getPredecessorValue
     *
     * @param goal
     * @param predecessor
     * @return
     */
    public double getPredecessorValue(BitID goal, Finger predecessor) {
        return 0;
    }

    /**
     * Method getBestPredecessor
     *
     * @param goal
     * @param currentGuess
     * @return
     */
    public Finger getBestPredecessor(BitID goal, Finger currentGuess) {
        int numFingers = fingers.size();

        if (numFingers == 0) {
            return selfFinger;
        }

        Finger curFinger = getSuccessor();

        if (goal.inRange(id, curFinger.getID(), false, true)) {
            return curFinger;
        }

        for (int i = 0; i < (numFingers - 1); i++) {
            curFinger = (Finger) fingers.get(i);

            if (goal.inRange(curFinger.getID(),
                             (((Finger) fingers.get(i + 1))).getID(), false,
                             true)) {
                return curFinger;
            }
        }

        return (Finger) fingers.get(numFingers - 1);
    }

    /**
     * Method size
     * @return
     */
    protected int size() {
        return fingers.size();
    }

    /**
     * Method toString
     * @return
     */
    public String toString() {
        String outStr = "<FingerTable: ";

        for (int i = 0; i < fingers.size(); i++) {
            outStr += "[" + fingers.get(i) + "]";
        }

        outStr += ">";

        return outStr;
    }
}