Skip to content

Instantly share code, notes, and snippets.

@lenary
Created June 11, 2013 07:56
Show Gist options
  • Save lenary/5755145 to your computer and use it in GitHub Desktop.
Save lenary/5755145 to your computer and use it in GitHub Desktop.
My alterations to `vorset2.erl` to make `merge/2` commute, and to get rid of some bugs
%%%-------------------------------------------------------------------
%%% @author Heinz Nikolaus Gies <heinz@licenser.net>
%%% @copyright (C) 2013, Heinz Nikolaus Gies
%%% @doc
%%% An Implementation of the OR Set (Observe Remove Set) CvRDT. It
%%% is optimized over the default implementation. Details about the
%%% optimization are based on the paper:
%%% http://www.cmi.ac.in/~madhavan/papers/mss-tr-2013.html
%%% @end
%%% Created : 1 Jun 2013 by Heinz Nikolaus Gies <heinz@licenser.net>
%%%-------------------------------------------------------------------
-module(vorset2).
-export([new/0, add/2, add/3, remove/2, merge/2, value/1, from_list/1, gc/1, equal/2]).
-record(orset2, {values :: [],
seen :: []}).
-opaque orset2() :: #orset2{}.
-export_type([orset2/0]).
%%%===================================================================
%%% Implementation
%%%===================================================================
%%--------------------------------------------------------------------
%% @doc
%% Creates a new empty OR Set.
%% @end
%%--------------------------------------------------------------------
-spec new() -> orset2().
new() ->
#orset2{values = orddict:new(),
seen = ordsets:new()}.
%%--------------------------------------------------------------------
%% @doc
%% Creates a new OR Set form a list by adding each element in the
%% list.
%% @end
%%--------------------------------------------------------------------
-spec from_list(list()) -> orset2().
from_list(L) ->
Values = lists:foldl(fun(E, D) -> orddict:store(E, ecrdt:id(), D) end, orddict:new()),
Seen = ordsets:from_list([orddict:fetch(E, Values) || E <- L]),
#orset2{values = Values,
seen = Seen}.
%%--------------------------------------------------------------------
%% @doc
%% Values an element to the OR set using the default ID function
%% provided by ecrdt:id().
%% @end
%%--------------------------------------------------------------------
-spec add(Element::term(), ORSet::orset2()) -> ORSet1::orset2().
add(Element, ORSet) ->
add(ecrdt:id(), Element, ORSet).
%%--------------------------------------------------------------------
%% @doc
%% Values an element to the OR set with a given master ID.
%% @end
%%--------------------------------------------------------------------
-spec add(ID::term(), Element::term(), ORSet::orset2()) -> ORSet1::orset2().
add(ID, Element, ORSet = #orset2{values = Values, seen = Seen}) ->
case ordsets:is_element(ID, Seen) of
true ->
ORSet;
false ->
ORSet#orset2{values = orddict:store(Element, ID, Values),
seen = ordsets:add_element(ID, Seen)}
end.
%%--------------------------------------------------------------------
%% @doc
%% Removes a element from the OR set.
%% @end
%%--------------------------------------------------------------------
-spec remove(Element::term(), ORSet::orset2()) -> ORSet1::orset2().
remove(Element, ORSet = #orset2{values = Values}) ->
ORSet#orset2{values = orddict:erase(Element, Values)}.
%%--------------------------------------------------------------------
%% @doc
%% Merges two OR Sets.
%% @end
%%--------------------------------------------------------------------
-spec merge(ORSet0::orset2(), ORSet1::orset2()) -> ORSetM::orset2().
merge(#orset2{values = ValuesA, seen = SeenA},
#orset2{values = ValuesB, seen = SeenB}) ->
#orset2{values = merge_values(ValuesA, ValuesB),
seen = merge_seen(SeenA, SeenB)}.
merge_values(ValuesA, ValuesB) ->
orddict:merge(fun(_E, IDA, IDB) -> max(IDA, IDB) end,
ValuesA, ValuesB).
merge_seen(SeenA, SeenB) ->
ordsets:union(SeenA, SeenB).
%%--------------------------------------------------------------------
%% @doc
%% Retrives the list of values from an OR Set.
%% @end
%%--------------------------------------------------------------------
-spec value(ORSet::orset2()) -> [Element::term()].
value(ORSet) ->
ordsets:from_list([E || {E, _} <- raw_value(ORSet)]).
%%--------------------------------------------------------------------
%% @doc
%% Garbage collects a OR set by removing all delted IDs.
%%
%% Be aware that this needs to be carried out syncronously or will
%% lead to unexpected results!
%% @end
%%--------------------------------------------------------------------
-spec gc(ORSet::orset2()) -> ORSetGCed::orset2().
gc(#orset2{values = Values}) ->
#orset2{values = Values,
seen = [ID || {_, ID} <- orddict:to_list(Values)]}.
%%%===================================================================
%%% Internal functions
%%%===================================================================
-spec raw_value(ORSet::orset2()) -> [{Element::term(), ID::term()}].
raw_value(#orset2{values = Values}) ->
orddict:to_list(Values).
equal(#orset2{values = Values1, seen=Seen1}, #orset2{values=Values2, seen=Seen2}) ->
Values1 == Values2 andalso ordsets:is_subset(Seen1, Seen2) andalso ordsets:is_subset(Seen2, Seen1).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment