✨ Add ct_capacity

elbeno · elbeno · commit 3d33dfcdf212 · 2024-02-15T19:20:38.000-07:00
diff --git a/docs/index.adoc b/docs/index.adoc
@@ -22,7 +22,9 @@ include::cx_vector.adoc[]
 include::for_each_n_args.adoc[]
 include::function_traits.adoc[]
 include::functional.adoc[]
+include::intrusive_forward_list.adoc[]
 include::intrusive_list.adoc[]
+include::iterator.adoc[]
 include::memory.adoc[]
 include::optional.adoc[]
 include::panic.adoc[]
diff --git a/docs/intro.adoc b/docs/intro.adoc
@@ -48,7 +48,9 @@ The following headers are available:
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/for_each_n_args.hpp[`for_each_n_args.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/function_traits.hpp[`function_traits.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/functional.hpp[`functional.hpp`]
+* https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/intrusive_forward_list.hpp[`intrusive_forward_list.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/intrusive_list.hpp[`intrusive_list.hpp`]
+* https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/iterator.hpp[`iterator.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/memory.hpp[`memory.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/optional.hpp[`optional.hpp`]
 * https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/panic.hpp[`panic.hpp`]
diff --git a/docs/intrusive_forward_list.adoc b/docs/intrusive_forward_list.adoc
@@ -0,0 +1,30 @@
+
+== `intrusive_forward_list.hpp`
+
+`intrusive_forward_list` is a singly-linked list designed for use at compile-time or
+with static objects. It supports pushing and popping at the front or back, and
+removal from the middle.
+
+[source,cpp]
+----
+// A node in an intrusive_list must have a next pointer
+struct node {
+  node *next{};
+};
+
+stdx::intrusive_forward_list<node> l;
+
+node n1{};
+l.push_front(&n1);
+
+node n2{};
+l.push_back(&n2);
+
+node n3{};
+l.push_back(&n3);
+
+node* nf = l.pop_front();
+
+l.clear();
+bool b = l.empty();
+----
diff --git a/docs/intrusive_list.adoc b/docs/intrusive_list.adoc
@@ -25,6 +25,9 @@ node n3{};
 l.push_back(&n3);
 
 l.remove(&n2); // removal from the middle is constant-time
-l.pop_front();
-l.pop_back();
+node* nf = l.pop_front();
+node* nb = l.pop_back();
+
+l.clear();
+bool b = l.empty();
 ----
diff --git a/docs/iterator.adoc b/docs/iterator.adoc
@@ -0,0 +1,25 @@
+
+== `iterator.hpp`
+
+https://github.com/intel/cpp-std-extensions/blob/main/include/stdx/iterator.hpp[`iterator.hpp`]
+contains `ct_capacity`, a `constexpr` function that returns the capacity of a
+container which is known at compile-time.
+
+[source,cpp]
+----
+auto const a = std::array{1, 2, 3, 4};
+constexpr auto c = stdx::ct_capacity(a); // std::size_t{4}
+----
+
+`ct_capacity` can be called with:
+
+* `std::array`
+* `std::span` (unless it has `std::dynamic_extent`)
+* `stdx::span` (unless it has `stdx::dynamic_extent`)
+* `stdx::cx_map`
+* `stdx::cx_multimap`
+* `stdx::cx_queue`
+* `stdx::cx_set`
+* `stdx::cx_vector`
+
+`ct_capacity_v` is a corresponding variable template of type `std::size_t`.
diff --git a/include/stdx/cx_map.hpp b/include/stdx/cx_map.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <stdx/concepts.hpp>
+#include <stdx/iterator.hpp>
 #include <stdx/utility.hpp>
 
 #include <array>
@@ -126,5 +127,8 @@ template <typename Key, typename Value, std::size_t N> class cx_map {
         return 0u;
     }
 };
+
+template <typename K, typename V, std::size_t N>
+constexpr auto ct_capacity_v<cx_map<K, V, N>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/include/stdx/cx_multimap.hpp b/include/stdx/cx_multimap.hpp
@@ -2,6 +2,7 @@
 
 #include <stdx/cx_map.hpp>
 #include <stdx/cx_set.hpp>
+#include <stdx/iterator.hpp>
 
 #include <cstddef>
 #include <iterator>
@@ -99,5 +100,8 @@ class cx_multimap {
 
     constexpr auto clear() -> void { storage.clear(); }
 };
+
+template <typename K, typename V, std::size_t N, std::size_t M>
+constexpr auto ct_capacity_v<cx_multimap<K, V, N, M>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/include/stdx/cx_queue.hpp b/include/stdx/cx_queue.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <stdx/iterator.hpp>
 #include <stdx/panic.hpp>
 
 #include <array>
@@ -104,5 +105,8 @@ class cx_queue {
         return entry;
     }
 };
+
+template <typename T, std::size_t N, typename OP>
+constexpr auto ct_capacity_v<cx_queue<T, N, OP>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/include/stdx/cx_set.hpp b/include/stdx/cx_set.hpp
@@ -2,6 +2,7 @@
 
 #include <stdx/concepts.hpp>
 #include <stdx/cx_map.hpp>
+#include <stdx/iterator.hpp>
 
 #include <cstddef>
 
@@ -107,5 +108,8 @@ template <typename Key, std::size_t N> class cx_set {
 
 template <typename T, typename... Ts>
 cx_set(T, Ts...) -> cx_set<T, 1 + sizeof...(Ts)>;
+
+template <typename T, std::size_t N>
+constexpr auto ct_capacity_v<cx_set<T, N>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/include/stdx/cx_vector.hpp b/include/stdx/cx_vector.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <stdx/concepts.hpp>
+#include <stdx/iterator.hpp>
 
 #include <array>
 #include <cstddef>
@@ -167,5 +168,8 @@ template <std::size_t I, typename T, std::size_t N>
 auto get(cx_vector<T, N> const &v) -> decltype(auto) {
     return v.template get<I>();
 }
+
+template <typename T, std::size_t N>
+constexpr auto ct_capacity_v<cx_vector<T, N>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/include/stdx/iterator.hpp b/include/stdx/iterator.hpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <stdx/type_traits.hpp>
+
+#include <array>
+#include <cstddef>
+
+namespace stdx {
+inline namespace v1 {
+namespace detail {
+template <typename T> struct ct_capacity_fail {
+    static_assert(always_false_v<stdx::remove_cvref_t<T>>,
+                  "Type does not support compile-time capacity");
+};
+} // namespace detail
+
+template <typename T>
+constexpr auto ct_capacity_v = detail::ct_capacity_fail<T>{};
+
+template <typename T, std::size_t N>
+constexpr auto ct_capacity_v<std::array<T, N>> = N;
+
+template <typename T> constexpr auto ct_capacity(T &&) -> std::size_t {
+    return ct_capacity_v<remove_cvref_t<T>>;
+}
+} // namespace v1
+} // namespace stdx
+
+#if __has_include(<span>)
+#include <span>
+
+#if __cpp_lib_span >= 202002L
+namespace stdx {
+inline namespace v1 {
+template <typename T, std::size_t N>
+constexpr auto ct_capacity_v<std::span<T, N>> = N;
+
+template <typename T>
+constexpr auto ct_capacity_v<std::span<T, std::dynamic_extent>> =
+    detail::ct_capacity_fail<std::span<T, std::dynamic_extent>>{};
+} // namespace v1
+} // namespace stdx
+
+#endif
+#endif
diff --git a/include/stdx/span.hpp b/include/stdx/span.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <stdx/bit.hpp>
+#include <stdx/iterator.hpp>
 #include <stdx/memory.hpp>
 #include <stdx/type_traits.hpp>
 
@@ -262,5 +263,7 @@ span(std::array<T, N> const &) -> span<T const, N>;
 template <typename R>
 span(R &&) -> span<std::remove_reference_t<detail::range_reference_t<R>>>;
 
+template <typename T, std::size_t N>
+constexpr auto ct_capacity_v<span<T, N>> = N;
 } // namespace v1
 } // namespace stdx
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
@@ -32,6 +32,7 @@ add_tests(
     intrusive_list
     intrusive_list_properties
     is_constant_evaluated
+    iterator
     memory
     optional
     overload
diff --git a/test/fail/CMakeLists.txt b/test/fail/CMakeLists.txt
@@ -23,7 +23,12 @@ add_fail_tests(
 
 if(${CMAKE_CXX_STANDARD} GREATER_EQUAL 20)
     add_fail_tests(
-        tuple_index_out_of_bounds tuple_equality_mismatch
-        tuple_equality_with_element tuple_spaceship_mismatch
-        tuple_spaceship_with_element tuple_type_not_found)
+        dynamic_span_no_ct_capacity
+        dynamic_container_no_ct_capacity
+        tuple_index_out_of_bounds
+        tuple_equality_mismatch
+        tuple_equality_with_element
+        tuple_spaceship_mismatch
+        tuple_spaceship_with_element
+        tuple_type_not_found)
 endif()
diff --git a/test/fail/dynamic_container_no_ct_capacity.cpp b/test/fail/dynamic_container_no_ct_capacity.cpp
@@ -0,0 +1,10 @@
+#include <stdx/iterator.hpp>
+
+#include <vector>
+
+// EXPECT: Type does not support compile-time capacity
+
+auto main() -> int {
+    auto v = std::vector{1, 2, 3, 4};
+    constexpr auto c = stdx::ct_capacity(v);
+}
diff --git a/test/fail/dynamic_span_no_ct_capacity.cpp b/test/fail/dynamic_span_no_ct_capacity.cpp
@@ -0,0 +1,13 @@
+#include <stdx/iterator.hpp>
+
+#include <array>
+#include <iterator>
+#include <span>
+
+// EXPECT: Type does not support compile-time capacity
+
+auto main() -> int {
+    auto a = std::array<int, 4>{};
+    auto s = std::span{std::begin(a), std::end(a)};
+    constexpr auto c = stdx::ct_capacity(s);
+}
diff --git a/test/iterator.cpp b/test/iterator.cpp
@@ -0,0 +1,59 @@
+#include <stdx/cx_map.hpp>
+#include <stdx/cx_multimap.hpp>
+#include <stdx/cx_queue.hpp>
+#include <stdx/cx_set.hpp>
+#include <stdx/cx_vector.hpp>
+#include <stdx/iterator.hpp>
+#include <stdx/span.hpp>
+
+#include <array>
+
+#if __has_include(<span>)
+#include <span>
+#endif
+
+#include <catch2/catch_test_macros.hpp>
+
+TEST_CASE("compile-time capacity (std::array)", "[iterator]") {
+    std::array a{1, 2, 3, 4};
+    static_assert(stdx::ct_capacity(a) == 4u);
+}
+
+#if __cpp_lib_span >= 202002L
+TEST_CASE("compile-time capacity (std::span)", "[iterator]") {
+    std::array a{1, 2, 3, 4};
+    std::span s{a};
+    static_assert(stdx::ct_capacity(s) == 4u);
+}
+#endif
+
+TEST_CASE("compile-time capacity (stdx::span)", "[iterator]") {
+    std::array a{1, 2, 3, 4};
+    stdx::span s{a};
+    static_assert(stdx::ct_capacity(s) == 4u);
+}
+
+TEST_CASE("compile-time capacity (stdx::cx_map)", "[iterator]") {
+    stdx::cx_map<int, int, 4> m{};
+    static_assert(stdx::ct_capacity(m) == 4u);
+}
+
+TEST_CASE("compile-time capacity (stdx::cx_multimap)", "[iterator]") {
+    stdx::cx_multimap<int, int, 4, 5> m{};
+    static_assert(stdx::ct_capacity(m) == 4u);
+}
+
+TEST_CASE("compile-time capacity (stdx::cx_queue)", "[iterator]") {
+    stdx::cx_queue<int, 4> q{};
+    static_assert(stdx::ct_capacity(q) == 4u);
+}
+
+TEST_CASE("compile-time capacity (stdx::cx_set)", "[iterator]") {
+    stdx::cx_set<int, 4> s{};
+    static_assert(stdx::ct_capacity(s) == 4u);
+}
+
+TEST_CASE("compile-time capacity (stdx::cx_vector)", "[iterator]") {
+    stdx::cx_vector<int, 4> v{};
+    static_assert(stdx::ct_capacity(v) == 4u);
+}
