You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
588 lines
19 KiB
588 lines
19 KiB
#ifndef _STACK_HPP_
|
|
#define _STACK_HPP_
|
|
// Ruler
|
|
// 1 2 3 4 5 6 7 8
|
|
//345678901234567890123456789012345678901234567890123456789012345678901234567890
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* The standard layout. */
|
|
/* */
|
|
/* The standard layout for 'hpp' files for this code is as */
|
|
/* follows: */
|
|
/* */
|
|
/* 1. Include files. */
|
|
/* 2. Constants exported from the class. */
|
|
/* 3. Data structures exported from the class. */
|
|
/* 4. Forward references to other data structures. */
|
|
/* 5. Class specifications (including inline functions). */
|
|
/* 6. Additional large inline functions. */
|
|
/* */
|
|
/* Any portion that is not required is simply omitted. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
#include "Global.hpp"
|
|
|
|
#include "Lock.hpp"
|
|
#include "Vector.hpp"
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Constants exported from the class. */
|
|
/* */
|
|
/* The stack constants specify the initial size of the stack. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
CONST SBIT32 StackSize = 1024;
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Stacks and stack management. */
|
|
/* */
|
|
/* This class provides general purpose stacks along with some */
|
|
/* basic management. The stacks are optimized for very high */
|
|
/* performance on SMP systems. Whenever possible multiple */
|
|
/* items should added and removed from a stack at the same time. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK=NO_LOCK> class STACK : public LOCK
|
|
{
|
|
//
|
|
// Private data.
|
|
//
|
|
SBIT32 MaxSize;
|
|
SBIT32 Top;
|
|
|
|
VECTOR<TYPE> Stack;
|
|
|
|
public:
|
|
//
|
|
// Public functions.
|
|
//
|
|
STACK( SBIT32 NewMaxSize = StackSize );
|
|
|
|
BOOLEAN MultiplePopStack
|
|
(
|
|
SBIT32 Requested,
|
|
TYPE Data[],
|
|
SBIT32 *Size
|
|
);
|
|
|
|
BOOLEAN MultiplePopStackReversed
|
|
(
|
|
SBIT32 Requested,
|
|
TYPE Data[],
|
|
SBIT32 *Size
|
|
);
|
|
|
|
VOID MultiplePushStack
|
|
(
|
|
CONST TYPE Data[],
|
|
CONST SBIT32 Size
|
|
);
|
|
|
|
VOID MultiplePushStackReversed
|
|
(
|
|
CONST TYPE Data[],
|
|
CONST SBIT32 Size
|
|
);
|
|
|
|
BOOLEAN PeekStack( TYPE *Data );
|
|
|
|
BOOLEAN PopStack( TYPE *Data );
|
|
|
|
VOID PushStack( CONST TYPE & Data );
|
|
|
|
BOOLEAN ReadStack( SBIT32 Index, TYPE *Data );
|
|
|
|
VOID ReverseStack( VOID );
|
|
|
|
BOOLEAN UpdateStack
|
|
(
|
|
CONST SBIT32 Index,
|
|
CONST TYPE & Data
|
|
);
|
|
|
|
~STACK( VOID );
|
|
|
|
//
|
|
// Public inline functions.
|
|
//
|
|
INLINE SBIT32 SizeOfStack( VOID )
|
|
{ return Top; }
|
|
|
|
private:
|
|
//
|
|
// Disabled operations.
|
|
//
|
|
STACK( CONST STACK & Copy );
|
|
|
|
VOID operator=( CONST STACK & Copy );
|
|
};
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Class constructor. */
|
|
/* */
|
|
/* Create a new stack and prepare it for use. This call is */
|
|
/* not thread safe and should only be made in a single thread */
|
|
/* environment. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> STACK<TYPE,LOCK>::STACK( SBIT32 NewMaxSize ) :
|
|
//
|
|
// Call the constructors for the contained classes.
|
|
//
|
|
Stack( NewMaxSize,1,CacheLineSize )
|
|
{
|
|
#ifdef DEBUGGING
|
|
if ( NewMaxSize > 0 )
|
|
{
|
|
#endif
|
|
MaxSize = NewMaxSize;
|
|
Top = 0;
|
|
#ifdef DEBUGGING
|
|
}
|
|
else
|
|
{ Failure( "Size in constructor for STACK" ); }
|
|
#endif
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Remove multiple items from a stack. */
|
|
/* */
|
|
/* We remove multiple items from a stack and check to make sure */
|
|
/* that the stack is not empty. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::MultiplePopStack
|
|
(
|
|
SBIT32 Requested,
|
|
TYPE Data[],
|
|
SBIT32 *Size
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack is not empty return the
|
|
// top elements.
|
|
if ( Top > 0 )
|
|
{
|
|
REGISTER SBIT32 Count;
|
|
|
|
(*Size) = (Top >= Requested) ? Requested : Top;
|
|
|
|
for ( Count = ((*Size) - 1);Count >= 0;Count -- )
|
|
{ Data[ Count ] = Stack[ -- Top ]; }
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Remove multiple items from a stack in reverse order. */
|
|
/* */
|
|
/* We remove multiple items from a stack in reverse order and */
|
|
/* check to make sure that the stack is not empty. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::MultiplePopStackReversed
|
|
(
|
|
SBIT32 Requested,
|
|
TYPE Data[],
|
|
SBIT32 *Size
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack is not empty return the
|
|
// top elements.
|
|
if ( Top > 0 )
|
|
{
|
|
REGISTER SBIT32 Count;
|
|
|
|
(*Size) = (Top >= Requested) ? Requested : Top;
|
|
|
|
for ( Count = 0;Count < (*Size);Count ++ )
|
|
{ Data[ Count ] = Stack[ -- Top ]; }
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Add multiple items to a stack. */
|
|
/* */
|
|
/* We add multiple items to a stack and check to make sure that */
|
|
/* the stack has not overflowed. If the stack has overflowed */
|
|
/* we double its size. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> VOID STACK<TYPE,LOCK>::MultiplePushStack
|
|
(
|
|
CONST TYPE Data[],
|
|
CONST SBIT32 Size
|
|
)
|
|
{
|
|
REGISTER SBIT32 Count;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack will overflow then expand it.
|
|
//
|
|
while ( (Top + Size) >= MaxSize )
|
|
{ Stack.Resize( (MaxSize *= ExpandStore) ); }
|
|
|
|
//
|
|
// Push the new elements.
|
|
//
|
|
for ( Count = 0;Count < Size;Count ++ )
|
|
{ Stack[ Top ++ ] = Data[ Count ]; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Add multiple items to a stack in reverse order. */
|
|
/* */
|
|
/* We add multiple items to a stack in reverse order and check */
|
|
/* to make sure that the stack has not overflowed. If the stack */
|
|
/* has overflowed we double its size. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> VOID STACK<TYPE,LOCK>::MultiplePushStackReversed
|
|
(
|
|
CONST TYPE Data[],
|
|
CONST SBIT32 Size
|
|
)
|
|
{
|
|
REGISTER SBIT32 Count;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack will overflow then expand it.
|
|
//
|
|
while ( (Top + Size) >= MaxSize )
|
|
{ Stack.Resize( (MaxSize *= ExpandStore) ); }
|
|
|
|
//
|
|
// Push the new elements in reverse order.
|
|
//
|
|
for ( Count = (Size-1);Count >= 0;Count -- )
|
|
{ Stack[ Top ++ ] = Data[ Count ]; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Peek at the top of stack. */
|
|
/* */
|
|
/* We return the top of stack with a pop but check to make sure */
|
|
/* that the stack is not empty. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::PeekStack
|
|
(
|
|
TYPE *Data
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an shared lock (if enabled).
|
|
//
|
|
ClaimSharedLock();
|
|
|
|
//
|
|
// If the stack is not empty return a copy
|
|
// of the top element.
|
|
//
|
|
if ( Top > 0 )
|
|
{
|
|
(*Data) = Stack[ (Top - 1) ];
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseSharedLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Remove a single item from a stack. */
|
|
/* */
|
|
/* We remove a single item from a stack and check to make sure */
|
|
/* that the stack is not empty. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::PopStack
|
|
(
|
|
TYPE *Data
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack is not empty return the
|
|
// top element.
|
|
//
|
|
if ( Top > 0 )
|
|
{
|
|
(*Data) = Stack[ -- Top ];
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Add a single item to a stack. */
|
|
/* */
|
|
/* We add a single item to a stack and check to make sure that */
|
|
/* the stack has not overflowed. If the stack has overflowed */
|
|
/* we double its size. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> VOID STACK<TYPE,LOCK>::PushStack
|
|
(
|
|
CONST TYPE & Data
|
|
)
|
|
{
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the stack is full then expand it.
|
|
//
|
|
while ( Top >= MaxSize )
|
|
{ Stack.Resize( (MaxSize *= ExpandStore) ); }
|
|
|
|
//
|
|
// Push a new element.
|
|
//
|
|
Stack[ Top ++ ] = Data;
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Read a stack value. */
|
|
/* */
|
|
/* We return a single item from the stack but check to make */
|
|
/* sure that it exists. . */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::ReadStack
|
|
(
|
|
SBIT32 Index,
|
|
TYPE *Data
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an shared lock (if enabled).
|
|
//
|
|
ClaimSharedLock();
|
|
|
|
//
|
|
// If the element exists then return a copy of
|
|
// it to the caller.
|
|
//
|
|
if ( Index < Top )
|
|
{
|
|
(*Data) = Stack[ Index ];
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseSharedLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Reverse the stack. */
|
|
/* */
|
|
/* We reverse the order of the stack to make effectively */
|
|
/* make it a queue. . */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> VOID STACK<TYPE,LOCK>::ReverseStack( VOID )
|
|
{
|
|
REGISTER SBIT32 Count;
|
|
REGISTER SBIT32 MidPoint = (Top / 2);
|
|
|
|
//
|
|
// Claim an exclusive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// Swap all elements around the mid point.
|
|
//
|
|
for ( Count=0;Count < MidPoint;Count ++ )
|
|
{
|
|
REGISTER TYPE *Low = & Stack[ Count ];
|
|
REGISTER TYPE *High = & Stack[ (Top - Count - 1) ];
|
|
REGISTER TYPE Temp = (*Low);
|
|
|
|
(*Low) = (*High);
|
|
(*High) = Temp;
|
|
}
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Update a stack value. */
|
|
/* */
|
|
/* We update a single item on the stack but check to make */
|
|
/* sure that it exists. . */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> BOOLEAN STACK<TYPE,LOCK>::UpdateStack
|
|
(
|
|
CONST SBIT32 Index,
|
|
CONST TYPE & Data
|
|
)
|
|
{
|
|
REGISTER BOOLEAN Result;
|
|
|
|
//
|
|
// Claim an exclisive lock (if enabled).
|
|
//
|
|
ClaimExclusiveLock();
|
|
|
|
//
|
|
// If the element exists then update it.
|
|
//
|
|
if ( Index < Top )
|
|
{
|
|
Stack[ Index ] = Data;
|
|
|
|
Result = True;
|
|
}
|
|
else
|
|
{ Result = False; }
|
|
|
|
//
|
|
// Release any lock we claimed earlier.
|
|
//
|
|
ReleaseExclusiveLock();
|
|
|
|
return Result;
|
|
}
|
|
|
|
/********************************************************************/
|
|
/* */
|
|
/* Class destructor. */
|
|
/* */
|
|
/* Destory the stack. This call is not thread safe and should */
|
|
/* only be made in a single thread environment. */
|
|
/* */
|
|
/********************************************************************/
|
|
|
|
template <class TYPE,class LOCK> STACK<TYPE,LOCK>::~STACK( VOID )
|
|
{ /* void */ }
|
|
#endif
|