Re: О lock-free алгоритмах (+бонус)
От: Sni4ok  
Дата: 10.03.10 18:25
Оценка: 3 (1)
раз пошла такая пьянка, можно я свой контейнер запощу?

суть его- один поток может только писать, а много потоков при этом могут читать, контейнер может только увеличиваеться со временем, максимальный размер ограничен параметрами шаблонов, при этом память выделяется блоками как в std::deque, все итераторы дествительные ранее- остаются действительными в дальнейшем, если end() — указывал на элемент за 10м, то и когда контейнер увеличится- он будет указывать на элемент за 10м.

#include <boost/array.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/interprocess/detail/atomic.hpp>

//with follower can work one writer and many readers without synchronization
template<typename type, boost::uint32_t block_size = 16384, boost::uint32_t num_blocks = 16384>
class follower : boost::noncopyable
{
    typedef typename boost::array<type*, num_blocks> bulks_type;
    bulks_type bulks;
    mutable volatile boost::uint32_t num_elems;
public:
    follower() : num_elems(){
    }
    ~follower(){
        boost::uint32_t end_bulk = num_elems / block_size;
        boost::uint32_t end_element = num_elems % block_size;
        if(end_element)
            ++end_bulk;
        for(boost::uint32_t i = 0; i != end_bulk; ++i)
            delete[] bulks[i];
    }
    void push_back(const type& value){
        boost::uint32_t end_bulk = num_elems / block_size;
        boost::uint32_t end_element = num_elems % block_size;

        if(!end_element)
            bulks[end_bulk] = new type[block_size];

        try{
            (bulks[end_bulk])[end_element] = value;
        }
        catch(...){
            if(!end_element)
                delete bulks[end_bulk];
            throw;
        }

        boost::interprocess::detail::atomic_inc32(&num_elems);
    }
    class const_iterator :  public boost::iterator_facade<
        const_iterator, const type, boost::random_access_traversal_tag>
    {
        const bulks_type* bulks;
        boost::uint32_t element;

        friend class follower;
        friend class boost::iterator_core_access;

        void advance(boost::int32_t diff){
            element += diff;
        }
        boost::int32_t distance_to(const const_iterator& to) const{
            return to.element - element;
        }
        void increment(){
            ++element;
        }
        const type& dereference() const{ 
            boost::uint32_t end_bulk = element / block_size;
            boost::uint32_t end_element = element % block_size;
            return ((*bulks)[end_bulk])[end_element];
        }
        bool equal(const_iterator const& other) const{
            return element == other.element;
        }
        const_iterator(const bulks_type& bulks, boost::uint32_t element) : bulks(&bulks), element(element){
        }
    public:
        const_iterator(){}
    };
    const_iterator begin() const{
        return const_iterator(bulks, 0);
    }
    const_iterator end() const{
        return const_iterator(bulks, boost::interprocess::detail::atomic_read32(&num_elems));
    }
};
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.