Tor  0.4.7.0-alpha-dev
bitarray.h
Go to the documentation of this file.
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 *
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
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
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
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
82 {
83  return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
84 }
85 
86 #endif /* !defined(TOR_BITARRAY_H) */
unsigned int bitarray_t
Definition: bitarray.h:30
static void bitarray_set(bitarray_t *b, int bit)
Definition: bitarray.h:68
static unsigned int bitarray_is_set(bitarray_t *b, int bit)
Definition: bitarray.h:81
static void bitarray_free_(bitarray_t *ba)
Definition: bitarray.h:60
static void bitarray_clear(bitarray_t *b, int bit)
Definition: bitarray.h:74
static bitarray_t * bitarray_expand(bitarray_t *ba, unsigned int n_bits_old, unsigned int n_bits_new)
Definition: bitarray.h:43
static bitarray_t * bitarray_init_zero(unsigned int n_bits)
Definition: bitarray.h:33
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
Integer definitions used throughout Tor.