defmodule SData.MerkleList do @moduledoc""" A simple Merkle list store. Future improvements: - When messages are inserted other than at the top, all intermediate hashes change. Keep track of the mapping from old hashes to new hashes so that get requests can work even for hashes that are not valid anymore. - group items in "pages" (bigger bundles) """ defstruct [:root, :top, :cmp, :store] @doc""" Create a Merkle list store. `cmp` is a function that compares stored items and provides a total order. It must return: - `:after` if the first argument is more recent - `:duplicate` if the two items are the same - `:before` if the first argument is older """ def new(cmp) do root_item = :root root_hash = SData.term_hash root_item state = %SData.MerkleList{ root: root_hash, top: root_hash, cmp: cmp, store: %{ root_hash => root_item } } state end defp push(state, item) do new_item = {item, state.top} new_item_hash = SData.term_hash new_item new_store = Map.put(state.store, new_item_hash, new_item) %{ state | :top => new_item_hash, :store => new_store } end defp pop(state) do if state.top == state.root do :error else {item, next} = Map.get(state.store, state.top) new_store = Map.delete(state.store, state.top) new_state = %{ state | :top => next, :store => new_store } {:ok, item, new_state} end end @doc""" Insert a list of items in the store. A callback function may be specified that is called on any item that is sucessfully added, i.e. that wasn't present in the store before. """ def insert_many(state, items, callback \\ (fn _ -> nil end)) do items_sorted = Enum.sort(items, fn (x, y) -> state.cmp.(x, y) == :after end) insert_many_aux(state, items_sorted, callback) end defp insert_many_aux(state, [], _callback) do state end defp insert_many_aux(state, [item | rest], callback) do case pop(state) do :error -> new_state = push(insert_many_aux(state, rest, callback), item) callback.(item) new_state {:ok, front, state_rest} -> case state.cmp.(item, front) do :after -> new_state = push(insert_many_aux(state, rest, callback), item) callback.(item) new_state :duplicate -> insert_many_aux(state, rest, callback) :before -> push(insert_many_aux(state_rest, [item | rest], callback), front) end end end @doc""" Insert a single item in the store. A callback function may be specified that is called on the item if it is sucessfully added, i.e. it wasn't present in the store before. """ def insert(state, item, callback \\ (fn _ -> nil end)) do insert_many(state, [item], callback) end @doc""" Read some items from the state. The two parameters are optional: - qbegin : hash of the first item to read - qlimit : number of items to read """ def read(state, qbegin \\ nil, qlimit \\ nil) do begin = qbegin || state.top limit = qlimit || 20 get_items_list(state, begin, limit) end @doc""" Get the hash of the last item """ def top(state) do state.top end @doc""" Get the hash of the root item """ def root(state) do state.root end @doc""" Check if the store holds a certain item """ def has(state, hash) do Map.has_key?(state.store, hash) end defp get_items_list(state, begin, limit) do case limit do 0 -> {:ok, [], begin} _ -> case Map.fetch(state.store, begin) do {:ok, :root} -> {:ok, [], nil } {:ok, {item, next}} -> case get_items_list(state, next, limit - 1) do {:ok, rest, past} -> {:ok, [ item | rest ], past } {:error, reason} -> {:error, reason} end :error -> {:error, begin} end end end @doc""" Compare function for timestamped strings """ def cmp_ts_str({ts1, str1}, {ts2, str2}) do cond do ts1 > ts2 -> :after ts1 < ts2 -> :before str1 == str2 -> :duplicate str1 > str2 -> :after str1 < str2 -> :before end end end