Index: uspace/lib/cpp/Makefile =================================================================== --- uspace/lib/cpp/Makefile (revision fc151209d08902a2b7441325eb2ead039cd1da62) +++ uspace/lib/cpp/Makefile (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -53,22 +53,22 @@ src/typeindex.cpp \ src/typeinfo.cpp \ - src/internal/runtime.cpp \ - src/internal/trycatch.cpp \ - src/internal/unwind.cpp \ - src/internal/test/adaptors.cpp \ - src/internal/test/array.cpp \ - src/internal/test/bitset.cpp \ - src/internal/test/deque.cpp \ - src/internal/test/map.cpp \ - src/internal/test/memory.cpp \ - src/internal/test/mock.cpp \ - src/internal/test/numeric.cpp \ - src/internal/test/set.cpp \ - src/internal/test/string.cpp \ - src/internal/test/test.cpp \ - src/internal/test/tuple.cpp \ - src/internal/test/unordered_map.cpp \ - src/internal/test/unordered_set.cpp \ - src/internal/test/vector.cpp + src/__bits/runtime.cpp \ + src/__bits/trycatch.cpp \ + src/__bits/unwind.cpp \ + src/__bits/test/adaptors.cpp \ + src/__bits/test/array.cpp \ + src/__bits/test/bitset.cpp \ + src/__bits/test/deque.cpp \ + src/__bits/test/map.cpp \ + src/__bits/test/memory.cpp \ + src/__bits/test/mock.cpp \ + src/__bits/test/numeric.cpp \ + src/__bits/test/set.cpp \ + src/__bits/test/string.cpp \ + src/__bits/test/test.cpp \ + src/__bits/test/tuple.cpp \ + src/__bits/test/unordered_map.cpp \ + src/__bits/test/unordered_set.cpp \ + src/__bits/test/vector.cpp include $(USPACE_PREFIX)/Makefile.common Index: uspace/lib/cpp/include/__bits/abi.hpp =================================================================== --- uspace/lib/cpp/include/__bits/abi.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/abi.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,159 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +namespace __cxxabiv1 +{ + /** + * Static constructor/destructor helpers. + */ + + extern "C" int __cxa_atexit(void (*)(void*), void*, void*); + + extern "C" void __cxa_finalize(void*); + + /** + * Itanium C++ ABI type infos. + * See section 2.9.4 (RTTI Layout) of the Itanium C++ ABI spec. + * + * Note: The memory representation of these classes must not + * be modified! (Wel, no modifications at all shall be done.) + * + * Source: https://itanium-cxx-abi.github.io/cxx-abi/abi.html + */ + + class __fundamental_type_info: public std::type_info + { + public: + virtual ~__fundamental_type_info(); + }; + + class __array_type_info: public std::type_info + { + public: + virtual ~__array_type_info(); + }; + + class __function_type_info: public std::type_info + { + public: + virtual ~__function_type_info(); + }; + + class __enum_type_info: public std::type_info + { + public: + virtual ~__enum_type_info(); + }; + + class __class_type_info: public std::type_info + { + public: + virtual ~__class_type_info(); + }; + + class __si_class_type_info: public __class_type_info + { + public: + virtual ~__si_class_type_info(); + + const __class_type_info* __base_type; + }; + + struct __base_class_type_info + { + const __class_type_info* __base_type; + long __offset_flags; + + enum __ofset_flags_masks + { + __virtual_mask = 0x1, + __public_mask = 0x2, + __offset_shift = 0x8 + }; + }; + + class __vmi_class_type_info: public __class_type_info + { + public: + virtual ~__vmi_class_type_info(); + + std::uint32_t __flags; + std::uint32_t __base_count; + + __base_class_type_info __base_info[1]; + + enum __flags_mask + { + __non_diamond_repeat_mask = 0x1, + __diamond_shaped_mask = 0x2 + }; + }; + + class __pbase_type_info: public std::type_info + { + public: + virtual ~__pbase_type_info(); + + std::uint32_t __flags; + const std::type_info* __pointee; + + enum __masks + { + __const_mask = 0x01, + __volatile_mask = 0x02, + __restrict_mask = 0x04, + __incomplete_mask = 0x08, + __incomplete_class_mask = 0x10, + __transaction_safe_mask = 0x20, + __noexcept_mask = 0x40 + }; + }; + + class __pointer_type_info: public __pbase_type_info + { + public: + virtual ~__pointer_type_info(); + }; + + class __pointer_to_member_type_info: public __pbase_type_info + { + public: + virtual ~__pointer_to_member_type_info(); + + const __class_type_info* __context; + }; + + extern "C" void* __dynamic_cast(const void*, const __class_type_info*, + const __class_type_info*, std::ptrdiff_t); +} + +namespace abi = __cxxabiv1; Index: uspace/lib/cpp/include/__bits/aux.hpp =================================================================== --- uspace/lib/cpp/include/__bits/aux.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/aux.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_AUX +#define LIBCPP_AUX + +namespace std +{ + /** + * 20.10.3, helper class: + */ + + template + struct integral_constant + { + static constexpr T value = v; + + using value_type = T; + using type = integral_constant; + + constexpr operator value_type() const noexcept + { + return value; + } + + constexpr value_type operator()() const noexcept + { + return value; + } + }; + + using true_type = integral_constant; + using false_type = integral_constant; +} + +namespace std::aux +{ + /** + * Two very handy templates, this allows us + * to easily follow the T::type and T::value + * convention by simply inheriting from specific + * instantiations of these templates. + * Examples: + * 1) We need a struct with int typedef'd to type: + * + * stuct has_type_int: aux::type {}; + * typename has_type_int::type x = 1; // x is of type int + * + * 2) We need a struct with static size_t member called value: + * + * struct has_value_size_t: aux::value {}; + * std::printf("%u\n", has_value_size_t::value); // prints "1\n" + */ + + template + struct type_is + { + using type = T; + }; + + // For compatibility with integral_constant. + template + using value_is = std::integral_constant; +} + +#endif Index: uspace/lib/cpp/include/__bits/builtins.hpp =================================================================== --- uspace/lib/cpp/include/__bits/builtins.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/builtins.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,87 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_BUILTINS +#define LIBCPP_BITS_BUILTINS + +/** + * Note: While the primary target of libcpp is the + * g++ compiler, using builtin functions that would + * unnecessarily limit the library to any specific + * compiler is discouraged and as such all the used + * builtins should be available atleast in g++ and + * clang++. + * GCC: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html + * LLVM: https://github.com/llvm-mirror/clang/blob/master/include/clang/Basic/Builtins.def + * (If anyone has a better link for LLVM, feel free to update it.) + */ + +#include + +namespace std::aux +{ + template + constexpr double log2(T val) + { + return __builtin_log2(static_cast(val)); + } + + template + constexpr double pow2(T exp) + { + return __builtin_pow(2.0, static_cast(exp)); + } + + template + constexpr size_t pow2u(T exp) + { + return static_cast(pow2(exp)); + } + + template + constexpr T pow(T base, U exp) + { + return static_cast( + __builtin_pow(static_cast(base), static_cast(exp)) + ); + } + + template + constexpr size_t ceil(T val) + { + return static_cast(__builtin_ceil(static_cast(val))); + } + + template + constexpr size_t floor(T val) + { + return static_cast(__builtin_floor(static_cast(val))); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/common.hpp =================================================================== --- uspace/lib/cpp/include/__bits/common.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/common.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,13 @@ +#ifndef LIBCPP_BITS_COMMON +#define LIBCPP_BITS_COMMON + +/** + * According to section 17.2 of the standard, + * the restrict qualifier shall be omitted. + */ +#define restrict + +#undef NULL +#define NULL nullptr + +#endif Index: uspace/lib/cpp/include/__bits/functional/arithmetic_operations.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/arithmetic_operations.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/arithmetic_operations.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,621 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_ARITHMETIC_OPERATIONS +#define LIBCPP_BITS_FUNCTIONAL_ARITHMETIC_OPERATIONS + +#include <__bits/utility/forward_move.hpp> +#include + +namespace std +{ + /** + * 20.9.5, arithmetic operations: + */ + + template + struct plus + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs + rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct minus + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs - rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct multiplies + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs * rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct divides + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs / rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct modulus + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs % rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct negate + { + constexpr T operator()(const T& x) const + { + return -x; + } + + using argument_type = T; + using result_type = T; + }; + + namespace aux + { + /** + * Used by some functions like std::set::find to determine + * whether a functor is transparent. + */ + struct transparent_t; + + template + struct is_transparent: false_type + { /* DUMMY BODY */ }; + + template + struct is_transparent> + : true_type + { /* DUMMY BODY */ }; + + template + inline constexpr bool is_transparent_v = is_transparent::value; + } + + template<> + struct plus + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) + forward(rhs)) + { + return forward(lhs) + forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct minus + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) - forward(rhs)) + { + return forward(lhs) - forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct multiplies + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) * forward(rhs)) + { + return forward(lhs) * forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct divides + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) / forward(rhs)) + { + return forward(lhs) / forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct modulus + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) % forward(rhs)) + { + return forward(lhs) % forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct negate + { + template + constexpr auto operator()(T&& x) const + -> decltype(-forward(x)) + { + return -forward(x); + } + + using is_transparent = aux::transparent_t; + }; + + /** + * 20.9.6, comparisons: + */ + + template + struct equal_to + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs == rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct not_equal_to + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs != rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct greater + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs > rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct less + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs < rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct greater_equal + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs >= rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct less_equal + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs <= rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template<> + struct equal_to + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) == forward(rhs)) + { + return forward(lhs) == forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct not_equal_to + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) != forward(rhs)) + { + return forward(lhs) != forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct greater + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) > forward(rhs)) + { + return forward(lhs) > forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct less + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) < forward(rhs)) + { + return forward(lhs) < forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct greater_equal + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) >= forward(rhs)) + { + return forward(lhs) >= forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct less_equal + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) <= forward(rhs)) + { + return forward(lhs) <= forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + /** + * 20.9.7, logical operations: + */ + + template + struct logical_and + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs && rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct logical_or + { + constexpr bool operator()(const T& lhs, const T& rhs) const + { + return lhs || rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = bool; + }; + + template + struct logical_not + { + constexpr bool operator()(const T& x) const + { + return !x; + } + + using argument_type = T; + using result_type = bool; + }; + + template<> + struct logical_and + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) && forward(rhs)) + { + return forward(lhs) && forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct logical_or + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) || forward(rhs)) + { + return forward(lhs) || forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct logical_not + { + template + constexpr auto operator()(T&& x) const + -> decltype(!forward(x)) + { + return !forward(x); + } + + using is_transparent = aux::transparent_t; + }; + + /** + * 20.9.8, bitwise operations: + */ + + template + struct bit_and + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs & rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct bit_or + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs | rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct bit_xor + { + constexpr T operator()(const T& lhs, const T& rhs) const + { + return lhs ^ rhs; + } + + using first_argument_type = T; + using second_argument_type = T; + using result_type = T; + }; + + template + struct bit_not + { + constexpr bool operator()(const T& x) const + { + return ~x; + } + + using argument_type = T; + using result_type = T; + }; + + template<> + struct bit_and + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) & forward(rhs)) + { + return forward(lhs) & forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct bit_or + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) | forward(rhs)) + { + return forward(lhs) | forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct bit_xor + { + template + constexpr auto operator()(T&& lhs, U&& rhs) const + -> decltype(forward(lhs) ^ forward(rhs)) + { + return forward(lhs) ^ forward(rhs); + } + + using is_transparent = aux::transparent_t; + }; + + template<> + struct bit_not + { + template + constexpr auto operator()(T&& x) const + -> decltype(~forward(x)) + { + return ~forward(x); + } + + using is_transparent = aux::transparent_t; + }; + + /** + * 20.9.9, negators: + */ + + template + class unary_negate + { + public: + using result_type = bool; + using argument_type = typename Predicate::argument_type; + + constexpr explicit unary_negate(const Predicate& pred) + : pred_{pred} + { /* DUMMY BODY */ } + + constexpr result_type operator()(const argument_type& arg) + { + return !pred_(arg); + } + + private: + Predicate pred_; + }; + + template + constexpr unary_negate not1(const Predicate& pred) + { + return unary_negate{pred}; + } + + template + class binary_negate + { + public: + using result_type = bool; + using first_argument_type = typename Predicate::first_argument_type; + using second_argument_type = typename Predicate::second_argument_type; + + constexpr explicit binary_negate(const Predicate& pred) + : pred_{pred} + { /* DUMMY BODY */ } + + constexpr result_type operator()(const first_argument_type& arg1, + const second_argument_type& arg2) + { + return !pred_(arg1, arg2); + } + + private: + Predicate pred_; + }; + + template + constexpr binary_negate not2(const Predicate& pred); +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/bind.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/bind.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/bind.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,240 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_BIND +#define LIBCPP_BITS_FUNCTIONAL_BIND + +#include <__bits/functional/function.hpp> +#include <__bits/functional/invoke.hpp> +#include <__bits/functional/reference_wrapper.hpp> +#include +#include +#include + +namespace std +{ + /** + * 20.9.10, bind: + */ + + namespace aux + { + template + struct placeholder_t + { + constexpr placeholder_t() = default; + constexpr placeholder_t(const placeholder_t&) = default; + constexpr placeholder_t(placeholder_t&&) = default; + }; + } + + template + struct is_placeholder: integral_constant + { /* DUMMY BODY */ }; + + template // Note: const because they are all constexpr. + struct is_placeholder> + : integral_constant + { /* DUMMY BODY */ }; + + template + inline constexpr int is_placeholder_v = is_placeholder::value; + + namespace aux + { + /** + * Note: Our internal bind return type has an extra type + * template parameter and an extra bool template parameter. + * We use this for the special version of bind that has + * the return type to have a result_type typedef + * (i.e. when the bool is true, the extra type parameter + * is typedefed as result_type - see the structure below). + * This is just a simplification of the implementation + * so that we don't need to have two return types for + * the two bind functions, because unlike function or + * mem_fn, we know exactly when to make the typedef. + */ + + template + struct bind_conditional_result_type + { /* DUMMY BODY */ }; + + template + struct bind_conditional_result_type + { + using result_type = R; + }; + + template + class bind_t; + + /** + * Filter class that uses its overloaded operator[] + * to filter our placeholders, reference_wrappers and bind + * subexpressions and replace them with the correct + * arguments (extracts references, calls the subexpressions etc). + */ + template + class bind_arg_filter + { + public: + bind_arg_filter(Args&&... args) + : args_{forward(args)...} + { /* DUMMY BODY */ } + + template + constexpr decltype(auto) operator[](T&& t) + { + return forward(t); + } + + template + constexpr decltype(auto) operator[](const placeholder_t) + { // Since placeholders are constexpr, this is the best match for them. + /** + * Come on, it's int! Why not use -1 as not placeholder + * and start them at 0? -.- + */ + return get(args_); + } + + template + constexpr T& operator[](reference_wrapper ref) + { + return ref.get(); + } + + template + constexpr decltype(auto) operator[](const bind_t b) + { + return b; // TODO: bind subexpressions + } + + + private: + tuple args_; + }; + + template + class bind_t: public bind_conditional_result_type + { + public: + template + constexpr bind_t(G&& g, BoundArgs&&... args) + : func_{forward(g)}, + bound_args_{forward(args)...} + { /* DUMMY BODY */ } + + constexpr bind_t(const bind_t& other) = default; + constexpr bind_t(bind_t&& other) = default; + + template + constexpr decltype(auto) operator()(ActualArgs&&... args) + { + return invoke_( + make_index_sequence{}, + forward(args)... + ); + } + + private: + function> func_; + tuple...> bound_args_; + + template + constexpr decltype(auto) invoke_( + index_sequence, ActualArgs&&... args + ) + { + /** + * The expression filter[bound_args_[bind_arg_index()]]... + * here expands bind_arg_index to 0, 1, ... sizeof...(ActualArgs) - 1 + * and then passes this variadic list of indices to the bound_args_ + * tuple which extracts the bound args from it. + * Our filter will then have its operator[] called on each of them + * and filter out the placeholders, reference_wrappers etc and changes + * them to the actual arguments. + */ + bind_arg_filter filter{forward(args)...}; + + return aux::invoke( + func_, + filter[get(bound_args_)]... + ); + } + }; + } + + template + struct is_bind_expression: false_type + { /* DUMMY BODY */ }; + + template + struct is_bind_expression> + : true_type + { /* DUMMY BODY */ }; + + template + aux::bind_t bind(F&& f, Args&&... args) + { + return aux::bind_t{forward(f), forward(args)...}; + } + + template + aux::bind_t bind(F&& f, Args&&... args) + { + return aux::bind_t{forward(f), forward(args)...}; + } + + namespace placeholders + { + /** + * Note: The number of placeholders is + * implementation defined, we've chosen + * 8 because it is a nice number + * and should be enough for any function + * call. + * Note: According to the C++14 standard, these + * are all extern non-const. We decided to use + * the C++17 form of them being inline constexpr + * because it is more convenient, makes sense + * and would eventually need to be upgraded + * anyway. + */ + inline constexpr aux::placeholder_t<1> _1; + inline constexpr aux::placeholder_t<2> _2; + inline constexpr aux::placeholder_t<3> _3; + inline constexpr aux::placeholder_t<4> _4; + inline constexpr aux::placeholder_t<5> _5; + inline constexpr aux::placeholder_t<6> _6; + inline constexpr aux::placeholder_t<7> _7; + inline constexpr aux::placeholder_t<8> _8; + } +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/conditional_function_typedefs.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/conditional_function_typedefs.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/conditional_function_typedefs.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,77 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTION_CONDITIONAL_FUNCTION_TYPEDEFS +#define LIBCPP_BITS_FUNCTION_CONDITIONAL_FUNCTION_TYPEDEFS + +namespace std::aux +{ + /** + * Note: Some types with possible function-like behavior + * (e.g. function, reference_wrapper, aux::mem_fn_t) + * have to define a type argument type or two types + * first_argument_type and second_argument_type when + * their invocation takes one or two arguments, respectively. + * + * The easiest way to conditionally define a type is using + * inheritance and the types below serve exactly for that + * purpose. + * + * If we have a type that is specialized as R(Args...) + * for some return type R and argument types Args..., + * we can simply (publicly) inherit from + * conditional_function_typedefs. If it is + * templated by some generic type T, we can inherit from + * conditional_function_typedefs>> + * so that the correct type below gets chosen. + */ + + template + struct conditional_function_typedefs + { /* DUMMY BODY */ }; + + template + struct conditional_function_typedefs + { + using argument_type = A; + }; + + template + struct conditional_function_typedefs + { + using first_argument_type = A1; + using second_argument_type = A2; + }; + + template + struct conditional_function_typedefs + : conditional_function_typedefs + { /* DUMMY BODY */ }; +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/function.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/function.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/function.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,377 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_FUNCTION +#define LIBCPP_BITS_FUNCTIONAL_FUNCTION + +#include <__bits/functional/conditional_function_typedefs.hpp> +#include <__bits/functional/reference_wrapper.hpp> +#include +#include + +namespace std +{ + /** + * 20.9.12, polymorphic function adaptors: + */ + + namespace aux + { + // TODO: fix this + /* template */ + /* struct is_callable_impl: false_type */ + /* { /1* DUMMY BODY *1/ }; */ + + /* template */ + /* struct is_callable_impl< */ + /* void_t(), declval()..., R))>, */ + /* R, Args... */ + /* > : true_type */ + /* { /1* DUMMY BODY *1/ }; */ + + /* template */ + /* struct is_callable: is_callable_impl, T> */ + /* { /1* DUMMY BODY *1/ }; */ + + template + R invoke_callable(Callable* clbl, Args&&... args) + { + return (*clbl)(forward(args)...); + } + + template + void copy_callable(Callable* to, Callable* from) + { + new(to) Callable{*from}; + } + + template + void destroy_callable(Callable* clbl) + { + if (clbl) + clbl->~Callable(); + } + } + + // TODO: implement + class bad_function_call; + + template + class function; // undefined + + /** + * Note: Ideally, this implementation wouldn't + * copy the target if it was a pointer to + * a function, but for the simplicity of the + * implementation, we do copy even in that + * case for now. It would be a nice optimization + * if this was changed in the future. + */ + template + class function + : public aux::conditional_function_typedefs + { + public: + using result_type = R; + + /** + * 20.9.12.2.1, construct/copy/destroy: + */ + + function() noexcept + : callable_{}, callable_size_{}, call_{}, + copy_{}, dest_{} + { /* DUMMY BODY */ } + + function(nullptr_t) noexcept + : function{} + { /* DUMMY BODY */ } + + function(const function& other) + : callable_{}, callable_size_{other.callable_size_}, + call_{other.call_}, copy_{other.copy_}, dest_{other.dest_} + { + callable_ = new uint8_t[callable_size_]; + (*copy_)(callable_, other.callable_); + } + + function(function&& other) + : callable_{other.callable_}, callable_size_{other.callable_size_}, + call_{other.call_}, copy_{other.copy_}, dest_{other.dest_} + { + other.callable_ = nullptr; + other.callable_size_ = size_t{}; + other.call_ = nullptr; + other.copy_ = nullptr; + other.dest_ = nullptr; + } + + // TODO: shall not participate in overloading unless aux::is_callable + template + function(F f) + : callable_{}, callable_size_{sizeof(F)}, + call_{(call_t)aux::invoke_callable}, + copy_{(copy_t)aux::copy_callable}, + dest_{(dest_t)aux::destroy_callable} + { + callable_ = new uint8_t[callable_size_]; + (*copy_)(callable_, (uint8_t*)&f); + } + + /** + * Note: For the moment we're ignoring the allocator + * for simplicity of the implementation. + */ + + template + function(allocator_arg_t, const A& a) noexcept + : function{} + { /* DUMMY BODY */ } + + template + function(allocator_arg_t, const A& a, nullptr_t) noexcept + : function{} + { /* DUMMY BODY */ } + + template + function(allocator_arg_t, const A& a, const function& other) + : function{other} + { /* DUMMY BODY */ } + + template + function(allocator_arg_t, const A& a, function&& other) + : function{move(other)} + { /* DUMMY BODY */ } + + // TODO: shall not participate in overloading unless aux::is_callable + template + function(allocator_arg_t, const A& a, F f) + : function{f} + { /* DUMMY BODY */ } + + function& operator=(const function& rhs) + { + function{rhs}.swap(*this); + + return *this; + } + + /** + * Note: We have to copy call_, copy_ + * and dest_ because they can be templated + * by a type F we don't know. + */ + function& operator=(function&& rhs) + { + clear_(); + + callable_ = rhs.callable_; + callable_size_ = rhs.callable_size_; + call_ = rhs.call_; + copy_ = rhs.copy_; + dest_ = rhs.dest_; + + rhs.callable_ = nullptr; + rhs.callable_size_ = size_t{}; + rhs.call_ = nullptr; + rhs.copy_ = nullptr; + rhs.dest_ = nullptr; + + return *this; + } + + function& operator=(nullptr_t) noexcept + { + clear_(); + + return *this; + } + + // TODO: shall not participate in overloading unless aux::is_callable + template + function& operator=(F&& f) + { + callable_size_ = sizeof(F); + callable_ = new uint8_t[callable_size_]; + call_ = aux::invoke_callable; + copy_ = aux::copy_callable; + dest_ = aux::destroy_callable; + + (*copy_)(callable_, (uint8_t*)&f); + } + + template + function& operator=(reference_wrapper ref) noexcept + { + return (*this) = ref.get(); + } + + ~function() + { + if (callable_) + { + (*dest_)(callable_); + delete[] callable_; + } + } + + /** + * 20.9.12.2.2, function modifiers: + */ + + void swap(function& other) noexcept + { + std::swap(callable_, other.callable_); + std::swap(callable_size_, other.callable_size_); + std::swap(call_, other.call_); + std::swap(copy_, other.copy_); + std::swap(dest_, other.dest_); + } + + template + void assign(F&& f, const A& a) + { + function{allocator_arg, a, forward(f)}.swap(*this); + } + + /** + * 20.9.12.2.3, function capacity: + */ + + explicit operator bool() const noexcept + { + return callable_ != nullptr; + } + + /** + * 20.9.12.2.4, function invocation: + */ + + result_type operator()(Args... args) const + { + // TODO: throw bad_function_call if !callable_ || !call_ + if constexpr (is_same_v) + (*call_)(callable_, forward(args)...); + else + return (*call_)(callable_, forward(args)...); + } + + /** + * 20.9.12.2.5, function target access: + */ + + const type_info& target_type() const noexcept + { + return typeid(*callable_); + } + + template + T* target() noexcept + { + if (target_type() == typeid(T)) + return (T*)callable_; + else + return nullptr; + } + + template + const T* target() const noexcept + { + if (target_type() == typeid(T)) + return (T*)callable_; + else + return nullptr; + } + + private: + using call_t = R(*)(uint8_t*, Args&&...); + using copy_t = void (*)(uint8_t*, uint8_t*); + using dest_t = void (*)(uint8_t*); + + uint8_t* callable_; + size_t callable_size_; + call_t call_; + copy_t copy_; + dest_t dest_; + + void clear_() + { + if (callable_) + { + (*dest_)(callable_); + delete[] callable_; + callable_ = nullptr; + } + } + }; + + /** + * 20.9.12.2.6, null pointer comparisons: + */ + + template + bool operator==(const function& f, nullptr_t) noexcept + { + return !f; + } + + template + bool operator==(nullptr_t, const function& f) noexcept + { + return !f; + } + + template + bool operator!=(const function& f, nullptr_t) noexcept + { + return (bool)f; + } + + template + bool operator!=(nullptr_t, const function& f) noexcept + { + return (bool)f; + } + + /** + * 20.9.12.2.7, specialized algorithms: + */ + + template + void swap(function& f1, function& f2) + { + f1.swap(f2); + } + + template + struct uses_allocator, Alloc> + : true_type + { /* DUMMY BODY */ }; +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/hash.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/hash.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/hash.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,318 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_HASH +#define LIBCPP_BITS_FUNCTIONAL_HASH + +#include +#include + +namespace std +{ + template + struct is_arithmetic; + + template + struct is_pointer; + + /** + * 20.9.13, hash function primary template: + */ + + namespace aux + { + template + union converter + { + T value; + uint64_t converted; + }; + + template + T hash_(uint64_t x) noexcept + { + /** + * Note: std::hash is used for indexing in + * unordered containers, not for cryptography. + * Because of this, we decided to simply convert + * the value to uin64_t, which will help us + * with testing (since in order to create + * a collision in a multiset or multimap + * we simply need 2 values that congruent + * by the size of the table. + */ + return static_cast(x); + } + + template + size_t hash(T x) noexcept + { + static_assert(is_arithmetic::value || is_pointer::value, + "invalid type passed to aux::hash"); + + converter conv; + conv.value = x; + + return hash_(conv.converted); + } + } + + template + struct hash + { /* DUMMY BODY */ }; + + template<> + struct hash + { + size_t operator()(bool x) const noexcept + { + return aux::hash(x); + } + + using argument_type = bool; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(char x) const noexcept + { + return aux::hash(x); + } + + using argument_type = char; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(signed char x) const noexcept + { + return aux::hash(x); + } + + using argument_type = signed char; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(unsigned char x) const noexcept + { + return aux::hash(x); + } + + using argument_type = unsigned char; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(char16_t x) const noexcept + { + return aux::hash(x); + } + + using argument_type = char16_t; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(char32_t x) const noexcept + { + return aux::hash(x); + } + + using argument_type = char32_t; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(wchar_t x) const noexcept + { + return aux::hash(x); + } + + using argument_type = wchar_t; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(short x) const noexcept + { + return aux::hash(x); + } + + using argument_type = short; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(unsigned short x) const noexcept + { + return aux::hash(x); + } + + using argument_type = unsigned short; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(int x) const noexcept + { + return aux::hash(x); + } + + using argument_type = int; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(unsigned int x) const noexcept + { + return aux::hash(x); + } + + using argument_type = unsigned int; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(long x) const noexcept + { + return aux::hash(x); + } + + using argument_type = long; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(long long x) const noexcept + { + return aux::hash(x); + } + + using argument_type = long long; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(unsigned long x) const noexcept + { + return aux::hash(x); + } + + using argument_type = unsigned long; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(unsigned long long x) const noexcept + { + return aux::hash(x); + } + + using argument_type = unsigned long long; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(float x) const noexcept + { + return aux::hash(x); + } + + using argument_type = float; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(double x) const noexcept + { + return aux::hash(x); + } + + using argument_type = double; + using result_type = size_t; + }; + + template<> + struct hash + { + size_t operator()(long double x) const noexcept + { + return aux::hash(x); + } + + using argument_type = long double; + using result_type = size_t; + }; + + template + struct hash + { + size_t operator()(T* x) const noexcept + { + return aux::hash(x); + } + + using argument_type = T*; + using result_type = size_t; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/invoke.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/invoke.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/invoke.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_INVOKE +#define LIBCPP_BITS_FUNCTIONAL_INVOKE + +#include <__bits/utility/declval.hpp> +#include <__bits/utility/forward_move.hpp> + +namespace std +{ + template + struct is_member_function_pointer; + + template + struct is_base_of; + + template + struct is_member_object_pointer; +} + +namespace std::aux +{ + /** + * 20.9.2, requirements: + */ + + template + decltype(auto) invoke(R T::* f, T1&& t1, Ts&&... args) + { + if constexpr (is_member_function_pointer::value) + { + if constexpr (is_base_of>::value) + // (1.1) + return (t1.*f)(forward(args)...); + else + // (1.2) + return ((*t1).*f)(forward(args)...); + } + else if constexpr (is_member_object_pointer::value && sizeof...(args) == 0) + { + /** + * Note: Standard requires to N be equal to 1, but we take t1 directly + * so we need sizeof...(args) to be 0. + */ + if constexpr (is_base_of>::value) + // (1.3) + return t1.*f; + else + // (1.4) + return (*t1).*f; + } + else + + /** + * Note: If this condition holds this will not be reachable, + * but a new addition to the standard (17.7 point (8.1)) + * prohibits us from simply using false as the condition here, + * so we use this because we know it is false here. + */ + static_assert(is_member_function_pointer::value, "invalid invoke"); + } + + template + decltype(auto) invoke(F&& f, Args&&... args) + { + // (1.5) + return f(forward(args)...); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/functional/reference_wrapper.hpp =================================================================== --- uspace/lib/cpp/include/__bits/functional/reference_wrapper.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/functional/reference_wrapper.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_FUNCTIONAL_REFERENCE_WRAPPER +#define LIBCPP_BITS_FUNCTIONAL_REFERENCE_WRAPPER + +#include <__bits/functional/conditional_function_typedefs.hpp> +#include <__bits/functional/invoke.hpp> +#include + +namespace std +{ + /** + * 20.9.4, reference_wrapper: + */ + + template + class reference_wrapper + : public aux::conditional_function_typedefs>> + { + public: + using type = T; + + reference_wrapper(type& val) noexcept + : data_{&val} + { /* DUMMY BODY */ } + + reference_wrapper(type&&) = delete; + + reference_wrapper(const reference_wrapper& other) noexcept + : data_{other.data_} + { /* DUMMY BODY */ } + + reference_wrapper& operator=(const reference_wrapper& other) noexcept + { + data_ = other.data_; + + return *this; + } + + operator type&() const noexcept + { + return *data_; + } + + type& get() const noexcept + { + return *data_; + } + + template + result_of_t operator()(Args&&... args) const + { + return invoke(*data_, std::forward(args)...); + } + + private: + type* data_; + }; + + template + reference_wrapper ref(T& t) noexcept + { + return reference_wrapper{t}; + } + + template + reference_wrapper cref(const T& t) noexcept + { + return reference_wrapper{t}; + } + + template + void ref(const T&&) = delete; + + template + void cref(const T&&) = delete; + + template + reference_wrapper ref(reference_wrapper t) noexcept + { + return ref(t.get()); + } + + template + reference_wrapper cref(reference_wrapper t) noexcept + { + return cref(t.get()); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/hash_table.hpp =================================================================== --- uspace/lib/cpp/include/__bits/hash_table.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/hash_table.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,595 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_HASH_TABLE +#define LIBCPP_BITS_HASH_TABLE + +#include +#include <__bits/list.hpp> +#include <__bits/key_extractors.hpp> +#include <__bits/hash_table_iterators.hpp> +#include <__bits/hash_table_policies.hpp> +#include +#include +#include +#include +#include + +namespace std::aux +{ + /** + * To save code, we're going to implement one hash table + * for both unordered_map and unordered_set. To do this, + * we create one inner hash table that is oblivious to its + * held type (and uses a key extractor to get the key from it) + * and two proxies that either use plain Key type or a pair + * of a key and a value. + * Additionally, we will use policies to represent both single + * and multi variants of these containers at once. + * Note: I am aware the naming is very unimaginative here, + * not my strong side :) + */ + + template< + class Value, class Key, class KeyExtractor, + class Hasher, class KeyEq, + class Alloc, class Size, + class Iterator, class ConstIterator, + class LocalIterator, class ConstLocalIterator, + class Policy + > + class hash_table + { + public: + using value_type = Value; + using key_type = Key; + using size_type = Size; + using allocator_type = Alloc; + using key_equal = KeyEq; + using hasher = Hasher; + using key_extract = KeyExtractor; + + using iterator = Iterator; + using const_iterator = ConstIterator; + using local_iterator = LocalIterator; + using const_local_iterator = ConstLocalIterator; + + using node_type = list_node; + + using place_type = tuple< + hash_table_bucket*, + list_node*, size_type + >; + + hash_table(size_type buckets, float max_load_factor = 1.f) + : table_{new hash_table_bucket[buckets]()}, + bucket_count_{buckets}, size_{}, hasher_{}, key_eq_{}, + key_extractor_{}, max_load_factor_{max_load_factor} + { /* DUMMY BODY */ } + + hash_table(size_type buckets, const hasher& hf, const key_equal& eql, + float max_load_factor = 1.f) + : table_{new hash_table_bucket[buckets]()}, + bucket_count_{buckets}, size_{}, hasher_{hf}, key_eq_{eql}, + key_extractor_{}, max_load_factor_{max_load_factor} + { /* DUMMY BODY */ } + + hash_table(const hash_table& other) + : hash_table{other.bucket_count_, other.hasher_, other.key_eq_, + other.max_load_factor_} + { + for (const auto& x: other) + insert(x); + } + + hash_table(hash_table&& other) + : table_{other.table_}, bucket_count_{other.bucket_count_}, + size_{other.size_}, hasher_{move(other.hasher_)}, + key_eq_{move(other.key_eq_)}, key_extractor_{move(other.key_extractor_)}, + max_load_factor_{other.max_load_factor_} + { + other.table_ = nullptr; + other.bucket_count_ = size_type{}; + other.size_ = size_type{}; + other.max_load_factor_ = 1.f; + } + + hash_table& operator=(const hash_table& other) + { + hash_table tmp{other}; + tmp.swap(*this); + + return *this; + } + + hash_table& operator=(hash_table&& other) + { + hash_table tmp{move(other)}; + tmp.swap(*this); + + return *this; + } + + bool empty() const noexcept + { + return size_ == 0; + } + + size_type size() const noexcept + { + return size_; + } + + size_type max_size(allocator_type& alloc) + { + return allocator_traits::max_size(alloc); + } + + iterator begin() noexcept + { + auto idx = first_filled_bucket_(); + return iterator{ + table_, idx, bucket_count_, + table_[idx].head + }; + } + + const_iterator begin() const noexcept + { + return cbegin(); + } + + iterator end() noexcept + { + return iterator{}; + } + + const_iterator end() const noexcept + { + return cend(); + } + + const_iterator cbegin() const noexcept + { + auto idx = first_filled_bucket_(); + return const_iterator{ + table_, idx, bucket_count_, + table_[idx].head + }; + } + + const_iterator cend() const noexcept + { + return const_iterator{}; + } + + template + auto emplace(Args&&... args) + { + return Policy::emplace(*this, forward(args)...); + } + + auto insert(const value_type& val) + { + return Policy::insert(*this, val); + } + + auto insert(value_type&& val) + { + return Policy::insert(*this, forward(val)); + } + + size_type erase(const key_type& key) + { + return Policy::erase(*this, key); + } + + iterator erase(const_iterator it) + { + auto node = it.node(); + auto idx = it.idx(); + + /** + * Note: This way we will continue on the next bucket + * if this is the last element in its bucket. + */ + iterator res{table_, idx, size_, node}; + ++res; + + if (table_[idx].head == node) + { + if (node->next != node) + table_[idx].head = node->next; + else + table_[idx].head = nullptr; + } + --size_; + + node->unlink(); + delete node; + + return res; + } + + void clear() noexcept + { + for (size_type i = 0; i < bucket_count_; ++i) + table_[i].clear(); + size_ = size_type{}; + } + + void swap(hash_table& other) + noexcept(allocator_traits::is_always_equal::value && + noexcept(swap(declval(), declval())) && + noexcept(swap(declval(), declval()))) + { + std::swap(table_, other.table_); + std::swap(bucket_count_, other.bucket_count_); + std::swap(size_, other.size_); + std::swap(hasher_, other.hasher_); + std::swap(key_eq_, other.key_eq_); + std::swap(max_load_factor_, other.max_load_factor_); + } + + hasher hash_function() const + { + return hasher_; + } + + key_equal key_eq() const + { + return key_eq_; + } + + iterator find(const key_type& key) + { + auto idx = get_bucket_idx_(key); + auto head = table_[idx].head; + + if (!head) + return end(); + + auto current = head; + do + { + if (key_eq_(key, key_extractor_(current->value))) + return iterator{table_, idx, size_, current}; + current = current->next; + } + while (current != head); + + return end(); + } + + const_iterator find(const key_type& key) const + { + auto idx = get_bucket_idx_(key); + auto head = table_[idx].head; + + if (!head) + return end(); + + auto current = head; + do + { + if (key_eq_(key, key_extractor_(current->value))) + return iterator{table_, idx, size_, current}; + current = current->next; + } + while (current != head); + + return end(); + } + + size_type count(const key_type& key) const + { + return Policy::count(*this, key); + } + + pair equal_range(const key_type& key) + { + return Policy::equal_range(*this, key); + } + + pair equal_range(const key_type& key) const + { + return Policy::equal_range_const(*this, key); + } + + size_type bucket_count() const noexcept + { + return bucket_count_; + } + + size_type max_bucket_count() const noexcept + { + return numeric_limits::max() / + sizeof(hash_table_bucket); + } + + size_type bucket_size(size_type n) const + { + return table_[n].size(); + } + + size_type bucket(const key_type& key) const + { + return get_bucket_idx_(key); + } + + local_iterator begin(size_type n) + { + return local_iterator{table_[n].head, table_[n].head}; + } + + const_local_iterator begin(size_type n) const + { + return cbegin(n); + } + + local_iterator end(size_type n) + { + return local_iterator{}; + } + + const_local_iterator end(size_type n) const + { + return cend(n); + } + + const_local_iterator cbegin(size_type n) const + { + return const_local_iterator{table_[n].head, table_[n].head}; + } + + const_local_iterator cend(size_type n) const + { + return const_local_iterator{}; + } + + float load_factor() const noexcept + { + return size_ / static_cast(bucket_count_); + } + + float max_load_factor() const noexcept + { + return max_load_factor_; + } + + void max_load_factor(float factor) + { + if (factor > 0.f) + max_load_factor_ = factor; + + rehash_if_needed(); + } + + void rehash(size_type count) + { + if (count < size_ / max_load_factor_) + count = size_ / max_load_factor_; + + /** + * Note: If an exception is thrown, there + * is no effect. Since this is the only + * place where an exception (no mem) can + * be thrown and no changes to this have been + * made, we're ok. + */ + hash_table new_table{count, max_load_factor_}; + + for (std::size_t i = 0; i < bucket_count_; ++i) + { + auto head = table_[i].head; + if (!head) + continue; + + auto current = head; + + do + { + auto next = current->next; + + current->next = current; + current->prev = current; + + auto where = Policy::find_insertion_spot( + new_table, key_extractor_(current->value) + ); + + /** + * Note: We're rehashing, so we know each + * key can be inserted. + */ + auto new_bucket = get<0>(where); + auto new_successor = get<1>(where); + + if (new_successor) + new_successor->append(current); + else + new_bucket->append(current); + + current = next; + } while (current != head); + + table_[i].head = nullptr; + } + + new_table.size_ = size_; + swap(new_table); + + delete[] new_table.table_; + new_table.table_ = nullptr; + } + + void reserve(size_type count) + { + rehash(count / max_load_factor_ + 1); + } + + bool is_eq_to(const hash_table& other) const + { + if (size() != other.size()) + return false; + + auto it = begin(); + while (it != end()) + { + /** + * For each key K we will check how many + * instances of K are there in the table. + * Then we will check if the count for K + * is equal to that amount. + */ + + size_type cnt{}; + auto tmp = it; + + while (key_eq_(key_extractor_(*it), key_extractor_(*tmp))) + { + ++cnt; + if (++tmp == end()) + break; + } + + auto other_cnt = other.count(key_extractor_(*it)); + if (cnt != other_cnt) + return false; + + it = tmp; // tmp is one past *it's key. + } + + return true; + } + + ~hash_table() + { + // Lists are deleted in ~hash_table_bucket. + if (table_) + delete[] table_; + } + + place_type find_insertion_spot(const key_type& key) const + { + return Policy::find_insertion_spot(*this, key); + } + + place_type find_insertion_spot(key_type&& key) const + { + return Policy::find_insertion_spot(*this, key); + } + + const key_type& get_key(const value_type& val) const + { + return key_extractor_(val); + } + + bool keys_equal(const key_type& key, const value_type& val) + { + return key_eq_(key, key_extractor_(val)); + } + + bool keys_equal(const key_type& key, const value_type& val) const + { + return key_eq_(key, key_extractor_(val)); + } + + hash_table_bucket* table() + { + return table_; + } + + hash_table_bucket* head(size_type idx) + { + if (idx < bucket_count_) + return table_[idx]->head; + else + return nullptr; + } + + void rehash_if_needed() + { + if (size_ > max_load_factor_ * bucket_count_) + rehash(bucket_count_ * bucket_count_growth_factor_); + } + + void increment_size() + { + ++size_; + + rehash_if_needed(); + } + + void decrement_size() + { + --size_; + } + + private: + hash_table_bucket* table_; + size_type bucket_count_; + size_type size_; + hasher hasher_; + key_equal key_eq_; + key_extract key_extractor_; + float max_load_factor_; + + static constexpr float bucket_count_growth_factor_{1.25}; + + size_type get_bucket_idx_(const key_type& key) const + { + return hasher_(key) % bucket_count_; + } + + size_type first_filled_bucket_() const + { + size_type res{}; + while (res < bucket_count_) + { + if (table_[res].head) + return res; + ++res; + } + + /** + * Note: This is used for iterators, + * so we need to return a valid index. + * But since table_[0].head is nullptr + * we know that if we return 0 the + * created iterator will test as equal + * to end(). + */ + return 0; + } + + friend Policy; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/hash_table_bucket.hpp =================================================================== --- uspace/lib/cpp/include/__bits/hash_table_bucket.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/hash_table_bucket.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_HASH_TABLE_BUCKET +#define LIBCPP_BITS_HASH_TABLE_BUCKET + +#include <__bits/list.hpp> + +namespace std::aux +{ + template + struct hash_table_bucket + { + /** + * Note: We use a doubly linked list because + * we need to use hints, which point to the + * element after the hinted spot. + */ + + list_node* head; + + hash_table_bucket() + : head{} + { /* DUMMY BODY */ } + + Size size() const noexcept + { + auto current = head; + Size res{}; + + do + { + ++res; + current = current->next; + } + while (current != head); + + return res; + } + + void append(list_node* node) + { + if (!head) + head = node; + else + head->append(node); + } + + void prepend(list_node* node) + { + if (!head) + head = node; + else + head->prepend(node); + } + + void clear() + { + if (!head) + return; + + auto current = head; + do + { + auto tmp = current; + current = current->next; + delete tmp; + } + while (current != head); + + head = nullptr; + } + + ~hash_table_bucket() + { + clear(); + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/hash_table_iterators.hpp =================================================================== --- uspace/lib/cpp/include/__bits/hash_table_iterators.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/hash_table_iterators.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,485 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_HASH_TABLE_ITERATORS +#define LIBCPP_BITS_HASH_TABLE_ITERATORS + +#include <__bits/iterator.hpp> +#include <__bits/list.hpp> +#include <__bits/hash_table_bucket.hpp> +#include + +namespace std::aux +{ + template + class hash_table_iterator + { + public: + using value_type = Value; + using size_type = Size; + using reference = Reference; + using pointer = Pointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_iterator(hash_table_bucket* table = nullptr, + size_type idx = size_type{}, size_type max_idx = size_type{}, + list_node* current = nullptr) + : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} + { /* DUMMY BODY */ } + + hash_table_iterator(const hash_table_iterator&) = default; + hash_table_iterator& operator=(const hash_table_iterator&) = default; + + reference operator*() + { + return current_->value; + } + + pointer operator->() + { + return ¤t_->value; + } + + hash_table_iterator& operator++() + { + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return *this; + } + + hash_table_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + list_node* node() + { + return current_; + } + + const list_node* node() const + { + return current_; + } + + size_type idx() const + { + return idx_; + } + + private: + hash_table_bucket* table_; + size_type idx_; + size_type max_idx_; + list_node* current_; + + template + friend class hash_table_const_iterator; + }; + + template + bool operator==(const hash_table_iterator& lhs, + const hash_table_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_iterator& lhs, + const hash_table_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_const_iterator + { + using non_const_iterator_type = hash_table_iterator< + Value, get_non_const_ref_t, + get_non_const_ptr_t, Size + >; + + public: + using value_type = Value; + using size_type = Size; + using const_reference = ConstReference; + using const_pointer = ConstPointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_const_iterator(const hash_table_bucket* table = nullptr, + size_type idx = size_type{}, size_type max_idx = size_type{}, + const list_node* current = nullptr) + : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} + { /* DUMMY BODY */ } + + hash_table_const_iterator(const hash_table_const_iterator&) = default; + hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default; + + hash_table_const_iterator(const non_const_iterator_type& other) + : table_{other.table_}, idx_{other.idx_}, max_idx_{other.max_idx_}, + current_{other.current_} + { /* DUMMY BODY */ } + + hash_table_const_iterator& operator=(const non_const_iterator_type& other) + { + table_ = other.table_; + idx_ = other.idx_; + max_idx_ = other.max_idx_; + current_ = other.current_; + + return *this; + } + + const_reference operator*() const + { + return current_->value; + } + + const_pointer operator->() const + { + return ¤t_->value; + } + + hash_table_const_iterator& operator++() + { + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return *this; + } + + hash_table_const_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + list_node* node() + { + return const_cast*>(current_); + } + + const list_node* node() const + { + return current_; + } + + size_type idx() const + { + return idx_; + } + + private: + const hash_table_bucket* table_; + size_type idx_; + size_type max_idx_; + const list_node* current_; + }; + + template + bool operator==(const hash_table_const_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return !(lhs == rhs); + } + + template + bool operator==(const hash_table_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return !(lhs == rhs); + } + + template + bool operator==(const hash_table_const_iterator& lhs, + const hash_table_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_iterator& lhs, + const hash_table_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_local_iterator + { + public: + using value_type = Value; + using reference = Reference; + using pointer = Pointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_local_iterator(list_node* head = nullptr, + list_node* current = nullptr) + : head_{head}, current_{current} + { /* DUMMY BODY */ } + + hash_table_local_iterator(const hash_table_local_iterator&) = default; + hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default; + + reference operator*() + { + return current_->value; + } + + pointer operator->() + { + return ¤t_->value; + } + + hash_table_local_iterator& operator++() + { + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return *this; + } + + hash_table_local_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + list_node* node() + { + return current_; + } + + const list_node* node() const + { + return current_; + } + + private: + list_node* head_; + list_node* current_; + + template + friend class hash_table_const_local_iterator; + }; + + template + bool operator==(const hash_table_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_const_local_iterator + { + using non_const_iterator_type = hash_table_local_iterator< + Value, get_non_const_ref_t, + get_non_const_ptr_t + >; + + public: + using value_type = Value; + using const_reference = ConstReference; + using const_pointer = ConstPointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + // TODO: requirement for forward iterator is default constructibility, fix others! + hash_table_const_local_iterator(const list_node* head = nullptr, + const list_node* current = nullptr) + : head_{head}, current_{current} + { /* DUMMY BODY */ } + + hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default; + hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default; + + hash_table_const_local_iterator(const non_const_iterator_type& other) + : head_{other.head_}, current_{other.current_} + { /* DUMMY BODY */ } + + hash_table_const_local_iterator& operator=(const non_const_iterator_type& other) + { + head_ = other.head_; + current_ = other.current_; + + return *this; + } + + const_reference operator*() const + { + return current_->value; + } + + const_pointer operator->() const + { + return ¤t_->value; + } + + hash_table_const_local_iterator& operator++() + { + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return *this; + } + + hash_table_const_local_iterator operator++(int) + { + auto tmp = *this; + ++(*this); + + return tmp; + } + + + list_node* node() + { + return const_cast*>(current_); + } + + const list_node* node() const + { + return current_; + } + + private: + const list_node* head_; + const list_node* current_; + }; + + template + bool operator==(const hash_table_const_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return !(lhs == rhs); + } + + template + bool operator==(const hash_table_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return !(lhs == rhs); + } + + template + bool operator==(const hash_table_const_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return !(lhs == rhs); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/hash_table_policies.hpp =================================================================== --- uspace/lib/cpp/include/__bits/hash_table_policies.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/hash_table_policies.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,435 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_HASH_TABLE_POLICIES +#define LIBCPP_BITS_HASH_TABLE_POLICIES + +#include +#include + +namespace std::aux +{ + struct hash_single_policy + { + template + static typename Table::size_type count(const Table& table, const Key& key) + { + return table.find(key) == table.end() ? 0 : 1; + } + + template + static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + return make_tuple( + &table.table_[idx], + table.table_[idx].head, + idx + ); + } + + template + static typename Table::size_type erase(Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto head = table.table_[idx].head; + auto current = head; + + if (!current) + return 0; + + do + { + if (table.keys_equal(key, current->value)) + { + --table.size_; + + if (current == head) + { + if (current->next != head) + table.table_[idx].head = current->next; + else + table.table_[idx].head = nullptr; + } + + current->unlink(); + delete current; + + return 1; + } + else + current = current->next; + } + while (current != head); + + return 0; + } + + template + static pair< + typename Table::iterator, + typename Table::iterator + > equal_range(Table& table, const Key& key) + { + auto it = table.find(key); + return make_pair(it, ++it); + } + + template + static pair< + typename Table::const_iterator, + typename Table::const_iterator + > equal_range_const(const Table& table, const Key& key) + { // Note: We cannot overload by return type, so we use a different name. + auto it = table.find(key); + return make_pair(it, ++it); + } + + /** + * Note: We have to duplicate code for emplace, insert(const&) + * and insert(&&) here, because the node (which makes distinction + * between the arguments) is only created if the value isn't + * in the table already. + */ + + template + static pair< + typename Table::iterator, bool + > emplace(Table& table, Args&&... args) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + auto val = value_type{forward(args)...}; + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{move(val)}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, const Value& val) + { + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{val}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, Value&& val) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{forward(val)}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + }; + + struct hash_multi_policy + { + template + static typename Table::size_type count(const Table& table, const Key& key) + { + auto head = table.table_[table.get_bucket_idx_(key)].head; + if (!head) + return 0; + + auto current = head; + typename Table::size_type res = 0; + do + { + if (table.keys_equal(key, current->value)) + ++res; + + current = current->next; + } + while (current != head); + + return res; + } + + template + static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto head = table.table_[idx].head; + + if (head) + { + auto current = head; + do + { + if (table.keys_equal(key, current->value)) + { + return make_tuple( + &table.table_[idx], + current, + idx + ); + } + + current = current->next; + } while (current != head); + } + + return make_tuple( + &table.table_[idx], + table.table_[idx].head, + idx + ); + } + + template + static typename Table::size_type erase(Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto head = table.table_[idx].head; + auto current = head; + table.table_[idx].head = nullptr; + + if (!current) + return 0; + + /** + * We traverse the list and delete if the keys + * equal, if they don't we append the nodes back + * to the bucket. + */ + typename Table::size_type res{}; + + do + { + auto tmp = current; + current = current->next; + + if (!table.keys_equal(key, tmp->value)) + table.table_[idx].append(tmp); + else + { + ++res; + --table.size_; + + delete tmp; + } + } + while (current != head); + + return res; + } + + template + static pair< + typename Table::iterator, + typename Table::iterator + > equal_range(Table& table, const Key& key) + { + auto first = table.find(key); + if (first == table.end()) + return make_pair(table.end(), table.end()); + + auto last = first; + do + { + ++last; + } while (table.keys_equal(key, *last)); + + return make_pair(first, last); + } + + template + static pair< + typename Table::const_iterator, + typename Table::const_iterator + > equal_range_const(const Table& table, const Key& key) + { + auto first = table.find(key); + if (first == table.end()) + return make_pair(table.end(), table.end()); + + auto last = first; + do + { + ++last; + } while (table.keys_equal(key, *last)); + + return make_pair(first, last); + } + + template + static typename Table::iterator emplace(Table& table, Args&&... args) + { + using node_type = typename Table::node_type; + + auto node = new node_type{forward(args)...}; + + return insert(table, node); + } + + template + static typename Table::iterator insert(Table& table, const Value& val) + { + using node_type = typename Table::node_type; + + auto node = new node_type{val}; + + return insert(table, node); + } + + template + static typename Table::iterator insert(Table& table, Value&& val) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + + auto node = new node_type{forward(val)}; + + return insert(table, node); + } + + template + static typename Table::iterator insert(Table& table, typename Table::node_type* node) + { + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(node->value); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + table.end(); + + if (target && table.keys_equal(key, target->value)) + target->append(node); + else + bucket->prepend(node); + + return iterator{ + table.table(), idx, + table.bucket_count(), + node + }; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/insert_iterator.hpp =================================================================== --- uspace/lib/cpp/include/__bits/insert_iterator.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/insert_iterator.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_INSERT_ITERATOR +#define LIBCPP_BITS_INSERT_ITERATOR + +namespace std +{ + struct forward_iterator_tag; +} + +namespace std::aux +{ + /** + * Note: Commonly the data structures in this library + * contain a set of insert member functions. These + * are often both iterator based and copy based. + * This iterator can change the copy version into + * an iterator version by creating a count based copy + * iterator. + * Usage: + * first == insert_iterator{value} + * last == insert_iterator{count} + * + * So the following code: + * while (first != last) + * *data_++ = *first++; + * + * Will insert a copy of value into the data_ + * iterator exactly count times. + * TODO: Apply this to existing containers? + */ + template + class insert_iterator + { + public: + using difference_type = unsigned long long; + using value_type = T; + using iterator_category = input_iterator_tag; + using reference = value_type&; + using pointer = value_type*; + + explicit insert_iterator(difference_type count, const value_type& val = value_type{}) + : value_{val}, count_{count} + { /* DUMMY BODY */ } + + insert_iterator(const insert_iterator&) = default; + insert_iterator& operator=(const insert_iterator&) = default; + + insert_iterator(insert_iterator&&) = default; + insert_iterator& operator=(insert_iterator&&) = default; + + const value_type& operator*() const + { + return value_; + } + + const value_type* operator->() const + { + return &value_; + } + + insert_iterator& operator++() + { + ++count_; + + return *this; + } + + insert_iterator operator++(int) + { + ++count_; + + return insert_iterator{count_ - 1, value_}; + } + + bool operator==(const insert_iterator& other) + { + return count_ == other.count_; + } + + bool operator!=(const insert_iterator& other) + { + return count_ != other.count_; + } + + private: + value_type value_; + difference_type count_; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/iomanip.hpp =================================================================== --- uspace/lib/cpp/include/__bits/iomanip.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/iomanip.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,156 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_IOMANIP +#define LIBCPP_BITS_IOMANIP + +#include +#include + +namespace std::aux +{ + /** + * Note: This allows us to lower the amount + * of code duplication in this module + * as we can avoid operator<> overloading + * for the manipulators. + */ + template + struct manip_wrapper + { + template + manip_wrapper(Args&&... args) + : manipulator{forward(args)...} + { /* DUMMY BODY */ } + + void operator()(ios_base& str) + { + manipulator(str); + } + + Manipulator manipulator; + }; + template + basic_ostream& operator<<( + basic_ostream& os, manip_wrapper manip + ) + { + manip(os); + + return os; + } + + template + basic_istream& operator>>( + basic_istream& is, manip_wrapper manip + ) + { + manip(is); + + return is; + } + + struct resetiosflags_t + { + resetiosflags_t(ios_base::fmtflags m); + + void operator()(ios_base& str) const; + + ios_base::fmtflags mask; + }; + + struct setiosflags_t + { + setiosflags_t(ios_base::fmtflags m); + + void operator()(ios_base& str) const; + + ios_base::fmtflags mask; + }; + + struct setbase_t + { + setbase_t(int b); + + void operator()(ios_base& str) const; + + int base; + }; + + /** + * Note: setfill is only for basic_ostream so + * this is the only case where we overload + * the appropriate operator again. + */ + template + struct setfill_t + { + setfill_t(Char c) + : fill{c} + { /* DUMMY BODY */ } + + template + void operator()(basic_ios& str) const + { + str.fill(fill); + } + + Char fill; + }; + + template + basic_ostream& operator<<( + basic_ostream& is, + setfill_t manip + ) + { + manip(is); + + return is; + } + + struct setprecision_t + { + setprecision_t(int); + + void operator()(ios_base&) const; + + int prec; + }; + + struct setw_t + { + setw_t(int); + + void operator()(ios_base&) const; + + int width; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/iterator.hpp =================================================================== --- uspace/lib/cpp/include/__bits/iterator.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/iterator.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_ITERATOR +#define LIBCPP_BITS_ITERATOR + +#include <__bits/aux.hpp> + +namespace std::aux +{ + /** + * Used for our custom iterators where we know + * that their references/const_references and + * pointers/const_pointers differ only in constness. + */ + + template + struct get_non_const_ref + : type_is + { /* DUMMY BODY */ }; + + template + struct get_non_const_ref + : type_is + { /* DUMMY BODY */ }; + + template + using get_non_const_ref_t = typename get_non_const_ref::type; + + template + struct get_non_const_ptr + : type_is + { /* DUMMY BODY */ }; + + template + struct get_non_const_ptr + : type_is + { /* DUMMY BODY */ }; + + template + using get_non_const_ptr_t = typename get_non_const_ptr::type; +} + +#endif Index: uspace/lib/cpp/include/__bits/key_extractors.hpp =================================================================== --- uspace/lib/cpp/include/__bits/key_extractors.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/key_extractors.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_KEY_EXTRACTORS +#define LIBCPP_BITS_KEY_EXTRACTORS + +#include + +namespace std::aux +{ + template + struct key_value_key_extractor + { + const Key& operator()(const pair& p) const noexcept + { + return p.first; + } + }; + + template + struct key_no_value_key_extractor + { + Key& operator()(Key& k) const noexcept + { + return k; + } + + const Key& operator()(const Key& k) const noexcept + { + return k; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/list.hpp =================================================================== --- uspace/lib/cpp/include/__bits/list.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/list.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LIST +#define LIBCPP_BITS_LIST + +namespace std::aux +{ + template + struct list_node + { + T value; + list_node* next; + list_node* prev; + + template + list_node(Args&&... args) + : value{forward(args)...}, + next{}, prev{} + { + next = this; + prev = this; + } + + list_node(const T& val) + : value{val}, next{}, prev{} + { + next = this; + prev = this; + } + + list_node(T&& val) + : value{forward(val)}, next{}, prev{} + { + next = this; + prev = this; + } + + void append(list_node* node) + { + node->next = next; + node->prev = this; + next->prev = node; + next = node; + } + + void prepend(list_node* node) + { + node->next = this; + node->prev = prev; + prev->next = node; + prev = node; + } + + void unlink() + { + prev->next = next; + next->prev = prev; + next = this; + prev = this; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/locale.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,173 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE +#define LIBCPP_BITS_LOCALE + +#include + +namespace std +{ + class locale; + + /** + * 22.3.1, class locale: + */ + + class locale + { + public: + class facet + { + protected: + explicit facet(size_t refs = 0); + + virtual ~facet(); + + facet(const facet&) = delete; + void operator=(const facet&) = delete; + }; + + class id + { + public: + id() = default; + + id(const id&) = delete; + void operator=(const id&) = delete; + }; + + using category = int; + + static const category none = 0b000'0001; + static const category collate = 0b000'0010; + static const category ctype = 0b000'0100; + static const category monetary = 0b000'1000; + static const category numeric = 0b001'0000; + static const category time = 0b010'0000; + static const category messages = 0b100'0000; + static const category all = collate | ctype | monetary | + numeric | time | messages; + + locale() noexcept; + + locale(const locale& other) noexcept; + + explicit locale(const char* name); + + explicit locale(const string& name); + + locale(const locale& other, const char* name, category); + + locale(const locale& other, const string& name, category); + + template + locale(const locale& other, Facet* f) + : name_{other.name_} + { /* DUMMY BODY */ } + + locale(const locale& other, const locale& one, category); + + ~locale() = default; + + const locale& operator=(const locale& other) noexcept; + + template + locale combine(const locale& other) const + { + return other; + } + + string name() const; + + bool operator==(const locale& other) const; + bool operator!=(const locale& other) const; + + template + bool operator()(const basic_string& s1, + const basic_string& s2) const + { + // TODO: define outside locale + /* return use_facet>(*this).compare( */ + /* s1.begin(), s1.end(), s2.begin(), s2.end() */ + /* ) < 0; */ + return false; + } + + static locale global(const locale&) + { + return *the_locale_; + } + + static const locale& classic() + { + return *the_locale_; + } + + private: + string name_; + + // TODO: implement the_locale_ + static constexpr locale* the_locale_{nullptr}; + + template + friend bool has_facet(const locale&); + + template + bool has_() + { // Our single locale atm has all facets. + return true; + } + + template + /* friend const Facet& use_facet(const locale&); */ + friend Facet use_facet(const locale&); + + template + /* const Facet& get_() const */ + Facet get_() const + { + return Facet{0U}; + } + }; + + template + /* const Facet& use_facet(const locale& loc) */ + Facet use_facet(const locale& loc) + { + return loc.get_(); + } + + template + bool has_facet(const locale& loc) + { + return loc.has_(); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/locale/codecvt.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale/codecvt.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale/codecvt.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,178 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE_CODECVT +#define LIBCPP_BITS_LOCALE_CODECVT + +#include +#include + +namespace std +{ + /** + * 22.4.1.4, class template codecvt: + */ + + class codecvt_base + { + public: + enum result + { + ok, partial, error, noconv + }; + }; + + template + class codecvt: public codecvt_base + { + public: + using intern_type = Intern; + using extern_type = Extern; + using state_type = State; + + explicit codecvt(size_t = 0) + { /* DUMMY BODY */ } + + result out(state_type& state, const intern_type* from, const intern_type* from_end, + const intern_type*& from_next, extern_type* to, extern_type* to_end, + extern_type*& to_next) const + { + return do_out(state, from, from_end, from_next, to, to_end, to_next); + } + + result unshift(state_type& state, extern_type* to, extern_type* to_end, + extern_type*& to_next) const + { + return do_unshift(state, to, to_end, to_next); + } + + result in(state_type& state, const extern_type* from, const extern_type* from_end, + const extern_type*& from_next, intern_type* to, intern_type* to_end, + intern_type*& to_next) const + { + return do_in(state, from, from_end, from_next, to, to_end, to_next); + } + + int encoding() const noexcept + { + return do_encoding(); + } + + bool always_noconv() const noexcept + { + return do_always_noconv(); + } + + int length(state_type& state, const extern_type* from, const extern_type* end, + size_t max) const + { + return do_length(state, from, end, max); + } + + int max_length() const noexcept + { + return do_max_length(); + } + + static locale::id id; + + ~codecvt() = default; + + protected: + virtual result do_out(state_type& state, const intern_type* from, const intern_type* from_end, + const intern_type*& from_next, extern_type* to, extern_type* to_end, + extern_type*& to_next) const + { + // TODO: implement + return error; + } + + virtual result do_unshift(state_type& state, extern_type* to, extern_type* to_end, + extern_type*& to_next) const + { + // TODO: implement + return error; + } + + virtual result do_in(state_type& state, const extern_type* from, const extern_type* from_end, + const extern_type*& from_next, intern_type* to, intern_type* to_end, + intern_type*& to_next) const + { + // TODO: implement + return error; + } + + virtual int do_encoding() const noexcept + { + // TODO: implement + return 0; + } + + virtual bool do_always_noconv() const noexcept + { + // TODO: implement + return false; + } + + virtual int do_length(state_type& state, const extern_type* from, const extern_type* end, + size_t max) const + { + // TODO: implement + return 0; + } + + virtual int do_max_length() const noexcept + { + // TODO: implement + return 0; + } + }; + + template + locale::id codecvt::id{}; + + /** + * 22.4.1.5, class template codecvt_byname: + * Note: Dummy, TODO: implement. + */ + + template + class codecvt_byname: public codecvt + { + public: + explicit codecvt_byname(const char*, size_t = 0) + { /* DUMMY BODY */ } + + explicit codecvt_byname(const string&, size_t = 0) + { /* DUMMY BODY */ } + + ~codecvt_byname() = default; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/locale/ctype.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale/ctype.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale/ctype.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,611 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE_CTYPE +#define LIBCPP_BITS_LOCALE_CTYPE + +#include +#include <__bits/locale.hpp> +#include + +namespace std +{ + /** + * 22.4.1, the type category: + */ + + class ctype_base + { + public: + using mask = uint16_t; + + static constexpr mask space = 0b00'0000'0001; + static constexpr mask print = 0b00'0000'0010; + static constexpr mask cntrl = 0b00'0000'0100; + static constexpr mask upper = 0b00'0000'1000; + static constexpr mask lower = 0b00'0001'0000; + static constexpr mask alpha = 0b00'0010'0000; + static constexpr mask digit = 0b00'0100'0000; + static constexpr mask punct = 0b00'1000'0000; + static constexpr mask xdigit = 0b01'0000'0000; + static constexpr mask blank = 0b10'0000'0000; + static constexpr mask alnum = alpha | digit; + static constexpr mask graph = alnum | punct; + }; + + /** + * 22.4.1.1, class template ctype: + */ + + template + class ctype: public locale::facet, public ctype_base + { + public: + using char_type = Char; + + explicit ctype(size_t) + { /* DUMMY BODY */ } + + bool is(mask m, char_type c) const + { + return do_is(m, c); + } + + const char_type* is(const char_type* low, const char_type* high, + mask* vec) const + { + return do_is(low, high, vec); + } + + const char_type* scan_is(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_is(m, low, high); + } + + const char_type* scan_not(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_not(m, low, high); + } + + char_type toupper(char_type c) const + { + return do_toupper(c); + } + + const char_type* toupper(char_type* low, const char_type* high) const + { + return do_toupper(low, high); + } + + char_type tolower(char_type c) const + { + return do_tolower(c); + } + + const char_type* tolower(char_type* low, const char_type* high) const + { + return do_tolower(low, high); + } + + char_type widen(char c) const + { + return do_widen(c); + } + + const char_type* widen(const char* low, const char* high, char_type* to) const + { + return do_widen(low, high, to); + } + + char narrow(char_type c, char def) const + { + return do_narrow(c, def); + } + + const char_type* narrow(const char_type* low, const char_type* high, + char def, char* to) const + { + return do_narrow(low, high, def, to); + } + + static locale::id id; + + /** + * Note: This is a deviation from the standard, because in the + * ISO C++ Standard this function is protected (because + * the instances are reference counted, but in our design + * they are not and as such we did this change). + * (This applies to all constructors of all facets.) + */ + ~ctype() = default; + + protected: + virtual bool do_is(mask m, char_type c) const + { + // TODO: implement + return false; + } + + virtual const char_type* do_is(const char_type* low, const char_type high, + mask m) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_is(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_not(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return low; + } + + virtual char_type do_toupper(char_type c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_toupper(char_type* low, const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_tolower(char_type c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_tolower(char_type* low, const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_widen(char c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_widen(const char* low, const char* high, + char_type* dest) const + { + // TODO: implement + return high; + } + + virtual char do_narrow(char_type c, char def) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_narrow(const char_type* low, const char_type* high, + char def, char* dest) const + { + // TODO: implement + return high; + } + }; + + template + locale::id ctype::id{}; + + /** + * 22.4.1.2, class template ctype_byname: + * Note: Dummy, TODO: implement. + */ + + template + class ctype_byname: public ctype + { + public: + using mask = typename ctype::mask; + + explicit ctype_byname(const char* name, size_t = 0) + { /* DUMMY BODY */ } + + explicit ctype_byname(const string& name, size_t = 0) + { /* DUMMY BODY */ } + + protected: + ~ctype_byname() = default; + }; + + /** + * 22.4.1.3, ctype specialziations: + */ + + template<> + class ctype: public locale::facet, public ctype_base + { + public: + using char_type = char; + + explicit ctype(const mask* tab = nullptr, bool del = false, size_t = 0) + { /* DUMMY BODY */ } + + bool is(mask m, char_type c) const + { + return do_is(m, c); + } + + const char_type* is(const char_type* low, const char_type* high, + mask* vec) const + { + return do_is(low, high, vec); + } + + const char_type* scan_is(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_is(m, low, high); + } + + const char_type* scan_not(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_not(m, low, high); + } + + char_type toupper(char_type c) const + { + return do_toupper(c); + } + + const char_type* toupper(char_type* low, const char_type* high) const + { + return do_toupper(low, high); + } + + char_type tolower(char_type c) const + { + return do_tolower(c); + } + + const char_type* tolower(char_type* low, const char_type* high) const + { + return do_tolower(low, high); + } + + char_type widen(char c) const + { + return do_widen(c); + } + + const char_type* widen(const char* low, const char* high, char_type* to) const + { + return do_widen(low, high, to); + } + + char narrow(char_type c, char def) const + { + return do_narrow(c, def); + } + + const char_type* narrow(const char_type* low, const char_type* high, + char def, char* to) const + { + return do_narrow(low, high, def, to); + } + + static locale::id id; + static const size_t table_size{0}; + + const mask* table() const noexcept + { + return classic_table(); + } + + static const mask* classic_table() noexcept + { + return classic_table_; + } + + ~ctype() = default; + + protected: + virtual bool do_is(mask m, char_type c) const + { + // TODO: implement, this is a dummy + if ((m & space) != 0 && std::isspace(c)) + return true; + else if ((m & alpha) != 0 && std::isalpha(c)) + return true; + else if ((m & upper) != 0 && std::isupper(c)) + return true; + else if ((m & lower) != 0 && std::islower(c)) + return true; + else if ((m & digit) != 0 && std::isdigit(c)) + return true; + return false; + } + + virtual const char_type* do_is(const char_type* low, const char_type* high, + mask* m) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_is(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_not(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_toupper(char_type c) const + { + return std::toupper(c); + } + + virtual const char_type* do_toupper(char_type* low, const char_type* high) const + { + while (low != high) + *low = std::toupper(*low); + + return high; + } + + virtual char_type do_tolower(char_type c) const + { + return std::tolower(c); + } + + virtual const char_type* do_tolower(char_type* low, const char_type* high) const + { + while (low != high) + *low = std::tolower(*low); + + return high; + } + + virtual char_type do_widen(char c) const + { + return c; + } + + virtual const char_type* do_widen(const char* low, const char* high, + char_type* dest) const + { + while (low != high) + *dest++ = *low++; + + return high; + } + + virtual char do_narrow(char_type c, char def) const + { + return c; + } + + virtual const char_type* do_narrow(const char_type* low, const char_type* high, + char def, char* dest) const + { + while (low != high) + *dest++ = *low++; + + return high; + } + + private: + static constexpr mask* classic_table_{nullptr}; + }; + + template<> + class ctype: public locale::facet, public ctype_base + { + public: + using char_type = wchar_t; + + explicit ctype(const mask* tab = nullptr, bool del = false, size_t = 0) + { /* DUMMY BODY */ } + + bool is(mask m, char_type c) const + { + return do_is(m, c); + } + + const char_type* is(const char_type* low, const char_type* high, + mask* vec) const + { + return do_is(low, high, vec); + } + + const char_type* scan_is(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_is(m, low, high); + } + + const char_type* scan_not(mask m, const char_type* low, + const char_type* high) const + { + return do_scan_not(m, low, high); + } + + char_type toupper(char_type c) const + { + return do_toupper(c); + } + + const char_type* toupper(char_type* low, const char_type* high) const + { + return do_toupper(low, high); + } + + char_type tolower(char_type c) const + { + return do_tolower(c); + } + + const char_type* tolower(char_type* low, const char_type* high) const + { + return do_tolower(low, high); + } + + char_type widen(char c) const + { + return do_widen(c); + } + + const char_type* widen(const char* low, const char* high, char_type* to) const + { + return do_widen(low, high, to); + } + + char narrow(char_type c, char def) const + { + return do_narrow(c, def); + } + + const char_type* narrow(const char_type* low, const char_type* high, + char def, char* to) const + { + return do_narrow(low, high, def, to); + } + + static locale::id id; + static const size_t table_size{0}; + + const mask* table() const noexcept + { + return classic_table(); + } + + static const mask* classic_table() noexcept + { + return classic_table_; + } + + ~ctype() = default; + + protected: + virtual bool do_is(mask m, char_type c) const + { + // TODO: implement + return false; + } + + virtual const char_type* do_is(const char_type* low, const char_type* high, + mask* m) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_is(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return high; + } + + virtual const char_type* do_scan_not(mask m, const char_type* low, + const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_toupper(char_type c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_toupper(char_type* low, const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_tolower(char_type c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_tolower(char_type* low, const char_type* high) const + { + // TODO: implement + return high; + } + + virtual char_type do_widen(char c) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_widen(const char* low, const char* high, + char_type* dest) const + { + // TODO: implement + return dest; + } + + virtual char do_narrow(char_type c, char def) const + { + // TODO: implement + return c; + } + + virtual const char_type* do_narrow(const char_type* low, const char_type* high, + char def, char* dest) const + { + // TODO: implement + return high; + } + + private: + static constexpr mask* classic_table_{nullptr}; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/locale/num_get.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale/num_get.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale/num_get.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,369 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE_NUM_GET +#define LIBCPP_BITS_LOCALE_NUM_GET + +#include +#include +#include <__bits/locale.hpp> +#include <__bits/locale/numpunct.hpp> +#include +#include +#include + +namespace std +{ + /** + * 22.4.2.1, class template num_get: + */ + + template> + class num_get: public locale::facet + { + public: + using char_type = Char; + using iter_type = InputIterator; + + explicit num_get(size_t refs = 0) + { /* DUMMY BODY */ } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, bool& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long long& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned short& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned int& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned long& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned long long& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, float& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, double& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long double& v) const + { + return do_get(in, end, base, err, v); + } + + iter_type get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, void*& v) const + { + return do_get(in, end, base, err, v); + } + + static locale::id id; + + ~num_get() + { /* DUMMY BODY */ } + + protected: + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, bool& v) const + { + if (in == end) + { + err = ios_base::eofbit; + return in; + } + + if ((base.flags() & ios_base::boolalpha) == 0) + { + int8_t tmp{}; + in = get_integral_(in, end, base, err, tmp); + + if (tmp == 0) + v = false; + else if (tmp == 1) + v = true; + else + { + v = true; + err = ios_base::failbit; + } + } + else + { + /** + * We track both truename() and falsename() + * at the same time, once either is matched + * or the input is too big without a match + * or the input ends the conversion ends + * and the result is deduced. + */ + + auto loc = base.getloc(); + const auto& nt = use_facet>(loc); + + auto true_target = nt.truename(); + auto false_target = nt.falsename(); + + if (true_target == "" || false_target == "") + { + v = (err == ios_base::failbit); + return in; + } + + auto true_str = true_target; + auto false_str = false_target; + + size_t i{}; + while (true) + { + if (true_str.size() <= i && false_str.size() <= i) + break; + auto c = *in++; + + if (i < true_str.size()) + true_str[i] = c; + if (i < false_str.size()) + false_str[i] = c; + ++i; + + if (in == end || *in == '\n') + { + err = ios_base::eofbit; + break; + } + } + + if (i == true_str.size() && true_str == true_target) + { + v = true; + + if (++in == end) + err = ios_base::eofbit; + else + err = ios_base::goodbit; + } + else if (i == false_str.size() && false_str == false_target) + { + v = false; + + if (in == end) + err = (ios_base::failbit | ios_base::eofbit); + else + err = ios_base::failbit; + } + else + err = ios_base::failbit; + } + + return in; + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long long& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned short& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned int& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned long& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, unsigned long long& v) const + { + return get_integral_(in, end, base, err, v); + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, float& v) const + { + // TODO: implement + return in; + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, double& v) const + { + // TODO: implement + return in; + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, long double& v) const + { + // TODO: implement + return in; + } + + iter_type do_get(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, void*& v) const + { + // TODO: implement + return in; + } + + private: + template + iter_type get_integral_(iter_type in, iter_type end, ios_base& base, + ios_base::iostate& err, T& v) const + { + BaseType res{}; + unsigned int num_base{10}; + + auto basefield = (base.flags() & ios_base::basefield); + if (basefield == ios_base::oct) + num_base = 8; + else if (basefield == ios_base::hex) + num_base = 16; + + auto size = fill_buffer_integral_(in, end, base); + if (size > 0) + { + int ret{}; + if constexpr (is_signed::value) + ret = std::hel::str_int64_t(base.buffer_, nullptr, num_base, false, &res); + else + ret = std::hel::str_uint64_t(base.buffer_, nullptr, num_base, false, &res); + + if (ret != EOK) + { + err |= ios_base::failbit; + v = 0; + } + else if (res > static_cast(numeric_limits::max())) + { + err |= ios_base::failbit; + v = numeric_limits::max(); + } + else if (res < static_cast(numeric_limits::min())) + { + err |= ios_base::failbit; + v = numeric_limits::min(); + } + else + v = static_cast(res); + } + else + { + err |= ios_base::failbit; + v = 0; + } + + return in; + } + + size_t fill_buffer_integral_(iter_type& in, iter_type end, ios_base& base) const + { + if (in == end) + return 0; + + auto loc = base.getloc(); + const auto& ct = use_facet>(loc); + auto hex = ((base.flags() & ios_base::hex) != 0); + + size_t i{}; + if (*in == '+' || *in == '-') + base.buffer_[i++] = *in++; + + while (in != end && i < ios_base::buffer_size_ - 1) + { + auto c = *in; + if (ct.is(ctype_base::digit, c) || (hex && + ((c >= ct.widen('A') && c <= ct.widen('F')) || + (c >= ct.widen('a') && c <= ct.widen('f'))))) + { + ++in; + base.buffer_[i++] = c; + } + else + break; + } + base.buffer_[i] = char_type{}; + + return i; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/locale/num_put.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale/num_put.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale/num_put.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,313 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE_NUM_PUT +#define LIBCPP_BITS_LOCALE_NUM_PUT + +#include <__bits/locale.hpp> +#include <__bits/locale/numpunct.hpp> +#include +#include + +namespace std +{ + /** + * 22.4.2.2, class template num_put: + */ + + template> + class num_put: public locale::facet + { + public: + using char_type = Char; + using iter_type = OutputIterator; + + explicit num_put(size_t refs = 0) + { /* DUMMY BODY */ } + + iter_type put(iter_type it, ios_base& base, char_type fill, bool v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, long v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, long long v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, unsigned long v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, unsigned long long v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, double v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, long double v) const + { + return do_put(it, base, fill, v); + } + + iter_type put(iter_type it, ios_base& base, char_type fill, const void* v) const + { + return do_put(it, base, fill, v); + } + + ~num_put() + { /* DUMMY BODY */ } + + protected: + iter_type do_put(iter_type it, ios_base& base, char_type fill, bool v) const + { + auto loc = base.getloc(); + + if ((base.flags() & ios_base::boolalpha) == 0) + return do_put(it, base, fill, (long)v); + else + { + auto s = v ? use_facet>(loc).truename() + : use_facet>(loc).falsename(); + for (auto c: s) + *it++ = c; + } + + return it; + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, long v) const + { + auto basefield = (base.flags() & ios_base::basefield); + auto uppercase = (base.flags() & ios_base::uppercase); + + int ret{}; + if (basefield == ios_base::oct) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lo", v); + else if ((basefield == ios_base::hex) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lx", v); + else if (basefield == ios_base::hex) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lX", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%ld", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, long long v) const + { + auto basefield = (base.flags() & ios_base::basefield); + auto uppercase = (base.flags() & ios_base::uppercase); + + int ret{}; + if (basefield == ios_base::oct) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llo", v); + else if ((basefield == ios_base::hex) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llx", v); + else if (basefield == ios_base::hex) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llX", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lld", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, unsigned long v) const + { + auto basefield = (base.flags() & ios_base::basefield); + auto uppercase = (base.flags() & ios_base::uppercase); + + int ret{}; + if (basefield == ios_base::oct) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lo", v); + else if ((basefield == ios_base::hex) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lx", v); + else if (basefield == ios_base::hex) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lX", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%lu", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, unsigned long long v) const + { + auto basefield = (base.flags() & ios_base::basefield); + auto uppercase = (base.flags() & ios_base::uppercase); + + // TODO: showbase + int ret{}; + if (basefield == ios_base::oct) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llo", v); + else if ((basefield == ios_base::hex) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llx", v); + else if (basefield == ios_base::hex) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llX", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%llu", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, double v) const + { + auto floatfield = (base.flags() & ios_base::floatfield); + auto uppercase = (base.flags() & ios_base::uppercase); + + // TODO: showbase + // TODO: precision + int ret{}; + if (floatfield == ios_base::fixed) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%f", v); + else if (floatfield == ios_base::scientific && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%e", v); + else if (floatfield == ios_base::scientific) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%E", v); + else if (floatfield == (ios_base::fixed | ios_base::scientific) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%a", v); + else if (floatfield == (ios_base::fixed | ios_base::scientific)) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%A", v); + else if (!uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%g", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%G", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, long double v) const + { + /** + * Note: Long double is not support at the moment in snprintf. + */ + auto floatfield = (base.flags() & ios_base::floatfield); + auto uppercase = (base.flags() & ios_base::uppercase); + + // TODO: showbase + // TODO: precision + int ret{}; + if (floatfield == ios_base::fixed) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%Lf", v); + else if (floatfield == ios_base::scientific && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%Le", v); + else if (floatfield == ios_base::scientific) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%LE", v); + else if (floatfield == (ios_base::fixed | ios_base::scientific) && !uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%La", v); + else if (floatfield == (ios_base::fixed | ios_base::scientific)) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%LA", v); + else if (!uppercase) + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%Lg", v); + else + ret = snprintf(base.buffer_, ios_base::buffer_size_, "%LG", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + iter_type do_put(iter_type it, ios_base& base, char_type fill, const void* v) const + { + int ret = snprintf(base.buffer_, ios_base::buffer_size_, "%p", v); + + return put_adjusted_buffer_(it, base, fill, ret); + } + + private: + iter_type put_adjusted_buffer_(iter_type it, ios_base& base, char_type fill, size_t size) const + { + auto adjustfield = (base.flags() & ios_base::adjustfield); + + size_t to_fill{}; + size_t width = static_cast(base.width()); + + if (base.width() > 0 && size < width) + to_fill = width - size; + + if (to_fill > 0) + { + if (adjustfield == ios_base::left) + { + it = put_buffer_(it, base, fill, 0, size); + for (size_t i = 0; i < to_fill; ++i) + *it++ = fill; + } + else if (adjustfield == ios_base::right) + { + for (size_t i = 0; i < to_fill; ++i) + *it++ = fill; + it = put_buffer_(it, base, fill, 0, size); + } + else if (adjustfield == ios_base::internal) + { + // TODO: pad after - or 0x/0X + } + else + { + for (size_t i = 0; i < to_fill; ++i) + *it++ = fill; + it = put_buffer_(it, base, fill, 0, size); + } + } + else + it = put_buffer_(it, base, fill, 0, size); + base.width(0); + + return it; + } + + iter_type put_buffer_(iter_type it, ios_base& base, char_type fill, size_t start, size_t size) const + { + const auto& loc = base.getloc(); + const auto& ct = use_facet>(loc); + const auto& punct = use_facet>(loc); + + for (size_t i = start; i < size; ++i) + { + if (base.buffer_[i] == '.') + *it++ = punct.decimal_point(); + else + *it++ = ct.widen(base.buffer_[i]); + // TODO: Should do grouping & thousands_sep, but that's a low + // priority for now. + } + + return it; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/locale/numpunct.hpp =================================================================== --- uspace/lib/cpp/include/__bits/locale/numpunct.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/locale/numpunct.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,214 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_LOCALE_NUMPUNCT +#define LIBCPP_BITS_LOCALE_NUMPUNCT + +#include <__bits/locale.hpp> +#include + +namespace std +{ + /** + * 22.4.3.1, class template numpunct: + */ + + template + class numpunct: public locale::facet + { + public: + using char_type = Char; + using string_type = basic_string; + + explicit numpunct(size_t refs = 0); + + char_type decimal_point() const + { + return do_decimal_point(); + } + + char_type thousands_sep() const + { + return do_thousands_sep(); + } + + string_type grouping() const + { + return do_grouping(); + } + + string_type truename() const + { + return do_truename(); + } + + string_type falsename() const + { + return do_falsename(); + } + + ~numpunct(); + + protected: + char_type do_decimal_point() const; + char_type do_thousands_sep() const; + string_type do_grouping() const; + string_type do_truename() const; + string_type do_falsename() const; + }; + + template<> + class numpunct: public locale::facet + { + public: + using char_type = char; + using string_type = basic_string; + + explicit numpunct(size_t refs = 0) + { /* DUMMY BODY */ } + + char_type decimal_point() const + { + return do_decimal_point(); + } + + char_type thousands_sep() const + { + return do_thousands_sep(); + } + + string_type grouping() const + { + return do_grouping(); + } + + string_type truename() const + { + return do_truename(); + } + + string_type falsename() const + { + return do_falsename(); + } + + ~numpunct() + { /* DUMMY BODY */ } + + protected: + char_type do_decimal_point() const + { + return '.'; + } + + char_type do_thousands_sep() const + { + return ','; + } + + string_type do_grouping() const + { + return ""; + } + + string_type do_truename() const + { + return "true"; + } + + string_type do_falsename() const + { + return "false"; + } + }; + + template<> + class numpunct: public locale::facet + { + public: + using char_type = wchar_t; + using string_type = basic_string; + + explicit numpunct(size_t refs = 0); + + char_type decimal_point() const + { + return do_decimal_point(); + } + + char_type thousands_sep() const + { + return do_thousands_sep(); + } + + string_type grouping() const + { + return do_grouping(); + } + + string_type truename() const + { + return do_truename(); + } + + string_type falsename() const + { + return do_falsename(); + } + + ~numpunct(); + + protected: + char_type do_decimal_point() const + { + return L'.'; + } + + char_type do_thousands_sep() const + { + return L','; + } + + string_type do_grouping() const + { + return L""; + } + + string_type do_truename() const + { + return L"true"; + } + + string_type do_falsename() const + { + return L"false"; + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/addressof.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/addressof.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/addressof.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_ADDRESSOF +#define LIBCPP_BITS_MEMORY_ADDRESSOF + +namespace std +{ + /** + * 20.7.12, specialized algorithms: + */ + + template + T* addressof(T& x) noexcept + { + return reinterpret_cast( + &const_cast( + reinterpret_cast(x) + )); + } +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/allocator_arg.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/allocator_arg.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/allocator_arg.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_ALLOCATOR_ARG +#define LIBCPP_BITS_MEMORY_ALLOCATOR_ARG + +namespace std +{ + /** + * 20.7.6, allocator argument tag: + */ + + struct allocator_arg_t + { /* DUMMY BODY */ }; + + constexpr allocator_arg_t allocator_arg{}; +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/allocator_traits.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/allocator_traits.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/allocator_traits.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,255 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_ALLOCATOR_TRAITS +#define LIBCPP_BITS_MEMORY_ALLOCATOR_TRAITS + +#include +#include <__bits/aux.hpp> +#include <__bits/memory/addressof.hpp> +#include <__bits/memory/pointer_traits.hpp> +#include <__bits/memory/type_getters.hpp> +#include +#include + +namespace std +{ + /** + * 20.7.7, uses_allocator: + */ + + namespace aux + { + template + struct has_allocator_type: false_type + { /* DUMMY BODY */ }; + + template + struct has_allocator_type> + : true_type + { /* DUMMY BODY */ }; + } + + template + struct uses_allocator + : aux::value_is< + bool, aux::has_allocator_type::value && is_convertible_v< + Alloc, typename T::allocator_type + > + > + { /* DUMMY BODY */ }; + + /** + * 20.7.8, allocator traits: + */ + + template + struct allocator_traits + { + using allocator_type = Alloc; + + using value_type = typename Alloc::value_type; + using pointer = typename aux::alloc_get_pointer::type; + using const_pointer = typename aux::alloc_get_const_pointer::type; + using void_pointer = typename aux::alloc_get_void_pointer::type; + using const_void_pointer = typename aux::alloc_get_const_void_pointer::type; + using difference_type = typename aux::alloc_get_difference_type::type; + using size_type = typename aux::alloc_get_size_type::type; + + using propagate_on_container_copy_assignment = typename aux::alloc_get_copy_propagate::type; + using propagate_on_container_move_assignment = typename aux::alloc_get_move_propagate::type; + using propagate_on_container_swap = typename aux::alloc_get_swap_propagate::type; + using is_always_equal = typename aux::alloc_get_always_equal::type; + + template + using rebind_alloc = typename aux::alloc_get_rebind_alloc; + + template + using rebind_traits = allocator_traits>; + + static pointer allocate(Alloc& alloc, size_type n) + { + return alloc.allocate(n); + } + + static pointer allocate(Alloc& alloc, size_type n, const_void_pointer hint) + { + if constexpr (aux::alloc_has_hint_allocate::value) + return alloc.allocate(n, hint); + else + return alloc.allocate(n); + } + + static void deallocate(Alloc& alloc, pointer ptr, size_type n) + { + alloc.deallocate(ptr, n); + } + + template + static void construct(Alloc& alloc, T* ptr, Args&&... args) + { + if constexpr (aux::alloc_has_construct::value) + alloc.construct(ptr, forward(args)...); + else + ::new(static_cast(ptr)) T(forward(args)...); + } + + template + static void destroy(Alloc& alloc, T* ptr) + { + if constexpr (aux::alloc_has_destroy::value) + alloc.destroy(ptr); + else + ptr->~T(); + } + + static size_type max_size(const Alloc& alloc) noexcept + { + if constexpr (aux::alloc_has_max_size::value) + return alloc.max_size(); + else + return numeric_limits::max(); + } + + static Alloc select_on_container_copy_construction(const Alloc& alloc) + { + if constexpr (aux::alloc_has_select::value) + return alloc.select_on_container_copy_construction(); + else + return alloc; + } + }; + + /** + * 20.7.9, the default allocator + */ + + template + class allocator; + + template<> + class allocator + { + public: + using pointer = void*; + using const_pointer = const void*; + using value_type = void; + + template + struct rebind + { + using other = allocator; + }; + }; + + template + T* addressof(T& x) noexcept; + + template + class allocator + { + public: + using size_type = size_t; + using difference_type = ptrdiff_t; + using pointer = T*; + using const_pointer = const T*; + using reference = T&; + using const_reference = const T&; + using value_type = T; + + template + struct rebind + { + using other = allocator; + }; + + using propagate_on_container_move_assignment = true_type; + using is_always_equal = true_type; + + allocator() noexcept = default; + + allocator(const allocator&) noexcept = default; + + template + allocator(const allocator&) noexcept + { /* DUMMY BODY */ } + + ~allocator() = default; + + pointer address(reference x) const noexcept + { + return addressof(x); + } + + const_pointer address(const_reference x) const noexcept + { + return addressof(x); + } + + pointer allocate(size_type n, allocator::const_pointer = 0) + { + return static_cast(::operator new(n * sizeof(value_type))); + } + + void deallocate(pointer ptr, size_type n) + { + ::operator delete(ptr, n); + } + + size_type max_size() const noexcept + { + return numeric_limits::max(); + } + + template + void construct(U* ptr, Args&&... args) + { + ::new((void*)ptr) U(forward(args)...); + } + + template + void destroy(U* ptr) + { + ptr->~U(); + } + }; + + template + bool operator==(const allocator&, const allocator&) noexcept + { + return true; + } + + template + bool operator!=(const allocator&, const allocator&) noexcept + { + return false; + } +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/misc.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/misc.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/misc.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_MISC +#define LIBCPP_BITS_MEMORY_MISC + +#include +#include +#include +#include + +namespace std +{ + /** + * 20.7.10, raw storage iterator: + */ + + template + class raw_storage_iterator: public iterator + { + public: + explicit raw_storage_iterator(OutputIterator it) + : it_{it} + { /* DUMMY BODY */ } + + raw_storage_iterator& operator*() + { + return *this; + } + + raw_storage_iterator& operator=(const T& element) + { + new(it_) T{element}; + + return *this; + } + + raw_storage_iterator& operator++() + { + ++it_; + + return *this; + } + + raw_storage_iterator operator++(int) + { + return raw_storage_iterator{it_++}; + } + + private: + OutputIterator it_; + }; + + /** + * 20.7.11, temporary buffers: + */ + + template + pair get_temporary_buffer(ptrdiff_t n) noexcept + { + T* res{}; + + while (n > 0) + { + res = (T*)malloc(n * sizeof(T)); + + if (res) + return make_pair(res, n); + + --n; + } + + return make_pair(nullptr, ptrdiff_t{}); + } + + template + void return_temporary_buffer(T* ptr) + { + free(ptr); + } + + /** + * 20.7.12, specialized algorithms: + */ + + template + struct iterator_traits; + + template + ForwardIterator unitialized_copy( + InputIterator first, InputIterator last, + ForwardIterator result + ) + { + for (; first != last; ++first, ++result) + ::new (static_cast(&*result)) typename iterator_traits::value_type(*first); + + return result; + } + + template + ForwardIterator unitialized_copy_n( + InputIterator first, Size n, ForwardIterator result + ) + { + for (; n > 0; ++first, --n, ++result) + ::new (static_cast(&*result)) typename iterator_traits::value_type(*first); + + return result; + } + + template + void unitialized_fill( + ForwardIterator first, ForwardIterator last, const T& x + ) + { + for (; first != last; ++first) + ::new (static_cast(&*first)) typename iterator_traits::value_type(x); + } + + template + ForwardIterator unitialized_fill_n( + ForwardIterator first, Size n, const T& x + ) + { + for (; n > 0; ++first, --n) + ::new (static_cast(&*first)) typename iterator_traits::value_type(x); + + return first; + } +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/owner_less.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/owner_less.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/owner_less.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_OWNER_LESS +#define LIBCPP_BITS_MEMORY_OWNER_LESS + +#include <__bits/memory/shared_ptr.hpp> +#include <__bits/memory/weak_ptr.hpp> + +namespace std +{ + /** + * 20.8.2.4, class template owner_less: + */ + + template + struct owner_less; + + template + struct owner_less> + { + using retult_type = bool; + using first_argument_type = shared_ptr; + using second_argument_type = shared_ptr; + + bool operator()(const shared_ptr& lhs, const shared_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + + bool operator()(const shared_ptr& lhs, const weak_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + + bool operator()(const weak_ptr& lhs, const shared_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + }; + + template + struct owner_less> + { + using retult_type = bool; + using first_argument_type = weak_ptr; + using second_argument_type = weak_ptr; + + bool operator()(const weak_ptr& lhs, const weak_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + + bool operator()(const shared_ptr& lhs, const weak_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + + bool operator()(const weak_ptr& lhs, const shared_ptr& rhs) const + { + return lhs.owner_before(rhs); + } + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/pointer_traits.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/pointer_traits.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/pointer_traits.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_POINTER_TRAITS +#define LIBCPP_BITS_MEMORY_POINTER_TRAITS + +#include +#include <__bits/memory/addressof.hpp> +#include <__bits/memory/type_getters.hpp> +#include + +namespace std +{ + /** + * 20.7.3, pointer traits: + */ + + template + struct pointer_traits + { + using pointer = Ptr; + using element_type = typename aux::ptr_get_element_type::type; + using difference_type = typename aux::ptr_get_difference_type::type; + + template + using rebind = typename aux::ptr_get_rebind::type; + + static pointer pointer_to( // If is_void_t, this type is unspecified. + conditional_t, char, element_type&> x + ) + { + return Ptr::pointer_to(x); + } + }; + + template + struct pointer_traits + { + using pointer = T*; + using element_type = T; + using difference_type = ptrdiff_t; + + template + using rebind = U*; + + static pointer pointer_to( + conditional_t, char, element_type&> x + ) + { + return std::addressof(x); + } + }; + + /** + * 20.7.4, pointer safety: + */ + + // TODO: implement + + /** + * 20.7.5, align: + */ + + // TODO: implement +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/shared_payload.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/shared_payload.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/shared_payload.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_SHARED_PAYLOAD +#define LIBCPP_BITS_MEMORY_SHARED_PAYLOAD + +#include +#include + +namespace std +{ + template + struct default_delete; + + struct allocator_arg_t; +} + +namespace std::aux +{ + /** + * At the moment we do not have atomics, change this + * to std::atomic once we do. + */ + using refcount_t = long; + + /** + * This allows us to construct shared_ptr from + * a payload pointer in make_shared etc. + */ + struct payload_tag_t + { /* DUMMY BODY */ }; + + inline constexpr payload_tag_t payload_tag{}; + + template + void use_payload_deleter(D* deleter, T* data) + { + if (deleter) + (*deleter)(data); + } + + template + class shared_payload_base + { + public: + virtual void destroy() = 0; + virtual T* get() const noexcept = 0; + + virtual uint8_t* deleter() const noexcept = 0; + + virtual void increment() noexcept = 0; + virtual void increment_weak() noexcept = 0; + virtual bool decrement() noexcept = 0; + virtual bool decrement_weak() noexcept = 0; + virtual refcount_t refs() const noexcept = 0; + virtual refcount_t weak_refs() const noexcept = 0; + virtual bool expired() const noexcept = 0; + virtual shared_payload_base* lock() noexcept = 0; + + virtual ~shared_payload_base() = default; + }; + + template> + class shared_payload: public shared_payload_base + { + public: + shared_payload(T* ptr, D deleter = D{}) + : data_{ptr}, deleter_{deleter}, + refcount_{1}, weak_refcount_{1} + { /* DUMMY BODY */ } + + template + shared_payload(Args&&... args) + : data_{new T{forward(args)...}}, + deleter_{}, refcount_{1}, weak_refcount_{1} + { /* DUMMY BODY */ } + + template + shared_payload(allocator_arg_t, Alloc alloc, Args&&... args) + : data_{alloc.allocate(1)}, + deleter_{}, refcount_{1}, weak_refcount_{1} + { + alloc.construct(data_, forward(args)...); + } + + template + shared_payload(D deleter, Alloc alloc, Args&&... args) + : data_{alloc.allocate(1)}, + deleter_{deleter}, refcount_{1}, weak_refcount_{1} + { + alloc.construct(data_, forward(args)...); + } + + void destroy() override + { + if (refs() == 0) + { + if (data_) + { + deleter_(data_); + data_ = nullptr; + } + + if (weak_refs() == 0) + delete this; + } + } + + T* get() const noexcept override + { + return data_; + } + + uint8_t* deleter() const noexcept override + { + return (uint8_t*)&deleter_; + } + + void increment() noexcept override + { + __atomic_add_fetch(&refcount_, 1, __ATOMIC_ACQ_REL); + } + + void increment_weak() noexcept override + { + __atomic_add_fetch(&weak_refcount_, 1, __ATOMIC_ACQ_REL); + } + + bool decrement() noexcept override + { + if (__atomic_sub_fetch(&refcount_, 1, __ATOMIC_ACQ_REL) == 0) + { + /** + * First call to destroy() will delete the held object, + * so it doesn't matter what the weak_refcount_ is, + * but we added one and we need to remove it now. + */ + decrement_weak(); + + return true; + } + else + return false; + } + + bool decrement_weak() noexcept override + { + return __atomic_sub_fetch(&weak_refcount_, 1, __ATOMIC_ACQ_REL) == 0 && refs() == 0; + } + + refcount_t refs() const noexcept override + { + return __atomic_load_n(&refcount_, __ATOMIC_RELAXED); + } + + refcount_t weak_refs() const noexcept override + { + return __atomic_load_n(&weak_refcount_, __ATOMIC_RELAXED); + } + + bool expired() const noexcept override + { + return refs() == 0; + } + + shared_payload_base* lock() noexcept override + { + refcount_t rfs = refs(); + while (rfs != 0L) + { + if (__atomic_compare_exchange_n(&refcount_, &rfs, rfs + 1, + true, __ATOMIC_RELAXED, + __ATOMIC_RELAXED)) + { + return this; + } + } + + return nullptr; + } + + private: + T* data_; + D deleter_; + + /** + * We're using a trick where refcount_ > 0 + * means weak_refcount_ has 1 added to it, + * this makes it easier for weak_ptrs that + * can't decrement the weak_refcount_ to + * zero with shared_ptrs using this object. + */ + refcount_t refcount_; + refcount_t weak_refcount_; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/shared_ptr.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/shared_ptr.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/shared_ptr.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,646 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_SHARED_PTR +#define LIBCPP_BITS_MEMORY_SHARED_PTR + +#include +#include <__bits/functional/arithmetic_operations.hpp> +#include <__bits/functional/hash.hpp> +#include <__bits/memory/allocator_arg.hpp> +#include <__bits/memory/shared_payload.hpp> +#include <__bits/memory/unique_ptr.hpp> +#include <__bits/trycatch.hpp> +#include + +namespace std +{ + template + class weak_ptr; + + /** + * 20.8.2.1, class bad_weak_ptr: + */ + + class bad_weak_ptr: public exception + { + public: + bad_weak_ptr() noexcept = default; + + const char* what() const noexcept override + { + return "std::bad_weak_ptr"; + } + }; + + /** + * 20.8.2.2, class template shared_ptr: + */ + + template + class shared_ptr + { + public: + using element_type = T; + + /** + * 20.8.2.2.1, constructors: + */ + + constexpr shared_ptr() noexcept + : payload_{}, data_{} + { /* DUMMY BODY */ } + + template + explicit shared_ptr( + U* ptr, + enable_if_t>* = nullptr + ) + : payload_{}, data_{ptr} + { + try + { + payload_ = new aux::shared_payload{ptr}; + } + catch (const bad_alloc&) + { + delete ptr; + + throw; + } + } + + template + shared_ptr( + U* ptr, D deleter, + enable_if_t>* = nullptr + ) + : shared_ptr{} + { + try + { + payload_ = new aux::shared_payload{ptr, deleter}; + } + catch (const bad_alloc&) + { + deleter(ptr); + + throw; + } + } + + template + shared_ptr( + U* ptr, D deleter, A, + enable_if_t>* = nullptr + ) + : shared_ptr{} + { + try + { + payload_ = new aux::shared_payload{ptr, deleter}; + } + catch (const bad_alloc&) + { + deleter(ptr); + + throw; + } + } + + template + shared_ptr(nullptr_t ptr, D deleter) + : shared_ptr{} + { /* DUMMY BODY */ } + + template + shared_ptr(nullptr_t, D deleter, A) + : shared_ptr{} + { /* DUMMY BODY */ } + + template + shared_ptr( + const shared_ptr& other, element_type* ptr, + enable_if_t>* = nullptr + ) + : payload_{other.payload_}, data_{ptr} + { + if (payload_) + payload_->increment(); + } + + shared_ptr(const shared_ptr& other) + : payload_{other.payload_}, data_{other.data_} + { + if (payload_) + payload_->increment(); + } + + template + shared_ptr( + const shared_ptr& other, + enable_if_t>* = nullptr + ) + : payload_{other.payload_}, data_{other.data_} + { + if (payload_) + payload_->increment(); + } + + shared_ptr(shared_ptr&& other) + : payload_{move(other.payload_)}, data_{move(other.data_)} + { + other.payload_ = nullptr; + other.data_ = nullptr; + } + + template + shared_ptr( + shared_ptr&& other, + enable_if_t>* = nullptr + ) + : payload_{move(other.payload_)}, data_{move(other.data_)} + { + other.payload_ = nullptr; + other.data_ = nullptr; + } + + template + explicit shared_ptr( + const weak_ptr& other, + enable_if_t>* = nullptr + ) + : payload_{}, data_{} + { + if (other.expired()) + throw bad_weak_ptr{}; + + if (other.payload_) + { + payload_ = other.payload_->lock(); + data_ = payload_->get(); + } + } + + template + shared_ptr( + unique_ptr&& other, + enable_if_t< + is_convertible_v< + typename unique_ptr::pointer, + element_type* + > + >* = nullptr + ) // TODO: if D is a reference type, it should be ref(other.get_deleter()) + : shared_ptr{other.release(), other.get_deleter()} + { /* DUMMY BODY */ } + + constexpr shared_ptr(nullptr_t) noexcept + : shared_ptr{} + { /* DUMMY BODY */ } + + /** + * 20.8.2.2.2, destructor: + */ + + ~shared_ptr() + { + remove_payload_(); + } + + /** + * 20.8.2.2.3, assignment: + */ + + shared_ptr& operator=(const shared_ptr& rhs) noexcept + { + if (rhs.payload_) + rhs.payload_->increment(); + + remove_payload_(); + + payload_ = rhs.payload_; + data_ = rhs.data_; + + return *this; + } + + template + enable_if_t, shared_ptr>& + operator=(const shared_ptr& rhs) noexcept + { + if (rhs.payload_) + rhs.payload_->increment(); + + remove_payload_(); + + payload_ = rhs.payload_; + data_ = rhs.data_; + + return *this; + } + + shared_ptr& operator=(shared_ptr&& rhs) noexcept + { + shared_ptr{move(rhs)}.swap(*this); + + return *this; + } + + template + shared_ptr& operator=(shared_ptr&& rhs) noexcept + { + shared_ptr{move(rhs)}.swap(*this); + + return *this; + } + + template + shared_ptr& operator=(unique_ptr&& rhs) + { + shared_ptr{move(rhs)}.swap(*this); + + return *this; + } + + /** + * 20.8.2.2.4, modifiers: + */ + + void swap(shared_ptr& other) noexcept + { + std::swap(payload_, other.payload_); + std::swap(data_, other.data_); + } + + void reset() noexcept + { + shared_ptr{}.swap(*this); + } + + template + void reset(U* ptr) + { + shared_ptr{ptr}.swap(*this); + } + + template + void reset(U* ptr, D deleter) + { + shared_ptr{ptr, deleter}.swap(*this); + } + + template + void reset(U* ptr, D deleter, A alloc) + { + shared_ptr{ptr, deleter, alloc}.swap(*this); + } + + /** + * 20.8.2.2.5, observers: + */ + + element_type* get() const noexcept + { + return data_; + } + + enable_if_t, T&> operator*() const noexcept + { + return *data_; + } + + T* operator->() const noexcept + { + return get(); + } + + long use_count() const noexcept + { + if (payload_) + return payload_->refs(); + else + return 0L; + } + + bool unique() const noexcept + { + return use_count() == 1L; + } + + explicit operator bool() const noexcept + { + return get() != nullptr; + } + + template + bool owner_before(const shared_ptr& ptr) const + { + return payload_ < ptr.payload_; + } + + template + bool owner_before(const weak_ptr& ptr) const + { + return payload_ < ptr.payload_; + } + + private: + aux::shared_payload_base* payload_; + element_type* data_; + + shared_ptr(aux::payload_tag_t, aux::shared_payload_base* payload) + : payload_{payload}, data_{payload->get()} + { /* DUMMY BODY */ } + + void remove_payload_() + { + if (payload_) + { + auto res = payload_->decrement(); + if (res) + payload_->destroy(); + + payload_ = nullptr; + } + + if (data_) + data_ = nullptr; + } + + template + friend shared_ptr make_shared(Args&&...); + + template + friend shared_ptr allocate_shared(const A&, Args&&...); + + template + D* get_deleter(const shared_ptr&) noexcept; + + template + friend class weak_ptr; + }; + + /** + * 20.8.2.2.6, shared_ptr creation: + * Note: According to the standard, these two functions + * should perform at most one memory allocation + * (should, don't have to :P). It might be better + * to create payloads that embed the type T to + * perform this optimization. + */ + + template + shared_ptr make_shared(Args&&... args) + { + return shared_ptr{ + aux::payload_tag, + new aux::shared_payload{forward(args)...} + }; + } + + template + shared_ptr allocate_shared(const A& alloc, Args&&... args) + { + return shared_ptr{ + aux::payload_tag, + new aux::shared_payload{allocator_arg, A{alloc}, forward(args)...} + }; + } + + /** + * 20.8.2.2.7, shared_ptr comparisons: + */ + + template + bool operator==(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return lhs.get() == rhs.get(); + } + + template + bool operator!=(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return !(lhs == rhs); + } + + template + bool operator<(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return less>{}(lhs.get(), rhs.get()); + } + + template + bool operator>(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return rhs < lhs; + } + + template + bool operator<=(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return !(rhs < lhs); + } + + template + bool operator>=(const shared_ptr& lhs, const shared_ptr& rhs) noexcept + { + return !(lhs < rhs); + } + + template + bool operator==(const shared_ptr& lhs, nullptr_t) noexcept + { + return !lhs; + } + + template + bool operator==(nullptr_t, const shared_ptr& rhs) noexcept + { + return !rhs; + } + + template + bool operator!=(const shared_ptr& lhs, nullptr_t) noexcept + { + return (bool)lhs; + } + + template + bool operator!=(nullptr_t, const shared_ptr& rhs) noexcept + { + return (bool)rhs; + } + + template + bool operator<(const shared_ptr& lhs, nullptr_t) noexcept + { + return less{}(lhs.get(), nullptr); + } + + template + bool operator<(nullptr_t, const shared_ptr& rhs) noexcept + { + return less{}(nullptr, rhs.get()); + } + + template + bool operator>(const shared_ptr& lhs, nullptr_t) noexcept + { + return nullptr < lhs; + } + + template + bool operator>(nullptr_t, const shared_ptr& rhs) noexcept + { + return rhs < nullptr; + } + + template + bool operator<=(const shared_ptr& lhs, nullptr_t) noexcept + { + return !(nullptr < lhs); + } + + template + bool operator<=(nullptr_t, const shared_ptr& rhs) noexcept + { + return !(rhs < nullptr); + } + + template + bool operator>=(const shared_ptr& lhs, nullptr_t) noexcept + { + return !(lhs < nullptr); + } + + template + bool operator>=(nullptr_t, const shared_ptr& rhs) noexcept + { + return !(nullptr < rhs); + } + + /** + * 20.8.2.2.8, shared_ptr specialized algorithms: + */ + + template + void swap(shared_ptr& lhs, shared_ptr& rhs) noexcept + { + lhs.swap(rhs); + } + + /** + * 20.8.2.2.9, shared_ptr casts: + */ + + template + shared_ptr static_pointer_cast(const shared_ptr& ptr) noexcept + { + if (!ptr) + return shared_ptr{}; + + return shared_ptr{ + ptr, static_cast(ptr.get()) + }; + } + + template + shared_ptr dynamic_pointer_cast(const shared_ptr& ptr) noexcept + { + if (auto res = dynamic_cast(ptr.get())) + return shared_ptr{ptr, res}; + else + return shared_ptr{}; + } + + template + shared_ptr const_pointer_cast(const shared_ptr& ptr) noexcept + { + if (!ptr) + return shared_ptr{}; + + return shared_ptr{ + ptr, const_cast(ptr.get()) + }; + } + + /** + * 20.8.2.2.10, shared_ptr get_deleter: + */ + + template + D* get_deleter(const shared_ptr& ptr) noexcept + { + if (ptr.payload_) + return static_cast(ptr.payload_->deleter()); + else + return nullptr; + } + + /** + * 20.8.2.2.11, shared_ptr I/O: + */ + + template + basic_ostream& operator<<(basic_ostream& os, + const shared_ptr& ptr) + { + return os << ptr.get(); + } + + /** + * 20.8.2.5, class template enable_shared_from_this: + */ + + // TODO: implement + + /** + * 20.8.2.6, shared_ptr atomic access + */ + + // TODO: implement + + /** + * 20.8.2.7, smart pointer hash support: + */ + + template + struct hash> + { + size_t operator()(const shared_ptr& ptr) const noexcept + { + return hash{}(ptr.get()); + } + + using argument_type = shared_ptr; + using result_type = size_t; + }; +} + +#endif Index: uspace/lib/cpp/include/__bits/memory/type_getters.hpp =================================================================== --- uspace/lib/cpp/include/__bits/memory/type_getters.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) +++ uspace/lib/cpp/include/__bits/memory/type_getters.hpp (revision 7bbf91e6ed519996e55429154b0d7d21549dcf14) @@ -0,0 +1,271 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_BITS_MEMORY_TYPE_GETTERS +#define LIBCPP_BITS_MEMORY_TYPE_GETTERS + +/** + * Allocator and pointer traits require us to provide + * conditional typedefs based on whether the wrapped + * allocator contains them or not. To avoid unnecessary + * code clutter in , we moved them to their + * separate header (though note that these metafunctions + * have no use outside of ). + */ + +#include +#include <__bits/aux.hpp> +#include + +namespace std +{ + template + struct pointer_traits; +} + +namespace std::aux +{ + /** + * Pointer traits: + */ + + template + struct ptr_get_element_type + { /* DUMMY BODY */ }; + + template + struct ptr_get_element_type> + : aux::type_is + { /* DUMMY BODY */ }; + + template