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

ACE_Unbounded_Set Class Template Reference

Implement a simple unordered set of <T> of unbounded size. More...

#include <Unbounded_Set.h>

Inheritance diagram for ACE_Unbounded_Set:

Inheritance graph
[legend]
Collaboration diagram for ACE_Unbounded_Set:

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 Methods

 ACE_Unbounded_Set (ACE_Allocator *alloc=0)
 Constructor. Use user specified allocation strategy if specified. More...

 ACE_Unbounded_Set (const ACE_Unbounded_Set< T > &)
 Copy constructor. More...

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

 ~ACE_Unbounded_Set (void)
 Destructor. More...

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

int is_full (void) const
 Returns 0. More...

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

int insert_tail (const T &item)
 Insert <item> at the tail of the set (doesn't check for duplicates). More...

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

int find (const T &item) const
 Finds if <item> occurs in the set. Returns 0 if find succeeds, else -1. More...

size_t size (void) const
 Size of the set. More...

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

void reset (void)
 Reset the <ACE_Unbounded_Set> to be empty. More...

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. More...


Private Methods

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

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


Private Attributes

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

size_t cur_size_
 Current size of the set. More...

ACE_Allocator * allocator_
 Allocation strategy of the set. More...


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 <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.

Requirements and Performance Characteristics

Definition at line 177 of file Unbounded_Set.h.

Member Typedef Documentation

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

Definition at line 187 of file Unbounded_Set.h.

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

Definition at line 186 of file Unbounded_Set.h.

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

Definition at line 185 of file Unbounded_Set.h.

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

Definition at line 184 of file Unbounded_Set.h.

Constructor & Destructor Documentation

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

Constructor. Use user specified allocation strategy if specified.

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

Definition at line 132 of file Unbounded_Set.cpp.

References ACE_NEW_MALLOC, allocator_, head_, and ACE_Allocator::instance. 

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

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 150 of file Unbounded_Set.cpp.

References ACE_NEW_MALLOC, ACE_TRACE, allocator_, copy_nodes, head_, and ACE_Allocator::instance. 

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

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

Destructor.

Destroy the nodes of the set.

Definition at line 117 of file Unbounded_Set.cpp.

References ACE_DES_FREE_TEMPLATE, delete_nodes, and head_. 

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

Member Function Documentation

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

Definition at line 237 of file Unbounded_Set.cpp.

Referenced by ACE_Registry::make_string, and ACE_Registry::Binding_Iterator::next_one. 

00238 {
00239   // ACE_TRACE ("ACE_Unbounded_Set<T>::begin");
00240   return ACE_Unbounded_Set_Iterator<T> (*this);
00241 }

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

Copy nodes into this set.

Definition at line 86 of file Unbounded_Set.cpp.

References head_, insert_tail, ACE_Node::item_, and ACE_Node::next_.

Referenced by ACE_Unbounded_Set, and operator=. 

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

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

Delete all the nodes in the Set.

Definition at line 95 of file Unbounded_Set.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, and ACE_Node::next_.

Referenced by operator=, reset, and ~ACE_Unbounded_Set. 

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

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

Dump the state of an object.

Definition at line 63 of file Unbounded_Set.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_LIB_TEXT, ACE_TRACE, ACE_Unbounded_Set_Iterator::advance, LM_DEBUG, and ACE_Unbounded_Set_Iterator::next. 

00064 {
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 }

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

Definition at line 244 of file Unbounded_Set.cpp.

Referenced by ACE_Registry::make_string. 

00245 {
00246   // ACE_TRACE ("ACE_Unbounded_Set<T>::end");
00247   return ACE_Unbounded_Set_Iterator<T> (*this, 1);
00248 }

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

Finds if <item> occurs in the set. Returns 0 if find succeeds, else -1.

Performs a linear find operation.

Definition at line 180 of file Unbounded_Set.cpp.

References head_, ACE_Node::item_, and ACE_Node::next_.

Referenced by insert. 

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

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 198 of file Unbounded_Set.cpp.

References find, and insert_tail.

Referenced by 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::list_names_i, ACE_Remote_Name_Space::list_type_entries, ACE_Local_Name_Space::list_type_entries_i, ACE_Remote_Name_Space::list_types, ACE_Local_Name_Space::list_types_i, ACE_Remote_Name_Space::list_value_entries, ACE_Local_Name_Space::list_value_entries_i, ACE_Remote_Name_Space::list_values, ACE_Registry_Name_Space::list_values, ACE_Local_Name_Space::list_values_i, ACE_Registry::make_name, ACE_Registry::Binding_Iterator::Context_Iteration::next_n, and ACE_Registry::Binding_Iterator::Object_Iteration::next_n. 

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

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

Insert <item> at the tail of the set (doesn't check for duplicates).

Constant time insert at the end of the set.

Definition at line 30 of file Unbounded_Set.cpp.

References ACE_NEW_MALLOC_RETURN, cur_size_, and head_.

Referenced by copy_nodes, and 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                          ACE_static_cast(ACE_Node<T>*,
00041                            this->allocator_->malloc (sizeof (ACE_Node<T>))),
00042                          ACE_Node<T> (this->head_->next_),
00043                          -1);
00044   // Link this pointer into the list.
00045   this->head_->next_ = temp;
00046 
00047   // Point the head to the new dummy node.
00048   this->head_ = temp;
00049 
00050   this->cur_size_++;
00051   return 0;
00052 }

template<class T>
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 5 of file Unbounded_Set.inl.

References ACE_TRACE, and head_. 

00006 {
00007   ACE_TRACE ("ACE_Unbounded_Set<T>::is_empty");
00008   return this->head_ == this->head_->next_;
00009 }

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 12 of file Unbounded_Set.inl.

References ACE_TRACE. 

00013 {
00014   ACE_TRACE ("ACE_Unbounded_Set<T>::is_full");
00015   return 0; // We should implement a "node of last resort for this..."
00016 }

template<class T>
void 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 168 of file Unbounded_Set.cpp.

References ACE_TRACE, copy_nodes, and delete_nodes. 

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

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 208 of file Unbounded_Set.cpp.

References ACE_DES_FREE_TEMPLATE, cur_size_, head_, and ACE_Node::next_. 

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

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

Reset the <ACE_Unbounded_Set> to be empty.

Delete the nodes of the set.

Definition at line 55 of file Unbounded_Set.cpp.

References ACE_TRACE, and delete_nodes.

Referenced by ACE_Registry::Naming_Context::list. 

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

template<class T>
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.

References cur_size_. 

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 181 of file Unbounded_Set.h.

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

Definition at line 180 of file Unbounded_Set.h.

Member Data Documentation

template<class T>
ACE_Unbounded_Set::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 282 of file Unbounded_Set.h.

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

Allocation strategy of the set.

Definition at line 298 of file Unbounded_Set.h.

Referenced by ACE_Unbounded_Set.

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

Current size of the set.

Definition at line 295 of file Unbounded_Set.h.

Referenced by delete_nodes, insert_tail, remove, and size.

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

Head of the linked list of Nodes.

Definition at line 292 of file Unbounded_Set.h.

Referenced by ACE_Unbounded_Set, copy_nodes, delete_nodes, find, insert_tail, is_empty, remove, and ~ACE_Unbounded_Set.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:58:53 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002