array.c

Go to the documentation of this file.

/**     \file array.c

    \brief Array code
*/

#include <stdio.h>
#include "util.h"
#include "array.h"


/**
  * \brief  Default number of entries in a new array.
  */

const int ARRAY_INIT_SIZE=3;


// globals that are expected by some old libraries. new code doesnt need
// these because of the tmpInteger field that's been added

int array_global_insert;
int array_global_index;


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/


/**AutomaticEnd***************************************************************/


/** \brief  Allocate an array of number objects, each of size size */

Array_t *
Array_DoAlloc (int size, int number)
{
  Array_t *array;

  array = ALLOC (Array_t, 1);
  if (array == NIL (Array_t))
    {
      return NIL (Array_t);
    }
  array->num = 0;
  array->n_size = MAX (number, ARRAY_INIT_SIZE);
  array->obj_size = size;
  array->index = -size;
  array->space = ALLOC (char, array->n_size * array->obj_size);
  if (array->space == NIL (char))
    {
      return NIL (Array_t);
    }
  (void) memset (array->space, 0, array->n_size * array->obj_size);
  return array;
}


/**     \brief Deallocate an array.  
  * 
  * If array is <code>NULL</code> nothing is done. Freeing the
  *     individual elements of the array is the responsibility of the user.
  */

void
Array_Free ( Array_t *array)
{
  if (array == NIL (Array_t))
    return;
  if (array->index >= 0)
    Array_Abort (array, 4);
  free (array->space);
  free (array);
}


/**     \brief Create a duplicate copy of an array. 
  *
  * If memory cannot be allocated for the new array, 
  * <tt>NIL(Array_t)</tt> is returned.
  */

Array_t *
Array_Dup (Array_t *old)
{
  Array_t *newArray;

  newArray = ALLOC (Array_t, 1);
  if (newArray == NIL (Array_t))
    {
      return NIL (Array_t);
    }
  newArray->num = old->num;
  newArray->n_size = old->num;
  newArray->obj_size = old->obj_size;
  newArray->index = -newArray->obj_size;
  newArray->space = ALLOC (char, newArray->n_size * newArray->obj_size);
  if (newArray->space == NIL (char))
    {
      free (newArray);
      return NIL (Array_t);
    }
  (void) memcpy (newArray->space, old->space, old->num * old->obj_size);
  return newArray;
}


/**
  * \brief  Appends the elements of array2 to the end of array1. Returns 1 if the
  *     operation is successful otherwise returns <tt>ARRAY_OUT_OF_MEM</tt>.
  *
  */

int
Array_Append ( Array_t *array1, Array_t *array2 )
{
  char *pos;

  if (array1->index >= 0)
    Array_Abort (array1, 4);
  if (array1->obj_size != array2->obj_size)
    {
      Array_Abort (array1, 2);
      /* NOTREACHED */
    }

  /* make sure array1 has enough room */
  if (array1->n_size < array1->num + array2->num)
    {
      if (Array_Resize (array1, array1->num + array2->num) ==
      ARRAY_OUT_OF_MEM)
    {
      return ARRAY_OUT_OF_MEM;
    }
    }
  pos = array1->space + array1->num * array1->obj_size;
  (void) memcpy (pos, array2->space, array2->num * array2->obj_size);
  array1->num += array2->num;

  return 1;
}


/**
  * \brief   Returns a new array which consists of the elements from array1
  *     followed by the elements of array2. If the operation is not
  *     successful <code>NIL(Array_t)</code> is returned.
  *
  */

Array_t *
Array_Join ( Array_t *array1, Array_t *array2 )
{
  Array_t *array;
  char *pos;

  if (array1->obj_size != array2->obj_size)
    {
      Array_Abort (array1, 3);
      fail ("array: join not defined for arrays of different sizes\n");
      /* NOTREACHED */
    }
  array = ALLOC (Array_t, 1);
  if (array == NIL (Array_t))
    {
      return NIL (Array_t);
    }
  array->num = array1->num + array2->num;
  array->n_size = array->num;
  array->obj_size = array1->obj_size;
  array->index = -array->obj_size;
  array->space = ALLOC (char, array->n_size * array->obj_size);
  if (array->space == NIL (char))
    {
      free (array);
      return NIL (Array_t);
    }
  (void) memcpy (array->space, array1->space, array1->num * array1->obj_size);
  pos = array->space + array1->num * array1->obj_size;
  (void) memcpy (pos, array2->space, array2->num * array2->obj_size);
  return array;
}

/** \brief Return a regular C array from given array */

char *
Array_DoData ( Array_t *array )
{
  char *data;

  data = ALLOC (char, array->num * array->obj_size);
  if (data == NIL (char))
    {
      return NIL (char);
    }
  (void) memcpy (data, array->space, array->num * array->obj_size);
  return data;
}

/** \brief Resize given array */

int             /* would like to be void, except for macro's */
Array_Resize ( Array_t *array, int new_size )
{
  int old_size;
  char *pos, *newspace;

  /* Note that this is not an exported function, and does not check if
     the array is locked since that is already done by the caller. */
  old_size = array->n_size;
  array->n_size = MAX (array->n_size * 2, new_size);
  newspace = REALLOC (char, array->space, array->n_size * array->obj_size);
  if (newspace == NIL (char))
    {
      array->n_size = old_size;
      return ARRAY_OUT_OF_MEM;
    }
  else
    {
      array->space = newspace;
    }

  pos = array->space + old_size * array->obj_size;
  (void) memset (pos, 0, (array->n_size - old_size) * array->obj_size);
  return 1;
}


/**
  * \brief Sort the elements of an array.  
 
 The <code>compare</code> function is defined as:
<pre>
                int
                compare(obj1, obj2)
                char **obj1;
                char **obj2;
</pre>
        and should return -1 if <code>obj1 < obj2</code>, 0 if <code>obj1 == obj2</code>, or 1
        if <code>obj1 > obj2</code>.

  */

void
Array_Sort ( Array_t *array, int (*compare) () )
{
  qsort (
        (void *) array->space, 
        array->num, 
        array->obj_size, 
        ( int (*)(const void*, const void*) ) compare
    );
}


/**
    \brief Compare adjacent elements of the array, and delete any duplicates.

        Usually the array should be sorted (using Array_Sort) before calling
        Array_Uniq.  `compare' is defined as:
<pre>
                int
                compare(obj1, obj2)
                char *obj1;
                char *obj2;
</pre>
        and returns -1 if <code>obj1 < obj2</code>, 0 if <code>obj1 == obj2</code>, or 1 if <code>obj1 > obj2</code>.
        <code>free_func</code> (if non-null) is defined as:
<pre>
                void
                free_func(obj1)
                char *obj1;
</pre>
        and frees the given array element.

*/


void
Array_Uniq (
     Array_t *array,
     int (*compare) (),
     void (*free_func) () )
{
  int i, last;
  char *dest, *obj1, *obj2;

  dest = array->space;
  obj1 = array->space;
  obj2 = array->space + array->obj_size;
  last = array->num;

  for (i = 1; i < last; i++)
    {
      if (((int (*)(const char**, const char**)) compare) ((const char **) obj1, (const char **) obj2) != 0)
    {
      if (dest != obj1)
        {
          (void) memcpy (dest, obj1, array->obj_size);
        }
      dest += array->obj_size;
    }
      else
    {
      if (free_func != 0) {
        (*( void(*)(char *))free_func) (obj1);
      }
      array->num--;
    }
      obj1 += array->obj_size;
      obj2 += array->obj_size;
    }
  if (dest != obj1)
    {
      (void) memcpy (dest, obj1, array->obj_size);
    }
}


/**
  * \brief Helper function for aborting an array computation.
  *
  *     Would like to be void, except used in macros which need a return type
  */

int             
Array_Abort (Array_t * a, int i)
{
  fputs ("array: ", stderr);

  switch (i)
    {

    case 0:         /* index error on insert */
      fprintf (stderr, "insert of %d\n", a->index);
      break;

    case 1:         /* index error on fetch */
      fprintf (stderr, "fetch index %d not in [0,%d]\n",
           a->tmpInteger, a->num - 1);
      break;

    case 2:         /* append with different element sizes */
      fprintf (stderr, "append undefined for arrays of different sizes\n");
      break;

    case 3:         /* join with different element sizes */
      fprintf (stderr, "join not defined for arrays of different sizes\n");
      break;

    case 4:         /* size error or locked error */
      if (a->index >= 0)
    {
      /* Since Array_Insert is a macro, it is not allowed to nest a
         call to any routine which might move the array space through
         a realloc or free inside an Array_Insert call. */
      fprintf (stderr, "nested insert, append, or free operations\n");
    }
      else
    {
      fprintf (stderr, "object size mismatch\n");
    }
      break;
    default:
      fputs ("unknown error\n", stderr);
      break;
    }

  fail ("array package error");
}


/**
  * \brief
  *    Set the array->num field to 0. This means that insert_last will
  *     happen from the beginning.  array->n_size, which is the actual
  *     number of allocated bytes is unchanged.  

  *     This function exists simply to allow us to reuse an array.  For example,
<pre>
                Array_t *foo;
                foo = Array_Alloc( int, 8 );
                for ( i = 0 ; i < 1024; i++ ) {
                  // do something with foo
                  // now we want to use foo again after we loop,
                  // so call
                  Array_Reset( foo );
               }
</pre>

  */


void
Array_Reset (Array_t *a)
{
  a->num = 0;
}


/**     \brief  Form the union of 3 Array_t
  *
  *     nil arg means array empty. Entries
  *     are ints, indicating applicable rules. Assuming arrays
  *     passed in are sorted in ascending order, result is sorted in
  *     ascending order.
  *
  */

void
Array_Merge (Array_t * result,
         Array_t * rulesFromFsm,
         Array_t * rulesFromShortStringTable,
         Array_t * rulesFromNoContentTable)
{
  int doneFromFsm = (rulesFromFsm == NIL (Array_t)) ||
    (Array_N (rulesFromFsm) == 0);
  int doneFromShort = (rulesFromShortStringTable == NIL (Array_t) ||
               (Array_N (rulesFromShortStringTable) == 0));
  int doneFromNoContent = (rulesFromNoContentTable == NIL (Array_t) ||
               (Array_N (rulesFromNoContentTable) == 0));

  int advance;

  int index0 = 0;
  int index1 = 0;
  int index2 = 0;

  int id0, id1, id2, le01, le02, le12;
  while (!doneFromFsm || !doneFromShort || !doneFromNoContent)
    {

      id0 = (doneFromFsm) ? MAXINT : Array_Fetch (int, rulesFromFsm, index0);
      id1 =
    (doneFromShort) ? MAXINT : Array_Fetch (int,
                        rulesFromShortStringTable,
                        index1);
      id2 =
    (doneFromNoContent) ? MAXINT : Array_Fetch (int,
                            rulesFromNoContentTable,
                            index2);

      le01 = (id0 < id1);
      le12 = (id1 < id2);
      le02 = (id0 < id2);

      if (le01 && le02)
    {
      advance = 0;
    }
      else
    {
      if (le12)
        {
          advance = 1;
        }
      else
        {
          advance = 2;
        }
    }
      if (advance == 0)
    {
      Array_InsertLast (int, result, id0);
      index0++;
      if (index0 == Array_N (rulesFromFsm))
        {
          doneFromFsm = 1;
        }
    }
      else
    {
      if (advance == 1)
        {
          Array_InsertLast (int, result, id1);
          index1++;
          if (index1 == Array_N (rulesFromShortStringTable))
        {
          doneFromShort = 1;
        }
        }
      else
        {
          Array_InsertLast (int, result, id2);
          index2++;
          if (index2 == Array_N (rulesFromNoContentTable))
        {
          doneFromNoContent = 1;
        }
        }
    }
    }
  return;
}


/**
  * \brief  Check functionality of Array_t 
  *
  * Useful when hacking basic Array_t data structure
  */

struct Array_Test_t
{
  int i;
  char c;
};

typedef struct Array_Test_t Array_Test_t;


/**
  * \brief Simple test of Array_t package
  */

void
Array_Test ()
{
  Array_t *iArray = array_alloc (int, 0);

  Array_InsertLast (int, iArray, 123);
  Array_InsertLast (int, iArray, 2 + 3);
  Array_InsertLast (int, iArray, -1);

  printf ("Entry 0 should be 123, is %d\n", Array_Fetch (int, iArray, 0));
  printf ("Entry 1 should be 5, is %d\n", Array_Fetch (int, iArray, 1));
  printf ("Entry 2 should be -1, is %d\n", Array_Fetch (int, iArray, 2));

  array_insert (int, iArray, 1, 400);
  printf ("Entry 1 should be 400, is %d\n", Array_Fetch (int, iArray, 1));

  array_insert (int, iArray, 100, 1968);
  printf ("Entry 100 should be 1968, is %d\n",
      Array_Fetch (int, iArray, 100));


  Array_t *cArray = array_alloc (char, 0);
  Array_InsertLast (char, cArray, 'a');
  Array_InsertLast (char, cArray, 'b');
  Array_InsertLast (char, cArray, 'c');

  printf ("Entry 0 should be a, is %c\n", Array_Fetch (char, cArray, 0));
  printf ("Entry 1 should be b, is %c\n", Array_Fetch (char, cArray, 1));
  printf ("Entry 2 should be c, is %c\n", Array_Fetch (char, cArray, 2));

  array_insert (char, cArray, 1, 'd');
  printf ("Entry 1 should be 'd', is %c\n", Array_Fetch (char, cArray, 1));

  Array_t *tArray = array_alloc (Array_Test_t, 0);
  Array_Test_t tmp;
  tmp.i = 0;
  tmp.c = 'a';

  Array_InsertLast (Array_Test_t, tArray, tmp);
  tmp.i = 1;
  tmp.c = 'b';
  Array_InsertLast (Array_Test_t, tArray, tmp);

  printf ("Entry 0 should be 0.a, is %d.%c\n",
      (Array_Fetch (Array_Test_t, tArray, 0)).i,
      (Array_Fetch (Array_Test_t, tArray, 0)).c);

  printf ("Entry 1 should be 1.b, is %d.%c\n",
      (Array_Fetch (Array_Test_t, tArray, 1)).i,
      (Array_Fetch (Array_Test_t, tArray, 1)).c);

}

void array_test() { Array_Test(); }