InfAdoptedAlgorithm

InfAdoptedAlgorithm — adOPTed implementation

Stability Level

Unstable, unless otherwise indicated

Functions

Properties

InfBuffer * buffer Read / Write / Construct Only
InfAdoptedStateVector * buffer-modified-state Read
InfAdoptedStateVector * current-state Read
guint max-total-log-size Read / Write / Construct Only
InfUserTable * user-table Read / Write / Construct Only

Signals

void apply-request Run Last
void can-redo-changed Run Last
void can-undo-changed Run Last
void execute-request Run Last

Types and Values

Object Hierarchy

    GObject
    ╰── InfAdoptedAlgorithm

Includes

#include <libinfinity/adopted/inf-adopted-algorithm.h>

Description

InfAdoptedAlgorithm implements the adOPTed algorithm for concurrency control as described in the paper "An integrating, transformation-oriented approach to concurrency control and undo in group editors" by Matthias Ressel, Doris Nitsche-Ruhland and Rul Gunzenhäuser (http://portal.acm.org/citation.cfm?id=240305).

It is based on requests, represented by the InfAdoptedRequest class. If there is at least one local InfUser in the algorithm's user table, then you can create own reequests by the functions inf_adopted_algorithm_generate_request(), inf_adopted_algorithm_generate_request_noexec(), inf_adopted_algorithm_generate_undo() and inf_adopted_algorithm_generate_redo(). Remote requests can be applied via inf_adopted_algorithm_receive_request(). This class does not take care of transfering the generated requests to other users which is the scope of InfAdoptedSession.

The implementation is not tied to text editing. It can handle any operations implementing InfAdoptedOperation as long as they define sufficient transformation functions. The libinftext library provides operations for text editing, see InfTextInsertOperation and InfTextDeleteOperation.

Functions

inf_adopted_algorithm_new ()

InfAdoptedAlgorithm *
inf_adopted_algorithm_new (InfUserTable *user_table,
                           InfBuffer *buffer);

Creates a InfAdoptedAlgorithm.

Parameters

user_table

The table of participating users.

 

buffer

The buffer to apply operations to.

 

Returns

A new InfAdoptedAlgorithm.


inf_adopted_algorithm_new_full ()

InfAdoptedAlgorithm *
inf_adopted_algorithm_new_full (InfUserTable *user_table,
                                InfBuffer *buffer,
                                guint max_total_log_size);

Note that it is possible that request logs need to grow a bit larger than max_total_log_size in high-latency situations or when a user does not send status updates frequently. However, when all requests have been processed by all users, the sum of all requests in the logs is guaranteed to be lower or equal to this value.

Set to G_MAXUINT to disable limitation. In theory, this would allow everyone to undo every operation up to the first one ever made. In practise, this issues a huge amount of data that needs to be synchronized on user join and is too expensive to compute anyway.

The default value is 2048.

Parameters

user_table

The table of participating users.

 

buffer

The buffer to apply operations to.

 

max_total_log_size

The maxmimum number of operations to keep in all user's request logs.

 

Returns

A new InfAdoptedAlgorithm.


inf_adopted_algorithm_get_current ()

InfAdoptedStateVector *
inf_adopted_algorithm_get_current (InfAdoptedAlgorithm *algorithm);

Returns the current vector time of algorithm .

Parameters

algorithm

A InfAdoptedAlgorithm.

 

Returns

A InfAdoptedStateVector owned by algorithm .


inf_adopted_algorithm_generate_request_noexec ()

InfAdoptedRequest *
inf_adopted_algorithm_generate_request_noexec
                               (InfAdoptedAlgorithm *algorithm,
                                InfAdoptedUser *user,
                                InfAdoptedOperation *operation);

Creates a InfAdoptedRequest for the given operation, executed by user . The user needs to have the INF_USER_LOCAL flag set.

The operation is not applied to the buffer, so you are responsible that the operation is applied before the next request is processed or generated. This may be useful if you are applying multiple operations, but want to only make a single request out of them to save bandwidth.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

operation

A InfAdoptedOperation.

 

Returns

A InfAdoptedRequest that needs to be transmitted to the other non-local users.


inf_adopted_algorithm_generate_request ()

InfAdoptedRequest *
inf_adopted_algorithm_generate_request
                               (InfAdoptedAlgorithm *algorithm,
                                InfAdoptedUser *user,
                                InfAdoptedOperation *operation);

Creates a InfAdoptedRequest for the given operation, executed by user . The user needs to have the INF_USER_LOCAL flag set. operation is applied to the buffer (by user ).

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

operation

A InfAdoptedOperation.

 

Returns

A InfAdoptedRequest that needs to be transmitted to the other non-local users.


inf_adopted_algorithm_generate_undo ()

InfAdoptedRequest *
inf_adopted_algorithm_generate_undo (InfAdoptedAlgorithm *algorithm,
                                     InfAdoptedUser *user);

Creates a request of type INF_ADOPTED_REQUEST_UNDO for the given user and with the current vector time. The user needs to have the INF_USER_LOCAL flag set. It also applies the effect of the operation to the buffer.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

Returns

A InfAdoptedRequest that needs to be transmitted to the other non-local users.


inf_adopted_algorithm_generate_redo ()

InfAdoptedRequest *
inf_adopted_algorithm_generate_redo (InfAdoptedAlgorithm *algorithm,
                                     InfAdoptedUser *user);

Creates a request of type INF_ADOPTED_REQUEST_REDO for the given user and with the current vector time. The user needs to have the INF_USER_LOCAL flag set. It also applies the effect of the operation to the buffer.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

Returns

A InfAdoptedRequest that needs to be transmitted to the other non-local users.


inf_adopted_algorithm_translate_request ()

InfAdoptedRequest *
inf_adopted_algorithm_translate_request
                               (InfAdoptedAlgorithm *algorithm,
                                InfAdoptedRequest *request,
                                InfAdoptedStateVector *to);

Translates request so that it can be applied to the document at state to . request will not be modified but a new, translated request is returned instead.

There are several preconditions for this function to be called. to must be a reachable point in the state space. Also, requests can only be translated in forward direction, so request 's vector time must be causally before (see inf_adopted_state_vector_causally_before()) to .

Parameters

algorithm

A InfAdoptedAlgorithm.

 

request

A InfAdoptedRequest.

 

to

The state vector to translate request to.

 

Returns

A new or cached InfAdoptedRequest. Free with g_object_unref() when no longer needed.


inf_adopted_algorithm_receive_request ()

void
inf_adopted_algorithm_receive_request (InfAdoptedAlgorithm *algorithm,
                                       InfAdoptedRequest *request);

This function processes a request received from a non-local user and applies its operation to the buffer.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

request

A InfAdoptedRequest from a non-local user.

 

inf_adopted_algorithm_can_undo ()

gboolean
inf_adopted_algorithm_can_undo (InfAdoptedAlgorithm *algorithm,
                                InfAdoptedUser *user);

Returns whether user can issue an undo request in the current state. Note that if user is non-local, then the result of this function does not depend on the current state but on the state that we know user is guaranteed to have reached. This is because user might still issue an Undo request even if the max-total-log-size is already exceeded if user does not know yet that it is exceeded.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

Returns

TRUE if Undo is possible, FALSE otherwise.


inf_adopted_algorithm_can_redo ()

gboolean
inf_adopted_algorithm_can_redo (InfAdoptedAlgorithm *algorithm,
                                InfAdoptedUser *user);

Returns whether user can issue a redo request in the current state. Note that if user is non-local, then the result of this function does not depend on the current state but on the state that we know user is guaranteed to have reached. This is because user might still issue a Redo request even if the max-total-log-size is already exceeded if user does not know yet that it is exceeded.

Parameters

algorithm

A InfAdoptedAlgorithm.

 

user

A local InfAdoptedUser.

 

Returns

TRUE if Redo is possible, FALSE otherwise.

Types and Values

struct InfAdoptedAlgorithm

struct InfAdoptedAlgorithm;

InfAdoptedAlgorithm is an opaque data type. You should only access it via the public API functions.


struct InfAdoptedAlgorithmClass

struct InfAdoptedAlgorithmClass {
  void(*can_undo_changed)(InfAdoptedAlgorithm* algorithm,
                          InfAdoptedUser* user,
                          gboolean can_undo);

  void(*can_redo_changed)(InfAdoptedAlgorithm* algorithm,
                          InfAdoptedUser* user,
                          gboolean can_redo);

  void(*execute_request)(InfAdoptedAlgorithm* algorithm,
                         InfAdoptedUser* user,
                         InfAdoptedRequest* request,
                         gboolean apply);

  void(*apply_request)(InfAdoptedAlgorithm* algorithm,
                       InfAdoptedUser* user,
                       InfAdoptedRequest* request);
};

Signals for the InfAdoptedAlgorithm class.

Members

can_undo_changed ()

Default signal handler for the “can_undo_changed” signal.

 

can_redo_changed ()

Default signal handler for the “can_redo_changed” signal.

 

execute_request ()

Default signal handler for the “execute_request” signal.

 

apply_request ()

Default signal handler for the “apply_request” signal.

 

Property Details

The “buffer” property

  “buffer”                   InfBuffer *

The buffer to apply operations to.

Flags: Read / Write / Construct Only


The “buffer-modified-state” property

  “buffer-modified-state”    InfAdoptedStateVector *

The state in which the buffer is considered not being modified.

Flags: Read


The “current-state” property

  “current-state”            InfAdoptedStateVector *

The state vector describing the current document state.

Flags: Read


The “max-total-log-size” property

  “max-total-log-size”       guint

The maximum number of requests to keep in all user's logs.

Flags: Read / Write / Construct Only

Default value: 2048


The “user-table” property

  “user-table”               InfUserTable *

The user table.

Flags: Read / Write / Construct Only

Signal Details

The “apply-request” signal

void
user_function (InfAdoptedAlgorithm *algorithm,
               InfAdoptedUser      *user,
               InfAdoptedRequest   *request,
               gpointer             user_data)

This signal is emitted every time the algorithm applies a request.

Note a call to inf_adopted_algorithm_generate_request(), inf_adopted_algorithm_generate_undo() or inf_adopted_algorithm_generate_redo() always applies the generated request. In contrast, inf_adopted_algorithm_receive_request() might not apply the given request (if requests it depends upon have not yet received) or might apply multiple request (if the provided request fulfills the dependencies of queued requests).

Note also that the signal is not emitted for every request processed by InfAdoptedAlgorithm since inf_adopted_algorithm_generate_request_noexec() generates a request but does not apply it.

Parameters

algorithm

The InfAdoptedAlgorithm applying a request.

 

user

The InfAdoptedUser applying the request.

 

request

The InfAdoptedRequest being applied.

 

user_data

user data set when the signal handler was connected.

 

Flags: Run Last


The “can-redo-changed” signal

void
user_function (InfAdoptedAlgorithm *algorithm,
               InfAdoptedUser      *user,
               gboolean             can_undo,
               gpointer             user_data)

This signal is emitted every time the can-redo state of a local user in algorithm 's user table changed. The can-redo state defines whether user can generate a redo request (via inf_adopted_algorithm_generate_redo()) in the current situation, see also inf_adopted_algorithm_can_redo().

Parameters

algorithm

The InfAdoptedAlgorithm for which a user's can-redo state changed.

 

user

The InfAdoptedUser whose can-redo state has changed.

 

can_undo

Whether user can issue a redo request in the current state or not.

 

user_data

user data set when the signal handler was connected.

 

Flags: Run Last


The “can-undo-changed” signal

void
user_function (InfAdoptedAlgorithm *algorithm,
               InfAdoptedUser      *user,
               gboolean             can_undo,
               gpointer             user_data)

This signal is emitted every time the can-undo state of a local user in algorithm 's user table changed. The can-undo state defines whether user can generate an undo request (via inf_adopted_algorithm_generate_undo()) in the current situation, see also inf_adopted_algorithm_can_undo().

Parameters

algorithm

The InfAdoptedAlgorithm for which a user's can-undo state changed.

 

user

The InfAdoptedUser whose can-undo state has changed.

 

can_undo

Whether user can issue an undo request in the current state or not.

 

user_data

user data set when the signal handler was connected.

 

Flags: Run Last


The “execute-request” signal

void
user_function (InfAdoptedAlgorithm *algorithm,
               InfAdoptedUser      *user,
               InfAdoptedRequest   *request,
               gboolean             apply,
               gpointer             user_data)

This signal is emitted every time the algorithm executes a request. request is the request that algorithm will execute. request can generally not be applied to the current state, and it might also be an undo or redo request. The default handler of this signal computes the operation that can be applied to the buffer, and applies it when apply is TRUE by emitting “apply-request”.

Parameters

algorithm

The InfAdoptedAlgorithm executing a request.

 

user

The InfAdoptedUser executing the request.

 

request

The InfAdoptedRequest being executed.

 

apply

Whether the request will be applied after execution.

 

user_data

user data set when the signal handler was connected.

 

Flags: Run Last

See Also

InfAdoptedSession