diff options
Diffstat (limited to '')
| -rw-r--r-- | contrib/frozen/AUTHORS | 3 | ||||
| -rw-r--r-- | contrib/frozen/CMakeLists.txt | 12 | ||||
| -rw-r--r-- | contrib/frozen/LICENSE | 202 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/algorithm.h | 197 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/algorithms.h | 229 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/basic_types.h | 200 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/constexpr_assert.h | 40 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/defines.h | 58 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/elsa.h | 50 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/exceptions.h | 39 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/pmh.h | 240 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/bits/version.h | 30 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/map.h | 323 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/random.h | 90 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/set.h | 220 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/string.h | 152 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/unordered_map.h | 197 | ||||
| -rw-r--r-- | contrib/frozen/include/frozen/unordered_set.h | 147 |
18 files changed, 2429 insertions, 0 deletions
diff --git a/contrib/frozen/AUTHORS b/contrib/frozen/AUTHORS new file mode 100644 index 0000000..d83d0f8 --- /dev/null +++ b/contrib/frozen/AUTHORS @@ -0,0 +1,3 @@ +serge-sans-paille <sguelton@quarkslab.com> +Jérôme Dumesnil <jerome.dumesnil@gmail.com> +Chris Beck <chbeck@tesla.com> diff --git a/contrib/frozen/CMakeLists.txt b/contrib/frozen/CMakeLists.txt new file mode 100644 index 0000000..185378d --- /dev/null +++ b/contrib/frozen/CMakeLists.txt @@ -0,0 +1,12 @@ +target_sources(frozen-headers INTERFACE + "${prefix}/frozen/algorithm.h" + "${prefix}/frozen/map.h" + "${prefix}/frozen/random.h" + "${prefix}/frozen/set.h" + "${prefix}/frozen/string.h" + "${prefix}/frozen/unordered_map.h" + "${prefix}/frozen/unordered_set.h" + "${prefix}/frozen/bits/algorithms.h" + "${prefix}/frozen/bits/basic_types.h" + "${prefix}/frozen/bits/elsa.h" + "${prefix}/frozen/bits/pmh.h") diff --git a/contrib/frozen/LICENSE b/contrib/frozen/LICENSE new file mode 100644 index 0000000..5b4b9bd --- /dev/null +++ b/contrib/frozen/LICENSE @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright 2017 Quarkslab + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/contrib/frozen/include/frozen/algorithm.h b/contrib/frozen/include/frozen/algorithm.h new file mode 100644 index 0000000..a543eb3 --- /dev/null +++ b/contrib/frozen/include/frozen/algorithm.h @@ -0,0 +1,197 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_ALGORITHM_H +#define FROZEN_LETITGO_ALGORITHM_H + +#include "frozen/bits/basic_types.h" +#include "frozen/bits/version.h" +#include "frozen/string.h" + +namespace frozen { + +// 'search' implementation if C++17 is not available +// https://en.cppreference.com/w/cpp/algorithm/search +template<class ForwardIterator, class Searcher> +ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher & searcher) +{ + return searcher(first, last).first; +} + +// text book implementation from +// https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm + +template <std::size_t size> class knuth_morris_pratt_searcher { + bits::carray<std::ptrdiff_t, size> step_; + bits::carray<char, size> needle_; + + static constexpr bits::carray<std::ptrdiff_t, size> + build_kmp_cache(char const (&needle)[size + 1]) { + std::ptrdiff_t cnd = 0; + bits::carray<std::ptrdiff_t, size> cache; + + cache.fill(-1); + for (std::size_t pos = 1; pos < size; ++pos) { + if (needle[pos] == needle[cnd]) { + cache[pos] = cache[cnd]; + cnd += 1; + } else { + cache[pos] = cnd; + cnd = cache[cnd]; + while (cnd >= 0 && needle[pos] != needle[cnd]) + cnd = cache[cnd]; + cnd += 1; + } + } + return cache; + } + +public: + constexpr knuth_morris_pratt_searcher(char const (&needle)[size + 1]) + : step_{build_kmp_cache(needle)}, needle_(needle) {} + + template <class ForwardIterator> + constexpr std::pair<ForwardIterator, ForwardIterator> operator()(ForwardIterator first, ForwardIterator last) const { + std::size_t i = 0; + ForwardIterator iter = first; + while (iter != last) { + if (needle_[i] == *iter) { + if (i == (size - 1)) + return { iter - i, iter - i + size }; + ++i; + ++iter; + } else { + if (step_[i] > -1) { + i = step_[i]; + } else { + ++iter; + i = 0; + } + } + } + return { last, last }; + } +}; + +template <std::size_t N> +constexpr knuth_morris_pratt_searcher<N - 1> make_knuth_morris_pratt_searcher(char const (&needle)[N]) { + return {needle}; +} + +// text book implementation from +// https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm + +template <std::size_t size> class boyer_moore_searcher { + using skip_table_type = bits::carray<std::ptrdiff_t, sizeof(char) << 8>; + using suffix_table_type = bits::carray<std::ptrdiff_t, size>; + + skip_table_type skip_table_; + suffix_table_type suffix_table_; + bits::carray<char, size> needle_; + + constexpr auto build_skip_table(char const (&needle)[size + 1]) { + skip_table_type skip_table; + + skip_table.fill(size); + for (std::size_t i = 0; i < size - 1; ++i) + skip_table[needle[i]] -= i + 1; + return skip_table; + } + + constexpr bool is_prefix(char const (&needle)[size + 1], std::size_t pos) { + std::size_t suffixlen = size - pos; + + for (std::size_t i = 0; i < suffixlen; i++) { + if (needle[i] != needle[pos + i]) + return false; + } + return true; + } + + constexpr std::size_t suffix_length(char const (&needle)[size + 1], + std::size_t pos) { + // increment suffix length slen to the first mismatch or beginning + // of the word + for (std::size_t slen = 0; slen < pos ; slen++) + if (needle[pos - slen] != needle[size - 1 - slen]) + return slen; + + return pos; + } + + constexpr auto build_suffix_table(char const (&needle)[size + 1]) { + suffix_table_type suffix; + std::ptrdiff_t last_prefix_index = size - 1; + + // first loop + for (std::ptrdiff_t p = size - 1; p >= 0; p--) { + if (is_prefix(needle, p + 1)) + last_prefix_index = p + 1; + + suffix[p] = last_prefix_index + (size - 1 - p); + } + + // second loop + for (std::size_t p = 0; p < size - 1; p++) { + auto slen = suffix_length(needle, p); + if (needle[p - slen] != needle[size - 1 - slen]) + suffix[size - 1 - slen] = size - 1 - p + slen; + + } + return suffix; + } + +public: + constexpr boyer_moore_searcher(char const (&needle)[size + 1]) + : skip_table_{build_skip_table(needle)}, + suffix_table_{build_suffix_table(needle)}, + needle_(needle) {} + + template <class ForwardIterator> + constexpr std::pair<ForwardIterator, ForwardIterator> operator()(ForwardIterator first, ForwardIterator last) const { + if (size == 0) + return { first, first + size }; + + ForwardIterator iter = first + size - 1; + while (iter < last) { + std::ptrdiff_t j = size - 1; + while (j > 0 && (*iter == needle_[j])) { + --iter; + --j; + } + if (*iter == needle_[0]) + return { iter, iter + size}; + + iter += std::max(skip_table_[*iter], suffix_table_[j]); + } + return { last, last + size}; + } +}; + +template <std::size_t N> +constexpr boyer_moore_searcher<N - 1> make_boyer_moore_searcher(char const (&needle)[N]) { + return {needle}; +} + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/bits/algorithms.h b/contrib/frozen/include/frozen/bits/algorithms.h new file mode 100644 index 0000000..8d1ffbc --- /dev/null +++ b/contrib/frozen/include/frozen/bits/algorithms.h @@ -0,0 +1,229 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_BITS_ALGORITHMS_H +#define FROZEN_LETITGO_BITS_ALGORITHMS_H + +#include "frozen/bits/basic_types.h" + +#include <limits> +#include <tuple> + +namespace frozen { + +namespace bits { + +auto constexpr next_highest_power_of_two(std::size_t v) { + // https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 + constexpr auto trip_count = std::numeric_limits<decltype(v)>::digits; + v--; + for(std::size_t i = 1; i < trip_count; i <<= 1) + v |= v >> i; + v++; + return v; +} + +template<class T> +auto constexpr log(T v) { + std::size_t n = 0; + while (v > 1) { + n += 1; + v >>= 1; + } + return n; +} + +constexpr std::size_t bit_weight(std::size_t n) { + return (n <= 8*sizeof(unsigned int)) + + (n <= 8*sizeof(unsigned long)) + + (n <= 8*sizeof(unsigned long long)) + + (n <= 128); +} + +unsigned int select_uint_least(std::integral_constant<std::size_t, 4>); +unsigned long select_uint_least(std::integral_constant<std::size_t, 3>); +unsigned long long select_uint_least(std::integral_constant<std::size_t, 2>); +template<std::size_t N> +unsigned long long select_uint_least(std::integral_constant<std::size_t, N>) { + static_assert(N < 2, "unsupported type size"); + return {}; +} + + +template<std::size_t N> +using select_uint_least_t = decltype(select_uint_least(std::integral_constant<std::size_t, bit_weight(N)>())); + +template <typename Iter, typename Compare> +constexpr auto min_element(Iter begin, const Iter end, + Compare const &compare) { + auto result = begin; + while (begin != end) { + if (compare(*begin, *result)) { + result = begin; + } + ++begin; + } + return result; +} + +template <class T> +constexpr void cswap(T &a, T &b) { + auto tmp = a; + a = b; + b = tmp; +} + +template <class T, class U> +constexpr void cswap(std::pair<T, U> & a, std::pair<T, U> & b) { + cswap(a.first, b.first); + cswap(a.second, b.second); +} + +template <class... Tys, std::size_t... Is> +constexpr void cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b, std::index_sequence<Is...>) { + using swallow = int[]; + (void) swallow{(cswap(std::get<Is>(a), std::get<Is>(b)), 0)...}; +} + +template <class... Tys> +constexpr void cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b) { + cswap(a, b, std::make_index_sequence<sizeof...(Tys)>()); +} + +template <typename Iterator, class Compare> +constexpr Iterator partition(Iterator left, Iterator right, Compare const &compare) { + auto pivot = left + (right - left) / 2; + auto value = *pivot; + cswap(*right, *pivot); + for (auto it = left; 0 < right - it; ++it) { + if (compare(*it, value)) { + cswap(*it, *left); + left++; + } + } + cswap(*right, *left); + return left; +} + +template <typename Iterator, class Compare> +constexpr void quicksort(Iterator left, Iterator right, Compare const &compare) { + while (0 < right - left) { + auto new_pivot = bits::partition(left, right, compare); + quicksort(left, new_pivot, compare); + left = new_pivot + 1; + } +} + +template <typename T, std::size_t N, class Compare> +constexpr bits::carray<T, N> quicksort(bits::carray<T, N> const &array, + Compare const &compare) { + bits::carray<T, N> res = array; + quicksort(res.begin(), res.end() - 1, compare); + return res; +} + +template <class T, class Compare> struct LowerBound { + T const &value_; + Compare const &compare_; + constexpr LowerBound(T const &value, Compare const &compare) + : value_(value), compare_(compare) {} + + template <class ForwardIt> + inline constexpr ForwardIt doit_fast(ForwardIt first, + std::integral_constant<std::size_t, 0>) { + return first; + } + + template <class ForwardIt, std::size_t N> + inline constexpr ForwardIt doit_fast(ForwardIt first, + std::integral_constant<std::size_t, N>) { + auto constexpr step = N / 2; + static_assert(N/2 == N - N / 2 - 1, "power of two minus 1"); + auto it = first + step; + auto next_it = compare_(*it, value_) ? it + 1 : first; + return doit_fast(next_it, std::integral_constant<std::size_t, N / 2>{}); + } + + template <class ForwardIt, std::size_t N> + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, true>) { + return doit_fast(first, std::integral_constant<std::size_t, N>{}); + } + + template <class ForwardIt, std::size_t N> + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, false>) { + auto constexpr next_power = next_highest_power_of_two(N); + auto constexpr next_start = next_power / 2 - 1; + auto it = first + next_start; + if (compare_(*it, value_)) { + auto constexpr next = N - next_start - 1; + return doitfirst(it + 1, std::integral_constant<std::size_t, next>{}, std::integral_constant<bool, next_highest_power_of_two(next) - 1 == next>{}); + } + else + return doit_fast(first, std::integral_constant<std::size_t, next_start>{}); + } + + template <class ForwardIt> + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, 1>, std::integral_constant<bool, false>) { + return doit_fast(first, std::integral_constant<std::size_t, 1>{}); + } +}; + +template <std::size_t N, class ForwardIt, class T, class Compare> +constexpr ForwardIt lower_bound(ForwardIt first, const T &value, Compare const &compare) { + return LowerBound<T, Compare>{value, compare}.doitfirst(first, std::integral_constant<std::size_t, N>{}, std::integral_constant<bool, next_highest_power_of_two(N) - 1 == N>{}); +} + +template <std::size_t N, class Compare, class ForwardIt, class T> +constexpr bool binary_search(ForwardIt first, const T &value, + Compare const &compare) { + ForwardIt where = lower_bound<N>(first, value, compare); + return (!(where == first + N) && !(compare(value, *where))); +} + + +template<class InputIt1, class InputIt2> +constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) +{ + for (; first1 != last1; ++first1, ++first2) { + if (!(*first1 == *first2)) { + return false; + } + } + return true; +} + +template<class InputIt1, class InputIt2> +constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) +{ + for (; (first1 != last1) && (first2 != last2); ++first1, ++first2) { + if (*first1 < *first2) + return true; + if (*first2 < *first1) + return false; + } + return (first1 == last1) && (first2 != last2); +} + +} // namespace bits +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/bits/basic_types.h b/contrib/frozen/include/frozen/bits/basic_types.h new file mode 100644 index 0000000..9814bac --- /dev/null +++ b/contrib/frozen/include/frozen/bits/basic_types.h @@ -0,0 +1,200 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_BASIC_TYPES_H +#define FROZEN_LETITGO_BASIC_TYPES_H + +#include "frozen/bits/exceptions.h" + +#include <utility> +#include <iterator> +#include <string> + +namespace frozen { + +namespace bits { + +// used as a fake argument for frozen::make_set and frozen::make_map in the case of N=0 +struct ignored_arg {}; + +template <class T, std::size_t N> +class cvector { + T data [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise + std::size_t dsize = 0; + +public: + // Container typdefs + using value_type = T; + using reference = value_type &; + using const_reference = const value_type &; + using pointer = value_type *; + using const_pointer = const value_type *; + using iterator = pointer; + using const_iterator = const_pointer; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + + // Constructors + constexpr cvector(void) = default; + constexpr cvector(size_type count, const T& value) : dsize(count) { + for (std::size_t i = 0; i < N; ++i) + data[i] = value; + } + + // Iterators + constexpr iterator begin() noexcept { return data; } + constexpr iterator end() noexcept { return data + dsize; } + + // Capacity + constexpr size_type size() const { return dsize; } + + // Element access + constexpr reference operator[](std::size_t index) { return data[index]; } + constexpr const_reference operator[](std::size_t index) const { return data[index]; } + + constexpr reference back() { return data[dsize - 1]; } + constexpr const_reference back() const { return data[dsize - 1]; } + + // Modifiers + constexpr void push_back(const T & a) { data[dsize++] = a; } + constexpr void push_back(T && a) { data[dsize++] = std::move(a); } + constexpr void pop_back() { --dsize; } + + constexpr void clear() { dsize = 0; } +}; + +template <class T, std::size_t N> +class carray { + T data_ [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise + + template <std::size_t M, std::size_t... I> + constexpr carray(T const (&init)[M], std::index_sequence<I...>) + : data_{init[I]...} {} + template <class Iter, std::size_t... I> + constexpr carray(Iter iter, std::index_sequence<I...>) + : data_{((void)I, *iter++)...} {} + +public: + // Container typdefs + using value_type = T; + using reference = value_type &; + using const_reference = const value_type &; + using pointer = value_type *; + using const_pointer = const value_type *; + using iterator = pointer; + using const_iterator = const_pointer; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + + // Constructors + constexpr carray(void) = default; + template <std::size_t M> + constexpr carray(T const (&init)[M]) + : carray(init, std::make_index_sequence<N>()) + { + static_assert(M >= N, "Cannot initialize a carray with an smaller array"); + } + constexpr carray(std::initializer_list<T> init) + : carray(init.begin(), std::make_index_sequence<N>()) + { + // clang & gcc doesn't recognize init.size() as a constexpr + // static_assert(init.size() >= N, "Cannot initialize a carray with an smaller initializer list"); + } + + // Iterators + constexpr iterator begin() noexcept { return data_; } + constexpr const_iterator begin() const noexcept { return data_; } + constexpr const_iterator cbegin() const noexcept { return data_; } + constexpr iterator end() noexcept { return data_ + N; } + constexpr const_iterator end() const noexcept { return data_ + N; } + constexpr const_iterator cend() const noexcept { return data_ + N; } + + constexpr reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } + constexpr const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } + constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } + constexpr reverse_iterator rend() noexcept { return reverse_iterator(begin()); } + constexpr const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } + constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } + + // Capacity + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + // Element access + constexpr reference operator[](std::size_t index) { return data_[index]; } + constexpr const_reference operator[](std::size_t index) const { return data_[index]; } + + constexpr reference at(std::size_t index) { + if (index > N) + FROZEN_THROW_OR_ABORT(std::out_of_range("Index (" + std::to_string(index) + ") out of bound (" + std::to_string(N) + ')')); + return data_[index]; + } + constexpr const_reference at(std::size_t index) const { + if (index > N) + FROZEN_THROW_OR_ABORT(std::out_of_range("Index (" + std::to_string(index) + ") out of bound (" + std::to_string(N) + ')')); + return data_[index]; + } + + constexpr reference front() { return data_[0]; } + constexpr const_reference front() const { return data_[0]; } + + constexpr reference back() { return data_[N - 1]; } + constexpr const_reference back() const { return data_[N - 1]; } + + constexpr value_type* data() noexcept { return data_; } + constexpr const value_type* data() const noexcept { return data_; } + + // Modifiers + constexpr void fill(const value_type& val) { + for (std::size_t i = 0; i < N; ++i) + data_[i] = val; + } +}; +template <class T> +class carray<T, 0> { + +public: + // Container typdefs + using value_type = T; + using reference = value_type &; + using const_reference = const value_type &; + using pointer = value_type *; + using const_pointer = const value_type *; + using iterator = pointer; + using const_iterator = const_pointer; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + + // Constructors + constexpr carray(void) = default; + +}; + +} // namespace bits + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/bits/constexpr_assert.h b/contrib/frozen/include/frozen/bits/constexpr_assert.h new file mode 100644 index 0000000..912210d --- /dev/null +++ b/contrib/frozen/include/frozen/bits/constexpr_assert.h @@ -0,0 +1,40 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_CONSTEXPR_ASSERT_H +#define FROZEN_LETITGO_CONSTEXPR_ASSERT_H + +#include <cassert> + +#ifdef _MSC_VER + +// FIXME: find a way to implement that correctly for msvc +#define constexpr_assert(cond, msg) + +#else + +#define constexpr_assert(cond, msg)\ + assert(cond && msg); +#endif + +#endif + diff --git a/contrib/frozen/include/frozen/bits/defines.h b/contrib/frozen/include/frozen/bits/defines.h new file mode 100644 index 0000000..0a1663d --- /dev/null +++ b/contrib/frozen/include/frozen/bits/defines.h @@ -0,0 +1,58 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_DEFINES_H +#define FROZEN_LETITGO_DEFINES_H + +#if defined(_MSVC_LANG) && !(defined(__EDG__) && defined(__clang__)) // TRANSITION, VSO#273681 + #define FROZEN_LETITGO_IS_MSVC +#endif + +// Code taken from https://stackoverflow.com/questions/43639122/which-values-can-msvc-lang-have +#if defined(FROZEN_LETITGO_IS_MSVC) + #if _MSVC_LANG > 201402 + #define FROZEN_LETITGO_HAS_CXX17 1 + #else /* _MSVC_LANG > 201402 */ + #define FROZEN_LETITGO_HAS_CXX17 0 + #endif /* _MSVC_LANG > 201402 */ +#else /* _MSVC_LANG etc. */ + #if __cplusplus > 201402 + #define FROZEN_LETITGO_HAS_CXX17 1 + #else /* __cplusplus > 201402 */ + #define FROZEN_LETITGO_HAS_CXX17 0 + #endif /* __cplusplus > 201402 */ +#endif /* _MSVC_LANG etc. */ +// End if taken code + +#if FROZEN_LETITGO_HAS_CXX17 == 1 && defined(FROZEN_LETITGO_IS_MSVC) + #define FROZEN_LETITGO_HAS_STRING_VIEW // We assume Visual Studio always has string_view in C++17 +#else + #if FROZEN_LETITGO_HAS_CXX17 == 1 && __has_include(<string_view>) + #define FROZEN_LETITGO_HAS_STRING_VIEW + #endif +#endif + +#ifdef __cpp_char8_t + #define FROZEN_LETITGO_HAS_CHAR8T +#endif + +#endif // FROZEN_LETITGO_DEFINES_H diff --git a/contrib/frozen/include/frozen/bits/elsa.h b/contrib/frozen/include/frozen/bits/elsa.h new file mode 100644 index 0000000..d7388be --- /dev/null +++ b/contrib/frozen/include/frozen/bits/elsa.h @@ -0,0 +1,50 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_ELSA_H +#define FROZEN_LETITGO_ELSA_H + +#include <type_traits> + +namespace frozen { + +template <class T> struct elsa { + static_assert(std::is_integral<T>::value || std::is_enum<T>::value, + "only supports integral types, specialize for other types"); + + constexpr std::size_t operator()(T const &value, std::size_t seed) const { + std::size_t key = seed ^ static_cast<std::size_t>(value); + key = (~key) + (key << 21); // key = (key << 21) - key - 1; + key = key ^ (key >> 24); + key = (key + (key << 3)) + (key << 8); // key * 265 + key = key ^ (key >> 14); + key = (key + (key << 2)) + (key << 4); // key * 21 + key = key ^ (key >> 28); + key = key + (key << 31); + return key; + } +}; + +template <class T> using anna = elsa<T>; +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/bits/exceptions.h b/contrib/frozen/include/frozen/bits/exceptions.h new file mode 100644 index 0000000..b43e3e6 --- /dev/null +++ b/contrib/frozen/include/frozen/bits/exceptions.h @@ -0,0 +1,39 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_EXCEPTIONS_H +#define FROZEN_LETITGO_EXCEPTIONS_H + +#if defined(FROZEN_NO_EXCEPTIONS) || (defined(_MSC_VER) && !defined(_CPPUNWIND)) || (!defined(_MSC_VER) && !defined(__cpp_exceptions)) + +#include <cstdlib> +#define FROZEN_THROW_OR_ABORT(_) std::abort() + +#else + +#include <stdexcept> +#define FROZEN_THROW_OR_ABORT(err) throw err + + +#endif + +#endif diff --git a/contrib/frozen/include/frozen/bits/pmh.h b/contrib/frozen/include/frozen/bits/pmh.h new file mode 100644 index 0000000..76e7ebe --- /dev/null +++ b/contrib/frozen/include/frozen/bits/pmh.h @@ -0,0 +1,240 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +// inspired from http://stevehanov.ca/blog/index.php?id=119 +#ifndef FROZEN_LETITGO_PMH_H +#define FROZEN_LETITGO_PMH_H + +#include "frozen/bits/algorithms.h" +#include "frozen/bits/basic_types.h" + +#include <array> +#include <limits> + +namespace frozen { + +namespace bits { + +// Function object for sorting buckets in decreasing order of size +struct bucket_size_compare { + template <typename B> + bool constexpr operator()(B const &b0, + B const &b1) const { + return b0.size() > b1.size(); + } +}; + +// Step One in pmh routine is to take all items and hash them into buckets, +// with some collisions. Then process those buckets further to build a perfect +// hash function. +// pmh_buckets represents the initial placement into buckets. + +template <size_t M> +struct pmh_buckets { + // Step 0: Bucket max is 2 * sqrt M + // TODO: Come up with justification for this, should it not be O(log M)? + static constexpr auto bucket_max = 2 * (1u << (log(M) / 2)); + + using bucket_t = cvector<std::size_t, bucket_max>; + carray<bucket_t, M> buckets; + uint64_t seed; + + // Represents a reference to a bucket. This is used because the buckets + // have to be sorted, but buckets are big, making it slower than sorting refs + struct bucket_ref { + unsigned hash; + const bucket_t * ptr; + + // Forward some interface of bucket + using value_type = typename bucket_t::value_type; + using const_iterator = typename bucket_t::const_iterator; + + constexpr auto size() const { return ptr->size(); } + constexpr const auto & operator[](std::size_t idx) const { return (*ptr)[idx]; } + constexpr auto begin() const { return ptr->begin(); } + constexpr auto end() const { return ptr->end(); } + }; + + // Make a bucket_ref for each bucket + template <std::size_t... Is> + carray<bucket_ref, M> constexpr make_bucket_refs(std::index_sequence<Is...>) const { + return {{ bucket_ref{Is, &buckets[Is]}... }}; + } + + // Makes a bucket_ref for each bucket and sorts them by size + carray<bucket_ref, M> constexpr get_sorted_buckets() const { + carray<bucket_ref, M> result{this->make_bucket_refs(std::make_index_sequence<M>())}; + bits::quicksort(result.begin(), result.end() - 1, bucket_size_compare{}); + return result; + } +}; + +template <size_t M, class Item, size_t N, class Hash, class Key, class PRG> +pmh_buckets<M> constexpr make_pmh_buckets(const carray<Item, N> & items, + Hash const & hash, + Key const & key, + PRG & prg) { + using result_t = pmh_buckets<M>; + result_t result{}; + bool rejected = false; + // Continue until all items are placed without exceeding bucket_max + while (1) { + for (auto & b : result.buckets) { + b.clear(); + } + result.seed = prg(); + rejected = false; + for (std::size_t i = 0; i < N; ++i) { + auto & bucket = result.buckets[hash(key(items[i]), static_cast<size_t>(result.seed)) % M]; + if (bucket.size() >= result_t::bucket_max) { + rejected = true; + break; + } + bucket.push_back(i); + } + if (!rejected) { return result; } + } +} + +// Check if an item appears in a cvector +template<class T, size_t N> +constexpr bool all_different_from(cvector<T, N> & data, T & a) { + for (std::size_t i = 0; i < data.size(); ++i) + if (data[i] == a) + return false; + + return true; +} + +// Represents either an index to a data item array, or a seed to be used with +// a hasher. Seed must have high bit of 1, value has high bit of zero. +struct seed_or_index { + using value_type = uint64_t; + +private: + static constexpr value_type MINUS_ONE = std::numeric_limits<value_type>::max(); + static constexpr value_type HIGH_BIT = ~(MINUS_ONE >> 1); + + value_type value_ = 0; + +public: + constexpr value_type value() const { return value_; } + constexpr bool is_seed() const { return value_ & HIGH_BIT; } + + constexpr seed_or_index(bool is_seed, value_type value) + : value_(is_seed ? (value | HIGH_BIT) : (value & ~HIGH_BIT)) {} + + constexpr seed_or_index() = default; + constexpr seed_or_index(const seed_or_index &) = default; + constexpr seed_or_index & operator =(const seed_or_index &) = default; +}; + +// Represents the perfect hash function created by pmh algorithm +template <std::size_t M, class Hasher> +struct pmh_tables { + uint64_t first_seed_; + carray<seed_or_index, M> first_table_; + carray<std::size_t, M> second_table_; + Hasher hash_; + + // Looks up a given key, to find its expected index in carray<Item, N> + // Always returns a valid index, must use KeyEqual test after to confirm. + template <typename KeyType> + constexpr std::size_t lookup(const KeyType & key) const { + auto const d = first_table_[hash_(key, static_cast<size_t>(first_seed_)) % M]; + if (!d.is_seed()) { return static_cast<std::size_t>(d.value()); } // this is narrowing uint64 -> size_t but should be fine + else { return second_table_[hash_(key, static_cast<std::size_t>(d.value())) % M]; } + } +}; + +// Make pmh tables for given items, hash function, prg, etc. +template <std::size_t M, class Item, std::size_t N, class Hash, class Key, class PRG> +pmh_tables<M, Hash> constexpr make_pmh_tables(const carray<Item, N> & + items, + Hash const &hash, + Key const &key, + PRG prg) { + // Step 1: Place all of the keys into buckets + auto step_one = make_pmh_buckets<M>(items, hash, key, prg); + + // Step 2: Sort the buckets to process the ones with the most items first. + auto buckets = step_one.get_sorted_buckets(); + + // G becomes the first hash table in the resulting pmh function + carray<seed_or_index, M> G; // Default constructed to "index 0" + + // H becomes the second hash table in the resulting pmh function + constexpr std::size_t UNUSED = std::numeric_limits<std::size_t>::max(); + carray<std::size_t, M> H; + H.fill(UNUSED); + + // Step 3: Map the items in buckets into hash tables. + for (const auto & bucket : buckets) { + auto const bsize = bucket.size(); + + if (bsize == 1) { + // Store index to the (single) item in G + // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M); + G[bucket.hash] = {false, static_cast<uint64_t>(bucket[0])}; + } else if (bsize > 1) { + + // Repeatedly try different H of d until we find a hash function + // that places all items in the bucket into free slots + seed_or_index d{true, prg()}; + cvector<std::size_t, decltype(step_one)::bucket_max> bucket_slots; + + while (bucket_slots.size() < bsize) { + auto slot = hash(key(items[bucket[bucket_slots.size()]]), static_cast<size_t>(d.value())) % M; + + if (H[slot] != UNUSED || !all_different_from(bucket_slots, slot)) { + bucket_slots.clear(); + d = {true, prg()}; + continue; + } + + bucket_slots.push_back(slot); + } + + // Put successful seed in G, and put indices to items in their slots + // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M); + G[bucket.hash] = d; + for (std::size_t i = 0; i < bsize; ++i) + H[bucket_slots[i]] = bucket[i]; + } + } + + // Any unused entries in the H table have to get changed to zero. + // This is because hashing should not fail or return an out-of-bounds entry. + // A lookup fails after we apply user-supplied KeyEqual to the query and the + // key found by hashing. Sending such queries to zero cannot hurt. + for (std::size_t i = 0; i < M; ++i) + if (H[i] == UNUSED) + H[i] = 0; + + return {step_one.seed, G, H, hash}; +} + +} // namespace bits + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/bits/version.h b/contrib/frozen/include/frozen/bits/version.h new file mode 100644 index 0000000..51804d2 --- /dev/null +++ b/contrib/frozen/include/frozen/bits/version.h @@ -0,0 +1,30 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_VERSION_H +#define FROZEN_LETITGO_VERSION_H + +#define FROZEN_MAJOR_VERSION 1 +#define FROZEN_MINOR_VERSION 0 +#define FROZEN_PATCH_VERSION 1 + +#endif diff --git a/contrib/frozen/include/frozen/map.h b/contrib/frozen/include/frozen/map.h new file mode 100644 index 0000000..107179c --- /dev/null +++ b/contrib/frozen/include/frozen/map.h @@ -0,0 +1,323 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_MAP_H +#define FROZEN_LETITGO_MAP_H + +#include "frozen/bits/algorithms.h" +#include "frozen/bits/basic_types.h" +#include "frozen/bits/constexpr_assert.h" +#include "frozen/bits/exceptions.h" +#include "frozen/bits/version.h" + +#include <utility> + +namespace frozen { + +namespace impl { + +template <class Comparator> class CompareKey { + + Comparator const comparator_; + +public: + constexpr CompareKey(Comparator const &comparator) + : comparator_(comparator) {} + + template <class Key, class Value> + constexpr int operator()(std::pair<Key, Value> const &self, + std::pair<Key, Value> const &other) const { + return comparator_(std::get<0>(self), std::get<0>(other)); + } + + template <class Key, class Value> + constexpr int operator()(Key const &self_key, + std::pair<Key, Value> const &other) const { + return comparator_(self_key, std::get<0>(other)); + } + + template <class Key, class Value> + constexpr int operator()(std::pair<Key, Value> const &self, + Key const &other_key) const { + return comparator_(std::get<0>(self), other_key); + } + + template <class Key> + constexpr int operator()(Key const &self_key, Key const &other_key) const { + return comparator_(self_key, other_key); + } +}; + +} // namespace impl + +template <class Key, class Value, std::size_t N, class Compare = std::less<Key>> +class map { + using container_type = bits::carray<std::pair<Key, Value>, N>; + impl::CompareKey<Compare> less_than_; + container_type items_; + +public: + using key_type = Key; + using mapped_type = Value; + using value_type = typename container_type::value_type; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::difference_type; + using key_compare = decltype(less_than_); + using reference = typename container_type::reference; + using const_reference = typename container_type::const_reference; + using pointer = typename container_type::pointer; + using const_pointer = typename container_type::const_pointer; + using iterator = typename container_type::iterator; + using const_iterator = typename container_type::const_iterator; + using reverse_iterator = typename container_type::reverse_iterator; + using const_reverse_iterator = + typename container_type::const_reverse_iterator; + +public: + /* constructors */ + constexpr map(container_type items, Compare const &compare) + : less_than_{compare} + , items_{bits::quicksort(items, less_than_)} {} + + explicit constexpr map(container_type items) + : map{items, Compare{}} {} + + constexpr map(std::initializer_list<value_type> items, Compare const &compare) + : map{container_type {items}, compare} { + constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument"); + } + + constexpr map(std::initializer_list<value_type> items) + : map{items, Compare{}} {} + + /* element access */ + constexpr Value const& at(Key const &key) const { + return at_impl(*this, key); + } + constexpr Value& at(Key const &key) { + return at_impl(*this, key); + } + + /* iterators */ + constexpr iterator begin() { return items_.begin(); } + constexpr const_iterator begin() const { return items_.begin(); } + constexpr const_iterator cbegin() const { return items_.cbegin(); } + constexpr iterator end() { return items_.end(); } + constexpr const_iterator end() const { return items_.end(); } + constexpr const_iterator cend() const { return items_.cend(); } + + constexpr reverse_iterator rbegin() { return items_.rbegin(); } + constexpr const_reverse_iterator rbegin() const { return items_.rbegin(); } + constexpr const_reverse_iterator crbegin() const { return items_.crbegin(); } + constexpr reverse_iterator rend() { return items_.rend(); } + constexpr const_reverse_iterator rend() const { return items_.rend(); } + constexpr const_reverse_iterator crend() const { return items_.crend(); } + + /* capacity */ + constexpr bool empty() const { return !N; } + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + /* lookup */ + + constexpr std::size_t count(Key const &key) const { + return bits::binary_search<N>(items_.begin(), key, less_than_); + } + + constexpr const_iterator find(Key const &key) const { + return find_impl(*this, key); + } + constexpr iterator find(Key const &key) { + return find_impl(*this, key); + } + + constexpr std::pair<const_iterator, const_iterator> + equal_range(Key const &key) const { + return equal_range_impl(*this, key); + } + constexpr std::pair<iterator, iterator> equal_range(Key const &key) { + return equal_range_impl(*this, key); + } + + constexpr const_iterator lower_bound(Key const &key) const { + return lower_bound_impl(*this, key); + } + constexpr iterator lower_bound(Key const &key) { + return lower_bound_impl(*this, key); + } + + constexpr const_iterator upper_bound(Key const &key) const { + return upper_bound_impl(*this, key); + } + constexpr iterator upper_bound(Key const &key) { + return upper_bound_impl(*this, key); + } + + /* observers */ + constexpr key_compare key_comp() const { return less_than_; } + constexpr key_compare value_comp() const { return less_than_; } + + private: + template <class This> + static inline constexpr auto& at_impl(This&& self, Key const &key) { + auto where = self.lower_bound(key); + if (where != self.end()) + return where->second; + else + FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); + } + + template <class This> + static inline constexpr auto find_impl(This&& self, Key const &key) { + auto where = self.lower_bound(key); + if ((where != self.end()) && !self.less_than_(key, *where)) + return where; + else + return self.end(); + } + + template <class This> + static inline constexpr auto equal_range_impl(This&& self, Key const &key) { + auto lower = self.lower_bound(key); + using lower_t = decltype(lower); + if (lower == self.end()) + return std::pair<lower_t, lower_t>{lower, lower}; + else + return std::pair<lower_t, lower_t>{lower, lower + 1}; + } + + template <class This> + static inline constexpr auto lower_bound_impl(This&& self, Key const &key) -> decltype(self.end()) { + auto where = bits::lower_bound<N>(self.items_.begin(), key, self.less_than_); + if ((where != self.end()) && !self.less_than_(key, *where)) + return where; + else + return self.end(); + } + + template <class This> + static inline constexpr auto upper_bound_impl(This&& self, Key const &key) -> decltype(self.end()) { + auto where = bits::lower_bound<N>(self.items_.begin(), key, self.less_than_); + if ((where != self.end()) && !self.less_than_(key, *where)) + return where + 1; + else + return self.end(); + } +}; + +template <class Key, class Value, class Compare> +class map<Key, Value, 0, Compare> { + using container_type = bits::carray<std::pair<Key, Value>, 0>; + impl::CompareKey<Compare> less_than_; + +public: + using key_type = Key; + using mapped_type = Value; + using value_type = typename container_type::value_type; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::difference_type; + using key_compare = decltype(less_than_); + using reference = typename container_type::reference; + using const_reference = typename container_type::const_reference; + using pointer = typename container_type::pointer; + using const_pointer = typename container_type::const_pointer; + using iterator = pointer; + using const_iterator = const_pointer; + using reverse_iterator = pointer; + using const_reverse_iterator = const_pointer; + +public: + /* constructors */ + constexpr map(const map &other) = default; + constexpr map(std::initializer_list<value_type>, Compare const &compare) + : less_than_{compare} {} + constexpr map(std::initializer_list<value_type> items) + : map{items, Compare{}} {} + + /* element access */ + constexpr mapped_type at(Key const &) const { + FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key")); + } + constexpr mapped_type at(Key const &) { + FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key")); + } + + /* iterators */ + constexpr iterator begin() { return nullptr; } + constexpr const_iterator begin() const { return nullptr; } + constexpr const_iterator cbegin() const { return nullptr; } + constexpr iterator end() { return nullptr; } + constexpr const_iterator end() const { return nullptr; } + constexpr const_iterator cend() const { return nullptr; } + + constexpr reverse_iterator rbegin() { return nullptr; } + constexpr const_reverse_iterator rbegin() const { return nullptr; } + constexpr const_reverse_iterator crbegin() const { return nullptr; } + constexpr reverse_iterator rend() { return nullptr; } + constexpr const_reverse_iterator rend() const { return nullptr; } + constexpr const_reverse_iterator crend() const { return nullptr; } + + /* capacity */ + constexpr bool empty() const { return true; } + constexpr size_type size() const { return 0; } + constexpr size_type max_size() const { return 0; } + + /* lookup */ + + constexpr std::size_t count(Key const &) const { return 0; } + + constexpr const_iterator find(Key const &) const { return end(); } + constexpr iterator find(Key const &) { return end(); } + + constexpr std::pair<const_iterator, const_iterator> + equal_range(Key const &) const { + return {end(), end()}; + } + constexpr std::pair<iterator, iterator> + equal_range(Key const &) { + return {end(), end()}; + } + + constexpr const_iterator lower_bound(Key const &) const { return end(); } + constexpr iterator lower_bound(Key const &) { return end(); } + + constexpr const_iterator upper_bound(Key const &) const { return end(); } + constexpr iterator upper_bound(Key const &) { return end(); } + + /* observers */ + constexpr key_compare key_comp() const { return less_than_; } + constexpr key_compare value_comp() const { return less_than_; } +}; + +template <typename T, typename U> +constexpr auto make_map(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { + return map<T, U, 0>{}; +} + +template <typename T, typename U, std::size_t N> +constexpr auto make_map(std::pair<T, U> const (&items)[N]) { + return map<T, U, N>{items}; +} + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/random.h b/contrib/frozen/include/frozen/random.h new file mode 100644 index 0000000..ea494dc --- /dev/null +++ b/contrib/frozen/include/frozen/random.h @@ -0,0 +1,90 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_RANDOM_H +#define FROZEN_LETITGO_RANDOM_H + +#include "frozen/bits/algorithms.h" +#include "frozen/bits/version.h" + +#include <cstdint> +#include <type_traits> + +namespace frozen { +template <class UIntType, UIntType a, UIntType c, UIntType m> +class linear_congruential_engine { + + static_assert(std::is_unsigned<UIntType>::value, + "UIntType must be an unsigned integral type"); + +public: + using result_type = UIntType; + static constexpr result_type multiplier = a; + static constexpr result_type increment = c; + static constexpr result_type modulus = m; + static constexpr result_type default_seed = 1u; + + linear_congruential_engine() = default; + constexpr linear_congruential_engine(result_type s) { seed(s); } + + void seed(result_type s = default_seed) { state_ = s; } + constexpr result_type operator()() { + using uint_least_t = bits::select_uint_least_t<bits::log(a) + bits::log(m) + 4>; + uint_least_t tmp = static_cast<uint_least_t>(multiplier) * state_ + increment; + + // the static cast below may end up doing a truncation + if(modulus != 0) + state_ = static_cast<result_type>(tmp % modulus); + else + state_ = static_cast<result_type>(tmp); + return state_; + } + constexpr void discard(unsigned long long n) { + while (n--) + operator()(); + } + static constexpr result_type min() { return increment == 0u ? 1u : 0u; }; + static constexpr result_type max() { return modulus - 1u; }; + friend constexpr bool operator==(linear_congruential_engine const &self, + linear_congruential_engine const &other) { + return self.state_ == other.state_; + } + friend constexpr bool operator!=(linear_congruential_engine const &self, + linear_congruential_engine const &other) { + return !(self == other); + } + +private: + result_type state_ = default_seed; +}; + +using minstd_rand0 = + linear_congruential_engine<std::uint_fast32_t, 16807, 0, 2147483647>; +using minstd_rand = + linear_congruential_engine<std::uint_fast32_t, 48271, 0, 2147483647>; + +// This generator is used by default in unordered frozen containers +using default_prg_t = minstd_rand; + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/set.h b/contrib/frozen/include/frozen/set.h new file mode 100644 index 0000000..d86d814 --- /dev/null +++ b/contrib/frozen/include/frozen/set.h @@ -0,0 +1,220 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_SET_H +#define FROZEN_SET_H + +#include "frozen/bits/algorithms.h" +#include "frozen/bits/basic_types.h" +#include "frozen/bits/constexpr_assert.h" +#include "frozen/bits/version.h" + +#include <utility> + +namespace frozen { + +template <class Key, std::size_t N, class Compare = std::less<Key>> class set { + using container_type = bits::carray<Key, N>; + Compare less_than_; + container_type keys_; + +public: + /* container typedefs*/ + using key_type = Key; + using value_type = Key; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::size_type; + using key_compare = Compare; + using value_compare = Compare; + using reference = typename container_type::const_reference; + using const_reference = reference; + using pointer = typename container_type::const_pointer; + using const_pointer = pointer; + using iterator = typename container_type::const_iterator; + using reverse_iterator = typename container_type::const_reverse_iterator; + using const_iterator = iterator; + using const_reverse_iterator = reverse_iterator; + +public: + /* constructors */ + constexpr set(const set &other) = default; + + constexpr set(container_type keys, Compare const & comp) + : less_than_{comp} + , keys_(bits::quicksort(keys, less_than_)) { + } + + explicit constexpr set(container_type keys) + : set{keys, Compare{}} {} + + constexpr set(std::initializer_list<Key> keys, Compare const & comp) + : set{container_type{keys}, comp} { + constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument"); + } + + constexpr set(std::initializer_list<Key> keys) + : set{keys, Compare{}} {} + + /* capacity */ + constexpr bool empty() const { return !N; } + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + /* lookup */ + constexpr std::size_t count(Key const &key) const { + return bits::binary_search<N>(keys_.begin(), key, less_than_); + } + + constexpr const_iterator find(Key const &key) const { + const_iterator where = lower_bound(key); + if ((where != end()) && !less_than_(key, *where)) + return where; + else + return end(); + } + + constexpr std::pair<const_iterator, const_iterator> equal_range(Key const &key) const { + auto const lower = lower_bound(key); + if (lower == end()) + return {lower, lower}; + else + return {lower, lower + 1}; + } + + constexpr const_iterator lower_bound(Key const &key) const { + auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_); + if ((where != end()) && !less_than_(key, *where)) + return where; + else + return end(); + } + + constexpr const_iterator upper_bound(Key const &key) const { + auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_); + if ((where != end()) && !less_than_(key, *where)) + return where + 1; + else + return end(); + } + + /* observers */ + constexpr key_compare key_comp() const { return less_than_; } + constexpr key_compare value_comp() const { return less_than_; } + + /* iterators */ + constexpr const_iterator begin() const { return keys_.begin(); } + constexpr const_iterator cbegin() const { return keys_.cbegin(); } + constexpr const_iterator end() const { return keys_.end(); } + constexpr const_iterator cend() const { return keys_.cend(); } + + constexpr const_reverse_iterator rbegin() const { return keys_.rbegin(); } + constexpr const_reverse_iterator crbegin() const { return keys_.crbegin(); } + constexpr const_reverse_iterator rend() const { return keys_.rend(); } + constexpr const_reverse_iterator crend() const { return keys_.crend(); } + + /* comparison */ + constexpr bool operator==(set const& rhs) const { return bits::equal(begin(), end(), rhs.begin()); } + constexpr bool operator!=(set const& rhs) const { return !(*this == rhs); } + constexpr bool operator<(set const& rhs) const { return bits::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end()); } + constexpr bool operator<=(set const& rhs) const { return (*this < rhs) || (*this == rhs); } + constexpr bool operator>(set const& rhs) const { return bits::lexicographical_compare(rhs.begin(), rhs.end(), begin(), end()); } + constexpr bool operator>=(set const& rhs) const { return (*this > rhs) || (*this == rhs); } +}; + +template <class Key, class Compare> class set<Key, 0, Compare> { + using container_type = bits::carray<Key, 0>; // just for the type definitions + Compare less_than_; + +public: + /* container typedefs*/ + using key_type = Key; + using value_type = Key; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::size_type; + using key_compare = Compare; + using value_compare = Compare; + using reference = typename container_type::const_reference; + using const_reference = reference; + using pointer = typename container_type::const_pointer; + using const_pointer = pointer; + using iterator = pointer; + using reverse_iterator = pointer; + using const_iterator = const_pointer; + using const_reverse_iterator = const_pointer; + +public: + /* constructors */ + constexpr set(const set &other) = default; + constexpr set(bits::carray<Key, 0>, Compare const &) {} + explicit constexpr set(bits::carray<Key, 0>) {} + + constexpr set(std::initializer_list<Key>, Compare const &comp) + : less_than_{comp} {} + constexpr set(std::initializer_list<Key> keys) : set{keys, Compare{}} {} + + /* capacity */ + constexpr bool empty() const { return true; } + constexpr size_type size() const { return 0; } + constexpr size_type max_size() const { return 0; } + + /* lookup */ + constexpr std::size_t count(Key const &) const { return 0; } + + constexpr const_iterator find(Key const &) const { return end(); } + + constexpr std::pair<const_iterator, const_iterator> + equal_range(Key const &) const { return {end(), end()}; } + + constexpr const_iterator lower_bound(Key const &) const { return end(); } + + constexpr const_iterator upper_bound(Key const &) const { return end(); } + + /* observers */ + constexpr key_compare key_comp() const { return less_than_; } + constexpr key_compare value_comp() const { return less_than_; } + + /* iterators */ + constexpr const_iterator begin() const { return nullptr; } + constexpr const_iterator cbegin() const { return nullptr; } + constexpr const_iterator end() const { return nullptr; } + constexpr const_iterator cend() const { return nullptr; } + + constexpr const_reverse_iterator rbegin() const { return nullptr; } + constexpr const_reverse_iterator crbegin() const { return nullptr; } + constexpr const_reverse_iterator rend() const { return nullptr; } + constexpr const_reverse_iterator crend() const { return nullptr; } +}; + +template <typename T> +constexpr auto make_set(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { + return set<T, 0>{}; +} + +template <typename T, std::size_t N> +constexpr auto make_set(const T (&args)[N]) { + return set<T, N>(args); +} + + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/string.h b/contrib/frozen/include/frozen/string.h new file mode 100644 index 0000000..4505bbf --- /dev/null +++ b/contrib/frozen/include/frozen/string.h @@ -0,0 +1,152 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_STRING_H +#define FROZEN_LETITGO_STRING_H + +#include "frozen/bits/elsa.h" +#include "frozen/bits/version.h" +#include "frozen/bits/defines.h" + +#include <functional> + +#ifdef FROZEN_LETITGO_HAS_STRING_VIEW +#include <string_view> +#endif + +namespace frozen { + +template <typename _CharT> +class basic_string { + using chr_t = _CharT; + + chr_t const *data_; + std::size_t size_; + +public: + template <std::size_t N> + constexpr basic_string(chr_t const (&data)[N]) + : data_(data), size_(N - 1) {} + constexpr basic_string(chr_t const *data, std::size_t size) + : data_(data), size_(size) {} + +#ifdef FROZEN_LETITGO_HAS_STRING_VIEW + constexpr basic_string(std::basic_string_view<chr_t> data) + : data_(data.data()), size_(data.size()) {} +#endif + + constexpr basic_string(const basic_string &) noexcept = default; + constexpr basic_string &operator=(const basic_string &) noexcept = default; + + constexpr std::size_t size() const { return size_; } + + constexpr chr_t operator[](std::size_t i) const { return data_[i]; } + + constexpr bool operator==(basic_string other) const { + if (size_ != other.size_) + return false; + for (std::size_t i = 0; i < size_; ++i) + if (data_[i] != other.data_[i]) + return false; + return true; + } + + constexpr bool operator<(const basic_string &other) const { + unsigned i = 0; + while (i < size() && i < other.size()) { + if ((*this)[i] < other[i]) { + return true; + } + if ((*this)[i] > other[i]) { + return false; + } + ++i; + } + return size() < other.size(); + } + + constexpr const chr_t *data() const { return data_; } +}; + +template <typename _CharT> struct elsa<basic_string<_CharT>> { + constexpr std::size_t operator()(basic_string<_CharT> value) const { + std::size_t d = 5381; + for (std::size_t i = 0; i < value.size(); ++i) + d = d * 33 + value[i]; + return d; + } + // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function + // With the lowest bits removed, based on experimental setup. + constexpr std::size_t operator()(basic_string<_CharT> value, std::size_t seed) const { + std::size_t d = (0x811c9dc5 ^ seed) * 0x01000193; + for (std::size_t i = 0; i < value.size(); ++i) + d = (d ^ value[i]) * 0x01000193; + return d >> 8 ; + } +}; + +using string = basic_string<char>; +using wstring = basic_string<wchar_t>; +using u16string = basic_string<char16_t>; +using u32string = basic_string<char32_t>; + +#ifdef FROZEN_LETITGO_HAS_CHAR8T +using u8string = basic_string<char8_t>; +#endif + +namespace string_literals { + +constexpr string operator"" _s(const char *data, std::size_t size) { + return {data, size}; +} + +constexpr wstring operator"" _s(const wchar_t *data, std::size_t size) { + return {data, size}; +} + +constexpr u16string operator"" _s(const char16_t *data, std::size_t size) { + return {data, size}; +} + +constexpr u32string operator"" _s(const char32_t *data, std::size_t size) { + return {data, size}; +} + +#ifdef FROZEN_LETITGO_HAS_CHAR8T +constexpr u8string operator"" _s(const char8_t *data, std::size_t size) { + return {data, size}; +} +#endif + +} // namespace string_literals + +} // namespace frozen + +namespace std { +template <typename _CharT> struct hash<frozen::basic_string<_CharT>> { + size_t operator()(frozen::basic_string<_CharT> s) const { + return frozen::elsa<frozen::basic_string<_CharT>>{}(s); + } +}; +} // namespace std + +#endif diff --git a/contrib/frozen/include/frozen/unordered_map.h b/contrib/frozen/include/frozen/unordered_map.h new file mode 100644 index 0000000..5e1e399 --- /dev/null +++ b/contrib/frozen/include/frozen/unordered_map.h @@ -0,0 +1,197 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_UNORDERED_MAP_H +#define FROZEN_LETITGO_UNORDERED_MAP_H + +#include "frozen/bits/basic_types.h" +#include "frozen/bits/constexpr_assert.h" +#include "frozen/bits/elsa.h" +#include "frozen/bits/exceptions.h" +#include "frozen/bits/pmh.h" +#include "frozen/bits/version.h" +#include "frozen/random.h" + +#include <tuple> +#include <functional> + +namespace frozen { + +namespace bits { + +struct GetKey { + template <class KV> constexpr auto const &operator()(KV const &kv) const { + return kv.first; + } +}; + +} // namespace bits + +template <class Key, class Value, std::size_t N, typename Hash = anna<Key>, + class KeyEqual = std::equal_to<Key>> +class unordered_map { + static constexpr std::size_t storage_size = + bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets + using container_type = bits::carray<std::pair<Key, Value>, N>; + using tables_type = bits::pmh_tables<storage_size, Hash>; + + KeyEqual const equal_; + container_type items_; + tables_type tables_; + +public: + /* typedefs */ + using Self = unordered_map<Key, Value, N, Hash, KeyEqual>; + using key_type = Key; + using mapped_type = Value; + using value_type = typename container_type::value_type; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::difference_type; + using hasher = Hash; + using key_equal = KeyEqual; + using reference = typename container_type::reference; + using const_reference = typename container_type::const_reference; + using pointer = typename container_type::pointer; + using const_pointer = typename container_type::const_pointer; + using iterator = typename container_type::iterator; + using const_iterator = typename container_type::const_iterator; + +public: + /* constructors */ + unordered_map(unordered_map const &) = default; + constexpr unordered_map(container_type items, + Hash const &hash, KeyEqual const &equal) + : equal_{equal} + , items_{items} + , tables_{ + bits::make_pmh_tables<storage_size>( + items_, hash, bits::GetKey{}, default_prg_t{})} {} + explicit constexpr unordered_map(container_type items) + : unordered_map{items, Hash{}, KeyEqual{}} {} + + constexpr unordered_map(std::initializer_list<value_type> items, + Hash const & hash, KeyEqual const & equal) + : unordered_map{container_type{items}, hash, equal} { + constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument"); + } + + constexpr unordered_map(std::initializer_list<value_type> items) + : unordered_map{items, Hash{}, KeyEqual{}} {} + + /* iterators */ + constexpr iterator begin() { return items_.begin(); } + constexpr iterator end() { return items_.end(); } + constexpr const_iterator begin() const { return items_.begin(); } + constexpr const_iterator end() const { return items_.end(); } + constexpr const_iterator cbegin() const { return items_.cbegin(); } + constexpr const_iterator cend() const { return items_.cend(); } + + /* capacity */ + constexpr bool empty() const { return !N; } + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + /* lookup */ + constexpr std::size_t count(Key const &key) const { + auto const &kv = lookup(key); + return equal_(kv.first, key); + } + + constexpr Value const &at(Key const &key) const { + return at_impl(*this, key); + } + constexpr Value &at(Key const &key) { + return at_impl(*this, key); + } + + constexpr const_iterator find(Key const &key) const { + return find_impl(*this, key); + } + constexpr iterator find(Key const &key) { + return find_impl(*this, key); + } + + constexpr std::pair<const_iterator, const_iterator> equal_range(Key const &key) const { + return equal_range_impl(*this, key); + } + constexpr std::pair<iterator, iterator> equal_range(Key const &key) { + return equal_range_impl(*this, key); + } + + /* bucket interface */ + constexpr std::size_t bucket_count() const { return storage_size; } + constexpr std::size_t max_bucket_count() const { return storage_size; } + + /* observers*/ + constexpr hasher hash_function() const { return tables_.hash_; } + constexpr key_equal key_eq() const { return equal_; } + +private: + template <class This> + static inline constexpr auto& at_impl(This&& self, Key const &key) { + auto& kv = self.lookup(key); + if (self.equal_(kv.first, key)) + return kv.second; + else + FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); + } + + template <class This> + static inline constexpr auto find_impl(This&& self, Key const &key) { + auto& kv = self.lookup(key); + if (self.equal_(kv.first, key)) + return &kv; + else + return self.items_.end(); + } + + template <class This> + static inline constexpr auto equal_range_impl(This&& self, Key const &key) { + auto& kv = self.lookup(key); + using kv_ptr = decltype(&kv); + if (self.equal_(kv.first, key)) + return std::pair<kv_ptr, kv_ptr>{&kv, &kv + 1}; + else + return std::pair<kv_ptr, kv_ptr>{self.items_.end(), self.items_.end()}; + } + + template <class This> + static inline constexpr auto& lookup_impl(This&& self, Key const &key) { + return self.items_[self.tables_.lookup(key)]; + } + + constexpr auto const& lookup(Key const &key) const { + return lookup_impl(*this, key); + } + constexpr auto& lookup(Key const &key) { + return lookup_impl(*this, key); + } +}; + +template <typename T, typename U, std::size_t N> +constexpr auto make_unordered_map(std::pair<T, U> const (&items)[N]) { + return unordered_map<T, U, N>{items}; +} + +} // namespace frozen + +#endif diff --git a/contrib/frozen/include/frozen/unordered_set.h b/contrib/frozen/include/frozen/unordered_set.h new file mode 100644 index 0000000..0fca292 --- /dev/null +++ b/contrib/frozen/include/frozen/unordered_set.h @@ -0,0 +1,147 @@ +/* + * Frozen + * Copyright 2016 QuarksLab + * + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +#ifndef FROZEN_LETITGO_UNORDERED_SET_H +#define FROZEN_LETITGO_UNORDERED_SET_H + +#include "frozen/bits/basic_types.h" +#include "frozen/bits/constexpr_assert.h" +#include "frozen/bits/elsa.h" +#include "frozen/bits/pmh.h" +#include "frozen/bits/version.h" +#include "frozen/random.h" + +#include <utility> + +namespace frozen { + +namespace bits { + +struct Get { + template <class T> constexpr T const &operator()(T const &key) const { + return key; + } +}; + +} // namespace bits + +template <class Key, std::size_t N, typename Hash = elsa<Key>, + class KeyEqual = std::equal_to<Key>> +class unordered_set { + static constexpr std::size_t storage_size = + bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets + using container_type = bits::carray<Key, N>; + using tables_type = bits::pmh_tables<storage_size, Hash>; + + KeyEqual const equal_; + container_type keys_; + tables_type tables_; + +public: + /* typedefs */ + using key_type = Key; + using value_type = Key; + using size_type = typename container_type::size_type; + using difference_type = typename container_type::difference_type; + using hasher = Hash; + using key_equal = KeyEqual; + using const_reference = typename container_type::const_reference; + using reference = const_reference; + using const_pointer = typename container_type::const_pointer; + using pointer = const_pointer; + using const_iterator = const_pointer; + using iterator = const_iterator; + +public: + /* constructors */ + unordered_set(unordered_set const &) = default; + constexpr unordered_set(container_type keys, Hash const &hash, + KeyEqual const &equal) + : equal_{equal} + , keys_{keys} + , tables_{bits::make_pmh_tables<storage_size>( + keys_, hash, bits::Get{}, default_prg_t{})} {} + explicit constexpr unordered_set(container_type keys) + : unordered_set{keys, Hash{}, KeyEqual{}} {} + + constexpr unordered_set(std::initializer_list<Key> keys) + : unordered_set{keys, Hash{}, KeyEqual{}} {} + + constexpr unordered_set(std::initializer_list<Key> keys, Hash const & hash, KeyEqual const & equal) + : unordered_set{container_type{keys}, hash, equal} { + constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument"); + } + + /* iterators */ + constexpr const_iterator begin() const { return keys_.begin(); } + constexpr const_iterator end() const { return keys_.end(); } + constexpr const_iterator cbegin() const { return keys_.cbegin(); } + constexpr const_iterator cend() const { return keys_.cend(); } + + /* capacity */ + constexpr bool empty() const { return !N; } + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + /* lookup */ + constexpr std::size_t count(Key const &key) const { + auto const k = lookup(key); + return equal_(k, key); + } + constexpr const_iterator find(Key const &key) const { + auto const &k = lookup(key); + if (equal_(k, key)) + return &k; + else + return keys_.end(); + } + + constexpr std::pair<const_iterator, const_iterator> equal_range(Key const &key) const { + auto const &k = lookup(key); + if (equal_(k, key)) + return {&k, &k + 1}; + else + return {keys_.end(), keys_.end()}; + } + + /* bucket interface */ + constexpr std::size_t bucket_count() const { return storage_size; } + constexpr std::size_t max_bucket_count() const { return storage_size; } + + /* observers*/ + constexpr hasher hash_function() const { return tables_.hash_; } + constexpr key_equal key_eq() const { return equal_; } + +private: + constexpr auto const &lookup(Key const &key) const { + return keys_[tables_.lookup(key)]; + } +}; + +template <typename T, std::size_t N> +constexpr auto make_unordered_set(T const (&keys)[N]) { + return unordered_set<T, N>{keys}; +} + +} // namespace frozen + +#endif |