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

Unbounded_Queue.cpp

Go to the documentation of this file.
00001 // $Id: Unbounded_Queue.cpp,v 1.1.1.2 2003/02/21 18:36:32 chad Exp $
00002 
00003 #ifndef ACE_UNBOUNDED_QUEUE_C
00004 #define ACE_UNBOUNDED_QUEUE_C
00005 
00006 #include "ace/Unbounded_Queue.h"
00007 #include "ace/Malloc_Base.h"
00008 #include "ace/Log_Msg.h"
00009 
00010 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00011 # pragma once
00012 #endif /* ACE_LACKS_PRAGMA_ONCE */
00013 
00014 #if !defined (__ACE_INLINE__)
00015 #include "ace/Unbounded_Queue.inl"
00016 #endif /* __ACE_INLINE__ */
00017 
00018 ACE_RCSID(ace, Unbounded_Queue, "$Id: Unbounded_Queue.cpp,v 1.1.1.2 2003/02/21 18:36:32 chad Exp $")
00019 
00020 ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Queue)
00021 
00022 template <class T>
00023 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc)
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 }
00039 
00040 template <class T>
00041 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us)
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 }
00057 
00058 template <class T> void
00059 ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us)
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 }
00069 
00070 template <class T> ACE_Unbounded_Queue_Iterator<T>
00071 ACE_Unbounded_Queue<T>::begin (void)
00072 {
00073   // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin");
00074   return ACE_Unbounded_Queue_Iterator<T> (*this);
00075 }
00076 
00077 template <class T> ACE_Unbounded_Queue_Iterator<T>
00078 ACE_Unbounded_Queue<T>::end (void)
00079 {
00080   // ACE_TRACE ("ACE_Unbounded_Queue<T>::end");
00081   return ACE_Unbounded_Queue_Iterator<T> (*this, 1);
00082 }
00083 
00084 template <class T> void
00085 ACE_Unbounded_Queue<T>::dump (void) const
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 }
00106 
00107 template <class T> void
00108 ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us)
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 }
00117 
00118 template <class T> void
00119 ACE_Unbounded_Queue<T>::delete_nodes (void)
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 }
00142 
00143 template <class T>
00144 ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)
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 }
00155 
00156 template <class T> int
00157 ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item)
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 }
00177 
00178 template <class T> int
00179 ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item)
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 }
00205 
00206 template <class T> int
00207 ACE_Unbounded_Queue<T>::dequeue_head (T &item)
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 }
00226 
00227 template <class T> void
00228 ACE_Unbounded_Queue<T>::reset (void)
00229 {
00230   ACE_TRACE ("reset");
00231 
00232   this->delete_nodes ();
00233 }
00234 
00235 template <class T> int
00236 ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const
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 }
00260 
00261 template <class T> int
00262 ACE_Unbounded_Queue<T>::set (const T &item,
00263                              size_t slot)
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 }
00319 
00320 // ****************************************************************
00321 
00322 template <class T> void
00323 ACE_Unbounded_Queue_Const_Iterator<T>::dump (void) const
00324 {
00325   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::dump");
00326 }
00327 
00328 template <class T>
00329 ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end)
00330   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
00331     queue_ (q)
00332 {
00333   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator");
00334 }
00335 
00336 template <class T> int
00337 ACE_Unbounded_Queue_Const_Iterator<T>::advance (void)
00338 {
00339   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::advance");
00340   this->current_ = this->current_->next_;
00341   return this->current_ != this->queue_.head_;
00342 }
00343 
00344 template <class T> int
00345 ACE_Unbounded_Queue_Const_Iterator<T>::first (void)
00346 {
00347   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::first");
00348   this->current_ = this->queue_.head_->next_;
00349   return this->current_ != this->queue_.head_;
00350 }
00351 
00352 template <class T> int
00353 ACE_Unbounded_Queue_Const_Iterator<T>::done (void) const
00354 {
00355   ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::done");
00356 
00357   return this->current_ == this->queue_.head_;
00358 }
00359 
00360 template <class T> int
00361 ACE_Unbounded_Queue_Const_Iterator<T>::next (T *&item)
00362 {
00363   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::next");
00364   if (this->current_ == this->queue_.head_)
00365     return 0;
00366   else
00367     {
00368       item = &this->current_->item_;
00369       return 1;
00370     }
00371 }
00372 
00373 // ****************************************************************
00374 
00375 template <class T> void
00376 ACE_Unbounded_Queue_Iterator<T>::dump (void) const
00377 {
00378   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump");
00379 }
00380 
00381 template <class T>
00382 ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end)
00383   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
00384     queue_ (q)
00385 {
00386   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator");
00387 }
00388 
00389 template <class T> int
00390 ACE_Unbounded_Queue_Iterator<T>::advance (void)
00391 {
00392   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance");
00393   this->current_ = this->current_->next_;
00394   return this->current_ != this->queue_.head_;
00395 }
00396 
00397 template <class T> int
00398 ACE_Unbounded_Queue_Iterator<T>::first (void)
00399 {
00400   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first");
00401   this->current_ = this->queue_.head_->next_;
00402   return this->current_ != this->queue_.head_;
00403 }
00404 
00405 template <class T> int
00406 ACE_Unbounded_Queue_Iterator<T>::done (void) const
00407 {
00408   ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done");
00409 
00410   return this->current_ == this->queue_.head_;
00411 }
00412 
00413 template <class T> int
00414 ACE_Unbounded_Queue_Iterator<T>::next (T *&item)
00415 {
00416   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next");
00417   if (this->current_ == this->queue_.head_)
00418     return 0;
00419   else
00420     {
00421       item = &this->current_->item_;
00422       return 1;
00423     }
00424 }
00425 
00426 #endif /* ACE_UNBOUNDED_QUEUE_C */

Generated on Mon Jun 16 11:22:00 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002