From 408c608fc7bf1557ee987dd7fbe662fabed21a53 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 15 Apr 2024 07:39:03 +0200 Subject: Adding upstream version 1.1.1. Signed-off-by: Daniel Baumann --- .appveyor.yml | 9 + .github/workflows/frozen.yml | 43 + .gitignore | 4 + .travis.yml | 91 + AUTHORS | 3 + CMakeLists.txt | 167 + LICENSE | 202 + README.rst | 245 + benchmarks/CMakeLists.txt | 36 + benchmarks/Makefile | 27 + benchmarks/bench_int_set.cpp | 94 + benchmarks/bench_main.cpp | 2 + benchmarks/bench_str_map.cpp | 84 + benchmarks/bench_str_search.cpp | 68 + benchmarks/bench_str_set.cpp | 102 + cmake/CTestCustom.cmake | 5 + cmake/detect_cxx_version.cmake | 45 + cmake/sed.cmake | 12 + cmake/sed.script.cmake | 18 + examples/CMakeLists.txt | 16 + examples/enum_to_string.cpp | 172 + examples/enum_to_string_hash.cpp | 127 + examples/html_entities_map.cpp | 2147 ++++ examples/pixel_art.cpp | 120 + examples/static_assert.cpp | 9 + examples/value_modification.cpp | 37 + include/frozen/CMakeLists.txt | 12 + include/frozen/algorithm.h | 197 + include/frozen/bits/algorithms.h | 229 + include/frozen/bits/basic_types.h | 207 + include/frozen/bits/constexpr_assert.h | 40 + include/frozen/bits/defines.h | 66 + include/frozen/bits/elsa.h | 57 + include/frozen/bits/elsa_std.h | 40 + include/frozen/bits/exceptions.h | 39 + include/frozen/bits/hash_string.h | 28 + include/frozen/bits/pmh.h | 245 + include/frozen/bits/version.h | 30 + include/frozen/map.h | 354 + include/frozen/random.h | 97 + include/frozen/set.h | 256 + include/frozen/string.h | 147 + include/frozen/unordered_map.h | 255 + include/frozen/unordered_set.h | 187 + tests/CMakeLists.txt | 61 + tests/Makefile | 64 + tests/bench.hpp | 65 + tests/catch.hpp | 17966 +++++++++++++++++++++++++++++++ tests/no_exceptions.cpp | 22 + tests/test_algorithms.cpp | 30 + tests/test_elsa_std.cpp | 44 + tests/test_main.cpp | 2 + tests/test_map.cpp | 481 + tests/test_rand.cpp | 40 + tests/test_set.cpp | 314 + tests/test_str.cpp | 244 + tests/test_str_set.cpp | 82 + tests/test_unordered_map.cpp | 248 + tests/test_unordered_map_str.cpp | 88 + tests/test_unordered_set.cpp | 199 + tests/test_unordered_str_set.cpp | 90 + 61 files changed, 26411 insertions(+) create mode 100644 .appveyor.yml create mode 100644 .github/workflows/frozen.yml create mode 100644 .gitignore create mode 100644 .travis.yml create mode 100644 AUTHORS create mode 100644 CMakeLists.txt create mode 100644 LICENSE create mode 100644 README.rst create mode 100644 benchmarks/CMakeLists.txt create mode 100644 benchmarks/Makefile create mode 100644 benchmarks/bench_int_set.cpp create mode 100644 benchmarks/bench_main.cpp create mode 100644 benchmarks/bench_str_map.cpp create mode 100644 benchmarks/bench_str_search.cpp create mode 100644 benchmarks/bench_str_set.cpp create mode 100644 cmake/CTestCustom.cmake create mode 100644 cmake/detect_cxx_version.cmake create mode 100644 cmake/sed.cmake create mode 100644 cmake/sed.script.cmake create mode 100644 examples/CMakeLists.txt create mode 100644 examples/enum_to_string.cpp create mode 100644 examples/enum_to_string_hash.cpp create mode 100644 examples/html_entities_map.cpp create mode 100644 examples/pixel_art.cpp create mode 100644 examples/static_assert.cpp create mode 100644 examples/value_modification.cpp create mode 100644 include/frozen/CMakeLists.txt create mode 100644 include/frozen/algorithm.h create mode 100644 include/frozen/bits/algorithms.h create mode 100644 include/frozen/bits/basic_types.h create mode 100644 include/frozen/bits/constexpr_assert.h create mode 100644 include/frozen/bits/defines.h create mode 100644 include/frozen/bits/elsa.h create mode 100644 include/frozen/bits/elsa_std.h create mode 100644 include/frozen/bits/exceptions.h create mode 100644 include/frozen/bits/hash_string.h create mode 100644 include/frozen/bits/pmh.h create mode 100644 include/frozen/bits/version.h create mode 100644 include/frozen/map.h create mode 100644 include/frozen/random.h create mode 100644 include/frozen/set.h create mode 100644 include/frozen/string.h create mode 100644 include/frozen/unordered_map.h create mode 100644 include/frozen/unordered_set.h create mode 100644 tests/CMakeLists.txt create mode 100644 tests/Makefile create mode 100644 tests/bench.hpp create mode 100644 tests/catch.hpp create mode 100644 tests/no_exceptions.cpp create mode 100644 tests/test_algorithms.cpp create mode 100644 tests/test_elsa_std.cpp create mode 100644 tests/test_main.cpp create mode 100644 tests/test_map.cpp create mode 100644 tests/test_rand.cpp create mode 100644 tests/test_set.cpp create mode 100644 tests/test_str.cpp create mode 100644 tests/test_str_set.cpp create mode 100644 tests/test_unordered_map.cpp create mode 100644 tests/test_unordered_map_str.cpp create mode 100644 tests/test_unordered_set.cpp create mode 100644 tests/test_unordered_str_set.cpp diff --git a/.appveyor.yml b/.appveyor.yml new file mode 100644 index 0000000..6d9c332 --- /dev/null +++ b/.appveyor.yml @@ -0,0 +1,9 @@ +image: +- Visual Studio 2017 + +platform: +- x64 + +build_script: + - cmake -DCMAKE_BUILD_TYPE=Release . + - cmake --build . diff --git a/.github/workflows/frozen.yml b/.github/workflows/frozen.yml new file mode 100644 index 0000000..0dcf504 --- /dev/null +++ b/.github/workflows/frozen.yml @@ -0,0 +1,43 @@ +name: CI + +on: [push] + +jobs: + build_frozen: + runs-on: ${{ matrix.os }} + strategy: + fail-fast: false + matrix: + os: + - ubuntu-latest + - windows-latest + - macOS-latest + cmake_args: + - "" + cxxstandard: + - 14 + - 17 + - 2a + steps: + - name: Checkout + uses: actions/checkout@v1 + with: + fetch-depth: 1 + + - name: Prepare + run: cmake -E make_directory build + + - name: Configure + working-directory: build + env: + CXXFLAGS: ${{matrix.os == 'windows-latest' && '/std:' || '-std='}}c++${{matrix.cxxstandard}} + run: cmake -DCMAKE_BUILD_TYPE=DEBUG "-Dfrozen.coverage=ON" -DCMAKE_VERBOSE_MAKEFILE=ON .. + + - name: Build + working-directory: build + run: cmake --build . + + - name: Test + if: startsWith(matrix.os, 'windows') == false + working-directory: build + run: cmake --build . --target test diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..81801b5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +tests/test_main +tests/*.o +*.*~ +Makefile~ diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..5488c68 --- /dev/null +++ b/.travis.yml @@ -0,0 +1,91 @@ +language: cpp + +matrix: + include: + - os: linux + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - g++-6 + env: CXX_COMPILER=g++-6 BUILD_TYPE=Debug COVERAGE=ON + - os: linux + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - g++-6 + env: CXX_COMPILER=g++-6 BUILD_TYPE=Debug COVERAGE=OFF + - os: linux + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - g++-6 + env: CXX_COMPILER=g++-6 BUILD_TYPE=Release COVERAGE=OFF + - os: linux + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - g++-7 + env: CXX_COMPILER=g++-7 BUILD_TYPE=Release COVERAGE=OFF + - os: linux + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - g++-7 + env: CXX_COMPILER=g++-7 BUILD_TYPE=Debug COVERAGE=OFF + - os: linux + dist: xenial + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - clang-5.0 + - g++-7 + env: CXX_COMPILER=clang++-5.0 BUILD_TYPE=Debug COVERAGE=OFF + - os: linux + dist: xenial + addons: + apt: + sources: + - ubuntu-toolchain-r-test + packages: + - clang-5.0 + - g++-7 + env: CXX_COMPILER=clang++-5.0 BUILD_TYPE=Release COVERAGE=OFF + - os: osx + osx_image: xcode8.3 + env: CXX_COMPILER=clang++ BUILD_TYPE=Debug COVERAGE=OFF + - os: osx + osx_image: xcode8.3 + env: CXX_COMPILER=clang++ BUILD_TYPE=Release COVERAGE=OFF + +script: + - mkdir build + - cd build + - > + cmake -DCMAKE_BUILD_TYPE=${BUILD_TYPE} \ + -Dfrozen.coverage=${COVERAGE} \ + -DCMAKE_CXX_COMPILER=${CXX_COMPILER} \ + -DCMAKE_VERBOSE_MAKEFILE=ON \ + -DCTEST_DROP_SITE_CDASH=TRUE \ + -DDROP_METHOD="http" \ + -DDROP_SITE="my.cdash.org" \ + -DDROP_LOCATION="/submit.php?project=frozen" \ + -DBUILDNAME="$(uname -s)-${CXX_COMPILER}-${BUILD_TYPE}" .. + - ctest -VV -M Experimental -T Start \ + && ctest -VV -M Experimental -T Build \ + && ctest -VV -M Experimental -T Test + - if [[ "$COVERAGE" = "ON" ]]; then ctest -VV -M Experimental -T Coverage; fi + - ctest -VV -M Experimental -T Submit + + diff --git a/AUTHORS b/AUTHORS new file mode 100644 index 0000000..d83d0f8 --- /dev/null +++ b/AUTHORS @@ -0,0 +1,3 @@ +serge-sans-paille +Jérôme Dumesnil +Chris Beck diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..5bc044a --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,167 @@ +cmake_minimum_required(VERSION 3.8) +# +# Here we check whether frozen is being configured in isolation or as a component +# of a larger proeject. To do so, we query whether the `PROJECT_NAME` CMake +# variable has been defined. In the case it has, we can conclude frozen is a +# subproject. +# +# This convention has been borrowed from the Catch C++ unit testing library. +# +if(DEFINED PROJECT_NAME) + set(subproject ON) + set(INSTALL_SUBPROJECTS ON CACHE BOOL "Install subproject dependencies") +else() + set(subproject OFF) + set_property(GLOBAL PROPERTY USE_FOLDERS ON) +endif() + +project(frozen VERSION 1.1.0 LANGUAGES CXX) +include(CMakeDependentOption) +include(CMakePackageConfigHelpers) # provides `write_basic_package_version_file` +include(CTest) +include(GNUInstallDirs) +include(cmake/detect_cxx_version.cmake) + +# +# The `frozen.testing`, `frozen.benchmark`, and `frozen.coverage` options +# only appear as cmake-gui and ccmake options iff frozen is the highest +# level project. In the case that frozen is a subproject, these options are +# hidden from the user interface and set to `OFF` +# +CMAKE_DEPENDENT_OPTION(frozen.tests + "Build the frozen tests and integrate with ctest" + ${BUILD_TESTING} "NOT subproject" OFF) + +CMAKE_DEPENDENT_OPTION(frozen.benchmark + "Build the frozen benchmark" + OFF "NOT subproject" OFF) + +CMAKE_DEPENDENT_OPTION(frozen.coverage + "Enable test coverage collection of frozen tests" + OFF "NOT subproject" OFF) + +# +# When the end user is consuming frozen as a nested subproject, an option +# is provided such that the user may exlude frozen from the set of installed +# cmake projects. This accomodates end users building executables or +# compiled libraries which privately link to frozen, but wish to only ship their +# artifacts in an installation +# +CMAKE_DEPENDENT_OPTION(frozen.installation + "Include frozen in the install set" + "${INSTALL_SUBPROJECTS}" "subproject" ON) +mark_as_advanced(frozen.installation) + +# +# frozen has no compiled components. As such, we declare it as an `INTERFACE` +# library, which denotes a collection of target properties to be applied +# transitively to linking targets. In our case, this amounts to an include +# directory and project header files. +# +add_library(frozen INTERFACE) +add_library(frozen::frozen ALIAS frozen) + +add_library(frozen-headers INTERFACE) +add_library(frozen::frozen-headers ALIAS frozen-headers) + +target_link_libraries(frozen-headers INTERFACE frozen::frozen) + +# +# frozen requires C++ 14 support, at a minimum. Setting the `cxx_std_14` compile +# features ensures that the corresponding C++ standard flag is populated in +# targets linking to frozen +# +target_compile_features(frozen INTERFACE cxx_std_14) + +# +# The include directory for frozen can be expected to vary between build +# and installaion. Here we use a CMake generator expression to dispatch +# on how the configuration under which this library is being consumed. +# + +string(CONCAT prefix + "$" + "$") + +target_include_directories(frozen INTERFACE ${prefix}) +add_subdirectory(include/frozen) + +if(frozen.tests) + add_subdirectory(tests) + add_subdirectory(examples) +endif() + +if(frozen.benchmark) + add_subdirectory(benchmarks) +endif() + +if(frozen.installation) + # + # As a header-only library, there are no target components to be installed + # directly (the PUBLIC_HEADER property is not white listed for INTERFACE + # targets for some reason). + # + # However, it is worthwhile export our target description in order to later + # generate a CMake configuration file for consumption by CMake's `find_package` + # intrinsic + # + install(TARGETS frozen frozen-headers EXPORT frozenConfig) + + # + # Non-testing header files (preserving relative paths) are installed to the + # `include` subdirectory of the `$INSTALL_DIR/${CMAKE_INSTALL_PREFIX}` + # directory. Source file permissions preserved. + # + install(DIRECTORY include/ + DESTINATION include + USE_SOURCE_PERMISSIONS + FILES_MATCHING PATTERN "*.h") + + # + # As a header-only library, there are no target components to be installed + # directly (the PUBLIC_HEADER property is not white listed for INTERFACE + # targets for some reason). + # + # However, it is worthwhile export our target description in order to later + # generate a CMake configuration file for consumption by CMake's `find_package` + # intrinsic + # + write_basic_package_version_file("frozenConfigVersion.cmake" + VERSION ${PROJECT_VERSION} + COMPATIBILITY SameMajorVersion) + + install(FILES "${PROJECT_BINARY_DIR}/frozenConfigVersion.cmake" + DESTINATION share/cmake/frozen) + + install(EXPORT frozenConfig + FILE frozenConfig.cmake + NAMESPACE frozen:: + DESTINATION share/cmake/frozen) + + # + # Rudimentary CPack support. + # + # CPack provides a mechanism to generate installation packaging for a project, + # e.g., self-extracting shell scripts, compressed tarballs, Debian Package files, + # RPM Package Manager files, Windows NSIS installation wizards, + # Apple Disk Images (.dmg), etc. + # + # A packaged installation can be generated by calling + # + # ```sh + # cpack -G --config CPackConfig.cmake + # ``` + # + # See `cpack --help` or the CPack documentation for more information. + # + if(NOT subproject) + set(CPACK_PACKAGE_VENDOR "Quarkslab") + set(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_CURRENT_SOURCE_DIR}/LICENSE") + set(CPACK_PACKAGE_VERSION_MAJOR "${PROJECT_VERSION_MAJOR}") + set(CPACK_PACKAGE_VERSION_MINOR "${PROJECT_VERSION_MINOR}") + set(CPACK_PACKAGE_VERSION_PATCH "${PROJECT_VERSION_PATCH}") + set(CPACK_PACKAGE_DESCRIPTION_SUMMARY "a C++14 header-only, constexpr alternative to gperf") + set(CMAKE_PROJECT_HOMEPAGE_URL "https://blog.quarkslab.com/frozen-an-header-only-constexpr-alternative-to-gperf-for-c14-users.html") + include(CPack) + endif() +endif() diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..5b4b9bd --- /dev/null +++ b/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/README.rst b/README.rst new file mode 100644 index 0000000..5a1ceb9 --- /dev/null +++ b/README.rst @@ -0,0 +1,245 @@ +Frozen +###### + +.. image:: https://travis-ci.org/serge-sans-paille/frozen.svg?branch=master + :target: https://travis-ci.org/serge-sans-paille/frozen + +Header-only library that provides 0 cost initialization for immutable containers, fixed-size containers, and various algorithms. + +Frozen provides: + +- immutable (a.k.a. frozen), ``constexpr``-compatible versions of ``std::set``, + ``std::unordered_set``, ``std::map`` and ``std::unordered_map``. + +- fixed-capacity, ``constinit``-compatible versions of ``std::map`` and + ``std::unordered_map`` with immutable, compile-time selected keys mapped + to mutable values. + +- 0-cost initialization version of ``std::search`` for frozen needles using + Boyer-Moore or Knuth-Morris-Pratt algorithms. + + +The ``unordered_*`` containers are guaranteed *perfect* (a.k.a. no hash +collision) and the extra storage is linear with respect to the number of keys. + +Once initialized, the container keys cannot be updated, and in exchange, lookups +are faster. And initialization is free when ``constexpr`` or ``constinit`` is +used :-). + + +Installation +------------ + +Just copy the ``include/frozen`` directory somewhere and points to it using the ``-I`` flag. Alternatively, using CMake: + +.. code:: sh + + > mkdir build + > cd build + > cmake -D CMAKE_BUILD_TYPE=Release .. + > make install + + +Installation via CMake populates configuration files into the ``/usr/local/share`` +directory which can be consumed by CMake's ``find_package`` instrinsic function. + +Requirements +------------ + +A C++ compiler that supports C++14. Clang version 5 is a good pick, GCC version +6 lags behind in terms of ``constexpr`` compilation time (At least on my +setup), but compiles correctly. Visual Studio 2017 also works correctly! + +Note that gcc 5 isn't supported. (Here's an `old compat branch`_ where a small amount of stuff was ported.) + +.. _old compat branch: https://github.com/cbeck88/frozen/tree/gcc5-support + +Usage +----- + +Compiled with ``-std=c++14`` flag: + +.. code:: C++ + + #include + + constexpr frozen::set some_ints = {1,2,3,5}; + + constexpr bool letitgo = some_ints.count(8); + + extern int n; + bool letitgoooooo = some_ints.count(n); + + +As the constructor and some methods are ``constexpr``, it's also possible to write weird stuff like: + +.. code:: C++ + + #include + + template + std::enable_if_t< frozen::set{{1,11,111}}.count(N), int> foo(); + +String support is built-in: + +.. code:: C++ + + #include + #include + + constexpr frozen::unordered_map olaf = { + {"19", 19}, + {"31", 31}, + }; + constexpr auto val = olaf.at("19"); + +The associative containers have different functionality with and without ``constexpr``. +With ``constexpr``, frozen maps have immutable keys and values. Without ``constexpr``, the +values can be updated in runtime (the keys, however, remain immutable): + +.. code:: C++ + + + #include + #include + + static constinit frozen::unordered_map voice = { + {"Anna", "???"}, + {"Elsa", "???"} + }; + + int main() { + voice.at("Anna") = "Kristen"; + voice.at("Elsa") = "Idina"; + } + +You may also prefer a slightly more DRY initialization syntax: + +.. code:: C++ + + #include + + constexpr auto some_ints = frozen::make_set({1,2,3,5}); + +There are similar ``make_X`` functions for all frozen containers. + +Exception Handling +------------------ + +For compatibility with STL's API, Frozen may eventually throw exceptions, as in +``frozen::map::at``. If you build your code without exception support, or +define the ``FROZEN_NO_EXCEPTIONS`` macro variable, they will be turned into an +``std::abort``. + +Extending +--------- + +Just like the regular C++14 container, you can specialize the hash function, +the key equality comparator for ``unordered_*`` containers, and the comparison +functions for the ordered version. + +It's also possible to specialize the ``frozen::elsa`` structure used for +hashing. Note that unlike `std::hash`, the hasher also takes a seed in addition +to the value being hashed. + +.. code:: C++ + + template struct elsa { + // in case of collisions, different seeds are tried + constexpr std::size_t operator()(T const &value, std::size_t seed) const; + }; + +Ideally, the hash function should have nice statistical properties like *pairwise-independence*: + +If ``x`` and ``y`` are different values, the chance that ``elsa{}(x, seed) == elsa{}(y, seed)`` +should be very low for a random value of ``seed``. + +Note that frozen always ultimately produces a perfect hash function, and you will always have ``O(1)`` +lookup with frozen. It's just that if the input hasher performs poorly, the search will take longer and +your project will take longer to compile. + +Troubleshooting +--------------- + +If you hit a message like this: + +.. code:: none + + [...] + note: constexpr evaluation hit maximum step limit; possible infinite loop? + +Then either you've got a very big container and you should increase Clang's +thresholds, using ``-fconstexpr-steps=1000000000`` for instance, or the hash +functions used by frozen do not suit your data, and you should change them, as +in the following: + +.. code:: c++ + + struct olaf { + constexpr std::size_t operator()(frozen::string const &value, std::size_t seed) const { return seed ^ value[0];} + }; + + constexpr frozen::unordered_set hans = { "a", "b" }; + +Tests and Benchmarks +-------------------- + +Using hand-written Makefiles crafted with love and care: + +.. code:: sh + + > # running tests + > make -C tests check + > # running benchmarks + > make -C benchmarks GOOGLE_BENCHMARK_PREFIX= + +Using CMake to generate a static configuration build system: + +.. code:: sh + + > mkdir build + > cd build + > cmake -D CMAKE_BUILD_TYPE=Release \ + -D frozen.benchmark=ON \ + -G <"Unix Makefiles" or "Ninja"> .. + > # building the tests and benchmarks... + > make # ... with make + > ninja # ... with ninja + > cmake --build . # ... with cmake + > # running the tests... + > make test # ... with make + > ninja test # ... with ninja + > cmake --build . --target test # ... with cmake + > ctest # ... with ctest + > # running the benchmarks... + > make benchmark # ... with make + > ninja benchmark # ... with ninja + > cmake --build . --target benchmark # ... with cmake + +Using CMake to generate an IDE build system with test and benchmark targets + +.. code:: sh + + > mkdir build + > cd build + > cmake -D frozen.benchmark=ON -G <"Xcode" or "Visual Studio 15 2017"> .. + > # using cmake to drive the IDE build, test, and benchmark + > cmake --build . --config Release + > cmake --build . --target test + > cmake --build . --target benchmark + + +Credits +------- + +The perfect hashing is strongly inspired by the blog post `Throw away the keys: +Easy, Minimal Perfect Hashing `_. + +Thanks a lot to Jérôme Dumesnil for his high-quality reviews, and to Chris Beck +for his contributions on perfect hashing. + +Contact +------- + +Serge sans Paille ```` + diff --git a/benchmarks/CMakeLists.txt b/benchmarks/CMakeLists.txt new file mode 100644 index 0000000..7a079c9 --- /dev/null +++ b/benchmarks/CMakeLists.txt @@ -0,0 +1,36 @@ +list(APPEND CMAKE_MODULE_PATH "${frozen_SOURCE_DIR}/cmake") +include(sed) + +find_package(benchmark REQUIRED) + +add_executable(frozen.benchmark "") + +target_link_libraries(frozen.benchmark PUBLIC + frozen::frozen + benchmark::benchmark) + +option(frozen.benchmark.str_search + "Build Benchmark Boyer-Moore string search (requires C++17 compiler)" OFF) + +target_compile_options(frozen.benchmark PUBLIC + $<$:cxx_std_17>) + +sed(${CMAKE_CURRENT_LIST_DIR}/bench_int_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_int_unordered_set.cpp + "set" "unordered_set" "Set" "UnorderedSet") + +sed(${CMAKE_CURRENT_LIST_DIR}/bench_str_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_str_unordered_set.cpp + "set" "unordered_set" "Set" "UnorderedSet") + +target_sources(frozen.benchmark PRIVATE + ${CMAKE_CURRENT_LIST_DIR}/bench_main.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_int_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_str_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/bench_str_map.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_int_unordered_set.cpp + ${frozen_BINARY_DIR}/benchmarks/bench_str_unordered_set.cpp + $<$: + ${CMAKE_CURRENT_LIST_DIR}/bench_str_search.cpp>) + +add_custom_target(benchmark frozen.benchmark) diff --git a/benchmarks/Makefile b/benchmarks/Makefile new file mode 100644 index 0000000..251f2bc --- /dev/null +++ b/benchmarks/Makefile @@ -0,0 +1,27 @@ +ifndef GOOGLE_BENCHMARK_PREFIX + $(error GOOGLE_BENCHMARK_PREFIX is undefined) +endif + +CXXFLAGS=-O2 +override CXXFLAGS+= -std=c++17 #17 for boyer_moore_searcher + +LIBS=-lbenchmark -lpthread +LDFLAGS=-L$(GOOGLE_BENCHMARK_PREFIX)/lib + +CPPFLAGS=-I../include -I$(GOOGLE_BENCHMARK_PREFIX)/include + + +all:bench + ./$< + +bench: bench_main.o bench_str_set.o bench_str_unordered_set.o bench_int_set.o bench_int_unordered_set.o bench_str_search.o + $(CXX) $^ $(LDFLAGS) $(LIBS) -o $@ + +clean: + $(RM) *.o bench bench_str_unordered_set.cpp bench_int_unordered_set.cpp + +bench_str_unordered_set.cpp:bench_str_set.cpp + sed -e 's/set/unordered_set/g' -e 's/Set/UnorderedSet/g' $< > $@ + +bench_int_unordered_set.cpp:bench_int_set.cpp + sed -e 's/set/unordered_set/g' -e 's/Set/UnorderedSet/g' $< > $@ diff --git a/benchmarks/bench_int_set.cpp b/benchmarks/bench_int_set.cpp new file mode 100644 index 0000000..38fa7d3 --- /dev/null +++ b/benchmarks/bench_int_set.cpp @@ -0,0 +1,94 @@ +#include + +#include + +#include +#include +#include + +static constexpr frozen::set Keywords{ + 0, 2, 4, 6, 8, 10, 12, 14, + 16, 18, 20, 22, 24, 26, 28, 30, + 32, 34, 36, 38, 40, 42, 44, 46, + 48, 50, 52, 54, 56, 58, 60, 62 +}; + +static auto const* volatile Some = &Keywords; + +static void BM_IntInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntInFzSet); + +static const std::set Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_IntInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_IntInStdSet); + +static const std::array Keywords__{{ + 0, 2, 4, 6, 8, 10, 12, 14, + 16, 18, 20, 22, 24, 26, 28, 30, + 32, 34, 36, 38, 40, 42, 44, 46, + 48, 50, 52, 54, 56, 58, 60, 62 +}}; +static void BM_IntInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_IntInStdArray); + +static const int SomeInts[32] = { + 1, 3, 5, 7, 9, 11, 13, 15, + 17, 19, 21, 23, 25, 27, 29, 31, + 33, 35, 37, 39, 41, 43, 45, 47, + 49, 51, 53, 55, 57, 59, 61, 63 +}; +static auto const * volatile SomeIntsPtr = &SomeInts; + +static void BM_IntNotInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInFzSet); + +static void BM_IntNotInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInStdSet); + +static void BM_IntNotInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeIntsPtr) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_IntNotInStdArray); diff --git a/benchmarks/bench_main.cpp b/benchmarks/bench_main.cpp new file mode 100644 index 0000000..71144c2 --- /dev/null +++ b/benchmarks/bench_main.cpp @@ -0,0 +1,2 @@ +#include +BENCHMARK_MAIN(); diff --git a/benchmarks/bench_str_map.cpp b/benchmarks/bench_str_map.cpp new file mode 100644 index 0000000..efe24b2 --- /dev/null +++ b/benchmarks/bench_str_map.cpp @@ -0,0 +1,84 @@ +#include + +#include +#include + +#include +#include +#include +#include + +static constexpr frozen::unordered_map Keywords{ + {"auto", "keyword"}, {"break", "keyword"}, {"case", "keyword"}, {"char", "keyword"}, {"const", "keyword"}, {"continue", "keyword"}, + {"default", "keyword"}, {"do", "keyword"}, {"double", "keyword"}, {"else", "keyword"}, {"enum", "keyword"}, {"extern", "keyword"}, + {"float", "keyword"}, {"for", "keyword"}, {"goto", "keyword"}, {"if", "keyword"}, {"int", "keyword"}, {"long", "keyword"}, + {"register", "keyword"}, {"return", "keyword"}, {"short", "keyword"}, {"signed", "keyword"}, {"sizeof", "keyword"}, {"static", "keyword"}, + {"struct", "keyword"}, {"switch", "keyword"}, {"typedef", "keyword"}, {"union", "keyword"}, {"unsigned", "keyword"}, + {"void", "keyword"}, {"volatile", "keyword"}, {"while", "keyword"} +}; + +static auto const *volatile Some = &Keywords; + +static void BM_StrInFzUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *Some) + { + volatile bool status = Keywords.count(kw.first); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrInFzUnorderedMap); + +static const std::unordered_map Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_StrInStdUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *Some) + { + volatile bool status = Keywords_.count(kw.first); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdUnorderedMap); + +static const frozen::string SomeStrings[32] = { + "auto0", "break0", "case0", "char0", "const0", "continue0", + "default0", "do0", "double0", "else0", "enum0", "extern0", + "float0", "for0", "goto0", "if0", "int0", "long0", + "register0", "return0", "short0", "signed0", "sizeof0", "static0", + "struct0", "switch0", "typedef0", "union0", "unsigned0", "void0", + "volatile0", "while0"}; +static auto const *volatile SomeStringsPtr = &SomeStrings; + +static void BM_StrNotInFzUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *SomeStringsPtr) + { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInFzUnorderedMap); + +static void BM_StrNotInStdUnorderedMap(benchmark::State &state) +{ + for (auto _ : state) + { + for (auto kw : *SomeStringsPtr) + { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInStdUnorderedMap); diff --git a/benchmarks/bench_str_search.cpp b/benchmarks/bench_str_search.cpp new file mode 100644 index 0000000..945b8a8 --- /dev/null +++ b/benchmarks/bench_str_search.cpp @@ -0,0 +1,68 @@ +#include +#include "frozen/algorithm.h" +#include +#include +#include + +static char const Words [] = R"( +Let it go, let it go +Can't hold it back anymore +Let it go, let it go +Turn my back and slam the door +The snow blows white on the mountain tonight +Not a footprint to be seen +A kingdom of isolation and it looks like I'm the queen +The wind is howling like the swirling storm inside +Couldn't keep it in +Heaven knows I try +Don't let them in, don't let them see +Be the good girl you always had to be +Conceal, don't feel, don't let them know +Well now they know +Let it go, let it go +Can't hold you back anymore +Let it go, let it go +Turn my back and slam the door +And here I stand +And here I'll stay +Let it go, let it go +The cold never bothered me anyway +It's funny how some distance makes everything seem small +And the fears that once controlled me can't get to me at all +Up here +)"; + +static auto * volatile WordsPtr = &Words; + +static constexpr char Word[] = "controlled"; + +static void BM_StrFzSearchInBM(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = frozen::search(std::begin(*WordsPtr), std::end(*WordsPtr), frozen::make_boyer_moore_searcher(Word)); + } +} +BENCHMARK(BM_StrFzSearchInBM); + +static void BM_StrStdSearchInBM(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = std::search(std::begin(*WordsPtr), std::end(*WordsPtr), + std::boyer_moore_searcher(std::begin(Word), std::end(Word))); + } +} +BENCHMARK(BM_StrStdSearchInBM); + +static void BM_StrFzSearchInKMP(benchmark::State& state) { + for (auto _ : state) { + volatile bool status = frozen::search(std::begin(*WordsPtr), std::end(*WordsPtr), frozen::make_knuth_morris_pratt_searcher(Word)); + } +} +BENCHMARK(BM_StrFzSearchInKMP); + +#if 0 +static void BM_StrStdSearchInStrStr(benchmark::State& state) { + for (auto _ : state) { + char const* volatile status = std::strstr(*WordsPtr, Word); + } +} +BENCHMARK(BM_StrStdSearchInStrStr); +#endif diff --git a/benchmarks/bench_str_set.cpp b/benchmarks/bench_str_set.cpp new file mode 100644 index 0000000..fe83cc3 --- /dev/null +++ b/benchmarks/bench_str_set.cpp @@ -0,0 +1,102 @@ +#include + +#include +#include + +#include +#include +#include +#include + +static constexpr frozen::set Keywords{ + "auto", "break", "case", "char", "const", "continue", + "default", "do", "double", "else", "enum", "extern", + "float", "for", "goto", "if", "int", "long", + "register", "return", "short", "signed", "sizeof", "static", + "struct", "switch", "typedef", "union", "unsigned", "void", + "volatile", "while"}; + +static auto const* volatile Some = &Keywords; + +static void BM_StrInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrInFzSet); + +static const std::set Keywords_(Keywords.begin(), Keywords.end()); + +static void BM_StrInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdSet); + +static const std::array Keywords__{ + "auto", "break", "case", "char", "const", "continue", + "default", "do", "double", "else", "enum", "extern", + "float", "for", "goto", "if", "int", "long", + "register", "return", "short", "signed", "sizeof", "static", + "struct", "switch", "typedef", "union", "unsigned", "void", + "volatile", "while"}; + +static void BM_StrInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *Some) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrInStdArray); + + +static const frozen::string SomeStrings[32] = { + "auto0", "break0", "case0", "char0", "const0", "continue0", + "default0", "do0", "double0", "else0", "enum0", "extern0", + "float0", "for0", "goto0", "if0", "int0", "long0", + "register0", "return0", "short0", "signed0", "sizeof0", "static0", + "struct0", "switch0", "typedef0", "union0", "unsigned0", "void0", + "volatile0", "while0"}; +static auto const * volatile SomeStringsPtr = &SomeStrings; + +static void BM_StrNotInFzSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = Keywords.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInFzSet); + +static void BM_StrNotInStdSet(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = Keywords_.count(kw); + benchmark::DoNotOptimize(status); + } + } +} +BENCHMARK(BM_StrNotInStdSet); + +static void BM_StrNotInStdArray(benchmark::State& state) { + for (auto _ : state) { + for(auto kw : *SomeStringsPtr) { + volatile bool status = std::find(Keywords__.begin(), Keywords__.end(), kw) != Keywords__.end(); + benchmark::DoNotOptimize(status); + } + } +} + +BENCHMARK(BM_StrNotInStdArray); diff --git a/cmake/CTestCustom.cmake b/cmake/CTestCustom.cmake new file mode 100644 index 0000000..d6ddbcf --- /dev/null +++ b/cmake/CTestCustom.cmake @@ -0,0 +1,5 @@ +set(CTEST_CUSTOM_COVERAGE_EXCLUDE + ".*examples.*" + ".*tests.*" + ".*benchmark.*" + ".*c[+][+].*") diff --git a/cmake/detect_cxx_version.cmake b/cmake/detect_cxx_version.cmake new file mode 100644 index 0000000..2021650 --- /dev/null +++ b/cmake/detect_cxx_version.cmake @@ -0,0 +1,45 @@ +set(cxx17_minimum_msvc_version 19.14) +set(cxx17_minimum_gcc_version 7.0) +set(cxx17_minimum_clang_version 4.0) +set(cxx17_minimum_appleclang_version 6.0) + +set(cxx20_minimum_msvc_version 19.22) +set(cxx20_minimum_gcc_version 9.0) +set(cxx20_minimum_clang_version 7.0) +set(cxx20_minimum_appleclang_version 10.0) + +set(cxx_17_supported OFF) + +if(MSVC AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx17_minimum_msvc_version}) + set(cxx_17_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx17_minimum_gcc_version}) + set(cxx_17_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx17_minimum_clang_version}) + set(cxx_17_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "AppleClang" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx17_minimum_appleclang_version}) + set(cxx_17_supported ON) +endif() + +set(cxx_20_supported OFF) + +if(MSVC AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx20_minimum_msvc_version}) + set(cxx_20_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx20_minimum_gcc_version}) + set(cxx_20_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx20_minimum_clang_version}) + set(cxx_20_supported ON) +endif() + +if(CMAKE_CXX_COMPILER_ID STREQUAL "AppleClang" AND NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS ${cxx20_minimum_appleclang_version}) + set(cxx_20_supported ON) +endif() diff --git a/cmake/sed.cmake b/cmake/sed.cmake new file mode 100644 index 0000000..feb0f1e --- /dev/null +++ b/cmake/sed.cmake @@ -0,0 +1,12 @@ +set(SED_SCRIPT "${CMAKE_CURRENT_LIST_DIR}/sed.script.cmake" + CACHE INTERNAL "path to sed script") + +function(sed input_file output_file) + add_custom_command(OUTPUT "${output_file}" + COMMAND ${CMAKE_COMMAND} + -Dinput_file="${input_file}" + -Doutput_file="${output_file}" + -Dreplacement_pairs="${ARGN}" + -P ${SED_SCRIPT} + DEPENDS "${input_file}") +endfunction() diff --git a/cmake/sed.script.cmake b/cmake/sed.script.cmake new file mode 100644 index 0000000..a596736 --- /dev/null +++ b/cmake/sed.script.cmake @@ -0,0 +1,18 @@ +string(REPLACE " " ";" replacement_pairs ${replacement_pairs}) + +file(READ "${input_file}" text) + +list(LENGTH replacement_pairs length) +math(EXPR last_index "${length} - 1") + +foreach(regex_index RANGE 0 ${last_index} 2) + math(EXPR replacement_index "${regex_index} + 1") + LIST(GET replacement_pairs ${regex_index} regex_expression) + LIST(GET replacement_pairs ${replacement_index} replacement_expression) + string(REPLACE + "${regex_expression}" + "${replacement_expression}" + text "${text}") +endforeach() + +file(WRITE ${output_file} "${text}") diff --git a/examples/CMakeLists.txt b/examples/CMakeLists.txt new file mode 100644 index 0000000..2ae5917 --- /dev/null +++ b/examples/CMakeLists.txt @@ -0,0 +1,16 @@ +set(frozen.examples.srcs enum_to_string enum_to_string_hash pixel_art static_assert value_modification) + +if ("${CMAKE_CXX_COMPILER_ID}" MATCHES ".*Clang") + list(APPEND frozen.examples.srcs html_entities_map) +endif() + +foreach(src IN LISTS frozen.examples.srcs) + add_executable(frozen.example.${src} ${src}.cpp) + target_link_libraries(frozen.example.${src} PUBLIC frozen::frozen) +endforeach() + +if (TARGET frozen.example.html_entities_map) + target_compile_options(frozen.example.html_entities_map PUBLIC + $<$:-fconstexpr-steps=123456789> + $<$:-fconstexpr-steps=123456789>) +endif() diff --git a/examples/enum_to_string.cpp b/examples/enum_to_string.cpp new file mode 100644 index 0000000..a602400 --- /dev/null +++ b/examples/enum_to_string.cpp @@ -0,0 +1,172 @@ +#include // for std::puts + +/* ELF Relocations */ + +#define ELF_RELOC(name, value) name = value, + +/** i386 relocations. */ +enum RELOC_i386 { + +#ifndef ELF_RELOC +#error "ELF_RELOC must be defined" +#endif + +/* TODO: this is just a subset */ +ELF_RELOC(R_386_NONE, 0) +ELF_RELOC(R_386_32, 1) +ELF_RELOC(R_386_PC32, 2) +ELF_RELOC(R_386_GOT32, 3) +ELF_RELOC(R_386_PLT32, 4) +ELF_RELOC(R_386_COPY, 5) +ELF_RELOC(R_386_GLOB_DAT, 6) +ELF_RELOC(R_386_JUMP_SLOT, 7) +ELF_RELOC(R_386_RELATIVE, 8) +ELF_RELOC(R_386_GOTOFF, 9) +ELF_RELOC(R_386_GOTPC, 10) +ELF_RELOC(R_386_32PLT, 11) +ELF_RELOC(R_386_TLS_TPOFF, 14) +ELF_RELOC(R_386_TLS_IE, 15) +ELF_RELOC(R_386_TLS_GOTIE, 16) +ELF_RELOC(R_386_TLS_LE, 17) +ELF_RELOC(R_386_TLS_GD, 18) +ELF_RELOC(R_386_TLS_LDM, 19) +ELF_RELOC(R_386_16, 20) +ELF_RELOC(R_386_PC16, 21) +ELF_RELOC(R_386_8, 22) +ELF_RELOC(R_386_PC8, 23) +ELF_RELOC(R_386_TLS_GD_32, 24) +ELF_RELOC(R_386_TLS_GD_PUSH, 25) +ELF_RELOC(R_386_TLS_GD_CALL, 26) +ELF_RELOC(R_386_TLS_GD_POP, 27) +ELF_RELOC(R_386_TLS_LDM_32, 28) +ELF_RELOC(R_386_TLS_LDM_PUSH, 29) +ELF_RELOC(R_386_TLS_LDM_CALL, 30) +ELF_RELOC(R_386_TLS_LDM_POP, 31) +ELF_RELOC(R_386_TLS_LDO_32, 32) +ELF_RELOC(R_386_TLS_IE_32, 33) +ELF_RELOC(R_386_TLS_LE_32, 34) +ELF_RELOC(R_386_TLS_DTPMOD32, 35) +ELF_RELOC(R_386_TLS_DTPOFF32, 36) +ELF_RELOC(R_386_TLS_TPOFF32, 37) +ELF_RELOC(R_386_TLS_GOTDESC, 39) +ELF_RELOC(R_386_TLS_DESC_CALL, 40) +ELF_RELOC(R_386_TLS_DESC, 41) +ELF_RELOC(R_386_IRELATIVE, 42) +ELF_RELOC(R_386_NUM, 43) +}; + +#ifndef SWITCH_VERSION + +#ifdef FROZEN_VERSION +#include "frozen/map.h" +#else +#include +#endif + +#ifdef FROZEN_VERSION +constexpr +frozen::map +#else +const +std::map +#endif +e2s = { + { RELOC_i386::R_386_NONE, "NONE"}, + { RELOC_i386::R_386_32, "R32"}, + { RELOC_i386::R_386_PC32, "PC32"}, + { RELOC_i386::R_386_GOT32, "GOT32"}, + { RELOC_i386::R_386_PLT32, "PLT32"}, + { RELOC_i386::R_386_COPY, "COPY"}, + { RELOC_i386::R_386_GLOB_DAT, "GLOB_DAT"}, + { RELOC_i386::R_386_JUMP_SLOT, "JUMP_SLOT"}, + { RELOC_i386::R_386_RELATIVE, "RELATIVE"}, + { RELOC_i386::R_386_GOTOFF, "GOTOFF"}, + { RELOC_i386::R_386_GOTPC, "GOTPC"}, + { RELOC_i386::R_386_32PLT, "R32PLT"}, + { RELOC_i386::R_386_TLS_TPOFF, "TLS_TPOFF"}, + { RELOC_i386::R_386_TLS_IE, "TLS_IE"}, + { RELOC_i386::R_386_TLS_GOTIE, "TLS_GOTIE"}, + { RELOC_i386::R_386_TLS_LE, "TLS_LE"}, + { RELOC_i386::R_386_TLS_GD, "TLS_GD"}, + { RELOC_i386::R_386_TLS_LDM, "TLS_LDM"}, + { RELOC_i386::R_386_16, "R16"}, + { RELOC_i386::R_386_PC16, "PC16"}, + { RELOC_i386::R_386_8, "R8"}, + { RELOC_i386::R_386_PC8, "PC8"}, + { RELOC_i386::R_386_TLS_GD_32, "TLS_GD_32"}, + { RELOC_i386::R_386_TLS_GD_PUSH, "TLS_GD_PUSH"}, + { RELOC_i386::R_386_TLS_GD_CALL, "TLS_GD_CALL"}, + { RELOC_i386::R_386_TLS_GD_POP, "TLS_GD_POP"}, + { RELOC_i386::R_386_TLS_LDM_32, "TLS_LDM_32"}, + { RELOC_i386::R_386_TLS_LDM_PUSH, "TLS_LDM_PUSH"}, + { RELOC_i386::R_386_TLS_LDM_CALL, "TLS_LDM_CALL"}, + { RELOC_i386::R_386_TLS_LDM_POP, "TLS_LDM_POP"}, + { RELOC_i386::R_386_TLS_LDO_32, "TLS_LDO_32"}, + { RELOC_i386::R_386_TLS_IE_32, "TLS_IE_32"}, + { RELOC_i386::R_386_TLS_LE_32, "TLS_LE_32"}, + { RELOC_i386::R_386_TLS_DTPMOD32, "TLS_DTPMOD32"}, + { RELOC_i386::R_386_TLS_DTPOFF32, "TLS_DTPOFF32"}, + { RELOC_i386::R_386_TLS_TPOFF32, "TLS_TPOFF32"}, + { RELOC_i386::R_386_TLS_GOTDESC, "TLS_GOTDESC"}, + { RELOC_i386::R_386_TLS_DESC_CALL, "TLS_DESC_CALL"}, + { RELOC_i386::R_386_TLS_DESC, "TLS_DESC"}, + { RELOC_i386::R_386_IRELATIVE, "IRELATIVE"}, + { RELOC_i386::R_386_NUM, "NUM"}, +}; + +char const * enum_to_string(RELOC_i386 e) { + return e2s.at(e); +} +#else +char const * enum_to_string(RELOC_i386 e) { + switch(e) { + case RELOC_i386::R_386_NONE: return "NONE"; + case RELOC_i386::R_386_32: return "R32"; + case RELOC_i386::R_386_PC32: return "PC32"; + case RELOC_i386::R_386_GOT32: return "GOT32"; + case RELOC_i386::R_386_PLT32: return "PLT32"; + case RELOC_i386::R_386_COPY: return "COPY"; + case RELOC_i386::R_386_GLOB_DAT: return "GLOB_DAT"; + case RELOC_i386::R_386_JUMP_SLOT: return "JUMP_SLOT"; + case RELOC_i386::R_386_RELATIVE: return "RELATIVE"; + case RELOC_i386::R_386_GOTOFF: return "GOTOFF"; + case RELOC_i386::R_386_GOTPC: return "GOTPC"; + case RELOC_i386::R_386_32PLT: return "R32PLT"; + case RELOC_i386::R_386_TLS_TPOFF: return "TLS_TPOFF"; + case RELOC_i386::R_386_TLS_IE: return "TLS_IE"; + case RELOC_i386::R_386_TLS_GOTIE: return "TLS_GOTIE"; + case RELOC_i386::R_386_TLS_LE: return "TLS_LE"; + case RELOC_i386::R_386_TLS_GD: return "TLS_GD"; + case RELOC_i386::R_386_TLS_LDM: return "TLS_LDM"; + case RELOC_i386::R_386_16: return "R16"; + case RELOC_i386::R_386_PC16: return "PC16"; + case RELOC_i386::R_386_8: return "R8"; + case RELOC_i386::R_386_PC8: return "PC8"; + case RELOC_i386::R_386_TLS_GD_32: return "TLS_GD_32"; + case RELOC_i386::R_386_TLS_GD_PUSH: return "TLS_GD_PUSH"; + case RELOC_i386::R_386_TLS_GD_CALL: return "TLS_GD_CALL"; + case RELOC_i386::R_386_TLS_GD_POP: return "TLS_GD_POP"; + case RELOC_i386::R_386_TLS_LDM_32: return "TLS_LDM_32"; + case RELOC_i386::R_386_TLS_LDM_PUSH: return "TLS_LDM_PUSH"; + case RELOC_i386::R_386_TLS_LDM_CALL: return "TLS_LDM_CALL"; + case RELOC_i386::R_386_TLS_LDM_POP: return "TLS_LDM_POP"; + case RELOC_i386::R_386_TLS_LDO_32: return "TLS_LDO_32"; + case RELOC_i386::R_386_TLS_IE_32: return "TLS_IE_32"; + case RELOC_i386::R_386_TLS_LE_32: return "TLS_LE_32"; + case RELOC_i386::R_386_TLS_DTPMOD32: return "TLS_DTPMOD32"; + case RELOC_i386::R_386_TLS_DTPOFF32: return "TLS_DTPOFF32"; + case RELOC_i386::R_386_TLS_TPOFF32: return "TLS_TPOFF32"; + case RELOC_i386::R_386_TLS_GOTDESC: return "TLS_GOTDESC"; + case RELOC_i386::R_386_TLS_DESC_CALL: return "TLS_DESC_CALL"; + case RELOC_i386::R_386_TLS_DESC: return "TLS_DESC"; + case RELOC_i386::R_386_IRELATIVE: return "IRELATIVE"; + case RELOC_i386::R_386_NUM: return "NUM"; + } +} + +#endif + +int main() { + std::puts(enum_to_string(RELOC_i386::R_386_8)); + return 0; +} diff --git a/examples/enum_to_string_hash.cpp b/examples/enum_to_string_hash.cpp new file mode 100644 index 0000000..18b0b69 --- /dev/null +++ b/examples/enum_to_string_hash.cpp @@ -0,0 +1,127 @@ +#include // for std::puts + +/* ELF Relocations */ + +#define ELF_RELOC(name, value) name = value, + +/** i386 relocations. */ +enum RELOC_i386 { + +#ifndef ELF_RELOC +#error "ELF_RELOC must be defined" +#endif + +/* TODO: this is just a subset */ +ELF_RELOC(R_386_NONE, 0) +ELF_RELOC(R_386_32, 1) +ELF_RELOC(R_386_PC32, 2) +ELF_RELOC(R_386_GOT32, 3) +ELF_RELOC(R_386_PLT32, 4) +ELF_RELOC(R_386_COPY, 5) +ELF_RELOC(R_386_GLOB_DAT, 6) +ELF_RELOC(R_386_JUMP_SLOT, 7) +ELF_RELOC(R_386_RELATIVE, 8) +ELF_RELOC(R_386_GOTOFF, 9) +ELF_RELOC(R_386_GOTPC, 10) +ELF_RELOC(R_386_32PLT, 11) +ELF_RELOC(R_386_TLS_TPOFF, 14) +ELF_RELOC(R_386_TLS_IE, 15) +ELF_RELOC(R_386_TLS_GOTIE, 16) +ELF_RELOC(R_386_TLS_LE, 17) +ELF_RELOC(R_386_TLS_GD, 18) +ELF_RELOC(R_386_TLS_LDM, 19) +ELF_RELOC(R_386_16, 20) +ELF_RELOC(R_386_PC16, 21) +ELF_RELOC(R_386_8, 22) +ELF_RELOC(R_386_PC8, 23) +ELF_RELOC(R_386_TLS_GD_32, 24) +ELF_RELOC(R_386_TLS_GD_PUSH, 25) +ELF_RELOC(R_386_TLS_GD_CALL, 26) +ELF_RELOC(R_386_TLS_GD_POP, 27) +ELF_RELOC(R_386_TLS_LDM_32, 28) +ELF_RELOC(R_386_TLS_LDM_PUSH, 29) +ELF_RELOC(R_386_TLS_LDM_CALL, 30) +ELF_RELOC(R_386_TLS_LDM_POP, 31) +ELF_RELOC(R_386_TLS_LDO_32, 32) +ELF_RELOC(R_386_TLS_IE_32, 33) +ELF_RELOC(R_386_TLS_LE_32, 34) +ELF_RELOC(R_386_TLS_DTPMOD32, 35) +ELF_RELOC(R_386_TLS_DTPOFF32, 36) +ELF_RELOC(R_386_TLS_TPOFF32, 37) +ELF_RELOC(R_386_TLS_GOTDESC, 39) +ELF_RELOC(R_386_TLS_DESC_CALL, 40) +ELF_RELOC(R_386_TLS_DESC, 41) +ELF_RELOC(R_386_IRELATIVE, 42) +ELF_RELOC(R_386_NUM, 43) +}; + +#ifdef FROZEN_VERSION +#include "frozen/unordered_map.h" +namespace frozen { + template <> struct elsa : elsa { + }; +} +#else +#include +#endif + +#ifdef FROZEN_VERSION +constexpr +frozen::unordered_map +#else +const +std::unordered_map +#endif +e2s = { + { RELOC_i386::R_386_NONE, "NONE"}, + { RELOC_i386::R_386_32, "R32"}, + { RELOC_i386::R_386_PC32, "PC32"}, + { RELOC_i386::R_386_GOT32, "GOT32"}, + { RELOC_i386::R_386_PLT32, "PLT32"}, + { RELOC_i386::R_386_COPY, "COPY"}, + { RELOC_i386::R_386_GLOB_DAT, "GLOB_DAT"}, + { RELOC_i386::R_386_JUMP_SLOT, "JUMP_SLOT"}, + { RELOC_i386::R_386_RELATIVE, "RELATIVE"}, + { RELOC_i386::R_386_GOTOFF, "GOTOFF"}, + { RELOC_i386::R_386_GOTPC, "GOTPC"}, + { RELOC_i386::R_386_32PLT, "R32PLT"}, + { RELOC_i386::R_386_TLS_TPOFF, "TLS_TPOFF"}, + { RELOC_i386::R_386_TLS_IE, "TLS_IE"}, + { RELOC_i386::R_386_TLS_GOTIE, "TLS_GOTIE"}, + { RELOC_i386::R_386_TLS_LE, "TLS_LE"}, + { RELOC_i386::R_386_TLS_GD, "TLS_GD"}, + { RELOC_i386::R_386_TLS_LDM, "TLS_LDM"}, + { RELOC_i386::R_386_16, "R16"}, + { RELOC_i386::R_386_PC16, "PC16"}, + { RELOC_i386::R_386_8, "R8"}, + { RELOC_i386::R_386_PC8, "PC8"}, + { RELOC_i386::R_386_TLS_GD_32, "TLS_GD_32"}, + { RELOC_i386::R_386_TLS_GD_PUSH, "TLS_GD_PUSH"}, + { RELOC_i386::R_386_TLS_GD_CALL, "TLS_GD_CALL"}, + { RELOC_i386::R_386_TLS_GD_POP, "TLS_GD_POP"}, + { RELOC_i386::R_386_TLS_LDM_32, "TLS_LDM_32"}, + { RELOC_i386::R_386_TLS_LDM_PUSH, "TLS_LDM_PUSH"}, + { RELOC_i386::R_386_TLS_LDM_CALL, "TLS_LDM_CALL"}, + { RELOC_i386::R_386_TLS_LDM_POP, "TLS_LDM_POP"}, + { RELOC_i386::R_386_TLS_LDO_32, "TLS_LDO_32"}, + { RELOC_i386::R_386_TLS_IE_32, "TLS_IE_32"}, + { RELOC_i386::R_386_TLS_LE_32, "TLS_LE_32"}, + { RELOC_i386::R_386_TLS_DTPMOD32, "TLS_DTPMOD32"}, + { RELOC_i386::R_386_TLS_DTPOFF32, "TLS_DTPOFF32"}, + { RELOC_i386::R_386_TLS_TPOFF32, "TLS_TPOFF32"}, + { RELOC_i386::R_386_TLS_GOTDESC, "TLS_GOTDESC"}, + { RELOC_i386::R_386_TLS_DESC_CALL, "TLS_DESC_CALL"}, + { RELOC_i386::R_386_TLS_DESC, "TLS_DESC"}, + { RELOC_i386::R_386_IRELATIVE, "IRELATIVE"}, + { RELOC_i386::R_386_NUM, "NUM"}, +}; + +char const * enum_to_string(RELOC_i386 e) { + return e2s.at(e); +} + +int main() { + std::puts(enum_to_string(RELOC_i386::R_386_8)); + return 0; +} + diff --git a/examples/html_entities_map.cpp b/examples/html_entities_map.cpp new file mode 100644 index 0000000..ac7d922 --- /dev/null +++ b/examples/html_entities_map.cpp @@ -0,0 +1,2147 @@ + +#include +#include +#include + +struct codes_t +{ + uint32_t iCodepoint1; + uint32_t iCodepoint2{0}; +}; + +static constexpr std::pair s_Entities[] +{ + { "AElig" , { 0xC6 }}, + { "AMP" , { 0x26 }}, + { "Aacute" , { 0xC1 }}, + { "Abreve" , { 0x0102 }}, + { "Acirc" , { 0xC2 }}, + { "Acy" , { 0x0410 }}, + { "Afr" , { 0x01D504 }}, + { "Agrave" , { 0xC0 }}, + { "Alpha" , { 0x0391 }}, + { "Amacr" , { 0x0100 }}, + { "And" , { 0x2A53 }}, + { "Aogon" , { 0x0104 }}, + { "Aopf" , { 0x01D538 }}, + { "ApplyFunction" , { 0x2061 }}, + { "Aring" , { 0xC5 }}, + { "Ascr" , { 0x01D49C }}, + { "Assign" , { 0x2254 }}, + { "Atilde" , { 0xC3 }}, + { "Auml" , { 0xC4 }}, + { "Backslash" , { 0x2216 }}, + { "Barv" , { 0x2AE7 }}, + { "Barwed" , { 0x2306 }}, + { "Bcy" , { 0x0411 }}, + { "Because" , { 0x2235 }}, + { "Bernoullis" , { 0x212C }}, + { "Beta" , { 0x0392 }}, + { "Bfr" , { 0x01D505 }}, + { "Bopf" , { 0x01D539 }}, + { "Breve" , { 0x02D8 }}, + { "Bscr" , { 0x212C }}, + { "Bumpeq" , { 0x224E }}, + { "CHcy" , { 0x0427 }}, + { "COPY" , { 0xA9 }}, + { "Cacute" , { 0x0106 }}, + { "Cap" , { 0x22D2 }}, + { "CapitalDifferentialD" , { 0x2145 }}, + { "Cayleys" , { 0x212D }}, + { "Ccaron" , { 0x010C }}, + { "Ccedil" , { 0xC7 }}, + { "Ccirc" , { 0x0108 }}, + { "Cconint" , { 0x2230 }}, + { "Cdot" , { 0x010A }}, + { "Cedilla" , { 0xB8 }}, + { "CenterDot" , { 0xB7 }}, + { "Cfr" , { 0x212D }}, + { "Chi" , { 0x03A7 }}, + { "CircleDot" , { 0x2299 }}, + { "CircleMinus" , { 0x2296 }}, + { "CirclePlus" , { 0x2295 }}, + { "CircleTimes" , { 0x2297 }}, + { "ClockwiseContourIntegral" , { 0x2232 }}, + { "CloseCurlyDoubleQuote" , { 0x201D }}, + { "CloseCurlyQuote" , { 0x2019 }}, + { "Colon" , { 0x2237 }}, + { "Colone" , { 0x2A74 }}, + { "Congruent" , { 0x2261 }}, + { "Conint" , { 0x222F }}, + { "ContourIntegral" , { 0x222E }}, + { "Copf" , { 0x2102 }}, + { "Coproduct" , { 0x2210 }}, + { "CounterClockwiseContourIntegral" , { 0x2233 }}, + { "Cross" , { 0x2A2F }}, + { "Cscr" , { 0x01D49E }}, + { "Cup" , { 0x22D3 }}, + { "CupCap" , { 0x224D }}, + { "DD" , { 0x2145 }}, + { "DDotrahd" , { 0x2911 }}, + { "DJcy" , { 0x0402 }}, + { "DScy" , { 0x0405 }}, + { "DZcy" , { 0x040F }}, + { "Dagger" , { 0x2021 }}, + { "Darr" , { 0x21A1 }}, + { "Dashv" , { 0x2AE4 }}, + { "Dcaron" , { 0x010E }}, + { "Dcy" , { 0x0414 }}, + { "Del" , { 0x2207 }}, + { "Delta" , { 0x0394 }}, + { "Dfr" , { 0x01D507 }}, + { "DiacriticalAcute" , { 0xB4 }}, + { "DiacriticalDot" , { 0x02D9 }}, + { "DiacriticalDoubleAcute" , { 0x02DD }}, + { "DiacriticalGrave" , { 0x60 }}, + { "DiacriticalTilde" , { 0x02DC }}, + { "Diamond" , { 0x22C4 }}, + { "DifferentialD" , { 0x2146 }}, + { "Dopf" , { 0x01D53B }}, + { "Dot" , { 0xA8 }}, + { "DotDot" , { 0x20DC }}, + { "DotEqual" , { 0x2250 }}, + { "DoubleContourIntegral" , { 0x222F }}, + { "DoubleDot" , { 0xA8 }}, + { "DoubleDownArrow" , { 0x21D3 }}, + { "DoubleLeftArrow" , { 0x21D0 }}, + { "DoubleLeftRightArrow" , { 0x21D4 }}, + { "DoubleLeftTee" , { 0x2AE4 }}, + { "DoubleLongLeftArrow" , { 0x27F8 }}, + { "DoubleLongLeftRightArrow" , { 0x27FA }}, + { "DoubleLongRightArrow" , { 0x27F9 }}, + { "DoubleRightArrow" , { 0x21D2 }}, + { "DoubleRightTee" , { 0x22A8 }}, + { "DoubleUpArrow" , { 0x21D1 }}, + { "DoubleUpDownArrow" , { 0x21D5 }}, + { "DoubleVerticalBar" , { 0x2225 }}, + { "DownArrow" , { 0x2193 }}, + { "DownArrowBar" , { 0x2913 }}, + { "DownArrowUpArrow" , { 0x21F5 }}, + { "DownBreve" , { 0x0311 }}, + { "DownLeftRightVector" , { 0x2950 }}, + { "DownLeftTeeVector" , { 0x295E }}, + { "DownLeftVector" , { 0x21BD }}, + { "DownLeftVectorBar" , { 0x2956 }}, + { "DownRightTeeVector" , { 0x295F }}, + { "DownRightVector" , { 0x21C1 }}, + { "DownRightVectorBar" , { 0x2957 }}, + { "DownTee" , { 0x22A4 }}, + { "DownTeeArrow" , { 0x21A7 }}, + { "Downarrow" , { 0x21D3 }}, + { "Dscr" , { 0x01D49F }}, + { "Dstrok" , { 0x0110 }}, + { "ENG" , { 0x014A }}, + { "ETH" , { 0xD0 }}, + { "Eacute" , { 0xC9 }}, + { "Ecaron" , { 0x011A }}, + { "Ecirc" , { 0xCA }}, + { "Ecy" , { 0x042D }}, + { "Edot" , { 0x0116 }}, + { "Efr" , { 0x01D508 }}, + { "Egrave" , { 0xC8 }}, + { "Element" , { 0x2208 }}, + { "Emacr" , { 0x0112 }}, + { "EmptySmallSquare" , { 0x25FB }}, + { "EmptyVerySmallSquare" , { 0x25AB }}, + { "Eogon" , { 0x0118 }}, + { "Eopf" , { 0x01D53C }}, + { "Epsilon" , { 0x0395 }}, + { "Equal" , { 0x2A75 }}, + { "EqualTilde" , { 0x2242 }}, + { "Equilibrium" , { 0x21CC }}, + { "Escr" , { 0x2130 }}, + { "Esim" , { 0x2A73 }}, + { "Eta" , { 0x0397 }}, + { "Euml" , { 0xCB }}, + { "Exists" , { 0x2203 }}, + { "ExponentialE" , { 0x2147 }}, + { "Fcy" , { 0x0424 }}, + { "Ffr" , { 0x01D509 }}, + { "FilledSmallSquare" , { 0x25FC }}, + { "FilledVerySmallSquare" , { 0x25AA }}, + { "Fopf" , { 0x01D53D }}, + { "ForAll" , { 0x2200 }}, + { "Fouriertrf" , { 0x2131 }}, + { "Fscr" , { 0x2131 }}, + { "GJcy" , { 0x0403 }}, + { "GT" , { 0x3E }}, + { "Gamma" , { 0x0393 }}, + { "Gammad" , { 0x03DC }}, + { "Gbreve" , { 0x011E }}, + { "Gcedil" , { 0x0122 }}, + { "Gcirc" , { 0x011C }}, + { "Gcy" , { 0x0413 }}, + { "Gdot" , { 0x0120 }}, + { "Gfr" , { 0x01D50A }}, + { "Gg" , { 0x22D9 }}, + { "Gopf" , { 0x01D53E }}, + { "GreaterEqual" , { 0x2265 }}, + { "GreaterEqualLess" , { 0x22DB }}, + { "GreaterFullEqual" , { 0x2267 }}, + { "GreaterGreater" , { 0x2AA2 }}, + { "GreaterLess" , { 0x2277 }}, + { "GreaterSlantEqual" , { 0x2A7E }}, + { "GreaterTilde" , { 0x2273 }}, + { "Gscr" , { 0x01D4A2 }}, + { "Gt" , { 0x226B }}, + { "HARDcy" , { 0x042A }}, + { "Hacek" , { 0x02C7 }}, + { "Hat" , { 0x5E }}, + { "Hcirc" , { 0x0124 }}, + { "Hfr" , { 0x210C }}, + { "HilbertSpace" , { 0x210B }}, + { "Hopf" , { 0x210D }}, + { "HorizontalLine" , { 0x2500 }}, + { "Hscr" , { 0x210B }}, + { "Hstrok" , { 0x0126 }}, + { "HumpDownHump" , { 0x224E }}, + { "HumpEqual" , { 0x224F }}, + { "IEcy" , { 0x0415 }}, + { "IJlig" , { 0x0132 }}, + { "IOcy" , { 0x0401 }}, + { "Iacute" , { 0xCD }}, + { "Icirc" , { 0xCE }}, + { "Icy" , { 0x0418 }}, + { "Idot" , { 0x0130 }}, + { "Ifr" , { 0x2111 }}, + { "Igrave" , { 0xCC }}, + { "Im" , { 0x2111 }}, + { "Imacr" , { 0x012A }}, + { "ImaginaryI" , { 0x2148 }}, + { "Implies" , { 0x21D2 }}, + { "Int" , { 0x222C }}, + { "Integral" , { 0x222B }}, + { "Intersection" , { 0x22C2 }}, + { "InvisibleComma" , { 0x2063 }}, + { "InvisibleTimes" , { 0x2062 }}, + { "Iogon" , { 0x012E }}, + { "Iopf" , { 0x01D540 }}, + { "Iota" , { 0x0399 }}, + { "Iscr" , { 0x2110 }}, + { "Itilde" , { 0x0128 }}, + { "Iukcy" , { 0x0406 }}, + { "Iuml" , { 0xCF }}, + { "Jcirc" , { 0x0134 }}, + { "Jcy" , { 0x0419 }}, + { "Jfr" , { 0x01D50D }}, + { "Jopf" , { 0x01D541 }}, + { "Jscr" , { 0x01D4A5 }}, + { "Jsercy" , { 0x0408 }}, + { "Jukcy" , { 0x0404 }}, + { "KHcy" , { 0x0425 }}, + { "KJcy" , { 0x040C }}, + { "Kappa" , { 0x039A }}, + { "Kcedil" , { 0x0136 }}, + { "Kcy" , { 0x041A }}, + { "Kfr" , { 0x01D50E }}, + { "Kopf" , { 0x01D542 }}, + { "Kscr" , { 0x01D4A6 }}, + { "LJcy" , { 0x0409 }}, + { "LT" , { 0x3C }}, + { "Lacute" , { 0x0139 }}, + { "Lambda" , { 0x039B }}, + { "Lang" , { 0x27EA }}, + { "Laplacetrf" , { 0x2112 }}, + { "Larr" , { 0x219E }}, + { "Lcaron" , { 0x013D }}, + { "Lcedil" , { 0x013B }}, + { "Lcy" , { 0x041B }}, + { "LeftAngleBracket" , { 0x27E8 }}, + { "LeftArrow" , { 0x2190 }}, + { "LeftArrowBar" , { 0x21E4 }}, + { "LeftArrowRightArrow" , { 0x21C6 }}, + { "LeftCeiling" , { 0x2308 }}, + { "LeftDoubleBracket" , { 0x27E6 }}, + { "LeftDownTeeVector" , { 0x2961 }}, + { "LeftDownVector" , { 0x21C3 }}, + { "LeftDownVectorBar" , { 0x2959 }}, + { "LeftFloor" , { 0x230A }}, + { "LeftRightArrow" , { 0x2194 }}, + { "LeftRightVector" , { 0x294E }}, + { "LeftTee" , { 0x22A3 }}, + { "LeftTeeArrow" , { 0x21A4 }}, + { "LeftTeeVector" , { 0x295A }}, + { "LeftTriangle" , { 0x22B2 }}, + { "LeftTriangleBar" , { 0x29CF }}, + { "LeftTriangleEqual" , { 0x22B4 }}, + { "LeftUpDownVector" , { 0x2951 }}, + { "LeftUpTeeVector" , { 0x2960 }}, + { "LeftUpVector" , { 0x21BF }}, + { "LeftUpVectorBar" , { 0x2958 }}, + { "LeftVector" , { 0x21BC }}, + { "LeftVectorBar" , { 0x2952 }}, + { "Leftarrow" , { 0x21D0 }}, + { "Leftrightarrow" , { 0x21D4 }}, + { "LessEqualGreater" , { 0x22DA }}, + { "LessFullEqual" , { 0x2266 }}, + { "LessGreater" , { 0x2276 }}, + { "LessLess" , { 0x2AA1 }}, + { "LessSlantEqual" , { 0x2A7D }}, + { "LessTilde" , { 0x2272 }}, + { "Lfr" , { 0x01D50F }}, + { "Ll" , { 0x22D8 }}, + { "Lleftarrow" , { 0x21DA }}, + { "Lmidot" , { 0x013F }}, + { "LongLeftArrow" , { 0x27F5 }}, + { "LongLeftRightArrow" , { 0x27F7 }}, + { "LongRightArrow" , { 0x27F6 }}, + { "Longleftarrow" , { 0x27F8 }}, + { "Longleftrightarrow" , { 0x27FA }}, + { "Longrightarrow" , { 0x27F9 }}, + { "Lopf" , { 0x01D543 }}, + { "LowerLeftArrow" , { 0x2199 }}, + { "LowerRightArrow" , { 0x2198 }}, + { "Lscr" , { 0x2112 }}, + { "Lsh" , { 0x21B0 }}, + { "Lstrok" , { 0x0141 }}, + { "Lt" , { 0x226A }}, + { "Map" , { 0x2905 }}, + { "Mcy" , { 0x041C }}, + { "MediumSpace" , { 0x205F }}, + { "Mellintrf" , { 0x2133 }}, + { "Mfr" , { 0x01D510 }}, + { "MinusPlus" , { 0x2213 }}, + { "Mopf" , { 0x01D544 }}, + { "Mscr" , { 0x2133 }}, + { "Mu" , { 0x039C }}, + { "NJcy" , { 0x040A }}, + { "Nacute" , { 0x0143 }}, + { "Ncaron" , { 0x0147 }}, + { "Ncedil" , { 0x0145 }}, + { "Ncy" , { 0x041D }}, + { "NegativeMediumSpace" , { 0x200B }}, + { "NegativeThickSpace" , { 0x200B }}, + { "NegativeThinSpace" , { 0x200B }}, + { "NegativeVeryThinSpace" , { 0x200B }}, + { "NestedGreaterGreater" , { 0x226B }}, + { "NestedLessLess" , { 0x226A }}, + { "NewLine" , { 0x0A }}, + { "Nfr" , { 0x01D511 }}, + { "NoBreak" , { 0x2060 }}, + { "NonBreakingSpace" , { 0xA0 }}, + { "Nopf" , { 0x2115 }}, + { "Not" , { 0x2AEC }}, + { "NotCongruent" , { 0x2262 }}, + { "NotCupCap" , { 0x226D }}, + { "NotDoubleVerticalBar" , { 0x2226 }}, + { "NotElement" , { 0x2209 }}, + { "NotEqual" , { 0x2260 }}, + { "NotEqualTilde" , { 0x2242, 0x0338 }}, + { "NotExists" , { 0x2204 }}, + { "NotGreater" , { 0x226F }}, + { "NotGreaterEqual" , { 0x2271 }}, + { "NotGreaterFullEqual" , { 0x2267, 0x0338 }}, + { "NotGreaterGreater" , { 0x226B, 0x0338 }}, + { "NotGreaterLess" , { 0x2279 }}, + { "NotGreaterSlantEqual" , { 0x2A7E, 0x0338 }}, + { "NotGreaterTilde" , { 0x2275 }}, + { "NotHumpDownHump" , { 0x224E, 0x0338 }}, + { "NotHumpEqual" , { 0x224F, 0x0338 }}, + { "NotLeftTriangle" , { 0x22EA }}, + { "NotLeftTriangleBar" , { 0x29CF, 0x0338 }}, + { "NotLeftTriangleEqual" , { 0x22EC }}, + { "NotLess" , { 0x226E }}, + { "NotLessEqual" , { 0x2270 }}, + { "NotLessGreater" , { 0x2278 }}, + { "NotLessLess" , { 0x226A, 0x0338 }}, + { "NotLessSlantEqual" , { 0x2A7D, 0x0338 }}, + { "NotLessTilde" , { 0x2274 }}, + { "NotNestedGreaterGreater" , { 0x2AA2, 0x0338 }}, + { "NotNestedLessLess" , { 0x2AA1, 0x0338 }}, + { "NotPrecedes" , { 0x2280 }}, + { "NotPrecedesEqual" , { 0x2AAF, 0x0338 }}, + { "NotPrecedesSlantEqual" , { 0x22E0 }}, + { "NotReverseElement" , { 0x220C }}, + { "NotRightTriangle" , { 0x22EB }}, + { "NotRightTriangleBar" , { 0x29D0, 0x0338 }}, + { "NotRightTriangleEqual" , { 0x22ED }}, + { "NotSquareSubset" , { 0x228F, 0x0338 }}, + { "NotSquareSubsetEqual" , { 0x22E2 }}, + { "NotSquareSuperset" , { 0x2290, 0x0338 }}, + { "NotSquareSupersetEqual" , { 0x22E3 }}, + { "NotSubset" , { 0x2282, 0x20D2 }}, + { "NotSubsetEqual" , { 0x2288 }}, + { "NotSucceeds" , { 0x2281 }}, + { "NotSucceedsEqual" , { 0x2AB0, 0x0338 }}, + { "NotSucceedsSlantEqual" , { 0x22E1 }}, + { "NotSucceedsTilde" , { 0x227F, 0x0338 }}, + { "NotSuperset" , { 0x2283, 0x20D2 }}, + { "NotSupersetEqual" , { 0x2289 }}, + { "NotTilde" , { 0x2241 }}, + { "NotTildeEqual" , { 0x2244 }}, + { "NotTildeFullEqual" , { 0x2247 }}, + { "NotTildeTilde" , { 0x2249 }}, + { "NotVerticalBar" , { 0x2224 }}, + { "Nscr" , { 0x01D4A9 }}, + { "Ntilde" , { 0xD1 }}, + { "Nu" , { 0x039D }}, + { "OElig" , { 0x0152 }}, + { "Oacute" , { 0xD3 }}, + { "Ocirc" , { 0xD4 }}, + { "Ocy" , { 0x041E }}, + { "Odblac" , { 0x0150 }}, + { "Ofr" , { 0x01D512 }}, + { "Ograve" , { 0xD2 }}, + { "Omacr" , { 0x014C }}, + { "Omega" , { 0x03A9 }}, + { "Omicron" , { 0x039F }}, + { "Oopf" , { 0x01D546 }}, + { "OpenCurlyDoubleQuote" , { 0x201C }}, + { "OpenCurlyQuote" , { 0x2018 }}, + { "Or" , { 0x2A54 }}, + { "Oscr" , { 0x01D4AA }}, + { "Oslash" , { 0xD8 }}, + { "Otilde" , { 0xD5 }}, + { "Otimes" , { 0x2A37 }}, + { "Ouml" , { 0xD6 }}, + { "OverBar" , { 0x203E }}, + { "OverBrace" , { 0x23DE }}, + { "OverBracket" , { 0x23B4 }}, + { "OverParenthesis" , { 0x23DC }}, + { "PartialD" , { 0x2202 }}, + { "Pcy" , { 0x041F }}, + { "Pfr" , { 0x01D513 }}, + { "Phi" , { 0x03A6 }}, + { "Pi" , { 0x03A0 }}, + { "PlusMinus" , { 0xB1 }}, + { "Poincareplane" , { 0x210C }}, + { "Popf" , { 0x2119 }}, + { "Pr" , { 0x2ABB }}, + { "Precedes" , { 0x227A }}, + { "PrecedesEqual" , { 0x2AAF }}, + { "PrecedesSlantEqual" , { 0x227C }}, + { "PrecedesTilde" , { 0x227E }}, + { "Prime" , { 0x2033 }}, + { "Product" , { 0x220F }}, + { "Proportion" , { 0x2237 }}, + { "Proportional" , { 0x221D }}, + { "Pscr" , { 0x01D4AB }}, + { "Psi" , { 0x03A8 }}, + { "QUOT" , { 0x22 }}, + { "Qfr" , { 0x01D514 }}, + { "Qopf" , { 0x211A }}, + { "Qscr" , { 0x01D4AC }}, + { "RBarr" , { 0x2910 }}, + { "REG" , { 0xAE }}, + { "Racute" , { 0x0154 }}, + { "Rang" , { 0x27EB }}, + { "Rarr" , { 0x21A0 }}, + { "Rarrtl" , { 0x2916 }}, + { "Rcaron" , { 0x0158 }}, + { "Rcedil" , { 0x0156 }}, + { "Rcy" , { 0x0420 }}, + { "Re" , { 0x211C }}, + { "ReverseElement" , { 0x220B }}, + { "ReverseEquilibrium" , { 0x21CB }}, + { "ReverseUpEquilibrium" , { 0x296F }}, + { "Rfr" , { 0x211C }}, + { "Rho" , { 0x03A1 }}, + { "RightAngleBracket" , { 0x27E9 }}, + { "RightArrow" , { 0x2192 }}, + { "RightArrowBar" , { 0x21E5 }}, + { "RightArrowLeftArrow" , { 0x21C4 }}, + { "RightCeiling" , { 0x2309 }}, + { "RightDoubleBracket" , { 0x27E7 }}, + { "RightDownTeeVector" , { 0x295D }}, + { "RightDownVector" , { 0x21C2 }}, + { "RightDownVectorBar" , { 0x2955 }}, + { "RightFloor" , { 0x230B }}, + { "RightTee" , { 0x22A2 }}, + { "RightTeeArrow" , { 0x21A6 }}, + { "RightTeeVector" , { 0x295B }}, + { "RightTriangle" , { 0x22B3 }}, + { "RightTriangleBar" , { 0x29D0 }}, + { "RightTriangleEqual" , { 0x22B5 }}, + { "RightUpDownVector" , { 0x294F }}, + { "RightUpTeeVector" , { 0x295C }}, + { "RightUpVector" , { 0x21BE }}, + { "RightUpVectorBar" , { 0x2954 }}, + { "RightVector" , { 0x21C0 }}, + { "RightVectorBar" , { 0x2953 }}, + { "Rightarrow" , { 0x21D2 }}, + { "Ropf" , { 0x211D }}, + { "RoundImplies" , { 0x2970 }}, + { "Rrightarrow" , { 0x21DB }}, + { "Rscr" , { 0x211B }}, + { "Rsh" , { 0x21B1 }}, + { "RuleDelayed" , { 0x29F4 }}, + { "SHCHcy" , { 0x0429 }}, + { "SHcy" , { 0x0428 }}, + { "SOFTcy" , { 0x042C }}, + { "Sacute" , { 0x015A }}, + { "Sc" , { 0x2ABC }}, + { "Scaron" , { 0x0160 }}, + { "Scedil" , { 0x015E }}, + { "Scirc" , { 0x015C }}, + { "Scy" , { 0x0421 }}, + { "Sfr" , { 0x01D516 }}, + { "ShortDownArrow" , { 0x2193 }}, + { "ShortLeftArrow" , { 0x2190 }}, + { "ShortRightArrow" , { 0x2192 }}, + { "ShortUpArrow" , { 0x2191 }}, + { "Sigma" , { 0x03A3 }}, + { "SmallCircle" , { 0x2218 }}, + { "Sopf" , { 0x01D54A }}, + { "Sqrt" , { 0x221A }}, + { "Square" , { 0x25A1 }}, + { "SquareIntersection" , { 0x2293 }}, + { "SquareSubset" , { 0x228F }}, + { "SquareSubsetEqual" , { 0x2291 }}, + { "SquareSuperset" , { 0x2290 }}, + { "SquareSupersetEqual" , { 0x2292 }}, + { "SquareUnion" , { 0x2294 }}, + { "Sscr" , { 0x01D4AE }}, + { "Star" , { 0x22C6 }}, + { "Sub" , { 0x22D0 }}, + { "Subset" , { 0x22D0 }}, + { "SubsetEqual" , { 0x2286 }}, + { "Succeeds" , { 0x227B }}, + { "SucceedsEqual" , { 0x2AB0 }}, + { "SucceedsSlantEqual" , { 0x227D }}, + { "SucceedsTilde" , { 0x227F }}, + { "SuchThat" , { 0x220B }}, + { "Sum" , { 0x2211 }}, + { "Sup" , { 0x22D1 }}, + { "Superset" , { 0x2283 }}, + { "SupersetEqual" , { 0x2287 }}, + { "Supset" , { 0x22D1 }}, + { "THORN" , { 0xDE }}, + { "TRADE" , { 0x2122 }}, + { "TSHcy" , { 0x040B }}, + { "TScy" , { 0x0426 }}, + { "Tab" , { 0x09 }}, + { "Tau" , { 0x03A4 }}, + { "Tcaron" , { 0x0164 }}, + { "Tcedil" , { 0x0162 }}, + { "Tcy" , { 0x0422 }}, + { "Tfr" , { 0x01D517 }}, + { "Therefore" , { 0x2234 }}, + { "Theta" , { 0x0398 }}, + { "ThickSpace" , { 0x205F, 0x200A }}, + { "ThinSpace" , { 0x2009 }}, + { "Tilde" , { 0x223C }}, + { "TildeEqual" , { 0x2243 }}, + { "TildeFullEqual" , { 0x2245 }}, + { "TildeTilde" , { 0x2248 }}, + { "Topf" , { 0x01D54B }}, + { "TripleDot" , { 0x20DB }}, + { "Tscr" , { 0x01D4AF }}, + { "Tstrok" , { 0x0166 }}, + { "Uacute" , { 0xDA }}, + { "Uarr" , { 0x219F }}, + { "Uarrocir" , { 0x2949 }}, + { "Ubrcy" , { 0x040E }}, + { "Ubreve" , { 0x016C }}, + { "Ucirc" , { 0xDB }}, + { "Ucy" , { 0x0423 }}, + { "Udblac" , { 0x0170 }}, + { "Ufr" , { 0x01D518 }}, + { "Ugrave" , { 0xD9 }}, + { "Umacr" , { 0x016A }}, + { "UnderBar" , { 0x5F }}, + { "UnderBrace" , { 0x23DF }}, + { "UnderBracket" , { 0x23B5 }}, + { "UnderParenthesis" , { 0x23DD }}, + { "Union" , { 0x22C3 }}, + { "UnionPlus" , { 0x228E }}, + { "Uogon" , { 0x0172 }}, + { "Uopf" , { 0x01D54C }}, + { "UpArrow" , { 0x2191 }}, + { "UpArrowBar" , { 0x2912 }}, + { "UpArrowDownArrow" , { 0x21C5 }}, + { "UpDownArrow" , { 0x2195 }}, + { "UpEquilibrium" , { 0x296E }}, + { "UpTee" , { 0x22A5 }}, + { "UpTeeArrow" , { 0x21A5 }}, + { "Uparrow" , { 0x21D1 }}, + { "Updownarrow" , { 0x21D5 }}, + { "UpperLeftArrow" , { 0x2196 }}, + { "UpperRightArrow" , { 0x2197 }}, + { "Upsi" , { 0x03D2 }}, + { "Upsilon" , { 0x03A5 }}, + { "Uring" , { 0x016E }}, + { "Uscr" , { 0x01D4B0 }}, + { "Utilde" , { 0x0168 }}, + { "Uuml" , { 0xDC }}, + { "VDash" , { 0x22AB }}, + { "Vbar" , { 0x2AEB }}, + { "Vcy" , { 0x0412 }}, + { "Vdash" , { 0x22A9 }}, + { "Vdashl" , { 0x2AE6 }}, + { "Vee" , { 0x22C1 }}, + { "Verbar" , { 0x2016 }}, + { "Vert" , { 0x2016 }}, + { "VerticalBar" , { 0x2223 }}, + { "VerticalLine" , { 0x7C }}, + { "VerticalSeparator" , { 0x2758 }}, + { "VerticalTilde" , { 0x2240 }}, + { "VeryThinSpace" , { 0x200A }}, + { "Vfr" , { 0x01D519 }}, + { "Vopf" , { 0x01D54D }}, + { "Vscr" , { 0x01D4B1 }}, + { "Vvdash" , { 0x22AA }}, + { "Wcirc" , { 0x0174 }}, + { "Wedge" , { 0x22C0 }}, + { "Wfr" , { 0x01D51A }}, + { "Wopf" , { 0x01D54E }}, + { "Wscr" , { 0x01D4B2 }}, + { "Xfr" , { 0x01D51B }}, + { "Xi" , { 0x039E }}, + { "Xopf" , { 0x01D54F }}, + { "Xscr" , { 0x01D4B3 }}, + { "YAcy" , { 0x042F }}, + { "YIcy" , { 0x0407 }}, + { "YUcy" , { 0x042E }}, + { "Yacute" , { 0xDD }}, + { "Ycirc" , { 0x0176 }}, + { "Ycy" , { 0x042B }}, + { "Yfr" , { 0x01D51C }}, + { "Yopf" , { 0x01D550 }}, + { "Yscr" , { 0x01D4B4 }}, + { "Yuml" , { 0x0178 }}, + { "ZHcy" , { 0x0416 }}, + { "Zacute" , { 0x0179 }}, + { "Zcaron" , { 0x017D }}, + { "Zcy" , { 0x0417 }}, + { "Zdot" , { 0x017B }}, + { "ZeroWidthSpace" , { 0x200B }}, + { "Zeta" , { 0x0396 }}, + { "Zfr" , { 0x2128 }}, + { "Zopf" , { 0x2124 }}, + { "Zscr" , { 0x01D4B5 }}, + { "aacute" , { 0xE1 }}, + { "abreve" , { 0x0103 }}, + { "ac" , { 0x223E }}, + { "acE" , { 0x223E, 0x0333 }}, + { "acd" , { 0x223F }}, + { "acirc" , { 0xE2 }}, + { "acute" , { 0xB4 }}, + { "acy" , { 0x0430 }}, + { "aelig" , { 0xE6 }}, + { "af" , { 0x2061 }}, + { "afr" , { 0x01D51E }}, + { "agrave" , { 0xE0 }}, + { "alefsym" , { 0x2135 }}, + { "aleph" , { 0x2135 }}, + { "alpha" , { 0x03B1 }}, + { "amacr" , { 0x0101 }}, + { "amalg" , { 0x2A3F }}, + { "amp" , { 0x26 }}, + { "and" , { 0x2227 }}, + { "andand" , { 0x2A55 }}, + { "andd" , { 0x2A5C }}, + { "andslope" , { 0x2A58 }}, + { "andv" , { 0x2A5A }}, + { "ang" , { 0x2220 }}, + { "ange" , { 0x29A4 }}, + { "angle" , { 0x2220 }}, + { "angmsd" , { 0x2221 }}, + { "angmsdaa" , { 0x29A8 }}, + { "angmsdab" , { 0x29A9 }}, + { "angmsdac" , { 0x29AA }}, + { "angmsdad" , { 0x29AB }}, + { "angmsdae" , { 0x29AC }}, + { "angmsdaf" , { 0x29AD }}, + { "angmsdag" , { 0x29AE }}, + { "angmsdah" , { 0x29AF }}, + { "angrt" , { 0x221F }}, + { "angrtvb" , { 0x22BE }}, + { "angrtvbd" , { 0x299D }}, + { "angsph" , { 0x2222 }}, + { "angst" , { 0xC5 }}, + { "angzarr" , { 0x237C }}, + { "aogon" , { 0x0105 }}, + { "aopf" , { 0x01D552 }}, + { "ap" , { 0x2248 }}, + { "apE" , { 0x2A70 }}, + { "apacir" , { 0x2A6F }}, + { "ape" , { 0x224A }}, + { "apid" , { 0x224B }}, + { "apos" , { 0x27 }}, + { "approx" , { 0x2248 }}, + { "approxeq" , { 0x224A }}, + { "aring" , { 0xE5 }}, + { "ascr" , { 0x01D4B6 }}, + { "ast" , { 0x2A }}, + { "asymp" , { 0x2248 }}, + { "asympeq" , { 0x224D }}, + { "atilde" , { 0xE3 }}, + { "auml" , { 0xE4 }}, + { "awconint" , { 0x2233 }}, + { "awint" , { 0x2A11 }}, + { "bNot" , { 0x2AED }}, + { "backcong" , { 0x224C }}, + { "backepsilon" , { 0x03F6 }}, + { "backprime" , { 0x2035 }}, + { "backsim" , { 0x223D }}, + { "backsimeq" , { 0x22CD }}, + { "barvee" , { 0x22BD }}, + { "barwed" , { 0x2305 }}, + { "barwedge" , { 0x2305 }}, + { "bbrk" , { 0x23B5 }}, + { "bbrktbrk" , { 0x23B6 }}, + { "bcong" , { 0x224C }}, + { "bcy" , { 0x0431 }}, + { "bdquo" , { 0x201E }}, + { "becaus" , { 0x2235 }}, + { "because" , { 0x2235 }}, + { "bemptyv" , { 0x29B0 }}, + { "bepsi" , { 0x03F6 }}, + { "bernou" , { 0x212C }}, + { "beta" , { 0x03B2 }}, + { "beth" , { 0x2136 }}, + { "between" , { 0x226C }}, + { "bfr" , { 0x01D51F }}, + { "bigcap" , { 0x22C2 }}, + { "bigcirc" , { 0x25EF }}, + { "bigcup" , { 0x22C3 }}, + { "bigodot" , { 0x2A00 }}, + { "bigoplus" , { 0x2A01 }}, + { "bigotimes" , { 0x2A02 }}, + { "bigsqcup" , { 0x2A06 }}, + { "bigstar" , { 0x2605 }}, + { "bigtriangledown" , { 0x25BD }}, + { "bigtriangleup" , { 0x25B3 }}, + { "biguplus" , { 0x2A04 }}, + { "bigvee" , { 0x22C1 }}, + { "bigwedge" , { 0x22C0 }}, + { "bkarow" , { 0x290D }}, + { "blacklozenge" , { 0x29EB }}, + { "blacksquare" , { 0x25AA }}, + { "blacktriangle" , { 0x25B4 }}, + { "blacktriangledown" , { 0x25BE }}, + { "blacktriangleleft" , { 0x25C2 }}, + { "blacktriangleright" , { 0x25B8 }}, + { "blank" , { 0x2423 }}, + { "blk12" , { 0x2592 }}, + { "blk14" , { 0x2591 }}, + { "blk34" , { 0x2593 }}, + { "block" , { 0x2588 }}, + { "bne" , { 0x3D, 0x20E5 }}, + { "bnequiv" , { 0x2261, 0x20E5 }}, + { "bnot" , { 0x2310 }}, + { "bopf" , { 0x01D553 }}, + { "bot" , { 0x22A5 }}, + { "bottom" , { 0x22A5 }}, + { "bowtie" , { 0x22C8 }}, + { "boxDL" , { 0x2557 }}, + { "boxDR" , { 0x2554 }}, + { "boxDl" , { 0x2556 }}, + { "boxDr" , { 0x2553 }}, + { "boxH" , { 0x2550 }}, + { "boxHD" , { 0x2566 }}, + { "boxHU" , { 0x2569 }}, + { "boxHd" , { 0x2564 }}, + { "boxHu" , { 0x2567 }}, + { "boxUL" , { 0x255D }}, + { "boxUR" , { 0x255A }}, + { "boxUl" , { 0x255C }}, + { "boxUr" , { 0x2559 }}, + { "boxV" , { 0x2551 }}, + { "boxVH" , { 0x256C }}, + { "boxVL" , { 0x2563 }}, + { "boxVR" , { 0x2560 }}, + { "boxVh" , { 0x256B }}, + { "boxVl" , { 0x2562 }}, + { "boxVr" , { 0x255F }}, + { "boxbox" , { 0x29C9 }}, + { "boxdL" , { 0x2555 }}, + { "boxdR" , { 0x2552 }}, + { "boxdl" , { 0x2510 }}, + { "boxdr" , { 0x250C }}, + { "boxh" , { 0x2500 }}, + { "boxhD" , { 0x2565 }}, + { "boxhU" , { 0x2568 }}, + { "boxhd" , { 0x252C }}, + { "boxhu" , { 0x2534 }}, + { "boxminus" , { 0x229F }}, + { "boxplus" , { 0x229E }}, + { "boxtimes" , { 0x22A0 }}, + { "boxuL" , { 0x255B }}, + { "boxuR" , { 0x2558 }}, + { "boxul" , { 0x2518 }}, + { "boxur" , { 0x2514 }}, + { "boxv" , { 0x2502 }}, + { "boxvH" , { 0x256A }}, + { "boxvL" , { 0x2561 }}, + { "boxvR" , { 0x255E }}, + { "boxvh" , { 0x253C }}, + { "boxvl" , { 0x2524 }}, + { "boxvr" , { 0x251C }}, + { "bprime" , { 0x2035 }}, + { "breve" , { 0x02D8 }}, + { "brvbar" , { 0xA6 }}, + { "bscr" , { 0x01D4B7 }}, + { "bsemi" , { 0x204F }}, + { "bsim" , { 0x223D }}, + { "bsime" , { 0x22CD }}, + { "bsol" , { 0x5C }}, + { "bsolb" , { 0x29C5 }}, + { "bsolhsub" , { 0x27C8 }}, + { "bull" , { 0x2022 }}, + { "bullet" , { 0x2022 }}, + { "bump" , { 0x224E }}, + { "bumpE" , { 0x2AAE }}, + { "bumpe" , { 0x224F }}, + { "bumpeq" , { 0x224F }}, + { "cacute" , { 0x0107 }}, + { "cap" , { 0x2229 }}, + { "capand" , { 0x2A44 }}, + { "capbrcup" , { 0x2A49 }}, + { "capcap" , { 0x2A4B }}, + { "capcup" , { 0x2A47 }}, + { "capdot" , { 0x2A40 }}, + { "caps" , { 0x2229, 0xFE00 }}, + { "caret" , { 0x2041 }}, + { "caron" , { 0x02C7 }}, + { "ccaps" , { 0x2A4D }}, + { "ccaron" , { 0x010D }}, + { "ccedil" , { 0xE7 }}, + { "ccirc" , { 0x0109 }}, + { "ccups" , { 0x2A4C }}, + { "ccupssm" , { 0x2A50 }}, + { "cdot" , { 0x010B }}, + { "cedil" , { 0xB8 }}, + { "cemptyv" , { 0x29B2 }}, + { "cent" , { 0xA2 }}, + { "centerdot" , { 0xB7 }}, + { "cfr" , { 0x01D520 }}, + { "chcy" , { 0x0447 }}, + { "check" , { 0x2713 }}, + { "checkmark" , { 0x2713 }}, + { "chi" , { 0x03C7 }}, + { "cir" , { 0x25CB }}, + { "cirE" , { 0x29C3 }}, + { "circ" , { 0x02C6 }}, + { "circeq" , { 0x2257 }}, + { "circlearrowleft" , { 0x21BA }}, + { "circlearrowright" , { 0x21BB }}, + { "circledR" , { 0xAE }}, + { "circledS" , { 0x24C8 }}, + { "circledast" , { 0x229B }}, + { "circledcirc" , { 0x229A }}, + { "circleddash" , { 0x229D }}, + { "cire" , { 0x2257 }}, + { "cirfnint" , { 0x2A10 }}, + { "cirmid" , { 0x2AEF }}, + { "cirscir" , { 0x29C2 }}, + { "clubs" , { 0x2663 }}, + { "clubsuit" , { 0x2663 }}, + { "colon" , { 0x3A }}, + { "colone" , { 0x2254 }}, + { "coloneq" , { 0x2254 }}, + { "comma" , { 0x2C }}, + { "commat" , { 0x40 }}, + { "comp" , { 0x2201 }}, + { "compfn" , { 0x2218 }}, + { "complement" , { 0x2201 }}, + { "complexes" , { 0x2102 }}, + { "cong" , { 0x2245 }}, + { "congdot" , { 0x2A6D }}, + { "conint" , { 0x222E }}, + { "copf" , { 0x01D554 }}, + { "coprod" , { 0x2210 }}, + { "copy" , { 0xA9 }}, + { "copysr" , { 0x2117 }}, + { "crarr" , { 0x21B5 }}, + { "cross" , { 0x2717 }}, + { "cscr" , { 0x01D4B8 }}, + { "csub" , { 0x2ACF }}, + { "csube" , { 0x2AD1 }}, + { "csup" , { 0x2AD0 }}, + { "csupe" , { 0x2AD2 }}, + { "ctdot" , { 0x22EF }}, + { "cudarrl" , { 0x2938 }}, + { "cudarrr" , { 0x2935 }}, + { "cuepr" , { 0x22DE }}, + { "cuesc" , { 0x22DF }}, + { "cularr" , { 0x21B6 }}, + { "cularrp" , { 0x293D }}, + { "cup" , { 0x222A }}, + { "cupbrcap" , { 0x2A48 }}, + { "cupcap" , { 0x2A46 }}, + { "cupcup" , { 0x2A4A }}, + { "cupdot" , { 0x228D }}, + { "cupor" , { 0x2A45 }}, + { "cups" , { 0x222A, 0xFE00 }}, + { "curarr" , { 0x21B7 }}, + { "curarrm" , { 0x293C }}, + { "curlyeqprec" , { 0x22DE }}, + { "curlyeqsucc" , { 0x22DF }}, + { "curlyvee" , { 0x22CE }}, + { "curlywedge" , { 0x22CF }}, + { "curren" , { 0xA4 }}, + { "curvearrowleft" , { 0x21B6 }}, + { "curvearrowright" , { 0x21B7 }}, + { "cuvee" , { 0x22CE }}, + { "cuwed" , { 0x22CF }}, + { "cwconint" , { 0x2232 }}, + { "cwint" , { 0x2231 }}, + { "cylcty" , { 0x232D }}, + { "dArr" , { 0x21D3 }}, + { "dHar" , { 0x2965 }}, + { "dagger" , { 0x2020 }}, + { "daleth" , { 0x2138 }}, + { "darr" , { 0x2193 }}, + { "dash" , { 0x2010 }}, + { "dashv" , { 0x22A3 }}, + { "dbkarow" , { 0x290F }}, + { "dblac" , { 0x02DD }}, + { "dcaron" , { 0x010F }}, + { "dcy" , { 0x0434 }}, + { "dd" , { 0x2146 }}, + { "ddagger" , { 0x2021 }}, + { "ddarr" , { 0x21CA }}, + { "ddotseq" , { 0x2A77 }}, + { "deg" , { 0xB0 }}, + { "delta" , { 0x03B4 }}, + { "demptyv" , { 0x29B1 }}, + { "dfisht" , { 0x297F }}, + { "dfr" , { 0x01D521 }}, + { "dharl" , { 0x21C3 }}, + { "dharr" , { 0x21C2 }}, + { "diam" , { 0x22C4 }}, + { "diamond" , { 0x22C4 }}, + { "diamondsuit" , { 0x2666 }}, + { "diams" , { 0x2666 }}, + { "die" , { 0xA8 }}, + { "digamma" , { 0x03DD }}, + { "disin" , { 0x22F2 }}, + { "div" , { 0xF7 }}, + { "divide" , { 0xF7 }}, + { "divideontimes" , { 0x22C7 }}, + { "divonx" , { 0x22C7 }}, + { "djcy" , { 0x0452 }}, + { "dlcorn" , { 0x231E }}, + { "dlcrop" , { 0x230D }}, + { "dollar" , { 0x24 }}, + { "dopf" , { 0x01D555 }}, + { "dot" , { 0x02D9 }}, + { "doteq" , { 0x2250 }}, + { "doteqdot" , { 0x2251 }}, + { "dotminus" , { 0x2238 }}, + { "dotplus" , { 0x2214 }}, + { "dotsquare" , { 0x22A1 }}, + { "doublebarwedge" , { 0x2306 }}, + { "downarrow" , { 0x2193 }}, + { "downdownarrows" , { 0x21CA }}, + { "downharpoonleft" , { 0x21C3 }}, + { "downharpoonright" , { 0x21C2 }}, + { "drbkarow" , { 0x2910 }}, + { "drcorn" , { 0x231F }}, + { "drcrop" , { 0x230C }}, + { "dscr" , { 0x01D4B9 }}, + { "dscy" , { 0x0455 }}, + { "dsol" , { 0x29F6 }}, + { "dstrok" , { 0x0111 }}, + { "dtdot" , { 0x22F1 }}, + { "dtri" , { 0x25BF }}, + { "dtrif" , { 0x25BE }}, + { "duarr" , { 0x21F5 }}, + { "duhar" , { 0x296F }}, + { "dwangle" , { 0x29A6 }}, + { "dzcy" , { 0x045F }}, + { "dzigrarr" , { 0x27FF }}, + { "eDDot" , { 0x2A77 }}, + { "eDot" , { 0x2251 }}, + { "eacute" , { 0xE9 }}, + { "easter" , { 0x2A6E }}, + { "ecaron" , { 0x011B }}, + { "ecir" , { 0x2256 }}, + { "ecirc" , { 0xEA }}, + { "ecolon" , { 0x2255 }}, + { "ecy" , { 0x044D }}, + { "edot" , { 0x0117 }}, + { "ee" , { 0x2147 }}, + { "efDot" , { 0x2252 }}, + { "efr" , { 0x01D522 }}, + { "eg" , { 0x2A9A }}, + { "egrave" , { 0xE8 }}, + { "egs" , { 0x2A96 }}, + { "egsdot" , { 0x2A98 }}, + { "el" , { 0x2A99 }}, + { "elinters" , { 0x23E7 }}, + { "ell" , { 0x2113 }}, + { "els" , { 0x2A95 }}, + { "elsdot" , { 0x2A97 }}, + { "emacr" , { 0x0113 }}, + { "empty" , { 0x2205 }}, + { "emptyset" , { 0x2205 }}, + { "emptyv" , { 0x2205 }}, + { "emsp13" , { 0x2004 }}, + { "emsp14" , { 0x2005 }}, + { "emsp" , { 0x2003 }}, + { "eng" , { 0x014B }}, + { "ensp" , { 0x2002 }}, + { "eogon" , { 0x0119 }}, + { "eopf" , { 0x01D556 }}, + { "epar" , { 0x22D5 }}, + { "eparsl" , { 0x29E3 }}, + { "eplus" , { 0x2A71 }}, + { "epsi" , { 0x03B5 }}, + { "epsilon" , { 0x03B5 }}, + { "epsiv" , { 0x03F5 }}, + { "eqcirc" , { 0x2256 }}, + { "eqcolon" , { 0x2255 }}, + { "eqsim" , { 0x2242 }}, + { "eqslantgtr" , { 0x2A96 }}, + { "eqslantless" , { 0x2A95 }}, + { "equals" , { 0x3D }}, + { "equest" , { 0x225F }}, + { "equiv" , { 0x2261 }}, + { "equivDD" , { 0x2A78 }}, + { "eqvparsl" , { 0x29E5 }}, + { "erDot" , { 0x2253 }}, + { "erarr" , { 0x2971 }}, + { "escr" , { 0x212F }}, + { "esdot" , { 0x2250 }}, + { "esim" , { 0x2242 }}, + { "eta" , { 0x03B7 }}, + { "eth" , { 0xF0 }}, + { "euml" , { 0xEB }}, + { "euro" , { 0x20AC }}, + { "excl" , { 0x21 }}, + { "exist" , { 0x2203 }}, + { "expectation" , { 0x2130 }}, + { "exponentiale" , { 0x2147 }}, + { "fallingdotseq" , { 0x2252 }}, + { "fcy" , { 0x0444 }}, + { "female" , { 0x2640 }}, + { "ffilig" , { 0xFB03 }}, + { "fflig" , { 0xFB00 }}, + { "ffllig" , { 0xFB04 }}, + { "ffr" , { 0x01D523 }}, + { "filig" , { 0xFB01 }}, + { "fjlig" , { 0x66, 0x6A }}, + { "flat" , { 0x266D }}, + { "fllig" , { 0xFB02 }}, + { "fltns" , { 0x25B1 }}, + { "fnof" , { 0x0192 }}, + { "fopf" , { 0x01D557 }}, + { "forall" , { 0x2200 }}, + { "fork" , { 0x22D4 }}, + { "forkv" , { 0x2AD9 }}, + { "fpartint" , { 0x2A0D }}, + { "frac12" , { 0xBD }}, + { "frac13" , { 0x2153 }}, + { "frac14" , { 0xBC }}, + { "frac15" , { 0x2155 }}, + { "frac16" , { 0x2159 }}, + { "frac18" , { 0x215B }}, + { "frac23" , { 0x2154 }}, + { "frac25" , { 0x2156 }}, + { "frac34" , { 0xBE }}, + { "frac35" , { 0x2157 }}, + { "frac38" , { 0x215C }}, + { "frac45" , { 0x2158 }}, + { "frac56" , { 0x215A }}, + { "frac58" , { 0x215D }}, + { "frac78" , { 0x215E }}, + { "frasl" , { 0x2044 }}, + { "frown" , { 0x2322 }}, + { "fscr" , { 0x01D4BB }}, + { "gE" , { 0x2267 }}, + { "gEl" , { 0x2A8C }}, + { "gacute" , { 0x01F5 }}, + { "gamma" , { 0x03B3 }}, + { "gammad" , { 0x03DD }}, + { "gap" , { 0x2A86 }}, + { "gbreve" , { 0x011F }}, + { "gcirc" , { 0x011D }}, + { "gcy" , { 0x0433 }}, + { "gdot" , { 0x0121 }}, + { "ge" , { 0x2265 }}, + { "gel" , { 0x22DB }}, + { "geq" , { 0x2265 }}, + { "geqq" , { 0x2267 }}, + { "geqslant" , { 0x2A7E }}, + { "ges" , { 0x2A7E }}, + { "gescc" , { 0x2AA9 }}, + { "gesdot" , { 0x2A80 }}, + { "gesdoto" , { 0x2A82 }}, + { "gesdotol" , { 0x2A84 }}, + { "gesl" , { 0x22DB, 0xFE00 }}, + { "gesles" , { 0x2A94 }}, + { "gfr" , { 0x01D524 }}, + { "gg" , { 0x226B }}, + { "ggg" , { 0x22D9 }}, + { "gimel" , { 0x2137 }}, + { "gjcy" , { 0x0453 }}, + { "gl" , { 0x2277 }}, + { "glE" , { 0x2A92 }}, + { "gla" , { 0x2AA5 }}, + { "glj" , { 0x2AA4 }}, + { "gnE" , { 0x2269 }}, + { "gnap" , { 0x2A8A }}, + { "gnapprox" , { 0x2A8A }}, + { "gne" , { 0x2A88 }}, + { "gneq" , { 0x2A88 }}, + { "gneqq" , { 0x2269 }}, + { "gnsim" , { 0x22E7 }}, + { "gopf" , { 0x01D558 }}, + { "grave" , { 0x60 }}, + { "gscr" , { 0x210A }}, + { "gsim" , { 0x2273 }}, + { "gsime" , { 0x2A8E }}, + { "gsiml" , { 0x2A90 }}, + { "gt" , { 0x3E }}, + { "gtcc" , { 0x2AA7 }}, + { "gtcir" , { 0x2A7A }}, + { "gtdot" , { 0x22D7 }}, + { "gtlPar" , { 0x2995 }}, + { "gtquest" , { 0x2A7C }}, + { "gtrapprox" , { 0x2A86 }}, + { "gtrarr" , { 0x2978 }}, + { "gtrdot" , { 0x22D7 }}, + { "gtreqless" , { 0x22DB }}, + { "gtreqqless" , { 0x2A8C }}, + { "gtrless" , { 0x2277 }}, + { "gtrsim" , { 0x2273 }}, + { "gvertneqq" , { 0x2269, 0xFE00 }}, + { "gvnE" , { 0x2269, 0xFE00 }}, + { "hArr" , { 0x21D4 }}, + { "hairsp" , { 0x200A }}, + { "half" , { 0xBD }}, + { "hamilt" , { 0x210B }}, + { "hardcy" , { 0x044A }}, + { "harr" , { 0x2194 }}, + { "harrcir" , { 0x2948 }}, + { "harrw" , { 0x21AD }}, + { "hbar" , { 0x210F }}, + { "hcirc" , { 0x0125 }}, + { "hearts" , { 0x2665 }}, + { "heartsuit" , { 0x2665 }}, + { "hellip" , { 0x2026 }}, + { "hercon" , { 0x22B9 }}, + { "hfr" , { 0x01D525 }}, + { "hksearow" , { 0x2925 }}, + { "hkswarow" , { 0x2926 }}, + { "hoarr" , { 0x21FF }}, + { "homtht" , { 0x223B }}, + { "hookleftarrow" , { 0x21A9 }}, + { "hookrightarrow" , { 0x21AA }}, + { "hopf" , { 0x01D559 }}, + { "horbar" , { 0x2015 }}, + { "hscr" , { 0x01D4BD }}, + { "hslash" , { 0x210F }}, + { "hstrok" , { 0x0127 }}, + { "hybull" , { 0x2043 }}, + { "hyphen" , { 0x2010 }}, + { "iacute" , { 0xED }}, + { "ic" , { 0x2063 }}, + { "icirc" , { 0xEE }}, + { "icy" , { 0x0438 }}, + { "iecy" , { 0x0435 }}, + { "iexcl" , { 0xA1 }}, + { "iff" , { 0x21D4 }}, + { "ifr" , { 0x01D526 }}, + { "igrave" , { 0xEC }}, + { "ii" , { 0x2148 }}, + { "iiiint" , { 0x2A0C }}, + { "iiint" , { 0x222D }}, + { "iinfin" , { 0x29DC }}, + { "iiota" , { 0x2129 }}, + { "ijlig" , { 0x0133 }}, + { "imacr" , { 0x012B }}, + { "image" , { 0x2111 }}, + { "imagline" , { 0x2110 }}, + { "imagpart" , { 0x2111 }}, + { "imath" , { 0x0131 }}, + { "imof" , { 0x22B7 }}, + { "imped" , { 0x01B5 }}, + { "in" , { 0x2208 }}, + { "incare" , { 0x2105 }}, + { "infin" , { 0x221E }}, + { "infintie" , { 0x29DD }}, + { "inodot" , { 0x0131 }}, + { "int" , { 0x222B }}, + { "intcal" , { 0x22BA }}, + { "integers" , { 0x2124 }}, + { "intercal" , { 0x22BA }}, + { "intlarhk" , { 0x2A17 }}, + { "intprod" , { 0x2A3C }}, + { "iocy" , { 0x0451 }}, + { "iogon" , { 0x012F }}, + { "iopf" , { 0x01D55A }}, + { "iota" , { 0x03B9 }}, + { "iprod" , { 0x2A3C }}, + { "iquest" , { 0xBF }}, + { "iscr" , { 0x01D4BE }}, + { "isin" , { 0x2208 }}, + { "isinE" , { 0x22F9 }}, + { "isindot" , { 0x22F5 }}, + { "isins" , { 0x22F4 }}, + { "isinsv" , { 0x22F3 }}, + { "isinv" , { 0x2208 }}, + { "it" , { 0x2062 }}, + { "itilde" , { 0x0129 }}, + { "iukcy" , { 0x0456 }}, + { "iuml" , { 0xEF }}, + { "jcirc" , { 0x0135 }}, + { "jcy" , { 0x0439 }}, + { "jfr" , { 0x01D527 }}, + { "jmath" , { 0x0237 }}, + { "jopf" , { 0x01D55B }}, + { "jscr" , { 0x01D4BF }}, + { "jsercy" , { 0x0458 }}, + { "jukcy" , { 0x0454 }}, + { "kappa" , { 0x03BA }}, + { "kappav" , { 0x03F0 }}, + { "kcedil" , { 0x0137 }}, + { "kcy" , { 0x043A }}, + { "kfr" , { 0x01D528 }}, + { "kgreen" , { 0x0138 }}, + { "khcy" , { 0x0445 }}, + { "kjcy" , { 0x045C }}, + { "kopf" , { 0x01D55C }}, + { "kscr" , { 0x01D4C0 }}, + { "lAarr" , { 0x21DA }}, + { "lArr" , { 0x21D0 }}, + { "lAtail" , { 0x291B }}, + { "lBarr" , { 0x290E }}, + { "lE" , { 0x2266 }}, + { "lEg" , { 0x2A8B }}, + { "lHar" , { 0x2962 }}, + { "lacute" , { 0x013A }}, + { "laemptyv" , { 0x29B4 }}, + { "lagran" , { 0x2112 }}, + { "lambda" , { 0x03BB }}, + { "lang" , { 0x27E8 }}, + { "langd" , { 0x2991 }}, + { "langle" , { 0x27E8 }}, + { "lap" , { 0x2A85 }}, + { "laquo" , { 0xAB }}, + { "larr" , { 0x2190 }}, + { "larrb" , { 0x21E4 }}, + { "larrbfs" , { 0x291F }}, + { "larrfs" , { 0x291D }}, + { "larrhk" , { 0x21A9 }}, + { "larrlp" , { 0x21AB }}, + { "larrpl" , { 0x2939 }}, + { "larrsim" , { 0x2973 }}, + { "larrtl" , { 0x21A2 }}, + { "lat" , { 0x2AAB }}, + { "latail" , { 0x2919 }}, + { "late" , { 0x2AAD }}, + { "lates" , { 0x2AAD, 0xFE00 }}, + { "lbarr" , { 0x290C }}, + { "lbbrk" , { 0x2772 }}, + { "lbrace" , { 0x7B }}, + { "lbrack" , { 0x5B }}, + { "lbrke" , { 0x298B }}, + { "lbrksld" , { 0x298F }}, + { "lbrkslu" , { 0x298D }}, + { "lcaron" , { 0x013E }}, + { "lcedil" , { 0x013C }}, + { "lceil" , { 0x2308 }}, + { "lcub" , { 0x7B }}, + { "lcy" , { 0x043B }}, + { "ldca" , { 0x2936 }}, + { "ldquo" , { 0x201C }}, + { "ldquor" , { 0x201E }}, + { "ldrdhar" , { 0x2967 }}, + { "ldrushar" , { 0x294B }}, + { "ldsh" , { 0x21B2 }}, + { "le" , { 0x2264 }}, + { "leftarrow" , { 0x2190 }}, + { "leftarrowtail" , { 0x21A2 }}, + { "leftharpoondown" , { 0x21BD }}, + { "leftharpoonup" , { 0x21BC }}, + { "leftleftarrows" , { 0x21C7 }}, + { "leftrightarrow" , { 0x2194 }}, + { "leftrightarrows" , { 0x21C6 }}, + { "leftrightharpoons" , { 0x21CB }}, + { "leftrightsquigarrow" , { 0x21AD }}, + { "leftthreetimes" , { 0x22CB }}, + { "leg" , { 0x22DA }}, + { "leq" , { 0x2264 }}, + { "leqq" , { 0x2266 }}, + { "leqslant" , { 0x2A7D }}, + { "les" , { 0x2A7D }}, + { "lescc" , { 0x2AA8 }}, + { "lesdot" , { 0x2A7F }}, + { "lesdoto" , { 0x2A81 }}, + { "lesdotor" , { 0x2A83 }}, + { "lesg" , { 0x22DA, 0xFE00 }}, + { "lesges" , { 0x2A93 }}, + { "lessapprox" , { 0x2A85 }}, + { "lessdot" , { 0x22D6 }}, + { "lesseqgtr" , { 0x22DA }}, + { "lesseqqgtr" , { 0x2A8B }}, + { "lessgtr" , { 0x2276 }}, + { "lesssim" , { 0x2272 }}, + { "lfisht" , { 0x297C }}, + { "lfloor" , { 0x230A }}, + { "lfr" , { 0x01D529 }}, + { "lg" , { 0x2276 }}, + { "lgE" , { 0x2A91 }}, + { "lhard" , { 0x21BD }}, + { "lharu" , { 0x21BC }}, + { "lharul" , { 0x296A }}, + { "lhblk" , { 0x2584 }}, + { "ljcy" , { 0x0459 }}, + { "ll" , { 0x226A }}, + { "llarr" , { 0x21C7 }}, + { "llcorner" , { 0x231E }}, + { "llhard" , { 0x296B }}, + { "lltri" , { 0x25FA }}, + { "lmidot" , { 0x0140 }}, + { "lmoust" , { 0x23B0 }}, + { "lmoustache" , { 0x23B0 }}, + { "lnE" , { 0x2268 }}, + { "lnap" , { 0x2A89 }}, + { "lnapprox" , { 0x2A89 }}, + { "lne" , { 0x2A87 }}, + { "lneq" , { 0x2A87 }}, + { "lneqq" , { 0x2268 }}, + { "lnsim" , { 0x22E6 }}, + { "loang" , { 0x27EC }}, + { "loarr" , { 0x21FD }}, + { "lobrk" , { 0x27E6 }}, + { "longleftarrow" , { 0x27F5 }}, + { "longleftrightarrow" , { 0x27F7 }}, + { "longmapsto" , { 0x27FC }}, + { "longrightarrow" , { 0x27F6 }}, + { "looparrowleft" , { 0x21AB }}, + { "looparrowright" , { 0x21AC }}, + { "lopar" , { 0x2985 }}, + { "lopf" , { 0x01D55D }}, + { "loplus" , { 0x2A2D }}, + { "lotimes" , { 0x2A34 }}, + { "lowast" , { 0x2217 }}, + { "lowbar" , { 0x5F }}, + { "loz" , { 0x25CA }}, + { "lozenge" , { 0x25CA }}, + { "lozf" , { 0x29EB }}, + { "lpar" , { 0x28 }}, + { "lparlt" , { 0x2993 }}, + { "lrarr" , { 0x21C6 }}, + { "lrcorner" , { 0x231F }}, + { "lrhar" , { 0x21CB }}, + { "lrhard" , { 0x296D }}, + { "lrm" , { 0x200E }}, + { "lrtri" , { 0x22BF }}, + { "lsaquo" , { 0x2039 }}, + { "lscr" , { 0x01D4C1 }}, + { "lsh" , { 0x21B0 }}, + { "lsim" , { 0x2272 }}, + { "lsime" , { 0x2A8D }}, + { "lsimg" , { 0x2A8F }}, + { "lsqb" , { 0x5B }}, + { "lsquo" , { 0x2018 }}, + { "lsquor" , { 0x201A }}, + { "lstrok" , { 0x0142 }}, + { "lt" , { 0x3C }}, + { "ltcc" , { 0x2AA6 }}, + { "ltcir" , { 0x2A79 }}, + { "ltdot" , { 0x22D6 }}, + { "lthree" , { 0x22CB }}, + { "ltimes" , { 0x22C9 }}, + { "ltlarr" , { 0x2976 }}, + { "ltquest" , { 0x2A7B }}, + { "ltrPar" , { 0x2996 }}, + { "ltri" , { 0x25C3 }}, + { "ltrie" , { 0x22B4 }}, + { "ltrif" , { 0x25C2 }}, + { "lurdshar" , { 0x294A }}, + { "luruhar" , { 0x2966 }}, + { "lvertneqq" , { 0x2268, 0xFE00 }}, + { "lvnE" , { 0x2268, 0xFE00 }}, + { "mDDot" , { 0x223A }}, + { "macr" , { 0xAF }}, + { "male" , { 0x2642 }}, + { "malt" , { 0x2720 }}, + { "maltese" , { 0x2720 }}, + { "map" , { 0x21A6 }}, + { "mapsto" , { 0x21A6 }}, + { "mapstodown" , { 0x21A7 }}, + { "mapstoleft" , { 0x21A4 }}, + { "mapstoup" , { 0x21A5 }}, + { "marker" , { 0x25AE }}, + { "mcomma" , { 0x2A29 }}, + { "mcy" , { 0x043C }}, + { "mdash" , { 0x2014 }}, + { "measuredangle" , { 0x2221 }}, + { "mfr" , { 0x01D52A }}, + { "mho" , { 0x2127 }}, + { "micro" , { 0xB5 }}, + { "mid" , { 0x2223 }}, + { "midast" , { 0x2A }}, + { "midcir" , { 0x2AF0 }}, + { "middot" , { 0xB7 }}, + { "minus" , { 0x2212 }}, + { "minusb" , { 0x229F }}, + { "minusd" , { 0x2238 }}, + { "minusdu" , { 0x2A2A }}, + { "mlcp" , { 0x2ADB }}, + { "mldr" , { 0x2026 }}, + { "mnplus" , { 0x2213 }}, + { "models" , { 0x22A7 }}, + { "mopf" , { 0x01D55E }}, + { "mp" , { 0x2213 }}, + { "mscr" , { 0x01D4C2 }}, + { "mstpos" , { 0x223E }}, + { "mu" , { 0x03BC }}, + { "multimap" , { 0x22B8 }}, + { "mumap" , { 0x22B8 }}, + { "nGg" , { 0x22D9, 0x0338 }}, + { "nGt" , { 0x226B, 0x20D2 }}, + { "nGtv" , { 0x226B, 0x0338 }}, + { "nLeftarrow" , { 0x21CD }}, + { "nLeftrightarrow" , { 0x21CE }}, + { "nLl" , { 0x22D8, 0x0338 }}, + { "nLt" , { 0x226A, 0x20D2 }}, + { "nLtv" , { 0x226A, 0x0338 }}, + { "nRightarrow" , { 0x21CF }}, + { "nVDash" , { 0x22AF }}, + { "nVdash" , { 0x22AE }}, + { "nabla" , { 0x2207 }}, + { "nacute" , { 0x0144 }}, + { "nang" , { 0x2220, 0x20D2 }}, + { "nap" , { 0x2249 }}, + { "napE" , { 0x2A70, 0x0338 }}, + { "napid" , { 0x224B, 0x0338 }}, + { "napos" , { 0x0149 }}, + { "napprox" , { 0x2249 }}, + { "natur" , { 0x266E }}, + { "natural" , { 0x266E }}, + { "naturals" , { 0x2115 }}, + { "nbsp" , { 0xA0 }}, + { "nbump" , { 0x224E, 0x0338 }}, + { "nbumpe" , { 0x224F, 0x0338 }}, + { "ncap" , { 0x2A43 }}, + { "ncaron" , { 0x0148 }}, + { "ncedil" , { 0x0146 }}, + { "ncong" , { 0x2247 }}, + { "ncongdot" , { 0x2A6D, 0x0338 }}, + { "ncup" , { 0x2A42 }}, + { "ncy" , { 0x043D }}, + { "ndash" , { 0x2013 }}, + { "ne" , { 0x2260 }}, + { "neArr" , { 0x21D7 }}, + { "nearhk" , { 0x2924 }}, + { "nearr" , { 0x2197 }}, + { "nearrow" , { 0x2197 }}, + { "nedot" , { 0x2250, 0x0338 }}, + { "nequiv" , { 0x2262 }}, + { "nesear" , { 0x2928 }}, + { "nesim" , { 0x2242, 0x0338 }}, + { "nexist" , { 0x2204 }}, + { "nexists" , { 0x2204 }}, + { "nfr" , { 0x01D52B }}, + { "ngE" , { 0x2267, 0x0338 }}, + { "nge" , { 0x2271 }}, + { "ngeq" , { 0x2271 }}, + { "ngeqq" , { 0x2267, 0x0338 }}, + { "ngeqslant" , { 0x2A7E, 0x0338 }}, + { "nges" , { 0x2A7E, 0x0338 }}, + { "ngsim" , { 0x2275 }}, + { "ngt" , { 0x226F }}, + { "ngtr" , { 0x226F }}, + { "nhArr" , { 0x21CE }}, + { "nharr" , { 0x21AE }}, + { "nhpar" , { 0x2AF2 }}, + { "ni" , { 0x220B }}, + { "nis" , { 0x22FC }}, + { "nisd" , { 0x22FA }}, + { "niv" , { 0x220B }}, + { "njcy" , { 0x045A }}, + { "nlArr" , { 0x21CD }}, + { "nlE" , { 0x2266, 0x0338 }}, + { "nlarr" , { 0x219A }}, + { "nldr" , { 0x2025 }}, + { "nle" , { 0x2270 }}, + { "nleftarrow" , { 0x219A }}, + { "nleftrightarrow" , { 0x21AE }}, + { "nleq" , { 0x2270 }}, + { "nleqq" , { 0x2266, 0x0338 }}, + { "nleqslant" , { 0x2A7D, 0x0338 }}, + { "nles" , { 0x2A7D, 0x0338 }}, + { "nless" , { 0x226E }}, + { "nlsim" , { 0x2274 }}, + { "nlt" , { 0x226E }}, + { "nltri" , { 0x22EA }}, + { "nltrie" , { 0x22EC }}, + { "nmid" , { 0x2224 }}, + { "nopf" , { 0x01D55F }}, + { "not" , { 0xAC }}, + { "notin" , { 0x2209 }}, + { "notinE" , { 0x22F9, 0x0338 }}, + { "notindot" , { 0x22F5, 0x0338 }}, + { "notinva" , { 0x2209 }}, + { "notinvb" , { 0x22F7 }}, + { "notinvc" , { 0x22F6 }}, + { "notni" , { 0x220C }}, + { "notniva" , { 0x220C }}, + { "notnivb" , { 0x22FE }}, + { "notnivc" , { 0x22FD }}, + { "npar" , { 0x2226 }}, + { "nparallel" , { 0x2226 }}, + { "nparsl" , { 0x2AFD, 0x20E5 }}, + { "npart" , { 0x2202, 0x0338 }}, + { "npolint" , { 0x2A14 }}, + { "npr" , { 0x2280 }}, + { "nprcue" , { 0x22E0 }}, + { "npre" , { 0x2AAF, 0x0338 }}, + { "nprec" , { 0x2280 }}, + { "npreceq" , { 0x2AAF, 0x0338 }}, + { "nrArr" , { 0x21CF }}, + { "nrarr" , { 0x219B }}, + { "nrarrc" , { 0x2933, 0x0338 }}, + { "nrarrw" , { 0x219D, 0x0338 }}, + { "nrightarrow" , { 0x219B }}, + { "nrtri" , { 0x22EB }}, + { "nrtrie" , { 0x22ED }}, + { "nsc" , { 0x2281 }}, + { "nsccue" , { 0x22E1 }}, + { "nsce" , { 0x2AB0, 0x0338 }}, + { "nscr" , { 0x01D4C3 }}, + { "nshortmid" , { 0x2224 }}, + { "nshortparallel" , { 0x2226 }}, + { "nsim" , { 0x2241 }}, + { "nsime" , { 0x2244 }}, + { "nsimeq" , { 0x2244 }}, + { "nsmid" , { 0x2224 }}, + { "nspar" , { 0x2226 }}, + { "nsqsube" , { 0x22E2 }}, + { "nsqsupe" , { 0x22E3 }}, + { "nsub" , { 0x2284 }}, + { "nsubE" , { 0x2AC5, 0x0338 }}, + { "nsube" , { 0x2288 }}, + { "nsubset" , { 0x2282, 0x20D2 }}, + { "nsubseteq" , { 0x2288 }}, + { "nsubseteqq" , { 0x2AC5, 0x0338 }}, + { "nsucc" , { 0x2281 }}, + { "nsucceq" , { 0x2AB0, 0x0338 }}, + { "nsup" , { 0x2285 }}, + { "nsupE" , { 0x2AC6, 0x0338 }}, + { "nsupe" , { 0x2289 }}, + { "nsupset" , { 0x2283, 0x20D2 }}, + { "nsupseteq" , { 0x2289 }}, + { "nsupseteqq" , { 0x2AC6, 0x0338 }}, + { "ntgl" , { 0x2279 }}, + { "ntilde" , { 0xF1 }}, + { "ntlg" , { 0x2278 }}, + { "ntriangleleft" , { 0x22EA }}, + { "ntrianglelefteq" , { 0x22EC }}, + { "ntriangleright" , { 0x22EB }}, + { "ntrianglerighteq" , { 0x22ED }}, + { "nu" , { 0x03BD }}, + { "num" , { 0x23 }}, + { "numero" , { 0x2116 }}, + { "numsp" , { 0x2007 }}, + { "nvDash" , { 0x22AD }}, + { "nvHarr" , { 0x2904 }}, + { "nvap" , { 0x224D, 0x20D2 }}, + { "nvdash" , { 0x22AC }}, + { "nvge" , { 0x2265, 0x20D2 }}, + { "nvgt" , { 0x3E, 0x20D2 }}, + { "nvinfin" , { 0x29DE }}, + { "nvlArr" , { 0x2902 }}, + { "nvle" , { 0x2264, 0x20D2 }}, + { "nvlt" , { 0x3C, 0x20D2 }}, + { "nvltrie" , { 0x22B4, 0x20D2 }}, + { "nvrArr" , { 0x2903 }}, + { "nvrtrie" , { 0x22B5, 0x20D2 }}, + { "nvsim" , { 0x223C, 0x20D2 }}, + { "nwArr" , { 0x21D6 }}, + { "nwarhk" , { 0x2923 }}, + { "nwarr" , { 0x2196 }}, + { "nwarrow" , { 0x2196 }}, + { "nwnear" , { 0x2927 }}, + { "oS" , { 0x24C8 }}, + { "oacute" , { 0xF3 }}, + { "oast" , { 0x229B }}, + { "ocir" , { 0x229A }}, + { "ocirc" , { 0xF4 }}, + { "ocy" , { 0x043E }}, + { "odash" , { 0x229D }}, + { "odblac" , { 0x0151 }}, + { "odiv" , { 0x2A38 }}, + { "odot" , { 0x2299 }}, + { "odsold" , { 0x29BC }}, + { "oelig" , { 0x0153 }}, + { "ofcir" , { 0x29BF }}, + { "ofr" , { 0x01D52C }}, + { "ogon" , { 0x02DB }}, + { "ograve" , { 0xF2 }}, + { "ogt" , { 0x29C1 }}, + { "ohbar" , { 0x29B5 }}, + { "ohm" , { 0x03A9 }}, + { "oint" , { 0x222E }}, + { "olarr" , { 0x21BA }}, + { "olcir" , { 0x29BE }}, + { "olcross" , { 0x29BB }}, + { "oline" , { 0x203E }}, + { "olt" , { 0x29C0 }}, + { "omacr" , { 0x014D }}, + { "omega" , { 0x03C9 }}, + { "omicron" , { 0x03BF }}, + { "omid" , { 0x29B6 }}, + { "ominus" , { 0x2296 }}, + { "oopf" , { 0x01D560 }}, + { "opar" , { 0x29B7 }}, + { "operp" , { 0x29B9 }}, + { "oplus" , { 0x2295 }}, + { "or" , { 0x2228 }}, + { "orarr" , { 0x21BB }}, + { "ord" , { 0x2A5D }}, + { "order" , { 0x2134 }}, + { "orderof" , { 0x2134 }}, + { "ordf" , { 0xAA }}, + { "ordm" , { 0xBA }}, + { "origof" , { 0x22B6 }}, + { "oror" , { 0x2A56 }}, + { "orslope" , { 0x2A57 }}, + { "orv" , { 0x2A5B }}, + { "oscr" , { 0x2134 }}, + { "oslash" , { 0xF8 }}, + { "osol" , { 0x2298 }}, + { "otilde" , { 0xF5 }}, + { "otimes" , { 0x2297 }}, + { "otimesas" , { 0x2A36 }}, + { "ouml" , { 0xF6 }}, + { "ovbar" , { 0x233D }}, + { "par" , { 0x2225 }}, + { "para" , { 0xB6 }}, + { "parallel" , { 0x2225 }}, + { "parsim" , { 0x2AF3 }}, + { "parsl" , { 0x2AFD }}, + { "part" , { 0x2202 }}, + { "pcy" , { 0x043F }}, + { "percnt" , { 0x25 }}, + { "period" , { 0x2E }}, + { "permil" , { 0x2030 }}, + { "perp" , { 0x22A5 }}, + { "pertenk" , { 0x2031 }}, + { "pfr" , { 0x01D52D }}, + { "phi" , { 0x03C6 }}, + { "phiv" , { 0x03D5 }}, + { "phmmat" , { 0x2133 }}, + { "phone" , { 0x260E }}, + { "pi" , { 0x03C0 }}, + { "pitchfork" , { 0x22D4 }}, + { "piv" , { 0x03D6 }}, + { "planck" , { 0x210F }}, + { "planckh" , { 0x210E }}, + { "plankv" , { 0x210F }}, + { "plus" , { 0x2B }}, + { "plusacir" , { 0x2A23 }}, + { "plusb" , { 0x229E }}, + { "pluscir" , { 0x2A22 }}, + { "plusdo" , { 0x2214 }}, + { "plusdu" , { 0x2A25 }}, + { "pluse" , { 0x2A72 }}, + { "plusmn" , { 0xB1 }}, + { "plussim" , { 0x2A26 }}, + { "plustwo" , { 0x2A27 }}, + { "pm" , { 0xB1 }}, + { "pointint" , { 0x2A15 }}, + { "popf" , { 0x01D561 }}, + { "pound" , { 0xA3 }}, + { "pr" , { 0x227A }}, + { "prE" , { 0x2AB3 }}, + { "prap" , { 0x2AB7 }}, + { "prcue" , { 0x227C }}, + { "pre" , { 0x2AAF }}, + { "prec" , { 0x227A }}, + { "precapprox" , { 0x2AB7 }}, + { "preccurlyeq" , { 0x227C }}, + { "preceq" , { 0x2AAF }}, + { "precnapprox" , { 0x2AB9 }}, + { "precneqq" , { 0x2AB5 }}, + { "precnsim" , { 0x22E8 }}, + { "precsim" , { 0x227E }}, + { "prime" , { 0x2032 }}, + { "primes" , { 0x2119 }}, + { "prnE" , { 0x2AB5 }}, + { "prnap" , { 0x2AB9 }}, + { "prnsim" , { 0x22E8 }}, + { "prod" , { 0x220F }}, + { "profalar" , { 0x232E }}, + { "profline" , { 0x2312 }}, + { "profsurf" , { 0x2313 }}, + { "prop" , { 0x221D }}, + { "propto" , { 0x221D }}, + { "prsim" , { 0x227E }}, + { "prurel" , { 0x22B0 }}, + { "pscr" , { 0x01D4C5 }}, + { "psi" , { 0x03C8 }}, + { "puncsp" , { 0x2008 }}, + { "qfr" , { 0x01D52E }}, + { "qint" , { 0x2A0C }}, + { "qopf" , { 0x01D562 }}, + { "qprime" , { 0x2057 }}, + { "qscr" , { 0x01D4C6 }}, + { "quaternions" , { 0x210D }}, + { "quatint" , { 0x2A16 }}, + { "quest" , { 0x3F }}, + { "questeq" , { 0x225F }}, + { "quot" , { 0x22 }}, + { "rAarr" , { 0x21DB }}, + { "rArr" , { 0x21D2 }}, + { "rAtail" , { 0x291C }}, + { "rBarr" , { 0x290F }}, + { "rHar" , { 0x2964 }}, + { "race" , { 0x223D, 0x0331 }}, + { "racute" , { 0x0155 }}, + { "radic" , { 0x221A }}, + { "raemptyv" , { 0x29B3 }}, + { "rang" , { 0x27E9 }}, + { "rangd" , { 0x2992 }}, + { "range" , { 0x29A5 }}, + { "rangle" , { 0x27E9 }}, + { "raquo" , { 0xBB }}, + { "rarr" , { 0x2192 }}, + { "rarrap" , { 0x2975 }}, + { "rarrb" , { 0x21E5 }}, + { "rarrbfs" , { 0x2920 }}, + { "rarrc" , { 0x2933 }}, + { "rarrfs" , { 0x291E }}, + { "rarrhk" , { 0x21AA }}, + { "rarrlp" , { 0x21AC }}, + { "rarrpl" , { 0x2945 }}, + { "rarrsim" , { 0x2974 }}, + { "rarrtl" , { 0x21A3 }}, + { "rarrw" , { 0x219D }}, + { "ratail" , { 0x291A }}, + { "ratio" , { 0x2236 }}, + { "rationals" , { 0x211A }}, + { "rbarr" , { 0x290D }}, + { "rbbrk" , { 0x2773 }}, + { "rbrace" , { 0x7D }}, + { "rbrack" , { 0x5D }}, + { "rbrke" , { 0x298C }}, + { "rbrksld" , { 0x298E }}, + { "rbrkslu" , { 0x2990 }}, + { "rcaron" , { 0x0159 }}, + { "rcedil" , { 0x0157 }}, + { "rceil" , { 0x2309 }}, + { "rcub" , { 0x7D }}, + { "rcy" , { 0x0440 }}, + { "rdca" , { 0x2937 }}, + { "rdldhar" , { 0x2969 }}, + { "rdquo" , { 0x201D }}, + { "rdquor" , { 0x201D }}, + { "rdsh" , { 0x21B3 }}, + { "real" , { 0x211C }}, + { "realine" , { 0x211B }}, + { "realpart" , { 0x211C }}, + { "reals" , { 0x211D }}, + { "rect" , { 0x25AD }}, + { "reg" , { 0xAE }}, + { "rfisht" , { 0x297D }}, + { "rfloor" , { 0x230B }}, + { "rfr" , { 0x01D52F }}, + { "rhard" , { 0x21C1 }}, + { "rharu" , { 0x21C0 }}, + { "rharul" , { 0x296C }}, + { "rho" , { 0x03C1 }}, + { "rhov" , { 0x03F1 }}, + { "rightarrow" , { 0x2192 }}, + { "rightarrowtail" , { 0x21A3 }}, + { "rightharpoondown" , { 0x21C1 }}, + { "rightharpoonup" , { 0x21C0 }}, + { "rightleftarrows" , { 0x21C4 }}, + { "rightleftharpoons" , { 0x21CC }}, + { "rightrightarrows" , { 0x21C9 }}, + { "rightsquigarrow" , { 0x219D }}, + { "rightthreetimes" , { 0x22CC }}, + { "ring" , { 0x02DA }}, + { "risingdotseq" , { 0x2253 }}, + { "rlarr" , { 0x21C4 }}, + { "rlhar" , { 0x21CC }}, + { "rlm" , { 0x200F }}, + { "rmoust" , { 0x23B1 }}, + { "rmoustache" , { 0x23B1 }}, + { "rnmid" , { 0x2AEE }}, + { "roang" , { 0x27ED }}, + { "roarr" , { 0x21FE }}, + { "robrk" , { 0x27E7 }}, + { "ropar" , { 0x2986 }}, + { "ropf" , { 0x01D563 }}, + { "roplus" , { 0x2A2E }}, + { "rotimes" , { 0x2A35 }}, + { "rpar" , { 0x29 }}, + { "rpargt" , { 0x2994 }}, + { "rppolint" , { 0x2A12 }}, + { "rrarr" , { 0x21C9 }}, + { "rsaquo" , { 0x203A }}, + { "rscr" , { 0x01D4C7 }}, + { "rsh" , { 0x21B1 }}, + { "rsqb" , { 0x5D }}, + { "rsquo" , { 0x2019 }}, + { "rsquor" , { 0x2019 }}, + { "rthree" , { 0x22CC }}, + { "rtimes" , { 0x22CA }}, + { "rtri" , { 0x25B9 }}, + { "rtrie" , { 0x22B5 }}, + { "rtrif" , { 0x25B8 }}, + { "rtriltri" , { 0x29CE }}, + { "ruluhar" , { 0x2968 }}, + { "rx" , { 0x211E }}, + { "sacute" , { 0x015B }}, + { "sbquo" , { 0x201A }}, + { "sc" , { 0x227B }}, + { "scE" , { 0x2AB4 }}, + { "scap" , { 0x2AB8 }}, + { "scaron" , { 0x0161 }}, + { "sccue" , { 0x227D }}, + { "sce" , { 0x2AB0 }}, + { "scedil" , { 0x015F }}, + { "scirc" , { 0x015D }}, + { "scnE" , { 0x2AB6 }}, + { "scnap" , { 0x2ABA }}, + { "scnsim" , { 0x22E9 }}, + { "scpolint" , { 0x2A13 }}, + { "scsim" , { 0x227F }}, + { "scy" , { 0x0441 }}, + { "sdot" , { 0x22C5 }}, + { "sdotb" , { 0x22A1 }}, + { "sdote" , { 0x2A66 }}, + { "seArr" , { 0x21D8 }}, + { "searhk" , { 0x2925 }}, + { "searr" , { 0x2198 }}, + { "searrow" , { 0x2198 }}, + { "sect" , { 0xA7 }}, + { "semi" , { 0x3B }}, + { "seswar" , { 0x2929 }}, + { "setminus" , { 0x2216 }}, + { "setmn" , { 0x2216 }}, + { "sext" , { 0x2736 }}, + { "sfr" , { 0x01D530 }}, + { "sfrown" , { 0x2322 }}, + { "sharp" , { 0x266F }}, + { "shchcy" , { 0x0449 }}, + { "shcy" , { 0x0448 }}, + { "shortmid" , { 0x2223 }}, + { "shortparallel" , { 0x2225 }}, + { "shy" , { 0xAD }}, + { "sigma" , { 0x03C3 }}, + { "sigmaf" , { 0x03C2 }}, + { "sigmav" , { 0x03C2 }}, + { "sim" , { 0x223C }}, + { "simdot" , { 0x2A6A }}, + { "sime" , { 0x2243 }}, + { "simeq" , { 0x2243 }}, + { "simg" , { 0x2A9E }}, + { "simgE" , { 0x2AA0 }}, + { "siml" , { 0x2A9D }}, + { "simlE" , { 0x2A9F }}, + { "simne" , { 0x2246 }}, + { "simplus" , { 0x2A24 }}, + { "simrarr" , { 0x2972 }}, + { "slarr" , { 0x2190 }}, + { "smallsetminus" , { 0x2216 }}, + { "smashp" , { 0x2A33 }}, + { "smeparsl" , { 0x29E4 }}, + { "smid" , { 0x2223 }}, + { "smile" , { 0x2323 }}, + { "smt" , { 0x2AAA }}, + { "smte" , { 0x2AAC }}, + { "smtes" , { 0x2AAC, 0xFE00 }}, + { "softcy" , { 0x044C }}, + { "sol" , { 0x2F }}, + { "solb" , { 0x29C4 }}, + { "solbar" , { 0x233F }}, + { "sopf" , { 0x01D564 }}, + { "spades" , { 0x2660 }}, + { "spadesuit" , { 0x2660 }}, + { "spar" , { 0x2225 }}, + { "sqcap" , { 0x2293 }}, + { "sqcaps" , { 0x2293, 0xFE00 }}, + { "sqcup" , { 0x2294 }}, + { "sqcups" , { 0x2294, 0xFE00 }}, + { "sqsub" , { 0x228F }}, + { "sqsube" , { 0x2291 }}, + { "sqsubset" , { 0x228F }}, + { "sqsubseteq" , { 0x2291 }}, + { "sqsup" , { 0x2290 }}, + { "sqsupe" , { 0x2292 }}, + { "sqsupset" , { 0x2290 }}, + { "sqsupseteq" , { 0x2292 }}, + { "squ" , { 0x25A1 }}, + { "square" , { 0x25A1 }}, + { "squarf" , { 0x25AA }}, + { "squf" , { 0x25AA }}, + { "srarr" , { 0x2192 }}, + { "sscr" , { 0x01D4C8 }}, + { "ssetmn" , { 0x2216 }}, + { "ssmile" , { 0x2323 }}, + { "sstarf" , { 0x22C6 }}, + { "star" , { 0x2606 }}, + { "starf" , { 0x2605 }}, + { "straightepsilon" , { 0x03F5 }}, + { "straightphi" , { 0x03D5 }}, + { "strns" , { 0xAF }}, + { "sub" , { 0x2282 }}, + { "subE" , { 0x2AC5 }}, + { "subdot" , { 0x2ABD }}, + { "sube" , { 0x2286 }}, + { "subedot" , { 0x2AC3 }}, + { "submult" , { 0x2AC1 }}, + { "subnE" , { 0x2ACB }}, + { "subne" , { 0x228A }}, + { "subplus" , { 0x2ABF }}, + { "subrarr" , { 0x2979 }}, + { "subset" , { 0x2282 }}, + { "subseteq" , { 0x2286 }}, + { "subseteqq" , { 0x2AC5 }}, + { "subsetneq" , { 0x228A }}, + { "subsetneqq" , { 0x2ACB }}, + { "subsim" , { 0x2AC7 }}, + { "subsub" , { 0x2AD5 }}, + { "subsup" , { 0x2AD3 }}, + { "succ" , { 0x227B }}, + { "succapprox" , { 0x2AB8 }}, + { "succcurlyeq" , { 0x227D }}, + { "succeq" , { 0x2AB0 }}, + { "succnapprox" , { 0x2ABA }}, + { "succneqq" , { 0x2AB6 }}, + { "succnsim" , { 0x22E9 }}, + { "succsim" , { 0x227F }}, + { "sum" , { 0x2211 }}, + { "sung" , { 0x266A }}, + { "sup1" , { 0xB9 }}, + { "sup2" , { 0xB2 }}, + { "sup3" , { 0xB3 }}, + { "sup" , { 0x2283 }}, + { "supE" , { 0x2AC6 }}, + { "supdot" , { 0x2ABE }}, + { "supdsub" , { 0x2AD8 }}, + { "supe" , { 0x2287 }}, + { "supedot" , { 0x2AC4 }}, + { "suphsol" , { 0x27C9 }}, + { "suphsub" , { 0x2AD7 }}, + { "suplarr" , { 0x297B }}, + { "supmult" , { 0x2AC2 }}, + { "supnE" , { 0x2ACC }}, + { "supne" , { 0x228B }}, + { "supplus" , { 0x2AC0 }}, + { "supset" , { 0x2283 }}, + { "supseteq" , { 0x2287 }}, + { "supseteqq" , { 0x2AC6 }}, + { "supsetneq" , { 0x228B }}, + { "supsetneqq" , { 0x2ACC }}, + { "supsim" , { 0x2AC8 }}, + { "supsub" , { 0x2AD4 }}, + { "supsup" , { 0x2AD6 }}, + { "swArr" , { 0x21D9 }}, + { "swarhk" , { 0x2926 }}, + { "swarr" , { 0x2199 }}, + { "swarrow" , { 0x2199 }}, + { "swnwar" , { 0x292A }}, + { "szlig" , { 0xDF }}, + { "target" , { 0x2316 }}, + { "tau" , { 0x03C4 }}, + { "tbrk" , { 0x23B4 }}, + { "tcaron" , { 0x0165 }}, + { "tcedil" , { 0x0163 }}, + { "tcy" , { 0x0442 }}, + { "tdot" , { 0x20DB }}, + { "telrec" , { 0x2315 }}, + { "tfr" , { 0x01D531 }}, + { "there4" , { 0x2234 }}, + { "therefore" , { 0x2234 }}, + { "theta" , { 0x03B8 }}, + { "thetasym" , { 0x03D1 }}, + { "thetav" , { 0x03D1 }}, + { "thickapprox" , { 0x2248 }}, + { "thicksim" , { 0x223C }}, + { "thinsp" , { 0x2009 }}, + { "thkap" , { 0x2248 }}, + { "thksim" , { 0x223C }}, + { "thorn" , { 0xFE }}, + { "tilde" , { 0x02DC }}, + { "times" , { 0xD7 }}, + { "timesb" , { 0x22A0 }}, + { "timesbar" , { 0x2A31 }}, + { "timesd" , { 0x2A30 }}, + { "tint" , { 0x222D }}, + { "toea" , { 0x2928 }}, + { "top" , { 0x22A4 }}, + { "topbot" , { 0x2336 }}, + { "topcir" , { 0x2AF1 }}, + { "topf" , { 0x01D565 }}, + { "topfork" , { 0x2ADA }}, + { "tosa" , { 0x2929 }}, + { "tprime" , { 0x2034 }}, + { "trade" , { 0x2122 }}, + { "triangle" , { 0x25B5 }}, + { "triangledown" , { 0x25BF }}, + { "triangleleft" , { 0x25C3 }}, + { "trianglelefteq" , { 0x22B4 }}, + { "triangleq" , { 0x225C }}, + { "triangleright" , { 0x25B9 }}, + { "trianglerighteq" , { 0x22B5 }}, + { "tridot" , { 0x25EC }}, + { "trie" , { 0x225C }}, + { "triminus" , { 0x2A3A }}, + { "triplus" , { 0x2A39 }}, + { "trisb" , { 0x29CD }}, + { "tritime" , { 0x2A3B }}, + { "trpezium" , { 0x23E2 }}, + { "tscr" , { 0x01D4C9 }}, + { "tscy" , { 0x0446 }}, + { "tshcy" , { 0x045B }}, + { "tstrok" , { 0x0167 }}, + { "twixt" , { 0x226C }}, + { "twoheadleftarrow" , { 0x219E }}, + { "twoheadrightarrow" , { 0x21A0 }}, + { "uArr" , { 0x21D1 }}, + { "uHar" , { 0x2963 }}, + { "uacute" , { 0xFA }}, + { "uarr" , { 0x2191 }}, + { "ubrcy" , { 0x045E }}, + { "ubreve" , { 0x016D }}, + { "ucirc" , { 0xFB }}, + { "ucy" , { 0x0443 }}, + { "udarr" , { 0x21C5 }}, + { "udblac" , { 0x0171 }}, + { "udhar" , { 0x296E }}, + { "ufisht" , { 0x297E }}, + { "ufr" , { 0x01D532 }}, + { "ugrave" , { 0xF9 }}, + { "uharl" , { 0x21BF }}, + { "uharr" , { 0x21BE }}, + { "uhblk" , { 0x2580 }}, + { "ulcorn" , { 0x231C }}, + { "ulcorner" , { 0x231C }}, + { "ulcrop" , { 0x230F }}, + { "ultri" , { 0x25F8 }}, + { "umacr" , { 0x016B }}, + { "uml" , { 0xA8 }}, + { "uogon" , { 0x0173 }}, + { "uopf" , { 0x01D566 }}, + { "uparrow" , { 0x2191 }}, + { "updownarrow" , { 0x2195 }}, + { "upharpoonleft" , { 0x21BF }}, + { "upharpoonright" , { 0x21BE }}, + { "uplus" , { 0x228E }}, + { "upsi" , { 0x03C5 }}, + { "upsih" , { 0x03D2 }}, + { "upsilon" , { 0x03C5 }}, + { "upuparrows" , { 0x21C8 }}, + { "urcorn" , { 0x231D }}, + { "urcorner" , { 0x231D }}, + { "urcrop" , { 0x230E }}, + { "uring" , { 0x016F }}, + { "urtri" , { 0x25F9 }}, + { "uscr" , { 0x01D4CA }}, + { "utdot" , { 0x22F0 }}, + { "utilde" , { 0x0169 }}, + { "utri" , { 0x25B5 }}, + { "utrif" , { 0x25B4 }}, + { "uuarr" , { 0x21C8 }}, + { "uuml" , { 0xFC }}, + { "uwangle" , { 0x29A7 }}, + { "vArr" , { 0x21D5 }}, + { "vBar" , { 0x2AE8 }}, + { "vBarv" , { 0x2AE9 }}, + { "vDash" , { 0x22A8 }}, + { "vangrt" , { 0x299C }}, + { "varepsilon" , { 0x03F5 }}, + { "varkappa" , { 0x03F0 }}, + { "varnothing" , { 0x2205 }}, + { "varphi" , { 0x03D5 }}, + { "varpi" , { 0x03D6 }}, + { "varpropto" , { 0x221D }}, + { "varr" , { 0x2195 }}, + { "varrho" , { 0x03F1 }}, + { "varsigma" , { 0x03C2 }}, + { "varsubsetneq" , { 0x228A, 0xFE00 }}, + { "varsubsetneqq" , { 0x2ACB, 0xFE00 }}, + { "varsupsetneq" , { 0x228B, 0xFE00 }}, + { "varsupsetneqq" , { 0x2ACC, 0xFE00 }}, + { "vartheta" , { 0x03D1 }}, + { "vartriangleleft" , { 0x22B2 }}, + { "vartriangleright" , { 0x22B3 }}, + { "vcy" , { 0x0432 }}, + { "vdash" , { 0x22A2 }}, + { "vee" , { 0x2228 }}, + { "veebar" , { 0x22BB }}, + { "veeeq" , { 0x225A }}, + { "vellip" , { 0x22EE }}, + { "verbar" , { 0x7C }}, + { "vert" , { 0x7C }}, + { "vfr" , { 0x01D533 }}, + { "vltri" , { 0x22B2 }}, + { "vnsub" , { 0x2282, 0x20D2 }}, + { "vnsup" , { 0x2283, 0x20D2 }}, + { "vopf" , { 0x01D567 }}, + { "vprop" , { 0x221D }}, + { "vrtri" , { 0x22B3 }}, + { "vscr" , { 0x01D4CB }}, + { "vsubnE" , { 0x2ACB, 0xFE00 }}, + { "vsubne" , { 0x228A, 0xFE00 }}, + { "vsupnE" , { 0x2ACC, 0xFE00 }}, + { "vsupne" , { 0x228B, 0xFE00 }}, + { "vzigzag" , { 0x299A }}, + { "wcirc" , { 0x0175 }}, + { "wedbar" , { 0x2A5F }}, + { "wedge" , { 0x2227 }}, + { "wedgeq" , { 0x2259 }}, + { "weierp" , { 0x2118 }}, + { "wfr" , { 0x01D534 }}, + { "wopf" , { 0x01D568 }}, + { "wp" , { 0x2118 }}, + { "wr" , { 0x2240 }}, + { "wreath" , { 0x2240 }}, + { "wscr" , { 0x01D4CC }}, + { "xcap" , { 0x22C2 }}, + { "xcirc" , { 0x25EF }}, + { "xcup" , { 0x22C3 }}, + { "xdtri" , { 0x25BD }}, + { "xfr" , { 0x01D535 }}, + { "xhArr" , { 0x27FA }}, + { "xharr" , { 0x27F7 }}, + { "xi" , { 0x03BE }}, + { "xlArr" , { 0x27F8 }}, + { "xlarr" , { 0x27F5 }}, + { "xmap" , { 0x27FC }}, + { "xnis" , { 0x22FB }}, + { "xodot" , { 0x2A00 }}, + { "xopf" , { 0x01D569 }}, + { "xoplus" , { 0x2A01 }}, + { "xotime" , { 0x2A02 }}, + { "xrArr" , { 0x27F9 }}, + { "xrarr" , { 0x27F6 }}, + { "xscr" , { 0x01D4CD }}, + { "xsqcup" , { 0x2A06 }}, + { "xuplus" , { 0x2A04 }}, + { "xutri" , { 0x25B3 }}, + { "xvee" , { 0x22C1 }}, + { "xwedge" , { 0x22C0 }}, + { "yacute" , { 0xFD }}, + { "yacy" , { 0x044F }}, + { "ycirc" , { 0x0177 }}, + { "ycy" , { 0x044B }}, + { "yen" , { 0xA5 }}, + { "yfr" , { 0x01D536 }}, + { "yicy" , { 0x0457 }}, + { "yopf" , { 0x01D56A }}, + { "yscr" , { 0x01D4CE }}, + { "yucy" , { 0x044E }}, + { "yuml" , { 0xFF }}, + { "zacute" , { 0x017A }}, + { "zcaron" , { 0x017E }}, + { "zcy" , { 0x0437 }}, + { "zdot" , { 0x017C }}, + { "zeetrf" , { 0x2128 }}, + { "zeta" , { 0x03B6 }}, + { "zfr" , { 0x01D537 }}, + { "zhcy" , { 0x0436 }}, + { "zigrarr" , { 0x21DD }}, + { "zopf" , { 0x01D56B }}, + { "zscr" , { 0x01D4CF }}, + { "zwj" , { 0x200D }}, + { "zwnj" , { 0x200C }}, +}; + +static constexpr auto s_NamedEntitiesHTML4 = frozen::make_unordered_map(s_Entities); + +int main(int argv, char** argc) +{ + return (s_NamedEntitiesHTML4.find("real") == s_NamedEntitiesHTML4.end()); +} + diff --git a/examples/pixel_art.cpp b/examples/pixel_art.cpp new file mode 100644 index 0000000..003ffe9 --- /dev/null +++ b/examples/pixel_art.cpp @@ -0,0 +1,120 @@ +#if 0 +g++ $0 -std=c++14 -Iinclude && ./a.out && rm -f a.out && qiv panda.ppm 1up.ppm +exit +#else + +#include +#include +#include + +constexpr frozen::map, 5> Tans{ + {'R', {(char)0xFF, (char)0x00, (char)0x00}}, + {'G', {(char)0x00, (char)0xFF, (char)0x00}}, + {'B', {(char)0x00, (char)0x00, (char)0xFF}}, + {'#', {(char)0x00, (char)0x00, (char)0x00}}, + {' ', {(char)0xFF, (char)0xFF, (char)0xFF}}, +}; + +constexpr unsigned itoa(unsigned char * start, unsigned i) { + constexpr unsigned step = sizeof(unsigned) * 3; + for(unsigned k = 0; k < step; ++k) + *start++ = ' '; + do { + *--start = '0' + i % 10; + i /= 10; + } while(i); + return step; +} + +template struct ppm { + unsigned char bytes[9 /* fixed header*/ + sizeof(unsigned) * 3 * 2 /* to hold sizes */ + 3 * H * W]; + + constexpr ppm(unsigned char const *data) : bytes{0} { + unsigned j = 0; + bytes[j++] = 'P'; + bytes[j++] = '6'; + bytes[j++] = ' '; + + j += itoa(bytes + j, H); + + bytes[j++] = ' '; + + j += itoa(bytes + j, W); + + bytes[j++] = ' '; + bytes[j++] = '2'; + bytes[j++] = '5'; + bytes[j++] = '5'; + bytes[j++] = '\n'; + for (unsigned i = 0; i < H * W; ++i) { + auto const code = Tans.find(data[i])->second; + bytes[j + 3 * i + 0] = code[0]; + bytes[j + 3 * i + 1] = code[1]; + bytes[j + 3 * i + 2] = code[2]; + } + } + + void save(char const path[]) const { + std::ofstream out{path, std::ios::binary}; + out.write((char *)bytes, sizeof bytes); + } +}; + +void make_panda() { + constexpr unsigned char bytes[] = " ### ### " + " ##### ########## ##### " + " ####### ####### " + " #### #### " + " ### ### " + " # # " + " # # " + " # ### ### # " + " # ##### ##### # " + " # #### # # #### # " + " # #### # # #### # " + " # ##### ##### # " + " # ### ## ### # " + " # ## # " + " #### RRR RRR #### " + " ######RRRRR RRRRR###### " + " ######RRRRRRRRRRRR###### " + " ######RRRRRRRRRRRR###### " + " ######RRRRRRRRRRRR###### " + " #######RRRRRRRRRR####### " + " ##### RRRRRRRR #### " + " ### RRRRRR ## " + " RRRR "; + constexpr ppm<26, 22> some{bytes}; + some.save("panda.ppm"); +} + +void make_1up() { + constexpr unsigned char bytes[] = " ###### " + " ##GGGG ## " + " # GGGG # " + " # GGGGGG # " + " # GG GG # " + " #GGG GGGGG# " + " #GGG GG G# " + " # GG G # " + " # GG GG # " + " # GGGGGGGGG G# " + " # GG########GGG# " + " ### # # ### " + " # # # # " + " # # " + " # # " + " ######## " + + ; + constexpr ppm<18, 16> some{bytes}; + some.save("1up.ppm"); +} + +int main() { + make_panda(); + make_1up(); + return 0; +} + +#endif diff --git a/examples/static_assert.cpp b/examples/static_assert.cpp new file mode 100644 index 0000000..0899292 --- /dev/null +++ b/examples/static_assert.cpp @@ -0,0 +1,9 @@ +#include + +static constexpr frozen::set supported_sizes = { + 1, 2, 4 +}; + +static_assert(supported_sizes.count(sizeof(short)), "unsupported size"); + +int main() { return 0; } diff --git a/examples/value_modification.cpp b/examples/value_modification.cpp new file mode 100644 index 0000000..2584efd --- /dev/null +++ b/examples/value_modification.cpp @@ -0,0 +1,37 @@ +#include +#include +#include +#include + +/// MAYBE_CONSTINIT expands to `constinit` if available. +#if __cpp_constinit +#define MAYBE_CONSTINIT constinit +#else +#define MAYBE_CONSTINIT +#endif + +// To make a frozen::unordered_map where you can modify the values, make a +// non-constexpr instance. If available, prefer to use constinit. It will +// initialize the map during compilation and detect any exceptions. +MAYBE_CONSTINIT static frozen::unordered_map fruits = { + {"n_apples", 0}, + {"n_pears", 0}, +}; + +int main() { + // Update the values using at() + fruits.at("n_apples") = 10; + fruits.at("n_pears") = fruits.at("n_apples") * 2; + std::cout << "n_apples: " << fruits.at("n_apples") << std::endl; + std::cout << "n_pears: " << fruits.at("n_pears") << std::endl; + + // You can also update values via the iterator returned by find() + auto found = fruits.find("n_apples"); + found->second = 0; + std::cout << "n_apples: " << fruits.at("n_apples") << std::endl; + + // Range also works + auto range = fruits.equal_range("n_apples"); + range.first->second = 1337; + std::cout << "n_apples: " << fruits.at("n_apples") << std::endl; +} \ No newline at end of file diff --git a/include/frozen/CMakeLists.txt b/include/frozen/CMakeLists.txt new file mode 100644 index 0000000..185378d --- /dev/null +++ b/include/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/include/frozen/algorithm.h b/include/frozen/algorithm.h new file mode 100644 index 0000000..a543eb3 --- /dev/null +++ b/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 +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 class knuth_morris_pratt_searcher { + bits::carray step_; + bits::carray needle_; + + static constexpr bits::carray + build_kmp_cache(char const (&needle)[size + 1]) { + std::ptrdiff_t cnd = 0; + bits::carray 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 + constexpr std::pair 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 +constexpr knuth_morris_pratt_searcher 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 class boyer_moore_searcher { + using skip_table_type = bits::carray; + using suffix_table_type = bits::carray; + + skip_table_type skip_table_; + suffix_table_type suffix_table_; + bits::carray 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 + constexpr std::pair 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 +constexpr boyer_moore_searcher make_boyer_moore_searcher(char const (&needle)[N]) { + return {needle}; +} + +} // namespace frozen + +#endif diff --git a/include/frozen/bits/algorithms.h b/include/frozen/bits/algorithms.h new file mode 100644 index 0000000..8d1ffbc --- /dev/null +++ b/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 +#include + +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::digits; + v--; + for(std::size_t i = 1; i < trip_count; i <<= 1) + v |= v >> i; + v++; + return v; +} + +template +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); +unsigned long select_uint_least(std::integral_constant); +unsigned long long select_uint_least(std::integral_constant); +template +unsigned long long select_uint_least(std::integral_constant) { + static_assert(N < 2, "unsupported type size"); + return {}; +} + + +template +using select_uint_least_t = decltype(select_uint_least(std::integral_constant())); + +template +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 +constexpr void cswap(T &a, T &b) { + auto tmp = a; + a = b; + b = tmp; +} + +template +constexpr void cswap(std::pair & a, std::pair & b) { + cswap(a.first, b.first); + cswap(a.second, b.second); +} + +template +constexpr void cswap(std::tuple &a, std::tuple &b, std::index_sequence) { + using swallow = int[]; + (void) swallow{(cswap(std::get(a), std::get(b)), 0)...}; +} + +template +constexpr void cswap(std::tuple &a, std::tuple &b) { + cswap(a, b, std::make_index_sequence()); +} + +template +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 +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 +constexpr bits::carray quicksort(bits::carray const &array, + Compare const &compare) { + bits::carray res = array; + quicksort(res.begin(), res.end() - 1, compare); + return res; +} + +template struct LowerBound { + T const &value_; + Compare const &compare_; + constexpr LowerBound(T const &value, Compare const &compare) + : value_(value), compare_(compare) {} + + template + inline constexpr ForwardIt doit_fast(ForwardIt first, + std::integral_constant) { + return first; + } + + template + inline constexpr ForwardIt doit_fast(ForwardIt first, + std::integral_constant) { + 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{}); + } + + template + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { + return doit_fast(first, std::integral_constant{}); + } + + template + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { + 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::integral_constant{}); + } + else + return doit_fast(first, std::integral_constant{}); + } + + template + inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { + return doit_fast(first, std::integral_constant{}); + } +}; + +template +constexpr ForwardIt lower_bound(ForwardIt first, const T &value, Compare const &compare) { + return LowerBound{value, compare}.doitfirst(first, std::integral_constant{}, std::integral_constant{}); +} + +template +constexpr bool binary_search(ForwardIt first, const T &value, + Compare const &compare) { + ForwardIt where = lower_bound(first, value, compare); + return (!(where == first + N) && !(compare(value, *where))); +} + + +template +constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) +{ + for (; first1 != last1; ++first1, ++first2) { + if (!(*first1 == *first2)) { + return false; + } + } + return true; +} + +template +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/include/frozen/bits/basic_types.h b/include/frozen/bits/basic_types.h new file mode 100644 index 0000000..b54a60d --- /dev/null +++ b/include/frozen/bits/basic_types.h @@ -0,0 +1,207 @@ +/* + * 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 +#include +#include +#include + +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 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 carray { + T data_ [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise + + template + constexpr carray(T const (&init)[M], std::index_sequence) + : data_{init[I]...} {} + template + constexpr carray(Iter iter, std::index_sequence) + : 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; + using const_reverse_iterator = std::reverse_iterator; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + + // Constructors + constexpr carray(void) = default; + template + constexpr carray(T const (&init)[M]) + : carray(init, std::make_index_sequence()) + { + static_assert(M >= N, "Cannot initialize a carray with an smaller array"); + } + template + constexpr carray(std::array const &init) + : carray(&init[0], std::make_index_sequence()) + { + static_assert(M >= N, "Cannot initialize a carray with an smaller array"); + } + constexpr carray(std::initializer_list init) + : carray(init.begin(), std::make_index_sequence()) + { + // 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 carray { + +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; + using const_reverse_iterator = std::reverse_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/include/frozen/bits/constexpr_assert.h b/include/frozen/bits/constexpr_assert.h new file mode 100644 index 0000000..912210d --- /dev/null +++ b/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 + +#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/include/frozen/bits/defines.h b/include/frozen/bits/defines.h new file mode 100644 index 0000000..e20f6d0 --- /dev/null +++ b/include/frozen/bits/defines.h @@ -0,0 +1,66 @@ +/* + * 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() + #define FROZEN_LETITGO_HAS_STRING_VIEW + #endif +#endif + +#ifdef __cpp_char8_t + #define FROZEN_LETITGO_HAS_CHAR8T +#endif + +#if __cpp_deduction_guides >= 201703L + #define FROZEN_LETITGO_HAS_DEDUCTION_GUIDES +#endif + +#if __cpp_lib_constexpr_string >= 201907L + #define FROZEN_LETITGO_HAS_CONSTEXPR_STRING +#endif + +#endif // FROZEN_LETITGO_DEFINES_H diff --git a/include/frozen/bits/elsa.h b/include/frozen/bits/elsa.h new file mode 100644 index 0000000..4618a9e --- /dev/null +++ b/include/frozen/bits/elsa.h @@ -0,0 +1,57 @@ +/* + * 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 + +namespace frozen { + +template struct elsa { + static_assert(std::is_integral::value || std::is_enum::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(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 <> struct elsa { + template + constexpr std::size_t operator()(T const &value, std::size_t seed) const { + return elsa{}(value, seed); + } +}; + +template using anna = elsa; +} // namespace frozen + +#endif diff --git a/include/frozen/bits/elsa_std.h b/include/frozen/bits/elsa_std.h new file mode 100644 index 0000000..0445e73 --- /dev/null +++ b/include/frozen/bits/elsa_std.h @@ -0,0 +1,40 @@ +#ifndef FROZEN_LETITGO_BITS_ELSA_STD_H +#define FROZEN_LETITGO_BITS_ELSA_STD_H + +#include "elsa.h" +#include "hash_string.h" + +#ifdef FROZEN_LETITGO_HAS_STRING_VIEW +#include +#endif +#include + +namespace frozen { + +#ifdef FROZEN_LETITGO_HAS_STRING_VIEW + +template struct elsa> +{ + constexpr std::size_t operator()(const std::basic_string_view& value) const { + return hash_string(value); + } + constexpr std::size_t operator()(const std::basic_string_view& value, std::size_t seed) const { + return hash_string(value, seed); + } +}; + +#endif + +template struct elsa> +{ + constexpr std::size_t operator()(const std::basic_string& value) const { + return hash_string(value); + } + constexpr std::size_t operator()(const std::basic_string& value, std::size_t seed) const { + return hash_string(value, seed); + } +}; + +} // namespace frozen + +#endif // FROZEN_LETITGO_BITS_ELSA_STD_H \ No newline at end of file diff --git a/include/frozen/bits/exceptions.h b/include/frozen/bits/exceptions.h new file mode 100644 index 0000000..b43e3e6 --- /dev/null +++ b/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 +#define FROZEN_THROW_OR_ABORT(_) std::abort() + +#else + +#include +#define FROZEN_THROW_OR_ABORT(err) throw err + + +#endif + +#endif diff --git a/include/frozen/bits/hash_string.h b/include/frozen/bits/hash_string.h new file mode 100644 index 0000000..da8fc51 --- /dev/null +++ b/include/frozen/bits/hash_string.h @@ -0,0 +1,28 @@ +#ifndef FROZEN_LETITGO_BITS_HASH_STRING_H +#define FROZEN_LETITGO_BITS_HASH_STRING_H + +#include + +namespace frozen { + +template +constexpr std::size_t hash_string(const String& value) { + std::size_t d = 5381; + for (const auto& c : value) + d = d * 33 + static_cast(c); + 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. +template +constexpr std::size_t hash_string(const String& value, std::size_t seed) { + std::size_t d = (0x811c9dc5 ^ seed) * static_cast(0x01000193); + for (const auto& c : value) + d = (d ^ static_cast(c)) * static_cast(0x01000193); + return d >> 8 ; +} + +} // namespace frozen + +#endif // FROZEN_LETITGO_BITS_HASH_STRING_H \ No newline at end of file diff --git a/include/frozen/bits/pmh.h b/include/frozen/bits/pmh.h new file mode 100644 index 0000000..f7261f8 --- /dev/null +++ b/include/frozen/bits/pmh.h @@ -0,0 +1,245 @@ +/* + * 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 +#include + +namespace frozen { + +namespace bits { + +// Function object for sorting buckets in decreasing order of size +struct bucket_size_compare { + template + 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 +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; + carray 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 + carray constexpr make_bucket_refs(std::index_sequence) const { + return {{ bucket_ref{Is, &buckets[Is]}... }}; + } + + // Makes a bucket_ref for each bucket and sorts them by size + carray constexpr get_sorted_buckets() const { + carray result{this->make_bucket_refs(std::make_index_sequence())}; + bits::quicksort(result.begin(), result.end() - 1, bucket_size_compare{}); + return result; + } +}; + +template +pmh_buckets constexpr make_pmh_buckets(const carray & items, + Hash const & hash, + Key const & key, + PRG & prg) { + using result_t = pmh_buckets; + 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(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 +constexpr bool all_different_from(cvector & 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::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 +struct pmh_tables { + uint64_t first_seed_; + carray first_table_; + carray second_table_; + Hasher hash_; + + template + constexpr std::size_t lookup(const KeyType & key) const { + return lookup(key, hash_); + } + + // Looks up a given key, to find its expected index in carray + // Always returns a valid index, must use KeyEqual test after to confirm. + template + constexpr std::size_t lookup(const KeyType & key, const HasherType& hasher) const { + auto const d = first_table_[hasher(key, static_cast(first_seed_)) % M]; + if (!d.is_seed()) { return static_cast(d.value()); } // this is narrowing uint64 -> size_t but should be fine + else { return second_table_[hasher(key, static_cast(d.value())) % M]; } + } +}; + +// Make pmh tables for given items, hash function, prg, etc. +template +pmh_tables constexpr make_pmh_tables(const carray & + items, + Hash const &hash, + Key const &key, + PRG prg) { + // Step 1: Place all of the keys into buckets + auto step_one = make_pmh_buckets(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 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::max(); + carray 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(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 bucket_slots; + + while (bucket_slots.size() < bsize) { + auto slot = hash(key(items[bucket[bucket_slots.size()]]), static_cast(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/include/frozen/bits/version.h b/include/frozen/bits/version.h new file mode 100644 index 0000000..7e57d70 --- /dev/null +++ b/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 1 +#define FROZEN_PATCH_VERSION 1 + +#endif diff --git a/include/frozen/map.h b/include/frozen/map.h new file mode 100644 index 0000000..54008cf --- /dev/null +++ b/include/frozen/map.h @@ -0,0 +1,354 @@ +/* + * 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 + +namespace frozen { + +namespace impl { + +template class CompareKey { + + Comparator const comparator_; + +public: + constexpr CompareKey(Comparator const &comparator) + : comparator_(comparator) {} + + template + constexpr int operator()(std::pair const &self, + std::pair const &other) const { + return comparator_(std::get<0>(self), std::get<0>(other)); + } + + template + constexpr int operator()(Key1 const &self_key, + std::pair const &other) const { + return comparator_(self_key, std::get<0>(other)); + } + + template + constexpr int operator()(std::pair const &self, + Key2 const &other_key) const { + return comparator_(std::get<0>(self), other_key); + } + + template + constexpr int operator()(Key1 const &self_key, Key2 const &other_key) const { + return comparator_(self_key, other_key); + } +}; + +} // namespace impl + +template > +class map { + using container_type = bits::carray, N>; + impl::CompareKey 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 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 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 */ + + template + constexpr std::size_t count(KeyType const &key) const { + return bits::binary_search(items_.begin(), key, less_than_); + } + + template + constexpr const_iterator find(KeyType const &key) const { + return map::find_impl(*this, key); + } + template + constexpr iterator find(KeyType const &key) { + return map::find_impl(*this, key); + } + + template + constexpr std::pair + equal_range(KeyType const &key) const { + return equal_range_impl(*this, key); + } + template + constexpr std::pair equal_range(KeyType const &key) { + return equal_range_impl(*this, key); + } + + template + constexpr const_iterator lower_bound(KeyType const &key) const { + return lower_bound_impl(*this, key); + } + template + constexpr iterator lower_bound(KeyType const &key) { + return lower_bound_impl(*this, key); + } + + template + constexpr const_iterator upper_bound(KeyType const &key) const { + return upper_bound_impl(*this, key); + } + template + constexpr iterator upper_bound(KeyType const &key) { + return upper_bound_impl(*this, key); + } + + /* observers */ + constexpr const key_compare& key_comp() const { return less_than_; } + constexpr const key_compare& value_comp() const { return less_than_; } + + private: + template + static inline constexpr auto& at_impl(This&& self, KeyType 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 + static inline constexpr auto find_impl(This&& self, KeyType const &key) { + auto where = self.lower_bound(key); + if ((where != self.end()) && !self.less_than_(key, *where)) + return where; + else + return self.end(); + } + + template + static inline constexpr auto equal_range_impl(This&& self, KeyType const &key) { + auto lower = self.lower_bound(key); + using lower_t = decltype(lower); + if (lower == self.end()) + return std::pair{lower, lower}; + else + return std::pair{lower, lower + 1}; + } + + template + static inline constexpr auto lower_bound_impl(This&& self, KeyType const &key) -> decltype(self.end()) { + auto where = bits::lower_bound(self.items_.begin(), key, self.less_than_); + if ((where != self.end()) && !self.less_than_(key, *where)) + return where; + else + return self.end(); + } + + template + static inline constexpr auto upper_bound_impl(This&& self, KeyType const &key) -> decltype(self.end()) { + auto where = bits::lower_bound(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 map { + using container_type = bits::carray, 0>; + impl::CompareKey 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, Compare const &compare) + : less_than_{compare} {} + constexpr map(std::initializer_list items) + : map{items, Compare{}} {} + + /* element access */ + template + constexpr mapped_type at(KeyType const &) const { + FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key")); + } + template + constexpr mapped_type at(KeyType 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 */ + + template + constexpr std::size_t count(KeyType const &) const { return 0; } + + template + constexpr const_iterator find(KeyType const &) const { return end(); } + template + constexpr iterator find(KeyType const &) { return end(); } + + template + constexpr std::pair + equal_range(KeyType const &) const { return {end(), end()}; } + template + constexpr std::pair + equal_range(KeyType const &) { return {end(), end()}; } + + template + constexpr const_iterator lower_bound(KeyType const &) const { return end(); } + template + constexpr iterator lower_bound(KeyType const &) { return end(); } + + template + constexpr const_iterator upper_bound(KeyType const &) const { return end(); } + template + constexpr iterator upper_bound(KeyType const &) { return end(); } + +/* observers */ + constexpr key_compare const& key_comp() const { return less_than_; } + constexpr key_compare const& value_comp() const { return less_than_; } +}; + +template > +constexpr auto make_map(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { + return map{}; +} + +template +constexpr auto make_map(std::pair const (&items)[N]) { + return map{items}; +} + +template +constexpr auto make_map(std::array, N> const &items) { + return map{items}; +} + +template +constexpr auto make_map(std::pair const (&items)[N], Compare const& compare = Compare{}) { + return map{items, compare}; +} + +template +constexpr auto make_map(std::array, N> const &items, Compare const& compare = Compare{}) { + return map{items, compare}; +} + +} // namespace frozen + +#endif diff --git a/include/frozen/random.h b/include/frozen/random.h new file mode 100644 index 0000000..727133b --- /dev/null +++ b/include/frozen/random.h @@ -0,0 +1,97 @@ +/* + * 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 +#include + +namespace frozen { +template +class linear_congruential_engine { + + static_assert(std::is_unsigned::value, + "UIntType must be an unsigned integral type"); + + template + static constexpr UIntType modulo(T val, std::integral_constant) { + return static_cast(val); + } + + template + static constexpr UIntType modulo(T val, std::integral_constant) { + // the static cast below may end up doing a truncation + return static_cast(val % M); + } + +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; + uint_least_t tmp = static_cast(multiplier) * state_ + increment; + + state_ = modulo(tmp, std::integral_constant()); + 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; +using minstd_rand = + linear_congruential_engine; + +// This generator is used by default in unordered frozen containers +using default_prg_t = minstd_rand; + +} // namespace frozen + +#endif diff --git a/include/frozen/set.h b/include/frozen/set.h new file mode 100644 index 0000000..c2f2f0d --- /dev/null +++ b/include/frozen/set.h @@ -0,0 +1,256 @@ +/* + * 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 "frozen/bits/defines.h" + +#include + +namespace frozen { + +template > class set { + using container_type = bits::carray; + 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 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 keys) + : set{keys, Compare{}} {} + + constexpr set& operator=(const set &other) = default; + + /* capacity */ + constexpr bool empty() const { return !N; } + constexpr size_type size() const { return N; } + constexpr size_type max_size() const { return N; } + + /* lookup */ + template + constexpr std::size_t count(KeyType const &key) const { + return bits::binary_search(keys_.begin(), key, less_than_); + } + + template + constexpr const_iterator find(KeyType const &key) const { + const_iterator where = lower_bound(key); + if ((where != end()) && !less_than_(key, *where)) + return where; + else + return end(); + } + + template + constexpr std::pair equal_range(KeyType const &key) const { + auto const lower = lower_bound(key); + if (lower == end()) + return {lower, lower}; + else + return {lower, lower + 1}; + } + + template + constexpr const_iterator lower_bound(KeyType const &key) const { + auto const where = bits::lower_bound(keys_.begin(), key, less_than_); + if ((where != end()) && !less_than_(key, *where)) + return where; + else + return end(); + } + + template + constexpr const_iterator upper_bound(KeyType const &key) const { + auto const where = bits::lower_bound(keys_.begin(), key, less_than_); + if ((where != end()) && !less_than_(key, *where)) + return where + 1; + else + return end(); + } + + /* observers */ + constexpr const key_compare& key_comp() const { return less_than_; } + constexpr const 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 set { + using container_type = bits::carray; // 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, Compare const &) {} + explicit constexpr set(bits::carray) {} + + constexpr set(std::initializer_list, Compare const &comp) + : less_than_{comp} {} + constexpr set(std::initializer_list keys) : set{keys, Compare{}} {} + + constexpr set& operator=(const set &other) = default; + + /* capacity */ + constexpr bool empty() const { return true; } + constexpr size_type size() const { return 0; } + constexpr size_type max_size() const { return 0; } + + /* lookup */ + template + constexpr std::size_t count(KeyType const &) const { return 0; } + + template + constexpr const_iterator find(KeyType const &) const { return end(); } + + template + constexpr std::pair + equal_range(KeyType const &) const { return {end(), end()}; } + + template + constexpr const_iterator lower_bound(KeyType const &) const { return end(); } + + template + constexpr const_iterator upper_bound(KeyType 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 +constexpr auto make_set(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { + return set{}; +} + +template +constexpr auto make_set(const T (&args)[N]) { + return set(args); +} + +template +constexpr auto make_set(std::array const &args) { + return set(args); +} + +template +constexpr auto make_set(const T (&args)[N], Compare const& compare = Compare{}) { + return set(args, compare); +} + +template +constexpr auto make_set(std::array const &args, Compare const& compare = Compare{}) { + return set(args, compare); +} + +#ifdef FROZEN_LETITGO_HAS_DEDUCTION_GUIDES + +template +set(T, Args...) -> set; + +#endif // FROZEN_LETITGO_HAS_DEDUCTION_GUIDES + +} // namespace frozen + +#endif diff --git a/include/frozen/string.h b/include/frozen/string.h new file mode 100644 index 0000000..9274406 --- /dev/null +++ b/include/frozen/string.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_STRING_H +#define FROZEN_LETITGO_STRING_H + +#include "frozen/bits/elsa.h" +#include "frozen/bits/hash_string.h" +#include "frozen/bits/version.h" +#include "frozen/bits/defines.h" + +#include + +#ifdef FROZEN_LETITGO_HAS_STRING_VIEW +#include +#endif + +namespace frozen { + +template +class basic_string { + using chr_t = _CharT; + + chr_t const *data_; + std::size_t size_; + +public: + template + 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 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_; } + constexpr const chr_t *begin() const { return data(); } + constexpr const chr_t *end() const { return data() + size(); } +}; + +template struct elsa> { + constexpr std::size_t operator()(basic_string<_CharT> value) const { + return hash_string(value); + } + constexpr std::size_t operator()(basic_string<_CharT> value, std::size_t seed) const { + return hash_string(value, seed); + } +}; + +using string = basic_string; +using wstring = basic_string; +using u16string = basic_string; +using u32string = basic_string; + +#ifdef FROZEN_LETITGO_HAS_CHAR8T +using u8string = basic_string; +#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 struct hash> { + size_t operator()(frozen::basic_string<_CharT> s) const { + return frozen::elsa>{}(s); + } +}; +} // namespace std + +#endif diff --git a/include/frozen/unordered_map.h b/include/frozen/unordered_map.h new file mode 100644 index 0000000..8835a20 --- /dev/null +++ b/include/frozen/unordered_map.h @@ -0,0 +1,255 @@ +/* + * 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 +#include + +namespace frozen { + +namespace bits { + +struct GetKey { + template constexpr auto const &operator()(KV const &kv) const { + return kv.first; + } +}; + +} // namespace bits + +template , + class KeyEqual = std::equal_to> +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, N>; + using tables_type = bits::pmh_tables; + + KeyEqual const equal_; + container_type items_; + tables_type tables_; + +public: + /* typedefs */ + using Self = unordered_map; + 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( + 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 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 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 */ + template + constexpr std::size_t count(KeyType const &key, Hasher const &hash, Equal const &equal) const { + auto const &kv = lookup(key, hash); + return equal(kv.first, key); + } + template + constexpr std::size_t count(KeyType const &key) const { + return count(key, hash_function(), key_eq()); + } + + template + constexpr Value const &at(KeyType const &key, Hasher const &hash, Equal const &equal) const { + return at_impl(*this, key, hash, equal); + } + template + constexpr Value &at(KeyType const &key, Hasher const &hash, Equal const &equal) { + return at_impl(*this, key, hash, equal); + } + template + constexpr Value const &at(KeyType const &key) const { + return at(key, hash_function(), key_eq()); + } + template + constexpr Value &at(KeyType const &key) { + return at(key, hash_function(), key_eq()); + } + + template + constexpr const_iterator find(KeyType const &key, Hasher const &hash, Equal const &equal) const { + return find_impl(*this, key, hash, equal); + } + template + constexpr iterator find(KeyType const &key, Hasher const &hash, Equal const &equal) { + return find_impl(*this, key, hash, equal); + } + template + constexpr const_iterator find(KeyType const &key) const { + return find(key, hash_function(), key_eq()); + } + template + constexpr iterator find(KeyType const &key) { + return find(key, hash_function(), key_eq()); + } + + template + constexpr std::pair equal_range(KeyType const &key, Hasher const &hash, Equal const &equal) const { + return equal_range_impl(*this, key, hash, equal); + } + template + constexpr std::pair equal_range(KeyType const &key, Hasher const &hash, Equal const &equal) { + return equal_range_impl(*this, key, hash, equal); + } + template + constexpr std::pair equal_range(KeyType const &key) const { + return equal_range(key, hash_function(), key_eq()); + } + template + constexpr std::pair equal_range(KeyType const &key) { + return equal_range(key, hash_function(), key_eq()); + } + + /* 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 const hasher& hash_function() const { return tables_.hash_; } + constexpr const key_equal& key_eq() const { return equal_; } + +private: + template + static inline constexpr auto& at_impl(This&& self, KeyType const &key, Hasher const &hash, Equal const &equal) { + auto& kv = self.lookup(key, hash); + if (equal(kv.first, key)) + return kv.second; + else + FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); + } + + template + static inline constexpr auto find_impl(This&& self, KeyType const &key, Hasher const &hash, Equal const &equal) { + auto& kv = self.lookup(key, hash); + if (equal(kv.first, key)) + return &kv; + else + return self.items_.end(); + } + + template + static inline constexpr auto equal_range_impl(This&& self, KeyType const &key, Hasher const &hash, Equal const &equal) { + auto& kv = self.lookup(key, hash); + using kv_ptr = decltype(&kv); + if (equal(kv.first, key)) + return std::pair{&kv, &kv + 1}; + else + return std::pair{self.items_.end(), self.items_.end()}; + } + + template + static inline constexpr auto& lookup_impl(This&& self, KeyType const &key, Hasher const &hash) { + return self.items_[self.tables_.lookup(key, hash)]; + } + + template + constexpr auto const& lookup(KeyType const &key, Hasher const &hash) const { + return lookup_impl(*this, key, hash); + } + template + constexpr auto& lookup(KeyType const &key, Hasher const &hash) { + return lookup_impl(*this, key, hash); + } +}; + +template +constexpr auto make_unordered_map(std::pair const (&items)[N]) { + return unordered_map{items}; +} + +template +constexpr auto make_unordered_map( + std::pair const (&items)[N], + Hasher const &hash = elsa{}, + Equal const &equal = std::equal_to{}) { + return unordered_map{items, hash, equal}; +} + +template +constexpr auto make_unordered_map(std::array, N> const &items) { + return unordered_map{items}; +} + +template +constexpr auto make_unordered_map( + std::array, N> const &items, + Hasher const &hash = elsa{}, + Equal const &equal = std::equal_to{}) { + return unordered_map{items, hash, equal}; +} + +} // namespace frozen + +#endif diff --git a/include/frozen/unordered_set.h b/include/frozen/unordered_set.h new file mode 100644 index 0000000..4d16df9 --- /dev/null +++ b/include/frozen/unordered_set.h @@ -0,0 +1,187 @@ +/* + * 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 + +namespace frozen { + +namespace bits { + +struct Get { + template constexpr T const &operator()(T const &key) const { + return key; + } +}; + +} // namespace bits + +template , + class KeyEqual = std::equal_to> +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; + using tables_type = bits::pmh_tables; + + 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( + 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 keys) + : unordered_set{keys, Hash{}, KeyEqual{}} {} + + constexpr unordered_set(std::initializer_list 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 */ + template + constexpr std::size_t count(KeyType const &key, Hasher const &hash, Equal const &equal) const { + auto const k = lookup(key, hash); + return equal(k, key); + } + template + constexpr std::size_t count(KeyType const &key) const { + return count(key, hash_function(), key_eq()); + } + + template + constexpr const_iterator find(KeyType const &key, Hasher const &hash, Equal const &equal) const { + auto const &k = lookup(key, hash); + if (equal(k, key)) + return &k; + else + return keys_.end(); + } + template + constexpr const_iterator find(KeyType const &key) const { + return find(key, hash_function(), key_eq()); + } + + template + constexpr std::pair equal_range( + KeyType const &key, Hasher const &hash, Equal const &equal) const { + auto const &k = lookup(key, hash); + if (equal(k, key)) + return {&k, &k + 1}; + else + return {keys_.end(), keys_.end()}; + } + template + constexpr std::pair equal_range(KeyType const &key) const { + return equal_range(key, hash_function(), key_eq()); + } + + /* 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 const hasher& hash_function() const { return tables_.hash_; } + constexpr const key_equal& key_eq() const { return equal_; } + +private: + template + constexpr auto const &lookup(KeyType const &key, Hasher const &hash) const { + return keys_[tables_.lookup(key, hash)]; + } +}; + +template +constexpr auto make_unordered_set(T const (&keys)[N]) { + return unordered_set{keys}; +} + +template +constexpr auto make_unordered_set(T const (&keys)[N], Hasher const& hash, Equal const& equal) { + return unordered_set{keys, hash, equal}; +} + +template +constexpr auto make_unordered_set(std::array const &keys) { + return unordered_set{keys}; +} + +template +constexpr auto make_unordered_set(std::array const &keys, Hasher const& hash, Equal const& equal) { + return unordered_set{keys, hash, equal}; +} + +#ifdef FROZEN_LETITGO_HAS_DEDUCTION_GUIDES + +template +unordered_set(T, Args...) -> unordered_set; + +#endif + +} // namespace frozen + +#endif diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt new file mode 100644 index 0000000..2e79297 --- /dev/null +++ b/tests/CMakeLists.txt @@ -0,0 +1,61 @@ +configure_file( + "${PROJECT_SOURCE_DIR}/cmake/CTestCustom.cmake" + "${PROJECT_BINARY_DIR}/CTestCustom.cmake" + COPYONLY) + +add_executable(frozen.tests "") +target_link_libraries(frozen.tests PUBLIC frozen::frozen) + +target_sources(frozen.tests PRIVATE + ${CMAKE_CURRENT_LIST_DIR}/bench.hpp + ${CMAKE_CURRENT_LIST_DIR}/catch.hpp + ${CMAKE_CURRENT_LIST_DIR}/test_algorithms.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_elsa_std.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_main.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_map.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_rand.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_str.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_str_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_unordered_map.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_unordered_map_str.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_unordered_set.cpp + ${CMAKE_CURRENT_LIST_DIR}/test_unordered_str_set.cpp) + +string(CONCAT generator + # msvc gives invalid integral overflow warning for unsigned type + "$<$:/W3;/WX;/wd4307>" + "$<$" + ",$" + ",$>" + ":-Wall;-Wextra;-Wpedantic;-Werror;-Wshadow;" + "$<$:--coverage>>" + "$<$:" + "$<$:/W3;/WX;>" + "$<$>:-Wall;-Werror>>") + +target_compile_options(frozen.tests PUBLIC ${generator}) + +if(cxx_20_supported) + target_compile_features(frozen.tests PUBLIC cxx_std_20) +elseif(cxx_17_supported) + target_compile_features(frozen.tests PUBLIC cxx_std_17) +endif() + +string(CONCAT generator + "$<$" + ",$" + ",$>" + ":$<$:--coverage>>") + +target_link_libraries(frozen.tests PUBLIC ${generator}) +add_test(NAME frozen.tests COMMAND frozen.tests) + + +add_executable(test_no_expections + ${CMAKE_CURRENT_LIST_DIR}/no_exceptions.cpp) +target_link_libraries(test_no_expections PUBLIC frozen::frozen) +target_compile_options(test_no_expections PUBLIC "-fno-exceptions") + +add_test(no_exceptions test_no_expections) +set_tests_properties(no_exceptions PROPERTIES WILL_FAIL TRUE) diff --git a/tests/Makefile b/tests/Makefile new file mode 100644 index 0000000..b4f75be --- /dev/null +++ b/tests/Makefile @@ -0,0 +1,64 @@ +SRCS=test_main.cpp test_rand.cpp test_set.cpp test_map.cpp test_unordered_set.cpp test_str_set.cpp test_unordered_str_set.cpp test_unordered_map.cpp test_unordered_map_str.cpp test_str.cpp test_algorithms.cpp + +TARGET=test_main +CXXFLAGS=-O3 -Wall -std=c++14 -march=native -Wextra -W -Werror -Wshadow -fPIC +CPPFLAGS=-I../include + +all:$(TARGET) + +$(TARGET):$(patsubst %.cpp, %.o , $(SRCS)) + $(CXX) $^ -o $@ + +clean: + $(RM) *.o $(TARGET) + +.PHONY:check + +check:$(TARGET) + ./$(TARGET) + +test_main.o: test_main.cpp catch.hpp +test_rand.o: test_rand.cpp \ + ../include/frozen/random.h \ + ../include/frozen/bits/algorithms.h \ + catch.hpp +test_algorithms.o: test_algorithms.cpp \ + ../include/frozen/bits/algorithms.h \ + catch.hpp +test_map.o: test_map.cpp ../include/frozen/map.h \ + ../include/frozen/bits/algorithms.h catch.hpp +test_set.o: test_set.cpp ../include/frozen/set.h \ + ../include/frozen/bits/algorithms.h catch.hpp +test_unordered_map.o: test_unordered_map.cpp \ + ../include/frozen/unordered_map.h ../include/frozen/bits/elsa.h \ + ../include/frozen/bits/pmh.h \ + ../include/frozen/bits/algorithms.h \ + ../include/frozen/bits/basic_types.h \ + catch.hpp +test_unordered_map_str.o: test_unordered_map_str.cpp \ + ../include/frozen/unordered_map.h ../include/frozen/bits/elsa.h \ + ../include/frozen/bits/pmh.h \ + ../include/frozen/bits/algorithms.h \ + ../include/frozen/bits/basic_types.h ../include/frozen/string.h \ + catch.hpp +test_unordered_set.o: test_unordered_set.cpp \ + ../include/frozen/unordered_set.h ../include/frozen/bits/pmh.h \ + ../include/frozen/bits/algorithms.h \ + ../include/frozen/bits/basic_types.h ../include/frozen/bits/elsa.h \ + catch.hpp +test_unordered_str_set.o: test_unordered_str_set.cpp \ + ../include/frozen/unordered_set.h ../include/frozen/bits/pmh.h \ + ../include/frozen/bits/algorithms.h \ + ../include/frozen/bits/basic_types.h ../include/frozen/bits/elsa.h \ + ../include/frozen/string.h \ + catch.hpp +test_str_set.o: test_str_set.cpp \ + ../include/frozen/set.h \ + ../include/frozen/bits/algorithms.h \ + ../include/frozen/bits/basic_types.h ../include/frozen/bits/elsa.h \ + ../include/frozen/string.h \ + catch.hpp +test_str.o: test_str.cpp \ + ../include/frozen/bits/basic_types.h ../include/frozen/bits/elsa.h \ + ../include/frozen/string.h ../include/frozen/algorithm.h \ + catch.hpp diff --git a/tests/bench.hpp b/tests/bench.hpp new file mode 100644 index 0000000..e6645ea --- /dev/null +++ b/tests/bench.hpp @@ -0,0 +1,65 @@ +// Copyright 2015 Google Inc. All rights reserved. +// +// 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. + +// Extracted from google benchmarks suite +// c.f. https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h +// +// These two functions DoNotOptimize and ClobberMemory prevent the compiler +// from optimizing in certain ways. +// +// There is an excellent talk by Chandler Carruth about this here: +// https://www.youtube.com/watch?v=nXaxk27zwlk + +#ifndef FROZEN_LETITGO_BENCH_HPP +#define FROZEN_LETITGO_BENCH_HPP + +namespace benchmark { + +#if defined(__GNUC__) +#define BENCHMARK_ALWAYS_INLINE __attribute__((always_inline)) +#else +#define BENCHMARK_ALWAYS_INLINE +#endif + +#if defined(__GNUC__) +template +inline BENCHMARK_ALWAYS_INLINE void +DoNotOptimize(Tp const & value) { + asm volatile("" : : "g"(value) : "memory"); +} +// Force the compiler to flush pending writes to global memory. Acts as an +// effective read/write barrier +inline BENCHMARK_ALWAYS_INLINE void +ClobberMemory() { + asm volatile("" : : : "memory"); +} + +#else + +template +inline BENCHMARK_ALWAYS_INLINE void +DoNotOptimize(Tp const & value) { + static_cast(&reinterpret_cast(value)); +} + +// TODO +template +inline BENCHMARK_ALWAYS_INLINE void +ClobberMemory() {} + +#endif + +} // end namespace benchmark + +#endif diff --git a/tests/catch.hpp b/tests/catch.hpp new file mode 100644 index 0000000..db1fed3 --- /dev/null +++ b/tests/catch.hpp @@ -0,0 +1,17966 @@ +/* + * Catch v2.13.8 + * Generated: 2022-01-03 21:20:09.589503 + * ---------------------------------------------------------- + * This file has been merged from multiple headers. Please don't edit it directly + * Copyright (c) 2022 Two Blue Cubes Ltd. All rights reserved. + * + * Distributed under the Boost Software License, Version 1.0. (See accompanying + * file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + */ +#ifndef TWOBLUECUBES_SINGLE_INCLUDE_CATCH_HPP_INCLUDED +#define TWOBLUECUBES_SINGLE_INCLUDE_CATCH_HPP_INCLUDED +// start catch.hpp + + +#define CATCH_VERSION_MAJOR 2 +#define CATCH_VERSION_MINOR 13 +#define CATCH_VERSION_PATCH 8 + +#ifdef __clang__ +# pragma clang system_header +#elif defined __GNUC__ +# pragma GCC system_header +#endif + +// start catch_suppress_warnings.h + +#ifdef __clang__ +# ifdef __ICC // icpc defines the __clang__ macro +# pragma warning(push) +# pragma warning(disable: 161 1682) +# else // __ICC +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wpadded" +# pragma clang diagnostic ignored "-Wswitch-enum" +# pragma clang diagnostic ignored "-Wcovered-switch-default" +# endif +#elif defined __GNUC__ + // Because REQUIREs trigger GCC's -Wparentheses, and because still + // supported version of g++ have only buggy support for _Pragmas, + // Wparentheses have to be suppressed globally. +# pragma GCC diagnostic ignored "-Wparentheses" // See #674 for details + +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-variable" +# pragma GCC diagnostic ignored "-Wpadded" +#endif +// end catch_suppress_warnings.h +#if defined(CATCH_CONFIG_MAIN) || defined(CATCH_CONFIG_RUNNER) +# define CATCH_IMPL +# define CATCH_CONFIG_ALL_PARTS +#endif + +// In the impl file, we want to have access to all parts of the headers +// Can also be used to sanely support PCHs +#if defined(CATCH_CONFIG_ALL_PARTS) +# define CATCH_CONFIG_EXTERNAL_INTERFACES +# if defined(CATCH_CONFIG_DISABLE_MATCHERS) +# undef CATCH_CONFIG_DISABLE_MATCHERS +# endif +# if !defined(CATCH_CONFIG_ENABLE_CHRONO_STRINGMAKER) +# define CATCH_CONFIG_ENABLE_CHRONO_STRINGMAKER +# endif +#endif + +#if !defined(CATCH_CONFIG_IMPL_ONLY) +// start catch_platform.h + +// See e.g.: +// https://opensource.apple.com/source/CarbonHeaders/CarbonHeaders-18.1/TargetConditionals.h.auto.html +#ifdef __APPLE__ +# include +# if (defined(TARGET_OS_OSX) && TARGET_OS_OSX == 1) || \ + (defined(TARGET_OS_MAC) && TARGET_OS_MAC == 1) +# define CATCH_PLATFORM_MAC +# elif (defined(TARGET_OS_IPHONE) && TARGET_OS_IPHONE == 1) +# define CATCH_PLATFORM_IPHONE +# endif + +#elif defined(linux) || defined(__linux) || defined(__linux__) +# define CATCH_PLATFORM_LINUX + +#elif defined(WIN32) || defined(__WIN32__) || defined(_WIN32) || defined(_MSC_VER) || defined(__MINGW32__) +# define CATCH_PLATFORM_WINDOWS +#endif + +// end catch_platform.h + +#ifdef CATCH_IMPL +# ifndef CLARA_CONFIG_MAIN +# define CLARA_CONFIG_MAIN_NOT_DEFINED +# define CLARA_CONFIG_MAIN +# endif +#endif + +// start catch_user_interfaces.h + +namespace Catch { + unsigned int rngSeed(); +} + +// end catch_user_interfaces.h +// start catch_tag_alias_autoregistrar.h + +// start catch_common.h + +// start catch_compiler_capabilities.h + +// Detect a number of compiler features - by compiler +// The following features are defined: +// +// CATCH_CONFIG_COUNTER : is the __COUNTER__ macro supported? +// CATCH_CONFIG_WINDOWS_SEH : is Windows SEH supported? +// CATCH_CONFIG_POSIX_SIGNALS : are POSIX signals supported? +// CATCH_CONFIG_DISABLE_EXCEPTIONS : Are exceptions enabled? +// **************** +// Note to maintainers: if new toggles are added please document them +// in configuration.md, too +// **************** + +// In general each macro has a _NO_ form +// (e.g. CATCH_CONFIG_NO_POSIX_SIGNALS) which disables the feature. +// Many features, at point of detection, define an _INTERNAL_ macro, so they +// can be combined, en-mass, with the _NO_ forms later. + +#ifdef __cplusplus + +# if (__cplusplus >= 201402L) || (defined(_MSVC_LANG) && _MSVC_LANG >= 201402L) +# define CATCH_CPP14_OR_GREATER +# endif + +# if (__cplusplus >= 201703L) || (defined(_MSVC_LANG) && _MSVC_LANG >= 201703L) +# define CATCH_CPP17_OR_GREATER +# endif + +#endif + +// Only GCC compiler should be used in this block, so other compilers trying to +// mask themselves as GCC should be ignored. +#if defined(__GNUC__) && !defined(__clang__) && !defined(__ICC) && !defined(__CUDACC__) && !defined(__LCC__) +# define CATCH_INTERNAL_START_WARNINGS_SUPPRESSION _Pragma( "GCC diagnostic push" ) +# define CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION _Pragma( "GCC diagnostic pop" ) + +# define CATCH_INTERNAL_IGNORE_BUT_WARN(...) (void)__builtin_constant_p(__VA_ARGS__) + +#endif + +#if defined(__clang__) + +# define CATCH_INTERNAL_START_WARNINGS_SUPPRESSION _Pragma( "clang diagnostic push" ) +# define CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION _Pragma( "clang diagnostic pop" ) + +// As of this writing, IBM XL's implementation of __builtin_constant_p has a bug +// which results in calls to destructors being emitted for each temporary, +// without a matching initialization. In practice, this can result in something +// like `std::string::~string` being called on an uninitialized value. +// +// For example, this code will likely segfault under IBM XL: +// ``` +// REQUIRE(std::string("12") + "34" == "1234") +// ``` +// +// Therefore, `CATCH_INTERNAL_IGNORE_BUT_WARN` is not implemented. +# if !defined(__ibmxl__) && !defined(__CUDACC__) +# define CATCH_INTERNAL_IGNORE_BUT_WARN(...) (void)__builtin_constant_p(__VA_ARGS__) /* NOLINT(cppcoreguidelines-pro-type-vararg, hicpp-vararg) */ +# endif + +# define CATCH_INTERNAL_SUPPRESS_GLOBALS_WARNINGS \ + _Pragma( "clang diagnostic ignored \"-Wexit-time-destructors\"" ) \ + _Pragma( "clang diagnostic ignored \"-Wglobal-constructors\"") + +# define CATCH_INTERNAL_SUPPRESS_PARENTHESES_WARNINGS \ + _Pragma( "clang diagnostic ignored \"-Wparentheses\"" ) + +# define CATCH_INTERNAL_SUPPRESS_UNUSED_WARNINGS \ + _Pragma( "clang diagnostic ignored \"-Wunused-variable\"" ) + +# define CATCH_INTERNAL_SUPPRESS_ZERO_VARIADIC_WARNINGS \ + _Pragma( "clang diagnostic ignored \"-Wgnu-zero-variadic-macro-arguments\"" ) + +# define CATCH_INTERNAL_SUPPRESS_UNUSED_TEMPLATE_WARNINGS \ + _Pragma( "clang diagnostic ignored \"-Wunused-template\"" ) + +#endif // __clang__ + +//////////////////////////////////////////////////////////////////////////////// +// Assume that non-Windows platforms support posix signals by default +#if !defined(CATCH_PLATFORM_WINDOWS) + #define CATCH_INTERNAL_CONFIG_POSIX_SIGNALS +#endif + +//////////////////////////////////////////////////////////////////////////////// +// We know some environments not to support full POSIX signals +#if defined(__CYGWIN__) || defined(__QNX__) || defined(__EMSCRIPTEN__) || defined(__DJGPP__) + #define CATCH_INTERNAL_CONFIG_NO_POSIX_SIGNALS +#endif + +#ifdef __OS400__ +# define CATCH_INTERNAL_CONFIG_NO_POSIX_SIGNALS +# define CATCH_CONFIG_COLOUR_NONE +#endif + +//////////////////////////////////////////////////////////////////////////////// +// Android somehow still does not support std::to_string +#if defined(__ANDROID__) +# define CATCH_INTERNAL_CONFIG_NO_CPP11_TO_STRING +# define CATCH_INTERNAL_CONFIG_ANDROID_LOGWRITE +#endif + +//////////////////////////////////////////////////////////////////////////////// +// Not all Windows environments support SEH properly +#if defined(__MINGW32__) +# define CATCH_INTERNAL_CONFIG_NO_WINDOWS_SEH +#endif + +//////////////////////////////////////////////////////////////////////////////// +// PS4 +#if defined(__ORBIS__) +# define CATCH_INTERNAL_CONFIG_NO_NEW_CAPTURE +#endif + +//////////////////////////////////////////////////////////////////////////////// +// Cygwin +#ifdef __CYGWIN__ + +// Required for some versions of Cygwin to declare gettimeofday +// see: http://stackoverflow.com/questions/36901803/gettimeofday-not-declared-in-this-scope-cygwin +# define _BSD_SOURCE +// some versions of cygwin (most) do not support std::to_string. Use the libstd check. +// https://gcc.gnu.org/onlinedocs/gcc-4.8.2/libstdc++/api/a01053_source.html line 2812-2813 +# if !((__cplusplus >= 201103L) && defined(_GLIBCXX_USE_C99) \ + && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF)) + +# define CATCH_INTERNAL_CONFIG_NO_CPP11_TO_STRING + +# endif +#endif // __CYGWIN__ + +//////////////////////////////////////////////////////////////////////////////// +// Visual C++ +#if defined(_MSC_VER) + +// Universal Windows platform does not support SEH +// Or console colours (or console at all...) +# if defined(WINAPI_FAMILY) && (WINAPI_FAMILY == WINAPI_FAMILY_APP) +# define CATCH_CONFIG_COLOUR_NONE +# else +# define CATCH_INTERNAL_CONFIG_WINDOWS_SEH +# endif + +# if !defined(__clang__) // Handle Clang masquerading for msvc + +// MSVC traditional preprocessor needs some workaround for __VA_ARGS__ +// _MSVC_TRADITIONAL == 0 means new conformant preprocessor +// _MSVC_TRADITIONAL == 1 means old traditional non-conformant preprocessor +# if !defined(_MSVC_TRADITIONAL) || (defined(_MSVC_TRADITIONAL) && _MSVC_TRADITIONAL) +# define CATCH_INTERNAL_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR +# endif // MSVC_TRADITIONAL + +// Only do this if we're not using clang on Windows, which uses `diagnostic push` & `diagnostic pop` +# define CATCH_INTERNAL_START_WARNINGS_SUPPRESSION __pragma( warning(push) ) +# define CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION __pragma( warning(pop) ) +# endif // __clang__ + +#endif // _MSC_VER + +#if defined(_REENTRANT) || defined(_MSC_VER) +// Enable async processing, as -pthread is specified or no additional linking is required +# define CATCH_INTERNAL_CONFIG_USE_ASYNC +#endif // _MSC_VER + +//////////////////////////////////////////////////////////////////////////////// +// Check if we are compiled with -fno-exceptions or equivalent +#if defined(__EXCEPTIONS) || defined(__cpp_exceptions) || defined(_CPPUNWIND) +# define CATCH_INTERNAL_CONFIG_EXCEPTIONS_ENABLED +#endif + +//////////////////////////////////////////////////////////////////////////////// +// DJGPP +#ifdef __DJGPP__ +# define CATCH_INTERNAL_CONFIG_NO_WCHAR +#endif // __DJGPP__ + +//////////////////////////////////////////////////////////////////////////////// +// Embarcadero C++Build +#if defined(__BORLANDC__) + #define CATCH_INTERNAL_CONFIG_POLYFILL_ISNAN +#endif + +//////////////////////////////////////////////////////////////////////////////// + +// Use of __COUNTER__ is suppressed during code analysis in +// CLion/AppCode 2017.2.x and former, because __COUNTER__ is not properly +// handled by it. +// Otherwise all supported compilers support COUNTER macro, +// but user still might want to turn it off +#if ( !defined(__JETBRAINS_IDE__) || __JETBRAINS_IDE__ >= 20170300L ) + #define CATCH_INTERNAL_CONFIG_COUNTER +#endif + +//////////////////////////////////////////////////////////////////////////////// + +// RTX is a special version of Windows that is real time. +// This means that it is detected as Windows, but does not provide +// the same set of capabilities as real Windows does. +#if defined(UNDER_RTSS) || defined(RTX64_BUILD) + #define CATCH_INTERNAL_CONFIG_NO_WINDOWS_SEH + #define CATCH_INTERNAL_CONFIG_NO_ASYNC + #define CATCH_CONFIG_COLOUR_NONE +#endif + +#if !defined(_GLIBCXX_USE_C99_MATH_TR1) +#define CATCH_INTERNAL_CONFIG_GLOBAL_NEXTAFTER +#endif + +// Various stdlib support checks that require __has_include +#if defined(__has_include) + // Check if string_view is available and usable + #if __has_include() && defined(CATCH_CPP17_OR_GREATER) + # define CATCH_INTERNAL_CONFIG_CPP17_STRING_VIEW + #endif + + // Check if optional is available and usable + # if __has_include() && defined(CATCH_CPP17_OR_GREATER) + # define CATCH_INTERNAL_CONFIG_CPP17_OPTIONAL + # endif // __has_include() && defined(CATCH_CPP17_OR_GREATER) + + // Check if byte is available and usable + # if __has_include() && defined(CATCH_CPP17_OR_GREATER) + # include + # if defined(__cpp_lib_byte) && (__cpp_lib_byte > 0) + # define CATCH_INTERNAL_CONFIG_CPP17_BYTE + # endif + # endif // __has_include() && defined(CATCH_CPP17_OR_GREATER) + + // Check if variant is available and usable + # if __has_include() && defined(CATCH_CPP17_OR_GREATER) + # if defined(__clang__) && (__clang_major__ < 8) + // work around clang bug with libstdc++ https://bugs.llvm.org/show_bug.cgi?id=31852 + // fix should be in clang 8, workaround in libstdc++ 8.2 + # include + # if defined(__GLIBCXX__) && defined(_GLIBCXX_RELEASE) && (_GLIBCXX_RELEASE < 9) + # define CATCH_CONFIG_NO_CPP17_VARIANT + # else + # define CATCH_INTERNAL_CONFIG_CPP17_VARIANT + # endif // defined(__GLIBCXX__) && defined(_GLIBCXX_RELEASE) && (_GLIBCXX_RELEASE < 9) + # else + # define CATCH_INTERNAL_CONFIG_CPP17_VARIANT + # endif // defined(__clang__) && (__clang_major__ < 8) + # endif // __has_include() && defined(CATCH_CPP17_OR_GREATER) +#endif // defined(__has_include) + +#if defined(CATCH_INTERNAL_CONFIG_COUNTER) && !defined(CATCH_CONFIG_NO_COUNTER) && !defined(CATCH_CONFIG_COUNTER) +# define CATCH_CONFIG_COUNTER +#endif +#if defined(CATCH_INTERNAL_CONFIG_WINDOWS_SEH) && !defined(CATCH_CONFIG_NO_WINDOWS_SEH) && !defined(CATCH_CONFIG_WINDOWS_SEH) && !defined(CATCH_INTERNAL_CONFIG_NO_WINDOWS_SEH) +# define CATCH_CONFIG_WINDOWS_SEH +#endif +// This is set by default, because we assume that unix compilers are posix-signal-compatible by default. +#if defined(CATCH_INTERNAL_CONFIG_POSIX_SIGNALS) && !defined(CATCH_INTERNAL_CONFIG_NO_POSIX_SIGNALS) && !defined(CATCH_CONFIG_NO_POSIX_SIGNALS) && !defined(CATCH_CONFIG_POSIX_SIGNALS) +# define CATCH_CONFIG_POSIX_SIGNALS +#endif +// This is set by default, because we assume that compilers with no wchar_t support are just rare exceptions. +#if !defined(CATCH_INTERNAL_CONFIG_NO_WCHAR) && !defined(CATCH_CONFIG_NO_WCHAR) && !defined(CATCH_CONFIG_WCHAR) +# define CATCH_CONFIG_WCHAR +#endif + +#if !defined(CATCH_INTERNAL_CONFIG_NO_CPP11_TO_STRING) && !defined(CATCH_CONFIG_NO_CPP11_TO_STRING) && !defined(CATCH_CONFIG_CPP11_TO_STRING) +# define CATCH_CONFIG_CPP11_TO_STRING +#endif + +#if defined(CATCH_INTERNAL_CONFIG_CPP17_OPTIONAL) && !defined(CATCH_CONFIG_NO_CPP17_OPTIONAL) && !defined(CATCH_CONFIG_CPP17_OPTIONAL) +# define CATCH_CONFIG_CPP17_OPTIONAL +#endif + +#if defined(CATCH_INTERNAL_CONFIG_CPP17_STRING_VIEW) && !defined(CATCH_CONFIG_NO_CPP17_STRING_VIEW) && !defined(CATCH_CONFIG_CPP17_STRING_VIEW) +# define CATCH_CONFIG_CPP17_STRING_VIEW +#endif + +#if defined(CATCH_INTERNAL_CONFIG_CPP17_VARIANT) && !defined(CATCH_CONFIG_NO_CPP17_VARIANT) && !defined(CATCH_CONFIG_CPP17_VARIANT) +# define CATCH_CONFIG_CPP17_VARIANT +#endif + +#if defined(CATCH_INTERNAL_CONFIG_CPP17_BYTE) && !defined(CATCH_CONFIG_NO_CPP17_BYTE) && !defined(CATCH_CONFIG_CPP17_BYTE) +# define CATCH_CONFIG_CPP17_BYTE +#endif + +#if defined(CATCH_CONFIG_EXPERIMENTAL_REDIRECT) +# define CATCH_INTERNAL_CONFIG_NEW_CAPTURE +#endif + +#if defined(CATCH_INTERNAL_CONFIG_NEW_CAPTURE) && !defined(CATCH_INTERNAL_CONFIG_NO_NEW_CAPTURE) && !defined(CATCH_CONFIG_NO_NEW_CAPTURE) && !defined(CATCH_CONFIG_NEW_CAPTURE) +# define CATCH_CONFIG_NEW_CAPTURE +#endif + +#if !defined(CATCH_INTERNAL_CONFIG_EXCEPTIONS_ENABLED) && !defined(CATCH_CONFIG_DISABLE_EXCEPTIONS) +# define CATCH_CONFIG_DISABLE_EXCEPTIONS +#endif + +#if defined(CATCH_INTERNAL_CONFIG_POLYFILL_ISNAN) && !defined(CATCH_CONFIG_NO_POLYFILL_ISNAN) && !defined(CATCH_CONFIG_POLYFILL_ISNAN) +# define CATCH_CONFIG_POLYFILL_ISNAN +#endif + +#if defined(CATCH_INTERNAL_CONFIG_USE_ASYNC) && !defined(CATCH_INTERNAL_CONFIG_NO_ASYNC) && !defined(CATCH_CONFIG_NO_USE_ASYNC) && !defined(CATCH_CONFIG_USE_ASYNC) +# define CATCH_CONFIG_USE_ASYNC +#endif + +#if defined(CATCH_INTERNAL_CONFIG_ANDROID_LOGWRITE) && !defined(CATCH_CONFIG_NO_ANDROID_LOGWRITE) && !defined(CATCH_CONFIG_ANDROID_LOGWRITE) +# define CATCH_CONFIG_ANDROID_LOGWRITE +#endif + +#if defined(CATCH_INTERNAL_CONFIG_GLOBAL_NEXTAFTER) && !defined(CATCH_CONFIG_NO_GLOBAL_NEXTAFTER) && !defined(CATCH_CONFIG_GLOBAL_NEXTAFTER) +# define CATCH_CONFIG_GLOBAL_NEXTAFTER +#endif + +// Even if we do not think the compiler has that warning, we still have +// to provide a macro that can be used by the code. +#if !defined(CATCH_INTERNAL_START_WARNINGS_SUPPRESSION) +# define CATCH_INTERNAL_START_WARNINGS_SUPPRESSION +#endif +#if !defined(CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION) +# define CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION +#endif +#if !defined(CATCH_INTERNAL_SUPPRESS_PARENTHESES_WARNINGS) +# define CATCH_INTERNAL_SUPPRESS_PARENTHESES_WARNINGS +#endif +#if !defined(CATCH_INTERNAL_SUPPRESS_GLOBALS_WARNINGS) +# define CATCH_INTERNAL_SUPPRESS_GLOBALS_WARNINGS +#endif +#if !defined(CATCH_INTERNAL_SUPPRESS_UNUSED_WARNINGS) +# define CATCH_INTERNAL_SUPPRESS_UNUSED_WARNINGS +#endif +#if !defined(CATCH_INTERNAL_SUPPRESS_ZERO_VARIADIC_WARNINGS) +# define CATCH_INTERNAL_SUPPRESS_ZERO_VARIADIC_WARNINGS +#endif + +// The goal of this macro is to avoid evaluation of the arguments, but +// still have the compiler warn on problems inside... +#if !defined(CATCH_INTERNAL_IGNORE_BUT_WARN) +# define CATCH_INTERNAL_IGNORE_BUT_WARN(...) +#endif + +#if defined(__APPLE__) && defined(__apple_build_version__) && (__clang_major__ < 10) +# undef CATCH_INTERNAL_SUPPRESS_UNUSED_TEMPLATE_WARNINGS +#elif defined(__clang__) && (__clang_major__ < 5) +# undef CATCH_INTERNAL_SUPPRESS_UNUSED_TEMPLATE_WARNINGS +#endif + +#if !defined(CATCH_INTERNAL_SUPPRESS_UNUSED_TEMPLATE_WARNINGS) +# define CATCH_INTERNAL_SUPPRESS_UNUSED_TEMPLATE_WARNINGS +#endif + +#if defined(CATCH_CONFIG_DISABLE_EXCEPTIONS) +#define CATCH_TRY if ((true)) +#define CATCH_CATCH_ALL if ((false)) +#define CATCH_CATCH_ANON(type) if ((false)) +#else +#define CATCH_TRY try +#define CATCH_CATCH_ALL catch (...) +#define CATCH_CATCH_ANON(type) catch (type) +#endif + +#if defined(CATCH_INTERNAL_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR) && !defined(CATCH_CONFIG_NO_TRADITIONAL_MSVC_PREPROCESSOR) && !defined(CATCH_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR) +#define CATCH_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR +#endif + +// end catch_compiler_capabilities.h +#define INTERNAL_CATCH_UNIQUE_NAME_LINE2( name, line ) name##line +#define INTERNAL_CATCH_UNIQUE_NAME_LINE( name, line ) INTERNAL_CATCH_UNIQUE_NAME_LINE2( name, line ) +#ifdef CATCH_CONFIG_COUNTER +# define INTERNAL_CATCH_UNIQUE_NAME( name ) INTERNAL_CATCH_UNIQUE_NAME_LINE( name, __COUNTER__ ) +#else +# define INTERNAL_CATCH_UNIQUE_NAME( name ) INTERNAL_CATCH_UNIQUE_NAME_LINE( name, __LINE__ ) +#endif + +#include +#include +#include + +// We need a dummy global operator<< so we can bring it into Catch namespace later +struct Catch_global_namespace_dummy {}; +std::ostream& operator<<(std::ostream&, Catch_global_namespace_dummy); + +namespace Catch { + + struct CaseSensitive { enum Choice { + Yes, + No + }; }; + + class NonCopyable { + NonCopyable( NonCopyable const& ) = delete; + NonCopyable( NonCopyable && ) = delete; + NonCopyable& operator = ( NonCopyable const& ) = delete; + NonCopyable& operator = ( NonCopyable && ) = delete; + + protected: + NonCopyable(); + virtual ~NonCopyable(); + }; + + struct SourceLineInfo { + + SourceLineInfo() = delete; + SourceLineInfo( char const* _file, std::size_t _line ) noexcept + : file( _file ), + line( _line ) + {} + + SourceLineInfo( SourceLineInfo const& other ) = default; + SourceLineInfo& operator = ( SourceLineInfo const& ) = default; + SourceLineInfo( SourceLineInfo&& ) noexcept = default; + SourceLineInfo& operator = ( SourceLineInfo&& ) noexcept = default; + + bool empty() const noexcept { return file[0] == '\0'; } + bool operator == ( SourceLineInfo const& other ) const noexcept; + bool operator < ( SourceLineInfo const& other ) const noexcept; + + char const* file; + std::size_t line; + }; + + std::ostream& operator << ( std::ostream& os, SourceLineInfo const& info ); + + // Bring in operator<< from global namespace into Catch namespace + // This is necessary because the overload of operator<< above makes + // lookup stop at namespace Catch + using ::operator<<; + + // Use this in variadic streaming macros to allow + // >> +StreamEndStop + // as well as + // >> stuff +StreamEndStop + struct StreamEndStop { + std::string operator+() const; + }; + template + T const& operator + ( T const& value, StreamEndStop ) { + return value; + } +} + +#define CATCH_INTERNAL_LINEINFO \ + ::Catch::SourceLineInfo( __FILE__, static_cast( __LINE__ ) ) + +// end catch_common.h +namespace Catch { + + struct RegistrarForTagAliases { + RegistrarForTagAliases( char const* alias, char const* tag, SourceLineInfo const& lineInfo ); + }; + +} // end namespace Catch + +#define CATCH_REGISTER_TAG_ALIAS( alias, spec ) \ + CATCH_INTERNAL_START_WARNINGS_SUPPRESSION \ + CATCH_INTERNAL_SUPPRESS_GLOBALS_WARNINGS \ + namespace{ Catch::RegistrarForTagAliases INTERNAL_CATCH_UNIQUE_NAME( AutoRegisterTagAlias )( alias, spec, CATCH_INTERNAL_LINEINFO ); } \ + CATCH_INTERNAL_STOP_WARNINGS_SUPPRESSION + +// end catch_tag_alias_autoregistrar.h +// start catch_test_registry.h + +// start catch_interfaces_testcase.h + +#include + +namespace Catch { + + class TestSpec; + + struct ITestInvoker { + virtual void invoke () const = 0; + virtual ~ITestInvoker(); + }; + + class TestCase; + struct IConfig; + + struct ITestCaseRegistry { + virtual ~ITestCaseRegistry(); + virtual std::vector const& getAllTests() const = 0; + virtual std::vector const& getAllTestsSorted( IConfig const& config ) const = 0; + }; + + bool isThrowSafe( TestCase const& testCase, IConfig const& config ); + bool matchTest( TestCase const& testCase, TestSpec const& testSpec, IConfig const& config ); + std::vector filterTests( std::vector const& testCases, TestSpec const& testSpec, IConfig const& config ); + std::vector const& getAllTestCasesSorted( IConfig const& config ); + +} + +// end catch_interfaces_testcase.h +// start catch_stringref.h + +#include +#include +#include +#include + +namespace Catch { + + /// A non-owning string class (similar to the forthcoming std::string_view) + /// Note that, because a StringRef may be a substring of another string, + /// it may not be null terminated. + class StringRef { + public: + using size_type = std::size_t; + using const_iterator = const char*; + + private: + static constexpr char const* const s_empty = ""; + + char const* m_start = s_empty; + size_type m_size = 0; + + public: // construction + constexpr StringRef() noexcept = default; + + StringRef( char const* rawChars ) noexcept; + + constexpr StringRef( char const* rawChars, size_type size ) noexcept + : m_start( rawChars ), + m_size( size ) + {} + + StringRef( std::string const& stdString ) noexcept + : m_start( stdString.c_str() ), + m_size( stdString.size() ) + {} + + explicit operator std::string() const { + return std::string(m_start, m_size); + } + + public: // operators + auto operator == ( StringRef const& other ) const noexcept -> bool; + auto operator != (StringRef const& other) const noexcept -> bool { + return !(*this == other); + } + + auto operator[] ( size_type index ) const noexcept -> char { + assert(index < m_size); + return m_start[index]; + } + + public: // named queries + constexpr auto empty() const noexcept -> bool { + return m_size == 0; + } + constexpr auto size() const noexcept -> size_type { + return m_size; + } + + // Returns the current start pointer. If the StringRef is not + // null-terminated, throws std::domain_exception + auto c_str() const -> char const*; + + public: // substrings and searches + // Returns a substring of [start, start + length). + // If start + length > size(), then the substring is [start, size()). + // If start > size(), then the substring is empty. + auto substr( size_type start, size_type length ) const noexcept -> StringRef; + + // Returns the current start pointer. May not be null-terminated. + auto data() const noexcept -> char const*; + + constexpr auto isNullTerminated() const noexcept -> bool { + return m_start[m_size] == '\0'; + } + + public: // iterators + constexpr const_iterator begin() const { return m_start; } + constexpr const_iterator end() const { return m_start + m_size; } + }; + + auto operator += ( std::string& lhs, StringRef const& sr ) -> std::string&; + auto operator << ( std::ostream& os, StringRef const& sr ) -> std::ostream&; + + constexpr auto operator "" _sr( char const* rawChars, std::size_t size ) noexcept -> StringRef { + return StringRef( rawChars, size ); + } +} // namespace Catch + +constexpr auto operator "" _catch_sr( char const* rawChars, std::size_t size ) noexcept -> Catch::StringRef { + return Catch::StringRef( rawChars, size ); +} + +// end catch_stringref.h +// start catch_preprocessor.hpp + + +#define CATCH_RECURSION_LEVEL0(...) __VA_ARGS__ +#define CATCH_RECURSION_LEVEL1(...) CATCH_RECURSION_LEVEL0(CATCH_RECURSION_LEVEL0(CATCH_RECURSION_LEVEL0(__VA_ARGS__))) +#define CATCH_RECURSION_LEVEL2(...) CATCH_RECURSION_LEVEL1(CATCH_RECURSION_LEVEL1(CATCH_RECURSION_LEVEL1(__VA_ARGS__))) +#define CATCH_RECURSION_LEVEL3(...) CATCH_RECURSION_LEVEL2(CATCH_RECURSION_LEVEL2(CATCH_RECURSION_LEVEL2(__VA_ARGS__))) +#define CATCH_RECURSION_LEVEL4(...) CATCH_RECURSION_LEVEL3(CATCH_RECURSION_LEVEL3(CATCH_RECURSION_LEVEL3(__VA_ARGS__))) +#define CATCH_RECURSION_LEVEL5(...) CATCH_RECURSION_LEVEL4(CATCH_RECURSION_LEVEL4(CATCH_RECURSION_LEVEL4(__VA_ARGS__))) + +#ifdef CATCH_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR +#define INTERNAL_CATCH_EXPAND_VARGS(...) __VA_ARGS__ +// MSVC needs more evaluations +#define CATCH_RECURSION_LEVEL6(...) CATCH_RECURSION_LEVEL5(CATCH_RECURSION_LEVEL5(CATCH_RECURSION_LEVEL5(__VA_ARGS__))) +#define CATCH_RECURSE(...) CATCH_RECURSION_LEVEL6(CATCH_RECURSION_LEVEL6(__VA_ARGS__)) +#else +#define CATCH_RECURSE(...) CATCH_RECURSION_LEVEL5(__VA_ARGS__) +#endif + +#define CATCH_REC_END(...) +#define CATCH_REC_OUT + +#define CATCH_EMPTY() +#define CATCH_DEFER(id) id CATCH_EMPTY() + +#define CATCH_REC_GET_END2() 0, CATCH_REC_END +#define CATCH_REC_GET_END1(...) CATCH_REC_GET_END2 +#define CATCH_REC_GET_END(...) CATCH_REC_GET_END1 +#define CATCH_REC_NEXT0(test, next, ...) next CATCH_REC_OUT +#define CATCH_REC_NEXT1(test, next) CATCH_DEFER ( CATCH_REC_NEXT0 ) ( test, next, 0) +#define CATCH_REC_NEXT(test, next) CATCH_REC_NEXT1(CATCH_REC_GET_END test, next) + +#define CATCH_REC_LIST0(f, x, peek, ...) , f(x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST1) ) ( f, peek, __VA_ARGS__ ) +#define CATCH_REC_LIST1(f, x, peek, ...) , f(x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST0) ) ( f, peek, __VA_ARGS__ ) +#define CATCH_REC_LIST2(f, x, peek, ...) f(x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST1) ) ( f, peek, __VA_ARGS__ ) + +#define CATCH_REC_LIST0_UD(f, userdata, x, peek, ...) , f(userdata, x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST1_UD) ) ( f, userdata, peek, __VA_ARGS__ ) +#define CATCH_REC_LIST1_UD(f, userdata, x, peek, ...) , f(userdata, x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST0_UD) ) ( f, userdata, peek, __VA_ARGS__ ) +#define CATCH_REC_LIST2_UD(f, userdata, x, peek, ...) f(userdata, x) CATCH_DEFER ( CATCH_REC_NEXT(peek, CATCH_REC_LIST1_UD) ) ( f, userdata, peek, __VA_ARGS__ ) + +// Applies the function macro `f` to each of the remaining parameters, inserts commas between the results, +// and passes userdata as the first parameter to each invocation, +// e.g. CATCH_REC_LIST_UD(f, x, a, b, c) evaluates to f(x, a), f(x, b), f(x, c) +#define CATCH_REC_LIST_UD(f, userdata, ...) CATCH_RECURSE(CATCH_REC_LIST2_UD(f, userdata, __VA_ARGS__, ()()(), ()()(), ()()(), 0)) + +#define CATCH_REC_LIST(f, ...) CATCH_RECURSE(CATCH_REC_LIST2(f, __VA_ARGS__, ()()(), ()()(), ()()(), 0)) + +#define INTERNAL_CATCH_EXPAND1(param) INTERNAL_CATCH_EXPAND2(param) +#define INTERNAL_CATCH_EXPAND2(...) INTERNAL_CATCH_NO## __VA_ARGS__ +#define INTERNAL_CATCH_DEF(...) INTERNAL_CATCH_DEF __VA_ARGS__ +#define INTERNAL_CATCH_NOINTERNAL_CATCH_DEF +#define INTERNAL_CATCH_STRINGIZE(...) INTERNAL_CATCH_STRINGIZE2(__VA_ARGS__) +#ifndef CATCH_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR +#define INTERNAL_CATCH_STRINGIZE2(...) #__VA_ARGS__ +#define INTERNAL_CATCH_STRINGIZE_WITHOUT_PARENS(param) INTERNAL_CATCH_STRINGIZE(INTERNAL_CATCH_REMOVE_PARENS(param)) +#else +// MSVC is adding extra space and needs another indirection to expand INTERNAL_CATCH_NOINTERNAL_CATCH_DEF +#define INTERNAL_CATCH_STRINGIZE2(...) INTERNAL_CATCH_STRINGIZE3(__VA_ARGS__) +#define INTERNAL_CATCH_STRINGIZE3(...) #__VA_ARGS__ +#define INTERNAL_CATCH_STRINGIZE_WITHOUT_PARENS(param) (INTERNAL_CATCH_STRINGIZE(INTERNAL_CATCH_REMOVE_PARENS(param)) + 1) +#endif + +#define INTERNAL_CATCH_MAKE_NAMESPACE2(...) ns_##__VA_ARGS__ +#define INTERNAL_CATCH_MAKE_NAMESPACE(name) INTERNAL_CATCH_MAKE_NAMESPACE2(name) + +#define INTERNAL_CATCH_REMOVE_PARENS(...) INTERNAL_CATCH_EXPAND1(INTERNAL_CATCH_DEF __VA_ARGS__) + +#ifndef CATCH_CONFIG_TRADITIONAL_MSVC_PREPROCESSOR +#define INTERNAL_CATCH_MAKE_TYPE_LIST2(...) decltype(get_wrapper()) +#define INTERNAL_CATCH_MAKE_TYPE_LIST(...) INTERNAL_CATCH_MAKE_TYPE_LIST2(INTERNAL_CATCH_REMOVE_PARENS(__VA_ARGS__)) +#else +#define INTERNAL_CATCH_MAKE_TYPE_LIST2(...) INTERNAL_CATCH_EXPAND_VARGS(decltype(get_wrapper())) +#define INTERNAL_CATCH_MAKE_TYPE_LIST(...) INTERNAL_CATCH_EXPAND_VARGS(INTERNAL_CATCH_MAKE_TYPE_LIST2(INTERNAL_CATCH_REMOVE_PARENS(__VA_ARGS__))) +#endif + +#define INTERNAL_CATCH_MAKE_TYPE_LISTS_FROM_TYPES(...)\ + CATCH_REC_LIST(INTERNAL_CATCH_MAKE_TYPE_LIST,__VA_ARGS__) + +#define INTERNAL_CATCH_REMOVE_PARENS_1_ARG(_0) INTERNAL_CATCH_REMOVE_PARENS(_0) +#define INTERNAL_CATCH_REMOVE_PARENS_2_ARG(_0, _1) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_1_ARG(_1) +#define INTERNAL_CATCH_REMOVE_PARENS_3_ARG(_0, _1, _2) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_2_ARG(_1, _2) +#define INTERNAL_CATCH_REMOVE_PARENS_4_ARG(_0, _1, _2, _3) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_3_ARG(_1, _2, _3) +#define INTERNAL_CATCH_REMOVE_PARENS_5_ARG(_0, _1, _2, _3, _4) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_4_ARG(_1, _2, _3, _4) +#define INTERNAL_CATCH_REMOVE_PARENS_6_ARG(_0, _1, _2, _3, _4, _5) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_5_ARG(_1, _2, _3, _4, _5) +#define INTERNAL_CATCH_REMOVE_PARENS_7_ARG(_0, _1, _2, _3, _4, _5, _6) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_6_ARG(_1, _2, _3, _4, _5, _6) +#define INTERNAL_CATCH_REMOVE_PARENS_8_ARG(_0, _1, _2, _3, _4, _5, _6, _7) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_7_ARG(_1, _2, _3, _4, _5, _6, _7) +#define INTERNAL_CATCH_REMOVE_PARENS_9_ARG(_0, _1, _2, _3, _4, _5, _6, _7, _8) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_8_ARG(_1, _2, _3, _4, _5, _6, _7, _8) +#define INTERNAL_CATCH_REMOVE_PARENS_10_ARG(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_9_ARG(_1, _2, _3, _4, _5, _6, _7, _8, _9) +#define INTERNAL_CATCH_REMOVE_PARENS_11_ARG(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10) INTERNAL_CATCH_REMOVE_PARENS(_0), INTERNAL_CATCH_REMOVE_PARENS_10_ARG(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10) + +#define INTERNAL_CATCH_VA_NARGS_IMPL(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, N, ...) N + +#define INTERNAL_CATCH_TYPE_GEN\ + template struct TypeList {};\ + template\ + constexpr auto get_wrapper() noexcept -> TypeList { return {}; }\ + template class...> struct TemplateTypeList{};\ + template class...Cs>\ + constexpr auto get_wrapper() noexcept -> TemplateTypeList { return {}; }\ + template\ + struct append;\ + template\ + struct rewrap;\ + template class, typename...>\ + struct create;\ + template class, typename>\ + struct convert;\ + \ + template \ + struct append { using type = T; };\ + template< template class L1, typename...E1, template class L2, typename...E2, typename...Rest>\ + struct append, L2, Rest...> { using type = typename append, Rest...>::type; };\ + template< template class L1, typename...E1, typename...Rest>\ + struct append, TypeList, Rest...> { using type = L1; };\ + \ + template< template class Container, template class List, typename...elems>\ + struct rewrap, List> { using type = TypeList>; };\ + template< template class Container, template class List, class...Elems, typename...Elements>\ + struct rewrap, List, Elements...> { using type = typename append>, typename rewrap, Elements...>::type>::type; };\ + \ + template