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