|
Boost : |
Subject: [boost] Interest request for pointer+bit compression optimization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-09-07 13:00:14
Hi,
I have recently found in the blog of Joaquin the following optimization consisting in embed a bit into the representation of a pointer. Please read it, it is not too long (http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.html)
I was wondering if it would be interesting to provide some generic template classes making easier this kind of optimization.
We can define two templates (See below)
template <typename E> struct bit_ref;
template <typename T> struct pointer_ref;
So instead of having
enum color_type{red=false,black=true};
class rb_node {
private:
color_type color_;
regular_rb_node_header* parent;
color_type& color(){return color_;}?
color_type color()const{return color_;}?
rb_node*& parent(){return parent_;}?
rb_node* parent() const{return parent_;}
}
we can compress the colot_type and the rb_node* as follows
class rb_node {
private:
uintptr_type parentcolor_;
public:
bit_ref<color_type> color(){return bit_ref<color_type>(&parentcolor_);}
color_type color()const{return bit_ref<color_type>(&parentcolor_);}
pointer_ref<rb_node> parent(){return pointer_ref<rb_node>(&parentcolor_);}
rb_node* parent() const {return pointer_ref<rb_node>(&parentcolor_);}
};
Next follows the definition of the template classes
template <typename E>
struct bit_ref {
bit_ref(uintptr_type* r_):r(r_){}
operator E() const {
return E(*r&uintptr_type(1));
}
bit_ref& operator=(E c) {
*r&=~uintptr_type(1);
*r|=uintptr_type(c);
return *this;
}
bit_ref& operator=(const bit_ref& x) {
return operator=(x.operator T());
}
private:
uintptr_type* r;
};
template <typename T>
struct pointer_ref {
pointer_ref(uintptr_type* r_):r(r_){}
operator T*() const {
return (T*)(void*)(*r&~uintptr_type(1));
}
pointer_ref& operator=(T* p) {
*r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
return *this;
}
pointer_ref& operator=(const pointer_ref& x) {
return operator=(x.operator T*());
}
pointer_ref operator->()const {
return operator T*();
}
private:
uintptr_type* r;
};
Thanks Joaquin for sharing simple things like this one, stable_vector and others in your Bannalia blog.
_____________________
Vicente Juan Botet Escribá
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk