Implement a simple unordered set of {T} with maximum {ACE_SIZE}. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Fixed_Set< T, ACE_SIZE >:

Public Types
typedef ACE_Fixed_Set_Iterator < T, ACE_SIZE >	ITERATOR
typedef ACE_Fixed_Set_Const_Iterator < T, ACE_SIZE >	CONST_ITERATOR
Public Member Functions
	ACE_Fixed_Set (void)
	Default Constructor.
	ACE_Fixed_Set (const ACE_Fixed_Set< T, ACE_SIZE > &)
	Copy constructor.
void	operator= (const ACE_Fixed_Set< T, ACE_SIZE > &)
	Assignment operator.
	~ACE_Fixed_Set (void)
	Destructor.
int	is_empty (void) const
	Returns 1 if the container is empty, otherwise returns 0.
int	is_full (void) const
	Returns 1 if the container is full, otherwise returns 0.
int	insert (const T &new_item)
	Linear time insertion of an item unique to the set.
int	remove (const T &item)
	Linear time removal operation of an item.
int	find (const T &item) const
	Finds if item occurs in the set. Returns 0 if finds, else -1.
size_t	size (void) const
	Size of the set.
void	dump (void) const
	Dump the state of an object.
Public Attributes
	ACE_ALLOC_HOOK_DECLARE
	Declare the dynamic allocation hooks.
T	item_
	Item in the set.
int	is_free_
	Keeps track of whether this item is in use or not.
Private Attributes
struct {
T item_
	Item in the set.
int is_free_
	Keeps track of whether this item is in use or not.
}	search_structure_ [ACE_SIZE]
	Holds the contents of the set.
size_t	cur_size_
	Current size of the set.
size_t	max_size_
	Maximum size of the set.
Friends
class	ACE_Fixed_Set_Iterator_Base< T, ACE_SIZE >
class	ACE_Fixed_Set_Iterator< T, ACE_SIZE >
class	ACE_Fixed_Set_Const_Iterator< T, ACE_SIZE >

Detailed Description

template<class T, size_t ACE_SIZE>
class ACE_Fixed_Set< T, ACE_SIZE >

Implement a simple unordered set of {T} with maximum {ACE_SIZE}.

This implementation of an unordered set uses a fixed array. It does not allow duplicate members. The set provides linear insertion/deletion operations.

Requirements and Performance Characteristics

Internal Structure Fixed array
Duplicates allowed? No
Random access allowed? No
Search speed Linear
Insert/replace speed Linear
Iterator still valid after change to container? Yes
Frees memory for removed elements? No
Items inserted by Value
Requirements for contained type
1. Default constructor
2. Copy constructor
3. operator=
4. operator==

Definition at line 1402 of file Containers_T.h.

Member Typedef Documentation

template<class T, size_t ACE_SIZE>

typedef ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE> ACE_Fixed_Set< T, ACE_SIZE >::CONST_ITERATOR

Definition at line 1411 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ACE_Fixed_Set< T, ACE_SIZE >::ITERATOR

Definition at line 1410 of file Containers_T.h.

Constructor & Destructor Documentation

template<class T , size_t ACE_SIZE>

ACE_Fixed_Set< T, ACE_SIZE >::ACE_Fixed_Set ( void )

Default Constructor.

Creates an empy set

Definition at line 957 of file Containers_T.cpp.

  : cur_size_ (0),
    max_size_ (ACE_SIZE)
{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::ACE_Fixed_Set");
  for (size_t i = 0; i < this->max_size_; i++)
    this->search_structure_[i].is_free_ = 1;
}

template<class T , size_t ACE_SIZE>

ACE_Fixed_Set< T, ACE_SIZE >::ACE_Fixed_Set ( const ACE_Fixed_Set< T, ACE_SIZE > & fs )

Copy constructor.

Initializes a set to be a copy of the set parameter.

Definition at line 931 of file Containers_T.cpp.

  : cur_size_ (fs.cur_size_)
{
  ACE_TRACE ("ACE_Fixed_Set<T>::ACE_Fixed_Set");

  for (size_t i = 0, j = 0; i < fs.max_size_ && j < this->cur_size_; ++i)
    if (fs.search_structure_[i].is_free_ == 0)
      this->search_structure_[j++] = fs.search_structure_[i];
}

template<class T , size_t ACE_SIZE>

ACE_Fixed_Set< T, ACE_SIZE >::~ACE_Fixed_Set ( void )

Destructor.

Destroys a set.

Definition at line 924 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::~ACE_Fixed_Set");
  this->cur_size_ = 0;
}

Member Function Documentation

template<class T , size_t ACE_SIZE>

void ACE_Fixed_Set< T, ACE_SIZE >::dump ( void ) const

Dump the state of an object.

Definition at line 916 of file Containers_T.cpp.

{
#if defined (ACE_HAS_DUMP)
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::dump");
#endif /* ACE_HAS_DUMP */
}

template<class T , size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::find ( const T & item ) const

Finds if item occurs in the set. Returns 0 if finds, else -1.

Performs a linear find operation for the specified item.

Definition at line 967 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::find");

  for (size_t i = 0, j = 0; i < this->max_size_ && j < this->cur_size_; ++i)
    if (this->search_structure_[i].is_free_ == 0)
      {
        if (this->search_structure_[i].item_ == item)
          return 0;
        ++j;
      }

  return -1;
}

template<class T , size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::insert ( const T & new_item )

Linear time insertion of an item unique to the set.

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 983 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::insert");
  ssize_t first_free = -1;   // Keep track of first free slot.
  size_t i;

  for (i = 0;
       i < this->max_size_  && first_free == -1;
       ++i)

    // First, make sure we don't allow duplicates.

    if (this->search_structure_[i].is_free_ == 0)
      {
        if (this->search_structure_[i].item_ == item)
          return 1;
      }
    else
      first_free = static_cast<ssize_t> (i);

  // If we found a free spot let's reuse it.

  if (first_free > -1)
    {
      this->search_structure_[first_free].item_ = item;
      this->search_structure_[first_free].is_free_ = 0;
      this->cur_size_++;
      return 0;
    }
  else /* No more room! */
    {
      errno = ENOMEM;
      return -1;
    }
}

template<class T , size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::is_empty ( void ) const [inline]

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

Performs constant time check to determine if a set is empty.

Definition at line 166 of file Containers_T.inl.

{
  ACE_TRACE ("ACE_Fixed_Set<T>::is_empty");
  return this->cur_size_ == 0;
}

template<class T , size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::is_full ( void ) const [inline]

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

Performs a constant time check to see if the set is full.

Definition at line 173 of file Containers_T.inl.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::is_full");
  return this->cur_size_ == this->max_size_;
}

template<class T , size_t ACE_SIZE>

void ACE_Fixed_Set< T, ACE_SIZE >::operator= ( const ACE_Fixed_Set< T, ACE_SIZE > & fs )

Assignment operator.

Deep copy of one set to another.

Definition at line 942 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T>::operator=");

  if (this != &fs)
    {
      this->cur_size_ = fs.cur_size_;

      for (size_t i = 0, j = 0; i < fs.max_size_ && j < this->cur_size_; ++i)
        if (fs.search_structure_[i].is_free_ == 0)
          this->search_structure_[j++] = fs.search_structure_[i];
    }
}

template<class T , size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::remove ( const T & item )

Linear time removal operation of an 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. Removal doesn't reclaim memory for the item.

Definition at line 1020 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::remove");

  for (size_t i = 0, j = 0;
       i < this->max_size_ && j < this->cur_size_;
       ++i)
    if (this->search_structure_[i].is_free_ == 0)
      {
        if (this->search_structure_[i].item_ == item)
          {
            // Mark this entry as being free.
            this->search_structure_[i].is_free_ = 1;

            --this->cur_size_;
            return 0;
          }
        else
          ++j;
      }

  return -1;
}

template<class T , size_t ACE_SIZE>

size_t ACE_Fixed_Set< T, ACE_SIZE >::size ( void ) const

Size of the set.

Returns the current size of the set.

Definition at line 909 of file Containers_T.cpp.

{
  ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::size");
  return this->cur_size_;
}

Friends And Related Function Documentation

template<class T, size_t ACE_SIZE>

friend class ACE_Fixed_Set_Const_Iterator< T, ACE_SIZE > [friend]

Definition at line 1407 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

friend class ACE_Fixed_Set_Iterator< T, ACE_SIZE > [friend]

Definition at line 1406 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

friend class ACE_Fixed_Set_Iterator_Base< T, ACE_SIZE > [friend]

Definition at line 1405 of file Containers_T.h.

Member Data Documentation

template<class T, size_t ACE_SIZE>

ACE_Fixed_Set< T, ACE_SIZE >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 1486 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

size_t ACE_Fixed_Set< T, ACE_SIZE >::cur_size_ [private]

Current size of the set.

Definition at line 1500 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

int ACE_Fixed_Set< T, ACE_SIZE >::is_free_

Keeps track of whether this item is in use or not.

Definition at line 1496 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

T ACE_Fixed_Set< T, ACE_SIZE >::item_

Item in the set.

Definition at line 1493 of file Containers_T.h.

template<class T, size_t ACE_SIZE>

size_t ACE_Fixed_Set< T, ACE_SIZE >::max_size_ [private]

Maximum size of the set.

Definition at line 1503 of file Containers_T.h.

struct { ... } ACE_Fixed_Set< T, ACE_SIZE >::search_structure_[ACE_SIZE] [private]

Holds the contents of the set.

The documentation for this class was generated from the following files:

ACE_Fixed_Set< T, ACE_SIZE > Class Template Reference

Public Types

Public Member Functions

Public Attributes

Private Attributes

Friends

Detailed Description

template<class T, size_t ACE_SIZE> class ACE_Fixed_Set< T, ACE_SIZE >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T, size_t ACE_SIZE>
class ACE_Fixed_Set< T, ACE_SIZE >