OSDN Git Service

2011-05-30 Jonathan Wakely <jwakely.gcc@gmail.com>
[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 <bits/uses_allocator.h>
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   template<typename _Alloc, typename _Tp>
211     class __alloctr_rebind_helper
212     {
213       template<typename _Alloc2, typename _Tp2>
214         static constexpr bool
215         _S_chk(typename _Alloc2::template rebind<_Tp2>::other*)
216         { return true; }
217
218       template<typename, typename>
219         static constexpr bool
220         _S_chk(...)
221         { return false; }
222
223     public:
224       static const bool __value = _S_chk<_Alloc, _Tp>(nullptr);
225     };
226
227   template<typename _Alloc, typename _Tp,
228            bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value>
229     struct __alloctr_rebind;
230
231   template<typename _Alloc, typename _Tp>
232     struct __alloctr_rebind<_Alloc, _Tp, true>
233     {
234       typedef typename _Alloc::template rebind<_Tp>::other __type;
235     };
236
237   template<template<typename, typename...> class _Alloc, typename _Tp,
238             typename _Up, typename... _Args>
239     struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false>
240     {
241       typedef _Alloc<_Tp, _Args...> __type;
242     };
243
244   /**
245    * @brief  Uniform interface to all allocator types.
246    * @ingroup allocators
247   */
248   template<typename _Alloc>
249     struct allocator_traits
250     {
251       /// The allocator type
252       typedef _Alloc allocator_type;
253       /// The allocated type
254       typedef typename _Alloc::value_type value_type;
255
256 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \
257   private: \
258   template<typename _Tp> \
259     static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \
260   static _ALT _S_##_NTYPE##_helper(...); \
261     typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \
262   public:
263
264 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
265
266       /**
267        * @brief   The allocator's pointer type.
268        *
269        * @c Alloc::pointer if that type exists, otherwise @c value_type*
270       */
271       typedef __pointer pointer;
272
273 // TODO: Use pointer_traits::rebind alias template.
274
275 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
276   typename pointer_traits<pointer>::template __rebind<const value_type>::__type)
277
278       /**
279        * @brief   The allocator's const pointer type.
280        *
281        * @c Alloc::const_pointer if that type exists, otherwise
282        * <tt> pointer_traits<pointer>::rebind<const value_type> </tt>
283       */
284       typedef __const_pointer const_pointer;
285
286 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
287   typename pointer_traits<pointer>::template __rebind<void>::__type)
288
289       /**
290        * @brief   The allocator's void pointer type.
291        *
292        * @c Alloc::void_pointer if that type exists, otherwise
293        * <tt> pointer_traits<pointer>::rebind<void> </tt>
294       */
295       typedef __void_pointer void_pointer;
296
297 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
298   typename pointer_traits<pointer>::template __rebind<const void>::__type)
299
300       /**
301        * @brief   The allocator's const void pointer type.
302        *
303        * @c Alloc::const_void_pointer if that type exists, otherwise
304        * <tt> pointer_traits<pointer>::rebind<const void> </tt>
305       */
306       typedef __const_void_pointer const_void_pointer;
307
308 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type,
309                               typename pointer_traits<pointer>::difference_type)
310
311       /**
312        * @brief   The allocator's difference type
313        *
314        * @c Alloc::difference_type if that type exists, otherwise
315        * <tt> pointer_traits<pointer>::difference_type </tt>
316       */
317       typedef __difference_type difference_type;
318
319 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type,
320                               typename make_unsigned<difference_type>::type)
321
322       /**
323        * @brief   The allocator's size type
324        *
325        * @c Alloc::size_type if that type exists, otherwise
326        * <tt> make_unsigned<difference_type>::type </tt>
327       */
328       typedef __size_type size_type;
329
330 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment,
331                               false_type)
332
333       /**
334        * @brief   How the allocator is propagated on copy assignment
335        *
336        * @c Alloc::propagate_on_container_copy_assignment if that type exists,
337        * otherwise @c false_type
338       */
339       typedef __propagate_on_container_copy_assignment
340         propagate_on_container_copy_assignment;
341
342 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment,
343                               false_type)
344
345       /**
346        * @brief   How the allocator is propagated on move assignment
347        *
348        * @c Alloc::propagate_on_container_move_assignment if that type exists,
349        * otherwise @c false_type
350       */
351       typedef __propagate_on_container_move_assignment
352         propagate_on_container_move_assignment;
353
354 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap,
355                               false_type)
356
357       /**
358        * @brief   How the allocator is propagated on swap
359        *
360        * @c Alloc::propagate_on_container_swap if that type exists,
361        * otherwise @c false_type
362       */
363       typedef __propagate_on_container_swap propagate_on_container_swap;
364
365 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE
366
367       /* TODO: use template alias 
368       template<typename _Tp>
369         using rebind_alloc = __alloctr_rebind<_Alloc, _Tp>::__type;
370       template<typename _Tp>
371         using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
372       */
373       template<typename _Tp>
374         struct __rebind_alloc
375         {
376           typedef typename __alloctr_rebind<_Alloc, _Tp>::__type __type;
377         };
378
379       template<typename _Tp>
380         struct __rebind_traits
381         {
382           typedef allocator_traits<typename __rebind_alloc<_Tp>::__type> __type;
383         };
384
385     private:
386       template<typename _Alloc2>
387         struct __allocate_helper
388         {
389           template<typename _Alloc3,
390             typename = decltype(std::declval<_Alloc3*>()->allocate(
391                   std::declval<size_type>(),
392                   std::declval<const_void_pointer>()))>
393             static true_type __test(int);
394
395           template<typename>
396             static false_type __test(...);
397
398           typedef decltype(__test<_Alloc>(0)) type;
399           static const bool value = type::value;
400         };
401
402       template<typename _Alloc2>
403         static typename
404         enable_if<__allocate_helper<_Alloc2>::value, pointer>::type
405         _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint)
406         { return __a.allocate(__n, __hint); }
407
408       template<typename _Alloc2>
409         static typename
410         enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type
411         _S_allocate(_Alloc2& __a, size_type __n, ...)
412         { return __a.allocate(__n); }
413
414       template<typename _Tp, typename... _Args>
415         struct __construct_helper
416         {
417           template<typename _Alloc2,
418             typename = decltype(std::declval<_Alloc2*>()->construct(
419                   std::declval<_Tp*>(), std::declval<_Args>()...))>
420             static true_type __test(int);
421
422           template<typename>
423             static false_type __test(...);
424
425           typedef decltype(__test<_Alloc>(0)) type;
426           static const bool value = type::value;
427         };
428
429       template<typename _Tp, typename... _Args>
430         static typename
431         enable_if<__construct_helper<_Tp, _Args...>::value, void>::type
432         _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
433         { __a.construct(__p, std::forward<_Args>(__args)...); }
434
435       template<typename _Tp, typename... _Args>
436         static typename
437         enable_if<!__construct_helper<_Tp, _Args...>::value, void>::type
438         _S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
439         { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); }
440
441       template<typename _Tp>
442         struct __destroy_helper
443         {
444           template<typename _Alloc2,
445             typename = decltype(std::declval<_Alloc2*>()->destroy(
446                   std::declval<_Tp*>()))>
447             static true_type __test(int);
448
449           template<typename>
450             static false_type __test(...);
451
452           typedef decltype(__test<_Alloc>(0)) type;
453           static const bool value = type::value;
454         };
455
456       template<typename _Tp>
457         static typename enable_if<__destroy_helper<_Tp>::value, void>::type
458         _S_destroy(_Alloc& __a, _Tp* __p)
459         { __a.destroy(__p); }
460
461       template<typename _Tp>
462         static typename enable_if<!__destroy_helper<_Tp>::value, void>::type
463         _S_destroy(_Alloc&, _Tp* __p)
464         { __p->~_Tp(); }
465
466       template<typename _Alloc2>
467         struct __maxsize_helper
468         {
469           template<typename _Alloc3,
470             typename = decltype(std::declval<_Alloc3*>()->max_size())>
471             static true_type __test(int);
472
473           template<typename>
474             static false_type __test(...);
475
476           typedef decltype(__test<_Alloc2>(0)) type;
477           static const bool value = type::value;
478         };
479
480       template<typename _Alloc2>
481         static typename
482         enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type
483         _S_max_size(_Alloc2& __a)
484         { return __a.max_size(); }
485
486       template<typename _Alloc2>
487         static typename
488         enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type
489         _S_max_size(_Alloc2&)
490         { return numeric_limits<size_type>::max(); }
491
492       template<typename _Alloc2>
493         struct __select_helper
494         {
495           template<typename _Alloc3, typename
496             = decltype(std::declval<_Alloc3*>()
497                 ->select_on_container_copy_construction())>
498             static true_type __test(int);
499
500           template<typename>
501             static false_type __test(...);
502
503           typedef decltype(__test<_Alloc2>(0)) type;
504           static const bool value = type::value;
505         };
506       template<typename _Alloc2>
507         static typename
508         enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type
509         _S_select(_Alloc2& __a)
510         { return __a.select_on_container_copy_construction(); }
511
512       template<typename _Alloc2>
513         static typename
514         enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type
515         _S_select(_Alloc2& __a)
516         { return __a; }
517
518     public:
519
520       /**
521        *  @brief  Allocate memory.
522        *  @param  a  An allocator.
523        *  @param  n  The number of objects to allocate space for.
524        *
525        *  Calls @c a.allocate(n)
526       */
527       static pointer
528       allocate(_Alloc& __a, size_type __n)
529       { return __a.allocate(__n); }
530
531       /**
532        *  @brief  Allocate memory.
533        *  @param  a  An allocator.
534        *  @param  n  The number of objects to allocate space for.
535        *  @param  hint Aid to locality.
536        *  @return Memory of suitable size and alignment for @a n objects
537        *          of type @c value_type
538        *
539        *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
540        *  well-formed, otherwise returns @c a.allocate(n)
541       */
542       static pointer
543       allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
544       { return _S_allocate(__a, __n, __hint); }
545
546       /**
547        *  @brief  Deallocate memory.
548        *  @param  a  An allocator.
549        *  @param  p  Pointer to the memory to deallocate.
550        *  @param  n  The number of objects space was allocated for.
551        *
552        *  Calls <tt> a.deallocate(p, n) </tt>
553       */
554       static void deallocate(_Alloc& __a, pointer __p, size_type __n)
555       { __a.deallocate(__p, __n); }
556
557       /**
558        *  @brief  Construct an object of type @a Tp
559        *  @param  a  An allocator.
560        *  @param  p  Pointer to memory of suitable size and alignment for Tp
561        *  @param  args Constructor arguments.
562        *
563        *  Calls <tt> a.construct(p, std::forward<Args>(args)...) </tt>
564        *  if that expression is well-formed, otherwise uses placement-new
565        *  to construct an object of type @a Tp at location @a p from the
566        *  arguments @a args...
567       */
568       template<typename _Tp, typename... _Args>
569         static void construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
570         { _S_construct(__a, __p, std::forward<_Args>(__args)...); }
571
572       /**
573        *  @brief  Destroy an object of type @a Tp
574        *  @param  a  An allocator.
575        *  @param  p  Pointer to the object to destroy
576        *
577        *  Calls @c a.destroy(p) if that expression is well-formed,
578        *  otherwise calls @c p->~Tp()
579       */
580       template <class _Tp>
581         static void destroy(_Alloc& __a, _Tp* __p)
582         { _S_destroy(__a, __p); }
583
584       /**
585        *  @brief  The maximum supported allocation size
586        *  @param  a  An allocator.
587        *  @return @c a.max_size() or @c %numeric_limits<size_type>::max()
588        *
589        *  Returns @c a.max_size() if that expression is well-formed,
590        *  otherwise returns @c %numeric_limits<size_type>::max()
591       */
592       static size_type max_size(const _Alloc& __a)
593       { return _S_max_size(__a); }
594
595       /**
596        *  @brief  Obtain an allocator to use when copying a container.
597        *  @param  rhs  An allocator.
598        *  @return @c rhs.select_on_container_copy_construction() or @a rhs
599        *
600        *  Returns @c rhs.select_on_container_copy_construction() if that
601        *  expression is well-formed, otherwise returns @a rhs
602       */
603       static _Alloc
604       select_on_container_copy_construction(const _Alloc& __rhs)
605       { return _S_select(__rhs); }
606     };
607
608 #endif
609
610 _GLIBCXX_END_NAMESPACE_VERSION
611 } // namespace std
612
613 #endif