iffl  1.3.4
Implements Intrusive Flat Forward List container
iffl_list.h
Go to the documentation of this file.
1 #pragma once
2 
210 #include <iffl_config.h>
211 #include <iffl_common.h>
212 #include <iffl_mpl.h>
217 namespace iffl {
285 template <typename T>
286 struct flat_forward_list_traits;
287 
329 template < typename T,
330  typename TT = flat_forward_list_traits<T>>
331 struct flat_forward_list_traits_traits {
332 
333 private:
334  //
335  // Meta-functions that we will use with detect-idiom to find
336  // properties of TT without triggering a compile time error
337  //
344  template <typename P>
345  using has_minimum_size_mfn = decltype(std::declval<P &>().minimum_size());
352  template <typename P>
353  using has_get_size_mfn = decltype(std::declval<P &>().get_size(std::declval<T const &>()));
360  template <typename P>
361  using has_next_offset_mfn = decltype(std::declval<P &>().get_next_offset(std::declval<T const &>()));
368  template <typename P>
369  using can_set_next_offset_mfn = decltype(std::declval<P &>().set_next_offset(std::declval<T &>(), size_t{ 0 }));
376  template <typename P>
377  using can_validate_mfn = decltype(std::declval<P &>().validate(size_t{0}, std::declval<T const &>()));
385  template <typename P>
386  using has_alignment_mfn = decltype(std::declval<P &>().alignment);
387 
388 public:
393  using value_type = T;
398  using type_traits = TT;
406  using has_minimum_size_t = iffl::mpl::is_detected < has_minimum_size_mfn, type_traits>;
411  constexpr static auto const has_minimum_size_v{ iffl::mpl::is_detected_v < has_minimum_size_mfn, type_traits> };
419  using has_get_size_t = iffl::mpl::is_detected < has_get_size_mfn, type_traits>;
424  constexpr static auto const has_get_size_v{ iffl::mpl::is_detected_v < has_get_size_mfn, type_traits> };
432  using has_next_offset_t = iffl::mpl::is_detected < has_next_offset_mfn, type_traits>;
437  constexpr static auto const has_next_offset_v{ iffl::mpl::is_detected_v < has_next_offset_mfn, type_traits> };
445  using can_set_next_offset_t = iffl::mpl::is_detected < can_set_next_offset_mfn, type_traits>;
450  constexpr static auto const can_set_next_offset_v{ iffl::mpl::is_detected_v < can_set_next_offset_mfn, type_traits> };
458  using can_validate_t = iffl::mpl::is_detected < can_validate_mfn, type_traits>;
463  constexpr static auto const can_validate_v{ iffl::mpl::is_detected_v < can_validate_mfn, type_traits> };
471  using has_alignment_t = iffl::mpl::is_detected < has_alignment_mfn, type_traits>;
476  constexpr static auto const has_alignment_v{ iffl::mpl::is_detected_v < has_alignment_mfn, type_traits> };
481  static value_type* ptr_to_t(void *ptr) {
482  return static_cast<value_type *>(ptr);
483  }
488  static value_type const* ptr_to_t(void const *ptr) {
489  return static_cast<value_type const *>(ptr);
490  }
495  static value_type* ptr_to_t(char *ptr) {
496  return reinterpret_cast<value_type *>(ptr);
497  }
502  static value_type const* ptr_to_t(char const *ptr) {
503  return reinterpret_cast<value_type const *>(ptr);
504  }
509  static value_type* ptr_to_t(unsigned char *ptr) {
510  return reinterpret_cast<value_type *>(ptr);
511  }
516  static value_type const* ptr_to_t(unsigned char const *ptr) {
517  return reinterpret_cast<value_type const *>(ptr);
518  }
522  [[nodiscard]] constexpr static size_t minimum_size() noexcept {
523  return type_traits::minimum_size();
524  }
529  [[nodiscard]] constexpr static size_t get_alignment() noexcept {
530  if constexpr (has_alignment_v) {
531  return type_traits::alignment;
532  } else {
533  return 1;
534  }
535  }
540  constexpr static size_t const alignment{ get_alignment() };
545  using range_t = range_with_alighment<alignment>;
550  using size_with_padding_t = size_with_padding<alignment>;
555  using offset_with_aligment_t = offset_with_aligment<alignment>;
562  [[nodiscard]] constexpr static size_t roundup_to_alignment(size_t s) noexcept {
563  if constexpr (has_alignment_v && 0 != alignment) {
564  return roundup_size_to_alignment(s, alignment);
565  } else {
566  return s;
567  }
568  }
574  [[nodiscard]] constexpr static size_with_padding_t get_size(char const *buffer) noexcept {
575  return size_with_padding_t{ type_traits::get_size(*ptr_to_t(buffer)) };
576  }
584  [[nodiscard]] constexpr static bool validate(size_t buffer_size, T const &buffer) noexcept {
585  if constexpr (can_validate_v) {
586  return type_traits::validate(buffer_size, buffer);
587  } else {
588  return true;
589  }
590  }
597  [[nodiscard]] constexpr static size_t get_next_offset(char const *buffer) noexcept {
598  if constexpr (has_next_offset_v) {
599  return type_traits::get_next_offset(*ptr_to_t(buffer));
600  } else {
601  size_with_padding_t s{ get_size(buffer) };
602  return s.size_padded();
603  }
604  }
612  constexpr static void set_next_offset(char *buffer, size_t size) noexcept {
613  static_assert(has_next_offset_v,
614  "set_next_offset is not supported for type that does not have get_next_offset");
615  if constexpr (has_alignment_v) {
616  //
617  // If traits specify alignment requirements then
618  // assert when attempt to set unaligned offset to
619  // next element
620  //
621  FFL_CODDING_ERROR_IF_NOT(size == roundup_to_alignment(size));
622  }
623  return type_traits::set_next_offset(*ptr_to_t(buffer), size);
624  }
629  static void print_traits_info() noexcept {
630  std::type_info const & ti = typeid(type_traits&);
631 
632  std::printf("type \"%s\" {\n", ti.name());
633 
634  if constexpr (has_minimum_size_v) {
635  std::printf(" minimum_size : yes -> %zu\n", minimum_size());
636  } else {
637  std::printf(" minimum_size : no \n");
638  }
639 
640  if constexpr (has_get_size_v) {
641  std::printf(" get_size : yes\n");
642  } else {
643  std::printf(" get_size : no \n");
644  }
645 
646  if constexpr (has_next_offset_v) {
647  std::printf(" get_next_offset : yes\n");
648  } else {
649  std::printf(" get_next_offset : no \n");
650  }
651 
652  if constexpr (can_set_next_offset_v) {
653  std::printf(" set_next_offset : yes\n");
654  } else {
655  std::printf(" set_next_offset : no \n");
656  }
657 
658  if constexpr (can_validate_v) {
659  std::printf(" validate : yes\n");
660  } else {
661  std::printf(" validate : no \n");
662  }
663 
664  if constexpr (has_alignment_v) {
665  std::printf(" alignment : yes -> %zu\n", alignment);
666  } else {
667  std::printf(" alignment : no \n");
668  }
669  std::printf("}\n");
670  }
671 };
672 
673 
678 template <typename T,
679  typename TT,
680  typename A>
681 class flat_forward_list;
686 template <typename T,
687  typename TT>
688 class flat_forward_list_ref;
689 
698 template<typename T,
699  typename TT = flat_forward_list_traits<T>>
700 struct default_validate_element_fn {
706  bool operator() (size_t buffer_size,
707  T const &e) const noexcept {
708  return TT::validate(buffer_size, e);
709  }
710 };
715 template<typename T,
716  typename TT = flat_forward_list_traits<T>>
717 struct noop_validate_element_fn {
722  bool operator() ([[maybe_unused]] size_t,
723  [[maybe_unused]] T const &) const noexcept {
724  return true;
725  }
726 };
730 template<typename T,
731  typename TT = flat_forward_list_traits<T>,
732  typename F = default_validate_element_fn<T, TT>>
733 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate_has_next_offset(char const *first,
734  char const *end,
735  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
739 template<typename T,
740  typename TT = flat_forward_list_traits<T>,
741  typename F = default_validate_element_fn<T, TT>>
742 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate_no_next_offset(char const *first,
743  char const *end,
744  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
748 template<typename T,
749  typename TT = flat_forward_list_traits<T>,
750  typename F = default_validate_element_fn<T, TT>>
751 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(char const *first,
752  char const *end,
753  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
757 template<typename T,
758  typename TT = flat_forward_list_traits<T>,
759  typename F = default_validate_element_fn<T, TT>>
760 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(char *first,
761  char *end,
762  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
766 template<typename T,
767  typename TT = flat_forward_list_traits<T>,
768  typename F = default_validate_element_fn<T, TT>>
769 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(T *first,
770  T *end,
771  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
775 template<typename T,
776  typename TT = flat_forward_list_traits<T>,
777  typename F = default_validate_element_fn<T, TT>>
778 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(T const *first,
779  T const *end,
780  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
784 template<typename T,
785  typename TT = flat_forward_list_traits<T>,
786  typename F = default_validate_element_fn<T, TT>>
787 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(unsigned char const *first,
788  unsigned char const *end,
789  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
793 template<typename T,
794  typename TT = flat_forward_list_traits<T>,
795  typename F = default_validate_element_fn<T, TT>>
796 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(unsigned char *first,
797  unsigned char *end,
798  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
802 template<typename T,
803  typename TT = flat_forward_list_traits<T>,
804  typename F = default_validate_element_fn<T, TT>>
805 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(void const *first,
806  void const *end,
807  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
811 template<typename T,
812  typename TT = flat_forward_list_traits<T>,
813  typename F = default_validate_element_fn<T, TT>>
814 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(void *first,
815  void *end,
816  F const &validate_element_fn = default_validate_element_fn<T, TT>{}) noexcept;
817 
831 template<typename T,
832  typename TT = flat_forward_list_traits<T>>
833 class flat_forward_list_iterator_t final {
834 
839  template <typename TU,
840  typename TTU,
841  typename AU>
842  friend class flat_forward_list;
843 
848  template <typename TU,
849  typename TTU>
850  friend class flat_forward_list_ref;
851 
852 public:
857  using iterator_category = std::forward_iterator_tag;
862  using value_type = T;
867  using difference_type = ptrdiff_t;
872  using pointer = T*;
877  using reference = T&;
882  using traits = TT;
887  using traits_traits = flat_forward_list_traits_traits<T, TT>;
893  using buffer_char_pointer = std::conditional_t<std::is_const_v<T>, char const *, char *>;
899  using buffer_unsigned_char_pointer = std::conditional_t<std::is_const_v<T>, unsigned char const *, unsigned char *>;
905  using buffer_void_pointer = std::conditional_t<std::is_const_v<T>, void const *, void *>;
910  using size_with_padding_t = typename traits_traits::size_with_padding_t;
918  constexpr flat_forward_list_iterator_t() noexcept = default;
922  constexpr flat_forward_list_iterator_t(flat_forward_list_iterator_t const &) noexcept = default;
927  constexpr flat_forward_list_iterator_t(flat_forward_list_iterator_t && other) noexcept
928  : p_{other.p_} {
929  other.p_ = nullptr;
930  }
936  using const_iterator = flat_forward_list_iterator_t< std::add_const_t<T>, TT>;
942  using non_const_iterator = flat_forward_list_iterator_t< std::remove_cv_t<T>, TT>;
947  constexpr static auto const is_const_iterator{ std::is_const_v<T> };
955  template <typename Iterator>
956  constexpr static auto const is_non_const_iterator_v{ std::is_same_v < std::remove_cv_t<Iterator>,
957  non_const_iterator > };
965  template <typename Iterator>
966  constexpr static auto const is_const_iterator_v{ std::is_same_v < std::remove_cv_t<Iterator>,
967  const_iterator > };
974  template <typename Iterator>
975  constexpr static auto const is_comparable_iterator_v{ is_non_const_iterator_v<Iterator> ||
976  is_const_iterator_v<Iterator> };
980  static_assert(!is_non_const_iterator_v<const_iterator>,
981  "This is a const iterator");
985  static_assert(is_non_const_iterator_v<non_const_iterator>,
986  "This is a non-const iterator");
987 
996  template< typename I,
997  typename = std::enable_if_t<is_const_iterator && is_non_const_iterator_v<I>>>
998  constexpr flat_forward_list_iterator_t(I const & other) noexcept
999  : p_{ other.get_ptr() } {
1000  }
1014  template< typename I,
1015  typename = std::enable_if_t<is_const_iterator && is_non_const_iterator_v<I>>>
1016  constexpr flat_forward_list_iterator_t(I && other) noexcept
1017  : p_{ other.get_ptr() } {
1018  //other.reset_ptr(nullptr);
1019  }
1024  constexpr flat_forward_list_iterator_t &operator= (flat_forward_list_iterator_t const &) noexcept = default;
1030  constexpr flat_forward_list_iterator_t & operator= (flat_forward_list_iterator_t && other) noexcept {
1031  if (this != &other) {
1032  p_ = other.p_;
1033  other.p_ = nullptr;
1034  }
1035  return *this;
1036  }
1046  template <typename I,
1047  typename = std::enable_if_t<is_const_iterator && is_non_const_iterator_v<I>>>
1048  constexpr flat_forward_list_iterator_t & operator= (I const & other) noexcept {
1049  p_ = other.get_ptr();
1050  return *this;
1051  }
1066  template <typename I,
1067  typename = std::enable_if_t<is_const_iterator && is_non_const_iterator_v<I>>>
1068  constexpr flat_forward_list_iterator_t & operator= (I && other) noexcept {
1069  p_ = other.get_ptr();
1070  //other.reset_ptr(nullptr);
1071  return *this;
1072  }
1077  constexpr void swap(flat_forward_list_iterator_t & other) noexcept {
1078  buffer_char_pointer *tmp = p_;
1079  p_ = other.p_;
1080  other.p_ = tmp;
1081  }
1086  constexpr explicit operator bool() const {
1087  return p_ != nullptr;
1088  }
1099  template <typename I,
1100  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1101  constexpr bool operator == (I const &other) const noexcept {
1102  return p_ == other.get_ptr();
1103  }
1114  template <typename I,
1115  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1116  constexpr bool operator != (I const &other) const noexcept {
1117  return !this->operator==(other);
1118  }
1129  template <typename I,
1130  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1131  constexpr bool operator < (I const &other) const noexcept {
1132  return p_ < other.get_ptr();
1133  }
1144  template <typename I,
1145  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1146  constexpr bool operator <= (I const &other) const noexcept {
1147  return p_ <= other.get_ptr();
1148  }
1159  template <typename I,
1160  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1161  constexpr bool operator > (I const &other) const noexcept {
1162  return !this->operator<=(other);
1163  }
1174  template <typename I,
1175  typename = std::enable_if_t<is_comparable_iterator_v<I>>>
1176  constexpr bool operator >= (I const &other) const noexcept {
1177  return !this->operator<(other);
1178  }
1184  constexpr flat_forward_list_iterator_t &operator++() noexcept {
1185  size_t const next_offset = traits_traits::get_next_offset(p_);
1186  if (0 == next_offset) {
1187  size_with_padding_t const element_size{ traits_traits::get_size(p_) };
1188  p_ += element_size.size_padded();
1189  } else {
1190  p_ += next_offset;
1191  }
1192  return *this;
1193  }
1200  constexpr flat_forward_list_iterator_t operator++(int) noexcept {
1201  flat_forward_list_iterator_t tmp{ p_ };
1202  size_t next_offset = traits_traits::get_next_offset(p_);
1203  if (0 == next_offset) {
1204  size_with_padding_t element_size{ traits_traits::get_size(p_) };
1205  p_ += element_size.size_padded();
1206  } else {
1207  p_ += next_offset;
1208  }
1209  return tmp;
1210  }
1220  constexpr flat_forward_list_iterator_t operator+(unsigned int advance_by) const noexcept {
1221  flat_forward_list_iterator_t result{ get_ptr() };
1222  while (nullptr != result.get_ptr() && 0 != advance_by) {
1223  ++result;
1224  --advance_by;
1225  }
1226  return result;
1227  }
1232  constexpr T &operator*() const noexcept {
1233  return *reinterpret_cast<T *>(p_);
1234  }
1239  constexpr T *operator->() const noexcept {
1240  return reinterpret_cast<T *>(p_);
1241  }
1242 
1246  constexpr buffer_char_pointer get_ptr() const noexcept {
1247  return p_;
1248  }
1249 
1250 private:
1251 
1257  constexpr buffer_char_pointer reset_ptr(buffer_char_pointer p) noexcept {
1258  buffer_char_pointer tmp{ p_ };
1259  p_ = p;
1260  return tmp;
1261  }
1266  constexpr explicit flat_forward_list_iterator_t(buffer_char_pointer p) noexcept
1267  : p_(p) {
1268  }
1273  constexpr explicit flat_forward_list_iterator_t(T *p) noexcept
1274  : p_((buffer_char_pointer)p) {
1275  }
1281  constexpr explicit flat_forward_list_iterator_t(buffer_unsigned_char_pointer p) noexcept
1282  : p_((buffer_char_pointer )p) {
1283  }
1289  constexpr explicit flat_forward_list_iterator_t(buffer_void_pointer p) noexcept
1290  : p_((buffer_char_pointer )p) {
1291  }
1297  constexpr flat_forward_list_iterator_t &operator= (buffer_char_pointer p) noexcept {
1298  p_ = p;
1299  return *this;
1300  }
1306  constexpr flat_forward_list_iterator_t &operator= (T *p) noexcept {
1307  p_ = (buffer_char_pointer)p;
1308  return *this;
1309  }
1315  constexpr flat_forward_list_iterator_t &operator= (buffer_unsigned_char_pointer p) noexcept {
1316  p_ = (buffer_char_pointer )p;
1317  return *this;
1318  }
1324  constexpr flat_forward_list_iterator_t &operator= (buffer_void_pointer p) noexcept {
1325  p_ = (buffer_char_pointer )p;
1326  return *this;
1327  }
1331  buffer_char_pointer p_{ nullptr };
1332 };
1333 
1342 template<typename T,
1343  typename TT = flat_forward_list_traits<T>>
1344 using flat_forward_list_iterator = flat_forward_list_iterator_t<T, TT>;
1345 
1354 template<typename T,
1355  typename TT = flat_forward_list_traits<T>>
1356 using flat_forward_list_const_iterator = flat_forward_list_iterator_t< std::add_const_t<T>, TT>;
1357 
1366 template <typename T,
1367  typename TT = flat_forward_list_traits<T>>
1368 class flat_forward_list_ref final {
1369 public:
1370 
1371  //
1372  // Technically we need T to be
1373  // - trivially destructible
1374  // - trivially constructible
1375  // - trivially movable
1376  // - trivially copyable
1377  //
1378  static_assert(std::is_pod_v<T>, "T must be a Plain Old Definition");
1382  inline static bool const is_ref{ !std::is_const_v<T> };
1387  using value_type = T;
1392  using pointer = T * ;
1397  using const_pointer = T const *;
1402  using reference = T & ;
1407  using const_reference = T const &;
1412  using size_type = std::size_t;
1417  using difference_type = std::ptrdiff_t;
1422  using traits = TT;
1427  using traits_traits = flat_forward_list_traits_traits<T, TT>;
1436  using range_t = typename traits_traits::range_t;
1441  using size_with_padding_t = typename traits_traits::size_with_padding_t;
1446  using offset_with_aligment_t = typename traits_traits::offset_with_aligment_t;
1451  using sizes_t = flat_forward_list_sizes<traits_traits::alignment>;
1461  using buffer_value_type = std::conditional_t<std::is_const_v<T>, char const, char>;
1467  using const_buffer_value_type = buffer_value_type const;
1472  using buffer_pointer = buffer_value_type *;
1477  using const_buffer_pointer = const_buffer_value_type *;
1482  using iterator = flat_forward_list_iterator<T, TT>;
1487  using const_iterator = flat_forward_list_const_iterator<T, TT>;
1493  using buffer_type = buffer_t<buffer_value_type>;
1498  inline static size_type const npos = iffl::npos;
1502  flat_forward_list_ref() noexcept
1503  : buffer_() {
1504  }
1513  template<typename V,
1514  typename VV,
1515  typename = std::enable_if<std::is_assignable_v<T*, V*>>>
1516  flat_forward_list_ref(flat_forward_list_ref<V, VV> const &other) noexcept
1517  : buffer_(other.buffer_) {
1518  }
1528  explicit flat_forward_list_ref(buffer_type const &other_buff) noexcept
1529  : buffer_(other_buff) {
1530  }
1531 
1545  flat_forward_list_ref(buffer_pointer buffer_begin,
1546  buffer_pointer last_element,
1547  buffer_pointer buffer_end) noexcept
1548  : buffer_(buffer_type{ buffer_begin, last_element, buffer_end }) {
1549  }
1562  template <typename V,
1563  typename VV,
1564  typename = std::enable_if<std::is_assignable_v<T*, V*>>>
1565  flat_forward_list_ref(flat_forward_list_iterator<V, VV> const &begin,
1566  flat_forward_list_iterator<V, VV> const &last) noexcept
1567  : buffer_(buffer_type{begin.get_ptr(),
1568  last.get_ptr(),
1569  reinterpret_cast<buffer_pointer>(last.get_ptr()) +
1570  traits_traits::get_size(last.get_ptr()).size }) {
1571  }
1582  flat_forward_list_ref(buffer_pointer *buffer,
1583  size_t buffer_size) noexcept {
1584  assign(buffer, buffer_size);
1585  }
1594  template <typename V,
1595  typename VV,
1596  typename A,
1597  typename UNUSED = std::enable_if<std::is_assignable_v<T*, V*>>>
1598  explicit flat_forward_list_ref(flat_forward_list<V, VV, A> const &c) noexcept;
1599 
1604  template <typename V,
1605  typename VV,
1606  typename = std::enable_if<std::is_assignable_v<T*, V*>>>
1607  flat_forward_list_ref &operator= (flat_forward_list_ref<V, VV> const & other) {
1608  buffer_ = other.buffer_;
1609  return *this;
1610  }
1615  flat_forward_list_ref &operator= (buffer_view const &other_buffer) {
1616  buffer_ = other_buffer;
1617  return *this;
1618  }
1628  template <typename V,
1629  typename VV,
1630  typename A,
1631  typename UNUSED = std::enable_if<std::is_assignable_v<T*, V*>>>
1632  flat_forward_list_ref &operator= (flat_forward_list<V, VV, A> const &c) noexcept;
1637  ~flat_forward_list_ref() noexcept {
1638  buff().clear();
1639  }
1648  void assign(buffer_type const &other_buff) noexcept {
1649  buffer_ = other_buff;
1650  }
1661  void assign(buffer_pointer buffer_begin,
1662  buffer_pointer last_element,
1663  buffer_pointer buffer_end) noexcept {
1664  buffer_ = buffer_type{ buffer_begin, last_element, buffer_end };
1665  }
1674  template <typename V,
1675  typename VV,
1676  typename = std::enable_if<std::is_assignable_v<T*, V*>>>
1677  void assign(flat_forward_list_iterator<V, VV> const &begin,
1678  flat_forward_list_iterator<V, VV> const &last) noexcept {
1679  buffer_ = buffer_type{ begin.get_ptr(),
1680  last.get_ptr(),
1681  reinterpret_cast<buffer_pointer>(last.get_ptr()) +
1682  traits_traits::get_size(last.get_ptr()).size };
1683  }
1689  void assign(buffer_pointer *buffer,
1690  size_t buffer_size) noexcept {
1691 
1692  auto[is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buffer,
1693  buffer + buffer_size);
1694 
1695  buffer_ = buffer_type{ buffer,
1696  is_valid ? buffer_view.last().get_ptr() : nullptr,
1697  buffer + buffer_size };
1698  }
1706  void swap(flat_forward_list_ref &other) noexcept {
1707  flat_forward_list_ref tmp{ std::move(other) };
1708  other = std::move(*this);
1709  *this = std::move(tmp);
1710  }
1715  T& front() {
1716  validate_pointer_invariants();
1717  FFL_CODDING_ERROR_IF(buff().last == nullptr || buff().begin == nullptr);
1718  return *(T *)buff().begin;
1719  }
1724  T const &front() const {
1725  validate_pointer_invariants();
1726  FFL_CODDING_ERROR_IF(buff().last == nullptr || buff().begin == nullptr);
1727  return *(T *)buff().begin;
1728  }
1733  T& back() {
1734  validate_pointer_invariants();
1735  FFL_CODDING_ERROR_IF(buff().last == nullptr);
1736  return *(T *)buff().last;
1737  }
1742  T const &back() const {
1743  validate_pointer_invariants();
1744  FFL_CODDING_ERROR_IF(buff().last == nullptr);
1745  return *(T *)buff().last;
1746  }
1751  iterator begin() noexcept {
1752  validate_pointer_invariants();
1753  return buff().last ? iterator{ buff().begin }
1754  : end();
1755  }
1760  const_iterator begin() const noexcept {
1761  validate_pointer_invariants();
1762  return buff().last ? const_iterator{ buff().begin }
1763  : cend();
1764  }
1765 
1766  //
1767  // It is not clear how to implement it
1768  // without adding extra boolean flags to iterator.
1769  // Since elements are variable length we need to be able
1770  // to query offset to next, and we cannot not do that
1771  // no before_begin element
1772  //
1773  // iterator before_begin() noexcept {
1774  // }
1775 
1780  iterator last() noexcept {
1781  validate_pointer_invariants();
1782  return buff().last ? iterator{ buff().last }
1783  : end();
1784  }
1789  const_iterator last() const noexcept {
1790  validate_pointer_invariants();
1791  return buff().last ? const_iterator{ buff().last }
1792  : cend();
1793  }
1807  iterator end() noexcept {
1808  validate_pointer_invariants();
1809  if (buff().last) {
1810  if (traits_traits::has_next_offset_v) {
1811  size_type next_offset = traits_traits::get_next_offset(buff().last);
1812  if (next_offset) {
1813  return iterator{ buff().last + next_offset };
1814  } else {
1815  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
1816  return iterator{ buff().last + last_element_size.size_padded() };
1817  }
1818  } else {
1819  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
1820  return iterator{ buff().last + last_element_size.size_padded() };
1821  }
1822  } else {
1823  return iterator{ };
1824  }
1825  }
1839  const_iterator end() const noexcept {
1840  validate_pointer_invariants();
1841  if (buff().last) {
1842  if (traits_traits::has_next_offset_v) {
1843  size_type const next_offset{ traits_traits::get_next_offset(buff().last) };
1844  if (next_offset) {
1845  return const_iterator{ buff().last + next_offset };
1846  } else {
1847  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
1848  return const_iterator{ buff().last + last_element_size.size_padded() };
1849  }
1850  } else {
1851  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
1852  return const_iterator{ buff().last + last_element_size.size_padded() };
1853  }
1854  } else {
1855  return const_iterator{ };
1856  }
1857  }
1862  const_iterator cbegin() const noexcept {
1863  return begin();
1864  }
1869  const_iterator clast() const noexcept {
1870  return last();
1871  }
1879  const_iterator cend() const noexcept {
1880  return end();
1881  }
1886  char* data() noexcept {
1887  return buff().begin;
1888  }
1893  char const *data() const noexcept {
1894  return buff().begin;
1895  }
1905  [[nodiscard]] bool revalidate_data() noexcept {
1906  auto[valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin,
1907  buff().end);
1908  if (valid) {
1909  buff().last = buffer_view.last().get_ptr();
1910  }
1911  return valid;
1912  }
1918  size_type required_size(const_iterator const &it) const noexcept {
1919  validate_pointer_invariants();
1920  validate_iterator_not_end(it);
1921  return size_unsafe(it).size;
1922  }
1928  size_type used_size(const_iterator const &it) const noexcept {
1929  validate_pointer_invariants();
1930  validate_iterator_not_end(it);
1931 
1932  return used_size_unsafe(it);
1933  }
1946  range_t range(const_iterator const &it) const noexcept {
1947  validate_iterator_not_end(it);
1948 
1949  return range_unsafe(it);
1950  }
1965  range_t closed_range(const_iterator const &begin, const_iterator const &last) const noexcept {
1966  validate_iterator_not_end(begin);
1967  validate_iterator_not_end(last);
1968 
1969  return closed_range_unsafe(begin, last);
1970  }
1986  range_t half_open_range(const_iterator const &begin, const_iterator const &end) const noexcept {
1987  validate_iterator_not_end(begin);
1988  validate_iterator_not_end(end);
1989 
1990  return half_open_range_usafe(begin, end);
1991  }
2003  [[nodiscard]] bool contains(const_iterator const &it, size_type position) const noexcept {
2004  validate_iterator(it);
2005  if (cend() == it || npos == position) {
2006  return false;
2007  }
2008  range_t const r{ range_unsafe(it) };
2009  return r.buffer_contains(position);
2010  }
2021  const_iterator find_element_before(size_type position) const noexcept {
2022  validate_pointer_invariants();
2023  if (empty_unsafe()) {
2024  return end();
2025  }
2026  auto[is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin,
2027  buff().begin + position);
2028  if (!buffer_view.empty()) {
2029  return const_iterator{ buffer_view.last().get_ptr() };
2030  }
2031  return end();
2032  }
2042  const_iterator find_element_at(size_type position) const noexcept {
2043  const_iterator it = find_element_before(position);
2044  if (cend() != it) {
2045  ++it;
2046  if (cend() != it) {
2047  FFL_CODDING_ERROR_IF_NOT(contains(it, position));
2048  return it;
2049  }
2050  }
2051  return end();
2052  }
2063  const_iterator find_element_after(size_type position) const noexcept {
2064  const_iterator it = find_element_at(position);
2065  if (cend() != it) {
2066  ++it;
2067  if (cend() != it) {
2068  return it;
2069  }
2070  }
2071  return end();
2072  }
2080  size_type size() const noexcept {
2081  validate_pointer_invariants();
2082  size_type s = 0;
2083  std::for_each(cbegin(), cend(), [&s](T const &) {
2084  ++s;
2085  });
2086  return s;
2087  }
2096  [[nodiscard]] bool empty() const noexcept {
2097  validate_pointer_invariants();
2098  return buff().last == nullptr;
2099  }
2104  explicit operator bool() const {
2105  return !empty();
2106  }
2111  size_type used_capacity() const noexcept {
2112  validate_pointer_invariants();
2113  sizes_t s{ get_all_sizes() };
2114  return s.used_capacity().size;
2115  }
2119  size_type total_capacity() const noexcept {
2120  validate_pointer_invariants();
2121  return buff().end - buff().begin;
2122  }
2127  size_type remaining_capacity() const noexcept {
2128  validate_pointer_invariants();
2129  sizes_t s{ get_all_sizes() };
2130  return s.remaining_capacity_for_append();
2131  }
2132 
2133 private:
2142  bool empty_unsafe() const noexcept {
2143  return buff().last == nullptr;
2144  }
2148  void validate_pointer_invariants() const noexcept {
2149  buff().validate();
2150  }
2155  void validate_iterator(const_iterator const &it) const noexcept {
2156  //
2157  // If we do not have any valid elements then
2158  // only end iterator is valid.
2159  // Otherwise iterator should be an end or point somewhere
2160  // between begin of the buffer and start of the first element
2161  //
2162  if (empty_unsafe()) {
2163  FFL_CODDING_ERROR_IF_NOT(cend() == it);
2164  } else {
2165  FFL_CODDING_ERROR_IF_NOT(cend() == it ||
2166  (buff().begin <= it.get_ptr() && it.get_ptr() <= buff().last));
2167  validate_compare_to_all_valid_elements(it);
2168  }
2169  }
2175  void validate_iterator_not_end(const_iterator const &it) const noexcept {
2176  //
2177  // Used in case when end iterator is meaningless.
2178  // Validates that container is not empty,
2179  // and iterator is pointing somewhere between
2180  // begin of the buffer and start of the first element
2181  //
2182  FFL_CODDING_ERROR_IF(cend() == it);
2183  FFL_CODDING_ERROR_IF(const_iterator{} == it);
2184  FFL_CODDING_ERROR_IF_NOT(buff().begin <= it.get_ptr() && it.get_ptr() <= buff().last);
2185  validate_compare_to_all_valid_elements(it);
2186  }
2192  void validate_compare_to_all_valid_elements(const_iterator const &it) const noexcept {
2193 #ifdef FFL_DBG_CHECK_ITERATOR_VALID
2194  //
2195  // If not end iterator then must point to one of the valid iterators.
2196  //
2197  if (end() != it) {
2198  bool found_match{ false };
2199  for (auto cur = cbegin(); cur != cend(); ++cur) {
2200  if (cur == it) {
2201  found_match = true;
2202  break;
2203  }
2204  }
2205  FFL_CODDING_ERROR_IF_NOT(found_match);
2206  }
2207 #else //FFL_DBG_CHECK_ITERATOR_VALID
2208  it;
2209 #endif //FFL_DBG_CHECK_ITERATOR_VALID
2210  }
2216  size_with_padding_t size_unsafe(const_iterator const &it) const noexcept {
2217  return traits_traits::get_size(it.get_ptr());
2218  }
2232  size_type used_size_unsafe(const_iterator const &it) const noexcept {
2233  if constexpr (traits_traits::has_next_offset_v) {
2234  size_type next_offset = traits_traits::get_next_offset(it.get_ptr());
2235  if (0 == next_offset) {
2236  size_with_padding_t s{ traits_traits::get_size(it.get_ptr()) };
2237  //
2238  // Last element
2239  //
2240  next_offset = s.size;
2241  }
2242  return next_offset;
2243  } else {
2244  size_with_padding_t s{ traits_traits::get_size(it.get_ptr()) };
2245  //
2246  // buffer might end without including padding for the last element
2247  //
2248  if (last() == it) {
2249  return s.size;
2250  } else {
2251  return s.size_padded();
2252  }
2253  }
2254  }
2272  range_t range_unsafe(const_iterator const &it) const noexcept {
2273  size_with_padding_t s{ traits_traits::get_size(it.get_ptr()) };
2274  range_t r{};
2275  r.buffer_begin = it.get_ptr() - buff().begin;
2276  r.data_end = r.begin() + s.size;
2277  if constexpr (traits_traits::has_next_offset_v) {
2278  size_type next_offset = traits_traits::get_next_offset(it.get_ptr());
2279  if (0 == next_offset) {
2280  FFL_CODDING_ERROR_IF(last() != it);
2281  r.buffer_end = r.begin() + s.size;
2282  } else {
2283  r.buffer_end = r.begin() + next_offset;
2284  }
2285  } else {
2286  if (last() == it) {
2287  r.buffer_end = r.begin() + s.size;
2288  } else {
2289  r.buffer_end = r.begin() + s.size_padded();
2290  }
2291  }
2292  return r;
2293  }
2298  range_t closed_range_unsafe(const_iterator const &first, const_iterator const &last) const noexcept {
2299  if (first == last) {
2300  return element_range_unsafe(first);
2301  } else {
2302  range_t first_element_range{ range_unsafe(first) };
2303  range_t last_element_range{ range_unsafe(last) };
2304 
2305  return range_t{ {first_element_range.begin,
2306  last_element_range.data_end,
2307  last_element_range.buffer_end } };
2308  }
2309  }
2317  range_t half_open_range_usafe(const_iterator const &first,
2318  const_iterator const &end) const noexcept {
2319 
2320  if (this->end() == end) {
2321  return closed_range_usafe(first, last());
2322  }
2323 
2324  size_t end_begin{ static_cast<size_t>(end->get_ptr() - buff().begin) };
2325  iterator last{ find_element_before(end_begin) };
2326 
2327  return closed_range_usafe(first, last);
2328  }
2335  sizes_t get_all_sizes() const noexcept {
2336  sizes_t s;
2337 
2338  s.total_capacity = buff().end - buff().begin;
2339 
2340  if (nullptr != buff().last) {
2341  s.last_element = range_unsafe(const_iterator{ buff().last });
2342  }
2343  FFL_CODDING_ERROR_IF(s.total_capacity < s.used_capacity().size);
2344 
2345  return s;
2346  }
2347 
2354  buffer_type &buff() noexcept {
2355  return buffer_;
2356  }
2363  buffer_type const &buff() const noexcept {
2364  return buffer_;
2365  }
2366 
2367  buffer_type buffer_;
2368 };
2373 template <typename T,
2374  typename TT = flat_forward_list_traits<T>>
2375 using flat_forward_list_view = flat_forward_list_ref<T const, TT>;
2376 
2388 template <typename T,
2389  typename TT>
2390 inline void swap(flat_forward_list_ref<T, TT> &lhs, flat_forward_list_ref<T, TT> &rhs) noexcept {
2391  lhs.swap(rhs);
2392 }
2404 template <typename T,
2405  typename TT>
2406 inline typename flat_forward_list_ref<T, TT>::iterator begin(flat_forward_list_ref<T, TT> &c) noexcept {
2407  return c.begin();
2408 }
2420 template <typename T,
2421  typename TT>
2422 inline typename flat_forward_list_ref<T, TT>::const_iterator begin(flat_forward_list_ref<T, TT> const &c) noexcept {
2423  return c.begin();
2424 }
2436 template <typename T,
2437  typename TT>
2438 inline typename flat_forward_list_ref<T, TT>::const_iterator cbegin(flat_forward_list_ref<T, TT> const &c) noexcept {
2439  return c.cbegin();
2440 }
2452 template <typename T,
2453  typename TT>
2454 inline typename flat_forward_list_ref<T, TT>::iterator end(flat_forward_list_ref<T, TT> &c) noexcept {
2455  return c.end();
2456 }
2468 template <typename T,
2469  typename TT>
2470 inline typename flat_forward_list_ref<T, TT>::const_iterator end(flat_forward_list_ref<T, TT> const &c) noexcept {
2471  return c.end();
2472 }
2484 template <typename T,
2485  typename TT>
2486 inline typename flat_forward_list_ref<T, TT>::const_iterator cend(flat_forward_list_ref<T, TT> const &c) noexcept {
2487  return c.cend();
2488 }
2500 template <typename T,
2501  typename TT>
2502 inline typename flat_forward_list_ref<T, TT>::iterator last(flat_forward_list_ref<T, TT> &c) noexcept {
2503  return c.last();
2504 }
2516 template <typename T,
2517  typename TT>
2518 inline typename flat_forward_list_ref<T, TT>::const_iterator last(flat_forward_list_ref<T, TT> const &c) noexcept {
2519  return c.last();
2520 }
2532 template <typename T,
2533  typename TT>
2534 inline typename flat_forward_list_ref<T, TT>::const_iterator clast(flat_forward_list_ref<T, TT> const &c) noexcept {
2535  return c.clast();
2536 }
2537 
2600 template <typename T,
2601  typename TT = flat_forward_list_traits<T>,
2602  typename A = std::allocator<T>>
2603 class flat_forward_list final {
2604 public:
2605 
2610  template <typename TU,
2611  typename TTU>
2612  friend class flat_forward_list_ref;
2613 
2614  //
2615  // Technically we need T to be
2616  // - trivially destructible
2617  // - trivially constructible
2618  // - trivially movable
2619  // - trivially copyable
2620  //
2621  static_assert(std::is_pod_v<T>, "T must be a Plain Old Definition");
2626  using value_type = T;
2631  using pointer = T * ;
2636  using const_pointer = T const *;
2641  using reference = T & ;
2646  using const_reference = T const &;
2651  using size_type = std::size_t;
2656  using difference_type = std::ptrdiff_t;
2661  using traits = TT;
2666  using traits_traits = flat_forward_list_traits_traits<T, TT>;
2675  using range_t = typename traits_traits::range_t;
2680  using size_with_padding_t = typename traits_traits::size_with_padding_t;
2685  using offset_with_aligment_t = typename traits_traits::offset_with_aligment_t;
2690  using sizes_t = flat_forward_list_sizes<traits_traits::alignment>;
2695  using allocator_type = typename std::allocator_traits<A>::template rebind_alloc<char>;
2700  using allocator_type_traits = std::allocator_traits<allocator_type>;
2708  using buffer_value_type = char;
2714  using const_buffer_value_type = char const;
2719  using buffer_pointer = char *;
2724  using const_buffer_pointer = char const *;
2725 
2730  using iterator = flat_forward_list_iterator<T, TT>;
2735  using const_iterator = flat_forward_list_const_iterator<T, TT>;
2741  using buffer_type = buffer_t<buffer_value_type>;
2746  inline static size_type const npos = iffl::npos;
2750  flat_forward_list() noexcept
2751  : buffer_( zero_then_variadic_args_t{} ) {
2752  }
2757  explicit flat_forward_list(allocator_type a) noexcept
2758  : buffer_( one_then_variadic_args_t{}, a ) {
2759  }
2765  flat_forward_list(flat_forward_list && other) noexcept
2766  : buffer_( one_then_variadic_args_t{}, std::move(other.alloc()) ) {
2767  move_from(std::move(other));
2768  }
2775  flat_forward_list(flat_forward_list const &other)
2776  : buffer_( one_then_variadic_args_t{}, allocator_type_traits::select_on_container_copy_construction(other.get_allocator()) ) {
2777  copy_from(other);
2778  }
2799  template <typename AA = allocator_type>
2800  flat_forward_list(attach_buffer,
2801  buffer_view const &other_buff,
2802  AA &&a = AA{}) noexcept
2803  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a) ) {
2804  attach(other_buff);
2805  }
2817  template <typename AA = allocator_type>
2818  explicit flat_forward_list(buffer_view const &other_buff,
2819  AA &&a = AA{})
2820  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a) ) {
2821  assign(other_buff);
2822  }
2848  template <typename AA = allocator_type>
2849  flat_forward_list(attach_buffer,
2850  char *buffer_begin,
2851  char *last_element,
2852  char *buffer_end,
2853  AA &&a = AA{}) noexcept
2854  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a) ) {
2855  attach(buffer_begin, last_element, buffer_end);
2856  }
2873  template <typename AA = allocator_type>
2874  flat_forward_list(char const *buffer_begin,
2875  char const *last_element,
2876  char const *buffer_end,
2877  AA &&a = AA{})
2878  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a) ) {
2879  assign(buffer_begin, last_element, buffer_end);
2880  }
2903  template <typename AA = allocator_type>
2904  flat_forward_list(attach_buffer,
2905  char *buffer,
2906  size_t buffer_size,
2907  AA &&a = AA{}) noexcept
2908  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a) ) {
2909  //
2910  // Drop error. If we cannot find valid list then
2911  // still attach to the buffer, but set last to nullptr
2912  //
2913  (void )attach(buffer, buffer_size);
2914  }
2928  template <typename AA = allocator_type>
2929  flat_forward_list(char const *buffer,
2930  size_t buffer_size,
2931  AA &&a = AA{})
2932  : buffer_( one_then_variadic_args_t{}, std::forward<AA>(a)) {
2933  //
2934  // Drop error. If we cannot find valid list then
2935  // still attach to the buffer, but set last to nullptr
2936  //
2937  (void )assign(buffer, buffer_size);
2938  }
2946  template <typename AA = allocator_type>
2947  flat_forward_list(const_iterator const &begin,
2948  const_iterator const &last,
2949  AA &&a = AA{})
2950  : buffer_(one_then_variadic_args_t{}, std::forward<AA>(a)) {
2951  assign(begin, last);
2952  }
2959  template <typename AA = allocator_type>
2960  flat_forward_list(flat_forward_list_view<T, TT> const &view,
2961  AA &&a = AA{})
2962  : buffer_(one_then_variadic_args_t{}, std::forward<AA>(a)) {
2963  assign(view);
2964  }
2975  flat_forward_list &operator= (flat_forward_list && other) noexcept (allocator_type_traits::propagate_on_container_move_assignment::value) {
2976  if (this != &other) {
2977  if constexpr (allocator_type_traits::propagate_on_container_move_assignment::value) {
2978  move_allocator_from(std::move(other));
2979  move_from(std::move(other));
2980  } else {
2981  try_move_from(std::move(other));
2982  }
2983  }
2984  return *this;
2985  }
2994  flat_forward_list &operator= (flat_forward_list const &other) {
2995  if (this != &other) {
2996  //
2997  // If we are propagating allocator then delete old data
2998  // before changing allocator
2999  //
3000  if constexpr (allocator_type_traits::propagate_on_container_copy_assignment::value) {
3001  clear();
3002  *static_cast<allocator_type *>(this) = allocator_type_traits::select_on_container_copy_construction(other.get_allocator());
3003  }
3004 
3005  copy_from(other);
3006  }
3007  return *this;
3008  }
3017  flat_forward_list &operator= (buffer_view const &other_buff) {
3018  assign(other_buff);
3019  return *this;
3020  }
3025  ~flat_forward_list() noexcept {
3026  clear();
3027  }
3034  buffer_ref detach() noexcept {
3035  buffer_ref tmp{ buff() };
3036  buff().clear();
3037  return tmp;
3038  }
3052  void attach(buffer_view const &other_buff) {
3053  FFL_CODDING_ERROR_IF(buff().begin == other_buff.begin);
3054  other_buff.validate();
3055  clear();
3056  buff() = other_buff;
3057  }
3077  void attach(char *buffer_begin,
3078  char *last_element,
3079  char *buffer_end) noexcept {
3080 
3081  FFL_CODDING_ERROR_IF(buff().begin == buffer_begin);
3082  if (last_element) {
3083  FFL_CODDING_ERROR_IF_NOT(buffer_begin < last_element && last_element < buffer_end);
3084  } else {
3085  FFL_CODDING_ERROR_IF_NOT(buffer_begin < buffer_end);
3086  }
3087  clear();
3088  buff().begin = buffer_begin;
3089  buff().end = buffer_end;
3090  buff().last = last_element;
3091  }
3107  [[nodiscard]] bool attach(char *buffer,
3108  size_t buffer_size) noexcept {
3109  FFL_CODDING_ERROR_IF(buff().begin == buffer);
3110  auto [is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buffer,
3111  buffer + buffer_size);
3112  attach(buffer,
3113  is_valid ? buffer_view.last().get_ptr() : nullptr,
3114  buffer + buffer_size);
3115  return is_valid;
3116  }
3125  void assign(buffer_view const &other_buff) {
3126  flat_forward_list l(get_allocator());
3127  other_buff.validate();
3128 
3129  l.buff().begin = allocate_buffer(other_buff.size());
3130  copy_data(l.buff().begin, other_buff.begin, other_buff.size());
3131  l.buff().end = l.buff().begin + other_buff.size();
3132  l.buff().last = l.buff().begin + other_buff.last_offset();
3133  swap(l);
3134  }
3149  void assign(char const *buffer_begin,
3150  char const *last_element,
3151  char const *buffer_end) {
3152  flat_forward_list l(get_allocator());
3153 
3154  if (last_element) {
3155  FFL_CODDING_ERROR_IF_NOT(buffer_begin < last_element && last_element < buffer_end);
3156  } else {
3157  FFL_CODDING_ERROR_IF_NOT(buffer_begin < buffer_end);
3158  }
3159 
3160  size_type buffer_size = buffer_end - buffer_begin;
3161  size_type last_element_offset = last_element - buffer_begin;
3162 
3163  l.buff().begin = allocate_buffer(buffer_size);
3164  copy_data(l.buff().begin, buffer_begin, buffer_size);
3165  l.buff().end = l.buff().begin + buffer_size;
3166  l.buff().last = l.buff().begin + last_element_offset;
3167  swap(l);
3168  }
3180  [[nodiscard]] bool assign(char const *buffer_begin,
3181  char const *buffer_end) {
3182 
3183  auto[is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buffer_begin,
3184  buffer_end);
3185  assign(buffer_begin,
3186  is_valid ? buffer_view.last().get_ptr() : nullptr,
3187  buffer_end);
3188 
3189  return is_valid;
3190  }
3202  [[nodiscard]] bool assign(char const *buffer,
3203  size_type buffer_size) {
3204 
3205  return assign(buffer, buffer + buffer_size);
3206  }
3212  void assign(const_iterator const &begin,
3213  const_iterator const &last) {
3214 
3215  flat_forward_list new_list(get_allocator());
3216  new_list.resize_buffer(distance(begin.get_ptr(),
3217  last.get_ptr()) + traits_traits::get_size(last.get_ptr()).size);
3218  const_iterator const end = last + 1;
3219  for (const_iterator it{ begin }; it != end; ++it) {
3220  new_list.push_back(used_size(it), it.get_ptr());
3221  }
3222  //
3223  // Swap with new list
3224  //
3225  swap(new_list);
3226  }
3231  void assign(flat_forward_list_view<T, TT> const &view) {
3232  if (!view.empty()) {
3233  const_iterator const &begin{ view.begin() };
3234  const_iterator const &last{ view.end() };
3235  flat_forward_list new_list(get_allocator());
3236  new_list.resize_buffer(distance(view.begin().get_ptr(),
3237  last.get_ptr()) + traits_traits::get_size(last.get_ptr()).size);
3238  const_iterator const end = last + 1;
3239  for (const_iterator const it = begin; it != end; ++it) {
3240  new_list.push_back(used_size(it), it.get_ptr());
3241  }
3242  //
3243  // Swap with new list
3244  //
3245  swap(new_list);
3246  } else {
3247  clear();
3248  }
3249  }
3256  template<typename AA>
3257  [[nodiscard]] bool is_compatible_allocator(AA const &other_allocator) const noexcept {
3258  return other_allocator == get_allocator();
3259  }
3264  allocator_type &get_allocator() & noexcept {
3265  return alloc();
3266  }
3271  allocator_type const &get_allocator() const & noexcept {
3272  return alloc();
3273  }
3280  size_type max_size() const noexcept {
3281  return allocator_type_traits::max_size(get_allocator());
3282  }
3287  void clear() noexcept {
3288  validate_pointer_invariants();
3289  if (buff().begin) {
3290  deallocate_buffer(buff().begin, total_capacity());
3291  buff().clear();
3292  }
3293  validate_pointer_invariants();
3294  }
3303  void tail_shrink_to_fit() {
3304  resize_buffer(used_capacity());
3305  }
3322  void resize_buffer(size_type size) {
3323  validate_pointer_invariants();
3324 
3325  sizes_t const prev_sizes{ get_all_sizes() };
3326 
3327  char *new_buffer{ nullptr };
3328  size_t new_buffer_size{ 0 };
3329  auto deallocate_buffer{ make_scoped_deallocator(&new_buffer, &new_buffer_size) };
3330  //
3331  // growing capacity
3332  //
3333  if (prev_sizes.total_capacity < size) {
3334  new_buffer = allocate_buffer(size);
3335  new_buffer_size = size;
3336  if (nullptr != buff().last) {
3337  copy_data(new_buffer, buff().begin, prev_sizes.used_capacity().size);
3338  buff().last = new_buffer + prev_sizes.last_element.begin();
3339  }
3340  commit_new_buffer(new_buffer, new_buffer_size);
3341  buff().end = buff().begin + size;
3342  //
3343  // shrinking to 0 is simple
3344  //
3345  } else if (0 == size) {
3346  clear();
3347  //
3348  // to shrink to a smaller size we first need to
3349  // find last element that would completely fit
3350  // in the new buffer, and if we found any, then
3351  // make it new last element. If we did not find
3352  // any, then designate that there are no last
3353  // element
3354  //
3355  } else if (prev_sizes.total_capacity > size) {
3356 
3357  new_buffer = allocate_buffer(size);
3358  new_buffer_size = size;
3359 
3360  bool is_valid{ true };
3361  char *last_valid{ buff().last };
3362  //
3363  // If we are shrinking below used capacity then last element will
3364  // be removed, and we need to do linear search for the new last element
3365  // that would fit new buffer size.
3366  //
3367  if (prev_sizes.used_capacity().size > size) {
3368  flat_forward_list_ref<T, TT> buffer_view;
3369  std::tie(is_valid, buffer_view) = flat_forward_list_validate<T, TT>(buff().begin,
3370  buff().begin + size);
3371  if (is_valid) {
3372  FFL_CODDING_ERROR_IF_NOT(buffer_view.last().get_ptr() == buff().last);
3373  } else {
3374  FFL_CODDING_ERROR_IF_NOT(buffer_view.last().get_ptr() != buff().last);
3375  }
3376  last_valid = buffer_view.last().get_ptr();
3377  }
3378 
3379  if (last_valid) {
3380  size_type new_last_element_offset = last_valid - buff().begin;
3381 
3382  size_with_padding_t const last_valid_element_size{ traits_traits::get_size(last_valid) };
3383  size_type const new_used_capacity{ new_last_element_offset + last_valid_element_size.size };
3384 
3385  set_no_next_element(last_valid);
3386 
3387  copy_data(new_buffer, buff().begin, new_used_capacity);
3388  buff().last = new_buffer + new_last_element_offset;
3389  } else {
3390  buff().last = nullptr;
3391  }
3392 
3393  commit_new_buffer(new_buffer, new_buffer_size);
3394  buff().end = buff().begin + size;
3395  }
3396 
3397  validate_pointer_invariants();
3398  validate_data_invariants();
3399  }
3411  void push_back(size_type init_buffer_size,
3412  char const *init_buffer = nullptr) {
3413 
3414  emplace_back(init_buffer_size,
3415  [init_buffer_size, init_buffer](T &buffer,
3416  size_type element_size) {
3417  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3418  if (init_buffer) {
3419  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3420  } else {
3421  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3422  }
3423  });
3424  }
3438  [[nodiscard]] bool try_push_back(size_type init_buffer_size,
3439  char const *init_buffer = nullptr) {
3440 
3441  return try_emplace_back(init_buffer_size,
3442  [init_buffer_size, init_buffer](T &buffer,
3443  size_type element_size) {
3444  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3445  if (init_buffer) {
3446  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3447  } else {
3448  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3449  }
3450  });
3451  }
3465  template <typename F>
3466  void emplace_back(size_type element_size,
3467  F const &fn) {
3468  bool const result{ try_emplace_back_impl(can_reallocate::yes, element_size, fn) };
3469  FFL_CODDING_ERROR_IF(!result);
3470  }
3471 
3484  template <typename F>
3485  [[nodiscard]] bool try_emplace_back(size_type element_size,
3486  F const &fn) {
3487  return try_emplace_back_impl(can_reallocate::no, element_size, fn);
3488  }
3489 
3499  void pop_back() noexcept {
3500  validate_pointer_invariants();
3501 
3502  FFL_CODDING_ERROR_IF(empty_unsafe());
3503 
3504  if (has_exactly_one_entry()) {
3505  //
3506  // The last element is also the first element
3507  //
3508  buff().last = nullptr;
3509  } else {
3510  //
3511  // Find element before last
3512  //
3513  size_t const last_element_start_offset{ static_cast<size_t>(buff().last - buff().begin) };
3514  iterator element_before_it{ find_element_before(last_element_start_offset) };
3515  //
3516  // We already handled the case when last element is first element.
3517  // In this branch we must find an element before last.
3518  //
3519  FFL_CODDING_ERROR_IF(end() == element_before_it);
3520  //
3521  // Element before last is the new last
3522  //
3523  set_no_next_element(element_before_it.get_ptr());
3524  buff().last = element_before_it.get_ptr();
3525  }
3526 
3527  validate_pointer_invariants();
3528  validate_data_invariants();
3529  }
3549  iterator insert(iterator const &it, size_type init_buffer_size, char const *init_buffer = nullptr) {
3550  emplace(it,
3551  init_buffer_size,
3552  [init_buffer_size, init_buffer](T &buffer,
3553  size_type element_size) {
3554  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3555 
3556  if (init_buffer) {
3557  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3558  } else {
3559  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3560  }
3561  });
3562  }
3583  [[nodiscard]] bool try_insert(iterator const &it,
3584  size_type init_buffer_size,
3585  char const *init_buffer = nullptr) {
3586  return try_emplace(it,
3587  init_buffer_size,
3588  [init_buffer_size, init_buffer](T &buffer,
3589  size_type element_size) {
3590  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3591  if (init_buffer) {
3592  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3593  } else {
3594  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3595  }
3596  });
3597  }
3622  template <typename F>
3623  iterator emplace(iterator const &it,
3624  size_type new_element_size,
3625  F const &fn) {
3626  auto [result, new_it] = try_emplace_impl(can_reallocate::yes,
3627  it,
3628  new_element_size,
3629  fn);
3630  FFL_CODDING_ERROR_IF(!result);
3631  return new_it;
3632  }
3655  template <typename F>
3656  [[nodiscard]] bool try_emplace(iterator const &it,
3657  size_type new_element_size,
3658  F const &fn) {
3659  auto[result, new_it] = try_emplace_impl(can_reallocate::no,
3660  it,
3661  new_element_size,
3662  fn);
3663  FFL_CODDING_ERROR_IF_NOT(it == new_it);
3664  return result;
3665  }
3677  void push_front(size_type init_buffer_size,
3678  char const *init_buffer = nullptr) {
3679  emplace(begin(),
3680  init_buffer_size,
3681  [init_buffer_size, init_buffer](T &buffer,
3682  size_type element_size) {
3683  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3684 
3685  if (init_buffer) {
3686  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3687  } else {
3688  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3689  }
3690  });
3691  }
3704  [[nodiscard]] bool try_push_front(size_type init_buffer_size,
3705  char const *init_buffer = nullptr) {
3706  return try_emplace(begin(),
3707  init_buffer_size,
3708  [init_buffer_size, init_buffer](T &buffer,
3709  size_type element_size) {
3710  FFL_CODDING_ERROR_IF_NOT(init_buffer_size == element_size);
3711  if (init_buffer) {
3712  copy_data(reinterpret_cast<char *>(&buffer), init_buffer, element_size);
3713  } else {
3714  zero_buffer(reinterpret_cast<char *>(&buffer), element_size);
3715  }
3716  });
3717  }
3732  template <typename F>
3733  void emplace_front(size_type element_size,
3734  F const &fn) {
3735  emplace(begin(), element_size, fn);
3736  }
3749  template <typename F>
3750  [[nodiscard]] bool try_emplace_front(size_type element_size,
3751  F const &fn) {
3752  return try_emplace(begin(), element_size, fn);
3753  }
3758  void pop_front() noexcept {
3759  validate_pointer_invariants();
3760 
3761  FFL_CODDING_ERROR_IF(empty_unsafe());
3762  //
3763  // If we have only one element then simply forget it
3764  //
3765  if (has_one_or_no_entry()) {
3766  buff().last = nullptr;
3767  return;
3768  }
3769  //
3770  // Otherwise calculate sizes and offsets
3771  //
3772  sizes_t const prev_sizes{ get_all_sizes() };
3773  iterator const begin_it{ iterator{ buff().begin } };
3774  iterator const secont_element_it{ begin_it + 1 };
3775  range_t const second_element_range{ this->range_unsafe(secont_element_it) };
3776  size_type const bytes_to_copy{ prev_sizes.used_capacity().size - second_element_range.begin() };
3777  //
3778  // Shift all elements after the first element
3779  // to the start of buffer
3780  //
3781  move_data(buff().begin, buff().begin + second_element_range.begin(), bytes_to_copy);
3782 
3783  buff().last -= second_element_range.begin();
3784 
3785  validate_pointer_invariants();
3786  validate_data_invariants();
3787  }
3794  void erase_after(iterator const &it) noexcept {
3795  validate_pointer_invariants();
3796  //
3797  // Cannot erase after end. Should we no-op or fail?
3798  //
3799  validate_iterator_not_end(it);
3800  //
3801  // There is no elements after last
3802  //
3803  FFL_CODDING_ERROR_IF( last() == it);
3804  FFL_CODDING_ERROR_IF(empty_unsafe());
3805  //
3806  // Find pointer to the element that we are erasing
3807  //
3808  iterator element_to_erase_it = it;
3809  ++element_to_erase_it;
3810  bool const erasing_last_element = (last() == element_to_erase_it);
3811 
3812  if (erasing_last_element) {
3813  //
3814  // trivial case when we are deleting last element and this element
3815  // is becoming last
3816  //
3817  set_no_next_element(it.get_ptr());
3818  buff().last = it.get_ptr();
3819  } else {
3820  //
3821  // calculate sizes and offsets
3822  //
3823  sizes_t const prev_sizes{ get_all_sizes() };
3824  range_t const element_to_erase_range{ this->range_unsafe(element_to_erase_it) };
3825  size_type const tail_size{ prev_sizes.used_capacity().size - element_to_erase_range.buffer_end };
3826  //
3827  // Shift all elements after the element that we are erasing
3828  // to the position where erased element used to be
3829  //
3830  move_data(buff().begin + element_to_erase_range.begin(),
3831  buff().begin + element_to_erase_range.buffer_end, tail_size
3832  );
3833  buff().last -= element_to_erase_range.buffer_size();
3834  }
3835 
3836  validate_pointer_invariants();
3837  validate_data_invariants();
3838  }
3839 
3851  void erase_after_half_closed(iterator const &before_start, iterator const &last) noexcept {
3852  validate_pointer_invariants();
3853  //
3854  // Cannot erase after end
3855  //
3856  validate_iterator_not_end(before_start);
3857  validate_iterator(before_start);
3858  //
3859  // There is no elements after last
3860  //
3861  FFL_CODDING_ERROR_IF(before_start == this->last());
3862  //
3863  // If we are truncating entire tail
3864  //
3865  if (end() == last) {
3866  erase_all_after(before_start);
3867  return;
3868  }
3869  //
3870  // We can support before_start == last by simply calling erase(last).
3871  // That will change complexity of algorithm by adding extra O(N).
3872  //
3873  FFL_CODDING_ERROR_IF_NOT(before_start < last);
3874 
3875  //
3876  // Find pointer to the element that we are erasing
3877  //
3878  iterator first_element_to_erase_it = before_start;
3879  ++first_element_to_erase_it;
3880  //
3881  // calculate sizes and offsets
3882  //
3883  sizes_t const prev_sizes{ get_all_sizes() };
3884 
3885  range_t const first_element_to_erase_range{ this->range_unsafe(first_element_to_erase_it) };
3886  range_t const last_element_to_erase_range{ this->range_unsafe(last) };
3887 
3888  //
3889  // Note that element_range returns element size adjusted with padding
3890  // that is required for the next element to be properly aligned.
3891  //
3892  size_type const bytes_to_copy{ prev_sizes.used_capacity().size - last_element_to_erase_range.buffer_end };
3893  size_type const bytes_erased{ last_element_to_erase_range.buffer_end - first_element_to_erase_range.begin() };
3894  //
3895  // Shift all elements after the last element that we are erasing
3896  // to the position where first erased element used to be
3897  //
3898  move_data(buff().begin + first_element_to_erase_range.begin(),
3899  buff().begin + last_element_to_erase_range.buffer_end,
3900  bytes_to_copy);
3901  buff().last -= bytes_erased;
3902 
3903  validate_pointer_invariants();
3904  validate_data_invariants();
3905  }
3912  void erase_all_after(iterator const &it) noexcept {
3913  validate_pointer_invariants();
3914  validate_iterator(it);
3915 
3916  //
3917  // erasing after end iterator is a no-op
3918  //
3919  if (end() != it) {
3920  buff().last = it.get_ptr();
3921  set_no_next_element(buff().last);
3922 
3923  validate_pointer_invariants();
3924  validate_data_invariants();
3925  }
3926  }
3934  iterator erase_all_from(iterator const &it) noexcept {
3935  validate_pointer_invariants();
3936  validate_iterator(it);
3937 
3938  //
3939  // erasing after end iterator is a no-op
3940  //
3941  if (end() != it) {
3942 
3943  if (it == begin()) {
3944  buff().last = nullptr;
3945  return end();
3946  }
3947 
3948  range_t const element_rtange{ range_unsafe(it) };
3949  iterator const element_before = find_element_before(element_rtange.begin());
3950  FFL_CODDING_ERROR_IF(end() == element_before);
3951 
3952  erase_all_after(element_before);
3953 
3954  set_no_next_element(element_before.get_ptr());
3955 
3956  return element_before;
3957  }
3958 
3959  return end();
3960  }
3964  void erase_all() noexcept {
3965  validate_pointer_invariants();
3966  buff().last = nullptr;
3967  }
3968 
3976  iterator erase(iterator const &it) noexcept {
3977  validate_pointer_invariants();
3978  validate_iterator_not_end(it);
3979 
3980  if (begin() == it) {
3981  pop_front();
3982  return begin();
3983  }
3984 
3985  if (last() == it) {
3986  pop_back();
3987  return end();
3988  }
3989 
3990  sizes_t const prev_sizes{ get_all_sizes() };
3991  range_t const element_range{ range_unsafe(it) };
3992  //
3993  // Size of all elements after element that we are erasing,
3994  // not counting padding after last element.
3995  //
3996  size_type const tail_size{ prev_sizes.used_capacity().size - element_range.buffer_end };
3997  //
3998  // Shifting remaining elements will erase this element.
3999  //
4000  move_data(buff().begin + element_range.begin(),
4001  buff().begin + element_range.buffer_end,
4002  tail_size);
4003 
4004  buff().last -= element_range.buffer_size();
4005 
4006  validate_pointer_invariants();
4007  validate_data_invariants();
4008 
4009  return it;
4010  }
4019  iterator erase(iterator const &start, iterator const &end) noexcept {
4020  validate_pointer_invariants();
4021  validate_iterator_not_end(start);
4022  validate_iterator(end);
4023  //
4024  // If it is an empty range then we are done
4025  //
4026  if (start == end) {
4027  return start;
4028  }
4029  //
4030  // If we are erasing all elements after start
4031  //
4032  if (this->end() == end) {
4033  return erase_all_from(start);
4034  }
4035  //
4036  // The rest of function deals with erasing from start to some existing element.
4037  // We need to shift all elements that we are keeping in place where start is.
4038  //
4039  sizes_t const prev_sizes{ get_all_sizes() };
4040 
4041  range_t const start_range = range_unsafe(start);
4042  range_t const end_range = range_unsafe(end);
4043  size_type const bytes_to_copy{ prev_sizes.used_capacity().size - end_range.buffer_end };
4044  size_type const bytes_erased{ end_range.begin() - start_range.begin() };
4045 
4046  move_data(buff().begin + start_range.begin(),
4047  buff().begin + end_range.begin(),
4048  bytes_to_copy);
4049 
4050  buff().last -= bytes_erased;
4051 
4052  validate_pointer_invariants();
4053  validate_data_invariants();
4054 
4055  return start;
4056  }
4064  void swap(flat_forward_list &other) noexcept (allocator_type_traits::propagate_on_container_swap::value ||
4065  allocator_type_traits::propagate_on_container_move_assignment::value) {
4066  if constexpr (allocator_type_traits::propagate_on_container_swap::value) {
4067  std::swap(get_allocator(), other.get_allocator());
4068  std::swap(buff().begin, other.buff().begin);
4069  std::swap(buff().end, other.buff().end);
4070  std::swap(buff().last, other.buff().last);
4071  } else {
4072  flat_forward_list tmp{ std::move(other) };
4073  other = std::move(*this);
4074  *this = std::move(tmp);
4075  }
4076  }
4084  template <typename LESS_F>
4085  void sort(LESS_F const &fn) {
4086  //
4087  // Create a vector of iterators to all elements in the
4088  // list and sort it using function passed to us by the
4089  // user.
4090  //
4091  std::vector<const_iterator> iterator_array;
4092  for (const_iterator i = begin(); i != end(); ++i) {
4093  iterator_array.push_back(i);
4094  }
4095  std::sort(iterator_array.begin(),
4096  iterator_array.end(),
4097  [&fn](const_iterator const &lhs,
4098  const_iterator const &rhs) -> bool {
4099 
4100  return fn(*lhs, *rhs);
4101  });
4102 
4103  //
4104  // Now that we have an array of sorted iterators
4105  // copy elements to the new list in the sorting order
4106  //
4107  flat_forward_list sorted_list(get_allocator());
4108  sorted_list.resize_buffer(used_capacity());
4109  for (const_iterator const &i : iterator_array) {
4110  sorted_list.push_back(used_size(i), i.get_ptr());
4111  }
4112 
4113  //
4114  // Swap with sorted list
4115  //
4116  swap(sorted_list);
4117  }
4122  void reverse() {
4123  flat_forward_list reversed_list(get_allocator());
4124  reversed_list.resize_buffer(used_capacity());
4125  for (iterator const &i = begin(); i != end(); ++i) {
4126  reversed_list.push_front(i.get_ptr(), element_used_size(i));
4127  }
4128  //
4129  // Swap with reversed list
4130  //
4131  swap(reversed_list);
4132  }
4142  template<class F>
4143  void merge(flat_forward_list &other,
4144  F const &fn) {
4145 
4146  flat_forward_list merged_list(get_allocator());
4147 
4148  iterator this_start = begin();
4149  iterator const this_end = end();
4150  iterator other_start = other.begin();
4151  iterator const other_end = other.end();
4152 
4153  for ( ; this_start != this_end && other_start != other_end;) {
4154  if (fn(*this_start, *other_start)) {
4155  merged_list.push_back(required_size(this_start), this_start.get_ptr());
4156  ++this_start;
4157  } else {
4158  merged_list.push_back(other.required_size(other_start), other_start.get_ptr());
4159  ++other_start;
4160  }
4161  }
4162 
4163  for (; this_start != this_end; ++this_start) {
4164  merged_list.push_back(required_size(this_start), this_start.get_ptr());
4165  }
4166 
4167  for (; other_start != other_end; ++other_start) {
4168  merged_list.push_back(other.required_size(other_start), other_start.get_ptr());
4169  }
4170 
4171  swap(merged_list);
4172  other.clear();
4173  }
4180  template<typename F>
4181  void unique(F const &fn) noexcept {
4182  iterator first = begin();
4183  if (first != end()) {
4184  iterator last = end();
4185  iterator after = first;
4186  for (++after; after != end(); ++after) {
4187  if (fn(*first, *after)) {
4188  //
4189  // remember last element for which predicate is true
4190  //
4191  last = after;
4192  } else if (last != end()) {
4193  //
4194  // If predicate is not true then erase (first, last]
4195  // elements after last shift left so first+1 is pointing
4196  // to the first element that is not equal to what we just
4197  // deleted.
4198  //
4199  erase_after_half_closed(first, last);
4200  last = end();
4201  ++first;
4202  after = first;
4203  } else {
4204  //
4205  // nothing to delete, just move first forward
4206  //
4207  first = after;
4208  }
4209  }
4210  }
4211  }
4217  template<typename F>
4218  void remove_if(F const &fn) noexcept {
4219  iterator first = end();
4220  for (iterator last = begin();
4221  last != end();
4222  ++last) {
4223 
4224  if (fn(*last)) {
4225  if (first == end()) {
4226  first = last;
4227  }
4228  } else if (first != end()) {
4229  last = erase(first, last);
4230  first = end();
4231  }
4232  }
4233  }
4238  T &front() noexcept {
4239  validate_pointer_invariants();
4240  FFL_CODDING_ERROR_IF(buff().last == nullptr || buff().begin == nullptr);
4241  return *reinterpret_cast<T *>(buff().begin);
4242  }
4247  T const &front() const noexcept {
4248  validate_pointer_invariants();
4249  FFL_CODDING_ERROR_IF(buff().last == nullptr || buff().begin == nullptr);
4250  return *reinterpret_cast<T *>(buff().begin);
4251  }
4256  T &back() noexcept {
4257  validate_pointer_invariants();
4258  FFL_CODDING_ERROR_IF(buff().last == nullptr);
4259  return *reinterpret_cast<T *>(buff().last);
4260  }
4265  T const &back() const noexcept {
4266  validate_pointer_invariants();
4267  FFL_CODDING_ERROR_IF(buff().last == nullptr);
4268  return *reinterpret_cast<T *>(buff().last);
4269  }
4274  iterator begin() noexcept {
4275  validate_pointer_invariants();
4276  return buff().last ? iterator{ buff().begin }
4277  : end();
4278  }
4283  const_iterator begin() const noexcept {
4284  validate_pointer_invariants();
4285  return buff().last ? const_iterator{ buff().begin }
4286  : cend();
4287  }
4288 
4289  //
4290  // It is not clear how to implement it
4291  // without adding extra boolean flags to iterator.
4292  // Since elements are variable length we need to be able
4293  // to query offset to next, and we cannot not do that
4294  // no before_begin element
4295  //
4296  // iterator before_begin() noexcept {
4297  // }
4298 
4303  iterator last() noexcept {
4304  validate_pointer_invariants();
4305  return buff().last ? iterator{ buff().last }
4306  : end();
4307  }
4312  const_iterator last() const noexcept {
4313  validate_pointer_invariants();
4314  return buff().last ? const_iterator{ buff().last }
4315  : cend();
4316  }
4322  iterator end() noexcept {
4323  validate_pointer_invariants();
4324  if (buff().last) {
4325  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
4326  return iterator{ buff().last + last_element_size.size_padded() };
4327  } else {
4328  return iterator{ };
4329  }
4330  }
4336  const_iterator end() const noexcept {
4337  validate_pointer_invariants();
4338  if (buff().last) {
4339  size_with_padding_t const last_element_size{ traits_traits::get_size(buff().last) };
4340  return const_iterator{ buff().last + last_element_size.size_padded() };
4341  } else {
4342  return const_iterator{ };
4343  }
4344  }
4349  const_iterator cbegin() const noexcept {
4350  return begin();
4351  }
4356  const_iterator clast() const noexcept {
4357  return last();
4358  }
4366  const_iterator cend() const noexcept {
4367  return end();
4368  }
4373  char *data() noexcept {
4374  return buff().begin;
4375  }
4380  char const *data() const noexcept {
4381  return buff().begin;
4382  }
4393  [[nodiscard]] bool revalidate_data(size_type data_size = npos) noexcept {
4394  size_type new_data_size{ total_capacity() };
4395  if (data_size != npos) {
4396  new_data_size = std::min(data_size, new_data_size);
4397  }
4398  auto[valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin,
4399  buff().begin + new_data_size);
4400  buff().last = valid ? buffer_view.last().get_ptr() : nullptr;
4401 
4402  return valid;
4403  }
4413  void shrink_to_fit() {
4414  shrink_to_fit(begin(), end());
4415  tail_shrink_to_fit();
4416  }
4425  void shrink_to_fit(iterator const &first, iterator const &end) {
4426  for (iterator i = first; i != end; ++i) {
4427  shrink_to_fit(i);
4428  }
4429  }
4437  void shrink_to_fit(iterator const &it) {
4438  validate_pointer_invariants();
4439  validate_iterator_not_end(it);
4440 
4441  size_type new_element_size{ required_size(it) };
4442  //
4443  // Make sure that any element, except the last one is padded at the end
4444  //
4445  if (last() != it) {
4446  new_element_size = traits_traits::roundup_to_alignment(new_element_size);
4447  }
4448 
4449  iterator const ret_it = element_resize(it,
4450  new_element_size,
4451  [new_element_size] ([[maybe_unused]] T &buffer,
4452  size_type old_size,
4453  size_type new_size) {
4454  //
4455  // might extend if element was not properly aligned.
4456  // must be shrinking, and
4457  // data must fit new buffer
4458  //
4459  FFL_CODDING_ERROR_IF_NOT(new_size <= new_element_size);
4460  //
4461  // Cannot assert it here since we have not changed next element offset yet
4462  // we will validate element at the end
4463  //
4464  //FFL_CODDING_ERROR_IF_NOT(traits_traits::validate(new_size, buffer));
4465  });
4466  //
4467  // We are either shrinking or not changing size
4468  // so there should be no reallocation
4469  //
4470  FFL_CODDING_ERROR_IF_NOT(it == ret_it);
4471  }
4482  iterator element_add_size(iterator const &it,
4483  size_type size_to_add) {
4484  validate_pointer_invariants();
4485  validate_iterator_not_end(it);
4486 
4487  return element_resize(it,
4488  traits_traits::roundup_to_alignment(used_size(it) + size_to_add),
4489  [] (T &buffer,
4490  size_type old_size,
4491  size_type new_size) {
4492  //
4493  // must be extending, and
4494  // data must fit new buffer
4495  //
4496  FFL_CODDING_ERROR_IF_NOT(old_size <= new_size);
4497  zero_buffer(reinterpret_cast<char *>(&buffer) + old_size, new_size - old_size);
4498  FFL_CODDING_ERROR_IF_NOT(traits_traits::validate(new_size, buffer));
4499  });
4500  }
4512  [[nodiscard]] bool try_element_add_size(iterator const &it,
4513  size_type size_to_add) {
4514  validate_pointer_invariants();
4515  validate_iterator_not_end(it);
4516 
4517  return try_element_resize(it,
4518  traits_traits::roundup_to_alignment(used_size(it) + size_to_add),
4519  [] (T &buffer,
4520  size_type old_size,
4521  size_type new_size) {
4522  //
4523  // must be extending, and
4524  // data must fit new buffer
4525  //
4526  FFL_CODDING_ERROR_IF_NOT(old_size <= new_size);
4527  zero_buffer(reinterpret_cast<char *>(&buffer) + old_size, new_size - old_size);
4528  FFL_CODDING_ERROR_IF_NOT(traits_traits::validate(new_size, buffer));
4529  });
4530  }
4543  template <typename F>
4544  iterator element_resize(iterator const &it,
4545  size_type new_size,
4546  F const &fn) {
4547  auto[result, new_it] = element_resize_impl(can_reallocate::yes,
4548  it,
4549  new_size,
4550  fn);
4551  FFL_CODDING_ERROR_IF(!result);
4552  return new_it;
4553  }
4567  template <typename F>
4568  [[nodiscard]] bool try_element_resize(iterator const &it,
4569  size_type new_size,
4570  F const &fn) {
4571  auto[result, new_it] = element_resize_impl(can_reallocate::no,
4572  it,
4573  new_size,
4574  fn);
4575  FFL_CODDING_ERROR_IF_NOT(new_it == it);
4576  return result;
4577  }
4583  size_type required_size(const_iterator const &it) const noexcept {
4584  validate_pointer_invariants();
4585  validate_iterator_not_end(it);
4586  return size_unsafe(it).size;
4587  }
4593  size_type used_size(const_iterator const &it) const noexcept {
4594  validate_pointer_invariants();
4595  //validate_iterator_not_end(it);
4596 
4597  return used_size_unsafe(it);
4598  }
4611  range_t range(const_iterator const &it) const noexcept {
4612  validate_iterator_not_end(it);
4613 
4614  return range_unsafe(it);
4615  }
4616 
4631  range_t closed_range(const_iterator const &begin, const_iterator const &last) const noexcept {
4632  validate_iterator_not_end(begin);
4633  validate_iterator_not_end(last);
4634 
4635  return closed_range_unsafe(begin, last);
4636  }
4652  range_t half_open_range(const_iterator const &begin, const_iterator const &end) const noexcept {
4653  validate_iterator_not_end(begin);
4654  validate_iterator_not_end(end);
4655 
4656  return half_open_range_usafe(begin, end);
4657  }
4669  bool contains(const_iterator const &it, size_type position) const noexcept {
4670  validate_iterator(it);
4671  if (cend() == it || npos == position) {
4672  return false;
4673  }
4674  range_t const r{ range_unsafe(it) };
4675  return r.buffer_contains(position);
4676  }
4687  iterator find_element_before(size_type position) noexcept {
4688  validate_pointer_invariants();
4689  if (empty_unsafe()) {
4690  return end();
4691  }
4692  auto const [is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin,
4693  buff().begin + position);
4694  unused_variable(is_valid);
4695 
4696  if (!buffer_view.empty()) {
4697  return iterator{ const_cast<char *>(buffer_view.last().get_ptr()) };
4698  }
4699  return end();
4700  }
4711  const_iterator find_element_before(size_type position) const noexcept {
4712  validate_pointer_invariants();
4713  if (empty_unsafe()) {
4714  return end();
4715  }
4716  auto[is_valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin,
4717  buff().begin + position);
4718  if (!buffer_view.empty()) {
4719  return const_iterator{ buffer_view.last() };
4720  }
4721  return end();
4722  }
4732  iterator find_element_at(size_type position) noexcept {
4733  iterator it = find_element_before(position);
4734  if (end() != it) {
4735  ++it;
4736  if (end() != it) {
4737  FFL_CODDING_ERROR_IF_NOT(contains(it, position));
4738  return it;
4739  }
4740  }
4741  return end();
4742  }
4752  const_iterator find_element_at(size_type position) const noexcept {
4753  const_iterator it = find_element_before(position);
4754  if (cend() != it) {
4755  ++it;
4756  if (cend() != it) {
4757  FFL_CODDING_ERROR_IF_NOT(contains(it, position));
4758  return it;
4759  }
4760  }
4761  return end();
4762  }
4773  iterator find_element_after(size_type position) noexcept {
4774  iterator it = find_element_at(position);
4775  if (end() != it) {
4776  ++it;
4777  if (end() != it) {
4778  return it;
4779  }
4780  }
4781  return end();
4782  }
4793  const_iterator find_element_after(size_type position) const noexcept {
4794  const_iterator it = find_element_at(position);
4795  if (cend() != it) {
4796  ++it;
4797  if (cend() != it) {
4798  return it;
4799  }
4800  }
4801  return end();
4802  }
4810  size_type size() const noexcept {
4811  validate_pointer_invariants();
4812  size_type s = 0;
4813  std::for_each(cbegin(), cend(), [&s](T const &) noexcept {
4814  ++s;
4815  });
4816  return s;
4817  }
4826  bool empty() const noexcept {
4827  validate_pointer_invariants();
4828  return buff().last == nullptr;
4829  }
4834  size_type used_capacity() const noexcept {
4835  validate_pointer_invariants();
4836  sizes_t const s{ get_all_sizes() };
4837  return s.used_capacity().size;
4838  }
4842  size_type total_capacity() const noexcept {
4843  validate_pointer_invariants();
4844  return buff().end - buff().begin;
4845  }
4850  size_type remaining_capacity() const noexcept {
4851  validate_pointer_invariants();
4852  sizes_t const s{ get_all_sizes() };
4853  return s.remaining_capacity_for_append();
4854  }
4862  void fill_padding(int fill_byte = 0,
4863  bool zero_unused_capacity = true) noexcept {
4864  validate_pointer_invariants();
4865  //
4866  // Fill gaps between any elements up to the last
4867  //
4868  auto const last{ this->last() };
4869  //
4870  // zero padding of each element
4871  //
4872  for (auto it = begin(); last != it; ++it) {
4873  range_t const element_range{ range_unsafe(it) };
4874  element_range.fill_unused_capacity_data_ptr(it.get_ptr(), fill_byte);
4875  }
4876  //
4877  // If we told so then zero tail
4878  //
4879  if (zero_unused_capacity) {
4880  sizes_t const prev_sizes{ get_all_sizes() };
4881  if (prev_sizes.used_capacity().size > 0) {
4882  size_type const last_element_end{ prev_sizes.last_element.begin() + prev_sizes.last_element.data_size() };
4883  size_type const unuset_tail_size{ prev_sizes.total_capacity - last_element_end };
4884  fill_buffer(buff().begin + last_element_end,
4885  fill_byte,
4886  unuset_tail_size);
4887  }
4888  }
4889 
4890  validate_pointer_invariants();
4891  validate_data_invariants();
4892  }
4893 
4894 private:
4895 
4901  enum class can_reallocate : bool {
4905  no,
4909  yes,
4910  };
4911 
4931  template <typename F>
4932  [[nodiscard]] bool try_emplace_back_impl(can_reallocate reallocation_policy,
4933  size_type element_size,
4934  F const &fn) {
4935  validate_pointer_invariants();
4936 
4937  FFL_CODDING_ERROR_IF(element_size < traits_traits::minimum_size());
4938 
4939  char *new_buffer{ nullptr };
4940  size_t new_buffer_size{ 0 };
4941  auto deallocate_buffer{ make_scoped_deallocator(&new_buffer, &new_buffer_size) };
4942 
4943  sizes_t const prev_sizes{ get_all_sizes() };
4944 
4945  char *cur{ nullptr };
4946  //
4947  // We are appending. New last element does not have to be padded
4948  // since there will be no elements after. We do need to pad the
4949  // previous last element so the new last element will be padded
4950  //
4951  if (prev_sizes.remaining_capacity_for_append() < element_size) {
4952  if (reallocation_policy == can_reallocate::no) {
4953  return false;
4954  }
4955  new_buffer_size = traits_traits::roundup_to_alignment(prev_sizes.total_capacity) +
4956  (element_size - prev_sizes.remaining_capacity_for_append());
4957  new_buffer = allocate_buffer(new_buffer_size);
4958  cur = new_buffer + prev_sizes.used_capacity().size_padded();
4959  } else {
4960  cur = buff().begin + prev_sizes.used_capacity().size_padded();
4961  }
4962 
4963  fn(*traits_traits::ptr_to_t(cur), element_size);
4964 
4965  set_no_next_element(cur);
4966  //
4967  // After element was constructed it cannot be larger than
4968  // size requested for this element.
4969  //
4970  size_with_padding_t const cur_element_size{ traits_traits::get_size(cur) };
4971  FFL_CODDING_ERROR_IF(element_size < cur_element_size.size);
4972  //
4973  // element that used to be last becomes
4974  // an element in the middle so we need to change
4975  // its next element pointer
4976  //
4977  if (buff().last) {
4978  set_next_offset(buff().last, prev_sizes.last_element.data_size_padded());
4979  }
4980  //
4981  // swap new buffer and new buffer
4982  //
4983  if (new_buffer != nullptr) {
4984  //
4985  // If we are reallocating buffer then move existing
4986  // elements to the new buffer.
4987  //
4988  if (buff().begin) {
4989  copy_data(new_buffer, buff().begin, prev_sizes.used_capacity().size);
4990  }
4991  commit_new_buffer(new_buffer, new_buffer_size);
4992  }
4993  //
4994  // Element that we've just added is the new last element
4995  //
4996  buff().last = cur;
4997 
4998  validate_pointer_invariants();
4999  validate_data_invariants();
5000 
5001  return true;
5002  }
5031  template <typename F>
5032  [[nodiscard]] std::pair<bool, iterator> try_emplace_impl(can_reallocate reallocation_policy,
5033  iterator const &it,
5034  size_type new_element_size,
5035  F const &fn) {
5036 
5037  validate_pointer_invariants();
5038  validate_iterator(it);
5039 
5040  FFL_CODDING_ERROR_IF(new_element_size < traits_traits::minimum_size());
5041 
5042  if (end() == it) {
5043  bool result{ try_emplace_back_impl(reallocation_policy,
5044  new_element_size,
5045  fn) };
5046  return std::make_pair(result, last());
5047  }
5048  //
5049  // When implacing in the middle of list we need to preserve alignment of the
5050  // next element so we need to make sure we add padding to the requested size.
5051  // An alternative would be to rely on the caller to make sure size is padded
5052  // and call out codding error if it is not.
5053  //
5054  size_t new_element_size_aligned = traits_traits::roundup_to_alignment(new_element_size);
5055 
5056  char *new_buffer{ nullptr };
5057  size_t new_buffer_size{ 0 };
5058  auto deallocate_buffer{ make_scoped_deallocator(&new_buffer, &new_buffer_size) };
5059 
5060  sizes_t const prev_sizes{ get_all_sizes() };
5061  range_t const element_range{ this->range_unsafe(it) };
5062  //
5063  // Note that in this case old element that was in that position
5064  // is a part of the tail
5065  //
5066  size_type const tail_size{ prev_sizes.used_capacity().size - element_range.begin() };
5067 
5068  char *begin{ nullptr };
5069  char *cur{ nullptr };
5070  //
5071  // We are inserting new element in the middle.
5072  // We do not need make last element aligned.
5073  // We need to add padding for the element that we are inserting to
5074  // keep element that we are shifting right properly aligned
5075  //
5076  if (prev_sizes.remaining_capacity_for_insert() < new_element_size_aligned) {
5077  if (can_reallocate::no == reallocation_policy) {
5078  return std::make_pair(false, it);
5079  }
5080  new_buffer_size = traits_traits::roundup_to_alignment(prev_sizes.total_capacity) +
5081  (new_element_size_aligned - prev_sizes.remaining_capacity_for_insert());
5082  new_buffer = allocate_buffer(new_buffer_size);
5083  cur = new_buffer + element_range.begin();
5084  begin = new_buffer;
5085  } else {
5086  cur = it.get_ptr();
5087  begin = buff().begin;
5088  }
5089  char *new_tail_start{ nullptr };
5090  //
5091  // Common part where we construct new part of the buffer
5092  //
5093  // Move tail forward.
5094  // This will free space to insert new element
5095  //
5096  if (!new_buffer) {
5097  new_tail_start = begin + element_range.begin() + new_element_size_aligned;
5098  move_data(new_tail_start, it.get_ptr(), tail_size);
5099  }
5100  //
5101  // construct
5102  //
5103  try {
5104  //
5105  // Pass to the constructor requested size, not padded size
5106  //
5107  fn(*traits_traits::ptr_to_t(cur), new_element_size);
5108  } catch (...) {
5109  //
5110  // on failure to construct move tail back
5111  // only if we are not reallocating
5112  //
5113  if (!new_buffer) {
5114  move_data(it.get_ptr(), new_tail_start, tail_size);
5115  }
5116  throw;
5117  }
5118 
5119  set_next_offset(cur, new_element_size_aligned);
5120  //
5121  // For types with next element pointer data can consume less than requested size.
5122  // for types that do not have next element pointer size must match exactly, otherwise
5123  // we would not be able to get to the next element
5124  //
5125  size_with_padding_t const cur_element_size{ traits_traits::get_size(cur) };
5126  if constexpr (traits_traits::has_next_offset_v) {
5127  FFL_CODDING_ERROR_IF(new_element_size < cur_element_size.size ||
5128  new_element_size_aligned < cur_element_size.size_padded());
5129  } else {
5130  FFL_CODDING_ERROR_IF_NOT(new_element_size == cur_element_size.size &&
5131  new_element_size_aligned == cur_element_size.size_padded());
5132  }
5133  //
5134  // now see if we need to update existing
5135  // buffer or swap with the new buffer
5136  //
5137  if (new_buffer != nullptr) {
5138  //
5139  // If we are reallocating buffer then move all elements
5140  // before and after position that we are inserting to
5141  //
5142  if (buff().begin) {
5143  copy_data(new_buffer, buff().begin, element_range.begin());
5144  copy_data(cur + new_element_size_aligned, it.get_ptr(), tail_size);
5145  }
5146  commit_new_buffer(new_buffer, new_buffer_size);
5147  }
5148  //
5149  // Last element moved ahead by the size of the new inserted element
5150  //
5151  buff().last = buff().begin + prev_sizes.last_element.begin() + new_element_size_aligned;
5152 
5153  validate_pointer_invariants();
5154  validate_data_invariants();
5155  //
5156  // Return iterator pointing to the new inserted element
5157  //
5158  return std::make_pair(true, iterator{ cur });
5159  }
5168  bool empty_unsafe() const noexcept {
5169  return buff().last == nullptr;
5170  }
5171 
5184  template <typename F>
5185  [[nodiscard]] std::pair<bool, iterator> resize_last_element(can_reallocate reallocation_policy,
5186  size_type new_size,
5187  F const &fn) {
5188 
5189  validate_pointer_invariants();
5190 
5191  sizes_t const prev_sizes{ get_all_sizes() };
5192  difference_type const element_size_diff{ static_cast<difference_type>(new_size - prev_sizes.last_element.data_size()) };
5193  //
5194  // If last element is shrinking or
5195  // if it does not reach capacity available in the buffer
5196  // for growing without need to worry about padding
5197  // then just call functor to modify element data.
5198  // there is no additional post processing after success
5199  // of failure.
5200  //
5201  // Otherwise allocate new buffer, copy element there,
5202  // modify it, and on success copy head
5203  //
5204  if (element_size_diff < 0 ||
5205  prev_sizes.remaining_capacity_for_insert() >= static_cast<size_type>(element_size_diff)) {
5206 
5207  fn(*traits_traits::ptr_to_t(buff().last),
5208  prev_sizes.last_element.data_size(),
5209  new_size);
5210 
5211  } else {
5212 
5213  if (can_reallocate::no == reallocation_policy) {
5214  return std::make_pair(false, last());
5215  }
5216 
5217  char *new_buffer{ nullptr };
5218  size_type new_buffer_size{ 0 };
5219  auto deallocate_buffer{ make_scoped_deallocator(&new_buffer, &new_buffer_size) };
5220 
5221  new_buffer_size = prev_sizes.used_capacity().size + new_size - prev_sizes.last_element.data_size();
5222  new_buffer = allocate_buffer(new_buffer_size);
5223 
5224  char *new_last_ptr{ new_buffer + prev_sizes.last_element.begin() };
5225  //
5226  // copy element
5227  //
5228  copy_data(new_last_ptr,
5229  buff().begin + prev_sizes.last_element.begin(),
5230  prev_sizes.last_element.data_size());
5231  //
5232  // change element
5233  //
5234  fn(*traits_traits::ptr_to_t(new_last_ptr),
5235  prev_sizes.last_element.data_size(),
5236  new_size);
5237  //
5238  // copy head
5239  //
5240  copy_data(new_buffer, buff().begin, prev_sizes.last_element.begin());
5241  //
5242  // commit mew buffer
5243  //
5244  commit_new_buffer(new_buffer, new_buffer_size);
5245  buff().last = new_last_ptr;
5246  }
5247 
5248  validate_pointer_invariants();
5249  validate_data_invariants();
5250 
5251  return std::make_pair(true, last());
5252  }
5265  template <typename F>
5266  [[nodiscard]] std::pair<bool, iterator> element_resize_impl(can_reallocate reallocation_policy,
5267  iterator const &it,
5268  size_type new_size,
5269  F const &fn) {
5270  //
5271  // Resize to 0 is same as erase
5272  //
5273  if (0 == new_size) {
5274  return std::make_pair(true, erase(it));
5275  }
5276 
5277  FFL_CODDING_ERROR_IF(new_size < traits_traits::minimum_size());
5278  //
5279  // Separately handle case of resizing the last element
5280  // we do not need to deal with tail and padding
5281  // for the next element
5282  //
5283  if (last() == it) {
5284  return resize_last_element(reallocation_policy, new_size, fn);
5285  }
5286  //
5287  // Now deal with resizing element in the middle
5288  // or at the head
5289  //
5290  validate_pointer_invariants();
5291  validate_iterator_not_end(it);
5292 
5293  iterator result_it;
5294 
5295  sizes_t prev_sizes{ get_all_sizes() };
5296  range_t element_range_before{ range_unsafe(it) };
5297  //
5298  // We will change element size by padded size to make sure
5299  // that next element stays padded
5300  //
5301  size_type new_size_padded{ traits_traits::roundup_to_alignment(new_size) };
5302  //
5303  // Calculate tail size
5304  //
5305  size_type const tail_size{ prev_sizes.used_capacity().size - element_range_before.buffer_end };
5306  //
5307  // By how much element size is changing
5308  //
5309  difference_type const element_size_diff{ static_cast<difference_type>(new_size_padded - element_range_before.buffer_size()) };
5310  //
5311  // This branch handles case when we do not need to reallocate buffer
5312  // and we have sufficiently large buffer.
5313  //
5314  if (element_size_diff < 0 ||
5315  prev_sizes.remaining_capacity_for_insert() >= static_cast<size_type>(element_size_diff)) {
5316 
5317  size_type tail_start_offset = element_range_before.buffer_end;
5318  //
5319  // If element is getting extended in size then shift tail to the
5320  // right to make space for element data, and remember new tail
5321  // position
5322  //
5323  if (new_size_padded > element_range_before.buffer_size()) {
5324  move_data(buff().begin + element_range_before.begin() + new_size_padded,
5325  buff().begin + tail_start_offset,
5326  tail_size);
5327 
5328  tail_start_offset = element_range_before.begin() + new_size_padded;
5329  }
5330  //
5331  // Regardless how we are exiting scope, by exception or not,
5332  // shift tail left so it would be right after the new end of
5333  // the element
5334  //
5335  auto fix_tail{ make_scope_guard([this,
5336  it,
5337  new_size,
5338  new_size_padded,
5339  tail_start_offset,
5340  tail_size,
5341  &element_range_before] {
5342  //
5343  // See how much space elements consumes now
5344  //
5345  size_with_padding_t const element_size_after { this->size_unsafe(it)};
5346  //
5347  // New element size must not be larger than size that it is
5348  // allowed to grow by
5349  //
5350  FFL_CODDING_ERROR_IF(element_size_after.size > new_size);
5351  //
5352  // If we have next pointer then next element should start after new_size_padded
5353  // otherwise if should start after padded size of the element
5354  //
5355  range_t element_range_after{ {element_range_before.begin(),
5356  element_range_before.begin() + element_size_after.size,
5357  element_range_before.begin() + new_size_padded} };
5358  element_range_after.verify();
5359  //
5360  // New evement end must not pass current tail position
5361  //
5362  FFL_CODDING_ERROR_IF(element_range_after.buffer_end > tail_start_offset);
5363  //
5364  // if size changed, then shift tail to the left
5365  //
5366  if (element_range_after.buffer_end != element_range_before.buffer_end) {
5367 
5368  move_data(buff().begin + element_range_after.buffer_end,
5369  buff().begin + tail_start_offset,
5370  tail_size);
5371  //
5372  // calculate by how much tail moved
5373  //
5374  difference_type tail_shift{ static_cast<difference_type>(element_range_after.buffer_size() -
5375  element_range_before.buffer_size()) };
5376  //
5377  // Update pointer to last element
5378  //
5379  buff().last += tail_shift;
5380  }
5381 
5382  this->set_next_offset(it.get_ptr(), element_range_after.buffer_size());
5383  }) };
5384 
5385  fn(*traits_traits::ptr_to_t(it.get_ptr()),
5386  element_range_before.buffer_size(),
5387  new_size);
5388 
5389  result_it = it;
5390 
5391  } else {
5392  if (can_reallocate::no == reallocation_policy) {
5393  return std::make_pair(false, it);
5394  }
5395  //
5396  // Buffer is increasing in size so we will need to reallocate buffer
5397  //
5398  char *new_buffer{ nullptr };
5399  size_type new_buffer_size{ 0 };
5400  auto deallocate_buffer{ make_scoped_deallocator(&new_buffer, &new_buffer_size) };
5401 
5402  new_buffer_size = prev_sizes.used_capacity().size + new_size_padded - element_range_before.buffer_size();
5403  new_buffer = allocate_buffer(new_buffer_size);
5404  //
5405  // copy element that we are changing to the new buffer
5406  //
5407  copy_data(new_buffer + element_range_before.begin(),
5408  buff().begin + element_range_before.begin(),
5409  element_range_before.buffer_size());
5410  //
5411  // change element
5412  //
5413  fn(*traits_traits::ptr_to_t(new_buffer + element_range_before.begin()),
5414  element_range_before.buffer_size(),
5415  new_size);
5416  //
5417  // fn did not throw an exception, and remainder of
5418  // function is noexcept
5419  //
5420  result_it = iterator{ new_buffer + element_range_before.begin() };
5421  //
5422  // copy head
5423  //
5424  copy_data(new_buffer, buff().begin, element_range_before.begin());
5425  //
5426  // See how much space elements consumes now
5427  //
5428  size_with_padding_t const element_size_after = this->size_unsafe(result_it);
5429  //
5430  // New element size must not be larger than size that it is
5431  // allowed to grow by
5432  //
5433  FFL_CODDING_ERROR_IF(element_size_after.size > new_size);
5434  //
5435  // If we have next pointer then next element should start after new_size_padded
5436  // otherwise if should start after padded size of the element
5437  //
5438  range_t element_range_after{ { element_range_before.begin(),
5439  element_range_before.begin() + element_size_after.size,
5440  element_range_before.begin() + new_size_padded } };
5441  element_range_after.verify();
5442  //
5443  // Copy tail
5444  //
5445  move_data(new_buffer + element_range_after.buffer_end,
5446  buff().begin + element_range_before.buffer_end,
5447  tail_size);
5448  //
5449  // commit mew buffer
5450  //
5451  commit_new_buffer(new_buffer, new_buffer_size);
5452  //
5453  // calculate by how much tail moved
5454  //
5455  difference_type tail_shift{ static_cast<difference_type>(element_range_after.buffer_size() -
5456  element_range_before.buffer_size()) };
5457  //
5458  // Update pointer to last element
5459  //
5460  buff().last = buff().begin + prev_sizes.last_element.begin() + tail_shift;
5461  //
5462  // fix offset to the next element
5463  //
5464  this->set_next_offset(result_it.get_ptr(), element_range_after.buffer_size());
5465  }
5466 
5467  validate_pointer_invariants();
5468  validate_data_invariants();
5469  //
5470  // Return iterator pointing to the new inserted element
5471  //
5472  return std::make_pair(true, result_it);
5473  }
5478  [[nodiscard]] constexpr bool has_one_or_no_entry() const noexcept {
5479  return buff().last == buff().begin;
5480  }
5485  [[nodiscard]] constexpr bool has_exactly_one_entry() const noexcept {
5486  return nullptr != buff().last &&
5487  buff().last == buff().begin;
5488  }
5495  constexpr static void set_no_next_element(char *buffer) noexcept {
5496  set_next_offset(buffer, 0);
5497  }
5505  constexpr static void set_next_offset([[maybe_unused]] char *buffer, [[maybe_unused]] size_t size) noexcept {
5506  if constexpr (traits_traits::has_next_offset_v) {
5507  traits_traits::set_next_offset(buffer, size);
5508  }
5509  }
5517  void move_allocator_from(flat_forward_list &&other) {
5518  alloc() = std::move(other.alloc());
5519  }
5526  void move_from(flat_forward_list &&other) noexcept {
5527  clear();
5528  buff().begin = other.buff().begin;
5529  buff().end = other.buff().end;
5530  buff().last = other.buff().last;
5531  other.buff().begin = nullptr;
5532  other.buff().end = nullptr;
5533  other.buff().last = nullptr;
5534  }
5542  void try_move_from(flat_forward_list &&other) {
5543  if (other.get_allocator() == get_allocator()) {
5544  move_from(std::move(other));
5545  } else {
5546  copy_from(other);
5547  }
5548  }
5553  void copy_from(flat_forward_list const &other) {
5554  clear();
5555  if (other.buff().last) {
5556  sizes_t const other_sizes{ other.get_all_sizes() };
5557  buff().begin = allocate_buffer(other_sizes.used_capacity().size);
5558  copy_data(buff().begin, other.buff().begin, other_sizes.used_capacity().size);
5559  buff().end = buff().begin + other_sizes.used_capacity().size;
5560  buff().last = buff().begin + other_sizes.last_element.begin();
5561  }
5562  }
5568  [[nodiscard]] char *allocate_buffer(size_t buffer_size) {
5569  char *ptr{ allocator_type_traits::allocate(alloc(), buffer_size) };
5570  FFL_CODDING_ERROR_IF(nullptr == ptr);
5571  return ptr;
5572  }
5579  void deallocate_buffer(char *buffer, size_t buffer_size) noexcept {
5580  FFL_CODDING_ERROR_IF(0 == buffer_size || nullptr == buffer);
5581  try {
5582  allocator_type_traits::deallocate(alloc(), buffer, buffer_size);
5583  } catch (...) {
5584  FFL_CRASH_APPLICATION();
5585  }
5586  }
5595  void commit_new_buffer(char *&buffer, size_t &buffer_size) noexcept {
5596  char *old_begin = buff().begin;
5597  FFL_CODDING_ERROR_IF(buff().end < buff().begin);
5598  size_type old_size = buff().end - buff().begin;
5599  FFL_CODDING_ERROR_IF(buffer == nullptr && buffer_size != 0);
5600  FFL_CODDING_ERROR_IF(buffer != nullptr && buffer_size == 0);
5601  buff().begin = buffer;
5602  buff().end = buff().begin + buffer_size;
5603  buffer = old_begin;
5604  buffer_size = old_size;
5605  }
5616  [[nodiscard]] auto make_scoped_deallocator(char **buffer, size_t *buffer_size) noexcept {
5617  return make_scope_guard([this, buffer, buffer_size]() {
5618  if (*buffer) {
5619  deallocate_buffer(*buffer, *buffer_size);
5620  *buffer = nullptr;
5621  *buffer_size = 0;
5622  }
5623  });
5624  }
5629  void validate_data_invariants() const noexcept {
5630 #ifdef FFL_DBG_CHECK_DATA_VALID
5631  if (buff().last) {
5632  size_with_padding_t const last_element_size = traits_traits::get_size(buff().last);
5633  //
5634  // For element types that have offset of next element use entire buffer for validation
5635  // for element types that do not have offset to the next element, we have to limit
5636  // by the end of the last element.
5637  // If there is sufficient reservation after last element then validate would not know
5638  // where to stop, and might fail.
5639  //
5640  size_type buffer_length{ 0 };
5641  if constexpr (traits_traits::has_next_offset_v) {
5642  buffer_length = static_cast<size_type>(buff().end - buff().begin);
5643  } else {
5644  buffer_length = static_cast<size_type>(buff().last - buff().begin) + last_element_size.size;
5645  }
5646 
5647  size_type const last_element_offset{ static_cast<size_type>(buff().last - buff().begin) };
5648  FFL_CODDING_ERROR_IF(buffer_length < (last_element_offset + last_element_size.size));
5649 
5650  auto const [valid, buffer_view] = flat_forward_list_validate<T, TT>(buff().begin, buff().begin + buffer_length);
5651  FFL_CODDING_ERROR_IF_NOT(valid);
5652  FFL_CODDING_ERROR_IF_NOT(buffer_view.last().get_ptr() == buff().last);
5653  }
5654 #endif //FFL_DBG_CHECK_DATA_VALID
5655  }
5659  void validate_pointer_invariants() const noexcept {
5660  buff().validate();
5661  }
5666  void validate_iterator(const_iterator const &it) const noexcept {
5667  //
5668  // If we do not have any valid elements then
5669  // only end iterator is valid.
5670  // Otherwise iterator should be an end or point somewhere
5671  // between begin of the buffer and start of the first element
5672  //
5673  if (empty_unsafe()) {
5674  FFL_CODDING_ERROR_IF_NOT(cend() == it);
5675  } else {
5676  FFL_CODDING_ERROR_IF_NOT(cend() == it ||
5677  (buff().begin <= it.get_ptr() && it.get_ptr() <= buff().last));
5678  validate_compare_to_all_valid_elements(it);
5679  }
5680  }
5686  void validate_iterator_not_end(const_iterator const &it) const noexcept {
5687  //
5688  // Used in case when end iterator is meaningless.
5689  // Validates that container is not empty,
5690  // and iterator is pointing somewhere between
5691  // begin of the buffer and start of the first element
5692  //
5693  FFL_CODDING_ERROR_IF(cend() == it);
5694  FFL_CODDING_ERROR_IF(const_iterator{} == it);
5695  FFL_CODDING_ERROR_IF_NOT(buff().begin <= it.get_ptr() && it.get_ptr() <= buff().last);
5696  validate_compare_to_all_valid_elements(it);
5697  }
5703  void validate_compare_to_all_valid_elements([[maybe_unused]] const_iterator const &it) const noexcept {
5704 #ifdef FFL_DBG_CHECK_ITERATOR_VALID
5705  //
5706  // If not end iterator then must point to one of the valid iterators.
5707  //
5708  if (end() != it) {
5709  bool found_match{ false };
5710  for (auto cur = cbegin(); cur != cend(); ++cur) {
5711  if (cur == it) {
5712  found_match = true;
5713  break;
5714  }
5715  }
5716  FFL_CODDING_ERROR_IF_NOT(found_match);
5717  }
5718 #else //FFL_DBG_CHECK_ITERATOR_VALID
5719  it;
5720 #endif //FFL_DBG_CHECK_ITERATOR_VALID
5721  }
5727  size_with_padding_t size_unsafe(const_iterator const &it) const noexcept {
5728  return traits_traits::get_size(it.get_ptr());
5729  }
5743  size_type used_size_unsafe(const_iterator const &it) const noexcept {
5744  if constexpr (traits_traits::has_next_offset_v) {
5745  size_type next_offset = traits_traits::get_next_offset(it.get_ptr());
5746  if (0 == next_offset) {
5747  size_with_padding_t const s{ traits_traits::get_size(it.get_ptr()) };
5748  //
5749  // Last element
5750  //
5751  next_offset = s.size;
5752  }
5753  return next_offset;
5754  } else {
5755  size_with_padding_t s{ traits_traits::get_size(it.get_ptr()) };
5756  //
5757  // buffer might end without including padding for the last element
5758  //
5759  if (last() == it) {
5760  return s.size;
5761  } else {
5762  return s.size_padded();
5763  }
5764  }
5765  }
5783  range_t range_unsafe(const_iterator const &it) const noexcept {
5784  size_with_padding_t const s{ traits_traits::get_size(it.get_ptr()) };
5785  range_t r{};
5786  r.buffer_begin = it.get_ptr() - buff().begin;
5787  r.data_end = r.begin() + s.size;
5788  if constexpr (traits_traits::has_next_offset_v) {
5789  size_type const next_offset = traits_traits::get_next_offset(it.get_ptr());
5790  if (0 == next_offset) {
5791  FFL_CODDING_ERROR_IF(last() != it);
5792  r.buffer_end = r.begin() + s.size;
5793  } else {
5794  r.buffer_end = r.begin() + next_offset;
5795  }
5796  } else {
5797  if (last() == it) {
5798  r.buffer_end = r.begin() + s.size;
5799  } else {
5800  r.buffer_end = r.begin() + s.size_padded();
5801  }
5802  }
5803  return r;
5804  }
5809  range_t closed_range_unsafe(const_iterator const &first, const_iterator const &last) const noexcept {
5810  if (first == last) {
5811  return element_range_unsafe(first);
5812  } else {
5813  range_t first_element_range{ range_unsafe(first) };
5814  range_t last_element_range{ range_unsafe(last) };
5815 
5816  return range_t{ {first_element_range.begin,
5817  last_element_range.data_end,
5818  last_element_range.buffer_end } };
5819  }
5820  }
5828  range_t half_open_range_usafe(const_iterator const &first,
5829  const_iterator const &end) const noexcept {
5830 
5831  if (this->end() == end) {
5832  return closed_range_usafe(first, last());
5833  }
5834 
5835  size_t end_begin{ static_cast<size_t>(end->get_ptr() - buff().begin) };
5836  iterator last{ find_element_before(end_begin) };
5837 
5838  return closed_range_usafe(first, last);
5839  }
5846  sizes_t get_all_sizes() const noexcept {
5847  sizes_t s;
5848 
5849  s.total_capacity = buff().end - buff().begin;
5850 
5851  if (nullptr != buff().last) {
5852  s.last_element = range_unsafe(const_iterator{ buff().last });
5853  }
5854  FFL_CODDING_ERROR_IF(s.total_capacity < s.used_capacity().size);
5855 
5856  return s;
5857  }
5864  buffer_type &buff() noexcept {
5865  return buffer_.get_second();
5866  }
5873  buffer_type const &buff() const noexcept {
5874  return buffer_.get_second();
5875  }
5876 
5882  allocator_type &alloc() noexcept {
5883  return buffer_.get_first();
5884  }
5890  allocator_type const &alloc() const noexcept {
5891  return buffer_.get_first();
5892  }
5897  compressed_pair<allocator_type, buffer_type> buffer_;
5898 };
5910 template <typename T,
5911  typename TT,
5912  typename A>
5913 inline void swap(flat_forward_list<T, TT, A> &lhs, flat_forward_list<T, TT, A> &rhs)
5914  noexcept (std::allocator_traits<A>::propagate_on_container_swap::value ||
5915  std::allocator_traits<A>::propagate_on_container_move_assignment::value) {
5916  lhs.swap(rhs);
5917 }
5929 template <typename T,
5930  typename TT,
5931  typename A>
5932 inline typename flat_forward_list<T, TT, A>::iterator begin(flat_forward_list<T, TT, A> &c) noexcept {
5933  return c.begin();
5934 }
5946 template <typename T,
5947  typename TT,
5948  typename A>
5949 inline typename flat_forward_list<T, TT, A>::const_iterator begin(flat_forward_list<T, TT, A> const &c) noexcept {
5950  return c.begin();
5951 }
5963 template <typename T,
5964  typename TT,
5965  typename A>
5966 inline typename flat_forward_list<T, TT, A>::const_iterator cbegin(flat_forward_list<T, TT, A> const &c) noexcept {
5967  return c.cbegin();
5968 }
5980 template <typename T,
5981  typename TT,
5982  typename A>
5983 inline typename flat_forward_list<T, TT, A>::iterator end(flat_forward_list<T, TT, A> &c) noexcept {
5984  return c.end();
5985 }
5997 template <typename T,
5998  typename TT,
5999  typename A>
6000 inline typename flat_forward_list<T, TT, A>::const_iterator end(flat_forward_list<T, TT, A> const &c) noexcept {
6001  return c.end();
6002 }
6014 template <typename T,
6015  typename TT,
6016  typename A>
6017 inline typename flat_forward_list<T, TT, A>::const_iterator cend(flat_forward_list<T, TT, A> const &c) noexcept {
6018  return c.cend();
6019 }
6031 template <typename T,
6032  typename TT,
6033  typename A>
6034 inline typename flat_forward_list<T, TT, A>::iterator last(flat_forward_list<T, TT, A> &c) noexcept {
6035  return c.last();
6036 }
6048 template <typename T,
6049  typename TT,
6050  typename A>
6051 inline typename flat_forward_list<T, TT, A>::const_iterator last(flat_forward_list<T, TT, A> const &c) noexcept {
6052  return c.last();
6053 }
6065 template <typename T,
6066  typename TT,
6067  typename A>
6068 inline typename flat_forward_list<T, TT, A>::const_iterator clast(flat_forward_list<T, TT, A> const &c) noexcept {
6069  return c.clast();
6070 }
6077 template <typename T,
6078  typename TT = flat_forward_list_traits<T>>
6079  using pmr_flat_forward_list = flat_forward_list<T,
6080  TT,
6081  FFL_PMR::polymorphic_allocator<char>>;
6088 template <typename T,
6089  typename TT>
6090 template <typename V,
6091  typename VV,
6092  typename A,
6093  typename UNUSED>
6094 flat_forward_list_ref<T, TT>::flat_forward_list_ref(flat_forward_list<V, VV, A> const &c) noexcept
6095 : buffer_(c.buff()) {
6096 }
6104 template <typename T,
6105  typename TT>
6106 template <typename V,
6107  typename VV,
6108  typename A,
6109  typename UNUSED>
6110 flat_forward_list_ref<T, TT> &flat_forward_list_ref<T, TT>::operator= (flat_forward_list<V, VV, A> const &c) noexcept {
6111  buffer_ = c.buff();
6112  return *this;
6113 }
6114 
6130 template<typename T,
6131  typename TT,
6132  typename F>
6133 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate_has_next_offset(char const *first,
6134  char const *end,
6135  F const &validate_element_fn) noexcept {
6136  using traits_traits = flat_forward_list_traits_traits<T, TT>;
6137  constexpr auto const type_has_next_offset{ traits_traits::has_next_offset_v };
6138  static_assert(type_has_next_offset, "traits type must define get_next_offset");
6139 
6140  char const *begin{ first };
6141  //
6142  // by default we did not found any valid elements
6143  //
6144  char const *last_valid = nullptr;
6145  //
6146  // null buffer is defined as valid
6147  //
6148  if (first == nullptr) {
6149  FFL_CODDING_ERROR_IF_NOT(nullptr == end);
6150  return std::make_pair(true, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6151  cast_to_char_ptr(last_valid),
6152  cast_to_char_ptr(end) });
6153  }
6154  //
6155  // empty buffer is defined as valid
6156  //
6157  if (first == end) {
6158  return std::make_pair(true, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6159  cast_to_char_ptr(last_valid),
6160  cast_to_char_ptr(end) });
6161  }
6162  //
6163  // Can we safely subtract pointers?
6164  //
6165  FFL_CODDING_ERROR_IF(end < first);
6166 
6167  size_t remaining_length{ static_cast<size_t>(end - first) };
6168  bool result = false;
6169  for (; remaining_length > 0;) {
6170  //
6171  // is it large enough to even query next offset?
6172  //
6173  if (remaining_length <= 0 || remaining_length < traits_traits::minimum_size()) {
6174  break;
6175  }
6176  //
6177  // If type has next element offset then validate it before
6178  // validating the rest of data
6179  //
6180  size_t const next_element_offset = traits_traits::get_next_offset(first);
6181  //
6182  // Is offset of the next element in bound of the remaining buffer
6183  //
6184  if (remaining_length < next_element_offset) {
6185  break;
6186  }
6187  //
6188  // minimum and next are valid, check rest of the fields
6189  //
6190  if (!validate_element_fn(remaining_length, *traits_traits::ptr_to_t(first))) {
6191  break;
6192  }
6193  //
6194  // This is end of list, we are done,
6195  // and everything is valid
6196  //
6197  if (0 == next_element_offset) {
6198  last_valid = first;
6199  result = true;
6200  break;
6201  }
6202  //
6203  // Advance last valid element forward
6204  //
6205  last_valid = first;
6206  //
6207  // Advance current element forward
6208  //
6209  first += next_element_offset;
6210  remaining_length -= next_element_offset;
6211  }
6212 
6213  return std::make_pair(result, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6214  cast_to_char_ptr(last_valid),
6215  cast_to_char_ptr(end) });
6216 }
6217 
6235 template<typename T,
6236  typename TT,
6237  typename F>
6238 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate_no_next_offset(char const *first,
6239  char const *end,
6240  F const &validate_element_fn) noexcept {
6241  char const *begin{ first };
6242  //
6243  // For this function to work correctly we do not care if
6244  // traits has get_next_offset
6245  using traits_traits = flat_forward_list_traits_traits<T, TT>;
6246  //
6247  // by default we did not found any valid elements
6248  //
6249  char const *last_valid = nullptr;
6250  //
6251  // null buffer is defined as valid
6252  //
6253  if (first == nullptr) {
6254  FFL_CODDING_ERROR_IF_NOT(nullptr == end);
6255  return std::make_pair(true, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6256  cast_to_char_ptr(last_valid),
6257  cast_to_char_ptr(end) });
6258  }
6259  //
6260  // empty buffer is defined as valid
6261  //
6262  if (first == end) {
6263  return std::make_pair(true, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6264  cast_to_char_ptr(last_valid),
6265  cast_to_char_ptr(end) });
6266  }
6267  //
6268  // Can we safely subtract pointers?
6269  //
6270  FFL_CODDING_ERROR_IF(end < first);
6271 
6272  std::ptrdiff_t remaining_length = end - first;
6273  bool result = false;
6274  for (;;) {
6275  //
6276  // is it large enough to even query next offset?
6277  //
6278  if (remaining_length <= 0 || remaining_length < static_cast<std::ptrdiff_t>(traits_traits::minimum_size())) {
6279  //
6280  // If buffer is too small to fit next element
6281  // then we are done.
6282  // If element type does not have next element offset
6283  // then validation succeeded.
6284  //
6285  result = true;
6286  break;
6287  }
6288  //
6289  // Check that element is valid before asking to calculate
6290  // element size.
6291  //
6292  if (!validate_element_fn(remaining_length, *traits_traits::ptr_to_t(first))) {
6293  break;
6294  }
6295  //
6296  // Next element starts right after this element ends
6297  //
6298  size_t next_element_offset = traits_traits::get_next_offset(first);
6299  //
6300  // Element size must be at least min size
6301  //
6302  if (next_element_offset < traits_traits::minimum_size()) {
6303  break;
6304  }
6305  //
6306  // keep going to see if buffer is large enough to hold
6307  // another element
6308  //
6309 
6310  //
6311  // Advance last valid element forward
6312  //
6313  last_valid = first;
6314  //
6315  // Advance current element forward
6316  //
6317  first += next_element_offset;
6318  remaining_length -= next_element_offset;
6319  }
6320 
6321  return std::make_pair(result, flat_forward_list_ref<T, TT>{ cast_to_char_ptr(begin),
6322  cast_to_char_ptr(last_valid),
6323  cast_to_char_ptr(end) });
6324 }
6382 template<typename T,
6383  typename TT,
6384  typename F>
6385 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(char const *first,
6386  char const *end,
6387  F const &validate_element_fn) noexcept {
6388  using traits_traits = flat_forward_list_traits_traits<T, TT>;
6389  constexpr auto const type_has_next_offset{ traits_traits::has_next_offset_v };
6390  //
6391  // If TT::get_next_offset is defined then use
6392  // flat_forward_list_validate_has_next_offset algorithm
6393  // otherwise use flat_forward_list_validate_no_next_offset
6394  // algorithm
6395  //
6396  if constexpr (type_has_next_offset) {
6397  return flat_forward_list_validate_has_next_offset<T, TT, F>(first, end, validate_element_fn);
6398  } else {
6399  return flat_forward_list_validate_no_next_offset<T, TT, F>(first, end, validate_element_fn);
6400  }
6401 }
6402 
6403 template<typename T,
6404  typename TT,
6405  typename F>
6406 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(char *first,
6407  char *end,
6408  F const &validate_element_fn) noexcept {
6409  using traits_traits = flat_forward_list_traits_traits<T, TT>;
6410  constexpr auto const type_has_next_offset{ traits_traits::has_next_offset_v };
6411  //
6412  // If TT::get_next_offset is defined then use
6413  // flat_forward_list_validate_has_next_offset algorithm
6414  // otherwise use flat_forward_list_validate_no_next_offset
6415  // algorithm
6416  //
6417  if constexpr (type_has_next_offset) {
6418  return flat_forward_list_validate_has_next_offset<T, TT, F>(first, end, validate_element_fn);
6419  } else {
6420  return flat_forward_list_validate_no_next_offset<T, TT, F>(first, end, validate_element_fn);
6421  }
6422 }
6426 template<typename T,
6427  typename TT,
6428  typename F>
6429 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(T *first,
6430  T *end,
6431  F const &validate_element_fn) noexcept {
6432  return flat_forward_list_validate<T, TT>(reinterpret_cast<char *>(first),
6433  reinterpret_cast<char *>(end),
6434  validate_element_fn);
6435 }
6439 template<typename T,
6440  typename TT,
6441  typename F>
6442 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(T const *first,
6443  T const *end,
6444  F const &validate_element_fn) noexcept {
6445  return flat_forward_list_validate<T, TT>(reinterpret_cast<char const *>(first),
6446  reinterpret_cast<char const *>(end),
6447  validate_element_fn);
6448 }
6452 template<typename T,
6453  typename TT,
6454  typename F>
6455 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(unsigned char const *first,
6456  unsigned char const *end,
6457  F const &validate_element_fn) noexcept {
6458  return flat_forward_list_validate<T, TT>(reinterpret_cast<char const *>(first),
6459  reinterpret_cast<char const *>(end),
6460  validate_element_fn);
6461 }
6465 template<typename T,
6466  typename TT,
6467  typename F>
6468 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(unsigned char *first,
6469  unsigned char *end,
6470  F const &validate_element_fn) noexcept {
6471  return flat_forward_list_validate<T, TT>(reinterpret_cast<char *>(first),
6472  reinterpret_cast<char *>(end),
6473  validate_element_fn);
6474 }
6478 template<typename T,
6479  typename TT,
6480  typename F>
6481 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(void const *first,
6482  void const *end,
6483  F const &validate_element_fn) noexcept {
6484  return flat_forward_list_validate<T, TT>(reinterpret_cast<char const *>(first),
6485  reinterpret_cast<char const *>(end),
6486  validate_element_fn);
6487 }
6491 template<typename T,
6492  typename TT,
6493  typename F>
6494 constexpr inline std::pair<bool, flat_forward_list_ref<T, TT>> flat_forward_list_validate(void *first,
6495  void *end,
6496  F const &validate_element_fn) noexcept {
6497  return flat_forward_list_validate<T, TT>(reinterpret_cast<char *>(first),
6498  reinterpret_cast<char *>(end),
6499  validate_element_fn);
6500 }
6501 
6502 } // namespace iffl
iffl::buffer_t::clear
constexpr void clear() noexcept
Resets all pointers to nullptr.
Definition: iffl_common.h:1159
iffl::flat_forward_list_traits_traits::type_traits
TT type_traits
Definition: iffl_list.h:398
iffl::flat_forward_list_sizes::last_element
range_with_alighment< ALIGNMENT_V > last_element
Last element range.
Definition: iffl_common.h:758
iffl::flat_forward_list_ref::npos
static size_type const npos
Constant that represents and invalid or non-existent position.
Definition: iffl_list.h:1498
iffl::flat_forward_list::erase_all
void erase_all() noexcept
Erases all elements in the buffer without deallocating buffer.
Definition: iffl_list.h:3964
iffl::flat_forward_list_ref::value_type
T value_type
Element value type.
Definition: iffl_list.h:1387
iffl::flat_forward_list::get_allocator
allocator_type & get_allocator() &noexcept
Returns reference to the allocator used by this container.
Definition: iffl_list.h:3264
iffl::zero_buffer
void zero_buffer(char *buffer, size_t length) noexcept
sets "length" consecutive bytes of "to_buffer" to 0.
Definition: iffl_common.h:344
iffl::flat_forward_list::try_emplace_front
bool try_emplace_front(size_type element_size, F const &fn)
Inserts new element at the beginning of the container. Element is initialized with a help of the func...
Definition: iffl_list.h:3750
iffl::flat_forward_list::reference
T & reference
Reference to the element type.
Definition: iffl_list.h:2641
iffl::flat_forward_list_ref::buffer_type
buffer_t< buffer_value_type > buffer_type
Pointers that describe buffer.
Definition: iffl_list.h:1493
iffl::flat_forward_list::pop_back
void pop_back() noexcept
Removes last element from the list.
Definition: iffl_list.h:3499
iffl::flat_forward_list::remaining_capacity
size_type remaining_capacity() const noexcept
Definition: iffl_list.h:4850
iffl::flat_forward_list_ref::data
char const * data() const noexcept
Definition: iffl_list.h:1893
iffl::flat_forward_list::sizes_t
flat_forward_list_sizes< traits_traits::alignment > sizes_t
Vocabulary type that contains information about buffer size, and last element range.
Definition: iffl_list.h:2690
iffl::flat_forward_list_iterator_t::iterator_category
std::forward_iterator_tag iterator_category
Marks iterator as a forward iterator.
Definition: iffl_list.h:857
iffl::cast_to_char_ptr
char * cast_to_char_ptr(T *p) noexcept
Helper method to cast a pointer to a char *.
Definition: iffl_common.h:362
iffl::flat_forward_list::buffer_value_type
char buffer_value_type
Since we have variable size elements, and we cannot express it in the C++ type system we treat buffer...
Definition: iffl_list.h:2708
iffl::flat_forward_list::erase_all_from
iterator erase_all_from(iterator const &it) noexcept
Erases element in the range [it, end)
Definition: iffl_list.h:3934
iffl_config.h
This file is supposed to be generated by cmake. Cmake pushes output to the folder where it generates ...
iffl::flat_forward_list_traits_traits::get_alignment
static constexpr size_t get_alignment() noexcept
If traits defined alignment then size of alignment, and 1 otherwise.
Definition: iffl_list.h:529
iffl::flat_forward_list::try_emplace
bool try_emplace(iterator const &it, size_type new_element_size, F const &fn)
Constructs new element at the position described by iterator. Element is initialized with a help of t...
Definition: iffl_list.h:3656
iffl::flat_forward_list_iterator_t::flat_forward_list_iterator_t
constexpr flat_forward_list_iterator_t(I &&other) noexcept
Perfect forwarding constructor for const iterator from non-const iterator.
Definition: iffl_list.h:1016
iffl::flat_forward_list_ref::clast
const_iterator clast() const noexcept
Definition: iffl_list.h:1869
iffl::flat_forward_list::assign
void assign(flat_forward_list_view< T, TT > const &view)
Copies elements from the view.
Definition: iffl_list.h:3231
iffl::range::begin
constexpr size_t begin() const
Offset of the element buffer begin in a larger buffer.
Definition: iffl_common.h:544
iffl::flat_forward_list::half_open_range
range_t half_open_range(const_iterator const &begin, const_iterator const &end) const noexcept
Information about the buffer occupied by elements in the range [begin, end).
Definition: iffl_list.h:4652
iffl::buffer_t::begin
pointer_type begin
Pointer to the beginning of buffer nullptr if no buffer.
Definition: iffl_common.h:1075
iffl::flat_forward_list_traits_traits::value_type
T value_type
Definition: iffl_list.h:393
iffl::flat_forward_list::flat_forward_list
flat_forward_list(flat_forward_list &&other) noexcept
Move constructor. Moves allocator and content of other container to this container.
Definition: iffl_list.h:2765
iffl::flat_forward_list::required_size
size_type required_size(const_iterator const &it) const noexcept
Returns capacity used by the element's data.
Definition: iffl_list.h:4583
iffl::flat_forward_list_ref
Non owning container for flat forward list.
Definition: iffl_list.h:688
iffl::flat_forward_list::try_element_resize
bool try_element_resize(iterator const &it, size_type new_size, F const &fn)
Resizes element.
Definition: iffl_list.h:4568
iffl::flat_forward_list_traits_traits::has_alignment_v
static constexpr auto const has_alignment_v
Instance of has_alignment_t.
Definition: iffl_list.h:476
iffl::flat_forward_list_ref::data
char * data() noexcept
Definition: iffl_list.h:1886
iffl::flat_forward_list::erase_after
void erase_after(iterator const &it) noexcept
Erases element after the element pointed by the iterator.
Definition: iffl_list.h:3794
iffl::flat_forward_list::size
size_type size() const noexcept
Number of elements in the container.
Definition: iffl_list.h:4810
iffl::flat_forward_list::closed_range
range_t closed_range(const_iterator const &begin, const_iterator const &last) const noexcept
Information about the buffer occupied by elements in the range [begin, last].
Definition: iffl_list.h:4631
iffl::flat_forward_list::const_iterator
flat_forward_list_const_iterator< T, TT > const_iterator
Type of const iterator.
Definition: iffl_list.h:2735
iffl::flat_forward_list_traits_traits::has_minimum_size_t
iffl::mpl::is_detected< has_minimum_size_mfn, type_traits > has_minimum_size_t
Uses detect idiom with has_minimum_size_mfn to find if traits implemented minimum_size.
Definition: iffl_list.h:406
iffl::flat_forward_list_iterator_t
THis class implements forward iterator for intrusive flat forward list.
Definition: iffl_list.h:833
iffl::flat_forward_list_iterator_t::reference
T & reference
Reference to the element type.
Definition: iffl_list.h:877
iffl::flat_forward_list_iterator_t::is_non_const_iterator_v
static constexpr auto const is_non_const_iterator_v
Is std::true_type{} if Iterator is same as non-const equivalent of the current iterator non-const equ...
Definition: iffl_list.h:956
iffl::flat_forward_list::unique
void unique(F const &fn) noexcept
If there are multiple equivalent elements next to each other then first one is kept,...
Definition: iffl_list.h:4181
iffl::flat_forward_list::revalidate_data
bool revalidate_data(size_type data_size=npos) noexcept
Validates that buffer contains a valid list.
Definition: iffl_list.h:4393
iffl::flat_forward_list::flat_forward_list
flat_forward_list(char const *buffer, size_t buffer_size, AA &&a=AA{})
Constructor that checks if buffer contains a valid list and if it does then copies that list.
Definition: iffl_list.h:2929
iffl::default_validate_element_fn::operator()
bool operator()(size_t buffer_size, T const &e) const noexcept
Function call iterator that validates element.
Definition: iffl_list.h:706
iffl::range::buffer_begin
size_t buffer_begin
Starting offset of element in a buffer Element always starts at the beginning of the buffer.
Definition: iffl_common.h:530
iffl::flat_forward_list::offset_with_aligment_t
typename traits_traits::offset_with_aligment_t offset_with_aligment_t
Vocabulary type used to describe size with alignment.
Definition: iffl_list.h:2685
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref(buffer_type const &other_buff) noexcept
Constructor that initializes view to point to the buffer.
Definition: iffl_list.h:1528
iffl::flat_forward_list_traits_traits::minimum_size
static constexpr size_t minimum_size() noexcept
returns minimum valid element size
Definition: iffl_list.h:522
iffl::flat_forward_list::find_element_before
iterator find_element_before(size_type position) noexcept
Searches for an element before the element that contains given position.
Definition: iffl_list.h:4687
iffl::flat_forward_list_iterator_t::is_comparable_iterator_v
static constexpr auto const is_comparable_iterator_v
Is std::true_type{} if Iterator is a const or non-const equivalent of this iterator and std::false_ty...
Definition: iffl_list.h:975
iffl::flat_forward_list::last
iterator last() noexcept
Definition: iffl_list.h:4303
iffl::flat_forward_list::operator=
flat_forward_list & operator=(flat_forward_list &&other) noexcept(allocator_type_traits::propagate_on_container_move_assignment::value)
Move assignment operator.
Definition: iffl_list.h:2975
iffl::noop_validate_element_fn
Definition: iffl_list.h:717
iffl::flat_forward_list_ref::range
range_t range(const_iterator const &it) const noexcept
Information about the buffer occupied by an element.
Definition: iffl_list.h:1946
iffl::flat_forward_list_iterator_t::is_const_iterator_v
static constexpr auto const is_const_iterator_v
Is std::true_type{} if Iterator is same as const equivalent of the current iterator non-const equival...
Definition: iffl_list.h:966
iffl::flat_forward_list::sort
void sort(LESS_F const &fn)
Sorts elements of container using comparator passed as a parameter.
Definition: iffl_list.h:4085
iffl::flat_forward_list_traits_traits::has_alignment_t
iffl::mpl::is_detected< has_alignment_mfn, type_traits > has_alignment_t
Uses detect idiom with has_alignment_mfn to find if traits implemented validate.
Definition: iffl_list.h:471
iffl::flat_forward_list::pop_front
void pop_front() noexcept
Removes first element from the container.
Definition: iffl_list.h:3758
iffl::flat_forward_list::try_element_add_size
bool try_element_add_size(iterator const &it, size_type size_to_add)
Adds unused capacity to the element.
Definition: iffl_list.h:4512
iffl::flat_forward_list::~flat_forward_list
~flat_forward_list() noexcept
Destructor.
Definition: iffl_list.h:3025
iffl::flat_forward_list_ref::assign
void assign(buffer_type const &other_buff) noexcept
Assigns view to point to the described buffer.
Definition: iffl_list.h:1648
iffl::fill_buffer
void fill_buffer(char *buffer, int value, size_t length) noexcept
sets "length" consecutive bytes of "to_buffer" to "value".
Definition: iffl_common.h:336
iffl::flat_forward_list::shrink_to_fit
void shrink_to_fit()
Removes unused padding of each element and at the tail.
Definition: iffl_list.h:4413
iffl::flat_forward_list_ref::offset_with_aligment_t
typename traits_traits::offset_with_aligment_t offset_with_aligment_t
Vocabulary type used to describe size with alignment.
Definition: iffl_list.h:1446
iffl::flat_forward_list::size_with_padding_t
typename traits_traits::size_with_padding_t size_with_padding_t
Vocabulary type used to describe size with padding.
Definition: iffl_list.h:2680
iffl::flat_forward_list::push_front
void push_front(size_type init_buffer_size, char const *init_buffer=nullptr)
Constructs new element at the beginning of the container. Element is initialized by copping provided ...
Definition: iffl_list.h:3677
iffl::flat_forward_list::erase
iterator erase(iterator const &start, iterator const &end) noexcept
Erases element in the range [start, end).
Definition: iffl_list.h:4019
iffl::flat_forward_list::emplace_front
void emplace_front(size_type element_size, F const &fn)
Inserts new element at the beginning of the container. Element is initialized with a help of the func...
Definition: iffl_list.h:3733
iffl::make_scope_guard
constexpr auto make_scope_guard(G &&g)
Factory method for scoped_guard.
Definition: iffl_common.h:489
iffl::attach_buffer
Helper class used as a parameter in flat_forward_list constructor to designate that it should take ow...
Definition: iffl_common.h:500
iffl::flat_forward_list_iterator_t::operator >
constexpr bool operator >(I const &other) const noexcept
Greater than operator used to compare to another iterator.
Definition: iffl_list.h:1161
iffl::flat_forward_list_traits_traits::has_get_size_t
iffl::mpl::is_detected< has_get_size_mfn, type_traits > has_get_size_t
Uses detect idiom with has_get_size_mfn to find if traits implemented get_size.
Definition: iffl_list.h:419
iffl::flat_forward_list_iterator_t::flat_forward_list_iterator_t
constexpr flat_forward_list_iterator_t() noexcept=default
Default initialize iterator.
iffl::flat_forward_list::flat_forward_list
flat_forward_list(const_iterator const &begin, const_iterator const &last, AA &&a=AA{})
Copies element pointed by the iterators.
Definition: iffl_list.h:2947
iffl::buffer_view
buffer_t< char const > buffer_view
Const flat forward list buffer.
Definition: iffl_common.h:1186
iffl::flat_forward_list_traits
traits for an elements that are in the flat forward list
Definition: iffl_list.h:286
iffl::flat_forward_list_ref::assign
void assign(flat_forward_list_iterator< V, VV > const &begin, flat_forward_list_iterator< V, VV > const &last) noexcept
Assigns view to point to the described buffer.
Definition: iffl_list.h:1677
iffl::swap
void swap(flat_forward_list< T, TT, A > &lhs, flat_forward_list< T, TT, A > &rhs) noexcept(std::allocator_traits< A >::propagate_on_container_swap::value||std::allocator_traits< A >::propagate_on_container_move_assignment::value)
Definition: iffl_list.h:5913
iffl::one_then_variadic_args_t
Tag type for constructing first from one argument, constructing second from remaining arguments.
Definition: iffl_common.h:798
iffl::flat_forward_list_iterator_t::difference_type
ptrdiff_t difference_type
Element pointers difference type.
Definition: iffl_list.h:867
iffl::size_with_padding::size_padded
constexpr size_t size_padded() const noexcept
Definition: iffl_common.h:734
iffl::flat_forward_list_ref::const_pointer
T const * const_pointer
Pointer to const element type.
Definition: iffl_list.h:1397
iffl::default_validate_element_fn
Definition: iffl_list.h:700
iffl::flat_forward_list::flat_forward_list
flat_forward_list(buffer_view const &other_buff, AA &&a=AA{})
Constructor that copies list from a buffer.
Definition: iffl_list.h:2818
iffl::flat_forward_list_ref::buffer_value_type
std::conditional_t< std::is_const_v< T >, char const, char > buffer_value_type
Depending if T is const we will use const or non-const buffer pointer.
Definition: iffl_list.h:1461
iffl::flat_forward_list::try_push_front
bool try_push_front(size_type init_buffer_size, char const *init_buffer=nullptr)
Constructs new element at the beginning of the container. Element is initialized by copping provided ...
Definition: iffl_list.h:3704
iffl::flat_forward_list::try_insert
bool try_insert(iterator const &it, size_type init_buffer_size, char const *init_buffer=nullptr)
Inserts new element at the position described by iterator. Element is initialized by copping provided...
Definition: iffl_list.h:3583
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref(flat_forward_list_ref< V, VV > const &other) noexcept
Assignment operator to view from a ref.
Definition: iffl_list.h:1516
iffl::begin
flat_forward_list_ref< T, TT >::iterator begin(flat_forward_list_ref< T, TT > &c) noexcept
Definition: iffl_list.h:2406
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type * ptr_to_t(unsigned char *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:509
iffl::flat_forward_list_iterator_t::traits
TT traits
Element traits type.
Definition: iffl_list.h:882
iffl::flat_forward_list_ref::used_capacity
size_type used_capacity() const noexcept
Definition: iffl_list.h:2111
iffl::distance
size_t distance(void const *begin, void const *end) noexcept
sets "length" consecutive bytes of "to_buffer" to 0.
Definition: iffl_common.h:352
iffl::flat_forward_list_ref::difference_type
std::ptrdiff_t difference_type
Element pointers difference type.
Definition: iffl_list.h:1417
iffl::flat_forward_list::assign
void assign(char const *buffer_begin, char const *last_element, char const *buffer_end)
Copies list from a buffer.
Definition: iffl_list.h:3149
iffl::flat_forward_list::clear
void clear() noexcept
Deallocated buffer owned by this container.
Definition: iffl_list.h:3287
iffl::flat_forward_list::clast
const_iterator clast() const noexcept
Definition: iffl_list.h:4356
iffl::flat_forward_list_traits_traits::has_minimum_size_v
static constexpr auto const has_minimum_size_v
Instance of has_minimum_size_t.
Definition: iffl_list.h:411
iffl::flat_forward_list::detach
buffer_ref detach() noexcept
Container releases ownership of the buffer.
Definition: iffl_list.h:3034
FFL_CODDING_ERROR_IF
#define FFL_CODDING_ERROR_IF(C)
If expression is true then fail fast with error ENOTRECOVERABLE(127 or 0x7f)
Definition: iffl_common.h:113
iffl::flat_forward_list_ref::size_with_padding_t
typename traits_traits::size_with_padding_t size_with_padding_t
Vocabulary type used to describe size with padding.
Definition: iffl_list.h:1441
iffl
intrusive flat forward list
iffl::flat_forward_list_traits_traits::can_validate_v
static constexpr auto const can_validate_v
Instance of can_validate_t.
Definition: iffl_list.h:463
iffl::flat_forward_list::back
T & back() noexcept
Definition: iffl_list.h:4256
iffl::pmr_flat_forward_list
flat_forward_list< T, TT, FFL_PMR::polymorphic_allocator< char > > pmr_flat_forward_list
Use this typedef if you want to use container with polymorphic allocator.
Definition: iffl_list.h:6081
iffl::flat_forward_list_iterator_t::operator->
constexpr T * operator->() const noexcept
pointer operator.
Definition: iffl_list.h:1239
iffl::last
flat_forward_list_ref< T, TT >::iterator last(flat_forward_list_ref< T, TT > &c) noexcept
Definition: iffl_list.h:2502
iffl::flat_forward_list_ref::back
T & back()
Definition: iffl_list.h:1733
iffl::flat_forward_list::find_element_after
const_iterator find_element_after(size_type position) const noexcept
Searches for an element after the element that contains given position.
Definition: iffl_list.h:4793
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type * ptr_to_t(char *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:495
iffl::flat_forward_list_traits_traits::can_validate_t
iffl::mpl::is_detected< can_validate_mfn, type_traits > can_validate_t
Uses detect idiom with can_validate_mfn to find if traits implemented validate.
Definition: iffl_list.h:458
iffl::flat_forward_list_iterator_t::operator==
constexpr bool operator==(I const &other) const noexcept
Equals operator used to compare to another iterator.
Definition: iffl_list.h:1101
iffl::flat_forward_list::flat_forward_list
flat_forward_list(allocator_type a) noexcept
Constructs an empty container with an instance of provided allocator.
Definition: iffl_list.h:2757
iffl::flat_forward_list_ref::size
size_type size() const noexcept
Number of elements in the container.
Definition: iffl_list.h:2080
iffl::flat_forward_list_iterator_t::swap
constexpr void swap(flat_forward_list_iterator_t &other) noexcept
swaps this iterator and the other iterator
Definition: iffl_list.h:1077
iffl::flat_forward_list_iterator_t::operator+
constexpr flat_forward_list_iterator_t operator+(unsigned int advance_by) const noexcept
Add operator. Advances iterator specified number of times.
Definition: iffl_list.h:1220
iffl::flat_forward_list_iterator_t::size_with_padding_t
typename traits_traits::size_with_padding_t size_with_padding_t
Vocabulary type used to describe size with padding.
Definition: iffl_list.h:910
iffl::flat_forward_list::const_buffer_pointer
char const * const_buffer_pointer
Type used as a pointer to the const buffer.
Definition: iffl_list.h:2724
iffl::flat_forward_list::flat_forward_list
flat_forward_list(char const *buffer_begin, char const *last_element, char const *buffer_end, AA &&a=AA{})
Constructor that copies list from a buffer.
Definition: iffl_list.h:2874
iffl::flat_forward_list::assign
bool assign(char const *buffer, size_type buffer_size)
Checks if buffer contains a valid list and if it does then copies that list.
Definition: iffl_list.h:3202
iffl::size_with_padding::size
size_t size
Not padded size.
Definition: iffl_common.h:730
iffl_mpl.h
This module contains few meta-programming facilities that are not part of the STL.
iffl::flat_forward_list_ref::sizes_t
flat_forward_list_sizes< traits_traits::alignment > sizes_t
Vocabulary type that contains information about buffer size, and last element range.
Definition: iffl_list.h:1451
iffl::flat_forward_list_iterator_t::value_type
T value_type
Element value type.
Definition: iffl_list.h:862
iffl::flat_forward_list::value_type
T value_type
Element value type.
Definition: iffl_list.h:2626
iffl::flat_forward_list_ref::buffer_pointer
buffer_value_type * buffer_pointer
Type used as a buffer pointer.
Definition: iffl_list.h:1472
iffl::flat_forward_list_iterator_t::operator !=
constexpr bool operator !=(I const &other) const noexcept
Not equals operator used to compare to another iterator.
Definition: iffl_list.h:1116
iffl::flat_forward_list::remove_if
void remove_if(F const &fn) noexcept
Removes all elements that satisfy predicate.
Definition: iffl_list.h:4218
iffl_common.h
Common definitions, utility functions and vocabulary types.
iffl::flat_forward_list_ref::front
T & front()
Definition: iffl_list.h:1715
iffl::flat_forward_list_sizes::remaining_capacity_for_append
constexpr size_t remaining_capacity_for_append() const
Definition: iffl_common.h:776
iffl::flat_forward_list_iterator_t::get_ptr
constexpr buffer_char_pointer get_ptr() const noexcept
Definition: iffl_list.h:1246
iffl::flat_forward_list_iterator_t::operator *
constexpr T & operator *() const noexcept
Dereference operator.
Definition: iffl_list.h:1232
iffl::buffer_t::last_offset
constexpr size_type last_offset() const noexcept
Definition: iffl_common.h:1123
iffl::flat_forward_list::find_element_at
iterator find_element_at(size_type position) noexcept
Searches for an element that contains given position.
Definition: iffl_list.h:4732
iffl::flat_forward_list::find_element_before
const_iterator find_element_before(size_type position) const noexcept
Searches for an element before the element that contains given position.
Definition: iffl_list.h:4711
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref(buffer_pointer buffer_begin, buffer_pointer last_element, buffer_pointer buffer_end) noexcept
Constructor that copies list from a buffer.
Definition: iffl_list.h:1545
iffl::flat_forward_list_ref::revalidate_data
bool revalidate_data() noexcept
Validates that buffer contains a valid list.
Definition: iffl_list.h:1905
iffl::flat_forward_list_ref::assign
void assign(buffer_pointer buffer_begin, buffer_pointer last_element, buffer_pointer buffer_end) noexcept
Assigns view to point to the described buffer.
Definition: iffl_list.h:1661
iffl::flat_forward_list::erase_all_after
void erase_all_after(iterator const &it) noexcept
Erases element in the range (before_start, end)
Definition: iffl_list.h:3912
iffl::flat_forward_list_ref::range_t
typename traits_traits::range_t range_t
Vocabulary type used to describe buffer used by the element and how much of this buffer is used by th...
Definition: iffl_list.h:1436
iffl::flat_forward_list_iterator_t::buffer_unsigned_char_pointer
std::conditional_t< std::is_const_v< T >, unsigned char const *, unsigned char * > buffer_unsigned_char_pointer
Definition: iffl_list.h:899
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref(flat_forward_list_iterator< V, VV > const &begin, flat_forward_list_iterator< V, VV > const &last) noexcept
Constructor that creates a view over a buffer described by a pair of iterators.
Definition: iffl_list.h:1565
iffl::flat_forward_list::find_element_at
const_iterator find_element_at(size_type position) const noexcept
Searches for an element that contains given position.
Definition: iffl_list.h:4752
iffl::flat_forward_list_traits_traits::get_next_offset
static constexpr size_t get_next_offset(char const *buffer) noexcept
Returns next element offset.
Definition: iffl_list.h:597
iffl::flat_forward_list_ref::const_reference
T const & const_reference
Reference to the const element type.
Definition: iffl_list.h:1407
iffl::flat_forward_list_validate_no_next_offset
constexpr std::pair< bool, flat_forward_list_ref< T, TT > > flat_forward_list_validate_no_next_offset(char const *first, char const *end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
Forward declaration.
Definition: iffl_list.h:6238
iffl::flat_forward_list::assign
void assign(buffer_view const &other_buff)
Copies list from a buffer.
Definition: iffl_list.h:3125
iffl::flat_forward_list_ref::size_type
std::size_t size_type
Size type.
Definition: iffl_list.h:1412
iffl::unused_variable
constexpr void unused_variable([[maybe_unused]] T const &)
Restore saved min and max definition.
Definition: iffl_common.h:216
iffl::flat_forward_list_iterator_t::operator >=
constexpr bool operator >=(I const &other) const noexcept
Greater or equals than operator used to compare to another iterator.
Definition: iffl_list.h:1176
iffl::flat_forward_list::allocator_type_traits
std::allocator_traits< allocator_type > allocator_type_traits
Type of allocator traits.
Definition: iffl_list.h:2700
iffl::flat_forward_list::buffer_type
buffer_t< buffer_value_type > buffer_type
Pointers that describe buffer.
Definition: iffl_list.h:2741
iffl::flat_forward_list::element_resize
iterator element_resize(iterator const &it, size_type new_size, F const &fn)
Resizes element.
Definition: iffl_list.h:4544
iffl::flat_forward_list_ref::contains
bool contains(const_iterator const &it, size_type position) const noexcept
Tells if given offset in the buffer falls into a buffer used by the element.
Definition: iffl_list.h:2003
iffl::flat_forward_list::used_size
size_type used_size(const_iterator const &it) const noexcept
Definition: iffl_list.h:4593
iffl::swap
void swap(flat_forward_list_ref< T, TT > &lhs, flat_forward_list_ref< T, TT > &rhs) noexcept
Definition: iffl_list.h:2390
iffl::flat_forward_list::empty
bool empty() const noexcept
Tells if container contains no elements.
Definition: iffl_list.h:4826
iffl::move_data
void move_data(char *to_buffer, char const *from_buffer, size_t length) noexcept
copies length bytes from from_buffer to to_buffer. source and destination buffers can overlap
Definition: iffl_common.h:327
iffl::flat_forward_list_ref::find_element_before
const_iterator find_element_before(size_type position) const noexcept
Searches for an element before the element that contains given position.
Definition: iffl_list.h:2021
iffl::flat_forward_list_ref::back
T const & back() const
Definition: iffl_list.h:1742
iffl::flat_forward_list_validate_has_next_offset
constexpr std::pair< bool, flat_forward_list_ref< T, TT > > flat_forward_list_validate_has_next_offset(char const *first, char const *end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
Forward declaration.
Definition: iffl_list.h:6133
iffl::flat_forward_list_ref::const_buffer_pointer
const_buffer_value_type * const_buffer_pointer
Type used as a pointer not the const buffer.
Definition: iffl_list.h:1477
iffl::flat_forward_list::erase_after_half_closed
void erase_after_half_closed(iterator const &before_start, iterator const &last) noexcept
Erases element in the range (before_start, last].
Definition: iffl_list.h:3851
iffl::flat_forward_list_ref::const_iterator
flat_forward_list_const_iterator< T, TT > const_iterator
Type of const iterator.
Definition: iffl_list.h:1487
iffl::flat_forward_list::swap
void swap(flat_forward_list &other) noexcept(allocator_type_traits::propagate_on_container_swap::value||allocator_type_traits::propagate_on_container_move_assignment::value)
Swaps content of this container and the other container.
Definition: iffl_list.h:4064
iffl::flat_forward_list::end
iterator end() noexcept
Definition: iffl_list.h:4322
iffl::flat_forward_list_ref::~flat_forward_list_ref
~flat_forward_list_ref() noexcept
Destructor.
Definition: iffl_list.h:1637
iffl::flat_forward_list_ref::remaining_capacity
size_type remaining_capacity() const noexcept
Definition: iffl_list.h:2127
iffl::flat_forward_list::fill_padding
void fill_padding(int fill_byte=0, bool zero_unused_capacity=true) noexcept
Fills parts of the buffer not used by element data with fill_byte.
Definition: iffl_list.h:4862
iffl::flat_forward_list_iterator_t::pointer
T * pointer
Pointer to element type.
Definition: iffl_list.h:872
iffl::buffer_t::end
pointer_type end
Pointer to the end of buffer nullptr if no buffer.
Definition: iffl_common.h:1086
iffl::flat_forward_list_ref::cend
const_iterator cend() const noexcept
Definition: iffl_list.h:1879
iffl::flat_forward_list_traits_traits::alignment
static constexpr size_t const alignment
Defines static constexpr member that with value that has alignment requirements of elements.
Definition: iffl_list.h:540
iffl::clast
flat_forward_list_ref< T, TT >::const_iterator clast(flat_forward_list_ref< T, TT > const &c) noexcept
Definition: iffl_list.h:2534
iffl::flat_forward_list::assign
void assign(const_iterator const &begin, const_iterator const &last)
Copies element pointed by the iterators.
Definition: iffl_list.h:3212
iffl::flat_forward_list_ref::closed_range
range_t closed_range(const_iterator const &begin, const_iterator const &last) const noexcept
Information about the buffer occupied by elements in the range [begin, last].
Definition: iffl_list.h:1965
iffl::flat_forward_list_ref::required_size
size_type required_size(const_iterator const &it) const noexcept
Returns capacity used by the element's data.
Definition: iffl_list.h:1918
iffl::flat_forward_list::const_reference
T const & const_reference
Reference to the const element type.
Definition: iffl_list.h:2646
iffl::flat_forward_list::iterator
flat_forward_list_iterator< T, TT > iterator
Type of iterator.
Definition: iffl_list.h:2730
iffl::flat_forward_list::npos
static size_type const npos
Constant that represents and invalid or non-existent position.
Definition: iffl_list.h:2746
iffl::range_with_alighment
Vocabulary type that describes a sub-buffer in a larger buffer and portion of that sub-buffer actuall...
Definition: iffl_common.h:632
iffl::flat_forward_list_ref::find_element_at
const_iterator find_element_at(size_type position) const noexcept
Searches for an element that contains given position.
Definition: iffl_list.h:2042
iffl::flat_forward_list_ref::last
iterator last() noexcept
Definition: iffl_list.h:1780
iffl::cbegin
flat_forward_list_ref< T, TT >::const_iterator cbegin(flat_forward_list_ref< T, TT > const &c) noexcept
Definition: iffl_list.h:2438
iffl::flat_forward_list::allocator_type
typename std::allocator_traits< A >::template rebind_alloc< char > allocator_type
Type of allocator.
Definition: iffl_list.h:2695
iffl::flat_forward_list::flat_forward_list
flat_forward_list() noexcept
Default constructor for container.
Definition: iffl_list.h:2750
iffl::flat_forward_list::size_type
std::size_t size_type
Size type.
Definition: iffl_list.h:2651
iffl::flat_forward_list::difference_type
std::ptrdiff_t difference_type
Element pointers difference type.
Definition: iffl_list.h:2656
iffl::flat_forward_list::element_add_size
iterator element_add_size(iterator const &it, size_type size_to_add)
Adds unused capacity to the element.
Definition: iffl_list.h:4482
iffl::flat_forward_list::emplace
iterator emplace(iterator const &it, size_type new_element_size, F const &fn)
Constructs new element at the position described by iterator. Element is initialized with a help of t...
Definition: iffl_list.h:3623
iffl::flat_forward_list_iterator_t::operator++
constexpr flat_forward_list_iterator_t operator++(int) noexcept
Postfix increment operator.
Definition: iffl_list.h:1200
iffl::flat_forward_list_ref::assign
void assign(buffer_pointer *buffer, size_t buffer_size) noexcept
Assigns view to point to the described buffer.
Definition: iffl_list.h:1689
iffl::flat_forward_list::back
T const & back() const noexcept
Definition: iffl_list.h:4265
iffl::flat_forward_list::const_buffer_value_type
char const const_buffer_value_type
When we do not intend to modify buffer we can treat it as a bag of const characters.
Definition: iffl_list.h:2714
iffl::flat_forward_list_iterator_t::buffer_void_pointer
std::conditional_t< std::is_const_v< T >, void const *, void * > buffer_void_pointer
Definition: iffl_list.h:905
iffl::flat_forward_list_ref::empty
bool empty() const noexcept
Tells if container contains no elements.
Definition: iffl_list.h:2096
iffl::flat_forward_list_traits_traits::range_t
range_with_alighment< alignment > range_t
Specialization of range_with_alighment for this type alignment.
Definition: iffl_list.h:545
iffl::flat_forward_list_traits_traits::has_next_offset_t
iffl::mpl::is_detected< has_next_offset_mfn, type_traits > has_next_offset_t
Uses detect idiom with has_next_offset_mfn to find if traits implemented get_next_offset.
Definition: iffl_list.h:432
iffl::flat_forward_list::flat_forward_list
flat_forward_list(attach_buffer, char *buffer, size_t buffer_size, AA &&a=AA{}) noexcept
Constructor that takes ownership of a buffer and attempts to find last element of the list.
Definition: iffl_list.h:2904
iffl::flat_forward_list::data
char const * data() const noexcept
Definition: iffl_list.h:4380
iffl::flat_forward_list_ref::operator=
flat_forward_list_ref & operator=(flat_forward_list_ref< V, VV > const &other)
Copy assignment operator.
Definition: iffl_list.h:1607
iffl::flat_forward_list_ref::swap
void swap(flat_forward_list_ref &other) noexcept
Swaps content of this container and the other container.
Definition: iffl_list.h:1706
iffl::flat_forward_list::front
T & front() noexcept
Definition: iffl_list.h:4238
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type const * ptr_to_t(unsigned char const *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:516
iffl::flat_forward_list_ref::end
const_iterator end() const noexcept
Definition: iffl_list.h:1839
iffl::flat_forward_list_ref::begin
const_iterator begin() const noexcept
Definition: iffl_list.h:1760
iffl::end
flat_forward_list_ref< T, TT >::iterator end(flat_forward_list_ref< T, TT > &c) noexcept
Definition: iffl_list.h:2454
iffl::flat_forward_list::contains
bool contains(const_iterator const &it, size_type position) const noexcept
Tells if given offset in the buffer falls into a buffer used by the element.
Definition: iffl_list.h:4669
iffl::flat_forward_list_traits_traits::roundup_to_alignment
static constexpr size_t roundup_to_alignment(size_t s) noexcept
If traits defined alignment then s padded to alignment, or unchanged value of s otherwise.
Definition: iffl_list.h:562
iffl::flat_forward_list_ref::reference
T & reference
Reference to the element type.
Definition: iffl_list.h:1402
iffl::flat_forward_list::front
T const & front() const noexcept
Definition: iffl_list.h:4247
iffl::flat_forward_list_ref::traits
TT traits
Element traits type.
Definition: iffl_list.h:1422
iffl::flat_forward_list::attach
bool attach(char *buffer, size_t buffer_size) noexcept
Takes ownership of a buffer and attempts to find last element of the list.
Definition: iffl_list.h:3107
iffl::flat_forward_list_traits_traits::offset_with_aligment_t
offset_with_aligment< alignment > offset_with_aligment_t
Specialization of offset_with_aligment for this type alignment.
Definition: iffl_list.h:555
iffl::cend
flat_forward_list_ref< T, TT >::const_iterator cend(flat_forward_list_ref< T, TT > const &c) noexcept
Definition: iffl_list.h:2486
iffl::flat_forward_list::merge
void merge(flat_forward_list &other, F const &fn)
Merges two linked list ordering lists using comparison functor.
Definition: iffl_list.h:4143
iffl::flat_forward_list_ref::front
T const & front() const
Definition: iffl_list.h:1724
iffl::flat_forward_list::last
const_iterator last() const noexcept
Definition: iffl_list.h:4312
iffl::flat_forward_list::flat_forward_list
flat_forward_list(attach_buffer, char *buffer_begin, char *last_element, char *buffer_end, AA &&a=AA{}) noexcept
Constructor that takes ownership of a buffer.
Definition: iffl_list.h:2849
iffl::buffer_t< buffer_value_type >
iffl::flat_forward_list::begin
iterator begin() noexcept
Definition: iffl_list.h:4274
iffl::flat_forward_list::pointer
T * pointer
Pointer to element type.
Definition: iffl_list.h:2631
iffl::flat_forward_list_ref::used_size
size_type used_size(const_iterator const &it) const noexcept
Definition: iffl_list.h:1928
iffl::roundup_size_to_alignment
constexpr size_t roundup_size_to_alignment(size_t size, size_t alignment) noexcept
Rounds up size to specified alignment.
Definition: iffl_common.h:255
iffl::flat_forward_list_traits_traits::can_set_next_offset_t
iffl::mpl::is_detected< can_set_next_offset_mfn, type_traits > can_set_next_offset_t
Uses detect idiom with can_set_next_offset_mfn to find if traits implemented set_next_offset.
Definition: iffl_list.h:445
iffl::flat_forward_list::shrink_to_fit
void shrink_to_fit(iterator const &first, iterator const &end)
Removes unused padding of each element in the range [first, end).
Definition: iffl_list.h:4425
iffl::flat_forward_list::reverse
void reverse()
Reverses elements of the list.
Definition: iffl_list.h:4122
iffl::flat_forward_list::max_size
size_type max_size() const noexcept
Returns maximum size.
Definition: iffl_list.h:3280
iffl::flat_forward_list_traits_traits::has_get_size_v
static constexpr auto const has_get_size_v
Instance of has_get_size_t.
Definition: iffl_list.h:424
iffl::copy_data
void copy_data(char *to_buffer, char const *from_buffer, size_t length) noexcept
copies length bytes from from_buffer to to_buffer. source and destination buffers cannot overlap
Definition: iffl_common.h:316
iffl::flat_forward_list_ref::last
const_iterator last() const noexcept
Definition: iffl_list.h:1789
iffl::flat_forward_list::insert
iterator insert(iterator const &it, size_type init_buffer_size, char const *init_buffer=nullptr)
Inserts new element at the position described by iterator. Element is initialized by copping provided...
Definition: iffl_list.h:3549
iffl::flat_forward_list::data
char * data() noexcept
Definition: iffl_list.h:4373
iffl::flat_forward_list::buffer_pointer
char * buffer_pointer
Type used as a buffer pointer.
Definition: iffl_list.h:2719
iffl::flat_forward_list::total_capacity
size_type total_capacity() const noexcept
Definition: iffl_list.h:4842
iffl::flat_forward_list::attach
void attach(char *buffer_begin, char *last_element, char *buffer_end) noexcept
Takes ownership of a buffer.
Definition: iffl_list.h:3077
iffl::flat_forward_list_iterator_t::buffer_char_pointer
std::conditional_t< std::is_const_v< T >, char const *, char * > buffer_char_pointer
Definition: iffl_list.h:893
iffl::flat_forward_list::try_emplace_back
bool try_emplace_back(size_type element_size, F const &fn)
Constructs new element at the end of the list if it fits in the existing free capacity.
Definition: iffl_list.h:3485
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type const * ptr_to_t(void const *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:488
iffl::flat_forward_list::range
range_t range(const_iterator const &it) const noexcept
Information about the buffer occupied by an element.
Definition: iffl_list.h:4611
iffl::flat_forward_list_ref::cbegin
const_iterator cbegin() const noexcept
Definition: iffl_list.h:1862
iffl::flat_forward_list_traits_traits::validate
static constexpr bool validate(size_t buffer_size, T const &buffer) noexcept
Asks type traits to validate element.
Definition: iffl_list.h:584
iffl::flat_forward_list::emplace_back
void emplace_back(size_type element_size, F const &fn)
Constructs new element at the end of the list.
Definition: iffl_list.h:3466
iffl::flat_forward_list::is_compatible_allocator
bool is_compatible_allocator(AA const &other_allocator) const noexcept
Compares if allocator used by container is equivalent to the other allocator.
Definition: iffl_list.h:3257
iffl::buffer_t::last
pointer_type last
Pointer to the last element in the list nullptr if no buffer or if there is no elements in the list.
Definition: iffl_common.h:1081
iffl::flat_forward_list_traits_traits
traits for flat_forward_list_traits
Definition: iffl_list.h:331
iffl::flat_forward_list_ref::begin
iterator begin() noexcept
Definition: iffl_list.h:1751
iffl::flat_forward_list_traits_traits::has_next_offset_v
static constexpr auto const has_next_offset_v
Instance of has_next_offset_t.
Definition: iffl_list.h:437
iffl::flat_forward_list_traits_traits::can_set_next_offset_v
static constexpr auto const can_set_next_offset_v
Instance of can_set_next_offset_t.
Definition: iffl_list.h:450
iffl::flat_forward_list_ref::half_open_range
range_t half_open_range(const_iterator const &begin, const_iterator const &end) const noexcept
Information about the buffer occupied by elements in the range [begin, end).
Definition: iffl_list.h:1986
iffl::flat_forward_list::try_push_back
bool try_push_back(size_type init_buffer_size, char const *init_buffer=nullptr)
Adds new element to the end of the list. Element is initialized by copping provided buffer.
Definition: iffl_list.h:3438
iffl::flat_forward_list::range_t
typename traits_traits::range_t range_t
Vocabulary type used to describe buffer used by the element and how much of this buffer is used by th...
Definition: iffl_list.h:2675
iffl::flat_forward_list::get_allocator
allocator_type const & get_allocator() const &noexcept
Returns const reference to the allocator used by this container.
Definition: iffl_list.h:3271
iffl::flat_forward_list_iterator_t::flat_forward_list_iterator_t
constexpr flat_forward_list_iterator_t(I const &other) noexcept
Unittest that is_non_const_iterator_v returns expected result.
Definition: iffl_list.h:998
iffl::flat_forward_list::flat_forward_list
flat_forward_list(flat_forward_list const &other)
Copy constructor. Copies allocator if supported and copies content of other container to this contain...
Definition: iffl_list.h:2775
iffl::noop_validate_element_fn::operator()
bool operator()([[maybe_unused]] size_t, [[maybe_unused]] T const &) const noexcept
Function call iterator that validates element.
Definition: iffl_list.h:722
iffl::flat_forward_list
Intrusive flat forward list container.
Definition: iffl_list.h:681
iffl::flat_forward_list::traits
TT traits
Element traits type.
Definition: iffl_list.h:2661
iffl::flat_forward_list_ref::find_element_after
const_iterator find_element_after(size_type position) const noexcept
Searches for an element after the element that contains given position.
Definition: iffl_list.h:2063
iffl::zero_then_variadic_args_t
Tag type for value - initializing first, constructing second from remaining arguments.
Definition: iffl_common.h:790
iffl::flat_forward_list_traits_traits::print_traits_info
static void print_traits_info() noexcept
Prints information about what traits_traits discovered about traits class.
Definition: iffl_list.h:629
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref(buffer_pointer *buffer, size_t buffer_size) noexcept
Constructor that checks if buffer contains a valid list and if it does then copies that list.
Definition: iffl_list.h:1582
iffl::offset_with_aligment
Vocabulary type that describes an offset in a larger buffer and template parameter that specifies ele...
Definition: iffl_common.h:693
iffl::flat_forward_list_ref::total_capacity
size_type total_capacity() const noexcept
Definition: iffl_list.h:2119
iffl::flat_forward_list_validate
constexpr std::pair< bool, flat_forward_list_ref< T, TT > > flat_forward_list_validate(char const *first, char const *end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
Forward declaration.
Definition: iffl_list.h:6385
FFL_CRASH_APPLICATION
#define FFL_CRASH_APPLICATION()
Fail fast with error ENOTRECOVERABLE(127 or 0x7f)
Definition: iffl_common.h:106
iffl::flat_forward_list_iterator_t::is_const_iterator
static constexpr auto const is_const_iterator
Is std::true_type{} if this iterator is an iterator for a T const, and std::false_type{} otherwise.
Definition: iffl_list.h:947
iffl::flat_forward_list::resize_buffer
void resize_buffer(size_type size)
Resizes buffer.
Definition: iffl_list.h:3322
iffl::flat_forward_list_ref::pointer
T * pointer
Pointer to element type.
Definition: iffl_list.h:1392
iffl::flat_forward_list_iterator_t::operator<=
constexpr bool operator<=(I const &other) const noexcept
Less than or equals operator used to compare to another iterator.
Definition: iffl_list.h:1146
iffl::buffer_t::validate
constexpr void validate() const noexcept
Fail fast is invariants are broken.
Definition: iffl_common.h:1146
iffl::flat_forward_list::shrink_to_fit
void shrink_to_fit(iterator const &it)
Removes unused padding of an element.
Definition: iffl_list.h:4437
iffl::flat_forward_list::used_capacity
size_type used_capacity() const noexcept
Definition: iffl_list.h:4834
iffl::flat_forward_list::begin
const_iterator begin() const noexcept
Definition: iffl_list.h:4283
iffl::flat_forward_list::end
const_iterator end() const noexcept
Definition: iffl_list.h:4336
iffl::flat_forward_list_traits_traits::set_next_offset
static constexpr void set_next_offset(char *buffer, size_t size) noexcept
Sets next element offset.
Definition: iffl_list.h:612
iffl::flat_forward_list::cbegin
const_iterator cbegin() const noexcept
Definition: iffl_list.h:4349
iffl::flat_forward_list::cend
const_iterator cend() const noexcept
Definition: iffl_list.h:4366
iffl::mpl::is_detected
typename details::detector< nonesuch, void, Operation, Arguments... >::value_type is_detected
is_detected will be either true_type or false_type, depending if Operation<Arguments....
Definition: iffl_mpl.h:335
iffl::flat_forward_list_ref::is_ref
static bool const is_ref
True if this is a ref and false if this is a view.
Definition: iffl_list.h:1382
iffl::flat_forward_list_iterator_t::operator=
constexpr flat_forward_list_iterator_t & operator=(flat_forward_list_iterator_t const &) noexcept=default
Default generated copy constructor.
iffl::flat_forward_list::erase
iterator erase(iterator const &it) noexcept
Erases element pointed by iterator.
Definition: iffl_list.h:3976
iffl::flat_forward_list::attach
void attach(buffer_view const &other_buff)
Takes ownership of a buffer.
Definition: iffl_list.h:3052
iffl::flat_forward_list::push_back
void push_back(size_type init_buffer_size, char const *init_buffer=nullptr)
Adds new element to the end of the list. Element is initialized by copping provided buffer.
Definition: iffl_list.h:3411
iffl::flat_forward_list_traits_traits::get_size
static constexpr size_with_padding_t get_size(char const *buffer) noexcept
Asks type traits to calculate element size.
Definition: iffl_list.h:574
iffl::flat_forward_list_iterator_t::operator++
constexpr flat_forward_list_iterator_t & operator++() noexcept
Prefix increment operator.
Definition: iffl_list.h:1184
iffl::flat_forward_list::flat_forward_list
flat_forward_list(attach_buffer, buffer_view const &other_buff, AA &&a=AA{}) noexcept
Constructor that takes ownership of a buffer.
Definition: iffl_list.h:2800
iffl::flat_forward_list_traits_traits::size_with_padding_t
size_with_padding< alignment > size_with_padding_t
Specialization of size_with_padding for this type alignment.
Definition: iffl_list.h:550
iffl::flat_forward_list_sizes::used_capacity
constexpr size_with_padding< ALIGNMENT_V > used_capacity() const
Capacity used by elements in the buffer.
Definition: iffl_common.h:762
iffl::flat_forward_list::find_element_after
iterator find_element_after(size_type position) noexcept
Searches for an element after the element that contains given position.
Definition: iffl_list.h:4773
iffl::flat_forward_list::const_pointer
T const * const_pointer
Pointer to const element type.
Definition: iffl_list.h:2636
iffl::flat_forward_list_sizes
Describes buffer used by container.
Definition: iffl_common.h:750
iffl::flat_forward_list::flat_forward_list
flat_forward_list(flat_forward_list_view< T, TT > const &view, AA &&a=AA{})
Copies element from the view.
Definition: iffl_list.h:2960
iffl::flat_forward_list_ref::const_buffer_value_type
buffer_value_type const const_buffer_value_type
When we do not intend to modify buffer we can treat it as a bag of const characters.
Definition: iffl_list.h:1467
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type * ptr_to_t(void *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:481
iffl::flat_forward_list_ref::flat_forward_list_ref
flat_forward_list_ref() noexcept
Default constructor.
Definition: iffl_list.h:1502
iffl::flat_forward_list_traits_traits::ptr_to_t
static value_type const * ptr_to_t(char const *ptr)
Casts buffer pointer to a pointer to the element type.
Definition: iffl_list.h:502
iffl::buffer_t::size
constexpr size_type size() const noexcept
Definition: iffl_common.h:1101
iffl::flat_forward_list_ref::end
iterator end() noexcept
Definition: iffl_list.h:1807
iffl::size_with_padding
Vocabulary type that describes an size and template parameter that specifies element's type alignment...
Definition: iffl_common.h:722
iffl::flat_forward_list::tail_shrink_to_fit
void tail_shrink_to_fit()
Resizes buffer to the used capacity.
Definition: iffl_list.h:3303
iffl::flat_forward_list_ref::iterator
flat_forward_list_iterator< T, TT > iterator
Type of iterator.
Definition: iffl_list.h:1482
FFL_CODDING_ERROR_IF_NOT
#define FFL_CODDING_ERROR_IF_NOT(C)
If expression is false then fail fast with error ENOTRECOVERABLE(127 or 0x7f)
Definition: iffl_common.h:120
iffl::flat_forward_list::assign
bool assign(char const *buffer_begin, char const *buffer_end)
Checks if buffer contains a valid list and if it does then copies that list.
Definition: iffl_list.h:3180
iffl::flat_forward_list_iterator_t::operator<
constexpr bool operator<(I const &other) const noexcept
Less than operator used to compare to another iterator.
Definition: iffl_list.h:1131
Generated by   doxygen 1.8.15