- Boost - lists.boost.org

Re: [boost] MPL bitand.hpp and iso646.h on MSVC 2008
by Nelson, Erik - 2 24 Jan '10

24 Jan '10

After further research, I saw that this is a duplicate of very similar reports previously. I'm not sure if it's scheduled to be fixed, but it still seems to be a problem in boost v1.41 Thanks Erik

3 3

[lockfree::fifo] Review
by Andrew Venikov 24 Jan '10

24 Jan '10

I decided to start a new thread on this topic since the last thread on the same topic is pretty outdated and not everyone will see it. (you can disregard my reply to the previous thread as this one is more complete) First of all I think that having a library of lock-free algorithms/containers would be greatly beneficial to a great number of boost users. On the other hand, having implemented several lock-free algorithms, I know that it is notoriously hard to get them right. We'll need all the help we can get from knowledgeable people in the field. The implementation needs to be thoroughly reviewed. Let me give the first attempt at that. In this e-mail I'll be primarily concentrating on the algorithm correctness rather than the interface. First, let me start with the choice of the algorithm for the fifo queues: Magued Michael and Michael Scott's "Simple, Fast, and Practical Non-blocking and blocking concurrent queues". I really think it is the best choice. Having said that, however, I need to point out that there some inherent limitation in this algorithm. The first limitation is that you can't peek at the head of the queue without dequeueing the element first, hence you can't get an interface that is conformant with std::queue. But I truly believe that it will be the case with any lock-free queue implementation, hence we should abandon the hope of having a lock-free queue look the same as std::queue Second, this algorithm makes certain assumptions about the ability to access memory that has been freed. The algorithm can try to read memory that has been de-allocated. (See further down for description of how). Several debug implementations of malloc/free store every allocated element on one page and when the element is freed, the page is marked protected for both reading and writing. That means that this algorithm can only work with a subset of custom allocators. Your "free_list" for example can't work with it since it's possible for a node to be freed when you call "deallocate". The "caching_freelist" and "static_freelist" on the other hand work just fine because they never return the memory back to the system. Third, and the biggest limitation, is the algorithm's assumption that you can store a pointer to an element plus an ABA tag in a contiguous memory space that can be passed to a CAS instruction. I believe not all platforms provide a DCAS instruction, that's why you're trying to work around this issue by using "packed pointers", i.e. storing the ABA tag in the part of the pointer that presumably is never used. The problem with that, however, is that some libc implementations of malloc/free do use all the bits in the pointer for their own needs, so you can't assume that you can meddle with them. My experience with this algorithm shows that the safest approach is to use a pre-allocated array for the queue and replace pointers with indexes into the array. Assuming that the size of an index is sufficiently lower than the size of a pointer, you can use the remaining bits to store the ABA tag. This alleviates both point 2 and 3. This does mean however, that the queue can't have an unbound size, the size has to be specified during the queue instantiation. Fourth, on platforms where CAS is implemented using LL/SC (such as PowerPC and MIPS), it is possible to livelock. The problem with LL/SC on most platforms is that the write granulum for marking LL's address as "dirty" isn't just the memory pointed to by LL, but the whole cache line where the memory resides. On these platforms it is important to make sure that each "node" of the queue is located on a separate cache line. Here's the code of your enqueue: bool enqueue(T const & t) { node * n = alloc_node(t); if (n == NULL) return false; for (;;) { atomic_node_ptr tail (tail_); //1 read_memory_barrier(); //2 atomic_node_ptr next (tail->next); //3 if (likely(tail == tail_)) //4 { if (next.get_ptr() == 0) //5 { if ( tail->next.cas(next, n) )//6 { tail_.cas(tail, n); return true; } } else tail_.cas(tail, next.get_ptr()); } } } 1. You're missing write barrier after a call to alloc_node(). Rational: alloc_node sets the "next" pointer of the newly allocated node to NULL. That is a store to shared memory. Setting next pointer to NULL has to be observable to other threads BEFORE they observe the inserted node. If you don't insert a write barrier, it is possible for other threads to see the new element in the list before element's next pointer is initialized with NULL. 2. You've misplaced the read_barrier. Rational: Line 4 checks the validity of the load done on line 3. That means that the read_barrier should be between lines 3 and 4. If you don't have a read_barrier after loading *tail->next, then this load can happen after the load of tail_ on line 4, which defies the purpose of line 4. Here's a scenario that makes it clear: State: queue is well-formed and tail_ points to the last element. 1. Thread A executes line1. State: the queue is unchanged and Thread A has a local copy of tail_ 2. Since there's no read barrier after line 3, loads at lines 3 and 4 happen out-of-order. tail_ is pre-loaded for comparison at line 4. 3. Thread B removes the element pointed by tail_, advances tail_ further State: tail_ is advanced, the old element is removed and given back to the allocator. A's local copy of tail_ becomes stale. 4. Thread A executes line 3 State: A's copy of tail is stale. This copy is used to load memory that has been reclamed by the allocator and possibly modified. The value of the memory happens to be 0. 5. Thread A executes line 4. Since tail_ has been preloaded, line 4 succedes. 6. Line 5 succedes 7. Line 6 succedes. Boom: you've just modified a piece of memory not controlled by the queue. You still need to have a barrier between lines 1 and 3, but here only a data dependency barrier will suffice, which is a weaker form of a read barrier and on most all platforms is a no-op since data dependent loads can be handled by processors automatically. 3. Your tail_ and head_ should be volatile. Furthermore, the getters for you tagged_ptr (like get_ptr, operator->() and operator* ) should return pointers/references to volatile types. Rational: If your tail_ is not volatile, then the compiler is free to load head_ just once and line 4 effectively becomes a no-op. Here's code for your "dequeue": bool dequeue (T * ret) { for (;;) { atomic_node_ptr head (head_); //1 read_memory_barrier(); //2 atomic_node_ptr tail(tail_); //3 node * next = head->next.get_ptr(); //4 if (likely(head == head_)) //5 { if (head.get_ptr() == tail.get_ptr()) //6 { if (next == 0) return false; tail_.cas(tail, next); } else { *ret = next->data; //7 if (head_.cas(head, next)) //8 { dealloc_node(head.get_ptr()); //9 return true; } } } } } 1. Again, you need to put read_barrier between lines 4 and 5. Only data dependency barrier will suffice at line 2. 2. You need to add write barrier after line 7 for the same reason as in the enqueue. Hope this was descriptive, Andy Venikov.

10 64

[1.42.0] Beta 1 available on Sourceforge
by Beman Dawes 23 Jan '10

23 Jan '10

1.42.0 beta 1 is now available. This release contains one new library and numerous bug fixes for existing libraries. For details, including download links, see http://beta.boost.org/users/news/version_1_42_0 The release can also be downloaded directly from SourceForge. See http://sourceforge.net/projects/boost/files/ There are a few known problems in the beta: * An odd 'simplesectsep' tag that doxygen creates which has turned up in the generated documentation, such as at http://tinyurl.com/ygbgkge. * Doxygen isn't expanding some of the macros in Boost.Accumulators. * A nasty bug in Spirit affecting copy construction of rules (rev. 50156) has been tracked down and fixed, but the fix was too late for the beta. These will be fixed in the final release. Please report any other problems by responding to this message on either the users or the main developers mailing lists. Thanks, --The Boost release team

3 3

help detecting presence of operator[]
by Jeffrey Hellrung 23 Jan '10

23 Jan '10

Hi all, I'm trying to perform a compile-time check to determine if a class has an operator[]. I'm using a "trick" I think I've seen in Adobe's library and on this list in the past: -------- BEGIN CODE -------- template< class T > struct has_op_bracket { struct base_t { void operator[]( int ); }; struct derived_t : T, base_t { }; template< void (base_t::*)( int ) > struct sfinae { typedef char type; }; template< class U > static typename sfinae< &U::operator[] >::type is_ambiguous(int); template< class U > static int is_ambiguous(...); static const bool value = sizeof( is_ambiguous< derived_t >(0) ) != 1; }; -------- END CODE -------- The way I understand this working is if T has no operator[], then &derived_t::operator[] unambiguously refers to *base_t::operator[], and so the first is_ambiguous overload is selected. Otherwise, &derived_t::operator[] is ambiguous, which is sufficient (I guess...?) for SFINAE to kick in, and the second is_ambiguous overload is selected. Now given the following definitions of X0 and X1: -------- BEGIN CODE -------- struct X0 { }; struct X1 { void operator[](void*); }; -------- END CODE -------- then the following static assertions pass, as expected: -------- BEGIN CODE -------- BOOST_STATIC_ASSERT(( !has_op_bracket<X0>::value )); BOOST_STATIC_ASSERT(( has_op_bracket<X1>::value )); -------- END CODE -------- However, if X2 is defined as -------- BEGIN CODE -------- struct X2 { template< class T > struct R : T { }; template< class T > typename R<T>::type operator[](T); }; -------- END CODE -------- then has_op_bracket<X2>::value fails to compile on MSVC9, but (according to Dinkum Exam[1]) it does compile just fine on "EDG/C++". The error in MSVC9 is -------- BEGIN OUTPUT -------- error C2516: 'T' : is not a legal base class 1> d:\test\main.cpp(9) : see declaration of 'T' 1> d:\test\main.cpp(9) : see reference to class template instantiation 'X2::R<T>' being compiled 1> with 1> [ 1> T=int 1> ] 1> d:\test\main.cpp(21) : see reference to class template instantiation 'has_op_bracket<T>' being compiled 1> with 1> [ 1> T=X2 1> ] -------- END OUTPUT -------- generated by the following program: -------- BEGIN CODE -------- template< class T > struct has_op_bracket { struct base_t { void operator[]( int ) const; }; struct derived_t : T, base_t { }; template< void (base_t::*)( int ) const > struct sfinae { typedef char type; }; template< class U > static typename sfinae< &U::operator[] >::type is_ambiguous(int); template< class U > static int is_ambiguous(...); static const bool value = sizeof( is_ambiguous< derived_t >(0) ) != 1; // line 9 }; struct X2 { template< class T > struct R : T { }; template< class T > typename R<T>::type operator[](T); }; int main() { has_op_bracket<X2>::value; // line 21 return 0; } -------- END CODE -------- What I don't understand is why MSVC is trying to instantiate R<int>. It seems to be grabbing the int from the parameter type of the member function pointer template parameter in sfinae, which doesn't seem like the right thing to do. I can change that parameter to anything else (as long as it doesn't have a nested type typedef) and the error persists. Is MSVC correct, or is this a compiler bug? Either way, is there an alternative, more portable approach to achieve the desired effect? Thanks in advance, - Jeff [1] http://www.dinkumware.com/exam/default.aspx

2 3

[test] mock objects
by Michael Robinson 23 Jan '10

23 Jan '10

Hi, I am a boost unit test newbie. I have been looking at the documentation and examples and would like to know if there is any documentation that specifically addresses the use of mock objects: I am specifically interested in how to interpret the output of est_example1.cpp and est_example2.cpp; as well as learning what the required format of the expectations log file (.elog) to be used for logged_exp_example.cpp is. Thank you, Mike ____________________________________________________________ Nutrition Improve your career health. Click now to study nutrition! http://thirdpartyoffers.netzero.net/TGL2241/c?cp=U1sp_d8XptT4jkLd7e_KlAAAJ1…

2 2

[typeof] Variadic functions
by Sergey Zubkovsky 22 Jan '10

22 Jan '10

Hi, Here is a patch to support variadic functions in the Boost.Typeof. Can anyone check it and commit? Thank you. Index: register_functions.hpp =================================================================== --- register_functions.hpp (revision 57837) +++ register_functions.hpp (working copy) @@ -18,18 +18,25 @@ #include BOOST_TYPEOF_INCREMENT_REGISTRATION_GROUP() #ifndef BOOST_TYPEOF_LIMIT_FUNCTION_ARITY -#define BOOST_TYPEOF_LIMIT_FUNCTION_ARITY 10 +#define BOOST_TYPEOF_LIMIT_FUNCTION_ARITY 15 #endif enum { FUN_ID = BOOST_TYPEOF_UNIQUE_ID(), - FUN_PTR_ID = FUN_ID + 1 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), - FUN_REF_ID = FUN_ID + 2 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), - MEM_FUN_ID = FUN_ID + 3 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), - CONST_MEM_FUN_ID = FUN_ID + 4 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), - VOLATILE_MEM_FUN_ID = FUN_ID + 5 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), - VOLATILE_CONST_MEM_FUN_ID = FUN_ID + 6 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY) + FUN_VAR_ID = FUN_ID + 1 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + FUN_PTR_ID = FUN_ID + 2 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + FUN_VAR_PTR_ID = FUN_ID + 3 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + FUN_REF_ID = FUN_ID + 4 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + FUN_VAR_REF_ID = FUN_ID + 5 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + MEM_FUN_ID = FUN_ID + 6 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + MEM_FUN_VAR_ID = FUN_ID + 7 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + CONST_MEM_FUN_ID = FUN_ID + 8 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + CONST_MEM_FUN_VAR_ID = FUN_ID + 9 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + VOLATILE_MEM_FUN_ID = FUN_ID + 10 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + VOLATILE_MEM_FUN_VAR_ID = FUN_ID + 11 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + VOLATILE_CONST_MEM_FUN_ID = FUN_ID + 12 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY), + VOLATILE_CONST_MEM_FUN_VAR_ID = FUN_ID + 13 * BOOST_PP_INC(BOOST_TYPEOF_LIMIT_FUNCTION_ARITY) }; BOOST_TYPEOF_BEGIN_ENCODE_NS Index: register_functions_iterate.hpp =================================================================== --- register_functions_iterate.hpp (revision 57837) +++ register_functions_iterate.hpp (working copy) @@ -6,6 +6,12 @@ #define n BOOST_PP_ITERATION() +#if ( n > 1 ) +# define comma , +#else +# define comma +#endif + // function pointers template<class V, class R BOOST_PP_ENUM_TRAILING_PARAMS(n, class P)> @@ -15,6 +21,13 @@ typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_PTR_ID + n) type; }; +template<class V, class R BOOST_PP_ENUM_TRAILING_PARAMS(n, class P)> +struct encode_type_impl<V, R(*)(BOOST_PP_ENUM_PARAMS(n, P)comma ...)> +{ + typedef R BOOST_PP_CAT(P, n); + typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_VAR_PTR_ID + n) type; +}; + template<class Iter> struct decode_type_impl<boost::mpl::size_t<FUN_PTR_ID + n>, Iter> { @@ -24,6 +37,15 @@ typedef BOOST_PP_CAT(iter, BOOST_PP_INC(n)) iter; }; +template<class Iter> +struct decode_type_impl<boost::mpl::size_t<FUN_VAR_PTR_ID + n>, Iter> +{ + typedef Iter iter0; + BOOST_TYPEOF_DECODE_PARAMS(BOOST_PP_INC(n)) + typedef BOOST_PP_CAT(p, n)(*type)(BOOST_PP_ENUM_PARAMS(n, p)comma ...); + typedef BOOST_PP_CAT(iter, BOOST_PP_INC(n)) iter; +}; + #ifndef BOOST_TYPEOF_NO_FUNCTION_TYPES // function references @@ -35,6 +57,13 @@ typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_REF_ID + n) type; }; + template<class V, class R BOOST_PP_ENUM_TRAILING_PARAMS(n, class P)> + struct encode_type_impl<V, R(&)(BOOST_PP_ENUM_PARAMS(n, P)comma ...)> + { + typedef R BOOST_PP_CAT(P, n); + typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_VAR_REF_ID + n) type; + }; + template<class Iter> struct decode_type_impl<boost::mpl::size_t<FUN_REF_ID + n>, Iter> { @@ -53,6 +82,13 @@ typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_ID + n) type; }; + template<class V, class R BOOST_PP_ENUM_TRAILING_PARAMS(n, class P)> + struct encode_type_impl<V, R(BOOST_PP_ENUM_PARAMS(n, P)comma ...)> + { + typedef R BOOST_PP_CAT(P, n); + typedef BOOST_TYPEOF_ENCODE_PARAMS(BOOST_PP_INC(n), FUN_VAR_ID + n) type; + }; + template<class Iter> struct decode_type_impl<boost::mpl::size_t<FUN_ID + n>, Iter> { @@ -62,6 +98,15 @@ typedef BOOST_PP_CAT(iter, BOOST_PP_INC(n)) iter; }; + template<class Iter> + struct decode_type_impl<boost::mpl::size_t<FUN_VAR_ID + n>, Iter> + { + typedef Iter iter0; + BOOST_TYPEOF_DECODE_PARAMS(BOOST_PP_INC(n)) + typedef BOOST_PP_CAT(p, n)(type)(BOOST_PP_ENUM_PARAMS(n, p)comma ...); + typedef BOOST_PP_CAT(iter, BOOST_PP_INC(n)) iter; + }; + #endif//BOOST_TYPEOF_NO_FUNCTION_TYPES #ifndef BOOST_TYPEOF_NO_MEMBER_FUNCTION_TYPES @@ -83,5 +128,6 @@ #define BOOST_TYPEOF_id VOLATILE_CONST_MEM_FUN_ID #include <boost/typeof/register_mem_functions.hpp> +#undef comma #undef n #endif

2 3

[iostreams 1.42 beta1] gcc warning
by Christoph Duelli 22 Jan '10

22 Jan '10

boost/iostreams/detail/config/unreachable_return.hpp:25:7: warning: no newline at end of file would be great it that could be fixed. Best regards Christoph

1 0

[Polygon] Template error in CodeWarrior when attempting union on polygon_set_data
by Kef Schecter 22 Jan '10

22 Jan '10

I hesitate to mark this as [Polygon] because the error message is in a different part of Boost. However, I have little idea what the actual cause of the problem is or what any of the relevant stuff even means, so I figure [Polygon] is as good as anything at the moment... As before, this is a custom version of CodeWarrior an embedded ARM system, so I have no idea how well it corresponds with other versions of CodeWarrior. Here is a trivial program that illustrates the problem, using the BOOST_VERY_LITTLE_SFINAE patch from the last discussion here: #include <iostream> #define BOOST_VERY_LITTLE_SFINAE #include <boost/polygon/polygon.hpp> using namespace boost::polygon; using namespace boost::polygon::operators; int main() { polygon_set_data<int> ps; ps += rectangle_data<int>(0, 0, 1, 1); return 0; } This results in the following error message : Error : illegal use of template argument dependent type 'T::type' The error occurs in this part of boost/mpl/aux_/preprocessed/plain/and.hpp: template< typename T1, typename T2, typename T3, typename T4 > struct and_impl< true,T1,T2,T3,T4 > : and_impl< BOOST_MPL_AUX_NESTED_TYPE_WKND(T1)::value , T2, T3, T4 , true_ > { }; Any ideas about what's wrong or how to fix it? - Kef

2 3

Re: [boost] boost::mpl::for_each and value_initialized
by Niels Dekker - address until 2010-10-10 22 Jan '10

22 Jan '10

>> Do I understand correctly that you want the memset call to be >> skipped for those compiler versions that have implemented >> value-initialization entirely correctly? Peter Foelsche wrote: > I'm only concerned with boost::mpl::for_each > This function calls a function object by passing an object of the > matching type. > The contents of this object usually do not matter -- and in case they > do, the programmer can write a default constructor to initialize this > object. So there is no need in boost::mpl::for_each to call > value_initialized. So you think the issue can be resolved properly, merely by modifying mpl/for_each.hpp, right? You proposed at http://lists.boost.org/Archives/boost/2009/09/155805.php to modify mpl/for_each.hpp by changing: ! value_initialized<arg> x; ! aux::unwrap(f, 0)(boost::get(x)); Into: ! aux::unwrap(f, 0)(arg()); I see some subtle differences here. First of all, boost::get(x) return a reference to an lvalue, while arg() is an rvalue. Do you think that's okay? Secondly, things *might* go wrong if arg doesn't have a user-declared default-constructor *and* the compiler hasn't correctly implemented value-initialization. That's why Fernando and I added the memset call to boost::value_initialized, of course. But you think the data members of the temporary arg() won't be accessed anyway, right? Unless arg has a user-declared default-constructor? I'm sorry I don't know mpl/for_each.hpp well enough. But if the answer to each of the above questions is yes, I guess your proposal is fine. Kind regards, Niels -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center

2 1

MPL bitand.hpp and iso646.h on MSVC 2008
by Nelson, Erik - 2 21 Jan '10

21 Jan '10

If I make a program like #undef BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS #include <iso646.h> #include <boost/mpl/bitand.hpp> I get an error like boost/mpl/aux_/include_preprocessed.hpp(37) : fatal error C1083: Cannot open include file: 'boost/mpl/aux_/preprocessed/plain/&.hpp': No such file or directory And if I change it to #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS #include <iso646.h> #include <boost/mpl/bitand.hpp> I get 1>c:\work\boost\boost/mpl/aux_/numeric_op.hpp(86) : error C2332: 'struct' : missing tag name 1>c:\work\boost\boost/mpl/aux_/numeric_op.hpp(86) : error C3306: 'boost::mpl::<unnamed-tag>': unnamed class template is not allowed 1>c:\work\boost\boost/mpl/aux_/numeric_op.hpp(86) : error C2143: syntax error : missing ';' before '&' I think the problem is in boost/mpl/bitand.hpp, where #define AUX778076_OP_PREFIX bitand Is defined. 'bitand' is (nonconformantly) #defined to '&' in VC 2008's iso646.h, borking the definition of AUX778076_OP_PREFIX. The fix seems to be to #define AUX778076_OP_PREFIX to something else that MSVC doesn't stomp on. Thanks Erik

1 0