<commit_before>/*
 * Copyright(c) Sophist Solutions, Inc. 1990-2021.  All rights reserved
 */
#ifndef _Stroika_Foundation_Containers_LockFreeDataStructures_forward_list_h_
#define _Stroika_Foundation_Containers_LockFreeDataStructures_forward_list_h_

#include "../../StroikaPreComp.h"

#include <atomic>
#include <optional>

/**
 *  Initial implementation copied from (so full credit for algorithms)
 *      https://codereview.stackexchange.com/questions/167252/c11-lock-free-collection-similar-to-stdforward-list-follow-up-2
 *      APPENTLY written by https://codereview.stackexchange.com/users/62314/brent
 *      All said about license we MIT licence, which is what Stroika uses, so I assume will be OK.
 * 
 *  TODO:
 *      @todo   Review https://en.wikipedia.org/wiki/Non-blocking_linked_list for more ideas on how to improve/fix
 *              this code.
 *      @todo   Review https://www.infoq.com/news/2014/10/cpp-lock-free-programming/ to make sure I've handled the
 *              parts he covers - at least - correctly.
 * 
 *              Sutters approach is fairly different. Worth considering, as much simpler. He probably showed all I really
 *              need - the definition of reference, and how that fits with push_front, pop_front... Could implement both ways
 *              with ifdefs?
 * 
 *              @see https://stroika.atlassian.net/browse/STK-723 for details on stuff todo above
 */

namespace Stroika::Foundation::Containers::LockFreeDataStructures {

    /**
     *  \brief lock-free, threadsafe singly linked list implementation (patterned after std::forward_list) - INTERNALLY SYNCRHONIZED
     * 
     * similar to std::forward_list, but thread safe and (partially) lock free
     * 
     *      o   all methods are thread safe, baring the destructor
     *      o   push, insert, emplace, pop, erase, and iterator increment/dereference are O(1)
     *      o   locks that do occur are per-element spin_ locks
     *      o   push, insert, emplace, clear, and separate operations are lock free.
     *      o   pop and erase are not lock free.
     *      o   begin, cbegin, and incrementing iterators are not lock free
     *      o   dereferencing iterators is lock free
     *      o   uses reference counting to preserve iterators (and values) of removed elements
     *      o   iterators of removed elements will increment to end()
     *      o   insert_after or emplace_after on a removed iterator will return end() to indicate failure.
     * 
     *  Methods from std::forward_list NYI
     *      o   get_allocator & allocators in general (probably doesn't make sense here)
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/before_begin
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/max_size
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/resize
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/merge
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/splice_after
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/remove
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/reverse
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/unique
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/sort
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/operator_cmp
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/erase2
     * 
     *  Methods from std::forward_list materially wrongly, incompletely implemented
     *      o   erase_after incomplete/wrong API
     * 
     *  See ALso:
     *      @see https://en.wikipedia.org/wiki/Non-blocking_linked_list
     *
     *  \note   \em Thread-Safety   <a href="Thread-Safety.md#Internally-Synchronized-Thread-Safety">Internally-Synchronized-Thread-Safety</a><commit_msg>cosmetic<commit_after>/*
 * Copyright(c) Sophist Solutions, Inc. 1990-2021.  All rights reserved
 */
#ifndef _Stroika_Foundation_Containers_LockFreeDataStructures_forward_list_h_
#define _Stroika_Foundation_Containers_LockFreeDataStructures_forward_list_h_

#include "../../StroikaPreComp.h"

#include <atomic>
#include <optional>

/**
 *  Initial implementation copied from (so full credit for algorithms)
 *      https://codereview.stackexchange.com/questions/167252/c11-lock-free-collection-similar-to-stdforward-list-follow-up-2
 *      APPENTLY written by https://codereview.stackexchange.com/users/62314/brent
 *      All said about license we MIT licence, which is what Stroika uses, so I assume will be OK.
 * 
 *  TODO:
 *      @todo   Review https://en.wikipedia.org/wiki/Non-blocking_linked_list for more ideas on how to improve/fix
 *              this code.
 *      @todo   Review https://www.infoq.com/news/2014/10/cpp-lock-free-programming/ to make sure I've handled the
 *              parts he covers - at least - correctly.
 * 
 *              Sutters approach is fairly different. Worth considering, as much simpler. He probably showed all I really
 *              need - the definition of reference, and how that fits with push_front, pop_front... Could implement both ways
 *              with ifdefs?
 * 
 *              @see https://stroika.atlassian.net/browse/STK-723 for details on stuff todo above
 */

namespace Stroika::Foundation::Containers::LockFreeDataStructures {

    /**
     *  \brief lock-free, threadsafe singly linked list implementation (patterned after std::forward_list) - INTERNALLY SYNCRHONIZED
     * 
     * similar to std::forward_list, but thread safe and (partially) lock free
     * 
     *      o   all methods are thread safe, baring the destructor
     *      o   push, insert, emplace, pop, erase, and iterator increment/dereference are O(1)
     *      o   locks that do occur are per-element spin_ locks
     *      o   push, insert, emplace, clear, and separate operations are lock free.
     *      o   pop and erase are not lock free.
     *      o   begin, cbegin, and incrementing iterators are not lock free
     *      o   dereferencing iterators is lock free
     *      o   uses reference counting to preserve iterators (and values) of removed elements
     *      o   iterators of removed elements will increment to end()
     *      o   insert_after or emplace_after on a removed iterator will return end() to indicate failure.
     * 
     *  Methods from std::forward_list NYI
     *      o   get_allocator & allocators in general (probably doesn't make sense here)
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/before_begin
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/max_size
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/resize
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/merge
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/splice_after
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/remove
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/reverse
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/unique
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/sort
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/operator_cmp
     *      o   https://en.cppreference.com/w/cpp/container/forward_list/erase2
     * 
     *  Methods from std::forward_list materially wrongly, incompletely implemented
     *      o   erase_after incomplete/wrong API
     * 
     *  See Also:
     *      @see https://en.wikipedia.org/wiki/Non-blocking_linked_list
     *
     *  \note   \em Thread-Safety   <a href="Thread-Safety.md#Internally-Synchronized-Thread-Safety">Internally-Synchronized-Thread-Safety</a>
{'fraction_non_alphanumeric': 0.09351509746464517, 'fraction_numerical': 0.008408714485921773, 'mean_word_length': 2.676814988290398, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 34, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5329141', 'n_tokens_mistral': 2422, 'n_tokens_neox': 2306, 'n_words': 599}