/src/tor/src/lib/container/bitarray.h
Line | Count | Source |
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 | 7.01M | #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 | 3.50M | #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 | 2.96k | { |
35 | | /* round up to the next int. */ |
36 | 2.96k | size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; |
37 | 2.96k | return tor_calloc(sz, sizeof(unsigned int)); |
38 | 2.96k | } Unexecuted instantiation: entrynodes.c:bitarray_init_zero Unexecuted instantiation: node_select.c:bitarray_init_zero Unexecuted instantiation: nodelist.c:bitarray_init_zero Unexecuted instantiation: predict_ports.c:bitarray_init_zero Unexecuted instantiation: routerlist.c:bitarray_init_zero Unexecuted instantiation: routerset.c:bitarray_init_zero Unexecuted instantiation: address_set.c:bitarray_init_zero Unexecuted instantiation: confmgt.c:bitarray_init_zero Unexecuted instantiation: bloomfilt.c:bitarray_init_zero Unexecuted instantiation: digestset.c:bitarray_init_zero Unexecuted instantiation: pubsub_check.c:bitarray_init_zero consdiff.c:bitarray_init_zero Line | Count | Source | 34 | 2.96k | { | 35 | | /* round up to the next int. */ | 36 | 2.96k | size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; | 37 | 2.96k | return tor_calloc(sz, sizeof(unsigned int)); | 38 | 2.96k | } |
Unexecuted instantiation: fuzz_diff_apply.c:bitarray_init_zero Unexecuted instantiation: fuzz_diff.c:bitarray_init_zero |
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 | 0 | { |
46 | 0 | size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT; |
47 | 0 | size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT; |
48 | 0 | char *ptr; |
49 | 0 | if (sz_new <= sz_old) |
50 | 0 | return ba; |
51 | 0 | ptr = tor_reallocarray(ba, sz_new, sizeof(unsigned int)); |
52 | 0 | /* This memset does nothing to the older excess bytes. But they were |
53 | 0 | * already set to 0 by bitarry_init_zero. */ |
54 | 0 | memset(ptr+sz_old*sizeof(unsigned int), 0, |
55 | 0 | (sz_new-sz_old)*sizeof(unsigned int)); |
56 | 0 | return (bitarray_t*) ptr; |
57 | 0 | } Unexecuted instantiation: entrynodes.c:bitarray_expand Unexecuted instantiation: node_select.c:bitarray_expand Unexecuted instantiation: nodelist.c:bitarray_expand Unexecuted instantiation: predict_ports.c:bitarray_expand Unexecuted instantiation: routerlist.c:bitarray_expand Unexecuted instantiation: routerset.c:bitarray_expand Unexecuted instantiation: address_set.c:bitarray_expand Unexecuted instantiation: confmgt.c:bitarray_expand Unexecuted instantiation: bloomfilt.c:bitarray_expand Unexecuted instantiation: digestset.c:bitarray_expand Unexecuted instantiation: pubsub_check.c:bitarray_expand Unexecuted instantiation: consdiff.c:bitarray_expand Unexecuted instantiation: fuzz_diff_apply.c:bitarray_expand Unexecuted instantiation: fuzz_diff.c:bitarray_expand |
58 | | /** Free the bit array <b>ba</b>. */ |
59 | | static inline void |
60 | | bitarray_free_(bitarray_t *ba) |
61 | 2.96k | { |
62 | 2.96k | tor_free(ba); |
63 | 2.96k | } Unexecuted instantiation: entrynodes.c:bitarray_free_ Unexecuted instantiation: node_select.c:bitarray_free_ Unexecuted instantiation: nodelist.c:bitarray_free_ Unexecuted instantiation: predict_ports.c:bitarray_free_ Unexecuted instantiation: routerlist.c:bitarray_free_ Unexecuted instantiation: routerset.c:bitarray_free_ Unexecuted instantiation: address_set.c:bitarray_free_ Unexecuted instantiation: confmgt.c:bitarray_free_ Unexecuted instantiation: bloomfilt.c:bitarray_free_ Unexecuted instantiation: digestset.c:bitarray_free_ Unexecuted instantiation: pubsub_check.c:bitarray_free_ consdiff.c:bitarray_free_ Line | Count | Source | 61 | 2.96k | { | 62 | | tor_free(ba); | 63 | 2.96k | } |
Unexecuted instantiation: fuzz_diff_apply.c:bitarray_free_ Unexecuted instantiation: fuzz_diff.c:bitarray_free_ |
64 | 2.96k | #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 | 1.64M | { |
70 | 1.64M | b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); |
71 | 1.64M | } Unexecuted instantiation: entrynodes.c:bitarray_set Unexecuted instantiation: node_select.c:bitarray_set Unexecuted instantiation: nodelist.c:bitarray_set Unexecuted instantiation: predict_ports.c:bitarray_set Unexecuted instantiation: routerlist.c:bitarray_set Unexecuted instantiation: routerset.c:bitarray_set Unexecuted instantiation: address_set.c:bitarray_set Unexecuted instantiation: confmgt.c:bitarray_set Unexecuted instantiation: bloomfilt.c:bitarray_set Unexecuted instantiation: digestset.c:bitarray_set Unexecuted instantiation: pubsub_check.c:bitarray_set Line | Count | Source | 69 | 1.64M | { | 70 | 1.64M | b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); | 71 | 1.64M | } |
Unexecuted instantiation: fuzz_diff_apply.c:bitarray_set Unexecuted instantiation: fuzz_diff.c:bitarray_set |
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 | 0 | { |
76 | 0 | b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); |
77 | 0 | } Unexecuted instantiation: entrynodes.c:bitarray_clear Unexecuted instantiation: node_select.c:bitarray_clear Unexecuted instantiation: nodelist.c:bitarray_clear Unexecuted instantiation: predict_ports.c:bitarray_clear Unexecuted instantiation: routerlist.c:bitarray_clear Unexecuted instantiation: routerset.c:bitarray_clear Unexecuted instantiation: address_set.c:bitarray_clear Unexecuted instantiation: confmgt.c:bitarray_clear Unexecuted instantiation: bloomfilt.c:bitarray_clear Unexecuted instantiation: digestset.c:bitarray_clear Unexecuted instantiation: pubsub_check.c:bitarray_clear Unexecuted instantiation: consdiff.c:bitarray_clear Unexecuted instantiation: fuzz_diff_apply.c:bitarray_clear Unexecuted instantiation: fuzz_diff.c:bitarray_clear |
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 | 1.86M | { |
83 | 1.86M | return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); |
84 | 1.86M | } Unexecuted instantiation: entrynodes.c:bitarray_is_set Unexecuted instantiation: node_select.c:bitarray_is_set Unexecuted instantiation: nodelist.c:bitarray_is_set Unexecuted instantiation: predict_ports.c:bitarray_is_set Unexecuted instantiation: routerlist.c:bitarray_is_set Unexecuted instantiation: routerset.c:bitarray_is_set Unexecuted instantiation: address_set.c:bitarray_is_set Unexecuted instantiation: confmgt.c:bitarray_is_set Unexecuted instantiation: bloomfilt.c:bitarray_is_set Unexecuted instantiation: digestset.c:bitarray_is_set Unexecuted instantiation: pubsub_check.c:bitarray_is_set consdiff.c:bitarray_is_set Line | Count | Source | 82 | 1.86M | { | 83 | 1.86M | return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); | 84 | 1.86M | } |
Unexecuted instantiation: fuzz_diff_apply.c:bitarray_is_set Unexecuted instantiation: fuzz_diff.c:bitarray_is_set |
85 | | |
86 | | #endif /* !defined(TOR_BITARRAY_H) */ |