kernel.core.history-buffer

History Buffer, HB for short. Serves as a central storage for operation metadata. Only a performance optimization and not essential.

Operations have to be stored in various data structures of a site. To avoid redundancy, all operation metadata is kept in the history buffer. The history buffer maps operation IDs to operations, so that other data structures only need to save an operation’s ID to be able to do a lookup. It is guaranteed to contain operation metadata for all operations that have not been garbage collected.

In contrast to other collaborative real-time editors, the history buffer is not ordered.

Without garbage collection, the history buffer may grow linearly over time.

_filter

(_filter HB fn)

Returns a set of all operations in the history buffer that match a given predicate in O(n). The predicate is passed an operation.

_remove

(_remove HB CO-ID)

Removes an operation from the history buffer in O(1).

initialize

(initialize)

Initializes a new history buffer without operations.

insert

(insert HB CO)

Inserts a newly received operation into the history buffer in O(1).

lookup

(lookup HB CO-ID)

Returns the operation for a given operation ID in O(1), if any.

lookup*

(lookup* HB CO-IDs)

For a given sequence of operation IDs, returns the associated operations in the same order in O(n).

remove-site

(remove-site HB site-ID)

Removes the given site from all operations’ vector clocks in the history buffer in O(n).