Debian Codegraph @

protolib/include/protoQueue.h

raw
1 #ifndef _PROTO_QUEUE
2 #define _PROTO_QUEUE
3
4 /**
5 * @class ProtoQueue
6 *
7 * @brief The ProtoQueue base class allows creation of various data
8 * structures that have Items that may be listed (included)
9 * in multiple, different queues. The queue management classes
10 * defined here allow derived ProtoQueue classes to use different
11 * data organization techniques and a couple of basic types are
12 * provided here that use the more basic Protolib data structure
13 * classes like "ProtoList", "ProtoTree",and "ProtoSortedTree"
14 *
15 * A ProtoQueue::Item may be a member of multiple, different queues
16 * (and even different types of queues since the ProtoQueue::Container
17 * determines how the item is sorted, etc, if applicable). However,
18 * note that only one instance of an individual ProtoQueue::Item may
19 * may be included in a given list. (i.e. an item can't be in the same
20 * list twice or more)
21 *
22 */
23
24 #include "protoDefs.h"
25 #include "protoTree.h"
26 #include "protoDebug.h"
27
28 class ProtoQueue
29 {
30 public:
31 class Item;
32
33 virtual ~ProtoQueue();
34
35 virtual void Remove(Item& item) = 0;
36
37 // returns true if item is in other queue besides this one
38 bool IsInOtherQueue(Item& item)
39 {return item.IsInOtherQueue(*this);}
40
41 bool Contains(Item& item) const
42 {return (NULL != item.GetContainer(*this));}
43
44 // Derived classes MUST implement the
45 // Empty() method _and_ call it in
46 // their destructor!
47 virtual void Empty() = 0;
48
49 /**
50 * @class Container
51 *
52 * @brief The "ProtoQueue::Container is a base class
53 * that enables ProtoQueue:Items to keep track of the
54 * ProtoQueues in which they are included. The intention
55 * here is that derived ProtoQueue subclasses will extend
56 * the "Container" as needed to keep whatever state is
57 * needed for the given data structure type.
58 */
59
60 // TBD - can we make Container _privately_ derive from ProtoTree::Item
61 // to avoid the need for the "Entry" member (i.e. save some space)
62
63 class ContainerPool;
64
65 class Container
66 {
67 friend class ProtoQueue;
68 friend class Item;
69 friend class ContainerPool;
70
71 public:
72 virtual ~Container();
73
74 Item* GetItem() const
75 {return item;}
76 ProtoQueue* GetQueue() const
77 {return queue;}
78
79 protected:
80 Container();
81
82 // Note: Any derived classes MUST call this Cleanup() method in
83 // their destructor to guarantee that no indirect calls
84 // to virtual functions are made in the ~Container()
85 // destructor.
86 void Cleanup();
87
88 private:
89 void Associate(Item& theItem, ProtoQueue& theQueue)
90 {
91 item = &theItem;
92 queue = &theQueue;
93 }
94 void Disassociate()
95 {
96 item = NULL;
97 queue = NULL;
98 }
99 void SetQueue(ProtoQueue& theQueue)
100 {queue = &theQueue;}
101
102 /**
103 * @class Entry
104 *
105 * @brief used by ProtoQueue::Item for their
106 * list of Containers (and hence ProtoQueue)
107 * (this list is keyed by the ProtoQueue*)
108 */
109 class Entry : public ProtoTree::Item
110 {
111 public:
112 Entry(Container& theContainer);
113 Container& GetContainer() const
114 {return container;}
115
116 const char* GetKey() const
117 {return ((const char*)container.GetQueueHandle());}
118 unsigned int GetKeysize() const
119 {return (sizeof(Container*) << 3);}
120 private:
121 Container& container;
122 }; // end class ProtoQueue::Container::Entry
123 Entry& AccessEntry()
124 {return entry;}
125
126 const ProtoQueue*const* GetQueueHandle() const
127 {return &queue;}
128
129 Item* item;
130 ProtoQueue* queue;
131 Entry entry;
132
133 }; // end class ProtoQueue::Container
134
135 class Item
136 {
137 friend class ProtoQueue;
138
139 public:
140 virtual ~Item();
141
142 bool IsInQueue() const
143 {return (!container_list.IsEmpty());}
144
145 Container* GetContainer(const ProtoQueue& queue) const
146 {
147 const ProtoQueue* ptr = &queue;
148 ProtoQueue::Container::Entry* entry =
149 static_cast<ProtoQueue::Container::Entry*>(container_list.Find((const char*)&ptr, sizeof(ProtoQueue*) << 3));
150 return ((NULL != entry) ? &entry->GetContainer() : NULL);
151 }
152
153 protected:
154 Item();
155
156 // Note derived classes MUST call this Cleanup()
157 // method in their destructor so the Item is safely
158 // removed from any queues in which it still resides.
159 // It can't be safely done in the Item base class
160 // destructor since the derived ProtoQueue type may
161 // depend upon extensions to this Item base class for
162 // the specific data structure it uses.
163 void Cleanup();
164
165 private:
166 bool IsInOtherQueue(const ProtoQueue& queue);
167
168 void Reference(ProtoQueue::Container& container)
169 {container_list.Insert(container.AccessEntry());}
170 void Dereference(ProtoQueue::Container& container)
171 {
172 ASSERT(this == container.GetItem());
173 container_list.Remove(container.AccessEntry());
174 }
175
176 // These members are for use by traversals and
177 // other queue manipulations as needed
178 ProtoTree container_list;
179
180 }; // end class ProtoQueue::Item
181
182
183 /**
184 * @class ProtoQueue::ContainerPool
185 *
186 * @brief Container repository. Note that a ContainerPool
187 * should ony be used to cache a single (i.e. homogeneous) type
188 * of Container (i.e. Container subclass) otherwise one
189 * may not "Get()" what one expects from the pool!
190 */
191 class ContainerPool : public ProtoTree::ItemPool
192 {
193 public:
194 ContainerPool();
195 virtual ~ContainerPool();
196
197 Container* Get()
198 {
199 Container::Entry* entry = static_cast<Container::Entry*>(ProtoTree::ItemPool::Get());
200 return ((NULL != entry) ? &(entry->GetContainer()) : NULL);
201 }
202
203 void Put(Container& theContainer)
204 {ProtoTree::ItemPool::Put(theContainer.AccessEntry());}
205
206 void Destroy();
207
208 }; // end class ProtoQueue::ContainerPool
209
210 protected:
211 ProtoQueue(bool usePool = false); // can optionally use the "builtin_container_pool"
212 ProtoQueue(ContainerPool* containerPool); // can optionally use an external container pool
213
214 void TransferContainer(Container& container, ProtoQueue& dstQueue)
215 {
216 Item* item = container.GetItem();
217 ASSERT(NULL != item);
218 item->Dereference(container);
219 container.SetQueue(dstQueue);
220 item->Reference(container);
221 }
222
223 Container* GetContainer(const Item& item) const
224 {return item.GetContainer(*this);}
225
226 Container* GetContainerFromPool()
227 {return ((NULL != container_pool) ? container_pool->Get() : NULL);}
228
229 void Associate(Item& item, Container& container)
230 {
231 container.Associate(item, *this);
232 item.container_list.Insert(container.AccessEntry());
233 }
234 void Disassociate(Item& item, Container& container)
235 {
236 item.container_list.Remove(container.AccessEntry());
237 container.Disassociate();
238 }
239
240 ContainerPool builtin_container_pool;
241 ContainerPool* container_pool;
242
243 }; // end class ProtoQueue
244
245
246 /**
247 * @class ProtoSimpleQueue
248 *
249 * @brief Functional and base class that provides a linked-list (based on ProtoList)
250 * queue. It can hold any kind of ProtoQueue::Item, but one can use
251 * the "ProtoSimpleQueueTemplate" below to create variants with easier-to-use
252 * iterators, etc for specific (derived) ProtoQueue::Item types
253 */
254 class ProtoSimpleQueue : public ProtoQueue
255 {
256 public:
257 class Container;
258 class ContainerPool;
259
260 ProtoSimpleQueue(bool usePool = false);
261 ProtoSimpleQueue(ContainerPool* containerPool);
262 virtual ~ProtoSimpleQueue();
263
264
265 bool Prepend(Item& theItem);
266 bool Append(Item& theItem);
267 bool Insert(Item& theItem, Item& nextItem); // insert "theItem" before "nextItem"
268 bool InsertAfter(Item& theItem, Item& prevItem); // insert "theItem" after "prevItem"
269 void Remove(Item& theItem);
270
271 Item* GetHead() const
272 {
273 Container* container = item_list.GetHead();
274 return ((NULL != container) ? container->GetItem() : NULL);
275 }
276 Item* RemoveHead();
277 Item* GetTail() const
278 {
279 Container* container = item_list.GetTail();
280 return ((NULL != container) ? container->GetItem() : NULL);
281 }
282 Item* RemoveTail();
283
284 Item* GetPrev(Item& item) const
285 {
286 const Container* container = static_cast<Container*>(GetContainer(item));
287 if (NULL != container)
288 {
289 container = static_cast<const Container*>(container->GetPrev());
290 return ((NULL != container) ? container->GetItem() : NULL);
291 }
292 else
293 {
294 return NULL;
295 }
296 }
297
298 bool IsEmpty() const
299 {return (NULL != GetHead()) ? false : true;}
300
301 void Empty(); // empties queue, but doesn't delete items
302
303 void Destroy(); // empties queue, deleting items
304
305 // TBD - add set operations
306 /*
307 const bool Union(ProtoSimpleQueue &unionQueue, const ProtoSimpleQueue &bQueue);
308 const bool Intersection(ProtoSimpleQueue &intersectionQueue, const ProtoSimpleQueue &bQueue);
309 const bool RelativeComplement(ProtoSimpleQueue &rcQueue, const ProtoSimpleQueue &bQueue);//(a - intersection of ab)
310 const bool SymmetricDifference(ProtoSimpleQueue &rcQueue, const ProtoSimpleQueue &bQueue);//(union of relative complements)
311
312 bool Union(const ProtoSimpleQueue &bQueue);
313 bool Intersection(const ProtoSimpleQueue &bQueue);
314 bool RelativeComplement(const ProtoSimpleQueue &bQueue);//(a - intersection of ab)
315 bool SymmetricDifference(const ProtoSimpleQueue &bQueue);//(union of relative complements)
316 */
317
318 class Iterator : private ProtoList::Iterator
319 {
320 public:
321 Iterator(ProtoSimpleQueue& theQueue, bool reverse = false);
322 virtual ~Iterator();
323
324 void Reset(bool reverse = false)
325 {ProtoList::Iterator::Reset(reverse);}
326
327 ProtoQueue::Item* GetNextItem()
328 {
329 Container* nextContainer = static_cast<Container*>(ProtoList::Iterator::GetNextItem());
330 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
331 }
332 ProtoQueue::Item* PeekNextItem() const
333 {
334 Container* nextContainer = static_cast<Container*>(ProtoList::Iterator::PeekNextItem());
335 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
336 }
337 ProtoQueue::Item* GetPrevItem()
338 {
339 Container* nextContainer = static_cast<Container*>(ProtoList::Iterator::GetPrevItem());
340 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
341 }
342 ProtoQueue::Item* PeekPrevItem() const
343 {
344 Container* nextContainer = static_cast<Container*>(ProtoList::Iterator::PeekPrevItem());
345 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
346 }
347 }; // end class ProtoSimpleQueue::Iterator
348
349 class Container : public ProtoQueue::Container, public ProtoList::Item
350 {
351 public:
352 Container();
353 ~Container();
354 }; // end class ProtoSimpleQueue::Container
355
356 class ContainerPool : public ProtoQueue::ContainerPool
357 {
358 public:
359 void Put(Container& theContainer)
360 {ProtoQueue::ContainerPool::Put(theContainer);}
361 Container* Get()
362 {return static_cast<Container*>(ProtoQueue::ContainerPool::Get());}
363 }; // end class ProtoSimpleQueue::ContainerPool
364
365 private:
366 // TBD - do we want to make CreateContainer() virtual so derived classes can do more?
367 Container* CreateContainer() const
368 {return new Container;}
369 Container* GetContainerFromPool()
370 {return static_cast<Container*>(ProtoQueue::GetContainerFromPool());}
371 void RemoveContainer(Container* theContainer, Item& theItem); // returns container to pool or deletes it
372 class List : public ProtoListTemplate<Container> {};
373 List item_list;
374
375 }; // end class ProtoSimpleQueue
376
377 template <class ITEM_TYPE>
378 class ProtoSimpleQueueTemplate : public ProtoSimpleQueue
379 {
380 public:
381 ProtoSimpleQueueTemplate(bool usePool = false)
382 : ProtoSimpleQueue(usePool) {}
383 ProtoSimpleQueueTemplate(ContainerPool* containerPool)
384 : ProtoSimpleQueue(containerPool) {}
385 virtual ~ProtoSimpleQueueTemplate() {}
386
387 ITEM_TYPE* GetHead() const
388 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::GetHead());}
389 ITEM_TYPE* RemoveHead()
390 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::RemoveHead());}
391 ITEM_TYPE* GetTail() const
392 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::GetTail());}
393 ITEM_TYPE* RemoveTail()
394 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::RemoveTail());}
395 ITEM_TYPE* GetPrev(ITEM_TYPE& item)
396 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::GetPrev(item));}
397
398 class Iterator : public ProtoSimpleQueue::Iterator
399 {
400 public:
401 Iterator(ProtoSimpleQueueTemplate& theQueue, bool reverse = false)
402 : ProtoSimpleQueue::Iterator(theQueue, reverse) {}
403 ~Iterator() {}
404
405 void Reset(bool reverse = false)
406 {ProtoSimpleQueue::Iterator::Reset(reverse);}
407
408 ITEM_TYPE* GetNextItem()
409 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::Iterator::GetNextItem());}
410 ITEM_TYPE* PeekNextItem() const
411 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::Iterator::PeekNextItem());}
412 ITEM_TYPE* GetPrevItem()
413 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::Iterator::GetPrevItem());}
414 ITEM_TYPE* PeekPrevItem() const
415 {return static_cast<ITEM_TYPE*>(ProtoSimpleQueue::Iterator::PeekPrevItem());}
416
417 }; // end class ProtoSimpleQueueTemplate::Iterator
418
419 }; // end class ProtoSimpleQueueTemplate
420
421
422 /* ProtoSimpleQueueTemplate usage example
423
424 class MyItem : public ProtoQueue::Item
425 {
426 };
427
428 class MyList : public ProtoSimpleQueue<MyItem> {};
429
430 MyList list;
431
432 list.Add(item)
433 list.Remove(item)
434
435 MyList::Iterator it;
436
437 MyItem* nextItem = it.GetNextItem() ...
438
439 */
440
441 class ProtoIndexedQueue : public ProtoQueue
442 {
443 public:
444 virtual ~ProtoIndexedQueue();
445
446 // Insert the "item" into the tree (will fail if item with equivalent key already in tree)
447 bool Insert(Item& item);
448
449 // Remove the "item" from the tree
450 void Remove(Item& item);
451
452 bool IsEmpty() const
453 {return item_tree.IsEmpty();}
454
455 // Find item with exact match to "key" and "keysize" (keysize is in bits)
456 Item* Find(const char* key, unsigned int keysize) const
457 {
458 Container* container = item_tree.Find(key, keysize);
459 return ((NULL != container) ? container->GetItem() : NULL);
460 }
461
462 Item* FindString(const char* keyString) const
463 {return Find(keyString, (unsigned int)(8*strlen(keyString)));}
464
465 Item* FindClosestMatch(const char* key, unsigned int keysize) const
466 {
467 Container* container = item_tree.FindClosestMatch(key, keysize);
468 return ((NULL != container) ? container->GetItem() : NULL);
469 }
470
471 // Find item which is largest prefix of the "key" (keysize is in bits)
472 Item* FindPrefix(const char* key, unsigned int keysize) const
473 {
474 Container* container = item_tree.FindPrefix(key, keysize);
475 return ((NULL != container) ? container->GetItem() : NULL);
476 }
477
478 void Empty(); // empties queue, but doesn't delete items
479
480 void Destroy(); // empties queue, deleting items
481
482 // Required overrides for ProtoIndexedQueue subclasses
483 // (Override these to determine how items are sorted)
484 virtual const char* GetKey(const Item& item) const = 0;
485 virtual unsigned int GetKeysize(const Item& item) const = 0;
486
487 class Container : public ProtoQueue::Container, public ProtoTree::Item
488 {
489 public:
490 Container();
491 ~Container();
492
493 private:
494 // Required ProtoTree::Item overrides
495 const char* GetKey() const;
496 unsigned int GetKeysize() const;
497
498 }; // end class ProtoIndexedQueue::Container
499
500 class ContainerPool : public ProtoQueue::ContainerPool
501 {
502 public:
503 void Put(Container& theContainer)
504 {ProtoQueue::ContainerPool::Put(theContainer);}
505 Container* Get()
506 {return static_cast<Container*>(ProtoQueue::ContainerPool::Get());}
507 }; // end class ProtoIndexedQueue::ContainerPool
508
509 class Iterator : public ProtoTree::Iterator
510 {
511 public:
512 Iterator(ProtoIndexedQueue& theQueue, bool reverse = false);
513 virtual ~Iterator();
514
515 void Reset(bool reverse = false,
516 const char* prefix = NULL,
517 unsigned int prefixSize = 0)
518 {ProtoTree::Iterator::Reset(reverse, prefix, prefixSize);}
519
520 Item* GetNextItem()
521 {
522 Container* nextContainer = static_cast<Container*>(ProtoTree::Iterator::GetNextItem());
523 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
524 }
525 Item* PeekNextItem()
526 {
527 Container* nextContainer = static_cast<Container*>(ProtoTree::Iterator::PeekNextItem());
528 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
529 }
530 Item* GetPrevItem()
531 {
532 Container* nextContainer = static_cast<Container*>(ProtoTree::Iterator::GetPrevItem());
533 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
534 }
535 Item* PeekPrevItem()
536 {
537 Container* nextContainer = static_cast<Container*>(ProtoTree::Iterator::PeekPrevItem());
538 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
539 }
540 }; // end class ProtoIndexedQueue::Iterator
541
542 protected:
543 ProtoIndexedQueue(bool usePool = false);
544 ProtoIndexedQueue(ContainerPool* containerPool);
545 Container* CreateContainer() const
546 {return new Container;}
547 Container* GetContainerFromPool()
548 {return static_cast<Container*>(ProtoQueue::GetContainerFromPool());}
549
550 private:
551 class Tree : public ProtoTreeTemplate<Container> {};
552 Tree item_tree;
553
554 }; // end class ProtoIndexedQueue
555
556 template <class ITEM_TYPE>
557 class ProtoIndexedQueueTemplate : public ProtoIndexedQueue
558 {
559 public:
560 virtual ~ProtoIndexedQueueTemplate() {}
561
562 // Required overrides to determine indexing
563 virtual const char* GetKey(const Item& item) const = 0;
564 virtual unsigned int GetKeysize(const Item& item) const = 0;
565
566 // Insert the "item" into the tree (will fail if item with equivalent key already in tree)
567 //bool Insert(ITEM_TYPE& item)
568 // {return ProtoIndexedQueue::Insert(item);}
569
570 // Remove the "item" from the tree
571 // LJT THIS HAD BEEN COMMENTED OUT
572 void Remove(ITEM_TYPE& item)
573 {return ProtoIndexedQueue::Remove(item);}
574
575 // Find item with exact match to "key" and "keysize" (keysize is in bits)
576 ITEM_TYPE* Find(const char* key, unsigned int keysize) const
577 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::Find(key, keysize));}
578
579 ITEM_TYPE* FindString(const char* keyString) const
580 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::FindString(keyString));}
581
582 ITEM_TYPE* FindClosestMatch(const char* key, unsigned int keysize) const
583 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::FindClosestMatch(key, keysize));}
584
585 // Find item which is largest prefix of the "key" (keysize is in bits)
586 ITEM_TYPE* FindPrefix(const char* key, unsigned int keysize) const
587 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::FindPrefix(key, keysize));}
588
589 class Iterator : public ProtoIndexedQueue::Iterator
590 {
591 public:
592 Iterator(ProtoIndexedQueueTemplate<ITEM_TYPE>& theQueue, bool reverse = false)
593 : ProtoIndexedQueue::Iterator(theQueue, reverse) {}
594 ~Iterator() {}
595
596 void Reset(bool reverse = false,
597 const char* prefix = NULL,
598 unsigned int prefixSize = 0)
599 {ProtoIndexedQueue::Iterator::Reset(reverse, prefix, prefixSize);}
600
601 ITEM_TYPE* GetNextItem()
602 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::Iterator::GetNextItem());}
603 ITEM_TYPE* PeekNextItem()
604 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::Iterator::PeekNextItem());}
605 ITEM_TYPE* GetPrevItem()
606 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::Iterator::GetPrevItem());}
607 ITEM_TYPE* PeekPrevItem()
608 {return static_cast<ITEM_TYPE*>(ProtoIndexedQueue::Iterator::PeekPrevItem());}
609 }; // end class ProtoIndexedQueueTemplate::Iterator
610
611 protected:
612 ProtoIndexedQueueTemplate(bool usePool = false)
613 : ProtoIndexedQueue(usePool) {}
614 ProtoIndexedQueueTemplate(ContainerPool* containerPool)
615 : ProtoIndexedQueue(containerPool) {}
616
617 private:
618 using ProtoIndexedQueue::Remove; // gets rid of hidden overloaded virtual function warning
619
620 }; // end class ProtoIndexedQueueTemplate
621
622 /*
623 // ProtoIndexedQueueTemplate usage example
624
625 class MyItem : public ProtoQueue::Item
626 {
627
628 };
629
630 class MyQueue public ProtoIndexedQueueTemplate<MyItem>
631 {
632 // 1) SHOULD implement constructors to determine use of Container pooling
633 MyQueue(bool usePool = false) : ProtoIndexedQueueTemplate<MyItem>(usePool) {}
634 MyQueue(ContainerPool* externalPool) : ProtoIndexedQueueTemplate<MyItem>(externalPool) {}
635
636 // 2) MUST implement these required overrides to determine indexing (i.e. sorting)
637 // (Note different ProtoIndexedQueue variants can implement these
638 // differently to have different indexing / sorting behaviors)
639 const char* GetKey(const Item& item) const
640 {return static_cast<const MyItem&>(item).GetKey();}
641 unsigned int GetKeysize(const Item& item) const
642 {return static_cast<const MyItem&>(item).GetKeysize();}
643 };
644
645 MyQueue queue;
646 MyItem item;
647 queue.Insert(item)
648 queue.Remove(item)
649 queue.FindItem() ...
650
651 MyQueue::Iterator it;
652
653 MyItem* nextItem = it.GetNextItem() ...
654
655 */
656
657 class ProtoSortedQueue : public ProtoQueue
658 {
659 public:
660 virtual ~ProtoSortedQueue();
661
662 // Insert the "item" into the tree (multiple items with same key is OK)
663 bool Insert(Item& item);
664
665 // Remove the "item" from the tree
666 void Remove(Item& item);
667
668 bool IsEmpty() const
669 {return item_tree.IsEmpty();}
670
671 // Find first item with exact match to "key" and "keysize" (keysize is in bits)
672 Item* Find(const char* key, unsigned int keysize) const
673 {
674 Container* container = item_tree.Find(key, keysize);
675 return ((NULL != container) ? container->GetItem() : NULL);
676 }
677
678 Item* GetHead() const
679 {
680 Container* head = item_tree.GetHead();
681 return ((NULL != head) ? head->GetItem() : NULL);
682 }
683
684 Item* GetTail() const
685 {
686 Container* tail = item_tree.GetTail();
687 return ((NULL != tail) ? tail->GetItem() : NULL);
688 }
689
690 void Empty(); // empties queue, but doesn't delete items
691
692 void Destroy(); // empties queue, deleting items
693
694 // Required overrides for ProtoSortedQueue subclasses
695 // (Override these to determine how items are sorted)
696 virtual const char* GetKey(const Item& item) const = 0;
697 virtual unsigned int GetKeysize(const Item& item) const = 0;
698
699 // Optional overrides for additional sorting control
700 virtual ProtoTree::Endian GetEndian() const;
701 virtual bool UseComplement2() const;
702 virtual bool UseSignBit() const;
703
704 class Container : public ProtoQueue::Container, public ProtoSortedTree::Item
705 {
706 public:
707 Container();
708 virtual ~Container();
709
710 private:
711 // Required ProtoTree::Item overrides
712 // (Note these can only be called while the
713 // Container is "associated" with a ProtoSortedQueue)
714 const char* GetKey() const;
715 unsigned int GetKeysize() const;
716 ProtoTree::Endian GetEndian() const;
717 bool UseComplement2() const;
718 bool UseSignBit() const;
719
720 }; // end class ProtoSortedQueue::Container
721
722 class ContainerPool : public ProtoQueue::ContainerPool
723 {
724 public:
725 void Put(Container& theContainer)
726 {ProtoQueue::ContainerPool::Put(theContainer);}
727 Container* Get()
728 {return static_cast<Container*>(ProtoQueue::ContainerPool::Get());}
729 }; // end class ProtoSortedQueue::ContainerPool
730
731 class Iterator : public ProtoSortedTree::Iterator
732 {
733 public:
734 Iterator(ProtoSortedQueue& theQueue,
735 bool reverse = false,
736 const char* keyMin = NULL,
737 unsigned int keysize = 0);
738 virtual ~Iterator();
739
740 void Reset(bool reverse = false,
741 const char* keyMin = NULL,
742 unsigned int keysize = 0)
743 {ProtoSortedTree::Iterator::Reset(reverse, keyMin, keysize);}
744
745 void SetCursor(ProtoSortedQueue& theQueue, ProtoQueue::Item& theItem)
746 {
747 Container* container = static_cast<ProtoSortedQueue::Container*>(theItem.GetContainer(theQueue));
748 ProtoSortedTree::Iterator::SetCursor(container);
749 }
750
751 Item* GetNextItem()
752 {
753 Container* nextContainer = static_cast<Container*>(ProtoSortedTree::Iterator::GetNextItem());
754 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
755 }
756 Item* PeekNextItem()
757 {
758 Container* nextContainer = static_cast<Container*>(ProtoSortedTree::Iterator::PeekNextItem());
759 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
760 }
761 Item* GetPrevItem()
762 {
763 Container* nextContainer = static_cast<Container*>(ProtoSortedTree::Iterator::GetPrevItem());
764 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
765 }
766 Item* PeekPrevItem()
767 {
768 Container* nextContainer = static_cast<Container*>(ProtoSortedTree::Iterator::PeekPrevItem());
769 return ((NULL != nextContainer) ? nextContainer->GetItem() : NULL);
770 }
771 }; // end class ProtoSortedQueue::Iterator
772
773 protected:
774 ProtoSortedQueue(bool usePool = false);
775 ProtoSortedQueue(ContainerPool* containerPool);
776 Container* CreateContainer() const
777 {return new Container;}
778 Container* GetContainerFromPool()
779 {return static_cast<Container*>(ProtoQueue::GetContainerFromPool());}
780
781 private:
782 class Tree : public ProtoSortedTreeTemplate<Container> {};
783 Tree item_tree;
784
785 }; // end class ProtoSortedQueue
786
787 template <class ITEM_TYPE>
788 class ProtoSortedQueueTemplate : public ProtoSortedQueue
789 {
790 public:
791 virtual ~ProtoSortedQueueTemplate() {}
792
793 // Required overrides to determine sorting index of enqueued items
794 virtual const char* GetKey(const Item& item) const = 0;
795 virtual unsigned int GetKeysize(const Item& item) const = 0;
796
797 // Optional overrides to fine tune sorting further
798 virtual ProtoTree::Endian GetEndian() const
799 {return ProtoSortedQueue::GetEndian();}
800 virtual bool UseComplement2() const
801 {return ProtoSortedQueue::UseComplement2();}
802 virtual bool UseSignBit() const
803 {return ProtoSortedQueue::UseSignBit();}
804
805 // Insert the "item" into the tree
806 bool Insert(ITEM_TYPE& item)
807 {return ProtoSortedQueue::Insert(item);}
808
809 // Remove the "item" from the tree
810 void Remove(ITEM_TYPE& item)
811 {ProtoSortedQueue::Remove(static_cast<Item&>(item));}
812
813 // Find firat item with exact match to "key" and "keysize" (keysize is in bits)
814 ITEM_TYPE* Find(const char* key, unsigned int keysize) const
815 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::Find(key, keysize));}
816
817 ITEM_TYPE* GetHead() const
818 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::GetHead());}
819 ITEM_TYPE* GetTail() const
820 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::GetTail());}
821
822 class Iterator : public ProtoSortedQueue::Iterator
823 {
824 public:
825 Iterator(ProtoSortedQueueTemplate& theQueue, bool reverse = false,
826 const char* keyMin = NULL, unsigned int keysize = 0)
827 : ProtoSortedQueue::Iterator(theQueue, reverse, keyMin, keysize) {}
828 ~Iterator() {}
829
830 void Reset(bool reverse = false)
831 {ProtoSortedQueue::Iterator::Reset(reverse);}
832
833 ITEM_TYPE* GetNextItem()
834 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::Iterator::GetNextItem());}
835 ITEM_TYPE* PeekNextItem()
836 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::Iterator::PeekNextItem());}
837 ITEM_TYPE* GetPrevItem()
838 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::Iterator::GetPrevItem());}
839 ITEM_TYPE* PeekPrevItem()
840 {return static_cast<ITEM_TYPE*>(ProtoSortedQueue::Iterator::PeekPrevItem());}
841 }; // end class ProtoSortedQueueTemplate::Iterator
842
843 protected:
844 ProtoSortedQueueTemplate(bool usePool = false)
845 : ProtoSortedQueue(usePool) {}
846 ProtoSortedQueueTemplate(ContainerPool* containerPool)
847 : ProtoSortedQueue(containerPool) {}
848
849 private:
850 using ProtoSortedQueue::Remove; // gets rid of hidden overloaded virtual function warning
851
852 }; // end class ProtoSortedQueueTemplate
853 #endif // _PROTO_QUEUE