µOS++ IIIe Reference  v6.3.15
“Perfekt ist nicht gut genug”
The third edition of µOS++, a POSIX inspired open source system, written in C++.
lists.h
Go to the documentation of this file.
1 /*
2  * This file is part of the µOS++ distribution.
3  * (https://github.com/micro-os-plus)
4  * Copyright (c) 2016 Liviu Ionescu.
5  *
6  * Permission is hereby granted, free of charge, to any person
7  * obtaining a copy of this software and associated documentation
8  * files (the "Software"), to deal in the Software without
9  * restriction, including without limitation the rights to use,
10  * copy, modify, merge, publish, distribute, sublicense, and/or
11  * sell copies of the Software, and to permit persons to whom
12  * the Software is furnished to do so, subject to the following
13  * conditions:
14  *
15  * The above copyright notice and this permission notice shall be
16  * included in all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25  * OTHER DEALINGS IN THE SOFTWARE.
26  */
27 
28 #ifndef CMSIS_PLUS_UTILS_LISTS_H_
29 #define CMSIS_PLUS_UTILS_LISTS_H_
30 
31 // ----------------------------------------------------------------------------
32 
33 #ifdef __cplusplus
34 
35 #include <cstdint>
36 #include <cstddef>
37 #include <cassert>
38 #include <iterator>
39 
40 namespace os
41 {
42  namespace utils
43  {
44  // ========================================================================
45 
53  {
54  public:
55 
65 
73  operator= (const static_double_list_links&) = delete;
75  operator= (static_double_list_links&&) = delete;
76 
85 
100  void
101  unlink (void);
102 
108  bool
109  unlinked (void);
110 
112  next (void) const;
113 
115  prev (void) const;
116 
117  void
119 
120  void
122 
127  protected:
128 
138 
143 
148  };
149 
150  // ========================================================================
151 
159  {
160  public:
161 
171 
176  double_list_links (const double_list_links&) = delete;
179  operator= (const double_list_links&) = delete;
181  operator= (double_list_links&&) = delete;
182 
190  ~double_list_links ();
191 
196  };
197 
198  // ========================================================================
199 
213  template<typename T, typename N, T* N::* MP, typename U = T>
215  {
216  public:
217 
226  using value_type = U;
227 
231  using pointer = U*;
232 
236  using reference = U&;
237 
241  using iterator_pointer = N*;
242 
246  using difference_type = ptrdiff_t;
247 
251  using iterator_category = std::forward_iterator_tag;
252 
257  // --------------------------------------------------------------------
263  constexpr
265 
266  constexpr explicit
268 
269  constexpr explicit
271 
281  pointer
282  operator-> () const;
283 
284  reference
285  operator* () const;
286 
288  operator++ ();
289 
291  operator++ (int);
292 
294  operator-- ();
295 
297  operator-- (int);
298 
299  bool
300  operator== (const double_list_iterator& other) const;
301 
302  bool
303  operator!= (const double_list_iterator& other) const;
304 
318  pointer
319  get_pointer (void) const;
320 
322  get_iterator_pointer () const;
323 
328  protected:
329 
339 
344  };
345 
346  // ========================================================================
347 
354  {
355  public:
356 
366 
371  static_double_list (const static_double_list&) = delete;
374  operator= (const static_double_list&) = delete;
376  operator= (static_double_list&&) = delete;
377 
385  ~static_double_list ();
386 
391  public:
392 
405  bool
406  uninitialized (void) const;
407 
415  void
416  clear (void);
417 
425  bool
426  empty (void) const;
427 
428  // TODO add iterator begin(), end()
429 
436  volatile static_double_list_links*
437  head (void) const;
438 
445  volatile static_double_list_links*
446  tail (void) const;
447 
452  protected:
453 
466  void
467  insert_after (static_double_list_links& node,
468  static_double_list_links* after);
469 
474  protected:
475 
487 
491  };
492 
493  // ========================================================================
494 
501  {
502  public:
503 
512  double_list ();
513 
518  double_list (const double_list&) = delete;
519  double_list (double_list&&) = delete;
520  double_list&
521  operator= (const double_list&) = delete;
522  double_list&
523  operator= (double_list&&) = delete;
524 
532  ~double_list ();
533 
538  };
539 
540  // ========================================================================
541 
555  template<typename T, typename N, N T::* MP, typename U = T>
557  {
558  public:
559 
568  using value_type = U;
569 
573  using pointer = U*;
574 
578  using reference = U&;
579 
583  using iterator_pointer = N*;
584 
588  using difference_type = ptrdiff_t;
589 
593  using iterator_category = std::forward_iterator_tag;
594 
599  // --------------------------------------------------------------------
605  constexpr
607 
608  constexpr explicit
610 
611  constexpr explicit
613 
623  pointer
624  operator-> () const;
625 
626  reference
627  operator* () const;
628 
630  operator++ ();
631 
633  operator++ (int);
634 
636  operator-- ();
637 
639  operator-- (int);
640 
641  bool
642  operator== (const intrusive_list_iterator& other) const;
643 
644  bool
645  operator!= (const intrusive_list_iterator& other) const;
646 
660  pointer
661  get_pointer (void) const;
662 
664  get_iterator_pointer () const;
665 
670  protected:
671 
681 
686  };
687 
688  // ========================================================================
689 
707  template<typename T, typename N, N T::* MP, typename U = T>
709  {
710  public:
711 
712  using value_type = U;
713  using pointer = U*;
714  using reference = U&;
715  using difference_type = ptrdiff_t;
716 
718 
722  using iterator_pointer = N*;
723 
732  intrusive_list ();
733 
738  intrusive_list (bool clr);
739 
744  intrusive_list (const intrusive_list&) = delete;
745  intrusive_list (intrusive_list&&) = delete;
747  operator= (const intrusive_list&) = delete;
749  operator= (intrusive_list&&) = delete;
750 
758  ~intrusive_list ();
759 
764  protected:
765 
766  pointer
767  get_pointer (iterator_pointer node) const;
768 
769  public:
770 
782  void
783  link (reference node);
784 
789  iterator
790  begin ();
791 
796  iterator
797  end () const;
798 
803  pointer
804  unlink_head (void);
805 
810  pointer
811  unlink_tail (void);
812 
816  };
817 
818  // --------------------------------------------------------------------------
819  } /* namespace utils */
820 } /* namespace os */
821 
822 // ----------------------------------------------------------------------------
823 
824 namespace os
825 {
826  namespace utils
827  {
828  // ========================================================================
829 
830  // Code analysis may trigger:
831  // "Member 'prev' was not initialized in constructor"
832  // "Member 'next' was not initialized in constructor"
833 
834  inline
836  {
837  ;
838  }
839 
840  inline
842  {
843  ;
844  }
845 
846  inline bool
848  {
849  return (next_ == nullptr);
850  }
851 
854  {
855  return next_;
856  }
857 
860  {
861  return prev_;
862  }
863 
864  inline void
866  {
867  next_ = n;
868  }
869 
870  inline void
872  {
873  prev_ = n;
874  }
875 
876  // ========================================================================
877 
878  inline
880  {
881  prev_ = nullptr;
882  next_ = nullptr;
883  }
884 
885  inline
887  {
888  ;
889  }
890 
891  // ========================================================================
892  template<typename T, typename N, T* N::* MP, typename U>
893  constexpr
895  node_
896  { }
897  {
898  ;
899  }
900 
901  template<typename T, typename N, T* N::* MP, typename U>
902  constexpr
904  iterator_pointer const node) :
905  node_
906  { node }
907  {
908  ;
909  }
910 
911  template<typename T, typename N, T* N::* MP, typename U>
912  constexpr
914  reference element) :
915  node_
916  { &(element.*MP) }
917  {
918  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
919  }
920 
921  template<typename T, typename N, T* N::* MP, typename U>
924  {
925  return get_pointer ();
926  }
927 
928  template<typename T, typename N, T* N::* MP, typename U>
931  {
932  return *get_pointer ();
933  }
934 
935  template<typename T, typename N, T* N::* MP, typename U>
938  {
939  node_ = static_cast<N*> (node_->next ());
940  return *this;
941  }
942 
943  template<typename T, typename N, T* N::* MP, typename U>
946  {
947  const auto tmp = *this;
948  node_ = static_cast<iterator_pointer> (node_->next);
949  return tmp;
950  }
951 
952  template<typename T, typename N, T* N::* MP, typename U>
955  {
956  node_ = static_cast<iterator_pointer> (node_->prev);
957  return *this;
958  }
959 
960  template<typename T, typename N, T* N::* MP, typename U>
963  {
964  const auto tmp = *this;
965  node_ = static_cast<iterator_pointer> (node_->prev);
966  return tmp;
967  }
968 
969  template<typename T, typename N, T* N::* MP, typename U>
970  inline bool
972  const double_list_iterator& other) const
973  {
974  return node_ == other.node_;
975  }
976 
977  template<typename T, typename N, T* N::* MP, typename U>
978  inline bool
980  const double_list_iterator& other) const
981  {
982  return node_ != other.node_;
983  }
984 
985 #if 1
986  template<typename T, typename N, T* N::* MP, typename U>
989  {
990  return (node_->*MP);
991  }
992 
993  template<typename T, typename N, T* N::* MP, typename U>
996  {
997  return node_;
998  }
999 #endif
1000 
1001  // ========================================================================
1002 
1007  inline
1009  {
1010  // By all means, do not add any code here.
1011  // The constructor was not `default` to benefit from inline.
1012  }
1013 
1018  inline
1020  {
1021  ;
1022  }
1023 
1024  inline bool
1026  {
1027  // If it points to nowhere, it is not yet initialised.
1028  return (head_.prev () == nullptr);
1029  }
1030 
1031  inline bool
1033  {
1034  // If it points to itself, it is empty.
1035  return (head_.next () == &head_) || (head_.next () == nullptr);
1036  }
1037 
1038  inline volatile static_double_list_links*
1040  {
1041  return static_cast<volatile static_double_list_links*> (head_.next ());
1042  }
1043 
1044  inline volatile static_double_list_links*
1046  {
1047  return (head_.prev ());
1048  }
1049 
1050  // ========================================================================
1051 
1052  template<typename T, typename N, N T::* MP, typename U>
1053  constexpr
1055  node_
1056  { }
1057  {
1058  ;
1059  }
1060 
1061  template<typename T, typename N, N T::* MP, typename U>
1062  constexpr
1064  N* const node) :
1065  node_
1066  { node }
1067  {
1068  ;
1069  }
1070 
1071  template<typename T, typename N, N T::* MP, typename U>
1072  constexpr
1074  reference element) :
1075  node_
1076  { &(element.*MP) }
1077  {
1078  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
1079  }
1080 
1081  template<typename T, typename N, N T::* MP, typename U>
1084  {
1085  return get_pointer ();
1086  }
1087 
1088  template<typename T, typename N, N T::* MP, typename U>
1091  {
1092  return *get_pointer ();
1093  }
1094 
1095  template<typename T, typename N, N T::* MP, typename U>
1098  {
1099  node_ = static_cast<iterator_pointer> (node_->next ());
1100  return *this;
1101  }
1102 
1103  template<typename T, typename N, N T::* MP, typename U>
1106  {
1107  const auto tmp = *this;
1108  node_ = static_cast<iterator_pointer> (node_->next ());
1109  return tmp;
1110  }
1111 
1112  template<typename T, typename N, N T::* MP, typename U>
1115  {
1116  node_ = static_cast<iterator_pointer> (node_->prev ());
1117  return *this;
1118  }
1119 
1120  template<typename T, typename N, N T::* MP, typename U>
1123  {
1124  const auto tmp = *this;
1125  node_ = static_cast<iterator_pointer> (node_->prev ());
1126  return tmp;
1127  }
1128 
1129  template<typename T, typename N, N T::* MP, typename U>
1130  inline bool
1132  const intrusive_list_iterator& other) const
1133  {
1134  return node_ == other.node_;
1135  }
1136 
1137  template<typename T, typename N, N T::* MP, typename U>
1138  inline bool
1140  const intrusive_list_iterator& other) const
1141  {
1142  return node_ != other.node_;
1143  }
1144 
1145  template<typename T, typename N, N T::* MP, typename U>
1148  {
1149  // static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
1150 
1151  // Compute the distance between the member intrusive link
1152  // node and the class begin.
1153  const auto offset =
1154  reinterpret_cast<difference_type> (&(static_cast<T*> (nullptr)->*MP));
1155 
1156  // Compute the address of the object which includes the
1157  // intrusive node, by adjusting down the node address.
1158  return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node_)
1159  - offset);
1160  }
1161 
1162  template<typename T, typename N, N T::* MP, typename U>
1165  {
1166  return node_;
1167  }
1168 
1169  // ========================================================================
1170 
1171  template<typename T, typename N, N T::* MP, typename U>
1172  inline
1174  {
1175  ;
1176  }
1177 
1178  template<typename T, typename N, N T::* MP, typename U>
1179  inline
1181  {
1182  if (clr)
1183  {
1184  clear ();
1185  }
1186  }
1187 
1188  template<typename T, typename N, N T::* MP, typename U>
1189  inline
1191  {
1192  ;
1193  }
1194 
1195  template<typename T, typename N, N T::* MP, typename U>
1196  void
1198  {
1199  if (uninitialized ())
1200  {
1201  // If this is the first time, initialise the list to empty.
1202  clear ();
1203  }
1204 
1205  // Compute the distance between the member intrusive link
1206  // node and the class begin.
1207  const auto offset =
1208  reinterpret_cast<difference_type> (&(static_cast<T*> (nullptr)->*MP));
1209 
1210  // Add thread intrusive node at the end of the list.
1211  insert_after (
1212  *reinterpret_cast<static_double_list_links*> (reinterpret_cast<difference_type> (&node)
1213  + offset),
1214  const_cast<static_double_list_links *> (tail ()));
1215  }
1216 
1221  template<typename T, typename N, N T::* MP, typename U>
1224  {
1225  if (uninitialized ())
1226  {
1227  // If this is the first time, initialise the list to empty.
1228  clear ();
1229  }
1230  return iterator
1231  { static_cast<iterator_pointer> (head_.next ()) };
1232  }
1233 
1234  template<typename T, typename N, N T::* MP, typename U>
1237  {
1238  return iterator
1239  {
1240  static_cast<iterator_pointer> (const_cast<static_double_list_links*> (&head_)) };
1241  }
1242 
1243  template<typename T, typename N, N T::* MP, typename U>
1244  inline typename intrusive_list<T, N, MP, U>::pointer
1246  {
1247  // static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
1248 
1249  // Compute the distance between the member intrusive link
1250  // node and the class begin.
1251  const auto offset =
1252  reinterpret_cast<difference_type> (&(static_cast<T*> (nullptr)->*MP));
1253 
1254  // Compute the address of the object which includes the
1255  // intrusive node, by adjusting down the node address.
1256  return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node)
1257  - offset);
1258  }
1259 
1260  template<typename T, typename N, N T::* MP, typename U>
1263  {
1264  assert(!empty ());
1265 
1266  // The first element in the list.
1267  iterator_pointer link = static_cast<iterator_pointer> (head_.next ());
1268  link->unlink ();
1269 
1270  return get_pointer (link);
1271  }
1272 
1273  template<typename T, typename N, N T::* MP, typename U>
1276  {
1277  assert(!empty ());
1278 
1279  // The last element in the list.
1280  iterator_pointer link = static_cast<iterator_pointer> (head_.prev ());
1281  link->unlink ();
1282 
1283  return get_pointer (link);
1284  }
1285 
1286  } /* namespace utils */
1287 } /* namespace os */
1288 
1289 // ----------------------------------------------------------------------------
1290 
1291 #endif /* __cplusplus */
1292 
1293 #endif /* CMSIS_PLUS_RTOS_INTERNAL_OS_LISTS_H_ */
pointer unlink_tail(void)
Unlink the last element from the list.
Definition: lists.h:1275
ptrdiff_t difference_type
Type of pointer difference.
Definition: lists.h:588
List of intrusive nodes.
Definition: lists.h:708
ptrdiff_t difference_type
Definition: lists.h:715
bool operator==(const double_list_iterator &other) const
Definition: lists.h:971
pointer get_pointer(void) const
Get the object node from the intrusive node.
Definition: lists.h:988
bool operator!=(thread::id x, thread::id y) noexcept
Ask for flags to be cleared after read.
Definition: os-decls.h:303
~intrusive_list()
Destruct the list.
Definition: lists.h:1190
volatile static_double_list_links * head(void) const
Get the list head.
Definition: lists.h:1039
ptrdiff_t difference_type
Type of pointer difference.
Definition: lists.h:246
System namespace.
U & reference
Type of reference to object "pointed to" by the iterator.
Definition: lists.h:578
U & reference
Type of reference to object "pointed to" by the iterator.
Definition: lists.h:236
bool operator!=(const intrusive_list_iterator &other) const
Definition: lists.h:1139
double_list_iterator & operator++()
Definition: lists.h:937
bool uninitialized(void) const
Check if the list is unitialised.
Definition: lists.h:1025
bool operator==(thread::id x, thread::id y) noexcept
volatile static_double_list_links * tail(void) const
Get the list tail.
Definition: lists.h:1045
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition: lists.h:583
iterator_pointer node_
Pointer to intrusive node.
Definition: lists.h:680
pointer unlink_head(void)
Unlink the first element from the list.
Definition: lists.h:1262
iterator_pointer get_iterator_pointer() const
Definition: lists.h:995
std::forward_iterator_tag iterator_category
Category of iterator.
Definition: lists.h:593
iterator begin()
Iterator begin.
Definition: lists.h:1223
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition: lists.h:722
Statically allocated circular double linked list of nodes.
Definition: lists.h:353
U * pointer
Type of pointer to object "pointed to" by the iterator.
Definition: lists.h:573
void link(reference node)
Add a node to the tail of the list.
Definition: lists.h:1197
intrusive_list_iterator & operator--()
Definition: lists.h:1114
U value_type
Type of value "pointed to" by the iterator.
Definition: lists.h:226
pointer operator->() const
Definition: lists.h:923
constexpr double_list_iterator()
Definition: lists.h:894
pointer get_pointer(iterator_pointer node) const
Definition: lists.h:1245
pointer get_pointer(void) const
Get the object node from the intrusive node.
Definition: lists.h:1147
int link(const char *existing, const char *_new)
static_double_list()
Construct a list.
Definition: lists.h:1008
Template for a double linked list iterator.
Definition: lists.h:214
std::forward_iterator_tag iterator_category
Category of iterator.
Definition: lists.h:251
static_double_list_links head_
A list node used to point to head and tail.
Definition: lists.h:486
bool empty(void) const
Check if the list is empty.
Definition: lists.h:1032
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition: lists.h:241
intrusive_list()
Construct an intrusive list.
Definition: lists.h:1173
reference operator*() const
Definition: lists.h:1090
Circular double linked list of nodes.
Definition: lists.h:500
iterator_pointer get_iterator_pointer() const
Definition: lists.h:1164
U * pointer
Type of pointer to object "pointed to" by the iterator.
Definition: lists.h:231
bool operator==(const intrusive_list_iterator &other) const
Definition: lists.h:1131
intrusive_list_iterator & operator++()
Definition: lists.h:1097
double_list_iterator & operator--()
Definition: lists.h:954
Template for an intrusive list iterator.
Definition: lists.h:556
bool operator!=(const double_list_iterator &other) const
Definition: lists.h:979
U value_type
Type of value "pointed to" by the iterator.
Definition: lists.h:568
iterator end() const
Iterator begin.
Definition: lists.h:1236
~static_double_list()
Destruct the list.
Definition: lists.h:1019
iterator_pointer node_
Pointer to intrusive node.
Definition: lists.h:338
reference operator*() const
Definition: lists.h:930