[Cppunit-cvs] cppunit2/include/cpptl _stlimpl.h, NONE, 1.1 smallmap.h, NONE, 1.1 forwards.h, 1.6, 1.7

[Baptiste L. <bl...@us...>]

Update of /cvsroot/cppunit/cppunit2/include/cpptl
In directory sc8-pr-cvs4.sourceforge.net:/tmp/cvs-serv20596/include/cpptl

Modified Files:
	forwards.h 
Added Files:
	_stlimpl.h smallmap.h 
Log Message:
* added CppTL:SmallMap, a std::map like container that use a sorted vector to hold item.

--- NEW FILE: _stlimpl.h ---
#ifndef CPPTL__STLIMPL_H_INCLUDED
# define CPPTL__STLIMPL_H_INCLUDED

# include "config.h"
// add include for malloc/free

/*
 Notes: we need to prefix some (all) functions with cpptl_ because some STL implementations
 are bugged:
 namespace A { 
    void copy();

    struct X { 
       X( int x ) : x_( x ) {} 
       int x_; 
    };
 }
 std::vector<X> a;   // failed to compile because std::vector template find A::copy()
                     // with ADL instead of std::copy().
 */



// Make exception related code optional
# ifndef CPPTL_NO_EXCEPTION_SUPPORT
#  define CPPTL_TRY_BEGIN
#  define CPPTL_TRY_END_CLEANUP( expression )
# else
#  define CPPTL_TRY_BEGIN try
#  define CPPTL_TRY_END_CLEANUP( expression ) catch ( ... ) { expression; throw; }
# endif


namespace CppTL { namespace Impl {

// iterator stuffs

   template<class T>
   struct ConstIteratorTraits
   {
      typedef T &reference;
      typedef T *pointer;
   };

   template<class T>
   struct NonConstIteratorTraits
   {
      typedef T &reference;
      typedef T *pointer;
   };

// algorithm for use when implementing containers
// algorithms

template<class T>
inline void construct( T &object, const T &value )
{
   new (&object) T(value);
}

template<class T>
inline void destruct( T &object )
{
   object.~T();
}

template<class T,class OutputIt>
inline void destruct_range( OutputIt first, OutputIt last )
{
   for ( ; first != last; ++first )
      ::CppTL::Impl::destruct( *first );
}

template<class InputIt,class OutputIt>
void
cpptl_copy( InputIt first, InputIt last, OutputIt firstDestIt )
{
   for ( ; first != last; ++first, ++firstDestIt )
      *first = *firstDestIt;
}

template<class InputIt,class OutputIt>
void
copy_backwards( InputIt first, InputIt last, OutputIt endDestIt )
{
   if ( first != last )
   {
      do
      {
         --last;
         --endDestIt;
         *endDestIt = *last;
      }
      while ( first != last );
   }
}

template<class InputIt,class OutputIt>
void
copy_with_construct( InputIt first, InputIt last, OutputIt firstDestIt )
{
   for ( ; first != last; ++first, ++firstDestIt )
   {
      CPPTL_TYPENAME InputIt::reference old = *first;
      ::CppTL::Impl::construct(*firstDestIt, *first );
   }
}

template<class OutputIt, class ValueType>
void
copy_with_construct_value( OutputIt firstDestIt, unsigned int count, const ValueType &value )
{
   while ( count-- >= 0 )
   {
      new (*firstDestIt)( value );
      ++firstDestIt;
   }
}


template<class InputIt,class OutputIt>
void
copy_and_destroy( InputIt first, InputIt last, OutputIt firstDestIt )
{
   for ( ; first != last; ++first, ++firstDestIt )
   {
      CPPTL_TYPENAME InputIt::reference old = *first;
      ::CppTL::Impl::construct(*firstDestIt, old );
      ::CppTL::Impl::destruct( old );
   }
}

template<class InputIt,class OutputIt>
void
copy_backwards_and_destroy( InputIt first, InputIt last, OutputIt endDestIt )
{
   if ( first != last )
   {
      do
      {
         --last;
         --endDestIt;
         CPPTL_TYPENAME InputIt::reference old = *last;
         ::CppTL::Impl::construct( *endDestIt, old );
         ::CppTL::Impl::destruct( old );
      }
      while ( first != last );
   }
}


} } // namespace CppTL { namespace Impl {



namespace CppTL { 

// Common predicates
template<class T>
struct LessPred
{
   bool operator()( const T &a, const T &b ) const
   {
      return a < b;
   }
};

// Pair
template<class A, class B>
class Pair
{
public:
   typedef A first_type;
   typedef B second_type;

   Pair()
   {
   }

   Pair( const first_type &a, const second_type &b )
      : first( a )
      , second( b )
   {
   }

   first_type first;
   second_type second;
};


// Common allocators

template<class T>
class MallocAllocator
{
public:
   typedef unsigned int size_t;

   T *allocate()
   {
      return static_cast<T*>( malloc( sizeof(T) ) );
   }

   void release( T *object )
   {
      free( object );
   }

   T *allocateArray( size_t count )
   {
      return static_cast<T*>( malloc( sizeof(T) * count ) );
   }

   void releaseArray( T *array, size_t allocatedSize )
   {
      free( array );
   }

   void swap( MallocAllocator &other )
   {
   }
};


} // namespace CppTL


#endif // CPPTL__STLIMPL_H_INCLUDED

--- NEW FILE: smallmap.h ---
#ifndef CPPTL_VECTOR_H_INCLUDED
# define CPPTL_VECTOR_H_INCLUDED

# include "_stlimpl.h"

// Notes: exception handling is bugged:
// In case where an exception is thrown by a copy constructor while copying a range,
// All destructors are not called correctly.


namespace CppTL {

template<class Item>
class SmallMapBase
{
public:
   typedef unsigned int size_t;

   SmallMapBase()
      : data_( 0 )
      , size_( 0 )
      , capacity_( 0 )
   {
   }

   SmallMapBase( Item *data, size_t size, size_t capacity )
      : data_( data )
      , size_( size )
      , capacity_( capacity )
   {
   }

   Item *data_;
   size_t size_;
   size_t capacity_;
};


template<class T>
class SmallMapIteratorBase
{
public:
   typedef unsigned int size_t;
   typedef int difference_type;
   typedef SmallMapIteratorBase<T> SelfType;
   typedef T Item;

   size_t index() const
   {
      CPPTL_ASSERT_MESSAGE( map_ != 0, "SmallMapIterator::index(): invalid iterator" );
      return current_ - map_->data_;
   }

   bool operator ==( const SelfType &other ) const
   {
      return isEqual( other );
   }

   bool operator !=( const SelfType &other ) const
   {
      return !isEqual( other );
   }

   bool operator <( const SelfType &other ) const
   {
      return isLess( other );
   }

   bool operator <=( const SelfType &other ) const
   {
      return !other.isLess( *this );
   }

   bool operator >=( const SelfType &other ) const
   {
      return !isLess( other );
   }

   bool operator >( const SelfType &other ) const
   {
      return other.isLess( *this );
   }

protected:
   SmallMapIteratorBase()
      : map_( 0 )
      , current_( 0 )
   {
   }

   SmallMapIteratorBase( const SmallMapBase<Item> &map,
                         Item *current )
      : map_( &map )
      , current_( current )
   {
   }


   T &deref() const
   {
      CPPTL_ASSERT_MESSAGE( current_ != 0,
                            "SmallMapIterator: dereferencing invalid iterator" );
      return *current_;
   }

   void increment()
   {
      CPPTL_ASSERT_MESSAGE( map_  &&  ( current_ < map_->data_ + map_->size_ ), 
                           "SmallMapIterator::increment: incrementing beyond end" );
      ++current_;
   }

   void decrement()
   {
      CPPTL_ASSERT_MESSAGE( map_  &&  ( current_ > map_->data_ ), 
                           "SmallMapIterator::decrement: decrementing beyond beginning" );
      --current_;
   }

   void advance( difference_type n )
   {
      CPPTL_ASSERT_MESSAGE( map_  &&  map_->size_  &&
                           ( current_+n < map_->data_ + map_->size_  &&  current+n >= map_->data_), 
                           "SmallMapIterator::advance: advancing beyond end or beginning" );
      current_ += n;
   }

   difference_type computeDistance( const SelfType &other ) const
   {
      CPPTL_ASSERT_MESSAGE( map_->data_ == other.map_->data_, "Comparing iterator on different container." );
      return current_ - other.current_;
   }

   bool isEqual( const SmallMapIteratorBase &other ) const
   {
      return current_ == other.current_;
   }

   bool isLess( const SmallMapIteratorBase &other ) const
   {
      return current_ < other.current_;
   }

protected:
   const SmallMapBase<Item> *map_;
   Item *current_;
};




template<class T, class Traits>
class SmallMapIterator : public SmallMapIteratorBase<T>
{
public:
   typedef unsigned int size_t;
   typedef int difference_type;
   typedef T value_type;
   typedef CPPTL_TYPENAME Traits::reference reference;
   typedef CPPTL_TYPENAME Traits::pointer pointer;

   typedef SmallMapIterator<T,Traits> SelfType;
   typedef SmallMapIteratorBase<T> SuperClass;
   typedef SmallMapIterator< T, ::CppTL::Impl::NonConstIteratorTraits<T> > NonConstSmallMapIterator;

   SmallMapIterator()
   {
   }

   // This constructor ensure that it is possible to construct a
   // const iterator from a non const iterator.
   SmallMapIterator( const NonConstSmallMapIterator &other )
      : SuperClass( other )
   {
   }

   SmallMapIterator( const SmallMapBase<Item> &map, Item *current )
      : SuperClass( map, current )
   {
   }

   SmallMapIterator( const SmallMapBase<Item> &map, size_t currentIndex )
      : SuperClass( map, map.data_ + currentIndex )
   {
   }

   SelfType &operator++()
   {
      increment();
      return *this;
   }

   SelfType operator++( int )
   {
      SelfType temp( *this );
      ++*this;
      return temp;
   }

   SelfType &operator--()
   {
      decrement();
      return *this;
   }

   SelfType operator--( int )
   {
      SelfType temp( *this );
      --*this;
      return temp;
   }

   SelfType &operator +=( difference_type n )
   {
      advance( n );
      return *this;
   }

   SelfType operator +( difference_type n ) const
   {
      SelfType temp( *this );
      return temp += n;
   }

   SelfType &operator -=( difference_type n )
   {
      advance( -n );
      return *this;
   }

   SelfType operator -( difference_type n ) const
   {
      SelfType temp( *this );
      return temp -= n;
   }

   reference operator[]( difference_type n ) const
   {
      return *( *this + n );
   }

   reference operator *() const
   {
      return deref();
   }

   pointer operator->() const
   {
      return &deref();
   }

   difference_type operator -( const SelfType &other ) const
   {
      return computeDistance( other );
   }
};



/// Store elements in a sorted vector.
template< class Key
        , class Value
        , class PredLess = CppTL::LessPred<Key>
        , class Allocator = CppTL::MallocAllocator< Pair<Key,Value> > >
class SmallMap : private SmallMapBase< Pair<Key,Value> >
{
public:
   typedef Pair<Key,Value> Item;

   typedef Item value_type;
   typedef Key key_type;
   typedef Value mapped_type;
   typedef SmallMapIterator<Item, ::CppTL::Impl::NonConstIteratorTraits<Item> > iterator;
   typedef SmallMapIterator<Item, ::CppTL::Impl::ConstIteratorTraits<Item> > const_iterator;
   typedef SmallMap<Key, Value, PredLess, Allocator> SelfType;
   typedef SmallMapBase< Pair<Key,Value> > SuperClass;

   SmallMap()
   {
   }

   SmallMap( const SmallMap &other )
      : SuperClass( 0, other.size_, other.size_ )
      , allocator_( other.allocator_ )
   {
      data_ = allocator_.allocateArray( size_ );
      CPPTL_TRY_BEGIN
      {
         ::CppTL::Impl::copy_with_construct( other.begin(), other.end(), data_ );
      }
      CPPTL_TRY_END_CLEANUP( allocator.releaseArray( data_, size_ ) )
   }

   ~SmallMap()
   {
   }

   SelfType &operator =( const SmallMap &other )
   {
      SelfType temp( other );
      swap( temp );
      return *this;
   }

   size_t size() const
   {
      return size_;
   }

   const_iterator find( const Key &key ) const
   {
      Item *found = lookUp( key );
      if ( found )
         return const_iterator( *this, found );
      return end();
   }

   iterator find( const Key &key )
   {
      Item *found = lookUp( key );
      if ( found )
         return iterator( *this, found );
      return end();
   }

   iterator lower_bound( const Key &key )
   {
      size_t index = insertionIndex( key, 0 );
      return iterator( *this, index );
   }

   iterator upper_bound( const Key &key )
   {
      size_t index = insertionIndex( key, 0 );
      return iterator( *this, index );
   }

   Pair<iterator,iterator> equal_range( const Key &key )
   {
      size_t index = insertionIndex( key, 0 );
      iterator it( *this, index );
      return Pair<iterator,iterator>( it, it );
   }

   const_iterator lower_bound( const Key &key ) const
   {
      size_t index = insertionIndex( key, 0 );
      return const_iterator( *this, index );
   }

   const_iterator upper_bound( const Key &key ) const
   {
      size_t index = insertionIndex( key, 0 );
      return const_iterator( *this, index );
   }

   Pair<const_iterator,const_iterator> equal_range( const Key &key ) const
   {
      size_t index = insertionIndex( key, 0 );
      const_iterator it( *this, index );
      return Pair<const_iterator,const_iterator>( it, it );
   }

   void clear()
   {
      SelfType temp;
      swap( temp );
   }

   iterator begin()
   {
      return iterator( *this, data_ );
   }

   iterator end()
   {
      return iterator( *this, size_ );
   }

   const_iterator begin() const
   {
      return const_iterator( *this, data_ );
   }

   const_iterator end() const
   {
      return const_iterator( *this, size_ );
   }

   size_t count( const Key &key ) const
   {
      return lookUp( key) ? 1 : 0;
   }

   bool empty() const
   {
      return size_ == 0;
   }

   // equal_range

   iterator erase( iterator where )
   {
      CPPTL_ASSERT_MESSAGE( where >= begin()  &&  where < end(), "SmallMap<T>::erase(): invalid iterator" );
      ::CppTL::Impl::copy_and_destroy( where+1, end(), where );
      --size_;
      return where;
   }

   iterator erase( iterator first, iterator last )
   {
      size_t whereIndex = first.index();
      size_t count = last - first;
      ::CppTL::Impl::copy_and_destroy( last, end(), first );
      size_ -= count;
      return iterator( *this, whereIndex );
   }

   iterator erase( const Key &key )
   {
      Item *found = lookUp( key );
      if ( found )
         return erase( iterator( *this, found ) );
      return end();
   }

   Value &operator[]( const Key &key )
   {
      typedef Pair<iterator,bool> ResultType;
      size_t whereIndex = insertionIndex( key, 0 );
      if ( whereIndex < size_
           &&  !less_( key, data_[whereIndex].first ) )
      {
         return data_[whereIndex].second;
      }
      return doInsert( whereIndex, Item( key, Value() ) )->second;
   }

   Pair<iterator,bool> insert( const Item &item )
   {
      typedef Pair<iterator,bool> ResultType;
      size_t whereIndex = insertionIndex( item.first, 0 );
      if ( whereIndex < size_
           &&  !less_( item.first, data_[whereIndex].first ) )
      {
         return ResultType( iterator( *this, whereIndex ), false );
      }
      return ResultType( doInsert( whereIndex, item ), true );
   }

   iterator insert( iterator where, const Item &item )
   {
      size_t whereIndex = insertionIndex( item.first, where.index() );
      if ( size_ == capacity_ )
      {
         if ( reserve( 1, whereIndex, &item ) )  // element was inserted when increasing capacity.
            return iterator( *this, whereIndex );
      }
      ++size_;
      iterator itWhere( *this, whereIndex );
      ::CppTL::Impl::copy_backwards_and_destroy( itWhere, end()-1, end() );
      ::CppTL::Impl::construct( *itWhere, item );
      return itWhere;
   }

   void insert( const_iterator first , const_iterator last )
   {
      reserve( last - first );
      iterator itHint = begin();
      for ( ; first != last; ++first )
         itHint = insert( itHint, *first ).first;
   }

   void swap( SelfType &other )
   {
      CppTL::swap( data_, other.data_ );
      CppTL::swap( size_, other.size_ );
      CppTL::swap( capacity_, other.capacity_ );
      allocator_.swap( other.allocator_ );
      CppTL::swap( less_, other.less_ );
   }

   bool operator <( const SelfType &other ) const
   {
      if ( size_ < other.size_ )
         return true;
      if ( size_ > other.size_  ||  size_ == 0 )
         return false;
      Item *i1 = data_, *i2 = other.data_;
      Item *i1end = data_ + size_;
      for ( ; i1 != i1end; ++i1, ++i2 )
      {
         if ( itemIsLess( *i1, *i2 ) )
            return true;
         if ( itemIsLess( *i2, *i1 ) )
            return false;
      }
      return false;
   }

   bool operator ==( const SelfType &other ) const
   {
      if ( size_ != other.size_ )
         return false;
      Item *i1 = data_, *i2 = other.data_;
      Item *i1end = data_ + size_;
      for ( ; i1 != i1end; ++i1, ++i2 )
      {
         if ( itemIsLess( *i1, *i2 )  ||  itemIsLess( *i2, *i1 ) )
            return false;
      }
      return true;
   }

private:
   // Ensure capacity is large enough to add count elements.
   // Optionaly, insert a new item in the middle at position insertIndex.
   bool reserve( size_t count, size_t insertIndex = 0, const Item *item = 0)
   {
      if ( size_ + count <= capacity_ )
         return false;
      const size_t initialCapacity = 8;
      const size_t minCapacityIncrement = 8;
      size_t newCapacity = size_ + count;
      newCapacity += CPPTL_MAX( newCapacity / 4, minCapacityIncrement );
      newCapacity = CPPTL_MAX( initialCapacity, newCapacity );
      Item *newData = allocator_.allocateArray( newCapacity );
      CPPTL_TRY_BEGIN
      {
         if ( !item )
            insertIndex = size_;
         ::CppTL::Impl::copy_and_destroy( begin(), begin() + insertIndex, newData );
         if ( item )
         {
            new (newData+insertIndex) Item( *item );
            ::CppTL::Impl::copy_and_destroy( begin() + insertIndex, end(), 
                                             newData + (insertIndex+1) );
         }
      }
      CPPTL_TRY_END_CLEANUP( allocator_.release( newData, newCapacity ) );
      if ( data_ )
         allocator_.releaseArray( data_, capacity_ );
      data_ = newData;
      capacity_ = newCapacity;
      if ( item )
         ++size_;
      return true;
   }

   size_t insertionIndex( const Key &key, size_t min = 0 ) const
   {
      size_t max = size_;
      while ( min != max )
      {
         size_t mid = (max+min) / 2;
         if ( less_( data_[mid].first, key ) )
            min = mid + 1;
         else
            max = mid;
      }
      return min;
   }

   Item *lookUp( const Key &key ) const
   {
      size_t pos = insertionIndex( key, 0 );
      if ( pos  < size_  &&  !less_( key, data_[pos].first ) )
         return data_ + pos;
      return 0;
   }

   iterator doInsert( size_t whereIndex, const Item &item )
   {
      if ( size_ == capacity_ )
      {
         if ( reserve( 1, whereIndex, &item ) )  // element was inserted when increasing capacity.
            return begin() + whereIndex;
      }
      ++size_;
      iterator itWhere( *this, whereIndex );
      iterator itEnd = end();
      if ( whereIndex != size_ - 1 )
         ::CppTL::Impl::copy_backwards_and_destroy( itWhere, itEnd-1, itEnd );
      ::CppTL::Impl::construct( *itWhere, item);
      return itWhere;
   }

   bool itemIsLess( const Item &a, const Item &b ) const
   {
      return less_( a.first, b.first )  ||
             ( !less_(b.first, a.first) &&  a.second < b.second );
   }


private:
   Allocator allocator_;
   PredLess less_;
};



} // namespace CppTL


#endif // CPPTL_VECTOR_H_INCLUDED

Index: forwards.h
===================================================================
RCS file: /cvsroot/cppunit/cppunit2/include/cpptl/forwards.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** forwards.h	20 Jul 2005 21:06:49 -0000	1.6
--- forwards.h	5 Jun 2006 12:02:56 -0000	1.7
***************
*** 44,48 ****
--- 44,53 ----
  class SharedPtr;
  
+ // _stlimpl.h
+ template<class T>
+ class MallocAllocator;
  
+ template<class T>
+ struct LessPred;
  
  } // namespace CppTL