Debian Codegraph @

protolib/src/common/protoQueue.cpp

raw
1
2 #include "protoQueue.h"
3
4 ProtoQueue::ProtoQueue(bool usePool)
5 : container_pool(usePool ? &builtin_container_pool : NULL)
6 {
7 }
8
9 ProtoQueue::ProtoQueue(ContainerPool* containerPool)
10 : container_pool(containerPool)
11 {
12 }
13
14 ProtoQueue::~ProtoQueue()
15 {
16 // Note the original plan was to call the Empty()
17 // method here so that when a ProtoQueue is deleted
18 // it removes any queued Containers so they aren't left
19 // with a bad pointer. But, you can't call virtual methods
20 // from a destructor in C++. So, the derived classes
21 // MUST call Empty() in their destructors!
22 builtin_container_pool.Destroy();
23 }
24
25
26 ProtoQueue::Container::Container()
27 : item(NULL), queue(NULL), entry(*this)
28 {
29 }
30
31 ProtoQueue::Container::~Container()
32 {
33 // Derived Container class destructors MUST
34 // also call "Cleanup()" so there is no danger
35 // of an indirect call to a virtual function
36 // (See the longer note in ProtoQueue::Item::~Item()
37 // below)
38 Cleanup();
39 }
40
41 void ProtoQueue::Container::Cleanup()
42 {
43 if (NULL != item)
44 {
45 ASSERT(NULL != queue);
46 queue->Remove(*item);
47 }
48 }
49
50 ProtoQueue::Container::Entry::Entry(Container& theContainer)
51 : container(theContainer)
52 {
53 }
54
55 ProtoQueue::Item::Item()
56 {
57 }
58
59 ProtoQueue::Item::~Item()
60 {
61 // If the call to Cleanup() causes some sort of core dump,
62 // it is likely the case that the derived ProtoQueue depends
63 // upon some extension of the base Item class for its data
64 // organization. So, derived Item types SHOULD/MUST call
65 // Cleanup() themselves so the Cleanup() call here doesn't do
66 // anything harmful. (the derived class' destructor() call to Cleanup()
67 // will be called first and be safer. In fact, perhaps it would be better to
68 // not call Cleanup() here at all and require programmers that create
69 // derived Item subclasses to call Cleanup(). The way to help force
70 // this may be to make the Cleanup() a pure virtual function in
71 // the base class so that subclasses must implement it? There is still
72 // some leftover safety issue here where further derivations are performed ...
73 // (This is the same issue as the note for the Empty() method above.)
74 // Perhaps there is a better design that avoids this C++ issue!
75 Cleanup();
76 }
77
78 void ProtoQueue::Item::Cleanup()
79 {
80 while (!container_list.IsEmpty())
81 {
82 Container::Entry*entry = static_cast<Container::Entry*>(container_list.GetRoot());
83 ProtoQueue* theQueue = entry->GetContainer().GetQueue();
84 ASSERT(NULL != theQueue);
85 theQueue->Remove(*this);
86 }
87 } // end ProtoQueue::Item::Cleanup()
88
89 bool ProtoQueue::Item::IsInOtherQueue(const ProtoQueue& queue)
90 {
91 ProtoTree::Iterator iterator(container_list);
92 const ProtoQueue::Container::Entry* entry;
93 while (NULL != (entry = static_cast<const Container::Entry*>(iterator.GetNextItem())))
94 {
95 if (&queue != entry->GetContainer().GetQueue())
96 return true;
97 }
98 return false;
99 } // end ProtoQueue::IsInOtherQueue()
100
101 ProtoQueue::ContainerPool::ContainerPool()
102 {
103 }
104
105 ProtoQueue::ContainerPool::~ContainerPool()
106 {
107 Destroy();
108 }
109
110 void ProtoQueue::ContainerPool::Destroy()
111 {
112 Container* container;
113 while (NULL != (container = Get()))
114 delete container;
115 } // end ProtoQueue::ContainerPool::Destroy()
116
117 ProtoSimpleQueue::ProtoSimpleQueue(bool usePool)
118 : ProtoQueue(usePool)
119 {
120 }
121
122 ProtoSimpleQueue::ProtoSimpleQueue(ContainerPool* containerPool)
123 : ProtoQueue(containerPool)
124 {
125 }
126
127 ProtoSimpleQueue::~ProtoSimpleQueue()
128 {
129 Empty();
130 }
131
132 bool ProtoSimpleQueue::Append(Item& theItem)
133 {
134 Container* theContainer = GetContainerFromPool();
135 if (NULL == theContainer) theContainer = CreateContainer();
136 if (NULL == theContainer) return false;
137 Associate(theItem, *theContainer);
138 item_list.Append(*theContainer);
139 return true;
140 } // end ProtoSimpleQueue::Append()
141
142 bool ProtoSimpleQueue::Prepend(ProtoQueue::Item& theItem)
143 {
144 Container* theContainer = GetContainerFromPool();
145 if (NULL == theContainer) theContainer = CreateContainer();
146 if (NULL == theContainer) return false;
147 Associate(theItem, *theContainer);
148 item_list.Prepend(*theContainer);
149 return true;
150 } // end ProtoSimpleQueue::Prepend()
151
152 bool ProtoSimpleQueue::Insert(ProtoQueue::Item& theItem, ProtoQueue::Item& nextItem)
153 {
154 Container* theContainer = GetContainerFromPool();
155 if (NULL == theContainer) theContainer = CreateContainer();
156 if (NULL == theContainer) return false;
157 Associate(theItem, *theContainer);
158 Container* nextContainer = static_cast<Container*>(nextItem.GetContainer(*this));
159 if (NULL == nextContainer)
160 {
161 PLOG(PL_ERROR, "ProtoSimpleQueue::Insert() error: nextItem not in this queue?!\n");
162 Disassociate(theItem, *theContainer);
163 if (NULL != container_pool)
164 container_pool->Put(*theContainer);
165 else
166 delete theContainer;
167 return false;
168 }
169 item_list.Insert(*theContainer, *nextContainer);
170 return true;
171 } // end ProtoSimpleQueue::Insert()
172
173 bool ProtoSimpleQueue::InsertAfter(ProtoQueue::Item& theItem, ProtoQueue::Item& nextItem)
174 {
175 Container* theContainer = GetContainerFromPool();
176 if (NULL == theContainer) theContainer = CreateContainer();
177 if (NULL == theContainer) return false;
178 Associate(theItem, *theContainer);
179 Container* nextContainer = static_cast<Container*>(nextItem.GetContainer(*this));
180 if (NULL == nextContainer)
181 {
182 PLOG(PL_ERROR, "ProtoSimpleQueue::Insert() error: nextItem not in this queue?!\n");
183 Disassociate(theItem, *theContainer);
184 if (NULL != container_pool)
185 container_pool->Put(*theContainer);
186 else
187 delete theContainer;
188 return false;
189 }
190 item_list.InsertAfter(*theContainer, *nextContainer);
191 return true;
192 } // end ProtoSimpleQueue::Insert()
193
194 void ProtoSimpleQueue::Remove(Item& theItem)
195 {
196 Container* theContainer = static_cast<Container*>(ProtoQueue::GetContainer(theItem));
197 if (NULL != theContainer) RemoveContainer(theContainer, theItem);
198 } // end ProtoSimpleQueue::Remove()
199
200 ProtoSimpleQueue::Item* ProtoSimpleQueue::RemoveHead()
201 {
202 Container* container = item_list.GetHead();
203 if (NULL != container)
204 {
205 Item* item = container->GetItem();
206 ASSERT(NULL != item);
207 RemoveContainer(container, *item);
208 return item;
209 }
210 else
211 {
212 return NULL;
213 }
214 } // end ProtoSimpleQueue::RemoveHead()
215
216 ProtoSimpleQueue::Item* ProtoSimpleQueue::RemoveTail()
217 {
218 Container* container = item_list.GetTail();
219 if (NULL != container)
220 {
221 Item* item = container->GetItem();
222 ASSERT(NULL != item);
223 RemoveContainer(container, *item);
224 return item;
225 }
226 else
227 {
228 return NULL;
229 }
230 } // end ProtoSimpleQueue::RemoveTail()
231
232 void ProtoSimpleQueue::RemoveContainer(Container* theContainer, Item& theItem)
233 {
234 ASSERT(NULL != theContainer);
235 item_list.Remove(*theContainer);
236 Disassociate(theItem, *theContainer);
237 if (NULL != container_pool)
238 container_pool->Put(*theContainer);
239 else
240 delete theContainer;
241 } // end ProtoSimpleQueue::RemoveContainer()
242
243 void ProtoSimpleQueue::Empty()
244 {
245 Container* nextContainer;
246 while (NULL != (nextContainer = item_list.RemoveHead()))
247 {
248 ProtoQueue::Item* nextItem = nextContainer->GetItem();
249 ASSERT(NULL != nextItem);
250 Disassociate(*nextItem, *nextContainer);
251 if (NULL != container_pool)
252 container_pool->Put(*nextContainer);
253 else
254 delete nextContainer;
255 }
256 } // end ProtoSimpleQueue::Empty()
257
258 void ProtoSimpleQueue::Destroy()
259 {
260 Container* nextContainer;
261 while (NULL != (nextContainer = item_list.RemoveHead()))
262 {
263 ProtoQueue::Item* nextItem = nextContainer->GetItem();
264 ASSERT(NULL != nextItem);
265 Disassociate(*nextItem, *nextContainer);
266 delete nextItem;
267 if (NULL != container_pool)
268 container_pool->Put(*nextContainer);
269 else
270 delete nextContainer;
271 }
272 } // end ProtoSimpleQueue::Destroy()
273
274 ProtoSimpleQueue::Iterator::Iterator(ProtoSimpleQueue& theQueue, bool reverse)
275 : ProtoList::Iterator(theQueue.item_list, reverse)
276 {
277 }
278
279 ProtoSimpleQueue::Iterator::~Iterator()
280 {
281 }
282
283 ProtoSimpleQueue::Container::Container()
284 {
285 }
286
287 ProtoSimpleQueue::Container::~Container()
288 {
289 Cleanup();
290 }
291
292 ProtoIndexedQueue::ProtoIndexedQueue(bool usePool)
293 : ProtoQueue(usePool)
294 {
295 }
296
297 ProtoIndexedQueue::ProtoIndexedQueue(ContainerPool* containerPool)
298 : ProtoQueue(containerPool)
299 {
300 }
301
302 ProtoIndexedQueue::~ProtoIndexedQueue()
303 {
304 Empty();
305 }
306
307 bool ProtoIndexedQueue::Insert(Item& theItem)
308 {
309 Container* theContainer = GetContainerFromPool();
310 if (NULL == theContainer) theContainer = CreateContainer();
311 if (NULL == theContainer) return false;
312 Associate(theItem, *theContainer);
313 //return item_tree.Insert(*theContainer);
314 //bunny Brian should we always return true here seems wrong...I'll let you do the update above or not.
315 item_tree.Insert(*theContainer);
316 return true;
317 } // end ProtoIndexedQueue::Insert()
318
319 void ProtoIndexedQueue::Remove(Item& theItem)
320 {
321 Container* theContainer = static_cast<Container*>(ProtoQueue::GetContainer(theItem));
322 if (NULL != theContainer)
323 {
324 item_tree.Remove(*theContainer);
325 Disassociate(theItem, *theContainer);
326 if (NULL != container_pool)
327 container_pool->Put(*theContainer);
328 else
329 delete theContainer;
330 }
331 } // end ProtoIndexedQueue::Remove()
332
333 void ProtoIndexedQueue::Empty()
334 {
335 // We use the "SimpleIterator here because it is safe
336 // to call from the destructor
337 Container* nextContainer;
338 Tree::SimpleIterator sit(item_tree);
339 // We have to defer container deletion until after item_tree traversal
340 // so we use this "tmpPool" (this is so the item virtuals aren't accessed)
341 ContainerPool tmpPool;
342 while (NULL != (nextContainer = sit.GetNextItem()))
343 {
344 ProtoQueue::Item* nextItem = nextContainer->GetItem();
345 ASSERT(NULL != nextItem);
346 Disassociate(*nextItem, *nextContainer);
347 if (NULL != container_pool)
348 container_pool->Put(*nextContainer);
349 else
350 tmpPool.Put(*nextContainer);
351 }
352 tmpPool.Destroy();
353 item_tree.Empty(); // sets the item_tree.root to NULL
354 } // end ProtoIndexedQueue::Empty()
355
356 // "Destroy" is same as "Empty", except items are deleted
357 void ProtoIndexedQueue::Destroy()
358 {
359 // We use the "SimpleIterator here because it is safe
360 // to call from the destructor
361 Container* nextContainer;
362 Tree::SimpleIterator sit(item_tree);
363 // We have to defer container deletion until after item_tree traversal
364 // so we use this "tmpPool" (this is so the item virtuals aren't accessed)
365 // The "trick" here is we stick the "container" directly into a pool
366 // without a "Remove" from the tree (where virtuals would be invoked).
367 // This is safe with the "SimpleIterator" we're using.
368 ContainerPool tmpPool;
369 while (NULL != (nextContainer = sit.GetNextItem()))
370 {
371 ProtoQueue::Item* nextItem = nextContainer->GetItem();
372 ASSERT(NULL != nextItem);
373 Disassociate(*nextItem, *nextContainer);
374 delete nextItem;
375 if (NULL != container_pool)
376 container_pool->Put(*nextContainer);
377 else
378 tmpPool.Put(*nextContainer);
379 }
380 tmpPool.Destroy();
381 item_tree.Empty(); // sets the item_tree.root to NULL
382 } // end ProtoIndexedQueue::Destroy()
383
384
385 ProtoIndexedQueue::Iterator::Iterator(ProtoIndexedQueue& theQueue, bool reverse)
386 : ProtoTree::Iterator(theQueue.item_tree, reverse)
387 {
388 }
389
390 ProtoIndexedQueue::Iterator::~Iterator()
391 {
392 }
393
394 ProtoIndexedQueue::Container::Container()
395 {
396 }
397
398 ProtoIndexedQueue::Container::~Container()
399 {
400 Cleanup();
401 }
402
403 const char* ProtoIndexedQueue::Container::GetKey() const
404 {
405 ProtoQueue::Item* item = GetItem();
406 ASSERT(NULL != item);
407 ProtoIndexedQueue* iq = static_cast<ProtoIndexedQueue*>(GetQueue());
408 return (iq->GetKey(*item));
409 } // end ProtoIndexedQueue::Container::GetKey()
410
411 unsigned int ProtoIndexedQueue::Container::GetKeysize() const
412 {
413 ProtoQueue::Item* item = GetItem();
414 ASSERT(NULL != item);
415 ProtoIndexedQueue* iq = static_cast<ProtoIndexedQueue*>(GetQueue());
416 return (iq->GetKeysize(*item));
417 } // end ProtoIndexedQueue::Container::GetKeysize()
418
419
420
421
422 ProtoSortedQueue::ProtoSortedQueue(bool usePool)
423 : ProtoQueue(usePool)
424 {
425 }
426
427 ProtoSortedQueue::ProtoSortedQueue(ContainerPool* containerPool)
428 : ProtoQueue(containerPool)
429 {
430 }
431
432 ProtoSortedQueue::~ProtoSortedQueue()
433 {
434 Empty();
435 }
436
437 bool ProtoSortedQueue::Insert(Item& theItem)
438 {
439 Container* theContainer = GetContainerFromPool();
440 if (NULL == theContainer) theContainer = CreateContainer();
441 if (NULL == theContainer) return false;
442 Associate(theItem, *theContainer);
443 item_tree.Insert(*theContainer);
444 return true;
445 } // end ProtoSortedQueue::Insert()
446
447 void ProtoSortedQueue::Remove(Item& theItem)
448 {
449 Container* theContainer = static_cast<Container*>(ProtoQueue::GetContainer(theItem));
450 if (NULL != theContainer)
451 {
452 item_tree.Remove(*theContainer);
453 Disassociate(theItem, *theContainer);
454 if (NULL != container_pool)
455 container_pool->Put(*theContainer);
456 else
457 delete theContainer;
458 }
459 } // end ProtoSortedQueue::Remove()
460
461 void ProtoSortedQueue::Empty()
462 {
463 Container* nextContainer;
464 ProtoSortedTree::Iterator iterator(item_tree);
465 while (NULL != (nextContainer = static_cast<Container*>(iterator.GetNextItem())))
466 {
467 ProtoQueue::Item* nextItem = nextContainer->GetItem();
468 ASSERT(NULL != nextItem);
469 Disassociate(*nextItem, *nextContainer);
470 if (NULL != container_pool)
471 container_pool->Put(*nextContainer);
472 else
473 delete nextContainer;
474 }
475 item_tree.Empty();
476 } // end ProtoSortedQueue::Empty()
477
478 void ProtoSortedQueue::Destroy()
479 {
480 Container* nextContainer;
481 ProtoSortedTree::Iterator iterator(item_tree);
482 while (NULL != (nextContainer = static_cast<Container*>(iterator.GetNextItem())))
483 {
484 ProtoQueue::Item* nextItem = nextContainer->GetItem();
485 ASSERT(NULL != nextItem);
486 Disassociate(*nextItem, *nextContainer);
487 delete nextItem;
488 if (NULL != container_pool)
489 container_pool->Put(*nextContainer);
490 else
491 delete nextContainer;
492 }
493 item_tree.Empty();
494 } // end ProtoSortedQueue::Destroy()
495
496 ProtoTree::Endian ProtoSortedQueue::GetEndian() const
497 {
498 return ProtoTree::ENDIAN_BIG; // BIG ENDIAN by default
499 }
500
501 bool ProtoSortedQueue::UseComplement2() const
502 {
503 return true;
504 } // end ProtoSortedQueue::UseComplement2()
505
506 bool ProtoSortedQueue::UseSignBit() const
507 {
508 return false;
509 } // end ProtoSortedQueue::UseSignBit()
510
511 ProtoSortedQueue::Iterator::Iterator(ProtoSortedQueue& theQueue,
512 bool reverse,
513 const char* keyMin,
514 unsigned int keysize)
515 : ProtoSortedTree::Iterator(theQueue.item_tree, reverse, keyMin, keysize)
516 {
517 }
518
519 ProtoSortedQueue::Iterator::~Iterator()
520 {
521 }
522
523 ProtoSortedQueue::Container::Container()
524 {
525 }
526
527 ProtoSortedQueue::Container::~Container()
528 {
529 Cleanup();
530 }
531
532 const char* ProtoSortedQueue::Container::GetKey() const
533 {
534 ProtoQueue::Item* item = GetItem();
535 ASSERT(NULL != item);
536 ProtoSortedQueue* sq = static_cast<ProtoSortedQueue*>(GetQueue());
537 return (sq->GetKey(*item));
538 } // end ProtoSortedQueue::Container::GetKey()
539
540 unsigned int ProtoSortedQueue::Container::GetKeysize() const
541 {
542 ProtoQueue::Item* item = GetItem();
543 ASSERT(NULL != item);
544 ProtoSortedQueue* sq = static_cast<ProtoSortedQueue*>(GetQueue());
545 return (sq->GetKeysize(*item));
546 } // end ProtoSortedQueue::Container::GetKeysize()
547
548
549 ProtoTree::Endian ProtoSortedQueue::Container::GetEndian() const
550 {
551 ProtoSortedQueue* sq = static_cast<ProtoSortedQueue*>(GetQueue());
552 ASSERT(NULL != sq);
553 return (sq->GetEndian());
554 } // end ProtoSortedQueue::Container::GetEndian()
555
556 bool ProtoSortedQueue::Container::UseComplement2() const
557 {
558 ProtoSortedQueue* sq = static_cast<ProtoSortedQueue*>(GetQueue());
559 ASSERT(NULL != sq);
560 return (sq->UseComplement2());
561 } // end ProtoSortedQueue::Container::UseComplement2()
562
563 bool ProtoSortedQueue::Container::UseSignBit() const
564 {
565 ProtoSortedQueue* sq = static_cast<ProtoSortedQueue*>(GetQueue());
566 ASSERT(NULL != sq);
567 return (sq->UseSignBit());
568 } // end ProtoSortedQueue::Container::UseSignBit()
569