utility/bitvector.c

   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 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. */
  43
  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)
  50 {
  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
  57    * crash later. */
  58
  59   fc_assert_ret(bits > 0 && bits < MAX_DBV_LENGTH);
  60
  61   pdbv->bits = bits;
  62   pdbv->vec = fc_calloc(1, _BV_BYTES(pdbv->bits) * sizeof(*pdbv->vec));
  63
  64   dbv_clr_all(pdbv);
  65 }
  66
  67 /***************************************************************************
  68   Resize a dynamic bitvector. Create it if needed.
  69 ***************************************************************************/
  70 void dbv_resize(struct dbv *pdbv, int bits)
  71 {
  72   fc_assert_ret(bits > 0 && bits < MAX_DBV_LENGTH);
  73
  74   if (pdbv->vec == NULL) {
  75     /* Initialise a new dbv. */
  76     dbv_init(pdbv, bits);
  77   } else {
  78     /* Resize an existing dbv. */
  79     fc_assert_ret(pdbv->bits != 0);
  80
  81     if (bits != pdbv->bits) {
  82       pdbv->bits = bits;
  83       pdbv->vec = fc_realloc(pdbv->vec,
  84                              _BV_BYTES(pdbv->bits) * sizeof(*pdbv->vec));
  85     }
  86
  87     dbv_clr_all(pdbv);
  88   }
  89 }
  90
  91 /***************************************************************************
  92   Destroy a dynamic bitvector.
  93 ***************************************************************************/
  94 void dbv_free(struct dbv *pdbv)
  95 {
  96   if (pdbv != NULL) {
  97     free(pdbv->vec);
  98     pdbv->vec = NULL;
  99
 100     pdbv->bits = 0;
 101   }
 102 }
 103
 104 /***************************************************************************
 105   Returns the number of bits defined in a dynamic bitvector.
 106 ***************************************************************************/
 107 int dbv_bits(struct dbv *pdbv)
 108 {
 109   if (pdbv != NULL) {
 110     return pdbv->bits;
 111   }
 112
 113   return -1;
 114 }
 115
 116 /***************************************************************************
 117   Check if the bit 'bit' is set.
 118 ***************************************************************************/
 119 bool dbv_isset(const struct dbv *pdbv, int bit)
 120 {
 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);
 124
 125   return ((pdbv->vec[_BV_BYTE_INDEX(bit)] & _BV_BITMASK(bit)) != 0);
 126 }
 127
 128 /***************************************************************************
 129   Test if any bit is set.
 130 ***************************************************************************/
 131 bool dbv_isset_any(const struct dbv *pdbv)
 132 {
 133   fc_assert_ret_val(pdbv != NULL, FALSE);
 134   fc_assert_ret_val(pdbv->vec != NULL, FALSE);
 135
 136   return bv_check_mask(pdbv->vec, pdbv->vec, _BV_BYTES(pdbv->bits),
 137                        _BV_BYTES(pdbv->bits));
 138 }
 139
 140 /***************************************************************************
 141   Set the bit given by 'bit'.
 142 ***************************************************************************/
 143 void dbv_set(struct dbv *pdbv, int bit)
 144 {
 145   fc_assert_ret(pdbv != NULL);
 146   fc_assert_ret(pdbv->vec != NULL);
 147   fc_assert_ret(bit < pdbv->bits);
 148
 149   pdbv->vec[_BV_BYTE_INDEX(bit)] |= _BV_BITMASK(bit);
 150 }
 151
 152 /***************************************************************************
 153   Set all bits.
 154 ***************************************************************************/
 155 void dbv_set_all(struct dbv *pdbv)
 156 {
 157   fc_assert_ret(pdbv != NULL);
 158   fc_assert_ret(pdbv->vec != NULL);
 159
 160   memset(pdbv->vec, 0xff, _BV_BYTES(pdbv->bits));
 161 }
 162
 163 /***************************************************************************
 164   Clear the bit given by 'bit'.
 165 ***************************************************************************/
 166 void dbv_clr(struct dbv *pdbv, int bit)
 167 {
 168   fc_assert_ret(pdbv != NULL);
 169   fc_assert_ret(pdbv->vec != NULL);
 170   fc_assert_ret(bit < pdbv->bits);
 171
 172   pdbv->vec[_BV_BYTE_INDEX(bit)] &= ~_BV_BITMASK(bit);
 173 }
 174
 175 /***************************************************************************
 176   Clear all bits.
 177 ***************************************************************************/
 178 void dbv_clr_all(struct dbv *pdbv)
 179 {
 180   fc_assert_ret(pdbv != NULL);
 181   fc_assert_ret(pdbv->vec != NULL);
 182
 183   memset(pdbv->vec, 0, _BV_BYTES(pdbv->bits));
 184 }
 185
 186 /***************************************************************************
 187   Check if the two dynamic bitvectors are equal.
 188 ***************************************************************************/
 189 bool dbv_are_equal(const struct dbv *pdbv1, const struct dbv *pdbv2)
 190 {
 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);
 195
 196   return bv_are_equal(pdbv1->vec, pdbv2->vec, _BV_BYTES(pdbv1->bits),
 197                       _BV_BYTES(pdbv2->bits));
 198 }
 199
 200 /***************************************************************************
 201   Debug a dynamic bitvector.
 202 ***************************************************************************/
 203 void dbv_debug(struct dbv *pdbv)
 204 {
 205   char test_str[51];
 206   int i, j, bit;
 207
 208   fc_assert_ret(pdbv != NULL);
 209   fc_assert_ret(pdbv->vec != NULL);
 210
 211   for (i = 0; i < (pdbv->bits - 1) / 50 + 1; i++) {
 212     for (j = 0; j < 50; j++) {
 213       bit = i * 50 + j;
 214       if (bit >= pdbv->bits) {
 215         break;
 216       }
 217       test_str[j] = dbv_isset(pdbv, bit) ? '1' : '0';
 218     }
 219     test_str[j] = '\0';
 220     log_error("[%5d] %s", i, test_str);
 221   }
 222 }
 223
 224 /***************************************************************************
 225   Return whether two vectors: vec1 and vec2 have common
 226   bits. I.e. (vec1 & vec2) != 0.
 227
 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)
 233 {
 234   size_t i;
 235   fc_assert_ret_val(size1 == size2, FALSE);
 236
 237   for (i = 0; i < size1; i++) {
 238     if ((vec1[0] & vec2[0]) != 0) {
 239       return TRUE;
 240     }
 241     vec1++;
 242     vec2++;
 243   }
 244   return FALSE;
 245 }
 246
 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)
 253 {
 254   size_t i;
 255   fc_assert_ret_val(size1 == size2, FALSE);
 256
 257   for (i = 0; i < size1; i++) {
 258     if (vec1[0] != vec2[0]) {
 259       return FALSE;
 260     }
 261     vec1++;
 262     vec2++;
 263   }
 264   return TRUE;
 265 }
 266
 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)
 270
 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)
 277 {
 278   size_t i;
 279
 280   fc_assert_ret(size_to == size_from);
 281
 282   for (i = 0; i < size_to; i++) {
 283     vec_to[i] |= vec_from[i];
 284   }
 285 }