- Boost - lists.boost.org

Re: [boost] [intrusive] Looking for a non-recursive structural tree cloning algorithm
by Steven Watanabe 09 Sep '07

09 Sep '07

AMDG Ion Gazta?aga <igaztanaga(a)gmail.com> wrote: > So if you are a tree expert, I need your help to get a tree cloning > function, that: > > * Does not use the comparison predicate or calls any function that uses > it (e.g.: insert()) > > * Can destroy all constructed nodes in a non-recursive form if > node-copying throws an exception. > > * It's pretty efficient ;-) > > Willing to help? > > Ion > > warning untested: node* current = root; node* new_root = 0; node* insertion_point = 0; insertion_point = new_root = copy_node(*current); // sets the links to zero try { while(true) { if(current->left != 0 && insertion_point->left == 0) { current = current->left; node* temp = insertion_point; insertion_point = copy_node(*current); insert_at_left(temp, insertion_point); } else if(current->right != 0 && insertion_point->right == 0) { current = current->right; node* temp = insertion_point; insertion_point = copy_node(*current); insert_at_right(temp, insertion_point); } else { if(current == root) break; current = current->parent; insertion_point = insertion_point->parent; } } } catch(...) { destroy_tree(new_root); throw; } In Christ, Steven Watanabe

2 2

[proto] Calculator Arity Transform and function varargs
by Felipe Magno de Almeida 08 Sep '07

08 Sep '07

Hi, I can't make it out how to do the arity transformation for proto::functions varargs too. Could anybody shed some light? Thanks and best regards, -- Felipe Magno de Almeida

2 3

boost::any visitor of known types
by Christian Holmquist 08 Sep '07

08 Sep '07

Hello all, Is there any visitor mechanism somewhere in boost that allows one to introspect the contained type of a boost::any? I've been using boost::variant frequently and I love the way its visitor works, but it's not always practical to know all possible types at compile time (library dependencies, compilation time etc..). I thought something similiar for boost::any, and I put together a small test: any_variant<T0, T1, T2> any_of_type_T0_T1_T2; It allows visitation of the types given as template parameters. A trivial example would be struct print_visitor { template<class T> void operator()(const T& x) const { std::cout << x <<std::endl; } }; void test() { typedef any_variant<int, float, std::string> any_types; boost::any a; any_types v(a); a = (int) 35; v(print_visitor()); a = std::string("str"); v(print_visitor()); a = (double) 45.0; v(print_visitor()); } // prints 35 str Also the example from boost::any docs, class consumer { public: virtual void notify(const any &) = 0; ... }; could be implemented like class my_consumer : public consumer { virtual void notify(const any &a) { any_variant<msg0, msg1> av(a); av(*this); } void operator()(const msg0&); void operator()(const msg1&); } The implementation is very basic, it just iterates over the types and compares typeids. If a match is found it calls the visitor and returns true, otherwise false. Does anyone else have a use for this, or have another solution at hand? Best regards, Christian #include <boost/any.hpp> #include <boost/mpl/begin.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/deref.hpp> #include <boost/mpl/vector.hpp> #include <boost/preprocessor/cat.hpp> #include <boost/preprocessor/control/expr_if.hpp> #include <boost/preprocessor/repetition/enum.hpp> #include <boost/preprocessor/repetition/enum_params.hpp> namespace detail { template<bool done = true> struct typeitr_loop { template<typename Iterator, typename LastIterator, typename Visitor> static bool invoke(boost::any&, Visitor) { return false; } }; template<> struct typeitr_loop<false> { template<typename Iterator, typename Last, typename Visitor> static bool invoke(boost::any& a, Visitor v) { typedef boost::mpl::deref<Iterator>::type type; if(typeid(type) == a.type()) { v(*boost::unsafe_any_cast<type>(&a)); return true; } else { typedef boost::mpl::next<Iterator>::type itr; return typeitr_loop<boost::is_same<itr, Last>::value>::invoke <itr, Last>(a, v); } } }; template<class Types, class Visitor> inline bool visit_any_type(boost::any& a, Visitor f) { typedef typename boost::mpl::begin<Types>::type first; typedef typename boost::mpl::end<Types>::type last; return detail::typeitr_loop<boost::is_same<first, last>::value>::invoke <first, last>(a, f); } } // // Preprocessor code copied from <boost/multi_index/indexed_by.hpp> // #ifndef ANY_VISITOR_LIMIT_TYPES #define ANY_VISITOR_LIMIT_TYPES 10 #endif #define ANY_VISITOR_TEMPLATE_PARM(z,n,var) \ typename BOOST_PP_CAT(var,n) BOOST_PP_EXPR_IF(n,=boost::mpl::na) template < BOOST_PP_ENUM( ANY_VISITOR_LIMIT_TYPES, ANY_VISITOR_TEMPLATE_PARM,T) > class any_variant { boost::any& any_; public: typedef boost::mpl::vector<BOOST_PP_ENUM_PARAMS(ANY_VISITOR_LIMIT_TYPES,T)> types; any_variant(boost::any& a) : any_(a) {} typedef bool result_type; template<class Visitor> bool operator()(Visitor v) const { return detail::visit_any_type<types>(any_, v); } }; #undef ANY_VISITOR_TEMPLATE_PARM #undef ANY_VISITOR_LIMIT_TYPES

2 1

How to download Functional module of Fusion 2 ???
by Marco Costalba 08 Sep '07

08 Sep '07

It seems is not included in the files you can download from http://spirit.sourceforge.net/dl_more/fusion_v2/ In particular I'm looking for #include <boost/fusion/functional/invocation/invoke_procedure.hpp> BTW fusion 2 is not bundled with the boost_1_34_1.tar.bz2 you get from sourceforge, so to be able to have a complete fusion library an user is supposed to walk: boost.org --> download boost_1_34_1.tar.bz2 from sourceforge --> (surprise! fusion is not in) --> google ---> spirit.sourceforge.net/dl_more/fusion_v2/ ---> (surprise! functional module is not in) ---> google again ----> pain!! -> ask to mailing list ---> ??? Not exactly what you would call "user friendly".... Interesting enough the corresponding documentation is much easier to find: http://spirit.sourceforge.net/dl_more/fusion_v2/libs/fusion/doc/html/index.… Thanks for any help to find this well hidden link. Marco

1 0

[test] BOOST_CHECK_NOT_EQUAL wanted
by Kevin Sopp 08 Sep '07

08 Sep '07

Hello, I found this old thread http://lists.boost.org/boost-users/2006/06/20028.php where it said bring up the issue again after 1.34 is released. I intuitively expected a BOOST_CHECK_NOT_EQUAL to exist and typed it in, but it wasn't there! So, here's one more person requesting macros for all comparison operators for the test tools. regards, Kevin Sopp

6 9

Repository Layout
by Frank Birbacher 08 Sep '07

08 Sep '07

Hi! I'm trying to think of a usable repository layout. The features it should provide IMHO: (1) release-ready branch, which is updated by the release manager/team and includes latest additions for the next release as well as bug fixes from the last release. this one is to prepare for a major release (2) release-fixing branch, which is updated by the release manager/team and only gets bug fixes. this one is to provide support/fixes for the last release (3) a main development branch for each library in boost. this would be updated by the library maintainer. this directory should hold changesets which the release manager/team merges into (1) (4) testing branches for each library which can hold various bugfixes and which are used for testing the changes before they are merged into the release-ready (1) and release-fixing branches (2). (5) possibly branches for each library which are "private" to the library and used by the maintainer as she likes To keep (3), (4), and (5) together, I think the following directory structre would do: /libraries /iostreams /trunk (3) /branches /testing_bug143 (4) /trying_refactor (5) /serialization /trunk (3) /branches /... /tags /... (also 5) /... /release /release-1-35-ready (1) /release-1-34-fixing (2) /tags /release-1-34 /release-1-34-1 /... Library work flow: Bring /library/foo/trunk in sync with last release. Fix bugs in this trunk. Report to release manager/team: "please include /libraries/foo/trunk -c 39042 into release, its a bug fix for ticket #374". Maybe branch off from trunk of foo or from latest release in order to develop new feature. Use this branch for heavy testing, too. When ready, report: "please include /libraries/foo/branches/new_feature -r 40000:42000 into release-ready, its a new feature requested in #845". Release work flow: When receiving a "bug fix report" merge it into working copy of the release-fixing branch and do local testing. maybe include some more requests. After that "commit" and create a tarball for external testing. Committing the only locally tested state will preserve this exact state in the subversion. I think this is needed to provide a tarball and an identical copy in repository. If tests are successful try the same bug fix in release-ready branch and do the same testing. Ok. I currently don't know how testing is done exactly, but other messages on the list indicated testing each bug fix as it is merged into the release branch. This seemed to require building a tarball and giving it away for testing. I think this is a process which takes days. So how long would it take to include a couple of fixes into the release-fixing branch? How much testing is done up to today? Frank

2 1

[intrusive] Info on ongoing interface changes. Need for ideas.
by Ion Gaztañaga 08 Sep '07

08 Sep '07

Hi Boost.Intrusive user, ------- 1 Info ------- As you might know, recently an interface change was discussed for Boost.Intrusive and more configurability was required. The discussion lead to the following templatized option specifiers: typedef list < member_hook<Hook> , constant_time_size<false> , size_type<unsigned short> , any_future_options<option_value> .... > MyList; I've implemented this approach and my first results were not very encouraging: list_test obj grew from 3.5MB to 11MB, compilation times skyrocketed, debug symbol files were really big... However, I started shortcutting internal symbols to reduce symbol length and I've reduced the bloat to 4.5MB obj and moderately increased compilation time. The executable has grown a bit (5-10% in release mode) but I still don't know why (maybe I still get some long symbols there but machine code has not grown). My conclusion is: Be careful with meta-programming. The current implementation, if the user does not specify any hook or value traits, the container automatically uses the corresponding base hook with the default tag, so defining a class to be insertable in different containers is pretty easy: using namespace boost::intrusive; class my_class : list_base_hook< link<auto_unlink> > , slist_base_hook< link<safe_unlink>, void_pointer<offset_ptr<void> > , set_base_hook<> {}; typedef list<my_class> MyList; typedef slist<my_class> MySlist; typedef set<my_class> MySet; I plan to upload a version with the new interface to get more comments. -------------------------- 2 Configuratility problem -------------------------- Now that compile_time configurability is more self-describing (which was one of the main goals of the change) we must also allow stateful option configurability. This means that constructors of containers must take objects of configured stateful policies. stateful policies can be: * Stateful ValueTraits * Comparison or Equality predicates * Hash functors * Any new stateful option we might imagine So a container might end with a long list of initializers: unordered_set ( bucket_info , const hash &h = hash() , const equal &e = equal() , const value_traits &v = value_traits() , const my_new_option &n() , ....) Obviously, if the user has to pass a stateful value_traits, he has to also specify all previous parameters. Similarly to template parameters, I would like to achieve something like: typedef unoredered_set < value_traits<my_stateful_value_traits> , hash <my_hash> , equal<my_stateful_equal> > MyUset; //my_value_traits_conf is passed to the internally built //value traits, all other options are default constructed MyUset u1 (to_value_traits(my_value_traits_conf)); //my_stateful_equal_conf is passed to the internally built //equal, all other options are default constructed MyUset u2 (to_equal(my_stateful_equal_conf)); //my_stateful_equal_conf is passed to the internally built //equal, _value_traits_conf is passed to the internally built //value traits, all other options are default constructed MyUset u3 (to_equal(my_stateful_equal_conf) ,to_value_traits(my_value_traits_conf)); I've thought about implementing this with a brute-force approach but since I know there are people who knows much more than me in this configurability issues, I would like to know how could we efficiently implement this. Compile-time performance appreciated. Big props guaranteed in the documentation. Regards, Ion

1 0

Interest in a small Enum IO utility?
by Marcus Lindblom 08 Sep '07

08 Sep '07

Hi, I have some code that helps with defining iostream-operators for enums. We use this in our C++<->xml bindings. Basically, it's just two maps (string->enum & enum<-string) and some syntactic sugar. However, I happen to think it is quite neat and so figured it might be useful to other people too. (And it's always nice to give something back :) So, is this something that would fit in boost? Advantages: * Enables lexical_cast on enums. * Pure implementation detail from user-of-enum's perspective. * Very little syntax overhead, inspired by boost::assign. * Works across namespaces & DLLS. * Allows user to define io-ops for "external" enums too. (But the IO-op-macro hs to go into the external namespace.) * Uses pimpl-idiom for faster compilation. * Suitable for header-only version. Issues to work out: * Uses the Loki-singleton to store implementation details. * Initialization is a bit rough. (We get away with it because we have a static "initClass" method for every class. It is a natural place for enumio-setup in our app, but this does not translate to general code well.) * Stores std::strings, although it's almost always constructed from string literals. Wastes a bit of memory for simpler implementation. * EnumIO<E>::The() is globally accessible, so there could be conflicts. (Very low probability though) See below for example & implementation. Comments? Cheers, /Marcus --- user .h ------------------------------------------------ enum Foo { Bar, Baz; } // to export from a win32 dll, add dllimport/export here std::istream& operator>>(std::istream&, Foo& foo); std::ostream& operator<<(std::ostream&, Foo foo); --- user.cpp ------------------------------------------------ #include "user.h" #include <enumio.h> ENUMIO_IMPLEMENT_IOSTREAM_OPS(Foo) // just one way to do it bool init = (::EnumIO<Foo>::the() (Bar, "bar") (Baz, "baz")), true; --- enumio.h ------------------------------------------------ class EnumUtilBase { public: ~ EnumIOBase(); protected: explicit EnumIOBase(const std::type_info& enumType); std::istream & in(std::istream & os, int &value) const; std::ostream & out(std::ostream & os, int value) const; protected: void add(int value, const char* data); private: class Impl; boost::scoped_ptr<Impl> m_i; }; // Helps with serialization (iostream) of enums template<class E> class EnumIO : public EnumIOBase { public: typedef E Enum; EnumIO<E> the() { return ::Loki::SingletonHolder<::EnumIO<E> >::the(); } EnumIO(); EnumIO<E>& operator()(E value, const char* data); std::istream & in(std::istream & is, E & value) const; std::ostream & out(std::ostream & os, E value) const; }; #define ENUMIO_IMPLEMENT_IOSTREAM_OPS(E) \ std::istream& operator>>(std::istream& is, E& value) { \ return ::EnumIO<E>::the().in(is, value); } \ std::ostream& operator>>(std::ostream& os, E value) { \ return ::EnumIO<E>::the().out(os, value); } template<class E> inline EnumIO<E>::EnumIO() : EnumIOBase(typeid(E)) { BOOST_STATIC_ASSERT(sizeof(E) == sizeof(int)); } template<class E> inline EnumIO<E> &EnumIO<E>::operator()(E value, const char* data) { EnumIOBase::add(value, data); return *this; } template<class E> inline std::istream & EnumIO<E>::in(std::istream & is, E & value) const { return EnumIOBase::in(is, (int&) value); } template<class E> inline std::ostream & EnumIO<E>::out(std::ostream& os, E value) const { return EnumIOBase::out(os, value); } --- enumio.cpp ------------------------------------------------ typedef std::map<int, std::string> MapOut; typedef std::map<std::string, int> MapIn; class EnumIOBase::Impl { public: const char* m_typename; ///< is retrieved from typeid(X).name() MapIn m_mapIn; MapOut m_mapOut; }; EnumIOBase::EnumIOBase(const std::type_info& enumType) : m_i(new Impl) { m_i->m_typename = enumType.name(); } EnumIOBase::~EnumIOBase() { } std::istream & EnumIOBase::in(std::istream & is, int &value) const { std::string str; is >> str; if (m_i->m_mapIn.empty()) { MapIn& m = const_cast<MapIn&>(m_i->m_mapIn); for(MapOut::const_iterator i = m_i->m_mapOut.begin(); i != m_i->m_mapOut.end(); ++i) { m.insert(std::make_pair(i->second, i->first)); } } MapIn::const_iterator i = m_i->m_mapIn.find(str); if (i != m_i->m_mapIn.end()) { value = i->second; } else { is.setstate(std::ios::failbit); } return is; } std::ostream & EnumIOBase::out(std::ostream & os, int value) const { const std::string& str = toStr(value); if (!str.empty()) { os << str; } else { os.setstate(std::ios::failbit); } return os; } void EnumIOBase::add(int value, const char* data) { m_i->m_mapOut.insert(std::make_pair(value, data)); }

2 6

[intrusive] Looking for a non-recursive structural tree cloning algorithm
by Ion Gaztañaga 08 Sep '07

08 Sep '07

Dear tree expert, As you might know, Boost.Intrusive implements an intrusive red-black tree and also a class offering red-black tree algorithms. Those algorithms were taken from the SGI STL code and optimized a bit. One of the goals of Boost.Intrusive is avoiding recursive calls to make those algorithms suitable for very big trees and/or embedded systems. The SGI STL uses two recursive algoritms: * Recursive destruction with no rebalancing * Recursive structural copy (which needs a erasing function in case a copy throws an exception). All STL implementations I'm aware of use recursive cloning and destruction. Boost.Intrusive changed the recursive tree destruction algorithm to a non-recursive one thanks to a step by step tree destruction function (unlink_leftmost_without_rebalance) that is also very useful to implement advanced tree cloning functions that might reuse old allocated nodes. However, I haven't found a non-recursive structural copy algorithm anywhere. So if you are a tree expert, I need your help to get a tree cloning function, that: * Does not use the comparison predicate or calls any function that uses it (e.g.: insert()) * Can destroy all constructed nodes in a non-recursive form if node-copying throws an exception. * It's pretty efficient ;-) Willing to help? Ion

1 0

Simple object factory: Checking signatures at runtime
by Marco Costalba 08 Sep '07

08 Sep '07

I'm extending the 'simple object factory' I have presented to this mailing list few threads ago. It is coming out pretty nice: the number of allowed object c'tor arguments have been extended until a given maximum and instead of an (optional) custom "object creator" function it is now possible to use any callable entity as example a functor object. The factory is now "almost" satisfactory. It has only a couple of drawbacks, one small and a work around does exist. The other is "important" because is a design issue. Very briefly: I can register any c'tor anywhere in a program to teach the factory how to build an object: Factory::register_class<Base, double>("MyObject"); Factory::register_class<Base, int, Base*>("MyObject"); Above instructions automatically instantiate and register two c'tor invokers c1 and c2 defined as: Base* c1(double d) { return new Base(d); } Base* c2(int i, Base* b) { return new Base(i, b); } Constructor overloading support it means that the factory will call two different functions also if the same key "MyObject" is passed depending on the argument types: Base* o1 = Factory::object("MyObject", 3.14); /* function 'c1' is called */ Base* o2 = Factory::object("MyObject", 3, o1); /* function 'c2' is called */ The factory is also able to check the signatures at runtime and discards any wrong call: Base* o3 = Factory::object("MyObject", o1, 3); /* o3 == NULL */ Finally, here it is the current big limitation: automatic argument type conversion is not supported: Factory::object("MyObject", 3.14, o1); /* fails: double -> int is not done */ Derived* d = new Derived(); /* say Derived it's a sub class of Base */ Factory::object("MyObject", 3, d); /* fails: Derived* -> Base* is not done */ The design issue is that type info is templatized so that only "near perfect matches" are discovered. Where "near perfect matches" it means that if a value 'v' has type V and constructor argument accepts type A then we have a match only if: A == V || A == V& || A == const V || A == const V& My question is: there exsist a way to check "relaxed" signatures at run-time? Put in general terms: Given a set 'Set' of functor objects f1,f2,..fn with different signatures in their operator() is it possible to check if a given set of values v1,v2,...vk are compatible with one or more of them ? What I would need is an implementation of the following algorithm: foreach(f in Set) if ( "f(v1,v2,..,vk)" is compilable ) return f; Constrains are: - Functors can be "registered" with the factory in different times and in different translation units. - At runtime you have a only set of values as input: v1,..vk - Functor signatures may not be homogeneous Thanks for your help Marco

4 15