nachos.kernel.threads
Class List

java.lang.Object
  extended by nachos.kernel.threads.List
Direct Known Subclasses:
SynchList

public class List
extends java.lang.Object

The following class defines a "list" -- a singly linked list of list elements, each of which points to a single item on the list. Although the Java API provides classes with functionality that subsume this one, linked lists are such an important data structure in operating systems that it seemed like a good idea to include here an implementation "from scratch". By using the sortedInsert() method, the list can be kept in sorted in increasing order with respect to a "sortKey". NOTE: Mutual exclusion must be provided by the caller. If you want a synchronized list, you must use the routines in synchlist.cc.


Nested Class Summary
protected static class List.ListElement
          The following class defines a "list element" -- which is used to keep track of one item on a list.
 
Field Summary
private  List.ListElement first
          Head of the list, null if list is empty
private  List.ListElement last
          Last element of the list.
 
Constructor Summary
List()
           
 
Method Summary
 void append(java.lang.Object item)
          Append an "item" to the end of the list.
 boolean isEmpty()
          Determine if the list is empty (has no items).
 void List()
          Initialize a list, empty to start with.
 void prepend(java.lang.Object item)
          Put an "item" on the front of the list.
 java.lang.Object remove()
          Remove the first "item" from the front of the list.
 void sortedInsert(java.lang.Object item, long sortKey)
          Insert an "item" into a list, so that the list elements are sorted in increasing order by "sortKey".
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

first

private List.ListElement first
Head of the list, null if list is empty


last

private List.ListElement last
Last element of the list.

Constructor Detail

List

public List()
Method Detail

List

public void List()
Initialize a list, empty to start with. Elements can then be added to the list.


append

public void append(java.lang.Object item)
Append an "item" to the end of the list. Allocate a ListElement to keep track of the item. If the list is empty, then this will be the only element. Otherwise, put it at the end.

Parameters:
item - The thing to put on the list, it can be any object.

prepend

public void prepend(java.lang.Object item)
Put an "item" on the front of the list. Allocate a ListElement to keep track of the item. If the list is empty, then this will be the only element. Otherwise, put it at the end.

Parameters:
item - The thing to put on the list, it can be any object.

remove

public java.lang.Object remove()
Remove the first "item" from the front of the list.

Returns:
the removed item, or null if nothing on the list.

isEmpty

public boolean isEmpty()
Determine if the list is empty (has no items).

Returns:
true if the list is empty, otherwise false.

sortedInsert

public void sortedInsert(java.lang.Object item,
                         long sortKey)
Insert an "item" into a list, so that the list elements are sorted in increasing order by "sortKey". Allocate a ListElement to keep track of the item. If the list is empty, then this will be the only element. Otherwise, walk through the list, one element at a time, to find where the new item should be placed.

Parameters:
item - The thing to put on the list, it can be any object.
sortKey - The priority of the item.