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