1    	// Allocator traits -*- C++ -*-
2    	
3    	// Copyright (C) 2011-2017 Free Software Foundation, Inc.
4    	//
5    	// This file is part of the GNU ISO C++ Library.  This library is free
6    	// software; you can redistribute it and/or modify it under the
7    	// terms of the GNU General Public License as published by the
8    	// Free Software Foundation; either version 3, or (at your option)
9    	// any later version.
10   	
11   	// This library is distributed in the hope that it will be useful,
12   	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13   	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   	// GNU General Public License for more details.
15   	
16   	// Under Section 7 of GPL version 3, you are granted additional
17   	// permissions described in the GCC Runtime Library Exception, version
18   	// 3.1, as published by the Free Software Foundation.
19   	
20   	// You should have received a copy of the GNU General Public License and
21   	// a copy of the GCC Runtime Library Exception along with this program;
22   	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23   	// <http://www.gnu.org/licenses/>.
24   	
25   	/** @file bits/alloc_traits.h
26   	 *  This is an internal header file, included by other library headers.
27   	 *  Do not attempt to use it directly. @headername{memory}
28   	 */
29   	
30   	#ifndef _ALLOC_TRAITS_H
31   	#define _ALLOC_TRAITS_H 1
32   	
33   	#if __cplusplus >= 201103L
34   	
35   	#include <bits/memoryfwd.h>
36   	#include <bits/ptr_traits.h>
37   	#include <ext/numeric_traits.h>
38   	
39   	#define __cpp_lib_allocator_traits_is_always_equal 201411
40   	
41   	namespace std _GLIBCXX_VISIBILITY(default)
42   	{
43   	_GLIBCXX_BEGIN_NAMESPACE_VERSION
44   	
45   	  struct __allocator_traits_base
46   	  {
47   	    template<typename _Tp, typename _Up, typename = void>
48   	      struct __rebind : __replace_first_arg<_Tp, _Up> { };
49   	
50   	    template<typename _Tp, typename _Up>
51   	      struct __rebind<_Tp, _Up,
52   			      __void_t<typename _Tp::template rebind<_Up>::other>>
53   	      { using type = typename _Tp::template rebind<_Up>::other; };
54   	
55   	  protected:
56   	    template<typename _Tp>
57   	      using __pointer = typename _Tp::pointer;
58   	    template<typename _Tp>
59   	      using __c_pointer = typename _Tp::const_pointer;
60   	    template<typename _Tp>
61   	      using __v_pointer = typename _Tp::void_pointer;
62   	    template<typename _Tp>
63   	      using __cv_pointer = typename _Tp::const_void_pointer;
64   	    template<typename _Tp>
65   	      using __pocca = typename _Tp::propagate_on_container_copy_assignment;
66   	    template<typename _Tp>
67   	      using __pocma = typename _Tp::propagate_on_container_move_assignment;
68   	    template<typename _Tp>
69   	      using __pocs = typename _Tp::propagate_on_container_swap;
70   	    template<typename _Tp>
71   	      using __equal = typename _Tp::is_always_equal;
72   	  };
73   	
74   	  template<typename _Alloc, typename _Up>
75   	    using __alloc_rebind
76   	      = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
77   	
78   	  /**
79   	   * @brief  Uniform interface to all allocator types.
80   	   * @ingroup allocators
81   	  */
82   	  template<typename _Alloc>
83   	    struct allocator_traits : __allocator_traits_base
84   	    {
85   	      /// The allocator type
86   	      typedef _Alloc allocator_type;
87   	      /// The allocated type
88   	      typedef typename _Alloc::value_type value_type;
89   	
90   	      /**
91   	       * @brief   The allocator's pointer type.
92   	       *
93   	       * @c Alloc::pointer if that type exists, otherwise @c value_type*
94   	      */
95   	      using pointer = __detected_or_t<value_type*, __pointer, _Alloc>;
96   	
97   	    private:
98   	      // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp>
99   	      template<template<typename> class _Func, typename _Tp, typename = void>
100  		struct _Ptr
101  		{
102  		  using type = typename pointer_traits<pointer>::template rebind<_Tp>;
103  		};
104  	
105  	      template<template<typename> class _Func, typename _Tp>
106  		struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>>
107  		{
108  		  using type = _Func<_Alloc>;
109  		};
110  	
111  	      // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type
112  	      template<typename _A2, typename _PtrT, typename = void>
113  		struct _Diff
114  		{ using type = typename pointer_traits<_PtrT>::difference_type; };
115  	
116  	      template<typename _A2, typename _PtrT>
117  		struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>>
118  		{ using type = typename _A2::difference_type; };
119  	
120  	      // Select _A2::size_type or make_unsigned<_DiffT>::type
121  	      template<typename _A2, typename _DiffT, typename = void>
122  		struct _Size : make_unsigned<_DiffT> { };
123  	
124  	      template<typename _A2, typename _DiffT>
125  		struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>>
126  		{ using type = typename _A2::size_type; };
127  	
128  	    public:
129  	      /**
130  	       * @brief   The allocator's const pointer type.
131  	       *
132  	       * @c Alloc::const_pointer if that type exists, otherwise
133  	       * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
134  	      */
135  	      using const_pointer = typename _Ptr<__c_pointer, const value_type>::type;
136  	
137  	      /**
138  	       * @brief   The allocator's void pointer type.
139  	       *
140  	       * @c Alloc::void_pointer if that type exists, otherwise
141  	       * <tt> pointer_traits<pointer>::rebind<void> </tt>
142  	      */
143  	      using void_pointer = typename _Ptr<__v_pointer, void>::type;
144  	
145  	      /**
146  	       * @brief   The allocator's const void pointer type.
147  	       *
148  	       * @c Alloc::const_void_pointer if that type exists, otherwise
149  	       * <tt> pointer_traits<pointer>::rebind<const void> </tt>
150  	      */
151  	      using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type;
152  	
153  	      /**
154  	       * @brief   The allocator's difference type
155  	       *
156  	       * @c Alloc::difference_type if that type exists, otherwise
157  	       * <tt> pointer_traits<pointer>::difference_type </tt>
158  	      */
159  	      using difference_type = typename _Diff<_Alloc, pointer>::type;
160  	
161  	      /**
162  	       * @brief   The allocator's size type
163  	       *
164  	       * @c Alloc::size_type if that type exists, otherwise
165  	       * <tt> make_unsigned<difference_type>::type </tt>
166  	      */
167  	      using size_type = typename _Size<_Alloc, difference_type>::type;
168  	
169  	      /**
170  	       * @brief   How the allocator is propagated on copy assignment
171  	       *
172  	       * @c Alloc::propagate_on_container_copy_assignment if that type exists,
173  	       * otherwise @c false_type
174  	      */
175  	      using propagate_on_container_copy_assignment
176  		= __detected_or_t<false_type, __pocca, _Alloc>;
177  	
178  	      /**
179  	       * @brief   How the allocator is propagated on move assignment
180  	       *
181  	       * @c Alloc::propagate_on_container_move_assignment if that type exists,
182  	       * otherwise @c false_type
183  	      */
184  	      using propagate_on_container_move_assignment
185  		= __detected_or_t<false_type, __pocma, _Alloc>;
186  	
187  	      /**
188  	       * @brief   How the allocator is propagated on swap
189  	       *
190  	       * @c Alloc::propagate_on_container_swap if that type exists,
191  	       * otherwise @c false_type
192  	      */
193  	      using propagate_on_container_swap
194  		= __detected_or_t<false_type, __pocs, _Alloc>;
195  	
196  	      /**
197  	       * @brief   Whether all instances of the allocator type compare equal.
198  	       *
199  	       * @c Alloc::is_always_equal if that type exists,
200  	       * otherwise @c is_empty<Alloc>::type
201  	      */
202  	      using is_always_equal
203  		= __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>;
204  	
205  	      template<typename _Tp>
206  		using rebind_alloc = __alloc_rebind<_Alloc, _Tp>;
207  	      template<typename _Tp>
208  		using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
209  	
210  	    private:
211  	      template<typename _Alloc2>
212  		static auto
213  		_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
214  		-> decltype(__a.allocate(__n, __hint))
215  		{ return __a.allocate(__n, __hint); }
216  	
217  	      template<typename _Alloc2>
218  		static pointer
219  		_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
220  		{ return __a.allocate(__n); }
221  	
222  	      template<typename _Tp, typename... _Args>
223  		struct __construct_helper
224  		{
225  		  template<typename _Alloc2,
226  		    typename = decltype(std::declval<_Alloc2*>()->construct(
227  			  std::declval<_Tp*>(), std::declval<_Args>()...))>
228  		    static true_type __test(int);
229  	
230  		  template<typename>
231  		    static false_type __test(...);
232  	
233  		  using type = decltype(__test<_Alloc>(0));
234  		};
235  	
236  	      template<typename _Tp, typename... _Args>
237  		using __has_construct
238  		  = typename __construct_helper<_Tp, _Args...>::type;
239  	
240  	      template<typename _Tp, typename... _Args>
241  		static _Require<__has_construct<_Tp, _Args...>>
242  		_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
243  		{ __a.construct(__p, std::forward<_Args>(__args)...); }
244  	
245  	      template<typename _Tp, typename... _Args>
246  		static
247  		_Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
248  				       is_constructible<_Tp, _Args...>>>
249  		_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
250  		{ ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
251  	
252  	      template<typename _Alloc2, typename _Tp>
253  		static auto
254  		_S_destroy(_Alloc2& __a, _Tp* __p, int)
255  		-> decltype(__a.destroy(__p))
256  		{ __a.destroy(__p); }
257  	
258  	      template<typename _Alloc2, typename _Tp>
259  		static void
260  		_S_destroy(_Alloc2&, _Tp* __p, ...)
261  		{ __p->~_Tp(); }
262  	
263  	      template<typename _Alloc2>
264  		static auto
265  		_S_max_size(_Alloc2& __a, int)
266  		-> decltype(__a.max_size())
267  		{ return __a.max_size(); }
268  	
269  	      template<typename _Alloc2>
270  		static size_type
271  		_S_max_size(_Alloc2&, ...)
272  		{
273  		  // _GLIBCXX_RESOLVE_LIB_DEFECTS
274  		  // 2466. allocator_traits::max_size() default behavior is incorrect
275  		  return __gnu_cxx::__numeric_traits<size_type>::__max
276  		    / sizeof(value_type);
277  		}
278  	
279  	      template<typename _Alloc2>
280  		static auto
281  		_S_select(_Alloc2& __a, int)
282  		-> decltype(__a.select_on_container_copy_construction())
283  		{ return __a.select_on_container_copy_construction(); }
284  	
285  	      template<typename _Alloc2>
286  		static _Alloc2
287  		_S_select(_Alloc2& __a, ...)
288  		{ return __a; }
289  	
290  	    public:
291  	
292  	      /**
293  	       *  @brief  Allocate memory.
294  	       *  @param  __a  An allocator.
295  	       *  @param  __n  The number of objects to allocate space for.
296  	       *
297  	       *  Calls @c a.allocate(n)
298  	      */
299  	      static pointer
300  	      allocate(_Alloc& __a, size_type __n)
301  	      { return __a.allocate(__n); }
302  	
303  	      /**
304  	       *  @brief  Allocate memory.
305  	       *  @param  __a  An allocator.
306  	       *  @param  __n  The number of objects to allocate space for.
307  	       *  @param  __hint Aid to locality.
308  	       *  @return Memory of suitable size and alignment for @a n objects
309  	       *          of type @c value_type
310  	       *
311  	       *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
312  	       *  well-formed, otherwise returns @c a.allocate(n)
313  	      */
314  	      static pointer
315  	      allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
316  	      { return _S_allocate(__a, __n, __hint, 0); }
317  	
318  	      /**
319  	       *  @brief  Deallocate memory.
320  	       *  @param  __a  An allocator.
321  	       *  @param  __p  Pointer to the memory to deallocate.
322  	       *  @param  __n  The number of objects space was allocated for.
323  	       *
324  	       *  Calls <tt> a.deallocate(p, n) </tt>
325  	      */
326  	      static void
327  	      deallocate(_Alloc& __a, pointer __p, size_type __n)
328  	      { __a.deallocate(__p, __n); }
329  	
330  	      /**
331  	       *  @brief  Construct an object of type @a _Tp
332  	       *  @param  __a  An allocator.
333  	       *  @param  __p  Pointer to memory of suitable size and alignment for Tp
334  	       *  @param  __args Constructor arguments.
335  	       *
336  	       *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
337  	       *  if that expression is well-formed, otherwise uses placement-new
338  	       *  to construct an object of type @a _Tp at location @a __p from the
339  	       *  arguments @a __args...
340  	      */
341  	      template<typename _Tp, typename... _Args>
342  		static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
343  		-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
344  		{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }
345  	
346  	      /**
347  	       *  @brief  Destroy an object of type @a _Tp
348  	       *  @param  __a  An allocator.
349  	       *  @param  __p  Pointer to the object to destroy
350  	       *
351  	       *  Calls @c __a.destroy(__p) if that expression is well-formed,
352  	       *  otherwise calls @c __p->~_Tp()
353  	      */
354  	      template<typename _Tp>
355  		static void destroy(_Alloc& __a, _Tp* __p)
356  		{ _S_destroy(__a, __p, 0); }
357  	
358  	      /**
359  	       *  @brief  The maximum supported allocation size
360  	       *  @param  __a  An allocator.
361  	       *  @return @c __a.max_size() or @c numeric_limits<size_type>::max()
362  	       *
363  	       *  Returns @c __a.max_size() if that expression is well-formed,
364  	       *  otherwise returns @c numeric_limits<size_type>::max()
365  	      */
366  	      static size_type max_size(const _Alloc& __a) noexcept
367  	      { return _S_max_size(__a, 0); }
368  	
369  	      /**
370  	       *  @brief  Obtain an allocator to use when copying a container.
371  	       *  @param  __rhs  An allocator.
372  	       *  @return @c __rhs.select_on_container_copy_construction() or @a __rhs
373  	       *
374  	       *  Returns @c __rhs.select_on_container_copy_construction() if that
375  	       *  expression is well-formed, otherwise returns @a __rhs
376  	      */
377  	      static _Alloc
378  	      select_on_container_copy_construction(const _Alloc& __rhs)
379  	      { return _S_select(__rhs, 0); }
380  	    };
381  	
382  	  /// Partial specialization for std::allocator.
383  	  template<typename _Tp>
384  	    struct allocator_traits<allocator<_Tp>>
385  	    {
386  	      /// The allocator type
387  	      using allocator_type = allocator<_Tp>;
388  	      /// The allocated type
389  	      using value_type = _Tp;
390  	
391  	      /// The allocator's pointer type.
392  	      using pointer = _Tp*;
393  	
394  	      /// The allocator's const pointer type.
395  	      using const_pointer = const _Tp*;
396  	
397  	      /// The allocator's void pointer type.
398  	      using void_pointer = void*;
399  	
400  	      /// The allocator's const void pointer type.
401  	      using const_void_pointer = const void*;
402  	
403  	      /// The allocator's difference type
404  	      using difference_type = std::ptrdiff_t;
405  	
406  	      /// The allocator's size type
407  	      using size_type = std::size_t;
408  	
409  	      /// How the allocator is propagated on copy assignment
410  	      using propagate_on_container_copy_assignment = false_type;
411  	
412  	      /// How the allocator is propagated on move assignment
413  	      using propagate_on_container_move_assignment = true_type;
414  	
415  	      /// How the allocator is propagated on swap
416  	      using propagate_on_container_swap = false_type;
417  	
418  	      /// Whether all instances of the allocator type compare equal.
419  	      using is_always_equal = true_type;
420  	
421  	      template<typename _Up>
422  		using rebind_alloc = allocator<_Up>;
423  	
424  	      template<typename _Up>
425  		using rebind_traits = allocator_traits<allocator<_Up>>;
426  	
427  	      /**
428  	       *  @brief  Allocate memory.
429  	       *  @param  __a  An allocator.
430  	       *  @param  __n  The number of objects to allocate space for.
431  	       *
432  	       *  Calls @c a.allocate(n)
433  	      */
434  	      static pointer
435  	      allocate(allocator_type& __a, size_type __n)
436  	      { return __a.allocate(__n); }
437  	
438  	      /**
439  	       *  @brief  Allocate memory.
440  	       *  @param  __a  An allocator.
441  	       *  @param  __n  The number of objects to allocate space for.
442  	       *  @param  __hint Aid to locality.
443  	       *  @return Memory of suitable size and alignment for @a n objects
444  	       *          of type @c value_type
445  	       *
446  	       *  Returns <tt> a.allocate(n, hint) </tt>
447  	      */
448  	      static pointer
449  	      allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
450  	      { return __a.allocate(__n, __hint); }
451  	
452  	      /**
453  	       *  @brief  Deallocate memory.
454  	       *  @param  __a  An allocator.
455  	       *  @param  __p  Pointer to the memory to deallocate.
456  	       *  @param  __n  The number of objects space was allocated for.
457  	       *
458  	       *  Calls <tt> a.deallocate(p, n) </tt>
459  	      */
460  	      static void
461  	      deallocate(allocator_type& __a, pointer __p, size_type __n)
462  	      { __a.deallocate(__p, __n); }
463  	
464  	      /**
465  	       *  @brief  Construct an object of type @a _Up
466  	       *  @param  __a  An allocator.
467  	       *  @param  __p  Pointer to memory of suitable size and alignment for Tp
468  	       *  @param  __args Constructor arguments.
469  	       *
470  	       *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
471  	      */
472  	      template<typename _Up, typename... _Args>
473  		static void
474  		construct(allocator_type& __a, _Up* __p, _Args&&... __args)
475  		{ __a.construct(__p, std::forward<_Args>(__args)...); }
476  	
477  	      /**
478  	       *  @brief  Destroy an object of type @a _Up
479  	       *  @param  __a  An allocator.
480  	       *  @param  __p  Pointer to the object to destroy
481  	       *
482  	       *  Calls @c __a.destroy(__p).
483  	      */
484  	      template<typename _Up>
485  		static void
486  		destroy(allocator_type& __a, _Up* __p)
487  		{ __a.destroy(__p); }
488  	
489  	      /**
490  	       *  @brief  The maximum supported allocation size
491  	       *  @param  __a  An allocator.
492  	       *  @return @c __a.max_size()
493  	      */
494  	      static size_type
495  	      max_size(const allocator_type& __a) noexcept
496  	      { return __a.max_size(); }
497  	
498  	      /**
499  	       *  @brief  Obtain an allocator to use when copying a container.
500  	       *  @param  __rhs  An allocator.
501  	       *  @return @c __rhs
502  	      */
503  	      static allocator_type
504  	      select_on_container_copy_construction(const allocator_type& __rhs)
505  	      { return __rhs; }
506  	    };
507  	
508  	
509  	  template<typename _Alloc>
510  	    inline void
511  	    __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type)
512  	    { __one = __two; }
513  	
514  	  template<typename _Alloc>
515  	    inline void
516  	    __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type)
517  	    { }
518  	
519  	  template<typename _Alloc>
520  	    inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two)
521  	    {
522  	      typedef allocator_traits<_Alloc> __traits;
523  	      typedef typename __traits::propagate_on_container_copy_assignment __pocca;
524  	      __do_alloc_on_copy(__one, __two, __pocca());
525  	    }
526  	
527  	  template<typename _Alloc>
528  	    inline _Alloc __alloc_on_copy(const _Alloc& __a)
529  	    {
530  	      typedef allocator_traits<_Alloc> __traits;
531  	      return __traits::select_on_container_copy_construction(__a);
532  	    }
533  	
534  	  template<typename _Alloc>
535  	    inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type)
536  	    { __one = std::move(__two); }
537  	
538  	  template<typename _Alloc>
539  	    inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type)
540  	    { }
541  	
542  	  template<typename _Alloc>
543  	    inline void __alloc_on_move(_Alloc& __one, _Alloc& __two)
544  	    {
545  	      typedef allocator_traits<_Alloc> __traits;
546  	      typedef typename __traits::propagate_on_container_move_assignment __pocma;
547  	      __do_alloc_on_move(__one, __two, __pocma());
548  	    }
549  	
550  	  template<typename _Alloc>
551  	    inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type)
552  	    {
553  	      using std::swap;
554  	      swap(__one, __two);
555  	    }
556  	
557  	  template<typename _Alloc>
558  	    inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type)
559  	    { }
560  	
561  	  template<typename _Alloc>
562  	    inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two)
563  	    {
564  	      typedef allocator_traits<_Alloc> __traits;
565  	      typedef typename __traits::propagate_on_container_swap __pocs;
566  	      __do_alloc_on_swap(__one, __two, __pocs());
567  	    }
568  	
569  	  template<typename _Alloc>
570  	    class __is_copy_insertable_impl
571  	    {
572  	      typedef allocator_traits<_Alloc> _Traits;
573  	
574  	      template<typename _Up, typename
575  		       = decltype(_Traits::construct(std::declval<_Alloc&>(),
576  						     std::declval<_Up*>(),
577  						     std::declval<const _Up&>()))>
578  		static true_type
579  		_M_select(int);
580  	
581  	      template<typename _Up>
582  		static false_type
583  		_M_select(...);
584  	
585  	    public:
586  	      typedef decltype(_M_select<typename _Alloc::value_type>(0)) type;
587  	    };
588  	
589  	  // true if _Alloc::value_type is CopyInsertable into containers using _Alloc
590  	  template<typename _Alloc>
591  	    struct __is_copy_insertable
592  	    : __is_copy_insertable_impl<_Alloc>::type
593  	    { };
594  	
595  	  // std::allocator<_Tp> just requires CopyConstructible
596  	  template<typename _Tp>
597  	    struct __is_copy_insertable<allocator<_Tp>>
598  	    : is_copy_constructible<_Tp>
599  	    { };
600  	
601  	_GLIBCXX_END_NAMESPACE_VERSION
602  	} // namespace std
603  	
604  	#endif
605  	#endif
606