001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.util;
014
015 import java.util.Collection;
016 import java.util.Iterator;
017 import java.util.List;
018 import java.util.ListIterator;
019 import org.jikesrvm.VM;
020
021 /**
022 * Implementation of java.util.LinkedList for use in classes that
023 * end up in the boot image.
024 */
025 public final class LinkedListRVM<T> implements List<T> {
026
027 /** Element count */
028 private int count = 0;
029
030 /** pointer to first element in the list */
031 Element<T> head = null;
032
033 /** pointer to last element in the list */
034 Element<T> tail = null;
035
036 /**
037 * Insert an element at a given position in the list.
038 * <p>
039 * UNIMPLEMENTED
040 *
041 * @param pos Position in the list (0..size()-1)
042 * @param entry Element to insert
043 */
044 @Override
045 public void add(int pos, T entry) {
046 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
047 }
048
049 /**
050 * Insert at the tail of the list
051 *
052 * @param entry The entry to add.
053 * @return true (as per java collections framework standard)
054 */
055 @Override
056 public boolean add(final T entry) {
057 final Element<T> element = new Element<T>(entry);
058 element.next = null;
059 if (head == null) {
060 if (VM.VerifyAssertions) VM._assert(tail == null);
061 head = element;
062 element.prev = null;
063 } else {
064 tail.next = element;
065 element.prev = tail;
066 }
067 tail = element;
068 count++;
069 return true;
070 }
071
072 /**
073 * Insert an entry after the given element. Used via the iterator.
074 *
075 * @param e List element
076 * @param t New list entry
077 */
078 void insertAfter(Element<T> e, T t) {
079 Element<T> newElement = new Element<T>(t);
080 if (e == null) {
081 newElement.next = head;
082 newElement.prev = null;
083 head = newElement;
084 } else {
085 newElement.next = e.next;
086 newElement.prev = e;
087 if (e.next != null) {
088 e.next.prev = newElement;
089 }
090 e.next = newElement;
091 }
092 if (tail == null || tail == e) {
093 tail = newElement;
094 }
095 count++;
096 }
097
098 /**
099 * Add all members of the given collection.
100 * <p>
101 * UNIMPLEMENTED
102 */
103 @Override
104 public boolean addAll(Collection<? extends T> arg0) {
105 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
106 return false;
107 }
108
109 /**
110 * Add all members of the given collection after the given element.
111 * <p>
112 * UNIMPLEMENTED
113 */
114 @Override
115 public boolean addAll(int arg0, Collection<? extends T> arg1) {
116 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
117 return false;
118 }
119
120 /**
121 * Discard all entries in the list
122 */
123 @Override
124 public void clear() {
125 head = tail = null;
126 count = 0;
127 }
128
129 /**
130 * Membership test
131 *
132 * @param arg0 Object to check
133 * @return true if the list contains arg0, false otherwise
134 */
135 @Override
136 public boolean contains(Object arg0) {
137 return indexOf(arg0) != -1;
138 }
139
140 /**
141 * Set inclusion test
142 *
143 * @param arg0 Objects to check
144 * @return true if the list contains all objects in arg0, false otherwise
145 */
146 @Override
147 public boolean containsAll(Collection<?> arg0) {
148 for (Object o : arg0) {
149 if (!contains(o)) {
150 return false;
151 }
152 }
153 return true;
154 }
155
156 /**
157 * Return the nth element of the list
158 * <p>
159 * UNIMPLEMENTED
160 * @param index
161 */
162 @Override
163 public T get(int index) {
164 /* Special-case getting the head of the list for speed */
165 if (index == 0 && head != null) {
166 return head.entry;
167 }
168
169 /* bounds check */
170 if (index < 0 || index >= size()) {
171 throw new IndexOutOfBoundsException();
172 }
173
174 Element<T> cursor = head;
175 for (int i = 0; i < index; i++) {
176 cursor = cursor.next;
177 }
178 return cursor.entry;
179 }
180
181 /**
182 * Return the position of the given element.
183 *
184 * @param arg0 Member to test for.
185 * @return Zero-based index of the element, or -1 if not found.
186 */
187 @Override
188 public int indexOf(Object arg0) {
189 int i = 0;
190 for (T t : this) {
191 if (t == arg0) {
192 return i;
193 }
194 i++;
195 }
196 return -1;
197 }
198
199 @Override
200 public boolean isEmpty() {
201 return count == 0;
202 }
203
204 @Override
205 public Iterator<T> iterator() {
206 return new LinkedListIteratorRVM<T>(this);
207 }
208
209 /** UNIMPLEMENTED */
210 @Override
211 public int lastIndexOf(Object arg0) {
212 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
213 return 0;
214 }
215
216 @Override
217 public ListIterator<T> listIterator() {
218 return new LinkedListIteratorRVM<T>(this);
219 }
220
221 /** UNIMPLEMENTED */
222 @Override
223 public ListIterator<T> listIterator(int arg0) {
224 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
225 return null;
226 }
227
228 /**
229 * Remove the nth element of the list.
230 *
231 * @param index n
232 * @return The nth element
233 */
234 @Override
235 public T remove(int index) {
236 /* bounds check */
237 if (index < 0 || index >= size()) {
238 throw new IndexOutOfBoundsException();
239 }
240
241 Element<T> cursor = head;
242 for (int i = 0; i < index; i++) {
243 cursor = cursor.next;
244 }
245 removeInternal(cursor);
246 return cursor.entry;
247 }
248
249 /**
250 * Remove the given element from the list
251 */
252 @Override
253 public boolean remove(Object arg0) {
254 Element<T> cursor = head;
255 while (cursor != null && !(arg0 == null ? cursor.entry == null : cursor.entry.equals(arg0))) {
256 cursor = cursor.next;
257 }
258 if (cursor == null) {
259 return false;
260 } else {
261 removeInternal(cursor);
262 return true;
263 }
264 }
265
266 void removeInternal(Element<T> e) {
267 if (e.prev == null) {
268 if (VM.VerifyAssertions) VM._assert(e == head);
269 head = e.next;
270 } else {
271 e.prev.next = e.next;
272 }
273
274 if (e.next == null) {
275 if (VM.VerifyAssertions) VM._assert(e == tail);
276 tail = e.prev;
277 } else {
278 e.next.prev = e.prev;
279 }
280
281 count--;
282 }
283
284 /** UNIMPLEMENTED */
285 @Override
286 public boolean removeAll(Collection<?> arg0) {
287 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
288 return false;
289 }
290
291 /** UNIMPLEMENTED */
292 @Override
293 public boolean retainAll(Collection<?> arg0) {
294 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
295 return false;
296 }
297
298 /** UNIMPLEMENTED */
299 @Override
300 public T set(int arg0, T arg1) {
301 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
302 return null;
303 }
304
305 @Override
306 public int size() {
307 return count;
308 }
309
310 /** UNIMPLEMENTED */
311 @Override
312 public List<T> subList(int arg0, int arg1) {
313 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
314 return null;
315 }
316
317 /** UNIMPLEMENTED */
318 @Override
319 public Object[] toArray() {
320 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
321 return null;
322 }
323
324 /** UNIMPLEMENTED */
325 @Override
326 public <U> U[] toArray(U[] arg0) {
327 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
328 return null;
329 }
330
331 /**
332 * Class for the actual elements of the list.
333 *
334 *
335 * @param <T> Type of the entry
336 */
337 static class Element<T> {
338 Element<T> next;
339 Element<T> prev;
340 T entry;
341
342 Element(T entry) {
343 this.entry = entry;
344 }
345 }
346 }