001 /*
002 * $Id: Deque.java,v 1.7 2002/08/11 15:58:00 kredel Exp $
003 */
004
005 //package edu.unima.ky.parallel;
006 package thread;
007
008 import java.io.*;
009
010 /**
011 * This Deque class implements a double ended queue in a
012 * similar way as the class BoundedBuffer does.
013 * It has some capacity to store objects.
014 * With the method <code>put</code> objects are placed into
015 * the buffer. With the <code>get</code> method objects are taken
016 * from the buffer in FIFO order and with <code>pop</code> objects
017 * are taken from the buffer in LIFO order.
018 * <code>put</code> blocks if there is no space to
019 * place a object into the buffer.
020 * <code>get</code> and <code>pop</code> block if there are
021 * no objects in the channel.
022 * This class is safe against Thread InterruptedException.
023 * @author Akitoshi Yoshida
024 * @author Heinz Kredel.
025 * @see BoundedBuffer
026 * see Channel
027 * see Queue
028 * see Deque
029 * see MemoryChannel
030 * see SyncChannel
031 * see Stack
032 */
033
034 public class Deque implements Serializable {
035
036 /**
037 * the buffer is the deque contents.
038 */
039 private Object[] buffer;
040
041 /**
042 * the buffer's size.
043 */
044 private int size;
045
046 /**
047 * index to the first filled cell.
048 */
049 private int front;
050
051 /**
052 * index to the first empty cell.
053 */
054 private int rear;
055
056 /**
057 * a semaphore indicating an empty cell.
058 */
059 private Semaphore empty;
060
061 /**
062 * a semaphore indicating a filled cell.
063 */
064 private Semaphore full;
065
066 /**
067 * mutex for send.
068 */
069 private Object snd;
070
071 /**
072 * mutex for receive.
073 */
074 private Object rcv;
075
076 /**
077 * Declares an undefined value of type <CODE>String</CODE>.
078 */
079 public final static String undefined = "undefined value";
080
081
082 /**
083 * Construct a Deque.
084 * @param init An integer which defines the deques size.
085 */
086 public Deque(int init) {
087 buffer = new Object[init];
088 size = init; front = 0; rear = 0;
089 empty = new Semaphore(init);
090 full = new Semaphore(0);
091 snd = new Object();
092 rcv = new Object();
093 }
094
095
096 /**
097 * Put an object to the deque.
098 * Return without object put if Interrupted.
099 * @exception InterruptedException.
100 */
101 public void put(Object v) throws InterruptedException {
102 empty.P(); // return without Object put if Interrupted
103 synchronized (snd) {
104 if (rear < 0) rear += size;
105 if (rear >= size) rear -= size;
106 buffer[rear] = v;
107 rear++;
108 }
109 full.V();
110 }
111
112
113 /**
114 * Push an object to the deque.
115 * Return without object pushed if Interrupted.
116 * @exception InterruptedException.
117 */
118 public void push(Object v) throws InterruptedException {
119 put(v);
120 }
121
122
123 /**
124 * Get an object from the deque, FIFO order.
125 * @exception InterruptedException.
126 * @return null object if Interrupted.
127 */
128 public Object get() throws InterruptedException {
129 Object v = null;
130 full.P(); // return without Object if Interrupted
131 synchronized (rcv) {
132 if (front >= size) front -= size;
133 v = buffer[front];
134 front++;
135 }
136 empty.V();
137 return v;
138 }
139
140
141 /**
142 * Get an object from the deque within given timeout, FIFO order.
143 * @exception InterruptedException.
144 * @return null object if Interrupted.
145 */
146 public Object get(int m) throws InterruptedException {
147 Object v = null;
148 if ( !full.P(m) ) return undefined;
149 // return without Object if Interrupted
150 synchronized (rcv) {
151 if (front >= size) front -= size;
152 v = buffer[front];
153 front++;
154 }
155 empty.V();
156 return v;
157 }
158
159
160 /**
161 * Pop an object from the deque, LIFO order.
162 * @exception InterruptedException.
163 * @return null object if Interrupted.
164 */
165 public Object pop() throws InterruptedException {
166 Object v = null;
167 full.P(); // return without Object if Interrupted
168 synchronized (snd) {
169 rear--;
170 if (rear < 0) rear += size;
171 if (rear >= size) rear -= size;
172 v = buffer[rear];
173 }
174 empty.V();
175 return v;
176 }
177
178
179 /**
180 * Pop an object from the deque within given timeout, LIFO order.
181 * @exception InterruptedException.
182 * @return null object if Interrupted.
183 */
184 public Object pop(int m) throws InterruptedException {
185 Object v = null;
186 if ( !full.P(m) ) return undefined;
187 // return without Object if Interrupted
188 synchronized (snd) {
189 rear--;
190 if (rear < 0) rear += size;
191 if (rear >= size) rear -= size;
192 v = buffer[rear];
193 }
194 empty.V();
195 return v;
196 }
197
198
199 /**
200 * Tests if the deque is empty.
201 */
202 public boolean empty() {
203 return ( !full.isPositive() );
204 }
205
206
207 /**
208 * Get the number of elements in the deque.
209 * @return size of deque.
210 */
211 public int size() {
212 int s = rear - front;
213 if ( s < 0 ) {
214 s += size;
215 }
216 return s;
217 }
218
219 }