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