diff options
author | coryan <coryan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2001-03-26 21:18:51 +0000 |
---|---|---|
committer | coryan <coryan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 2001-03-26 21:18:51 +0000 |
commit | 72f31a3b615b4acf94b679a7f7a39204ace0c381 (patch) | |
tree | d2a03a59e7a8e39f4aeef13f0b7eb07b589b076c /ace | |
parent | 8f8a2ba51de660ba91df2342783c72a930e8b39a (diff) | |
download | ATCD-72f31a3b615b4acf94b679a7f7a39204ace0c381.tar.gz |
ChangeLogTag:Mon Mar 26 13:00:37 2001 Carlos O'Ryan <coryan@uci.edu>
Diffstat (limited to 'ace')
36 files changed, 1838 insertions, 1571 deletions
diff --git a/ace/ARGV.cpp b/ace/ARGV.cpp index fee1fbafe39..a45949285b8 100644 --- a/ace/ARGV.cpp +++ b/ace/ARGV.cpp @@ -1,7 +1,7 @@ // ARGV.cpp // $Id$ -// Transforms a string BUF into an ARGV-style vector of strings. +// Transforms a string BUF into an ARGV-style vector of strings. #include "ace/ARGV.h" #include "ace/Log_Msg.h" @@ -74,7 +74,7 @@ ACE_ARGV::ACE_ARGV (const ACE_TCHAR buf[], // Create this->argv_. if (this->string_to_argv () == -1) - ACE_ERROR ((LM_ERROR, + ACE_ERROR ((LM_ERROR, ACE_LIB_TEXT ("%p\n"), ACE_LIB_TEXT ("string_to_argv"))); } @@ -95,7 +95,7 @@ ACE_ARGV::ACE_ARGV (ACE_TCHAR *argv[], return; int buf_len = 0; - + // Determine the length of the buffer. for (int i = 0; argv[i] != 0; i++) @@ -107,7 +107,7 @@ ACE_ARGV::ACE_ARGV (ACE_TCHAR *argv[], if (this->substitute_env_args_ && (argv[i][0] == '$' && (temp = ACE_OS::getenv (&argv[i][1])) != 0)) - buf_len += ACE_OS::strlen (temp); + buf_len += ACE_OS::strlen (temp); else #endif /* !ACE_LACKS_ENV */ buf_len += ACE_OS::strlen (argv[i]); @@ -151,7 +151,7 @@ ACE_ARGV::ACE_ARGV (ACE_TCHAR *argv[], *end = '\0'; } -ACE_ARGV::ACE_ARGV (ACE_TCHAR *first_argv[], +ACE_ARGV::ACE_ARGV (ACE_TCHAR *first_argv[], ACE_TCHAR *second_argv[], int substitute_env_args) : substitute_env_args_ (substitute_env_args), @@ -236,7 +236,7 @@ ACE_ARGV::add (const ACE_TCHAR *next_arg) // Wipe argv_ and buf_ away so that they will be recreated if the // user calls argv () or buf (). - if (this->argv_ != 0) + if (this->argv_ != 0) { for (int i = 0; this->argv_[i] != 0; i++) ACE_OS::free ((void *) this->argv_[i]); @@ -266,7 +266,7 @@ ACE_ARGV::add (ACE_TCHAR *argv[]) ACE_ARGV::~ACE_ARGV (void) { ACE_TRACE ("ACE_ARGV::~ACE_ARGV"); - + if (this->argv_ != 0) for (int i = 0; this->argv_[i] != 0; i++) ACE_OS::free ((void *) this->argv_[i]); @@ -301,7 +301,7 @@ ACE_ARGV::create_buf_from_queue (void) size_t len; int more = 0; - while (!iter.done ()) + while (!iter.done ()) { // Get next argument from the queue. iter.next (arg); @@ -318,7 +318,7 @@ ACE_ARGV::create_buf_from_queue (void) ptr += len; // Put in an argument separating space. - if (more != 0) + if (more != 0) *ptr++ = ' '; } diff --git a/ace/ARGV.h b/ace/ARGV.h index 29ab8dd0ca5..613af430fed 100644 --- a/ace/ARGV.h +++ b/ace/ARGV.h @@ -21,7 +21,7 @@ # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -#include "ace/Containers.h" +#include "ace/Unbounded_Queue.h" /** * @class ACE_ARGV diff --git a/ace/Array_Base.cpp b/ace/Array_Base.cpp new file mode 100644 index 00000000000..8647a10178e --- /dev/null +++ b/ace/Array_Base.cpp @@ -0,0 +1,203 @@ +// $Id$ + +#ifndef ACE_ARRAY_BASE_C +#define ACE_ARRAY_BASE_C + +#include "ace/Array_Base.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +#if !defined (__ACE_INLINE__) +#include "ace/Array_Base.inl" +#endif /* __ACE_INLINE__ */ + +ACE_RCSID(ace, Array_Base, "$Id$") + + +// Dynamically initialize an array. + +template <class T> +ACE_Array_Base<T>::ACE_Array_Base (size_t size, + ACE_Allocator *alloc) + : max_size_ (size), + cur_size_ (size), + allocator_ (alloc) +{ + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + if (size != 0) + { + ACE_ALLOCATOR (this->array_, + (T *) this->allocator_->malloc (size * sizeof (T))); + for (size_t i = 0; i < size; ++i) + new (&array_[i]) T; + } + else + this->array_ = 0; +} + +template <class T> +ACE_Array_Base<T>::ACE_Array_Base (size_t size, + const T &default_value, + ACE_Allocator *alloc) + : max_size_ (size), + cur_size_ (size), + allocator_ (alloc) +{ + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + if (size != 0) + { + ACE_ALLOCATOR (this->array_, + (T *) this->allocator_->malloc (size * sizeof (T))); + for (size_t i = 0; i < size; ++i) + new (&array_[i]) T (default_value); + } + else + this->array_ = 0; +} + +// The copy constructor (performs initialization). + +template <class T> +ACE_Array_Base<T>::ACE_Array_Base (const ACE_Array_Base<T> &s) + : max_size_ (s.size ()), + cur_size_ (s.size ()), + allocator_ (s.allocator_) +{ + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_ALLOCATOR (this->array_, + (T *) this->allocator_->malloc (s.size () * sizeof (T))); + for (size_t i = 0; i < this->size (); i++) + new (&this->array_[i]) T (s.array_[i]); +} + +// Assignment operator (performs assignment). + +template <class T> void +ACE_Array_Base<T>::operator= (const ACE_Array_Base<T> &s) +{ + // Check for "self-assignment". + + if (this != &s) + { + if (this->max_size_ < s.size ()) + { + ACE_DES_ARRAY_FREE (this->array_, + this->max_size_, + this->allocator_->free, + T); + ACE_ALLOCATOR (this->array_, + (T *) this->allocator_->malloc (s.size () * sizeof (T))); + this->max_size_ = s.size (); + } + else + { + ACE_DES_ARRAY_NOFREE (this->array_, + s.size (), + T); + } + + this->cur_size_ = s.size (); + + for (size_t i = 0; i < this->size (); i++) + new (&this->array_[i]) T (s.array_[i]); + } +} + +// Set an item in the array at location slot. + +template <class T> int +ACE_Array_Base<T>::set (const T &new_item, size_t slot) +{ + if (this->in_range (slot)) + { + this->array_[slot] = new_item; + return 0; + } + else + return -1; +} + +// Get an item in the array at location slot. + +template <class T> int +ACE_Array_Base<T>::get (T &item, size_t slot) const +{ + if (this->in_range (slot)) + { + // Copies the item. If you don't want to copy, use operator [] + // instead (but then you'll be responsible for range checking). + item = this->array_[slot]; + return 0; + } + else + return -1; +} + +template<class T> int +ACE_Array_Base<T>::max_size (size_t new_size) +{ + if (new_size > this->max_size_) + { + T *tmp; + + ACE_ALLOCATOR_RETURN (tmp, + (T *) this->allocator_->malloc (new_size * sizeof (T)), + -1); + for (size_t i = 0; i < this->cur_size_; ++i) + new (&tmp[i]) T (this->array_[i]); + + // Initialize the new portion of the array that exceeds the + // previously allocated section. + for (size_t j = this->cur_size_; j < new_size; j++) + new (&tmp[j]) T; + + ACE_DES_ARRAY_FREE (this->array_, + this->max_size_, + this->allocator_->free, + T); + this->array_ = tmp; + this->max_size_ = new_size; + this->cur_size_ = new_size; + } + + return 0; +} + +template<class T> int +ACE_Array_Base<T>::size (size_t new_size) +{ + int r = this->max_size (new_size); + if (r != 0) + return r; + this->cur_size_ = new_size; + return 0; +} + +// **************************************************************** + +template <class T> int +ACE_Array_Iterator<T>::next (T *&item) +{ + // ACE_TRACE ("ACE_Array_Iterator<T>::next"); + + if (this->done ()) + { + item = 0; + return 0; + } + else + { + item = &array_[current_]; + return 1; + } +} + +#endif /* ACE_ARRAY_BASE_C */ diff --git a/ace/Array_Base.h b/ace/Array_Base.h new file mode 100644 index 00000000000..60ebb993867 --- /dev/null +++ b/ace/Array_Base.h @@ -0,0 +1,205 @@ +/* -*- C++ -*- */ + +//============================================================================= +/** + * @file Array_Base.h + * + * $Id$ + * + * @author Doug Schmidt + */ +//============================================================================= + + +#ifndef ACE_ARRAY_BASE_H +#define ACE_ARRAY_BASE_H +#include "ace/pre.h" + +#include "ace/config-all.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +// Forward declaration. +template <class T> class ACE_Array_Iterator; + +/** + * @class ACE_Array_Base + * + * @brief Implement a simple dynamic array + * + * This parametric class implements a simple dynamic array; + * resizing must be controlled by the user. No comparison or find + * operations are implemented. + */ +template<class T> +class ACE_Array_Base +{ +public: + + // Define a "trait" + typedef T TYPE; + typedef ACE_Array_Iterator<T> ITERATOR; + + // = Initialization and termination methods. + + /// Dynamically create an uninitialized array. + ACE_Array_Base (size_t size = 0, + ACE_Allocator *alloc = 0); + + /// Dynamically initialize the entire array to the <default_value>. + ACE_Array_Base (size_t size, + const T &default_value, + ACE_Allocator *alloc = 0); + + /** + * The copy constructor performs initialization by making an exact + * copy of the contents of parameter <s>, i.e., *this == s will + * return true. + */ + ACE_Array_Base (const ACE_Array_Base<T> &s); + + /** + * Assignment operator performs an assignment by making an exact + * copy of the contents of parameter <s>, i.e., *this == s will + * return true. Note that if the <max_size_> of <array_> is >= than + * <s.max_size_> we can copy it without reallocating. However, if + * <max_size_> is < <s.max_size_> we must delete the <array_>, + * reallocate a new <array_>, and then copy the contents of <s>. + */ + void operator= (const ACE_Array_Base<T> &s); + + /// Clean up the array (e.g., delete dynamically allocated memory). + ~ACE_Array_Base (void); + + // = Set/get methods. + + /// Set item in the array at location <slot>. Doesn't + /// perform range checking. + T &operator [] (size_t slot); + + /// Get item in the array at location <slot>. Doesn't + /// perform range checking. + const T &operator [] (size_t slot) const; + + /// Set an item in the array at location <slot>. Returns + /// -1 if <slot> is not in range, else returns 0. + int set (const T &new_item, size_t slot); + + /** + * Get an item in the array at location <slot>. Returns -1 if + * <slot> is not in range, else returns 0. Note that this function + * copies the item. If you want to avoid the copy, you can use + * the const operator [], but then you'll be responsible for range checking. + */ + int get (T &item, size_t slot) const; + + /// Returns the <cur_size_> of the array. + size_t size (void) const; + + /** + * Changes the size of the array to match <new_size>. + * It copies the old contents into the new array. + * Return -1 on failure. + */ + int size (size_t new_size); + + /// Returns the <max_size_> of the array. + size_t max_size (void) const; + + /** + * Changes the size of the array to match <new_size>. + * It copies the old contents into the new array. + * Return -1 on failure. + * It does not affect new_size + */ + int max_size (size_t new_size); + +private: + /// Returns 1 if <slot> is within range, i.e., 0 >= <slot> < + /// <cur_size_>, else returns 0. + int in_range (size_t slot) const; + + /// Maximum size of the array, i.e., the total number of <T> elements + /// in <array_>. + size_t max_size_; + + /** + * Current size of the array. This starts out being == to + * <max_size_>. However, if we are assigned a smaller array, then + * <cur_size_> will become less than <max_size_>. The purpose of + * keeping track of both sizes is to avoid reallocating memory if we + * don't have to. + */ + size_t cur_size_; + + /// Pointer to the array's storage buffer. + T *array_; + + /// Allocation strategy of the ACE_Array_Base. + ACE_Allocator *allocator_; + + friend class ACE_Array_Iterator<T>; +}; + +// **************************************************************** + +/** + * @class ACE_Array_Iterator + * + * @brief Implement an iterator over an ACE_Array. + * + * This iterator is safe in the face of array element deletions. + * But it is NOT safe if the array is resized (via the ACE_Array + * assignment operator) during iteration. That would be very + * odd, and dangerous. + */ +template <class T> +class ACE_Array_Iterator +{ +public: + // = Initialization method. + ACE_Array_Iterator (ACE_Array_Base<T> &); + + // = Iteration methods. + + /// Pass back the <next_item> that hasn't been seen in the Array. + /// Returns 0 when all items have been seen, else 1. + int next (T *&next_item); + + /// Move forward by one element in the Array. Returns 0 when all the + /// items in the Array have been seen, else 1. + int advance (void); + + /// Returns 1 when all items have been seen, else 0. + int done (void) const; + + /// Dump the state of an object. + void dump (void) const; + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + /// Pointer to the current item in the iteration. + u_int current_; + + /// Pointer to the Array we're iterating over. + ACE_Array_Base<T> &array_; +}; + +#if defined (__ACE_INLINE__) +#include "ace/Array_Base.inl" +#endif /* __ACE_INLINE__ */ + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Array_Base.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Array_Base.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#include "ace/post.h" +#endif /* ACE_ARRAY_BASE_H */ diff --git a/ace/Array_Base.inl b/ace/Array_Base.inl new file mode 100644 index 00000000000..b682fec615f --- /dev/null +++ b/ace/Array_Base.inl @@ -0,0 +1,84 @@ +/* -*- C++ -*- */ +// $Id$ + +// Clean up the array (e.g., delete dynamically allocated memory). + +template <class T> ACE_INLINE +ACE_Array_Base<T>::~ACE_Array_Base (void) +{ + ACE_DES_ARRAY_FREE (this->array_, + this->max_size_, + this->allocator_->free, + T); +} + +template <class T> ACE_INLINE size_t +ACE_Array_Base<T>::size (void) const +{ + return this->cur_size_; +} + +template <class T> ACE_INLINE size_t +ACE_Array_Base<T>::max_size (void) const +{ + return this->max_size_; +} + +template <class T> ACE_INLINE int +ACE_Array_Base<T>::in_range (size_t index) const +{ + return index < this->cur_size_; +} + +template <class T> ACE_INLINE T & +ACE_Array_Base<T>::operator[] (size_t index) +{ + return this->array_[index]; +} + +template <class T> ACE_INLINE const T & +ACE_Array_Base<T>::operator[] (size_t index) const +{ + return this->array_[index]; +} + +// **************************************************************** + +template <class T> ACE_INLINE void +ACE_Array_Iterator<T>::dump (void) const +{ + // ACE_TRACE ("ACE_Array_Iterator<T>::dump"); +} + +template <class T> ACE_INLINE +ACE_Array_Iterator<T>::ACE_Array_Iterator (ACE_Array_Base<T> &a) + : current_ (0), + array_ (a) +{ + // ACE_TRACE ("ACE_Array_Iterator<T>::ACE_Array_Iterator"); +} + +template <class T> ACE_INLINE int +ACE_Array_Iterator<T>::advance (void) +{ + // ACE_TRACE ("ACE_Array_Iterator<T>::advance"); + + if (this->current_ < array_.size ()) + { + ++this->current_; + return 1; + } + else + { + // Already finished iterating. + return 0; + } +} + +template <class T> ACE_INLINE int +ACE_Array_Iterator<T>::done (void) const +{ + ACE_TRACE ("ACE_Array_Iterator<T>::done"); + + return this->current_ >= array_.size (); +} diff --git a/ace/Containers_T.cpp b/ace/Containers_T.cpp index 5326b8f1ad3..eeb47912ddf 100644 --- a/ace/Containers_T.cpp +++ b/ace/Containers_T.cpp @@ -3,7 +3,7 @@ #ifndef ACE_CONTAINERS_T_C #define ACE_CONTAINERS_T_C -#include "ace/Malloc.h" +#include "ace/Malloc_Base.h" #if !defined (ACE_LACKS_PRAGMA_ONCE) # pragma once @@ -329,355 +329,6 @@ ACE_Unbounded_Stack<T>::remove (const T &item) } } -template <class T> -ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc) - : head_ (0), - cur_size_ (0), - allocator_ (alloc) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (void)"); - - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - ACE_NEW_MALLOC (this->head_, - (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T>); - // Make the list circular by pointing it back to itself. - this->head_->next_ = this->head_; -} - -template <class T> -ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us) - : head_ (0), - cur_size_ (0), - allocator_ (us.allocator_) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue"); - - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - ACE_NEW_MALLOC (this->head_, - (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T>); - this->head_->next_ = this->head_; - this->copy_nodes (us); -} - -template <class T> void -ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::operator="); - - if (this != &us) - { - this->delete_nodes (); - this->copy_nodes (us); - } -} - -template <class T> ACE_Unbounded_Queue_Iterator<T> -ACE_Unbounded_Queue<T>::begin (void) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin"); - return ACE_Unbounded_Queue_Iterator<T> (*this); -} - -template <class T> ACE_Unbounded_Queue_Iterator<T> -ACE_Unbounded_Queue<T>::end (void) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::end"); - return ACE_Unbounded_Queue_Iterator<T> (*this, 1); -} - - -ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Queue) - -template <class T> void -ACE_Unbounded_Queue<T>::dump (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::dump"); - - ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_ = %u"), this->head_)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); - - T *item = 0; -#if !defined (ACE_NLOGGING) - size_t count = 1; -#endif /* ! ACE_NLOGGING */ - - for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this); - iter.next (item) != 0; - iter.advance ()) - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++)); - - ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); -} - -template <class T> void -ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us) -{ - for (ACE_Node<T> *curr = us.head_->next_; - curr != us.head_; - curr = curr->next_) - if (this->enqueue_tail (curr->item_) == -1) - // @@ What's the right thing to do here? - this->delete_nodes (); -} - -template <class T> void -ACE_Unbounded_Queue<T>::delete_nodes (void) -{ - for (ACE_Node<T> *curr = this->head_->next_; - // Keep looking until we've hit the dummy node. - curr != this->head_; - ) - { - ACE_Node<T> *temp = curr; - curr = curr->next_; - - ACE_DES_FREE_TEMPLATE (temp, - this->allocator_->free, - ACE_Node, - <T>); - this->cur_size_--; - // @@ Doesnt make sense to have this check since - // this will always be true. - // ACE_ASSERT (this->cur_size_ >= 0); - } - - // Reset the list to be a circular list with just a dummy node. - this->head_->next_ = this->head_; -} - -template <class T> -ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)"); - - this->delete_nodes (); - ACE_DES_FREE_TEMPLATE (head_, - this->allocator_->free, - ACE_Node, - <T>); - this->head_ = 0; -} - -template <class T> int -ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head"); - - ACE_Node<T> *temp; - - // Create a new node that points to the original head. - ACE_NEW_MALLOC_RETURN (temp, - (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T> (new_item, this->head_->next_), - -1); - // Link this pointer into the front of the list. Note that the - // "real" head of the queue is <head_->next_>, whereas <head_> is - // just a pointer to the dummy node. - this->head_->next_ = temp; - - this->cur_size_++; - return 0; -} - -template <class T> int -ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail"); - - ACE_Node<T> *temp; - - // Insert <item> into the old dummy node location. Note that this - // isn't actually the "head" item in the queue, it's a dummy node at - // the "tail" of the queue... - this->head_->item_ = new_item; - - // Create a new dummy node. - ACE_NEW_MALLOC_RETURN (temp, - (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T> (this->head_->next_), -1); - // Link this dummy pointer into the list. - this->head_->next_ = temp; - - // Point the head to the new dummy node. - this->head_ = temp; - - this->cur_size_++; - return 0; -} - -template <class T> int -ACE_Unbounded_Queue<T>::dequeue_head (T &item) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head"); - - // Check for empty queue. - if (this->is_empty ()) - return -1; - - ACE_Node<T> *temp = this->head_->next_; - - item = temp->item_; - this->head_->next_ = temp->next_; - ACE_DES_FREE_TEMPLATE (temp, - this->allocator_->free, - ACE_Node, - <T>); - --this->cur_size_; - return 0; -} - -template <class T> void -ACE_Unbounded_Queue<T>::reset (void) -{ - ACE_TRACE ("reset"); - - this->delete_nodes (); -} - -template <class T> int -ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::get"); - - ACE_Node<T> *curr = this->head_->next_; - - size_t i; - - for (i = 0; i < this->cur_size_; i++) - { - if (i == slot) - break; - - curr = curr->next_; - } - - if (i < this->cur_size_) - { - item = &curr->item_; - return 0; - } - else - return -1; -} - -template <class T> int -ACE_Unbounded_Queue<T>::set (const T &item, - size_t slot) -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::set"); - - ACE_Node<T> *curr = this->head_->next_; - - size_t i; - - for (i = 0; - i < slot && i < this->cur_size_; - i++) - curr = curr->next_; - - if (i < this->cur_size_) - { - // We're in range, so everything's cool. - curr->item_ = item; - return 0; - } - else - { - // We need to expand the list. - - // A common case will be increasing the set size by 1. - // Therefore, we'll optimize for this case. - if (i == slot) - { - // Try to expand the size of the set by 1. - if (this->enqueue_tail (item) == -1) - return -1; - else - return 0; - } - else - { - T dummy; - - // We need to expand the list by multiple (dummy) items. - for (; i < slot; i++) - { - // This head points to the existing dummy node, which is - // about to be overwritten when we add the new dummy - // node. - curr = this->head_; - - // Try to expand the size of the set by 1, but don't - // store anything in the dummy node (yet). - if (this->enqueue_tail (dummy) == -1) - return -1; - } - - curr->item_ = item; - return 0; - } - } -} - -template <class T> void -ACE_Unbounded_Queue_Iterator<T>::dump (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump"); -} - -template <class T> -ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end) - : current_ (end == 0 ? q.head_->next_ : q.head_ ), - queue_ (q) -{ - // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator"); -} - -template <class T> int -ACE_Unbounded_Queue_Iterator<T>::advance (void) -{ - // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance"); - this->current_ = this->current_->next_; - return this->current_ != this->queue_.head_; -} - -template <class T> int -ACE_Unbounded_Queue_Iterator<T>::first (void) -{ - // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first"); - this->current_ = this->queue_.head_->next_; - return this->current_ != this->queue_.head_; -} - -template <class T> int -ACE_Unbounded_Queue_Iterator<T>::done (void) const -{ - ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done"); - - return this->current_ == this->queue_.head_; -} - -template <class T> int -ACE_Unbounded_Queue_Iterator<T>::next (T *&item) -{ - // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next"); - if (this->current_ == this->queue_.head_) - return 0; - else - { - item = &this->current_->item_; - return 1; - } -} - //-------------------------------------------------- ACE_ALLOC_HOOK_DEFINE(ACE_Double_Linked_List_Iterator_Base) @@ -1665,38 +1316,6 @@ ACE_Bounded_Set_Iterator<T>::next (T *&item) return 0; } -ACE_ALLOC_HOOK_DEFINE(ACE_Node) - -# if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) - template <class T> -ACE_Node<T>::~ACE_Node (void) -{ -} -# endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ - -template <class T> -ACE_Node<T>::ACE_Node (const T &i, ACE_Node<T> *n) - : next_ (n), - item_ (i) -{ - // ACE_TRACE ("ACE_Node<T>::ACE_Node"); -} - -template <class T> -ACE_Node<T>::ACE_Node (ACE_Node<T> *n, int) - : next_ (n) -{ - // ACE_TRACE ("ACE_Node<T>::ACE_Node"); -} - -template <class T> -ACE_Node<T>::ACE_Node (const ACE_Node<T> &s) - : next_ (s.next_), - item_ (s.item_) -{ - // ACE_TRACE ("ACE_Node<T>::ACE_Node"); -} - ACE_ALLOC_HOOK_DEFINE(ACE_DNode) template <class T> @@ -1712,338 +1331,7 @@ ACE_DNode<T>::~ACE_DNode (void) } # endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ -ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set) - - template <class T> size_t -ACE_Unbounded_Set<T>::size (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::size"); - return this->cur_size_; -} - -template <class T> int -ACE_Unbounded_Set<T>::insert_tail (const T &item) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::insert_tail"); - ACE_Node<T> *temp; - - // Insert <item> into the old dummy node location. - this->head_->item_ = item; - - // Create a new dummy node. - ACE_NEW_MALLOC_RETURN (temp, - (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T> (this->head_->next_), - -1); - // Link this pointer into the list. - this->head_->next_ = temp; - - // Point the head to the new dummy node. - this->head_ = temp; - - this->cur_size_++; - return 0; -} - -template <class T> void -ACE_Unbounded_Set<T>::reset (void) -{ - ACE_TRACE ("reset"); - - this->delete_nodes (); -} - -template <class T> void -ACE_Unbounded_Set<T>::dump (void) const -{ - ACE_TRACE ("ACE_Unbounded_Set<T>::dump"); - - ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_ = %u"), this->head_)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); - - T *item = 0; -#if !defined (ACE_NLOGGING) - size_t count = 1; -#endif /* ! ACE_NLOGGING */ - - for (ACE_Unbounded_Set_Iterator<T> iter (*(ACE_Unbounded_Set<T> *) this); - iter.next (item) != 0; - iter.advance ()) - ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++)); - - ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); -} - -template <class T> void -ACE_Unbounded_Set<T>::copy_nodes (const ACE_Unbounded_Set<T> &us) -{ - for (ACE_Node<T> *curr = us.head_->next_; - curr != us.head_; - curr = curr->next_) - this->insert_tail (curr->item_); -} - -template <class T> void -ACE_Unbounded_Set<T>::delete_nodes (void) -{ - ACE_Node<T> *curr = this->head_->next_; - - // Keep looking until we've hit the dummy node. - - while (curr != this->head_) - { - ACE_Node<T> *temp = curr; - curr = curr->next_; - ACE_DES_FREE_TEMPLATE (temp, - this->allocator_->free, - ACE_Node, - <T>); - this->cur_size_--; - } - - // Reset the list to be a circular list with just a dummy node. - this->head_->next_ = this->head_; -} - -template <class T> -ACE_Unbounded_Set<T>::~ACE_Unbounded_Set (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::~ACE_Unbounded_Set"); - - this->delete_nodes (); - - // Delete the dummy node. - ACE_DES_FREE_TEMPLATE (head_, - this->allocator_->free, - ACE_Node, - <T>); - this->head_ = 0; -} - -template <class T> -ACE_Unbounded_Set<T>::ACE_Unbounded_Set (ACE_Allocator *alloc) - : head_ (0), - cur_size_ (0), - allocator_ (alloc) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); - - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - ACE_NEW_MALLOC (this->head_, - (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T>); - // Make the list circular by pointing it back to itself. - this->head_->next_ = this->head_; -} - -template <class T> -ACE_Unbounded_Set<T>::ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &us) - : head_ (0), - cur_size_ (0), - allocator_ (us.allocator_) -{ - ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); - - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - ACE_NEW_MALLOC (this->head_, - (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), - ACE_Node<T>); - this->head_->next_ = this->head_; - this->copy_nodes (us); -} - -template <class T> void -ACE_Unbounded_Set<T>::operator= (const ACE_Unbounded_Set<T> &us) -{ - ACE_TRACE ("ACE_Unbounded_Set<T>::operator="); - - if (this != &us) - { - this->delete_nodes (); - this->copy_nodes (us); - } -} - -template <class T> int -ACE_Unbounded_Set<T>::find (const T &item) const -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::find"); - // Set <item> into the dummy node. - this->head_->item_ = item; - - ACE_Node<T> *temp = this->head_->next_; - - // Keep looping until we find the item. - while (!(temp->item_ == item)) - temp = temp->next_; - - // If we found the dummy node then it's not really there, otherwise, - // it is there. - return temp == this->head_ ? -1 : 0; -} - -template <class T> int -ACE_Unbounded_Set<T>::insert (const T &item) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::insert"); - if (this->find (item) == 0) - return 1; - else - return this->insert_tail (item); -} - -template <class T> int -ACE_Unbounded_Set<T>::remove (const T &item) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::remove"); - - // Insert the item to be founded into the dummy node. - this->head_->item_ = item; - - ACE_Node<T> *curr = this->head_; - - while (!(curr->next_->item_ == item)) - curr = curr->next_; - - if (curr->next_ == this->head_) - return -1; // Item was not found. - else - { - ACE_Node<T> *temp = curr->next_; - // Skip over the node that we're deleting. - curr->next_ = temp->next_; - this->cur_size_--; - ACE_DES_FREE_TEMPLATE (temp, - this->allocator_->free, - ACE_Node, - <T>); - return 0; - } -} - -template <class T> ACE_Unbounded_Set_Iterator<T> -ACE_Unbounded_Set<T>::begin (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::begin"); - return ACE_Unbounded_Set_Iterator<T> (*this); -} - -template <class T> ACE_Unbounded_Set_Iterator<T> -ACE_Unbounded_Set<T>::end (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set<T>::end"); - return ACE_Unbounded_Set_Iterator<T> (*this, 1); -} - - -ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set_Iterator) - - template <class T> void -ACE_Unbounded_Set_Iterator<T>::dump (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::dump"); -} - -template <class T> -ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end) - : current_ (end == 0 ? s.head_->next_ : s.head_ ), - set_ (&s) -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator"); -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::advance (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::advance"); - this->current_ = this->current_->next_; - return this->current_ != this->set_->head_; -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::first (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::first"); - this->current_ = this->set_->head_->next_; - return this->current_ != this->set_->head_; -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::done (void) const -{ - ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::done"); - - return this->current_ == this->set_->head_; -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::next (T *&item) -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::next"); - if (this->current_ == this->set_->head_) - return 0; - else - { - item = &this->current_->item_; - return 1; - } -} - -template <class T> ACE_Unbounded_Set_Iterator<T> -ACE_Unbounded_Set_Iterator<T>::operator++ (int) -{ - //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator++ (int)"); - ACE_Unbounded_Set_Iterator<T> retv (*this); - - // postfix operator - - this->advance (); - return retv; -} - -template <class T> ACE_Unbounded_Set_Iterator<T>& -ACE_Unbounded_Set_Iterator<T>::operator++ (void) -{ - // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator++ (void)"); - - // prefix operator - - this->advance (); - return *this; -} - -template <class T> T& -ACE_Unbounded_Set_Iterator<T>::operator* (void) -{ - //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator*"); - T *retv = 0; - - int result = this->next (retv); - ACE_ASSERT (result != 0); - ACE_UNUSED_ARG (result); - - return *retv; -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::operator== (const ACE_Unbounded_Set_Iterator<T> &rhs) const -{ - //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator=="); - return (this->set_ == rhs.set_ && this->current_ == rhs.current_); -} - -template <class T> int -ACE_Unbounded_Set_Iterator<T>::operator!= (const ACE_Unbounded_Set_Iterator<T> &rhs) const -{ - //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator!="); - return (this->set_ != rhs.set_ || this->current_ != rhs.current_); -} +// **************************************************************** template <class T> void ACE_Unbounded_Stack_Iterator<T>::dump (void) const @@ -2489,171 +1777,6 @@ ACE_DLList<T>::delete_tail (void) return temp2; } -// Dynamically initialize an array. - -template <class T> -ACE_Array_Base<T>::ACE_Array_Base (size_t size, - ACE_Allocator *alloc) - : max_size_ (size), - cur_size_ (size), - allocator_ (alloc) -{ - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - if (size != 0) - { - ACE_ALLOCATOR (this->array_, - (T *) this->allocator_->malloc (size * sizeof (T))); - for (size_t i = 0; i < size; ++i) - new (&array_[i]) T; - } - else - this->array_ = 0; -} - -template <class T> -ACE_Array_Base<T>::ACE_Array_Base (size_t size, - const T &default_value, - ACE_Allocator *alloc) - : max_size_ (size), - cur_size_ (size), - allocator_ (alloc) -{ - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - if (size != 0) - { - ACE_ALLOCATOR (this->array_, - (T *) this->allocator_->malloc (size * sizeof (T))); - for (size_t i = 0; i < size; ++i) - new (&array_[i]) T (default_value); - } - else - this->array_ = 0; -} - -// The copy constructor (performs initialization). - -template <class T> -ACE_Array_Base<T>::ACE_Array_Base (const ACE_Array_Base<T> &s) - : max_size_ (s.size ()), - cur_size_ (s.size ()), - allocator_ (s.allocator_) -{ - if (this->allocator_ == 0) - this->allocator_ = ACE_Allocator::instance (); - - ACE_ALLOCATOR (this->array_, - (T *) this->allocator_->malloc (s.size () * sizeof (T))); - for (size_t i = 0; i < this->size (); i++) - new (&this->array_[i]) T (s.array_[i]); -} - -// Assignment operator (performs assignment). - -template <class T> void -ACE_Array_Base<T>::operator= (const ACE_Array_Base<T> &s) -{ - // Check for "self-assignment". - - if (this != &s) - { - if (this->max_size_ < s.size ()) - { - ACE_DES_ARRAY_FREE (this->array_, - this->max_size_, - this->allocator_->free, - T); - ACE_ALLOCATOR (this->array_, - (T *) this->allocator_->malloc (s.size () * sizeof (T))); - this->max_size_ = s.size (); - } - else - { - ACE_DES_ARRAY_NOFREE (this->array_, - s.size (), - T); - } - - this->cur_size_ = s.size (); - - for (size_t i = 0; i < this->size (); i++) - new (&this->array_[i]) T (s.array_[i]); - } -} - -// Set an item in the array at location slot. - -template <class T> int -ACE_Array_Base<T>::set (const T &new_item, size_t slot) -{ - if (this->in_range (slot)) - { - this->array_[slot] = new_item; - return 0; - } - else - return -1; -} - -// Get an item in the array at location slot. - -template <class T> int -ACE_Array_Base<T>::get (T &item, size_t slot) const -{ - if (this->in_range (slot)) - { - // Copies the item. If you don't want to copy, use operator [] - // instead (but then you'll be responsible for range checking). - item = this->array_[slot]; - return 0; - } - else - return -1; -} - -template<class T> int -ACE_Array_Base<T>::max_size (size_t new_size) -{ - if (new_size > this->max_size_) - { - T *tmp; - - ACE_ALLOCATOR_RETURN (tmp, - (T *) this->allocator_->malloc (new_size * sizeof (T)), - -1); - for (size_t i = 0; i < this->cur_size_; ++i) - new (&tmp[i]) T (this->array_[i]); - - // Initialize the new portion of the array that exceeds the - // previously allocated section. - for (size_t j = this->cur_size_; j < new_size; j++) - new (&tmp[j]) T; - - ACE_DES_ARRAY_FREE (this->array_, - this->max_size_, - this->allocator_->free, - T); - this->array_ = tmp; - this->max_size_ = new_size; - this->cur_size_ = new_size; - } - - return 0; -} - -template<class T> int -ACE_Array_Base<T>::size (size_t new_size) -{ - int r = this->max_size (new_size); - if (r != 0) - return r; - this->cur_size_ = new_size; - return 0; -} - // **************************************************************** // Compare this array with <s> for equality. @@ -2676,21 +1799,4 @@ ACE_Array<T>::operator== (const ACE_Array<T> &s) const // **************************************************************** -template <class T> int -ACE_Array_Iterator<T>::next (T *&item) -{ - // ACE_TRACE ("ACE_Array_Iterator<T>::next"); - - if (this->done ()) - { - item = 0; - return 0; - } - else - { - item = &array_[current_]; - return 1; - } -} - #endif /* ACE_CONTAINERS_T_C */ diff --git a/ace/Containers_T.h b/ace/Containers_T.h index 4521a2aa299..83f9dc14dc0 100644 --- a/ace/Containers_T.h +++ b/ace/Containers_T.h @@ -24,6 +24,18 @@ // Need by ACE_DLList_Node. #include "ace/Containers.h" +// Shared with "ace/Unbounded_Set.h" +#include "ace/Node.h" + +// Backwards compatibility, please include "ace/Array_Base.h" directly. +#include "ace/Array_Base.h" + +// Backwards compatibility, please include "ace/Unbounded_Set.h" directly. +#include "ace/Unbounded_Set.h" + +// Backwards compatibility, please include "ace/Unbounded_Set.h" directly. +#include "ace/Unbounded_Queue.h" + class ACE_Allocator; /** @@ -182,49 +194,8 @@ private: //---------------------------------------- -// Forward declarations. -template <class T> class ACE_Unbounded_Set; -template <class T> class ACE_Unbounded_Set_Iterator; -template <class T> class ACE_Unbounded_Queue; -template <class T> class ACE_Unbounded_Queue_Iterator; -template <class T> class ACE_Unbounded_Stack; -template <class T> class ACE_Unbounded_Stack_Iterator; -template <class T> class ACE_Ordered_MultiSet; -template <class T> class ACE_Ordered_MultiSet_Iterator; - -/** - * @class ACE_Node - * - * @brief Implementation element in a Queue, Set, and Stack. - */ -template<class T> -class ACE_Node -{ -public: - friend class ACE_Unbounded_Queue<T>; - friend class ACE_Unbounded_Queue_Iterator<T>; - friend class ACE_Unbounded_Set<T>; - friend class ACE_Unbounded_Set_Iterator<T>; - friend class ACE_Unbounded_Stack<T>; - friend class ACE_Unbounded_Stack_Iterator<T>; - -# if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) - /// This isn't necessary, but it keeps some compilers happy. - ~ACE_Node (void); -# endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ - -private: - // = Initialization methods - ACE_Node (const T &i, ACE_Node<T> *n); - ACE_Node (ACE_Node<T> *n = 0, int = 0); - ACE_Node (const ACE_Node<T> &n); - - /// Pointer to next element in the list of <ACE_Node>s. - ACE_Node<T> *next_; - - /// Current value of the item in this node. - T item_; -}; +template<class T> class ACE_Ordered_MultiSet; +template<class T> class ACE_Ordered_MultiSet_Iterator; /** * @class ACE_DNode @@ -412,153 +383,6 @@ private: }; template <class T> -class ACE_Unbounded_Queue; - -/** - * @class ACE_Unbounded_Queue_Iterator - * - * @brief Implement an iterator over an unbounded queue. - */ -template <class T> -class ACE_Unbounded_Queue_Iterator -{ -public: - // = Initialization method. - ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0); - - // = Iteration methods. - - /// Pass back the <next_item> that hasn't been seen in the queue. - /// Returns 0 when all items have been seen, else 1. - int next (T *&next_item); - - /// Move forward by one element in the set. Returns 0 when all the - /// items in the queue have been seen, else 1. - int advance (void); - - /// Move to the first element in the queue. Returns 0 if the - /// queue is empty, else 1. - int first (void); - - /// Returns 1 when all items have been seen, else 0. - int done (void) const; - - /// Dump the state of an object. - void dump (void) const; - - /// Declare the dynamic allocation hooks. - ACE_ALLOC_HOOK_DECLARE; - -private: - /// Pointer to the current node in the iteration. - ACE_Node<T> *current_; - - /// Pointer to the queue we're iterating over. - ACE_Unbounded_Queue<T> &queue_; -}; - -/** - * @class ACE_Unbounded_Queue - * - * @brief A Queue of "infinite" length. - * - * This implementation of an unbounded queue uses a circular - * linked list with a dummy node. - */ -template <class T> -class ACE_Unbounded_Queue -{ -public: - friend class ACE_Unbounded_Queue_Iterator<T>; - - // Trait definition. - typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR; - - // = Initialization and termination methods. - /// construction. Use user specified allocation strategy - /// if specified. - ACE_Unbounded_Queue (ACE_Allocator *alloc = 0); - - /// Copy constructor. - ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &); - - /// Assignment operator. - void operator= (const ACE_Unbounded_Queue<T> &); - - /// construction. - ~ACE_Unbounded_Queue (void); - - // = Check boundary conditions. - - /// Returns 1 if the container is empty, otherwise returns 0. - int is_empty (void) const; - - /// Returns 1 if the container is full, otherwise returns 0. - int is_full (void) const; - - // = Classic queue operations. - - /// Adds <new_item> to the tail of the queue. Returns 0 on success, - /// -1 on failure. - int enqueue_tail (const T &new_item); - - /// Adds <new_item> to the head of the queue. Returns 0 on success, - /// -1 on failure. - int enqueue_head (const T &new_item); - - /// Removes and returns the first <item> on the queue. Returns 0 on - /// success, -1 if the queue was empty. - int dequeue_head (T &item); - - // = Additional utility methods. - - /// Reset the <ACE_Unbounded_Queue> to be empty and release all its - /// dynamically allocated resources. - void reset (void); - - /// Get the <slot>th element in the set. Returns -1 if the element - /// isn't in the range {0..<size> - 1}, else 0. - int get (T *&item, size_t slot = 0) const; - - /** - * Set the <slot>th element in the set. Will pad out the set with - * empty nodes if <slot> is beyond the range {0..<size> - 1}. - * Returns -1 on failure, 0 if <slot> isn't initially in range, and - * 0 otherwise. - */ - int set (const T &item, size_t slot); - - /// The number of items in the queue. - size_t size (void) const; - - /// Dump the state of an object. - void dump (void) const; - - // = STL-styled unidirectional iterator factory. - ACE_Unbounded_Queue_Iterator<T> begin (void); - ACE_Unbounded_Queue_Iterator<T> end (void); - - /// Declare the dynamic allocation hooks. - ACE_ALLOC_HOOK_DECLARE; - -protected: - /// Delete all the nodes in the queue. - void delete_nodes (void); - - /// Copy nodes into this queue. - void copy_nodes (const ACE_Unbounded_Queue<T> &); - - /// Pointer to the dummy node in the circular linked Queue. - ACE_Node<T> *head_; - - /// Current size of the queue. - size_t cur_size_; - - /// Allocation Strategy of the queue. - ACE_Allocator *allocator_; -}; - -template <class T> class ACE_Double_Linked_List; /** @@ -1128,163 +952,6 @@ private: ACE_DLList<T> *list_; }; -/** - * @class ACE_Unbounded_Set_Iterator - * - * @brief Implement an iterator over an unbounded set. - */ -template <class T> -class ACE_Unbounded_Set_Iterator -{ -public: - // = Initialization method. - ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end = 0); - - // = Iteration methods. - - /// Pass back the <next_item> that hasn't been seen in the Set. - /// Returns 0 when all items have been seen, else 1. - int next (T *&next_item); - - /// Move forward by one element in the set. Returns 0 when all the - /// items in the set have been seen, else 1. - int advance (void); - - /// Move to the first element in the set. Returns 0 if the - /// set is empty, else 1. - int first (void); - - /// Returns 1 when all items have been seen, else 0. - int done (void) const; - - /// Dump the state of an object. - void dump (void) const; - - // = STL styled iteration, compare, and reference functions. - - /// Postfix advance. - ACE_Unbounded_Set_Iterator<T> operator++ (int); - - /// Prefix advance. - ACE_Unbounded_Set_Iterator<T>& operator++ (void); - - /// Returns a reference to the internal element <this> is pointing to. - T& operator* (void); - - /// Check if two iterators point to the same position - int operator== (const ACE_Unbounded_Set_Iterator<T> &) const; - int operator!= (const ACE_Unbounded_Set_Iterator<T> &) const; - - /// Declare the dynamic allocation hooks. - ACE_ALLOC_HOOK_DECLARE; - -private: - - /// Pointer to the current node in the iteration. - ACE_Node<T> *current_; - - /// Pointer to the set we're iterating over. - ACE_Unbounded_Set<T> *set_; -}; - -/** - * @class ACE_Unbounded_Set - * - * @brief Implement a simple unordered set of <T> of unbounded size. - * - * This implementation of an unordered set uses a circular - * linked list with a dummy node. This implementation does not - * allow duplicates, but it maintains FIFO ordering of insertions. - */ -template <class T> -class ACE_Unbounded_Set -{ -public: - friend class ACE_Unbounded_Set_Iterator<T>; - - // Trait definition. - typedef ACE_Unbounded_Set_Iterator<T> ITERATOR; - typedef ACE_Unbounded_Set_Iterator<T> iterator; - - // = Initialization and termination methods. - /// Constructor. Use user specified allocation strategy - /// if specified. - ACE_Unbounded_Set (ACE_Allocator *alloc = 0); - - /// Copy constructor. - ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &); - - /// Assignment operator. - void operator= (const ACE_Unbounded_Set<T> &); - - /// Destructor. - ~ACE_Unbounded_Set (void); - - // = Check boundary conditions. - - /// Returns 1 if the container is empty, otherwise returns 0. - int is_empty (void) const; - - /// Returns 1 if the container is full, otherwise returns 0. - int is_full (void) const; - - // = Classic unordered set operations. - - /** - * Insert <new_item> into the set (doesn't allow duplicates). - * Returns -1 if failures occur, 1 if item is already present, else - * 0. - */ - int insert (const T &new_item); - - /** - * Remove first occurrence of <item> from the set. Returns 0 if - * it removes the item, -1 if it can't find the item, and -1 if a - * failure occurs. - */ - int remove (const T &item); - - /// Finds if <item> occurs in the set. Returns 0 if find succeeds, - /// else -1. - int find (const T &item) const; - - /// Size of the set. - size_t size (void) const; - - /// Dump the state of an object. - void dump (void) const; - - /// Reset the <ACE_Unbounded_Set> to be empty. - void reset (void); - - // = STL-styled unidirectional iterator factory. - ACE_Unbounded_Set_Iterator<T> begin (void); - ACE_Unbounded_Set_Iterator<T> end (void); - - /// Declare the dynamic allocation hooks. - ACE_ALLOC_HOOK_DECLARE; - -private: - /// Insert <item> at the tail of the set (doesn't check for - /// duplicates). - int insert_tail (const T &item); - - /// Delete all the nodes in the Set. - void delete_nodes (void); - - /// Copy nodes into this set. - void copy_nodes (const ACE_Unbounded_Set<T> &); - - /// Head of the linked list of Nodes. - ACE_Node<T> *head_; - - /// Current size of the set. - size_t cur_size_; - - /// Allocation strategy of the set. - ACE_Allocator *allocator_; -}; - // Forward declaration. template <class T, size_t ACE_SIZE> class ACE_Fixed_Set; @@ -1744,130 +1411,6 @@ private: // **************************************************************** -// Forward declaration. -template <class T> class ACE_Array_Iterator; - -/** - * @class ACE_Array_Base - * - * @brief Implement a simple dynamic array - * - * This parametric class implements a simple dynamic array; - * resizing must be controlled by the user. No comparison or find - * operations are implemented. - */ -template<class T> -class ACE_Array_Base -{ -public: - - // Define a "trait" - typedef T TYPE; - typedef ACE_Array_Iterator<T> ITERATOR; - - // = Initialization and termination methods. - - /// Dynamically create an uninitialized array. - ACE_Array_Base (size_t size = 0, - ACE_Allocator *alloc = 0); - - /// Dynamically initialize the entire array to the <default_value>. - ACE_Array_Base (size_t size, - const T &default_value, - ACE_Allocator *alloc = 0); - - /** - * The copy constructor performs initialization by making an exact - * copy of the contents of parameter <s>, i.e., *this == s will - * return true. - */ - ACE_Array_Base (const ACE_Array_Base<T> &s); - - /** - * Assignment operator performs an assignment by making an exact - * copy of the contents of parameter <s>, i.e., *this == s will - * return true. Note that if the <max_size_> of <array_> is >= than - * <s.max_size_> we can copy it without reallocating. However, if - * <max_size_> is < <s.max_size_> we must delete the <array_>, - * reallocate a new <array_>, and then copy the contents of <s>. - */ - void operator= (const ACE_Array_Base<T> &s); - - /// Clean up the array (e.g., delete dynamically allocated memory). - ~ACE_Array_Base (void); - - // = Set/get methods. - - /// Set item in the array at location <slot>. Doesn't - /// perform range checking. - T &operator [] (size_t slot); - - /// Get item in the array at location <slot>. Doesn't - /// perform range checking. - const T &operator [] (size_t slot) const; - - /// Set an item in the array at location <slot>. Returns - /// -1 if <slot> is not in range, else returns 0. - int set (const T &new_item, size_t slot); - - /** - * Get an item in the array at location <slot>. Returns -1 if - * <slot> is not in range, else returns 0. Note that this function - * copies the item. If you want to avoid the copy, you can use - * the const operator [], but then you'll be responsible for range checking. - */ - int get (T &item, size_t slot) const; - - /// Returns the <cur_size_> of the array. - size_t size (void) const; - - /** - * Changes the size of the array to match <new_size>. - * It copies the old contents into the new array. - * Return -1 on failure. - */ - int size (size_t new_size); - - /// Returns the <max_size_> of the array. - size_t max_size (void) const; - - /** - * Changes the size of the array to match <new_size>. - * It copies the old contents into the new array. - * Return -1 on failure. - * It does not affect new_size - */ - int max_size (size_t new_size); - -private: - /// Returns 1 if <slot> is within range, i.e., 0 >= <slot> < - /// <cur_size_>, else returns 0. - int in_range (size_t slot) const; - - /// Maximum size of the array, i.e., the total number of <T> elements - /// in <array_>. - size_t max_size_; - - /** - * Current size of the array. This starts out being == to - * <max_size_>. However, if we are assigned a smaller array, then - * <cur_size_> will become less than <max_size_>. The purpose of - * keeping track of both sizes is to avoid reallocating memory if we - * don't have to. - */ - size_t cur_size_; - - /// Pointer to the array's storage buffer. - T *array_; - - /// Allocation strategy of the ACE_Array_Base. - ACE_Allocator *allocator_; - - friend class ACE_Array_Iterator<T>; -}; - -// **************************************************************** - /** * @class ACE_Array * @@ -1932,50 +1475,6 @@ public: int operator!= (const ACE_Array<T> &s) const; }; -/** - * @class ACE_Array_Iterator - * - * @brief Implement an iterator over an ACE_Array. - * - * This iterator is safe in the face of array element deletions. - * But it is NOT safe if the array is resized (via the ACE_Array - * assignment operator) during iteration. That would be very - * odd, and dangerous. - */ -template <class T> -class ACE_Array_Iterator -{ -public: - // = Initialization method. - ACE_Array_Iterator (ACE_Array_Base<T> &); - - // = Iteration methods. - - /// Pass back the <next_item> that hasn't been seen in the Array. - /// Returns 0 when all items have been seen, else 1. - int next (T *&next_item); - - /// Move forward by one element in the Array. Returns 0 when all the - /// items in the Array have been seen, else 1. - int advance (void); - - /// Returns 1 when all items have been seen, else 0. - int done (void) const; - - /// Dump the state of an object. - void dump (void) const; - - /// Declare the dynamic allocation hooks. - ACE_ALLOC_HOOK_DECLARE; - -private: - /// Pointer to the current item in the iteration. - u_int current_; - - /// Pointer to the Array we're iterating over. - ACE_Array_Base<T> &array_; -}; - #if defined (__ACE_INLINE__) #include "ace/Containers_T.i" #endif /* __ACE_INLINE__ */ diff --git a/ace/Containers_T.i b/ace/Containers_T.i index f1835efacbe..ae123bb4f61 100644 --- a/ace/Containers_T.i +++ b/ace/Containers_T.i @@ -158,41 +158,6 @@ ACE_Unbounded_Stack<T>::size (void) const // --- -template <class T> ACE_INLINE size_t -ACE_Unbounded_Queue<T>::size (void) const -{ - return this->cur_size_; -} - -template <class T> ACE_INLINE int -ACE_Unbounded_Queue<T>::is_empty (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::is_empty"); - return this->head_ == this->head_->next_; -} - -template <class T> ACE_INLINE int -ACE_Unbounded_Queue<T>::is_full (void) const -{ - // ACE_TRACE ("ACE_Unbounded_Queue<T>::is_full"); - return 0; // We should implement a "node of last resort for this..." -} - -// --- - -template <class T> ACE_INLINE int -ACE_Unbounded_Set<T>::is_empty (void) const -{ - ACE_TRACE ("ACE_Unbounded_Set<T>::is_empty"); - return this->head_ == this->head_->next_; -} - -template <class T> ACE_INLINE int -ACE_Unbounded_Set<T>::is_full (void) const -{ - ACE_TRACE ("ACE_Unbounded_Set<T>::is_full"); - return 0; // We should implement a "node of last resort for this..." -} // --- @@ -303,49 +268,6 @@ ACE_Ordered_MultiSet<T>::size (void) const // **************************************************************** -// Clean up the array (e.g., delete dynamically allocated memory). - -template <class T> ACE_INLINE -ACE_Array_Base<T>::~ACE_Array_Base (void) -{ - ACE_DES_ARRAY_FREE (this->array_, - this->max_size_, - this->allocator_->free, - T); -} - -template <class T> ACE_INLINE size_t -ACE_Array_Base<T>::size (void) const -{ - return this->cur_size_; -} - -template <class T> ACE_INLINE size_t -ACE_Array_Base<T>::max_size (void) const -{ - return this->max_size_; -} - -template <class T> ACE_INLINE int -ACE_Array_Base<T>::in_range (size_t index) const -{ - return index < this->cur_size_; -} - -template <class T> ACE_INLINE T & -ACE_Array_Base<T>::operator[] (size_t index) -{ - return this->array_[index]; -} - -template <class T> ACE_INLINE const T & -ACE_Array_Base<T>::operator[] (size_t index) const -{ - return this->array_[index]; -} - -// **************************************************************** - template <class T> ACE_INLINE ACE_Array<T>::ACE_Array (size_t size, ACE_Allocator *alloc) @@ -390,44 +312,6 @@ ACE_Array<T>::operator!= (const ACE_Array<T> &s) const // **************************************************************** -template <class T> ACE_INLINE void -ACE_Array_Iterator<T>::dump (void) const -{ - // ACE_TRACE ("ACE_Array_Iterator<T>::dump"); -} - -template <class T> ACE_INLINE -ACE_Array_Iterator<T>::ACE_Array_Iterator (ACE_Array_Base<T> &a) - : current_ (0), - array_ (a) -{ - // ACE_TRACE ("ACE_Array_Iterator<T>::ACE_Array_Iterator"); -} - -template <class T> ACE_INLINE int -ACE_Array_Iterator<T>::advance (void) -{ - // ACE_TRACE ("ACE_Array_Iterator<T>::advance"); - - if (this->current_ < array_.size ()) - { - ++this->current_; - return 1; - } - else - { - // Already finished iterating. - return 0; - } -} - -template <class T> ACE_INLINE int -ACE_Array_Iterator<T>::done (void) const -{ - ACE_TRACE ("ACE_Array_Iterator<T>::done"); - - return this->current_ >= array_.size (); -} // **************************************************************** diff --git a/ace/Future.h b/ace/Future.h index fddc69ffbc2..594a3a451f7 100644 --- a/ace/Future.h +++ b/ace/Future.h @@ -18,7 +18,7 @@ #define ACE_FUTURE_H #include "ace/pre.h" -#include "ace/Containers.h" +#include "ace/Unbounded_Set.h" #include "ace/Synch.h" #include "ace/Strategies_T.h" diff --git a/ace/Handle_Gobbler.h b/ace/Handle_Gobbler.h index 69b298e18ee..b823539f7a4 100644 --- a/ace/Handle_Gobbler.h +++ b/ace/Handle_Gobbler.h @@ -21,7 +21,7 @@ # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -#include "ace/Containers_T.h" +#include "ace/Unbounded_Set.h" /** * @class ACE_Handle_Gobbler diff --git a/ace/Local_Name_Space.h b/ace/Local_Name_Space.h index 96de84acb54..285c44a351b 100644 --- a/ace/Local_Name_Space.h +++ b/ace/Local_Name_Space.h @@ -23,7 +23,6 @@ # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -#include "ace/Containers.h" #include "ace/Malloc_T.h" #include "ace/Synch.h" diff --git a/ace/Makefile b/ace/Makefile index 5f8f298a756..b980112f9d4 100644 --- a/ace/Makefile +++ b/ace/Makefile @@ -228,6 +228,10 @@ OTHER_FILES = \ TEMPLATE_FILES = \ Acceptor \ Active_Map_Manager_T \ + Array_Base \ + Node \ + Unbounded_Set \ + Unbounded_Queue \ Asynch_Acceptor \ Auto_IncDec_T \ Auto_Ptr \ diff --git a/ace/Makefile.am b/ace/Makefile.am index 0672fadb9d8..c5ad3d8aed8 100644 --- a/ace/Makefile.am +++ b/ace/Makefile.am @@ -430,6 +430,10 @@ libACE_la_LIBADD = $(X_PRE_LIBS) $(ACE_XLIBS) $(X_EXTRA_LIBS) TEMPLATE_FILES = \ Acceptor.cpp \ Active_Map_Manager_T.cpp \ + Array_Base.cpp \ + Node.cpp \ + Unbounded_Set.cpp \ + Unbounded_Queue.cpp \ Asynch_Acceptor.cpp \ Auto_IncDec_T.cpp \ Auto_Ptr.cpp \ diff --git a/ace/Makefile.bor b/ace/Makefile.bor index e1ffea7f45b..23de7130f4e 100644 --- a/ace/Makefile.bor +++ b/ace/Makefile.bor @@ -233,6 +233,10 @@ INCLUDES = \ *.h *.i *.inl *_T.cpp \ Acceptor.cpp \ Asynch_Acceptor.cpp \ + Array_Base.cpp \ + Node.cpp \ + Unbounded_Set.cpp \ + Unbounded_Queue.cpp \ Auto_Ptr.cpp \ Connector.cpp \ CORBA_Ref.cpp \ diff --git a/ace/Malloc_Base.h b/ace/Malloc_Base.h index 89df21cac2e..3b9f5c7161f 100644 --- a/ace/Malloc_Base.h +++ b/ace/Malloc_Base.h @@ -15,6 +15,12 @@ #define ACE_MALLOC_BASE_H #include "ace/pre.h" +#include "ace/OS.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + // The definition of this class is located in Malloc.cpp. /** diff --git a/ace/Memory_Pool.h b/ace/Memory_Pool.h index 56a13c96557..7b475311970 100644 --- a/ace/Memory_Pool.h +++ b/ace/Memory_Pool.h @@ -27,6 +27,8 @@ #include "ace/SV_Semaphore_Complex.h" #endif /* !ACE_WIN32 */ +#include "ace/Unbounded_Set.h" + #if !defined (ACE_LACKS_SBRK) /** * @class ACE_Sbrk_Memory_Pool_Options diff --git a/ace/Name_Space.h b/ace/Name_Space.h index 58ebeb110f6..839179af741 100644 --- a/ace/Name_Space.h +++ b/ace/Name_Space.h @@ -22,7 +22,7 @@ #endif /* ACE_LACKS_PRAGMA_ONCE */ #include "ace/SString.h" -#include "ace/Containers.h" +#include "ace/Unbounded_Set.h" #include "ace/Name_Proxy.h" typedef ACE_Unbounded_Set<ACE_WString> ACE_WSTRING_SET; diff --git a/ace/Node.cpp b/ace/Node.cpp new file mode 100644 index 00000000000..91e989d739b --- /dev/null +++ b/ace/Node.cpp @@ -0,0 +1,46 @@ +// $Id$ + +#ifndef ACE_NODE_C +#define ACE_NODE_C + +#include "ace/Node.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +ACE_RCSID(ace, Node, "$Id$") + +ACE_ALLOC_HOOK_DEFINE(ACE_Node) + +# if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) + template <class T> +ACE_Node<T>::~ACE_Node (void) +{ +} +# endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ + +template <class T> +ACE_Node<T>::ACE_Node (const T &i, ACE_Node<T> *n) + : next_ (n), + item_ (i) +{ + // ACE_TRACE ("ACE_Node<T>::ACE_Node"); +} + +template <class T> +ACE_Node<T>::ACE_Node (ACE_Node<T> *n, int) + : next_ (n) +{ + // ACE_TRACE ("ACE_Node<T>::ACE_Node"); +} + +template <class T> +ACE_Node<T>::ACE_Node (const ACE_Node<T> &s) + : next_ (s.next_), + item_ (s.item_) +{ + // ACE_TRACE ("ACE_Node<T>::ACE_Node"); +} + +#endif /* ACE_NODE_C */ diff --git a/ace/Node.h b/ace/Node.h new file mode 100644 index 00000000000..9e4a0717ecc --- /dev/null +++ b/ace/Node.h @@ -0,0 +1,75 @@ +/* -*- C++ -*- */ + +//============================================================================= +/** + * @file Node.h + * + * $Id$ + * + * @author Doug Schmidt + */ +//============================================================================= + + +#ifndef ACE_NODE_H +#define ACE_NODE_H +#include "ace/pre.h" + +#include "ace/config-all.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +// Forward declarations. +template <class T> class ACE_Unbounded_Set; +template <class T> class ACE_Unbounded_Set_Iterator; +template <class T> class ACE_Unbounded_Queue; +template <class T> class ACE_Unbounded_Queue_Iterator; +template <class T> class ACE_Unbounded_Stack; +template <class T> class ACE_Unbounded_Stack_Iterator; + +/** + * @class ACE_Node + * + * @brief Implementation element in a Queue, Set, and Stack. + */ +template<class T> +class ACE_Node +{ +public: + friend class ACE_Unbounded_Queue<T>; + friend class ACE_Unbounded_Queue_Iterator<T>; + friend class ACE_Unbounded_Set<T>; + friend class ACE_Unbounded_Set_Iterator<T>; + friend class ACE_Unbounded_Stack<T>; + friend class ACE_Unbounded_Stack_Iterator<T>; + +# if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) + /// This isn't necessary, but it keeps some compilers happy. + ~ACE_Node (void); +# endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ + +private: + // = Initialization methods + ACE_Node (const T &i, ACE_Node<T> *n); + ACE_Node (ACE_Node<T> *n = 0, int = 0); + ACE_Node (const ACE_Node<T> &n); + + /// Pointer to next element in the list of <ACE_Node>s. + ACE_Node<T> *next_; + + /// Current value of the item in this node. + T item_; +}; + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Node.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Node.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#include "ace/post.h" +#endif /* ACE_NODE_H */ diff --git a/ace/Priority_Reactor.h b/ace/Priority_Reactor.h index d2e63ee5f63..398c644f6a9 100644 --- a/ace/Priority_Reactor.h +++ b/ace/Priority_Reactor.h @@ -15,7 +15,7 @@ #define ACE_PRIORITY_REACTOR_H #include "ace/pre.h" -#include "ace/Containers.h" +#include "ace/Unbounded_Queue.h" #if !defined (ACE_LACKS_PRAGMA_ONCE) # pragma once diff --git a/ace/Remote_Name_Space.h b/ace/Remote_Name_Space.h index 1e8bcb795b8..6d5d8a5ab15 100644 --- a/ace/Remote_Name_Space.h +++ b/ace/Remote_Name_Space.h @@ -22,7 +22,6 @@ #endif /* ACE_LACKS_PRAGMA_ONCE */ #include "ace/SString.h" -#include "ace/Containers.h" #include "ace/Name_Proxy.h" #include "ace/Name_Space.h" diff --git a/ace/Service_Config.h b/ace/Service_Config.h index 9ec359750ce..beddbcaf9c0 100644 --- a/ace/Service_Config.h +++ b/ace/Service_Config.h @@ -22,7 +22,8 @@ #endif /* ACE_LACKS_PRAGMA_ONCE */ #include "ace/Signal.h" -#include "ace/Containers.h" +#include "ace/Unbounded_Queue.h" +#include "ace/Unbounded_Set.h" #include "ace/SString.h" // Forward decl. diff --git a/ace/Signal.cpp b/ace/Signal.cpp index ed2c81f53f8..3bd3d01cedb 100644 --- a/ace/Signal.cpp +++ b/ace/Signal.cpp @@ -4,6 +4,7 @@ #include "ace/Signal.h" #include "ace/Object_Manager.h" #include "ace/Log_Msg.h" +#include "ace/Containers.h" #if !defined (__ACE_INLINE__) #include "ace/Signal.i" diff --git a/ace/Signal.h b/ace/Signal.h index fc046d0404b..3461de28771 100644 --- a/ace/Signal.h +++ b/ace/Signal.h @@ -494,8 +494,6 @@ private: }; #endif /* ACE_HAS_BROKEN_HPUX_TEMPLATES */ -#include "ace/Containers.h" - #if defined (ACE_HAS_SIG_C_FUNC) extern "C" void ace_sig_handler_dispatch (int signum, siginfo_t *info, ucontext_t *context); diff --git a/ace/Stats.h b/ace/Stats.h index c413dd7f062..999fd6da7fa 100644 --- a/ace/Stats.h +++ b/ace/Stats.h @@ -21,7 +21,7 @@ # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -#include "ace/Containers.h" +#include "ace/Unbounded_Queue.h" #include "ace/Log_Msg.h" #include "ace/Basic_Stats.h" diff --git a/ace/Thread_Manager.h b/ace/Thread_Manager.h index 4b8e06518ec..a44a7052dd6 100644 --- a/ace/Thread_Manager.h +++ b/ace/Thread_Manager.h @@ -23,6 +23,7 @@ #endif /* ACE_LACKS_PRAGMA_ONCE */ #include "ace/Synch.h" +#include "ace/Unbounded_Queue.h" #include "ace/Containers.h" #include "ace/Free_List.h" #include "ace/Singleton.h" @@ -185,10 +186,10 @@ public: /// Current state of the thread. ACE_UINT32 state (void) const; - + /// Return the pointer to an <ACE_Task_Base> or NULL if there's no /// <ACE_Task_Base> associated with this thread.; - ACE_Task_Base *task (void) const; + ACE_Task_Base *task (void) const; protected: /// Reset this base thread descriptor. diff --git a/ace/Timeprobe_T.h b/ace/Timeprobe_T.h index 41744e153d8..52740f6456f 100644 --- a/ace/Timeprobe_T.h +++ b/ace/Timeprobe_T.h @@ -23,7 +23,7 @@ #if defined (ACE_COMPILE_TIMEPROBES) -#include "ace/Containers.h" +#include "ace/Unbounded_Set.h" /** * @class ACE_Timeprobe diff --git a/ace/Timer_Heap_T.h b/ace/Timer_Heap_T.h index 4eee67b00ad..7bf2b7c0e4f 100644 --- a/ace/Timer_Heap_T.h +++ b/ace/Timer_Heap_T.h @@ -22,7 +22,7 @@ #endif /* ACE_LACKS_PRAGMA_ONCE */ #include "ace/Free_List.h" -#include "ace/Containers.h" +#include "ace/Unbounded_Set.h" // Forward declaration template <class TYPE, class FUNCTOR, class ACE_LOCK> diff --git a/ace/Timer_Queue_Adapters.h b/ace/Timer_Queue_Adapters.h index 0f6619b1463..ef05e7f79f4 100644 --- a/ace/Timer_Queue_Adapters.h +++ b/ace/Timer_Queue_Adapters.h @@ -12,16 +12,16 @@ #ifndef ACE_TIMER_QUEUE_ADAPTERS_H -# define ACE_TIMER_QUEUE_ADAPTERS_H -# include "ace/pre.h" +#define ACE_TIMER_QUEUE_ADAPTERS_H +#include "ace/pre.h" -# include "ace/Task.h" +#include "ace/Task.h" #if !defined (ACE_LACKS_PRAGMA_ONCE) # pragma once #endif /* ACE_LACKS_PRAGMA_ONCE */ -# include "ace/Signal.h" +#include "ace/Signal.h" /** * @class ACE_Async_Timer_Queue_Adapter @@ -214,17 +214,17 @@ private: ACE_thread_t thr_id_; }; -# if defined (__ACE_INLINE__) -# include "ace/Timer_Queue_Adapters.i" -# endif /* __ACE_INLINE__ */ +#if defined (__ACE_INLINE__) +# include "ace/Timer_Queue_Adapters.i" +#endif /* __ACE_INLINE__ */ -# if defined (ACE_TEMPLATES_REQUIRE_SOURCE) -# include "ace/Timer_Queue_Adapters.cpp" -# endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +# include "ace/Timer_Queue_Adapters.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ -# if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) -# pragma implementation ("Timer_Queue_Adapters.cpp") -# endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +# pragma implementation ("Timer_Queue_Adapters.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ -# include "ace/post.h" +#include "ace/post.h" #endif /* ACE_TIMER_QUEUE_ADAPTERS_H */ diff --git a/ace/TkReactor.cpp b/ace/TkReactor.cpp index 68fe024b63b..6240bf5879b 100644 --- a/ace/TkReactor.cpp +++ b/ace/TkReactor.cpp @@ -93,13 +93,17 @@ ACE_TkReactor::TimerCallbackProc (ClientData cd) self->reset_timeout (); } -// This could be made shorter if we know which *kind* of event we were -// about to get. Here we use <select> to find out which one might be -// available. - +/** + * @todo the unused mask argument is probably quite useful, but we + * ignore it, why? In fact the following comment probably + * relates to that: + * This could be made shorter if we know which *kind* of event + * we were about to get. Here we use <select> to find out which + * one might be available. + */ void ACE_TkReactor::InputCallbackProc (ClientData cd, - int mask) + int /* mask */) { ACE_TkReactor_Input_Callback *callback = (ACE_TkReactor_Input_Callback *) cd; ACE_TkReactor *self = callback->reactor_; @@ -357,7 +361,7 @@ ACE_TkReactor::reset_timeout (void) int ACE_TkReactor::reset_timer_interval - (long timer_id, + (long timer_id, const ACE_Time_Value &interval) { ACE_TRACE ("ACE_TkReactor::reset_timer_interval"); diff --git a/ace/Unbounded_Queue.cpp b/ace/Unbounded_Queue.cpp new file mode 100644 index 00000000000..dd0f81d5079 --- /dev/null +++ b/ace/Unbounded_Queue.cpp @@ -0,0 +1,370 @@ +// $Id$ + +#ifndef ACE_UNBOUNDED_QUEUE_C +#define ACE_UNBOUNDED_QUEUE_C + +#include "ace/Unbounded_Queue.h" +#include "ace/Malloc_Base.h" +#include "ace/Log_Msg.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +#if !defined (__ACE_INLINE__) +#include "ace/Unbounded_Queue.inl" +#endif /* __ACE_INLINE__ */ + +ACE_RCSID(ace, Unbounded_Queue, "$Id$") + +ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Queue) + +template <class T> +ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc) + : head_ (0), + cur_size_ (0), + allocator_ (alloc) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (void)"); + + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_NEW_MALLOC (this->head_, + (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T>); + // Make the list circular by pointing it back to itself. + this->head_->next_ = this->head_; +} + +template <class T> +ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us) + : head_ (0), + cur_size_ (0), + allocator_ (us.allocator_) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue"); + + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_NEW_MALLOC (this->head_, + (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T>); + this->head_->next_ = this->head_; + this->copy_nodes (us); +} + +template <class T> void +ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::operator="); + + if (this != &us) + { + this->delete_nodes (); + this->copy_nodes (us); + } +} + +template <class T> ACE_Unbounded_Queue_Iterator<T> +ACE_Unbounded_Queue<T>::begin (void) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin"); + return ACE_Unbounded_Queue_Iterator<T> (*this); +} + +template <class T> ACE_Unbounded_Queue_Iterator<T> +ACE_Unbounded_Queue<T>::end (void) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::end"); + return ACE_Unbounded_Queue_Iterator<T> (*this, 1); +} + +template <class T> void +ACE_Unbounded_Queue<T>::dump (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::dump"); + + ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_ = %u"), this->head_)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); + + T *item = 0; +#if !defined (ACE_NLOGGING) + size_t count = 1; +#endif /* ! ACE_NLOGGING */ + + for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this); + iter.next (item) != 0; + iter.advance ()) + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++)); + + ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); +} + +template <class T> void +ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us) +{ + for (ACE_Node<T> *curr = us.head_->next_; + curr != us.head_; + curr = curr->next_) + if (this->enqueue_tail (curr->item_) == -1) + // @@ What's the right thing to do here? + this->delete_nodes (); +} + +template <class T> void +ACE_Unbounded_Queue<T>::delete_nodes (void) +{ + for (ACE_Node<T> *curr = this->head_->next_; + // Keep looking until we've hit the dummy node. + curr != this->head_; + ) + { + ACE_Node<T> *temp = curr; + curr = curr->next_; + + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + this->cur_size_--; + // @@ Doesnt make sense to have this check since + // this will always be true. + // ACE_ASSERT (this->cur_size_ >= 0); + } + + // Reset the list to be a circular list with just a dummy node. + this->head_->next_ = this->head_; +} + +template <class T> +ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)"); + + this->delete_nodes (); + ACE_DES_FREE_TEMPLATE (head_, + this->allocator_->free, + ACE_Node, + <T>); + this->head_ = 0; +} + +template <class T> int +ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head"); + + ACE_Node<T> *temp; + + // Create a new node that points to the original head. + ACE_NEW_MALLOC_RETURN (temp, + (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T> (new_item, this->head_->next_), + -1); + // Link this pointer into the front of the list. Note that the + // "real" head of the queue is <head_->next_>, whereas <head_> is + // just a pointer to the dummy node. + this->head_->next_ = temp; + + this->cur_size_++; + return 0; +} + +template <class T> int +ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail"); + + ACE_Node<T> *temp; + + // Insert <item> into the old dummy node location. Note that this + // isn't actually the "head" item in the queue, it's a dummy node at + // the "tail" of the queue... + this->head_->item_ = new_item; + + // Create a new dummy node. + ACE_NEW_MALLOC_RETURN (temp, + (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T> (this->head_->next_), -1); + // Link this dummy pointer into the list. + this->head_->next_ = temp; + + // Point the head to the new dummy node. + this->head_ = temp; + + this->cur_size_++; + return 0; +} + +template <class T> int +ACE_Unbounded_Queue<T>::dequeue_head (T &item) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head"); + + // Check for empty queue. + if (this->is_empty ()) + return -1; + + ACE_Node<T> *temp = this->head_->next_; + + item = temp->item_; + this->head_->next_ = temp->next_; + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + --this->cur_size_; + return 0; +} + +template <class T> void +ACE_Unbounded_Queue<T>::reset (void) +{ + ACE_TRACE ("reset"); + + this->delete_nodes (); +} + +template <class T> int +ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::get"); + + ACE_Node<T> *curr = this->head_->next_; + + size_t i; + + for (i = 0; i < this->cur_size_; i++) + { + if (i == slot) + break; + + curr = curr->next_; + } + + if (i < this->cur_size_) + { + item = &curr->item_; + return 0; + } + else + return -1; +} + +template <class T> int +ACE_Unbounded_Queue<T>::set (const T &item, + size_t slot) +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::set"); + + ACE_Node<T> *curr = this->head_->next_; + + size_t i; + + for (i = 0; + i < slot && i < this->cur_size_; + i++) + curr = curr->next_; + + if (i < this->cur_size_) + { + // We're in range, so everything's cool. + curr->item_ = item; + return 0; + } + else + { + // We need to expand the list. + + // A common case will be increasing the set size by 1. + // Therefore, we'll optimize for this case. + if (i == slot) + { + // Try to expand the size of the set by 1. + if (this->enqueue_tail (item) == -1) + return -1; + else + return 0; + } + else + { + T dummy; + + // We need to expand the list by multiple (dummy) items. + for (; i < slot; i++) + { + // This head points to the existing dummy node, which is + // about to be overwritten when we add the new dummy + // node. + curr = this->head_; + + // Try to expand the size of the set by 1, but don't + // store anything in the dummy node (yet). + if (this->enqueue_tail (dummy) == -1) + return -1; + } + + curr->item_ = item; + return 0; + } + } +} + +// **************************************************************** + +template <class T> void +ACE_Unbounded_Queue_Iterator<T>::dump (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump"); +} + +template <class T> +ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end) + : current_ (end == 0 ? q.head_->next_ : q.head_ ), + queue_ (q) +{ + // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator"); +} + +template <class T> int +ACE_Unbounded_Queue_Iterator<T>::advance (void) +{ + // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance"); + this->current_ = this->current_->next_; + return this->current_ != this->queue_.head_; +} + +template <class T> int +ACE_Unbounded_Queue_Iterator<T>::first (void) +{ + // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first"); + this->current_ = this->queue_.head_->next_; + return this->current_ != this->queue_.head_; +} + +template <class T> int +ACE_Unbounded_Queue_Iterator<T>::done (void) const +{ + ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done"); + + return this->current_ == this->queue_.head_; +} + +template <class T> int +ACE_Unbounded_Queue_Iterator<T>::next (T *&item) +{ + // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next"); + if (this->current_ == this->queue_.head_) + return 0; + else + { + item = &this->current_->item_; + return 1; + } +} + +#endif /* ACE_UNBOUNDED_QUEUE_C */ diff --git a/ace/Unbounded_Queue.h b/ace/Unbounded_Queue.h new file mode 100644 index 00000000000..d41c838f977 --- /dev/null +++ b/ace/Unbounded_Queue.h @@ -0,0 +1,186 @@ +/* -*- C++ -*- */ + +//============================================================================= +/** + * @file Unbounded_Queue.h + * + * $Id$ + * + * @author Doug Schmidt + */ +//============================================================================= + + +#ifndef ACE_UNBOUNDED_QUEUE_H +#define ACE_UNBOUNDED_QUEUE_H +#include "ace/pre.h" + +#include "ace/Node.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +class ACE_Allocator; + +template <class T> +class ACE_Unbounded_Queue; + +/** + * @class ACE_Unbounded_Queue_Iterator + * + * @brief Implement an iterator over an unbounded queue. + */ +template <class T> +class ACE_Unbounded_Queue_Iterator +{ +public: + // = Initialization method. + ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0); + + // = Iteration methods. + + /// Pass back the <next_item> that hasn't been seen in the queue. + /// Returns 0 when all items have been seen, else 1. + int next (T *&next_item); + + /// Move forward by one element in the set. Returns 0 when all the + /// items in the queue have been seen, else 1. + int advance (void); + + /// Move to the first element in the queue. Returns 0 if the + /// queue is empty, else 1. + int first (void); + + /// Returns 1 when all items have been seen, else 0. + int done (void) const; + + /// Dump the state of an object. + void dump (void) const; + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + /// Pointer to the current node in the iteration. + ACE_Node<T> *current_; + + /// Pointer to the queue we're iterating over. + ACE_Unbounded_Queue<T> &queue_; +}; + +/** + * @class ACE_Unbounded_Queue + * + * @brief A Queue of "infinite" length. + * + * This implementation of an unbounded queue uses a circular + * linked list with a dummy node. + */ +template <class T> +class ACE_Unbounded_Queue +{ +public: + friend class ACE_Unbounded_Queue_Iterator<T>; + + // Trait definition. + typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR; + + // = Initialization and termination methods. + /// construction. Use user specified allocation strategy + /// if specified. + ACE_Unbounded_Queue (ACE_Allocator *alloc = 0); + + /// Copy constructor. + ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &); + + /// Assignment operator. + void operator= (const ACE_Unbounded_Queue<T> &); + + /// construction. + ~ACE_Unbounded_Queue (void); + + // = Check boundary conditions. + + /// Returns 1 if the container is empty, otherwise returns 0. + int is_empty (void) const; + + /// Returns 1 if the container is full, otherwise returns 0. + int is_full (void) const; + + // = Classic queue operations. + + /// Adds <new_item> to the tail of the queue. Returns 0 on success, + /// -1 on failure. + int enqueue_tail (const T &new_item); + + /// Adds <new_item> to the head of the queue. Returns 0 on success, + /// -1 on failure. + int enqueue_head (const T &new_item); + + /// Removes and returns the first <item> on the queue. Returns 0 on + /// success, -1 if the queue was empty. + int dequeue_head (T &item); + + // = Additional utility methods. + + /// Reset the <ACE_Unbounded_Queue> to be empty and release all its + /// dynamically allocated resources. + void reset (void); + + /// Get the <slot>th element in the set. Returns -1 if the element + /// isn't in the range {0..<size> - 1}, else 0. + int get (T *&item, size_t slot = 0) const; + + /** + * Set the <slot>th element in the set. Will pad out the set with + * empty nodes if <slot> is beyond the range {0..<size> - 1}. + * Returns -1 on failure, 0 if <slot> isn't initially in range, and + * 0 otherwise. + */ + int set (const T &item, size_t slot); + + /// The number of items in the queue. + size_t size (void) const; + + /// Dump the state of an object. + void dump (void) const; + + // = STL-styled unidirectional iterator factory. + ACE_Unbounded_Queue_Iterator<T> begin (void); + ACE_Unbounded_Queue_Iterator<T> end (void); + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +protected: + /// Delete all the nodes in the queue. + void delete_nodes (void); + + /// Copy nodes into this queue. + void copy_nodes (const ACE_Unbounded_Queue<T> &); + + /// Pointer to the dummy node in the circular linked Queue. + ACE_Node<T> *head_; + + /// Current size of the queue. + size_t cur_size_; + + /// Allocation Strategy of the queue. + ACE_Allocator *allocator_; +}; + +#if defined (__ACE_INLINE__) +#include "ace/Unbounded_Queue.inl" +#endif /* __ACE_INLINE__ */ + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Unbounded_Queue.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Unbounded_Queue.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#include "ace/post.h" +#endif /* ACE_UNBOUNDED_QUEUE_H */ diff --git a/ace/Unbounded_Queue.inl b/ace/Unbounded_Queue.inl new file mode 100644 index 00000000000..ea552e7d3d8 --- /dev/null +++ b/ace/Unbounded_Queue.inl @@ -0,0 +1,21 @@ +// $Id$ + +template <class T> ACE_INLINE size_t +ACE_Unbounded_Queue<T>::size (void) const +{ + return this->cur_size_; +} + +template <class T> ACE_INLINE int +ACE_Unbounded_Queue<T>::is_empty (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::is_empty"); + return this->head_ == this->head_->next_; +} + +template <class T> ACE_INLINE int +ACE_Unbounded_Queue<T>::is_full (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Queue<T>::is_full"); + return 0; // We should implement a "node of last resort for this..." +} diff --git a/ace/Unbounded_Set.cpp b/ace/Unbounded_Set.cpp new file mode 100644 index 00000000000..af5b8d45b04 --- /dev/null +++ b/ace/Unbounded_Set.cpp @@ -0,0 +1,353 @@ +// $Id$ + +#ifndef ACE_UNBOUNDED_SET_C +#define ACE_UNBOUNDED_SET_C + +#include "ace/Unbounded_Set.h" +#include "ace/Malloc_Base.h" +#include "ace/Log_Msg.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +#if !defined (__ACE_INLINE__) +#include "ace/Unbounded_Set.inl" +#endif /* __ACE_INLINE__ */ + +ACE_RCSID(ace, Unbounded_Set, "$Id$") + +ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set) + + template <class T> size_t +ACE_Unbounded_Set<T>::size (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::size"); + return this->cur_size_; +} + +template <class T> int +ACE_Unbounded_Set<T>::insert_tail (const T &item) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::insert_tail"); + ACE_Node<T> *temp; + + // Insert <item> into the old dummy node location. + this->head_->item_ = item; + + // Create a new dummy node. + ACE_NEW_MALLOC_RETURN (temp, + (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T> (this->head_->next_), + -1); + // Link this pointer into the list. + this->head_->next_ = temp; + + // Point the head to the new dummy node. + this->head_ = temp; + + this->cur_size_++; + return 0; +} + +template <class T> void +ACE_Unbounded_Set<T>::reset (void) +{ + ACE_TRACE ("reset"); + + this->delete_nodes (); +} + +template <class T> void +ACE_Unbounded_Set<T>::dump (void) const +{ + ACE_TRACE ("ACE_Unbounded_Set<T>::dump"); + + ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_ = %u"), this->head_)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); + + T *item = 0; +#if !defined (ACE_NLOGGING) + size_t count = 1; +#endif /* ! ACE_NLOGGING */ + + for (ACE_Unbounded_Set_Iterator<T> iter (*(ACE_Unbounded_Set<T> *) this); + iter.next (item) != 0; + iter.advance ()) + ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("count = %d\n"), count++)); + + ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); +} + +template <class T> void +ACE_Unbounded_Set<T>::copy_nodes (const ACE_Unbounded_Set<T> &us) +{ + for (ACE_Node<T> *curr = us.head_->next_; + curr != us.head_; + curr = curr->next_) + this->insert_tail (curr->item_); +} + +template <class T> void +ACE_Unbounded_Set<T>::delete_nodes (void) +{ + ACE_Node<T> *curr = this->head_->next_; + + // Keep looking until we've hit the dummy node. + + while (curr != this->head_) + { + ACE_Node<T> *temp = curr; + curr = curr->next_; + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + this->cur_size_--; + } + + // Reset the list to be a circular list with just a dummy node. + this->head_->next_ = this->head_; +} + +template <class T> +ACE_Unbounded_Set<T>::~ACE_Unbounded_Set (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::~ACE_Unbounded_Set"); + + this->delete_nodes (); + + // Delete the dummy node. + ACE_DES_FREE_TEMPLATE (head_, + this->allocator_->free, + ACE_Node, + <T>); + this->head_ = 0; +} + +template <class T> +ACE_Unbounded_Set<T>::ACE_Unbounded_Set (ACE_Allocator *alloc) + : head_ (0), + cur_size_ (0), + allocator_ (alloc) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); + + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_NEW_MALLOC (this->head_, + (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T>); + // Make the list circular by pointing it back to itself. + this->head_->next_ = this->head_; +} + +template <class T> +ACE_Unbounded_Set<T>::ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &us) + : head_ (0), + cur_size_ (0), + allocator_ (us.allocator_) +{ + ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); + + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_NEW_MALLOC (this->head_, + (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), + ACE_Node<T>); + this->head_->next_ = this->head_; + this->copy_nodes (us); +} + +template <class T> void +ACE_Unbounded_Set<T>::operator= (const ACE_Unbounded_Set<T> &us) +{ + ACE_TRACE ("ACE_Unbounded_Set<T>::operator="); + + if (this != &us) + { + this->delete_nodes (); + this->copy_nodes (us); + } +} + +template <class T> int +ACE_Unbounded_Set<T>::find (const T &item) const +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::find"); + // Set <item> into the dummy node. + this->head_->item_ = item; + + ACE_Node<T> *temp = this->head_->next_; + + // Keep looping until we find the item. + while (!(temp->item_ == item)) + temp = temp->next_; + + // If we found the dummy node then it's not really there, otherwise, + // it is there. + return temp == this->head_ ? -1 : 0; +} + +template <class T> int +ACE_Unbounded_Set<T>::insert (const T &item) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::insert"); + if (this->find (item) == 0) + return 1; + else + return this->insert_tail (item); +} + +template <class T> int +ACE_Unbounded_Set<T>::remove (const T &item) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::remove"); + + // Insert the item to be founded into the dummy node. + this->head_->item_ = item; + + ACE_Node<T> *curr = this->head_; + + while (!(curr->next_->item_ == item)) + curr = curr->next_; + + if (curr->next_ == this->head_) + return -1; // Item was not found. + else + { + ACE_Node<T> *temp = curr->next_; + // Skip over the node that we're deleting. + curr->next_ = temp->next_; + this->cur_size_--; + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + return 0; + } +} + +template <class T> ACE_Unbounded_Set_Iterator<T> +ACE_Unbounded_Set<T>::begin (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::begin"); + return ACE_Unbounded_Set_Iterator<T> (*this); +} + +template <class T> ACE_Unbounded_Set_Iterator<T> +ACE_Unbounded_Set<T>::end (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set<T>::end"); + return ACE_Unbounded_Set_Iterator<T> (*this, 1); +} + + +ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set_Iterator) + + template <class T> void +ACE_Unbounded_Set_Iterator<T>::dump (void) const +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::dump"); +} + +template <class T> +ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end) + : current_ (end == 0 ? s.head_->next_ : s.head_ ), + set_ (&s) +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator"); +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::advance (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::advance"); + this->current_ = this->current_->next_; + return this->current_ != this->set_->head_; +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::first (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::first"); + this->current_ = this->set_->head_->next_; + return this->current_ != this->set_->head_; +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::done (void) const +{ + ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::done"); + + return this->current_ == this->set_->head_; +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::next (T *&item) +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::next"); + if (this->current_ == this->set_->head_) + return 0; + else + { + item = &this->current_->item_; + return 1; + } +} + +template <class T> ACE_Unbounded_Set_Iterator<T> +ACE_Unbounded_Set_Iterator<T>::operator++ (int) +{ + //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator++ (int)"); + ACE_Unbounded_Set_Iterator<T> retv (*this); + + // postfix operator + + this->advance (); + return retv; +} + +template <class T> ACE_Unbounded_Set_Iterator<T>& +ACE_Unbounded_Set_Iterator<T>::operator++ (void) +{ + // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator++ (void)"); + + // prefix operator + + this->advance (); + return *this; +} + +template <class T> T& +ACE_Unbounded_Set_Iterator<T>::operator* (void) +{ + //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator*"); + T *retv = 0; + + int result = this->next (retv); + ACE_ASSERT (result != 0); + ACE_UNUSED_ARG (result); + + return *retv; +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::operator== (const ACE_Unbounded_Set_Iterator<T> &rhs) const +{ + //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator=="); + return (this->set_ == rhs.set_ && this->current_ == rhs.current_); +} + +template <class T> int +ACE_Unbounded_Set_Iterator<T>::operator!= (const ACE_Unbounded_Set_Iterator<T> &rhs) const +{ + //ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::operator!="); + return (this->set_ != rhs.set_ || this->current_ != rhs.current_); +} + +#endif /* ACE_UNBOUNDED_SET_C */ diff --git a/ace/Unbounded_Set.h b/ace/Unbounded_Set.h new file mode 100644 index 00000000000..3a6f94daf03 --- /dev/null +++ b/ace/Unbounded_Set.h @@ -0,0 +1,196 @@ +/* -*- C++ -*- */ + +//============================================================================= +/** + * @file Unbounded_Set.h + * + * $Id$ + * + * @author Doug Schmidt + */ +//============================================================================= + + +#ifndef ACE_UNBOUNDED_SET_H +#define ACE_UNBOUNDED_SET_H +#include "ace/pre.h" + +#include "ace/Node.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +class ACE_Allocator; + +/** + * @class ACE_Unbounded_Set_Iterator + * + * @brief Implement an iterator over an unbounded set. + */ +template <class T> +class ACE_Unbounded_Set_Iterator +{ +public: + // = Initialization method. + ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end = 0); + + // = Iteration methods. + + /// Pass back the <next_item> that hasn't been seen in the Set. + /// Returns 0 when all items have been seen, else 1. + int next (T *&next_item); + + /// Move forward by one element in the set. Returns 0 when all the + /// items in the set have been seen, else 1. + int advance (void); + + /// Move to the first element in the set. Returns 0 if the + /// set is empty, else 1. + int first (void); + + /// Returns 1 when all items have been seen, else 0. + int done (void) const; + + /// Dump the state of an object. + void dump (void) const; + + // = STL styled iteration, compare, and reference functions. + + /// Postfix advance. + ACE_Unbounded_Set_Iterator<T> operator++ (int); + + /// Prefix advance. + ACE_Unbounded_Set_Iterator<T>& operator++ (void); + + /// Returns a reference to the internal element <this> is pointing to. + T& operator* (void); + + /// Check if two iterators point to the same position + int operator== (const ACE_Unbounded_Set_Iterator<T> &) const; + int operator!= (const ACE_Unbounded_Set_Iterator<T> &) const; + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + + /// Pointer to the current node in the iteration. + ACE_Node<T> *current_; + + /// Pointer to the set we're iterating over. + ACE_Unbounded_Set<T> *set_; +}; + +/** + * @class ACE_Unbounded_Set + * + * @brief Implement a simple unordered set of <T> of unbounded size. + * + * This implementation of an unordered set uses a circular + * linked list with a dummy node. This implementation does not + * allow duplicates, but it maintains FIFO ordering of insertions. + */ +template <class T> +class ACE_Unbounded_Set +{ +public: + friend class ACE_Unbounded_Set_Iterator<T>; + + // Trait definition. + typedef ACE_Unbounded_Set_Iterator<T> ITERATOR; + typedef ACE_Unbounded_Set_Iterator<T> iterator; + + // = Initialization and termination methods. + /// Constructor. Use user specified allocation strategy + /// if specified. + ACE_Unbounded_Set (ACE_Allocator *alloc = 0); + + /// Copy constructor. + ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &); + + /// Assignment operator. + void operator= (const ACE_Unbounded_Set<T> &); + + /// Destructor. + ~ACE_Unbounded_Set (void); + + // = Check boundary conditions. + + /// Returns 1 if the container is empty, otherwise returns 0. + int is_empty (void) const; + + /// Returns 1 if the container is full, otherwise returns 0. + int is_full (void) const; + + // = Classic unordered set operations. + + /** + * Insert <new_item> into the set (doesn't allow duplicates). + * Returns -1 if failures occur, 1 if item is already present, else + * 0. + */ + int insert (const T &new_item); + + /** + * Remove first occurrence of <item> from the set. Returns 0 if + * it removes the item, -1 if it can't find the item, and -1 if a + * failure occurs. + */ + int remove (const T &item); + + /// Finds if <item> occurs in the set. Returns 0 if find succeeds, + /// else -1. + int find (const T &item) const; + + /// Size of the set. + size_t size (void) const; + + /// Dump the state of an object. + void dump (void) const; + + /// Reset the <ACE_Unbounded_Set> to be empty. + void reset (void); + + // = STL-styled unidirectional iterator factory. + ACE_Unbounded_Set_Iterator<T> begin (void); + ACE_Unbounded_Set_Iterator<T> end (void); + + /// Declare the dynamic allocation hooks. + ACE_ALLOC_HOOK_DECLARE; + +private: + /// Insert <item> at the tail of the set (doesn't check for + /// duplicates). + int insert_tail (const T &item); + + /// Delete all the nodes in the Set. + void delete_nodes (void); + + /// Copy nodes into this set. + void copy_nodes (const ACE_Unbounded_Set<T> &); + + /// Head of the linked list of Nodes. + ACE_Node<T> *head_; + + /// Current size of the set. + size_t cur_size_; + + /// Allocation strategy of the set. + ACE_Allocator *allocator_; +}; + +#if defined (__ACE_INLINE__) +#include "ace/Unbounded_Set.inl" +#endif /* __ACE_INLINE__ */ + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Unbounded_Set.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Unbounded_Set.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#include "ace/post.h" +#endif /* ACE_UNBOUNDED_SET_H */ diff --git a/ace/Unbounded_Set.inl b/ace/Unbounded_Set.inl new file mode 100644 index 00000000000..3f71cd2b498 --- /dev/null +++ b/ace/Unbounded_Set.inl @@ -0,0 +1,16 @@ +/* -*- C++ -*- */ +// $Id$ + +template <class T> ACE_INLINE int +ACE_Unbounded_Set<T>::is_empty (void) const +{ + ACE_TRACE ("ACE_Unbounded_Set<T>::is_empty"); + return this->head_ == this->head_->next_; +} + +template <class T> ACE_INLINE int +ACE_Unbounded_Set<T>::is_full (void) const +{ + ACE_TRACE ("ACE_Unbounded_Set<T>::is_full"); + return 0; // We should implement a "node of last resort for this..." +} |