---

ACE_Unbounded_Stack Class Template Reference

Implement a generic LIFO abstract data type. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Unbounded_Stack:

[legend]List of all members.

Public Types
typedef ACE_Unbounded_Stack_Iterator< T >	ITERATOR
Public Methods
	ACE_Unbounded_Stack (ACE_Allocator *alloc=0)
	Initialize a new stack so that it is empty. Use user defined allocation strategy if specified. More...
	ACE_Unbounded_Stack (const ACE_Unbounded_Stack< T > &s)
	The copy constructor (performs initialization). More...
void	operator= (const ACE_Unbounded_Stack< T > &s)
	Assignment operator (performs assignment). More...
	~ACE_Unbounded_Stack (void)
	Perform actions needed when stack goes out of scope. More...
int	push (const T &new_item)
	Push an element onto the top of stack. More...
int	pop (T &item)
	Pop the top element of the stack. More...
int	top (T &item) const
	Examine the top of the stack. More...
int	is_empty (void) const
	Returns 1 if the container is empty, otherwise returns 0. More...
int	is_full (void) const
	Returns 1 if the container is full, otherwise returns 0. More...
int	insert (const T &new_item)
	Linear Insert of an item. More...
int	remove (const T &item)
	Remove item from the Stack. Returns 0 if it removes the item, -1 if it can't find the item, and -1 if a failure occurs. More...
int	find (const T &item) const
	Finds if item occurs the set. Returns 0 if finds, else -1. More...
size_t	size (void) const
	The number of items in the stack. More...
void	dump (void) const
	Dump the state of an object. More...
Public Attributes
	ACE_ALLOC_HOOK_DECLARE
	Declare the dynamic allocation hooks. More...
Private Methods
void	delete_all_nodes (void)
	Delete all the nodes in the stack. More...
void	copy_all_nodes (const ACE_Unbounded_Stack< T > &s)
	Copy all nodes from <s> to <this>. More...
Private Attributes
ACE_Node< T > *	head_
	Head of the linked list of Nodes. More...
size_t	cur_size_
	Current size of the stack. More...
ACE_Allocator *	allocator_
	Allocation strategy of the stack. More...
Friends
class	ACE_Unbounded_Stack_Iterator< T >

---

Detailed Description

template<class T>
class ACE_Unbounded_Stack< T >

Implement a generic LIFO abstract data type.

This implementation of an unbounded Stack uses a linked list. If you use the <insert> or <remove> methods you should keep in mind that duplicate entries aren't allowed. In general, therefore, you should avoid the use of these methods since they aren't really part of the ADT stack. The stack is implemented as a doubly linked list.

Requirements and Performance Characteristics

• Internal Structure Double linked list
• 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? Yes
• Items inserted by Value
• Requirements for contained type
  1. Default constructor
  2. Copy constructor
  3. operator=

Definition at line 374 of file Containers_T.h.

---

Member Typedef Documentation

template<class T> typedef ACE_Unbounded_Stack_Iterator<T> ACE_Unbounded_Stack::ITERATOR

Definition at line 380 of file Containers_T.h.

---

Constructor & Destructor Documentation

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

Initialize a new stack so that it is empty. Use user defined allocation strategy if specified. Initialize an empty stack using the user specified allocation strategy if provided. Definition at line 140 of file Containers_T.cpp. References ACE_NEW_MALLOC, allocator_, head_, and ACE_Allocator::instance. : head_ (0), cur_size_ (0), allocator_ (alloc) { // ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack"); if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); this->head_->next_ = this->head_; }

template<class T> ACE_Unbounded_Stack< T >::ACE_Unbounded_Stack (  const ACE_Unbounded_Stack< T > &    s )

The copy constructor (performs initialization). Initialize this stack to be an exact copy of <s>. Definition at line 197 of file Containers_T.cpp. References ACE_NEW_MALLOC, allocator_, copy_all_nodes, head_, and ACE_Allocator::instance. : head_ (0), cur_size_ (0), allocator_ (s.allocator_) { if (this->allocator_ == 0) this->allocator_ = ACE_Allocator::instance (); ACE_NEW_MALLOC (this->head_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T>); this->head_->next_ = this->head_; // ACE_TRACE ("ACE_Unbounded_Stack<T>::ACE_Unbounded_Stack"); this->copy_all_nodes (s); }

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

Perform actions needed when stack goes out of scope. Destroy the underlying list for the stack. Definition at line 227 of file Containers_T.cpp. References ACE_DES_FREE_TEMPLATE, delete_all_nodes, and head_. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::~ACE_Unbounded_Stack"); this->delete_all_nodes (); ACE_DES_FREE_TEMPLATE (head_, this->allocator_->free, ACE_Node, <T>); }

---

Member Function Documentation

template<class T> void ACE_Unbounded_Stack< T >::copy_all_nodes (  const ACE_Unbounded_Stack< T > &    s )  [private]

Copy all nodes from <s> to <this>. Definition at line 175 of file Containers_T.cpp. References ACE_ASSERT, ACE_NEW_MALLOC, cur_size_, head_, ACE_Node::item_, and ACE_Node::next_. Referenced by ACE_Unbounded_Stack, and operator=. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::copy_all_nodes"); ACE_ASSERT (this->head_ == this->head_->next_); ACE_Node<T> *temp = this->head_; for (ACE_Node<T> *s_temp = s.head_->next_; s_temp != s.head_; s_temp = s_temp->next_) { ACE_Node<T> *nptr = temp->next_; ACE_NEW_MALLOC (temp->next_, (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)), ACE_Node<T> (s_temp->item_, nptr)); temp = temp->next_; } this->cur_size_ = s.cur_size_; }

template<class T> void ACE_Unbounded_Stack< T >::delete_all_nodes (  void    )  [private]

Delete all the nodes in the stack. Definition at line 156 of file Containers_T.cpp. References ACE_ASSERT, ACE_DES_FREE_TEMPLATE, cur_size_, head_, is_empty, and ACE_Node::next_. Referenced by operator=, and ~ACE_Unbounded_Stack. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::delete_all_nodes"); while (this->is_empty () == 0) { ACE_Node<T> *temp = this->head_->next_; this->head_->next_ = temp->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); } this->cur_size_ = 0; ACE_ASSERT (this->head_ == this->head_->next_ && this->is_empty ()); }

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

Dump the state of an object. Definition at line 134 of file Containers_T.cpp. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::dump"); }

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

Finds if item occurs the set. Returns 0 if finds, else -1. Linear find operation. Definition at line 278 of file Containers_T.cpp. References head_, ACE_Node::item_, and ACE_Node::next_. Referenced by insert. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::find"); // Set <item> into the dummy node. this->head_->item_ = item; ACE_Node<T> *temp = this->head_->next_; // Keep looping until we find the item. while (!(temp->item_ == item)) temp = temp->next_; // If we found the dummy node then it's not really there, otherwise, // it is there. return temp == this->head_ ? -1 : 0; }

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

Linear Insert of an item. Insert <new_item> into the Stack at the head (but doesn't allow duplicates). Returns -1 if failures occur, 1 if item is already present (i.e., no duplicates are allowed), else 0. Definition at line 296 of file Containers_T.cpp. References find, and push. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::insert"); if (this->find (item) == 0) return 1; else return this->push (item); }

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

Returns 1 if the container is empty, otherwise returns 0. Constant time check to see if the stack is empty. Definition at line 127 of file Containers_T.i. References head_. Referenced by delete_all_nodes, pop, and top. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::is_empty"); return this->head_ == this->head_->next_; }

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

Returns 1 if the container is full, otherwise returns 0. Always resturns 0 since the stack is unbounded. Definition at line 147 of file Containers_T.i. References ACE_TRACE. { ACE_TRACE ("ACE_Unbounded_Stack<T>::is_full"); return 0; // ??? }

template<class T> void ACE_Unbounded_Stack< T >::operator= (  const ACE_Unbounded_Stack< T > &    s )

Assignment operator (performs assignment). Perform a deep copy of the rhs into the lhs. Definition at line 215 of file Containers_T.cpp. References copy_all_nodes, and delete_all_nodes. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::operator="); if (this != &s) { this->delete_all_nodes (); this->copy_all_nodes (s); } }

template<class T> int ACE_Unbounded_Stack< T >::pop (  T &    item )

Pop the top element of the stack. Remove and return the top stack item. Returns -1 if the stack is already empty, 0 if the stack is not already empty, and -1 if failure occurs. Definition at line 256 of file Containers_T.cpp. References ACE_DES_FREE_TEMPLATE, cur_size_, head_, is_empty, ACE_Node::item_, and ACE_Node::next_. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::pop"); if (this->is_empty ()) return -1; else { ACE_Node<T> *temp = this->head_->next_; item = temp->item_; this->head_->next_ = temp->next_; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); this->cur_size_--; return 0; } }

template<class T> int ACE_Unbounded_Stack< T >::push (  const T &    new_item )

Push an element onto the top of stack. Place a new item on top of the stack. Returns -1 if the stack is already full, 0 if the stack is not already full, and -1 if failure occurs. Definition at line 239 of file Containers_T.cpp. References ACE_NEW_MALLOC_RETURN, cur_size_, and head_. Referenced by insert. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::push"); ACE_Node<T> *temp; ACE_NEW_MALLOC_RETURN (temp, ACE_static_cast(ACE_Node<T> *, this->allocator_->malloc (sizeof (ACE_Node<T>))), ACE_Node<T> (new_item, this->head_->next_), -1); this->head_->next_ = temp; this->cur_size_++; return 0; }

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

Remove item from the Stack. Returns 0 if it removes the item, -1 if it can't find the item, and -1 if a failure occurs. Linear remove operation. Definition at line 307 of file Containers_T.cpp. References ACE_DES_FREE_TEMPLATE, cur_size_, head_, and ACE_Node::next_. { // ACE_TRACE ("ACE_Unbounded_Stack<T>::remove"); // Insert the item to be founded into the dummy node. this->head_->item_ = item; ACE_Node<T> *curr = this->head_; while (!(curr->next_->item_ == item)) curr = curr->next_; if (curr->next_ == this->head_) return -1; // Item was not found. else { ACE_Node<T> *temp = curr->next_; // Skip over the node that we're deleting. curr->next_ = temp->next_; this->cur_size_--; ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, ACE_Node, <T>); return 0; } }

template<class T> ACE_INLINE size_t ACE_Unbounded_Stack< T >::size (  void    )  const

The number of items in the stack. Constant time access to the current stack size. Definition at line 154 of file Containers_T.i. References cur_size_. { return this->cur_size_; }

template<class T> ACE_INLINE int ACE_Unbounded_Stack< T >::top (  T &    item )  const

Examine the top of the stack. Return top stack item without removing it. Returns -1 if the stack is already empty, 0 if the stack is not already empty, and -1 if failure occurs. Definition at line 134 of file Containers_T.i. References ACE_TRACE, head_, and is_empty. { ACE_TRACE ("ACE_Unbounded_Stack<T>::top"); if (this->is_empty () == 0) { item = this->head_->next_->item_; return 0; } else return -1; }

---

Friends And Related Function Documentation

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

Definition at line 377 of file Containers_T.h.

---

Member Data Documentation

template<class T> ACE_Unbounded_Stack::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks. Definition at line 483 of file Containers_T.h.

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

Allocation strategy of the stack. Definition at line 499 of file Containers_T.h. Referenced by ACE_Unbounded_Stack.

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

Current size of the stack. Definition at line 496 of file Containers_T.h. Referenced by copy_all_nodes, delete_all_nodes, pop, push, remove, and size.

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

Head of the linked list of Nodes. Definition at line 493 of file Containers_T.h. Referenced by ACE_Unbounded_Stack, copy_all_nodes, delete_all_nodes, find, is_empty, pop, push, remove, top, and ~ACE_Unbounded_Stack.

---

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

• Containers_T.h
• Containers_T.cpp
• Containers_T.i

---