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
|
/*
Implementation of arrays that can grow in size.
Diego Zamboni, Mar 7, 1997.
*/
/* Chunk sizes in which the array grows */
#define EXT_ARRAY_CHUNK_SIZE 50
typedef struct ext_array_struct {
int size; /* Total number of units which have been allocated for
storage of the extendable array */
int elems; /* last_elem+1 */
int last_elem; /* Largest index of all elements which have been set */
void *data;
} extendable_array;
/* This is all implemented with macros to allow for specification of
types. */
/* Inserts an element in the next available free spot in the array */
#define EXT_ARRAY_ADD(var,type,val) \
{\
EXT_ARRAY_SET(var,type,var.elems,val);\
}
/* Initialize a variable of type extendable_array */
#define EXT_ARRAY_INIT(var,type,inisize) \
{\
int i;\
var.size=inisize;\
var.elems=0;\
var.last_elem=-1;\
var.data=(type *)malloc(sizeof(type) * inisize);\
for (i=0; i < inisize; i++)\
((type *)var.data)[i] = 0;\
}
/* Set the n-th element of the array to a value, extending the array
* if necessary. All elements which are added to the array and not
* explicitly set to a value are given the value of 0. */
#define EXT_ARRAY_SET(var,type,n,val) \
{\
int ext_index;\
if(n >= var.size) {\
var.data = (type *)realloc(var.data,\
sizeof(type)*\
(((n/EXT_ARRAY_CHUNK_SIZE)+1)*\
EXT_ARRAY_CHUNK_SIZE));\
var.size = (((n/EXT_ARRAY_CHUNK_SIZE)+1)*\
EXT_ARRAY_CHUNK_SIZE);\
}\
if (n >= var.elems){\
for (ext_index=var.elems; ext_index <= n; ext_index++)\
((type *) var.data)[ext_index] = 0;\
var.elems = n+1;\
}\
if(n >= var.last_elem) {\
var.last_elem = n;\
}\
((type *) var.data)[n]=val;\
}\
/* Initialize for n elements and set elements to val. We can save a lot of
* manipulations of parts of var until we're finished. */
#define EXT_ARRAY_INIT_N_SET(var,type,inisize,val) \
{\
int i;\
(var).size=(inisize);\
(var).data=(type *)malloc(sizeof(type) * (inisize));\
for (i=0; i < (inisize); i++)\
((type *)var.data)[i] = (val);\
(var).elems = (inisize);\
(var).last_elem = (inisize);\
}
/* Get the value of an element. If index is out of range, returns 0 */
#define EXT_ARRAY_GET(var,type,n) \
((n < var.elems && n >= 0) ? (((type *)(var.data))[n]) : (type) 0)
/* Free memory used by extended array - array must be initialized to become
usable again. */
/* written by Jason Rennie <jr6b+@andrew.cmu.edu> for ifile */
#define EXT_ARRAY_FREE(var,type) \
{\
free((type *)var.data);\
var.data = NULL;\
}
/* Free memory used by elements of array (elements MUST be pointers) */
/* written by Jason Rennie <jr6b+@andrew.cmu.edu> for ifile */
#define EXT_ARRAY_FREE_ELEMS(var,type) \
{\
int i;\
for (i=0; i < var.elems; i++) \
{\
if (((type *)var.data)[i] != NULL) \
{\
free(((type *)var.data)[i]); \
((type *)var.data)[i] = NULL; \
}\
}\
var.elems=0;\
var.last_elem=-1;\
}
|
