summaryrefslogtreecommitdiff
path: root/kernel/lib/libcxx/include/__algorithm
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/lib/libcxx/include/__algorithm')
-rw-r--r--kernel/lib/libcxx/include/__algorithm/bound.h89
-rw-r--r--kernel/lib/libcxx/include/__algorithm/comparison.h75
-rw-r--r--kernel/lib/libcxx/include/__algorithm/copy.h53
-rw-r--r--kernel/lib/libcxx/include/__algorithm/fill.h30
-rw-r--r--kernel/lib/libcxx/include/__algorithm/find.h41
-rw-r--r--kernel/lib/libcxx/include/__algorithm/for_each.h31
-rw-r--r--kernel/lib/libcxx/include/__algorithm/minmax.h76
-rw-r--r--kernel/lib/libcxx/include/__algorithm/sort.h62
8 files changed, 457 insertions, 0 deletions
diff --git a/kernel/lib/libcxx/include/__algorithm/bound.h b/kernel/lib/libcxx/include/__algorithm/bound.h
new file mode 100644
index 0000000..560104b
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/bound.h
@@ -0,0 +1,89 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_BOUND_H
+#define _LIBBASTION_ALGORITHM_BOUND_H
+
+#include <__config>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _ForwardIt, class _Tp>
+_LIBBASTION_NODISCARD constexpr _ForwardIt lower_bound(_ForwardIt __first, _ForwardIt __last, const _Tp& __val) {
+ auto __len = __last - __first;
+ while (__len > 0) {
+ auto __half = __len / 2;
+ auto __mid = __first;
+ __mid += __half;
+ if (*__mid < __val) {
+ __first = __mid;
+ ++__first;
+ __len -= __half + 1;
+ } else {
+ __len = __half;
+ }
+ }
+ return __first;
+}
+
+template<class _ForwardIt, class _Tp, class _Compare>
+_LIBBASTION_NODISCARD constexpr _ForwardIt lower_bound(_ForwardIt __first, _ForwardIt __last, const _Tp& __val, _Compare __comp) {
+ auto __len = __last - __first;
+ while (__len > 0) {
+ auto __half = __len / 2;
+ auto __mid = __first;
+ __mid += __half;
+ if (__comp(*__mid, __val)) {
+ __first = __mid;
+ ++__first;
+ __len -= __half + 1;
+ } else {
+ __len = __half;
+ }
+ }
+ return __first;
+}
+
+template<class _ForwardIt, class _Tp>
+_LIBBASTION_NODISCARD constexpr _ForwardIt upper_bound(_ForwardIt __first, _ForwardIt __last, const _Tp& __val) {
+ auto __len = __last - __first;
+ while (__len > 0) {
+ auto __half = __len / 2;
+ auto __mid = __first;
+ __mid += __half;
+ if (!(__val < *__mid)) {
+ __first = __mid;
+ ++__first;
+ __len -= __half + 1;
+ } else {
+ __len = __half;
+ }
+ }
+ return __first;
+}
+
+template<class _ForwardIt, class _Tp, class _Compare>
+_LIBBASTION_NODISCARD constexpr _ForwardIt upper_bound(_ForwardIt __first, _ForwardIt __last, const _Tp& __val, _Compare __comp) {
+ auto __len = __last - __first;
+ while (__len > 0) {
+ auto __half = __len / 2;
+ auto __mid = __first;
+ __mid += __half;
+ if (!__comp(__val, *__mid)) {
+ __first = __mid;
+ ++__first;
+ __len -= __half + 1;
+ } else {
+ __len = __half;
+ }
+ }
+ return __first;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_BOUND_H
diff --git a/kernel/lib/libcxx/include/__algorithm/comparison.h b/kernel/lib/libcxx/include/__algorithm/comparison.h
new file mode 100644
index 0000000..8c8799c
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/comparison.h
@@ -0,0 +1,75 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_COMPARISON_H
+#define _LIBBASTION_ALGORITHM_COMPARISON_H
+
+#include <__config>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _InputIt1, class _InputIt2>
+_LIBBASTION_NODISCARD constexpr bool equal(_InputIt1 __first1, _InputIt1 __last1, _InputIt2 __first2) {
+ for (; __first1 != __last1; ++__first1, ++__first2)
+ if (!(*__first1 == *__first2))
+ return false;
+ return true;
+}
+
+template<class _InputIt1, class _InputIt2, class _BinPred>
+_LIBBASTION_NODISCARD constexpr bool equal(_InputIt1 __first1, _InputIt1 __last1, _InputIt2 __first2, _BinPred __pred) {
+ for (; __first1 != __last1; ++__first1, ++__first2)
+ if (!__pred(*__first1, *__first2))
+ return false;
+ return true;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr bool all_of(_InputIt __first, _InputIt __last, _Pred __pred) {
+ for (; __first != __last; ++__first)
+ if (!__pred(*__first))
+ return false;
+ return true;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr bool any_of(_InputIt __first, _InputIt __last, _Pred __pred) {
+ for (; __first != __last; ++__first)
+ if (__pred(*__first))
+ return true;
+ return false;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr bool none_of(_InputIt __first, _InputIt __last, _Pred __pred) {
+ for (; __first != __last; ++__first)
+ if (__pred(*__first))
+ return false;
+ return true;
+}
+
+template<class _InputIt, class _Tp>
+_LIBBASTION_NODISCARD constexpr auto count(_InputIt __first, _InputIt __last, const _Tp& __val) {
+ decltype(__last - __first) __ret = 0;
+ for (; __first != __last; ++__first)
+ if (*__first == __val)
+ ++__ret;
+ return __ret;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr auto count_if(_InputIt __first, _InputIt __last, _Pred __pred) {
+ decltype(__last - __first) __ret = 0;
+ for (; __first != __last; ++__first)
+ if (__pred(*__first))
+ ++__ret;
+ return __ret;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_COMPARISON_H
diff --git a/kernel/lib/libcxx/include/__algorithm/copy.h b/kernel/lib/libcxx/include/__algorithm/copy.h
new file mode 100644
index 0000000..e4251f6
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/copy.h
@@ -0,0 +1,53 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_COPY_H
+#define _LIBBASTION_ALGORITHM_COPY_H
+
+#include <__config>
+#include <__utility/move.h>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _InputIt, class _OutputIt>
+constexpr _OutputIt copy(_InputIt __first, _InputIt __last, _OutputIt __d_first) {
+ for (; __first != __last; ++__first, ++__d_first)
+ *__d_first = *__first;
+ return __d_first;
+}
+
+template<class _InputIt, class _Size, class _OutputIt>
+constexpr _OutputIt copy_n(_InputIt __first, _Size __count, _OutputIt __result) {
+ for (_Size __i = 0; __i < __count; ++__i, ++__first, ++__result)
+ *__result = *__first;
+ return __result;
+}
+
+template<class _InputIt, class _OutputIt>
+constexpr _OutputIt copy_backward(_InputIt __first, _InputIt __last, _OutputIt __d_last) {
+ while (__first != __last)
+ *(--__d_last) = *(--__last);
+ return __d_last;
+}
+
+template<class _InputIt, class _OutputIt>
+constexpr _OutputIt move(_InputIt __first, _InputIt __last, _OutputIt __d_first) {
+ for (; __first != __last; ++__first, ++__d_first)
+ *__d_first = std::move(*__first);
+ return __d_first;
+}
+
+template<class _InputIt, class _OutputIt>
+constexpr _OutputIt move_backward(_InputIt __first, _InputIt __last, _OutputIt __d_last) {
+ while (__first != __last)
+ *(--__d_last) = std::move(*(--__last));
+ return __d_last;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_COPY_H
diff --git a/kernel/lib/libcxx/include/__algorithm/fill.h b/kernel/lib/libcxx/include/__algorithm/fill.h
new file mode 100644
index 0000000..be09b1c
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/fill.h
@@ -0,0 +1,30 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_FILL_H
+#define _LIBBASTION_ALGORITHM_FILL_H
+
+#include <__config>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _ForwardIt, class _Tp>
+constexpr void fill(_ForwardIt __first, _ForwardIt __last, const _Tp& __val) {
+ for (; __first != __last; ++__first)
+ *__first = __val;
+}
+
+template<class _OutputIt, class _Size, class _Tp>
+constexpr _OutputIt fill_n(_OutputIt __first, _Size __count, const _Tp& __val) {
+ for (_Size __i = 0; __i < __count; ++__i, ++__first)
+ *__first = __val;
+ return __first;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_FILL_H
diff --git a/kernel/lib/libcxx/include/__algorithm/find.h b/kernel/lib/libcxx/include/__algorithm/find.h
new file mode 100644
index 0000000..c47b914
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/find.h
@@ -0,0 +1,41 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_FIND_H
+#define _LIBBASTION_ALGORITHM_FIND_H
+
+#include <__config>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _InputIt, class _Tp>
+_LIBBASTION_NODISCARD constexpr _InputIt find(_InputIt __first, _InputIt __last, const _Tp& __val) {
+ for (; __first != __last; ++__first)
+ if (*__first == __val)
+ return __first;
+ return __last;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr _InputIt find_if(_InputIt __first, _InputIt __last, _Pred __pred) {
+ for (; __first != __last; ++__first)
+ if (__pred(*__first))
+ return __first;
+ return __last;
+}
+
+template<class _InputIt, class _Pred>
+_LIBBASTION_NODISCARD constexpr _InputIt find_if_not(_InputIt __first, _InputIt __last, _Pred __pred) {
+ for (; __first != __last; ++__first)
+ if (!__pred(*__first))
+ return __first;
+ return __last;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_FIND_H
diff --git a/kernel/lib/libcxx/include/__algorithm/for_each.h b/kernel/lib/libcxx/include/__algorithm/for_each.h
new file mode 100644
index 0000000..af9a762
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/for_each.h
@@ -0,0 +1,31 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_FOR_EACH_H
+#define _LIBBASTION_ALGORITHM_FOR_EACH_H
+
+#include <__config>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _InputIt, class _UnaryFunc>
+constexpr _UnaryFunc for_each(_InputIt __first, _InputIt __last, _UnaryFunc __f) {
+ for (; __first != __last; ++__first)
+ __f(*__first);
+ return __f;
+}
+
+template<class _InputIt, class _Size, class _UnaryFunc>
+constexpr _InputIt for_each_n(_InputIt __first, _Size __n, _UnaryFunc __f) {
+ for (_Size __i = 0; __i < __n; ++__first, ++__i)
+ __f(*__first);
+ return __first;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_FOR_EACH_H
diff --git a/kernel/lib/libcxx/include/__algorithm/minmax.h b/kernel/lib/libcxx/include/__algorithm/minmax.h
new file mode 100644
index 0000000..b28d66c
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/minmax.h
@@ -0,0 +1,76 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_MINMAX_H
+#define _LIBBASTION_ALGORITHM_MINMAX_H
+
+#include <__config>
+#include <initializer_list>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+// ── min ─────────────────────────────────────────────────────────────────────
+
+template<class _Tp>
+_LIBBASTION_NODISCARD constexpr const _Tp& min(const _Tp& __a, const _Tp& __b) {
+ return (__b < __a) ? __b : __a;
+}
+
+template<class _Tp, class _Compare>
+_LIBBASTION_NODISCARD constexpr const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
+ return __comp(__b, __a) ? __b : __a;
+}
+
+template<class _Tp>
+_LIBBASTION_NODISCARD constexpr _Tp min(initializer_list<_Tp> __il) {
+ const _Tp* __first = __il.begin();
+ const _Tp* __last = __il.end();
+ const _Tp* __result = __first;
+ for (++__first; __first != __last; ++__first)
+ if (*__first < *__result)
+ __result = __first;
+ return *__result;
+}
+
+// ── max ─────────────────────────────────────────────────────────────────────
+
+template<class _Tp>
+_LIBBASTION_NODISCARD constexpr const _Tp& max(const _Tp& __a, const _Tp& __b) {
+ return (__a < __b) ? __b : __a;
+}
+
+template<class _Tp, class _Compare>
+_LIBBASTION_NODISCARD constexpr const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
+ return __comp(__a, __b) ? __b : __a;
+}
+
+template<class _Tp>
+_LIBBASTION_NODISCARD constexpr _Tp max(initializer_list<_Tp> __il) {
+ const _Tp* __first = __il.begin();
+ const _Tp* __last = __il.end();
+ const _Tp* __result = __first;
+ for (++__first; __first != __last; ++__first)
+ if (*__result < *__first)
+ __result = __first;
+ return *__result;
+}
+
+// ── clamp ───────────────────────────────────────────────────────────────────
+
+template<class _Tp>
+_LIBBASTION_NODISCARD constexpr const _Tp& clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) {
+ return (__v < __lo) ? __lo : (__hi < __v) ? __hi : __v;
+}
+
+template<class _Tp, class _Compare>
+_LIBBASTION_NODISCARD constexpr const _Tp& clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp) {
+ return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_MINMAX_H
diff --git a/kernel/lib/libcxx/include/__algorithm/sort.h b/kernel/lib/libcxx/include/__algorithm/sort.h
new file mode 100644
index 0000000..22c7b33
--- /dev/null
+++ b/kernel/lib/libcxx/include/__algorithm/sort.h
@@ -0,0 +1,62 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the BastionOS freestanding C++ standard library.
+//
+// Insertion sort — simple, stable, good for small arrays (typical in kernel).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBBASTION_ALGORITHM_SORT_H
+#define _LIBBASTION_ALGORITHM_SORT_H
+
+#include <__config>
+#include <__utility/move.h>
+#include <__utility/swap.h>
+
+_LIBBASTION_BEGIN_NAMESPACE_STD
+
+template<class _RandomIt>
+constexpr void sort(_RandomIt __first, _RandomIt __last) {
+ for (auto __i = __first; __i != __last; ++__i) {
+ auto __key = std::move(*__i);
+ auto __j = __i;
+ while (__j != __first) {
+ auto __prev = __j;
+ --__prev;
+ if (!(__key < *__prev)) break;
+ *__j = std::move(*__prev);
+ __j = __prev;
+ }
+ *__j = std::move(__key);
+ }
+}
+
+template<class _RandomIt, class _Compare>
+constexpr void sort(_RandomIt __first, _RandomIt __last, _Compare __comp) {
+ for (auto __i = __first; __i != __last; ++__i) {
+ auto __key = std::move(*__i);
+ auto __j = __i;
+ while (__j != __first) {
+ auto __prev = __j;
+ --__prev;
+ if (!__comp(__key, *__prev)) break;
+ *__j = std::move(*__prev);
+ __j = __prev;
+ }
+ *__j = std::move(__key);
+ }
+}
+
+template<class _BidirIt>
+constexpr void reverse(_BidirIt __first, _BidirIt __last) {
+ while (__first != __last && __first != --__last) {
+ using std::swap;
+ swap(*__first, *__last);
+ ++__first;
+ }
+}
+
+_LIBBASTION_END_NAMESPACE_STD
+
+#endif // _LIBBASTION_ALGORITHM_SORT_H
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-05 20:37:13 +0000