]>
diplodocus.org Git - nmh/blob - sbr/vector.c
e975e27199d43ecd6cd9ecf2f86befc1adc6f7e3
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.
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)
41 unsigned long tiny
[2];
44 static void bvector_resize (bvector_t
, size_t);
47 bvector_create (size_t init_size
) {
51 /* See "wider than unsigned long" comment above. */
52 assert (sizeof *vec
->bits
<= sizeof 1ul);
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
);
63 bytes
= BVEC_BYTES(init_size
);
64 vec
->bits
= mh_xcalloc (1, bytes
);
65 vec
->maxsize
= bytes
* CHAR_BIT
;
71 bvector_copy (bvector_t dest
, bvector_t src
) {
72 size_t bytes
= BVEC_BYTES(src
->maxsize
);
74 if (dest
->bits
!= dest
->tiny
)
76 dest
->bits
= mh_xmalloc (bytes
);
77 memcpy (dest
->bits
, src
->bits
, bytes
);
78 dest
->maxsize
= src
->maxsize
;
82 bvector_free (bvector_t vec
) {
83 if (vec
->bits
!= vec
->tiny
)
89 bvector_clear (bvector_t vec
, size_t n
) {
90 size_t word
= BVEC_WORD(n
);
91 size_t offset
= BVEC_OFFSET(n
);
93 if (n
>= vec
->maxsize
)
94 bvector_resize (vec
, n
);
96 vec
->bits
[word
] &= ~(1ul << offset
);
101 bvector_clear_all (bvector_t vec
) {
102 memset (vec
->bits
, 0, BVEC_BYTES(vec
->maxsize
));
107 bvector_set (bvector_t vec
, size_t n
) {
108 size_t word
= BVEC_WORD(n
);
109 size_t offset
= BVEC_OFFSET(n
);
111 if (n
>= vec
->maxsize
)
112 bvector_resize (vec
, n
);
113 vec
->bits
[word
] |= 1ul << offset
;
117 bvector_at (bvector_t vec
, size_t i
) {
118 size_t word
= BVEC_WORD(i
);
119 size_t offset
= BVEC_OFFSET(i
);
121 return i
< vec
->maxsize
122 ? (vec
->bits
[word
] & (1ul << offset
) ? 1 : 0)
127 bvector_resize (bvector_t vec
, size_t maxsize
) {
128 size_t old_maxsize
= vec
->maxsize
;
132 while ((vec
->maxsize
*= 2) < maxsize
)
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
);
139 vec
->bits
= mh_xrealloc(vec
->bits
, bytes
);
140 for (i
= old_maxsize
; i
< vec
->maxsize
; ++i
)
141 bvector_clear (vec
, i
);
144 const unsigned long *
145 bvector_bits (bvector_t vec
) {
156 static void svector_resize (svector_t
, size_t);
159 svector_create (size_t init_size
) {
164 vec
->maxsize
= init_size
? init_size
: SVEC_INIT_SIZE
;
165 bytes
= vec
->maxsize
* sizeof (char *);
166 vec
->strs
= mh_xcalloc (1, bytes
);
173 svector_free (svector_t vec
) {
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
;
186 svector_at (svector_t vec
, size_t i
) {
187 if (i
>= vec
->maxsize
)
188 svector_resize (vec
, i
);
193 * Return address of first element that stringwise matches s.
194 * The caller can replace the contents of the return address.
197 svector_find (svector_t vec
, const char *s
) {
199 char **str
= vec
->strs
;
201 for (i
= 0; i
< vec
->size
; ++i
, ++str
) {
202 if (*str
&& ! strcmp(*str
, s
)) {
211 svector_strs (svector_t vec
) {
216 svector_size (svector_t vec
) {
221 svector_resize (svector_t vec
, size_t maxsize
) {
222 size_t old_maxsize
= vec
->maxsize
;
225 while ((vec
->maxsize
*= 2) < maxsize
)
227 vec
->strs
= mh_xrealloc (vec
->strs
, vec
->maxsize
* sizeof (char *));
228 for (i
= old_maxsize
; i
< vec
->maxsize
; ++i
)
239 static void ivector_resize (ivector_t
, size_t);
242 ivector_create (size_t init_size
) {
247 vec
->maxsize
= init_size
? init_size
: IVEC_INIT_SIZE
;
248 bytes
= vec
->maxsize
* sizeof (int);
249 vec
->ints
= mh_xcalloc (1, bytes
);
256 ivector_free (ivector_t vec
) {
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
;
269 ivector_at (ivector_t vec
, size_t i
) {
270 if (i
>= vec
->maxsize
)
271 ivector_resize (vec
, i
);
276 ivector_atp (ivector_t vec
, size_t i
) {
277 if (i
>= vec
->maxsize
)
278 ivector_resize (vec
, i
);
279 return &vec
->ints
[i
];
283 ivector_resize (ivector_t vec
, size_t maxsize
) {
284 size_t old_maxsize
= vec
->maxsize
;
287 while ((vec
->maxsize
*= 2) < maxsize
)
289 vec
->ints
= mh_xrealloc (vec
->ints
, vec
->maxsize
* sizeof (int));
290 for (i
= old_maxsize
; i
< vec
->maxsize
; ++i
)