Dogcows Code - chaz/rasterize/blob - array.h

   1
   2 /*
   3  * CS5600 University of Utah
   4  * Charles McGarvey
   5  * mcgarvey@eng.utah.edu
   6  */
   7
   8 #ifndef _ARRAY_H_
   9 #define _ARRAY_H_
  10
  11 #include "assert.h"
  12 #include "common.h"
  13
  14
  15 #define ARRAY_CAPACITY_DEFAULT  (128)
  16 #define ARRAY_CAPACITY_MIN      (4)
  17
  18
  19 /*
  20  * A random-access dynamically-expandable array class.
  21  */
  22 struct array
  23 {
  24     void*   arr;
  25     size_t  cap;
  26     size_t  len;
  27     size_t  siz;
  28 };
  29 typedef struct array array_t;
  30
  31 /*
  32  * Allocate a new array with the element size and initial capacity.
  33  */
  34 array_t* array_alloc2(size_t size, size_t capacity);
  35
  36 /*
  37  * Allocate a new array with the element size.
  38  */
  39 INLINE_MAYBE
  40 array_t* array_alloc(size_t size)
  41 {
  42     return array_alloc2(size, ARRAY_CAPACITY_DEFAULT);
  43 }
  44
  45 #define array_alloc_type(T)        array_alloc(sizeof(T))
  46 #define array_alloc_type2(T, C)    array_alloc2(sizeof(T), C)
  47
  48 /*
  49  * Destroy an array, freeing up its memory.
  50  */
  51 INLINE_MAYBE
  52 void array_destroy(array_t* v)
  53 {
  54     assert(v && v->arr);
  55     mem_free(v->arr);
  56     mem_free(v);
  57 }
  58
  59
  60 /*
  61  * An iterator class for the array.
  62  */
  63 struct array_it
  64 {
  65     const array_t*  arr;
  66     size_t          pos;
  67     int             dir;
  68 };
  69 typedef struct array_it array_it_t;
  70
  71 /*
  72  * Initialize an array iterator.
  73  */
  74 INLINE_MAYBE
  75 void array_it_init(array_it_t* it, const array_t* v, size_t position, int direction)
  76 {
  77     assert(it);
  78     it->arr = v;
  79     it->pos = position;
  80     it->dir = direction;
  81 }
  82
  83
  84 /*
  85  * Index into a random position into the array.
  86  */
  87 INLINE_MAYBE
  88 void* array_index(const array_t* v, size_t i)
  89 {
  90     assert(v && v->arr);
  91     return (char*)v->arr + i * v->siz;
  92 }
  93
  94 /*
  95  * Get the first item in the array.
  96  */
  97 INLINE_MAYBE
  98 void* array_front(const array_t* v)
  99 {
 100     return array_index(v, 0);
 101 }
 102
 103 /*
 104  * Get the last item in the array.
 105  */
 106 INLINE_MAYBE
 107 void* array_back(const array_t* v)
 108 {
 109     return array_index(v, v->len - 1);
 110 }
 111
 112
 113 /*
 114  * Get a forward iterator at the first item in the array.
 115  */
 116 INLINE_MAYBE
 117 array_it_t array_begin(const array_t* v)
 118 {
 119     assert(v && v->arr);
 120     array_it_t it;
 121     array_it_init(&it, v, 0, 1);
 122     return it;
 123 }
 124
 125 /*
 126  * Get a forward iterator after the last item in the array.
 127  */
 128 INLINE_MAYBE
 129 array_it_t array_end(const array_t* v)
 130 {
 131     assert(v && v->arr);
 132     array_it_t it;
 133     array_it_init(&it, v, v->len, 1);
 134     return it;
 135 }
 136
 137 /*
 138  * Get a backward iterator at the last item in the array.
 139  */
 140 INLINE_MAYBE
 141 array_it_t array_rbegin(const array_t* v)
 142 {
 143     assert(v && v->arr);
 144     array_it_t it;
 145     array_it_init(&it, v, v->len - 1, -1);
 146     return it;
 147 }
 148
 149 /*
 150  * Get a backward iterator before the first item in the array.
 151  */
 152 INLINE_MAYBE
 153 array_it_t array_rend(const array_t* v)
 154 {
 155     assert(v && v->arr);
 156     array_it_t it;
 157     array_it_init(&it, v, -1, -1);
 158     return it;
 159 }
 160
 161
 162 /*
 163  * Get the current capacity of the array.  The capacity is how many elements
 164  * could be inserted into the array without reallocating more memory.
 165  */
 166 INLINE_MAYBE
 167 size_t array_capacity(const array_t* v)
 168 {
 169     assert(v && v->arr);
 170     return v->cap;
 171 }
 172
 173 /*
 174  * Make sure there is at least enough memory for a certain number of elements.
 175  */
 176 void array_reserve(array_t* v, size_t s);
 177
 178 /*
 179  * Shrink the amount of memory used to fit what is currently inserted into the
 180  * array and no more.  Of course more memory can be reallocated later.
 181  */
 182 void array_done(array_t* v);
 183
 184
 185 /*
 186  * Get the current number of items in the array.  This is less than or equal
 187  * to the capacity of the array.
 188  */
 189 INLINE_MAYBE
 190 size_t array_size(const array_t* v)
 191 {
 192     assert(v && v->arr);
 193     return v->len;
 194 }
 195
 196 /*
 197  * Get whether or not the array is empty.
 198  */
 199 INLINE_MAYBE
 200 bool array_empty(const array_t* v)
 201 {
 202     return array_size(v) == 0;
 203 }
 204
 205 /*
 206  * Resize the array, either truncating or expanding the size.
 207  */
 208 INLINE_MAYBE
 209 void array_resize(array_t* v, size_t s)
 210 {
 211     array_reserve(v, s);
 212     v->len = s;
 213 }
 214
 215 /*
 216  * Remove all items from the array.
 217  */
 218 INLINE_MAYBE
 219 void array_clear(array_t* v)
 220 {
 221     assert(v && v->arr);
 222     v->len = 0;
 223 }
 224
 225
 226 /*
 227  * Push an item onto the end of the array.
 228  */
 229 INLINE_MAYBE
 230 void array_push(array_t* v, void* e)
 231 {
 232     assert(v && v->arr);
 233     size_t len = v->len + 1;
 234     if (v->cap < len) {
 235         array_reserve(v, len);
 236     }
 237     memcpy(array_index(v, v->len), e, v->siz);
 238     v->len = len;
 239 }
 240
 241
 242 /*
 243  * Pop the item off of the end of the array.  The item is returned, but its
 244  * memory could be overwritten with addition array calls, so it must be copied
 245  * if it needs to be kept.
 246  */
 247 INLINE_MAYBE
 248 void* array_pop(array_t* v)
 249 {
 250     assert(v && v->arr);
 251     return array_index(v, --v->len);
 252 }
 253
 254
 255 /*
 256  * The type of function used when calling elements of the array.
 257  */
 258 typedef void (*array_call_fn_t)(size_t i, void* e);
 259
 260 /*
 261  * Call a function once for each element of the array.
 262  */
 263 void array_call(const array_t* v, array_call_fn_t fn);
 264
 265
 266 /*
 267  * Get the element pointed to by an iterator and increment the iterator.
 268  */
 269 INLINE_MAYBE
 270 void* array_it_next(array_it_t* it)
 271 {
 272     assert(it->arr);
 273     if (it->pos < it->arr->len) {
 274         void* e = array_index(it->arr, it->pos);
 275         it->pos += it->dir;
 276         return e;
 277     }
 278     return NULL;
 279 }
 280
 281 /*
 282  * Decrement the iterator and get the element pointed to by the iterator.
 283  */
 284 INLINE_MAYBE
 285 void* array_it_prev(array_it_t* it)
 286 {
 287     assert(it->arr);
 288     if (it->pos - it->dir < it->arr->len) {
 289         it->pos -= it->dir;
 290         void* e = array_index(it->arr, it->pos);
 291         return e;
 292     }
 293     return NULL;
 294 }
 295
 296
 297 #define DEFINE_ARRAY_TYPE(T) DEFINE_ARRAY_TYPE2(T##_t, T)
 298 #define DEFINE_ARRAY_TYPE2(T, N) \
 299 INLINE_MAYBE array_t* array_##N##_alloc() \
 300 { \
 301     return array_alloc(sizeof(T)); \
 302 } \
 303 INLINE_MAYBE array_t* array_##N##_alloc2(size_t capacity) \
 304 { \
 305     return array_alloc2(sizeof(T), capacity); \
 306 } \
 307 INLINE_MAYBE T* array_##N##_index(const array_t* v, size_t i) \
 308 { \
 309     return (T*)array_index(v, i); \
 310 } \
 311 INLINE_MAYBE T* array_##N##_front(array_t* v) \
 312 { \
 313     return (T*)array_front(v); \
 314 } \
 315 INLINE_MAYBE T* array_##N##_back(array_t* v) \
 316 { \
 317     return (T*)array_back(v); \
 318 } \
 319 INLINE_MAYBE void array_##N##_push(array_t* v, T e) \
 320 { \
 321     assert(v && v->arr); \
 322     size_t len = v->len + 1; \
 323     if (v->cap < len) { \
 324         array_reserve(v, len); \
 325     } \
 326     T* t = array_##N##_back(v); \
 327     *(t + 1) = e; \
 328     /* specialize with assignment copying rather than memcpy */ \
 329     v->len = len; \
 330 } \
 331 INLINE_MAYBE T* array_##N##_pop(array_t* v) \
 332 { \
 333     return (T*)array_pop(v); \
 334 } \
 335 typedef void (*array_##N##_call_fn_t)(size_t i, T* e); \
 336 INLINE_MAYBE void \
 337 array_##N##_call(array_t* v, array_##N##_call_fn_t fn) \
 338 { \
 339     array_call(v, (array_call_fn_t)fn); \
 340 } \
 341 INLINE_MAYBE T* array_it_##N##_next(array_it_t* it) \
 342 { \
 343     return (T*)array_it_next(it); \
 344 } \
 345 INLINE_MAYBE T* array_it_##N##_prev(array_it_t* it) \
 346 { \
 347     return (T*)array_it_prev(it); \
 348 }
 349
 350
 351 #endif // _ARRAY_H_
 352