понедельник, 22 октября 2007 г.

Dynamic array template

This is my article prepared for publishing on codeproject.com.

Abstract

Often it is useful to allocate continuous memory block for some data to hold picture or string in it. Sometimes such memory block has non-trivial structure. For instance, it can be some class with dynamic array of elements and the static header as for bitmap that we want to send over network. And the problem is we want to chose array size dynamically. And we want to do it in the simplest and fastest way. This article is written to solve that problem.


Introduction

To send some data block via network or shared memory it is required to be continuous. It can't contain pointers or classes based on dynamic memory allocation – std::vector, for instance. (To be honest it is possible to send non-continuous data, but it could require to write a lot of code on both client and server side. And that code could be hard to support). So what to do in this case?

The simples way to solve the problem is to use C++ zero-sized arrays. Let's look at the following sample:

struct DynamicSizeStruct
{
    int a, b;
    float g;
    long SomeData[0]; // Microsoft compiler reports warning here, but it is safe to use
}

Ok, we have structure declaration now. It's time to allocate some memory. The very first though is to use malloc or it can be function called operator new. Anyway, there is no difference at this point.

size_t data_count = 100;
DynamicSizeStruct* p = reinterpret_cast<DynamicSizeStruct*>(
    malloc( sizeof(DynamicSizeStruct) + sizeof(long)*data_count ) );

Quite a lot of code for simple memory allocation... isn't it? That's the first problem, but it is not the biggest. Let's look at the more complex sample.

class DataUnit
{
public:
    DataUnit();
    ~DataUnit();

    long Data;
};

class DynamicSizeStruct
{
public:
    DynamicSizeStruct();
    virtual ~DynamicSizeStruct();

    int a, b;
    float g;
    DataUnit SomeData[0];
};

Well, we can use malloc as earlier but constructor and destructor will not be invoked. We'll could even use global function operator new for DynamicSizeStruct, but what about DataUnit? That the second problem – how to invoke constructors/destructors for all of the array members?

Here we have two problems. Now the time for solving it.


Reduce code size

To solve the first problem we'll use C++ template:

template<typename BaseT, DataT> class DynamicArrayHolder : public BaseT
{
public:
    DynamicArrayHolder() {};
    virtual ~DynamicArrayHolder() {};

    void* operator new( std::size_t size, std::size_t count );
    void operator delete( void* p ) { ::operator delete ( p ); };
    const DataT& operator[]( std::size_t pos ) const { return N[pos]; }
    DataT& operator[]( std::size_t pos ) { return N[pos]; }

protected:
    DataT DAHData[0]; // dynamic array declaration
}

Template has two parameters, BaseT is the base class to where we want to add dynamic size array, DataT — type of data elements in array. I declared operator new here to allocate all necessary memory at once. Operator delete is quite simple, it's just release all allocated memory. Index operator allows to gain access to data array members.

As you can see constructor and destructor are trivial at this point. The operator new have to care about allocation memory required by DataT elements. Parameter size will be filled by C++ compiler at compile time (it will contain number of bytes required to hold all data members of class BaseT + 4 bytes for virtual table). And parameter count we will use to define number of elements at runtime.


Now we can compare the old way to allocate data:

void* operator new( std::size_t size, std::size_t count )
{
    assert( count > 0 );
    if ( count == 0 ) throw std::bad_alloc();

    void* p = ::operator new ( size + sizeof( DataT )*count ); // allocate all required memory at once
    reinterpret_cast<DynamicArrayHolder*>(p)->Ncount = count;
    return p;
}

with the new one:

struct DynamicSizeStruct
{
    int a, b;
    float g;

    long SomeData[0]; // Microsoft compiler reports warning here, but it is safe to use
};

void someFunc()
{
    size_t data_count = 100;
    DynamicSizeStruct* p = reinterpret_cast<DynamicSizeStruct*>(
        malloc( sizeof( DynamicSizeStruct ) + sizeof(long)*data_count ) );
}

Less code and more readable as we planned! In the final implementation that you can download I've added three more functions GetDataPtr, GetByteSize and GetArraySize. GetDataPtr returns pointer to actual data of the BaseT class and you can use that pointer in memcpy functions with result of GetByteSize function. And finally, GetArraySize returns count of elements in dynamic array. I have to notice that there is one known restriction – we cannot construct BaseStruct with non-empty parameters list constructor.



Time to invoke DataT's constructors

We've already seen global function ::operator new in our operator new. But there we used "most common" form of that function. There is another one. And we will use it to invoke constructors for array members. New constructor implementation will look like that:

DynamicArrayHolder()
{
    for ( size_t n = 0; n < Ncount; ++n ) new ( &N[n] ) DataT;
};

It's just construct DataT elements one by one on already allocated memory block. In destructor we have to call destructor for all DataT elements:

virtual ~DynamicArrayHolder()
{
    for ( size_t n = 0; n < Ncount; ++n ) N[n].~DataT();
};

It is available full version of DynamicArrayHolder template in file DynamicArrayHolder.hpp. It contains additionaly copy constructor and some primitive error processing in the code. Also I've written sample code that have been placed in main.cpp file.

Download test.zip - 1.4 KB

Комментировать в ВКонтакте