tor

The Tor anonymity network
git clone https://git.dasho.dev/tor.git
Log | Files | Refs | README | LICENSE

bitarray.h (2647B)

      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) */