openmethod/detail/static_list.hpp

0001 // Copyright (c) 2018-2025 Jean-Louis Leroy
0002 // Distributed under the Boost Software License, Version 1.0.
0003 // See accompanying file LICENSE_1_0.txt
0004 // or copy at http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_OPENMETHOD_DETAIL_STATIC_LIST_HPP
0007 #define BOOST_OPENMETHOD_DETAIL_STATIC_LIST_HPP
0008
0009 #include <algorithm>
0010 #include <boost/assert.hpp>
0011
0012 namespace boost::openmethod {
0013
0014 namespace detail {
0015
0016 template<typename T>
0017 class static_list {
0018   public:
0019     static_list(static_list&) = delete;
0020     static_list() = default;
0021
0022     class static_link {
0023       public:
0024         static_link(const static_link&) = delete;
0025         static_link() = default;
0026
0027         auto next() -> T* {
0028             return next_ptr;
0029         }
0030
0031       protected:
0032         friend class static_list;
0033         T* prev_ptr;
0034         T* next_ptr;
0035     };
0036
0037     void push_back(T& node) {
0038         BOOST_ASSERT(node.prev_ptr == nullptr);
0039         BOOST_ASSERT(node.next_ptr == nullptr);
0040
0041         if (!first) {
0042             first = &node;
0043             node.prev_ptr = &node;
0044             return;
0045         }
0046
0047         auto last = first->prev_ptr;
0048         last->next_ptr = &node;
0049         node.prev_ptr = last;
0050         first->prev_ptr = &node;
0051     }
0052
0053     void remove(T& node) {
0054         BOOST_ASSERT(first != nullptr);
0055
0056         auto prev = node.prev_ptr;
0057         auto next = node.next_ptr;
0058         auto last = first->prev_ptr;
0059
0060         node.prev_ptr = nullptr;
0061         node.next_ptr = nullptr;
0062
0063         if (&node == last) {
0064             if (&node == first) {
0065                 first = nullptr;
0066                 return;
0067             }
0068
0069             first->prev_ptr = prev;
0070             prev->next_ptr = nullptr;
0071             return;
0072         }
0073
0074         if (&node == first) {
0075             first = next;
0076             first->prev_ptr = last;
0077             return;
0078         }
0079
0080         prev->next_ptr = next;
0081         next->prev_ptr = prev;
0082     }
0083
0084     void clear() {
0085         auto next = first;
0086         first = nullptr;
0087
0088         while (next) {
0089             auto cur = next;
0090             next = cur->next_ptr;
0091             cur->prev_ptr = nullptr;
0092             cur->next_ptr = nullptr;
0093         }
0094     }
0095
0096     class iterator {
0097       public:
0098         using iterator_category = std::forward_iterator_tag;
0099         using difference_type = std::ptrdiff_t;
0100         using value_type = T;
0101         using pointer = value_type*;
0102         using reference = value_type&;
0103
0104         iterator() : ptr(nullptr) {
0105         }
0106         explicit iterator(T* p) : ptr(p) {
0107         }
0108
0109         auto operator*() -> reference {
0110             return *ptr;
0111         }
0112         auto operator->() -> pointer {
0113             return ptr;
0114         }
0115
0116         auto operator++() -> iterator& {
0117             BOOST_ASSERT(ptr);
0118             ptr = ptr->next_ptr;
0119             return *this;
0120         }
0121
0122         auto operator++(int) -> iterator {
0123             auto tmp = *this;
0124             ++(*this);
0125             return tmp;
0126         }
0127
0128         friend auto operator==(const iterator& a, const iterator& b) -> bool {
0129             return a.ptr == b.ptr;
0130         };
0131         friend auto operator!=(const iterator& a, const iterator& b) -> bool {
0132             return a.ptr != b.ptr;
0133         };
0134
0135       private:
0136         T* ptr;
0137     };
0138
0139     auto begin() -> iterator {
0140         return iterator(first);
0141     }
0142
0143     auto end() -> iterator {
0144         return iterator(nullptr);
0145     }
0146
0147     class const_iterator {
0148       public:
0149         using iterator_category = std::forward_iterator_tag;
0150         using difference_type = std::ptrdiff_t;
0151         using value_type = const T;
0152         using pointer = value_type*;
0153         using reference = value_type&;
0154
0155         const_iterator() : ptr(nullptr) {
0156         }
0157         explicit const_iterator(T* p) : ptr(p) {
0158         }
0159
0160         auto operator*() -> reference {
0161             return *ptr;
0162         }
0163         auto operator->() -> pointer {
0164             return ptr;
0165         }
0166
0167         auto operator++() -> const_iterator& {
0168             BOOST_ASSERT(ptr);
0169             ptr = ptr->next_ptr;
0170             return *this;
0171         }
0172
0173         auto operator++(int) -> const_iterator {
0174             auto tmp = *this;
0175             ++(*this);
0176             return tmp;
0177         }
0178
0179         friend auto
0180         operator==(const const_iterator& a, const const_iterator& b) -> bool {
0181             return a.ptr == b.ptr;
0182         };
0183         friend auto
0184         operator!=(const const_iterator& a, const const_iterator& b) -> bool {
0185             return a.ptr != b.ptr;
0186         };
0187
0188       private:
0189         T* ptr;
0190     };
0191
0192     auto begin() const -> const_iterator {
0193         return const_iterator(first);
0194     }
0195
0196     auto end() const -> const_iterator {
0197         return const_iterator(nullptr);
0198     }
0199
0200     auto size() const -> std::size_t {
0201         return std::distance(begin(), end());
0202     }
0203
0204     auto empty() const -> bool {
0205         return !first;
0206     }
0207
0208   protected:
0209     T* first;
0210 };
0211
0212 } // namespace detail
0213 } // namespace boost::openmethod
0214
0215 #endif