/* * Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package sun.security.jgss; import org.ietf.jgss.MessageProp;import java.util.LinkedList; /** * A utility class that implements a number list that keeps track of which * tokens have arrived by storing their token numbers in the list. It helps * detect old tokens, out of sequence tokens, and duplicate tokens. * * Each element of the list is an interval [a, b]. Its existence in the * list implies that all token numbers in the range a, a+1, ..., b-1, b * have arrived. Gaps in arrived token numbers are represented by the * numbers that fall in between two elements of the list. eg. {[a,b], * [c,d]} indicates that the token numbers b+1, ..., c-1 have not arrived * yet. * * The maximum number of intervals that we keep track of is * MAX_INTERVALS. Thus if there are too many gaps, then some of the older * sequence numbers are deleted from the list. The earliest sequence number * that exists in the list is the windowStart. The next expected sequence * number, or expectedNumber, is one greater than the latest sequence * number in the list. * * The list keeps track the first token number that should have arrived * (initNumber) so that it is able to detect if certain numbers occur after * the first valid token number but before windowStart. That would happen * if the number of elements (intervals) exceeds MAX_INTERVALS and some * initial elements had  to be deleted. * * The working of the list is optimized for the normal case where the * tokens arrive in sequence. * * @author Mayank Upadhyay * @since 1.4 */public class TokenTracker {     static final int MAX_INTERVALS = 5;     private int initNumber;    private int windowStart;    private int expectedNumber;     private int windowStartIndex = 0;     private LinkedList<Entry> list = new LinkedList<Entry>();     public TokenTracker(int initNumber) {         this.initNumber = initNumber;        this.windowStart = initNumber;        this.expectedNumber = initNumber;         // Make an entry with one less than the expected first token        Entry entry = new Entry(initNumber-1);         list.add(entry);    }     /**     * Returns the index for the entry into which this number will fit. If     * there is none, it returns the index of the last interval     * which precedes this number. It returns -1 if the number needs to be     * a in a new interval ahead of the whole list.     */    private int getIntervalIndex(int number) {        Entry entry = null;        int i;        // Start from the rear to optimize for the normal case        for (i = list.size() - 1; i >= 0; i--) {            entry = list.get(i);            if (entry.compareTo(number) <= 0)                break;        }        return i;    }     /**     * Sets the sequencing and replay information for the given token     * number.     *     * The following represents the number line with positions of     * initNumber, windowStart, expectedNumber marked on it. Regions in     * between them show the different sequencing and replay state     * possibilites for tokens that fall in there.     *     *  (1)      windowStart     *           initNumber               expectedNumber     *              |                           |     *           ---|---------------------------|---     *          GAP |    DUP/UNSEQ              | GAP     *     *     *  (2)       initNumber   windowStart   expectedNumber     *              |               |              |     *           ---|---------------|--------------|---     *          GAP |      OLD      |  DUP/UNSEQ   | GAP     *     *     *  (3)                                windowStart     *           expectedNumber            initNumber     *              |                           |     *           ---|---------------------------|---     *    DUP/UNSEQ |           GAP             | DUP/UNSEQ     *     *     *  (4)      expectedNumber    initNumber   windowStart     *              |               |              |     *           ---|---------------|--------------|---     *    DUP/UNSEQ |        GAP    |    OLD       | DUP/UNSEQ     *     *     *     *  (5)      windowStart   expectedNumber    initNumber     *              |               |              |     *           ---|---------------|--------------|---     *          OLD |    DUP/UNSEQ  |     GAP      | OLD     *     *     *     * (This analysis leaves out the possibility that expectedNumber passes     * initNumber after wrapping around. That may be added later.)     */    synchronized public final void getProps(int number, MessageProp prop) {         boolean gap = false;        boolean old = false;        boolean unsequenced = false;        boolean duplicate = false;         // System.out.println("\n\n==========");        // System.out.println("TokenTracker.getProps(): number=" + number);        // System.out.println(toString());         int pos = getIntervalIndex(number);        Entry entry = null;        if (pos != -1)            entry = list.get(pos);         // Optimize for the expected case:         if (number == expectedNumber) {            expectedNumber++;        } else {             // Next trivial case is to check for duplicate            if (entry != null && entry.contains(number))                duplicate = true;            else {                 if (expectedNumber >= initNumber) {                     // Cases (1) and (2)                     if (number > expectedNumber) {                        gap = true;                    } else if (number >= windowStart) {                        unsequenced = true;                    } else if (number >= initNumber) {                        old = true;                    } else {                        gap = true;                    }                } else {                     // Cases (3), (4) and (5)                     if (number > expectedNumber) {                        if (number < initNumber) {                            gap = true;                        } else if (windowStart >= initNumber) {                            if (number >= windowStart) {                               unsequenced = true;                            } else                                old = true;                        } else {                            old = true;                        }                    } else if (windowStart > expectedNumber) {                        unsequenced = true;                    } else if (number < windowStart) {                        old = true;                    } else                        unsequenced = true;                }            }        }         if (!duplicate && !old)            add(number, pos);         if (gap)            expectedNumber = number+1;         prop.setSupplementaryStates(duplicate, old, unsequenced, gap,                                    0, null);         // System.out.println("Leaving with state:");        // System.out.println(toString());        // System.out.println("==========\n");    }     /**     * Adds the number to the list just after the entry that is currently     * at position prevEntryPos. If prevEntryPos is -1, then the number     * will begin a new interval at the front of the list.     */    private void add(int number, int prevEntryPos) {         Entry entry;        Entry entryBefore = null;        Entry entryAfter = null;         boolean appended = false;        boolean prepended = false;         if (prevEntryPos != -1) {            entryBefore = list.get(prevEntryPos);             // Can this number simply be added to the previous interval?            if (number == (entryBefore.getEnd() + 1)) {                entryBefore.setEnd(number);                appended = true;            }        }         // Now check the interval that follows this number         int nextEntryPos = prevEntryPos + 1;        if ((nextEntryPos) < list.size()) {            entryAfter = list.get(nextEntryPos);             // Can this number simply be added to the next interval?            if (number == (entryAfter.getStart() - 1)) {                if (!appended) {                    entryAfter.setStart(number);                } else {                    // Merge the two entries                    entryAfter.setStart(entryBefore.getStart());                    list.remove(prevEntryPos);                    // Index of any entry following this gets decremented                    if (windowStartIndex > prevEntryPos)                        windowStartIndex--;                }                prepended = true;            }        }         if (prepended || appended)            return;         /*         * At this point we know that the number will start a new interval         * which needs to be added to the list. We might have to recyle an         * older entry in the list.         */         if (list.size() < MAX_INTERVALS) {            entry = new Entry(number);            if (prevEntryPos  < windowStartIndex)                windowStartIndex++; // due to the insertion which will happen        } else {            /*             * Delete the entry that marks the start of the current window.             * The marker will automatically point to the next entry in the             * list when this happens. If the current entry is at the end             * of the list then set the marker to the start of the list.             */            int oldWindowStartIndex = windowStartIndex;            if (windowStartIndex == (list.size() - 1))                windowStartIndex = 0;             entry = list.remove(oldWindowStartIndex);            windowStart = list.get(windowStartIndex).getStart();            entry.setStart(number);            entry.setEnd(number);             if (prevEntryPos >= oldWindowStartIndex) {                prevEntryPos--; // due to the deletion that just happened            } else {                /*                 * If the start of the current window just moved from the                 * end of the list to the front of the list, and if the new                 * entry will be added to the front of the list, then                 * the new entry is the actual window start.                 * eg, Consider { [-10, -8], ..., [-6, -3], [3, 9]}. In                 * this list, suppose the element [3, 9] is the start of                 * the window and has to be deleted to make place to add                 * [-12, -12]. The resultant list will be                 * {[-12, -12], [-10, -8], ..., [-6, -3]} and the new start                 * of the window should be the element [-12, -12], not                 * [-10, -8] which succeeded [3, 9] in the old list.                 */                if (oldWindowStartIndex != windowStartIndex) {                    // windowStartIndex is 0 at this point                    if (prevEntryPos == -1)                        // The new entry is going to the front                        windowStart = number;                } else {                    // due to the insertion which will happen:                    windowStartIndex++;                }            }        }         // Finally we are ready to actually add to the list at index        // 'prevEntryPos+1'         list.add(prevEntryPos+1, entry);    }     public String toString() {        StringBuffer buf = new StringBuffer("TokenTracker: ");        buf.append(" initNumber=").append(initNumber);        buf.append(" windowStart=").append(windowStart);        buf.append(" expectedNumber=").append(expectedNumber);        buf.append(" windowStartIndex=").append(windowStartIndex);        buf.append("\n\tIntervals are: {");        for (int i = 0; i < list.size(); i++) {            if (i != 0)                buf.append(", ");            buf.append(list.get(i).toString());        }        buf.append('}');        return buf.toString();    }     /**     * An entry in the list that represents the sequence of received     * tokens. Each entry is actaully an interval of numbers, all of which     * have been received.     */    class Entry {         private int start;        private int end;         Entry(int number) {            start = number;            end = number;        }         /**         * Returns -1 if this interval represented by this entry precedes         * the number, 0 if the the number is contained in the interval,         * and -1 if the interval occurs after the number.         */        final int compareTo(int number) {            if (start > number)                return 1;            else if (end < number)                return -1;            else                return 0;        }         final boolean contains(int number) {            return (number >= start &&                    number <= end);        }         final void append(int number) {            if (number == (end + 1))                end = number;        }         final void setInterval(int start, int end) {            this.start = start;            this.end = end;        }         final void setEnd(int end) {            this.end = end;        }         final void setStart(int start) {            this.start = start;        }         final int getStart() {            return start;        }         final int getEnd() {            return end;        }         public String toString() {            return ("[" + start + ", " + end + "]");        }     }}