]>
diplodocus.org Git - nmh/blob - sbr/vector.c
c2bd0df913b3003e5781ab42ac33fd7aa7b69f01
1 /* vector.c -- dynamically sized vectors
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.
9 * This file defines several kinds of vectors:
11 * svector: vector of char arrays
12 * ivector: vector of ints
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.
22 #define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
23 #define SVEC_INIT_SIZE 256
24 #define IVEC_INIT_SIZE 256
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.
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)
45 unsigned long tiny
[2];
48 static void bvector_resize (bvector_t
, size_t);
51 bvector_create (size_t init_size
) {
55 /* See "wider than unsigned long" comment above. */
56 assert (sizeof *vec
->bits
<= sizeof 1ul);
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
);
67 bytes
= BVEC_BYTES(init_size
);
68 vec
->bits
= mh_xcalloc (1, bytes
);
69 vec
->maxsize
= bytes
* CHAR_BIT
;
75 bvector_copy (bvector_t dest
, bvector_t src
) {
76 size_t bytes
= BVEC_BYTES(src
->maxsize
);
78 if (dest
->bits
!= dest
->tiny
)
80 dest
->bits
= mh_xmalloc (bytes
);
81 memcpy (dest
->bits
, src
->bits
, bytes
);
82 dest
->maxsize
= src
->maxsize
;
86 bvector_free (bvector_t vec
) {
87 if (vec
->bits
!= vec
->tiny
)
93 bvector_clear (bvector_t vec
, size_t n
) {
94 size_t word
= BVEC_WORD(n
);
95 size_t offset
= BVEC_OFFSET(n
);
97 if (n
>= vec
->maxsize
)
98 bvector_resize (vec
, n
);
100 vec
->bits
[word
] &= ~(1ul << offset
);
105 bvector_clear_all (bvector_t vec
) {
106 memset (vec
->bits
, 0, BVEC_BYTES(vec
->maxsize
));
111 bvector_set (bvector_t vec
, size_t n
) {
112 size_t word
= BVEC_WORD(n
);
113 size_t offset
= BVEC_OFFSET(n
);
115 if (n
>= vec
->maxsize
)
116 bvector_resize (vec
, n
);
117 vec
->bits
[word
] |= 1ul << offset
;
121 bvector_at (bvector_t vec
, size_t i
) {
122 size_t word
= BVEC_WORD(i
);
123 size_t offset
= BVEC_OFFSET(i
);
125 return i
< vec
->maxsize
126 ? (vec
->bits
[word
] & (1ul << offset
) ? 1 : 0)
131 bvector_resize (bvector_t vec
, size_t maxsize
) {
132 size_t old_maxsize
= vec
->maxsize
;
135 while ((vec
->maxsize
*= 2) < maxsize
)
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
);
142 vec
->bits
= mh_xrealloc(vec
->bits
, bytes
);
144 memset(vec
->bits
+ (old_maxsize
/ BVEC_BITS_BITS
), 0,
145 (vec
->maxsize
- old_maxsize
) / CHAR_BIT
);
149 bvector_first_bits (bvector_t vec
) {
160 static void svector_resize (svector_t
, size_t);
163 svector_create (size_t init_size
) {
168 vec
->maxsize
= init_size
? init_size
: SVEC_INIT_SIZE
;
169 bytes
= vec
->maxsize
* sizeof (char *);
170 vec
->strs
= mh_xcalloc (1, bytes
);
177 svector_free (svector_t vec
) {
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
;
190 svector_at (svector_t vec
, size_t i
) {
191 if (i
>= vec
->maxsize
)
192 svector_resize (vec
, i
);
197 * Return address of first element that stringwise matches s.
198 * The caller can replace the contents of the return address.
201 svector_find (svector_t vec
, const char *s
) {
203 char **str
= vec
->strs
;
205 for (i
= 0; i
< vec
->size
; ++i
, ++str
) {
206 if (*str
&& ! strcmp(*str
, s
)) {
215 svector_strs (svector_t vec
) {
220 svector_size (svector_t vec
) {
225 svector_resize (svector_t vec
, size_t maxsize
) {
226 size_t old_maxsize
= vec
->maxsize
;
228 while ((vec
->maxsize
*= 2) < maxsize
)
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
);
242 static void ivector_resize (ivector_t
, size_t);
245 ivector_create (size_t init_size
) {
250 vec
->maxsize
= init_size
? init_size
: IVEC_INIT_SIZE
;
251 bytes
= vec
->maxsize
* sizeof (int);
252 vec
->ints
= mh_xcalloc (1, bytes
);
259 ivector_free (ivector_t vec
) {
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
;
272 ivector_at (ivector_t vec
, size_t i
) {
273 if (i
>= vec
->maxsize
)
274 ivector_resize (vec
, i
);
279 ivector_atp (ivector_t vec
, size_t i
) {
280 if (i
>= vec
->maxsize
)
281 ivector_resize (vec
, i
);
282 return &vec
->ints
[i
];
286 ivector_resize (ivector_t vec
, size_t maxsize
) {
287 size_t old_maxsize
= vec
->maxsize
;
289 while ((vec
->maxsize
*= 2) < maxsize
)
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
);