Created
June 11, 2013 07:56
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%%%------------------------------------------------------------------- | |
%%% @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