-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.cc
240 lines (211 loc) · 7.17 KB
/
list.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
// list.cc
//
// Routines to manage a singly-linked list of "things".
//
// A "ListElement" is allocated for each item to be put on the
// list; it is de-allocated when the item is removed. This means
// we don't need to keep a "next" pointer in every object we
// want to put on a list.
//
// NOTE: Mutual exclusion must be provided by the caller.
// If you want a synchronized list, you must use the routines
// in synchlist.cc.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved. See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.
#include "copyright.h"
#include "list.h"
//----------------------------------------------------------------------
// ListElement::ListElement
// Initialize a list element, so it can be added somewhere on a list.
//
// "itemPtr" is the item to be put on the list. It can be a pointer
// to anything.
// "sortKey" is the priority of the item, if any.
//----------------------------------------------------------------------
ListElement::ListElement(void *itemPtr, long long unsigned sortKey)
{
item = itemPtr;
key = sortKey;
next = NULL; // assume we'll put it at the end of the list
}
//----------------------------------------------------------------------
// List::List
// Initialize a list, empty to start with.
// Elements can now be added to the list.
//----------------------------------------------------------------------
List::List()
{
first = last = NULL;
}
//----------------------------------------------------------------------
// List::~List
// Prepare a list for deallocation. If the list still contains any
// ListElements, de-allocate them. However, note that we do *not*
// de-allocate the "items" on the list -- this module allocates
// and de-allocates the ListElements to keep track of each item,
// but a given item may be on multiple lists, so we can't
// de-allocate them here.
//----------------------------------------------------------------------
List::~List()
{
while (Remove() != NULL)
; // delete all the list elements
}
//----------------------------------------------------------------------
// List::Append
// 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.
//
// "item" is the thing to put on the list, it can be a pointer to
// anything.
//----------------------------------------------------------------------
void
List::Append(void *item)
{
ListElement *element = new ListElement(item, 0);
if (IsEmpty()) { // list is empty
first = element;
last = element;
} else { // else put it after last
last->next = element;
last = element;
}
}
//----------------------------------------------------------------------
// List::Prepend
// 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 beginning.
//
// "item" is the thing to put on the list, it can be a pointer to
// anything.
//----------------------------------------------------------------------
void
List::Prepend(void *item)
{
ListElement *element = new ListElement(item, 0);
if (IsEmpty()) { // list is empty
first = element;
last = element;
} else { // else put it before first
element->next = first;
first = element;
}
}
//----------------------------------------------------------------------
// List::Remove
// Remove the first "item" from the front of the list.
//
// Returns:
// Pointer to removed item, NULL if nothing on the list.
//----------------------------------------------------------------------
void *
List::Remove()
{
return SortedRemove(NULL); // Same as SortedRemove, but ignore the key
}
//----------------------------------------------------------------------
// List::Mapcar
// Apply a function to each item on the list, by walking through
// the list, one element at a time.
//
// Unlike LISP, this mapcar does not return anything!
//
// "func" is the procedure to apply to each element of the list.
//----------------------------------------------------------------------
void
List::Mapcar(VoidFunctionPtr func)
{
for (ListElement *ptr = first; ptr != NULL; ptr = ptr->next) {
DEBUG('l', (char *) "In mapcar, about to invoke %x(%x)\n", func, ptr->item);
(*func)((int)ptr->item);
}
}
//----------------------------------------------------------------------
// List::IsEmpty
// Returns TRUE if the list is empty (has no items).
//----------------------------------------------------------------------
bool
List::IsEmpty()
{
if (first == NULL)
return true;
else
return false;
}
//----------------------------------------------------------------------
// List::SortedInsert
// 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.
//
// "item" is the thing to put on the list, it can be a pointer to
// anything.
// "sortKey" is the priority of the item.
//----------------------------------------------------------------------
void
List::SortedInsert(void *item, long long unsigned sortKey)
{
ListElement *element = new ListElement(item, sortKey);
ListElement *ptr; // keep track
if (IsEmpty()) { // if list is empty, put
first = element;
last = element;
} else if (sortKey < first->key) {
// item goes on front of list
element->next = first;
first = element;
} else { // look for first elt in list bigger than item
for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
if (sortKey < ptr->next->key) {
element->next = ptr->next;
ptr->next = element;
return;
}
}
last->next = element; // item goes at end of list
last = element;
}
}
//----------------------------------------------------------------------
// List::SortedRemove
// Remove the first "item" from the front of a sorted list.
//
// Returns:
// Pointer to removed item, NULL if nothing on the list.
// Sets *keyPtr to the priority value of the removed item
// (this is needed by interrupt.cc, for instance).
//
// "keyPtr" is a pointer to the location in which to store the
// priority of the removed item.
//----------------------------------------------------------------------
void *
List::SortedRemove(long long unsigned *keyPtr)
{
ListElement *element = first;
void *thing;
if (IsEmpty())
return NULL;
thing = first->item;
if (first == last) { // list had one item, now has none
first = NULL;
last = NULL;
} else {
first = element->next;
}
if (keyPtr != NULL)
*keyPtr = element->key;
delete element;
return thing;
}