ACE/ace/Unbounded_Queue.cpp

   1 #ifndef ACE_UNBOUNDED_QUEUE_CPP
   2 #define ACE_UNBOUNDED_QUEUE_CPP
   3
   4 #include "ace/Unbounded_Queue.h"
   5
   6 #if !defined (ACE_LACKS_PRAGMA_ONCE)
   7 # pragma once
   8 #endif /* ACE_LACKS_PRAGMA_ONCE */
   9
  10 #if !defined (__ACE_INLINE__)
  11 #include "ace/Unbounded_Queue.inl"
  12 #endif /* __ACE_INLINE__ */
  13
  14 #include "ace/Malloc_Base.h"
  15 #include "ace/Log_Category.h"
  16 #include "ace/os_include/os_errno.h"
  17
  18 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  19
  20 ACE_ALLOC_HOOK_DEFINE_Tc(ACE_Unbounded_Queue)
  21
  22 template <class T>
  23 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc)
  24   : head_ (0),
  25     cur_size_ (0),
  26     allocator_ (alloc)
  27 {
  28   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue ()");
  29
  30   if (this->allocator_ == 0)
  31     this->allocator_ = ACE_Allocator::instance ();
  32
  33   ACE_NEW_MALLOC (this->head_,
  34                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
  35                   ACE_Node<T>);
  36   // Make the list circular by pointing it back to itself.
  37   this->head_->next_ = this->head_;
  38 }
  39
  40 template <class T>
  41 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us)
  42   : head_ (0),
  43     cur_size_ (0),
  44     allocator_ (us.allocator_)
  45 {
  46   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue");
  47
  48   if (this->allocator_ == 0)
  49     this->allocator_ = ACE_Allocator::instance ();
  50
  51   ACE_NEW_MALLOC (this->head_,
  52                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
  53                   ACE_Node<T>);
  54   this->head_->next_ = this->head_;
  55   this->copy_nodes (us);
  56 }
  57
  58 template <class T> void
  59 ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us)
  60 {
  61   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::operator=");
  62
  63   if (this != &us)
  64     {
  65       this->delete_nodes ();
  66       this->copy_nodes (us);
  67     }
  68 }
  69
  70 template <class T> ACE_Unbounded_Queue_Iterator<T>
  71 ACE_Unbounded_Queue<T>::begin ()
  72 {
  73   // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin");
  74   return ACE_Unbounded_Queue_Iterator<T> (*this);
  75 }
  76
  77 template <class T> ACE_Unbounded_Queue_Iterator<T>
  78 ACE_Unbounded_Queue<T>::end ()
  79 {
  80   // ACE_TRACE ("ACE_Unbounded_Queue<T>::end");
  81   return ACE_Unbounded_Queue_Iterator<T> (*this, 1);
  82 }
  83
  84 template <class T> void
  85 ACE_Unbounded_Queue<T>::dump () const
  86 {
  87 #if defined (ACE_HAS_DUMP)
  88   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dump");
  89
  90   ACELIB_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  91   ACELIB_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_ = %u"), this->head_));
  92   ACELIB_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
  93   ACELIB_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
  94
  95   T *item = 0;
  96 #if !defined (ACE_NLOGGING)
  97   size_t count = 1;
  98 #endif /* ! ACE_NLOGGING */
  99
 100   for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this);
 101        iter.next (item) != 0;
 102        iter.advance ())
 103     ACELIB_DEBUG ((LM_DEBUG, ACE_TEXT ("count = %d\n"), count++));
 104
 105   ACELIB_DEBUG ((LM_DEBUG, ACE_END_DUMP));
 106 #endif /* ACE_HAS_DUMP */
 107 }
 108
 109 template <class T> void
 110 ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us)
 111 {
 112   for (ACE_Node<T> *curr = us.head_->next_;
 113        curr != us.head_;
 114        curr = curr->next_)
 115     if (this->enqueue_tail (curr->item_) == -1)
 116       // @@ What's the right thing to do here?
 117       this->delete_nodes ();
 118 }
 119
 120 template <class T> void
 121 ACE_Unbounded_Queue<T>::delete_nodes ()
 122 {
 123   for (ACE_Node<T> *curr = this->head_->next_;
 124        // Keep looking until we've hit the dummy node.
 125        curr != this->head_;
 126        )
 127     {
 128       ACE_Node<T> *temp = curr;
 129       curr = curr->next_;
 130
 131       ACE_DES_FREE_TEMPLATE (temp,
 132                              this->allocator_->free,
 133                              ACE_Node,
 134                              <T>);
 135       --this->cur_size_;
 136       // @@ Doesnt make sense to have this check since
 137       // this will always be true.
 138       //   ACE_ASSERT (this->cur_size_ >= 0);
 139     }
 140
 141   // Reset the list to be a circular list with just a dummy node.
 142   this->head_->next_ = this->head_;
 143 }
 144
 145 template <class T>
 146 ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue ()
 147 {
 148   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue ()");
 149
 150   this->delete_nodes ();
 151   ACE_DES_FREE_TEMPLATE (head_,
 152                          this->allocator_->free,
 153                          ACE_Node,
 154                          <T>);
 155 }
 156
 157 template <class T> int
 158 ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item)
 159 {
 160   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head");
 161
 162   ACE_Node<T> *temp = 0;
 163
 164   // Create a new node that points to the original head.
 165   ACE_NEW_MALLOC_RETURN (temp,
 166                          static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))),
 167                          ACE_Node<T> (new_item, this->head_->next_),
 168                          -1);
 169   // Link this pointer into the front of the list.  Note that the
 170   // "real" head of the queue is <head_->next_>, whereas <head_> is
 171   // just a pointer to the dummy node.
 172   this->head_->next_ = temp;
 173
 174   ++this->cur_size_;
 175   return 0;
 176 }
 177
 178 template <class T> int
 179 ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item)
 180 {
 181   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail");
 182
 183   // Insert <item> into the old dummy node location.  Note that this
 184   // isn't actually the "head" item in the queue, it's a dummy node at
 185   // the "tail" of the queue...
 186   this->head_->item_ = new_item;
 187
 188   ACE_Node<T> *temp = 0;
 189
 190   // Create a new dummy node.
 191   ACE_NEW_MALLOC_RETURN (temp,
 192                          static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))),
 193                          ACE_Node<T> (this->head_->next_),
 194                          -1);
 195   // Link this dummy pointer into the list.
 196   this->head_->next_ = temp;
 197
 198   // Point the head to the new dummy node.
 199   this->head_ = temp;
 200
 201   ++this->cur_size_;
 202   return 0;
 203 }
 204
 205 template <class T> int
 206 ACE_Unbounded_Queue<T>::dequeue_head (T &item)
 207 {
 208   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head");
 209
 210   // Check for empty queue.
 211   if (this->is_empty ())
 212     return -1;
 213
 214   ACE_Node<T> *temp = this->head_->next_;
 215
 216   item = temp->item_;
 217   this->head_->next_ = temp->next_;
 218   ACE_DES_FREE_TEMPLATE (temp,
 219                          this->allocator_->free,
 220                          ACE_Node,
 221                          <T>);
 222   --this->cur_size_;
 223   return 0;
 224 }
 225
 226 template <class T> void
 227 ACE_Unbounded_Queue<T>::reset ()
 228 {
 229   ACE_TRACE ("reset");
 230
 231   this->delete_nodes ();
 232 }
 233
 234 template <class T> int
 235 ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const
 236 {
 237   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::get");
 238
 239   ACE_Node<T> *curr = this->head_->next_;
 240
 241   size_t i;
 242
 243   for (i = 0; i < this->cur_size_; i++)
 244     {
 245       if (i == slot)
 246         break;
 247
 248       curr = curr->next_;
 249     }
 250
 251   if (i < this->cur_size_)
 252     {
 253       item = &curr->item_;
 254       return 0;
 255     }
 256   else
 257     return -1;
 258 }
 259
 260 template <class T> int
 261 ACE_Unbounded_Queue<T>::set (const T &item,
 262                              size_t slot)
 263 {
 264   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::set");
 265
 266   ACE_Node<T> *curr = this->head_->next_;
 267
 268   size_t i;
 269
 270   for (i = 0;
 271        i < slot && i < this->cur_size_;
 272        ++i)
 273     curr = curr->next_;
 274
 275   if (i < this->cur_size_)
 276     {
 277       // We're in range, so everything's cool.
 278       curr->item_ = item;
 279       return 0;
 280     }
 281   else
 282     {
 283       // We need to expand the list.
 284
 285       // A common case will be increasing the set size by 1.
 286       // Therefore, we'll optimize for this case.
 287       if (i == slot)
 288         {
 289           // Try to expand the size of the set by 1.
 290           if (this->enqueue_tail (item) == -1)
 291             return -1;
 292           else
 293             return 0;
 294         }
 295       else
 296         {
 297           T const dummy = T ();
 298
 299           // We need to expand the list by multiple (dummy) items.
 300           for (; i < slot; ++i)
 301             {
 302               // This head points to the existing dummy node, which is
 303               // about to be overwritten when we add the new dummy
 304               // node.
 305               curr = this->head_;
 306
 307               // Try to expand the size of the set by 1, but don't
 308               // store anything in the dummy node (yet).
 309               if (this->enqueue_tail (dummy) == -1)
 310                 return -1;
 311             }
 312
 313           curr->item_ = item;
 314           return 0;
 315         }
 316     }
 317 }
 318
 319 // ****************************************************************
 320
 321 template <class T> void
 322 ACE_Unbounded_Queue_Const_Iterator<T>::dump () const
 323 {
 324 #if defined (ACE_HAS_DUMP)
 325   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::dump");
 326 #endif /* ACE_HAS_DUMP */
 327 }
 328
 329 template <class T>
 330 ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end)
 331   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
 332     queue_ (q)
 333 {
 334   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator");
 335 }
 336
 337 template <class T> int
 338 ACE_Unbounded_Queue_Const_Iterator<T>::advance ()
 339 {
 340   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::advance");
 341   this->current_ = this->current_->next_;
 342   return this->current_ != this->queue_.head_;
 343 }
 344
 345 template <class T> int
 346 ACE_Unbounded_Queue_Const_Iterator<T>::first ()
 347 {
 348   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::first");
 349   this->current_ = this->queue_.head_->next_;
 350   return this->current_ != this->queue_.head_;
 351 }
 352
 353 template <class T> int
 354 ACE_Unbounded_Queue_Const_Iterator<T>::done () const
 355 {
 356   ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::done");
 357
 358   return this->current_ == this->queue_.head_;
 359 }
 360
 361 template <class T> int
 362 ACE_Unbounded_Queue_Const_Iterator<T>::next (T *&item)
 363 {
 364   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::next");
 365   if (this->current_ == this->queue_.head_)
 366     return 0;
 367   else
 368     {
 369       item = &this->current_->item_;
 370       return 1;
 371     }
 372 }
 373
 374 // ****************************************************************
 375
 376 template <class T> void
 377 ACE_Unbounded_Queue_Iterator<T>::dump () const
 378 {
 379 #if defined (ACE_HAS_DUMP)
 380   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump");
 381 #endif /* ACE_HAS_DUMP */
 382 }
 383
 384 template <class T>
 385 ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end)
 386   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
 387     queue_ (q)
 388 {
 389   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator");
 390 }
 391
 392 template <class T> int
 393 ACE_Unbounded_Queue_Iterator<T>::advance ()
 394 {
 395   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance");
 396   this->current_ = this->current_->next_;
 397   return this->current_ != this->queue_.head_;
 398 }
 399
 400 template <class T> int
 401 ACE_Unbounded_Queue_Iterator<T>::first ()
 402 {
 403   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first");
 404   this->current_ = this->queue_.head_->next_;
 405   return this->current_ != this->queue_.head_;
 406 }
 407
 408 template <class T> int
 409 ACE_Unbounded_Queue_Iterator<T>::done () const
 410 {
 411   ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done");
 412
 413   return this->current_ == this->queue_.head_;
 414 }
 415
 416 template <class T> int
 417 ACE_Unbounded_Queue_Iterator<T>::next (T *&item)
 418 {
 419   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next");
 420   if (this->current_ == this->queue_.head_)
 421     return 0;
 422   else
 423     {
 424       item = &this->current_->item_;
 425       return 1;
 426     }
 427 }
 428
 429 ACE_END_VERSIONED_NAMESPACE_DECL
 430
 431 #endif /* ACE_UNBOUNDED_QUEUE_CPP */