Freeciv-3.2: /fast/freeciv/nightly/S3_2/utility/bitvector.c Source File

Freeciv-3.2

Loading...
Searching...
No Matches
bitvector.c
Go to the documentation of this file.
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)
6 any later version.
7
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***********************************************************************/
13
14#ifdef HAVE_CONFIG_H
15#include <fc_config.h>
16#endif
17
18#include "fc_prehdrs.h"
19
20#include <errno.h>
21#include <stdarg.h>
22#include <stdio.h>
23#include <stdlib.h>
24#include <string.h>
25
26/* utility */
27#include "fciconv.h"
28#include "fcintl.h"
29#include "mem.h"
30#include "rand.h"
31#include "string_vector.h"
32
33#include "bitvector.h"
34
35/* There are two types of bitvectors defined in this file:
36 (1) bv_* - static bitvectors; used for data where the length is
37 fixed (number of players; flags for enums; ...). They are
38 named bv_*, and BV_* macros are defined.
39 (2) dbv_* - dynamic bitvectors; their size is not known a priori
40 but defined by the player (map known bitvectors).
41 These bitvectors are given as 'struct dbv' and the information
42 can be accessed using dbv_*() functions.
43 They use BV_* macros. */
44
45/***********************************************************************/
50 void dbv_init(struct dbv *pdbv, int bits)
51{
52 /* Here used to be asserts checking if pdbv->vec is NULL
53 * and pdbv->bits is 0, but that's just broken. One would
54 * assume that _init() function can be called when the thing
55 * is currently uninitialized, i.e., can have any values.
56 * Those fc_assert_ret()s caused this function to return
57 * without actually initializing the structure, leading to
58 * crash later. */
59
60 fc_assert_ret(bits > 0 && bits < MAX_DBV_LENGTH);
61
62 pdbv->bits = bits;
63 pdbv->vec = fc_calloc(1, _BV_BYTES(pdbv->bits) * sizeof(*pdbv->vec));
64
65 dbv_clr_all(pdbv);
66}
67
68/***********************************************************************/
71 void dbv_resize(struct dbv *pdbv, int bits)
72{
73 fc_assert_ret(bits > 0 && bits < MAX_DBV_LENGTH);
74
75 if (pdbv->vec == NULL) {
76 /* Initialise a new dbv. */
77 dbv_init(pdbv, bits);
78 } else {
79 /* Resize an existing dbv. */
80 fc_assert_ret(pdbv->bits != 0);
81
82 if (bits != pdbv->bits) {
83 pdbv->bits = bits;
84 pdbv->vec = fc_realloc(pdbv->vec,
85 _BV_BYTES(pdbv->bits) * sizeof(*pdbv->vec));
86 }
87
88 dbv_clr_all(pdbv);
89 }
90}
91
92/***********************************************************************/
95 void dbv_free(struct dbv *pdbv)
96{
97 if (pdbv != NULL) {
98 free(pdbv->vec);
99 pdbv->vec = NULL;
100
101 pdbv->bits = 0;
102 }
103}
104
105/***********************************************************************/
108 int dbv_bits(struct dbv *pdbv)
109{
110 if (pdbv != NULL) {
111 return pdbv->bits;
112 }
113
114 return -1;
115}
116
117/***********************************************************************/
120 bool dbv_isset(const struct dbv *pdbv, int bit)
121{
122 fc_assert_ret_val(pdbv != NULL, FALSE);
123 fc_assert_ret_val(pdbv->vec != NULL, FALSE);
124 fc_assert_ret_val(bit < pdbv->bits, FALSE);
125
126 return ((pdbv->vec[_BV_BYTE_INDEX(bit)] & _BV_BITMASK(bit)) != 0);
127}
128
129/***********************************************************************/
132 bool dbv_isset_any(const struct dbv *pdbv)
133{
134 fc_assert_ret_val(pdbv != NULL, FALSE);
135 fc_assert_ret_val(pdbv->vec != NULL, FALSE);
136
137 return bv_check_mask(pdbv->vec, pdbv->vec, _BV_BYTES(pdbv->bits),
138 _BV_BYTES(pdbv->bits));
139}
140
141/***********************************************************************/
144 void dbv_set(struct dbv *pdbv, int bit)
145{
146 fc_assert_ret(pdbv != NULL);
147 fc_assert_ret(pdbv->vec != NULL);
148 fc_assert_ret(bit < pdbv->bits);
149
150 pdbv->vec[_BV_BYTE_INDEX(bit)] |= _BV_BITMASK(bit);
151}
152
153/***********************************************************************/
156 void dbv_set_all(struct dbv *pdbv)
157{
158 fc_assert_ret(pdbv != NULL);
159 fc_assert_ret(pdbv->vec != NULL);
160
161 memset(pdbv->vec, 0xff, _BV_BYTES(pdbv->bits));
162}
163
164/***********************************************************************/
167 void dbv_clr(struct dbv *pdbv, int bit)
168{
169 fc_assert_ret(pdbv != NULL);
170 fc_assert_ret(pdbv->vec != NULL);
171 fc_assert_ret(bit < pdbv->bits);
172
173 pdbv->vec[_BV_BYTE_INDEX(bit)] &= ~_BV_BITMASK(bit);
174}
175
176/***********************************************************************/
179 void dbv_clr_all(struct dbv *pdbv)
180{
181 fc_assert_ret(pdbv != NULL);
182 fc_assert_ret(pdbv->vec != NULL);
183
184 memset(pdbv->vec, 0, _BV_BYTES(pdbv->bits));
185}
186
187/***********************************************************************/
190 bool dbv_are_equal(const struct dbv *pdbv1, const struct dbv *pdbv2)
191{
192 fc_assert_ret_val(pdbv1 != NULL, FALSE);
193 fc_assert_ret_val(pdbv1->vec != NULL, FALSE);
194 fc_assert_ret_val(pdbv2 != NULL, FALSE);
195 fc_assert_ret_val(pdbv2->vec != NULL, FALSE);
196
197 return bv_are_equal(pdbv1->vec, pdbv2->vec, _BV_BYTES(pdbv1->bits),
198 _BV_BYTES(pdbv2->bits));
199}
200
201/***********************************************************************/
205 bool bv_match_dbv(const struct dbv *match, const unsigned char *src)
206{
207 size_t bytes = _BV_BYTES(match->bits);
208 int i;
209
210 for (i = 0; i < bytes; i++) {
211 if (match->vec[i] != src[i]) {
212 return FALSE;
213 }
214 }
215
216 return TRUE;
217}
218
219/***********************************************************************/
222 void dbv_copy(struct dbv *dest, const struct dbv *src)
223{
224 if (dest->bits != src->bits) {
225 dbv_resize(dest, src->bits);
226 }
227
228 memcpy(dest->vec, src->vec, _BV_BYTES(src->bits));
229}
230
231/***********************************************************************/
235 void dbv_to_bv(unsigned char *dest, const struct dbv *src)
236{
237 memcpy(dest, src->vec, _BV_BYTES(src->bits));
238}
239
240/***********************************************************************/
244 void bv_to_dbv(struct dbv *dest, const unsigned char *src)
245{
246 memcpy(dest->vec, dest, _BV_BYTES(dest->bits));
247}
248
249/***********************************************************************/
252 void dbv_debug(struct dbv *pdbv)
253{
254 char test_str[51];
255 int i, j, bit;
256
257 fc_assert_ret(pdbv != NULL);
258 fc_assert_ret(pdbv->vec != NULL);
259
260 for (i = 0; i < (pdbv->bits - 1) / 50 + 1; i++) {
261 for (j = 0; j < 50; j++) {
262 bit = i * 50 + j;
263 if (bit >= pdbv->bits) {
264 break;
265 }
266 test_str[j] = dbv_isset(pdbv, bit) ? '1' : '0';
267 }
268 test_str[j] = '\0';
269 log_error("[%5d] %s", i, test_str);
270 }
271}
272
273/***********************************************************************/
280 bool bv_check_mask(const unsigned char *vec1, const unsigned char *vec2,
281 size_t size1, size_t size2)
282{
283 size_t i;
284
285 fc_assert_ret_val(size1 == size2, FALSE);
286
287 for (i = 0; i < size1; i++) {
288 if ((vec1[0] & vec2[0]) != 0) {
289 return TRUE;
290 }
291 vec1++;
292 vec2++;
293 }
294
295 return FALSE;
296}
297
298/***********************************************************************/
302 bool bv_are_equal(const unsigned char *vec1, const unsigned char *vec2,
303 size_t size1, size_t size2)
304{
305 size_t i;
306
307 fc_assert_ret_val(size1 == size2, FALSE);
308
309 for (i = 0; i < size1; i++) {
310 if (vec1[0] != vec2[0]) {
311 return FALSE;
312 }
313 vec1++;
314 vec2++;
315 }
316
317 return TRUE;
318}
319
320/***********************************************************************/
329 void bv_set_all_from(unsigned char *vec_to,
330 const unsigned char *vec_from,
331 size_t size_to, size_t size_from)
332{
333 size_t i;
334
335 fc_assert_ret(size_to == size_from);
336
337 for (i = 0; i < size_to; i++) {
338 vec_to[i] |= vec_from[i];
339 }
340}
341
342/***********************************************************************/
351 void bv_clr_all_from(unsigned char *vec_to,
352 const unsigned char *vec_from,
353 size_t size_to, size_t size_from)
354{
355 size_t i;
356
357 fc_assert_ret(size_to == size_from);
358
359 for (i = 0; i < size_to; i++) {
360 vec_to[i] &= ~vec_from[i];
361 }
362}
bv_check_mask
bool bv_check_mask(const unsigned char *vec1, const unsigned char *vec2, size_t size1, size_t size2)
Definition bitvector.c:280
bv_to_dbv
void bv_to_dbv(struct dbv *dest, const unsigned char *src)
Definition bitvector.c:244
dbv_isset_any
bool dbv_isset_any(const struct dbv *pdbv)
Definition bitvector.c:132
dbv_resize
void dbv_resize(struct dbv *pdbv, int bits)
Definition bitvector.c:71
bv_match_dbv
bool bv_match_dbv(const struct dbv *match, const unsigned char *src)
Definition bitvector.c:205
dbv_init
void dbv_init(struct dbv *pdbv, int bits)
Definition bitvector.c:50
bv_clr_all_from
void bv_clr_all_from(unsigned char *vec_to, const unsigned char *vec_from, size_t size_to, size_t size_from)
Definition bitvector.c:351
dbv_bits
int dbv_bits(struct dbv *pdbv)
Definition bitvector.c:108
dbv_set_all
void dbv_set_all(struct dbv *pdbv)
Definition bitvector.c:156
dbv_set
void dbv_set(struct dbv *pdbv, int bit)
Definition bitvector.c:144
bv_are_equal
bool bv_are_equal(const unsigned char *vec1, const unsigned char *vec2, size_t size1, size_t size2)
Definition bitvector.c:302
dbv_isset
bool dbv_isset(const struct dbv *pdbv, int bit)
Definition bitvector.c:120
dbv_copy
void dbv_copy(struct dbv *dest, const struct dbv *src)
Definition bitvector.c:222
dbv_debug
void dbv_debug(struct dbv *pdbv)
Definition bitvector.c:252
bv_set_all_from
void bv_set_all_from(unsigned char *vec_to, const unsigned char *vec_from, size_t size_to, size_t size_from)
Definition bitvector.c:329
dbv_free
void dbv_free(struct dbv *pdbv)
Definition bitvector.c:95
dbv_clr_all
void dbv_clr_all(struct dbv *pdbv)
Definition bitvector.c:179
dbv_clr
void dbv_clr(struct dbv *pdbv, int bit)
Definition bitvector.c:167
dbv_are_equal
bool dbv_are_equal(const struct dbv *pdbv1, const struct dbv *pdbv2)
Definition bitvector.c:190
dbv_to_bv
void dbv_to_bv(unsigned char *dest, const struct dbv *src)
Definition bitvector.c:235
bitvector.h
MAX_DBV_LENGTH
#define MAX_DBV_LENGTH
Definition bitvector.h:63
_BV_BYTE_INDEX
#define _BV_BYTE_INDEX(bits)
Definition bitvector.h:67
_BV_BYTES
#define _BV_BYTES(bits)
Definition bitvector.h:66
_BV_BITMASK
#define _BV_BITMASK(bit)
Definition bitvector.h:68
incite_cost
char * incite_cost
Definition comments.c:74
fc_prehdrs.h
fciconv.h
fcintl.h
fc_assert_ret
#define fc_assert_ret(condition)
Definition log.h:191
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
log_error
#define log_error(message,...)
Definition log.h:103
mem.h
fc_calloc
#define fc_calloc(n, esz)
Definition mem.h:38
fc_realloc
#define fc_realloc(ptr, sz)
Definition mem.h:36
rand.h
string_vector.h
dbv
Definition bitvector.h:32
dbv::bits
int bits
Definition bitvector.h:33
dbv::vec
unsigned char * vec
Definition bitvector.h:34
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47