summaryrefslogtreecommitdiff
path: root/graphics/sketch/dynarray.h
blob: 29bfe26fc3155ff0515054b8ff037f50a155c69a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
/* dynarray.h
   Copyright (C) 2005,2006,2007 Eugene K. Ressler, Jr.

This file is part of Sketch, a small, simple system for making 
3d drawings with LaTeX and the PSTricks or TikZ package.

Sketch is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

Sketch is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Sketch; see the file COPYING.txt.  If not, see
http://www.gnu.org/copyleft */

#ifndef __DYNARRAY
#define __DYNARRAY

/* 
  dyanamic arrays in C (through preprocessor abuse)

  parameters:

  ELEMENT_TYPE - type of elements of dynamic array to be declared
  NAME - base name used in constructor, destructor, and accessor functions
  ELTS - field name of C array of elements inside the dynamic array struct
  N_ELTS - field name for fill pointer, current number of valid elements

  structure:

  a dynamic array is a struct with the following fields:

    current_size - the number of array elements currently allocated to the array

    N_ELTS - a "fill pointer" that tracks the number of elements that have been
      pushed onto the array so far; push()ing grows the array automatically

    ELTS - a pointer to ELEMENT_TYPE with specified name; these are the 
      array elements

  an example

    // ---- in foo.h ----

  // we need a dynamic array of these things
    typedef struct foo_t {
      char *name;
      int count;
    } FOO;

    // create the typedef for the type FOO_ARRAY
    TYPEDEF_DYNAMIC_ARRAY(FOO_ARRAY, FOO, foo_list, val, n_vals) // no semicolons!

    // do the prototypes for the constructor, destructor, and accessor functions
    DECLARE_DYNAMIC_ARRAY_PROTOS(FOO_ARRAY, FOO, foo_list, val, n_vals)

    // ---- in foo.c ----

  // create the bodies for the constructor, destructor, and accessor functions
    DECLARE_DYNAMIC_ARRAY_FUNCS(FOO_ARRAY, FOO, foo_list, val, n_vals)

    // use all the new stuff!
    void do_stuff_with_foos(void)
    {
      int i;
      char buf[100];
      FOO_ARRAY list[1];  // or FOO_ARRAY list; but then we're forever &'ing
      FOO_ARRAY copy[1];
  
      init_foo_list(list);  // do this JUST ONCE right after declaration
      init_foo_list(copy);   // (not necessary for static/global decls)

      setup_foo_list(list, 10);  // allow for 10 elements

      // read some data and push it on the list tail
      while (scanf("%d %s", &i, buf) == 2) {
        // get pointer to new (empty) element at the end of array
        FOO *p = pushed_foo_list_val(list);
        // fill in field values
        p->name = strdup(buf);
        p->count = i;
      }

      // shows unsafe access to elements
      printf("forward listing:\n");
      for (i = 0; i < list->n_val; i++)
        printf("name=%s count=%d (%d)\n", 
          list->val[i].name,                  // fast unsafe access
          foo_list_val_ptr(list, i)->count,   // slower safe pointer access
          foo_list_val(list, i).count);       // copying access

      copy_foo_list_filled(copy, list);       // copies only filled elements

      // print in reverse order by popping from tail
      printf("backward listing:\n");
      while (copy->n_val > 0) {
        FOO *p = popped_foo_list_val(copy);
        printf("name=%s count=%d\n", p->name, p->count);
      }

      // clear out all the allocated storage for the ilst
      clear_foo_list(list);
      clear_foo_list(copy);
    }

  notes on the example:

  * NAME (foo_list) must be unique in the namespace to avoid collisions

  * ELTS need not be unique

  * the declaration FOO_ARRAY list[1]; is an idiom that avoids lots of &'s
    in the rest of the code;  feel free to use FOO_ARRAY list; if you like &'s

  * init_foo_list() is not needed on static or global declarations because
    it merely sets things to zero

  * the call pushed_foo_list_val() grows the list automatically to accomodate
    more than 10 elements; arrays grow (never shrink) until they are clear()ed;
    the fill pointer is foo_list->n_val

  * safe copying access is good for reading small elements; pointer access is
    for writing elements and for reading within large struct elements

  * copy_foo_list_filled() copies only n_val elements after ensuring there is
    enough space in the destination; copy_foo_list() does the same thing
    for all current_size elements; it ignores the fill pointer except to copy 
    its value
  
  macros:

  TYPEDEF_DYNAMIC_ARRAY(ELEMENT_TYPE, NAME, ELTS) - declare a typedef
  for a new dyamic array type with the given attributes

*/

#include <string.h>
#include "error.h"

#define DYNAMIC_ARRAY_FIELDS(ELEMENT_TYPE, ELTS, N_ELTS)  \
  int current_size, N_ELTS;  \
  ELEMENT_TYPE *ELTS

#define DECLARE_DYNAMIC_ARRAY_PROTOS(ARRAY_TYPE, ELEMENT_TYPE, NAME, ELTS, N_ELTS)  \
void init_##NAME(ARRAY_TYPE *a);  \
ARRAY_TYPE *new_##NAME(int size);  \
void delete_##NAME(ARRAY_TYPE *a); \
void setup_##NAME(ARRAY_TYPE *a, int size);  \
void extend_##NAME(ARRAY_TYPE *a, int new_size);  \
ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a);  \
ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a);  \
void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
void copy_filled_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src);  \
void clear_##NAME(ARRAY_TYPE *a);  \
ELEMENT_TYPE *NAME##_##ELTS##_ptr(ARRAY_TYPE *a, int i);  \
ELEMENT_TYPE NAME##_##ELTS(ARRAY_TYPE *a, int i);

// use this for OTHER_INIT parameter when there is none
#define NO_OTHER_INIT /**/
#define DECLARE_DYNAMIC_ARRAY_FUNCS(ARRAY_TYPE, ELEMENT_TYPE, NAME, ELTS, N_ELTS, OTHER_INIT)  \
  \
/* initialize raw array record */  \
void init_##NAME(ARRAY_TYPE *a)  \
{  \
  a->current_size = a->N_ELTS = 0;  \
  a->ELTS = 0;  \
  OTHER_INIT  \
}  \
  \
/* allocate an array dynamically and initialize it */  \
ARRAY_TYPE *new_##NAME(int size)  \
{  \
  ARRAY_TYPE *a = safe_malloc(sizeof(ARRAY_TYPE));  \
  init_##NAME(a);  \
  setup_##NAME(a, size);  \
  return a;  \
}  \
 \
void delete_##NAME(ARRAY_TYPE *a) \
{ \
  if (!a) return; \
  clear_##NAME(a); \
  safe_free(a); \
} \
/* set up (or increase size of existing) initialized array with given size */ \
void setup_##NAME(ARRAY_TYPE *a, int size) \
{ \
  if (size > a->current_size) { \
    a->ELTS = safe_realloc(a->ELTS, size * sizeof(ELEMENT_TYPE)); \
    a->current_size = size; \
  } \
} \
 \
void extend_##NAME(ARRAY_TYPE *a, int new_size) \
{ \
  int actual_new_size = a->current_size; \
  if (actual_new_size <= 0) actual_new_size = 1; \
  while (actual_new_size < new_size) \
    actual_new_size *= 2; \
  setup_##NAME(a, actual_new_size); \
} \
ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a) \
{ \
  extend_##NAME(a, a->N_ELTS + 1); \
  return &a->ELTS[a->N_ELTS++]; \
} \
 \
ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a) \
{ \
  if (a->N_ELTS <= 0) \
    die(no_line, "popped_" #NAME "_" #ELTS ": no elements to pop"); \
  return &a->ELTS[--a->N_ELTS]; \
} \
 \
void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  extend_##NAME(dst, src->current_size); \
  dst->N_ELTS = src->N_ELTS; \
  memcpy(dst->ELTS, src->ELTS, src->current_size * sizeof(ELEMENT_TYPE)); \
} \
 \
void copy_##NAME##_filled(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  extend_##NAME(dst, src->N_ELTS); \
  dst->N_ELTS = src->N_ELTS; \
  memcpy(dst->ELTS, src->ELTS, src->N_ELTS * sizeof(ELEMENT_TYPE)); \
} \
 \
void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  int i, j; \
  extend_##NAME(dst, src->N_ELTS); \
  dst->N_ELTS = src->N_ELTS; \
  for (i = 0, j = dst->N_ELTS - 1; j >= 0; i++, j--) \
    dst->ELTS[j] = src->ELTS[i]; \
} \
 \
void clear_##NAME(ARRAY_TYPE *a) \
{ \
  safe_free(a->ELTS); \
  init_##NAME(a); \
} \
 \
ELEMENT_TYPE *NAME##_##ELTS##_ptr(ARRAY_TYPE *a, int i) \
{ \
  if (i < 0 || i >= a->N_ELTS) \
    die(no_line, #NAME "_elt_ptr: " #ELEMENT_TYPE "_ARRAY reference [%d] out of bounds", i); \
  return &a->ELTS[i]; \
} \
 \
ELEMENT_TYPE NAME##_##ELTS(ARRAY_TYPE *a, int i) \
{ \
  if (i < 0 || i >= a->N_ELTS) \
    die(no_line, #NAME "_elt: " #ELEMENT_TYPE "_ARRAY reference [%d] out of bounds", i); \
  return a->ELTS[i]; \
}
// ---- dyanmic arrays of elements that are static one-dimensional arrays ------
// this is meant to be identical to the above except to compensate for C's strange
// quirks regarding arrays of arrays
#define DYNAMIC_2D_ARRAY_FIELDS(ELEMENT_TYPE, ELTS, N_ELTS) \
  int current_size, N_ELTS; \
  ELEMENT_TYPE *ELTS
#define DECLARE_DYNAMIC_2D_ARRAY_PROTOS(ARRAY_TYPE, ELEMENT_TYPE, SUB_ELEMENT_TYPE, NAME, ELTS, N_ELTS) \
void init_##NAME(ARRAY_TYPE *a); \
ARRAY_TYPE *new_##NAME(int size); \
void delete_##NAME(ARRAY_TYPE *a); \
void setup_##NAME(ARRAY_TYPE *a, int size); \
void extend_##NAME(ARRAY_TYPE *a, int new_size); \
SUB_ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a); \
SUB_ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a); \
void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
void copy_##NAME##_filled(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src); \
void clear_##NAME(ARRAY_TYPE *a); \
SUB_ELEMENT_TYPE *NAME##_##ELTS(ARRAY_TYPE *a, int i); \
SUB_ELEMENT_TYPE NAME##_##ELTS##_elt(ARRAY_TYPE *a, int i, int j);
#define DECLARE_DYNAMIC_2D_ARRAY_FUNCS(ARRAY_TYPE, ELEMENT_TYPE, SUB_ELEMENT_TYPE, NAME, ELTS, N_ELTS, OTHER_INIT) \
 \
/* initialize raw array record */ \
void init_##NAME(ARRAY_TYPE *a) \
{ \
  a->current_size = a->N_ELTS = 0; \
  a->ELTS = 0; \
  OTHER_INIT \
} \
 \
/* allocate an array dynamically and initialize it */ \
ARRAY_TYPE *new_##NAME(int size) \
{ \
  ARRAY_TYPE *a = safe_malloc(sizeof(ARRAY_TYPE)); \
  init_##NAME(a); \
  setup_##NAME(a, size); \
  return a; \
} \
 \
void delete_##NAME(ARRAY_TYPE *a) \
{ \
  if (!a) return; \
  clear_##NAME(a); \
  safe_free(a); \
} \
 \
/* set up (or increase size of existing) initialized array with given size */ \
void setup_##NAME(ARRAY_TYPE *a, int size) \
{ \
  if (size > a->current_size) { \
    a->ELTS = safe_realloc(a->ELTS, size * sizeof(ELEMENT_TYPE)); \
    a->current_size = size; \
  } \
} \
 \
void extend_##NAME(ARRAY_TYPE *a, int new_size) \
{ \
  int actual_new_size = a->current_size; \
  if (actual_new_size <= 0) actual_new_size = 1; \
  while (actual_new_size < new_size) \
    actual_new_size *= 2; \
  setup_##NAME(a, actual_new_size); \
} \
 \
SUB_ELEMENT_TYPE *pushed_##NAME##_##ELTS(ARRAY_TYPE *a) \
{ \
  extend_##NAME(a, a->N_ELTS + 1); \
  return a->ELTS[a->N_ELTS++]; \
} \
 \
SUB_ELEMENT_TYPE *popped_##NAME##_##ELTS(ARRAY_TYPE *a) \
{ \
  if (a->N_ELTS <= 0) \
    die(no_line, "popped_" #NAME "_" #ELTS ": no elements to pop"); \
  return a->ELTS[--a->N_ELTS]; \
} \
 \
void copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  extend_##NAME(dst, src->current_size); \
  dst->N_ELTS = src->N_ELTS; \
  memcpy(dst->ELTS, src->ELTS, src->current_size * sizeof(ELEMENT_TYPE)); \
} \
 \
void copy_filled_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  extend_##NAME(dst, src->N_ELTS); \
  dst->N_ELTS = src->N_ELTS; \
  memcpy(dst->ELTS, src->ELTS, src->N_ELTS * sizeof(ELEMENT_TYPE)); \
} \
 \
void reverse_copy_##NAME(ARRAY_TYPE *dst, ARRAY_TYPE *src) \
{ \
  int i, j; \
  extend_##NAME(dst, src->N_ELTS); \
  dst->N_ELTS = src->N_ELTS; \
  for (i = 0, j = dst->N_ELTS - 1; j >= 0; i++, j--) \
    memcpy(dst->ELTS[j], src->ELTS[i], sizeof dst->ELTS[0]); \
} \
 \
void clear_##NAME(ARRAY_TYPE *a) \
{ \
  safe_free(a->ELTS); \
  init_##NAME(a); \
} \
 \
SUB_ELEMENT_TYPE *NAME##_##ELTS(ARRAY_TYPE *a, int i) \
{ \
  if (i < 0 || i > a->N_ELTS) \
    die(no_line, #NAME "_elt: " #ELEMENT_TYPE "_ARRAY reference out of bounds"); \
  return a->ELTS[i]; \
} \
 \
SUB_ELEMENT_TYPE NAME##_##ELTS##_elt(ARRAY_TYPE *a, int i, int j) \
{ \
  if (i < 0 || i >= a->N_ELTS || j < 0 || j >= sizeof(ELEMENT_TYPE) / sizeof(SUB_ELEMENT_TYPE)) \
    die(no_line, #NAME "_subelt: " #ELEMENT_TYPE "_ARRAY reference [%d][%d] out of bounds", i, j); \
  return a->ELTS[i][j]; \
}
#endif