]> diplodocus.org Git - nmh/blob - sbr/vector.c
c2bd0df913b3003e5781ab42ac33fd7aa7b69f01
[nmh] / sbr / vector.c
1 /* vector.c -- dynamically sized vectors
2 *
3 * This code is Copyright (c) 2013, by the authors of nmh. See the
4 * COPYRIGHT file in the root directory of the nmh distribution for
5 * complete copyright information.
6 */
7
8 /*
9 * This file defines several kinds of vectors:
10 * bvector: bit vector
11 * svector: vector of char arrays
12 * ivector: vector of ints
13 *
14 * The interfaces provide only the capabilities needed by nmh. The
15 * implementations rely on dynamic allocation, so that a vector
16 * can be as large as needed, as long as it fits in (virtual) memory.
17 */
18
19 #include <h/mh.h>
20 #include <h/utils.h>
21
22 #define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
23 #define SVEC_INIT_SIZE 256
24 #define IVEC_INIT_SIZE 256
25
26 /*
27 * These try to hide the type of the "bits" member of bvector. But if
28 * that is changed to a type that's wider than unsigned long, the 1ul
29 * constants in the code below must also be changed to a 1 that's at
30 * least as wide as the new type.
31 */
32
33 /* The *sizeof* struct bvector's bits member. Not its size in bits. */
34 #define BVEC_SIZEOF_BITS (sizeof *(((bvector_t)NULL)->bits))
35 /* The number of bits held in one element of the bits member. */
36 #define BVEC_BITS_BITS (BVEC_SIZEOF_BITS * CHAR_BIT)
37 #define BVEC_WORD(max) ((max) / BVEC_BITS_BITS)
38 #define BVEC_OFFSET(max) ((max) % BVEC_BITS_BITS)
39 #define BVEC_BYTES(n) \
40 ((BVEC_WORD(n) + (BVEC_OFFSET(n) == 0 ? 0 : 1)) * BVEC_SIZEOF_BITS)
41
42 struct bvector {
43 unsigned long *bits;
44 size_t maxsize;
45 unsigned long tiny[2];
46 };
47
48 static void bvector_resize (bvector_t, size_t);
49
50 bvector_t
51 bvector_create (size_t init_size) {
52 bvector_t vec;
53 size_t bytes;
54
55 /* See "wider than unsigned long" comment above. */
56 assert (sizeof *vec->bits <= sizeof 1ul);
57
58 NEW(vec);
59
60 if (init_size <= BVEC_INIT_SIZE) {
61 vec->bits = vec->tiny;
62 vec->maxsize = BVEC_INIT_SIZE;
63 memset(vec->tiny, 0, sizeof vec->tiny);
64 return vec;
65 }
66
67 bytes = BVEC_BYTES(init_size);
68 vec->bits = mh_xcalloc (1, bytes);
69 vec->maxsize = bytes * CHAR_BIT;
70
71 return vec;
72 }
73
74 void
75 bvector_copy (bvector_t dest, bvector_t src) {
76 size_t bytes = BVEC_BYTES(src->maxsize);
77
78 if (dest->bits != dest->tiny)
79 free(dest->bits);
80 dest->bits = mh_xmalloc (bytes);
81 memcpy (dest->bits, src->bits, bytes);
82 dest->maxsize = src->maxsize;
83 }
84
85 void
86 bvector_free (bvector_t vec) {
87 if (vec->bits != vec->tiny)
88 free(vec->bits);
89 free (vec);
90 }
91
92 void
93 bvector_clear (bvector_t vec, size_t n) {
94 size_t word = BVEC_WORD(n);
95 size_t offset = BVEC_OFFSET(n);
96
97 if (n >= vec->maxsize)
98 bvector_resize (vec, n);
99
100 vec->bits[word] &= ~(1ul << offset);
101 }
102
103
104 void
105 bvector_clear_all (bvector_t vec) {
106 memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
107 }
108
109
110 void
111 bvector_set (bvector_t vec, size_t n) {
112 size_t word = BVEC_WORD(n);
113 size_t offset = BVEC_OFFSET(n);
114
115 if (n >= vec->maxsize)
116 bvector_resize (vec, n);
117 vec->bits[word] |= 1ul << offset;
118 }
119
120 unsigned int
121 bvector_at (bvector_t vec, size_t i) {
122 size_t word = BVEC_WORD(i);
123 size_t offset = BVEC_OFFSET(i);
124
125 return i < vec->maxsize
126 ? (vec->bits[word] & (1ul << offset) ? 1 : 0)
127 : 0;
128 }
129
130 static void
131 bvector_resize (bvector_t vec, size_t maxsize) {
132 size_t old_maxsize = vec->maxsize;
133 size_t bytes;
134
135 while ((vec->maxsize *= 2) < maxsize)
136 ;
137 bytes = BVEC_BYTES(vec->maxsize);
138 if (vec->bits == vec->tiny) {
139 vec->bits = mh_xmalloc(bytes);
140 memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
141 } else
142 vec->bits = mh_xrealloc(vec->bits, bytes);
143
144 memset(vec->bits + (old_maxsize / BVEC_BITS_BITS), 0,
145 (vec->maxsize - old_maxsize) / CHAR_BIT);
146 }
147
148 unsigned long
149 bvector_first_bits (bvector_t vec) {
150 return *vec->bits;
151 }
152
153
154 struct svector {
155 char **strs;
156 size_t maxsize;
157 size_t size;
158 };
159
160 static void svector_resize (svector_t, size_t);
161
162 svector_t
163 svector_create (size_t init_size) {
164 svector_t vec;
165 size_t bytes;
166
167 NEW(vec);
168 vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
169 bytes = vec->maxsize * sizeof (char *);
170 vec->strs = mh_xcalloc (1, bytes);
171 vec->size = 0;
172
173 return vec;
174 }
175
176 void
177 svector_free (svector_t vec) {
178 free (vec->strs);
179 free (vec);
180 }
181
182 char *
183 svector_push_back (svector_t vec, char *s) {
184 if (++vec->size >= vec->maxsize)
185 svector_resize (vec, vec->size);
186 return vec->strs[vec->size-1] = s;
187 }
188
189 char *
190 svector_at (svector_t vec, size_t i) {
191 if (i >= vec->maxsize)
192 svector_resize (vec, i);
193 return vec->strs[i];
194 }
195
196 /*
197 * Return address of first element that stringwise matches s.
198 * The caller can replace the contents of the return address.
199 */
200 char **
201 svector_find (svector_t vec, const char *s) {
202 size_t i;
203 char **str = vec->strs;
204
205 for (i = 0; i < vec->size; ++i, ++str) {
206 if (*str && ! strcmp(*str, s)) {
207 return str;
208 }
209 }
210
211 return NULL;
212 }
213
214 char **
215 svector_strs (svector_t vec) {
216 return vec->strs;
217 }
218
219 size_t
220 svector_size (svector_t vec) {
221 return vec->size;
222 }
223
224 static void
225 svector_resize (svector_t vec, size_t maxsize) {
226 size_t old_maxsize = vec->maxsize;
227
228 while ((vec->maxsize *= 2) < maxsize)
229 ;
230 vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
231 memset(vec->strs + old_maxsize, 0,
232 (vec->maxsize - old_maxsize) * sizeof *vec->strs);
233 }
234
235
236 struct ivector {
237 int *ints;
238 size_t maxsize;
239 size_t size;
240 };
241
242 static void ivector_resize (ivector_t, size_t);
243
244 ivector_t
245 ivector_create (size_t init_size) {
246 ivector_t vec;
247 size_t bytes;
248
249 NEW(vec);
250 vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
251 bytes = vec->maxsize * sizeof (int);
252 vec->ints = mh_xcalloc (1, bytes);
253 vec->size = 0;
254
255 return vec;
256 }
257
258 void
259 ivector_free (ivector_t vec) {
260 free (vec->ints);
261 free (vec);
262 }
263
264 int
265 ivector_push_back (ivector_t vec, int n) {
266 if (++vec->size >= vec->maxsize)
267 ivector_resize (vec, vec->size);
268 return vec->ints[vec->size-1] = n;
269 }
270
271 int
272 ivector_at (ivector_t vec, size_t i) {
273 if (i >= vec->maxsize)
274 ivector_resize (vec, i);
275 return vec->ints[i];
276 }
277
278 int *
279 ivector_atp (ivector_t vec, size_t i) {
280 if (i >= vec->maxsize)
281 ivector_resize (vec, i);
282 return &vec->ints[i];
283 }
284
285 static void
286 ivector_resize (ivector_t vec, size_t maxsize) {
287 size_t old_maxsize = vec->maxsize;
288
289 while ((vec->maxsize *= 2) < maxsize)
290 ;
291 vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
292 memset(vec->ints + old_maxsize, 0,
293 (vec->maxsize - old_maxsize) * sizeof *vec->ints);
294 }