| 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 | 3687 | static inline size_t bitset_word_idx(unsigned char ch) | |
| 18 | { | ||
| 19 | 3687 | return ch / BITSET_WORD_BITS; | |
| 20 | } | ||
| 21 | |||
| 22 | 3687 | static inline unsigned int bitset_bit_idx(unsigned char ch) | |
| 23 | { | ||
| 24 | 3687 | return ch & BITSET_BIT_MASK; | |
| 25 | } | ||
| 26 | |||
| 27 | 2774 | static inline BitSetWord bitset_bit(unsigned char ch) | |
| 28 | { | ||
| 29 | 2774 | 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 | 1219 | static inline void bitset_add(BitSetWord *set, unsigned char ch) | |
| 39 | { | ||
| 40 | 1219 | size_t idx = bitset_word_idx(ch); | |
| 41 | 1219 | set[idx] |= bitset_bit(ch); | |
| 42 | 1219 | } | |
| 43 | |||
| 44 | 919 | static inline BitSetWord bitset_word_max(void) | |
| 45 | { | ||
| 46 | 919 | BitSetWord m = 0; | |
| 47 | 919 | return ~m; | |
| 48 | } | ||
| 49 | |||
| 50 | // Return a word in which the bit for `ch` and all higher bits are set | ||
| 51 | 913 | static inline BitSetWord bitset_start_mask(unsigned char ch) | |
| 52 | { | ||
| 53 | 913 | 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 | 913 | static inline BitSetWord bitset_end_mask(unsigned char ch) | |
| 58 | { | ||
| 59 | 913 | BitSetWord bit = bitset_bit(ch); | |
| 60 | 913 | BUG_ON(bit == 0); | |
| 61 | 913 | return bit | (bit - 1); | |
| 62 | } | ||
| 63 | |||
| 64 | 793 | static inline void bitset_add_char_range(BitSetWord *set, const unsigned char *r) | |
| 65 | { | ||
| 66 |
2/2✓ Branch 0 (16→3) taken 2133 times.
✓ Branch 1 (16→17) taken 793 times.
|
2926 | for (size_t i = 0; r[i]; i++) { |
| 67 | 2133 | unsigned int first_char = r[i]; | |
| 68 |
4/4✓ Branch 0 (3→4) taken 963 times.
✓ Branch 1 (3→5) taken 1170 times.
✓ Branch 2 (4→5) taken 49 times.
✓ Branch 3 (4→7) taken 914 times.
|
2133 | if (r[i + 1] != '-' || r[i + 2] == '\0') { |
| 69 | // Not a range; set bit for a single character | ||
| 70 | 1219 | bitset_add(set, first_char); | |
| 71 | 1219 | continue; | |
| 72 | } | ||
| 73 | |||
| 74 | 914 | i += 2; | |
| 75 | 914 | unsigned int last_char = r[i]; | |
| 76 |
2/2✓ Branch 0 (7→8) taken 1 times.
✓ Branch 1 (7→9) taken 913 times.
|
914 | if (unlikely(first_char > last_char)) { |
| 77 | 1 | continue; | |
| 78 | } | ||
| 79 | |||
| 80 | 913 | size_t first_word = bitset_word_idx(first_char); | |
| 81 | 913 | size_t last_word = bitset_word_idx(last_char); | |
| 82 | 913 | BitSetWord start_mask = bitset_start_mask(first_char); | |
| 83 | 913 | BitSetWord end_mask = bitset_end_mask(last_char); | |
| 84 | |||
| 85 |
2/2✓ Branch 0 (10→11) taken 894 times.
✓ Branch 1 (10→12) taken 19 times.
|
913 | if (first_word == last_word) { |
| 86 | // Only 1 word affected; use the intersection of both masks | ||
| 87 | 894 | set[first_word] |= start_mask & end_mask; | |
| 88 | 894 | 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 | 793 | } | |
| 99 | |||
| 100 | 46 | static inline void bitset_invert(BitSetWord *set, size_t nr_words) | |
| 101 | { | ||
| 102 |
2/2✓ Branch 0 (4→3) taken 184 times.
✓ Branch 1 (4→5) taken 46 times.
|
230 | for (size_t i = 0; i < nr_words; i++) { |
| 103 | 184 | set[i] = ~set[i]; | |
| 104 | } | ||
| 105 | 46 | } | |
| 106 | |||
| 107 | #endif | ||
| 108 |