By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,507 Members | 1,758 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,507 IT Pros & Developers. It's quick & easy.

Using templates to enforce compile-time bounds checking

P: n/a
I have the following program that uses an array of chars to simulate a bit
set:

---------

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags[i] = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK
bitset9.set(-1); // BoundsException thrown

bitset9.set(8); // OK
bitset9.set(9); // BoundsException thrown

return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

-dr
Nov 22 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On Sun, 20 Nov 2005 21:22:46 GMT, Dave Rahardja <as*@me.com> wrote:
I have the following program that uses an array of chars to simulate a bit
set:

---------

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags[i] = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK
bitset9.set(-1); // BoundsException thrown

bitset9.set(8); // OK
bitset9.set(9); // BoundsException thrown

return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?

-dr


First of all, there is std::bitset<size_t> as well as
std::vector<bool>. No need to re-invent the wheel here.

Not sure about your last question -- runtime and compile-time are two
orthogonal concepts, actually they are somewhat diametrically opposed.
It seems that you would like to have your cake and eat it, too. If you
want to use runtime values to create a bitset, you have to allocate
the memory dynamically. You could do this if you implement the storage
as a vector and not as an array.

BTW, there are standard exception classes in <stdexcept> you could use
instead of your own BoundsException (std::out_of_range or
std::invalid_argument come to mind). You could also inherit
BoundsException from one of these, or from std::exception.

--
Bob Hairgrove
No**********@Home.com
Nov 22 '05 #2

P: n/a
> However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?


a simple compile time check could be performed with the following set()
variant:

template <int bits = 1>
class Bitset
{
public:
...
// Sets a bit in the bitset.
template <int bit>
void set()
{
static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}
...
}

int main()
{
Bitset<9> bitset9;
bitset9.set<0>(); // OK
bitset9.set<-1>(); // compile time error

bitset9.set<8>(); // OK
bitset9.set<9>(); // compile time error
return 0;

}

this is a template trick that relies on the compiler evaluating the
array size expression at compile time, and complaining about an illegal
size of 0.

maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
more fletched out variant of static assertion.

see http://www.boost.org/doc/html/boost_staticassert.html

-- peter

Nov 22 '05 #3

P: n/a
Dave Rahardja wrote:

See the code I added.

// An out-of-bounds exception
class BoundsException {};

template <int bits = 1>
class Bitset
{
public:

Bitset()
{
// Clear all the bits in the bit flag bytes
for (int i = 0; i < charCount; ++i) {
bitFlags[i] = 0;
}
}

// Sets a bit in the bitset.
void set(int bit)
{
if (bit >= bits || bit < 0) {
throw BoundsException();
}
int byteNum = bit / 8;
int bitNum = bit % 8;
bitFlags[byteNum] |= (1 << bitNum);
}
template <int N>
void set()
{
static_assert( (N<=bits) && (N>=0) );
set( N );
}

private:
static const int charCount = (bits + 7) / 8;
unsigned char bitFlags[charCount];
};

int main()
{
Bitset<9> bitset9;
bitset9.set(0); // OK bitset9.set<0>();
bitset9.set(-1); // BoundsException thrown bitset9.set<-1>();
bitset9.set(8); // OK bitset9.set<8>(); bitset9.set(9); // BoundsException thrown bitset9.set<9>();
return 0;
}

---------

As you can see, I'm using runtime checks to bounds-check the bit number each
time set() is called.

However, it turns out that set() will only receive compile-time constants, and
never runtime computed values.

Is there a way to perform _compile-time_ bounds checking for the indexes? A
little template trickery maybe?


You need to change the parameter and make it a template parameter. You
can either do it by passing a special type or by passing a parameter
specifically.

Anything you can catch at compile time is better than catching at run-time.
Nov 22 '05 #4

P: n/a
On 20 Nov 2005 14:12:32 -0800, "peter steiner" <pn*******@gmail.com> wrote:

static char check_bounds__[(bit >= bits || bit < 0) ? 0 : 1];
....
this is a template trick that relies on the compiler evaluating the
array size expression at compile time, and complaining about an illegal
size of 0.
Nice! This is just what I'm looking for.
maybe you should have a look at BOOST_STATIC_ASSERT for a portable and
more fletched out variant of static assertion.


Right.

Thanks to all the other posters who suggested using the std::bitset and
std::vector<bool> implementations, but I'm writing code for an embedded
product for which the STL implementations are overkill. All the code I posted
is virtually all that's needed.

Besides, I'm still going to resort to a similar trick to make the std::
containers provide me compile-time checks.

-dr
Nov 22 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.