code:
// Memory extensions -*- C++ -*-

// Copyright (C) 2002, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation 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.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation 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.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file ext/memory
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).
 */

#ifndef _EXT_MEMORY
#define _EXT_MEMORY 1

#pragma GCC system_header

#include <memory>
#include <bits/stl_tempbuf.h>

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  using std::ptrdiff_t;
  using std::pair;
  using std::__iterator_category;
  using std::_Temporary_buffer;

  template<typename _InputIter, typename _Size, typename _ForwardIter>
    pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n(_InputIter __first, _Size __count,
			   _ForwardIter __result, std::input_iterator_tag)
    {
      _ForwardIter __cur = __result;
      try
	{
	  for (; __count > 0 ; --__count, ++__first, ++__cur)
	    std::_Construct(&*__cur, *__first);
	  return pair<_InputIter, _ForwardIter>(__first, __cur);
	}
      catch(...)
	{
	  std::_Destroy(__result, __cur);
	  __throw_exception_again;
	}
    }

  template<typename _RandomAccessIter, typename _Size, typename _ForwardIter>
    inline pair<_RandomAccessIter, _ForwardIter>
    __uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
			   _ForwardIter __result,
			   std::random_access_iterator_tag)
    {
      _RandomAccessIter __last = __first + __count;
      return (pair<_RandomAccessIter, _ForwardIter>
	      (__last, std::uninitialized_copy(__first, __last, __result)));
    }

  template<typename _InputIter, typename _Size, typename _ForwardIter>
    inline pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n(_InputIter __first, _Size __count,
			 _ForwardIter __result)
    { return __uninitialized_copy_n(__first, __count, __result,
				    __iterator_category(__first)); }

  /**
   *  @brief Copies the range [first,last) into result.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  result An output iterator.
   *  @return   result + (first - last)
   *  @ingroup SGIextensions
   *
   *  Like copy(), but does not require an initialized output range.
  */
  template<typename _InputIter, typename _Size, typename _ForwardIter>
    inline pair<_InputIter, _ForwardIter>
    uninitialized_copy_n(_InputIter __first, _Size __count,
			 _ForwardIter __result)
    { return __uninitialized_copy_n(__first, __count, __result,
				    __iterator_category(__first)); }

  // An alternative version of uninitialized_copy_n that constructs
  // and destroys objects with a user-provided allocator.
  template<typename _InputIter, typename _Size, typename _ForwardIter,
           typename _Allocator>
    pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
			     _ForwardIter __result,
			     _Allocator __alloc)
    {
      _ForwardIter __cur = __result;
      try
	{
	  for (; __count > 0 ; --__count, ++__first, ++__cur)
	    __alloc.construct(&*__cur, *__first);
	  return pair<_InputIter, _ForwardIter>(__first, __cur);
	}
      catch(...)
	{
	  std::_Destroy(__result, __cur, __alloc);
	  __throw_exception_again;
	}
    }

  template<typename _InputIter, typename _Size, typename _ForwardIter,
           typename _Tp>
    inline pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
			     _ForwardIter __result,
			     std::allocator<_Tp>)
    {
      return uninitialized_copy_n(__first, __count, __result);
    }

  /**
   *  This class provides similar behavior and semantics of the standard
   *  functions get_temporary_buffer() and return_temporary_buffer(), but
   *  encapsulated in a type vaguely resembling a standard container.
   *
   *  By default, a temporary_buffer<Iter> stores space for objects of
   *  whatever type the Iter iterator points to.  It is constructed from a
   *  typical [first,last) range, and provides the begin(), end(), size()
   *  functions, as well as requested_size().  For non-trivial types, copies
   *  of *first will be used to initialize the storage.
   *
   *  @c malloc is used to obtain underlying storage.
   *
   *  Like get_temporary_buffer(), not all the requested memory may be
   *  available.  Ideally, the created buffer will be large enough to hold a
   *  copy of [first,last), but if size() is less than requested_size(),
   *  then this didn't happen.
   *
   *  @ingroup SGIextensions
  */
  template <class _ForwardIterator, class _Tp
	    = typename std::iterator_traits<_ForwardIterator>::value_type >
    struct temporary_buffer : public _Temporary_buffer<_ForwardIterator, _Tp>
    {
      /// Requests storage large enough to hold a copy of [first,last).
      temporary_buffer(_ForwardIterator __first, _ForwardIterator __last)
      : _Temporary_buffer<_ForwardIterator, _Tp>(__first, __last) { }

      /// Destroys objects and frees storage.
      ~temporary_buffer() { }
    };

_GLIBCXX_END_NAMESPACE

#endif


code:
// MT-optimized allocator -*- C++ -*-

// Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file ext/mt_allocator.h
 *  This file is a GNU extension to the Standard C++ Library.
 */

#ifndef _MT_ALLOCATOR_H
#define _MT_ALLOCATOR_H 1

#include <new>
#include <cstdlib>
#include <bits/functexcept.h>
#include <ext/atomicity.h>

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  using std::size_t;
  using std::ptrdiff_t;

  typedef void (*__destroy_handler)(void*);

  /// @brief  Base class for pool object.
  struct __pool_base
  {
    // Using short int as type for the binmap implies we are never
    // caching blocks larger than 32768 with this allocator.
    typedef unsigned short int _Binmap_type;

    // Variables used to configure the behavior of the allocator,
    // assigned and explained in detail below.
    struct _Tune
     {
      // Compile time constants for the default _Tune values.
      enum { _S_align = 8 };
      enum { _S_max_bytes = 128 };
      enum { _S_min_bin = 8 };
      enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
      enum { _S_max_threads = 4096 };
      enum { _S_freelist_headroom = 10 };

      // Alignment needed.
      // NB: In any case must be >= sizeof(_Block_record), that
      // is 4 on 32 bit machines and 8 on 64 bit machines.
      size_t	_M_align;

      // Allocation requests (after round-up to power of 2) below
      // this value will be handled by the allocator. A raw new/
      // call will be used for requests larger than this value.
      // NB: Must be much smaller than _M_chunk_size and in any
      // case <= 32768.
      size_t	_M_max_bytes;

      // Size in bytes of the smallest bin.
      // NB: Must be a power of 2 and >= _M_align (and of course
      // much smaller than _M_max_bytes).
      size_t	_M_min_bin;

      // In order to avoid fragmenting and minimize the number of
      // new() calls we always request new memory using this
      // value. Based on previous discussions on the libstdc++
      // mailing list we have choosen the value below.
      // See http://gcc.gnu.org/ml/libstdc++/2001-07/msg00077.html
      // NB: At least one order of magnitude > _M_max_bytes.
      size_t	_M_chunk_size;

      // The maximum number of supported threads. For
      // single-threaded operation, use one. Maximum values will
      // vary depending on details of the underlying system. (For
      // instance, Linux 2.4.18 reports 4070 in
      // /proc/sys/kernel/threads-max, while Linux 2.6.6 reports
      // 65534)
      size_t 	_M_max_threads;

      // Each time a deallocation occurs in a threaded application
      // we make sure that there are no more than
      // _M_freelist_headroom % of used memory on the freelist. If
      // the number of additional records is more than
      // _M_freelist_headroom % of the freelist, we move these
      // records back to the global pool.
      size_t 	_M_freelist_headroom;

      // Set to true forces all allocations to use new().
      bool 	_M_force_new;

      explicit
      _Tune()
      : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
      _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads),
      _M_freelist_headroom(_S_freelist_headroom),
      _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
      { }

      explicit
      _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk,
	    size_t __maxthreads, size_t __headroom, bool __force)
      : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
      _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
      _M_freelist_headroom(__headroom), _M_force_new(__force)
      { }
    };

    struct _Block_address
    {
      void* 			_M_initial;
      _Block_address* 		_M_next;
    };

    const _Tune&
    _M_get_options() const
    { return _M_options; }

    void
    _M_set_options(_Tune __t)
    {
      if (!_M_init)
	_M_options = __t;
    }

    bool
    _M_check_threshold(size_t __bytes)
    { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }

    size_t
    _M_get_binmap(size_t __bytes)
    { return _M_binmap[__bytes]; }

    const size_t
    _M_get_align()
    { return _M_options._M_align; }

    explicit
    __pool_base()
    : _M_options(_Tune()), _M_binmap(NULL), _M_init(false) { }

    explicit
    __pool_base(const _Tune& __options)
    : _M_options(__options), _M_binmap(NULL), _M_init(false) { }

  private:
    explicit
    __pool_base(const __pool_base&);

    __pool_base&
    operator=(const __pool_base&);

  protected:
    // Configuration options.
    _Tune 	       		_M_options;

    _Binmap_type* 		_M_binmap;

    // Configuration of the pool object via _M_options can happen
    // after construction but before initialization. After
    // initialization is complete, this variable is set to true.
    bool 			_M_init;
  };

  /**
   *  @brief  Data describing the underlying memory pool, parameterized on
   *  threading support.
   */
  template<bool _Thread>
    class __pool;

  /// Specialization for single thread.
  template<>
    class __pool<false> : public __pool_base
    {
    public:
      union _Block_record
      {
	// Points to the block_record of the next free block.
	_Block_record* 			_M_next;
      };

      struct _Bin_record
      {
	// An "array" of pointers to the first free block.
	_Block_record**			_M_first;

	// A list of the initial addresses of all allocated blocks.
	_Block_address*		     	_M_address;
      };

      void
      _M_initialize_once()
      {
	if (__builtin_expect(_M_init == false, false))
	  _M_initialize();
      }

      void
      _M_destroy() throw();

      char*
      _M_reserve_block(size_t __bytes, const size_t __thread_id);

      void
      _M_reclaim_block(char* __p, size_t __bytes);

      size_t
      _M_get_thread_id() { return 0; }

      const _Bin_record&
      _M_get_bin(size_t __which)
      { return _M_bin[__which]; }

      void
      _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t)
      { }

      explicit __pool()
      : _M_bin(NULL), _M_bin_size(1) { }

      explicit __pool(const __pool_base::_Tune& __tune)
      : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1) { }

    private:
      // An "array" of bin_records each of which represents a specific
      // power of 2 size. Memory to this "array" is allocated in
      // _M_initialize().
      _Bin_record*		 _M_bin;

      // Actual value calculated in _M_initialize().
      size_t 	       	     	_M_bin_size;

      void
      _M_initialize();
  };

#ifdef __GTHREADS
  /// Specialization for thread enabled, via gthreads.h.
  template<>
    class __pool<true> : public __pool_base
    {
    public:
      // Each requesting thread is assigned an id ranging from 1 to
      // _S_max_threads. Thread id 0 is used as a global memory pool.
      // In order to get constant performance on the thread assignment
      // routine, we keep a list of free ids. When a thread first
      // requests memory we remove the first record in this list and
      // stores the address in a __gthread_key. When initializing the
      // __gthread_key we specify a destructor. When this destructor
      // (i.e. the thread dies) is called, we return the thread id to
      // the front of this list.
      struct _Thread_record
      {
	// Points to next free thread id record. NULL if last record in list.
	_Thread_record*			_M_next;

	// Thread id ranging from 1 to _S_max_threads.
	size_t                          _M_id;
      };

      union _Block_record
      {
	// Points to the block_record of the next free block.
	_Block_record*			_M_next;

	// The thread id of the thread which has requested this block.
	size_t                          _M_thread_id;
      };

      struct _Bin_record
      {
	// An "array" of pointers to the first free block for each
	// thread id. Memory to this "array" is allocated in
	// _S_initialize() for _S_max_threads + global pool 0.
	_Block_record**			_M_first;

	// A list of the initial addresses of all allocated blocks.
	_Block_address*		     	_M_address;

	// An "array" of counters used to keep track of the amount of
	// blocks that are on the freelist/used for each thread id.
	// - Note that the second part of the allocated _M_used "array"
	//   actually hosts (atomic) counters of reclaimed blocks:  in
	//   _M_reserve_block and in _M_reclaim_block those numbers are
	//   subtracted from the first ones to obtain the actual size
	//   of the "working set" of the given thread.
	// - Memory to these "arrays" is allocated in _S_initialize()
	//   for _S_max_threads + global pool 0.
	size_t*				_M_free;
	size_t*			        _M_used;

	// Each bin has its own mutex which is used to ensure data
	// integrity while changing "ownership" on a block.  The mutex
	// is initialized in _S_initialize().
	__gthread_mutex_t*              _M_mutex;
      };

      // XXX GLIBCXX_ABI Deprecated
      void
      _M_initialize(__destroy_handler);

      void
      _M_initialize_once()
      {
	if (__builtin_expect(_M_init == false, false))
	  _M_initialize();
      }

      void
      _M_destroy() throw();

      char*
      _M_reserve_block(size_t __bytes, const size_t __thread_id);

      void
      _M_reclaim_block(char* __p, size_t __bytes);

      const _Bin_record&
      _M_get_bin(size_t __which)
      { return _M_bin[__which]; }

      void
      _M_adjust_freelist(const _Bin_record& __bin, _Block_record* __block,
			 size_t __thread_id)
      {
	if (__gthread_active_p())
	  {
	    __block->_M_thread_id = __thread_id;
	    --__bin._M_free[__thread_id];
	    ++__bin._M_used[__thread_id];
	  }
      }

      // XXX GLIBCXX_ABI Deprecated
      void
      _M_destroy_thread_key(void*);

      size_t
      _M_get_thread_id();

      explicit __pool()
      : _M_bin(NULL), _M_bin_size(1), _M_thread_freelist(NULL)
      { }

      explicit __pool(const __pool_base::_Tune& __tune)
      : __pool_base(__tune), _M_bin(NULL), _M_bin_size(1),
      _M_thread_freelist(NULL)
      { }

    private:
      // An "array" of bin_records each of which represents a specific
      // power of 2 size. Memory to this "array" is allocated in
      // _M_initialize().
      _Bin_record*		_M_bin;

      // Actual value calculated in _M_initialize().
      size_t 	       	     	_M_bin_size;

      _Thread_record* 		_M_thread_freelist;
      void*			_M_thread_freelist_initial;

      void
      _M_initialize();
    };
#endif

  template<template <bool> class _PoolTp, bool _Thread>
    struct __common_pool
    {
      typedef _PoolTp<_Thread> 		pool_type;

      static pool_type&
      _S_get_pool()
      {
	static pool_type _S_pool;
	return _S_pool;
      }
    };

  template<template <bool> class _PoolTp, bool _Thread>
    struct __common_pool_base;

  template<template <bool> class _PoolTp>
    struct __common_pool_base<_PoolTp, false>
    : public __common_pool<_PoolTp, false>
    {
      using  __common_pool<_PoolTp, false>::_S_get_pool;

      static void
      _S_initialize_once()
      {
	static bool __init;
	if (__builtin_expect(__init == false, false))
	  {
	    _S_get_pool()._M_initialize_once();
	    __init = true;
	  }
      }
    };

#ifdef __GTHREADS
  template<template <bool> class _PoolTp>
    struct __common_pool_base<_PoolTp, true>
    : public __common_pool<_PoolTp, true>
    {
      using  __common_pool<_PoolTp, true>::_S_get_pool;

      static void
      _S_initialize()
      { _S_get_pool()._M_initialize_once(); }

      static void
      _S_initialize_once()
      {
	static bool __init;
	if (__builtin_expect(__init == false, false))
	  {
	    if (__gthread_active_p())
	      {
		// On some platforms, __gthread_once_t is an aggregate.
		static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
		__gthread_once(&__once, _S_initialize);
	      }

	    // Double check initialization. May be necessary on some
	    // systems for proper construction when not compiling with
	    // thread flags.
	    _S_get_pool()._M_initialize_once();
	    __init = true;
	  }
      }
    };
#endif

  /// @brief  Policy for shared __pool objects.
  template<template <bool> class _PoolTp, bool _Thread>
    struct __common_pool_policy : public __common_pool_base<_PoolTp, _Thread>
    {
      template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp,
	       bool _Thread1 = _Thread>
        struct _M_rebind
        { typedef __common_pool_policy<_PoolTp1, _Thread1> other; };

      using  __common_pool_base<_PoolTp, _Thread>::_S_get_pool;
      using  __common_pool_base<_PoolTp, _Thread>::_S_initialize_once;
  };

  template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
    struct __per_type_pool
    {
      typedef _Tp 			value_type;
      typedef _PoolTp<_Thread> 		pool_type;

      static pool_type&
      _S_get_pool()
      {
	// Sane defaults for the _PoolTp.
	typedef typename pool_type::_Block_record _Block_record;
	const static size_t __a = (__alignof__(_Tp) >= sizeof(_Block_record)
				   ? __alignof__(_Tp) : sizeof(_Block_record));

	typedef typename __pool_base::_Tune _Tune;
	static _Tune _S_tune(__a, sizeof(_Tp) * 64,
			     sizeof(_Tp) * 2 >= __a ? sizeof(_Tp) * 2 : __a,
			     sizeof(_Tp) * size_t(_Tune::_S_chunk_size),
			     _Tune::_S_max_threads,
			     _Tune::_S_freelist_headroom,
			     std::getenv("GLIBCXX_FORCE_NEW") ? true : false);
	static pool_type _S_pool(_S_tune);
	return _S_pool;
      }
    };

  template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
    struct __per_type_pool_base;

  template<typename _Tp, template <bool> class _PoolTp>
    struct __per_type_pool_base<_Tp, _PoolTp, false>
    : public __per_type_pool<_Tp, _PoolTp, false>
    {
      using  __per_type_pool<_Tp, _PoolTp, false>::_S_get_pool;

      static void
      _S_initialize_once()
      {
	static bool __init;
	if (__builtin_expect(__init == false, false))
	  {
	    _S_get_pool()._M_initialize_once();
	    __init = true;
	  }
      }
    };

 #ifdef __GTHREADS
 template<typename _Tp, template <bool> class _PoolTp>
    struct __per_type_pool_base<_Tp, _PoolTp, true>
    : public __per_type_pool<_Tp, _PoolTp, true>
    {
      using  __per_type_pool<_Tp, _PoolTp, true>::_S_get_pool;

      static void
      _S_initialize()
      { _S_get_pool()._M_initialize_once(); }

      static void
      _S_initialize_once()
      {
	static bool __init;
	if (__builtin_expect(__init == false, false))
	  {
	    if (__gthread_active_p())
	      {
		// On some platforms, __gthread_once_t is an aggregate.
		static __gthread_once_t __once = __GTHREAD_ONCE_INIT;
		__gthread_once(&__once, _S_initialize);
	      }

	    // Double check initialization. May be necessary on some
	    // systems for proper construction when not compiling with
	    // thread flags.
	    _S_get_pool()._M_initialize_once();
	    __init = true;
	  }
      }
    };
#endif

  /// @brief  Policy for individual __pool objects.
  template<typename _Tp, template <bool> class _PoolTp, bool _Thread>
    struct __per_type_pool_policy
    : public __per_type_pool_base<_Tp, _PoolTp, _Thread>
    {
      template<typename _Tp1, template <bool> class _PoolTp1 = _PoolTp,
	       bool _Thread1 = _Thread>
        struct _M_rebind
        { typedef __per_type_pool_policy<_Tp1, _PoolTp1, _Thread1> other; };

      using  __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_get_pool;
      using  __per_type_pool_base<_Tp, _PoolTp, _Thread>::_S_initialize_once;
  };

  /// @brief  Base class for _Tp dependent member functions.
  template<typename _Tp>
    class __mt_alloc_base
    {
    public:
      typedef size_t                    size_type;
      typedef ptrdiff_t                 difference_type;
      typedef _Tp*                      pointer;
      typedef const _Tp*                const_pointer;
      typedef _Tp&                      reference;
      typedef const _Tp&                const_reference;
      typedef _Tp                       value_type;

      pointer
      address(reference __x) const
      { return &__x; }

      const_pointer
      address(const_reference __x) const
      { return &__x; }

      size_type
      max_size() const throw()
      { return size_t(-1) / sizeof(_Tp); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 402. wrong new expression in [some_] allocator::construct
      void
      construct(pointer __p, const _Tp& __val)
      { ::new(__p) _Tp(__val); }

      void
      destroy(pointer __p) { __p->~_Tp(); }
    };

#ifdef __GTHREADS
#define __thread_default true
#else
#define __thread_default false
#endif

  /**
   *  @brief  This is a fixed size (power of 2) allocator which - when
   *  compiled with thread support - will maintain one freelist per
   *  size per thread plus a "global" one. Steps are taken to limit
   *  the per thread freelist sizes (by returning excess back to
   *  the "global" list).
   *
   *  Further details:
   *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/mt_allocator.html
   */
  template<typename _Tp,
	   typename _Poolp = __common_pool_policy<__pool, __thread_default> >
    class __mt_alloc : public __mt_alloc_base<_Tp>
    {
    public:
      typedef size_t                    	size_type;
      typedef ptrdiff_t                 	difference_type;
      typedef _Tp*                      	pointer;
      typedef const _Tp*                	const_pointer;
      typedef _Tp&                      	reference;
      typedef const _Tp&                	const_reference;
      typedef _Tp                       	value_type;
      typedef _Poolp      			__policy_type;
      typedef typename _Poolp::pool_type	__pool_type;

      template<typename _Tp1, typename _Poolp1 = _Poolp>
        struct rebind
        {
	  typedef typename _Poolp1::template _M_rebind<_Tp1>::other pol_type;
	  typedef __mt_alloc<_Tp1, pol_type> other;
	};

      __mt_alloc() throw() { }

      __mt_alloc(const __mt_alloc&) throw() { }

      template<typename _Tp1, typename _Poolp1>
        __mt_alloc(const __mt_alloc<_Tp1, _Poolp1>&) throw() { }

      ~__mt_alloc() throw() { }

      pointer
      allocate(size_type __n, const void* = 0);

      void
      deallocate(pointer __p, size_type __n);

      const __pool_base::_Tune
      _M_get_options()
      {
	// Return a copy, not a reference, for external consumption.
	return __policy_type::_S_get_pool()._M_get_options();
      }

      void
      _M_set_options(__pool_base::_Tune __t)
      { __policy_type::_S_get_pool()._M_set_options(__t); }
    };

  template<typename _Tp, typename _Poolp>
    typename __mt_alloc<_Tp, _Poolp>::pointer
    __mt_alloc<_Tp, _Poolp>::
    allocate(size_type __n, const void*)
    {
      if (__builtin_expect(__n > this->max_size(), false))
	std::__throw_bad_alloc();

      __policy_type::_S_initialize_once();

      // Requests larger than _M_max_bytes are handled by operator
      // new/delete directly.
      __pool_type& __pool = __policy_type::_S_get_pool();
      const size_t __bytes = __n * sizeof(_Tp);
      if (__pool._M_check_threshold(__bytes))
	{
	  void* __ret = ::operator new(__bytes);
	  return static_cast<_Tp*>(__ret);
	}

      // Round up to power of 2 and figure out which bin to use.
      const size_t __which = __pool._M_get_binmap(__bytes);
      const size_t __thread_id = __pool._M_get_thread_id();

      // Find out if we have blocks on our freelist.  If so, go ahead
      // and use them directly without having to lock anything.
      char* __c;
      typedef typename __pool_type::_Bin_record _Bin_record;
      const _Bin_record& __bin = __pool._M_get_bin(__which);
      if (__bin._M_first[__thread_id])
	{
	  // Already reserved.
	  typedef typename __pool_type::_Block_record _Block_record;
	  _Block_record* __block = __bin._M_first[__thread_id];
	  __bin._M_first[__thread_id] = __block->_M_next;

	  __pool._M_adjust_freelist(__bin, __block, __thread_id);
	  __c = reinterpret_cast<char*>(__block) + __pool._M_get_align();
	}
      else
	{
	  // Null, reserve.
	  __c = __pool._M_reserve_block(__bytes, __thread_id);
	}
      return static_cast<_Tp*>(static_cast<void*>(__c));
    }

  template<typename _Tp, typename _Poolp>
    void
    __mt_alloc<_Tp, _Poolp>::
    deallocate(pointer __p, size_type __n)
    {
      if (__builtin_expect(__p != 0, true))
	{
	  // Requests larger than _M_max_bytes are handled by
	  // operators new/delete directly.
	  __pool_type& __pool = __policy_type::_S_get_pool();
	  const size_t __bytes = __n * sizeof(_Tp);
	  if (__pool._M_check_threshold(__bytes))
	    ::operator delete(__p);
	  else
	    __pool._M_reclaim_block(reinterpret_cast<char*>(__p), __bytes);
	}
    }

  template<typename _Tp, typename _Poolp>
    inline bool
    operator==(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
    { return true; }

  template<typename _Tp, typename _Poolp>
    inline bool
    operator!=(const __mt_alloc<_Tp, _Poolp>&, const __mt_alloc<_Tp, _Poolp>&)
    { return false; }

#undef __thread_default

_GLIBCXX_END_NAMESPACE

#endif

repo_name: veiledmerc/mira

license: mit


code:
// Allocator that wraps operator new -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file ext/new_allocator.h
 *  This file is a GNU extension to the Standard C++ Library.
 */

#ifndef _NEW_ALLOCATOR_H
#define _NEW_ALLOCATOR_H 1

#include <new>
#include <bits/functexcept.h>

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  using std::size_t;
  using std::ptrdiff_t;

  /**
   *  @brief  An allocator that uses global new, as per [20.4].
   *
   *  This is precisely the allocator defined in the C++ Standard.
   *    - all allocation calls operator new
   *    - all deallocation calls operator delete
   */
  template<typename _Tp>
    class new_allocator
    {
    public:
      typedef size_t     size_type;
      typedef ptrdiff_t  difference_type;
      typedef _Tp*       pointer;
      typedef const _Tp* const_pointer;
      typedef _Tp&       reference;
      typedef const _Tp& const_reference;
      typedef _Tp        value_type;

      template<typename _Tp1>
        struct rebind
        { typedef new_allocator<_Tp1> other; };

      new_allocator() throw() { }

      new_allocator(const new_allocator&) throw() { }

      template<typename _Tp1>
        new_allocator(const new_allocator<_Tp1>&) throw() { }

      ~new_allocator() throw() { }

      pointer
      address(reference __x) const { return &__x; }

      const_pointer
      address(const_reference __x) const { return &__x; }

      // NB: __n is permitted to be 0.  The C++ standard says nothing
      // about what the return value is when __n == 0.
      pointer
      allocate(size_type __n, const void* = 0)
      {
	if (__builtin_expect(__n > this->max_size(), false))
	  std::__throw_bad_alloc();

	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
      }

      // __p is not permitted to be a null pointer.
      void
      deallocate(pointer __p, size_type)
      { ::operator delete(__p); }

      size_type
      max_size() const throw()
      { return size_t(-1) / sizeof(_Tp); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 402. wrong new expression in [some_] allocator::construct
      void
      construct(pointer __p, const _Tp& __val)
      { ::new(__p) _Tp(__val); }

      void
      destroy(pointer __p) { __p->~_Tp(); }
    };

  template<typename _Tp>
    inline bool
    operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
    { return true; }

  template<typename _Tp>
    inline bool
    operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
    { return false; }

_GLIBCXX_END_NAMESPACE

#endif


code:
// Numeric extensions -*- C++ -*-

// Copyright (C) 2002, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation 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.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation 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.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file ext/numeric
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).
 */

#ifndef _EXT_NUMERIC
#define _EXT_NUMERIC 1

#pragma GCC system_header

#include <bits/concept_check.h>
#include <numeric>

#include <ext/functional> // For identity_element

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  // Returns __x ** __n, where __n >= 0.  _Note that "multiplication"
  // is required to be associative, but not necessarily commutative.
  template<typename _Tp, typename _Integer, typename _MonoidOperation>
    _Tp
    __power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
    {
      if (__n == 0)
	return identity_element(__monoid_op);
      else
	{
	  while ((__n & 1) == 0)
	    {
	      __n >>= 1;
	      __x = __monoid_op(__x, __x);
	    }

	  _Tp __result = __x;
	  __n >>= 1;
	  while (__n != 0)
	    {
	      __x = __monoid_op(__x, __x);
	      if ((__n & 1) != 0)
		__result = __monoid_op(__result, __x);
	      __n >>= 1;
	    }
	  return __result;
	}
    }

  template<typename _Tp, typename _Integer>
    inline _Tp
    __power(_Tp __x, _Integer __n)
    { return __power(__x, __n, std::multiplies<_Tp>()); }

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
  */
  // Alias for the internal name __power.  Note that power is an extension,
  // not part of the C++ standard.
  template<typename _Tp, typename _Integer, typename _MonoidOperation>
    inline _Tp
    power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
    { return __power(__x, __n, __monoid_op); }

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
  */
  template<typename _Tp, typename _Integer>
    inline _Tp
    power(_Tp __x, _Integer __n)
    { return __power(__x, __n); }

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
  */
  // iota is not part of the C++ standard.  It is an extension.
  template<typename _ForwardIter, typename _Tp>
    void
    iota(_ForwardIter __first, _ForwardIter __last, _Tp __value)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
      __glibcxx_function_requires(_ConvertibleConcept<_Tp,
	    typename std::iterator_traits<_ForwardIter>::value_type>)

      while (__first != __last)
	*__first++ = __value++;
    }

_GLIBCXX_END_NAMESPACE

#endif


code:
// -*- C++ -*-

// Copyright (C) 2007 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

/** @file ext/numeric_traits.h
 *  This file is a GNU extension to the Standard C++ Library.
 */

#ifndef _EXT_NUMERIC_TRAITS
#define _EXT_NUMERIC_TRAITS 1

#pragma GCC system_header

#include <limits>
#include <bits/cpp_type_traits.h>
#include <ext/type_traits.h>

_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  // Compile time constants for builtin types.
  // Sadly std::numeric_limits member functions cannot be used for this.
#define __glibcxx_signed(_Tp) ((_Tp)(-1) < 0)
#define __glibcxx_digits(_Tp) \
  (sizeof(_Tp) * __CHAR_BIT__ - __glibcxx_signed(_Tp))

#define __glibcxx_min(_Tp) \
  (__glibcxx_signed(_Tp) ? (_Tp)1 << __glibcxx_digits(_Tp) : (_Tp)0)

#define __glibcxx_max(_Tp) \
  (__glibcxx_signed(_Tp) ? \
   (((((_Tp)1 << (__glibcxx_digits(_Tp) - 1)) - 1) << 1) + 1) : ~(_Tp)0)

  template<typename _Value>
    struct __numeric_traits_integer
    {
      // Only integers for initialization of member constant.
      static const _Value __min = __glibcxx_min(_Value);
      static const _Value __max = __glibcxx_max(_Value);
    };

  template<typename _Value>
    const _Value __numeric_traits_integer<_Value>::__min;

  template<typename _Value>
    const _Value __numeric_traits_integer<_Value>::__max;

  template<typename _Value>
    struct __numeric_traits_floating
    {
      // Only floating point types. See N1822.
      static const int __max_digits10 =
	2 + std::numeric_limits<_Value>::digits * 3010/10000;
    };

  template<typename _Value>
    const int __numeric_traits_floating<_Value>::__max_digits10;

  template<typename _Value>
    struct __numeric_traits
    : public __conditional_type<std::__is_integer<_Value>::__value,
				__numeric_traits_integer<_Value>,
				__numeric_traits_floating<_Value> >::__type
    { };

_GLIBCXX_END_NAMESPACE

#undef __glibcxx_signed
#undef __glibcxx_min
#undef __glibcxx_max
#undef __glibcxx_digits

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file assoc_container.hpp
 * Contains associative containers.
 */

#ifndef PB_DS_ASSOC_CNTNR_HPP
#define PB_DS_ASSOC_CNTNR_HPP

#include <ext/typelist.h>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/detail/container_base_dispatch.hpp>
#include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>

namespace pb_ds
{
#define PB_DS_BASE_C_DEC \
  detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type

  // An abstract basic associative container.
  template<typename Key,
	   typename Mapped,
	   typename Tag,
	   typename Policy_Tl,
	   typename Allocator>
  class container_base : public PB_DS_BASE_C_DEC
  {
  private:
    typedef typename PB_DS_BASE_C_DEC 			base_type;

  public:
    typedef Tag 					container_category;
    typedef Allocator 					allocator;
    typedef typename allocator::size_type 		size_type;
    typedef typename allocator::difference_type 	difference_type;

    // key_type
    typedef typename allocator::template rebind<Key>::other::value_type key_type;
    typedef typename allocator::template rebind<key_type>::other key_rebind;
    typedef typename key_rebind::reference 		key_reference;
    typedef typename key_rebind::const_reference 	const_key_reference;
    typedef typename key_rebind::pointer 		key_pointer;
    typedef typename key_rebind::const_pointer 		const_key_pointer;

    // mapped_type
    typedef Mapped 					mapped_type;
    typedef typename allocator::template rebind<mapped_type>::other mapped_rebind;
    typedef typename mapped_rebind::reference 		mapped_reference;
    typedef typename mapped_rebind::const_reference	const_mapped_reference;
    typedef typename mapped_rebind::pointer 		mapped_pointer;
    typedef typename mapped_rebind::const_pointer 	const_mapped_pointer;

    // value_type
    typedef typename base_type::value_type 		value_type;
    typedef typename allocator::template rebind<value_type>::other value_rebind;
    typedef typename value_rebind::reference		reference;
    typedef typename value_rebind::const_reference 	const_reference;
    typedef typename value_rebind::pointer 		pointer;
    typedef typename value_rebind::const_pointer 	const_pointer;

    // iterators
    typedef typename base_type::iterator 		iterator;
    typedef typename base_type::const_iterator 		const_iterator;
    typedef typename base_type::point_iterator 		point_iterator;
    typedef typename base_type::const_point_iterator 	const_point_iterator;

    virtual
    ~container_base() { }

  protected:
#define PB_DS_CLASS_NAME 		container_base
#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
#undef PB_DS_CLASS_NAME
  };

#undef PB_DS_BASE_C_DEC

#define PB_DS_BASE_C_DEC \
  container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
  typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>

  // An abstract basic hash-based associative container.
  template<typename Key,
	   typename Mapped,
	   typename Hash_Fn,
	   typename Eq_Fn,
	   typename Resize_Policy,
	   bool Store_Hash,
	   typename Tag,
	   typename Policy_TL,
	   typename Allocator>
  class basic_hash_table : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC base_type;

  public:
    virtual
    ~basic_hash_table() { }

  protected:
#define PB_DS_CLASS_NAME basic_hash_table
#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
#undef PB_DS_CLASS_NAME

  private:
    basic_hash_table&
    operator=(const base_type&);
  };

#undef PB_DS_BASE_C_DEC

#define PB_DS_BASE_C_DEC \
  basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
		   cc_hash_tag,	\
	  typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>

  // A concrete collision-chaining hash-based associative container.
  template<typename Key,
	   typename Mapped,
	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
	   typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
	   bool Store_Hash = detail::default_store_hash,
	   typename Allocator = std::allocator<char> >
  class cc_hash_table :  public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC 	base_type;

  public:
    typedef Hash_Fn 		hash_fn;
    typedef Eq_Fn 		eq_fn;
    typedef Resize_Policy 	resize_policy;
    typedef Comb_Hash_Fn 	comb_hash_fn;

    // Default constructor.
    cc_hash_table() { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the Hash_Fn object of the container object.
    cc_hash_table(const hash_fn& h)
    : base_type(h) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, and
    // r_eq_fn will be copied by the eq_fn object of the container
    // object.
    cc_hash_table(const hash_fn& h, const eq_fn& e)
    : base_type(h, e) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, r_eq_fn
    // will be copied by the eq_fn object of the container object, and
    // r_comb_hash_fn will be copied by the comb_hash_fn object of the
    // container object.
    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
    : base_type(h, e, ch) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, r_eq_fn
    // will be copied by the eq_fn object of the container object,
    // r_comb_hash_fn will be copied by the comb_hash_fn object of the
    // container object, and r_resize_policy will be copied by the
    // resize_policy object of the container object.
    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
		  const resize_policy& rp)
    : base_type(h, e, ch, rp) { }

    // Constructor taking __iterators to a range of value_types. The
    // value_types between first_it and last_it will be inserted into
    // the container object.
    template<typename It>
    cc_hash_table(It first, It last)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object.
    template<typename It>
    cc_hash_table(It first, It last, const hash_fn& h)
    : base_type(h)
    { copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // and r_eq_fn will be copied by the eq_fn object of the container
    // object.
    template<typename It>
    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
    : base_type(h, e)
    { copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // r_eq_fn will be copied by the eq_fn object of the container
    // object, and r_comb_hash_fn will be copied by the comb_hash_fn
    // object of the container object.
    template<typename It>
    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
		  const comb_hash_fn& ch)
    : base_type(h, e, ch)
    { copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // r_eq_fn will be copied by the eq_fn object of the container
    // object, r_comb_hash_fn will be copied by the comb_hash_fn
    // object of the container object, and r_resize_policy will be
    // copied by the resize_policy object of the container object.
    template<typename It>
    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
		  const comb_hash_fn& ch, const resize_policy& rp)
    : base_type(h, e, ch, rp)
    { copy_from_range(first, last); }

    cc_hash_table(const cc_hash_table& other)
    : base_type((const base_type&)other)
    { }

    virtual
    ~cc_hash_table() { }

    cc_hash_table&
    operator=(const cc_hash_table& other)
    {
      if (this != &other)
	{
	  cc_hash_table tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(cc_hash_table& other)
    { base_type::swap(other); }
  };

#undef PB_DS_BASE_C_DEC

#define PB_DS_BASE_C_DEC \
  basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
		   gp_hash_tag, \
		   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>

  // A concrete general-probing hash-based associative container.
  template<typename Key,
	   typename Mapped,
	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
	   typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
	   typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
	   bool Store_Hash = detail::default_store_hash,
	   typename Allocator = std::allocator<char> >
  class gp_hash_table : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC 	base_type;

  public:
    typedef Hash_Fn 		hash_fn;
    typedef Eq_Fn 		eq_fn;
    typedef Comb_Probe_Fn	comb_probe_fn;
    typedef Probe_Fn 		probe_fn;
    typedef Resize_Policy 	resize_policy;

    // Default constructor.
    gp_hash_table() { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object.
    gp_hash_table(const hash_fn& h)
    : base_type(h) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, and
    // r_eq_fn will be copied by the eq_fn object of the container
    // object.
    gp_hash_table(const hash_fn& h, const eq_fn& e)
    : base_type(h, e) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, r_eq_fn
    // will be copied by the eq_fn object of the container object, and
    // r_comb_probe_fn will be copied by the comb_probe_fn object of
    // the container object.
    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
    : base_type(h, e, cp) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, r_eq_fn
    // will be copied by the eq_fn object of the container object,
    // r_comb_probe_fn will be copied by the comb_probe_fn object of
    // the container object, and r_probe_fn will be copied by the
    // probe_fn object of the container object.
    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
		  const probe_fn& p)
    : base_type(h, e, cp, p) { }

    // Constructor taking some policy objects. r_hash_fn will be
    // copied by the hash_fn object of the container object, r_eq_fn
    // will be copied by the eq_fn object of the container object,
    // r_comb_probe_fn will be copied by the comb_probe_fn object of
    // the container object, r_probe_fn will be copied by the probe_fn
    // object of the container object, and r_resize_policy will be
    // copied by the Resize_Policy object of the container object.
    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
		  const probe_fn& p, const resize_policy& rp)
    : base_type(h, e, cp, p, rp) { }

    // Constructor taking __iterators to a range of value_types. The
    // value_types between first_it and last_it will be inserted into
    // the container object.
    template<typename It>
    gp_hash_table(It first, It last)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object.
    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h)
    : base_type(h)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // and r_eq_fn will be copied by the eq_fn object of the container
    // object.
    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
    : base_type(h, e)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // r_eq_fn will be copied by the eq_fn object of the container
    // object, and r_comb_probe_fn will be copied by the comb_probe_fn
    // object of the container object.
    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
		  const comb_probe_fn& cp)
    : base_type(h, e, cp)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // r_eq_fn will be copied by the eq_fn object of the container
    // object, r_comb_probe_fn will be copied by the comb_probe_fn
    // object of the container object, and r_probe_fn will be copied
    // by the probe_fn object of the container object.
    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
		  const comb_probe_fn& cp, const probe_fn& p)
    : base_type(h, e, cp, p)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object. r_hash_fn
    // will be copied by the hash_fn object of the container object,
    // r_eq_fn will be copied by the eq_fn object of the container
    // object, r_comb_probe_fn will be copied by the comb_probe_fn
    // object of the container object, r_probe_fn will be copied by
    // the probe_fn object of the container object, and
    // r_resize_policy will be copied by the resize_policy object of
    // the container object.
    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
		  const comb_probe_fn& cp, const probe_fn& p,
		  const resize_policy& rp)
    : base_type(h, e, cp, p, rp)
    { base_type::copy_from_range(first, last); }

    gp_hash_table(const gp_hash_table& other)
    : base_type((const base_type&)other)
    { }

    virtual
    ~gp_hash_table() { }

    gp_hash_table&
    operator=(const gp_hash_table& other)
    {
      if (this != &other)
	{
	  gp_hash_table tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(gp_hash_table& other)
    { base_type::swap(other); }
  };

#undef PB_DS_BASE_C_DEC

#define PB_DS_BASE_C_DEC \
  container_base<Key, Mapped, Tag, Policy_Tl, Allocator>

  // An abstract basic tree-like (tree, trie) associative container.
  template<typename Key, typename Mapped, typename Tag,
	   typename Node_Update, typename Policy_Tl, typename Allocator>
  class basic_tree : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC 	base_type;

  public:
    typedef Node_Update 	node_update;

    virtual
    ~basic_tree() { }

  protected:
#define PB_DS_CLASS_NAME 		basic_tree
#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
#undef PB_DS_CLASS_NAME
  };

#undef PB_DS_BASE_C_DEC

#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>

#define PB_DS_BASE_C_DEC \
  basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
	     typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>

  // A concrete basic tree-based associative container.
  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
	   typename Tag = rb_tree_tag,
	   template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
  class Node_Update = pb_ds::null_tree_node_update,
	   typename Allocator = std::allocator<char> >
  class tree : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC 	base_type;

  public:
    // Comparison functor type.
    typedef Cmp_Fn 		cmp_fn;

    tree() { }

    // Constructor taking some policy objects. r_cmp_fn will be copied
    // by the Cmp_Fn object of the container object.
    tree(const cmp_fn& c)
    : base_type(c) { }

    // Constructor taking __iterators to a range of value_types. The
    // value_types between first_it and last_it will be inserted into
    // the container object.
    template<typename It>
    tree(It first, It last)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects The value_types between first_it and
    // last_it will be inserted into the container object. r_cmp_fn
    // will be copied by the cmp_fn object of the container object.
    template<typename It>
    tree(It first, It last, const cmp_fn& c)
      : base_type(c)
    { base_type::copy_from_range(first, last); }

    tree(const tree& other)
    : base_type((const base_type&)other) { }

    virtual
    ~tree() { }

    tree&
    operator=(const tree& other)
    {
      if (this != &other)
	{
	  tree tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(tree& other)
    { base_type::swap(other); }
  };

#undef PB_DS_BASE_C_DEC
#undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC

#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
  detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>

#define PB_DS_BASE_C_DEC \
  basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
	     typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>

  // A concrete basic trie-based associative container.
  template<typename Key,
	   typename Mapped,
	   typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
	   typename Tag = pat_trie_tag,
	   template<typename Const_Node_Iterator,
		    typename Node_Iterator,
		    typename E_Access_Traits_,
		    typename Allocator_>
  class Node_Update = null_trie_node_update,
	   typename Allocator = std::allocator<char> >
  class trie : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC base_type;

  public:
    // Element access traits type.
    typedef E_Access_Traits e_access_traits;

    trie() { }

    // Constructor taking some policy objects. r_e_access_traits will
    // be copied by the E_Access_Traits object of the container
    // object.
    trie(const e_access_traits& t)
    : base_type(t) { }

    // Constructor taking __iterators to a range of value_types. The
    // value_types between first_it and last_it will be inserted into
    // the container object.
    template<typename It>
    trie(It first, It last)
    { base_type::copy_from_range(first, last); }

    // Constructor taking __iterators to a range of value_types and
    // some policy objects. The value_types between first_it and
    // last_it will be inserted into the container object.
    template<typename It>
    trie(It first, It last, const e_access_traits& t)
    : base_type(t)
    { base_type::copy_from_range(first, last); }

    trie(const trie& other)
    : base_type((const base_type&)other) { }

    virtual
    ~trie() { }

    trie&
    operator=(const trie& other)
    {
      if (this != &other)
	{
	  trie tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(trie& other)
    { base_type::swap(other); }
  };

#undef PB_DS_BASE_C_DEC
#undef PB_DS_TRIE_NODE_AND_ITS_TRAITS

#define PB_DS_BASE_C_DEC \
  container_base<Key, Mapped, list_update_tag, \
		 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>

  // A list-update based associative container.
  template<typename Key,
	   typename Mapped,
	   class Eq_Fn = typename detail::default_eq_fn<Key>::type,
	   class Update_Policy = detail::default_update_policy::type,
	   class Allocator = std::allocator<char> >
  class list_update : public PB_DS_BASE_C_DEC
  {
  private:
    typedef PB_DS_BASE_C_DEC 	base_type;

  public:
    typedef Eq_Fn 		eq_fn;
    typedef Update_Policy 	update_policy;
    typedef Allocator 		allocator;

    list_update() { }

    // Constructor taking __iterators to a range of value_types. The
    // value_types between first_it and last_it will be inserted into
    // the container object.
    template<typename It>
    list_update(It first, It last)
    { base_type::copy_from_range(first, last); }

    list_update(const list_update& other)
    : base_type((const base_type&)other) { }

    virtual
    ~list_update() { }

    list_update&
    operator=(const list_update& other)
    {
      if (this !=& other)
	{
	  list_update tmp(other);
	  swap(tmp);
	}
      return *this;
    }

    void
    swap(list_update& other)
    { base_type::swap(other); }
  };

#undef PB_DS_BASE_C_DEC

} // namespace pb_ds

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file basic_tree_policy_base.hpp
 * Contains a base class for tree_like policies.
 */

#ifndef PB_DS_TREE_LIKE_POLICY_BASE_HPP
#define PB_DS_TREE_LIKE_POLICY_BASE_HPP

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_C_DEC						\
    basic_tree_policy_base<						\
							Const_Node_Iterator, \
							Node_Iterator,	\
							Allocator>

    template<typename Const_Node_Iterator,
	     typename Node_Iterator,
	     typename Allocator>
    struct basic_tree_policy_base
    {
    protected:
      typedef typename Node_Iterator::value_type it_type;

      typedef typename std::iterator_traits< it_type>::value_type value_type;

      typedef typename value_type::first_type key_type;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	key_type>::type>::other::const_reference
      const_key_reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::const_reference
      const_reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::reference
      reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::const_pointer
      const_pointer;

      static inline const_key_reference
      extract_key(const_reference r_val)
      {
	return (r_val.first);
      }

      virtual it_type
      end() = 0;

      it_type
      end_iterator() const
      {
	return (const_cast<PB_DS_CLASS_C_DEC* >(this)->end());
      }

      virtual
      ~basic_tree_policy_base()
      { }
    };

    template<typename Const_Node_Iterator, typename Allocator>
    struct basic_tree_policy_base<
      Const_Node_Iterator,
      Const_Node_Iterator,
      Allocator>
    {
    protected:
      typedef typename Const_Node_Iterator::value_type it_type;

      typedef typename std::iterator_traits< it_type>::value_type value_type;

      typedef value_type key_type;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	key_type>::type>::other::const_reference
      const_key_reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::const_reference
      const_reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::reference
      reference;

      typedef
      typename Allocator::template rebind<
	typename remove_const<
	value_type>::type>::other::const_pointer
      const_pointer;

      static inline const_key_reference
      extract_key(const_reference r_val)
      {
	return (r_val);
      }

      virtual it_type
      end() const = 0;

      it_type
      end_iterator() const
      {
	return (end());
      }

      virtual
      ~basic_tree_policy_base()
      { }
    };

#undef PB_DS_CLASS_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_TREE_LIKE_POLICY_BASE_HPP


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file null_node_metadata.hpp
 * Contains an implementation class for tree-like classes.
 */

#ifndef PB_DS_NULL_NODE_METADATA_HPP
#define PB_DS_NULL_NODE_METADATA_HPP

#include <ext/pb_ds/detail/types_traits.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Key, class Data, class Allocator>
    struct dumconst_node_iterator
    {
    private:
      typedef typename types_traits<Key, Data, Allocator, false>::pointer const_iterator;

    public:
      typedef const_iterator value_type;
      typedef const_iterator const_reference;
      typedef const_reference reference;
    };

    struct null_node_metadata
    { };
  } // namespace detail
} // namespace pb_ds

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file traits.hpp
 * Contains an implementation class for tree-like classes.
 */

#ifndef PB_DS_NODE_AND_IT_TRAITS_HPP
#define PB_DS_NODE_AND_IT_TRAITS_HPP

#include <ext/pb_ds/detail/types_traits.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/traits.hpp>
#include <ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp>
#include <ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Key,
	     typename Data,
	     class Cmp_Fn,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class Cmp_Fn_,
		      class Allocator>
    class Node_Update,
	     class Tag,
	     class Allocator>
    struct tree_traits;

    template<typename Key,
	     typename Data,
	     class E_Access_Traits,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class E_Access_Traits_,
		      class Allocator>
    class Node_Update,
	     class Tag,
	     class Allocator>
    struct trie_traits;

  } // namespace detail
} // namespace pb_ds

#include <ext/pb_ds/detail/rb_tree_map_/traits.hpp>
#include <ext/pb_ds/detail/splay_tree_/traits.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/traits.hpp>
#include <ext/pb_ds/detail/pat_trie_/traits.hpp>

#endif // #ifndef PB_DS_NODE_AND_IT_TRAITS_HPP


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file basic_types.hpp
 * Contains basic types used by containers.
 */

#ifndef PB_DS_BASIC_TYPES_HPP
#define PB_DS_BASIC_TYPES_HPP

#include <algorithm>
#include <utility>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Key, typename Mapped, typename Allocator, bool Store_Hash>
    struct value_type_base;

    /**
     * Specialization of value_type_base for the case where the hash value
     * is not stored alongside each value.
     **/
    template<typename Key, typename Mapped, typename Allocator>
    struct value_type_base<Key, Mapped, Allocator, false>
    {
      typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
      typedef typename mapped_type_allocator::value_type mapped_type;
      typedef typename mapped_type_allocator::pointer mapped_pointer;
      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
      typedef typename mapped_type_allocator::reference mapped_reference;
      typedef typename mapped_type_allocator::const_reference const_mapped_reference;

      typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
      typedef typename value_type_allocator::value_type value_type;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;

      struct stored_value_type
      {
	value_type m_value;
      };
    };

    /**
     * Specialization of value_type_base for the case where the hash value
     * is stored alongside each value.
     **/
    template<typename Key, typename Mapped, typename Allocator>
    struct value_type_base<Key, Mapped, Allocator, true>
    {
      typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
      typedef typename mapped_type_allocator::value_type mapped_type;
      typedef typename mapped_type_allocator::pointer mapped_pointer;
      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
      typedef typename mapped_type_allocator::reference mapped_reference;
      typedef typename mapped_type_allocator::const_reference const_mapped_reference;

      typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
      typedef typename value_type_allocator::value_type value_type;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;

      struct stored_value_type
      {
	value_type m_value;
	typename Allocator::size_type m_hash;
      };
    };

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Allocator>

#define PB_DS_CLASS_C_DEC \
    value_type_base<Key, null_mapped_type, Allocator, false>

    /**
     * Specialization of value_type_base for the case where the hash value
     * is not stored alongside each value.
     **/
    template<typename Key, typename Allocator>
    struct value_type_base<Key, null_mapped_type, Allocator, false>
    {
      typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
      typedef typename mapped_type_allocator::value_type mapped_type;
      typedef typename mapped_type_allocator::pointer mapped_pointer;
      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
      typedef typename mapped_type_allocator::reference mapped_reference;
      typedef typename mapped_type_allocator::const_reference const_mapped_reference;

      typedef Key value_type;

      typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;

      struct stored_value_type
      {
	value_type m_value;
      };

      static null_mapped_type s_null_mapped;
    };

    PB_DS_CLASS_T_DEC
    null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Allocator>

#define PB_DS_CLASS_C_DEC \
    value_type_base<Key, null_mapped_type, Allocator, true>

    /**
     * Specialization of value_type_base for the case where the hash value
     * is stored alongside each value.
     **/
    template<typename Key, typename Allocator>
    struct value_type_base<Key, null_mapped_type, Allocator, true>
    {
      typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
      typedef typename mapped_type_allocator::value_type mapped_type;
      typedef typename mapped_type_allocator::pointer mapped_pointer;
      typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
      typedef typename mapped_type_allocator::reference mapped_reference;
      typedef typename mapped_type_allocator::const_reference const_mapped_reference;

      typedef Key value_type;

      typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;

      struct stored_value_type
      {
	value_type m_value;
	typename Allocator::size_type m_hash;
      };

      static null_mapped_type s_null_mapped;
    };

    PB_DS_CLASS_T_DEC
    null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

    template<typename Key, typename Mapped>
    struct no_throw_copies
    {
      typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator;
    };

    template<typename Key>
    struct no_throw_copies<Key, null_mapped_type>
    {
      typedef integral_constant<int, is_simple<Key>::value> indicator;
    };
  } // namespace detail
} // namespace pb_ds

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file bin_search_tree_.hpp
 * Contains an implementation class for bin_search_tree_.
 */
/*
 * This implementation uses an idea from the SGI STL (using a "header" node
 *    which is needed for efficient iteration).
 */

#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
#include <ext/pb_ds/detail/types_traits.hpp>
#include <ext/pb_ds/detail/map_debug_base.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/tree_trace_base.hpp>
#include <utility>
#include <functional>
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC						\
    template<typename Key, typename Mapped, class Cmp_Fn,		\
	     class Node_And_It_Traits, class Allocator>

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME			\
    bin_search_tree_data_
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME			\
    bin_search_tree_no_data_
#endif

#define PB_DS_CLASS_C_DEC						\
    PB_DS_CLASS_NAME<							\
						Key,			\
						Mapped,			\
						Cmp_Fn,			\
						Node_And_It_Traits,	\
						Allocator>

#define PB_DS_TYPES_TRAITS_C_DEC				\
    types_traits<				\
						Key,		\
						Mapped,		\
						Allocator,	\
						false>

#ifdef _GLIBCXX_DEBUG
#define PB_DS_MAP_DEBUG_BASE_C_DEC					\
    map_debug_base<Key,	eq_by_less<Key, Cmp_Fn>, \
	      typename Allocator::template rebind<Key>::other::const_reference>
#endif

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#define PB_DS_V2S(X) (X).second
#define PB_DS_EP2VP(X)& ((X)->m_value)
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#define PB_DS_V2S(X) Mapped_Data()
#define PB_DS_EP2VP(X)& ((X)->m_value.first)
#endif

#ifdef PB_DS_TREE_TRACE
#define PB_DS_TREE_TRACE_BASE_C_DEC					\
    tree_trace_base<							\
									typename Node_And_It_Traits::const_node_iterator, \
									typename Node_And_It_Traits::node_iterator, \
									Cmp_Fn,	\
									true, \
									Allocator>
#endif

    /**
     * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
     **/
    template<typename Key,
	     typename Mapped,
	     class Cmp_Fn,
	     class Node_And_It_Traits,
	     class Allocator>
    class PB_DS_CLASS_NAME :
#ifdef _GLIBCXX_DEBUG
      public PB_DS_MAP_DEBUG_BASE_C_DEC,
#endif
#ifdef PB_DS_TREE_TRACE
      public PB_DS_TREE_TRACE_BASE_C_DEC,
#endif
      public Cmp_Fn,
      public PB_DS_TYPES_TRAITS_C_DEC,
      public Node_And_It_Traits::node_update
    {

    protected:
      typedef
      typename Allocator::template rebind<
      typename Node_And_It_Traits::node>::other
      node_allocator;

      typedef typename node_allocator::value_type node;

      typedef typename node_allocator::pointer node_pointer;

      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;

      typedef
      typename Node_And_It_Traits::null_node_update_pointer
      null_node_update_pointer;

    private:
      typedef cond_dealtor< node, Allocator> cond_dealtor_t;

#ifdef _GLIBCXX_DEBUG
      typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
#endif

    public:

      typedef typename Allocator::size_type size_type;

      typedef typename Allocator::difference_type difference_type;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
      const_key_pointer;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
      const_key_reference;

#ifdef PB_DS_DATA_TRUE_INDICATOR
      typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
      mapped_pointer;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
      const_mapped_pointer;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
      mapped_reference;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
      const_mapped_reference;
#endif

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;

      typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;

      typedef
      typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
      const_reference;

      typedef
      typename Node_And_It_Traits::const_point_iterator
      const_point_iterator;

      typedef const_point_iterator const_iterator;

      typedef typename Node_And_It_Traits::point_iterator point_iterator;

      typedef point_iterator iterator;

      typedef
      typename Node_And_It_Traits::const_reverse_iterator
      const_reverse_iterator;

      typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;

      typedef
      typename Node_And_It_Traits::const_node_iterator
      const_node_iterator;

      typedef typename Node_And_It_Traits::node_iterator node_iterator;

      typedef Cmp_Fn cmp_fn;

      typedef Allocator allocator;

      typedef typename Node_And_It_Traits::node_update node_update;

    public:

      PB_DS_CLASS_NAME();

      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);

      PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);

      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      ~PB_DS_CLASS_NAME();

      inline bool
      empty() const;

      inline size_type
      size() const;

      inline size_type
      max_size() const;

      Cmp_Fn&
      get_cmp_fn();

      const Cmp_Fn&
      get_cmp_fn() const;

      inline point_iterator
      lower_bound(const_key_reference r_key);

      inline const_point_iterator
      lower_bound(const_key_reference r_key) const;

      inline point_iterator
      upper_bound(const_key_reference r_key);

      inline const_point_iterator
      upper_bound(const_key_reference r_key) const;

      inline point_iterator
      find(const_key_reference r_key);

      inline const_point_iterator
      find(const_key_reference r_key) const;

      inline iterator
      begin();

      inline const_iterator
      begin() const;

      inline iterator
      end();

      inline const_iterator
      end() const;

      inline reverse_iterator
      rbegin();

      inline const_reverse_iterator
      rbegin() const;

      inline reverse_iterator
      rend();

      inline const_reverse_iterator
      rend() const;

      inline const_node_iterator
      node_begin() const;

      inline node_iterator
      node_begin();

      inline const_node_iterator
      node_end() const;

      inline node_iterator
      node_end();

      void
      clear();

    protected:

      void
      value_swap(PB_DS_CLASS_C_DEC& other);

      void
      initialize_min_max();

      inline iterator
      insert_imp_empty(const_reference r_value);

      inline iterator
      insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);

      inline node_pointer
      get_new_node_for_leaf_insert(const_reference r_val, false_type);

      inline node_pointer
      get_new_node_for_leaf_insert(const_reference r_val, true_type);

      inline void
      actual_erase_node(node_pointer p_nd);

      inline std::pair<node_pointer, bool>
      erase(node_pointer p_nd);

      inline void
      update_min_max_for_erased_node(node_pointer p_nd);

      static void
      clear_imp(node_pointer p_nd);

      inline std::pair<
	point_iterator,
	bool>
      insert_leaf(const_reference r_value);

      inline void
      rotate_left(node_pointer p_x);

      inline void
      rotate_right(node_pointer p_y);

      inline void
      rotate_parent(node_pointer p_nd);

      inline void
      apply_update(node_pointer p_nd, null_node_update_pointer);

      template<typename Node_Update_>
      inline void
      apply_update(node_pointer p_nd, Node_Update_* p_update);

      inline void
      update_to_top(node_pointer p_nd, null_node_update_pointer);

      template<typename Node_Update_>
      inline void
      update_to_top(node_pointer p_nd, Node_Update_* p_update);

      bool
      join_prep(PB_DS_CLASS_C_DEC& other);

      void
      join_finish(PB_DS_CLASS_C_DEC& other);

      bool
      split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);

      void
      split_finish(PB_DS_CLASS_C_DEC& other);

      size_type
      recursive_count(node_pointer p_nd) const;

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;

      void
      structure_only_assert_valid() const;

      void
      assert_node_consistent(const node_pointer p_nd) const;
#endif

    private:
#ifdef _GLIBCXX_DEBUG
      void
      assert_iterators() const;

      void
      assert_consistent_with_debug_base() const;

      void
      assert_node_consistent_with_left(const node_pointer p_nd) const;

      void
      assert_node_consistent_with_right(const node_pointer p_nd) const;

      void
      assert_consistent_with_debug_base(const node_pointer p_nd) const;

      void
      assert_min() const;

      void
      assert_min_imp(const node_pointer p_nd) const;

      void
      assert_max() const;

      void
      assert_max_imp(const node_pointer p_nd) const;

      void
      assert_size() const;

      typedef std::pair< const_pointer, const_pointer> node_consistent_t;

      node_consistent_t
      assert_node_consistent_(const node_pointer p_nd) const;
#endif

      void
      initialize();

      node_pointer
      recursive_copy_node(const node_pointer p_nd);

    protected:
      node_pointer m_p_head;

      size_type m_size;

      static node_allocator s_node_allocator;
    };

#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>

#undef PB_DS_CLASS_C_DEC

#undef PB_DS_CLASS_T_DEC

#undef PB_DS_CLASS_NAME

#undef PB_DS_TYPES_TRAITS_C_DEC

#undef PB_DS_MAP_DEBUG_BASE_C_DEC

#ifdef PB_DS_TREE_TRACE
#undef PB_DS_TREE_TRACE_BASE_C_DEC
#endif

#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S

  } // namespace detail
} // namespace pb_ds