ACE_Bounded_Set< T > Class Template Reference

Implement a simple unordered set of {T} with maximum set at creation time. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Bounded_Set< T >:

[legend]List of all members.

Public Types
typedef ACE_Bounded_Set_Iterator< T >	ITERATOR
	DEFAULT_SIZE = 10
enum	{ DEFAULT_SIZE = 10 }
Public Member Functions
	ACE_Bounded_Set (void)
	Construct a Bounded_Set using the default size.
	ACE_Bounded_Set (size_t size)
	Construct a Bounded_Set with the provided sizeB.
	ACE_Bounded_Set (const ACE_Bounded_Set< T > &)
	Construct a Bounded_Set that is a copy of the provides Bounded_Set.
void	operator= (const ACE_Bounded_Set< T > &)
	Assignment operator.
	~ACE_Bounded_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)
	Inserts a new element unique to the set.
int	remove (const T &item)
	Finds the specified element and removes it from the set.
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.
Private Attributes
Search_Structure *	search_structure_
	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_Bounded_Set_Iterator< T >
Classes
struct	Search_Structure

---

Detailed Description

template<class T>
class ACE_Bounded_Set< T >

Implement a simple unordered set of {T} with maximum set at creation time.

This implementation of an unordered set uses a Bounded array. This implementation does not allow duplicates. It provides linear insert/remove/find operations. Insertion/removal does not invalidate iterators, but caution should be taken to ensure expected behavior. Once initialized, the object has a maximum size which can only be increased by the assignment of another larger Bounded_Set.

Requirements and Performance Characteristics

• Internal Structure Bounded array which can grow via assignment
• 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 1546 of file Containers_T.h.

---

Member Typedef Documentation

template<class T>

typedef ACE_Bounded_Set_Iterator<T> ACE_Bounded_Set< T >::ITERATOR

Definition at line 1552 of file Containers_T.h.

---

Member Enumeration Documentation

template<class T>

anonymous enum

Enumerator:

DEFAULT_SIZE

Definition at line 1554 of file Containers_T.h.

  {
    DEFAULT_SIZE = 10
  };

---

Constructor & Destructor Documentation

template<class T>

ACE_Bounded_Set< T >::ACE_Bounded_Set

(

void

)

Construct a Bounded_Set using the default size.

The default constructor initializes the Bounded_Set to a maximum size specified by the DEFAULT_SIZE.

Definition at line 1235 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::max_size_.

  : cur_size_ (0),
    max_size_ (static_cast<size_t> (ACE_Bounded_Set<T>::DEFAULT_SIZE))
{
  ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");

  ACE_NEW (this->search_structure_,
           typename ACE_Bounded_Set<T>::Search_Structure[this->max_size_]);

  for (size_t i = 0; i < this->max_size_; ++i)
    this->search_structure_[i].is_free_ = 1;
}

template<class T>

ACE_Bounded_Set< T >::ACE_Bounded_Set

(

size_t

size

)

Construct a Bounded_Set with the provided sizeB.

Initialize the Bounded_Set to have a maximum size equal to the size parameter specified.

Definition at line 1292 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::max_size_.

  : cur_size_ (0),
    max_size_ (size)
{
  ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");
  ACE_NEW (this->search_structure_,
           typename ACE_Bounded_Set<T>::Search_Structure[size]);

  for (size_t i = 0; i < this->max_size_; i++)
    this->search_structure_[i].is_free_ = 1;
}

template<class T>

ACE_Bounded_Set< T >::ACE_Bounded_Set

(

const ACE_Bounded_Set< T > &

)

Construct a Bounded_Set that is a copy of the provides Bounded_Set.

Initialize the Bounded_Set to be a copy of the Bounded_Set parameter.

Definition at line 1256 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, and ACE_Bounded_Set< T >::search_structure_.

  : cur_size_ (bs.cur_size_),
    max_size_ (bs.max_size_)
{
  ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set");

  ACE_NEW (this->search_structure_,
           typename ACE_Bounded_Set<T>::Search_Structure[this->max_size_]);

  for (size_t i = 0; i < this->cur_size_; i++)
    this->search_structure_[i] = bs.search_structure_[i];
}

template<class T>

ACE_Bounded_Set< T >::~ACE_Bounded_Set

(

void

)

Destructor.

Clean up the underlying dynamically allocated memory that is used by the Bounded_Set.

Definition at line 1228 of file Containers_T.cpp.

References ACE_TRACE, and ACE_Bounded_Set< T >::search_structure_.

{
  ACE_TRACE ("ACE_Bounded_Set<T>::~ACE_Bounded_Set");
  delete [] this->search_structure_;
}

---

Member Function Documentation

template<class T>

void ACE_Bounded_Set< T >::dump

(

void

)

const

Dump the state of an object.

Definition at line 1220 of file Containers_T.cpp.

References ACE_TRACE.

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

template<class T>

int ACE_Bounded_Set< T >::find

(

const T &

item

)

const

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

find preforms a linear search for {item} and returns 0 on successful find and -1 otherwise.

Definition at line 1305 of file Containers_T.cpp.

References ACE_TRACE, and ACE_Bounded_Set< T >::cur_size_.

{
  ACE_TRACE ("ACE_Bounded_Set<T>::find");

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

  return -1;
}

template<class T>

int ACE_Bounded_Set< T >::insert

(

const T &

new_item

)

Inserts a new element unique to the set.

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

Definition at line 1318 of file Containers_T.cpp.

References ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, and ACE_Bounded_Set< T >::max_size_.

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

  for (i = 0; i < this->cur_size_; i++)
    // First, make sure we don't allow duplicates.

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

  if (first_free > -1)   // If we found a free spot let's reuse it.
    {
      this->search_structure_[first_free].item_ = item;
      this->search_structure_[first_free].is_free_ = 0;
      return 0;
    }
  else if (i < this->max_size_) // Insert at the end of the active portion.
    {
      this->search_structure_[i].item_ = item;
      this->search_structure_[i].is_free_ = 0;
      this->cur_size_++;
      return 0;
    }
  else /* No more room! */
    {
      errno = ENOMEM;
      return -1;
    }
}

template<class T>

ACE_INLINE int ACE_Bounded_Set< T >::is_empty

(

void

)

const

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

A constant time check is performed to determine if the Bounded_Set is empty.

Definition at line 182 of file Containers_T.inl.

References ACE_TRACE, and ACE_Bounded_Set< T >::cur_size_.

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

template<class T>

ACE_INLINE int ACE_Bounded_Set< T >::is_full

(

void

)

const

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

Performs a constant time check to determine if the Bounded_Set is at capacity.

Definition at line 189 of file Containers_T.inl.

References ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, and ACE_Bounded_Set< T >::max_size_.

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

template<class T>

void ACE_Bounded_Set< T >::operator=

(

const ACE_Bounded_Set< T > &

)

Assignment operator.

The assignment will make a deep copy of the Bounded_Set provided. If the rhs has more elements than the capacity of the lhs, then the lhs will be deleted and reallocated to accomadate the larger number of elements.

Definition at line 1270 of file Containers_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, ACE_Bounded_Set< T >::max_size_, and ACE_Bounded_Set< T >::search_structure_.

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

  if (this != &bs)
    {
      if (this->max_size_ < bs.cur_size_)
        {
          delete [] this->search_structure_;
          ACE_NEW (this->search_structure_,
                   typename ACE_Bounded_Set<T>::Search_Structure[bs.cur_size_]);
          this->max_size_ = bs.cur_size_;
        }

      this->cur_size_ = bs.cur_size_;

      for (size_t i = 0; i < this->cur_size_; i++)
        this->search_structure_[i] = bs.search_structure_[i];
    }
}

template<class T>

int ACE_Bounded_Set< T >::remove

(

const T &

item

)

Finds the specified element and removes it from the set.

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. The linear remove operation does not reclaim the memory associated with the removed item.

Definition at line 1354 of file Containers_T.cpp.

References ACE_TRACE, and ACE_Bounded_Set< T >::cur_size_.

{
  ACE_TRACE ("ACE_Bounded_Set<T>::remove");
  for (size_t i = 0; i < this->cur_size_; i++)
    if (this->search_structure_[i].item_ == item)
      {
        // Mark this entry as being free.
        this->search_structure_[i].is_free_ = 1;

        // If we just unbound the highest entry, then we need to
        // figure out where the next highest active entry is.
        if (i + 1 == this->cur_size_)
          {
            while (i > 0 && this->search_structure_[--i].is_free_)
              continue;

            if (i == 0 && this->search_structure_[i].is_free_)
              this->cur_size_ = 0;
            else
              this->cur_size_ = i + 1;
          }
        return 0;
      }

  return -1;
}

template<class T>

size_t ACE_Bounded_Set< T >::size

(

void

)

const

Size of the set.

Returns a size_t representing the current size of the set.

Definition at line 1249 of file Containers_T.cpp.

References ACE_TRACE, and ACE_Bounded_Set< T >::cur_size_.

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

---

Friends And Related Function Documentation

template<class T>

friend class ACE_Bounded_Set_Iterator< T > [friend]

Definition at line 1549 of file Containers_T.h.

---

Member Data Documentation

template<class T>

ACE_Bounded_Set< T >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 1648 of file Containers_T.h.

template<class T>

size_t ACE_Bounded_Set< T >::cur_size_ [private]

Current size of the set.

Definition at line 1664 of file Containers_T.h.

Referenced by ACE_Bounded_Set< T >::ACE_Bounded_Set(), ACE_Bounded_Set< T >::find(), ACE_Bounded_Set< T >::insert(), ACE_Bounded_Set< T >::is_empty(), ACE_Bounded_Set< T >::is_full(), ACE_Bounded_Set< T >::operator=(), ACE_Bounded_Set< T >::remove(), and ACE_Bounded_Set< T >::size().

template<class T>

size_t ACE_Bounded_Set< T >::max_size_ [private]

Maximum size of the set.

Definition at line 1667 of file Containers_T.h.

Referenced by ACE_Bounded_Set< T >::ACE_Bounded_Set(), ACE_Bounded_Set< T >::insert(), ACE_Bounded_Set< T >::is_full(), and ACE_Bounded_Set< T >::operator=().

template<class T>

Search_Structure* ACE_Bounded_Set< T >::search_structure_ [private]

Holds the contents of the set.

Definition at line 1661 of file Containers_T.h.

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

---

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

• Containers_T.h
• Containers_T.cpp
• Containers_T.inl

---