ycpp_map.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software for any
 * purpose is hereby granted without fee, provided that the above copyright
 * notice appear in all copies and that both that copyright notice and this
 * permission notice appear in supporting documentation.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_MAP_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_MAP_HEADER_FILE__
//------------------------------------------------------------------------------
#include <memory>
#include <utility>
#include <iterator>
#include <algorithm>
#include <functional>
#include "../youngc/yc_bbstree.h"
#include "../youngc/yc_memory.h"
#include "ycpp_memory.hpp"
#include "ycpp_function.hpp"
//------------------------------------------------------------------------------
namespace youngcpp {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename Key, typename Value, typename Compare, typename Allocator >
class map;

template< typename Key, typename Value, typename Compare, typename Allocator >
class multimap;

template< typename T, typename Ref, typename Ptr, typename Key, typename Mapped,
          typename Compare, typename Allocator >
class map_iterator;

template< typename Key, typename Value, typename Compare, typename Allocator >
struct move_traits< map<Key, Value, Compare, Allocator> >
{
    typedef  true_type  move_ability;
};

template< typename Key, typename Value, typename Compare, typename Allocator >
struct move_traits< multimap<Key, Value, Compare, Allocator> >
{
    typedef  true_type  move_ability;
};

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T, typename Ref, typename Ptr, typename Key, typename Mapped,
          typename Compare, typename Allocator >
class map_iterator
{
private:
    typedef  typename primal_traits<Ref>::contrary_const_ref  ccRef;
    typedef  typename primal_traits<Ptr>::contrary_const_ptr  ccPtr;

    friend class map<Key, Mapped, Compare, Allocator>;
    friend class multimap<Key, Mapped, Compare, Allocator>;
    friend class map_iterator<T, ccRef, ccPtr, Key, Mapped, Compare, Allocator>;

    youngc::bbstree_iterator itr;

public:
    typedef  std::bidirectional_iterator_tag    iterator_category;
    typedef  size_t                             size_type;
    typedef  ptrdiff_t                          difference_type;
    typedef  T                                  value_type;
    typedef  Ref                                reference;
    typedef  Ptr                                pointer;

    typedef  map_iterator<T, Ref, Ptr, Key, Mapped, Compare, Allocator>  self;
    typedef  map_iterator<T, T&, T*, Key, Mapped, Compare, Allocator>    iterator;

    map_iterator() : itr(0)  {}
    map_iterator( const iterator& src ) : itr(src.itr)  {}
    map_iterator( const youngc::bbstree_iterator& src ) : itr(src)  {}

    bool operator==( const self& rhs ) const  {  return itr == rhs.itr;  }
    bool operator!=( const self& rhs ) const  {  return itr != rhs.itr;  }

    reference operator*() const
        {  return *( (pointer)bbstree_itr_deref(itr) );  }
    pointer operator->() const
        {  return (pointer)bbstree_itr_deref(itr);  }

    self& operator++()  {  bbstree_itr_inc(&itr);  return *this;  }
    self& operator--()  {  bbstree_itr_dec(&itr);  return *this;  }

    self operator++(int)
        {  self old = *this;  bbstree_itr_inc(&itr);  return old;  }
    self operator--(int)
        {  self old = *this;  bbstree_itr_dec(&itr);  return old;  }
};

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename Key, typename Value, typename Compare = std::less<Key>,
          typename Allocator = std::allocator< std::pair<const Key, Value> > >
class map
{
public:
    typedef  map<Key, Value, Compare, Allocator>  self;

    typedef  Key                            key_type;
    typedef  Value                          mapped_type;
    typedef  std::pair<const Key, Value>    value_type;
    typedef  Compare                        key_compare;
    typedef  Allocator                      allocator_type;

    typedef  size_t                         size_type;
    typedef  ptrdiff_t                      difference_type;
    typedef  value_type&                    reference;
    typedef  const value_type&              const_reference;
    typedef  value_type*                    pointer;
    typedef  const value_type*              cons_pointer;

    typedef  map_iterator<value_type, reference, pointer,
                          Key, mapped_type, Compare, Allocator>  iterator;
    typedef  map_iterator<value_type, const_reference, cons_pointer,
                          Key, mapped_type, Compare, Allocator>  const_iterator;
    typedef  std::reverse_iterator<iterator>        reverse_iterator;
    typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;

    map()
    {
        typedef  typename property_traits<key_type>::is_POD     kPOD;
        typedef  typename property_traits<mapped_type>::is_POD  vPOD;
        init( kPOD(), vPOD() );
    }

    template< typename InputIterator >
    map( InputIterator first, InputIterator last )
    {
        typedef  typename property_traits<key_type>::is_POD     kPOD;
        typedef  typename property_traits<mapped_type>::is_POD  vPOD;
        init( kPOD(), vPOD() );
        for( ; first != last; ++first )
        {
            if( !bbstree_insert_unique_value(&m_tree, &(*first)) )
            {
                bbstree_destroy( &m_tree );
                throw std::bad_alloc();
            }
        }
    }

    map( const self& rhs )
    {
        if( bbstree_init_copy( &m_tree, &(rhs.m_tree) ) == 0 )
            throw std::bad_alloc();
    }

    self& operator=( const self& rhs )
    {
        if( bbstree_assign_copy( &m_tree, &(rhs.m_tree) ) == 0 )
            throw std::bad_alloc();
        return *this;
    }

    ~map()  {  bbstree_destroy( &m_tree );  }

    static void init_move( void* uninit_dst, void* src )
    {
        bbstree_init_move( &( static_cast<self*>(uninit_dst)->m_tree ),
                           &( static_cast<self*>(src)->m_tree ) );
    }

    static void assign_move( void* dst, void* src )
    {
        bbstree_assign_move( &( static_cast<self*>(dst)->m_tree ),
                             &( static_cast<self*>(src)->m_tree ) );
    }

    iterator begin()
        {  return iterator( bbstree_begin(&m_tree) );  }
    iterator end()
        {  return iterator( bbstree_end(&m_tree) );  }
    const_iterator begin() const
        {  return const_iterator( bbstree_begin(&m_tree) );  }
    const_iterator end() const
        {  return const_iterator( bbstree_end(&m_tree) );  }

    reverse_iterator rbegin()
        {  return reverse_iterator( end() );  }
    reverse_iterator rend()
        {  return reverse_iterator( begin() );  }
    const_reverse_iterator rbegin() const
        {  return const_reverse_iterator( end() );  }
    const_reverse_iterator rend() const
        {  return const_reverse_iterator( begin() );  }

    void clear()                  {  bbstree_destroy(&m_tree);  }
    bool empty() const            {  return bbstree_size(&m_tree) == 0;  }
    size_type size() const        {  return bbstree_size(&m_tree);  }
    size_type max_size() const    {  return youngc::bbstree_max_size();  }
    void swap( const self& rhs )  {  bbstree_swap( &m_tree, &(rhs.m_tree) );  }

    void erase( iterator position )
        {  bbstree_erase_pos( &m_tree, position.itr );  }
    void erase( iterator first, iterator last )
        {  bbstree_erase_range( &m_tree, first.itr, last.itr );  }
    size_type erase( const key_type& k )
        {  return bbstree_erase_key( &m_tree, &k );  }

    std::pair<iterator, bool> insert( const value_type& v )
    {
        size_type old = size();
        youngc::bbstree_iterator p = bbstree_insert_unique_value(&m_tree, &v);
        if( !p )
            throw std::bad_alloc();
        return old == size() ? std::pair<iterator, bool>( p, false )
                             : std::pair<iterator, bool>( p, true );
    }
    iterator insert( iterator pos, const value_type& v )
    {
        youngc::bbstree_iterator p = bbstree_insert_unique_pos( &m_tree,
                                                                pos.itr, &v );
        if( !p )
            throw std::bad_alloc();
        return p;
    }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
    {
        for( ; first != last; ++first )
        {
            if( !bbstree_insert_unique_value(&m_tree, &(*first)) )
                throw std::bad_alloc();
        }
    }

    mapped_type& operator[]( const key_type& k )
    {
        return insert( value_type(k, mapped_type()) ).first->second;
    }

    size_type count( const key_type& k ) const
        {  return bbstree_count( &m_tree, &k );  }

    iterator find( const key_type& k )
        {  return bbstree_find( &m_tree, &k );  }
    const_iterator find( const key_type& k ) const
        {  return bbstree_find( &m_tree, &k );  }

    iterator lower_bound( const key_type& k )
        {  return bbstree_lower_bound( &m_tree, &k );  }
    const_iterator lower_bound( const key_type& k ) const
        {  return bbstree_lower_bound( &m_tree, &k );  }

    iterator upper_bound( const key_type& k )
        {  return bbstree_upper_bound( &m_tree, &k );  }
    const_iterator upper_bound( const key_type& k ) const
        {  return bbstree_upper_bound( &m_tree, &k );  }

    std::pair<iterator, iterator> equal_range( const key_type& k )
    {
        youngc::bbstree_pair_iterator pr = bbstree_equal_range( &m_tree, &k );
        return std::pair<iterator, iterator>( pr.first, pr.second );
    }
    std::pair<const_iterator, const_iterator> equal_range( const key_type& k ) const
    {
        youngc::bbstree_pair_iterator pr = bbstree_equal_range( &m_tree, &k );
        return std::pair<const_iterator, const_iterator>( pr.first, pr.second );
    }

    bool replace_key( iterator position, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        return bbstree_replace_key_unique_pos( &m_tree, position.itr,
                                &new_key, assign_copy_adapter<key_type> );
    }
    iterator replace_key( const key_type& old_key, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        return bbstree_replace_key_unique( &m_tree, &old_key, &new_key,
                                           assign_copy_adapter<key_type> );
    }

private:
    mutable youngc::bbstree m_tree;

    void init( true_type, true_type )
    {
        bbstree_init( &m_tree,sizeof(value_type),
                      NULL, NULL, get_key, cmp_adapter<Key, Compare>,
                      alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    template< typename T1, typename T2 >
    void init( T1, T2 )
    {
        bbstree_init( &m_tree, sizeof(value_type),
                      init_copy_adapter<value_type>, destroy_adapter<value_type>,
                      get_key, cmp_adapter<Key, Compare>,
                      alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }

    static const void* get_key( const void* value )
    {
        return &( ((value_type*)value)->first );
    }
};



template< typename Key, typename Value, typename Compare, typename Allocator >
inline void swap( map<Key, Value, Compare, Allocator>& lhs,