1 /**********************************************************************
2 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12 ***********************************************************************/
15 #include <fc_config.h>
18 #include "fc_prehdrs.h"
31 #include "string_vector.h"
33 #include "bitvector.h"
35 /* There are two types of bitvectors defined in this file:
36 (1) bv_* - static bitvectors; used for data which where the length is
37 fixed (number of players; flags for enums; ...). They are
38 named bv_* and the macros BV_* are defined.
39 (2) dbv_* - dynamic bitvectors; its size is not known a priori but defined
40 by the player (map known bitvectors). This bitvectors are
41 given as 'struct dbv' and the information can be accessed
42 using the functions dbv_*(). They uses the BV_* macros. */
44 /***************************************************************************
45 Initialize a dynamic bitvector of size 'bits'. 'bits' must be greater
46 than 0 and lower than the maximal size given by MAX_DBV_LENGTH. The
47 bitvector is set to all clear.
48 ***************************************************************************/
49 void dbv_init(struct dbv
*pdbv
, int bits
)
51 /* Here used to be asserts checking if pdbv->vec is NULL
52 * and pdbv->bits is 0, but that's just broken. One would
53 * assume that _init() function can be called when the thing
54 * is currently uninitialized, i.e., can have any values.
55 * Those fc_assert_ret()s caused this function to return
56 * without actually initializing the structure, leading to
59 fc_assert_ret(bits
> 0 && bits
< MAX_DBV_LENGTH
);
62 pdbv
->vec
= fc_calloc(1, _BV_BYTES(pdbv
->bits
) * sizeof(*pdbv
->vec
));
67 /***************************************************************************
68 Resize a dynamic bitvector. Create it if needed.
69 ***************************************************************************/
70 void dbv_resize(struct dbv
*pdbv
, int bits
)
72 fc_assert_ret(bits
> 0 && bits
< MAX_DBV_LENGTH
);
74 if (pdbv
->vec
== NULL
) {
75 /* Initialise a new dbv. */
78 /* Resize an existing dbv. */
79 fc_assert_ret(pdbv
->bits
!= 0);
81 if (bits
!= pdbv
->bits
) {
83 pdbv
->vec
= fc_realloc(pdbv
->vec
,
84 _BV_BYTES(pdbv
->bits
) * sizeof(*pdbv
->vec
));
91 /***************************************************************************
92 Destroy a dynamic bitvector.
93 ***************************************************************************/
94 void dbv_free(struct dbv
*pdbv
)
104 /***************************************************************************
105 Returns the number of bits defined in a dynamic bitvector.
106 ***************************************************************************/
107 int dbv_bits(struct dbv
*pdbv
)
116 /***************************************************************************
117 Check if the bit 'bit' is set.
118 ***************************************************************************/
119 bool dbv_isset(const struct dbv
*pdbv
, int bit
)
121 fc_assert_ret_val(pdbv
!= NULL
, FALSE
);
122 fc_assert_ret_val(pdbv
->vec
!= NULL
, FALSE
);
123 fc_assert_ret_val(bit
< pdbv
->bits
, FALSE
);
125 return ((pdbv
->vec
[_BV_BYTE_INDEX(bit
)] & _BV_BITMASK(bit
)) != 0);
128 /***************************************************************************
129 Test if any bit is set.
130 ***************************************************************************/
131 bool dbv_isset_any(const struct dbv
*pdbv
)
133 fc_assert_ret_val(pdbv
!= NULL
, FALSE
);
134 fc_assert_ret_val(pdbv
->vec
!= NULL
, FALSE
);
136 return bv_check_mask(pdbv
->vec
, pdbv
->vec
, _BV_BYTES(pdbv
->bits
),
137 _BV_BYTES(pdbv
->bits
));
140 /***************************************************************************
141 Set the bit given by 'bit'.
142 ***************************************************************************/
143 void dbv_set(struct dbv
*pdbv
, int bit
)
145 fc_assert_ret(pdbv
!= NULL
);
146 fc_assert_ret(pdbv
->vec
!= NULL
);
147 fc_assert_ret(bit
< pdbv
->bits
);
149 pdbv
->vec
[_BV_BYTE_INDEX(bit
)] |= _BV_BITMASK(bit
);
152 /***************************************************************************
154 ***************************************************************************/
155 void dbv_set_all(struct dbv
*pdbv
)
157 fc_assert_ret(pdbv
!= NULL
);
158 fc_assert_ret(pdbv
->vec
!= NULL
);
160 memset(pdbv
->vec
, 0xff, _BV_BYTES(pdbv
->bits
));
163 /***************************************************************************
164 Clear the bit given by 'bit'.
165 ***************************************************************************/
166 void dbv_clr(struct dbv
*pdbv
, int bit
)
168 fc_assert_ret(pdbv
!= NULL
);
169 fc_assert_ret(pdbv
->vec
!= NULL
);
170 fc_assert_ret(bit
< pdbv
->bits
);
172 pdbv
->vec
[_BV_BYTE_INDEX(bit
)] &= ~_BV_BITMASK(bit
);
175 /***************************************************************************
177 ***************************************************************************/
178 void dbv_clr_all(struct dbv
*pdbv
)
180 fc_assert_ret(pdbv
!= NULL
);
181 fc_assert_ret(pdbv
->vec
!= NULL
);
183 memset(pdbv
->vec
, 0, _BV_BYTES(pdbv
->bits
));
186 /***************************************************************************
187 Check if the two dynamic bitvectors are equal.
188 ***************************************************************************/
189 bool dbv_are_equal(const struct dbv
*pdbv1
, const struct dbv
*pdbv2
)
191 fc_assert_ret_val(pdbv1
!= NULL
, FALSE
);
192 fc_assert_ret_val(pdbv1
->vec
!= NULL
, FALSE
);
193 fc_assert_ret_val(pdbv2
!= NULL
, FALSE
);
194 fc_assert_ret_val(pdbv2
->vec
!= NULL
, FALSE
);
196 return bv_are_equal(pdbv1
->vec
, pdbv2
->vec
, _BV_BYTES(pdbv1
->bits
),
197 _BV_BYTES(pdbv2
->bits
));
200 /***************************************************************************
201 Debug a dynamic bitvector.
202 ***************************************************************************/
203 void dbv_debug(struct dbv
*pdbv
)
208 fc_assert_ret(pdbv
!= NULL
);
209 fc_assert_ret(pdbv
->vec
!= NULL
);
211 for (i
= 0; i
< (pdbv
->bits
- 1) / 50 + 1; i
++) {
212 for (j
= 0; j
< 50; j
++) {
214 if (bit
>= pdbv
->bits
) {
217 test_str
[j
] = dbv_isset(pdbv
, bit
) ? '1' : '0';
220 log_error("[%5d] %s", i
, test_str
);
224 /***************************************************************************
225 Return whether two vectors: vec1 and vec2 have common
226 bits. I.e. (vec1 & vec2) != 0.
228 Don't call this function directly, use BV_CHECK_MASK macro
229 instead. Don't call this function with two different bitvectors.
230 ***************************************************************************/
231 bool bv_check_mask(const unsigned char *vec1
, const unsigned char *vec2
,
232 size_t size1
, size_t size2
)
235 fc_assert_ret_val(size1
== size2
, FALSE
);
237 for (i
= 0; i
< size1
; i
++) {
238 if ((vec1
[0] & vec2
[0]) != 0) {
247 /***************************************************************************
248 Compares elements of two bitvectors. Both vectors are expected to have
249 same number of elements, i.e. , size1 must be equal to size2.
250 ***************************************************************************/
251 bool bv_are_equal(const unsigned char *vec1
, const unsigned char *vec2
,
252 size_t size1
, size_t size2
)
255 fc_assert_ret_val(size1
== size2
, FALSE
);
257 for (i
= 0; i
< size1
; i
++) {
258 if (vec1
[0] != vec2
[0]) {
267 /**************************************************************************
268 Set everything that is true in vec_from in vec_to. Stuff that already is
269 true in vec_to aren't touched. (Bitwise inclusive OR assignment)
271 Both vectors are expected to have same number of elements,
272 i.e. , size1 must be equal to size2.
273 **************************************************************************/
274 void bv_set_all_from(unsigned char *vec_to
,
275 const unsigned char *vec_from
,
276 size_t size_to
, size_t size_from
)
280 fc_assert_ret(size_to
== size_from
);
282 for (i
= 0; i
< size_to
; i
++) {
283 vec_to
[i
] |= vec_from
[i
];