0
|
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 |
void * List::removeElement(void * item)
|
|
255 |
// find this item in list and remove it
|
|
256 |
// return item pointer or NULL
|
|
257 |
{
|
|
258 |
for (ListElement * ptr = first; ptr!=NULL; ptr= ptr->next)
|
|
259 |
{
|
|
260 |
if (ptr->item == item)
|
|
261 |
{
|
|
262 |
removeAt(ptr);
|
|
263 |
return item;
|
|
264 |
}
|
|
265 |
}
|
|
266 |
return NULL;
|
|
267 |
|
|
268 |
}
|
|
269 |
|
|
270 |
void List::insertAfter(ListElement * listEl, void *item)
|
|
271 |
// insert a new item after this one
|
|
272 |
{
|
|
273 |
ListElement *newElement = new ListElement(item, 0);
|
|
274 |
newElement->next = listEl->next;
|
|
275 |
newElement->previous = listEl;
|
|
276 |
listEl->next = newElement;
|
|
277 |
if (last == listEl)
|
|
278 |
last = newElement;
|
|
279 |
length++;
|
|
280 |
}
|
|
281 |
|
|
282 |
|
|
283 |
void List::insertBefore(ListElement * listEl, void *item)
|
|
284 |
// insert a new item before this one
|
|
285 |
{
|
|
286 |
ListElement *newElement = new ListElement(item, 0);
|
|
287 |
newElement->next = listEl;
|
|
288 |
newElement->previous = listEl->previous;
|
|
289 |
listEl->previous = newElement;
|
|
290 |
if (first == listEl)
|
|
291 |
first = newElement;
|
|
292 |
length++;
|
|
293 |
}
|
|
294 |
|
|
295 |
|
|
296 |
|
|
297 |
void List::removeAt(ListElement * listEl)
|
|
298 |
// removes listEl from the list. Do not delete it from memory
|
|
299 |
{
|
|
300 |
if(first != listEl)
|
|
301 |
{
|
|
302 |
(listEl->previous)->next = listEl->next;
|
|
303 |
}
|
|
304 |
else
|
|
305 |
{
|
|
306 |
first = listEl->next;
|
|
307 |
}
|
|
308 |
if(last != listEl)
|
|
309 |
(listEl->next)->previous = listEl->previous;
|
|
310 |
else
|
|
311 |
last = listEl->previous;
|
|
312 |
|
|
313 |
if (first != NULL) first->previous = NULL;
|
|
314 |
if (last != NULL) last->next = NULL;
|
|
315 |
|
|
316 |
|
|
317 |
delete listEl;
|
|
318 |
length --;
|
|
319 |
}
|
|
320 |
|
|
321 |
|
|
322 |
|
|
323 |
void List::printList()
|
|
324 |
{
|
|
325 |
int i=0;
|
|
326 |
printf("length= %d first = %u last = %u\n", length, first, last);
|
|
327 |
for(ListElement * ptr = first; ptr != NULL; ptr=ptr->next)
|
|
328 |
{
|
|
329 |
if ((i++%3) == 0) printf("\n");
|
|
330 |
printf(" ( %u, %u, %u ) ", ptr->previous, ptr, ptr->next);
|
|
331 |
}
|
|
332 |
printf("\n");
|
|
333 |
}
|
|
334 |
|
|
335 |
|
|
336 |
|
|
337 |
|
|
338 |
|
|
339 |
|
|
340 |
|
|
341 |
|
|
342 |
|
|
343 |
|
|
344 |
|
|
345 |
|
|
346 |
|
|
347 |
|
|
348 |
|