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

ACE_Unbounded_Set< T > Class Template Reference

Implement a simple unordered set of of unbounded size. More...

#include <Unbounded_Set.h>

Collaboration diagram for ACE_Unbounded_Set< T >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Unbounded_Set_Iterator<
T > 		ITERATOR
typedef ACE_Unbounded_Set_Iterator<
T > 		iterator
typedef ACE_Unbounded_Set_Const_Iterator<
T > 		CONST_ITERATOR
typedef ACE_Unbounded_Set_Const_Iterator<
T > 		const_iterator

Public Member Functions

 ACE_Unbounded_Set (ACE_Allocator *alloc=0)
 ACE_Unbounded_Set (const ACE_Unbounded_Set< T > &)
 Copy constructor.

ACE_Unbounded_Set< T > & operator= (const ACE_Unbounded_Set< T > &)
 Assignment operator.

 ~ACE_Unbounded_Set (void)
 Destructor.

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

int is_full (void) const
 Returns 0.

int insert (const T &new_item)
 Linear insertion of an item.

int insert_tail (const T &item)
int remove (const T &item)
 Linear remove operation.

int find (const T &item) const
size_t size (void) const
 Size of the set.

void dump (void) const
 Dump the state of an object.

void reset (void)
 Reset the to be empty.

ACE_Unbounded_Set_Iterator<
T > 		begin (void)
ACE_Unbounded_Set_Iterator<
T > 		end (void)

Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks.


Private Member Functions

void delete_nodes (void)
 Delete all the nodes in the Set.

void copy_nodes (const ACE_Unbounded_Set< T > &)
 Copy nodes into this set.


Private Attributes

ACE_Node< T > * head_
 Head of the linked list of Nodes.

size_t cur_size_
 Current size of the set.

ACE_Allocator * allocator_
 Allocation strategy of the set.


Friends

class ACE_Unbounded_Set_Iterator< T >
class ACE_Unbounded_Set_Const_Iterator< T >

Detailed Description

template<class T>
class ACE_Unbounded_Set< T >

Implement a simple unordered set of 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.

Requirements and Performance Characteristics

Definition at line 180 of file Unbounded_Set.h.

Member Typedef Documentation

template<class T>
typedef ACE_Unbounded_Set_Const_Iterator<T> ACE_Unbounded_Set< T >::const_iterator
 

Definition at line 190 of file Unbounded_Set.h.

template<class T>
typedef ACE_Unbounded_Set_Const_Iterator<T> ACE_Unbounded_Set< T >::CONST_ITERATOR
 

Definition at line 189 of file Unbounded_Set.h.

template<class T>
typedef ACE_Unbounded_Set_Iterator<T> ACE_Unbounded_Set< T >::iterator
 

Definition at line 188 of file Unbounded_Set.h.

template<class T>
typedef ACE_Unbounded_Set_Iterator<T> ACE_Unbounded_Set< T >::ITERATOR
 

Definition at line 187 of file Unbounded_Set.h.

Constructor & Destructor Documentation

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

Initialize an empty set using the allocation strategy of the user if provided.

Definition at line 133 of file Unbounded_Set.cpp.

References ACE_NEW_MALLOC, and ACE_Allocator::instance(). 

00134   : head_ (0),
00135     cur_size_ (0),
00136     allocator_ (alloc)
00137 {
00138   // ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set");
00139 
00140   if (this->allocator_ == 0)
00141     this->allocator_ = ACE_Allocator::instance ();
00142 
00143   ACE_NEW_MALLOC (this->head_,
00144                   (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00145                   ACE_Node<T>);
00146   // Make the list circular by pointing it back to itself.
00147   this->head_->next_ = this->head_;
00148 }

template<class T>
ACE_Unbounded_Set< T >::ACE_Unbounded_Set (  const ACE_Unbounded_Set< T > &   ) 
 

Copy constructor.

Initialize this set to be an exact copy of the set provided.

Definition at line 151 of file Unbounded_Set.cpp.

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

00152   : head_ (0),
00153     cur_size_ (0),
00154     allocator_ (us.allocator_)
00155 {
00156   ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set");
00157 
00158   if (this->allocator_ == 0)
00159     this->allocator_ = ACE_Allocator::instance ();
00160 
00161   ACE_NEW_MALLOC (this->head_,
00162                   (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)),
00163                   ACE_Node<T>);
00164   this->head_->next_ = this->head_;
00165   this->copy_nodes (us);
00166 }

template<class T>
ACE_Unbounded_Set< T >::~ACE_Unbounded_Set (  void   ) 
 

Destructor.

Destroy the nodes of the set.

Definition at line 118 of file Unbounded_Set.cpp.

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

00119 {
00120   // ACE_TRACE ("ACE_Unbounded_Set<T>::~ACE_Unbounded_Set");
00121 
00122   this->delete_nodes ();
00123 
00124   // Delete the dummy node.
00125   ACE_DES_FREE_TEMPLATE (head_,
00126                          this->allocator_->free,
00127                          ACE_Node,
00128                          <T>);
00129   this->head_ = 0;
00130 }

Member Function Documentation

template<class T>
ACE_Unbounded_Set_Iterator< T > ACE_Unbounded_Set< T >::begin (  void   ) 
 

Definition at line 240 of file Unbounded_Set.cpp.

Referenced by ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::find_description_i(), ACE_Registry_Name_Space::list_name_entries(), ACE_Registry::make_string(), ACE_Registry::Binding_Iterator::next_one(), ACE_Future_Rep< T >::set(), and ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::sort_event_descriptions_i(). 

00241 {
00242   // ACE_TRACE ("ACE_Unbounded_Set<T>::begin");
00243   return ACE_Unbounded_Set_Iterator<T> (*this);
00244 }

template<class T>
void ACE_Unbounded_Set< T >::copy_nodes (  const ACE_Unbounded_Set< T > &   )  [private]
 

Copy nodes into this set.

Definition at line 87 of file Unbounded_Set.cpp.

References ACE_Unbounded_Set< T >::head_, ACE_Unbounded_Set< T >::insert_tail(), ACE_Node< T >::item_, and ACE_Node< T >::next_.

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

00088 {
00089   for (ACE_Node<T> *curr = us.head_->next_;
00090        curr != us.head_;
00091        curr = curr->next_)
00092     this->insert_tail (curr->item_);
00093 }

template<class T>
void ACE_Unbounded_Set< T >::delete_nodes (  void   )  [private]
 

Delete all the nodes in the Set.

Definition at line 96 of file Unbounded_Set.cpp.

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

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

00097 {
00098   ACE_Node<T> *curr = this->head_->next_;
00099 
00100   // Keep looking until we've hit the dummy node.
00101 
00102   while (curr != this->head_)
00103     {
00104       ACE_Node<T> *temp = curr;
00105       curr = curr->next_;
00106       ACE_DES_FREE_TEMPLATE (temp,
00107                              this->allocator_->free,
00108                              ACE_Node,
00109                              <T>);
00110       --this->cur_size_;
00111     }
00112 
00113   // Reset the list to be a circular list with just a dummy node.
00114   this->head_->next_ = this->head_;
00115 }

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

Dump the state of an object.

Definition at line 62 of file Unbounded_Set.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_LIB_TEXT, ACE_TRACE, ACE_Unbounded_Set_Iterator< T >::advance(), LM_DEBUG, and ACE_Unbounded_Set_Iterator< T >::next(). 

00063 {
00064 #if defined (ACE_HAS_DUMP)
00065   ACE_TRACE ("ACE_Unbounded_Set<T>::dump");
00066 
00067   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00068   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_ = %u"), this->head_));
00069   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
00070   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
00071 
00072   T *item = 0;
00073 #if !defined (ACE_NLOGGING)
00074   size_t count = 1;
00075 #endif /* ! ACE_NLOGGING */
00076 
00077   for (ACE_Unbounded_Set_Iterator<T> iter (*(ACE_Unbounded_Set<T> *) this);
00078        iter.next (item) != 0;
00079        iter.advance ())
00080     ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("count = %d\n"), count++));
00081 
00082   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00083 #endif /* ACE_HAS_DUMP */
00084 }

template<class T>
ACE_Unbounded_Set_Iterator< T > ACE_Unbounded_Set< T >::end (  void   ) 
 

Definition at line 247 of file Unbounded_Set.cpp.

Referenced by ACE_Registry_Name_Space::list_name_entries(), ACE_Registry::make_string(), ACE_Future_Rep< T >::set(), and ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::sort_event_descriptions_i(). 

00248 {
00249   // ACE_TRACE ("ACE_Unbounded_Set<T>::end");
00250   return ACE_Unbounded_Set_Iterator<T> (*this, 1);
00251 }

template<class T>
int ACE_Unbounded_Set< T >::find (  const T &  item  )  const
 

Performs a linear find operation.

Definition at line 183 of file Unbounded_Set.cpp.

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

Referenced by ACE_Unbounded_Set< T >::insert(). 

00184 {
00185   // ACE_TRACE ("ACE_Unbounded_Set<T>::find");
00186   // Set <item> into the dummy node.
00187   this->head_->item_ = item;
00188 
00189   ACE_Node<T> *temp = this->head_->next_;
00190 
00191   // Keep looping until we find the item.
00192   while (!(temp->item_ == item))
00193     temp = temp->next_;
00194 
00195   // If we found the dummy node then it's not really there, otherwise,
00196   // it is there.
00197   return temp == this->head_ ? -1 : 0;
00198 }

template<class T>
int ACE_Unbounded_Set< T >::insert (  const T &  new_item  ) 
 

Linear insertion of an item.

Insert new_item into the set (doesn't allow duplicates). Returns -1 if failures occur, 1 if item is already present, else 0.

Definition at line 201 of file Unbounded_Set.cpp.

References ACE_Unbounded_Set< T >::find(), and ACE_Unbounded_Set< T >::insert_tail().

Referenced by ACE_Future_Rep< T >::attach(), ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::event_descriptions(), ACE_Service_Gestalt::insert(), ACE_Registry::Naming_Context::list(), ACE_Remote_Name_Space::list_name_entries(), ACE_Registry_Name_Space::list_name_entries(), ACE_Remote_Name_Space::list_names(), ACE_Registry_Name_Space::list_names(), ACE_Local_Name_Space<, ACE_LOCK >::list_names_i(), ACE_Remote_Name_Space::list_type_entries(), ACE_Local_Name_Space<, ACE_LOCK >::list_type_entries_i(), ACE_Remote_Name_Space::list_types(), ACE_Local_Name_Space<, ACE_LOCK >::list_types_i(), ACE_Remote_Name_Space::list_value_entries(), ACE_Local_Name_Space<, ACE_LOCK >::list_value_entries_i(), ACE_Remote_Name_Space::list_values(), ACE_Registry_Name_Space::list_values(), ACE_Local_Name_Space<, ACE_LOCK >::list_values_i(), ACE_Registry::make_name(), ACE_Registry::Binding_Iterator::Context_Iteration::next_n(), ACE_Registry::Binding_Iterator::Object_Iteration::next_n(), and ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::sort_event_descriptions_i(). 

00202 {
00203   // ACE_TRACE ("ACE_Unbounded_Set<T>::insert");
00204   if (this->find (item) == 0)
00205     return 1;
00206   else
00207     return this->insert_tail (item);
00208 }

template<class T>
int ACE_Unbounded_Set< T >::insert_tail (  const T &  item  ) 
 

Constant time insert at the end of the set.

Definition at line 30 of file Unbounded_Set.cpp.

References ACE_NEW_MALLOC_RETURN.

Referenced by ACE_Unbounded_Set< T >::copy_nodes(), and ACE_Unbounded_Set< T >::insert(). 

00031 {
00032   // ACE_TRACE ("ACE_Unbounded_Set<T>::insert_tail");
00033   ACE_Node<T> *temp;
00034 
00035   // Insert <item> into the old dummy node location.
00036   this->head_->item_ = item;
00037 
00038   // Create a new dummy node.
00039   ACE_NEW_MALLOC_RETURN (temp,
00040                          static_cast<ACE_Node<T>*> (this->allocator_->malloc (sizeof (ACE_Node<T>))),
00041                          ACE_Node<T> (this->head_->next_),
00042                          -1);
00043   // Link this pointer into the list.
00044   this->head_->next_ = temp;
00045 
00046   // Point the head to the new dummy node.
00047   this->head_ = temp;
00048 
00049   ++this->cur_size_;
00050   return 0;
00051 }

template<class T>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL ACE_INLINE int ACE_Unbounded_Set< T >::is_empty (  void   )  const
 

Returns 1 if the container is empty, otherwise returns 0.

Constant time is_empty check.

Definition at line 10 of file Unbounded_Set.inl.

References ACE_TRACE.

Referenced by ACE_Service_Gestalt::close(), and ACE_Service_Gestalt::~ACE_Service_Gestalt(). 

00011 {
00012   ACE_TRACE ("ACE_Unbounded_Set<T>::is_empty");
00013   return this->head_ == this->head_->next_;
00014 }

template<class T>
ACE_INLINE int ACE_Unbounded_Set< T >::is_full (  void   )  const
 

Returns 0.

Always returns 0 since the set can never fill up.

Definition at line 17 of file Unbounded_Set.inl.

References ACE_TRACE. 

00018 {
00019   ACE_TRACE ("ACE_Unbounded_Set<T>::is_full");
00020   return 0; // We should implement a "node of last resort for this..."
00021 }

template<class T>
ACE_Unbounded_Set< T > & ACE_Unbounded_Set< T >::operator= (  const ACE_Unbounded_Set< T > &   ) 
 

Assignment operator.

Perform a deep copy of the rhs into the lhs.

Definition at line 169 of file Unbounded_Set.cpp.

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

00170 {
00171   ACE_TRACE ("ACE_Unbounded_Set<T>::operator=");
00172 
00173   if (this != &us)
00174     {
00175       this->delete_nodes ();
00176       this->copy_nodes (us);
00177     }
00178 
00179   return *this;
00180 }

template<class T>
int ACE_Unbounded_Set< T >::remove (  const T &  item  ) 
 

Linear remove operation.

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.

Definition at line 211 of file Unbounded_Set.cpp.

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

Referenced by ACE_Future_Rep< T >::detach(), and ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::sort_event_descriptions_i(). 

00212 {
00213   // ACE_TRACE ("ACE_Unbounded_Set<T>::remove");
00214 
00215   // Insert the item to be founded into the dummy node.
00216   this->head_->item_ = item;
00217 
00218   ACE_Node<T> *curr = this->head_;
00219 
00220   while (!(curr->next_->item_ == item))
00221     curr = curr->next_;
00222 
00223   if (curr->next_ == this->head_)
00224     return -1; // Item was not found.
00225   else
00226     {
00227       ACE_Node<T> *temp = curr->next_;
00228       // Skip over the node that we're deleting.
00229       curr->next_ = temp->next_;
00230       --this->cur_size_;
00231       ACE_DES_FREE_TEMPLATE (temp,
00232                              this->allocator_->free,
00233                              ACE_Node,
00234                              <T>);
00235       return 0;
00236     }
00237 }

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

Reset the to be empty.

Delete the nodes of the set.

Definition at line 54 of file Unbounded_Set.cpp.

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

00055 {
00056   ACE_TRACE ("reset");
00057 
00058   this->delete_nodes ();
00059 }

template<class T>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL size_t ACE_Unbounded_Set< T >::size (  void   )  const
 

Size of the set.

Access the size of the set.

Definition at line 23 of file Unbounded_Set.cpp.

Referenced by ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::find_description_i(), and ACE_Timeprobe_Ex< ACE_LOCK, ALLOCATOR >::sort_event_descriptions_i(). 

00024 {
00025   // ACE_TRACE ("ACE_Unbounded_Set<T>::size");
00026   return this->cur_size_;
00027 }

Friends And Related Function Documentation

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

Definition at line 184 of file Unbounded_Set.h.

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

Definition at line 183 of file Unbounded_Set.h.

Member Data Documentation

template<class T>
ACE_Unbounded_Set< T >::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 285 of file Unbounded_Set.h.

template<class T>
ACE_Allocator* ACE_Unbounded_Set< T >::allocator_ [private]
 

Allocation strategy of the set.

Definition at line 301 of file Unbounded_Set.h.

template<class T>
size_t ACE_Unbounded_Set< T >::cur_size_ [private]
 

Current size of the set.

Definition at line 298 of file Unbounded_Set.h.

template<class T>
ACE_Node<T>* ACE_Unbounded_Set< T >::head_ [private]
 

Head of the linked list of Nodes.

Definition at line 295 of file Unbounded_Set.h.

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

The documentation for this class was generated from the following files:
Generated on Thu Nov 9 11:32:11 2006 for ACE by doxygen 1.3.6