[boost] Interest request for pointer+bit compression optimization

7 Sep 2009

      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.ht...)

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] Interest request for pointer+bit compression optimization

vicente.botet