View Javadoc

1   /*
2    * Copyright (c) 1998-2002 The Jgroup Team.
3    *
4    * This program is free software; you can redistribute it and/or modify
5    * it under the terms of the GNU Lesser General Public License version 2 as
6    * published by the Free Software Foundation.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU Lesser General Public License for more details.
12   *
13   * You should have received a copy of the GNU Lesser General Public License
14   * along with this program; if not, write to the Free Software
15   * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16   *
17   */
18  
19  package jgroup.relacs.mss;
20  
21  import org.apache.log4j.Logger;
22  
23  
24  
25  /**
26   *  The <code>SWindow</code> class implements the datastructures for a
27   *  sliding window protocol.
28   *
29   *  @author Salvatore Cammarrata
30   *  @author Hein Meling
31   *  @since Jgroup 1.2
32   */
33  final class SWindow
34    implements MssConstants
35  {
36  
37    ////////////////////////////////////////////////////////////////////////////////////////////
38    // Logger
39    ////////////////////////////////////////////////////////////////////////////////////////////
40  
41    /** Obtain logger for this class */
42    private static final Logger log = Logger.getLogger(SWindow.class);
43  
44  
45    ////////////////////////////////////////////////////////////////////////////////////////////
46    // Fields
47    ////////////////////////////////////////////////////////////////////////////////////////////
48  
49    /** Max width of the sliding window */
50    private int maxWindow;
51  
52    /** Left edge of the window */
53    int lastMsgDlvr;
54  
55    /**
56     * Array representing the sliding window, in which a true value
57     * indicates that the message was received, while a false indicates
58     * not yet received.
59     */
60    private boolean[] win;
61  
62  
63    ////////////////////////////////////////////////////////////////////////////////////////////
64    // Constructors
65    ////////////////////////////////////////////////////////////////////////////////////////////
66  
67    SWindow(int maxWindow, int lastMsgDlvr)
68    {
69      this.maxWindow = maxWindow;
70      this.win = new boolean[maxWindow];
71      this.lastMsgDlvr = lastMsgDlvr;
72    }
73  
74  
75    ////////////////////////////////////////////////////////////////////////////////////////////
76    // Methods
77    ////////////////////////////////////////////////////////////////////////////////////////////
78  
79    /**
80     *  Returns true if the given message fragment is within the sliding
81     *  window range; otherwise false is returned.
82     */
83    boolean inWindow(int fid)
84    {
85      return (fid - lastMsgDlvr <= maxWindow);
86    }
87  
88  
89    /**
90     * Returns true if the whole window is unused; that is no messages
91     * have been marked as received in the current window space.  If at
92     * least one message has been received in this window, a false is
93     * returned.
94     */
95    boolean isAllZero()
96    {
97      for (int i = 0; i < win.length; i++) {
98        if (win[i])
99          return false;
100     }
101     return true;
102   }
103 
104 
105   /**
106    *  Shift the window <code>pos</code> bits to the left.
107    */
108   int shift(int pos)
109   {
110     int i;
111     for (i = 0; i < win.length - pos ; i++)
112       win[i] = win[i+pos];
113     for (i = win.length - pos; i < win.length ; i++)
114       win[i] = false;
115     return (lastMsgDlvr += pos);
116   }
117 
118 
119   /**
120    *  Shift the window one bit to the left.
121    */
122   int shift()
123   {
124     return shift(1);
125   }
126 
127 
128   /**
129    *  Shift the window to the left, the number of received (yet
130    *  undelivered) message fragments.  Return the number of messages in
131    *  FIFO order in this sliding window that has been received, yet has
132    *  not been delivered.
133    */
134   int shiftFIFO()
135   {
136     int pos = 0;
137     while (win[pos])
138       pos++;
139     shift(pos);
140     return pos;
141   }
142 
143 
144   /**
145    *  Set the left edge (last message delivered) of the sliding window
146    *  to the given value, and return its previous value.
147    */
148   int setLastMsgDlvr(int le)
149   {
150     int ple = lastMsgDlvr;
151     lastMsgDlvr = le;
152     return ple;
153   }
154 
155 
156   /**
157    *  Return the current left edge (last message delivered) of the
158    *  sliding window.
159    */
160   int getLastMsgDlvr()
161   {
162     return lastMsgDlvr;
163   }
164 
165 
166   /**
167    *  Increment the current left edge by one.
168    */
169   int incLastMsgDlvr()
170   {
171     return (lastMsgDlvr += 1);
172   }
173 
174 
175   /**
176    *  Mark the given fragment as received in the sliding window.
177    */
178   void set(int fid)
179   {
180     if (log.isDebugEnabled())
181       log.debug("fragId=" + fid + " lastMsgDlvr=" + lastMsgDlvr);
182     int pos = fid - lastMsgDlvr - 1;
183     if (pos >= win.length || pos < 0)
184       log.warn("out of bounds - pos: " + pos);
185     else
186       win[pos] = true;
187   }
188 
189 
190   /**
191    *  Mark the given fragment as not received in the sliding window.
192    */
193   void unset(int fid)
194   {
195     if (log.isDebugEnabled())
196       log.debug("fragId=" + fid + " lastMsgDlvr=" + lastMsgDlvr);
197     int pos = fid - lastMsgDlvr - 1;
198     if (pos >= win.length || pos < 0)
199       log.warn("out of bounds - pos: " + pos);
200     else
201       win[pos] = false;
202   }
203 
204 
205   /**
206    *  Obtain the status of the given fragment.  Returns true if the
207    *  fragment has been received; otherwise false.
208    */
209   boolean lookup(int fid)
210   {
211     int pos = fid - lastMsgDlvr - 1;
212     if (pos >= win.length || pos < 0) {
213       log.warn("out of bounds - pos: " + pos);
214       return false;
215     } else {
216       return win[pos];
217     }
218   }
219 
220 
221   /**
222    *  Clear the sliding window state.
223    */
224   void clear(int lastMsgDlvr)
225   {
226     this.lastMsgDlvr = lastMsgDlvr;
227     for (int i = 0 ; i < win.length ; i++)
228       win[i] = false;
229   }
230 
231 
232   ////////////////////////////////////////////////////////////////////////////////////////////
233   // Methods from Object
234   ////////////////////////////////////////////////////////////////////////////////////////////
235 
236   /**
237    *  Returns a string representation of this object
238    */
239   public String toString()
240   {
241     StringBuilder buffer = new StringBuilder();
242     buffer.append("[SWindow: size=");
243     buffer.append(win.length);
244     buffer.append(", lastMsgDlvr=");
245     buffer.append(lastMsgDlvr);
246     buffer.append(", win={");
247     for (int i = 0; i < win.length; i++) {
248       if (i > 0 && win[i])
249         buffer.append(i);
250       buffer.append(win[i] ? (" " + i) : "");
251     }
252     buffer.append("}]");
253     return buffer.toString();
254   }
255 
256 } // END SWindow