Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Counted Body Techniques

Counted Body Techniques

Kevlin Henney
(kevlin@acm.org, khenney@qatraining.com)

And then there were none...

Attached vs detached

A requirements based approach

Getting smart

template
class countable_ptr
{
public: // construction and destruction

    explicit countable_ptr(countable_type *);
    countable_ptr(const countable_ptr &);
    ~countable_ptr();

public: // access

    countable_type *operator->() const;
    countable_type &operator*() const;
    countable_type *get() const;

public: // modification

    countable_ptr &clear();
    countable_ptr &assign(countable_type *);
    countable_ptr &assign(const countable_ptr &);
    countable_ptr &operator=(const countable_ptr &);

private: // representation

    countable_type *body;

};

The interface to this class has been kept intentionally simple, e.g. member templates and throw specs have been omitted, for exposition. The majority of the functions are quite simple in implementation, relying very much on the assign member as a keystone function:

template
countable_ptr::countable_ptr(countable_type *initial)
  : body(initial)
{
    acquire(body);
}

template
countable_ptr::countable_ptr(const countable_ptr &other)
  : body(other.body)
{
    acquire(body);
}

template
countable_ptr::~countable_ptr()
{
    clear();
}

template
countable_type *countable_ptr::operator->() const
{
    return body;
}

template
countable_type &countable_ptr::operator*() const
{
    return *body;
}

template
countable_type *countable_ptr::get() const
{
    return body;
}

template
countable_ptr &countable_ptr::clear()
{
    return assign(0);
}

template
countable_ptr &countable_ptr::assign(countable_type *rhs)
{
    // set to rhs (uses Copy Before Release idiom which is self assignment safe)
    acquire(rhs);
    countable_type *old_body = body;
    body = rhs;

    // tidy up
    release(old_body);
    if(!acquired(old_body))
    {
        dispose(old_body, old_body);
    }

    return *this;
}

template
countable_ptr &countable_ptr::assign(const countable_ptr &rhs)
{
    return assign(rhs.body);
}

template
countable_ptr &countable_ptr::operator=(const countable_ptr &rhs)
{
    return assign(rhs);
}

Public accountability

class countability
{
public: // manipulation

    void acquire() const;
    void release() const;
    size_t acquired() const;

protected: // construction and destruction

    countability();
    ~countability();

private: // representation

    mutable size_t count;

private: // prevention

    countability(const countability &);
    countability &operator=(const countability &);

};

Notice that the manipulation functions are const and that the count member itself is mutable. This is because countability is not a part of an object's abstract state: memory management does not depend on the const-ness or otherwise of an object. I won't include the definitions of the member functions here as you can probably guess them: increment, decrement and return the current count, respectively for the manipulation functions. In a multithreaded environment you should ensure that such read and write operations are atomic.

So how do we make this class Countable? A simple set of forwarding functions does the job:

void acquire(const countability *ptr)
{
    if(ptr)
    {
        ptr->acquire();
    }
}

void release(const countability *ptr)
{
    if(ptr)
    {
        ptr->release();
    }
}

size_t acquired(const countability *ptr)
{
    return ptr ? ptr->acquired() : 0;
}

template
void dispose(const countability_derived *ptr, const countability *)
{
    delete ptr;
}

Any type that now derives from countability may now be used with countable_ptr:

class example : public countability
{
    ...
};

void simple()
{
    countable_ptr ptr(new example);
    countable_ptr qtr(ptr);
    ptr.clear(); // set ptr to point to null
}   // allocated object deleted when qtr destructs

Runtime mixin

struct countable_new;
extern const countable_new countable;

void *operator new(size_t, const countable_new &);
void operator delete(void *, const countable_new &);

We have overloaded operator new with a dummy argument to distinguish it from the regular global operator new. This is comparable to the use of the std::nothrow_t type and std::nothrow object in the standard library. The placement operator delete is there to perform any tidy up in the event of failed construction. Note that this is not yet supported on all that many compilers.

The result of a new expression using countable is an object allocated on the heap that has a header block that holds the count, i.e. we have extended the object by prefixing it. We can provide a couple of features in an anonymous namespace (not shown) in the implementation file for for supporting the count and its access from a raw pointer:

struct count
{
    size_t value;
};

count *header(const void *ptr)
{
    return const_cast(static_cast(ptr) - 1);
}

An important constraint to observe here is the alignment of count should be such that it is suitably aligned for any type. For the definition shown this will be the case on almost all platforms. However, you may need to add a padding member for those that don't, e.g. using an anonymous union to coalign count and the most aligned type. Unfortunately, there is no portable way of specifying this such that the minimum alignment is also observed - this is a common problem when specifying your own allocators that do not directly use the results of either new or malloc.

Again, note that the count is not considered to be a part of the logical state of the object, and hence the conversion from const to non-const - count is in effect a mutable type.

The allocator functions themselves are fairly straightforward:

void *operator new(size_t size, const countable_new &)
{
    count *allocated = static_cast(::operator new(sizeof(count) + size));
    *allocated = count(); // initialise the header
    return allocated + 1; // adjust result to point to the body
}

void operator delete(void *ptr, const countable_new &)
{
    ::operator delete(header(ptr));
}

Given a correctly allocated header, we now need the Countable functions to operate on const void * to complete the picture:

void acquire(const void *ptr)
{
    if(ptr)
    {
        ++header(ptr)->value;
    }
}

void release(const void *ptr)
{
    if(ptr)
    {
        --header(ptr)->value;
    }
}

size_t acquired(const void *ptr)
{
    return ptr ? header(ptr)->value : 0;
}

template
void dispose(const countable_type *ptr, const void *)
{
    ptr->~countable_type();
    operator delete(const_cast(ptr), countable);
}

The most complex of these is the dispose function that must ensure that the correct type is destructed and also that the memory is collected from the correct offset. It uses the value and type of first argument to perform this correctly, and the second argument merely acts as a strategy selector, i.e. the use of const void * distinguishes it from the earlier dispose shown for const countability *.

Getting smarter

class example
{
    ...
};

void simple()
{
    countable_ptr ptr(new(countable) example);
    countable_ptr qtr(ptr);
    ptr.clear(); // set ptr to point to null
}   // allocated object deleted when qtr destructs

The new(countable) expression defines a different policy for allocation and deallocation and, in common with other allocators, any attempt to mix your allocation policies, e.g. call delete on an object allocated with new(countable), results in undefined behaviour. This is similar to what happens when you mix new[] with delete or malloc with delete. The whole point of Countable conformance is that Countable objects are used with countable_ptr, and this ensures the correct use.

However, accidents will happen, and inevitably you may forget to allocate using new(countable) and instead use new. This error and others can be detected in most cases by extending the code shown here to add a check member to the count, validating the check on every access. A benefit of ensuring clear separation between header and implementation source files means that you can introduce a checking version of this allocator without having to recompile your code.

Conclusion

First published in Overload 25, April 1998, ISSN 1354-3172
© Copyright Kevlin Henney, 1998, 1999