]> diplodocus.org Git - nmh/blob - sbr/vector.c
e975e27199d43ecd6cd9ecf2f86befc1adc6f7e3
[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 #define BVEC_SIZEOF_BITS (sizeof *(((bvector_t)NULL)->bits))
33 #define BVEC_WORD(max) ((max) / (BVEC_SIZEOF_BITS * CHAR_BIT))
34 #define BVEC_OFFSET(max) ((max) % (BVEC_SIZEOF_BITS * CHAR_BIT))
35 #define BVEC_BYTES(n) \
36 ((BVEC_WORD(n) + (BVEC_OFFSET(n) == 0 ? 0 : 1)) * BVEC_SIZEOF_BITS)
37
38 struct bvector {
39 unsigned long *bits;
40 size_t maxsize;
41 unsigned long tiny[2];
42 };
43
44 static void bvector_resize (bvector_t, size_t);
45
46 bvector_t
47 bvector_create (size_t init_size) {
48 bvector_t vec;
49 size_t bytes;
50
51 /* See "wider than unsigned long" comment above. */
52 assert (sizeof *vec->bits <= sizeof 1ul);
53
54 NEW(vec);
55
56 if (init_size <= BVEC_INIT_SIZE) {
57 vec->bits = vec->tiny;
58 vec->maxsize = BVEC_INIT_SIZE;
59 memset(vec->tiny, 0, sizeof vec->tiny);
60 return vec;
61 }
62
63 bytes = BVEC_BYTES(init_size);
64 vec->bits = mh_xcalloc (1, bytes);
65 vec->maxsize = bytes * CHAR_BIT;
66
67 return vec;
68 }
69
70 void
71 bvector_copy (bvector_t dest, bvector_t src) {
72 size_t bytes = BVEC_BYTES(src->maxsize);
73
74 if (dest->bits != dest->tiny)
75 free(dest->bits);
76 dest->bits = mh_xmalloc (bytes);
77 memcpy (dest->bits, src->bits, bytes);
78 dest->maxsize = src->maxsize;
79 }
80
81 void
82 bvector_free (bvector_t vec) {
83 if (vec->bits != vec->tiny)
84 free(vec->bits);
85 free (vec);
86 }
87
88 void
89 bvector_clear (bvector_t vec, size_t n) {
90 size_t word = BVEC_WORD(n);
91 size_t offset = BVEC_OFFSET(n);
92
93 if (n >= vec->maxsize)
94 bvector_resize (vec, n);
95
96 vec->bits[word] &= ~(1ul << offset);
97 }
98
99
100 void
101 bvector_clear_all (bvector_t vec) {
102 memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));
103 }
104
105
106 void
107 bvector_set (bvector_t vec, size_t n) {
108 size_t word = BVEC_WORD(n);
109 size_t offset = BVEC_OFFSET(n);
110
111 if (n >= vec->maxsize)
112 bvector_resize (vec, n);
113 vec->bits[word] |= 1ul << offset;
114 }
115
116 unsigned int
117 bvector_at (bvector_t vec, size_t i) {
118 size_t word = BVEC_WORD(i);
119 size_t offset = BVEC_OFFSET(i);
120
121 return i < vec->maxsize
122 ? (vec->bits[word] & (1ul << offset) ? 1 : 0)
123 : 0;
124 }
125
126 static void
127 bvector_resize (bvector_t vec, size_t maxsize) {
128 size_t old_maxsize = vec->maxsize;
129 size_t bytes;
130 size_t i;
131
132 while ((vec->maxsize *= 2) < maxsize)
133 ;
134 bytes = BVEC_BYTES(vec->maxsize);
135 if (vec->bits == vec->tiny) {
136 vec->bits = mh_xmalloc(bytes);
137 memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
138 } else
139 vec->bits = mh_xrealloc(vec->bits, bytes);
140 for (i = old_maxsize; i < vec->maxsize; ++i)
141 bvector_clear (vec, i);
142 }
143
144 const unsigned long *
145 bvector_bits (bvector_t vec) {
146 return vec->bits;
147 }
148
149
150 struct svector {
151 char **strs;
152 size_t maxsize;
153 size_t size;
154 };
155
156 static void svector_resize (svector_t, size_t);
157
158 svector_t
159 svector_create (size_t init_size) {
160 svector_t vec;
161 size_t bytes;
162
163 NEW(vec);
164 vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;
165 bytes = vec->maxsize * sizeof (char *);
166 vec->strs = mh_xcalloc (1, bytes);
167 vec->size = 0;
168
169 return vec;
170 }
171
172 void
173 svector_free (svector_t vec) {
174 free (vec->strs);
175 free (vec);
176 }
177
178 char *
179 svector_push_back (svector_t vec, char *s) {
180 if (++vec->size >= vec->maxsize)
181 svector_resize (vec, vec->size);
182 return vec->strs[vec->size-1] = s;
183 }
184
185 char *
186 svector_at (svector_t vec, size_t i) {
187 if (i >= vec->maxsize)
188 svector_resize (vec, i);
189 return vec->strs[i];
190 }
191
192 /*
193 * Return address of first element that stringwise matches s.
194 * The caller can replace the contents of the return address.
195 */
196 char **
197 svector_find (svector_t vec, const char *s) {
198 size_t i;
199 char **str = vec->strs;
200
201 for (i = 0; i < vec->size; ++i, ++str) {
202 if (*str && ! strcmp(*str, s)) {
203 return str;
204 }
205 }
206
207 return NULL;
208 }
209
210 char **
211 svector_strs (svector_t vec) {
212 return vec->strs;
213 }
214
215 size_t
216 svector_size (svector_t vec) {
217 return vec->size;
218 }
219
220 static void
221 svector_resize (svector_t vec, size_t maxsize) {
222 size_t old_maxsize = vec->maxsize;
223 size_t i;
224
225 while ((vec->maxsize *= 2) < maxsize)
226 ;
227 vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
228 for (i = old_maxsize; i < vec->maxsize; ++i)
229 vec->strs[i] = NULL;
230 }
231
232
233 struct ivector {
234 int *ints;
235 size_t maxsize;
236 size_t size;
237 };
238
239 static void ivector_resize (ivector_t, size_t);
240
241 ivector_t
242 ivector_create (size_t init_size) {
243 ivector_t vec;
244 size_t bytes;
245
246 NEW(vec);
247 vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;
248 bytes = vec->maxsize * sizeof (int);
249 vec->ints = mh_xcalloc (1, bytes);
250 vec->size = 0;
251
252 return vec;
253 }
254
255 void
256 ivector_free (ivector_t vec) {
257 free (vec->ints);
258 free (vec);
259 }
260
261 int
262 ivector_push_back (ivector_t vec, int n) {
263 if (++vec->size >= vec->maxsize)
264 ivector_resize (vec, vec->size);
265 return vec->ints[vec->size-1] = n;
266 }
267
268 int
269 ivector_at (ivector_t vec, size_t i) {
270 if (i >= vec->maxsize)
271 ivector_resize (vec, i);
272 return vec->ints[i];
273 }
274
275 int *
276 ivector_atp (ivector_t vec, size_t i) {
277 if (i >= vec->maxsize)
278 ivector_resize (vec, i);
279 return &vec->ints[i];
280 }
281
282 static void
283 ivector_resize (ivector_t vec, size_t maxsize) {
284 size_t old_maxsize = vec->maxsize;
285 size_t i;
286
287 while ((vec->maxsize *= 2) < maxsize)
288 ;
289 vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
290 for (i = old_maxsize; i < vec->maxsize; ++i)
291 vec->ints[i] = 0;
292 }