August 2009 - Boost - lists.preview.boost.org

boost.lockfree review request
by Tim Blechmann 17 Aug '09

17 Aug '09

hi all, i would like to submit a small library of lock-free data structures for review. boost.lockfree provides implementations of lock-free data structures. lock-free data structures can be accessed by multiple threads without the necessity of blocking synchronization primitives such as guards. lock-free data structures can be used in real-time systems, where blocking algorithms may lead to high worst-case execution times, to avoid priority inversion, or to increase the scalability for multi-processor machines. boost.lockfree provides: * boost::lockfree::fifo, a lock-free fifo queue * boost::lockfree::stack, a lock-free stack the code is available from the boost vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=boost_… and from my personal git repository: git://tim.klingt.org/boost_lockfree.git http://tim.klingt.org/git?p=boost_lockfree.git the documentation is available at: http://tim.klingt.org/boost_lockfree/ thanks in advance, tim -- tim(a)klingt.org http://tim.klingt.org You don't have to call it music if the term shocks you. John Cage

1 0

[1.40.0] Unmerged changes delaying beta 1
by Beman Dawes 17 Aug '09

17 Aug '09

There seem to be a large number of changes to trunk that have not been merged into branches/release. Perhaps a lot of merges were forgotten after the bug fixing sprint. All of the libraries listed below are suspect, although some may just be holding changes until after the release. "svn diff" can be used to see exactly what changes have not been merged. Here is a simple Windows batch file that eases typing; perhaps someone could post a Unix equivalent. @echo off if not %1$==$ goto usage_ok echo Usage: unmerged library-name goto done :usage_ok svn diff %2 %3 %4 %5 %6 http://svn.boost.org/svn/boost/branches/release/boost/%1.hpp http://svn.boost.org/svn/boost/trunk/boost/%1.hpp svn diff %2 %3 %4 %5 %6 http://svn.boost.org/svn/boost/branches/release/boost/%1 http://svn.boost.org/svn/boost/trunk/boost/%1 svn diff %2 %3 %4 %5 %6 http://svn.boost.org/svn/boost/branches/release/libs/%1 http://svn.boost.org/svn/boost/trunk/libs/%1 :done If your library has changes that need to be merged, please do so right away. I'll hold off on the beta until Monday morning to give folks a chance to do merges and let tests cycle. --Beman accumulators algorithm any array asio assign bimap bind circular_buffer compatibility concept concept_check config conversion crc date_time detail disjoint_sets dynamic_bitset exception flyweight foreach format function function_types functional fusion gil graph integer io iostreams iterator lambda math mpi mpl multi_array multi_index numeric optional parameter pool preprocessor program_options property_map proto ptr_container python random range rational regex scope_exit serialization signals smart_ptr spirit statechart static_assert system thread timer tokenizer tr tuple type_traits typeof units unordered utility variant wave xpressive

13 16

[bgl] Transitive closure
by Gustavo Gutiérrez 14 Aug '09

14 Aug '09

Hello, I am trying to compute the transitive closure of a graph. The definition of the graph is: typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_name_t, int> > graph_t; The code that calls the transitive closure function is: (g is of type graph_t) // prepare a map Vertex-int. map<Vertex,int> extmap; VertexIt vi, v_end; int i = 0; for (tie(vi,v_end) = vertices(g); vi != v_end; ++vi, i++) { extmap.insert(pair<Vertex,int>(*vi,i)); } associative_property_map<map<Vertex,int> > tempMap(extmap); map<Vertex,Vertex> vmap; adjacency_list<> c; boost::transitive_closure(g, c, vmap, tempMap); According with the documentation, tempMap must be a map from vertices to integers. When I try to compile the program, the following error occurs: /usr/local/include/boost/graph/transitive_closure.hpp:182: error: invalid initialization of reference of type 'const std::vector<long unsigned int, std::allocator<long unsigned int> >&' from expression of type 'std::vector<int, std::allocator<int> >' After taking a look at the file, the vector successors is defined as: std::vector<std::vector<cg_vertex> > successors(...); The error occurs with the following call: detail::union_successor_sets(successors[u], successors[v], successors[u]); the definition of union_successor_sets is: inline void union_successor_sets(const std::vector < std::size_t > &s1, const std::vector < std::size_t > &s2, std::vector < std::size_t > &s3) {...} Probably I am really wrong, but successors[u] is an std::vector<cg_vertex> and the function expects a std::vector < std::size_t >. So size_t and cg_vertex should be the same type, which according with the error reported by the compiler is not true. Can someone give me a hint on how to solve my problem? Thaks in advance.

2 2

stack-allocated STL-containers
by Stefan Strasser 13 Aug '09

13 Aug '09

I recently ran into the problem that a local container on the stack, which was likely to be very small, but its size was still not known at compile-time, consumed a considerable amount of runtime because of allocation/deallocation. e.g. void do(istream &i){ vector<int> vec; vec.reserve(20); while(...){ int tmp; i >> tmp; vec.push_back(tmp); } } so I wrote an allocator that I think is generally useful and could be added e.g. to Boost.Array: void do(int n){ int buffer[20]; stack_allocator<int,20> alloc(buffer); vector<int,stack_allocator<int,20> > vec(alloc); vec.reserve(alloc.max_stack_size()); while(...){ int tmp; i >> tmp; vec.push_back(tmp); } } the vector operates on the stack as long as there is enough space, and moves to the heap afterwards. in most cases there is no dynamic allocation. here's the source: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=stack_… it uses the simple_seq_fit allocation algorithm described here: http://www.boost.org/doc/libs/1_37_0/doc/html/interprocess/allocators_conta…

4 5

Generic copy-on-write infrastructure in boost?
by Jason Dictos 13 Aug '09

13 Aug '09

Hi, I'm looking for a way to implement a project using some copy-on-write feature, similar to how STL strings use reference counters to prevent needles copying of data. Is there anything in boost to help me out with this? -Jason ---------------------------------- Check out the Barracuda Spam & Virus Firewall - offering the fastest virus & malware protection in the industry: www.barracudanetworks.com/spam

5 7

[Serialization] Bizarre bug
by Jarl Lindrud 12 Aug '09

12 Aug '09

There is a rather bizarre bug in Boost.Serialization, that was reported on this list three years ago: http://article.gmane.org/gmane.comp.lib.boost.devel/147010/match=serializat… +bizarre+bug To sum up, a piece of code that is never even executed, is causing a serialization error in a different part of the program. Unfortunately it seems that this bug was never fixed - I just tried it on Boost 1.39.0, and the bug is still there. Any chance something can be done about it? For reference, here is the sample program that reproduces the issue: #include <sstream> #include <string> #include <vector> #include <boost/archive/text_iarchive.hpp> #include <boost/archive/text_oarchive.hpp> #include <boost/serialization/vector.hpp> template<typename Archive> struct X { template<typename T> void operator<<(const T &t) { Archive &archive = (*(Archive *) NULL); archive << t; } }; void dummy() { typedef boost::archive::text_oarchive Archive; X<Archive> &x = * (X<Archive> *) NULL; std::vector<char> *pt = NULL; // uncomment this line to cause the test in main() to fail //x << pt; } int main(int argc, char* argv[]) { std::vector<char> v0(25, '%'); std::vector<char> v1; std::ostringstream ostr; boost::archive::text_oarchive(ostr) & v0; std::istringstream istr(ostr.str()); boost::archive::text_iarchive(istr) & v1; bool ok = (v0 == v1); return 0; }

7 35

[mpl] strange vector_c and integral_c construction
by Maxim Yanchenko 12 Aug '09

12 Aug '09

Hi all, > Probably this is well-known and I just failed to find it in the docs and mailing list. According to the docs (http://www.boost.org/doc/libs/1_39_0/libs/mpl/doc/refmanual/integral-sequen…) typedef seq_c<T,c1,c2,... cn> s; Semantics: s is a sequence seq of integral constant wrappers integral_c<T,c1>, integral_c<T,c2>, ... integral_c<T,cn>. Consider the following example: const int64_t max_int = integer_traits<int>::const_max; const int64_t max_int_plus_1 = max_int + 1; BOOST_MPL_ASSERT(( equal< vector_c< int64_t, 1 > , vector< integral_c< int64_t, 1 > > > )); BOOST_MPL_ASSERT(( equal< vector_c< int64_t, max_int > , vector< integral_c< int64_t, max_int > > > )); BOOST_MPL_ASSERT(( equal< vector_c< int64_t, max_int_plus_1 > , vector< integral_c< int64_t, max_int_plus_1 > > > )); The first assert passes, while the second and third fail with the following error messages (removed repetition of 2147483647l for readability): test.h:149: error: ************mpl::equal<mpl::vector_c<int64_t, 2147483647l, 2147483647l, ...>, mpl::vector<mpl_::integral_c<int64_t, 2147483647>>, is_same<true> >::************' test.h:153: error: ************mpl::equal<mpl::vector_c<int64_t, -0x00000000080000000l, 2147483647l, ...>, mpl::vector<mpl_::integral_c<int64_t, 2147483648ll>>, is_same<true> >::************' I consider these errors as a contradiction to the docs statement. Probably, I configured MPL wrong, as I see in the preprocessed code, where long is used (boost/mpl/aux_/preprocessed/gcc/vector_c.hpp) template< typename T, long C0 = LONG_MAX, long C1 = LONG_MAX, long C2 = LONG_MAX , long C3 = LONG_MAX, long C4 = LONG_MAX, long C5 = LONG_MAX , long C6 = LONG_MAX, long C7 = LONG_MAX, long C8 = LONG_MAX , long C9 = LONG_MAX, long C10 = LONG_MAX, long C11 = LONG_MAX , long C12 = LONG_MAX, long C13 = LONG_MAX, long C14 = LONG_MAX , long C15 = LONG_MAX, long C16 = LONG_MAX, long C17 = LONG_MAX , long C18 = LONG_MAX, long C19 = LONG_MAX > struct vector_c; I'm using GCC 3.4.6, on Linux-64, compiling 32-bit binary (so int and long are of same size, and boost::int64_t is bigger than long). Thanks, Maxim (to reply in private, please use FirstName.LastName at gmail.com)

4 4

Microsoft Security Bulletin MS09-03: Vulnerabilities in Visual Studio Active Template Library Could Allow Remote Code Execution (969706)
by Christian Eckstein 12 Aug '09

12 Aug '09

Hi, I need to know the impact of the following security bulletin on Boost: Microsoft Security Bulletin MS09-03: Vulnerabilities in Visual Studio Active Template Library Could Allow Remote Code Execution (969706). I found usage of ATL only in the range and regex libraries and it seems that only string and array classes are used. None of the problematic methods seem to be used that are described in the checklist at http://msdn.microsoft.com/en-us/visualc/ee309358.aspx. - No class implements IUnknown so there is no ActiveX control. - No PROP_* macros are used - VT_* is not used - ReadFromStream is not used I think no modification of Boost and no recompilation of the Boost binaries is needed. I would be very happy if somebody could confirm this. Kind regards, Christian

2 1

persistence library proposal (with prototype implementation)
by Stefan Strasser 12 Aug '09

12 Aug '09

Is there any interest to include a persistence library in boost, built upon the boost serialization library? the basic idea is: transaction tx; change_objects(); tx.commit(); all changes made by change_objects() should be undone if tx is destroyed without calling commit(), e.g. because of an exception thrown by change_objects(). the library should provide ACID transaction properties, so that multiple transactions (in different threads) can work on the same objects and conflicts are discovered by the library. further, an application crash should be recovered, with the changes made by a transaction either committed as a whole or undone. to partition your object model into many different objects, which can be saved to disk and loaded back on demand, there is a new smart pointer introduced, which behaves like smart_ptr and is convertible to smart_ptr. objects that are handled by this smart pointer and are no longer used in memory are not destroyed but saved to disk. only objects which are no longer in use either in memory or on disk are destroyed. the only requirement on persistent objects would be to model the concept "Serializable" as defined by boost serialization. e.g. a linked list, whose elements are loaded from disk on demand could look like: struct node{ db_ptr<node> next; private: //Serializable requirements }; void traverse(){ while(current) current=current->next; //operator-> loads the next node } prototype implementation --- i've attached a test case using the current implementation. it demonstrates multiple concurrent transactions.running isolated from each other. it models a bank, with multiple threads constantly withdrawing from one (random) bank account and depositing the amount on another. when two threads are using the same bank account at the same time, resulting in money being lost, an isolation_exception is thrown in one of the threads and the transaction can be restarted. there is no manual thread synchronization involved. the current implementation uses an optimistic multiversion approach, meaning that each transaction running concurrently is working on its own copy of an object. when the transaction is committed conflicts are discovered and an isolation_exception is thrown. several things like reference counting on disk and the recovery process after a crash aren't implemented yet, but the basics are in place and should give you an idea of what kind of a library I'm proposing.

4 12

different matrix library?
by DE 12 Aug '09

12 Aug '09

hi i'm new to boost so please don't blame me the question is do you need a matrix library which allows you to write clear, human readable code like dV = (1/m)*force + transpose(A)*g - cross_product(omega, V) //here dV is a derivative of velocity, m is (scalar) mass //A is transition matrix and //g is gravity acceleration vector //omega is angular velocity and V is velocity vector itself //force is defined in body space (e.g. aerodynamics and thrust) that is an expression of newton's 2nd law (or if you like 'change in momentum' law: d(m*V)/dt = d_local(m*V)/dt + (omega)x(m*V) = sum_of(forces) as you can see so far i'm a math nerd) of course it must be implemented through lazy evaluation technique (which immediately implies expression templates) ps i looked at uBLAS and the design seemed obsolete to me so i thought there could be a better approach then blindly following blas design pps thanks for reading til here and forgive for (possibly) wasting your time

9 39