jupiter_algorithm.hpp

Go to the documentation of this file.

/* libobby - Network text editing library
 * Copyright (C) 2005, 2006 0x539 dev group
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#ifndef _OBBY_JUPITER_ALGORITHM_HPP_
#define _OBBY_JUPITER_ALGORITHM_HPP_

#include <net6/non_copyable.hpp>
#include "jupiter_error.hpp"
#include "operation.hpp"
#include "record.hpp"

namespace obby
{

template<typename Document>
class jupiter_algorithm: private net6::non_copyable
{
public:
        typedef Document document_type;
        typedef operation<document_type> operation_type;
        typedef record<document_type> record_type;

        jupiter_algorithm();
        ~jupiter_algorithm();

        std::auto_ptr<record_type> local_op(const operation_type& op);

        std::auto_ptr<operation_type> remote_op(const record_type& rec);
protected:
        class operation_storage: private net6::non_copyable
        {
        public:
                operation_storage(unsigned int count,
                                  const operation_type& op);

                operation_storage(unsigned int count,
                                  std::auto_ptr<operation_type> op);

                unsigned int get_count() const;

                const operation_type& get_operation() const;

                void reset_operation(const operation_type& new_op);

                void reset_operation(std::auto_ptr<operation_type> new_op);
        protected:
                unsigned int m_count;
                std::auto_ptr<operation_type> m_operation;
        };

        void discard_operations(const record_type& rec);

        std::auto_ptr<operation_type> transform(const operation_type& op) const;

        void check_preconditions(const record_type& rec) const;

protected:
        typedef std::list<operation_storage*> ack_list_type;

        vector_time m_time;
        ack_list_type m_ack_list;
};

template<typename Document>
jupiter_algorithm<Document>::operation_storage::
	operation_storage(unsigned int count,
                          const operation_type& op):
        m_count(count), m_operation(op.clone() )
{
}

template<typename Document>
jupiter_algorithm<Document>::operation_storage::
	operation_storage(unsigned int count,
                          std::auto_ptr<operation_type> op):
        m_count(count), m_operation(op)
{
}

template<typename Document>
unsigned int jupiter_algorithm<Document>::operation_storage::get_count() const
{
        return m_count;
}

template<typename Document>
const typename jupiter_algorithm<Document>::operation_type&
jupiter_algorithm<Document>::operation_storage::get_operation() const
{
        return *m_operation;
}

template<typename Document>
void jupiter_algorithm<Document>::operation_storage::
	reset_operation(const operation_type& new_op)
{
        m_operation.reset(new_op.clone() );
}

template<typename Document>
void jupiter_algorithm<Document>::operation_storage::
	reset_operation(std::auto_ptr<operation_type> new_op)
{
        m_operation = new_op;
}

template<typename Document>
jupiter_algorithm<Document>::jupiter_algorithm():
        m_time(0, 0)
{
}

template<typename Document>
jupiter_algorithm<Document>::~jupiter_algorithm()
{
        for(typename ack_list_type::iterator iter = m_ack_list.begin();
            iter != m_ack_list.end();
            ++ iter)
        {
                delete *iter;
        }
}

template<typename Document>
std::auto_ptr<typename jupiter_algorithm<Document>::record_type>
jupiter_algorithm<Document>::local_op(const operation_type& op)
{
        std::auto_ptr<record_type> rec(new record_type(m_time, op) );
        m_ack_list.push_back(new operation_storage(m_time.get_local(), op) );
        m_time.inc_local();
        return rec;
}

template<typename Document>
std::auto_ptr<typename jupiter_algorithm<Document>::operation_type>
jupiter_algorithm<Document>::remote_op(const record_type& rec)
{
        check_preconditions(rec);
        discard_operations(rec);
        std::auto_ptr<operation_type> op(transform(rec.get_operation()) );
        m_time.inc_remote();
        return op;
}

template<typename Document>
void jupiter_algorithm<Document>::discard_operations(const record_type& rec)
{
        typename ack_list_type::iterator iter;
        for(iter = m_ack_list.begin(); iter != m_ack_list.end(); ++ iter)
        {
                if( (*iter)->get_count() < rec.get_time().get_remote() )
                        delete *iter;
                else
                        break;
        }

        m_ack_list.erase(m_ack_list.begin(), iter);

        // Verify sequence order (TCP should ensure this, if noone sends
        // corrupt packets).
        if(rec.get_time().get_local() != m_time.get_remote() )
        {
                throw jupiter_error(
                        "Sequence order mismatch: Incoming record's local "
                        "time does not match own remote time"
                );
        }
}

template<typename Document>
std::auto_ptr<typename jupiter_algorithm<Document>::operation_type>
jupiter_algorithm<Document>::transform(const operation_type& op) const
{
        std::auto_ptr<operation_type> new_op(op.clone() );

        for(typename ack_list_type::const_iterator iter = m_ack_list.begin();
            iter != m_ack_list.end();
            ++ iter)
        {
                const operation_type* existing_op =
                        &(*iter)->get_operation();
                operation_type* new_trans_op =
                        existing_op->transform(*new_op);
                operation_type* existing_trans_op =
                        new_op->transform(*existing_op);

                (*iter)->reset_operation(
                        std::auto_ptr<operation_type>(existing_trans_op)
                );

                new_op.reset(new_trans_op);
        }

        return new_op;
}

template<typename Document>
void obby::jupiter_algorithm<Document>::
	check_preconditions(const record_type& rec) const
{
        if(!m_ack_list.empty() &&
           rec.get_time().get_remote() < m_ack_list.front()->get_count() )
        {
                throw jupiter_error(
                        "Transformation precondition failed: Incoming remote "
                        "time is lower than oldest time in ack list"
                );
        }

        if(rec.get_time().get_remote() > m_time.get_local() )
        {
                throw jupiter_error(
                        "Transformation precondition failed: Incoming remote "
                        "time is greater than own local time"
                );
        }

        if(rec.get_time().get_local() != m_time.get_remote() )
        {
                throw jupiter_error(
                        "Transformation precondition failed: Incoming local "
                        "time does not match own remote time"
                );
        }
}

} // namespace obby

#endif // _OBBY_JUPITER_ALGORITHM_HPP_

---