SaraP
391 lines
16 KiB
C++
391 lines
16 KiB
C++
////////////////////////////////////////////////////////////////////////////////
|
|
/**
|
|
\file
|
|
\brief \ru Очередь объектов, которые не имеют деструкторов.
|
|
\en Queue of objects without destructors. \~
|
|
|
|
*/
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
|
|
|
|
#ifndef __TEMPL_S_QUEUE_H
|
|
#define __TEMPL_S_QUEUE_H
|
|
|
|
|
|
#include <io_define.h>
|
|
#include <tool_quick_sort.h>
|
|
#include <tool_err_handling.h>
|
|
#include <string.h>
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
/** \brief \ru Очередь объектов, которые не имеют деструкторов.
|
|
\en Queue of objects without destructors. \~
|
|
\details \ru Очередь объектов, которые не имеют деструкторов. \n
|
|
|
|
Требования к объектам очереди такие же, как в SArray<Type>.
|
|
\en Queue of objects without destructors. \n
|
|
|
|
Requirement for the objects are the same as in SArray<Type>. \~
|
|
\attention \ru В целях эффективности контейнера проверки обращения к запредельной
|
|
памяти реализованы только под откладкой
|
|
\en In order to efficiency of the container validation - the usage of prohibitive
|
|
memory are implemented only for debug version \~
|
|
\par \ru Рекомендации по использованию
|
|
Если предполагается фиксированный (известный) наибольший размер очереди, то
|
|
рекомендуется использовать функцию SQueue<class Type>::Push() для добавления
|
|
объекта. Если предельный размер очереди не известен, то следует применять метод
|
|
SQueue<class Type>::PushAlloc(), который при добавлении "наращивает" память
|
|
по мере необходимости.
|
|
\en Usage recommendations
|
|
If the fixed (known) maximum size of queue is assumed then
|
|
it is recommended to use the function SQueue<class Type>::Push() to add
|
|
an object. If the limit size of queue is unknown then there should be applied the method
|
|
SQueue<class Type>::PushAlloc() which builds up the memory
|
|
as necessary. \~
|
|
|
|
\par \ru Правило выделения памяти
|
|
Если размера буфера для хранения объектов очереди не достаточно, то выделяется
|
|
новый участок кучи с размеров на SQueue::delta больше. Если SQueue::delta = 1,
|
|
то размер выделенной памяти уведичивается на 12,5% при каждом достижении предела.
|
|
\en The rule of memory allocation
|
|
If the size of the buffer for storage of queue objects is not enough then allocated
|
|
a new part of the heap which has size greater on SQueue::delta. If SQueue::delta = 1,
|
|
then the size of allocated memory is increased by 12,5% each time the limit is reached. \~
|
|
|
|
\ingroup Base_Tools_Containers
|
|
*/
|
|
// ---
|
|
template <class Type>
|
|
class SQueue
|
|
{
|
|
Type * data; ///< \ru Адрес начала выделенной памяти. \en An address of the beginning of the allocated memory.
|
|
Type * qlast; ///< \ru Адрес конца выделенной памяти (последний элемент массива выделенной памяти). \en An address of the end of the allocated memory (the last element of the allocated memory's array)
|
|
Type * qp1; ///< \ru Самый первый извлекаемый (queue pointer 1). \en The first extracted one (queue pointer 1).
|
|
Type * qp2; ///< \ru Следующий элемент от последнего вошедшего (queue pointer 2). \en The next element from the last entering (queue pointer 2).
|
|
|
|
public:
|
|
/// \ru Конструктор. \en Constructor.
|
|
SQueue( size_t capacity = 0 );
|
|
/// \ru Деструктор. \en Destructor.
|
|
virtual ~SQueue();
|
|
public:
|
|
/// \ru Выдать размер выделенной памяти. \en Get the size of the allocated memory.
|
|
size_t Capacity() const { return qlast+1-data; }
|
|
/// \ru Последний элемент очереди. \en The last element of the queue.
|
|
Type & Back();
|
|
/// \ru Последний элемент очереди. \en The last element of the queue.
|
|
const Type & Back() const;
|
|
/// \ru Первый элемент очереди. \en The first element of the queue.
|
|
Type & Front();
|
|
/// \ru Первый элемент очереди. \en The first element of the queue.
|
|
const Type & Front() const;
|
|
/// \ru Свойство пустого множества. \en A property of the empty set.
|
|
bool Empty() const { return qp1 == qp2; }
|
|
/// \ru Свойство исчерпанной памяти. \en An expended memory property.
|
|
bool IsFull() const;
|
|
/// \ru Самый первый, выходящий из очереди (корректно работает только для непустой очереди). \en The very first one outgoing from the queue (it works correctly only for nonempty queue).
|
|
Type & First() const;
|
|
/// \ru Добавить в очередь и нарастить буфер выделенной памяти при необходимости. \en Add to the queue and increase the buffer of the allocated memory if it is necessary.
|
|
void Push( const Type & obj );
|
|
/// \ru Вывести из очереди. \en Move out from queue.
|
|
void Pop();
|
|
/// \ru Вывести из очереди. \en Move out from queue.
|
|
void Pop( Type & obj );
|
|
/// \ru Зарезервировать дополнительную память. \en Reserve an additional memory.
|
|
bool Reserve( size_t );
|
|
/// \ru Очистить очередь. \en Clear the queue.
|
|
void SetEmpty() { qp1 = qp2 = data; }
|
|
/// \ru Выдать размер очереди. \en Get the queue size.
|
|
size_t Size() const;
|
|
|
|
private:
|
|
/// \ru Инкремент указателя с учётом зацикленности памяти. \en An increment of the pointer considering a looped memory.
|
|
Type * _IncPtr( Type * ptr ) const;
|
|
/// \ru Добавить в очередь без проверки израсходованной памяти. \en Add to the queue without check of consumed memory.
|
|
void _Push( const Type & u );
|
|
/// \ru Задать наибольший размер очереди. \en Set the maximum size of the queue.
|
|
bool _NewCapacity( size_t max_len, bool clear );
|
|
};
|
|
|
|
//-------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template <class Type>
|
|
SQueue<Type>::SQueue( size_t capacity )
|
|
: data( nullptr )
|
|
, qlast( nullptr )
|
|
, qp1( nullptr )
|
|
, qp2( nullptr )
|
|
{
|
|
if ( capacity > 0 ) {
|
|
try {
|
|
data = new Type[capacity];
|
|
}
|
|
catch ( const std::bad_alloc & ) {
|
|
data = nullptr;
|
|
throw;
|
|
}
|
|
}
|
|
|
|
qlast = data+capacity-1;
|
|
qp1 = qp2 = data;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template <class Type>
|
|
SQueue<Type>::~SQueue()
|
|
{
|
|
delete [] data;
|
|
|
|
#ifdef C3D_DEBUG
|
|
::memset( &qp1, 0xFE, sizeof(Type *) );
|
|
::memset( &qp2, 0xFE, sizeof(Type *) );
|
|
::memset( &qlast, 0xFE, sizeof(Type *) );
|
|
::memset( &data, 0xFE, sizeof(Type *) );
|
|
#endif // C3D_DEBUG
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Кто крайний? (корректно работает только для непустой очереди); \en Which is the last? (it works correctly only for nonempty queue);
|
|
// ---
|
|
template <class Type>
|
|
inline const Type & SQueue<Type>::Back() const
|
|
{
|
|
PRECONDITION( !Empty() && Capacity() > 0 );
|
|
return qp2 == data ? *qlast : *( qp2 - 1 );
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Кто крайний? (корректно работает только для непустой очереди) \en Which is the last? (it works correctly only for nonempty queue)
|
|
// ---
|
|
template <class Type>
|
|
inline Type & SQueue<Type>::Back()
|
|
{
|
|
PRECONDITION( !Empty() && Capacity() > 0 );
|
|
return qp2 == data ? *qlast : *( qp2 - 1 );
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru Первый элемент очереди. \en The first element of the queue.
|
|
// ---
|
|
template <class Type>
|
|
inline Type & SQueue<Type>::Front()
|
|
{
|
|
PRECONDITION( Capacity() > 0 && !Empty() );
|
|
return *qp1;
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru Первый элемент очереди. \en The first element of the queue.
|
|
// ---
|
|
template <class Type>
|
|
inline const Type & SQueue<Type>::Front() const
|
|
{
|
|
PRECONDITION( Capacity() > 0 && !Empty() );
|
|
return *qp1;
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru Самый первый, выходящий из очереди (корректно работает только для непустой очереди). \en The very first one outgoing from the queue (it works correctly only for nonempty queue).
|
|
// ---
|
|
template <class Type>
|
|
inline Type & SQueue<Type>::First() const
|
|
{
|
|
PRECONDITION( qp1 <= qlast && qp1 >= data && qp1 != qp2 );
|
|
return *qp1;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Свойство полностью исчерпанного буфера \en A expended buffer property.
|
|
/**\ru Фактически свойство отвечает возможно ли добавить в очередь элемент без
|
|
передислокации буфера.
|
|
\en In fact this property answeres whether it is possible to add in a queue an element without
|
|
redeployment of the buffer. \~
|
|
*/
|
|
// ---
|
|
template <class Type>
|
|
inline bool SQueue<Type>::IsFull() const
|
|
{
|
|
return data == nullptr || _IncPtr( qp2 ) == qp1;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Инкремент указателя с учётом зацикленности памяти \en An increment of the pointer considering a looped memory
|
|
//---
|
|
template <class Type>
|
|
inline Type * SQueue<Type>::_IncPtr( Type * ptr ) const
|
|
{
|
|
PRECONDITION( ptr >= data && ptr <= qlast );
|
|
if ( ++ptr > qlast )
|
|
ptr = data;
|
|
return ptr;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template <class Type>
|
|
inline void SQueue<Type>::_Push( const Type & obj )
|
|
{
|
|
PRECONDITION( !IsFull() && Size() < Capacity() );
|
|
if ( !IsFull() && Size() < Capacity() ) {
|
|
memcpy( qp2, &obj, sizeof( Type ) );
|
|
qp2 = _IncPtr( qp2 );
|
|
PRECONDITION( !Empty() ); // \ru после добавления очередь не может быть пустой \en the queue may bacome empty after the adding
|
|
PRECONDITION( qp2 >= data && qp2 <= qlast );
|
|
}
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Добавить в очередь и нарастить буфер выделенной памяти при необходимости \en Add to the queue and increase the buffer of the llocated memory if it is necessary
|
|
/**\ru Тоже, что и #SQueue<Type>::Push, но с перезахватом памяти при исчерпании буфера
|
|
\en The same as #SQueue<Type>::Push, but with memory reallocation in a case when the buffer is full \~
|
|
*/
|
|
// ---
|
|
template <class Type>
|
|
void SQueue<Type>::Push( const Type & obj )
|
|
{
|
|
if ( IsFull() ) // \ru Требуется перезахват памяти \en A memory reallocation is required
|
|
{
|
|
size_t cap = Capacity();
|
|
cap += ::KsAutoDelta( cap );
|
|
if ( !_NewCapacity(cap, false/*clear*/) )
|
|
return;
|
|
}
|
|
_Push( obj );
|
|
|
|
PRECONDITION( qp2 >= data && qp2 <= qlast );
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template <class Type>
|
|
inline void SQueue<Type>::Pop( Type & obj )
|
|
{
|
|
PRECONDITION( qp2 != qp1 ); // \ru перед извлечением очередь не может быть пустой \en the queue can't be empty before the extraction
|
|
if ( qp2 != qp1 ) {
|
|
memcpy( &obj, qp1, sizeof( Type ) );
|
|
qp1 = _IncPtr( qp1 );
|
|
PRECONDITION( qp1 <= qlast && qp1 >= data );
|
|
}
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template <class Type>
|
|
inline void SQueue<Type>::Pop()
|
|
{
|
|
PRECONDITION( qp2 != qp1 ); // \ru перед извлечением очередь не может быть пустой \en the queue can't be empty before the extraction
|
|
if ( qp2 != qp1 ) {
|
|
qp1 = _IncPtr( qp1 );
|
|
PRECONDITION( qp1 <= qlast && qp1 >= data );
|
|
}
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Зарезервировать дополнительную память \en Reserve an additional memory
|
|
// ---
|
|
template <class Type>
|
|
bool SQueue<Type>::Reserve( size_t addCapacity )
|
|
{
|
|
PRECONDITION( addCapacity > 0 );
|
|
const size_t futureSize = Size() + addCapacity; // \ru Предполагаемый размер, растущей очереди \en An assumed size of increasing queue
|
|
if ( Capacity() < futureSize )
|
|
{
|
|
return _NewCapacity( futureSize, false );
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Выдать размер очереди \en Get the queue size
|
|
//---
|
|
template <class Type>
|
|
inline size_t SQueue<Type>::Size() const
|
|
{
|
|
if ( qp2 >= qp1 )
|
|
{
|
|
return qp2 - qp1; // \ru Нефрагментированная очередь \en Not fragmented queue
|
|
}
|
|
return ( qlast + 1 - qp1 ) + ( qp2 - data ); // \ru Сумма длин двух фрагментов очереди \en The lengths sum of two fragments of queue
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
/// \ru Задать наибольший размер очереди \en Set the maximum size of the queue
|
|
// ---
|
|
template <class Type>
|
|
bool SQueue<Type>::_NewCapacity( size_t max_len, bool clear )
|
|
{
|
|
if ( clear || Empty() || max_len == 0 )
|
|
{
|
|
try {
|
|
delete [] data;
|
|
data = qlast = qp1 = qp2 = nullptr;
|
|
if ( max_len > 0 ) {
|
|
data = new Type[max_len];
|
|
qlast = data + max_len - 1;
|
|
qp1 = qp2 = data;
|
|
}
|
|
}
|
|
catch ( ... ) {
|
|
data = qlast = qp1 = qp2 = nullptr;
|
|
C3D_CONTROLED_THROW;
|
|
return false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
PRECONDITION( qp1 != qp2 && max_len>0 && clear == false ); // \ru Выражение обязано быть истинным \en The expression should be true
|
|
Type * n_data = nullptr;
|
|
try {
|
|
n_data = new Type[max_len];
|
|
if ( qp1 < qp2 ) // \ru Вариант без фрагментации \en A variant without fragmentation
|
|
{
|
|
size_t len = std_min( (size_t)/*OV_x64 (uint)*/( qp2 - qp1 ), max_len ); // \ru Количество ячеек с полезной информацией (не байты) \en The number of cells with useful information (not bites)
|
|
PRECONDITION( len <= max_len );
|
|
::memcpy( n_data, qp1, len * sizeof( Type ) );
|
|
delete[] data;
|
|
data = qp1 = qp2 = n_data;
|
|
qp2 += len;
|
|
}
|
|
else if ( qp1 > qp2 ) // \ru Вариант с фрагментированным массивом полезной информации \en A variant with the fragmented array of useful information
|
|
{
|
|
size_t len1 = std_min( (size_t)( qlast - qp1 + 1 ), max_len ); // \ru Количество ячеек первого фрагмента \en The number of cells of the first fragment
|
|
size_t len2 = std_min( (size_t)( qp2 - data ), (size_t)( max_len - len1 ) ); // \ru Количество ячеек второго фрагмента \en The number of cells of the second fragment
|
|
PRECONDITION( len1 + len2 <= max_len );
|
|
::memcpy( n_data, qp1, len1 * sizeof( Type ) );
|
|
::memcpy( n_data + len1, data, len2 * sizeof( Type ) );
|
|
delete[] data;
|
|
data = qp1 = qp2 = n_data;
|
|
qp2 += len1;
|
|
qp2 += len2;
|
|
}
|
|
qlast = data + max_len - 1;
|
|
}
|
|
catch ( ... ) {
|
|
C3D_CONTROLED_THROW;
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
#endif // __TEMPL_S_QUEUE_H
|