Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_Unbounded_Queue Class Template Reference

A Queue of "infinite" length. More...

#include <Unbounded_Queue.h>

Inheritance diagram for ACE_Unbounded_Queue:

Inheritance graph
[legend]
Collaboration diagram for ACE_Unbounded_Queue:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Unbounded_Queue_Iterator<
T > 		ITERATOR
typedef ACE_Unbounded_Queue_Const_Iterator<
T > 		CONST_ITERATOR

Public Methods

 ACE_Unbounded_Queue (ACE_Allocator *alloc=0)
 Construction. Use user specified allocation strategy if specified. More...

 ACE_Unbounded_Queue (const ACE_Unbounded_Queue< T > &)
 Copy constructor. More...

void operator= (const ACE_Unbounded_Queue< T > &)
 Assignment operator. More...

 ~ACE_Unbounded_Queue (void)
 Destructor. More...

int is_empty (void) const
 Returns 1 if the container is empty, otherwise returns 0. More...

int is_full (void) const
 Returns 0. More...

int enqueue_tail (const T &new_item)
 Adds new_item to the tail of the queue. Returns 0 on success, -1 on failure. More...

int enqueue_head (const T &new_item)
 Adds new_item to the head of the queue. Returns 0 on success, -1 on failure. More...

int dequeue_head (T &item)
 Removes and returns the first item on the queue. Returns 0 on success, -1 if the queue was empty. More...

void reset (void)
 Reset the ACE_Unbounded_Queue to be empty and release all its dynamically allocated resources. More...

int 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. More...

int set (const T &item, size_t slot)
 Set the slot th element of the queue to item. More...

size_t size (void) const
 The number of items in the queue. More...

void dump (void) const
 Dump the state of an object. More...

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. More...


Protected Methods

void delete_nodes (void)
 Delete all the nodes in the queue. More...

void copy_nodes (const ACE_Unbounded_Queue< T > &)
 Copy nodes into this queue. More...


Protected Attributes

ACE_Node< T > * head_
 Pointer to the dummy node in the circular linked Queue. More...

size_t cur_size_
 Current size of the queue. More...

ACE_Allocator * allocator_
 Allocation Strategy of the queue. More...


Friends

class ACE_Unbounded_Queue_Iterator< T >
class ACE_Unbounded_Queue_Const_Iterator< T >

Detailed Description

template<class T>
class ACE_Unbounded_Queue< 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 149 of file Unbounded_Queue.h.

Member Typedef Documentation

template<class T>
typedef ACE_Unbounded_Queue_Const_Iterator<T> ACE_Unbounded_Queue::CONST_ITERATOR
 

Definition at line 157 of file Unbounded_Queue.h.

template<class T>
typedef ACE_Unbounded_Queue_Iterator<T> ACE_Unbounded_Queue::ITERATOR
 

Definition at line 156 of file Unbounded_Queue.h.

Constructor & Destructor Documentation

template<class T>
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 23 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC, allocator_, head_, and ACE_Allocator::instance. 

00024   : head_ (0),
00025     cur_size_ (0),
00026     allocator_ (alloc)
00027 {
00028   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (void)");
00029 
00030   if (this->allocator_ == 0)
00031     this->allocator_ = ACE_Allocator::instance ();
00032 
00033   ACE_NEW_MALLOC (this->head_,
00034                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00035                   ACE_Node<T>);
00036   // Make the list circular by pointing it back to itself.
00037   this->head_->next_ = this->head_;
00038 }

template<class T>
ACE_Unbounded_Queue< T >::ACE_Unbounded_Queue (  const ACE_Unbounded_Queue< T > &    ) 
 

Copy constructor.

Initialize the queue to be a copy of the provided queue.

Definition at line 41 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC, allocator_, copy_nodes, head_, and ACE_Allocator::instance. 

00042   : head_ (0),
00043     cur_size_ (0),
00044     allocator_ (us.allocator_)
00045 {
00046   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue");
00047 
00048   if (this->allocator_ == 0)
00049     this->allocator_ = ACE_Allocator::instance ();
00050 
00051   ACE_NEW_MALLOC (this->head_,
00052                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00053                   ACE_Node<T>);
00054   this->head_->next_ = this->head_;
00055   this->copy_nodes (us);
00056 }

template<class T>
ACE_Unbounded_Queue< T >::~ACE_Unbounded_Queue (  void    ) 
 

Destructor.

Clean up the memory for the queue.

Definition at line 144 of file Unbounded_Queue.cpp.

References ACE_DES_FREE_TEMPLATE, delete_nodes, and head_. 

00145 {
00146   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)");
00147 
00148   this->delete_nodes ();
00149   ACE_DES_FREE_TEMPLATE (head_,
00150                          this->allocator_->free,
00151                          ACE_Node,
00152                          <T>);
00153   this->head_ = 0;
00154 }

Member Function Documentation

template<class T>
ACE_Unbounded_Queue_Iterator< T > ACE_Unbounded_Queue< T >::begin (  void    ) 
 

Definition at line 71 of file Unbounded_Queue.cpp. 

00072 {
00073   // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin");
00074   return ACE_Unbounded_Queue_Iterator<T> (*this);
00075 }

template<class T>
void ACE_Unbounded_Queue< T >::copy_nodes (  const ACE_Unbounded_Queue< T > &    )  [protected]
 

Copy nodes into this queue.

Definition at line 108 of file Unbounded_Queue.cpp.

References delete_nodes, enqueue_tail, head_, ACE_Node::item_, and ACE_Node::next_.

Referenced by ACE_Unbounded_Queue, and operator=. 

00109 {
00110   for (ACE_Node<T> *curr = us.head_->next_;
00111        curr != us.head_;
00112        curr = curr->next_)
00113     if (this->enqueue_tail (curr->item_) == -1)
00114       // @@ What's the right thing to do here?
00115       this->delete_nodes ();
00116 }

template<class T>
void ACE_Unbounded_Queue< T >::delete_nodes (  void    )  [protected]
 

Delete all the nodes in the queue.

Definition at line 119 of file Unbounded_Queue.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, and ACE_Node::next_.

Referenced by copy_nodes, operator=, reset, and ~ACE_Unbounded_Queue. 

00120 {
00121   for (ACE_Node<T> *curr = this->head_->next_;
00122        // Keep looking until we've hit the dummy node.
00123        curr != this->head_;
00124        )
00125     {
00126       ACE_Node<T> *temp = curr;
00127       curr = curr->next_;
00128 
00129       ACE_DES_FREE_TEMPLATE (temp,
00130                              this->allocator_->free,
00131                              ACE_Node,
00132                              <T>);
00133       this->cur_size_--;
00134       // @@ Doesnt make sense to have this check since
00135       // this will always be true.
00136       //   ACE_ASSERT (this->cur_size_ >= 0);
00137     }
00138 
00139   // Reset the list to be a circular list with just a dummy node.
00140   this->head_->next_ = this->head_;
00141 }

template<class T>
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 207 of file Unbounded_Queue.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, is_empty, ACE_Node::item_, and ACE_Node::next_.

Referenced by ACE_Select_Reactor_Notify::purge_pending_notifications, and ACE_Dev_Poll_Reactor_Notify::purge_pending_notifications. 

00208 {
00209   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head");
00210 
00211   // Check for empty queue.
00212   if (this->is_empty ())
00213     return -1;
00214 
00215   ACE_Node<T> *temp = this->head_->next_;
00216 
00217   item = temp->item_;
00218   this->head_->next_ = temp->next_;
00219   ACE_DES_FREE_TEMPLATE (temp,
00220                          this->allocator_->free,
00221                          ACE_Node,
00222                          <T>);
00223   --this->cur_size_;
00224   return 0;
00225 }

template<class T>
void ACE_Unbounded_Queue< T >::dump (  void    )  const
 

Dump the state of an object.

Definition at line 85 of file Unbounded_Queue.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_LIB_TEXT, ACE_Unbounded_Queue_Iterator::advance, LM_DEBUG, and ACE_Unbounded_Queue_Iterator::next. 

00086 {
00087   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dump");
00088 
00089   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00090   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_ = %u"), this->head_));
00091   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
00092   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
00093 
00094   T *item = 0;
00095 #if !defined (ACE_NLOGGING)
00096   size_t count = 1;
00097 #endif /* ! ACE_NLOGGING */
00098 
00099   for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this);
00100        iter.next (item) != 0;
00101        iter.advance ())
00102     ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++));
00103 
00104   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00105 }

template<class T>
ACE_Unbounded_Queue_Iterator< T > ACE_Unbounded_Queue< T >::end (  void    ) 
 

Definition at line 78 of file Unbounded_Queue.cpp. 

00079 {
00080   // ACE_TRACE ("ACE_Unbounded_Queue<T>::end");
00081   return ACE_Unbounded_Queue_Iterator<T> (*this, 1);
00082 }

template<class T>
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 157 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC_RETURN, cur_size_, and head_.

Referenced by ACE_Select_Reactor_Notify::purge_pending_notifications, and ACE_Dev_Poll_Reactor_Notify::purge_pending_notifications. 

00158 {
00159   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head");
00160 
00161   ACE_Node<T> *temp;
00162 
00163   // Create a new node that points to the original head.
00164   ACE_NEW_MALLOC_RETURN (temp,
00165                          ACE_static_cast(ACE_Node<T> *,
00166                            this->allocator_->malloc (sizeof (ACE_Node<T>))),
00167                          ACE_Node<T> (new_item, this->head_->next_),
00168                          -1);
00169   // Link this pointer into the front of the list.  Note that the
00170   // "real" head of the queue is <head_->next_>, whereas <head_> is
00171   // just a pointer to the dummy node.
00172   this->head_->next_ = temp;
00173 
00174   this->cur_size_++;
00175   return 0;
00176 }

template<class T>
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 179 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC_RETURN, cur_size_, and head_.

Referenced by copy_nodes, and set. 

00180 {
00181   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail");
00182 
00183   // Insert <item> into the old dummy node location.  Note that this
00184   // isn't actually the "head" item in the queue, it's a dummy node at
00185   // the "tail" of the queue...
00186   this->head_->item_ = new_item;
00187 
00188   ACE_Node<T> *temp;
00189 
00190   // Create a new dummy node.
00191   ACE_NEW_MALLOC_RETURN (temp,
00192                          ACE_static_cast(ACE_Node<T> *,
00193                            this->allocator_->malloc (sizeof (ACE_Node<T>))),
00194                          ACE_Node<T> (this->head_->next_),
00195                          -1);
00196   // Link this dummy pointer into the list.
00197   this->head_->next_ = temp;
00198 
00199   // Point the head to the new dummy node.
00200   this->head_ = temp;
00201 
00202   this->cur_size_++;
00203   return 0;
00204 }

template<class T>
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 236 of file Unbounded_Queue.cpp.

References cur_size_, head_, ACE_Node::item_, and ACE_Node::next_. 

00237 {
00238   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::get");
00239 
00240   ACE_Node<T> *curr = this->head_->next_;
00241 
00242   size_t i;
00243 
00244   for (i = 0; i < this->cur_size_; i++)
00245     {
00246       if (i == slot)
00247         break;
00248 
00249       curr = curr->next_;
00250     }
00251 
00252   if (i < this->cur_size_)
00253     {
00254       item = &curr->item_;
00255       return 0;
00256     }
00257   else
00258     return -1;
00259 }

template<class T>
ACE_INLINE int ACE_Unbounded_Queue< T >::is_empty (  void    )  const
 

Returns 1 if the container is empty, otherwise returns 0.

Constant time check to see if the queue is empty.

Definition at line 10 of file Unbounded_Queue.inl.

References head_.

Referenced by dequeue_head. 

00011 {
00012   //  ACE_TRACE ("ACE_Unbounded_Queue<T>::is_empty");
00013   return this->head_ == this->head_->next_;
00014 }

template<class T>
ACE_INLINE int ACE_Unbounded_Queue< T >::is_full (  void    )  const
 

Returns 0.

The queue cannot be full, so it always returns 0.

Definition at line 17 of file Unbounded_Queue.inl. 

00018 {
00019   //  ACE_TRACE ("ACE_Unbounded_Queue<T>::is_full");
00020   return 0; // We should implement a "node of last resort for this..."
00021 }

template<class T>
void ACE_Unbounded_Queue< T >::operator= (  const ACE_Unbounded_Queue< T > &    ) 
 

Assignment operator.

Perform a deep copy of rhs.

Definition at line 59 of file Unbounded_Queue.cpp.

References copy_nodes, and delete_nodes. 

00060 {
00061   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::operator=");
00062 
00063   if (this != &us)
00064     {
00065       this->delete_nodes ();
00066       this->copy_nodes (us);
00067     }
00068 }

template<class T>
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 228 of file Unbounded_Queue.cpp.

References ACE_TRACE, and delete_nodes. 

00229 {
00230   ACE_TRACE ("reset");
00231 
00232   this->delete_nodes ();
00233 }

template<class T>
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 262 of file Unbounded_Queue.cpp.

References cur_size_, enqueue_tail, head_, ACE_Node::item_, and ACE_Node::next_. 

00264 {
00265   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::set");
00266 
00267   ACE_Node<T> *curr = this->head_->next_;
00268 
00269   size_t i;
00270 
00271   for (i = 0;
00272        i < slot && i < this->cur_size_;
00273        i++)
00274     curr = curr->next_;
00275 
00276   if (i < this->cur_size_)
00277     {
00278       // We're in range, so everything's cool.
00279       curr->item_ = item;
00280       return 0;
00281     }
00282   else
00283     {
00284       // We need to expand the list.
00285 
00286       // A common case will be increasing the set size by 1.
00287       // Therefore, we'll optimize for this case.
00288       if (i == slot)
00289         {
00290           // Try to expand the size of the set by 1.
00291           if (this->enqueue_tail (item) == -1)
00292             return -1;
00293           else
00294             return 0;
00295         }
00296       else
00297         {
00298           T dummy;
00299 
00300           // We need to expand the list by multiple (dummy) items.
00301           for (; i < slot; i++)
00302             {
00303               // This head points to the existing dummy node, which is
00304               // about to be overwritten when we add the new dummy
00305               // node.
00306               curr = this->head_;
00307 
00308               // Try to expand the size of the set by 1, but don't
00309               // store anything in the dummy node (yet).
00310               if (this->enqueue_tail (dummy) == -1)
00311                 return -1;
00312             }
00313 
00314           curr->item_ = item;
00315           return 0;
00316         }
00317     }
00318 }

template<class T>
ACE_INLINE 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 4 of file Unbounded_Queue.inl.

References cur_size_.

Referenced by ACE_Select_Reactor_Notify::purge_pending_notifications, and ACE_Dev_Poll_Reactor_Notify::purge_pending_notifications. 

00005 {
00006   return this->cur_size_;
00007 }

Friends And Related Function Documentation

template<class T>
friend class ACE_Unbounded_Queue_Const_Iterator< T > [friend]
 

Definition at line 153 of file Unbounded_Queue.h.

template<class T>
friend class ACE_Unbounded_Queue_Iterator< T > [friend]
 

Definition at line 152 of file Unbounded_Queue.h.

Member Data Documentation

template<class T>
ACE_Unbounded_Queue::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 262 of file Unbounded_Queue.h.

template<class T>
ACE_Allocator* ACE_Unbounded_Queue::allocator_ [protected]
 

Allocation Strategy of the queue.

Definition at line 278 of file Unbounded_Queue.h.

Referenced by ACE_Unbounded_Queue.

template<class T>
size_t ACE_Unbounded_Queue::cur_size_ [protected]
 

Current size of the queue.

Definition at line 275 of file Unbounded_Queue.h.

Referenced by delete_nodes, dequeue_head, enqueue_head, enqueue_tail, get, set, and size.

template<class T>
ACE_Node<T>* ACE_Unbounded_Queue::head_ [protected]
 

Pointer to the dummy node in the circular linked Queue.

Definition at line 272 of file Unbounded_Queue.h.

Referenced by ACE_Unbounded_Queue, copy_nodes, delete_nodes, dequeue_head, enqueue_head, enqueue_tail, get, is_empty, set, and ~ACE_Unbounded_Queue.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:58:50 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002