Debian Codegraph @

src/perfect-hashing/frozen/string.h

raw
1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_LETITGO_STRING_H
24 #define FROZEN_LETITGO_STRING_H
25
26 #include "frozen/bits/elsa.h"
27 #include "frozen/bits/version.h"
28 #include "frozen/bits/defines.h"
29
30 #include <functional>
31
32 #ifdef FROZEN_LETITGO_HAS_STRING_VIEW
33 #include <string_view>
34 #endif
35
36 namespace frozen {
37
38 template <typename _CharT> class basic_string {
39 using chr_t = _CharT;
40
41 chr_t const *data_;
42 std::size_t size_;
43
44 public:
45 template <std::size_t N> constexpr basic_string(chr_t const (&data)[N]) : data_(data), size_(N - 1) {}
46 constexpr basic_string(chr_t const *data, std::size_t size) : data_(data), size_(size) {}
47
48 #ifdef FROZEN_LETITGO_HAS_STRING_VIEW
49 constexpr basic_string(std::basic_string_view<chr_t> data) : data_(data.data()), size_(data.size()) {}
50 #endif
51
52 constexpr basic_string(const basic_string &) noexcept = default;
53 constexpr basic_string &operator=(const basic_string &) noexcept = default;
54
55 constexpr std::size_t
56 size() const {
57 return size_;
58 }
59
60 constexpr chr_t
61 operator[](std::size_t i) const {
62 return data_[i];
63 }
64
65 constexpr bool
66 operator==(basic_string other) const {
67 if (size_ != other.size_) return false;
68 for (std::size_t i = 0; i < size_; ++i)
69 if (data_[i] != other.data_[i]) return false;
70 return true;
71 }
72
73 constexpr bool
74 operator<(const basic_string &other) const {
75 unsigned i = 0;
76 while (i < size() && i < other.size()) {
77 if ((*this)[i] < other[i]) { return true; }
78 if ((*this)[i] > other[i]) { return false; }
79 ++i;
80 }
81 return size() < other.size();
82 }
83
84 constexpr const chr_t *
85 data() const {
86 return data_;
87 }
88 };
89
90 template <typename _CharT> struct elsa<basic_string<_CharT>> {
91 constexpr std::size_t
92 operator()(basic_string<_CharT> value) const {
93 std::size_t d = 5381;
94 for (std::size_t i = 0; i < value.size(); ++i) d = d * 33 + static_cast<size_t>(value[i]);
95 return d;
96 }
97 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
98 // With the lowest bits removed, based on experimental setup.
99 constexpr std::size_t
100 operator()(basic_string<_CharT> value, std::size_t seed) const {
101 std::size_t d = (0x811c9dc5 ^ seed) * static_cast<size_t>(0x01000193);
102 for (std::size_t i = 0; i < value.size(); ++i) d = (d ^ static_cast<size_t>(value[i])) * static_cast<size_t>(0x01000193);
103 return d >> 8;
104 }
105 };
106
107 using string = basic_string<char>;
108 using wstring = basic_string<wchar_t>;
109 using u16string = basic_string<char16_t>;
110 using u32string = basic_string<char32_t>;
111
112 #ifdef FROZEN_LETITGO_HAS_CHAR8T
113 using u8string = basic_string<char8_t>;
114 #endif
115
116 namespace string_literals {
117
118 constexpr string
119 operator"" _s(const char *data, std::size_t size) {
120 return {data, size};
121 }
122
123 constexpr wstring
124 operator"" _s(const wchar_t *data, std::size_t size) {
125 return {data, size};
126 }
127
128 constexpr u16string
129 operator"" _s(const char16_t *data, std::size_t size) {
130 return {data, size};
131 }
132
133 constexpr u32string
134 operator"" _s(const char32_t *data, std::size_t size) {
135 return {data, size};
136 }
137
138 #ifdef FROZEN_LETITGO_HAS_CHAR8T
139 constexpr u8string
140 operator"" _s(const char8_t *data, std::size_t size) {
141 return {data, size};
142 }
143 #endif
144
145 } // namespace string_literals
146
147 } // namespace frozen
148
149 namespace std {
150 template <typename _CharT> struct hash<frozen::basic_string<_CharT>> {
151 size_t
152 operator()(frozen::basic_string<_CharT> s) const {
153 return frozen::elsa<frozen::basic_string<_CharT>>{}(s);
154 }
155 };
156 } // namespace std
157
158 #endif