src/lib/container/bitarray.h

   1 /* Copyright (c) 2003-2004, Roger Dingledine
   2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   3  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   4 /* See LICENSE for licensing information */
   5
   6 #ifndef TOR_BITARRAY_H
   7 #define TOR_BITARRAY_H
   8
   9 /**
  10  * \file bitarray.h
  11  *
  12  * \brief Implements a variable-sized (but non-resizeable) bit-array.
  13  **/
  14
  15 #include "orconfig.h"
  16 #include <string.h>
  17 #include "lib/cc/torint.h"
  18 #include "lib/malloc/malloc.h"
  19
  20 #if SIZEOF_INT == 4
  21 #define BITARRAY_SHIFT 5
  22 #elif SIZEOF_INT == 8
  23 #define BITARRAY_SHIFT 6
  24 #else
  25 #error "int is neither 4 nor 8 bytes. I can't deal with that."
  26 #endif /* SIZEOF_INT == 4 || ... */
  27 #define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1)
  28
  29 /** A random-access array of one-bit-wide elements. */
  30 typedef unsigned int bitarray_t;
  31 /** Create a new bit array that can hold <b>n_bits</b> bits. */
  32 static inline bitarray_t *
  33 bitarray_init_zero(unsigned int n_bits)
  34 {
  35   /* round up to the next int. */
  36   size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
  37   return tor_calloc(sz, sizeof(unsigned int));
  38 }
  39 /** Expand <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>,
  40  * clearing all new bits.  Returns a possibly changed pointer to the
  41  * bitarray. */
  42 static inline bitarray_t *
  43 bitarray_expand(bitarray_t *ba,
  44                 unsigned int n_bits_old, unsigned int n_bits_new)
  45 {
  46   size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
  47   size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
  48   char *ptr;
  49   if (sz_new <= sz_old)
  50     return ba;
  51   ptr = tor_reallocarray(ba, sz_new, sizeof(unsigned int));
  52   /* This memset does nothing to the older excess bytes.  But they were
  53    * already set to 0 by bitarry_init_zero. */
  54   memset(ptr+sz_old*sizeof(unsigned int), 0,
  55          (sz_new-sz_old)*sizeof(unsigned int));
  56   return (bitarray_t*) ptr;
  57 }
  58 /** Free the bit array <b>ba</b>. */
  59 static inline void
  60 bitarray_free_(bitarray_t *ba)
  61 {
  62   tor_free(ba);
  63 }
  64 #define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_free_, (ba))
  65
  66 /** Set the <b>bit</b>th bit in <b>b</b> to 1. */
  67 static inline void
  68 bitarray_set(bitarray_t *b, int bit)
  69 {
  70   b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
  71 }
  72 /** Set the <b>bit</b>th bit in <b>b</b> to 0. */
  73 static inline void
  74 bitarray_clear(bitarray_t *b, int bit)
  75 {
  76   b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
  77 }
  78 /** Return true iff <b>bit</b>th bit in <b>b</b> is nonzero.  NOTE: does
  79  * not necessarily return 1 on true. */
  80 static inline unsigned int
  81 bitarray_is_set(bitarray_t *b, int bit)
  82 {
  83   return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
  84 }
  85
  86 #endif /* !defined(TOR_BITARRAY_H) */