Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages | Search for 

ACE_Unbounded_Queue< T > Class Template Reference

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

#include <Unbounded_Queue.h>

Collaboration diagram for ACE_Unbounded_Queue< T >:

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

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

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

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 150 of file Unbounded_Queue.h.

Member Typedef Documentation

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

Definition at line 158 of file Unbounded_Queue.h.

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

Definition at line 157 of file Unbounded_Queue.h.

Constructor & Destructor Documentation

template<class T>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL ACE_Unbounded_Queue< T >::ACE_Unbounded_Queue (  ACE_Allocator *  alloc = 0  ) 
 

Initialize an empty queue using the strategy provided.

Definition at line 25 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC, and ACE_Allocator::instance(). 

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

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 43 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC, ACE_Unbounded_Queue< T >::copy_nodes(), and ACE_Allocator::instance(). 

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

template<class T>
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.

References ACE_DES_FREE_TEMPLATE, and ACE_Unbounded_Queue< T >::delete_nodes(). 

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

Member Function Documentation

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

Definition at line 73 of file Unbounded_Queue.cpp. 

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

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

Copy nodes into this queue.

Definition at line 112 of file Unbounded_Queue.cpp.

References ACE_Unbounded_Queue< T >::delete_nodes(), ACE_Unbounded_Queue< T >::enqueue_tail(), ACE_Unbounded_Queue< T >::head_, ACE_Node< T >::item_, and ACE_Node< T >::next_.

Referenced by ACE_Unbounded_Queue< T >::ACE_Unbounded_Queue(), and ACE_Unbounded_Queue< T >::operator=(). 

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

template<class T>
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.

References ACE_DES_FREE_TEMPLATE, and ACE_Node< T >::next_.

Referenced by ACE_Unbounded_Queue< T >::copy_nodes(), ACE_Unbounded_Queue< T >::operator=(), ACE_Unbounded_Queue< T >::reset(), and ACE_Unbounded_Queue< T >::~ACE_Unbounded_Queue(). 

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

template<class T>
int ACE_Unbounded_Queue< T >::dequeue_head (  T &  item  ) 
 

Remove an item from the head of the queue.

Definition at line 209 of file Unbounded_Queue.cpp.

References ACE_DES_FREE_TEMPLATE, ACE_Unbounded_Queue< T >::is_empty(), ACE_Node< T >::item_, and ACE_Node< T >::next_.

Referenced by ACE_Priority_Reactor::dispatch_io_set(). 

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

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

Dump the state of an object.

Definition at line 87 of file Unbounded_Queue.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_TEXT, ACE_Unbounded_Queue_Iterator< T >::advance(), LM_DEBUG, and ACE_Unbounded_Queue_Iterator< T >::next(). 

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

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

Definition at line 80 of file Unbounded_Queue.cpp. 

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

template<class T>
int ACE_Unbounded_Queue< T >::enqueue_head (  const T &  new_item  ) 
 

Insert an item at the head of the queue.

Definition at line 161 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC_RETURN. 

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

template<class T>
int ACE_Unbounded_Queue< T >::enqueue_tail (  const T &  new_item  ) 
 

Insert an item at the end of the queue.

Definition at line 182 of file Unbounded_Queue.cpp.

References ACE_NEW_MALLOC_RETURN.

Referenced by ACE_Priority_Reactor::build_bucket(), ACE_Unbounded_Queue< T >::copy_nodes(), ACE_Service_Gestalt::parse_args_i(), and ACE_Unbounded_Queue< T >::set(). 

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

template<class T>
int ACE_Unbounded_Queue< T >::get (  T *&  item,
size_t  slot = 0
)  const
 

Find the item in the queue between 0 and the provided index of the queue.

Definition at line 238 of file Unbounded_Queue.cpp.

References ACE_Node< T >::item_, and ACE_Node< T >::next_. 

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

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 14 of file Unbounded_Queue.inl.

Referenced by ACE_Unbounded_Queue< T >::dequeue_head(), and ACE_Priority_Reactor::dispatch_io_set(). 

00015 {
00016   //  ACE_TRACE ("ACE_Unbounded_Queue<T>::is_empty");
00017   return this->head_ == this->head_->next_;
00018 }

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 21 of file Unbounded_Queue.inl. 

00022 {
00023   //  ACE_TRACE ("ACE_Unbounded_Queue<T>::is_full");
00024   return 0; // We should implement a "node of last resort for this..."
00025 }

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 61 of file Unbounded_Queue.cpp.

References ACE_Unbounded_Queue< T >::copy_nodes(), and ACE_Unbounded_Queue< T >::delete_nodes(). 

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

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

Delete the queue nodes.

Definition at line 230 of file Unbounded_Queue.cpp.

References ACE_TRACE, and ACE_Unbounded_Queue< T >::delete_nodes().

Referenced by ACE_Priority_Reactor::dispatch_io_set(). 

00231 {
00232   ACE_TRACE ("reset");
00233 
00234   this->delete_nodes ();
00235 }

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 264 of file Unbounded_Queue.cpp.

References ACE_Unbounded_Queue< T >::enqueue_tail(), ACE_Node< T >::item_, and ACE_Node< T >::next_. 

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

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

00009 {
00010   return this->cur_size_;
00011 }

Friends And Related Function Documentation

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

Definition at line 154 of file Unbounded_Queue.h.

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

Definition at line 153 of file Unbounded_Queue.h.

Member Data Documentation

template<class T>
ACE_Unbounded_Queue< T >::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 263 of file Unbounded_Queue.h.

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

Allocation Strategy of the queue.

Definition at line 279 of file Unbounded_Queue.h.

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

Current size of the queue.

Definition at line 276 of file Unbounded_Queue.h.

template<class T>
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.

Referenced by ACE_Unbounded_Queue< T >::copy_nodes().

The documentation for this class was generated from the following files:
Generated on Sun Jan 27 12:59:19 2008 for ACE by doxygen 1.3.6