array.h

Go to the documentation of this file.

#ifndef ARRAY_H
#define ARRAY_H

#ifdef __cplusplus
extern "C" {
#endif

#include "assert.h"

/** \file array.h

\brief Array data structures

An array_t is a dynamically allocated array.  As elements are inserted
the array is automatically grown to accomodate the new elements.

The first element of the array is always element 0, and the last
element is element n-1 (if the array contains n elements).

This array package is intended for generic objects (i.e., an array of
int, array of char, array of double, array of struct foo *, or even
array of struct foo).

Be careful when creating an array with holes (i.e., when there is no
object stored at a particular position).  An attempt to read such a
position will return a 'zero' object.  It is poor practice to assume
that this value will be properly interpreted as, for example,  (double)
0.0 or (char *) 0.

In the definitions below, 'typeof' indicates that the argument to the
'function' is a C data type; these 'functions' are actually implemented
as macros.

*/


/** \brief Array structure */

typedef struct Array_t
{
  char *space;
  int num;          /* number of array elements.            */
  int n_size;           /* size of 'data' array (in objects)    */
  int obj_size;         /* size of each array object.           */
  int index;            /* combined index and locking flag.     */
  int tmpInteger;       /* use to avoid declaring locally.      */
} Array_t;

typedef Array_t array_t;

// exported functions, live in array.c

extern void Array_Test ( );

extern array_t *Array_DoAlloc (int, int);

static inline array_t *array_do_alloc( int a, int b ) {
  return Array_DoAlloc( a, b );
}


extern Array_t *Array_Dup (Array_t *);
static inline array_t *array_dup( array_t * a ) {
  return Array_Dup( a );
}

extern Array_t *Array_Join (Array_t *, Array_t *);
static inline array_t *array_join (array_t * a, array_t * b) {
  return Array_Join( a, b );
}

extern void Array_Free (Array_t *);
static inline void array_free (array_t * a) {
  return Array_Free ( a );
}

extern void Array_Reset (Array_t *);
static inline void array_reset (array_t * a) {
  return Array_Reset ( a );
}

extern int Array_Append (array_t *, array_t *);
static inline int array_append (array_t * a, array_t * b) {
  return Array_Append ( a, b ); 
}

extern void Array_Sort (array_t *, int (*)());
static inline void array_sort (array_t *a , int (*b)() ) {
  return Array_Sort ( a, b );
}

extern void Array_Uniq (array_t *, int (*)(), void (*)());
static inline void array_uniq (array_t * a, int (*b)() , void (*c)() ) {
  return Array_Uniq ( a, b, c );
}

extern int Array_Abort (array_t *, int);
static inline int array_abort (array_t * a, int b) {
  return Array_Abort (a, b );
}

extern int Array_Resize (array_t *, int);
static inline int array_resize (array_t * a, int b) {
  return Array_Resize ( a ,  b );
}

extern char *Array_DoData (array_t *);
static inline char *array_do_data (array_t * a) {
  return Array_DoData ( a );
}

extern void Array_Merge (array_t *, array_t *, array_t *, array_t *);
static inline void array_merge (array_t *a, array_t *b, array_t *c, array_t * d) {
  return Array_Merge ( a, b, c, d ); 
}


// Return value when memory allocation fails 
#define ARRAY_OUT_OF_MEM -10000


/** \brief Insert an element into an array 

   Perform basic checks: object being inserted is right size, index is legal

*/

static inline void
Array_InsertInternal (int typeSize, array_t * a, int i, void *datum)
{

  // we're passing in the failure message using the comma operator
  // assert is preferred since it will be compiled away with optimization flags set
  if( a->obj_size != typeSize) {
    printf("Insertion into array with wrong size\n");
    assert(0);
  }

  a->index = i;
  if (i < 0)
    {
      printf ("Insertion into array before entry 0\n");
      assert (0);
    }

  if (i >= a->n_size)
    {
      a->tmpInteger = array_resize (a, i + 1);
      if (a->tmpInteger == ARRAY_OUT_OF_MEM)
    {
      printf ("Out of memory resizing array, inserting index %d,"
          "num entries was %d\n", i, a->n_size);
      assert (0);
    }
    }

  if (typeSize == 4)
    {
      *(u_int32_t *) (a->space + i * a->obj_size) = *(u_int32_t *) datum;
    }
  else if (typeSize == 1)
    {
      *(u_int8_t *) (a->space + i * a->obj_size) = *(u_int8_t *) datum;
    }
  else
    {
      memcpy ((a->space + i * a->obj_size), datum, typeSize);
    }
  if (a->index >= a->num)
    {
      a->num = a->index + 1;
    }
  a->index = -(int) typeSize;
}


/** \brief  Returns the number of elements stored in the array.  If this is
`n', then the last element of the array is at position `n' - 1.
*/

static inline int
Array_N (array_t * array)
{
  return array->num;
}

static inline int array_n( array_t *a ) { return Array_N( a ) ; }


static inline void *
Array_FetchInternal (array_t * a, int index, int decrCount)
{
  void *result;

  if (index >= a->num)
    {
      printf ("indexing array outside limit\n");
      assert (0);
    }

  result = (a)->space + (index * a->obj_size);
  if (decrCount)
    {
      // used only by array_delete_last
      assert (index == a->num - 1);
      a->num--;
    }
  return result;
}

/** \brief  Reduce the number of entries by 1

Does not recover space.
*/

static inline void
Array_Decrement (array_t * a)
{
  a->num--;
}

static inline void array_decrement( array_t * a ) { return Array_Decrement( a ); }

/** \brief Insert a new element into an array at the given position.  

The array is dynamically extended if necessary to accomodate the
new item.  It is a serious error if sizeof(type) is not the
same as the type used when the array was allocated.  It is also
a serious error for 'position' to be less than zero.
*/

#define Array_Insert( type, a, i, datum )       \
  { type _array_datum_dup = datum; Array_InsertInternal( sizeof( type ), (a), (i) , & _array_datum_dup );}

#define array_insert( type, a, i, datum )  Array_Insert( type, a, i, datum ) 

/** \brief Allocate and initialize an array of objects of type `type'.

        Polymorphic arrays are okay as long as the type of largest
        object is used for initialization.  The array can initially
        hold `number' objects.  Typical use sets `number' to 0, and
        allows the array to grow dynamically.

  */

#define Array_Alloc(type, number)       \
    Array_DoAlloc( sizeof(type), number)

#define array_alloc( type, number ) Array_Alloc( type, number )

/** 
   \brief Insert a new element at the end of the array.  Equivalent to:

   <pre>array_insert(type, array, array_n(array), object)</pre>

  */

#define Array_InsertLast(type, array, datum)    \
    array_insert(type, array, (array)->num, datum)

#define array_insert_last(type, array, datum) Array_InsertLast(type, array, datum)

/** \brief Fetch an element from an array.  

A runtime error occurs on an
attempt to reference outside the bounds of the array.  There is
no type-checking that the value at the given position is
actually of the type used when dereferencing the array.
*/


#define Array_Fetch( type, a, i )       \
        ( * ( ( type * ) Array_FetchInternal( a, i, 0 ) ) )

#define array_fetch( type, a, i ) \
    Array_Fetch( type, a, i ) 

/** \brief  Fetch a pointer to an element in an array 
*/

#define Array_FetchPtr(type, a, i)                       \
     ( ( type * ) Array_FetchInternal( a, i, 0 ) )

#define array_fetch_p(type, a, i) Array_FetchPtr(type, a, i)                       \

/** \brief  Fetch the last element from an array.  

A runtime error occurs
if there are no elements in the array.  There is no type-checking
that the value at the given position is actually of the type used
when dereferencing the array.  Equivalent to:

<pre>array_fetch(type, array, array_n(array))</pre>
*/


#define Array_FetchLast(type, array)        \
        Array_Fetch(type, array, ((array)->num)-1)

#define array_fetch_last(type, array ) \
    Array_FetchLast(type, array)        \


/**
  * \brief Fetch the last element of the array and delete it from the array.
  */

#define Array_DeleteLast( type, array )     \
     ( * ( ( type * ) Array_FetchInternal( array, ((array)->num)-1, 1 ) ) )

#define array_delete_last( type, array )    \
    Array_DeleteLast( type, array )

/** \brief  Returns a normal `C' array from an array_t structure.  

This is sometimes necessary when dealing with functions which do not
understand the array_t data type.  A copy of the array is
returned, and it is the users responsibility to free it.  array_n()
can be used to get the number of elements in the array.
*/

#define Array_Data(type, array)         \
    (type *) Array_DoData(array)

// conflicts with qt
// #define array_data( type, array ) Array_Data( type, array )


/** \brief Macro to iterate over the items of an array.

<ul>
<li>  <code>type</code>,  type of object stored in array 
<li>  <code>array</code>, array to iterate 
<li>  <code>i</code>,     int, local variable for iterator 
<li>  <code>data</code>   object of type 
</ul>
*/


#define arrayForEachItem(                                      \
  type,  /* type of object stored in array */                  \
  array, /* array to iterate */                                \
  i,     /* int, local variable for iterator */                \
  data   /* object of type */                                  \
)                                                              \
  for((i) = 0;                                                 \
      (((i) < array_n((array)))                                \
       && (((data) = array_fetch(type, (array), (i))), 1));    \
      (i)++)

// orignial code 

#define array_insert_old(type, a, i, datum)         \
    (  -(a)->index != sizeof(type) ? array_abort((a),4) : 0,\
        (a)->index = (i),\
        (a)->index < 0 ? array_abort((a),0) : 0,\
        (a)->index >= (a)->n_size ?\
    a->tmpInteger = array_resize(a, (a)->index + 1) : 0,\
        a->tmpInteger != ARRAY_OUT_OF_MEM ?\
        *((type *) ((a)->space + (a)->index * (a)->obj_size)) = datum : datum,\
        a->tmpInteger != ARRAY_OUT_OF_MEM ?\
        ((a)->index >= (a)->num ? (a)->num = (a)->index + 1 : 0) : 0,\
        a->tmpInteger != ARRAY_OUT_OF_MEM ?\
        ((a)->index = -(int)sizeof(type)) : ARRAY_OUT_OF_MEM )

#define array_fetch_old(type, a, i)         \
    (a->tmpInteger = (i),               \
      (a->tmpInteger >= (a)->num) ? array_abort((a),1) : 0,\
      *((type *) ((a)->space + a->tmpInteger * (a)->obj_size)))

#ifdef __cplusplus
}
#endif

#endif // ARRAY_H