Ion Gaztañaga wrote:
Tobias Schwinger wrote:
However, I've been wondering whether it would be possible to make the "hook interface" easier to use and less demanding in terms of names that are injected into client code. So I started experimenting a bit and the attachment is what I came up with. I believe that scheme might actually work (not sure, though)...
[code]
Very interesting, although I don't fully understand the goal. If the goal is to avoid name injection, I could rework hooks to group all the name definitions in a single internal structure and avoid code bloat.
Maybe because there were two goals: 1. Get rid of the syntactic bloat currently needed to make a class Intrusive-ready. 2. Reduce the probability of name clashes with arbitrary existing client code. Here is a second take of the code hopefully addressing the issues you pointed me to.
What I found interesting is the non-intrusive Intrusive version (nice definition ;-)). Using ADL, there is a way to obtain the hook from the value. However, Intrusive uses a two level architecture, where node algorithms only know about nodes (which in the singly linked list case is just an structure holding a single pointer) and containers know also about values (values hold nodes/hooks as base or members).
Well, it was a "waste product" trying to preserve flexibility, they might as well be replaced with function objects, as you suggested below.
This guarantees that template bloat is minimized, because instantiated algorithms are the same for all values using the same hook. Containers transform nodes to values and the inverse (using static_cast for base hooks or calculating the offset of the hook in the value in member hooks).
Ah, I see! So the "syntactic bloat" sorta just fell into place minimizing the "machine language bloat" some misguided compilers' code generation stages produce (not recognizing the that X<T> and X<U> are equivalent for something like template<class T> class X { T* x; T* y; public: /* ...member functions that work on x and y ... */ }; ). I noticed the two-level architecture, but didn't quite understand what it's for. Now that I know, I see my sample introduced an undesirable type dependency.
Although your example is not directly applicable to current Intrusive code, you suggest a very nice possibility: storing nodes(hooks) independently from values. The programmer could just offer a way to get the node from the value and the inverse when not using any base or member hook.
In the two-level Intrusive architecture your example would need two maps (we could just use boost::bimap) to transform independently stored nodes (slist_node_mgmt_data in your example) to values and the inverse operation.
... or extended the node structure with a back pointer like the attached code. I didn't notice boost::bimap is checked-in already, until now. <snip>
A lot of questions, but I think it's a fresh, great idea. Thanks!
Glad you like it. Regards, Tobias #include <boost/pointee.hpp> #include <boost/noncopyable.hpp> namespace intrusive { // ---- node with policies // management data for one node template< class Policies = void > class slist_node_mgmt_data { template< typename U, class Tr > friend class slist; slist_node_mgmt_data* ptr_next; public: slist_node_mgmt_data() { } }; // ADL extension points to allow Boost.Intrusive to work with custom // members or even non-intrusively (using some external, bidirectional // mapping). // The default implementations assume the hook a base of the value. template< class Policies > slist_node_mgmt_data<Policies>& value_to_hook( slist_node_mgmt_data<Policies>& value) { return value; } // Note: Raw pointers will probably be enough, here... template< typename NodePointer, class Policies > void hook_to_value( NodePointer& result, slist_node_mgmt_data<Policies>& node) { // ... (using Smart Pointer - capable implementation just in case). // If not, Smart Pointers must provide support for boost::pointee // (e.g. an 'element_type' member). result = NodePointer( static_cast< typename boost::pointee<NodePointer>::type* >(& node) ); } // ---- container // traits for customization template< typename T > struct slist_node_traits { typedef T value_type; typedef T* pointer_type; typedef T& reference; // not sure it belongs here, move elsewhere at will typedef void policies; // ... }; // single-linked list (incomplete for illustration) template< typename T, class Traits = slist_node_traits<T> > class slist : boost::noncopyable { typedef Traits traits; public: typedef typename traits::value_type value_type; typedef typename traits::pointer_type pointer_type; typedef typename traits::reference reference; typedef typename traits::policies policies; // ... slist_node_mgmt_data<policies>* ptr_first; public: // Note: Algorithms can work without depending on the value type // (except for casting or mapping for input and output, which will // always be there in some form). void push_front(reference x) { slist_node_mgmt_data<policies>& node = value_to_hook(x); node.ptr_next = this->ptr_first; this->ptr_first = & node; } void pop_front() { this->ptr_first = value_to_hook(* this->ptr_first).ptr_next; } reference front() { pointer_type result; hook_to_value(result, *this->ptr_first); return *result; } // ... }; } #include <boost/detail/lightweight_test.hpp> #include <map> class foo : public intrusive::slist_node_mgmt_data<> // Note: Base class does not insert any names { int val_data; public: foo(int data) : val_data(data) { } int data() const { return this->val_data; } // Note: No "member hook" }; void foo_test() { intrusive::slist<foo> my_list; foo foo1(1); my_list.push_front(foo1); foo foo2(2); my_list.push_front(foo2); BOOST_TEST( my_list.front().data() == 2 ); my_list.pop_front(); BOOST_TEST( my_list.front().data() == 1 ); my_list.pop_front(); } // Ok, let's try non-intrusive Intrusive ;-) class bar // Note: No base class { int val_data; public: bar(int data) : val_data(data) { } int data() const { return this->val_data; } // Note: No "member hook" }; // External management facility struct mgmt_data : intrusive::slist_node_mgmt_data<> // adds a back pointer for bidi mapping { bar* ptr_value; }; std::map<bar*,mgmt_data> bar_mgmt_map; intrusive::slist_node_mgmt_data<>& value_to_hook(bar& that) { mgmt_data& result = bar_mgmt_map[& that]; result.ptr_value = & that; // set back pointer return result; } void hook_to_value(bar*& result, intrusive::slist_node_mgmt_data<>& that) { // downcast to access the back pointer result = static_cast<mgmt_data&>(that).ptr_value; } void bar_test() { intrusive::slist<bar> my_list; bar bar1(1); my_list.push_front(bar1); bar bar2(2); my_list.push_front(bar2); BOOST_TEST( my_list.front().data() == 2 ); my_list.pop_front(); BOOST_TEST( my_list.front().data() == 1 ); my_list.pop_front(); } // Run the tests... int main() { foo_test(); bar_test(); return boost::report_errors(); }