dte test coverage

Directory: ./
File: src/syntax/bitset.h
Date: 2025-02-14 16:55:22
Exec Total Coverage
Lines: 48 48 100.0%
Functions: 10 10 100.0%
Branches: 14 14 100.0%
Line Branch Exec Source
1 #ifndef SYNTAX_BITSET_H
2 #define SYNTAX_BITSET_H
3
4 #include <limits.h>
5 #include <stdbool.h>
6 #include <stddef.h>
7 #include "util/debug.h"
8 #include "util/macros.h"
9
10 #define BITSET_WORD_BITS BITSIZE(BitSetWord)
11 #define BITSET_BIT_MASK (BITSET_WORD_BITS - 1)
12 #define BITSET_NR_WORDS(bits) (((bits) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
13 #define BITSET_INVERT(set) bitset_invert(set, ARRAYLEN(set))
14
15 typedef unsigned long BitSetWord;
16
17 3663 static inline size_t bitset_word_idx(unsigned char ch)
18 {
19 3663 return ch / BITSET_WORD_BITS;
20 }
21
22 3663 static inline unsigned int bitset_bit_idx(unsigned char ch)
23 {
24 3663 return ch & BITSET_BIT_MASK;
25 }
26
27 2757 static inline BitSetWord bitset_bit(unsigned char ch)
28 {
29 2757 return ((BitSetWord)1) << bitset_bit_idx(ch);
30 }
31
32 642 static inline bool bitset_contains(const BitSetWord *set, unsigned char ch)
33 {
34 642 size_t idx = bitset_word_idx(ch);
35 642 return set[idx] & bitset_bit(ch);
36 }
37
38 1209 static inline void bitset_add(BitSetWord *set, unsigned char ch)
39 {
40 1209 size_t idx = bitset_word_idx(ch);
41 1209 set[idx] |= bitset_bit(ch);
42 1209 }
43
44 912 static inline BitSetWord bitset_word_max(void)
45 {
46 912 BitSetWord m = 0;
47 912 return ~m;
48 }
49
50 // Return a word in which the bit for `ch` and all higher bits are set
51 906 static inline BitSetWord bitset_start_mask(unsigned char ch)
52 {
53 906 return bitset_word_max() << bitset_bit_idx(ch);
54 }
55
56 // Return a word in which the bit for `ch` and all lower bits are set
57 906 static inline BitSetWord bitset_end_mask(unsigned char ch)
58 {
59 906 BitSetWord bit = bitset_bit(ch);
60 906 BUG_ON(bit == 0);
61 906 return bit | (bit - 1);
62 }
63
64 788 static inline void bitset_add_char_range(BitSetWord *set, const unsigned char *r)
65 {
66
2/2
✓ Branch 0 (16→3) taken 2116 times.
✓ Branch 1 (16→17) taken 788 times.
 2904 for (size_t i = 0; r[i]; i++) {
67 2116 unsigned int first_char = r[i];
68
4/4
✓ Branch 0 (3→4) taken 956 times.
✓ Branch 1 (3→5) taken 1160 times.
✓ Branch 2 (4→5) taken 49 times.
✓ Branch 3 (4→7) taken 907 times.
 2116 if (r[i + 1] != '-' || r[i + 2] == '\0') {
69 // Not a range; set bit for a single character
70 1209 bitset_add(set, first_char);
71 1209 continue;
72 }
73
74 907 i += 2;
75 907 unsigned int last_char = r[i];
76
2/2
✓ Branch 0 (7→8) taken 1 times.
✓ Branch 1 (7→9) taken 906 times.
 907 if (unlikely(first_char > last_char)) {
77 1 continue;
78 }
79
80 906 size_t first_word = bitset_word_idx(first_char);
81 906 size_t last_word = bitset_word_idx(last_char);
82 906 BitSetWord start_mask = bitset_start_mask(first_char);
83 906 BitSetWord end_mask = bitset_end_mask(last_char);
84
85
2/2
✓ Branch 0 (10→11) taken 887 times.
✓ Branch 1 (10→12) taken 19 times.
 906 if (first_word == last_word) {
86 // Only 1 word affected; use the intersection of both masks
87 887 set[first_word] |= start_mask & end_mask;
88 887 continue;
89 }
90
91 // Set partial ranges in first/last word, then saturate any others
92 19 set[first_word] |= start_mask;
93 19 set[last_word] |= end_mask;
94
2/2
✓ Branch 0 (14→13) taken 2 times.
✓ Branch 1 (14→15) taken 19 times.
 21 for (size_t w = first_word + 1; w < last_word; w++) {
95 2 set[w] = bitset_word_max();
96 }
97 }
98 788 }
99
100 44 static inline void bitset_invert(BitSetWord *set, size_t nr_words)
101 {
102
2/2
✓ Branch 0 (4→3) taken 176 times.
✓ Branch 1 (4→5) taken 44 times.
 220 for (size_t i = 0; i < nr_words; i++) {
103 176 set[i] = ~set[i];
104 }
105 44 }
106
107 #endif
108