1// Copyright 2017 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Character Map Class
16//
17// A fast, bit-vector map for 8-bit unsigned characters.
18// This class is useful for non-character purposes as well.
19
20#ifndef ABSL_STRINGS_INTERNAL_CHAR_MAP_H_
21#define ABSL_STRINGS_INTERNAL_CHAR_MAP_H_
22
23#include <cstddef>
24#include <cstdint>
25#include <cstring>
26
27#include "absl/base/macros.h"
28#include "absl/base/port.h"
29
30namespace absl {
31namespace strings_internal {
32
33class Charmap {
34 public:
35 constexpr Charmap() : m_() {}
36
37 // Initializes with a given char*. Note that NUL is not treated as
38 // a terminator, but rather a char to be flicked.
39 Charmap(const char* str, int len) : m_() {
40 while (len--) SetChar(*str++);
41 }
42
43 // Initializes with a given char*. NUL is treated as a terminator
44 // and will not be in the charmap.
45 explicit Charmap(const char* str) : m_() {
46 while (*str) SetChar(*str++);
47 }
48
49 constexpr bool contains(unsigned char c) const {
50 return (m_[c / 64] >> (c % 64)) & 0x1;
51 }
52
53 // Returns true if and only if a character exists in both maps.
54 bool IntersectsWith(const Charmap& c) const {
55 for (size_t i = 0; i < ABSL_ARRAYSIZE(m_); ++i) {
56 if ((m_[i] & c.m_[i]) != 0) return true;
57 }
58 return false;
59 }
60
61 bool IsZero() const {
62 for (uint64_t c : m_) {
63 if (c != 0) return false;
64 }
65 return true;
66 }
67
68 // Containing only a single specified char.
69 static constexpr Charmap Char(char x) {
70 return Charmap(CharMaskForWord(x, 0), CharMaskForWord(x, 1),
71 CharMaskForWord(x, 2), CharMaskForWord(x, 3));
72 }
73
74 // Containing all the chars in the C-std::string 's'.
75 // Note that this is expensively recursive because of the C++11 constexpr
76 // formulation. Use only in constexpr initializers.
77 static constexpr Charmap FromString(const char* s) {
78 return *s == 0 ? Charmap() : (Char(*s) | FromString(s + 1));
79 }
80
81 // Containing all the chars in the closed interval [lo,hi].
82 static constexpr Charmap Range(char lo, char hi) {
83 return Charmap(RangeForWord(lo, hi, 0), RangeForWord(lo, hi, 1),
84 RangeForWord(lo, hi, 2), RangeForWord(lo, hi, 3));
85 }
86
87 friend constexpr Charmap operator&(const Charmap& a, const Charmap& b) {
88 return Charmap(a.m_[0] & b.m_[0], a.m_[1] & b.m_[1], a.m_[2] & b.m_[2],
89 a.m_[3] & b.m_[3]);
90 }
91
92 friend constexpr Charmap operator|(const Charmap& a, const Charmap& b) {
93 return Charmap(a.m_[0] | b.m_[0], a.m_[1] | b.m_[1], a.m_[2] | b.m_[2],
94 a.m_[3] | b.m_[3]);
95 }
96
97 friend constexpr Charmap operator~(const Charmap& a) {
98 return Charmap(~a.m_[0], ~a.m_[1], ~a.m_[2], ~a.m_[3]);
99 }
100
101 private:
102 constexpr Charmap(uint64_t b0, uint64_t b1, uint64_t b2, uint64_t b3)
103 : m_{b0, b1, b2, b3} {}
104
105 static constexpr uint64_t RangeForWord(unsigned char lo, unsigned char hi,
106 uint64_t word) {
107 return OpenRangeFromZeroForWord(hi + 1, word) &
108 ~OpenRangeFromZeroForWord(lo, word);
109 }
110
111 // All the chars in the specified word of the range [0, upper).
112 static constexpr uint64_t OpenRangeFromZeroForWord(uint64_t upper,
113 uint64_t word) {
114 return (upper <= 64 * word)
115 ? 0
116 : (upper >= 64 * (word + 1))
117 ? ~static_cast<uint64_t>(0)
118 : (~static_cast<uint64_t>(0) >> (64 - upper % 64));
119 }
120
121 static constexpr uint64_t CharMaskForWord(unsigned char x, uint64_t word) {
122 return (x / 64 == word) ? (static_cast<uint64_t>(1) << (x % 64)) : 0;
123 }
124
125 private:
126 void SetChar(unsigned char c) {
127 m_[c / 64] |= static_cast<uint64_t>(1) << (c % 64);
128 }
129
130 uint64_t m_[4];
131};
132
133// Mirror the char-classifying predicates in <cctype>
134constexpr Charmap UpperCharmap() { return Charmap::Range('A', 'Z'); }
135constexpr Charmap LowerCharmap() { return Charmap::Range('a', 'z'); }
136constexpr Charmap DigitCharmap() { return Charmap::Range('0', '9'); }
137constexpr Charmap AlphaCharmap() { return LowerCharmap() | UpperCharmap(); }
138constexpr Charmap AlnumCharmap() { return DigitCharmap() | AlphaCharmap(); }
139constexpr Charmap XDigitCharmap() {
140 return DigitCharmap() | Charmap::Range('A', 'F') | Charmap::Range('a', 'f');
141}
142constexpr Charmap PrintCharmap() { return Charmap::Range(0x20, 0x7e); }
143constexpr Charmap SpaceCharmap() { return Charmap::FromString("\t\n\v\f\r "); }
144constexpr Charmap CntrlCharmap() {
145 return Charmap::Range(0, 0x7f) & ~PrintCharmap();
146}
147constexpr Charmap BlankCharmap() { return Charmap::FromString("\t "); }
148constexpr Charmap GraphCharmap() { return PrintCharmap() & ~SpaceCharmap(); }
149constexpr Charmap PunctCharmap() { return GraphCharmap() & ~AlnumCharmap(); }
150
151} // namespace strings_internal
152} // namespace absl
153
154#endif // ABSL_STRINGS_INTERNAL_CHAR_MAP_H_
155