Header File for an Array Class

Note:

Table of Contents

• Intend of the class
• Some Preprocessor Stuff
• Handling of Array Traits
  • Definition of the class default_array_traits<T>
  • Definition of the class memcpy_array_traits<T>
• Definition of the class array
• Definition of the Member Functions of array
  • The Normal Constructor
  • The Copy Constructor
  • The Destructor
  • The Assignment Operator
  • The Access Operators
  • The Resize Function

Intend

• There is no need for a default constructor to construct the objects in the array. Instead the objects are created using the copy constructor with a prototype object as argument.
• The array can be resized. It is attempted to make resizing of the array quite efficient.

• Allocation and dislocation of "raw memory": memory is alloceted using operator new[]() and dislocated using operator delete[](). This makes sure that the allocated memory is proper aligned.
• Placement new: Objects are constructed using placement new.
• Explicit destructor calls: The objects constructed with placement new are destructed with an explicit call to the destructor.

Prevent Multiple Inclusion

    #ifndef DK_ARRAY_H
    #define DK_ARRAY_H
    

External Declarations

• assert.h is included for the assert() macro used for a simple bounds check.
• string.h is included for the declaration of memcpy(): This function is used as another example how the traits for the array may look like. However, the traits using memcpy() are not safe for all types and I recommend not to use them. I have made some simple performence tests on Sparc Stations which showed, that these traits are not faster for built-in types than the default types. If the class is finished I want to make more realistic performance tests too.
• new.h is included for the declaration of a placement new.
• dk_defs.h is included for some macros used to encapsulated differences between supported compilers.
• auto_res.h is included for the declaration and implementation of the class auto_res which is a generalization of the auto_ptr class found in the DWP: auto_res claims ownership for an arbitary resource. This is resource is released on destruction. The method to release a resource is defined using a traits template argument.
• Not all currently available C++ compilers support the new C++ built-in type bool. Since this type is used, a kludge to do some support is declared.
• It is also not possible to call the operatores operator new[](...) and operator delete[](...) with all C++ compilers...: Because I think that these operators should be called if they are available some macros are set up to use them if appropriate.

    #include <assert.h>
    #include <string.h>
    #include <new.h>
    
    #include "dk_defs.h"
    #include "auto_res.h"
    
    #ifndef HAVE_BUILT_IN_BOOL
      enum bool
      {
        false = 0,
        true  = 1
      };
    #endif
    
    #ifdef HAVE_ARRAY_OPERATORS
    #  define ARRAY_OP_NEW(size)   ::operator new[] (size)
    #  define ARRAY_OP_DELETE(ptr) ::operator delete[] (ptr)
    #else
    #  define ARRAY_OP_NEW(size)   ::operator new (size)
    #  define ARRAY_OP_DELETE(ptr) ::operator delete (ptr)
    #endif

CAN_DETECT_UNUSED

This macro indicates whether a compiler is able to detect that a certain default argument is never used. This is used by a constructor of class array: To construct an arrayarrayT of the objects stored in the arrayarray. If the compiler does not support the detection that a default argument is never used, it tries to access the default constructor of type T. However, the only need for a default constructor is this default argument. Thus the default argument is disabled if the compiler does not detect that it is unused.

HAVE_FAST_MEMCPY

This macro indicates that memcpy() is really faster in copying an array of objects of a "moveable" type than a "hand-written" loop which uses the copy constructor and the destructor.

HAVE_TEMPLATE_DEFAULT_ARGS

This macro indicates that the compiler is capable to make use of template default arguments. This allows to specify only those template arguments which are of interest and use provided defaults for the other template arguments. For the array class a default template argument is used to select the traits. Without defining this flag, the user has to specify all template arguments.

Array Traits

T *allocate(int size)

This function has to return enough memory to hold (at least) size objects of type T (i.e. the size of the memory returned has to be at least size * sizeof(T). The returned memory has to be correctly aligned.

void dislocate(int size, T *ptr)

This function is used to release the memory which was allocated by allocate(). The argument size is the same as the corresponding argument to the allocate() function unless in an error situation: If the memory is released due to an exception being thrown, the size argument may be 0. The argument ptr is a pointer returned from the allocation function.

void create(T const &proto, void *dst)

This function is used to construct the objects in a new array or the new objects in an array which was enlarged. The argument proto is an object which is expected to be copied. This is used to avoid the need of a default constructor. The argument dst points to the memory reserved for the new object. As a result of this operation dst should point to a constructed object of type T. If it seems to be more appropriate to use some other mechansim than to copy proto to construct the new object, the argument proto can be ignored.

void copy(T const &src, void *dst)

This function is used to copy objects into a new array. The difference to the previous function is that the src argument cannot be ignored like the proto arguement. However, it is still the responsibility of this function to create the copy and how it is done is left to the function. The argument src is the object which is to be copied. The argument dst points to the memory for the new object. As a result of this operation dst should point to a constructed object of type T.

void move(T &src, void *dst)

This function is used to move an object in memory: The argument src is an object which is to be moved to the location indicated by the argument dst. After this operation src is not considered to be a constructed object anymore. I.e. no access is made to it again (from the array; external reference cannot be handled) and no destructor is called. Instead, dst should point to a constructed object of type T.

void destruct(T &obj)

This function is used to destruct an object. The argument obj is the object which has to be destructed.

default_array_traits<T>

These are the traits which are most likely to be used: All operations are made using the normal copy constructor and the destructor of the class. This should be save for all classes which have a correct implementation of the copy constructor and the destructor.

memcpy_array_traits<T>

These are traits which are much like the default traits. Thus it is derived from default_array_traits<T> with only the different function(s) replaced. This is a kind of "static virtuality": The correct function to be called is determined at compile time. The only difference of this traits is the strategy to move an object: Instead of using the copy constructor followed by the destructor, an object is moved using memcpy(). This version will work protable with simple types T: built-in types and POD (plain old data). It might work with additional data types but it is not obvious when it can be used portably. For other types alternatives should be considered.

    template <class T>
    struct default_array_traits
    {
      static void *allocate(int size)               { return ARRAY_OP_NEW(size * sizeof(T)); }
      static void dislocate(int, void *ptr)         { ARRAY_OP_DELETE(ptr); }
    
      static void create(T const &proto, void *dst) { new(dst) T(proto); }
      static void copy(T const &src, void *dst)     { new(dst) T(src); }
      static void move(T &src, void *dst)           { new(dst) T(src); src.~T(); }
      static void destruct(T &obj)                  { obj.~T(); }
    };
    
    template <class T>
    struct memcpy_array_traits: public default_array_traits<T>
    {
      static void move(T &src, void *dst)           { memcpy(dst, &src, sizeof(T)); }
    };

    template <class T>
    struct array_traits: public default_array_traits<T>
    {
    };
    
    #ifdef	HAVE_FAST_MEMCPY
    struct array_traits<char>: public memcpy_array_traits<char> { };
    struct array_traits<unsigned char>: public memcpy_array_traits<unsigned char> { };
    struct array_traits<signed char>: public memcpy_array_traits<signed char> { };
    
    struct array_traits<unsigned short>: public memcpy_array_traits<unsigned short> { };
    struct array_traits<signed short>: public memcpy_array_traits<signed short> { };
    
    struct array_traits<unsigned int>: public memcpy_array_traits<unsigned int> { };
    struct array_traits<signed int>: public memcpy_array_traits<signed int> { };
    
    struct array_traits<unsigned long>: public memcpy_array_traits<unsigned long> { };
    struct array_traits<signed long>: public memcpy_array_traits<signed long> { };
    
    struct array_traits<bool>: public memcpy_array_traits<bool> { };
    struct array_traits<double>: public memcpy_array_traits<double> { };
    struct array_traits<long double>: public memcpy_array_traits<long double> { };
    #endif

    
    #ifdef HAVE_TEMPLATE_DEFAULT_ARGS
    template <class T, class traits = array_traits<T>, class P = T>
    #else
    template <class T, class traits, class P>
    #endif
    
    class array
    {
    private:
      struct res_traits
      {
        static T    *default_value()   { return 0; }
        static void release(void *ptr) { traits::dislocate(0, ptr); }
      };
    
      int                      i_memsize;
      int                      i_size;
      P                        i_proto;
      auto_res<T*, res_traits> i_array;
    
    public:
    #if CAN_DETECT_UNUSED
      array(int size, P const &proto = P());
    #else
      array(int size, P const &proto);
    #endif
      array(array const &rhs);
      ~array();
      array   &operator= (array const &rhs);
    
      T       &operator[] (int idx);
      T const &operator[] (int idx) const;
    
      T       *begin() const;
      T       *end() const;
    
      bool    resize(int new_size);
    };

Normal Constructor

    template <class T, class traits, class P>
    array<T, traits, P>::array(int size, P const &proto):
      i_memsize(size),
      i_size(size),
      i_proto(proto),
  i_array()		cannot be initialized due to assertion.
    {
      assert(0 <= size);
    
      i_array.reset((T *)traits::allocate(i_memsize));
    
      T *arr = i_array.get();
      for (int i = 0; i < i_size; ++i)
        traits::create(i_proto, arr + i);
    }

Copy Constructor

    template <class T, class traits, class P>
    array<T, traits, P>::array(array<T, traits, P> const &rhs):
      i_memsize(rhs.i_size),
      i_size(rhs.i_size),
      i_proto(rhs.i_proto),
      i_array((T *)traits::allocate(i_memsize))
    {
      T *arr     = i_array.get();
      T *rhs_arr = rhs.i_array.get();
    
      for (int i = 0; i < i_size; ++i)
        traits::copy(rhs_arr[i], arr + i);
    }

Destructor

    template <class T, class traits, class P>
    array<T, traits, P>::~array()
    {
      T *arr = i_array.get();
      for (int i = i_size; i--; )
        traits::destruct(arr[i]);
      traits::dislocate(i_memsize, i_array.release());
    }

Assignment Operator

    template <class T, class traits, class P>
    array<T, traits, P> &array<T, traits, P>::operator= (array<T, traits, P> const &rhs)
    {
      if (this != &rhs)
      {
        T *tmp_arr = i_array.get();
        for ( int i = i_size; i--; )
          traits::destruct(tmp_arr[i]);
    
        if (i_memsize < rhs.i_size)
        {
          traits::dislocate(i_memsize, i_array.release());
    
          i_memsize = rhs.i_size;
          i_size    = rhs.i_size;
          i_array.reset((T *)traits::allocate(i_memsize));
        }
        else
          i_size = rhs.i_size;
    
        traits::destruct(i_proto);
        traits::copy(rhs.i_proto, &i_proto);
    
        T *arr     = i_array.get();
        T *rhs_arr = rhs.i_array.get();
        for (int j = 0; j < i_size; ++j)
          traits::copy(rhs_arr[j], arr + j);
      }
      return *this;
    }

Access Operators

    template <class T, class traits, class P>
    T       &array<T, traits, P>::operator[] (int idx)
    {
      assert(0 <= idx && idx < i_size);
      return i_array.get()[idx];
    }
    
    template <class T, class traits, class P>
    T const &array<T, traits, P>::operator[] (int idx) const
    {
      assert(0 <= idx && idx < i_size);
      return i_array.get()[idx];
    }

Resize Function

    template <class T, class traits, class P>
    bool array<T, traits, P>::resize(int new_size)
    {
      assert(0 <= new_size);
    
      if (new_size <= i_size)
      {
        T *arr = i_array.get();
    
        for (int i = new_size; i < i_size; ++i)
          traits::destruct(arr[i]);
    
        i_size = new_size;
        return false;
      }
      else if (new_size <= i_memsize)
      {
        T *arr = i_array.get();
    
        for (int i = i_size; i < new_size; ++i)
          traits::create(i_proto, arr + i);
    
        i_size = new_size;
        return false;
      }
      else
      {
        auto_res<T*, res_traits> new_array((T *)traits::allocate(new_size));
    
        int i        = 0;
        T   *arr     = i_array.get();
        T   *new_arr = new_array.get();
    
        for (; i < i_size; ++i)
          traits::move(arr[i], new_arr + i);
        for (; i < new_size; ++i)
          traits::create(i_proto, new_arr + i);
        
        traits::dislocate(i_memsize, i_array.release());
    
        i_memsize = new_size;
        i_size    = new_size;
        i_array.reset(new_array.release());
    
        return true;
      }
    }
    

    #endif