NAME

dynarray − generic dynamic arrays for C++

SYNOPSIS

#include <codelibs/dynarray.h>
 // preconditions:
class TYPE
{
public:
TYPE();// optional constructor
~TYPE();// optional destructor
void operator=(TYPE &t);
};
 // declare and create an ARRAY of type TYPE and a BUMP value:
declare_array(ARRAY, TYPE, BUMP);
implement_array(ARRAY, TYPE, BUMP);
 // which creates this class:
class ARRAY
{
public:
ARRAY(long length);
ARRAY();
ARRAY(const ARRAY &);
~ARRAY();
ARRAY &operator=(const ARRAY &);
long size() const;
void reset(int newlen = 0);
TYPE &operator[](long elt);
TYPE &elt(long e) const;
TYPE &end();
TYPE *getarr() const;
TYPE *operator()() const;
};
  // a DYNARRAY with arbitrary lower bound instead of zero:
declare_dynarray(DYNARRAY, TYPE);
implement_dynarray(DYNARRAY, TYPE);
class DYNARRAY
{
public:
DYNARRAY(long len, long start = 0, unsigned bump = 1024);
DYNARRAY();
DYNARRAY(const DYNARRAY &t);
~DYNARRAY();
DYNARRAY &operator=(const DYNARRAY &);
long size() const;
void reset(long newlen = 0, long newstart = 0);
long smallest() const;
long largest() const;
TYPE &operator[](long elt);
TYPE &elt(long e) const;
TYPE &end();
TYPE *getarr() const;
TYPE *operator()() const;
};
 // pre-declared type Charbuf for a buffer of characters:
declare_array(Charbuf, char, 256);
 CC ... -lcodelibs

DESCRIPTION

Dynarray is a C++ generic header file for declaring dynamic arrays of any arbitrary type (including other dynamic arrays).  These arrays have no upper bound limit and are automatically grown to accomodate new elements. 

They may be used to implement buffers of characters for I/O processing which never “run off the end”, simple sequential lists instead of using a linked list, and even a stack with no top. 

Preconditions

For both types of dynamic arrays, the user’s TYPE must have operator= defined for assignment to copy array elements when growing the array. If the type chosen is a builtin type, the assignment operator is already defined. If a constructor and destructor are defined, they will be used appropriately as array elements are created and destroyed.

ARRAY

An ARRAY is the most efficient form of dynamic array.  The lower bound is always zero (0) and it acts much like a normal C or C++ array. 

declaration & implementation

The macro declare_array declares an ARRAY of a specified TYPE. The name ARRAY is now the name of a new class.  There may only be a single declare_array for a given ARRAY.

The integer value BUMP is used when growing the array to somewhat control memory size and fragmentation.  The ARRAY is roughly doubled in size until it hits the BUMP limit, after which it is grown only in BUMP sized chunks, if necessary.  A large value limits fragmentation at the expense of using more memory.  The BUMP value must always be a number greater than zero or a core-dump will be the most likely result. 

The macro implement_array must have the same arguments as declare_array and must only be used once for an ARRAY of a TYPE in the user code.  Typically, the implement_array is put in a user’s "file.C" source file and the associated declare_array in a "file.h" header file. 

The normal generic macros (as described in the “C++ Programming Language” by Bjarne Stroustrup pp. 209) declare and implement may also be used if desired, but with the name darray as in "declare(darray,int)".  BUMP is preset to 1024 as a nice default bumpsize.  This style of creating darrays is not recommended since it is somewhat more difficult to read. 

If TYPE needs to be initialized to some value, it should be made into a class with the appropriate constructors. 

constructors

The constructors allow setting the initial length of the array (if desired) for efficiency, but do not affect or modify the BUMP value described above. 

operator=

This allows one array to be efficiently copied to another. 

size

Return the current length of the array.  The length will change as larger elements are accessed. 

reset

This sets the length of the array to newlen even if the array has to be grown to fit.  If newlen is less than the current array bounds, memory used by the array is NOT freed, even though the current size() of the array is smaller.  The newlen value must not be less than zero. 

operator[]

This accesses an array returning the element at the index elt. If elt does not currently exist, the array is grown and the new element is returned.  The value of elt must not be less than zero. 

elt

This returns the element e in the array much like operator[] above, but without any bounds checking or array growing at all.  This is used for efficiency when the array length is known and no greater indexes are needed. 

end

This just returns one element beyond the current end of the array.  This is the equivalent of the idiom arr[arr.size()] but somewhat less clumbersome for easily appending elements to the end of an array. 

getarr operator()

Return a pointer to the start of the actual array.  This is for even more direct access to the array than elt(). This should be used carefully, since the array may be moved around in memory if its size changes rendering all previous values returned by getarr invalid. 

DYNARRAY

A DYNARRAY allows setting arbitrary lower bounds as well as upper bounds.  This flavor of dynamic array is more Pascal-like ("A[-3:4]") but can grow in either direction automatically. 

declaration & implementation

This is done much like array except that there is no BUMP value.  Where each ARRAY class has a bump size, each DYNARRAY variable (instantiated class) can have its own bump value.  Again, the generic declare and implement macros may also be used, as in the example code below. 

constructors

Dynarrays may be constructed with optional length, initial index start, and bump sizes.  The initial index is the initial lower bound of the array.  The upper bound is length plus start.

When grown, the array size is roughly doubled until it is larger than bump after which it is just grown in bump sized chunks.  The bump value must be a positive value. 

operator=

This allows efficient copying of one array to another. 

size

Returns the current total length of the array. 

reset

Sets the new length of the array to newlen and the lower bound to newstart even if the array has to be grown to fit.  Again, memory isn’t actually freed if the new size is smaller. 

smallest

Returns the lower bound of the array. 

largest

Returns the upper bound of the array. 

operator[]

Return the element elt in the array.  If elt is out of current bounds, the array is grown in the appropriate directory and the new element returned. 

elt

Returns the element e without bounds checking or growing the array.  This allows efficient array access once the bounds are known. 

end

This just returns the element located just beyond the current largest element, and is the equivalent of arr[arr.largest() + 1]

getarr operator()

Returns a pointer to the zeroth element of the array, so that negative index references work as expected.  Again, this should be used very carefully, as the array may be moved in memory to re-size it. 

Charbuf

This is a pre-defined class for a dynamic array of characters.  It is quite handy for buffering (effectively) infinite numbers of characters without having to allocate a fixed size buffer nor having to remember to grow the array properly.  Just use operator[] or end() to add characters to the buffer, size() to get the current location within the buffer, reset() to reset the pointer to the beginning, and getarr() to get a pointer to the start of the buffer.  To add characters to the end of the buffer easily, use end().

EXAMPLES

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <codelibs/dynarray.h>
  // this declares and creates an ARRAY of longs named "intarr":
// note the very small bump size to force the array to grow slowly
declare_array(intarr, long, 4);
implement_array(intarr, long, 4);
 // here’s another way to do the same thing using DYNARRAYs:
declare(dynarray, long);
implement(dynarray, long);
  main()
{
    // we create a new intarr named "a"
    intarr a;
    long i;
     // append new int values to the end of "a" - treat it like a list
    for (i = 0; i < 10; i++)
    a[i] = i + 1;
    // then print them out backwards
    for (i = a.size() - 1; i >= 0; i--)
    printf("%d ", a[i]);
    printf("\n");
       // here’s the other way to declare a dynarray:
    dynarray(long) b;
     // add the elements from "a" to "b" in wierd way
    for (i = 0; i < a.size(); i++)
    {
for (int j = 0; j < a.size(); j++)
    b[-j + i] = i;
    }
     // and print them out
    for (i = b.smallest(); i <= b.largest(); i++)
    printf("%d=%d ", i, b[i]);
    printf("\n\n");
       // this is the most useful - an array of characters:
    Charbuf buf;
     // add some characters, append a null, then print it out
    buf.reset();
    for (int c = 0; c < 26; c++)
    buf.end() = ’A’ + c;
    buf.end() = ’\0’;
    printf("%s\n", buf.getarr());
      return 0;
}

  —