A Queue of "infinite" length. More...
#include <Unbounded_Queue.h>
Public Types | |
typedef ACE_Unbounded_Queue_Iterator < T > | ITERATOR |
typedef ACE_Unbounded_Queue_Const_Iterator < T > | CONST_ITERATOR |
Public Member Functions | |
ACE_Unbounded_Queue (ACE_Allocator *alloc=0) | |
ACE_Unbounded_Queue (const ACE_Unbounded_Queue< T > &) | |
Copy constructor. | |
void | operator= (const ACE_Unbounded_Queue< T > &) |
Assignment operator. | |
~ACE_Unbounded_Queue (void) | |
Destructor. | |
bool | is_empty (void) const |
Returns true if the container is empty, otherwise returns false. | |
bool | is_full (void) const |
Returns 0. | |
int | enqueue_tail (const T &new_item) |
int | enqueue_head (const T &new_item) |
int | dequeue_head (T &item) |
void | reset (void) |
int | get (T *&item, size_t slot=0) const |
int | set (const T &item, size_t slot) |
Set the slot th element of the queue to item. | |
size_t | size (void) const |
The number of items in the queue. | |
void | dump (void) const |
Dump the state of an object. | |
ACE_Unbounded_Queue_Iterator< T > | begin (void) |
ACE_Unbounded_Queue_Iterator< T > | end (void) |
Public Attributes | |
ACE_ALLOC_HOOK_DECLARE | |
Declare the dynamic allocation hooks. | |
Protected Member Functions | |
void | delete_nodes (void) |
Delete all the nodes in the queue. | |
void | copy_nodes (const ACE_Unbounded_Queue< T > &) |
Copy nodes into this queue. | |
Protected Attributes | |
ACE_Node< T > * | head_ |
Pointer to the dummy node in the circular linked Queue. | |
size_t | cur_size_ |
Current size of the queue. | |
ACE_Allocator * | allocator_ |
Allocation Strategy of the queue. | |
Friends | |
class | ACE_Unbounded_Queue_Iterator< T > |
class | ACE_Unbounded_Queue_Const_Iterator< T > |
A Queue of "infinite" length.
This implementation of an unbounded queue uses a circular linked list with a dummy node.
Requirements and Performance Characteristics
Definition at line 150 of file Unbounded_Queue.h.
typedef ACE_Unbounded_Queue_Const_Iterator<T> ACE_Unbounded_Queue< T >::CONST_ITERATOR |
Definition at line 158 of file Unbounded_Queue.h.
typedef ACE_Unbounded_Queue_Iterator<T> ACE_Unbounded_Queue< T >::ITERATOR |
Definition at line 157 of file Unbounded_Queue.h.
ACE_Unbounded_Queue< T >::ACE_Unbounded_Queue | ( | ACE_Allocator * | alloc = 0 |
) |
Construction. Use user specified allocation strategy if specified. Initialize an empty queue using the strategy provided.
Definition at line 25 of file Unbounded_Queue.cpp.
: head_ (0), cur_size_ (0), allocator_ (alloc) { // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (void)"); if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); // Make the list circular by pointing it back to itself. this->head_->next_ = this->head_; }
ACE_Unbounded_Queue< T >::ACE_Unbounded_Queue | ( | const ACE_Unbounded_Queue< T > & | us | ) |
Copy constructor.
Initialize the queue to be a copy of the provided queue.
Definition at line 43 of file Unbounded_Queue.cpp.
: head_ (0), cur_size_ (0), allocator_ (us.allocator_) { // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue"); if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); this->head_->next_ = this->head_; this->copy_nodes (us); }
ACE_Unbounded_Queue< T >::~ACE_Unbounded_Queue | ( | void | ) |
Destructor.
Clean up the memory for the queue.
Definition at line 148 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)"); this->delete_nodes (); ACE_DES_FREE_TEMPLATE (head_, this->allocator_->free, ACE_Node, <T>); }
ACE_Unbounded_Queue_Iterator< T > ACE_Unbounded_Queue< T >::begin | ( | void | ) |
Definition at line 73 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin"); return ACE_Unbounded_Queue_Iterator<T> (*this); }
void ACE_Unbounded_Queue< T >::copy_nodes | ( | const ACE_Unbounded_Queue< T > & | us | ) | [protected] |
Copy nodes into this queue.
Definition at line 112 of file Unbounded_Queue.cpp.
{ for (ACE_Node<T> *curr = us.head_->next_; curr != us.head_; curr = curr->next_) if (this->enqueue_tail (curr->item_) == -1) // @@ What's the right thing to do here? this->delete_nodes (); }
void ACE_Unbounded_Queue< T >::delete_nodes | ( | void | ) | [protected] |
Delete all the nodes in the queue.
Definition at line 123 of file Unbounded_Queue.cpp.
{ for (ACE_Node<T> *curr = this->head_->next_; // Keep looking until we've hit the dummy node. curr != this->head_; ) { ACE_Node<T> *temp = curr; curr = curr->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); --this->cur_size_; // @@ Doesnt make sense to have this check since // this will always be true. // ACE_ASSERT (this->cur_size_ >= 0); } // Reset the list to be a circular list with just a dummy node. this->head_->next_ = this->head_; }
int ACE_Unbounded_Queue< T >::dequeue_head | ( | T & | item | ) |
Removes and returns the first item on the queue. Returns 0 on success, -1 if the queue was empty. Remove an item from the head of the queue.
Definition at line 208 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head"); // Check for empty queue. if (this->is_empty ()) return -1; ACE_Node<T> *temp = this->head_->next_; item = temp->item_; this->head_->next_ = temp->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); --this->cur_size_; return 0; }
void ACE_Unbounded_Queue< T >::dump | ( | void | ) | const |
Dump the state of an object.
Definition at line 87 of file Unbounded_Queue.cpp.
{ #if defined (ACE_HAS_DUMP) // ACE_TRACE ("ACE_Unbounded_Queue<T>::dump"); ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_ = %u"), this->head_)); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); T *item = 0; #if !defined (ACE_NLOGGING) size_t count = 1; #endif /* ! ACE_NLOGGING */ for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this); iter.next (item) != 0; iter.advance ()) ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("count = %d\n"), count++)); ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); #endif /* ACE_HAS_DUMP */ }
ACE_Unbounded_Queue_Iterator< T > ACE_Unbounded_Queue< T >::end | ( | void | ) |
Definition at line 80 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::end"); return ACE_Unbounded_Queue_Iterator<T> (*this, 1); }
int ACE_Unbounded_Queue< T >::enqueue_head | ( | const T & | new_item | ) |
Adds new_item to the head of the queue. Returns 0 on success, -1 on failure. Insert an item at the head of the queue.
Definition at line 160 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head"); ACE_Node<T> *temp = 0; // Create a new node that points to the original head. ACE_NEW_MALLOC_RETURN (temp, static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))), ACE_Node<T> (new_item, this->head_->next_), -1); // Link this pointer into the front of the list. Note that the // "real" head of the queue is <head_->next_>, whereas <head_> is // just a pointer to the dummy node. this->head_->next_ = temp; ++this->cur_size_; return 0; }
int ACE_Unbounded_Queue< T >::enqueue_tail | ( | const T & | new_item | ) |
Adds new_item to the tail of the queue. Returns 0 on success, -1 on failure. Insert an item at the end of the queue.
Definition at line 181 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail"); // Insert <item> into the old dummy node location. Note that this // isn't actually the "head" item in the queue, it's a dummy node at // the "tail" of the queue... this->head_->item_ = new_item; ACE_Node<T> *temp = 0; // Create a new dummy node. ACE_NEW_MALLOC_RETURN (temp, static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))), ACE_Node<T> (this->head_->next_), -1); // Link this dummy pointer into the list. this->head_->next_ = temp; // Point the head to the new dummy node. this->head_ = temp; ++this->cur_size_; return 0; }
int ACE_Unbounded_Queue< T >::get | ( | T *& | item, | |
size_t | slot = 0 | |||
) | const |
Get the slot th element in the set. Returns -1 if the element isn't in the range {0..cur_size_ - 1}, else 0. Find the item in the queue between 0 and the provided index of the queue.
Definition at line 237 of file Unbounded_Queue.cpp.
bool ACE_Unbounded_Queue< T >::is_empty | ( | void | ) | const |
Returns true if the container is empty, otherwise returns false.
Constant time check to see if the queue is empty.
Definition at line 14 of file Unbounded_Queue.inl.
bool ACE_Unbounded_Queue< T >::is_full | ( | void | ) | const |
Returns 0.
The queue cannot be full, so it always returns 0.
Definition at line 21 of file Unbounded_Queue.inl.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::is_full"); return false; // We should implement a "node of last resort for this..." }
void ACE_Unbounded_Queue< T >::operator= | ( | const ACE_Unbounded_Queue< T > & | us | ) |
Assignment operator.
Perform a deep copy of rhs.
Definition at line 61 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::operator="); if (this != &us) { this->delete_nodes (); this->copy_nodes (us); } }
void ACE_Unbounded_Queue< T >::reset | ( | void | ) |
Reset the ACE_Unbounded_Queue to be empty and release all its dynamically allocated resources. Delete the queue nodes.
Definition at line 229 of file Unbounded_Queue.cpp.
{ ACE_TRACE ("reset"); this->delete_nodes (); }
int ACE_Unbounded_Queue< T >::set | ( | const T & | item, | |
size_t | slot | |||
) |
Set the slot th element of the queue to item.
Set the slot th element in the set. Will pad out the set with empty nodes if slot is beyond the range {0..cur_size_ - 1}. Returns -1 on failure, 0 if slot isn't initially in range, and 0 otherwise.
Definition at line 263 of file Unbounded_Queue.cpp.
{ // ACE_TRACE ("ACE_Unbounded_Queue<T>::set"); ACE_Node<T> *curr = this->head_->next_; size_t i; for (i = 0; i < slot && i < this->cur_size_; ++i) curr = curr->next_; if (i < this->cur_size_) { // We're in range, so everything's cool. curr->item_ = item; return 0; } else { // We need to expand the list. // A common case will be increasing the set size by 1. // Therefore, we'll optimize for this case. if (i == slot) { // Try to expand the size of the set by 1. if (this->enqueue_tail (item) == -1) return -1; else return 0; } else { T const dummy = T (); // We need to expand the list by multiple (dummy) items. for (; i < slot; ++i) { // This head points to the existing dummy node, which is // about to be overwritten when we add the new dummy // node. curr = this->head_; // Try to expand the size of the set by 1, but don't // store anything in the dummy node (yet). if (this->enqueue_tail (dummy) == -1) return -1; } curr->item_ = item; return 0; } } }
size_t ACE_Unbounded_Queue< T >::size | ( | void | ) | const |
The number of items in the queue.
Return the size of the queue.
Definition at line 8 of file Unbounded_Queue.inl.
{ return this->cur_size_; }
friend class ACE_Unbounded_Queue_Const_Iterator< T > [friend] |
Definition at line 154 of file Unbounded_Queue.h.
friend class ACE_Unbounded_Queue_Iterator< T > [friend] |
Definition at line 153 of file Unbounded_Queue.h.
ACE_Unbounded_Queue< T >::ACE_ALLOC_HOOK_DECLARE |
Declare the dynamic allocation hooks.
Definition at line 263 of file Unbounded_Queue.h.
ACE_Allocator* ACE_Unbounded_Queue< T >::allocator_ [protected] |
Allocation Strategy of the queue.
Definition at line 279 of file Unbounded_Queue.h.
size_t ACE_Unbounded_Queue< T >::cur_size_ [protected] |
Current size of the queue.
Definition at line 276 of file Unbounded_Queue.h.
ACE_Node<T>* ACE_Unbounded_Queue< T >::head_ [protected] |
Pointer to the dummy node in the circular linked Queue.
Definition at line 273 of file Unbounded_Queue.h.