Debian Codegraph @

protolib/src/common/protoList.cpp

raw
1 /**
2 * @file protoList.cpp
3 *
4 * @brief The ProtoList class provides a simple double linked-list
5 * class with a "ProtoList::Item" base class to use for
6 * deriving your own classes you wish to store in a
7 * ProtoList
8 */
9
10 #include "protoList.h"
11 #include "protoDebug.h"
12
13
14 ProtoIterable::ProtoIterable()
15 : iterator_list_head(NULL)
16 {
17 }
18
19 ProtoIterable::~ProtoIterable()
20 {
21 // Need to tell associated iterators that
22 // we don't exist anymore
23 while (NULL != iterator_list_head)
24 RemoveIterator(*iterator_list_head);
25 }
26
27 void ProtoIterable::AddIterator(Iterator& iterator)
28 {
29 iterator.ilist_prev = NULL;
30 iterator.ilist_next = iterator_list_head;
31 if (NULL != iterator_list_head)
32 iterator_list_head->ilist_prev = &iterator;
33 iterator_list_head = &iterator;
34 } // end ProtoIterable::AddIterator()
35
36 void ProtoIterable::RemoveIterator(Iterator& iterator)
37 {
38 if (NULL == iterator.ilist_prev)
39 iterator_list_head = iterator.ilist_next;
40 else
41 iterator.ilist_prev->ilist_next = iterator.ilist_next;
42 if (NULL != iterator.ilist_next)
43 iterator.ilist_next->ilist_prev = iterator.ilist_prev;
44 iterator.ilist_prev = iterator.ilist_next = NULL;
45 iterator.iterable = NULL;
46 } // end ProtoIterable::RemoveIterator()
47
48 // This should be called before or after theAction is executed by the iterable
49 // depending on the data structure. For example, APPEND/PREPEND list actions
50 // use the head/tail state to update list iterators properly so these need
51 // to call UpdateIterator _before_ apppend/prepend while other types may
52 // require post-action data structure state.
53 void ProtoIterable::UpdateIterators(Item* theItem, Iterator::Action theAction) const
54 {
55 Iterator* nextIterator = iterator_list_head;
56 while (NULL != nextIterator)
57 {
58 nextIterator->Update(theItem, theAction);
59 nextIterator = nextIterator->ilist_next;
60 }
61 } // end ProtoIterable::UpdateIterators()
62
63 ProtoIterable::Iterator::Iterator(ProtoIterable& theIterable)
64 : iterable(&theIterable), ilist_prev(NULL), ilist_next(NULL)
65 {
66 theIterable.AddIterator(*this);
67 }
68
69 ProtoIterable::Iterator::~Iterator()
70 {
71 if (NULL != iterable)
72 iterable->RemoveIterator(*this);
73 }
74
75
76 ProtoList::Item::Item()
77 {
78 }
79
80 ProtoList::Item::~Item()
81 {
82 }
83
84 ProtoList::ProtoList()
85 : head(NULL), tail(NULL)
86 {
87 }
88
89 ProtoList::~ProtoList()
90 {
91 }
92
93 void ProtoList::Prepend(Item& item)
94 {
95 UpdateIterators(&item, Iterator::PREPEND);
96 item.plist_prev = NULL;
97 if (NULL != head)
98 head->plist_prev = &item;
99 else
100 tail = &item;
101 item.plist_next = head;
102 head = &item;
103 } // end ProtoList::Prepend()
104
105 void ProtoList::Append(Item& item)
106 {
107 UpdateIterators(&item, Iterator::APPEND);
108 item.plist_next = NULL;
109 if (NULL != tail)
110 tail->plist_next = &item;
111 else
112 head = &item;
113 item.plist_prev = tail;
114 tail = &item;
115 } // end ProtoList::Append()
116
117 void ProtoList::Insert(Item& theItem, Item& nextItem)
118 {
119 theItem.plist_next = &nextItem;
120 theItem.plist_prev = nextItem.plist_prev;
121 if (&nextItem == head)
122 head = &theItem;
123 else
124 nextItem.plist_prev->plist_next = &theItem;
125 nextItem.plist_prev = &theItem;
126 UpdateIterators(&theItem, Iterator::INSERT);
127 } // end ProtoList::Insert()
128
129 void ProtoList::InsertAfter(Item& theItem, Item& prevItem)
130 {
131 theItem.plist_prev = &prevItem;
132 theItem.plist_next = prevItem.plist_next;
133 if (&prevItem == tail)
134 tail = &theItem;
135 else
136 prevItem.plist_next->plist_prev = &theItem;
137 prevItem.plist_next = &theItem;
138 UpdateIterators(&theItem, Iterator::INSERT);
139 } // end ProtoList::ProtoList::InsertAfter()
140
141 void ProtoList::Remove(Item& item)
142 {
143 UpdateIterators(&item, Iterator::REMOVE);
144 if (NULL == item.plist_prev)
145 head = item.plist_next;
146 else
147 item.plist_prev->plist_next = item.plist_next;
148
149 if (NULL == item.plist_next)
150 tail = item.plist_prev;
151 else
152 item.plist_next->plist_prev = item.plist_prev;
153 item.plist_prev = item.plist_next = NULL;
154 } // end ProtoList::Remove()
155
156 ProtoList::Item* ProtoList::RemoveHead()
157 {
158 Item* item = head;
159 if (NULL != item) Remove(*item);
160 return item;
161 } // end ProtoList::RemoveHead()
162
163 ProtoList::Item* ProtoList::RemoveTail()
164 {
165 Item* item = tail;
166 if (NULL != item) Remove(*item);
167 return item;
168 } // end ProtoList::RemoveTail()
169
170 void ProtoList::Empty()
171 {
172 UpdateIterators(NULL, Iterator::EMPTY);
173 head = tail = NULL;
174 } // end ProtoList::Empty()
175
176 void ProtoList::EmptyToPool(ItemPool& pool)
177 {
178 if (NULL != tail)
179 {
180 tail->plist_next = pool.head;
181 pool.head = head;
182 Empty();
183 }
184 } // end ProtoList::EmptyToPool()
185
186 void ProtoList::Destroy()
187 {
188 Item* item = head;
189 while (NULL != item)
190 {
191 Remove(*item);
192 delete item;
193 item = head;
194 }
195 } // end ProtoList::Destroy()
196
197
198
199 ProtoList::ItemPool::ItemPool()
200 : head(NULL)
201 {
202 }
203
204 ProtoList::ItemPool::~ItemPool()
205 {
206 Destroy();
207 }
208
209 ProtoList::Item* ProtoList::ItemPool::Get()
210 {
211 Item* item = head;
212 if (NULL != item) head = item->plist_next;
213 return item;
214 } // end ProtoList::ItemPool::Get()
215
216 void ProtoList::ItemPool::Put(Item& item)
217 {
218 item.plist_next = head;
219 head = &item;
220 } // end ProtoList::ItemPool::Put()
221
222 void ProtoList::ItemPool::Destroy()
223 {
224 Item* item;
225 while (NULL != (item = Get())) delete item;
226 } // end ProtoList::ItemPool::Destroy()
227
228
229 ProtoList::Iterator::Iterator(ProtoList& theList, bool reverse)
230 : ProtoIterable::Iterator(theList)
231 {
232 Reset(reverse);
233 }
234
235 void ProtoList::Iterator::Reset(bool reverse)
236 {
237 ProtoList* list = static_cast<ProtoList*>(iterable);
238 reversed = reverse;
239 if (NULL != list)
240 item = reverse ? list->tail : list->head;
241 else
242 item = NULL;
243 } // end ProtoList::Iterator::Reset()
244
245 ProtoList::Iterator::~Iterator()
246 {
247 }
248
249 ProtoList::Item* ProtoList::Iterator::GetNextItem()
250 {
251 if (reversed)
252 {
253 ProtoList* list = static_cast<ProtoList*>(iterable);
254 if (NULL != item)
255 item = item->plist_next;
256 else if (NULL != list)
257 item = list->head;
258 reversed = false;
259 }
260 if (NULL != item)
261 {
262 Item* next = item;
263 item = item->plist_next;
264 return next;
265 }
266 else
267 {
268 return NULL;
269 }
270 } // end ProtoList::Iterator::GetNextItem()
271
272 ProtoList::Item* ProtoList::Iterator::GetPrevItem()
273 {
274 if (!reversed)
275 {
276 ProtoList* list = static_cast<ProtoList*>(iterable);
277 if (NULL != item)
278 item = item->plist_prev;
279 else if (NULL != list)
280 item = list->tail;
281 reversed = true;
282 }
283 if (NULL != item)
284 {
285 Item* prev = item;
286 item = item->plist_prev;
287 return prev;
288 }
289 else
290 {
291 return NULL;
292 }
293 } // end ProtoList::Iterator::GetPrevItem()
294
295 ProtoList::Item* ProtoList::Iterator::PeekPrevItem() const
296 {
297 ProtoList* list = static_cast<ProtoList*>(iterable);
298 Item* prevItem = NULL;
299 if (NULL != list)
300 {
301 if (reversed)
302 prevItem = item;
303 else
304 prevItem = (NULL != item) ? item->plist_prev : list->tail;
305 }
306 return prevItem;
307 } // end ProtoList::Iterator::PeekPrevItem()
308
309 void ProtoList::Iterator::Reverse()
310 {
311 if (reversed)
312 {
313 if (NULL != item)
314 {
315 item = item->plist_next;
316 }
317 else
318 {
319 ProtoList* list = static_cast<ProtoList*>(iterable);
320 if (NULL != list)
321 item = list->GetHead();
322 else
323 item = NULL;
324 }
325 reversed = false;
326 }
327 else
328 {
329 if (NULL != item)
330 {
331 item = item->plist_prev;
332 }
333 else
334 {
335 ProtoList* list = static_cast<ProtoList*>(iterable);
336 if (NULL != list)
337 item = list->GetTail();
338 else
339 item = NULL;
340 }
341 reversed = true;
342 }
343 } // end ProtoList::Iterator::Reverse()
344
345 void ProtoList::Iterator::Update(ProtoIterable::Item* theItem, Action theAction)
346 {
347 ProtoList::Item* listItem = static_cast<ProtoList::Item*>(theItem);
348 switch (theAction)
349 {
350 case REMOVE:
351 if (listItem == item)
352 {
353 if (reversed)
354 item = listItem->plist_prev;
355 else
356 item = listItem->plist_next;
357 }
358 break;
359 case PREPEND:
360 {
361 ProtoList* list = static_cast<ProtoList*>(iterable);
362 if (reversed)
363 {
364 if (NULL == item)
365 item = listItem;
366 }
367 else if (list->head == item)
368 {
369 item = listItem;
370 }
371 break;
372 }
373 case APPEND:
374 {
375 ProtoList* list = static_cast<ProtoList*>(iterable);
376 if (reversed)
377 {
378 if (list->tail == item)
379 item = listItem;
380 }
381 else if (NULL == item)
382 {
383 item = listItem;
384 }
385 break;
386 }
387 case INSERT:
388 if (reversed)
389 {
390 if (listItem->plist_prev == item)
391 item = listItem;
392 }
393 else
394 {
395 if (listItem->plist_next == item)
396 item = listItem;
397 }
398 break;
399 case EMPTY:
400 item = NULL;
401 break;
402 }
403 } // end ProtoList::Iterator::Update()
404
405
406 ProtoStack::ProtoStack()
407 : head(NULL), tail(NULL)
408 {
409 }
410
411 ProtoStack::~ProtoStack()
412 {
413 }
414
415
416 void ProtoStack::Push(Item& item)
417 {
418 item.pstack_next = head;
419 head = &item;
420 if (NULL == tail) tail = &item;
421 } // end ProtoStack::Push(Item& item)
422
423
424 ProtoStack::Item* ProtoStack::Pop()
425 {
426 Item* item = head;
427 if (NULL != item)
428 {
429 if (NULL != item->pstack_next)
430 head = item->pstack_next;
431 else
432 head = tail = NULL;
433 }
434 return item;
435 } // end ProtoStack::Pop()
436
437 void ProtoStack::Put(Item& item)
438 {
439 item.pstack_next = NULL;
440 if (NULL != tail)
441 tail->pstack_next = &item;
442 else
443 head = tail = &item;
444 } // end ProtoStack::Put()
445
446 void ProtoStack::Destroy()
447 {
448 Item* item;
449 while (NULL != (item = Pop()))
450 delete item;
451 } // end ProtoStack::Destroy()
452
453 ProtoStack::Item::Item()
454 : pstack_next(NULL)
455 {
456 }
457
458 ProtoStack::Item::~Item()
459 {
460 }
461
462 ProtoStack::Iterator::Iterator(const ProtoStack& theStack)
463 : stack(theStack), next(theStack.GetHead())
464 {
465 }
466
467 ProtoStack::Iterator::~Iterator()
468 {
469 }
470
471 ProtoStack::Item* ProtoStack::Iterator::GetNextItem()
472 {
473 Item* item = next;
474 if (NULL != item)
475 next = item->pstack_next;
476 return item;
477 } // end ProtoStack::Iterator::GetNextItem()