little_helpers/tikz/sketch-0.2.161/dynarray.h

   1 /* dynarray.h
   2    Copyright (C) 2005,2006,2007,2008 Eugene K. Ressler, Jr.
   3
   4 This file is part of Sketch, a small, simple system for making
   5 3d drawings with LaTeX and the PSTricks or TikZ package.
   6
   7 Sketch is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 Sketch is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Sketch; see the file COPYING.txt.  If not, see
  19 http://www.gnu.org/copyleft */
  20
  21 #ifndef __DYNARRAY
  22 #define __DYNARRAY
  23
  24 /*
  25   dyanamic arrays in C (through preprocessor abuse)
  26
  27   parameters:
  28
  29   ELEMENT_TYPE - type of elements of dynamic array to be declared
  30   NAME - base name used in constructor, destructor, and accessor functions
  31   ELTS - field name of C array of elements inside the dynamic array struct
  32   N_ELTS - field name for fill pointer, current number of valid elements
  33
  34   structure:
  35
  36   a dynamic array is a struct with the following fields:
  37
  38     current_size - the number of array elements currently allocated to the array
  39
  40     N_ELTS - a "fill pointer" that tracks the number of elements that have been
  41       pushed onto the array so far; push()ing grows the array automatically
  42
  43     ELTS - a pointer to ELEMENT_TYPE with specified name; these are the
  44       array elements
  45
  46   an example
  47
  48     // ---- in foo.h ----
  49
  50   // we need a dynamic array of these things
  51     typedef struct foo_t {
  52       char *name;
  53       int count;
  54     } FOO;
  55
  56     // create the typedef for the type FOO_ARRAY
  57     TYPEDEF_DYNAMIC_ARRAY(FOO_ARRAY, FOO, foo_list, val, n_vals) // no semicolons!
  58
  59     // do the prototypes for the constructor, destructor, and accessor functions
  60     DECLARE_DYNAMIC_ARRAY_PROTOS(FOO_ARRAY, FOO, foo_list, val, n_vals)
  61
  62     // ---- in foo.c ----
  63
  64   // create the bodies for the constructor, destructor, and accessor functions
  65     DECLARE_DYNAMIC_ARRAY_FUNCS(FOO_ARRAY, FOO, foo_list, val, n_vals)
  66
  67     // use all the new stuff!
  68     void do_stuff_with_foos(void)
  69     {
  70       int i;
  71       char buf[100];
  72       FOO_ARRAY list[1];  // or FOO_ARRAY list; but then we're forever &'ing
  73       FOO_ARRAY copy[1];
  74
  75       init_foo_list(list);  // do this JUST ONCE right after declaration
  76       init_foo_list(copy);   // (not necessary for static/global decls)
  77
  78       setup_foo_list(list, 10);  // allow for 10 elements
  79
  80       // read some data and push it on the list tail
  81       while (scanf("%d %s", &i, buf) == 2) {
  82         // get pointer to new (empty) element at the end of array
  83         FOO *p = pushed_foo_list_val(list);
  84         // fill in field values
  85         p->name = strdup(buf);
  86         p->count = i;
  87       }
  88
  89       // shows unsafe access to elements
  90       printf("forward listing:\n");
  91       for (i = 0; i < list->n_val; i++)
  92         printf("name=%s count=%d (%d)\n",
  93           list->val[i].name,                  // fast unsafe access
  94           foo_list_val_ptr(list, i)->count,   // slower safe pointer access
  95           foo_list_val(list, i).count);       // copying access
  96
  97       copy_foo_list_filled(copy, list);       // copies only filled elements
  98
  99       // print in reverse order by popping from tail
 100       printf("backward listing:\n");
 101       while (copy->n_val > 0) {
 102         FOO *p = popped_foo_list_val(copy);
 103         printf("name=%s count=%d\n", p->name, p->count);
 104       }
 105
 106       // clear out all the allocated storage for the ilst
 107       clear_foo_list(list);
 108       clear_foo_list(copy);
 109     }
 110
 111   notes on the example:
 112
 113   * NAME (foo_list) must be unique in the namespace to avoid collisions
 114
 115   * ELTS need not be unique
 116
 117   * the declaration FOO_ARRAY list[1]; is an idiom that avoids lots of &'s
 118     in the rest of the code;  feel free to use FOO_ARRAY list; if you like &'s
 119
 120   * init_foo_list() is not needed on static or global declarations because
 121     it merely sets things to zero
 122
 123   * the call pushed_foo_list_val() grows the list automatically to accomodate
 124     more than 10 elements; arrays grow (never shrink) until they are clear()ed;
 125     the fill pointer is foo_list->n_val
 126
 127   * safe copying access is good for reading small elements; pointer access is
 128     for writing elements and for reading within large struct elements
 129
 130   * copy_foo_list_filled() copies only n_val elements after ensuring there is
 131     enough space in the destination; copy_foo_list() does the same thing
 132     for all current_size elements; it ignores the fill pointer except to copy
 133     its value
 134
 135   macros:
 136
 137   TYPEDEF_DYNAMIC_ARRAY(ELEMENT_TYPE, NAME, ELTS) - declare a typedef
 138   for a new dyamic array type with the given attributes
 139
 140 */
 141
 142 #include <string.h>
 143 #include "error.h"
 144
 145 #define DYNAMIC_ARRAY_FIELDS(ELEMENT_TYPE, ELTS, N_ELTS)  \
 146   int current_size, N_ELTS;  \
 147   ELEMENT_TYPE *ELTS
 148
 149 #define DECLARE_DYNAMIC_ARRAY_PROTOS(ARRAY_TYPE, ELEMENT_TYPE, NAME, ELTS, N_ELTS)  \
 150 void init_##NAME(ARRAY_TYPE *a);  \
 151 ARRAY_TYPE *new_##NAME(int size);  \
 152 void delete_##NAME(ARRAY_TYPE *a); \
 153 void setup_##NAME(ARRAY_TYPE *a, int size);  \
 154 void extend_##NAME(ARRAY_TYPE *a, int new_size);  \
 155 ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a);  \
 156 ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a);  \
 157 void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
 158 void copy_filled_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
 159 void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
 160 void clear_##NAME(ARRAY_TYPE *a);  \
 161 ELEMENT_TYPE *NAME##_##ELTS##_ptr(ARRAY_TYPE *a, int i);  \
 162 ELEMENT_TYPE NAME##_##ELTS(ARRAY_TYPE *a, int i);
 163
 164 // use this for OTHER_INIT parameter when there is none
 165 #define NO_OTHER_INIT /**/
 166 #define DECLARE_DYNAMIC_ARRAY_FUNCS(ARRAY_TYPE, ELEMENT_TYPE, NAME, ELTS, N_ELTS, OTHER_INIT)  \
 167   \
 168 /* initialize raw array record */  \
 169 void init_##NAME(ARRAY_TYPE *a)  \
 170 {  \
 171   a->current_size = a->N_ELTS = 0;  \
 172   a->ELTS = 0;  \
 173   OTHER_INIT  \
 174 }  \
 175   \
 176 /* allocate an array dynamically and initialize it */  \
 177 ARRAY_TYPE *new_##NAME(int size)  \
 178 {  \
 179   ARRAY_TYPE *a = safe_malloc(sizeof(ARRAY_TYPE));  \
 180   init_##NAME(a);  \
 181   setup_##NAME(a, size);  \
 182   return a;  \
 183 }  \
 184  \
 185 void delete_##NAME(ARRAY_TYPE *a) \
 186 { \
 187   if (!a) return; \
 188   clear_##NAME(a); \
 189   safe_free(a); \
 190 } \
 191 /* set up (or increase size of existing) initialized array with given size */ \
 192 void setup_##NAME(ARRAY_TYPE *a, int size) \
 193 { \
 194   if (size > a->current_size) { \
 195     a->ELTS = safe_realloc(a->ELTS, size * sizeof(ELEMENT_TYPE)); \
 196     a->current_size = size; \
 197   } \
 198 } \
 199  \
 200 void extend_##NAME(ARRAY_TYPE *a, int new_size) \
 201 { \
 202   int actual_new_size = a->current_size; \
 203   if (actual_new_size <= 0) actual_new_size = 1; \
 204   while (actual_new_size < new_size) \
 205     actual_new_size *= 2; \
 206   setup_##NAME(a, actual_new_size); \
 207 } \
 208 ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a) \
 209 { \
 210   extend_##NAME(a, a->N_ELTS + 1); \
 211   return &a->ELTS[a->N_ELTS++]; \
 212 } \
 213  \
 214 ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a) \
 215 { \
 216   if (a->N_ELTS <= 0) \
 217     die(no_line, "popped_" #NAME "_" #ELTS ": no elements to pop"); \
 218   return &a->ELTS[--a->N_ELTS]; \
 219 } \
 220  \
 221 void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 222 { \
 223   extend_##NAME(dst, src->current_size); \
 224   dst->N_ELTS = src->N_ELTS; \
 225   memcpy(dst->ELTS, src->ELTS, src->current_size * sizeof(ELEMENT_TYPE)); \
 226 } \
 227  \
 228 void copy_##NAME##_filled(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 229 { \
 230   extend_##NAME(dst, src->N_ELTS); \
 231   dst->N_ELTS = src->N_ELTS; \
 232   memcpy(dst->ELTS, src->ELTS, src->N_ELTS * sizeof(ELEMENT_TYPE)); \
 233 } \
 234  \
 235 void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 236 { \
 237   int i, j; \
 238   extend_##NAME(dst, src->N_ELTS); \
 239   dst->N_ELTS = src->N_ELTS; \
 240   for (i = 0, j = dst->N_ELTS - 1; j >= 0; i++, j--) \
 241     dst->ELTS[j] = src->ELTS[i]; \
 242 } \
 243  \
 244 void clear_##NAME(ARRAY_TYPE *a) \
 245 { \
 246   safe_free(a->ELTS); \
 247   init_##NAME(a); \
 248 } \
 249  \
 250 ELEMENT_TYPE *NAME##_##ELTS##_ptr(ARRAY_TYPE *a, int i) \
 251 { \
 252   if (i < 0 || i >= a->N_ELTS) \
 253     die(no_line, #NAME "_elt_ptr: " #ELEMENT_TYPE "_ARRAY reference [%d] out of bounds", i); \
 254   return &a->ELTS[i]; \
 255 } \
 256  \
 257 ELEMENT_TYPE NAME##_##ELTS(ARRAY_TYPE *a, int i) \
 258 { \
 259   if (i < 0 || i >= a->N_ELTS) \
 260     die(no_line, #NAME "_elt: " #ELEMENT_TYPE "_ARRAY reference [%d] out of bounds", i); \
 261   return a->ELTS[i]; \
 262 }
 263 // ---- dyanmic arrays of elements that are static one-dimensional arrays ------
 264 // this is meant to be identical to the above except to compensate for C's strange
 265 // quirks regarding arrays of arrays
 266 #define DYNAMIC_2D_ARRAY_FIELDS(ELEMENT_TYPE, ELTS, N_ELTS) \
 267   int current_size, N_ELTS; \
 268   ELEMENT_TYPE *ELTS
 269 #define DECLARE_DYNAMIC_2D_ARRAY_PROTOS(ARRAY_TYPE, ELEMENT_TYPE, SUB_ELEMENT_TYPE, NAME, ELTS, N_ELTS) \
 270 void init_##NAME(ARRAY_TYPE *a); \
 271 ARRAY_TYPE *new_##NAME(int size); \
 272 void delete_##NAME(ARRAY_TYPE *a); \
 273 void setup_##NAME(ARRAY_TYPE *a, int size); \
 274 void extend_##NAME(ARRAY_TYPE *a, int new_size); \
 275 SUB_ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a); \
 276 SUB_ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a); \
 277 void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
 278 void copy_##NAME##_filled(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
 279 void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
 280 void clear_##NAME(ARRAY_TYPE *a); \
 281 SUB_ELEMENT_TYPE *NAME##_##ELTS(ARRAY_TYPE *a, int i); \
 282 SUB_ELEMENT_TYPE NAME##_##ELTS##_elt(ARRAY_TYPE *a, int i, int j);
 283 #define DECLARE_DYNAMIC_2D_ARRAY_FUNCS(ARRAY_TYPE, ELEMENT_TYPE, SUB_ELEMENT_TYPE, NAME, ELTS, N_ELTS, OTHER_INIT) \
 284  \
 285 /* initialize raw array record */ \
 286 void init_##NAME(ARRAY_TYPE *a) \
 287 { \
 288   a->current_size = a->N_ELTS = 0; \
 289   a->ELTS = 0; \
 290   OTHER_INIT \
 291 } \
 292  \
 293 /* allocate an array dynamically and initialize it */ \
 294 ARRAY_TYPE *new_##NAME(int size) \
 295 { \
 296   ARRAY_TYPE *a = safe_malloc(sizeof(ARRAY_TYPE)); \
 297   init_##NAME(a); \
 298   setup_##NAME(a, size); \
 299   return a; \
 300 } \
 301  \
 302 void delete_##NAME(ARRAY_TYPE *a) \
 303 { \
 304   if (!a) return; \
 305   clear_##NAME(a); \
 306   safe_free(a); \
 307 } \
 308  \
 309 /* set up (or increase size of existing) initialized array with given size */ \
 310 void setup_##NAME(ARRAY_TYPE *a, int size) \
 311 { \
 312   if (size > a->current_size) { \
 313     a->ELTS = safe_realloc(a->ELTS, size * sizeof(ELEMENT_TYPE)); \
 314     a->current_size = size; \
 315   } \
 316 } \
 317  \
 318 void extend_##NAME(ARRAY_TYPE *a, int new_size) \
 319 { \
 320   int actual_new_size = a->current_size; \
 321   if (actual_new_size <= 0) actual_new_size = 1; \
 322   while (actual_new_size < new_size) \
 323     actual_new_size *= 2; \
 324   setup_##NAME(a, actual_new_size); \
 325 } \
 326  \
 327 SUB_ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a) \
 328 { \
 329   extend_##NAME(a, a->N_ELTS + 1); \
 330   return a->ELTS[a->N_ELTS++]; \
 331 } \
 332  \
 333 SUB_ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a) \
 334 { \
 335   if (a->N_ELTS <= 0) \
 336     die(no_line, "popped_" #NAME "_" #ELTS ": no elements to pop"); \
 337   return a->ELTS[--a->N_ELTS]; \
 338 } \
 339  \
 340 void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 341 { \
 342   extend_##NAME(dst, src->current_size); \
 343   dst->N_ELTS = src->N_ELTS; \
 344   memcpy(dst->ELTS, src->ELTS, src->current_size * sizeof(ELEMENT_TYPE)); \
 345 } \
 346  \
 347 void copy_filled_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 348 { \
 349   extend_##NAME(dst, src->N_ELTS); \
 350   dst->N_ELTS = src->N_ELTS; \
 351   memcpy(dst->ELTS, src->ELTS, src->N_ELTS * sizeof(ELEMENT_TYPE)); \
 352 } \
 353  \
 354 void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
 355 { \
 356   int i, j; \
 357   extend_##NAME(dst, src->N_ELTS); \
 358   dst->N_ELTS = src->N_ELTS; \
 359   for (i = 0, j = dst->N_ELTS - 1; j >= 0; i++, j--) \
 360     memcpy(dst->ELTS[j], src->ELTS[i], sizeof dst->ELTS[0]); \
 361 } \
 362  \
 363 void clear_##NAME(ARRAY_TYPE *a) \
 364 { \
 365   safe_free(a->ELTS); \
 366   init_##NAME(a); \
 367 } \
 368  \
 369 SUB_ELEMENT_TYPE *NAME##_##ELTS(ARRAY_TYPE *a, int i) \
 370 { \
 371   if (i < 0 || i > a->N_ELTS) \
 372     die(no_line, #NAME "_elt: " #ELEMENT_TYPE "_ARRAY reference out of bounds"); \
 373   return a->ELTS[i]; \
 374 } \
 375  \
 376 SUB_ELEMENT_TYPE NAME##_##ELTS##_elt(ARRAY_TYPE *a, int i, int j) \
 377 { \
 378   if (i < 0 || i >= a->N_ELTS || j < 0 || j >= sizeof(ELEMENT_TYPE) / sizeof(SUB_ELEMENT_TYPE)) \
 379     die(no_line, #NAME "_subelt: " #ELEMENT_TYPE "_ARRAY reference [%d][%d] out of bounds", i, j); \
 380   return a->ELTS[i][j]; \
 381 }
 382 #endif