Unbounded_Queue.cpp

Go to the documentation of this file.
00001 // Unbounded_Queue.cpp,v 4.9 2006/06/27 13:06:03 jwillemsen Exp
00002 
00003 #ifndef ACE_UNBOUNDED_QUEUE_CPP
00004 #define ACE_UNBOUNDED_QUEUE_CPP
00005 
00006 #include "ace/Unbounded_Queue.h"
00007 
00008 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00009 # pragma once
00010 #endif /* ACE_LACKS_PRAGMA_ONCE */
00011 
00012 #if !defined (__ACE_INLINE__)
00013 #include "ace/Unbounded_Queue.inl"
00014 #endif /* __ACE_INLINE__ */
00015 
00016 #include "ace/Malloc_Base.h"
00017 #include "ace/Log_Msg.h"
00018 #include "ace/os_include/os_errno.h"
00019 
00020 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
00021 
00022 ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Queue)
00023 
00024 template <class T>
00025 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc)
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 }
00041 
00042 template <class T>
00043 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us)
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 }
00059 
00060 template <class T> void
00061 ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us)
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 }
00071 
00072 template <class T> ACE_Unbounded_Queue_Iterator<T>
00073 ACE_Unbounded_Queue<T>::begin (void)
00074 {
00075   // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin");
00076   return ACE_Unbounded_Queue_Iterator<T> (*this);
00077 }
00078 
00079 template <class T> ACE_Unbounded_Queue_Iterator<T>
00080 ACE_Unbounded_Queue<T>::end (void)
00081 {
00082   // ACE_TRACE ("ACE_Unbounded_Queue<T>::end");
00083   return ACE_Unbounded_Queue_Iterator<T> (*this, 1);
00084 }
00085 
00086 template <class T> void
00087 ACE_Unbounded_Queue<T>::dump (void) const
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_LIB_TEXT ("\nhead_ = %u"), this->head_));
00094   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
00095   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_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_LIB_TEXT ("count = %d\n"), count++));
00106 
00107   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00108 #endif /* ACE_HAS_DUMP */
00109 }
00110 
00111 template <class T> void
00112 ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us)
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 }
00121 
00122 template <class T> void
00123 ACE_Unbounded_Queue<T>::delete_nodes (void)
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 }
00146 
00147 template <class T>
00148 ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)
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 }
00159 
00160 template <class T> int
00161 ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item)
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 }
00180 
00181 template <class T> int
00182 ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item)
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 }
00207 
00208 template <class T> int
00209 ACE_Unbounded_Queue<T>::dequeue_head (T &item)
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 }
00228 
00229 template <class T> void
00230 ACE_Unbounded_Queue<T>::reset (void)
00231 {
00232   ACE_TRACE ("reset");
00233 
00234   this->delete_nodes ();
00235 }
00236 
00237 template <class T> int
00238 ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const
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 }
00262 
00263 template <class T> int
00264 ACE_Unbounded_Queue<T>::set (const T &item,
00265                              size_t slot)
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 dummy;
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 }
00321 
00322 // ****************************************************************
00323 
00324 template <class T> void
00325 ACE_Unbounded_Queue_Const_Iterator<T>::dump (void) const
00326 {
00327 #if defined (ACE_HAS_DUMP)
00328   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::dump");
00329 #endif /* ACE_HAS_DUMP */
00330 }
00331 
00332 template <class T>
00333 ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end)
00334   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
00335     queue_ (q)
00336 {
00337   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator");
00338 }
00339 
00340 template <class T> int
00341 ACE_Unbounded_Queue_Const_Iterator<T>::advance (void)
00342 {
00343   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::advance");
00344   this->current_ = this->current_->next_;
00345   return this->current_ != this->queue_.head_;
00346 }
00347 
00348 template <class T> int
00349 ACE_Unbounded_Queue_Const_Iterator<T>::first (void)
00350 {
00351   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::first");
00352   this->current_ = this->queue_.head_->next_;
00353   return this->current_ != this->queue_.head_;
00354 }
00355 
00356 template <class T> int
00357 ACE_Unbounded_Queue_Const_Iterator<T>::done (void) const
00358 {
00359   ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::done");
00360 
00361   return this->current_ == this->queue_.head_;
00362 }
00363 
00364 template <class T> int
00365 ACE_Unbounded_Queue_Const_Iterator<T>::next (T *&item)
00366 {
00367   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::next");
00368   if (this->current_ == this->queue_.head_)
00369     return 0;
00370   else
00371     {
00372       item = &this->current_->item_;
00373       return 1;
00374     }
00375 }
00376 
00377 // ****************************************************************
00378 
00379 template <class T> void
00380 ACE_Unbounded_Queue_Iterator<T>::dump (void) const
00381 {
00382 #if defined (ACE_HAS_DUMP)
00383   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump");
00384 #endif /* ACE_HAS_DUMP */
00385 }
00386 
00387 template <class T>
00388 ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end)
00389   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
00390     queue_ (q)
00391 {
00392   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator");
00393 }
00394 
00395 template <class T> int
00396 ACE_Unbounded_Queue_Iterator<T>::advance (void)
00397 {
00398   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance");
00399   this->current_ = this->current_->next_;
00400   return this->current_ != this->queue_.head_;
00401 }
00402 
00403 template <class T> int
00404 ACE_Unbounded_Queue_Iterator<T>::first (void)
00405 {
00406   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first");
00407   this->current_ = this->queue_.head_->next_;
00408   return this->current_ != this->queue_.head_;
00409 }
00410 
00411 template <class T> int
00412 ACE_Unbounded_Queue_Iterator<T>::done (void) const
00413 {
00414   ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done");
00415 
00416   return this->current_ == this->queue_.head_;
00417 }
00418 
00419 template <class T> int
00420 ACE_Unbounded_Queue_Iterator<T>::next (T *&item)
00421 {
00422   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next");
00423   if (this->current_ == this->queue_.head_)
00424     return 0;
00425   else
00426     {
00427       item = &this->current_->item_;
00428       return 1;
00429     }
00430 }
00431 
00432 ACE_END_VERSIONED_NAMESPACE_DECL
00433 
00434 #endif /* ACE_UNBOUNDED_QUEUE_CPP */

Generated on Thu Nov 9 09:42:08 2006 for ACE by doxygen 1.3.6