Example of templates computing object sizes for slab allocators

gistfile1.txt

/*
  Test that implements some template meta programming. 

  - two_to_the_power_of<Power> calculates 2^Power into it's ::value.

  - rightshits<V> calculates how many times V can be rightshifted
  until it's 1 or 0, result is in ::value.

  - if_t<bool,A,B> places A or B in ::value, depending on the bool
  
  - next_power_of_two<N> computes the next power of 2 such that N <=
  2^power into ::value. Ie, for N=16 ::value=16, and for N=20
  ::value=32.

  This was planned for use in a allocator, such that the code would
  chose an allocator based on the size of the type to allocate, but
  group them in slabs that are the size of 2^n.

  typedef Pool<next_power_of_two<sizeof (MyClass)>::value> MyClassPool;

  It could be further specialsed, so ie. all <32 size objects go into
  allocator for size 32 objects, and objects with size > 32k get their
  private slab.
 */

#include <iostream>
#include <assert.h>

using namespace std;

// Anonymous namespace, since all this is kinda private
// to "next_power_of_two"
namespace {
    template<int Power>
    struct two_to_the_power_of {
        enum { value = 2 * two_to_the_power_of<Power - 1>::value };
    };
    
    template<>
    struct two_to_the_power_of<0> {
        enum { value = 1 };
    };
    
    template<int V>
    struct rightshifts {
        enum { value = 1 + rightshifts<V >> 1>::value };
    };
    
    template<>
    struct rightshifts<1> {
        enum { value = 0 };
    };
    
    template<>
    struct rightshifts<0> {
        enum { value = 0 };
    };
    
    template<bool, int A, int B> 
    struct if_t {
        enum { value = B };
    };
    
    template<int A, int B> 
    struct if_t<true, A, B> {
        enum { value = A };
    };
}

template<int Sz> 
struct next_power_of_two {
    enum { 
        rights = rightshifts<Sz>::value,
        candidate = two_to_the_power_of<rights>::value,
        value = if_t<candidate == Sz, candidate, 2 * candidate>::value
    };
};

template<>
struct next_power_of_two<0> {
    enum { value = 0 };
};

#define test(a,b) \
    if (a::value == b) { \
       cout << #a << " = " << b << endl; \
    } else { \
      cout << "***" << #a << " = " << a::value << " but should be " << b << endl; \
      assert (a::value == b); \
    }

void test_two_to_the_power_of () {
  next_power_of_two<sizeof (Foo)>::value == 64
    test (two_to_the_power_of<0>, 1);
    test (two_to_the_power_of<1>, 2);
    test (two_to_the_power_of<2>, 4);
    test (two_to_the_power_of<3>, 8);
    test (two_to_the_power_of<4>, 16);
}

void test_rightshifts () {
    test (rightshifts<0>, 0);
    test (rightshifts<1>, 0);
    test (rightshifts<2>, 1);
    test (rightshifts<3>, 1);
    test (rightshifts<4>, 2);
    test (rightshifts<10>, 3);
    test (rightshifts<19>, 4);
}

void test_next_power_of_two () {
    test (next_power_of_two<0>, 0);
    test (next_power_of_two<1>, 1);
    test (next_power_of_two<2>, 2);
    test (next_power_of_two<3>, 4);
    test (next_power_of_two<4>, 4);
    test (next_power_of_two<16>, 16);
    test (next_power_of_two<30>, 32);
    test (next_power_of_two<32>, 32);
    test (next_power_of_two<300>, 512);
    test (next_power_of_two<400>, 512);
    test (next_power_of_two<4000>, 4096);
    test (next_power_of_two<30000>, 32768);
    test (next_power_of_two<32768>, 32768);
    test (next_power_of_two<40000>, 65536);
}

int main (int argc, char *argv[]) {
    test_two_to_the_power_of ();
    test_rightshifts ();
    test_next_power_of_two ();
}