utility/bitvector.h

   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 #ifndef FC__BITVECTOR_H
  14 #define FC__BITVECTOR_H
  15
  16 #ifdef __cplusplus
  17 extern "C" {
  18 #endif /* __cplusplus */
  19
  20 #include <stdlib.h> /* size_t */
  21 #include <string.h> /* memset */
  22
  23 /* utility */
  24 #include "log.h"
  25 #include "support.h" /* bool, fc__attribute */
  26
  27 /* Yields TRUE iff the bit bit_no is set in val. */
  28 #define TEST_BIT(val, bit_no)                                               \
  29   (((val) & (1u << (bit_no))) == (1u << (bit_no)))
  30
  31 /* Dynamic bitvectors */
  32 struct dbv {
  33   int bits;
  34   unsigned char *vec;
  35 };
  36
  37 void dbv_init(struct dbv *pdbv, int bits);
  38 void dbv_resize(struct dbv *pdbv, int bits);
  39 void dbv_free(struct dbv *pdbv);
  40
  41 int dbv_bits(struct dbv *pdbv);
  42
  43 bool dbv_isset(const struct dbv *pdbv, int bit);
  44 bool dbv_isset_any(const struct dbv *pdbv);
  45
  46 void dbv_set(struct dbv *pdbv, int bit);
  47 void dbv_set_all(struct dbv *pdbv);
  48
  49 void dbv_clr(struct dbv *pdbv, int bit);
  50 void dbv_clr_all(struct dbv *pdbv);
  51
  52 bool dbv_are_equal(const struct dbv *pdbv1, const struct dbv *pdbv2);
  53
  54 void dbv_debug(struct dbv *pdbv);
  55
  56 /* Maximal size of a dynamic bitvector.
  57    Use a large value to be on the safe side (4Mbits = 512kbytes). */
  58 #define MAX_DBV_LENGTH (4 * 1024 * 1024)
  59
  60 /* Static bitvectors. */
  61 #define _BV_BYTES(bits)        ((((bits) - 1) / 8) + 1)
  62 #define _BV_BYTE_INDEX(bits)   ((bits) / 8)
  63 #define _BV_BITMASK(bit)       (1u << ((bit) & 0x7))
  64 #ifdef FREECIV_DEBUG
  65 #  define _BV_ASSERT(bv, bit)  fc_assert((bit) >= 0                         \
  66                                          && (bit) < (signed int) sizeof((bv).vec) * 8)
  67 #else
  68 #  define _BV_ASSERT(bv, bit)  (void)0
  69 #endif
  70 #define BV_ISSET(bv, bit)                                                   \
  71   (_BV_ASSERT(bv, bit),                                                     \
  72    ((bv).vec[_BV_BYTE_INDEX(bit)] & _BV_BITMASK(bit)) != 0)
  73 #define BV_SET(bv, bit)                                                     \
  74   do {                                                                      \
  75     _BV_ASSERT(bv, bit);                                                    \
  76     (bv).vec[_BV_BYTE_INDEX(bit)] |= _BV_BITMASK(bit);                      \
  77   } while (FALSE)
  78 #define BV_CLR(bv, bit)                                                     \
  79   do {                                                                      \
  80     _BV_ASSERT(bv, bit);                                                    \
  81     (bv).vec[_BV_BYTE_INDEX(bit)] &= ~_BV_BITMASK(bit);                     \
  82   } while (FALSE)
  83 #define BV_SET_VAL(bv, bit, val)                                            \
  84   do {                                                                      \
  85     if (val) { BV_SET(bv, bit); } else { BV_CLR(bv, bit); }                 \
  86   } while (FALSE);
  87 #define BV_CLR_ALL(bv)                                                      \
  88   do {                                                                      \
  89      memset((bv).vec, 0, sizeof((bv).vec));                                 \
  90   } while (FALSE)
  91 #define BV_SET_ALL(bv)                                                      \
  92   do {                                                                      \
  93     memset((bv).vec, 0xff, sizeof((bv).vec));                               \
  94   } while (FALSE)
  95
  96 bool bv_check_mask(const unsigned char *vec1, const unsigned char *vec2,
  97                    size_t size1, size_t size2);
  98 #define BV_CHECK_MASK(vec1, vec2)                                           \
  99   bv_check_mask((vec1).vec, (vec2).vec, sizeof((vec1).vec),                 \
 100                 sizeof((vec2).vec))
 101 #define BV_ISSET_ANY(vec) BV_CHECK_MASK(vec, vec)
 102
 103 bool bv_are_equal(const unsigned char *vec1, const unsigned char *vec2,
 104                   size_t size1, size_t size2);
 105 #define BV_ARE_EQUAL(vec1, vec2)                                            \
 106   bv_are_equal((vec1).vec, (vec2).vec, sizeof((vec1).vec),                  \
 107                sizeof((vec2).vec))
 108
 109 void bv_set_all_from(unsigned char *vec_to,
 110                      const unsigned char *vec_from,
 111                      size_t size_to, size_t size_from);
 112 #define BV_SET_ALL_FROM(vec_to, vec_from)                                 \
 113   bv_set_all_from((vec_to).vec, (vec_from).vec,                           \
 114                   sizeof((vec_to).vec), sizeof((vec_from).vec))
 115
 116 /* Used to make a BV typedef. Such types are usually called "bv_foo". */
 117 #define BV_DEFINE(name, bits)                                               \
 118   typedef struct { unsigned char vec[_BV_BYTES(bits)]; } name
 119
 120 #ifdef __cplusplus
 121 }
 122 #endif /* __cplusplus */
 123
 124 #endif  /* FC__BITVECTOR_H */