OSDN Git Service

37c6a596b9189c07cf10b22bf814ee0123c61e76
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / allocator.h
1 // Allocators -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27  * Copyright (c) 1996-1997
28  * Silicon Graphics Computer Systems, Inc.
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation.  Silicon Graphics makes no
35  * representations about the suitability of this software for any
36  * purpose.  It is provided "as is" without express or implied warranty.
37  */
38
39 /** @file bits/allocator.h
40  *  This is an internal header file, included by other library headers.
41  *  Do not attempt to use it directly. @headername{memory}
42  */
43
44 #ifndef _ALLOCATOR_H
45 #define _ALLOCATOR_H 1
46
47 // Define the base class to std::allocator.
48 #include <bits/c++allocator.h>
49
50 #ifdef __GXX_EXPERIMENTAL_CXX0X__
51 #include <bits/ptr_traits.h>
52 #include <type_traits> // For _GLIBCXX_HAS_NESTED_TYPE
53 #include <limits>
54 #endif
55
56 namespace std _GLIBCXX_VISIBILITY(default)
57 {
58 _GLIBCXX_BEGIN_NAMESPACE_VERSION
59
60   /**
61    * @defgroup allocators Allocators
62    * @ingroup memory
63    *
64    * Classes encapsulating memory operations.
65    */
66
67   template<typename _Tp>
68     class allocator;
69
70   /// allocator<void> specialization.
71   template<>
72     class allocator<void>
73     {
74     public:
75       typedef size_t      size_type;
76       typedef ptrdiff_t   difference_type;
77       typedef void*       pointer;
78       typedef const void* const_pointer;
79       typedef void        value_type;
80
81       template<typename _Tp1>
82         struct rebind
83         { typedef allocator<_Tp1> other; };
84     };
85
86   /**
87    * @brief  The @a standard allocator, as per [20.4].
88    * @ingroup allocators
89    *
90    *  See http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt04ch11.html
91    *  for further details.
92    */
93   template<typename _Tp>
94     class allocator: public __glibcxx_base_allocator<_Tp>
95     {
96    public:
97       typedef size_t     size_type;
98       typedef ptrdiff_t  difference_type;
99       typedef _Tp*       pointer;
100       typedef const _Tp* const_pointer;
101       typedef _Tp&       reference;
102       typedef const _Tp& const_reference;
103       typedef _Tp        value_type;
104
105       template<typename _Tp1>
106         struct rebind
107         { typedef allocator<_Tp1> other; };
108
109       allocator() throw() { }
110
111       allocator(const allocator& __a) throw()
112       : __glibcxx_base_allocator<_Tp>(__a) { }
113
114       template<typename _Tp1>
115         allocator(const allocator<_Tp1>&) throw() { }
116
117       ~allocator() throw() { }
118
119       // Inherit everything else.
120     };
121
122   template<typename _T1, typename _T2>
123     inline bool
124     operator==(const allocator<_T1>&, const allocator<_T2>&)
125     { return true; }
126
127   template<typename _Tp>
128     inline bool
129     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
130     { return true; }
131
132   template<typename _T1, typename _T2>
133     inline bool
134     operator!=(const allocator<_T1>&, const allocator<_T2>&)
135     { return false; }
136
137   template<typename _Tp>
138     inline bool
139     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
140     { return false; }
141
142   // Inhibit implicit instantiations for required instantiations,
143   // which are defined via explicit instantiations elsewhere.
144 #if _GLIBCXX_EXTERN_TEMPLATE
145   extern template class allocator<char>;
146   extern template class allocator<wchar_t>;
147 #endif
148
149   // Undefine.
150 #undef __glibcxx_base_allocator
151
152   // To implement Option 3 of DR 431.
153   template<typename _Alloc, bool = __is_empty(_Alloc)>
154     struct __alloc_swap
155     { static void _S_do_it(_Alloc&, _Alloc&) { } };
156
157   template<typename _Alloc>
158     struct __alloc_swap<_Alloc, false>
159     {
160       static void
161       _S_do_it(_Alloc& __one, _Alloc& __two)
162       {
163         // Precondition: swappable allocators.
164         if (__one != __two)
165           swap(__one, __two);
166       }
167     };
168
169   // Optimize for stateless allocators.
170   template<typename _Alloc, bool = __is_empty(_Alloc)>
171     struct __alloc_neq
172     {
173       static bool
174       _S_do_it(const _Alloc&, const _Alloc&)
175       { return false; }
176     };
177
178   template<typename _Alloc>
179     struct __alloc_neq<_Alloc, false>
180     {
181       static bool
182       _S_do_it(const _Alloc& __one, const _Alloc& __two)
183       { return __one != __two; }
184     };
185
186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
187   // A very basic implementation for now.  In general we have to wait for
188   // the availability of the infrastructure described in N2983:  we should
189   // try when either T has a move constructor which cannot throw or T is
190   // CopyConstructible.
191   // NB: This code doesn't properly belong here, we should find a more
192   // suited place common to std::vector and std::deque.
193   template<typename _Tp,
194            bool = __has_trivial_copy(typename _Tp::value_type)>
195     struct __shrink_to_fit
196     { static void _S_do_it(_Tp&) { } };
197
198   template<typename _Tp>
199     struct __shrink_to_fit<_Tp, true>
200     {
201       static void
202       _S_do_it(_Tp& __v)
203       {
204         __try
205           { _Tp(__v).swap(__v); }
206         __catch(...) { }
207       }
208     };
209
210
211   /// [allocator.tag]
212   struct allocator_arg_t { };
213
214   constexpr allocator_arg_t allocator_arg = allocator_arg_t();
215
216 _GLIBCXX_HAS_NESTED_TYPE(allocator_type)
217
218   template<typename _Tp, typename _Alloc,
219            bool = __has_allocator_type<_Tp>::value>
220     struct __uses_allocator_helper
221     : public false_type { };
222
223   template<typename _Tp, typename _Alloc>
224     struct __uses_allocator_helper<_Tp, _Alloc, true>
225     : public integral_constant<bool, is_convertible<_Alloc,
226                                      typename _Tp::allocator_type>::value>
227     { };
228
229   /// [allocator.uses.trait]
230   template<typename _Tp, typename _Alloc>
231     struct uses_allocator
232     : public integral_constant<bool,
233                                __uses_allocator_helper<_Tp, _Alloc>::value>
234     { };
235
236   template<typename _Alloc, typename _Tp>
237     class __alloctr_rebind_helper
238     {
239       template<typename _Alloc2, typename _Tp2>
240         static constexpr bool
241         _S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
242         { return true; }
243
244       template<typename, typename>
245         static constexpr bool
246         _S_chk(...)
247         { return false; }
248
249     public:
250       static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
251     };
252
253   template<typename _Alloc, typename _Tp,
254            bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
255     struct __alloctr_rebind;
256
257   template<typename _Alloc, typename _Tp>
258     struct __alloctr_rebind<_Alloc, _Tp, true>
259     {
260       typedef typename _Alloc::template rebind<_Tp>::other __type;
261     };
262
263   template<template<typename, typename...> class _Alloc, typename _Tp,
264             typename _Up, typename... _Args>
265     struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
266     {
267       typedef _Alloc<_Tp, _Args...> __type;
268     };
269
270   /**
271    * @brief  Uniform interface to all allocator types.
272    * @ingroup allocators
273   */
274   template<typename _Alloc>
275     struct allocator_traits
276     {
277       /// The allocator type
278       typedef _Alloc allocator_type;
279       /// The allocated type
280       typedef typename _Alloc::value_type value_type;
281
282 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
283   private: \
284   template<typename _Tp> \
285     static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
286   static _ALT _S_##_NTYPE##_helper(...); \
287     typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
288   public:
289
290 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
291
292       /**
293        * @brief   The allocator's pointer type.
294        *
295        * @c Alloc::pointer if that type exists, otherwise @c value_type*
296       */
297       typedef __pointer pointer;
298
299 // TODO: Use pointer_traits::rebind alias template.
300
301 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
302   typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
303
304       /**
305        * @brief   The allocator's const pointer type.
306        *
307        * @c Alloc::const_pointer if that type exists, otherwise
308        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
309       */
310       typedef __const_pointer const_pointer;
311
312 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
313   typename pointer_traits<pointer>::template __rebind<void>::__type)
314
315       /**
316        * @brief   The allocator's void pointer type.
317        *
318        * @c Alloc::void_pointer if that type exists, otherwise
319        * <tt> pointer_traits<pointer>::rebind<void> </tt>
320       */
321       typedef __void_pointer void_pointer;
322
323 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
324   typename pointer_traits<pointer>::template __rebind<const void>::__type)
325
326       /**
327        * @brief   The allocator's const void pointer type.
328        *
329        * @c Alloc::const_void_pointer if that type exists, otherwise
330        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
331       */
332       typedef __const_void_pointer const_void_pointer;
333
334 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
335                               typename pointer_traits<pointer>::difference_type)
336
337       /**
338        * @brief   The allocator's difference type
339        *
340        * @c Alloc::difference_type if that type exists, otherwise
341        * <tt> pointer_traits<pointer>::difference_type </tt>
342       */
343       typedef __difference_type difference_type;
344
345 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
346                               typename make_unsigned<difference_type>::type)
347
348       /**
349        * @brief   The allocator's size type
350        *
351        * @c Alloc::size_type if that type exists, otherwise
352        * <tt> make_unsigned<difference_type>::type </tt>
353       */
354       typedef __size_type size_type;
355
356 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
357                               false_type)
358
359       /**
360        * @brief   How the allocator is propagated on copy assignment
361        *
362        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
363        * otherwise @c false_type
364       */
365       typedef __propagate_on_container_copy_assignment
366         propagate_on_container_copy_assignment;
367
368 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
369                               false_type)
370
371       /**
372        * @brief   How the allocator is propagated on move assignment
373        *
374        * @c Alloc::propagate_on_container_move_assignment if that type exists,
375        * otherwise @c false_type
376       */
377       typedef __propagate_on_container_move_assignment
378         propagate_on_container_move_assignment;
379
380 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
381                               false_type)
382
383       /**
384        * @brief   How the allocator is propagated on swap
385        *
386        * @c Alloc::propagate_on_container_swap if that type exists,
387        * otherwise @c false_type
388       */
389       typedef __propagate_on_container_swap propagate_on_container_swap;
390
391 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
392
393       /* TODO: use template alias 
394       template<typename _Tp>
395         using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
396       template<typename _Tp>
397         using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
398       */
399       template<typename _Tp>
400         struct __rebind_alloc
401         {
402           typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
403         };
404
405       template<typename _Tp>
406         struct __rebind_traits
407         {
408           typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
409         };
410
411     private:
412       template<typename _Alloc2>
413         struct __allocate_helper
414         {
415           template<typename _Alloc3,
416             typename = decltype(std::declval<_Alloc3*>()->allocate(
417                   std::declval<size_type>(),
418                   std::declval<const_void_pointer>()))>
419             static true_type __test(int);
420
421           template<typename>
422             static false_type __test(...);
423
424           typedef decltype(__test<_Alloc>(0)) type;
425           static const bool value = type::value;
426         };
427
428       template<typename _Alloc2>
429         static typename
430         enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
431         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
432         { return __a.allocate(__n, __hint); }
433
434       template<typename _Alloc2>
435         static typename
436         enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
437         _S_allocate(_Alloc2& __a, size_type __n, ...)
438         { return __a.allocate(__n); }
439
440       template<typename _Tp, typename... _Args>
441         struct __construct_helper
442         {
443           template<typename _Alloc2,
444             typename = decltype(std::declval<_Alloc2*>()->construct(
445                   std::declval<_Tp*>(), std::declval<_Args>()...))>
446             static true_type __test(int);
447
448           template<typename>
449             static false_type __test(...);
450
451           typedef decltype(__test<_Alloc>(0)) type;
452           static const bool value = type::value;
453         };
454
455       template<typename _Tp, typename... _Args>
456         static typename
457         enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
458         _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
459         { __a.construct(__p, std::forward<_Args>(__args)...); }
460
461       template<typename _Tp, typename... _Args>
462         static typename
463         enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
464         _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
465         { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
466
467       template<typename _Tp>
468         struct __destroy_helper
469         {
470           template<typename _Alloc2,
471             typename = decltype(std::declval<_Alloc2*>()->destroy(
472                   std::declval<_Tp*>()))>
473             static true_type __test(int);
474
475           template<typename>
476             static false_type __test(...);
477
478           typedef decltype(__test<_Alloc>(0)) type;
479           static const bool value = type::value;
480         };
481
482       template<typename _Tp>
483         static typename enable_if<__destroy_helper<_Tp>::value, void>::type
484         _S_destroy(_Alloc& __a, _Tp* __p)
485         { __a.destroy(__p); }
486
487       template<typename _Tp>
488         static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
489         _S_destroy(_Alloc&, _Tp* __p)
490         { __p->~_Tp(); }
491
492       template<typename _Alloc2>
493         struct __maxsize_helper
494         {
495           template<typename _Alloc3,
496             typename = decltype(std::declval<_Alloc3*>()->max_size())>
497             static true_type __test(int);
498
499           template<typename>
500             static false_type __test(...);
501
502           typedef decltype(__test<_Alloc2>(0)) type;
503           static const bool value = type::value;
504         };
505
506       template<typename _Alloc2>
507         static typename
508         enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
509         _S_max_size(_Alloc2& __a)
510         { return __a.max_size(); }
511
512       template<typename _Alloc2>
513         static typename
514         enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
515         _S_max_size(_Alloc2&)
516         { return numeric_limits<size_type>::max(); }
517
518       template<typename _Alloc2>
519         struct __select_helper
520         {
521           template<typename _Alloc3, typename
522             = decltype(std::declval<_Alloc3*>()
523                 ->select_on_container_copy_construction())>
524             static true_type __test(int);
525
526           template<typename>
527             static false_type __test(...);
528
529           typedef decltype(__test<_Alloc2>(0)) type;
530           static const bool value = type::value;
531         };
532       template<typename _Alloc2>
533         static typename
534         enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
535         _S_select(_Alloc2& __a)
536         { return __a.select_on_container_copy_construction(); }
537
538       template<typename _Alloc2>
539         static typename
540         enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
541         _S_select(_Alloc2& __a)
542         { return __a; }
543
544     public:
545
546       /**
547        *  @brief  Allocate memory.
548        *  @param  a  An allocator.
549        *  @param  n  The number of objects to allocate space for.
550        *
551        *  Calls @c a.allocate(n)
552       */
553       static pointer
554       allocate(_Alloc& __a, size_type __n)
555       { return __a.allocate(__n); }
556
557       /**
558        *  @brief  Allocate memory.
559        *  @param  a  An allocator.
560        *  @param  n  The number of objects to allocate space for.
561        *  @param  hint Aid to locality.
562        *  @return Memory of suitable size and alignment for @a n objects
563        *          of type @c value_type
564        *
565        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
566        *  well-formed, otherwise returns @c a.allocate(n)
567       */
568       static pointer
569       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
570       { return _S_allocate(__a, __n, __hint); }
571
572       /**
573        *  @brief  Deallocate memory.
574        *  @param  a  An allocator.
575        *  @param  p  Pointer to the memory to deallocate.
576        *  @param  n  The number of objects space was allocated for.
577        *
578        *  Calls <tt> a.deallocate(p, n) </tt>
579       */
580       static void deallocate(_Alloc& __a, pointer __p, size_type __n)
581       { __a.deallocate(__p, __n); }
582
583       /**
584        *  @brief  Construct an object of type @a Tp
585        *  @param  a  An allocator.
586        *  @param  p  Pointer to memory of suitable size and alignment for Tp
587        *  @param  args Constructor arguments.
588        *
589        *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
590        *  if that expression is well-formed, otherwise uses placement-new
591        *  to construct an object of type @a Tp at location @a p from the
592        *  arguments @a args...
593       */
594       template<typename _Tp, typename... _Args>
595         static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
596         { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
597
598       /**
599        *  @brief  Destroy an object of type @a Tp
600        *  @param  a  An allocator.
601        *  @param  p  Pointer to the object to destroy
602        *
603        *  Calls @c a.destroy(p) if that expression is well-formed,
604        *  otherwise calls @c p->~Tp()
605       */
606       template <class _Tp>
607         static void destroy(_Alloc& __a, _Tp* __p)
608         { _S_destroy(__a, __p); }
609
610       /**
611        *  @brief  The maximum supported allocation size
612        *  @param  a  An allocator.
613        *  @return @c a.max_size() or @c %numeric_limits<size_type>::max()
614        *
615        *  Returns @c a.max_size() if that expression is well-formed,
616        *  otherwise returns @c %numeric_limits<size_type>::max()
617       */
618       static size_type max_size(const _Alloc& __a)
619       { return _S_max_size(__a); }
620
621       /**
622        *  @brief  Obtain an allocator to use when copying a container.
623        *  @param  rhs  An allocator.
624        *  @return @c rhs.select_on_container_copy_construction() or @a rhs
625        *
626        *  Returns @c rhs.select_on_container_copy_construction() if that
627        *  expression is well-formed, otherwise returns @a rhs
628       */
629       static _Alloc
630       select_on_container_copy_construction(const _Alloc& __rhs)
631       { return _S_select(__rhs); }
632     };
633
634 #endif
635
636 _GLIBCXX_END_NAMESPACE_VERSION
637 } // namespace std
638
639 #endif