char_map.h
Go to the documentation of this file.
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 
30 namespace absl {
31 namespace strings_internal {
32 
33 class 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>
134 constexpr Charmap UpperCharmap() { return Charmap::Range('A', 'Z'); }
135 constexpr Charmap LowerCharmap() { return Charmap::Range('a', 'z'); }
136 constexpr Charmap DigitCharmap() { return Charmap::Range('0', '9'); }
137 constexpr Charmap AlphaCharmap() { return LowerCharmap() | UpperCharmap(); }
138 constexpr Charmap AlnumCharmap() { return DigitCharmap() | AlphaCharmap(); }
139 constexpr Charmap XDigitCharmap() {
140  return DigitCharmap() | Charmap::Range('A', 'F') | Charmap::Range('a', 'f');
141 }
142 constexpr Charmap PrintCharmap() { return Charmap::Range(0x20, 0x7e); }
143 constexpr Charmap SpaceCharmap() { return Charmap::FromString("\t\n\v\f\r "); }
144 constexpr Charmap CntrlCharmap() {
145  return Charmap::Range(0, 0x7f) & ~PrintCharmap();
146 }
147 constexpr Charmap BlankCharmap() { return Charmap::FromString("\t "); }
148 constexpr Charmap GraphCharmap() { return PrintCharmap() & ~SpaceCharmap(); }
149 constexpr Charmap PunctCharmap() { return GraphCharmap() & ~AlnumCharmap(); }
150 
151 } // namespace strings_internal
152 } // namespace absl
153 
154 #endif // ABSL_STRINGS_INTERNAL_CHAR_MAP_H_
constexpr Charmap AlphaCharmap()
Definition: char_map.h:137
Charmap(const char *str)
Definition: char_map.h:45
constexpr bool contains(unsigned char c) const
Definition: char_map.h:49
static constexpr uint64_t RangeForWord(unsigned char lo, unsigned char hi, uint64_t word)
Definition: char_map.h:105
constexpr Charmap XDigitCharmap()
Definition: char_map.h:139
constexpr Charmap PunctCharmap()
Definition: char_map.h:149
static constexpr uint64_t CharMaskForWord(unsigned char x, uint64_t word)
Definition: char_map.h:121
static constexpr uint64_t OpenRangeFromZeroForWord(uint64_t upper, uint64_t word)
Definition: char_map.h:112
constexpr Charmap PrintCharmap()
Definition: char_map.h:142
Definition: algorithm.h:29
constexpr Charmap SpaceCharmap()
Definition: char_map.h:143
T::second_type b2
friend constexpr Charmap operator|(const Charmap &a, const Charmap &b)
Definition: char_map.h:92
constexpr Charmap BlankCharmap()
Definition: char_map.h:147
T::second_type b1
friend constexpr Charmap operator&(const Charmap &a, const Charmap &b)
Definition: char_map.h:87
constexpr Charmap AlnumCharmap()
Definition: char_map.h:138
static constexpr Charmap Range(char lo, char hi)
Definition: char_map.h:82
constexpr Charmap GraphCharmap()
Definition: char_map.h:148
bool IntersectsWith(const Charmap &c) const
Definition: char_map.h:54
constexpr Charmap UpperCharmap()
Definition: char_map.h:134
static constexpr Charmap Char(char x)
Definition: char_map.h:69
friend constexpr Charmap operator~(const Charmap &a)
Definition: char_map.h:97
constexpr Charmap LowerCharmap()
Definition: char_map.h:135
#define ABSL_ARRAYSIZE(array)
Definition: macros.h:42
constexpr Charmap(uint64_t b0, uint64_t b1, uint64_t b2, uint64_t b3)
Definition: char_map.h:102
void SetChar(unsigned char c)
Definition: char_map.h:126
uint64_t b
Definition: layout_test.cc:50
static constexpr Charmap FromString(const char *s)
Definition: char_map.h:77
constexpr Charmap DigitCharmap()
Definition: char_map.h:136
Charmap(const char *str, int len)
Definition: char_map.h:39
constexpr Charmap CntrlCharmap()
Definition: char_map.h:144


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:56