Line data    Source code

       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        5939 : bitarray_init_zero(unsigned int n_bits)
      34             : {
      35             :   /* round up to the next int. */
      36        5939 :   size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
      37        5939 :   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        6207 : bitarray_free_(bitarray_t *ba)
      61             : {
      62        6207 :   tor_free(ba);
      63        6207 : }
      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      154426 : bitarray_set(bitarray_t *b, int bit)
      69             : {
      70      154426 :   b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
      71      154426 : }
      72             : /** Set the <b>bit</b>th bit in <b>b</b> to 0. */
      73             : static inline void
      74        2943 : bitarray_clear(bitarray_t *b, int bit)
      75             : {
      76        2943 :   b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
      77        2943 : }
      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      312843 : bitarray_is_set(bitarray_t *b, int bit)
      82             : {
      83      312843 :   return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
      84             : }
      85             : 
      86             : #endif /* !defined(TOR_BITARRAY_H) */