4ac9e4f44d
git-svn-id: svn://svn.code.sf.net/p/loki-lib/code/trunk@1116 7ec92016-0320-0410-acc4-a06ded1c099a
368 lines
9.4 KiB
C++
368 lines
9.4 KiB
C++
////////////////////////////////////////////////////////////////////////////////
|
|
// The Loki Library
|
|
// Copyright (c) 2001 by Andrei Alexandrescu
|
|
// Copyright (c) 2006 Richard Sposato
|
|
// This code accompanies the book:
|
|
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design
|
|
// Patterns Applied". Copyright (c) 2001. Addison-Wesley.
|
|
// Code covered by the MIT License
|
|
//
|
|
// Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
// of this software and associated documentation files (the "Software"), to deal
|
|
// in the Software without restriction, including without limitation the rights
|
|
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
// copies of the Software, and to permit persons to whom the Software is
|
|
// furnished to do so, subject to the following conditions:
|
|
//
|
|
// The above copyright notice and this permission notice shall be included in
|
|
// all copies or substantial portions of the Software.
|
|
//
|
|
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
|
// SOFTWARE.
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
|
|
// $Id$
|
|
|
|
|
|
#include <loki/SmartPtr.h>
|
|
|
|
#include <cassert>
|
|
|
|
#include <stdexcept>
|
|
#include <string>
|
|
|
|
//#define DO_EXTRA_LOKI_TESTS
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
#include <iostream>
|
|
#endif
|
|
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
namespace Loki
|
|
{
|
|
|
|
namespace Private
|
|
{
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
void DeleteArrayBase::Swap( DeleteArrayBase & rhs )
|
|
{
|
|
assert( NULL != this );
|
|
|
|
const size_t temp = m_itemCount;
|
|
m_itemCount = rhs.m_itemCount;
|
|
rhs.m_itemCount = temp;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
void DeleteArrayBase::OnInit( const void * p ) const
|
|
{
|
|
assert( NULL != this );
|
|
if ( NULL == p )
|
|
{
|
|
assert( 0 == m_itemCount );
|
|
}
|
|
else
|
|
{
|
|
assert( 0 < m_itemCount );
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
void DeleteArrayBase::OnCheckRange( size_t index ) const
|
|
{
|
|
assert( NULL != this );
|
|
|
|
if ( index < m_itemCount )
|
|
return;
|
|
|
|
const ::std::string message( "index out of range in ::Loki::DeleteArrayBase::OnCheckRange" );
|
|
throw ::std::out_of_range( message );
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
RefLinkedBase::RefLinkedBase( const RefLinkedBase & rhs ) :
|
|
prev_( &rhs ),
|
|
next_( rhs.next_ )
|
|
{
|
|
prev_->next_ = this;
|
|
next_->prev_ = this;
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
assert( prev_->HasPrevNode( this ) );
|
|
assert( next_->HasNextNode( this ) );
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
#endif
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
bool RefLinkedBase::Release()
|
|
{
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
assert( prev_->HasPrevNode( this ) );
|
|
assert( next_->HasNextNode( this ) );
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
#endif
|
|
|
|
if ( NULL == next_ )
|
|
{
|
|
assert( NULL == prev_ );
|
|
// Return false so it does not try to destroy shared object
|
|
// more than once.
|
|
return false;
|
|
}
|
|
else if (next_ == this)
|
|
{
|
|
assert(prev_ == this);
|
|
// Set these to NULL to prevent re-entrancy.
|
|
prev_ = NULL;
|
|
next_ = NULL;
|
|
return true;
|
|
}
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
assert( this != prev_ );
|
|
assert( NULL != prev_ );
|
|
assert( prev_->HasPrevNode( this ) );
|
|
assert( next_->HasNextNode( this ) );
|
|
#endif
|
|
|
|
prev_->next_ = next_;
|
|
next_->prev_ = prev_;
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
next_ = this;
|
|
prev_ = this;
|
|
assert( 1 == CountNextCycle( this ) );
|
|
assert( 1 == CountPrevCycle( this ) );
|
|
#endif
|
|
|
|
return false;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
void RefLinkedBase::Swap(RefLinkedBase& rhs)
|
|
{
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
assert( prev_->HasPrevNode( this ) );
|
|
assert( next_->HasNextNode( this ) );
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
#endif
|
|
|
|
if (next_ == this)
|
|
{
|
|
assert(prev_ == this);
|
|
if (rhs.next_ == &rhs)
|
|
{
|
|
assert(rhs.prev_ == &rhs);
|
|
// both lists are empty, nothing 2 do
|
|
return;
|
|
}
|
|
prev_ = rhs.prev_;
|
|
next_ = rhs.next_;
|
|
prev_->next_ = next_->prev_ = this;
|
|
rhs.next_ = rhs.prev_ = &rhs;
|
|
return;
|
|
}
|
|
if (rhs.next_ == &rhs)
|
|
{
|
|
rhs.Swap(*this);
|
|
return;
|
|
}
|
|
if (next_ == &rhs ) // rhs is next neighbour
|
|
{
|
|
if ( prev_ == &rhs )
|
|
return; // cycle of 2 pointers - no need to swap.
|
|
std::swap(prev_, next_);
|
|
std::swap(rhs.prev_, rhs.next_);
|
|
std::swap(rhs.prev_, next_);
|
|
std::swap(rhs.prev_->next_,next_->prev_);
|
|
}
|
|
else if ( prev_ == &rhs ) // rhs is prev neighbor
|
|
{
|
|
if ( next_ == &rhs )
|
|
return; // cycle of 2 pointers - no need to swap.
|
|
std::swap( prev_, next_ );
|
|
std::swap( rhs.next_, rhs.prev_ );
|
|
std::swap( rhs.next_, prev_ );
|
|
std::swap( rhs.next_->prev_, prev_->next_ );
|
|
}
|
|
else // not neighhbors
|
|
{
|
|
std::swap(prev_, rhs.prev_);
|
|
std::swap(next_, rhs.next_);
|
|
std::swap(prev_->next_, rhs.prev_->next_);
|
|
std::swap(next_->prev_, rhs.next_->prev_);
|
|
}
|
|
|
|
#ifdef DO_EXTRA_LOKI_TESTS
|
|
assert( next_ == this ? prev_ == this : prev_ != this);
|
|
assert( prev_ == this ? next_ == this : next_ != this);
|
|
assert( prev_->HasPrevNode( this ) );
|
|
assert( next_->HasNextNode( this ) );
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
assert( rhs.prev_->HasPrevNode( &rhs ) );
|
|
assert( rhs.next_->HasNextNode( &rhs ) );
|
|
assert( CountPrevCycle( &rhs ) == CountNextCycle( &rhs ) );
|
|
#endif
|
|
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
unsigned int RefLinkedBase::CountPrevCycle( const RefLinkedBase * pThis )
|
|
{
|
|
if ( NULL == pThis )
|
|
return 0;
|
|
const RefLinkedBase * p = pThis->prev_;
|
|
if ( NULL == p )
|
|
return 0;
|
|
if ( pThis == p )
|
|
return 1;
|
|
|
|
unsigned int count = 1;
|
|
do
|
|
{
|
|
p = p->prev_;
|
|
++count;
|
|
} while ( p != pThis );
|
|
|
|
return count;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
unsigned int RefLinkedBase::CountNextCycle( const RefLinkedBase * pThis )
|
|
{
|
|
if ( NULL == pThis )
|
|
return 0;
|
|
const RefLinkedBase * p = pThis->next_;
|
|
if ( NULL == p )
|
|
return 0;
|
|
if ( pThis == p )
|
|
return 1;
|
|
|
|
unsigned int count = 1;
|
|
while ( p != pThis )
|
|
{
|
|
p = p->next_;
|
|
++count;
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
bool RefLinkedBase::HasPrevNode( const RefLinkedBase * p ) const
|
|
{
|
|
if ( this == p )
|
|
return true;
|
|
const RefLinkedBase * prev = prev_;
|
|
if ( NULL == prev )
|
|
return false;
|
|
while ( prev != this )
|
|
{
|
|
if ( p == prev )
|
|
return true;
|
|
prev = prev->prev_;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
bool RefLinkedBase::HasNextNode( const RefLinkedBase * p ) const
|
|
{
|
|
if ( this == p )
|
|
return true;
|
|
const RefLinkedBase * next = next_;
|
|
if ( NULL == next )
|
|
return false;
|
|
while ( next != this )
|
|
{
|
|
if ( p == next )
|
|
return true;
|
|
next = next->next_;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
bool RefLinkedBase::Merge( RefLinkedBase & rhs )
|
|
{
|
|
|
|
if ( NULL == next_ )
|
|
{
|
|
assert( NULL == prev_ );
|
|
return false;
|
|
}
|
|
RefLinkedBase * prhs = &rhs;
|
|
if ( prhs == this )
|
|
return true;
|
|
if ( NULL == prhs->next_ )
|
|
{
|
|
assert( NULL == prhs->prev_ );
|
|
return true;
|
|
}
|
|
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
assert( CountPrevCycle( prhs ) == CountNextCycle( prhs ) );
|
|
// If rhs node is already in this cycle, then no need to merge.
|
|
if ( HasPrevNode( &rhs ) )
|
|
{
|
|
assert( HasNextNode( &rhs ) );
|
|
return true;
|
|
}
|
|
|
|
if ( prhs == prhs->next_ )
|
|
{
|
|
/// rhs is in a cycle with 1 node.
|
|
assert( prhs->prev_ == prhs );
|
|
prhs->prev_ = prev_;
|
|
prhs->next_ = this;
|
|
prev_->next_ = prhs;
|
|
prev_ = prhs;
|
|
}
|
|
else if ( this == next_ )
|
|
{
|
|
/// this is in a cycle with 1 node.
|
|
assert( prev_ == this );
|
|
prev_ = prhs->prev_;
|
|
next_ = prhs;
|
|
prhs->prev_->next_ = this;
|
|
prhs->prev_ = this;
|
|
}
|
|
else
|
|
{
|
|
next_->prev_ = prhs->prev_;
|
|
prhs->prev_->next_ = prev_;
|
|
next_ = prhs;
|
|
prhs->prev_ = this;
|
|
}
|
|
|
|
assert( CountPrevCycle( this ) == CountNextCycle( this ) );
|
|
return true;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
} // end namespace Private
|
|
|
|
} // end namespace Loki
|
|
|