Implements intrusive flat forward list. More...

#include <iffl_config.h>
#include <iffl_common.h>
#include <iffl_mpl.h>

Classes
class	iffl::flat_forward_list_traits< T >
	traits for an elements that are in the flat forward list More...

class	iffl::flat_forward_list_traits_traits< T, TT >
	traits for flat_forward_list_traits More...

class	iffl::flat_forward_list< T, TT, A >
	Intrusive flat forward list container. More...

class	iffl::flat_forward_list_ref< T, TT >
	Non owning container for flat forward list. More...

class	iffl::default_validate_element_fn< T, TT >

class	iffl::noop_validate_element_fn< T, TT >

class	iffl::flat_forward_list_iterator_t< T, TT >
	THis class implements forward iterator for intrusive flat forward list. More...

class	iffl::flat_forward_list_ref< T, TT >
	Non owning container for flat forward list. More...

class	iffl::flat_forward_list< T, TT, A >
	Intrusive flat forward list container. More...

Namespaces
	iffl::mpl
	intrusive flat forward list

	iffl
	intrusive flat forward list

Typedefs
template<typename T , typename TT = flat_forward_list_traits<T>>
using	iffl::flat_forward_list_iterator = flat_forward_list_iterator_t< T, TT >
	non-const iterator More...

template<typename T , typename TT = flat_forward_list_traits<T>>
using	iffl::flat_forward_list_const_iterator = flat_forward_list_iterator_t< std::add_const_t< T >, TT >
	const iterator More...

template<typename T , typename TT = flat_forward_list_traits<T>>
using	iffl::flat_forward_list_view = flat_forward_list_ref< T const, TT >
	Constant view to flat forward list.

template<typename T , typename TT = flat_forward_list_traits<T>>
using	iffl::pmr_flat_forward_list = flat_forward_list< T, TT, FFL_PMR::polymorphic_allocator< char > >
	Use this typedef if you want to use container with polymorphic allocator. More...

Functions
template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::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. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::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. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (char const first, char const end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (char first, char end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration.

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (T first, T end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (T const first, T const end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (unsigned char const first, unsigned char const end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (unsigned char first, unsigned char end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (void const first, void const end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT = flat_forward_list_traits<T>, typename F = default_validate_element_fn<T, TT>>
constexpr std::pair< bool, flat_forward_list_ref< T, TT > >	iffl::flat_forward_list_validate (void first, void end, F const &validate_element_fn=default_validate_element_fn< T, TT >{}) noexcept
	Forward declaration. More...

template<typename T , typename TT >
void	iffl::swap (flat_forward_list_ref< T, TT > &lhs, flat_forward_list_ref< T, TT > &rhs) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::iterator	iffl::begin (flat_forward_list_ref< T, TT > &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::begin (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::cbegin (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::iterator	iffl::end (flat_forward_list_ref< T, TT > &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::end (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::cend (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::iterator	iffl::last (flat_forward_list_ref< T, TT > &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::last (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT >
flat_forward_list_ref< T, TT >::const_iterator	iffl::clast (flat_forward_list_ref< T, TT > const &c) noexcept

template<typename T , typename TT , typename A >
void	iffl::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)

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::iterator	iffl::begin (flat_forward_list< T, TT, A > &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::begin (flat_forward_list< T, TT, A > const &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::cbegin (flat_forward_list< T, TT, A > const &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::iterator	iffl::end (flat_forward_list< T, TT, A > &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::end (flat_forward_list< T, TT, A > const &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::cend (flat_forward_list< T, TT, A > const &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::iterator	iffl::last (flat_forward_list< T, TT, A > &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::last (flat_forward_list< T, TT, A > const &c) noexcept

template<typename T , typename TT , typename A >
flat_forward_list< T, TT, A >::const_iterator	iffl::clast (flat_forward_list< T, TT, A > const &c) noexcept

Detailed Description

Implements intrusive flat forward list.

Author: Vladimir Petter

iffl github

This container is designed for POD types with following general structure:

                     ------------------------------------------------------------
                     |                                                          |
                     |                                                          V
| <fields> | offset to next element | <offsets of data> | [data] | [padding] || [next element] ...
|                        header                         | [data] | [padding] || [next element] ...

Examples:

FILE_FULL_EA_INFORMATION

typedef struct _FILE_FULL_EA_INFORMATION {
    ULONG  NextEntryOffset;
    UCHAR  Flags;
    UCHAR  EaNameLength;
    USHORT EaValueLength;
    CHAR   EaName[1];
} FILE_FULL_EA_INFORMATION, *PFILE_FULL_EA_INFORMATION;

FILE_NOTIFY_EXTENDED_INFORMATION

typedef struct _FILE_NOTIFY_EXTENDED_INFORMATION {
    DWORD         NextEntryOffset;
    DWORD         Action;
    LARGE_INTEGER CreationTime;
    LARGE_INTEGER LastModificationTime;
    LARGE_INTEGER LastChangeTime;
    LARGE_INTEGER LastAccessTime;
    LARGE_INTEGER AllocatedLength;
    LARGE_INTEGER FileSize;
    DWORD         FileAttributes;
    DWORD         ReparsePointTag;
    LARGE_INTEGER FileId;
    LARGE_INTEGER ParentFileId;
    DWORD         FileNameLength;
    WCHAR         FileName[1];
} FILE_NOTIFY_EXTENDED_INFORMATION, *PFILE_NOTIFY_EXTENDED_INFORMATION;

FILE_INFO_BY_HANDLE_CLASS output for the following information classes

FileIdBothDirectoryInfo
FileIdBothDirectoryRestartInfo
FileIoPriorityHintInfo
FileRemoteProtocolInfo
FileFullDirectoryInfo
FileFullDirectoryRestartInfo
FileStorageInfo
FileAlignmentInfo
FileIdInfo
FileIdExtdDirectoryInfo
FileIdExtdDirectoryRestartInfo

Output of NtQueryDirectoryFile

typedef struct _FILE_BOTH_DIR_INFORMATION {
    ULONG         NextEntryOffset;
    ULONG         FileIndex;
    LARGE_INTEGER CreationTime;
    LARGE_INTEGER LastAccessTime;
    LARGE_INTEGER LastWriteTime;
    LARGE_INTEGER ChangeTime;
    LARGE_INTEGER EndOfFile;
    LARGE_INTEGER AllocationSize;
    ULONG         FileAttributes;
    ULONG         FileNameLength;
    ULONG         EaSize;
    CCHAR         ShortNameLength;
    WCHAR         ShortName[12];
    WCHAR         FileName[1];
} FILE_BOTH_DIR_INFORMATION, *PFILE_BOTH_DIR_INFORMATION;

Or types that do not have next element offset, but it can be calculated.

Offset of the next element is size of this element data, plus optional padding to keep next element properly aligned

                     -----------------------------------
                     |                                 |
    (next element offset = sizeof(this element)        |
                     |   + padding)                    |
                     |                                 V
| <fields> | <offsets of data> | [data] | [padding] || [next element] ...
|       header                 | [data] | [padding] || [next element] ...

Examples:

CLUSPROP_SYNTAX property list

data structures

cluster property syntax

typedef union CLUSPROP_SYNTAX {
  DWORD  dw;
  struct {
      WORD wFormat;
      WORD wType;
  } DUMMYSTRUCTNAME;
} CLUSPROP_SYNTAX;

CLUSPROP_VALUE

typedef struct CLUSPROP_VALUE {
    CLUSPROP_SYNTAX Syntax;
    DWORD           cbLength;
} CLUSPROP_VALUE;

This module implements

function flat_forward_list_validate that can be use to deal with untrusted buffers. You can use it to validate if untrusted buffer contains a valid list, and to find entry at which list gets invalid. It also can be used to enumerate over validated elements.

flat_forward_list_iterator and flat_forward_list_const_iterator that can be used to enumerate over previously validated buffer.

flat_forward_list a container that provides a set of helper algorithms and manages buffer lifetime while list changes.

pmr_flat_forward_list is a an alias of flat_forward_list where allocator is polymorphic_allocator.

Interface that user have to implement for a type that will be stored in the container:

Since we are implementing intrusive container, user have to give us a helper class that implements following methods

Specifies alignment requirements for the type
constexpr static size_t const alignment{ TYPE_ALIGNMENT };
tell minimum required size am element must have to be able to query element size
constexpr static size_t minimum_size() noexcept
query offset to next element
constexpr static size_t get_next_offset(char const *buffer) noexcept
update offset to the next element
constexpr static void set_next_offset(char *buffer, size_t size) noexcept
calculate element size from data
constexpr static size_t get_size(char const *buffer) noexcept
validate that data fit into the buffer
constexpr static bool validate(size_t buffer_size, char const *buffer) noexcept

By default algorithms and containers in this library are looking for specialization of flat_forward_list_traits for the element type. For example:

namespace iffl {
    template <>
    struct flat_forward_list_traits<FLAT_FORWARD_LIST_TEST> {
        constexpr static size_t const alignment{ TYPE_ALIGNMENT };
        constexpr static size_t minimum_size() noexcept { <implementation> }
        constexpr static size_t get_next_offset(char const *buffer) noexcept { <implementation> }
        constexpr static void set_next_offset(char *buffer, size_t size) noexcept { <implementation> }
        constexpr static size_t get_size(char const *buffer) noexcept { <implementation> }
        constexpr static bool validate(size_t buffer_size, char const *buffer) noexcept {<implementation>}
    };
}

for sample implementation see flat_forward_list_traits<FLAT_FORWARD_LIST_TEST> @ test\iffl_test_cases.cpp and addition documentation in this mode right before primary template for flat_forward_list_traits definition

If picking traits using partial specialization is not preferable then traits can be passed as an explicit template parameter. For example:

using ffl_iterator = iffl::flat_forward_list_iterator<FLAT_FORWARD_LIST_TEST, my_traits>;

Debugging:

if you define FFL_DBG_CHECK_DATA_VALID then every method that modifies data in container will call flat_forward_list_validate at the end and makes sure that data are valid, and last element is where container believes it should be. Cost O(n).

If you define FFL_DBG_CHECK_ITERATOR_VALID then every input iterator will be checked to match to valid element in the container. Cost O(n)

You can use debug_memory_resource and pmr_flat_forward_list to validate that all allocations are freed and that there are no buffer overruns/under-runs

Classes

Namespaces

Typedefs

Functions

Detailed Description