StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
list.hxx
Go to the documentation of this file.
1/*
2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
3 *
4 * This is the base for StormByte Suite libraries.
5 *
6 * StormByte original source is dual-licensed:
7 *
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
12 * any later version.
13 *
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
18 *
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
23 *
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
27 *
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
36 *
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
38 */
39
40#pragma once
41
42#include <StormByte/size.hxx>
47
48#include <cassert>
49#include <cstddef>
50#include <functional>
51#include <initializer_list>
52#include <iterator>
53#include <limits>
54#include <list>
55#include <ranges>
56#include <utility>
57
62namespace StormByte {
67 namespace Safe {
75 template<Type::SafeValue T>
77 private:
78 struct Link;
79 struct Node;
80
81 public:
82 using value_type = T;
83 using size_type = Size;
84 using difference_type = std::ptrdiff_t;
85 using reference = T&;
86 using const_reference = const T&;
87
95 template<bool IsConst>
96 class BasicIterator final {
97 using LinkType = std::conditional_t<IsConst, const Link, Link>;
98
99 public:
100 using iterator_category = std::bidirectional_iterator_tag;
101 using iterator_concept = std::bidirectional_iterator_tag;
102 using value_type = T;
103 using difference_type = std::ptrdiff_t;
104 using reference = std::conditional_t<IsConst, const T&, T&>;
105 using pointer = std::conditional_t<IsConst, const T*, T*>;
106 using StormByteSafeCursor = void;
107
111 BasicIterator() noexcept: m_link(nullptr) {}
112
117 template<bool OtherConst>
118 requires IsConst && (!OtherConst)
119 BasicIterator(const BasicIterator<OtherConst>& other) noexcept: m_link(other.m_link) {}
120
125 reference operator*() const noexcept { return static_cast<Node*>(const_cast<Link*>(m_link))->Value; }
126
131 pointer operator->() const noexcept { return &static_cast<Node*>(const_cast<Link*>(m_link))->Value; }
132
137 BasicIterator& operator++() noexcept { m_link = m_link->Next; return *this; }
138
143 BasicIterator operator++(int) noexcept { BasicIterator previous(*this); ++(*this); return previous; }
144
149 BasicIterator& operator--() noexcept { m_link = m_link->Prev; return *this; }
150
155 BasicIterator operator--(int) noexcept { BasicIterator previous(*this); --(*this); return previous; }
156
162 template<bool OtherConst>
163 bool operator==(const BasicIterator<OtherConst>& other) const noexcept { return m_link == other.m_link; }
164
165 private:
166 friend class List;
167 template<bool> friend class BasicIterator;
168
173 explicit BasicIterator(LinkType* link) noexcept: m_link(link) {}
174
175 LinkType* m_link;
176 };
177
180 using reverse_iterator = std::reverse_iterator<iterator>;
181 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
182
189 class node_type {
190 public:
194 node_type() noexcept = default;
195
199 node_type(const node_type&) = delete;
200
205 node_type(node_type&& other) noexcept: m_node(other.m_node) { other.m_node = nullptr; }
206
210 ~node_type() { reset(); }
211
216 node_type& operator=(const node_type&) = delete;
217
223 node_type& operator=(node_type&& other) noexcept {
224 if (this != &other) {
225 reset();
226 m_node = other.m_node;
227 other.m_node = nullptr;
228 }
229 return *this;
230 }
231
236 bool empty() const noexcept { return m_node == nullptr; }
237
242 explicit operator bool() const noexcept { return !empty(); }
243
248 T& value() { return m_node->Value; }
249
254 const T& value() const { return m_node->Value; }
255
260 void swap(node_type& other) noexcept { std::swap(m_node, other.m_node); }
261
262 private:
263 friend class List;
264
269 explicit node_type(Node* node) noexcept: m_node(node) {}
270
274 void reset() noexcept {
275 if (m_node == nullptr)
276 return;
277 m_node->Value.~T();
278 Heap::Free(m_node);
279 m_node = nullptr;
280 }
281
282 Node* m_node = nullptr;
283 };
284
288 List() noexcept;
289
295 explicit List(size_type count);
296
303 List(size_type count, const T& value);
304
310 List(const List& other);
311
316 List(List&& other) noexcept;
317
323 STORMBYTE_FORCE_INLINE explicit List(const std::list<T>& other): List() {
324 for (const T& value : other)
325 push_back(value);
326 }
327
333 STORMBYTE_FORCE_INLINE explicit List(std::list<T>&& other): List() {
334 for (T& value : other)
335 push_back(std::move(value));
336 other.clear();
337 }
338
345 template<std::ranges::input_range R>
346 requires std::convertible_to<std::ranges::range_reference_t<R>, T>
347 STORMBYTE_FORCE_INLINE explicit List(std::from_range_t, R&& range): List() {
348 insert_range(end(), std::forward<R>(range));
349 }
350
356 List(std::initializer_list<T> values);
357
361 ~List() noexcept;
362
369 List& operator=(const List& other);
370
376 List& operator=(List&& other) noexcept;
377
384 List& operator=(std::initializer_list<T> values);
385
392 void assign(size_type count, const T& value);
393
399 void assign(std::initializer_list<T> values);
400
407 template<std::ranges::input_range R>
408 requires std::convertible_to<std::ranges::range_reference_t<R>, T>
410 List replacement(std::from_range, std::forward<R>(range));
411 swap(replacement);
412 }
413
418 T& front() noexcept { assert(!empty()); return *begin(); }
419
424 const T& front() const noexcept { assert(!empty()); return *begin(); }
425
430 T& back() noexcept { assert(!empty()); return *std::prev(end()); }
431
436 const T& back() const noexcept { assert(!empty()); return *std::prev(end()); }
437
442 iterator begin() noexcept { return iterator(m_sentinel.Next); }
443
448 iterator end() noexcept { return iterator(&m_sentinel); }
449
454 const_iterator begin() const noexcept { return const_iterator(m_sentinel.Next); }
455
460 const_iterator end() const noexcept { return const_iterator(&m_sentinel); }
461
466 const_iterator cbegin() const noexcept { return begin(); }
467
472 const_iterator cend() const noexcept { return end(); }
473
478 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
479
484 reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
485
491
497
502 const_reverse_iterator crbegin() const noexcept { return rbegin(); }
503
508 const_reverse_iterator crend() const noexcept { return rend(); }
509
514 bool empty() const noexcept { return m_size == 0; }
515
520 size_type size() const noexcept { return m_size; }
521
526 size_type max_size() const noexcept { return std::numeric_limits<size_type>::max(); }
527
531 void clear() noexcept;
532
540 iterator insert(const_iterator position, const T& value);
541
549 iterator insert(const_iterator position, T&& value);
550
559 iterator insert(const_iterator position, size_type count, const T& value);
560
568 iterator insert(const_iterator position, std::initializer_list<T> values);
569
578 template<std::ranges::input_range R>
579 requires std::convertible_to<std::ranges::range_reference_t<R>, T>
581 iterator first(const_cast<Link*>(position.m_link));
582 bool started = false;
583 for (auto&& value : range) {
584 iterator inserted = insert(position, T(std::forward<decltype(value)>(value)));
585 if (!started) {
586 first = inserted;
587 started = true;
588 }
589 }
590 return first;
591 }
592
601 template<class... Args>
602 iterator emplace(const_iterator position, Args&&... args);
603
610
618
624 void push_front(const T& value);
625
631 void push_front(T&& value);
632
640 template<class... Args>
641 T& emplace_front(Args&&... args);
642
646 void pop_front() noexcept;
647
653 void push_back(const T& value);
654
660 void push_back(T&& value);
661
669 template<class... Args>
670 T& emplace_back(Args&&... args);
671
675 void pop_back() noexcept;
676
682 void resize(size_type count);
683
690 void resize(size_type count, const T& value);
691
696 void swap(List& other) noexcept;
697
703 void splice(const_iterator position, List& other) noexcept;
704
711 void splice(const_iterator position, List& other, const_iterator source) noexcept;
712
720 void splice(const_iterator position, List& other, const_iterator first, const_iterator last) noexcept;
721
728
736
741 void merge(List& other);
742
749 template<class Compare>
750 void merge(List& other, Compare compare);
751
757 size_type remove(const T& value);
758
765 template<class Predicate>
766 size_type remove_if(Predicate predicate);
767
771 void reverse() noexcept;
772
778
785 template<class Predicate>
786 size_type unique(Predicate predicate);
787
791 void sort();
792
798 template<class Compare>
799 void sort(Compare compare);
800
806 bool operator==(const List& other) const;
807
813 STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const List& other) const;
814
819 STORMBYTE_FORCE_INLINE explicit operator std::list<T>() const {
820 std::list<T> copied;
821 for (const T& value : *this)
822 copied.push_back(value);
823 return copied;
824 }
825
826 private:
830 struct Link {
831 Link* Next = nullptr;
832 Link* Prev = nullptr;
833 };
834
838 struct Node: Link {
839 T Value;
840
846 template<class... Args>
847 explicit Node(Args&&... args): Value(std::forward<Args>(args)...) {}
848 };
849
853 void ResetSentinel() noexcept;
854
862 template<class... Args>
863 Node* MakeNode(Args&&... args);
864
870 void LinkBefore(Link* position, Node* node) noexcept;
871
876 void Unlink(Node* node) noexcept;
877
881 void Destroy() noexcept;
882
883 Link m_sentinel{};
884 size_type m_size = 0;
885 };
886
893 template<Type::SafeValue T>
894 void swap(List<T>& left, List<T>& right) noexcept { left.swap(right); }
895 }
896
901 namespace Type {
906 template<SafeValue T>
907 requires IsSafe<T>::value
908 struct IsSafe<Safe::List<T>>: std::true_type {};
909
914 template<SafeValue T>
915 requires MaybeSafe<T>
916 struct IsMaybeSafe<Safe::List<T>>: std::true_type {};
917
922 template<SafeValue T>
923 struct IsSafeValue<Safe::List<T>>: std::true_type {};
924 }
925}
926
938extern template class STORMBYTE_PUBLIC StormByte::Safe::List<int>;
946
Bidirectional cursor over Base-owned list nodes.
Definition list.hxx:96
std::conditional_t< IsConst, const T &, T & > reference
Element reference.
Definition list.hxx:104
T value_type
Element type.
Definition list.hxx:102
BasicIterator & operator--() noexcept
Move to the previous element.
Definition list.hxx:149
std::ptrdiff_t difference_type
Iterator distance type.
Definition list.hxx:103
std::bidirectional_iterator_tag iterator_concept
C++20 iterator concept.
Definition list.hxx:101
BasicIterator operator--(int) noexcept
Move to the previous element.
Definition list.hxx:155
std::conditional_t< IsConst, const T *, T * > pointer
Element pointer.
Definition list.hxx:105
BasicIterator & operator++() noexcept
Advance to the next element.
Definition list.hxx:137
friend class BasicIterator
Definition list.hxx:167
std::bidirectional_iterator_tag iterator_category
Iterator category.
Definition list.hxx:100
reference operator*() const noexcept
Return the element stored in the node.
Definition list.hxx:125
BasicIterator() noexcept
Construct a singular iterator.
Definition list.hxx:111
BasicIterator operator++(int) noexcept
Advance to the next element.
Definition list.hxx:143
friend class List
Definition list.hxx:166
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one link pointer.
Definition list.hxx:106
pointer operator->() const noexcept
Access the element stored in the node.
Definition list.hxx:131
&&!OtherConst BasicIterator(const BasicIterator< OtherConst > &other) noexcept
Convert a mutable iterator to a const iterator.
Definition list.hxx:119
bool operator==(const BasicIterator< OtherConst > &other) const noexcept
Compare link identity.
Definition list.hxx:163
Owning handle to one extracted Base node.
Definition list.hxx:189
~node_type()
Destroy the owned node, if any.
Definition list.hxx:210
node_type & operator=(const node_type &)=delete
Copying a node handle is not supported.
void swap(node_type &other) noexcept
Exchange owned nodes.
Definition list.hxx:260
node_type & operator=(node_type &&other) noexcept
Take the node.
Definition list.hxx:223
friend class List
Definition list.hxx:263
T & value()
Return the owned element.
Definition list.hxx:248
node_type() noexcept=default
Construct an empty handle.
const T & value() const
Return the owned element.
Definition list.hxx:254
bool empty() const noexcept
Test whether the handle owns a node.
Definition list.hxx:236
Doubly linked list stored on Base's heap.
Definition list.hxx:76
size_type remove_if(Predicate predicate)
Erase every element for which predicate is true.
iterator end() noexcept
Return the past-the-end iterator.
Definition list.hxx:448
BasicIterator< true > const_iterator
Read-only iterator.
Definition list.hxx:179
const T & front() const noexcept
Return the first element.
Definition list.hxx:424
iterator insert(const_iterator position, const T &value)
Insert a copy of value before position.
std::ptrdiff_t difference_type
Iterator distance type.
Definition list.hxx:84
size_type size() const noexcept
Return the element count.
Definition list.hxx:520
T value_type
Element type.
Definition list.hxx:82
const T & const_reference
Read-only element reference.
Definition list.hxx:86
List() noexcept
Construct an empty list.
void pop_back() noexcept
Destroy the last element.
void clear() noexcept
Destroy every element.
size_type unique()
Erase consecutive duplicates.
void reverse() noexcept
Reverse the chain.
void push_back(const T &value)
Copy value to the back.
reverse_iterator rbegin() noexcept
Return a reverse iterator to the last element.
Definition list.hxx:478
const_reverse_iterator crbegin() const noexcept
Return a reverse iterator to the last element.
Definition list.hxx:502
void push_front(T &&value)
Move value to the front.
List(std::initializer_list< T > values)
Insert every element of an initializer list.
const_reverse_iterator crend() const noexcept
Return the reverse past-the-end iterator.
Definition list.hxx:508
void resize(size_type count)
Grow or shrink to count.
T & emplace_front(Args &&... args)
Construct an element at the front.
T & back() noexcept
Return the last element.
Definition list.hxx:430
size_type remove(const T &value)
Erase every element equal to value.
iterator emplace(const_iterator position, Args &&... args)
Construct an element in place before position.
void splice(const_iterator position, List &other) noexcept
Relink every node of other before position.
~List() noexcept
Destroy every node through Base.
void merge(List &other)
Move the ordered nodes of other into this ordered list.
bool empty() const noexcept
Test whether the list holds no elements.
Definition list.hxx:514
STORMBYTE_FORCE_INLINE iterator insert_range(const_iterator position, R &&range)
Insert every element of range before position.
Definition list.hxx:580
const_iterator cend() const noexcept
Return the past-the-end iterator.
Definition list.hxx:472
BasicIterator< false > iterator
Mutable iterator.
Definition list.hxx:178
Size size_type
Element count. Size, not std::size_t.
Definition list.hxx:83
T & front() noexcept
Return the first element.
Definition list.hxx:418
const T & back() const noexcept
Return the last element.
Definition list.hxx:436
void assign(size_type count, const T &value)
Replace the contents with count copies of value.
STORMBYTE_FORCE_INLINE List(std::list< T > &&other)
Move elements from a caller-owned STL list and leave it empty.
Definition list.hxx:333
const_iterator cbegin() const noexcept
Return the first element.
Definition list.hxx:466
T & emplace_back(Args &&... args)
Construct an element at the back.
size_type max_size() const noexcept
Return the maximum element count this list can report.
Definition list.hxx:526
void pop_front() noexcept
Destroy the first element.
reverse_iterator rend() noexcept
Return the reverse past-the-end iterator.
Definition list.hxx:484
STORMBYTE_FORCE_INLINE List(std::from_range_t, R &&range)
Copy the elements of range.
Definition list.hxx:347
void swap(List &other) noexcept
Exchange chains.
std::reverse_iterator< const_iterator > const_reverse_iterator
Read-only reverse iterator.
Definition list.hxx:181
const_iterator begin() const noexcept
Return the first element.
Definition list.hxx:454
const_iterator end() const noexcept
Return the past-the-end iterator.
Definition list.hxx:460
node_type extract(const_iterator position)
Unlink the element at position.
STORMBYTE_FORCE_INLINE void assign_range(R &&range)
Replace the contents with range.
Definition list.hxx:409
T & reference
Mutable element reference.
Definition list.hxx:85
iterator erase(const_iterator position)
Erase the element at position.
const_reverse_iterator rend() const noexcept
Return the reverse past-the-end iterator.
Definition list.hxx:496
iterator erase(const_iterator first, const_iterator last)
Erase the half-open range [first, last).
const_reverse_iterator rbegin() const noexcept
Return a reverse iterator to the last element.
Definition list.hxx:490
void push_front(const T &value)
Copy value to the front.
void sort()
Sort the chain.
iterator begin() noexcept
Return the first element.
Definition list.hxx:442
std::reverse_iterator< iterator > reverse_iterator
Mutable reverse iterator.
Definition list.hxx:180
Count of abstract units (uint64_t storage).
Definition size.hxx:107
Recognizes a conditional Safe component after stripping cv and references.
Definition safe.hxx:301
Private Base heap used by StormByte::Safe::Shared, StormByte::Safe::Unique and StormByte::Safe::Clona...
void Free(void *pointer) noexcept
Release a block obtained from Allocate.
Owned values that cross a DLL without the caller's CRT.
void swap(Binary &left, Binary &right) noexcept
Exchange two sequences.
Definition binary.hxx:760
Root namespace of the StormByte suite.
Octet count. Defined in byte_size.hxx. Forwarded so Type::Numeral can name it.
STL namespace.
#define STORMBYTE_FORCE_INLINE
Definition platform.h:134
Host-width-stable count (uint64_t), implicit only to std::size_t.
Recognizes types whose DLL-boundary safety depends on documented provider requirements.
Definition safe.hxx:262
Recognizes collection values with Base-controlled lifetime.
Definition safe.hxx:347
Recognizes Base Safe components, not universal ABI compatibility.
Definition safe.hxx:138
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52