[boost] Re: Challenge: pool allocator

From: John Maddock (John_Maddock_at_[hidden])
Date: 2000-03-02 07:22:10

Steve,

>These issues are handled.  boost::pool automatically handles alignment
>issues in a portable way, and the free-list overlay is also guaranteed
>to be portable.  (I think -- this is the shakiest part of the whole
>thing).

Aha! someone else who can't resist a challenge :-)

I've only looked *quickly* at your alignment code, however I don't think
that it quite guarentees correct alignment - as I understand it your code
only guarantees alignment on a sizeof(char*) boundary, but there may be
types which require alignment on a larger boundary than that, I figured
that the logic goes like this:

1) we need to store two differnt types T and U in the same memory location
- so that memory must be properly aligned for both T and U - that is the
smallest number A which has both Align(T) and Align(U) as a factor.
2)The memory must be large enough for both T and U, and rounded up to a
multiple of A - the common alignment factor.

The code I put together only deels with (1) - finding the alignment
requirements of any type T, and combining to alignments into a "smallest
common multiple", the rest is somewhat easier (I hope!).

Anyway here is the code with a short test program, the classes alignment_of
and least_common_mult do all the work:

#include <iostream>
#include <set>
#include <string>

using namespace std;

template <typename T> 
struct align_size
{ 
   char c; 
   T t; 
};

template <typename T>
struct alignment_of
{
   static const unsigned value =
(char*)&(static_cast<align_size<T>*>(0)->t) - static_cast<char*>(0);
};

template <unsigned A, unsigned B, unsigned Val, unsigned done>
struct least_comm_mult_imp
{
   static const unsigned value = ::least_comm_mult_imp<A, B, Val+A,
(Val+A)%B>::value;
};

template <unsigned A, unsigned B, unsigned Val>
struct least_comm_mult_imp<A,B,Val,0>
{
   static const unsigned value = Val;
};

template <unsigned A, unsigned B>
struct least_common_mult
{
   static const unsigned value = ::least_comm_mult_imp<A, B, A,
A%B>::value;
};

struct composite
{
   double d;
   int i;
   long l;
   char c[13];
};

int main()
{
   cout << "alignment of char is: " << alignment_of<char>::value << endl;
   cout << "alignment of short is: " << alignment_of<short>::value << endl;
   cout << "alignment of int is: " << alignment_of<int>::value << endl;
   cout << "alignment of long is: " << alignment_of<long>::value << endl;
   cout << "alignment of float is: " << alignment_of<float>::value << endl;
   cout << "alignment of double is: " << alignment_of<double>::value <<
endl;
   cout << "alignment of struct composite is: " <<
alignment_of<composite>::value << endl;
   cout << "alignment of std::string is: " <<
alignment_of<std::string>::value << endl;
   cout << "alignment of std::set<double> is: " <<
alignment_of<std::set<double> >::value << endl;
   cout << endl;
   cout << "common alignment of char and short is " <<
least_common_mult<alignment_of<char>::value,
alignment_of<short>::value>::value << endl;
   cout << "common alignment of char and int is " <<
least_common_mult<alignment_of<char>::value,
alignment_of<int>::value>::value << endl;
   cout << "common alignment of long and int is " <<
least_common_mult<alignment_of<long>::value,
alignment_of<int>::value>::value << endl;
   cout << "common alignment of double and int is " <<
least_common_mult<alignment_of<double>::value,
alignment_of<int>::value>::value << endl;

   return 0;
}

As an after thought, I haven't been able to figure out a specific example
where your code would fail (so you may be correct) - unless a platform did
something really strange and had say 6-byte alignment rules for some types
and 4-byte alignment rules for others.

- John.