- Boost - lists.boost.org

[graph]Direct Edge Access
by Takatoshi Kondo 08 Mar '13

08 Mar '13

Hello, I'm using Boost.Graph version 1.53.0. I'm trying to write some graph algorithms and I want to minimize the requirements of the input graph. I have a question about Boost.Graph concepts. I wrote a very simple code as follows: typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS> G; int main() { G g; boost::add_edge(0, 1, g); auto res = boost::edge(0, 1, g); // Why can I call it? std::cout << std::boolalpha << res.second << std::endl; boost::graph_traits<G>::edge_descriptor e = res.first; std::cout << boost::source(e, g) << "," << boost::target(e, g) << std::endl; } It works, but I don't understand why I can call boost::edge(). According to the following document, AdjacencyMatrix concept provides Direct Edge Access functionality, so I can call edge(u,v,g) : http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/AdjacencyMatrix.html The class template adjacency_list is a model of VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable. http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/adjacency_list.html So, adjacency_list is not satisfied AdjacencyMatrix concept. I checked which function template is called, then I found the following function is called: boost/graph/detail/adjacency_list.hpp:1582 template <class Config, class Base> inline std::pair<typename Config::edge_descriptor, bool> edge(typename Config::vertex_descriptor u, typename Config::vertex_descriptor v, const adj_list_helper<Config, Base>& g_) { typedef typename Config::graph_type Graph; typedef typename Config::StoredEdge StoredEdge; const Graph& cg = static_cast<const Graph&>(g_); typedef typename Config::out_edge_iterator out_edge_iterator; const typename Config::OutEdgeList& el = cg.out_edge_list(u); typename Config::OutEdgeList::const_iterator it = graph_detail:: find(el, StoredEdge(v)); return std::make_pair( typename Config::edge_descriptor (u, v, (it == el.end() ? 0 : &(*it).get_property())), (it != el.end())); } Also, I found the following document: http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/using_adjacency_list.ht… This document describes that: edge() The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer. It seems that edge() is a part of the public interface of adjacency_list. But I think that it is not a part of any graph concepts. If I want to write an algorithm that depends on several graph concepts, not actual classes such as adjancency_list, I can use edge(u,v,g) only if the input graph class satisfies AdjacencyMatrix concept. Am I understanding correctly? Thanks, Taka

2 3

[locale] Memory leaks?
by Jookia 07 Mar '13

07 Mar '13

Hello! I've been debugging my application that uses Boost.Locale for the past five hours or so, and I've found it curious that it leaks memory. In order to stop it, I have to do a couple of weird things, such as including ICU in to my projects and calling u_cleanup at the end of my application. I also have to disable certain facets. I've put all this together in some source code, that by default won't leak, but uncommenting various parts will cause it to leak: // ---- BEGIN CODE ---------------------------------------------------- #include <boost/locale.hpp> #include <unicode/uclean.h> #include <iostream> using namespace boost::locale; using namespace std; int main() { generator gen; gen.categories( convert_facet | //collation_facet | // Various errors. //formatting_facet | // Various errors. //parsing_facet | // Various errors. message_facet | //codepage_facet | // Various errors. boundary_facet | calendar_facet | information_facet); locale newLoc = gen("zh_CN.GB18030"); locale::global(newLoc); cout.imbue(newLoc); // ios_info::get doesn't clean up after itself. //cout << as::date << time(0) << endl; // Do this at the end of the program to clean up resources. locale::global(std::locale("C")); cout.imbue(std::locale("C")); u_cleanup(); } // ---- END CODE ------------------------------------------------------ Dumping this as 'hello.cpp' and running this is how I'm debugging it: g++ hello.cpp -lboost_locale -licuuc && valgrind --leak-check=full --show-reachable=yes ./a.out Thanks, Jookia.

2 6

[interprocess] leaked named mutexes
by Eric Niebler 07 Mar '13

07 Mar '13

I recently discovered that a process can very easily leave a named mutex dangling. Consider the following: #include <cstdlib> #include <iostream> #include <boost/interprocess/sync/named_mutex.hpp> #include <boost/interprocess/sync/scoped_lock.hpp> namespace ip = boost::interprocess; char const *name = "mynamedmutex"; int main(int argc, char*argv[]) { ip::named_mutex mtx(ip::open_or_create, name); std::cout << "acquiring named mutex" << std::endl; ip::scoped_lock<ip::named_mutex> lock(mtx); std::cout << "acquired" << std::endl; exit(EXIT_FAILURE); // whoops } On my Linux box, this runs fine the first time, but the second time it hangs waiting to acquire the mutex. I have to manually delete the semaphore in /dev/shm/. This will happen whenever the process exits without calling destructors of locals; for instance: - std::exit - std::quick_exit - std::abort - std::terminate - a crash - assert failure - an unhandled exception - etc.. I find I can handle *some* of this by registering a terminate handler, an exit handler (and on C++11, a quick_exit handler) that calls boost::interprocess::named_mutex::remove. This raises a few questions, though... - Is there a better way? - Is it safe to `remove` the same named mutex multiple times? - Does this clean up only this process's use of the named_mutex, or does it nuke it from the system, even if another process is using it? (The docs suggest the latter, which is not what I want, is it?) Thanks, -- Eric Niebler Boost.org

5 5

[Graph][Parallel][PBGL] Bug deleting self loop edges
by bminano 07 Mar '13

07 Mar '13

Hello, I think I found a bug in the graph parallel library. I have a bidirectional adjacency list which has some self loop edges. When I try to delete them with remove_edge_if (or remove_out_edge_if or remove_in_edge_if) the edges are deleted, but it seems that some reference gets broken in the graph. If I iterate over the in_edges a reference to a self loop is found. But it does not happen if I iterate over the out_edges. If the graph is written in a graphviz file the self loop edges does not appear. I think there is some broken reference into the adjacency list that keeps the in_edges. I have two different pieces of code (one with pbgl and the other with bgl). They do the same, create a graph, delete the self-edges and print the in_edges. Could someone have a look at this problem? We want to use this library in our research but with this problem will not be possible. Thank you pbgl_in_edges.cpp <http://boost.2283326.n4.nabble.com/file/n4643903/pbgl_in_edges.cpp> bgl_in_edges.cpp <http://boost.2283326.n4.nabble.com/file/n4643903/bgl_in_edges.cpp> -- View this message in context: http://boost.2283326.n4.nabble.com/Graph-Parallel-PBGL-Bug-deleting-self-lo… Sent from the Boost - Dev mailing list archive at Nabble.com.

1 0

make_shared causes stack overflow with large objects
by Gregor Jasny 07 Mar '13

07 Mar '13

Hello, the bug described in #7965 causes stack overflows and sometimes hard to track crashes. I'd really appreciate if anyone could have a look. Thanks, Gregor

2 3

[thread] thread_specific_ptr leaks on VS2012 when using std::async()
by Klaim - Joël Lamotte 05 Mar '13

05 Mar '13

Hi, The title says it all. I think I found a memory leak with the help of boost.log author Andrei Semashev. I was using Boost.Log in Visual Studio 2012 (released one) and tried to use Visual Leak Detector because Visual Studio basic leak detector was reporting leaks. I isolated the leaks to usage of log and switched to VLD to check if the basic detector wasn't giving me false positive. I contacted Andrei to see if he could check it but he don't have VS2012 available so I setup some tests to isolate the problem. In the end of our exchange we concluded it was a false positive (it only leak on end of program). However it is still an annoying noise in the leak report logs, so people not understanding the source of this problem might be interested in this email. I attach the whole email exchange to this email, tell me if leak logs are necessary too. The last version of my test is at the end of the email (first program). Basically, the leak appear only when using std::async() in combination of boost::thread_specific_ptr : - using exclusively boost threading libraries (both with dynamic and static linking) result in no leak - using exclusively std threading libraries but not std::async() result in no leak - using std::async() result in a leak The second test program shows that using Intel Threading Building Blocks, I get leaks only if : - I use std::async() in combination with boost::thread_specific_ptr, as before (I mean I use tbb without a leak, then I add a std::async() call to the same task function and there is a leak) - I don't use std::async() but I don't manage the lifetime of tbb task scheduler We think the threads spawned by both tbb (that is supposed to be a superset of ppl) and std::async() (that is supposed to use ppl/concrt task scheduler) are not ended yet when the program reach the end of main (which seems logical as the task scheduler is then managed as a static global), making boost::thread_specific_ptr not release some data on thread destruction, as it is notified too late and any leak detection tool willl generate noise due to this. A way to fix this is to explicitely end the task scheduler, being tbb or ppl/concrt. I will use tbb task scheduler explicitely initialized/terminated in my project so it will solve the problem on my side. Joel Lamotte ------------------------------------ // this program was used to see the memory leak #define TEST_ASYNC // comment this to make it linear and not leak //#define WITH_BOOST_THREADS #define WITH_STD_ASYNC // uncomment this to leak //#define WITH_BOOST_LOG // boost log also leak if std::async is used #include <boost/thread.hpp> #ifdef WITH_BOOST_THREADS # include <boost/thread/future.hpp> # include <boost/chrono.hpp> # define THIS_THREAD boost::this_thread # define THREAD_LIB boost::thread # define CHRONO_LIB boost::chrono # define MY_FUTURE boost::future #else # include <future> # include <thread> # include <chrono> # define THIS_THREAD std::this_thread # define THREAD_LIB std::thread # define CHRONO_LIB std::chrono # define MY_FUTURE std::future #endif #ifdef WITH_BOOST_LOG # include <boost/log/trivial.hpp> # define MY_LOG BOOST_LOG_TRIVIAL(info) #else # include <iostream> # define MY_LOG std::cout << '\n' #endif #define BASIC_VS_LEAK_DETECTOR 0 #define VISUAL_LEAK_DETECTOR 1 #define LEAK_DETECTOR VISUAL_LEAK_DETECTOR #if LEAK_DETECTOR == BASIC_VS_LEAK_DETECTOR # define _CRTDBG_MAP_ALLOC # include <stdlib.h> # include <crtdbg.h> #else # include "vld.h" #endif struct my_data { char data[1024]; my_data() { MY_LOG << "CONSTRUCTOR my_data - " << THIS_THREAD::get_id(); } ~my_data() { MY_LOG << "DESTRUCTOR my_data - " << THIS_THREAD::get_id(); } }; boost::thread_specific_ptr< my_data > ts_ptr; void my_thread_foo() { ts_ptr.reset(new my_data()); } int work() { for( int i = 0; i < 42; ++i ) { MY_LOG << "THIS IS A MESSAGE - I = " << i; MY_LOG << "ts_ptr = " << ts_ptr.get(); my_thread_foo(); THIS_THREAD::sleep_for( CHRONO_LIB::milliseconds(10) ); } return 0; } int main(int argc, char *argv[]) { #if LEAK_DETECTOR == BASIC_VS_LEAK_DETECTOR // First simple memory leak detection for Visual Studio // use _crtBreakAlloc to put a breakpoint on the provided memory leak id allocation //_crtBreakAlloc = 1149; _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF ); #endif //int* k = new int[42]; // to check that memory leak detection does work MY_LOG << "Hello, World!"; #ifdef TEST_ASYNC # ifndef WITH_BOOST_THREADS std::vector< std::future<int> > work_in_progress(2); # ifdef WITH_STD_ASYNC for( auto& ftr : work_in_progress ) { ftr = std::async( work ); } # else for( auto& ftr : work_in_progress ) { std::packaged_task< int() > task(work); ftr = task.get_future(); std::thread thread( std::move(task) ); thread.detach(); } # endif for( auto& ftr : work_in_progress ) { ftr.get(); } # else std::vector< boost::unique_future<int> > work_in_progress(42); for( auto& ftr : work_in_progress ) { boost::packaged_task<int> task(work); // boost's packaged_task don't take the full signature as parameter, it takes the return type only ftr = task.get_future(); boost::thread thread( boost::move(task) ); thread.detach(); } for( auto& ftr : work_in_progress ) { ftr.get(); } # endif #else for( int i = 0; i < 42; ++i ) { work(); } #endif MY_LOG << "END"; return EXIT_SUCCESS; } -------------------------------------- // this program tests if the memory leaks appear with Threading Building Blocks #define BASIC_VS_LEAK_DETECTOR 0 #define VISUAL_LEAK_DETECTOR 1 #define LEAK_DETECTOR VISUAL_LEAK_DETECTOR #define WITH_ROOT_TASK //#define WITH_BOOST_LOG //#define WITH_STD_ASYNC // uncomment to leak #ifdef WITH_STD_ASYNC # include <future> #endif #include <thread> #include <atomic> #include <boost/thread.hpp> #include <tbb/tbb.h> #include <tbb/task_scheduler_init.h> #ifdef WITH_BOOST_LOG # include <boost/log/trivial.hpp> # define MY_LOG BOOST_LOG_TRIVIAL(info) #else # include <iostream> # define MY_LOG std::cout << '\n' #endif #if LEAK_DETECTOR == BASIC_VS_LEAK_DETECTOR # define _CRTDBG_MAP_ALLOC # include <stdlib.h> # include <crtdbg.h> #else # include "vld.h" #endif namespace test { struct my_data { char data[1024]; }; boost::thread_specific_ptr< my_data > ts_ptr; void my_thread_foo() { ts_ptr.reset(new my_data()); } class UpdateTask : public tbb::task { public: UpdateTask() : idx( s_idx++ ) { MY_LOG << "[UpdateTask " << idx << " ] " << std::endl; } ~UpdateTask() { MY_LOG << "[/UpdateTask " << idx << " ]" << std::endl; } tbb::task* execute() { MY_LOG << "[" << std::this_thread::get_id() << "] Tick "<< m_count <<std::endl; my_thread_foo(); ++m_count; if( m_count < 100 ) { // make sure this is re-executed this->increment_ref_count(); this->recycle_as_safe_continuation(); } return nullptr; } private: static std::atomic<int> s_idx; std::atomic<int> m_count; const int idx; }; std::atomic<int> UpdateTask::s_idx = 0; class TaskScheduler // using TBB { public: #ifdef WITH_ROOT_TASK TaskScheduler() : m_root_task( *new (tbb::task::allocate_root()) tbb::empty_task ) { m_root_task.increment_ref_count(); } ~TaskScheduler() { m_root_task.destroy(m_root_task); } #endif void register_update_task() { #ifdef WITH_ROOT_TASK m_root_task.increment_ref_count(); UpdateTask& updater = *new(m_root_task.allocate_child()) UpdateTask(); #else UpdateTask& updater = *new(tbb::task::allocate_root()) UpdateTask(); #endif m_task_list.push_back( updater ); } void run_and_wait() { #ifdef WITH_ROOT_TASK m_root_task.spawn( m_task_list ); m_root_task.wait_for_all(); #else tbb::task::spawn_root_and_wait( m_task_list ); #endif } private: tbb::task_list m_task_list; // uncomment the following line to not leak tbb //tbb::task_scheduler_init m_engine_instance; // We explicitly create and destroy the TBB task scheduler to avoid memory leak warning noises. #ifdef WITH_ROOT_TASK tbb::task& m_root_task; #endif }; void tbb_test() { TaskScheduler task_scheduler; for( int i = 0; i < 50; ++i ) { task_scheduler.register_update_task(); } task_scheduler.run_and_wait(); } } int main(int argc, char *argv[]) { #if LEAK_DETECTOR == BASIC_VS_LEAK_DETECTOR // First simple memory leak detection for Visual Studio // use _crtBreakAlloc to put a breakpoint on the provided memory leak id allocation //_crtBreakAlloc = 148; _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF ); #endif #ifdef WITH_STD_ASYNC std::atomic<bool> finished = false; std::async( [&]{ while( !finished ) { MY_LOG << "POP"; test::my_thread_foo(); std::this_thread::sleep_for( std::chrono::milliseconds(500) ); } } ); #endif test::tbb_test(); #ifdef WITH_STD_ASYNC finished = true; #endif MY_LOG << "\nEND"; std::this_thread::sleep_for( std::chrono::seconds(4) ); return 0; }

3 5

[thread] C++11 once_flag enabled when constexpr is not available
by Andrey Semashev 05 Mar '13

05 Mar '13

Hi, Vicente! I see you applied my patch for call_once but you seem to forgot to disable the C++11 call_once interface when the compiler does not support constexpr. Was that intentional or you just missed it? Anyway, please find the patch attached.

3 3

[locale] Composing asymmetric locale for character encoding conversion
by Andrey Semashev 05 Mar '13

05 Mar '13

Hi, Suppose I have a logging application that writes log records in wide (wchar_t, UTF-16) and narrow (char, UTF-8) encodings and I want these logs to be stored in a UTF-16LE encoded file. For simplicity, let's assume that I write log files with std::wofstream. Now, the standard says that the file stream buffer is supposed to convert wide characters to byte sequences using the locale imbued into the buffer. However, it seems that the locale should be the same as the one imbued into the stream (basic_ostream::imbue makes sure of that). What this leads to is that in order to achieve my goal the locale should be able to convert narrow characters of UTF-8 to wide characters of UTF-16 and wide characters of UTF-16 to narrow characters representing byte sequence of UTF16LE. Is it possible to make such an asymmetric locale with Boost.Locale? Or maybe there is another way of doing this? An additional question. Is it possible to to achieve my goal with std::ofstream (as opposed to std::wofstream)? I have a very strong suspicion that the answer is no because the narrow characters will pass on unconverted to the file instead of being translated from UTF-8 to UTF-16LE, but maybe I'm missing something. Thank you.

3 4

[coroutine] documentation comment
by Brian Wood 05 Mar '13

05 Mar '13

I wrote about this last month on Boost users but there wasn't a reply. I have a comment about a sentence on this page: http://www.boost.org/doc/libs/1_53_0/libs/coroutine/doc/html/coroutine/intr… "The principal difference between coroutines and routines is that a coroutine enables explicit suspend and resume their progress via additional operations by preserving local state ..." I'm wondering if it would be helpful to change that to this: The principal difference between coroutines and routines is that coroutines enable explicit suspend and resume of their progress via additional operations by preserving local state ... Shalom Brian Wood Ebenezer Enterprises http://webEbenezer.net (651) 251-9384

2 1

[tweener] Preliminary Submission
by Julien Jorge 05 Mar '13

05 Mar '13

Hello, I would like to propose the Boost.Tweener library for preliminary submission. The purpose of the Boost.Tweener library is to provide solutions to interpolate the intermediate values between two given values during a time interval. Various easing functions can be applied to control the computation of the intermediate values. I felt the need of such a library while developing games but I have also seen this need in various animation softwares. The library provides the following functionalities: - Interpolation is done on the value of a given variable or using an user-provided callback function, - The interpolated values are computed using a predefined easing function or any user-provided function respecting the contract, - Several tweeners can easily be executed simultaneously or in a row, - The type of the interpolated values are user defined. Please follow this link to download a Zip of the library: http://sourceforge.net/projects/libclaw/files/boost/boost-tweener-rc1.tar.g… Can you check that the library works as expected or tell me what should be fixed before submitting for review? There are various example programs in the archive. Regards, Julien Jorge

6 15