gistfile1.cpp

// -*-c++-*-

#ifndef TRIVIAL_ALLOCATOR_H_
#define TRIVIAL_ALLOCATOR_H_

#include <cstdlib>
#include <climits>

namespace af {

template<typename T>
class TrivialAllocator {
  public:
    typedef unsigned char byte;
    typedef T value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    typedef T* pointer;
    typedef const T* const_pointer;

    typedef T& reference;
    typedef const T& const_reference;

    TrivialAllocator(size_t size_bytes, byte* underlying)
        :size_bytes_(size_bytes),
         underlying_(underlying),
         pos_(0) {       
    }
    
    virtual ~TrivialAllocator() {        
    }

    template<typename U>
    TrivialAllocator(const TrivialAllocator<U>& other)
            :underlying_(other.GetUnderlying()),
             size_bytes_(other.GetSizeBytes()),
             pos_(other.GetPos()) {
    }

    template<typename U>
    struct rebind {
        typedef TrivialAllocator<U> other;
    };
   
    byte* GetUnderlying() const {
        return underlying_;
    }
    
    size_t GetSizeBytes() const {
        return size_bytes_;
    }
    
    size_t GetPos() const {
        return pos_;
    }
    
    pointer address(reference r) const {
        return &r;
    }
    
    const_pointer address(const_reference r) const {
        return &r;
    }

    pointer allocate(size_type n, const void* /*hint*/ = NULL) {
        pointer ret = NULL;
        size_t requested = n * sizeof(value_type);
        if ((pos_ + requested) < size_bytes_) {
            ret = reinterpret_cast<pointer>(&underlying_[pos_]);
            pos_ += requested;
        }
        if (ret == NULL) {
            throw std::bad_alloc();
        }
        return ret;                
    }
    
    void deallocate(pointer /*hint*/, size_type /*hint*/) {
        // Nothing to do, we're re-using the space
    }

    void construct(pointer p, const T& val) {
        // Using placement new
        new (p) T(val);
    }
    
    void destroy(pointer p) {
        p->~T();
    }

    size_type max_size() const {
        return ULONG_MAX / sizeof(T);
    }
    
private:
    size_t size_bytes_;
    byte* underlying_;    
    size_t pos_;
};

}

#endif // TRIVIAL_ALLOCATOR_H_

trivial_allocator_test.cc

#include "test_common.h"
#include "trivial_allocator.h"
#include "gtest/gtest.h"

#include <cstdint>
#include <vector>
#include <cstdlib>

namespace {

using af::TrivialAllocator;
using af::Person;

class TrivialAllocatorTest: public ::testing::Test {
  protected:
    typedef unsigned char byte;
    
    enum { kBytes = 4096 };

    TrivialAllocatorTest()
            :underlying_(static_cast<byte*>(std::calloc(kBytes, sizeof(byte)))),
             integers_(kBytes, underlying_),
             people_(kBytes, underlying_),
             bytes_(kBytes, underlying_) {
    }

    virtual ~TrivialAllocatorTest() {
        std::free(underlying_);
    }
    
    byte* underlying_;
    TrivialAllocator<uint32_t> integers_;
    TrivialAllocator<Person> people_;
    TrivialAllocator<byte> bytes_;
};

// Test that the allocator works for integral types
TEST_F(TrivialAllocatorTest, IntegralTypes) {
    std::vector<uint32_t, TrivialAllocator<uint32_t> > vec(integers_);
    for (uint32_t i = 0; i < 256; ++i) {
        vec.push_back(i);
        EXPECT_EQ(i, vec[i]);
    }
}

// Test that the allocator works with user defined types
TEST_F(TrivialAllocatorTest, UserDefinedTypes) {
    std::vector<Person, TrivialAllocator<Person> > vec(people_);
    Person doe(21, "John Doe");
    vec.push_back(doe);
    EXPECT_EQ(doe, vec[0]);
}

// Test that the allocator throws bad alloc when we overflow
TEST_F(TrivialAllocatorTest, TestThrowBadAlloc) {
    std::vector<byte, TrivialAllocator<byte> > vec(bytes_);
    byte b = 0;
    for (int i = 0; i < kBytes / 2; ++i) {
        vec.push_back(b);
    }
    EXPECT_THROW(vec.push_back(b), std::bad_alloc);
}

} // namespace

int main(int argc, char **argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}