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>
39 class basic_string {
40   using chr_t = _CharT;
41 
42   chr_t const *data_;
43   std::size_t size_;
44 
45 public:
46   template <std::size_t N>
basic_string(chr_t const (& data)[N])47   constexpr basic_string(chr_t const (&data)[N])
48       : data_(data), size_(N - 1) {}
basic_string(chr_t const * data,std::size_t size)49   constexpr basic_string(chr_t const *data, std::size_t size)
50       : data_(data), size_(size) {}
51 
52 #ifdef FROZEN_LETITGO_HAS_STRING_VIEW
basic_string(std::basic_string_view<chr_t> data)53   constexpr basic_string(std::basic_string_view<chr_t> data)
54       : data_(data.data()), size_(data.size()) {}
55 #endif
56 
57   constexpr basic_string(const basic_string &) noexcept = default;
58   constexpr basic_string &operator=(const basic_string &) noexcept = default;
59 
size()60   constexpr std::size_t size() const { return size_; }
61 
62   constexpr chr_t operator[](std::size_t i) const { return data_[i]; }
63 
64   constexpr bool operator==(basic_string other) const {
65     if (size_ != other.size_)
66       return false;
67     for (std::size_t i = 0; i < size_; ++i)
68       if (data_[i] != other.data_[i])
69         return false;
70     return true;
71   }
72 
73   constexpr bool operator<(const basic_string &other) const {
74     unsigned i = 0;
75     while (i < size() && i < other.size()) {
76       if ((*this)[i] < other[i]) {
77         return true;
78       }
79       if ((*this)[i] > other[i]) {
80         return false;
81       }
82       ++i;
83     }
84     return size() < other.size();
85   }
86 
data()87   constexpr const chr_t *data() const { return data_; }
88 };
89 
90 template <typename _CharT> struct elsa<basic_string<_CharT>> {
91   constexpr std::size_t operator()(basic_string<_CharT> value) const {
92     std::size_t d = 5381;
93     for (std::size_t i = 0; i < value.size(); ++i)
94       d = d * 33 + 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 operator()(basic_string<_CharT> value, std::size_t seed) const {
100     std::size_t d =  (0x811c9dc5 ^ seed) * 0x01000193;
101     for (std::size_t i = 0; i < value.size(); ++i)
102       d = (d ^ value[i]) * 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 operator"" _s(const char *data, std::size_t size) {
119   return {data, size};
120 }
121 
122 constexpr wstring operator"" _s(const wchar_t *data, std::size_t size) {
123   return {data, size};
124 }
125 
126 constexpr u16string operator"" _s(const char16_t *data, std::size_t size) {
127   return {data, size};
128 }
129 
130 constexpr u32string operator"" _s(const char32_t *data, std::size_t size) {
131   return {data, size};
132 }
133 
134 #ifdef FROZEN_LETITGO_HAS_CHAR8T
135 constexpr u8string operator"" _s(const char8_t *data, std::size_t size) {
136   return {data, size};
137 }
138 #endif
139 
140 } // namespace string_literals
141 
142 } // namespace frozen
143 
144 namespace std {
145 template <typename _CharT> struct hash<frozen::basic_string<_CharT>> {
146   size_t operator()(frozen::basic_string<_CharT> s) const {
147     return frozen::elsa<frozen::basic_string<_CharT>>{}(s);
148   }
149 };
150 } // namespace std
151 
152 #endif
153