utils-lists 4.0.2
The µOS++ Intrusive Lists
Loading...
Searching...
No Matches
lists.h
Go to the documentation of this file.
1/*
2 * This file is part of the µOS++ project (https://micro-os-plus.github.com/).
3 * Copyright (c) 2016 Liviu Ionescu. All rights reserved.
4 *
5 * Permission to use, copy, modify, and/or distribute this software
6 * for any purpose is hereby granted, under the terms of the MIT license.
7 *
8 * If a copy of the license was not distributed with this file, it can
9 * be obtained from https://opensource.org/licenses/mit.
10 */
11
25
49
50#ifndef MICRO_OS_PLUS_UTILS_LISTS_H_
51#define MICRO_OS_PLUS_UTILS_LISTS_H_
52
53// ----------------------------------------------------------------------------
54
55#ifdef __cplusplus
56
57// ----------------------------------------------------------------------------
58
59#if defined(MICRO_OS_PLUS_INCLUDE_CONFIG_H)
60#include <micro-os-plus/config.h>
61#endif // MICRO_OS_PLUS_INCLUDE_CONFIG_H
62
63#include <cstdint>
64#include <cstddef>
65#include <cassert>
66#include <iterator>
67
68// ----------------------------------------------------------------------------
69
70#if defined(__GNUC__)
71#pragma GCC diagnostic push
72
73#pragma GCC diagnostic ignored "-Waggregate-return"
74#if defined(__clang__)
75#pragma clang diagnostic ignored "-Wc++98-compat"
76#endif
77#endif
78
94{
95 // ==========================================================================
96
113 {
114 public:
118 constexpr double_list_links_base ();
119
120 // This class follows the rule of five.
121
131
140
151 = delete;
152
162 = delete;
163
167 constexpr ~double_list_links_base ();
168
177 bool
178 uninitialized (void) const;
179
188 constexpr void
189 initialize (void);
190
199 void
200 initialize_once (void);
201
209 void
211
219 void
221
230 void
231 unlink (void);
232
241 bool
242 linked (void) const;
243
251 constexpr double_list_links_base*
252 next (void) const;
253
261 constexpr double_list_links_base*
262 previous (void) const;
263
264 protected:
269
274 };
275
276 // ==========================================================================
277
296 {
297 public:
302 using is_statically_allocated = std::false_type;
303
307 constexpr double_list_links ();
308
309 // This class follows the rule of five.
310
320
329
340 = delete;
341
351 = delete;
352
360 constexpr ~double_list_links ();
361 };
362
363 // ==========================================================================
364
396 {
397 public:
401 using is_statically_allocated = std::true_type;
402
407 constexpr static_double_list_links ();
408
418
428
439 = delete;
440
450 = delete;
451
455 constexpr ~static_double_list_links ();
456
465 void
466 nullify (void);
467 };
468
469 // ==========================================================================
470
488 template <class T, class N = T, class U = T>
490 {
491 public:
495 using value_type = U;
496
501
506
511
515 using difference_type = ptrdiff_t;
516
520 using iterator_category = std::forward_iterator_tag;
521
522 // ------------------------------------------------------------------------
523
529
535 constexpr explicit double_list_iterator (iterator_pointer const node);
536
543 constexpr explicit double_list_iterator (reference element);
544
545 // DO NOT delete the copy constructors, since the default ones are
546 // used.
547
553 constexpr pointer
554 operator->() const;
555
561 constexpr reference
562 operator* () const;
563
569 constexpr double_list_iterator&
571
577 constexpr double_list_iterator
579
585 constexpr double_list_iterator&
587
593 constexpr double_list_iterator
595
603 constexpr bool
605
613 constexpr bool
615
623 constexpr pointer
624 get_pointer (void) const;
625
633 constexpr iterator_pointer
635
636 protected:
641 };
642
643 // ==========================================================================
644
673 template <class T, class L = double_list_links>
675 {
676 public:
677 static_assert (std::is_base_of<double_list_links_base, L>::value == true,
678 "L must be derived from double_list_links_base!");
679 static_assert (std::is_base_of<double_list_links_base, T>::value == true,
680 "T must be derived from double_list_links_base!");
681
686 using links_type = L;
687
691 using value_type = T;
692
697
702
707
712
717 typename links_type::is_statically_allocated;
718
722 double_list ();
723
732 double_list (const double_list&) = delete;
733
743
754 = delete;
755
765 = delete;
766
770 constexpr ~double_list ();
771
772 public:
782 bool
783 uninitialized (void) const;
784
793 void
794 initialize_once (void);
795
804 bool
805 empty (void) const;
806
815 void
816 clear (void);
817
825 constexpr pointer
826 head (void) const;
827
835 constexpr pointer
836 tail (void) const;
837
845 void
846 link_tail (reference node);
847
855 void
856 link_head (reference node);
857
858 // ------------------------------------------------------------------------
859
866 begin () const;
867
874 end () const;
875
876 // Required in derived class iterator end(), where direct
877 // access to member fails.
885 constexpr const links_type*
886 links_pointer (void) const
887 {
888 return &links_;
889 }
890
891 // ------------------------------------------------------------------------
892
893 protected:
905 };
906
907 // ==========================================================================
908
927 template <class T, class N, N T::* MP, class U = T>
929 {
930 public:
934 using value_type = U;
935
940
945
950
954 using difference_type = ptrdiff_t;
955
959 using iterator_category = std::forward_iterator_tag;
960
961 // ------------------------------------------------------------------------
962
968
974 constexpr explicit intrusive_list_iterator (iterator_pointer const node);
975
982 constexpr explicit intrusive_list_iterator (reference element);
983
984 // DO NOT delete the copy constructors, since this implies that
985 // the default ones will be used.
986
992 pointer
993 operator->() const;
994
1000 reference
1001 operator* () const;
1002
1010
1018
1026
1034
1042 bool
1044
1051 bool
1053
1061 pointer
1062 get_pointer (void) const;
1063
1073
1074 protected:
1082 };
1083
1084 // ==========================================================================
1085
1086#if defined(__clang__)
1087#pragma clang diagnostic push
1088#pragma clang diagnostic ignored "-Wdocumentation"
1089#endif
1129#if defined(__clang__)
1130#pragma clang diagnostic pop
1131#endif
1132
1133 template <class T, class N, N T::* MP, class L = double_list_links,
1134 class U = T>
1135 class intrusive_list : public double_list<N, L>
1136 {
1137 public:
1138 static_assert (std::is_base_of<double_list_links_base, L>::value == true,
1139 "L must be derived from double_list_links_base!");
1140 static_assert (std::is_base_of<double_list_links_base, N>::value == true,
1141 "N must be derived from double_list_links_base!");
1142
1147 using links_type = L;
1148
1152 using value_type = U;
1153
1158
1163
1168
1173 typename links_type::is_statically_allocated;
1174
1179
1183 using difference_type = ptrdiff_t;
1184
1188 constexpr intrusive_list ();
1189
1190 // This class follows the rule of five.
1191
1201
1211
1222 = delete;
1223
1233 = delete;
1234
1238 constexpr ~intrusive_list ();
1239
1240 public:
1249 void
1250 initialize_once (void);
1251
1260 constexpr bool
1261 empty (void) const;
1262
1270 void
1271 link_tail (reference node);
1272
1280 void
1281 link_head (reference node);
1282
1290 pointer
1291 unlink_tail (void);
1292
1300 pointer
1301 unlink_head (void);
1302
1303 // ------------------------------------------------------------------------
1304
1310 iterator
1311 begin () const;
1312
1318 iterator
1319 end () const;
1320
1321 // ------------------------------------------------------------------------
1322 protected:
1329 pointer
1330 get_pointer (iterator_pointer node) const;
1331 };
1332
1333 // --------------------------------------------------------------------------
1334} // namespace micro_os_plus::utils
1335
1336#if defined(__GNUC__)
1337#pragma GCC diagnostic pop
1338#endif
1339
1340// ----------------------------------------------------------------------------
1341
1342#endif // __cplusplus
1343
1344// ===== Inline & template implementations ====================================
1345
1346// All other inlines.
1347#include "lists-inlines.h"
1348
1349// ----------------------------------------------------------------------------
1350
1351#endif // MICRO_OS_PLUS_UTILS_LISTS_H_
1352
1353// ----------------------------------------------------------------------------
A class template for a doubly linked list forward iterator.
Definition lists.h:490
constexpr double_list_iterator(reference element)
Construct an iterator from a reference to an element.
ptrdiff_t difference_type
Type of pointer difference.
Definition lists.h:515
constexpr bool operator==(const double_list_iterator &other) const
Equality comparison operator.
constexpr iterator_pointer get_iterator_pointer(void) const
Get the internal iterator pointer (node pointer).
constexpr pointer operator->() const
Pointer access operator.
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:500
constexpr pointer get_pointer(void) const
Get a pointer to the value pointed to by the iterator.
constexpr double_list_iterator & operator--()
Pre-decrement operator.
constexpr bool operator!=(const double_list_iterator &other) const
Inequality comparison operator.
std::forward_iterator_tag iterator_category
Category of iterator.
Definition lists.h:520
constexpr double_list_iterator & operator++()
Pre-increment operator.
constexpr reference operator*() const
Dereference operator.
constexpr double_list_iterator(iterator_pointer const node)
Construct an iterator from a node pointer.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:505
U value_type
Type of value pointed to by the iterator.
Definition lists.h:495
constexpr double_list_iterator()
Default constructor. Constructs an iterator pointing to nullptr.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:510
constexpr const links_type * links_pointer(void) const
Get the address of the node storing the list links.
Definition lists.h:886
void link_head(reference node)
Add a node to the head of the list.
links_type links_
The list top node used to point to head and tail nodes.
Definition lists.h:904
L links_type
Type of the links node object where the pointers to the list head and tail are stored.
Definition lists.h:686
value_type * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:711
constexpr pointer tail(void) const
Get the list tail.
double_list(double_list &&)=delete
Deleted move constructor.
void initialize_once(void)
Initialize the list only at first run.
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:696
constexpr ~double_list()
Destruct the list.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:701
double_list()
Construct a doubly linked list.
void clear(void)
Clear the list.
constexpr pointer head(void) const
Get the list head.
iterator end() const
Iterator end.
double_list & operator=(const double_list &)=delete
Deleted copy assignment operator.
double_list(const double_list &)=delete
Deleted copy constructor.
T value_type
Type of value pointed to by the iterator.
Definition lists.h:691
iterator begin() const
Iterator begin.
double_list_iterator< value_type > iterator
Type of iterator over the values.
Definition lists.h:706
bool empty(void) const
Check if the list is empty.
void link_tail(reference node)
Add a node to the tail of the list.
bool uninitialized(void) const
Check if the list is uninitialised (only statically allocated lists can be uninitialised).
typename links_type::is_statically_allocated is_statically_allocated
Type indicating if the links node is statically allocated.
Definition lists.h:716
A class template for the intrusive list iterator.
Definition lists.h:929
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:939
std::forward_iterator_tag iterator_category
Category of iterator.
Definition lists.h:959
pointer get_pointer(void) const
Get the object node from the intrusive node.
intrusive_list_iterator & operator++()
Pre-increment operator.
iterator_pointer get_iterator_pointer(void) const
Retrieve the iterator pointer for the current node.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:949
reference operator*() const
Dereference operator.
bool operator==(const intrusive_list_iterator &other) const
Equality comparison operator.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:944
constexpr intrusive_list_iterator()
Default constructor. Constructs an iterator pointing to nullptr.
bool operator!=(const intrusive_list_iterator &other) const
Inequality comparison operator.
U value_type
Type of value pointed to by the iterator.
Definition lists.h:934
pointer operator->() const
Pointer access operator.
constexpr intrusive_list_iterator(iterator_pointer const node)
Construct an iterator from a node pointer.
constexpr intrusive_list_iterator(reference element)
Construct an iterator from a reference to an element.
intrusive_list_iterator & operator--()
Pre-decrement operator.
ptrdiff_t difference_type
Type of pointer difference.
Definition lists.h:954
constexpr intrusive_list()
Construct an intrusive doubly linked list.
L links_type
Type of the list links node object where the pointers to the list head and tail are stored.
Definition lists.h:1147
constexpr bool empty(void) const
Check if the list is empty.
void link_tail(reference node)
Add a node to the tail of the list.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:1178
iterator begin() const
Iterator begin.
typename links_type::is_statically_allocated is_statically_allocated
Type indicating if the links node is statically allocated.
Definition lists.h:1172
pointer unlink_head(void)
Unlink the first element from the list.
void link_head(reference node)
Add a node to the head of the list.
constexpr ~intrusive_list()
Destruct the list.
intrusive_list_iterator< T, N, MP, U > iterator
Type of iterator over the values.
Definition lists.h:1167
void initialize_once(void)
Initialize the list only at first run.
U value_type
Type of value pointed to by the iterator.
Definition lists.h:1152
iterator end() const
Iterator begin.
intrusive_list & operator=(const intrusive_list &)=delete
Deleted copy assignment operator.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:1162
ptrdiff_t difference_type
Type of pointer difference.
Definition lists.h:1183
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:1157
intrusive_list(intrusive_list &&)=delete
Deleted move constructor.
pointer unlink_tail(void)
Unlink the last element from the list.
pointer get_pointer(iterator_pointer node) const
Get the address of the object from the intrusive node pointer.
intrusive_list(const intrusive_list &)=delete
Deleted copy constructor.
C++ header file with the inline implementations for the µOS++ lists methods.
The µOS++ utilities definitions.