1
2// Copyright 2005-2011 Daniel James.
3// Copyright 2009 Pablo Halpern.
4// Distributed under the Boost Software License, Version 1.0. (See accompanying
5// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7// See http://www.boost.org/libs/unordered for documentation
8
9#ifndef BOOST_UNORDERED_ALLOCATE_HPP
10#define BOOST_UNORDERED_ALLOCATE_HPP
11
12#include <boost/config.hpp>
13#if defined(BOOST_HAS_PRAGMA_ONCE)
14#pragma once
15#endif
16
17#include <boost/unordered/detail/fwd.hpp>
18#include <boost/move/move.hpp>
19#include <boost/preprocessor/cat.hpp>
20#include <boost/preprocessor/inc.hpp>
21#include <boost/preprocessor/dec.hpp>
22#include <boost/preprocessor/repetition/enum.hpp>
23#include <boost/preprocessor/repetition/enum_params.hpp>
24#include <boost/preprocessor/repetition/enum_binary_params.hpp>
25#include <boost/preprocessor/repetition/repeat_from_to.hpp>
26#include <boost/type_traits/is_class.hpp>
27#include <boost/type_traits/add_lvalue_reference.hpp>
28#include <boost/tuple/tuple.hpp>
29#include <boost/utility/enable_if.hpp>
30#include <boost/utility/addressof.hpp>
31#include <boost/detail/select_type.hpp>
32#include <boost/assert.hpp>
33#include <utility>
34
35#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
36#include <tuple>
37#endif
38
39#if defined(BOOST_MSVC)
40#pragma warning(push)
41#pragma warning(disable:4512) // assignment operator could not be generated.
42#pragma warning(disable:4345) // behavior change: an object of POD type
43 // constructed with an initializer of the form ()
44 // will be default-initialized.
45#endif
46
47#define BOOST_UNORDERED_EMPLACE_LIMIT 10
48
49namespace boost { namespace unordered { namespace detail {
50
51 ////////////////////////////////////////////////////////////////////////////
52 // Bits and pieces for implementing traits
53
54 template <typename T> typename boost::add_lvalue_reference<T>::type make();
55 struct choice9 { typedef char (&type)[9]; };
56 struct choice8 : choice9 { typedef char (&type)[8]; };
57 struct choice7 : choice8 { typedef char (&type)[7]; };
58 struct choice6 : choice7 { typedef char (&type)[6]; };
59 struct choice5 : choice6 { typedef char (&type)[5]; };
60 struct choice4 : choice5 { typedef char (&type)[4]; };
61 struct choice3 : choice4 { typedef char (&type)[3]; };
62 struct choice2 : choice3 { typedef char (&type)[2]; };
63 struct choice1 : choice2 { typedef char (&type)[1]; };
64 choice1 choose();
65
66 typedef choice1::type yes_type;
67 typedef choice2::type no_type;
68
69 struct private_type
70 {
71 private_type const &operator,(int) const;
72 };
73
74 template <typename T>
75 no_type is_private_type(T const&);
76 yes_type is_private_type(private_type const&);
77
78 struct convert_from_anything {
79 template <typename T>
80 convert_from_anything(T const&);
81 };
82
83 ////////////////////////////////////////////////////////////////////////////
84 // emplace_args
85 //
86 // Either forwarding variadic arguments, or storing the arguments in
87 // emplace_args##n
88
89#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
90
91#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
92#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
93#define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)...
94
95#define BOOST_UNORDERED_EMPLACE_ARGS1(a0) a0
96#define BOOST_UNORDERED_EMPLACE_ARGS2(a0, a1) a0, a1
97#define BOOST_UNORDERED_EMPLACE_ARGS3(a0, a1, a2) a0, a1, a2
98
99#else
100
101#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
102#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
103#define BOOST_UNORDERED_EMPLACE_FORWARD args
104
105#define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
106 BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
107
108#define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
109 boost::forward<BOOST_PP_CAT(A,i)>(BOOST_PP_CAT(a,i))
110
111#define BOOST_UNORDERED_EARGS(z, n, _) \
112 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
113 struct BOOST_PP_CAT(emplace_args, n) \
114 { \
115 BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) \
116 BOOST_PP_CAT(emplace_args, n) ( \
117 BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b) \
118 ) : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
119 {} \
120 \
121 }; \
122 \
123 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
124 inline BOOST_PP_CAT(emplace_args, n) < \
125 BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
126 > create_emplace_args( \
127 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b) \
128 ) \
129 { \
130 BOOST_PP_CAT(emplace_args, n) < \
131 BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
132 > e(BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
133 return e; \
134 }
135
136#define BOOST_UNORDERED_EMPLACE_ARGS1 create_emplace_args
137#define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args
138#define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args
139
140#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
141
142#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
143 typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
144 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
145
146#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
147 BOOST_PP_CAT(a, n)( \
148 boost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(b, n)))
149
150#else
151
152#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
153 typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \
154 BOOST_PP_CAT(Arg, n); \
155 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
156
157#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
158 BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
159
160#endif
161
162BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS,
163 _)
164
165#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
166#undef BOOST_UNORDERED_EARGS_MEMBER
167#undef BOOST_UNORDERED_EARGS_INIT
168
169#endif
170
171}}}
172
173////////////////////////////////////////////////////////////////////////////////
174//
175// Pick which version of allocator_traits to use
176//
177// 0 = Own partial implementation
178// 1 = std::allocator_traits
179// 2 = boost::container::allocator_traits
180
181#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
182# if defined(__GXX_EXPERIMENTAL_CXX0X__) && \
183 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
184# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
185# elif defined(BOOST_MSVC)
186# if BOOST_MSVC < 1400
187 // Use container's allocator_traits for older versions of Visual
188 // C++ as I don't test with them.
189# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
190# endif
191# endif
192#endif
193
194#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
195# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
196#endif
197
198////////////////////////////////////////////////////////////////////////////////
199//
200// Some utilities for implementing allocator_traits, but useful elsewhere so
201// they're always defined.
202
203#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
204# include <type_traits>
205#endif
206
207namespace boost { namespace unordered { namespace detail {
208
209 ////////////////////////////////////////////////////////////////////////////
210 // Integral_constrant, true_type, false_type
211 //
212 // Uses the standard versions if available.
213
214#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
215
216 using std::integral_constant;
217 using std::true_type;
218 using std::false_type;
219
220#else
221
222 template <typename T, T Value>
223 struct integral_constant { enum { value = Value }; };
224
225 typedef boost::unordered::detail::integral_constant<bool, true> true_type;
226 typedef boost::unordered::detail::integral_constant<bool, false> false_type;
227
228#endif
229
230 ////////////////////////////////////////////////////////////////////////////
231 // Explicitly call a destructor
232
233#if defined(BOOST_MSVC)
234#pragma warning(push)
235#pragma warning(disable:4100) // unreferenced formal parameter
236#endif
237
238 namespace func {
239 template <class T>
240 inline void destroy(T* x) {
241 x->~T();
242 }
243 }
244
245#if defined(BOOST_MSVC)
246#pragma warning(pop)
247#endif
248
249 ////////////////////////////////////////////////////////////////////////////
250 // Expression test mechanism
251 //
252 // When SFINAE expressions are available, define
253 // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
254 // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
255 // can detect if a class has the specified member, but not that it has the
256 // correct type, this is good enough for a passable impression of
257 // allocator_traits.
258
259#if !defined(BOOST_NO_SFINAE_EXPR)
260
261 template <typename T, unsigned int> struct expr_test;
262 template <typename T> struct expr_test<T, sizeof(char)> : T {};
263
264# define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
265 template <typename U> \
266 static typename boost::unordered::detail::expr_test< \
267 BOOST_PP_CAT(choice, result), \
268 sizeof(for_expr_test(( \
269 (expression), \
270 0)))>::type test( \
271 BOOST_PP_CAT(choice, count))
272
273# define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
274 template <typename U> \
275 static BOOST_PP_CAT(choice, result)::type test( \
276 BOOST_PP_CAT(choice, count))
277
278# define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
279 struct BOOST_PP_CAT(has_, name) \
280 { \
281 template <typename U> static char for_expr_test(U const&); \
282 BOOST_UNORDERED_CHECK_EXPRESSION(1, 1, \
283 boost::unordered::detail::make< thing >().name args); \
284 BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \
285 \
286 enum { value = sizeof(test<T>(choose())) == sizeof(choice1::type) };\
287 }
288
289#else
290
291 template <typename T> struct identity { typedef T type; };
292
293# define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
294 \
295 typedef typename boost::unordered::detail::identity<member>::type \
296 BOOST_PP_CAT(check, count); \
297 \
298 template <BOOST_PP_CAT(check, count) e> \
299 struct BOOST_PP_CAT(test, count) { \
300 typedef BOOST_PP_CAT(choice, result) type; \
301 }; \
302 \
303 template <class U> static typename \
304 BOOST_PP_CAT(test, count)<&U::name>::type \
305 test(BOOST_PP_CAT(choice, count))
306
307# define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
308 template <class U> static BOOST_PP_CAT(choice, result)::type \
309 test(BOOST_PP_CAT(choice, count))
310
311# define BOOST_UNORDERED_HAS_MEMBER(name) \
312 struct BOOST_PP_CAT(has_, name) \
313 { \
314 struct impl { \
315 struct base_mixin { int name; }; \
316 struct base : public T, public base_mixin {}; \
317 \
318 BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \
319 BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \
320 \
321 enum { value = sizeof(choice2::type) == \
322 sizeof(test<base>(choose())) \
323 }; \
324 }; \
325 \
326 enum { value = impl::value }; \
327 }
328
329#endif
330
331}}}
332
333////////////////////////////////////////////////////////////////////////////////
334//
335// Allocator traits
336//
337// First our implementation, then later light wrappers around the alternatives
338
339#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
340
341# include <boost/limits.hpp>
342# include <boost/utility/enable_if.hpp>
343# include <boost/pointer_to_other.hpp>
344# if defined(BOOST_NO_SFINAE_EXPR)
345# include <boost/type_traits/is_same.hpp>
346# endif
347
348# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \
349 !defined(BOOST_NO_SFINAE_EXPR)
350# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
351# else
352# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
353# endif
354
355namespace boost { namespace unordered { namespace detail {
356
357 // TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>?
358 template <typename Alloc, typename T>
359 struct rebind_wrap
360 {
361 typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other type;
362 };
363
364# if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
365
366# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
367 template <typename Tp, typename Default> \
368 struct default_type_ ## tname { \
369 \
370 template <typename X> \
371 static choice1::type test(choice1, typename X::tname* = 0); \
372 \
373 template <typename X> \
374 static choice2::type test(choice2, void* = 0); \
375 \
376 struct DefaultWrap { typedef Default tname; }; \
377 \
378 enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
379 \
380 typedef typename boost::detail::if_true<value>:: \
381 BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
382 ::type::tname type; \
383 }
384
385# else
386
387 template <typename T, typename T2>
388 struct sfinae : T2 {};
389
390# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
391 template <typename Tp, typename Default> \
392 struct default_type_ ## tname { \
393 \
394 template <typename X> \
395 static typename boost::unordered::detail::sfinae< \
396 typename X::tname, choice1>::type \
397 test(choice1); \
398 \
399 template <typename X> \
400 static choice2::type test(choice2); \
401 \
402 struct DefaultWrap { typedef Default tname; }; \
403 \
404 enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
405 \
406 typedef typename boost::detail::if_true<value>:: \
407 BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
408 ::type::tname type; \
409 }
410
411# endif
412
413# define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg) \
414 typename default_type_ ## tname<T, arg>::type
415
416 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
417 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
418 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer);
419 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer);
420 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type);
421 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type);
422 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_copy_assignment);
423 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_move_assignment);
424 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
425
426# if !defined(BOOST_NO_SFINAE_EXPR)
427
428 template <typename T>
429 BOOST_UNORDERED_HAS_FUNCTION(
430 select_on_container_copy_construction, U const, (), 0
431 );
432
433 template <typename T>
434 BOOST_UNORDERED_HAS_FUNCTION(
435 max_size, U const, (), 0
436 );
437
438# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
439
440 template <typename T, typename ValueType, typename... Args>
441 BOOST_UNORDERED_HAS_FUNCTION(
442 construct, U, (
443 boost::unordered::detail::make<ValueType*>(),
444 boost::unordered::detail::make<Args const>()...), 2
445 );
446
447# else
448
449 template <typename T, typename ValueType>
450 BOOST_UNORDERED_HAS_FUNCTION(
451 construct, U, (
452 boost::unordered::detail::make<ValueType*>(),
453 boost::unordered::detail::make<ValueType const>()), 2
454 );
455
456# endif
457
458 template <typename T, typename ValueType>
459 BOOST_UNORDERED_HAS_FUNCTION(
460 destroy, U, (boost::unordered::detail::make<ValueType*>()), 1
461 );
462
463# else
464
465 template <typename T>
466 BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
467
468 template <typename T>
469 BOOST_UNORDERED_HAS_MEMBER(max_size);
470
471 template <typename T, typename ValueType>
472 BOOST_UNORDERED_HAS_MEMBER(construct);
473
474 template <typename T, typename ValueType>
475 BOOST_UNORDERED_HAS_MEMBER(destroy);
476
477# endif
478
479 namespace func
480 {
481
482 template <typename Alloc>
483 inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
484 typename boost::enable_if_c<
485 boost::unordered::detail::
486 has_select_on_container_copy_construction<Alloc>::value, void*
487 >::type = 0)
488 {
489 return rhs.select_on_container_copy_construction();
490 }
491
492 template <typename Alloc>
493 inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
494 typename boost::disable_if_c<
495 boost::unordered::detail::
496 has_select_on_container_copy_construction<Alloc>::value, void*
497 >::type = 0)
498 {
499 return rhs;
500 }
501
502 template <typename SizeType, typename Alloc>
503 inline SizeType call_max_size(const Alloc& a,
504 typename boost::enable_if_c<
505 boost::unordered::detail::has_max_size<Alloc>::value, void*
506 >::type = 0)
507 {
508 return a.max_size();
509 }
510
511 template <typename SizeType, typename Alloc>
512 inline SizeType call_max_size(const Alloc&, typename boost::disable_if_c<
513 boost::unordered::detail::has_max_size<Alloc>::value, void*
514 >::type = 0)
515 {
516 return (std::numeric_limits<SizeType>::max)();
517 }
518
519 } // namespace func.
520
521 template <typename Alloc>
522 struct allocator_traits
523 {
524 typedef Alloc allocator_type;
525 typedef typename Alloc::value_type value_type;
526
527 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, pointer, value_type*)
528 pointer;
529
530 template <typename T>
531 struct pointer_to_other : boost::pointer_to_other<pointer, T> {};
532
533 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer,
534 typename pointer_to_other<const value_type>::type)
535 const_pointer;
536
537 //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer,
538 // typename pointer_to_other<void>::type)
539 // void_pointer;
540 //
541 //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer,
542 // typename pointer_to_other<const void>::type)
543 // const_void_pointer;
544
545 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, difference_type,
546 std::ptrdiff_t) difference_type;
547
548 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, size_type, std::size_t)
549 size_type;
550
551 // TODO: rebind_alloc and rebind_traits
552
553 static pointer allocate(Alloc& a, size_type n)
554 { return a.allocate(n); }
555
556 // I never use this, so I'll just comment it out for now.
557 //
558 //static pointer allocate(Alloc& a, size_type n,
559 // const_void_pointer hint)
560 // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
561
562 static void deallocate(Alloc& a, pointer p, size_type n)
563 { a.deallocate(p, n); }
564
565 public:
566
567# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
568
569 template <typename T, typename... Args>
570 static typename boost::enable_if_c<
571 boost::unordered::detail::has_construct<Alloc, T, Args...>
572 ::value>::type
573 construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x)
574 {
575 a.construct(p, boost::forward<Args>(x)...);
576 }
577
578 template <typename T, typename... Args>
579 static typename boost::disable_if_c<
580 boost::unordered::detail::has_construct<Alloc, T, Args...>
581 ::value>::type
582 construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
583 {
584 new ((void*) p) T(boost::forward<Args>(x)...);
585 }
586
587 template <typename T>
588 static typename boost::enable_if_c<
589 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
590 destroy(Alloc& a, T* p)
591 {
592 a.destroy(p);
593 }
594
595 template <typename T>
596 static typename boost::disable_if_c<
597 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
598 destroy(Alloc&, T* p)
599 {
600 boost::unordered::detail::func::destroy(p);
601 }
602
603# elif !defined(BOOST_NO_SFINAE_EXPR)
604
605 template <typename T>
606 static typename boost::enable_if_c<
607 boost::unordered::detail::has_construct<Alloc, T>::value>::type
608 construct(Alloc& a, T* p, T const& x)
609 {
610 a.construct(p, x);
611 }
612
613 template <typename T>
614 static typename boost::disable_if_c<
615 boost::unordered::detail::has_construct<Alloc, T>::value>::type
616 construct(Alloc&, T* p, T const& x)
617 {
618 new ((void*) p) T(x);
619 }
620
621 template <typename T>
622 static typename boost::enable_if_c<
623 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
624 destroy(Alloc& a, T* p)
625 {
626 a.destroy(p);
627 }
628
629 template <typename T>
630 static typename boost::disable_if_c<
631 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
632 destroy(Alloc&, T* p)
633 {
634 boost::unordered::detail::func::destroy(p);
635 }
636
637# else
638
639 // If we don't have SFINAE expressions, only call construct for the
640 // copy constructor for the allocator's value_type - as that's
641 // the only construct method that old fashioned allocators support.
642
643 template <typename T>
644 static void construct(Alloc& a, T* p, T const& x,
645 typename boost::enable_if_c<
646 boost::unordered::detail::has_construct<Alloc, T>::value &&
647 boost::is_same<T, value_type>::value,
648 void*>::type = 0)
649 {
650 a.construct(p, x);
651 }
652
653 template <typename T>
654 static void construct(Alloc&, T* p, T const& x,
655 typename boost::disable_if_c<
656 boost::unordered::detail::has_construct<Alloc, T>::value &&
657 boost::is_same<T, value_type>::value,
658 void*>::type = 0)
659 {
660 new ((void*) p) T(x);
661 }
662
663 template <typename T>
664 static void destroy(Alloc& a, T* p,
665 typename boost::enable_if_c<
666 boost::unordered::detail::has_destroy<Alloc, T>::value &&
667 boost::is_same<T, value_type>::value,
668 void*>::type = 0)
669 {
670 a.destroy(p);
671 }
672
673 template <typename T>
674 static void destroy(Alloc&, T* p,
675 typename boost::disable_if_c<
676 boost::unordered::detail::has_destroy<Alloc, T>::value &&
677 boost::is_same<T, value_type>::value,
678 void*>::type = 0)
679 {
680 boost::unordered::detail::func::destroy(p);
681 }
682
683# endif
684
685 static size_type max_size(const Alloc& a)
686 {
687 return boost::unordered::detail::func::
688 call_max_size<size_type>(a);
689 }
690
691 // Allocator propagation on construction
692
693 static Alloc select_on_container_copy_construction(Alloc const& rhs)
694 {
695 return boost::unordered::detail::func::
696 call_select_on_container_copy_construction(rhs);
697 }
698
699 // Allocator propagation on assignment and swap.
700 // Return true if lhs is modified.
701 typedef BOOST_UNORDERED_DEFAULT_TYPE(
702 Alloc, propagate_on_container_copy_assignment, false_type)
703 propagate_on_container_copy_assignment;
704 typedef BOOST_UNORDERED_DEFAULT_TYPE(
705 Alloc,propagate_on_container_move_assignment, false_type)
706 propagate_on_container_move_assignment;
707 typedef BOOST_UNORDERED_DEFAULT_TYPE(
708 Alloc,propagate_on_container_swap,false_type)
709 propagate_on_container_swap;
710 };
711}}}
712
713# undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
714# undef BOOST_UNORDERED_DEFAULT_TYPE
715
716////////////////////////////////////////////////////////////////////////////////
717//
718// std::allocator_traits
719
720#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
721
722# include <memory>
723
724# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
725
726namespace boost { namespace unordered { namespace detail {
727
728 template <typename Alloc>
729 struct allocator_traits : std::allocator_traits<Alloc> {};
730
731 template <typename Alloc, typename T>
732 struct rebind_wrap
733 {
734 typedef typename std::allocator_traits<Alloc>::
735 template rebind_alloc<T> type;
736 };
737}}}
738
739////////////////////////////////////////////////////////////////////////////////
740//
741// boost::container::allocator_traits
742
743#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
744
745# include <boost/container/allocator_traits.hpp>
746
747# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
748
749namespace boost { namespace unordered { namespace detail {
750
751 template <typename Alloc>
752 struct allocator_traits :
753 boost::container::allocator_traits<Alloc> {};
754
755 template <typename Alloc, typename T>
756 struct rebind_wrap :
757 boost::container::allocator_traits<Alloc>::
758 template portable_rebind_alloc<T>
759 {};
760
761}}}
762
763#else
764
765#error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
766
767#endif
768
769
770namespace boost { namespace unordered { namespace detail { namespace func {
771
772 ////////////////////////////////////////////////////////////////////////////
773 // call_construct
774
775#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
776
777# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
778
779 template <typename Alloc, typename T, typename... Args>
780 inline void call_construct(Alloc& alloc, T* address,
781 BOOST_FWD_REF(Args)... args)
782 {
783 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
784 address, boost::forward<Args>(args)...);
785 }
786
787 template <typename Alloc, typename T>
788 inline void destroy_value_impl(Alloc& alloc, T* x) {
789 boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x);
790 }
791
792
793# else
794
795 template <typename Alloc, typename T, typename... Args>
796 inline void call_construct(Alloc&, T* address,
797 BOOST_FWD_REF(Args)... args)
798 {
799 new((void*) address) T(boost::forward<Args>(args)...);
800 }
801
802 template <typename Alloc, typename T>
803 inline void destroy_value_impl(Alloc&, T* x) {
804 boost::unordered::detail::func::destroy(x);
805 }
806
807
808# endif
809
810#else
811
812 template <typename Alloc, typename T>
813 inline void destroy_value_impl(Alloc&, T* x) {
814 boost::unordered::detail::func::destroy(x);
815 }
816
817#endif
818
819 ////////////////////////////////////////////////////////////////////////////
820 // Construct from tuple
821 //
822 // Used for piecewise construction.
823
824#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
825
826# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
827 template<typename Alloc, typename T> \
828 void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \
829 { \
830 boost::unordered::detail::func::call_construct(alloc, ptr); \
831 } \
832 \
833 BOOST_PP_REPEAT_FROM_TO(1, n, \
834 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
835
836# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
837 template<typename Alloc, typename T, \
838 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
839 void construct_from_tuple(Alloc& alloc, T* ptr, \
840 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
841 { \
842 boost::unordered::detail::func::call_construct(alloc, ptr, \
843 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
844 ); \
845 }
846
847# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
848 namespace_ get<n>(x)
849
850#elif !defined(__SUNPRO_CC)
851
852# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
853 template<typename Alloc, typename T> \
854 void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>) \
855 { \
856 new ((void*) ptr) T(); \
857 } \
858 \
859 BOOST_PP_REPEAT_FROM_TO(1, n, \
860 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
861
862# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
863 template<typename Alloc, typename T, \
864 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
865 void construct_from_tuple(Alloc&, T* ptr, \
866 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
867 { \
868 new ((void*) ptr) T( \
869 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
870 ); \
871 }
872
873# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
874 namespace_ get<n>(x)
875
876#else
877
878 template <int N> struct length {};
879
880# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
881 template<typename Alloc, typename T> \
882 void construct_from_tuple_impl( \
883 boost::unordered::detail::func::length<0>, Alloc&, T* ptr, \
884 namespace_ tuple<>) \
885 { \
886 new ((void*) ptr) T(); \
887 } \
888 \
889 BOOST_PP_REPEAT_FROM_TO(1, n, \
890 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
891
892# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
893 template<typename Alloc, typename T, \
894 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
895 void construct_from_tuple_impl( \
896 boost::unordered::detail::func::length<n>, Alloc&, T* ptr, \
897 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
898 { \
899 new ((void*) ptr) T( \
900 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
901 ); \
902 }
903
904# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
905 namespace_ get<n>(x)
906
907#endif
908
909BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
910
911#if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE)
912 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::)
913#endif
914
915#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
916#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL
917#undef BOOST_UNORDERED_GET_TUPLE_ARG
918
919#if defined(__SUNPRO_CC)
920
921 template <typename Alloc, typename T, typename Tuple>
922 void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
923 {
924 construct_from_tuple_impl(
925 boost::unordered::detail::func::length<
926 boost::tuples::length<Tuple>::value>(),
927 alloc, ptr, x);
928 }
929
930#endif
931
932 ////////////////////////////////////////////////////////////////////////////
933 // Trait to check for piecewise construction.
934
935 template <typename A0>
936 struct use_piecewise {
937 static choice1::type test(choice1,
938 boost::unordered::piecewise_construct_t);
939
940 static choice2::type test(choice2, ...);
941
942 enum { value = sizeof(choice1::type) ==
943 sizeof(test(choose(), boost::unordered::detail::make<A0>())) };
944 };
945
946#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
947
948 ////////////////////////////////////////////////////////////////////////////
949 // Construct from variadic parameters
950
951 // For the standard pair constructor.
952
953 template <typename Alloc, typename T, typename... Args>
954 inline void construct_value_impl(Alloc& alloc, T* address,
955 BOOST_FWD_REF(Args)... args)
956 {
957 boost::unordered::detail::func::call_construct(alloc,
958 address, boost::forward<Args>(args)...);
959 }
960
961 // Special case for piece_construct
962 //
963 // TODO: When possible, it might be better to use std::pair's
964 // constructor for std::piece_construct with std::tuple.
965
966 template <typename Alloc, typename A, typename B,
967 typename A0, typename A1, typename A2>
968 inline typename enable_if<use_piecewise<A0>, void>::type
969 construct_value_impl(Alloc& alloc, std::pair<A, B>* address,
970 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
971 {
972 boost::unordered::detail::func::construct_from_tuple(alloc,
973 boost::addressof(address->first), boost::forward<A1>(a1));
974 boost::unordered::detail::func::construct_from_tuple(alloc,
975 boost::addressof(address->second), boost::forward<A2>(a2));
976 }
977
978#else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
979
980////////////////////////////////////////////////////////////////////////////////
981// Construct from emplace_args
982
983 // Explicitly write out first three overloads for the sake of sane
984 // error messages.
985
986 template <typename Alloc, typename T, typename A0>
987 inline void construct_value_impl(Alloc&, T* address,
988 emplace_args1<A0> const& args)
989 {
990 new((void*) address) T(boost::forward<A0>(args.a0));
991 }
992
993 template <typename Alloc, typename T, typename A0, typename A1>
994 inline void construct_value_impl(Alloc&, T* address,
995 emplace_args2<A0, A1> const& args)
996 {
997 new((void*) address) T(
998 boost::forward<A0>(args.a0),
999 boost::forward<A1>(args.a1)
1000 );
1001 }
1002
1003 template <typename Alloc, typename T, typename A0, typename A1, typename A2>
1004 inline void construct_value_impl(Alloc&, T* address,
1005 emplace_args3<A0, A1, A2> const& args)
1006 {
1007 new((void*) address) T(
1008 boost::forward<A0>(args.a0),
1009 boost::forward<A1>(args.a1),
1010 boost::forward<A2>(args.a2)
1011 );
1012 }
1013
1014 // Use a macro for the rest.
1015
1016#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
1017 template < \
1018 typename Alloc, typename T, \
1019 BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \
1020 > \
1021 inline void construct_value_impl(Alloc&, T* address, \
1022 boost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) < \
1023 BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \
1024 > const& args) \
1025 { \
1026 new((void*) address) T( \
1027 BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, \
1028 args.a)); \
1029 }
1030
1031 BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
1032 BOOST_UNORDERED_CONSTRUCT_IMPL, _)
1033
1034#undef BOOST_UNORDERED_CONSTRUCT_IMPL
1035
1036 // Construct with piece_construct
1037
1038 template <typename Alloc, typename A, typename B,
1039 typename A0, typename A1, typename A2>
1040 inline void construct_value_impl(Alloc& alloc, std::pair<A, B>* address,
1041 boost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
1042 typename enable_if<use_piecewise<A0>, void*>::type = 0)
1043 {
1044 boost::unordered::detail::func::construct_from_tuple(alloc,
1045 boost::addressof(address->first), args.a1);
1046 boost::unordered::detail::func::construct_from_tuple(alloc,
1047 boost::addressof(address->second), args.a2);
1048 }
1049
1050#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1051
1052}}}}
1053
1054namespace boost { namespace unordered { namespace detail {
1055
1056 ////////////////////////////////////////////////////////////////////////////
1057 //
1058 // array_constructor
1059 //
1060 // Allocate and construct an array in an exception safe manner, and
1061 // clean up if an exception is thrown before the container takes charge
1062 // of it.
1063
1064 template <typename Allocator>
1065 struct array_constructor
1066 {
1067 typedef boost::unordered::detail::allocator_traits<Allocator> traits;
1068 typedef typename traits::pointer pointer;
1069
1070 Allocator& alloc_;
1071 pointer ptr_;
1072 pointer constructed_;
1073 std::size_t length_;
1074
1075 array_constructor(Allocator& a)
1076 : alloc_(a), ptr_(), constructed_(), length_(0)
1077 {
1078 constructed_ = pointer();
1079 ptr_ = pointer();
1080 }
1081
1082 ~array_constructor() {
1083 if (ptr_) {
1084 for(pointer p = ptr_; p != constructed_; ++p) {
1085 boost::unordered::detail::func::destroy(
1086 boost::addressof(*p));
1087 }
1088
1089 traits::deallocate(alloc_, ptr_, length_);
1090 }
1091 }
1092
1093 template <typename V>
1094 void construct(V const& v, std::size_t l)
1095 {
1096 BOOST_ASSERT(!ptr_);
1097 length_ = l;
1098 ptr_ = traits::allocate(alloc_, length_);
1099 pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_);
1100 for(constructed_ = ptr_; constructed_ != end; ++constructed_) {
1101 new ((void*) boost::addressof(*constructed_)) V(v);
1102 }
1103 }
1104
1105 pointer get() const
1106 {
1107 return ptr_;
1108 }
1109
1110 pointer release()
1111 {
1112 pointer p(ptr_);
1113 ptr_ = pointer();
1114 return p;
1115 }
1116
1117 private:
1118
1119 array_constructor(array_constructor const&);
1120 array_constructor& operator=(array_constructor const&);
1121 };
1122}}}
1123
1124#if defined(BOOST_MSVC)
1125#pragma warning(pop)
1126#endif
1127
1128#endif
1129

source code of boost/boost/unordered/detail/allocate.hpp