Boost logo

Boost :

Subject: [boost] Interest request for pointer+bit compression optimization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-09-07 13:00:14


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 (

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 {
    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 {
    uintptr_type parentcolor_;
   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) {
      return *this;
    bit_ref& operator=(const bit_ref& x) {
      return operator=(x.operator T());
    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) {
      return *this;
    pointer_ref& operator=(const pointer_ref& x) {
      return operator=(x.operator T*());
    pointer_ref operator->()const {
      return operator T*();
    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, gregod at, cpdaniel at, john at