corporate.fm
this repo has no description
garrison.corporate.fm
1defmodule Hobbes.VersionMap do
2 @moduledoc """
3 VersionMap is an ordered in-memory mapping of keys to versions
4 used by Resolvers to keep track of when a key or range was
5 last written to.
6
7 VersionMap is backed by an `:ets` table.
8 """
9
10 import Hobbes.Utils
11
12 @opaque t :: :ets.table
13
14 @doc """
15 Creates a new VersionMap.
16 """
17 @spec new :: :ets.table
18 def new do
19 :ets.new(:version_map, [:ordered_set, :private])
20 end
21
22 @doc """
23 Adds `keys` to the version map at `version`.
24
25 ## Examples
26
27 iex> add_writes(vm, 100, ["foo", "hello"])
28 :ok
29
30 """
31 @spec add_writes(VersionMap.t, non_neg_integer, [binary]) :: :ok
32 def add_writes(table, version, keys) when is_integer(version) and is_list(keys) do
33 Enum.each(keys, fn
34 {sk, ek} -> add_range(table, version, sk, ek)
35 k -> add_range(table, version, k, next_key(k))
36 end)
37 :ok
38 end
39
40 defp add_range(table, version, start_key, end_key) do
41 prev_key =
42 case :ets.prev_lookup(table, start_key) do
43 {_, [{sk, {ek, ver}}]} ->
44 cond do
45 ek <= start_key ->
46 # The previous range does not intersect with this range
47 :noop
48 ek <= end_key ->
49 # The previous range intersects with this range and must be trimmed to {sk, start_key}
50 :ets.insert(table, {sk, {start_key, ver}})
51 ek > end_key ->
52 # The previous range completely envelops this range and must be split into {sk, start_key} and {end_key, ek}
53 :ets.insert(table, {sk, {start_key, ver}})
54 :ets.insert(table, {end_key, {ek, ver}})
55 end
56
57 sk
58
59 :"$end_of_table" ->
60 # There is no previous range
61 nil
62 end
63
64 case clear_between(table, end_key, prev_key) do
65 {sk, {ek, ver}} ->
66 case sk < end_key do
67 true ->
68 # The last range of the clear intersects with the end of this range and must be trimmed to {end_key, ek}
69 :ets.delete(table, sk)
70 :ets.insert(table, {end_key, {ek, ver}})
71
72 false -> :noop
73 end
74
75 nil -> :noop
76 end
77
78 :ets.insert(table, {start_key, {end_key, version}})
79 end
80
81 defp clear_between(table, end_key, prev_key) do
82 case :ets.next_lookup(table, prev_key) do
83 {_, [{sk, {ek, ver}}]} ->
84 case ek <= end_key do
85 true ->
86 :ets.delete(table, sk)
87 clear_between(table, end_key, sk)
88 false ->
89 {sk, {ek, ver}}
90 end
91
92 :"$end_of_table" ->
93 nil
94 end
95 end
96
97 @doc """
98 Checks if a key or key range has been written to after `version`.
99
100 ## Examples
101
102 iex> written_after?(vm, 100, "foo")
103 false
104
105 iex> written_after?(vm, 100, {"foo", "zoo"})
106 true
107
108 """
109 @spec written_after?(VersionMap.t, non_neg_integer, binary | {binary, binary}) :: boolean
110 def written_after?(table, version, key_or_range)
111
112 def written_after?(table, version, key) when is_integer(version) and is_binary(key) do
113 case :ets.prev_lookup(table, next_key(key)) do
114 {_, [{_sk, {ek, ver}}]} -> ver > version and key < ek
115 :"$end_of_table" -> false
116 end
117 end
118
119 @spec written_after?(VersionMap.t, non_neg_integer, {binary, binary}) :: boolean
120 def written_after?(table, version, {start_key, end_key})
121 when is_integer(version) and is_binary(start_key) and is_binary(end_key) do
122 # Check first key, then scan
123 case written_after?(table, version, start_key) do
124 true -> true
125 false -> do_written_after_scan(table, version, start_key, end_key)
126 end
127 end
128
129 defp do_written_after_scan(table, version, prev_key, end_key) do
130 case :ets.next_lookup(table, prev_key) do
131 {_, [{sk, {_ek, ver}}]} ->
132 case sk < end_key do
133 true ->
134 # Range intersects, check for a conflict
135 case ver > version do
136 # Conflict found
137 true -> true
138 # Range does not conflict, keep scanning
139 false -> do_written_after_scan(table, version, sk, end_key)
140 end
141
142 # Range does not intersect, scan complete
143 false -> false
144 end
145
146 # Reached the end of the table without finding a conflict
147 :"$end_of_table" -> false
148 end
149 end
150
151 @doc """
152 Clears out keys with a version less than or equal to `version`.
153
154 ## Examples
155
156 iex> clear_old(vm, 100)
157 :ok
158
159 """
160 @spec clear_old(VersionMap.t, non_neg_integer) :: :ok
161 def clear_old(table, up_to_version) when is_integer(up_to_version) and up_to_version >= 0 do
162 :ets.select_delete(table, [{
163 {:"$1", {:"$2", :"$3"}},
164 [{:"=<", :"$3", up_to_version}],
165 [true],
166 }])
167 :ok
168 end
169
170 # For debugging and tests
171 @doc false
172 def dump(table) do
173 :ets.tab2list(table)
174 end
175end