From a4753b7776d685fdc902dfe0ff96d35fa38dcf3d Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Tue, 13 Jun 2017 04:26:59 -0700 Subject: [PATCH] add constexpr_array and add Enum_traits; working on adding Enum_set --- src/util/constexpr_array.h | 206 ++++++++++++++++++++++++++++++++++++ src/util/enum.h | 211 +++++++++++++++++++++++++++++++++++++ 2 files changed, 417 insertions(+) create mode 100644 src/util/constexpr_array.h create mode 100644 src/util/enum.h diff --git a/src/util/constexpr_array.h b/src/util/constexpr_array.h new file mode 100644 index 0000000..14e62f7 --- /dev/null +++ b/src/util/constexpr_array.h @@ -0,0 +1,206 @@ +/* + * Copyright 2017 Jacob Lifshay + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + */ + +#ifndef UTIL_CONSTEXPR_ARRAY_H_ +#define UTIL_CONSTEXPR_ARRAY_H_ + +#include "is_swappable.h" +#include +#include +#include +#include + +namespace vulkan_cpu +{ +namespace util +{ +template +struct Constexpr_array +{ + T values[N]; + typedef T value_type; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + typedef T &reference; + typedef const T &const_reference; + typedef T *pointer; + typedef const T *const_pointer; + typedef T *iterator; + typedef const T *const_iterator; + typedef std::reverse_iterator reverse_iterator; + typedef std::reverse_iterator const_reverse_iterator; + constexpr T &at(std::size_t index) + { + if(index >= N) + throw std::out_of_range("Constexpr_array::at"); + return values[index]; + } + constexpr const T &at(std::size_t index) const + { + if(index >= N) + throw std::out_of_range("Constexpr_array::at"); + return values[index]; + } + constexpr T &operator[](std::size_t index) noexcept + { + return values[index]; + } + constexpr const T &operator[](std::size_t index) const noexcept + { + return values[index]; + } + constexpr T &front() noexcept + { + return values[0]; + } + constexpr const T &front() const noexcept + { + return values[0]; + } + constexpr T &back() noexcept + { + return values[N - 1]; + } + constexpr const T &back() const noexcept + { + return values[N - 1]; + } + constexpr T *data() noexcept + { + return values; + } + constexpr const T *data() const noexcept + { + return values; + } + constexpr iterator begin() noexcept + { + return values; + } + constexpr const_iterator begin() const noexcept + { + return values; + } + constexpr const_iterator cbegin() const noexcept + { + return values; + } + constexpr iterator end() noexcept + { + return values + N; + } + constexpr const_iterator end() const noexcept + { + return values + N; + } + constexpr const_iterator cend() const noexcept + { + return values + N; + } + constexpr reverse_iterator rbegin() noexcept + { + return reverse_iterator(end()); + } + constexpr const_reverse_iterator rbegin() const noexcept + { + return const_reverse_iterator(end()); + } + constexpr const_reverse_iterator crbegin() const noexcept + { + return const_reverse_iterator(end()); + } + constexpr reverse_iterator rend() noexcept + { + return reverse_iterator(begin()); + } + constexpr const_reverse_iterator rend() const noexcept + { + return const_reverse_iterator(begin()); + } + constexpr const_reverse_iterator crend() const noexcept + { + return const_reverse_iterator(begin()); + } + constexpr bool empty() const noexcept + { + return size() == 0; + } + constexpr std::size_t size() const noexcept + { + return N; + } + constexpr std::size_t max_size() const noexcept + { + return N; + } + constexpr void fill(const T &value) noexcept(std::is_nothrow_copy_assignable::value) + { + for(auto &i : values) + i = value; + } + constexpr void swap(Constexpr_array &other) noexcept(is_nothrow_swappable_v) + { + using std::swap; + for(std::size_t index = 0; index < size(); index++) + swap(values[index], other.values[index]); + } +}; + +template +constexpr void swap(Constexpr_array &a, + Constexpr_array &b) noexcept(is_nothrow_swappable_v) +{ + a.swap(b); +} + +template +constexpr T &get(Constexpr_array &v) noexcept +{ + static_assert(I < N, ""); + return v[I]; +} + +template +constexpr const T &get(const Constexpr_array &v) noexcept +{ + static_assert(I < N, ""); + return v[I]; +} + +template +constexpr const T &&get(const Constexpr_array &&v) noexcept +{ + static_assert(I < N, ""); + return std::move(v[I]); +} + +template +constexpr T &&get(Constexpr_array &&v) noexcept +{ + static_assert(I < N, ""); + return std::move(v[I]); +} +} +} + +#endif /* UTIL_CONSTEXPR_ARRAY_H_ */ diff --git a/src/util/enum.h b/src/util/enum.h new file mode 100644 index 0000000..09a923f --- /dev/null +++ b/src/util/enum.h @@ -0,0 +1,211 @@ +/* + * Copyright 2017 Jacob Lifshay + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + */ + +#ifndef UTIL_ENUM_H_ +#define UTIL_ENUM_H_ + +#include +#include +#include "constexpr_array.h" +#include "bitset.h" + +namespace vulkan_cpu +{ +namespace util +{ +template +void enum_traits_resolve_function(T) = delete; + +template +struct Enum_traits +{ +private: + typedef decltype(enum_traits_resolve_function(T())) base; + +public: + static constexpr std::size_t value_count = base::values.size(); + static constexpr Constexpr_array values = base::values; + typedef typename std::underlying_type::type underlying_type; + +private: + static constexpr bool is_compact_helper() noexcept + { + for(std::size_t i = 0; i < value_count; i++) + if(i + != static_cast(static_cast(values[i])) + - static_cast(static_cast(values.front()))) + return false; + return true; + } + +public: + static constexpr bool is_compact = is_compact_helper(); + +private: + template + static constexpr Constexpr_array, N> sort_value_index_map( + const std::pair *value_index_map) noexcept + { + // uses merge sort algorithm + if(N == 0) + return {}; + Constexpr_array, N> retval{}; + if(N == 1) + { + retval[0] = value_index_map[0]; + return; + } + + // split + constexpr std::size_t split_index = N2 / 2; + constexpr std::size_t part1_size = split_index; + constexpr std::size_t part2_size = N2 - part1_size; + auto part1 = sort_value_index_map(value_index_map); + auto part2 = sort_value_index_map(value_index_map + split_index); + + // merge, preserving order of equal values + std::size_t part1_index = 0; + std::size_t part2_index = 0; + std::size_t retval_index = 0; + while(part1_index < part1_size && part2_index < part2_size) + { + // we want to copy from part1 if values are equal + if(static_cast(std::get<0>(part2[part2_index])) + < static_cast(std::get<0>(part1[part1_index]))) + retval[retval_index++] = part2[part2_index++]; + else + retval[retval_index++] = part1[part1_index++]; + } + while(part1_index < part1_size) + retval[retval_index++] = part1[part1_index++]; + while(part2_index < part2_size) + retval[retval_index++] = part2[part2_index++]; + return retval; + } + static constexpr Constexpr_array, value_count> + make_sorted_value_index_map() noexcept + { + Constexpr_array, N> retval{}; + for(std::size_t i = 0; i < value_count; i++) + retval[i] = {values[i], i}; + retval = sort_value_index_map(retval.data()); + return retval; + } + +public: + static constexpr Constexpr_array, value_count> + sorted_value_index_map = make_sorted_value_index_map(); + static constexpr std::size_t npos = -1; + /** find first occurrence of value in values and return index if found, otherwise return npos */ + static constexpr std::size_t find_value(T value) noexcept + { + std::size_t retval{}; + constexpr std::size_t binary_search_transition = 8; + if(is_compact) + { + retval = static_cast(static_cast(value)) + - static_cast(static_cast(values.front())); + } + else if(value_count < 8) + { + retval = -1; + for(std::size_t i = 0; i < value_count; i++) + { + if(values[i] == value) + { + retval = i; + break; + } + } + } + else + { + retval = 0; + std::size_t count = value_count; + while(count != 0) + { + std::size_t step = count / 2; + if(static_cast(values[retval + step]) + < static_cast(value)) + { + retval += step + 1; + count -= step + 1; + } + else + { + count = step; + } + } + } + if(retval >= value_count) + return npos; + return retval; + } +}; + +template +constexpr std::size_t Enum_traits::value_count; + +template +constexpr Constexpr_array::value_count> Enum_traits::values; + +template +constexpr bool Enum_traits::is_compact; + +template +constexpr Constexpr_array, Enum_traits::value_count> + Enum_traits::sorted_value_index_map; + +template +constexpr std::size_t Enum_traits::npos; + +namespace detail +{ +template +struct Default_enum_traits +{ + static constexpr Constexpr_array values = {{Values...}}; +}; + +template +static constexpr Enum_values Default_enum_traits::values; +#define vulkan_cpu_util_generate_enum_traits(...) \ + ::vulkan_cpu::util::detail::Default_enum_traits<__VA_ARGS__> enum_traits_resolve_function(Enum); +} + +template +class Enum_set +{ +private: + util::bitset::value_count> bits; + +public: + constexpr enum_set() noexcept : bits(0) + { + } +#warning finish +}; +} +} + +#endif /* UTIL_ENUM_H_ */ -- 2.30.2