Public Types | Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | Friends

ACE_Unbounded_Set_Ex< T, C > Class Template Reference

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

#include <Unbounded_Set_Ex.h>

Collaboration diagram for ACE_Unbounded_Set_Ex< T, C >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef
ACE_Unbounded_Set_Ex_Iterator
< T, C > 		ITERATOR
typedef
ACE_Unbounded_Set_Ex_Iterator
< T, C > 		iterator
typedef
ACE_Unbounded_Set_Ex_Const_Iterator
< T, C > 		CONST_ITERATOR
typedef
ACE_Unbounded_Set_Ex_Const_Iterator
< T, C > 		const_iterator
typedef C COMP
typedef ACE_Node< T, C > NODE
typedef T value_type
typedef T const const_value_type
typedef value_type & reference
typedef const_value_type & const_reference
typedef value_type * pointer
typedef const_value_type * const_pointer
typedef ptrdiff_t difference_type

Public Member Functions

 ACE_Unbounded_Set_Ex (ACE_Allocator *alloc=0)
 ACE_Unbounded_Set_Ex (const C &comparator, ACE_Allocator *alloc=0)
 ACE_Unbounded_Set_Ex (const ACE_Unbounded_Set_Ex< T, C > &)
 Copy constructor.
ACE_Unbounded_Set_Ex< T, C > & operator= (const ACE_Unbounded_Set_Ex< T, C > &)
 Assignment operator.
 ~ACE_Unbounded_Set_Ex (void)
 Destructor.
bool is_empty (void) const
 Returns true if the container is empty, otherwise returns false.
bool is_full (void) const
 Returns false.
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 ACE_Unbounded_Set_Ex to be empty.
iterator begin (void)
iterator end (void)
const_iterator begin (void) const
const_iterator end (void) const

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_Ex< T, C > &)
 Copy nodes into this set.

Private Attributes

NODE * 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.
COMP comp_
 Comparator to be used.

Friends

class ACE_Unbounded_Set_Ex_Iterator< T, C >
class ACE_Unbounded_Set_Ex_Const_Iterator< T, C >

Detailed Description

template<class T, class C>
class ACE_Unbounded_Set_Ex< T, C >

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.

This implementation may also be parameterized with a comparator functor, which must implement bool operator () (const T&, const T&) const, returning true if the given items are equivalent. The default comparator is sufficient for objects reliably compared with operator==.

Requirements and Performance Characteristics

Definition at line 215 of file Unbounded_Set_Ex.h.

Member Typedef Documentation

template<class T, class C>
typedef C ACE_Unbounded_Set_Ex< T, C >::COMP

Definition at line 226 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::CONST_ITERATOR

Definition at line 224 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::const_iterator

Definition at line 225 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef const_value_type* ACE_Unbounded_Set_Ex< T, C >::const_pointer

Definition at line 235 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef const_value_type& ACE_Unbounded_Set_Ex< T, C >::const_reference

Definition at line 233 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef T const ACE_Unbounded_Set_Ex< T, C >::const_value_type

Definition at line 231 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ptrdiff_t ACE_Unbounded_Set_Ex< T, C >::difference_type

Definition at line 236 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::iterator

Definition at line 223 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::ITERATOR

Definition at line 222 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Node<T, C> ACE_Unbounded_Set_Ex< T, C >::NODE

Definition at line 227 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef value_type* ACE_Unbounded_Set_Ex< T, C >::pointer

Definition at line 234 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef value_type& ACE_Unbounded_Set_Ex< T, C >::reference

Definition at line 232 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef T ACE_Unbounded_Set_Ex< T, C >::value_type

Definition at line 230 of file Unbounded_Set_Ex.h.

Constructor & Destructor Documentation

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( 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 134 of file Unbounded_Set_Ex.cpp.

  : head_ (0),
    cur_size_ (0),
    allocator_ (alloc)
{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");

  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  ACE_NEW_MALLOC (this->head_,
                  (NODE*) this->allocator_->malloc (sizeof (NODE)),
                  NODE);
  // Make the list circular by pointing it back to itself.
  this->head_->next_ = this->head_;
}

template<class T , class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( const C &  comparator,
ACE_Allocator *  alloc = 0 
)

Initialize an empty set using the allocation strategy of the user if provided, and a given comparator functor.

Definition at line 152 of file Unbounded_Set_Ex.cpp.

  : head_ (0),
    cur_size_ (0),
    allocator_ (alloc),
    comp_ (comp)
{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");

  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  ACE_NEW_MALLOC (this->head_,
                  (NODE*) this->allocator_->malloc (sizeof (NODE)),
                  NODE);
  // Make the list circular by pointing it back to itself.
  this->head_->next_ = this->head_;
}

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( const ACE_Unbounded_Set_Ex< T, C > &  us  ) 

Copy constructor.

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

Definition at line 172 of file Unbounded_Set_Ex.cpp.

  : head_ (0),
    cur_size_ (0),
    allocator_ (us.allocator_),
    comp_ (us.comp_)
{
  ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");

  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  ACE_NEW_MALLOC (this->head_,
                  (NODE*) this->allocator_->malloc (sizeof (NODE)),
                  NODE);
  this->head_->next_ = this->head_;
  this->copy_nodes (us);
}

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::~ACE_Unbounded_Set_Ex ( void   ) 

Destructor.

Destroy the nodes of the set.

Definition at line 119 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::~ACE_Unbounded_Set_Ex");

  this->delete_nodes ();

  // Delete the dummy node.
  ACE_DES_FREE_TEMPLATE2 (head_,
                         this->allocator_->free,
                         ACE_Node,
                         T, C);
  this->head_ = 0;
}

Member Function Documentation

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void   ) 

Definition at line 256 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::begin");
  return iterator (*this);
}

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void   )  const

Definition at line 270 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::begin");
  return const_iterator (*this);
}

template<class T, class C>
void ACE_Unbounded_Set_Ex< T, C >::copy_nodes ( const ACE_Unbounded_Set_Ex< T, C > &  us  )  [private]

Copy nodes into this set.

Definition at line 88 of file Unbounded_Set_Ex.cpp.

{
  for (NODE *curr = us.head_->next_;
       curr != us.head_;
       curr = curr->next_)
    this->insert_tail (curr->item_);
}

template<class T , class C >
void ACE_Unbounded_Set_Ex< T, C >::delete_nodes ( void   )  [private]

Delete all the nodes in the Set.

Definition at line 97 of file Unbounded_Set_Ex.cpp.

{
  NODE *curr = this->head_->next_;

  // Keep looking until we've hit the dummy node.

  while (curr != this->head_)
    {
      NODE *temp = curr;
      curr = curr->next_;
      ACE_DES_FREE_TEMPLATE2 (temp,
                             this->allocator_->free,
                             ACE_Node,
                             T, C);
      --this->cur_size_;
    }

  // Reset the list to be a circular list with just a dummy node.
  this->head_->next_ = this->head_;
}

template<class T , class C >
void ACE_Unbounded_Set_Ex< T, C >::dump ( void   )  const

Dump the state of an object.

Definition at line 62 of file Unbounded_Set_Ex.cpp.

{
#if defined (ACE_HAS_DUMP)
  ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::dump");

  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_ = %u"), this->head_));
  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
  ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));

  T *item = 0;
#if !defined (ACE_NLOGGING)
  size_t count = 1;
#endif /* ! ACE_NLOGGING */

  const_iterator const the_end = this->end ();
  for (const_iterator i (this->begin ());
       i != end;
       ++i)
    ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("count = %u\n"), count++));

  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
#endif /* ACE_HAS_DUMP */
}

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::end ( void   ) 

Definition at line 263 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::end");
  return iterator (*this, 1);
}

template<class T , class C >
ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::end ( void   )  const

Definition at line 277 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::end");
  return const_iterator (*this, 1);
}

template<class T, class C >
int ACE_Unbounded_Set_Ex< T, C >::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 205 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::find");
  const_iterator const the_end = this->end ();
  for (const_iterator i = this->begin (); i != the_end; ++i)
    if (this->comp_(*i, item))
      return 0;

  return -1;
}

template<class T, class C >
int ACE_Unbounded_Set_Ex< T, C >::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 217 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::insert");
  if (this->find (item) == 0)
    return 1;
  else
    return this->insert_tail (item);
}

template<class T, class C >
int ACE_Unbounded_Set_Ex< T, C >::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_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::insert_tail");
  NODE *temp = 0;

  // Insert <item> into the old dummy node location.
  this->head_->item_ = item;

  // Create a new dummy node.
  ACE_NEW_MALLOC_RETURN (temp,
                         static_cast<NODE*> (this->allocator_->malloc (sizeof (NODE))),
                         NODE (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 , class C >
bool ACE_Unbounded_Set_Ex< T, C >::is_empty ( void   )  const

Returns true if the container is empty, otherwise returns false.

Constant time is_empty check.

Definition at line 10 of file Unbounded_Set_Ex.inl.

{
  ACE_TRACE ("ACE_Unbounded_Set_Ex<T>::is_empty");
  return this->head_ == this->head_->next_;
}

template<class T , class C >
bool ACE_Unbounded_Set_Ex< T, C >::is_full ( void   )  const

Returns false.

Always returns false since the set can never fill up.

Definition at line 17 of file Unbounded_Set_Ex.inl.

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

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C > & ACE_Unbounded_Set_Ex< T, C >::operator= ( const ACE_Unbounded_Set_Ex< T, C > &  us  ) 

Assignment operator.

Perform a deep copy of the rhs into the lhs.

Definition at line 191 of file Unbounded_Set_Ex.cpp.

{
  ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::operator=");

  if (this != &us)
    {
      this->delete_nodes ();
      this->copy_nodes (us);
    }

  return *this;
}

template<class T, class C >
int ACE_Unbounded_Set_Ex< T, C >::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 227 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::remove");

  // Insert the item to be founded into the dummy node.
  this->head_->item_ = item;

  NODE *curr = this->head_;

  while (!(this->comp_ (curr->next_->item_, item)))
    curr = curr->next_;

  if (curr->next_ == this->head_)
    return -1; // Item was not found.
  else
    {
      NODE *temp = curr->next_;
      // Skip over the node that we're deleting.
      curr->next_ = temp->next_;
      --this->cur_size_;
      ACE_DES_FREE_TEMPLATE2 (temp,
                             this->allocator_->free,
                             ACE_Node,
                             T, C);
      return 0;
    }
}

template<class T , class C >
void ACE_Unbounded_Set_Ex< T, C >::reset ( void   ) 

Reset the ACE_Unbounded_Set_Ex to be empty.

Delete the nodes of the set.

Definition at line 54 of file Unbounded_Set_Ex.cpp.

{
  ACE_TRACE ("reset");

  this->delete_nodes ();
}

template<class T , class C >
size_t ACE_Unbounded_Set_Ex< T, C >::size ( void   )  const

Size of the set.

Access the size of the set.

Definition at line 23 of file Unbounded_Set_Ex.cpp.

{
  // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::size");
  return this->cur_size_;
}

Friends And Related Function Documentation

template<class T, class C>
friend class ACE_Unbounded_Set_Ex_Const_Iterator< T, C > [friend]

Definition at line 219 of file Unbounded_Set_Ex.h.

template<class T, class C>
friend class ACE_Unbounded_Set_Ex_Iterator< T, C > [friend]

Definition at line 218 of file Unbounded_Set_Ex.h.

Member Data Documentation

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 339 of file Unbounded_Set_Ex.h.

template<class T, class C>
ACE_Allocator* ACE_Unbounded_Set_Ex< T, C >::allocator_ [private]

Allocation strategy of the set.

Definition at line 355 of file Unbounded_Set_Ex.h.

template<class T, class C>
COMP ACE_Unbounded_Set_Ex< T, C >::comp_ [private]

Comparator to be used.

Definition at line 358 of file Unbounded_Set_Ex.h.

template<class T, class C>
size_t ACE_Unbounded_Set_Ex< T, C >::cur_size_ [private]

Current size of the set.

Definition at line 352 of file Unbounded_Set_Ex.h.

template<class T, class C>
NODE* ACE_Unbounded_Set_Ex< T, C >::head_ [private]

Head of the linked list of Nodes.

Definition at line 349 of file Unbounded_Set_Ex.h.

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Thu Dec 9 2010 11:57:58 for ACE by  doxygen 1.7.0