1 // list.cc 

     2 //

     3 //     	Routines to manage a singly-linked list of "things".

     4 //

     5 // 	A "ListElement" is allocated for each item to be put on the

     6 //	list; it is de-allocated when the item is removed. This means

     7 //      we don't need to keep a "next" pointer in every object we

     8 //      want to put on a list.

     9 // 

    10 //     	NOTE: Mutual exclusion must be provided by the caller.

    11 //  	If you want a synchronized list, you must use the routines 

    12 //	in synchlist.cc.

    13 //

    14 // Copyright (c) 1992-1993 The Regents of the University of California.

    15 // All rights reserved.  See copyright.h for copyright notice and limitation 

    16 // of liability and disclaimer of warranty provisions.

    17 

    18 

    19 #include "list.h"

    20 

    21 //----------------------------------------------------------------------

    22 // ListElement::ListElement

    23 // 	Initialize a list element, so it can be added somewhere on a list.

    24 //

    25 //	"itemPtr" is the item to be put on the list.  It can be a pointer

    26 //		to anything.

    27 //	"sortKey" is the priority of the item, if any.

    28 //----------------------------------------------------------------------

    29 

    30 ListElement::ListElement(void *itemPtr, int sortKey)

    31 {

    32      item = itemPtr;

    33      key = sortKey;

    34      next = NULL;	// assume we'll put it at the end of the list 

    35      previous = NULL;

    36 }

    37 

    38 //----------------------------------------------------------------------

    39 // List::List

    40 //	Initialize a list, empty to start with.

    41 //	Elements can now be added to the list.

    42 //----------------------------------------------------------------------

    43 

    44 List::List()

    45 { 

    46     first = last = NULL;

    47     length = 0;

    48 }

    49 

    50 //----------------------------------------------------------------------

    51 // List::~List

    52 //	Prepare a list for deallocation.  If the list still contains any 

    53 //	ListElements, de-allocate them.  However, note that we do *not*

    54 //	de-allocate the "items" on the list -- this module allocates

    55 //	and de-allocates the ListElements to keep track of each item,

    56 //	but a given item may be on multiple lists, so we can't

    57 //	de-allocate them here.

    58 //----------------------------------------------------------------------

    59 

    60 List::~List()

    61 { 

    62     while (Remove() != NULL)

    63 	;	 // delete all the list elements

    64 }

    65 

    66 //----------------------------------------------------------------------

    67 // List::Append

    68 //      Append an "item" to the end of the list.

    69 //      

    70 //	Allocate a ListElement to keep track of the item.

    71 //      If the list is empty, then this will be the only element.

    72 //	Otherwise, put it at the end.

    73 //

    74 //	"item" is the thing to put on the list, it can be a pointer to 

    75 //		anything.

    76 //----------------------------------------------------------------------

    77 

    78 void

    79 List::Append(void *item)

    80 {

    81     ListElement *element = new ListElement(item, 0);

    82 

    83     if (IsEmpty()) {		// list is empty

    84 	first = element;

    85 	last = element;

    86     } else {			// else put it after last

    87 	last->next = element;

    88 	element->previous = last;

    89 	last = element;

    90     }

    91     length++;

    92 }

    93 

    94 //----------------------------------------------------------------------

    95 // List::Prepend

    96 //      Put an "item" on the front of the list.

    97 //      

    98 //	Allocate a ListElement to keep track of the item.

    99 //      If the list is empty, then this will be the only element.

   100 //	Otherwise, put it at the beginning.

   101 //

   102 //	"item" is the thing to put on the list, it can be a pointer to 

   103 //		anything.

   104 //----------------------------------------------------------------------

   105 

   106 void

   107 List::Prepend(void *item)

   108 {

   109     ListElement *element = new ListElement(item, 0);

   110 

   111     if (IsEmpty()) {		// list is empty

   112 	first = element;

   113 	last = element;

   114     } else {			// else put it before first

   115 	element->next = first;

   116 	first->previous = element;

   117 	first = element;

   118     }

   119     length++;

   120 }

   121 

   122 //----------------------------------------------------------------------

   123 // List::Remove

   124 //      Remove the first "item" from the front of the list.

   125 // 

   126 // Returns:

   127 //	Pointer to removed item, NULL if nothing on the list.

   128 //----------------------------------------------------------------------

   129 

   130 void *

   131 List::Remove()

   132 {

   133     return SortedRemove(NULL);  // Same as SortedRemove, but ignore the key

   134     length--;

   135 }

   136 

   137 //----------------------------------------------------------------------

   138 // List::Mapcar

   139 //	Apply a function to each item on the list, by walking through  

   140 //	the list, one element at a time.

   141 //

   142 //	Unlike LISP, this mapcar does not return anything!

   143 //

   144 //	"func" is the procedure to apply to each element of the list.

   145 //----------------------------------------------------------------------

   146 

   147 void

   148 List::Mapcar(VoidFunctionPtr func)

   149 {

   150     for (ListElement *ptr = first; ptr != NULL; ptr = ptr->next) {

   151        (*func)((int)ptr->item);

   152     }

   153 }

   154 

   155 //----------------------------------------------------------------------

   156 // List::IsEmpty

   157 //      Returns TRUE if the list is empty (has no items).

   158 //----------------------------------------------------------------------

   159 

   160 bool

   161 List::IsEmpty() 

   162 { 

   163     if (first == NULL)

   164         return TRUE;

   165     else

   166 	return FALSE; 

   167 }

   168 

   169 //----------------------------------------------------------------------

   170 // List::SortedInsert

   171 //      Insert an "item" into a list, so that the list elements are

   172 //	sorted in increasing order by "sortKey".

   173 //      

   174 //	Allocate a ListElement to keep track of the item.

   175 //      If the list is empty, then this will be the only element.

   176 //	Otherwise, walk through the list, one element at a time,

   177 //	to find where the new item should be placed.

   178 //

   179 //	"item" is the thing to put on the list, it can be a pointer to 

   180 //		anything.

   181 //	"sortKey" is the priority of the item.

   182 //----------------------------------------------------------------------

   183 

   184 void

   185 List::SortedInsert(void *item, int sortKey)

   186 {

   187     ListElement *element = new ListElement(item, sortKey);

   188     ListElement *ptr;		// keep track

   189 

   190     if (IsEmpty()) {	// if list is empty, put

   191         first = element;

   192         last = element;

   193     } else if (sortKey < first->key) {	

   194 		// item goes on front of list

   195 	element->next = first;

   196 	first->previous = element;

   197 	first = element;

   198     } else {		// look for first elt in list bigger than item

   199         for (ptr = first; ptr->next != NULL; ptr = ptr->next) {

   200             if (sortKey < ptr->next->key) {

   201 		element->next = ptr->next;

   202 		element->previous = ptr;

   203 		ptr->next->previous = element;

   204 	        ptr->next = element;

   205 		return;

   206 	    }

   207 	}

   208 	last->next = element;		// item goes at end of list

   209 	element->previous = last;

   210 	last = element;

   211     }

   212     length++;

   213 }

   214 

   215 //----------------------------------------------------------------------

   216 // List::SortedRemove

   217 //      Remove the first "item" from the front of a sorted list.

   218 // 

   219 // Returns:

   220 //	Pointer to removed item, NULL if nothing on the list.

   221 //	Sets *keyPtr to the priority value of the removed item

   222 //	(this is needed by interrupt.cc, for instance).

   223 //

   224 //	"keyPtr" is a pointer to the location in which to store the 

   225 //  priority of the removed item.

   226 //----------------------------------------------------------------------

   227 

   228 void *

   229 List::SortedRemove(int *keyPtr)

   230 {

   231     ListElement *element = first;

   232     void *thing;

   233 

   234     if (IsEmpty()) 

   235 	return NULL;

   236 

   237     thing = first->item;

   238     if (first == last) {	// list had one item, now has none 

   239         first = NULL;

   240 	last = NULL;

   241     } else {

   242         first = element->next;

   243 	if (first != NULL)

   244 	  first->previous = NULL;

   245     }

   246     if (keyPtr != NULL)

   247         *keyPtr = element->key;

   248     delete element;

   249     length--;

   250     return thing;

   251 }

   252 

   253 

   254 

   255 void List::insertAfter(ListElement * listEl, void *item)   

   256  // insert a new item after this one

   257 {

   258     ListElement *newElement = new ListElement(item, 0);

   259     newElement->next = listEl->next;

   260     newElement->previous = listEl;

   261     listEl->next = newElement;

   262     if (last == listEl)

   263       last = newElement;

   264     length++;

   265 }

   266 

   267 

   268 void List::insertBefore(ListElement * listEl, void *item)   

   269  // insert a new item before this one

   270 {

   271     ListElement *newElement = new ListElement(item, 0);

   272     newElement->next = listEl;

   273     newElement->previous = listEl->previous;

   274     listEl->previous = newElement;

   275     if (first == listEl)

   276       first = newElement;

   277     length++;

   278 }

   279 

   280 

   281 

   282 void List::removeAt(ListElement * listEl)   

   283      // removes listEl from the list. Do not delete it from memory

   284 {

   285     if(first != listEl)

   286       (listEl->previous)->next = listEl->next;

   287     else 

   288       first = listEl->next;

   289     if(last != listEl)

   290       (listEl->next)->previous = listEl->previous;

   291     else 

   292       last = listEl->previous;

   293 //    delete listEl;

   294     length --;

   295 }

   296 

   297 

   298 

   299 

   300 

   301 

   302 

   303 

   304 

   305 

   306 

   307 

   308 

   309 

   310 

   311 

   312 

   313 

   314