Azinix

array.h

Go to the documentation of this file.
00001 #ifndef ARRAY_H
00002 #define ARRAY_H
00003 
00004 #ifdef __cplusplus
00005 extern "C" {
00006 #endif
00007 
00008 #include "assert.h"
00009 
00010 /** \file array.h
00011 
00012 \brief Array data structures
00013 
00014 An array_t is a dynamically allocated array.  As elements are inserted
00015 the array is automatically grown to accomodate the new elements.
00016 
00017 The first element of the array is always element 0, and the last
00018 element is element n-1 (if the array contains n elements).
00019 
00020 This array package is intended for generic objects (i.e., an array of
00021 int, array of char, array of double, array of struct foo *, or even
00022 array of struct foo).
00023 
00024 Be careful when creating an array with holes (i.e., when there is no
00025 object stored at a particular position).  An attempt to read such a
00026 position will return a 'zero' object.  It is poor practice to assume
00027 that this value will be properly interpreted as, for example,  (double)
00028 0.0 or (char *) 0.
00029 
00030 In the definitions below, 'typeof' indicates that the argument to the
00031 'function' is a C data type; these 'functions' are actually implemented
00032 as macros.
00033 
00034 */
00035 
00036 
00037 /** \brief Array structure */
00038 
00039 typedef struct Array_t
00040 {
00041   char *space;
00042   int num;          /* number of array elements.            */
00043   int n_size;           /* size of 'data' array (in objects)    */
00044   int obj_size;         /* size of each array object.           */
00045   int index;            /* combined index and locking flag.     */
00046   int tmpInteger;       /* use to avoid declaring locally.      */
00047 } Array_t;
00048 
00049 typedef Array_t array_t;
00050 
00051 // exported functions, live in array.c
00052 
00053 extern void Array_Test ( );
00054 
00055 extern array_t *Array_DoAlloc (int, int);
00056 
00057 static inline array_t *array_do_alloc( int a, int b ) {
00058   return Array_DoAlloc( a, b );
00059 }
00060 
00061 
00062 extern Array_t *Array_Dup (Array_t *);
00063 static inline array_t *array_dup( array_t * a ) {
00064   return Array_Dup( a );
00065 }
00066 
00067 extern Array_t *Array_Join (Array_t *, Array_t *);
00068 static inline array_t *array_join (array_t * a, array_t * b) {
00069   return Array_Join( a, b );
00070 }
00071 
00072 extern void Array_Free (Array_t *);
00073 static inline void array_free (array_t * a) {
00074   return Array_Free ( a );
00075 }
00076 
00077 extern void Array_Reset (Array_t *);
00078 static inline void array_reset (array_t * a) {
00079   return Array_Reset ( a );
00080 }
00081 
00082 extern int Array_Append (array_t *, array_t *);
00083 static inline int array_append (array_t * a, array_t * b) {
00084   return Array_Append ( a, b ); 
00085 }
00086 
00087 extern void Array_Sort (array_t *, int (*)());
00088 static inline void array_sort (array_t *a , int (*b)() ) {
00089   return Array_Sort ( a, b );
00090 }
00091 
00092 extern void Array_Uniq (array_t *, int (*)(), void (*)());
00093 static inline void array_uniq (array_t * a, int (*b)() , void (*c)() ) {
00094   return Array_Uniq ( a, b, c );
00095 }
00096 
00097 extern int Array_Abort (array_t *, int);
00098 static inline int array_abort (array_t * a, int b) {
00099   return Array_Abort (a, b );
00100 }
00101 
00102 extern int Array_Resize (array_t *, int);
00103 static inline int array_resize (array_t * a, int b) {
00104   return Array_Resize ( a ,  b );
00105 }
00106 
00107 extern char *Array_DoData (array_t *);
00108 static inline char *array_do_data (array_t * a) {
00109   return Array_DoData ( a );
00110 }
00111 
00112 extern void Array_Merge (array_t *, array_t *, array_t *, array_t *);
00113 static inline void array_merge (array_t *a, array_t *b, array_t *c, array_t * d) {
00114   return Array_Merge ( a, b, c, d ); 
00115 }
00116 
00117 
00118 // Return value when memory allocation fails 
00119 #define ARRAY_OUT_OF_MEM -10000
00120 
00121 
00122 /** \brief Insert an element into an array 
00123 
00124    Perform basic checks: object being inserted is right size, index is legal
00125 
00126 */
00127 
00128 static inline void
00129 Array_InsertInternal (int typeSize, array_t * a, int i, void *datum)
00130 {
00131 
00132   // we're passing in the failure message using the comma operator
00133   // assert is preferred since it will be compiled away with optimization flags set
00134   if( a->obj_size != typeSize) {
00135     printf("Insertion into array with wrong size\n");
00136     assert(0);
00137   }
00138 
00139   a->index = i;
00140   if (i < 0)
00141     {
00142       printf ("Insertion into array before entry 0\n");
00143       assert (0);
00144     }
00145 
00146   if (i >= a->n_size)
00147     {
00148       a->tmpInteger = array_resize (a, i + 1);
00149       if (a->tmpInteger == ARRAY_OUT_OF_MEM)
00150     {
00151       printf ("Out of memory resizing array, inserting index %d,"
00152           "num entries was %d\n", i, a->n_size);
00153       assert (0);
00154     }
00155     }
00156 
00157   if (typeSize == 4)
00158     {
00159       *(u_int32_t *) (a->space + i * a->obj_size) = *(u_int32_t *) datum;
00160     }
00161   else if (typeSize == 1)
00162     {
00163       *(u_int8_t *) (a->space + i * a->obj_size) = *(u_int8_t *) datum;
00164     }
00165   else
00166     {
00167       memcpy ((a->space + i * a->obj_size), datum, typeSize);
00168     }
00169   if (a->index >= a->num)
00170     {
00171       a->num = a->index + 1;
00172     }
00173   a->index = -(int) typeSize;
00174 }
00175 
00176 
00177 /** \brief  Returns the number of elements stored in the array.  If this is
00178 `n', then the last element of the array is at position `n' - 1.
00179 */
00180 
00181 static inline int
00182 Array_N (array_t * array)
00183 {
00184   return array->num;
00185 }
00186 
00187 static inline int array_n( array_t *a ) { return Array_N( a ) ; }
00188 
00189 
00190 static inline void *
00191 Array_FetchInternal (array_t * a, int index, int decrCount)
00192 {
00193   void *result;
00194 
00195   if (index >= a->num)
00196     {
00197       printf ("indexing array outside limit\n");
00198       assert (0);
00199     }
00200 
00201   result = (a)->space + (index * a->obj_size);
00202   if (decrCount)
00203     {
00204       // used only by array_delete_last
00205       assert (index == a->num - 1);
00206       a->num--;
00207     }
00208   return result;
00209 }
00210 
00211 /** \brief  Reduce the number of entries by 1
00212 
00213 Does not recover space.
00214 */
00215 
00216 static inline void
00217 Array_Decrement (array_t * a)
00218 {
00219   a->num--;
00220 }
00221 
00222 static inline void array_decrement( array_t * a ) { return Array_Decrement( a ); }
00223 
00224 /** \brief Insert a new element into an array at the given position.  
00225 
00226 The array is dynamically extended if necessary to accomodate the
00227 new item.  It is a serious error if sizeof(type) is not the
00228 same as the type used when the array was allocated.  It is also
00229 a serious error for 'position' to be less than zero.
00230 */
00231 
00232 #define Array_Insert( type, a, i, datum )       \
00233   { type _array_datum_dup = datum; Array_InsertInternal( sizeof( type ), (a), (i) , & _array_datum_dup );}
00234 
00235 #define array_insert( type, a, i, datum )  Array_Insert( type, a, i, datum ) 
00236 
00237 /** \brief Allocate and initialize an array of objects of type `type'.
00238 
00239         Polymorphic arrays are okay as long as the type of largest
00240         object is used for initialization.  The array can initially
00241         hold `number' objects.  Typical use sets `number' to 0, and
00242         allows the array to grow dynamically.
00243 
00244   */
00245 
00246 #define Array_Alloc(type, number)       \
00247     Array_DoAlloc( sizeof(type), number)
00248 
00249 #define array_alloc( type, number ) Array_Alloc( type, number )
00250 
00251 /** 
00252    \brief Insert a new element at the end of the array.  Equivalent to:
00253 
00254    <pre>array_insert(type, array, array_n(array), object)</pre>
00255 
00256   */
00257 
00258 #define Array_InsertLast(type, array, datum)    \
00259     array_insert(type, array, (array)->num, datum)
00260 
00261 #define array_insert_last(type, array, datum) Array_InsertLast(type, array, datum)
00262 
00263 /** \brief Fetch an element from an array.  
00264 
00265 A runtime error occurs on an
00266 attempt to reference outside the bounds of the array.  There is
00267 no type-checking that the value at the given position is
00268 actually of the type used when dereferencing the array.
00269 */
00270 
00271 
00272 #define Array_Fetch( type, a, i )       \
00273         ( * ( ( type * ) Array_FetchInternal( a, i, 0 ) ) )
00274 
00275 #define array_fetch( type, a, i ) \
00276     Array_Fetch( type, a, i ) 
00277 
00278 /** \brief  Fetch a pointer to an element in an array 
00279 */
00280 
00281 #define Array_FetchPtr(type, a, i)                       \
00282      ( ( type * ) Array_FetchInternal( a, i, 0 ) )
00283 
00284 #define array_fetch_p(type, a, i) Array_FetchPtr(type, a, i)                       \
00285 
00286 /** \brief  Fetch the last element from an array.  
00287 
00288 A runtime error occurs
00289 if there are no elements in the array.  There is no type-checking
00290 that the value at the given position is actually of the type used
00291 when dereferencing the array.  Equivalent to:
00292 
00293 <pre>array_fetch(type, array, array_n(array))</pre>
00294 */
00295 
00296 
00297 #define Array_FetchLast(type, array)        \
00298         Array_Fetch(type, array, ((array)->num)-1)
00299 
00300 #define array_fetch_last(type, array ) \
00301     Array_FetchLast(type, array)        \
00302 
00303 
00304 /**
00305   * \brief Fetch the last element of the array and delete it from the array.
00306   */
00307 
00308 #define Array_DeleteLast( type, array )     \
00309      ( * ( ( type * ) Array_FetchInternal( array, ((array)->num)-1, 1 ) ) )
00310 
00311 #define array_delete_last( type, array )    \
00312     Array_DeleteLast( type, array )
00313 
00314 /** \brief  Returns a normal `C' array from an array_t structure.  
00315 
00316 This is sometimes necessary when dealing with functions which do not
00317 understand the array_t data type.  A copy of the array is
00318 returned, and it is the users responsibility to free it.  array_n()
00319 can be used to get the number of elements in the array.
00320 */
00321 
00322 #define Array_Data(type, array)         \
00323     (type *) Array_DoData(array)
00324 
00325 // conflicts with qt
00326 // #define array_data( type, array ) Array_Data( type, array )
00327 
00328 
00329 /** \brief Macro to iterate over the items of an array.
00330 
00331 <ul>
00332 <li>  <code>type</code>,  type of object stored in array 
00333 <li>  <code>array</code>, array to iterate 
00334 <li>  <code>i</code>,     int, local variable for iterator 
00335 <li>  <code>data</code>   object of type 
00336 </ul>
00337 */
00338 
00339 
00340 #define arrayForEachItem(                                      \
00341   type,  /* type of object stored in array */                  \
00342   array, /* array to iterate */                                \
00343   i,     /* int, local variable for iterator */                \
00344   data   /* object of type */                                  \
00345 )                                                              \
00346   for((i) = 0;                                                 \
00347       (((i) < array_n((array)))                                \
00348        && (((data) = array_fetch(type, (array), (i))), 1));    \
00349       (i)++)
00350 
00351 // orignial code 
00352 
00353 #define array_insert_old(type, a, i, datum)         \
00354     (  -(a)->index != sizeof(type) ? array_abort((a),4) : 0,\
00355         (a)->index = (i),\
00356         (a)->index < 0 ? array_abort((a),0) : 0,\
00357         (a)->index >= (a)->n_size ?\
00358     a->tmpInteger = array_resize(a, (a)->index + 1) : 0,\
00359         a->tmpInteger != ARRAY_OUT_OF_MEM ?\
00360         *((type *) ((a)->space + (a)->index * (a)->obj_size)) = datum : datum,\
00361         a->tmpInteger != ARRAY_OUT_OF_MEM ?\
00362         ((a)->index >= (a)->num ? (a)->num = (a)->index + 1 : 0) : 0,\
00363         a->tmpInteger != ARRAY_OUT_OF_MEM ?\
00364         ((a)->index = -(int)sizeof(type)) : ARRAY_OUT_OF_MEM )
00365 
00366 #define array_fetch_old(type, a, i)         \
00367     (a->tmpInteger = (i),               \
00368       (a->tmpInteger >= (a)->num) ? array_abort((a),1) : 0,\
00369       *((type *) ((a)->space + a->tmpInteger * (a)->obj_size)))
00370 
00371 #ifdef __cplusplus
00372 }
00373 #endif
00374 
00375 #endif // ARRAY_H