001: /*
002: * Copyright (c) 2001 by Matt Welsh and The Regents of the University of
003: * California. All rights reserved.
004: *
005: * Permission to use, copy, modify, and distribute this software and its
006: * documentation for any purpose, without fee, and without written agreement is
007: * hereby granted, provided that the above copyright notice and the following
008: * two paragraphs appear in all copies of this software.
009: *
010: * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
011: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
012: * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
013: * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
014: *
015: * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
016: * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
017: * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
018: * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
019: * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
020: *
021: * Author: Matt Welsh <mdw@cs.berkeley.edu>
022: *
023: */
024:
025: package seda.sandStorm.core;
026:
027: /**
028: * The ssLinkedList class is just that - a linked list abstraction that
029: * supports very efficient insertion and deletion, as well as an
030: * Enumeration interface. None of the methods in this linked list are
031: * synchronized. If you want synchronization, do it yourself.
032: *
033: * @author Steve Gribble
034: */
035: public class ssLinkedList {
036:
037: private int num_in_list;
038: private ssLinkedListElement first;
039: private ssLinkedListElement last;
040:
041: // some private variables to maintain a heap of elements for fast
042: // allocation
043: private ssLinkedListElement lle_heap[];
044: private int num_in_lle_heap;
045: private static final int HEAP_ALLOC_NUM = 5;
046:
047: /**
048: * This inner class is the chaining mechanism for the linked list
049: */
050: private class ssLinkedListElement {
051: public Object obj;
052: protected ssLinkedListElement prev, next;
053:
054: public ssLinkedListElement(Object o) {
055: prev = next = null;
056: obj = o;
057: }
058:
059: }
060:
061: /**
062: * A ssLinkedListEnumeration is a java.util.Enumeration over the
063: * ssLinkedList elements.
064: *
065: * @see java.util.Enumeration
066: */
067: public class ssLinkedListEnumeration implements
068: java.util.Enumeration {
069: private ssLinkedListElement curElement;
070:
071: public ssLinkedListEnumeration() {
072: curElement = ssLinkedList.this .first;
073: }
074:
075: // the enumeration methods
076: public boolean hasMoreElements() {
077: if (curElement == null)
078: return false;
079: return true;
080: }
081:
082: public Object nextElement()
083: throws java.util.NoSuchElementException {
084: Object retme;
085:
086: if (curElement == null)
087: throw new java.util.NoSuchElementException();
088: retme = curElement.obj;
089: curElement = curElement.next;
090: return retme;
091: }
092: }
093:
094: private static ssLinkedListEqualityComparator ll_equality_comparator = new ssLinkedListEqualityComparator();
095:
096: /**
097: * Allocates a brand new ssLinkedList
098: */
099: public ssLinkedList() {
100: num_in_list = 0;
101: first = last = null;
102: lle_heap = new ssLinkedListElement[HEAP_ALLOC_NUM];
103: num_in_lle_heap = 0;
104: }
105:
106: // heap o' elements - we'll try to keep no more than 25 cached
107:
108: private ssLinkedListElement alloc_lle(Object o) {
109: ssLinkedListElement retel;
110:
111: if (num_in_lle_heap == 0) {
112: for (int i = 0; i < HEAP_ALLOC_NUM; i++) {
113: lle_heap[i] = new ssLinkedListElement(null);
114: num_in_lle_heap++;
115: }
116: }
117:
118: num_in_lle_heap--;
119: retel = lle_heap[num_in_lle_heap];
120: retel.obj = o;
121: return retel;
122: }
123:
124: private void free_lle(ssLinkedListElement lle) {
125: if (num_in_lle_heap < HEAP_ALLOC_NUM) {
126: lle_heap[num_in_lle_heap] = lle;
127: num_in_lle_heap++;
128: lle.next = lle.prev = null;
129: lle.obj = null;
130: }
131: }
132:
133: /**
134: * Returns the number of elements in the list
135: *
136: * @return number of elements in the list
137: */
138: public int size() {
139: return num_in_list;
140: }
141:
142: /**
143: * Adds an object to the tail (end) of the linked list.
144: *
145: * @param o the object to add
146: */
147: public void add_to_tail(Object o) {
148: ssLinkedListElement lle = alloc_lle(o);
149:
150: if (first == null) {
151: first = last = lle;
152: } else {
153: last.next = lle;
154: lle.prev = last;
155: last = lle;
156: }
157: num_in_list++;
158: }
159:
160: /**
161: * Gets the tail object from the linked list.
162: *
163: * @return the tail, or null if there is nothing in the list.
164: */
165: public Object get_tail() {
166: if (last == null)
167: return null;
168: return last.obj;
169: }
170:
171: /**
172: * Removes the tail object from the linked list, and returns it.
173: *
174: * @return the tail, or null if there is nothing in the list.
175: */
176: public Object remove_tail() {
177: ssLinkedListElement retme = null;
178: Object retobj = null;
179:
180: if (last == null)
181: return null;
182: retme = last;
183:
184: if (first == last) {
185: first = last = null;
186: } else {
187: last = last.prev;
188: last.next = null;
189: }
190:
191: num_in_list--;
192: retobj = retme.obj;
193: free_lle(retme);
194: return retobj;
195: }
196:
197: /**
198: * Adds an object to the head (start) of the linked list.
199: *
200: * @param o the object to add
201: */
202: public void add_to_head(Object o) {
203: ssLinkedListElement lle = alloc_lle(o);
204:
205: if (first == null) {
206: first = last = lle;
207: } else {
208: first.prev = lle;
209: lle.next = first;
210: first = lle;
211: }
212: num_in_list++;
213: }
214:
215: /**
216: * Gets the head object from the linked list.
217: *
218: * @return the head, or null if there is nothing in the list.
219: */
220: public Object get_head() {
221: if (first == null)
222: return null;
223: return first.obj;
224: }
225:
226: /**
227: * Removes the head object from the linked list, and returns it.
228: *
229: * @return the head, or null if there is nothing in the list.
230: */
231: public Object remove_head() {
232: ssLinkedListElement retme = null;
233: Object retobj = null;
234:
235: if (first == null)
236: return null;
237: retme = first;
238:
239: if (first == last) {
240: first = last = null;
241: } else {
242: first = first.next;
243: first.prev = null;
244: }
245:
246: num_in_list--;
247: retobj = retme.obj;
248: free_lle(retme);
249: return retobj;
250: }
251:
252: public void remove_all() {
253: num_in_list = 0;
254: first = last = null;
255: lle_heap = new ssLinkedListElement[HEAP_ALLOC_NUM];
256: num_in_lle_heap = 0;
257: }
258:
259: /**
260: * Gets the first object to match according to the comparator
261: * function.
262: *
263: * @return the matching object, or null if there is nothing that matches.
264: */
265: public Object get_comparator(Object known,
266: ssLinkedListComparator llc) {
267: ssLinkedListElement tmp;
268:
269: tmp = first;
270: while (tmp != null) {
271: if (llc.compare(known, tmp.obj)) {
272: return tmp.obj;
273: }
274: tmp = tmp.next;
275: }
276: return null;
277: }
278:
279: /**
280: * Removes the first object to match according to the comparator function,
281: * and returns it.
282: *
283: * @return the match, or null if there is nothing that matches.
284: */
285: public Object remove_comparator(Object known,
286: ssLinkedListComparator llc) {
287: ssLinkedListElement tmp;
288:
289: tmp = first;
290: while (tmp != null) {
291: if (llc.compare(known, tmp.obj)) {
292:
293: // cut it out and return it
294: if (tmp == first) {
295: return this .remove_head();
296: } else if (tmp == last) {
297: return this .remove_tail();
298: } else {
299: // somewhere in middle
300: Object retobj;
301:
302: (tmp.prev).next = tmp.next;
303: (tmp.next).prev = tmp.prev;
304: num_in_list--;
305: retobj = tmp.obj;
306: free_lle(tmp);
307: return retobj;
308: }
309: }
310: tmp = tmp.next;
311: }
312: return null;
313: }
314:
315: /**
316: * Returns the first object that is "equal" to the given object,
317: * based on the response of the Object.equals() method.
318: **/
319: public Object get_item(Object known) {
320: return get_comparator(known, ll_equality_comparator);
321: }
322:
323: /**
324: * Removes the first object that is "equal" to the given object,
325: * based on the response of the Object.equals() method.
326: **/
327: public Object remove_item(Object known) {
328: return remove_comparator(known, ll_equality_comparator);
329: }
330:
331: /**
332: * Returns a java.util.Enumeration enumeration over the elements of the
333: * linked list. If you modify the list while enumerating over it,
334: * you get what you deserve (i.e. undefined behaviour).
335: *
336: * @return the enumeration over the elements
337: * @see java.util.Enumeration
338: */
339: public java.util.Enumeration elements() {
340: return (java.util.Enumeration) (new ssLinkedListEnumeration());
341: }
342:
343: /**
344: * Return a string representation, for debugging purposes
345: **/
346: public String toString() {
347: return toString("");
348: }
349:
350: public String toString(String prefix) {
351: String pre = prefix;
352: if (pre == null)
353: pre = "";
354:
355: String ret = pre + "ssLinkedList: length=" + num_in_list + "\n";
356:
357: ssLinkedListElement current = first;
358: while (current != null) {
359: if (current.obj == null) {
360: ret += pre + " (null)\n";
361: }
362:
363: else {
364: if (current.obj instanceof ssLinkedList) {
365: ret += pre
366: + "LINKED LIST\n"
367: + ((ssLinkedList) current.obj).toString(pre
368: + " ");
369: } else {
370: ret += pre + " " + current.obj.toString() + "\n";
371: }
372: }
373:
374: current = current.next;
375: }
376:
377: return ret;
378: }
379:
380: // test code
381: private static void printTime(long long1, long long3, int int5) {
382: long long6 = long3 - long1;
383: double double8 = (double) int5 / (double) long6;
384: double double10 = double8 * 1000.0;
385:
386: System.out.println(int5 + " iterations in " + long6
387: + " milliseconds = " + double10
388: + " iterations per second");
389: }
390:
391: /**
392: * Test code for the ssLinkedList
393: */
394:
395: private static final int NUM_IT = 10000000;
396:
397: public static void main(String args[]) {
398: ssLinkedList ll = new ssLinkedList();
399: long before, after;
400:
401: for (int i = 0; i < 990; i++)
402: ll.add_to_tail(null);
403:
404: before = System.currentTimeMillis();
405: before = System.currentTimeMillis();
406: for (int i = 0; i < NUM_IT; i++) {
407: ll.add_to_tail(null);
408: ll.remove_head();
409: }
410: after = System.currentTimeMillis();
411: printTime(before, after, NUM_IT);
412: }
413:
414: }
|