[boost] [gsoc][RFC] Pointer Plus Bits

Subject: [boost] [gsoc][RFC] Pointer Plus Bits
From: Brian Bartman (bbartmanboost_at_[hidden])
Date: 2010-07-25 09:35:18

Hello,

I previously sent out an email to the list about a pointer plus bits like
data structure and received some feedback about a pointer plus bits data
structure. After taking into consideration all of the different points of
view, comments and concerns voiced by the Boost community I have implemented
an extension to my bitfield_tuple which allows the user to easily store
parts of a pointer and use the extra bits for storage.

Here is a basic overview of the bitfield_tuple:

Its a tuple like data structure which stores bitfields instead of whole
types inside of single tuple. This allows the user to skirt packing
limitations of structs and classes in C++ and create bitfields over the
storage type of their choice OR leave that decision up to the data structure
(the behavior for selecting the storage type is to select the smallest
possible unsigned integral type which will hold the all of the bitfields).

example of basic bitfield_tuple declaration.

#include<boost/integer/bitfield_tuple.hpp>
struct red;
struct green;
struct blue;

using namespace boost;
using namespace boost::bitfields;

typedef bitfield_tuple<
    member<unsigned char, red, 5>,
    member<char, green, 6>,
    member<unsigned int, blue,5>
 >  rgb565_t;

The bitfield_tuple takes ordered named template parameters (In the case of
the storage type order is ignored. IE no matter where you put the storage<
type > template the ending result will be the same).

the bitfield_tuple supports the following template named template parameters
(all of the templates which follow are located within the boost::bitfields
namespace):
bit_align< std::size_t> -> increases the offset of the next field to an
offset which is divisible by the supplied value unless the current index is
divisible by the supplied value then there is no increase.
filler<std::size_t> -> bits to be skipped.
member<typename, typename, std::size_t> -> this is a basic bitfield
parameters it takes are the type the bitfield is to return, a naming type
and the width of a bitfield
flag<typename> -> boolean version of member.
storage<typename> -> uses the supplied type for internal storage.
pointer<typename, typename, typename> -> NEW described below.

Pointer Member Information:

The pointer member takes three template parameters.
1) The type you would like to make a pointer to.
2) The name which can be used (instead of an index, index is also still
available to use) to access the pointer.
3) This is an integral_constant or integral_constant like type which is used
to make a mask over the value bits of the pointer. This has a default value
to leave the last two bits open. You can use leading or ending bits of the
pointer for storage by supplying a different mask.

Reasoning behind allowing for leading storage bits. There are some systems
which do low address allocations and then store values within the higher
part of the address. While this is much more rare then the use case of
stuffing two bits inside of the end of a pointer I felt that it would be
best to provide a way to actually do this.

Reasoning behind restricting the mask to an integral_constant or
integral_constant like type. The intent for this is to associate a non
deduced type with the mask itself, however if people feel better simply
using hex to specify the mask I could change the behavior to do that. There
are mask creation utilities which can be used to create the mask from a
higher level the simply supplying hex.

Here are some examples of how to declare a bitfield_tuple with a pointer
member:

#include <boost/integer/bitfield_tuple.hpp>
#include <boost/assert.hpp>

using namespace boost;
using namespace boost::bitfields;

struct ptr;
struct color;
struct i1;
struct i2;

typedef bitfield_tuple< pointer<int, ptr> > ptr_1;
typedef bitfield_tuple< pointer<int, ptr>, flag<b1>, flag<b2> >
ptr_plus_two_bools;
typedef bitfield_tuple< pointer<int, ptr>, member<unsigned int,color,2> >
ptr_plus_two_bit_color;

int main() {
    ptr_1 p1;
    int i = 10;
    p1.get<0>() = &i;
    BOOST_ASSERT(*p1.get<ptr>() == 10);

    ptr_plus_two_bools p2;
    p2.get<ptr>() = &i;
    ptr.get<b1>() = true;
    ptr.get<2>() = false;

    ptr_plus_two_bit_color p3;
    p3.get<ptr>() = &i;
    p3.get<color>() = 3;
    return 0;
}

The pointer does NOT have to be the first parameter of the bitfield tuple
one can simply place things in front of the the pointer and the value mask
of the pointer will not be affected. The only thing which is different when
this is done is the offset of the pointer within the bitfield_tuples
storage, this only changes the location of the bitfield where the pointer is
actually being stored. That being said you will always receive the value
bits of the pointer in the exact same way they were taken from inside the
pointer.
-- 
thanks,
Brian Bartman