Azinix

array.c

Go to the documentation of this file.
00001 /**     \file array.c
00002 
00003     \brief Array code
00004 */
00005 
00006 #include <stdio.h>
00007 #include "util.h"
00008 #include "array.h"
00009 
00010 
00011 /**
00012   * \brief  Default number of entries in a new array.
00013   */
00014 
00015 const int ARRAY_INIT_SIZE=3;
00016 
00017 
00018 // globals that are expected by some old libraries. new code doesnt need
00019 // these because of the tmpInteger field that's been added
00020 
00021 int array_global_insert;
00022 int array_global_index;
00023 
00024 
00025 /**AutomaticStart*************************************************************/
00026 
00027 /*---------------------------------------------------------------------------*/
00028 /* Static function prototypes                                                */
00029 /*---------------------------------------------------------------------------*/
00030 
00031 
00032 /**AutomaticEnd***************************************************************/
00033 
00034 
00035 /** \brief  Allocate an array of number objects, each of size size */
00036 
00037 Array_t *
00038 Array_DoAlloc (int size, int number)
00039 {
00040   Array_t *array;
00041 
00042   array = ALLOC (Array_t, 1);
00043   if (array == NIL (Array_t))
00044     {
00045       return NIL (Array_t);
00046     }
00047   array->num = 0;
00048   array->n_size = MAX (number, ARRAY_INIT_SIZE);
00049   array->obj_size = size;
00050   array->index = -size;
00051   array->space = ALLOC (char, array->n_size * array->obj_size);
00052   if (array->space == NIL (char))
00053     {
00054       return NIL (Array_t);
00055     }
00056   (void) memset (array->space, 0, array->n_size * array->obj_size);
00057   return array;
00058 }
00059 
00060 
00061 /**     \brief Deallocate an array.  
00062   * 
00063   * If array is <code>NULL</code> nothing is done. Freeing the
00064   *     individual elements of the array is the responsibility of the user.
00065   */
00066 
00067 void
00068 Array_Free ( Array_t *array)
00069 {
00070   if (array == NIL (Array_t))
00071     return;
00072   if (array->index >= 0)
00073     Array_Abort (array, 4);
00074   free (array->space);
00075   free (array);
00076 }
00077 
00078 
00079 /**     \brief Create a duplicate copy of an array. 
00080   *
00081   * If memory cannot be allocated for the new array, 
00082   * <tt>NIL(Array_t)</tt> is returned.
00083   */
00084 
00085 Array_t *
00086 Array_Dup (Array_t *old)
00087 {
00088   Array_t *newArray;
00089 
00090   newArray = ALLOC (Array_t, 1);
00091   if (newArray == NIL (Array_t))
00092     {
00093       return NIL (Array_t);
00094     }
00095   newArray->num = old->num;
00096   newArray->n_size = old->num;
00097   newArray->obj_size = old->obj_size;
00098   newArray->index = -newArray->obj_size;
00099   newArray->space = ALLOC (char, newArray->n_size * newArray->obj_size);
00100   if (newArray->space == NIL (char))
00101     {
00102       free (newArray);
00103       return NIL (Array_t);
00104     }
00105   (void) memcpy (newArray->space, old->space, old->num * old->obj_size);
00106   return newArray;
00107 }
00108 
00109 
00110 /**
00111   * \brief  Appends the elements of array2 to the end of array1. Returns 1 if the
00112   *     operation is successful otherwise returns <tt>ARRAY_OUT_OF_MEM</tt>.
00113   *
00114   */
00115 
00116 int
00117 Array_Append ( Array_t *array1, Array_t *array2 )
00118 {
00119   char *pos;
00120 
00121   if (array1->index >= 0)
00122     Array_Abort (array1, 4);
00123   if (array1->obj_size != array2->obj_size)
00124     {
00125       Array_Abort (array1, 2);
00126       /* NOTREACHED */
00127     }
00128 
00129   /* make sure array1 has enough room */
00130   if (array1->n_size < array1->num + array2->num)
00131     {
00132       if (Array_Resize (array1, array1->num + array2->num) ==
00133       ARRAY_OUT_OF_MEM)
00134     {
00135       return ARRAY_OUT_OF_MEM;
00136     }
00137     }
00138   pos = array1->space + array1->num * array1->obj_size;
00139   (void) memcpy (pos, array2->space, array2->num * array2->obj_size);
00140   array1->num += array2->num;
00141 
00142   return 1;
00143 }
00144 
00145 
00146 /**
00147   * \brief   Returns a new array which consists of the elements from array1
00148   *     followed by the elements of array2. If the operation is not
00149   *     successful <code>NIL(Array_t)</code> is returned.
00150   *
00151   */
00152 
00153 Array_t *
00154 Array_Join ( Array_t *array1, Array_t *array2 )
00155 {
00156   Array_t *array;
00157   char *pos;
00158 
00159   if (array1->obj_size != array2->obj_size)
00160     {
00161       Array_Abort (array1, 3);
00162       fail ("array: join not defined for arrays of different sizes\n");
00163       /* NOTREACHED */
00164     }
00165   array = ALLOC (Array_t, 1);
00166   if (array == NIL (Array_t))
00167     {
00168       return NIL (Array_t);
00169     }
00170   array->num = array1->num + array2->num;
00171   array->n_size = array->num;
00172   array->obj_size = array1->obj_size;
00173   array->index = -array->obj_size;
00174   array->space = ALLOC (char, array->n_size * array->obj_size);
00175   if (array->space == NIL (char))
00176     {
00177       free (array);
00178       return NIL (Array_t);
00179     }
00180   (void) memcpy (array->space, array1->space, array1->num * array1->obj_size);
00181   pos = array->space + array1->num * array1->obj_size;
00182   (void) memcpy (pos, array2->space, array2->num * array2->obj_size);
00183   return array;
00184 }
00185 
00186 /** \brief Return a regular C array from given array */
00187 
00188 char *
00189 Array_DoData ( Array_t *array )
00190 {
00191   char *data;
00192 
00193   data = ALLOC (char, array->num * array->obj_size);
00194   if (data == NIL (char))
00195     {
00196       return NIL (char);
00197     }
00198   (void) memcpy (data, array->space, array->num * array->obj_size);
00199   return data;
00200 }
00201 
00202 /** \brief Resize given array */
00203 
00204 int             /* would like to be void, except for macro's */
00205 Array_Resize ( Array_t *array, int new_size )
00206 {
00207   int old_size;
00208   char *pos, *newspace;
00209 
00210   /* Note that this is not an exported function, and does not check if
00211      the array is locked since that is already done by the caller. */
00212   old_size = array->n_size;
00213   array->n_size = MAX (array->n_size * 2, new_size);
00214   newspace = REALLOC (char, array->space, array->n_size * array->obj_size);
00215   if (newspace == NIL (char))
00216     {
00217       array->n_size = old_size;
00218       return ARRAY_OUT_OF_MEM;
00219     }
00220   else
00221     {
00222       array->space = newspace;
00223     }
00224 
00225   pos = array->space + old_size * array->obj_size;
00226   (void) memset (pos, 0, (array->n_size - old_size) * array->obj_size);
00227   return 1;
00228 }
00229 
00230 
00231 /**
00232   * \brief Sort the elements of an array.  
00233  
00234  The <code>compare</code> function is defined as:
00235 <pre>
00236                 int
00237                 compare(obj1, obj2)
00238                 char **obj1;
00239                 char **obj2;
00240 </pre>
00241         and should return -1 if <code>obj1 < obj2</code>, 0 if <code>obj1 == obj2</code>, or 1
00242         if <code>obj1 > obj2</code>.
00243 
00244   */
00245 
00246 void
00247 Array_Sort ( Array_t *array, int (*compare) () )
00248 {
00249   qsort (
00250         (void *) array->space, 
00251         array->num, 
00252         array->obj_size, 
00253         ( int (*)(const void*, const void*) ) compare
00254     );
00255 }
00256 
00257 
00258 /**
00259     \brief Compare adjacent elements of the array, and delete any duplicates.
00260 
00261         Usually the array should be sorted (using Array_Sort) before calling
00262         Array_Uniq.  `compare' is defined as:
00263 <pre>
00264                 int
00265                 compare(obj1, obj2)
00266                 char *obj1;
00267                 char *obj2;
00268 </pre>
00269         and returns -1 if <code>obj1 < obj2</code>, 0 if <code>obj1 == obj2</code>, or 1 if <code>obj1 > obj2</code>.
00270         <code>free_func</code> (if non-null) is defined as:
00271 <pre>
00272                 void
00273                 free_func(obj1)
00274                 char *obj1;
00275 </pre>
00276         and frees the given array element.
00277 
00278 */
00279 
00280 
00281 void
00282 Array_Uniq (
00283      Array_t *array,
00284      int (*compare) (),
00285      void (*free_func) () )
00286 {
00287   int i, last;
00288   char *dest, *obj1, *obj2;
00289 
00290   dest = array->space;
00291   obj1 = array->space;
00292   obj2 = array->space + array->obj_size;
00293   last = array->num;
00294 
00295   for (i = 1; i < last; i++)
00296     {
00297       if (((int (*)(const char**, const char**)) compare) ((const char **) obj1, (const char **) obj2) != 0)
00298     {
00299       if (dest != obj1)
00300         {
00301           (void) memcpy (dest, obj1, array->obj_size);
00302         }
00303       dest += array->obj_size;
00304     }
00305       else
00306     {
00307       if (free_func != 0) {
00308         (*( void(*)(char *))free_func) (obj1);
00309       }
00310       array->num--;
00311     }
00312       obj1 += array->obj_size;
00313       obj2 += array->obj_size;
00314     }
00315   if (dest != obj1)
00316     {
00317       (void) memcpy (dest, obj1, array->obj_size);
00318     }
00319 }
00320 
00321 
00322 /**
00323   * \brief Helper function for aborting an array computation.
00324   *
00325   *     Would like to be void, except used in macros which need a return type
00326   */
00327 
00328 int             
00329 Array_Abort (Array_t * a, int i)
00330 {
00331   fputs ("array: ", stderr);
00332 
00333   switch (i)
00334     {
00335 
00336     case 0:         /* index error on insert */
00337       fprintf (stderr, "insert of %d\n", a->index);
00338       break;
00339 
00340     case 1:         /* index error on fetch */
00341       fprintf (stderr, "fetch index %d not in [0,%d]\n",
00342            a->tmpInteger, a->num - 1);
00343       break;
00344 
00345     case 2:         /* append with different element sizes */
00346       fprintf (stderr, "append undefined for arrays of different sizes\n");
00347       break;
00348 
00349     case 3:         /* join with different element sizes */
00350       fprintf (stderr, "join not defined for arrays of different sizes\n");
00351       break;
00352 
00353     case 4:         /* size error or locked error */
00354       if (a->index >= 0)
00355     {
00356       /* Since Array_Insert is a macro, it is not allowed to nest a
00357          call to any routine which might move the array space through
00358          a realloc or free inside an Array_Insert call. */
00359       fprintf (stderr, "nested insert, append, or free operations\n");
00360     }
00361       else
00362     {
00363       fprintf (stderr, "object size mismatch\n");
00364     }
00365       break;
00366     default:
00367       fputs ("unknown error\n", stderr);
00368       break;
00369     }
00370 
00371   fail ("array package error");
00372 }
00373 
00374 
00375 /**
00376   * \brief
00377   *    Set the array->num field to 0. This means that insert_last will
00378   *     happen from the beginning.  array->n_size, which is the actual
00379   *     number of allocated bytes is unchanged.  
00380 
00381   *     This function exists simply to allow us to reuse an array.  For example,
00382 <pre>
00383                 Array_t *foo;
00384                 foo = Array_Alloc( int, 8 );
00385                 for ( i = 0 ; i < 1024; i++ ) {
00386                   // do something with foo
00387                   // now we want to use foo again after we loop,
00388                   // so call
00389                   Array_Reset( foo );
00390                }
00391 </pre>
00392 
00393   */
00394 
00395 
00396 void
00397 Array_Reset (Array_t *a)
00398 {
00399   a->num = 0;
00400 }
00401 
00402 
00403 /**     \brief  Form the union of 3 Array_t
00404   *
00405   *     nil arg means array empty. Entries
00406   *     are ints, indicating applicable rules. Assuming arrays
00407   *     passed in are sorted in ascending order, result is sorted in
00408   *     ascending order.
00409   *
00410   */
00411 
00412 void
00413 Array_Merge (Array_t * result,
00414          Array_t * rulesFromFsm,
00415          Array_t * rulesFromShortStringTable,
00416          Array_t * rulesFromNoContentTable)
00417 {
00418   int doneFromFsm = (rulesFromFsm == NIL (Array_t)) ||
00419     (Array_N (rulesFromFsm) == 0);
00420   int doneFromShort = (rulesFromShortStringTable == NIL (Array_t) ||
00421                (Array_N (rulesFromShortStringTable) == 0));
00422   int doneFromNoContent = (rulesFromNoContentTable == NIL (Array_t) ||
00423                (Array_N (rulesFromNoContentTable) == 0));
00424 
00425   int advance;
00426 
00427   int index0 = 0;
00428   int index1 = 0;
00429   int index2 = 0;
00430 
00431   int id0, id1, id2, le01, le02, le12;
00432   while (!doneFromFsm || !doneFromShort || !doneFromNoContent)
00433     {
00434 
00435       id0 = (doneFromFsm) ? MAXINT : Array_Fetch (int, rulesFromFsm, index0);
00436       id1 =
00437     (doneFromShort) ? MAXINT : Array_Fetch (int,
00438                         rulesFromShortStringTable,
00439                         index1);
00440       id2 =
00441     (doneFromNoContent) ? MAXINT : Array_Fetch (int,
00442                             rulesFromNoContentTable,
00443                             index2);
00444 
00445       le01 = (id0 < id1);
00446       le12 = (id1 < id2);
00447       le02 = (id0 < id2);
00448 
00449       if (le01 && le02)
00450     {
00451       advance = 0;
00452     }
00453       else
00454     {
00455       if (le12)
00456         {
00457           advance = 1;
00458         }
00459       else
00460         {
00461           advance = 2;
00462         }
00463     }
00464       if (advance == 0)
00465     {
00466       Array_InsertLast (int, result, id0);
00467       index0++;
00468       if (index0 == Array_N (rulesFromFsm))
00469         {
00470           doneFromFsm = 1;
00471         }
00472     }
00473       else
00474     {
00475       if (advance == 1)
00476         {
00477           Array_InsertLast (int, result, id1);
00478           index1++;
00479           if (index1 == Array_N (rulesFromShortStringTable))
00480         {
00481           doneFromShort = 1;
00482         }
00483         }
00484       else
00485         {
00486           Array_InsertLast (int, result, id2);
00487           index2++;
00488           if (index2 == Array_N (rulesFromNoContentTable))
00489         {
00490           doneFromNoContent = 1;
00491         }
00492         }
00493     }
00494     }
00495   return;
00496 }
00497 
00498 
00499 /**
00500   * \brief  Check functionality of Array_t 
00501   *
00502   * Useful when hacking basic Array_t data structure
00503   */
00504 
00505 struct Array_Test_t
00506 {
00507   int i;
00508   char c;
00509 };
00510 
00511 typedef struct Array_Test_t Array_Test_t;
00512 
00513 
00514 /**
00515   * \brief Simple test of Array_t package
00516   */
00517 
00518 void
00519 Array_Test ()
00520 {
00521   Array_t *iArray = array_alloc (int, 0);
00522 
00523   Array_InsertLast (int, iArray, 123);
00524   Array_InsertLast (int, iArray, 2 + 3);
00525   Array_InsertLast (int, iArray, -1);
00526 
00527   printf ("Entry 0 should be 123, is %d\n", Array_Fetch (int, iArray, 0));
00528   printf ("Entry 1 should be 5, is %d\n", Array_Fetch (int, iArray, 1));
00529   printf ("Entry 2 should be -1, is %d\n", Array_Fetch (int, iArray, 2));
00530 
00531   array_insert (int, iArray, 1, 400);
00532   printf ("Entry 1 should be 400, is %d\n", Array_Fetch (int, iArray, 1));
00533 
00534   array_insert (int, iArray, 100, 1968);
00535   printf ("Entry 100 should be 1968, is %d\n",
00536       Array_Fetch (int, iArray, 100));
00537 
00538 
00539   Array_t *cArray = array_alloc (char, 0);
00540   Array_InsertLast (char, cArray, 'a');
00541   Array_InsertLast (char, cArray, 'b');
00542   Array_InsertLast (char, cArray, 'c');
00543 
00544   printf ("Entry 0 should be a, is %c\n", Array_Fetch (char, cArray, 0));
00545   printf ("Entry 1 should be b, is %c\n", Array_Fetch (char, cArray, 1));
00546   printf ("Entry 2 should be c, is %c\n", Array_Fetch (char, cArray, 2));
00547 
00548   array_insert (char, cArray, 1, 'd');
00549   printf ("Entry 1 should be 'd', is %c\n", Array_Fetch (char, cArray, 1));
00550 
00551   Array_t *tArray = array_alloc (Array_Test_t, 0);
00552   Array_Test_t tmp;
00553   tmp.i = 0;
00554   tmp.c = 'a';
00555 
00556   Array_InsertLast (Array_Test_t, tArray, tmp);
00557   tmp.i = 1;
00558   tmp.c = 'b';
00559   Array_InsertLast (Array_Test_t, tArray, tmp);
00560 
00561   printf ("Entry 0 should be 0.a, is %d.%c\n",
00562       (Array_Fetch (Array_Test_t, tArray, 0)).i,
00563       (Array_Fetch (Array_Test_t, tArray, 0)).c);
00564 
00565   printf ("Entry 1 should be 1.b, is %d.%c\n",
00566       (Array_Fetch (Array_Test_t, tArray, 1)).i,
00567       (Array_Fetch (Array_Test_t, tArray, 1)).c);
00568 
00569 }
00570 
00571 void array_test() { Array_Test(); }